数据结构试卷（二）

数据结构试卷（二）

技术杂学铺 文

看技术教程就去技术杂学铺

编写：小兰 张秣 方方

排版：M小白

内容品控：小楠

前言：写一套卷子分析、审查、排版消耗的时间是巨大的。如果觉得好，请点个订阅点个赞。

1.一个函数具有下列形式，判断递归调用是否正确，如果不正确，应该如何修改？分析该函数的平均时间复杂度，以O的方式给出，给出分析过程。

分析：本题就是一个二分调用的过程，不过并未实现什么功能，同时代码存在一些问题，现做修改如下

解释：

（1）first >= last，不难理解在后面的调用中first = last。

（2）第二处修改，由于数组指针已经修改，这里会超界，举例如下：

假设 a[10] = ，first = 0, last = 9, 那么原始代码会执行func(&a[5], 5, 9)，这时传入函数的数组头指针已经修改为a+5，而不是a，因此后面的调用a[(first+last)/2]之时就是 a+5+7，超过原始界限，其中a+5为传入函数的指针。因此需要修改first = 0，last = (last – first – 1)/2

或者也可以改为func(a,(first+last)/2,last)

注：读者可自行打印a[(first + last)/2]测试，笔者代码中测试了两种极限情况

具体代码见：https://github.com/tofar/data-structure/tree/master/数据结构复习卷/2017_1.c

2. 将数组 调整为最大堆并使用堆排序将其排为升序数组。要求用图形和数组表示过程。

分析：考察最大堆排序及其数组表示

具体步骤：

a) 以最小堆的构建过程为例，从最后一个非叶节点开始

b) 比较其两个儿子节点，找出较大的儿子节点

c) 比较 较大的儿子节点 与该节点，如果子节点较大则上滤交换位置

d) 交换过的元素应一路交换至其正确位置，即交换后与其子节点进行堆序性的检查

e) 重复以上步骤，比较完一层之后进行上一层的比较，直到与根节点比较完成

P.S .最小堆可参考《数据结构与算法分析：C语言描述》 P140 构建堆过程 （或数据结构试卷（一）第四题）

3.编写C语言函数 int is_index(int a[], int n) 判断升序排列的整数数组a（长度为n）中是否存在a[i] = i；如果存在，返回TRUE，否则返回FALSE。说明程序的时间复杂度是多少。

题解：

顺序求解：

只需使用一个for循环遍历数组是否存在满足 a[i] == i条件的即可，时间复杂度为O(n)

分治求解：

前提：升序数组中元素不重复

由于本题中的数组是升序排列，故可用分治算法来减少时间复杂度，分治算法只需每次判断中间元和索引i的关系，即可将搜索空间折半。

具体代码见：https://github.com/tofar/data-structure/tree/master/数据结构复习卷/2017_3.c

4.对下列整数进行基数排序，，要求标出所使用的基以及每一趟桶式排序中的元素变化过程。

题解：

桶式排序：对于一组小于m的正整数进行排序，准备m个桶，将每个元素放进对应的桶里，处理过所有数之后按桶的顺序输出所有元素。

基数排序：桶式排序的推广，桶式排序的缺点在于需要的桶太多，基数排序针对位数进行多趟桶式排序，第一趟根据个位上的数将元素加入相应的表头，第二趟考察十位，第三趟考察百位，直到所有的元素都被插入到0表头，整个排序过程结束。顺序输出0表头。

（编者按：由于编者的强迫症所以下图的表均为满表，实际实现过程中使用n*n的数组会造成空间上的浪费，而使用链表替代，故以下的表均可以变换为链表的形式，可参考散列。）

5. 用分治算法的思想计算3^192的十位数是多少？说明算法的步骤，给出计算过程。

分治解法：

思想如下：对于mk只需分别求出m^k/2和m^(k-k/2)的最后两位数，假设为x1,x2，那么mk的最后两位数一定是x1和x2的乘积的最后两位数，如此不断分治即可。

具体代码如下：

具体代码见：https://github.com/tofar/data-structure/tree/master/数据结构复习卷/2017_5.c

6.利用分治算法的思想编写C语言函数int find_median(int a[], int m, int b[], int n)，在长度分别为m和n的两个排序整型数组中找出总体的中位值，其中a为升序排列，b为降序排列。说明时间复杂度。中位值定义为第

（m+n）/ 2 小的元素。

本题参照 数据结构试卷（一） 第六题题解即可，只是在开始的时候计算时，取k = （m+n）/ 2，其他一模一样。

主要代码如下：

具体代码见：https://github.com/tofar/data-structure/tree/master/数据结构复习卷/2017_6.c

7.已知一棵二叉树的先序遍历结果为ABCDEFGHI，中序遍历结果为CEDBAGFHI，结点由字母表示。这棵树是否存在？如果存在，请构造出这棵树并标出构造过程。如果不存在，请说明为什么。

不存在，原因如下：

先序遍历第一个字母为A，中序遍历的第一个字母为C，故可以确定最深的树序列为 A->B->C (左子树)，由中序遍历可知C的父节点为E，与前面的矛盾（C的父节点为B），故不存在。

8. 一组符号Si，i = 1 .. 12，其出现的频率分别是3，14，6， 8，15，25，35，12，65，13，33和5。请设计出相应的Huffman编码。要求画出Huffman树，并给出编码。

哈夫曼编码过程如下：

（1） 首先排序如下：3, 5, 6, 8, 12, 13, 14, 15, 25, 33, 35, 65

（2） 第一次合并： 6, 8, *8(3+5), 12, 13, 14, 15, 25, 33, 35, 65

（3） 第二次合并： *8(3+5), 12, 13, 14, *14(6+8), 15, 25, 33, 35, 65

（4） 第三次合并： 13, 14, *14(6+8), 15, *20(8+12), 25, 33, 35, 65

（5） 第四次合并： *14(6+8), 15, *20(8+12), 25, *27(13+14), 33, 35, 65

（6） 第五次合并： *20(8+12), 25, *27(13+14), *29(14+15), 33, 35, 65

（7） 第六次合并： *27(13+14), *29(14+15), 33, 35, *45(20+25), 65

（8） 第七次合并： 33, 35, *45(20+25), *56(27+29), 65

（9） 第八次合并： *45(20+25), *56(27+29), 65, *68(33+35)

（10） 第九次合并： 65, *68(33+35), *101(45+56)

（11） 第十次合并： *101(45+56), *133(65+68)

（12） 第十一次合并： *234（101+133）

Huffman树如下：

9. 编写一个C语言函数int count_nodes(BinTreeNode *root)返回以root为根的二叉树中节点的个数。

题解：

本题只需使用一个递归返回左子树和右子树的节点数再加 1即可

count_nodes(root->left) + 1 + count_nodes(root->right)

代码如下：

10.写出下图的邻接链表表，判断是否存在拓扑排序；如果存在，则给出它的一个拓扑排序；否则，说明原因。

题解：

参照《数据结构与算法分析：C语言描述》 的217页的拓扑排序

注：图片中序号按照从左到右从上到下标号，即

1 2 3 4

5 6 7 8

9 10 11 12

由于途中v2->v3->v7->v2构成一个圈，故本题不存在一个拓扑排序