武汉大学数据结构考试题(附答案)

《武汉大学数据结构考试题(附答案)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、....1.下面程序段的执行次数为（A）for(i=0;i＜n-1;i++)for(j=n;j＞i;j--)state;A.n(n+2)2B.(n-1)(n+2)2C.n(n+1)2D.(n-1)(n+2)2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）A.110B.108C.100D.1203.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（C）A.edcbaB.decbaC.dceabD.abcde4.循环队列用数组A[0,m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是（D）A

2、.(rear-front+m)%mB.read-front+1C.read-front-1D.read-front5．不带头结点的单链表head为空的判定条件是（A）A.head=NULLB.head-next=NULLC.head-next=headD.head!=NULL6．在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行（B）A.s-next=p;p-next=s;B.s-next=p-next;p-next=s;C.s-next=p-next;p=s;D.p-next=s;s-next=p;7.从一个具有n个结点的单链表中查找其值等于x结点时，

3、在查找成功的情况下，需平均比较多少个结点（D）A.nB.n2C.(n-1)2D.(n+1)28．从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行(D)A.x=HS;HS=HS-next;B.x=HS-data;C.HS=HS-next;x=HS-data;D.x=HS-data;HS=HS-next;9．串是一种特殊的线性表，其特殊性体现在(B)A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符11．二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素

4、M[3][5]的起始地址与M按列存储时下列哪一元素的起始地址相同(B)A.M[2][4]B.M[3][4]C.M[3][5]D.M[4][4]12.数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为(C)A.SA+144B.SA+180C.SA+222D.SA+225参考....13.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为：(B)A.2hB.2h-1C.2h+1D.h+114.已知某二叉树的后序遍历序列是dabec，中序遍历序列

5、是debac，它的前序遍历序列是(D)A.acbedB.decabC.deabcD.cedba15.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确(A)A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对16.具有6个顶点的无向图至少应有多少条边才能确保是一个连通图(A)A.5B.6C.7D.817.顺序查找法适合于存储结构为(B)的

6、线性表A.散列存储B.顺序存储或链接存储C.压缩存储D.索引存储18.采用顺序查找方法查找长度为n的线性表每个元素的平均查找长度为(C)A.nB.n2C.(n+1)2D.(n-1)219.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为(B)A.3512B.3712C.3912D.431220.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，几次比较后查找成功（C）二、填空题（每空1分，共20分）1.在线性表的顺序存储中，元素之间的逻辑关系是通过物理

7、存储位置，决定的；在线性表的链接存储中，元素之间的逻辑关系是通过链域的指针值决定的。2．对于一个具有N个结点的单链表，在已知的结点P后插入一个新结点的时间复杂度为O(1),在给定值为X的结点后插入一个新结点的时间复杂度为O(N)。3.有一空桟，现有输入序列1,2,3,4,5,经push,push,pop,push,pop,push,push后，输出序列为2,3。4．在一个无向图中，所有顶点的度数之和等于所有边数的2倍5.对于一棵具有n个结点的树，该树中所有结点的度数之和为n-1。6.在一棵三