数据结构模拟试题1(1).pdfVIP

数据结构模拟试题1（1）

⼀、选择题（共10题，每题1分，共10分）

1．下⾯关于线性表的叙述中，错误的是哪⼀个？（B）

A．线性表采⽤顺序存储，必须占⽤⼀⽚连续的存储单元

B．线性表采⽤顺序存储，便于进⾏插⼊和删除操作

C．线性表采⽤链接存储，不必占⽤⼀⽚连续的存储单元

D．线性表采⽤链接存储，便于插⼊和删除操作

2．在⼀个单链表中，已知q所指结点是p所指结点的前驱，若在p和q之间插⼊s所指结点，则执⾏的操作是（）。

A.s-next=p-next;p-next=s;

B.q-next=s;s-next=p;

C.p-next=s-next;s-next=p;

D.p-next=s;s-next=q;

3．设有三个元素X，Y，Z顺序进栈，下列得不到的出栈排列是()。

A．XYZB.YZXC.ZXYD.ZYX

4．若⽤⼀个长度为6的数组来实现循环队列，且当前rear和front的值分别为0和3，则从队列中删除⼀个元素，再增加两个元素

后，rear和front的值分别是()。

A．1和5B．2和4C．4和2D.5和1

5．下列说法中正确的是（）。

A．⼆叉树就是度为2的树B．⼆叉树中不存在度⼤于2的结点

C．⼆叉树中⾄少有⼀个结点的度为2D．⼆叉树中任何⼀个结点的度都为2

6．在具有n个结点的⼆叉链表中，共有（）个空指针。

A.n

B.n-1

C.n+1

D.不确定

7．根据⼆叉树与树的转换关系可知，深度为h的满⼆叉树对应的森林由（）棵树构成。

A．1B．log2nC.h/2D.h

8．在⼀个⽆向图中，所有顶点的度数之和等于所有边数的（）倍。

A．1/2B．1C.2D.4

9．对17个元素的查找表做折半查找，则查找长度为5的元素下标依次是（）。

A．8,17Ｂ．5,10,12C．9,16D．9,17

10．关于排序，下列说法中正确的是（）。

A.稳定的排序⽅法优于不稳定的排序⽅法，因为稳定的排序⽅法效率较⾼

B.在顺序表上实现的排序⽅法在链表上也可以实现

C.在链表上可以实现简单选择排序，但是难以实现堆排序

D.就平均性能⽽⾔，堆排序最佳

⼆、填空题（共10空，每空2分，共20分）

1．计算机执⾏下⾯的语句时，语句s的执⾏次数为(n+3)(n-2)/2。

for(i=l；i

for(j=n;j=i;j--)s;

2．队列是限制插⼊只能在表的⼀端，⽽删除在表的另⼀端进⾏的线性表，其特点是___FIFO____。3．数组A[0..5,0..6]的每

个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是_1175______。

4．⼀棵有124个叶⼦结点的完全⼆叉树，最多有个_248______结点。

5．N个顶点的⽆向连通图若要存在回路，则⾄少需要_N-1_________条边。

6．对于⼀棵⼆叉排序树做_中序_____遍历，可以得到⼀个有序的序列。

7．进⾏折半查找的两个先决条件是查找表中数据有序和__顺序存储________。

8．按{12,24,36,90,52,30}的顺序构成的平衡⼆叉树，其根结点是__36________。

9．时间复杂度为O（nlg2n）且稳定的排序算法是_归并_________排序。

10．快速排序在__数据基本有序________情况下会蜕变成为冒泡排序。

三、应⽤题（共5题，每题10分，共50分）

1．设⼀棵⼆叉树的先序遍历序列：ABDFCEGH中序遍历序列：BFDAGEHC（1）画出这棵⼆叉树。

（2）将这棵⼆叉树转换成对应的树（或森林）。

2．给定⼀组数列（15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G出现的频度，画出Huffman树，并给出各字符的Huffman

编码。

3．根据Prim算法或Kruskal算法，求右图的最⼩⽣成树。

4．某⼀⼯程作业的⽹络图如右图所⽰，其中箭头表⽰作业，箭头边的数字表⽰完成作业所需的天数。箭头前后的圆圈表⽰事

件的编号。求出所有事件开始的最早时间和最晚时间，并给出关键路径。

5．设哈希函数H（k）=3*Kmod11，散列地址空间为0～10，对关键字序列（32,13,49,24,38,21,4,12）按线性探测再散列的

⽅法解决冲突，构造哈希表，并求出等概率下查找成功时的平均查找长度

四、程序设计题（共2题，共20分）

1．设有两条带头结点单链表La和Lb，且表