数据结构模拟试卷及参考答案.pdf

《数据结构模拟试卷及参考答案.pdf》由会员分享，可在线阅读，更多相关《数据结构模拟试卷及参考答案.pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数据结构模拟试卷(一)及参考答案 一单项选择题（本大题共 15 小题，每小题 2 分，共 30 分）1如果只想得到 1024 个元素组成的序列中的前 5 个最小元素，那么用(A )方法最快。A、起泡排序 B、快速排序 C、堆排序 D、直接选择排序 2算法分析的目的是（B ）A辨别数据结构的合理性、B评价算法的效率 C研究算法中输入与输出的关系 D鉴别算法的可读性 3在线性表的下列运算中，不改变数据元素之间结构关系的运算是（C ）A插入 B删除 C定位 D排序 4若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（D ）A3，2，6，1，4，5 B5，6，4

2、，2，3，1 C1，2，5，3，4，6 D3，4，2，1，6，5 5设串 sl=DataStructureswithJava,s2=it，则子串定位函数 index(s1,s2)的值为（A ）A15 B16 C17 D18 6一个顺序存储的线性表的第一个元素的存储地址是 100，每个元素的长度为 4，则第 4个元素的存储地址是（B）。A.108 B.112 C.116 D.120 7从一个具有 n 个结点的单链表中查找其值等于 x 的结点，在查找成功的情况下，平均需要比较（C ）个结点。A.n B.n/2 C.(n+1)/2 D.(n-1)/2。8在任意一棵二叉树的前序序列和后序序列中，各叶子

3、之间的相对次序关系（D ）A不一定相同 B互为逆序 C都不相同 D都相同 9高度为 5 的二叉树至多有结点数为（A ）A.63 B.32 C.24 10若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为（B ）A图中每个顶点的出度 B图中每个顶点的入度 C图中弧的条数 D图中连通分量的数目】11图的邻接矩阵表示法适用于表示（C ）A无向图 B有向图 C稠密图 D稀疏图 12在一个单链表中，若 p 所指的结点不是最后一个结点，在 p 之后插入 s 所指的结点，则执行（D）。A.s-next=p;p-next=s B.p-next=s;s-next=p C.p=s;s-next=p-next

4、 D.s-next=p-next;p-next=s 13下列排序算法中，其时间复杂度和记录的初始排列无关的是（A ）A直接选择排序 B插入排序!C快速排序 D冒泡排序 14若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字 b 的过程中，先后进行比较的关键字依次为（B ）Af,d,b Bf,c,b Cg,c,b Dg,d,b 15如下图所示的 4 棵二叉树中，（C ）不是完全二叉树。二填空题（本大题共 15 小题，每小题 2 分，共 30 分）1.-2.在数据结构中，数据的逻辑结构分线性结构和 非线性结构 。3.称算法的时间复杂度为 O(f(n)，其含义是指算

5、法的执行时间和_ f(n)_的数量级相同。4.在一个长度为 n 的单链表 L 中，删除链表中*p 的前驱结点的时间复杂度为_ O(n)_。5.假设为循环队列分配的向量空间为 Q20，若队列的长度和队头指针值分别为 13和 17，则当前尾指针的值为_10_。6.对于栈只能在_栈顶_插入和删除元素。7.通常从正确性、_可使用性_、可读性、效率和健壮性等 5 个方面评价算法（包括程序）的质量。8.在具有 n 个单元的循环队列中，队满时共有 n-1 个元素。9.若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为 (15,02,2

6、1,24,26,57,43,66,80,48,73)。10.11.在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为 稠密 索引，若对应数据对象表中的若干个表项，则称此索引为 稀疏 索引。12.二叉树中度为0的结点数为30，度为1的结点数为30，总结点数为 89 。13.广义表 A(a，b，c)，(d，e，f)的表尾为 （(d，e，f)）。14.设有一个顺序栈 S，元素 sl，s2，s3，s4，s5，s6 依次进栈，如果 6 个元素的出栈顺序为 s2，s3，s4，s6，s5，sl，则顺序栈的容量至少应为 3 。15.根据一组记录(56，42，50，64，48)依次插入结

7、点生成一棵 AVL 树(高度平衡的二叉搜索树)时，当插人到值为 50 的结点时需要进行旋转调整。16.n（n0）个顶点的无向图最多有 n(n-1)2 条边。17.设无向图的邻接表如下图所示，则该图的边的数目是 5 。A B C D 三 四 判断题(本大题共 10 小题，每小题 1 分，共 10 分)1.（）链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。2.（）在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。3.（）通常递归的算法简单、易懂、容易编写，而且执行的效率也高。4.（）一个广义表的表尾总是一个广义表。5.（）对于一棵具有

8、 n 个结点，其高度为 h 的二叉树，进行任一种次序遍历的时间复杂度为 O（h）。6.（）当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。7.（）存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。8.!9.（）进行折半搜索的表必须是顺序存储的有序表。10.（）直接选择排序是一种稳定的排序方法。11.（）在用单链表表示的链式队列中，队头在链表的链尾位置。五问答题(本大题共 5 小题，每小题 6 分，共 30 分)1由如图所示的二叉树，回答以下问题。a.其中序遍历序列为 d g b a e c h i

9、 f 。b.其先序遍历序列为 a b d g c e f h i 。c.其后序遍历序列为 g d b e i h f c a 。|2已知图 G=(V,E)，其中 Va,b,c,d,e,f,g，E,，请画出图 G，并写出其邻接矩阵和邻接表表示。&a d c b e f g h i a b c g f e d ）邻接矩阵：邻接表：/3写出利用直接选择排序对关键字序列(40,24,80,39,43,18,20)进行从小到大排序的每一趟结果。参考答案：18,24,80,39,43,40,20 18,20,80,39,43,40,24 18,20,24,39,43,40,80 18,20,24,39,4

10、3,40,80 18,20,24,39,40,43,80 18,20,24,39,40,43,80 4设 A、B、C 是不同的关键字且 ABC，可组成 6 种不同的输入顺序。问其中哪几种输入顺序所构造的二叉排序树的高度为 2 参考答案：【4 种。A BC A C B C A B C B A 评分标准：次序不限，写对一种得 1 分，4 种全写对得 6 分。若在 4 种正确答案之外，又多写一种则只能得 4 分，若 6 种排列顺序全写上则 0 分。5在如图所示的 AOE 网中，试回答如下问题：（1）计算出每个顶点所表示的事件的最早发生时间和最迟发生时间；（2）计算出每条边所表示的活动的最早开始时间和

11、最迟开始时间；（3）找出此网络中的关键活动和关键路径。】64 5 11 8 7 4 a c e h k 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 2 0 0 0 1 0 0 a b c d。e f a b c d e f g 0 1 2 3 4 5 a b c d;e f、g 1 6 6 1 2 5 3 0 4 2 3 5 /事件的最早发生时间和最迟发生时间：活动的最早开始时间和最迟开始时间：网络中的关键活动：ab,be,eh,hk 关键路径:abehk 。数据结构模拟试卷(二)一、单项选择题

12、（每小题 2 分，共 30 分）1.线性结构的逻辑特征是除第一个节点和最后一个节点，其它节点都有 。A一个直接前趋和一个直接后继 B多个直接前趋和一个直接后继 C一个直接前趋和多个直接后继 next=P-next;P-next=S;BP-next=S-next;S-next=P;&CS-next=P;P-next=S;DP-next=S;S-next=P;9.设将整数 1,2,3,4,5 依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进行，则出栈序列不可能是 。A23415 B54132 C23145 D15432 10.循环队列是空队列的条件是 。￥AQ-rear=Q-front B

13、(Q-rear+1)%maxsize=Q-front CQ-rear=0 DQ-front=0 11.设有一广义表 E=（a,b,(c,d)），其长度为 。A2 B3 C4（D5 12.某二叉树的前序遍历序列为 ABDEFC，中序遍历序列为 DBEFAC，则后序遍历序列为 。ADFEBCA BDBECFA CBDAECF DDBEFCA 13.下列哪项不是利用查找表中数据元素的关系进行查找的方法。A有序表的查找 B二叉排序树的查找 C平衡二叉树 D散列查找 14.下述几种排序方法中，要求内存量最大的是 。A插入排序 B快速排序 C归并排序 D选择排序 15.16.在一个有向图中，所有顶点的入度

14、之和等于所有顶点的出度之和的 倍。A1/2 B1 C2 D4 二、填空题(每空 2 分，共 20 分)16数据结构一般包括三个方面内容：数据的 ，数据的存储结构及数据的运算。17在包含 n 个结点的顺序表上做等概率插入运算，平均要移动_ _个结点。18队列的特性是_ _ _。19已知二叉树中叶子数为 30，仅有一个孩子的结点数为 20，则总结点数为_ _。20 _ _遍历二叉排序树中的结点可以得到一个递增的关键字序列（选填“先序”、“中序”或“后序”）。21n 个节点的连通图至少有_ _条边。22在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑，应最好选择 排序。23带有一个头

15、结点的单链表 head 为空的条件是（假设指针域的名称为 next）、_ _。24设一组初始关键字序列为(38，65，97，76，13，27，10)，则第 3 趟简单选择排序后的结果为_ _。25在拓扑排序中，拓扑序列的第一个顶点必定是 的顶点。三、简答题（每题 6 分，共 36 分）26 已知一棵树边的集合为,，画出这棵树，并回答下列问题：（1）哪个是根结点（2）哪些是叶子结点（3）!（4）哪些是结点 g 的祖先（5）树的深度是多少（6）树的度数是多少 27 以下面数据作为叶子结点的权值构造一 Huffman 树，画出该树并计算出其带权路径长度。2，4，5，8 28给定关键字集合(45,28

16、,52,20,10,35,40,70,30,75,63,32)，（1）$（2）从一棵空的二叉搜索树开始，按表中元素的次序构造一棵二叉搜索树。（3）画出从该二叉搜索树中删除关键码 28 和 52 后的结果。29试画出下面带权无向图的一棵最小生成树。30写出利用希尔排序对关键字序列(40,24,80,39,43,18,20,10,90,70)进行从小到大排序的每一趟结果。（假设 gap 取值分别为 5、3、1）31设一散列表长为 13，采用线性探查法解决冲突。散列函数 h(key)=key%13。next=NULL _。(24设一组初始关键字序列为(38，65，97，76，13，27，10)，则第

17、 3 趟简单选择排序后的结果为_10,13,27,76,65,97,38 _。25在拓扑排序中，拓扑序列的第一个顶点必定是 入度为零 的顶点。七、简答题（每题 6 分，共 36 分）26 已知一棵树边的集合为,，画出这棵树，并回答下列问题：（7）哪个是根结点（8）哪些是叶子结点（9）哪些是结点 g 的祖先（10）【（11）树的深度是多少（12）树的度数是多少 参考答案：根结点是：a 叶子结点是：d i f j k l g 的祖先：a c 树的深度：4 树的度数：3?27 以下面数据作为叶子结点的权值构造一 Huffman 树，画出该树并计算出其带权路径长度。2，4，5，8 参考答案：，带权路径

18、长度：WPL=(2+4)*3+5*2+8=36 28给定关键字集合(45,28,52,20,10,35,40,70,30,75,63,32)，（4）从一棵空的二叉搜索树开始，按表中元素的次序构造一棵二叉搜索树。（5）画出从该二叉搜索树中删除关键码 28 和 52 后的结果。参考答案：、(1)19 8&6 4 2 (2)（评分标准：每个图 3 分）29试画出下面带权无向图的一棵最小生成树。-$参考答案：(对 1 根线得 1 分，全对得 6 分)30写出利用希尔排序对关键字序列(40,24,80,39,43,18,20,10,90,70)进行从小到大排序的每一趟结果。（假设 gap 取值分别为 5

19、、3、1）参考答案：Gap=5 时 18,20,10,39,43,40,24,80,90,70 Gap=3 时 18,20,10,24,43,40,39,80,90,70 Gap=1 时 10,18,20,24,39,40,43,70,80,90 (每对 1 行得 2 分)31设一散列表长为 13，采用线性探查法解决冲突。散列函数 h(key)=key%13。（1）画出在空表中依次插入关键字 25,20,36,15,41,52,29,72,67 后的散列表。（2）该散列表在等概率查找成功和不成功的平均查找长度。参考答案：(1)散列表：（2 分）】(2)ASLSUCC=(5*1+3*2+1*4)

20、/9=5/3（2 分）5 7 6 8 4 3 2 9 9 7 a b d c e f 0 1 2 3 4 5 6 7 8 9 10 11 12 52 15 41 29 67 20 72 36 25 5 4 2 6 a 】d c e ASLNSUCC=(2+1+5+4+3+2+1+3+2+1+2+1+3)/13=30/13 （2 分）八、综合题（共 14 分）32试对下图所示的 AOE 网络回答下列问题：（4）-（5）这个工程最早可能在什么时间结束。（2 分）（6）求每个活动的最早开始时间e()和最迟开始时间l().（8 分）（7）确定哪些活动是关键活动。（4 分）&数据结构模拟试卷(三)二、单

21、项选择题（每小题 2 分，共 30 分）1一个非空广义表的表头 A一定是子表 B.一定是原子 C不能是子表 D.可以是原子，也可以是子表 2下列排序算法中时间复杂度不受数据初始状态影响，恒为 O(n2)的是 A堆排序 B.冒泡排序、6 5 10 19 4#1 2 3 、5 6 11 C直接选择排序 D.快速排序 3设将整数 1,2,3,4,5 依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进行，则出栈序列不可能是 A23415 B.15432 C23145 D.54132 4.算法必须具备输入、输出和 A.计算方法 B.排序方法 C解决问题的有限运算步骤 D.程序设计方法 5拓扑排序运

22、算只能用于 A带权有向图 B.连通无向图 C有向无环图 D.无向图 6.在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 A.O(1)B.O(n)C.O(n2)D.O(nlogn)7在一个无向图中，所有顶点的度数之和等于图的边数的 倍 A1/2 B.1 C.2 D.4【8.设二维数组 A0.m-10.n-1按行优先顺序存储，则元素 Aij的地址为 A LOC(A00)+(i*m+j)BLOC(A00)+(i*n+j)C.LOC(A00)+(i-1)*n+j-1 D.LOC(A00)+(i-1)*m+j-1 9单链表的存储密度 A大于 1 B.等于 1 C小于 1

23、D.不能确定 10.有 n 个节点的顺序表中，算法的时间复杂度是 O(1)的操作是 A.访问第 i 个节点（1in）B.C.在第 i 个节点后插入一个新节点（1in）D.删除第 i 个节点（1in）E.将 n 个节点从小到大排序 11.循环队列 SQ 的存储空间是数组 dm，队头、队尾指针分别是 front 和 rear，则执行出队后其头指针 front 值是 Afront=front+1 B.front=(front+1)%(m-1)C.front=(front-1)%m D.front=(front+1)%m 12下列排序算法中时间复杂度不受数据初始状态影响，恒为 O(n2)的是 A堆排序

24、 B.冒泡排序 C直接选择排序 D.快速排序 13.若要惟一地确定一棵二叉树，只需知道该二叉树的 A前序序列 B.中序序列 C前序和后序序列 D.中序和后序序列 14在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 A希尔排序 B.冒泡排序 C插入排序 D.选择排序 15具有 n 个节点的完全二叉树的深度为|Alog2(n+1)-1 B.log2n+1 C.log2n D.log2n 三、填空题（每小题 2 分，共 20 分）1数据的逻辑结构分为两大类，它们是线性结构和 。2在单链表中（假设结点指针域名称为 next），删除指针 P 所指结点的后继结点的语句是 。3已知循环队列用

25、数组 datan存储元素值，用 front,rear 分别作为头尾指针，则当前元素个数为 。4 若 n 为主串长，m 为子串长，则串的朴素匹配算法最坏的情况下需要比较字符的总次数为_。5 广义表(a),(b),j,(d)的表尾是 。6 已知二叉树有 61 个叶子节点，且仅有一个孩子的节点数为 45，则总节点数为 。7 解决计算机与打印机之间速度不匹配问题，须要设置一个数据缓冲区，应是一个 结构。8 n 个顶点 e 条边的图采用邻接表存储，深度优先遍历算法的时间复杂度为_。9 对于 n 个关键字的集合进行冒泡排序，在最坏情况下所需要的时间为_。10在一个长度为 n 的顺序表中的第 i 个元素（1

26、in）之前插入一个元素时，需向后移 个元素。四、算法阅读题（每空 2 分，共 10 分）1设线性表的 n 个结点定义为（a0,a1,an-1），在顺序表上实现的插入和删除算法如下，请在空白处填入适当内容。(顺序表的最大可容纳项数为 MaxSize)Template int SeqList:Insert(Type&x,int i);If(ilast+1|last=(1)return 0;Else Last+;For(int j=last;ji;j-)dataj=(2);(3);Return 1;：Template int seqList:Remove(Type&x)int i=Find(x);i

27、f(i=0)last-;for(int j=(4);jnext=p-next-next 7 队列 3(rear-front+n)%n 8 O(n+e)4（n-m+1）m 9 O（n2）5 (b),j,(d)10 n-i+1 三、算法阅读题（每小题 5 分，共 10 分）答案:(1)MaxSize-1 (2)dataj-1 (3)Datai=x(4)i (5)dataj+1 四、问答题（共 40 分）1已知一棵二叉树的中序序列和序序列分别如下，请写出它的后序序列。（10 分）答案:后序序列：D E B G R K H M C A 2已知 AOE 网的邻接表如下：（10分）(1)并标明每个事件发生

28、的 Ve 及 Vl vi A B C D E F G H ve 0 5 2 11 7 14 19 23 vl 0 7 2 13 7 16 19 23 (2).写出 AOE 网的关键路径:关键路径(Critical Path):,3.（10 分）初始 03，87，12，61，98，70，97，27，53，42，56，77 第一趟 03，77，12，53，42，56，87，27，61，98，70，97 第二趟 03，27，12，53，42，56，87，70，61，98，77，97 每三趟 03,12,27,42,53,56,61,70,77,87,97,98 4有一电文 00 （10 分）答案：O:=011 G:=10 D:=00:=010 F:=11 GOODFOODGOOD