华中科技大学计算机学院数据结构(计算机专业)试题

1、华中科技大学计算机学院华中科技大学计算机学院 PAGE 4 PAGE 41数据结构试卷 (A 卷)2010 2011 年度第二学期计算机学院班级 学号 姓名 考试时间：2011年 月日考试形式：闭卷题号一二三四五六七八总分核对人题分得分101010123210610100得分评卷人一、单项选择题(从下列各题四个备选答案中选出一个正确答案, 将其代号(A,B,C,D)写在下表中,每小题 1 分,共 10 分得分评卷人题号题号答案12345678910对于栈的进栈和出栈运算，采用存储结构时运算效率最高A单链表B容量足够大的顺序表C单向循环链表D双向循环链表 2链式队列和顺序队列比较，具有这个优势A

2、进队操作方便B出队操作方便 C通常不会出现满队列情况 D求队列元素个数方下列关于串的叙述中，正确的是。A2个串的长度相等，则2 个串相等B空串至少包一个空格C替换操作可以实现字符的删除D一个串的长度至少是二叉树在线索化后，下列问题中相对难解决的是A先根线索二叉树中求先根后继 B中根线索二叉树中求中根前趋 C中根线索二叉树中求中根后继 D后根线索二叉树中求后根后继5对序列（30，26，18，16，5，66）进行2 遍排序后得到序列（5，16，1，26，30，66。A选择B冒泡 C插入D归并在下列排序算法中，算法可能出现如下情况：在最后一趟排序之前所有元素均不在其最终的位置上。A堆排序B快速排序

3、C冒泡排序 D插入排7由4 个结点可以组成棵不同形态的二叉树。A10B12C14D16对包含n 个元素的散列表进行检索，平均查找长度为。AO(logn)BO(n)CO(nlogn)D不直接依赖于9广义表(a,(b),c),(),(d),(e),f),()的长度是。A2B3C4D5 10向图一定是。A连通图B树图C有回路的连通图D完全图得分评卷人二、填空题得分评卷人题号题号答案12345678910具有n 个单元、用首尾指针、无标志位的循环队列中，队满时共有元素。设顶点数为n，弧数为e的有向图的用邻接表存储，求顶点值为V的顶点的度的算法时间复杂度为。某哈夫曼树有11个结点，则它有个度为2 的结点

4、。设森林T 中有三棵树，第一、二、三棵树的结点个数分别是那当把森林转换成二叉树后，其根结点的右子树上有个结点。当线性表经常进行插入和删除操作时，应该选择使用存储结构。设栈S 和队列Q的初始状态为空，元素abcdef依次通过栈S，一个元素出栈后即进入队列Q。若这6 个元素出队列的顺序是b、d、c、f、e、a， 则栈S 的容量至少应该是。满足先根遍历序列为a、b、c，后根序列为c、b、a的二叉树共有棵。按广度优先搜索遍历图的算法需要借助的辅助数据结构是。高度为4 的平衡二叉树至少有个结点。对n 个元素的序列进行简单选择排序，最多进行次元素的交换。得分得分评卷人(判断下列各题叙述的正确性,用表示正确

5、，表示错误，每小题 1 分,共 10 分)题号答案12345678910可以以随机方式访问以三元组方式存放的稀疏矩阵的非零元素。h h 层的结点数，一定能求二叉树的结点数。算法分析的目的之一是分析算法的效率以求改进。正确性是算法的特征之一。线性表的逻辑结构与存储顺序总是一致的。在循环链表中，任何一个结点的指针部分都指向其直接后继元素的结点。将递归算法改写成非递归算法时，通常需要使用的数据结构为栈。n 条弧的有向图不一定是强连通图。是二叉排序树。快速排序方法的每一趟都能找到一个元素把它放到最终的位置上。得分评卷人四、存储结构图(要求标明各结点的数据域、指针域、权值等， 每小题 6 分，共 12

6、分得分评卷人T的一种线索二叉树逻辑362355NULLNULL362355NULLNULL123066二叉排序TA4A4C48910D6B8EG得分得分评卷人五、求解问题(8 32 分)1n 2n-1 SA1m（1）m 值是什么？（2）Ai，jSAk中，试写出由下标(i，j)k 的转换公式。000 0000 a1,na0 a2,n-1 2,n2,n+100 . a .a .a. 0 i,n-i+1i,ni,n+i-1aaaa n,1 n,2n,n2如下图所示为有序表试问该判定树是否正确？如果正确，说明理由，错误则指出错误处并给出正确结 果。4444156810336770216086(6372

7、8868663843),画出该平衡二叉排序树写出平衡二叉排序树T的中序遍历序列,(3)素的查找概率相等,计算查找成功时的平均查找长度。 华中科技大学计算机学院 PAGE 10 PAGE 1010A出发求图的深度遍历的结果。A2A2361B4B45C16D25E24F133456得分评卷人六、证明题(每小题 5 分，共 10 分) 1得分评卷人2证明有 n 个结点的完全二叉树的高度为 log2(n+1)。得分评卷人七、编程题(6 分得分评卷人CreateBiTree 相关说明如下：typedefstruct node ElemType data;struct node *lchild,*rchi

8、ld; NODE,*bitTree;bitTree CreateBiTree(ElemType X，ElemType Y，int n);/*型说明,X、Yn个结点的二叉树的先根和中根遍历序列*/得分评卷人八、阅读并改进算法(每小题 5 分，共 10 分得分评卷人#define N 10 void main() int aN =1,4,5,6, 8,10,11,13,15,20 , bN,i,j,k;scanf（”%d”,&k）;for(i=0;iN;i+) i=j=0;while(iN & jN)bN-i-1=k-ai;if (ai=bj)break;else if (ai=N |j=N)pr

9、intf(No Solution!);elseprintf(%5d%5d,ai,k-bj);阅读上面的算法程序，叙述算法的功能，并给出算法的时间与空间复杂度。改写算法，使改进算法的时间和空间效率尽可能提高。数据结构试卷参考答案 (A 卷)2010 2011 年度第二学期计算机学院(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D) 写在下表中,1 分,10 分)题号12345678910答案BCCDADCDCA二、填空题(在下表中填写正确的答案,每空 1 分,共 10 分)题号12345678910答案n-1(n+e)5n2+n3链式34队列7n-1三、判断题(判断下列各题叙

10、述的正确性,用表示正确，表示错误，每小题 1分,共 10 分)题号12345678910答案四、存储结构图(要求标明各结点的数据域、指针域、权值等，每小题6 分，共 12 分)2如下图所示为二叉树排序树 T 的一种线索二叉树逻辑结构图，试画出插入结点0 36 00 23 00 55 0 1 12 11 30 10 36 00 23 00 55 0 1 12 11 30 11 48 11 66 12 试画出如下图所示无向网的邻接多重表存储结构图。参考答案：A B C DA B C DE10248014024039126138141234五、求解问题(每小题 8 分，共 32 分)n 2n-1SA

11、1m（1）m 值是什么？（2）Ai，jSAk中，试写出由下标(i，j)k 的转换公式。0 0 0 0 000 a1,na0 a2,n-1 2,n2,n+100 . a .a .a. 0 i,n-i+1i,ni,n+i-1aaaa n,1 n,2n,n（1m=2（2）k=(i-1)2+i+j-n( |j-n|data=X0;for(i=0; Yi=X0 ;i+);T-lchild= CreateBiTree(&X1,Y,i);T-rchild= CreateBiTree(&Xi+1,&Yi+1,n-i-1); Return T;八、阅读并改进算法(每小题 4 分，共 8 分)（1）. 阅读上面的算法程序，叙述算法的功能，并给出算法的时间与空间复杂度。答案：输入一个数k，在有序序列中找 2 个数，使其和等于kT(n)= O(n)S(n)= O(n)（2） 改写算法，使改进算法的时间和空间效率尽可能提高。参考答案：#include #define M