中南大学计算机数据结构2013试题参考答案

中南大学考试试卷

2015--2016学年上学期期末考试试题 时间100分钟

数据结构课程56学时3.5学分 考试形式：闭卷

专业年级：计算机科学与技术10级总分100分，占总评成绩70%

姓名 班级 学号

（本试卷共四道大题，答案全部做在答题纸上！）

一、选择题(每题2分，共24分)

1. 以下数据结构中，属于线性结构的是（）

A．图 B．栈 C．二分查找树 D．森林

2. 用二分法查找表(a0,a1,a2,a3,……a16)，需要比较2次才能找到的元素是（）

A．a7和a16 B．a11和a13 C．a1和a14 D．a3和a12

3. 用概率查找改进查找效率，是经过多次查找以后使得（）

A．查找次数越少的元素查找速度越快 B．查找次数越少的元素越往前存放 C．查找次数越多的元素越往后存放 D．查找次数越多的元素查找速度越快 4. 二分查找要求元素( )

A.有序、顺序存储 B.有序、链式存储 C.无序、顺序存储 D.无序、链式存储 5. 已知pPre为指向链表中某结点的指针，pNew是指向新结点的指针，以下哪段伪码算法

是将一个新结点插入到链表中pPre所指向结点的后面？（） A．pPre->link = pNew; pNew = null;

B．pPre->link = pNew->link; pNew->link = null; C．pNew->link = pPre->link; pPre->link = pNew; D．pNew->link = pPre->link; pPre->link = null;

6. 在递归算法执行过程中，计算机系统必定会用到的数据结构是（）

A．队列 B．链表 C．栈 D．二叉树

7. 一个队列的入列序为ABCD，则队列的可能输出序列为（） A．DCBA B．ABCD C．ADCB D．CBDA

8. 具有10个叶子结点的二叉树中有（）个度为2的结点 A．8 B．9 C．10 D．11

9. 若A=10，B=4，C=6，D=4，E=15则后缀表达式“AB*CD+-E+”的值为( )。

A．45 B．31 C．53 D．65

10. 在一个具有n个顶点的无向图中,要连通全部顶点至少需要（）条边。

A．n B．n+1 C．n-1 D．n/2 11. 对数据序列｛15,9,7,8,20,-1,4｝进行排序，进行一趟后数据的排序变为｛9,15,7,8,20,-1,4｝ ，则采用的是（）算法。 A．直接选择排序 B．冒泡排序 C．直接插入排序 D．希尔排序

12. 以下哪个算法可以判断出一个有向图中是否有回路（）。

A．广度优先遍历B．拓扑排序C．求最短路径D．求关键路径 1. 2. 3. 4. 5. 6. B D D A C C 7. 8. 9. 10. 11. 12. B B A C C B 二、填空题(每题2分，共20分)

1． 一个算法的时间效率表达式是40n2+2log2n+1000, 这个算法的大O表达式是。

2． 向一个长度为n的顺序表中的第i个元素（1≤i≤n）之前插入一个元素时，需要向后移

动_____ _____个元素。

3． 如果经常对线性表进行插入和删除运算，则最好采用 存储结构。 4． 在有n个叶子结点的哈夫曼树中，总结点数是_______。 5． 带头结点的双循环链表L为空表的条件是_______。

6． 用数组Q（其下标在0…n-1之间，共有n个元素）表示一个循环队列，front 为当前队

头元素的前一个位置，rear为队尾元素的位置，假设队列中的元素个数总小于n，则求队列中元素个数的公式是_____________________。

7． 在双链表中，在指针P所指结点前面插入一个结点*S时的语句序列是：

S->next=P;S->prior=P->prior;P->prior=S;_______； 8． 表达式a*(b+c)-d的后缀表达式是。

9． 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。

void bubble(intr[n]) {

for(i=1;i<=n-1; i++) {

for(exchange=0,j=0; j

if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if (exchange==0) return； } } 10． 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。

struct record{int key; int others;}; intbisearch(struct record r[ ], int k)

{

int low=1,mid,high=n; while(low<=high) {

________________________________; if(r[mid].key==k) return(mid);

else if(r[mid].key>k) high=mid-1;else low=mid+1; }

return(0); } O(n2) （n-i+1） 链式 2n-1 L->next=L->prior 或 L->next=L (Q.rear-Q.front+n)%n S->prior->next=S abc+*d- d != i low>high 三、应用题(每题9分，共36分)

1. 已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。

2. 如下图所示为5个乡镇之间的交通图，乡镇之间道路的长度如图中边上所注。现在要在

这5个乡镇中选择一个乡镇建立一个消防站，问这个消防站应建在哪个乡镇，才能使离消防站最远的乡镇到消防站的路程最短。试回答解决上述问题应采用什么算法，并写出应用该算法解答上述问题的每一步计算结果。

135641226394

由弗洛伊德（Floyd）算法进行求解，具体步骤如下：

D(?1)?0129?3??0129?1206????1206???(0)??9604??，D??960?????406?????4???3??60???31512??406??4063?15??12?； ?6?0??D(1)?0129?1206???960????4??315123??0129133??12061015?15????(2)12?，D??960412?； ???6?1310406???0???3151260??D(3)?0129133??012993??12061015??12061015?????(4)??960412?，D??960410?。 ????1310406910406???????3151060???3151060??设乡镇vi到其他各乡镇的最远距离为max_disdance(vi)，则有：max_disdance(v1)=12，

max_disdance(v2)=15，max_disdance(v3)=10，max_disdance(v4)=10，max_disdance(v5)=15，所以可知消防站应建在v3或v4乡镇，才能使离消防站最远的乡镇到消防站的路程最短。

3. 设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：

（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，试回答下列问题： ⑴画出哈希表的示意图；

⑵若查找关键字63，需要依次与哪些关键字进行比较？ ⑶若查找关键字60，需要依次与哪些关键字比较？

⑷假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 解：（1）画表如下：3分 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 （2）查找63,首先要与H(63)=63=15号单元内容比较，即63vs31 ,no; 2分 然后顺移，与46,47,32,17,63相比，一共比较了6次！

（3）查找60,首先要与H(60)=60=12号单元内容比较，但因为12号单元为空（应

当有空标记），所以应当只比较这一次即可。2分

（4）对于黑色数据元素，各比较1次；共6次； 2分

对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次， 所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55

4. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，

0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。 解：方案1；哈夫曼编码

先将概率放大100倍，以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】,??19,21,32

（100）

0 1 （40）（60）

0 1 0 1 19 21 32 （28）

19 21 32 （17） （11）

0 1 7 10 6 （5）

0 1 0 1 2 3 7 10 6 0 1

2 3

方案比较：

字母编号 对应编码 出现频率 字母编号 对应编码 出现频率 1 1100 0.07 1 000 0.07 2 00 0.19 2 001 0.19 3 11110 0.02 3 010 0.02 4 1110 0.06 4 011 0.06

10 0.32 5 100 0.32 5 11111 0.03 6 101 0.03 6 7 110 0.21

方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3

结论：哈夫曼编码优于等长二进制编码

四、算法设计题(每题10分，共20分)

1． 设有一组初始记录关键字序列（K1，K2，?，Kn），要求设计一个算法能够在O(n)的时

间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。

voidquickpass(int r[], int s, int t) {

int i=s, j=t, x=r[s]; while(i

while (ix) j=j-1; if (i

r[i]=x; }

2． 试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径

（i<>j）。注意：算法中涉及的图的基本操作必须在存储结构上实现。

在有向图中，判断顶点Vi和顶点Vj间是否有路径，可采用遍历的方法，从顶点Vi出发，不论是深度优先遍历（dfs）还是宽度优先遍历（bfs），在未退出dfs或bfs前,若访问到Vj，则说明有通路，否则无通路。设一全程变量flag。初始化为0，若有通路，则flag=1。 算法 int visited[]=0; //全局变量，访问数组初始化 intdfs(AdjList g , vi)

//以邻接表为存储结构的有向图g，判断顶点Vi到Vj是否有通路,返回1或0表示有或无

{ visited[vi]=1; //visited是访问数组，设顶点的信息就是顶点编号。 p=g[vi].firstarc; //第一个邻接点。 while ( p!=null) { j=p->adjvex;

if (vj==j) { flag=1; return（1）;} //vi 和vj有通路。 if (visited[j]==0) dfs(g,j); p=p->next； }//while if (!flag) return(0); }//结束

本文来源：https://www.bwwdw.com/article/8gx6.html