数据结构试卷(二)

数据结构试卷(二)

技术杂学铺 文

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

编写:小兰 张秣 方方

排版: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构成一个圈,故本题不存在一个拓扑排序

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180121G09WIF00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券