考研计算机-数据结构模拟试题

《考研计算机-数据结构模拟试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机数据结构模拟试题（一）一.单项选择题：1～40题，每小题2分共80分。在每小题给出的四个选项中，请选出一项最符合题目要求的。1.在一个单链表中，已知指针p指向其中的某个结点，若在该结点前插入一个由指针s指向的结点，则需执行（　　）。A．s->next = p->next;p->next = s; B．p->next = s;s->next = p;C． r = p->next;p->next = s;s->next = r;D．仅靠已知条件无法实现2.设顺序表长度为n，从表中删除元素的概率相等。则在平均情况下，从表中删除一个元素需要移动

2、的元素个数是（）。A．(n−1)/2B．n/2C．n(n − 1)/2D．n(n + 1)/23.在一个具有n个单元的顺序栈中，假定以高端（即第n−1单元）作为栈底，以top为栈顶指针，则当作出栈运算时，top变化为（）。A．top不变B．top = 0C．top--D．top ++4.若一个栈以向量V[n]存储，设栈空时，栈顶指针top为n−1，则下面x进栈的正确操作是（）。A．top = top + 1；V[top] = xB．V[top] = x；top = top + 1C．top = top − 1；V[top] = xD．V[to

3、p] = x；top = top − 15.经过以下栈运算后，x的值是（）。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Push(s,c);Pop(s,x);GetTop(s,x);A.aB．bC．cD．d6.若一棵二叉树有126个节点，在第7层（根结点在第1层）的结点个数至多有（　　）。A．32B．64C．63D．不存在第7层7.具有n个顶点的有向图的边最多有（）。A．nB．n(n−1)C．n(n+1)D．n28.设连通图G的顶点数为n，则G的生成树的边数为（）。A．nB．n−1C．2nD．2n−19

4、.散列查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行（）次探测。A．kB．k + 1C．k(k + 1)/2D．1 + k(k + 1)/210.一组记录的关键字为(45，80，55，40，42，85)，则利用堆排序的方法建立的初始堆为（）。A．(80，45，55，40，42，85)B．(85，80，55，40，42，45)C．(85，80，55，45，42，40)D．(85，55，80，42，45，40)二、综合应用题：41-47小题，共70分1.已知顺序表中有m个记录，表中记录不依关键字有序

5、。编写算法为该顺序表建立一个有序的索引表，索引表中每一项应含有记录关键字和记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O(m)。2.在二叉链表的每个结点中添加一个域intdepth，表示以该结点为根的子树的深度，即：typedefstructBiTNode{// 结点结构TElemTypedata;structBiTNode*lchild,*rchild;// 左右孩子指针intdepth;// 以该结点为根的子树的深度}BiTNode,*BiTree;（1）试编写一递归函数BiTreeDepth(BiTreeT)，计算二叉

6、树T中每个结点的depth值，函数的返回值为树T的深度。（2）在（1）的基础上（即已求出二叉树中每个结点的depth值），编写一递归函数BiTreeBalance(BiTreeT)，判断二叉排序树T是否为平衡二叉树，如果是平衡二叉树，则函数的返回值为真。计算机数据结构模拟试题（一）参考答案答案仅供参考一、单项选择题：1～40题，每小题2分共80分。在每小题给出的四个选项中，请选出一项最符合题目要求的。1.D2.A3.C4.D5.A6.C7.B8.B9.C10.B二、综合应用题：41-47小题，共70分1.解答（参考算法）：索引表的类型定义如下

7、：typedefstruct{KeyTypekey;//关键字intid;//对应记录在顺序表中的序号}IndexType,IdxTable[MAXSIZE + 1];顺序表类型定义如下：typedefstruct{KeyTypekey;…}RedType;typedefstruct{RedTyper[MAXSIZE + 1];//r[0]闲置或用作哨兵单元 intlength;//顺序表长度}SqList;算法：voidcreateIdx(SqListL,IdxTableIdx){//顺序表L中有m个记录，本算法为该顺序表建立一个有序的索引

8、表，索引表中每一项包含记录//的关键字和记录在顺序表中的序号两个数据项Idx[1].key = L.r[1].key;Idx[1].id = 1;for(i=2;i