中南大学计算机数据结构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和a13C．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．9C．10 D．11

9.若A=10，B=4，C=6，D=4，E=15则后缀表达式“AB*CD+-E+”的值为( )。A．45 B．31C．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．求关键路径

⼆、填空题(每题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);}

三、应⽤题(每题9分，共36分)

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

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

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

由弗洛伊德（Floyd ）算法进⾏求解，具体步骤如下：∞∞∞∞∞∞∞∞=-0636044069601239120)1(D ，∞∞∞∞=0612

15360412406915601239120)0(D ； ∞∞∞∞=06

1215360412406915601239120)1(D ，??

=06121536041013124069151060123139120)

2(D ； =06101536041013124069151060123139120)3(D ，

=061015360410910406915106012399120)

4(D 。 设乡镇v i 到其他各乡镇的最远距离为max_disdance(v i )，则有：max_disdance(v 1)=12，

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

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

（10，24，32，17，31，30，46，47，40，63，49）造出Hash 表，试回答下列问题： ⑴画出哈希表的⽰意图；⑵若查找关键字63，需要依次与哪些关键字进⾏⽐较？ ⑶若查找关键字60，需要依次与哪些关键字⽐较？⑷假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

然后顺移，与46,47,32,17,63相⽐，⼀共⽐较了6次！

（3）查找60,⾸先要与H(60)=60%16=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）（40）（60）19 21

32 （28）

（）（11）7 10 6 （5）2 3⽅案⽐较：

⽅案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 (iwhile (i}r[i]=x;}

2．试写⼀算法，判断以邻接表⽅式存储的有向图中是否存在由顶点Vi到顶点Vj的路径（i<>j）。注意：算法中涉及的图的基本操作必须在存储结构上实现。

在有向图中，判断顶点Vi和顶点Vj间是否有路径，可采⽤遍历的⽅法，从顶点Vi出发，不论是深度优先遍历（dfs）还是宽度优先遍历（bfs），在未退出dfs或bfs前,若访问到Vj，则说明有通路，否则⽆通路。设⼀全程变量flag。初始化为0，若有通路，则flag=1。

算法int visited[]=0; //全局变量，访问数组初始化int dfs(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； }//whileif (!flag) return(0);}//结束