2022年数据结构期末复习题宣贯 .pdf

1.线性表2.单选在一个单链表中，若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; 2 单选 线性表的顺序存储结构是一种顺序存取的存储结构，线性表的链式存储结构是一种_A_的存储结构。A: 随机存取B: 顺序存取3.C: 索引存取D: 散列存取3. 单选向一个长度为n 的顺序表的第 i 个元素（ 1i n+1）之前插入一个元素时，需向后移动 _D_ 个元素。A: i: Bn-i C: n-i-1 Dn-i+1 4. 单选在单链表的一个节点中有_A_ 。A: 1 个指针B: 2 个指针C: 0 个指针D: 3 个指针5. 单选在一个单链表中，若删除p 所指结点的后续结点，则执行_A_。A: p-next=p-next-next; B: p=p-next;p-next=p-next-next; C: p-next=p-next; D: p=p-next-next 6. 单选使用双向链表存储数据，其优点是可以_A_ 。A: 提高检索速度 B: 很方便地插入和删除数据C: 节约存储空间D: 很快回收存储空间7. 单选某个顺序表第一个元素的存储地址是100，每个元素的长度为 2，则第 5 个元素的地址是 _B_ 。A: 110 B: 108 C: 100 D: 120 8. 单选在一个单链表中，已知q 所指结点是 p 所指结点的前驱结点，若在q 和 p 之间插入 s 结点，则执行 _C_ 。A: s-next=p-next; p-next=s; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 17 页 - - - - - - - - - B: p-next=s-next; s-next=p; C: q-next=s; s-next=p; D: p-next=s; s-next=q; 9. 单选从一个长度为n 的向量中删除第 i 个元素（ 1i n）时，需向前移动_B_ 个元素。A: i B: n-i C: n-i-1 D: n-i+1 10. 单选顺序存储结构 _C_ 。A: 仅适合于静态查找表的存储B: 仅适合于动态查找表的存储C: 既适合静态又适合动态查找表的存储D: 既不适合静态又不适合动态查找表的存储11. 单选一维数组的元素起始地址loc6=1000 ，元素长度为 4，则 loc8为_C_ 。A: 1000 B: 1004 C: 1008 D: 8 12. 单选某个顺序表第一个元素的存储地址是100，每个元素的长度为2，则第 6 个元素的地址是 _A_。A: 110 B: 108 C: 100 D: 120 13. 单选若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_D_ 存储方式最节省运算时间。A: 单链表B: 仅有头指针的单循环链表C: 双链表D: 仅有尾指针的单循环链表14. 单选若对数据结构采用了顺序存储，第一个节点的地址为1001，每个节点的值需占用 2 个存储单元，则第三个节点的起始地址为_B_。A: 1003 B: 1005 C: 1006 D: 1007 15. 单选顺序表中逻辑上相邻的节点其物理位置也_A_ 。A: 一定相邻B: 不必相邻C: 按某种规律排列D: 无要求名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 17 页 - - - - - - - - - 栈和队列1. 单选一个队列的入列序列是1，2，3，4，则队列的输出序列是 _B_ 。A: 4,3,2,1 B: 1,2,3,4 C: 1,4,3,2 D: 3,2,4,1 2. 单选判定一个循环队列QU （最多元素为 m0 ）为空的条件是 _A_。A: QU-front=QU-rear B: QU-front!=QU-rear C: QU-front=(QU-rear+1)%m0 D: QU-front!=(QU-rear+1)%m0 3. 单选从一个顺序队列删除元素时，首先需要_B_ 。A: 前移一位队首指针B: 后移一位队首指针C: 取出队首指针所指位置上的元素D: 取出队尾指针所指位置上的元素4. 单选循环队列用数组A0,m-1 存放其元素值，已知其头尾指针分别是front和 rear ，则当前队列中的元素个数是_A_。A: (rear-front+m)%m B: rear-front+1 C: rear-front-1 D: rear-front 5. 单选当利用大小为N的数组顺序存储一个队列时，该队列的最大长度为_B_。A: N-2 B: N-1 C: N D: N+1 6. 单选判定一个队列QU （最多元素为 m0 ）为空的条件是 _C_ 。A: QU-rear-QU-front=m0 B: QU-rear-QU-front-1=m0 C: QU-front=QU-rear D: QU-front=QU-rear+1 7. 单选队列操作的原则是_A_ 。A: 先进先出B: 后进先出C: 只能进行插入D: 只能进行删除8. 单选判定一个队列QU （最多元素为 m0 ）为满队列的条件是 _A_。A: QU-rear-QU-front=m0 B: QU-rear-QU-front-1=m0 C: QU-front=QU-rear D: QU-front=QU-rear+1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 17 页 - - - - - - - - - 9. 单选在一个顺序队列中，队首指针指向队首元素的_A_ 位置。A: 前一个B: 后一个C: 当前D: 后面10. 单选一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是_C_ 。A: edcba B: decba C: dceab D: abcde 11. 单选 4 个元素进 Q队列的顺序是 A，B，C ，D ，进行 DeQueue(Q) 操作后，队头元素是 _B_ 。A: A B: B C: C D: D 12. 单选一个栈的入栈序列是a,b,c ，则栈的不可能的输出序列是_D_ 。A: acb B: bac C: bca D: cab 13. 单选假定一个链队的队首和队尾指针分别为front和 rear ，则判断队空的条件为 _D_ 。A: front=rear B: front!=NULL C: rear!=NULL D: front=NULL 14. 单选判定一个循环队列QU （最多元素为 m0 ）为满队列的条件是 _C_ 。A: QU-front=QU-rear B: QU-front!=QU-rear C: QU-front=(QU-rear+1)%m0 D: QU-front!=(QU-rear+1)%m0 15. 单选假定一个顺序队列的队首和队尾指针分别为f 和 r ，则判断队空的条件为 _D_ 。A: f+1=r B: r+1=f C: f=0 D: f=r 16. 单选栈与一般线性表的区别主要在_D_ 。A: 元素个数B: 元素类型C: 逻辑结构D: 插入、删除元素的位置名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 17 页 - - - - - - - - - 多维数组和广义表1. 单选所谓稀疏矩阵指的是_C_ 。A: 零元素个数较多的矩阵B: 零元素个数占矩阵元素总个数一半的矩阵C: 零元素个数远远多于非零元素个数且分布没有规律的矩阵D: 包含有零元素的矩阵2. 单选数组 A中，每个元素 A的长度为 3 个字节，行下标 i 从 1 到 8，列下标 j 从 1 到 10，从首地址 SA开始连续存放在存储器内，该数组按行存放时，元素 A85的起始地址为 _C_ 。A: SA+140 B: SA+144 C: SA+222 D: SA+225 3. 单选设二维数组 A0.m-10.n-1按列优先顺序存储， 则元素 Aij的地址为 _A_ 。A: LOC(A00)+(j*m+i) B: LOC(A00)+(j*n+i) C: LOC(A00)+(j-1)*n+i-1 D: LOC(A00)+(j-1)*m+i-1 4. 单选数组与一般线性表的区别主要在_D_ 。A: 存储方面B: 元素类型一致C: 逻辑结构方面D: 不能进行插入、删除运算5. 单选在以下的叙述中，正确的是_B_。A: 线性表的线性存储结构优于链表存储结构B: 二维数组是其数据元素为线性表的线性表C: 栈的操作方式是先进先出D: 队列的操作方式是先进后出写出下列稀疏矩阵A所对应的三元组表：a-m=5 a-n=5 a-t=5 i j v 0 0 1 -2 1 1 4 80 2 2 1 93 3 4 0 54 A55= 0 -2 0 0 0 0 0 0 0 80 0 93 0 0 0 0 0 0 0 0 54 0 18 0 0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 17 页 - - - - - - - - - 4 4 2 18 树1. 单选将递归算法转换成对应的非递归算法时，通常需要使用_A_ 。A: 栈B: 队列C: 链表D: 树2. 单选深度为 4 的完全二叉树至少有 _B_ 个结点。A: 7 B: 8 C: 15 D: 16 3. 单选如图所示的4 棵二叉树中， _C_ 不是完全二叉树。A: B: C: D: 4. 单选某二叉树的前序遍历结点访问顺序是abdgcefh ，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是_D_ 。A: bdgcefha B: gdbecfha C: bdgaechf D: gdbehfca 5. 单选如果 T2 是由森林 T 转换而来的二叉树， 那么 T 中结点的后序遍历就是 T2 中结点的 _B_ 。A: 先序遍历B: 中序遍历C: 后序遍历D: 层次序名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 17 页 - - - - - - - - - 6. 单选深度为 5 的二叉树至多有 _C_ 个节点。A: 16 B: 32 C: 31 D: 10 7. 单选如图所示的4 棵二叉树中， _C_ 不是完全二叉树。A: B: D: 8. 单选将一棵有100 个节点的完全二叉树从上到下，从左到右依次对节点进行编号，根节点的编号为1，则编号为 49 的节点的左孩子编号为 _B_ 。A: 99 B: 98 C: 50 D: 48 9. 单选满二叉树 _A_ 二叉树。A: 一定是完全B: 不一定是完全C: 不是D: 不是完全10. 单选对于二叉树来说，第i 层上至多有 _C_ 个节点。A: 2iB: 2i-1 C: 2i-1D: 2i-1-1 11. 单选深度为 5 的二叉树至多有 _C_ 个结点。A: 16 B: 32 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 17 页 - - - - - - - - - C: 31 D: 10 12. 单选设高度为 k 的二叉树上只有度为0 和 2 的结点，则此类二叉树中所含的结点数至少为 _C_ 。A: k+1 B: 2k C: 2k-1 D: 2k+1 13. 单选下列算法中， _C_ 是中序遍历二叉树的递归算法。A: B: C: 14. 单选按照二叉树的定义，具有3 个结点的二叉树有 _C_ 种。A: 3 B: 4 C: 5 D: 6 15. 单选设高度为 h 的二叉树上只有度为0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为_B_ 。A: 2hB: 2h-1C: 2h+1D: h+1 16. 单选设 T 是一棵树， T1是对应于 T的二叉树，则 T的后根次序遍历和T1的_B_次序遍历相同。A: 先根B: 中根C: 后根D: 都不同名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 17 页 - - - - - - - - - 17. 单选如图所示二叉树的中序遍历序列是_B_ 。A: abdgcefh B: dgbaechf C: gdbehfca D: abcdefgh 18. 单选下列算法中， _A_ 是前序遍历二叉树的递归算法。A: B: C: 19. 单选对于一棵满二叉树，m个树叶， n 个节点，深度为 h，则_D_ 。A: n=h+m B: h+m=2n C: m=h-1 D: n=2h-1 20. 单选设有 13 个值，用它们组成一棵哈夫曼树， 则该哈夫曼树中共有 _D_个结点。A: 13 B: 12 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 17 页 - - - - - - - - - C: 26 D: 25 21. 单选如果某二叉树的前序为stuwv，中序为 uwtvs，那么该二叉树的后序为_C_/ 。A: uwvts B: vwuts C: wuvts D: wutsv 22. 单选如图所示二叉树的中序遍历序列是_B_ 。A: abcdgef B: dfebagc C: dbaefcg D: defbagc 23. 单选完全二叉树 _B_ 二叉树。A: 一定是满B: 可能是满C: 不是D: 一定不是满24. 单选具有 65 个结点的完全二叉树其深度为_B_ 。（根的层次号为1）: 8 B: 7 C: 6 D: 5 25. 单选下列算法中， _BB_ 是后序遍历二叉树的递归算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 17 页 - - - - - - - - - A: B: C: 26. 单选对一个满二叉树，m个树叶， n 个结点，深度为 h，则_D_ 。A: n=h+m B: h+m=2nC: m=h-1 D: n=2h-1 27. 单选某二叉树的后序遍历序列为DABEC ，中序遍历序列为DEBAC ，则前序序列遍历为 _D_ 。A: ACBED B: DECAB C: DEABC D: CEDBA 1. 单选在一个具有n 个顶点的无向图中，要连通全部顶点至少需要_C_条边。A: n B: n+1 C: n-1 D: n/2 2. 单选已知一个图如图所示， 若从顶点 a 出发按深度优先搜索法进行遍历，则可能得到的一种顶点序列为_D_ 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 17 页 - - - - - - - - - A: a,b,e,c,d,f B: a,c,f,e,b,d C: a,e,b,c,f,d D: a,e,d,f,c,b 3. 单选采用邻接存储的图的深度优先遍历算法类似于二叉树的_A_ 。A: 先序遍历B: 中序遍历C: 后序遍历D: 按层遍历4. 单选具有 6 个顶点的无向图至少应有_A_ 条边才能确保是一个连通图。A: 5 B: 6 C: 7 D: 8 5. 单选在一个图中，所有顶点的度数之和等于所有边数的_C_ 倍。A: 1/2 B: 1 C: 2 D: 4 6. 单选具有 4 个顶点的无向完全图有 _A_ 条边。A: 6 B: 12 C: 16 D: 20 7. 单选一个有 n 个顶点的无向图最多有 _C_ 条边。A: n B: n(n-1) C: n(n-1)/2 D: 2n 8. 单选采用邻接存储的图的广度优先遍历算法类似于二叉树的_D_ 。A: 先序遍历B: 中序遍历C: 后序遍历D: 按层遍历9. 单选已知一个图如图所示，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为 _B_ 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 17 页 - - - - - - - - - A: a,b,c,e,d,f B: a,b,c,e,f,d C: a,e,b,c,f,d D: a,c,f,d,e,b 如下 AOE- 网表示一个假想的工程，顶点1 表示工程开始，顶点8 表示工程结束，试求出该 AOE- 网的关键路径a3=33a9=34 a0=28a2=59 a7=40a10=84a11=73 a1=82 a4=37a5=60 a6=28a8=56 求解过程：顶点ve vl 活动e l l-e 1 0 0 a00 0 0 2 2828a10 42423 8787a228280 4 124124a3281591315 152152a487870 6 192192a5879257 226226a61241240 8 299299a71521520 a815224391a91921920 a1019221523a112262260 关键活动为：（ a0，a2，a4，a6，a7，a9，a11）关键路径为：（ 1，2，3，4，5，6，7，8）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 17 页 - - - - - - - - - 查找1. 单选对有序表 (18,20,25,34,48,62,74,85)用二分查找 85，所需的比较次数为 _D_ 。A: 1 次B: 2 次C: 3 次D: 4 次2. 单选用线性探查法查找闭散列表，可能要探测多个散列地址，这些位置上的键值 _D_ 。A: 一定都是同义词B: 一定都不是同义词C: 都相同D: 不一定都是同义词3. 单选顺序查找法适合于存储结构为_D_ 的线性表。A: 散列存储B: 顺序存储或链接存储C: 压缩存储D: 索引存储4. 单选顺序查找法适合于存储结构为_B_ 的线性表。A: 散列存储B: 顺序存储或链接存储C: 压缩存储D: 索引存储5. 单选下列二叉树中，_B_ 不是二叉排序树。A: B: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 17 页 - - - - - - - - - C: D: 6. 单选采用 _B_ 二叉排序树后，能得到一个有序的序列。A: 先序遍历B: 中序遍历C: 后序遍历D: 层次序7. 单选二分查找的存储结构仅限于_A_。A: 顺序存储结构，且是有序的B: 顺序存储结构，可以是无序的C: 链式存储结构，且是有序的D: 链式存储结构，可以是无序的8. 单选有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100，当二分查找值 82 为的结点时， _C_ 次比较后查找成功。A: 1 B: 2 C: 4 D: 8 9. 单选如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用 _C_ 查找方法。A: 顺序B: 折半C: 分块D: 基于属性10. 单选在查找过程中，若同时还要做增、删工作，这种查找称为_B_ 。A: 静态查找B: 动态查找C: 内查找D: 外查找11. 单选二叉排序树中，键值最小的结点_A_ 。A: 左指针一定为空B: 右指针一定为空C: 左、右指针均为空D: 左、右指针均不为空名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 17 页 - - - - - - - - - 排序1. 单选若表 r 在排序前已按元素链值递增顺序排列，采用_A_ 方法比较次数少。A: 直接插入排序B: 快速排序C: 归并排序D: 选择排序2. 单选下列关键字序列中_D_ 是堆。A: 16,72,31,23,94,53 B: 94,23,31,72,16,53 C: 16,53,23,94,31,72 D: 16,23,53,31,94,72 3. 单选若一组记录的关键码为 (46,79,56,38,40,84)，则利用快速排序的方法，以第一记录为准得到的一次划分结果为_C_ 。A: 38,40,46,56,79,84 B: 40,38,46,79,56,84 C: 40,38,46,56,79,84 D: 40,38,46,84,56,79 4. 单选排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空） 中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为_C_ 。A: 希尔排序B: 起泡排序C: 插入排序D: 选择排序5. 单选下列排序算法中， _C_ 排序在每趟结束后不一定能选出一个元素放到其排好序的最终位置上。A: 选择B: 冒泡C: 归并D: 堆6. 单选在待排序的元素序列基本有序的前提下，效率最高的排序方法是_A_。A: 插入排序B: 选择排序C: 快速排序D: 归并排序7. 单选设有 1000 个无序的元素，希望用最快的速度挑选出其中前10 个最大的元素，最好选用 _C_ 排序法。A: 起泡排序B: 快速排序C: 堆排序D: 基数排序名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 17 页 - - - - - - - - - 8. 单选一个序列中有10000 个元素，若只想得到其中前10 个最小元素，最好采用 _B_方法。A: 快速排序B: 堆排序C: 插入排序D: 二归路排序9. 单选目前以比较为基础的内部排序方法中其比较次数与待排序的记录的初始排列状态无关的是 _B_。A: 插入排序 B: 二分插入排序C: 快速排序D: 冒泡排序10. 单选排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较， 将其放入已排序序列的正确位置上的方法称为_C_ 。A: 希尔排序B: 冒泡排序C: 插入排序D: 选择排序11. 单选在下列排序方法中，_B_ 是不稳定的排序方法。A: 直接插入排序B: 直接选择排序C: 冒泡排序D: 归并排序12. 单选在所有排序方法中， 关键字比较的次数与记录的初始排列次序无关的是_D_ 。A: 希尔排序B: 起泡排序C: 插入排序D: 选择排序13. 单选设有 1000 个无序的元素， 希望以最快的速度挑选出其中前10 个最大的元素，最好选用的排序法是_B_ 。A: 起泡排序B: 快速排序C: 堆排序D: 基数排序名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 17 页 - - - - - - - - -