2022年数据结构试题试卷一含答案 .pdf

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

1、学而不思则惘，思而不学则殆模拟试题一模拟试题一一、选择题（ 30 分） 1. 组成数据的基本单位是(c) 。 A) 数据项B）数据类型C）数据元素 D）数据变量2.线性表采用链式存储结构时，要求内存中可用存储单元的地址( D )。 A) 必须是连续的B ）部分地址必须是连续的 C) 一定是不连续的 D）连续或不连续都可以 3. 在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是(B ) 。 A)O(1) B)O(n) C) O(n2) D) O(nlog2n) 4. 栈结构通常采用的两种结构是(A ) 。 A) 顺序存储结构和链表存储结构 B) 散列方式和索引方式 C)

2、链表存储结构和数组 D) 线性链表结构和非线性存储结构 5. 表达式 a*(b+c)-d的后缀表达式是(B ) 。 A) abcd+- B）abc+*d- C）abc*+d- D）一十 *abcd 6. 栈和队列的共同特点是( C ) 。 A) 都是先进先出B）都是先进后出 C) 只允许在端点处插入和删除元素 D）没有共同点 7. 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH 和 DBGEACHF，则该二叉树的后序遍历为 ( B) 。 A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHG 精选学习资料 - - - - - - - - - 名师

3、归纳总结 - - - - - - -第 1 页，共 8 页学而不思则惘，思而不学则殆 8. 链表不具有的特点是( B ) ， A) 不必事先估计存储空间 B）可随机访问任一元素 C) 插入删除不需要移动元素 D）所需空间与线性表长度成正比 9. 在深度为5 的满二叉树中，叶子结点的个数为( B。 A) 32 B) 31 C) 16 D) 15 10. 最简单的交换排序方法是( D ) 。 A) 快速排序 B）选择排序 C）堆排序 D）冒泡排序 11. 数据结构是研究数据的( C ) 以及它们之间的相互关系。 A) 理想结构，物理结构 B）理想结构，抽象结构 C) 物理结构，逻辑结构 D）抽象结

4、构，逻辑结构 12. 线性表采用链式存储时，其地址( D ) 。 A) 必须是连续的 B）部分地址必须是连续的 C) -定是不连续的 D）连续与否均可以 13. 设循环队列Ql.n-l的首尾指针为f 和 r ，当插入元素时尾指针r 加 1，首指针 F 总是指在队列中第一个元素的前一个位置，则队列中元素计数为( D) 。 A) r-f B) n- (r-f) C)(r-f+n)%n D) (f-r+n)%n 14. 完成堆排序的全过程需要(A ) 个记录大小的辅助空间。 A)1 B)n C) nlog2n D)|_nlog2n_| 15. 若给定的关键字集合为20 ，15，14，18，21，36

5、，40，10 ，一趟快速排序结束时，键值的排列为(A ) 。 A) 10, 15, 14, 18, 20, 36, 40, 21 B) 10, 15, 14, 18, 20, 40, 36, 21 C) 10, 15, 14, 20, 18, 40, 36, 21 D) 15, 10, 14, 18, 20, 36, 40, 21 二、填空题（ 22 分） 1. 一棵完全二叉树的第5 层有 5 个结点，则共有_20_个结点。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 8 页学而不思则惘，思而不学则殆 2. 有向图 G用邻接矩阵A1n

6、，1.n存储，其第i 列的所有元素等于顶点i 的 _。 3. 设有一空栈，栈顶指针为IOOOH （十六进制），现有输入序列为1，2，3，4， 5，经过 Push, Push ，Pop， Push，Pop，Push，Push 操作后，输出序列为_。4. 在具有 n(n 1) 个结点的k 叉树中，有 _个空指针。5. 模式中“ ababbabbab”的前缀函数为_。6. 设图 G的顶点数为n，边数为e，第 i 个顶点的度数为D(vi) ，则 e=_即边数与各项点的度数之间的关系）。 7. 按_遍历二叉树，可以得到按值递增的关键值序列，在下图所示的二叉树中，检索关键值85 的过程中，需与85 进行比

7、较的关键码序列为_。8. 下列算法实现二叉树排序树上的查找，请在空格处填上适当的语句，完成上述功能。 bitreptr *bstsearch (bitreptr *t, keytype k) if (t=NULL) return NULL; else while(t!=NULL) if(t-key=k_; if(t-keyk)_; else_; 三、应用题 (16 分) 1. 设二叉树的顺序存储结构如下所示。（4 分） (1) 根据其存储结构，画出二叉树。 (2) 写出按前序、中序、后序遍历该二叉树所得的结点序列。 (3) 画出二叉树的后序线索化树。精选学习资料 - - - - - - - -

8、 - 名师归纳总结 - - - - - - -第 3 页，共 8 页学而不思则惘，思而不学则殆 2.- 棵完全二叉树共有21 个结点，现顺序存放在一个矢量中，矢量的下标正好为结点的序号，试问序号为12 的双亲结点存在吗？是什么？（4 分） 3. 线性表有顺序表和链表两种存储结构，简述各自的优缺点。（4 分） 4. 何谓队列的“假溢”现象？如何解决？（4 分）四、算法设计（32 分） 1. 已知线性表的元素按递增顺序排列，并以带首结点的单链表作为存储结构。试编写一个删除表中所有值大于min 且小于 max的元素的算法。 2. 试设计一个算法，求出指定结点在给定的二叉树中的层次。 3. 已知一个单

9、链表中每个结点存放一个整数，并且其结点数不少于2。试编写算法以判断该链表中从第二项起的每个元素值是否等于其序号的平方减去其前驱结点的值，若满足，返回True，否则返回False 。4. 在含有 n 个元素的堆中增加一个元素，且调整为堆。模拟试题一答案模拟试题一参考答案一、选择题 1.C 2.D 3.B 4.A 5.B 6.C 7.B 8.B 9.C 10.D 11.C 12.D 13.D 14.A 15.A 二、填空题 1. 20。 2. 入度即 ID(i)。 3.2 ，3， 5，4， 1. 4.n(k-l)+l。 5. Nextj=(0 1 1 2 3 1 2 3 1 2)。精选学习资料 -

10、 - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 8 页学而不思则惘，思而不学则殆 6. 7. 中序， 55 90 57 75 85a 8. Return(t), Return(bstsearch(t-lchild, k), Return(bstsearch(t-rchild, k) 。三、应用题 1.(1)该存储结构对应的二叉树为 (2) 先序序列为EADCBFHGI 。中序序列为ABCDEFGHI 。后序序列为BCDAGIHFE 。 (3)后序线索树为。 2. 序号为 12 的双亲结点存在。因为这棵完全二叉树除根结点外的其余20 个结点都有 1 个唯

11、一的双亲结点。序号为i 的双亲结点是 |_i/2_|，所以 12 的双亲结点为|_12/2_|=6。 3. 在顺序表结构中，逻辑相邻的元素其存储位置也相邻。只要确定了线性表的起始存储位置， 就可以随机存取任意数据元素。所以顺序表的优点是方便查找，缺点是做插入和删除操作时需移动大量元素。链表结构不要求逻辑相邻元素的存储位置相邻，即可存放内存中任何位置，元素间逻辑关系依指针相连。查找时必须从表头指针开始依序查找。但插入和删除操作时无需移动元素， 只修改元素的指针即可。所以链表的优点是方便插入和删除操作，缺点是不能精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - -

12、 -第 5 页，共 8 页学而不思则惘，思而不学则殆随机查找任一元素。 4. 随着数据元素的不断插入和删除，队列的队首指针已指向允许插入的最大位置，此时或许还有很多可插入的空间，但却不能插入数据元素了，这种现象称为队列的“假溢”。解决的方法是采用循环链表（队列）。四、算法设计 1. 删除表中所有值大于min 且小于 max的元素的算法如下： Typedef struct node int data; struct node +next linklist; delete( linklist *head, int max, int min) /* 删除有序单链表中所有值大于min 且小于 max的

13、元素 */ linklist *p, *q; if (head! =NULL) q=head; p=head-next; while(p!=NULL &p-datanext; while(p!=NULL p-datanext; q-next=p; 2. 求出指定结点在给定的二叉树中的层次的算法： Void level (bitree *t, bitree *p,int h,int th) /*t为指向二叉树的指针，p指向待找的结点，h 为 p 结点的层次数， th 为当前的层次数 */ 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 8

14、 页学而不思则惘，思而不学则殆 if (t=NULl) h=0; /* 树为空时返回0*/ else if(p=t) h=th; /* 找到结点p 时*/ else level (p, t-lchild,h，th+l); /* 在左子树中查找*/ if （h=-1）level (p, t-rchild,h，th+l);/*在右子树中查找*/ 3. 判断链表中从第二项起的每个元素值是否等于其序号的平方减去其前驱结点的值的算法如下： int Judge (linklist *head) int flag,i linklist *P, *q; q=head-next; flag=False; i=2

15、; while(p!-NUIL)( if (p-data=i*i-q-data) flag=True; else return False; q=p; p=p-next; i+; ) return flag; 4. 在含有 n 个元素的堆中增加一个元素，且调整为堆的算法： void heapinsert (RectyPe R, datatype x) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 8 页学而不思则惘，思而不学则殆/* 在堆 R1 到 Rn 中插入一个新元素x*/ int i， j; j=n+1; /* 初始化 */ while (jl) i=i/2 /* 求结点 kj 的双亲结点ki*/ if(Ri.keyx.key) j=l; /* 若为堆，跳出循环*/ else f Rj=Ri; j =i; /* 不为堆，再调整*/ Rj=x; /*x 插入正确的位置*/ 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 8 页