江南大学计算机真题回忆版

2016年江南大学计算机专业课

1.函数vr6174是对卡布列克运算的验证程序，所谓卡布列克运算，

是指任意一个四位数，只要它们各个位上的数字不全相同，就有这样的规律：

（1）将组成该四位数的四个数字由大到小排列，形成由这四个数字构成的最大的四位数；

（2）将组成该四位数的四个数字由大到小排列，形成由这四个数字构成的最小的四位数（如果四个数中含有0，则得到的数不足

四位）；

（3）求两个数的差，得到一个新的四位数（高位0保留）如果当n=5346时调用vr6174（n），便会输出如下结果：

6543-3456=3078

8730-378=8352

8532-2358=6174

用c语言编程完成程序，在主函数vr（6174）中要调用divide 函数对其四位数进行分解，分别求出各位上的数，调用

max—min函数求出最大值和最小值，把得到的值放入数组

signdigit中。

2.编写算法将带头节点的单链表中值重复的节点删除，使所得的链

表中各节点值不同。

3.给定一组数列（15,8,10,21,6,19,3）分别代表字符A , B , C , D ,

E ,

F , G出现的频度，试叙述建立哈夫曼树的算法思想，画出哈

夫曼树，给出各字符的编码值，并说明这种编码的优点。

4.有关键字为21,15,20,14,10,2的一组记录，在末尾插入关键字5，

将其关键字转换成最大堆和最小堆。

（1）画出最大堆和最小堆；

（2）写出最大堆和最小堆得基本思想；

（3）用程序实现运算编码。

5.已知两个定长数组，它们分别存放两个非降序有序序列，请编写

程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序（非降序）并且第一数组中所有的数都不大于第三个数组中的任意一个数，注意，不能另开辟数组，也不能对任意一个数组进行降序操作。例如：

第一个数组为：4 , 12 , 28

第二个数组为：1 , 7 , 9 , 29 , 45

输出结果为：1 , 4 , 7-----------------第一个数组

9 , 12 , 28 , 29 , 45-----第二个数组

6.编程实现二分查找算法，并写出二分查找的代码。

7.3个矩阵A1、A2、A3的行列分别为10×100、100×5/5×50，其

加括号的方法一共有两种，具体如下：(（A1A2）A3)、（A1(A2A3)），两种加括号方法所需要乘法的次数分别为：(（A1A2）A3)：

10×100×5+5×10×50=7500 ；（A1(A2A3)）：

5×100×50+100×10×50=75000. 那么，矩阵连乘问题就是对于给定n个连乘的矩阵，找出一种加括号的方法，使得矩阵连乘的计算量最小。

（1）写出算法思想

（2）写出运行程序

8.一辆汽车加满油后可以行驶N千米，旅游途中有若干个加油站，

指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在哪些加油站停靠加油。