国开助手《数据结构与算法》形考作业2答案
小虾米
2026-05-11 06:29:59
2 次阅读
0 分钟阅读
1. 无向图的顶点个数为n，则图中边数的最大值为（）。
A. n× （n-1）
B. n× （n-1）/2
C. n-1
D. n
2. 在一个无向图中，所有顶点的度数之和等于所有边数的（）。
A. 3倍
B. 2倍
C. 1倍
D. 0.5倍
3. 在图的邻接矩阵存储结构中删除一个顶点，下列说法错误的是（）。
A. 直接在删除顶点处做删除标记即可
B. 删除顶点顺序表中的该顶点
C. 删除邻接矩阵中该顶点所在的行
D. 删除邻接矩阵中该顶点所在的列
4. 一个有e条边的无向图，邻接表中包含的边结点的总数是（）。
A. e
B. e-1
C. e+1
D. 2e
5. 对于下图的无向图，插入一个顶点E后，顶点顺序表为（）。
A. 选项A
B. 选项B
C. 选项C
D. 选项D
6. 对于下面的图，从结点0开始进行深度优先搜索，可能的搜索结果是（）。
A. 0,1,2,3,4,5
B. 0,1,2,3,5,4
C. 0,2,3,4,1,5
D. 0,4,3,1,2,5
7. 对于下面的图，从结点1开始进行广度优先搜索，可能的搜索结果是（）。
A. 1,3,2,4,0,5
B. 1,0,4,2,3,5
C. 1,3,0,2,4,5
D. 1,5,0,2,4,3
8. 设一组初始记录关键字序列为（17，29，32，48，51，63，78，92，151），则利用顺序查找方法查找关键字78需要比较的关键字个数为（）。
A. 5
B. 6
C. 7
D. 8
9. 设一组初始记录关键字序列为（12，25，27，37，52，61，72，89，97）,则利用折半查找过程中第一个比较的关键字是（）。
A. 12
B. 17
C. 52
D. 61
10. 设一组初始记录关键字序列为（28，32，49，53，67，71，86，94，115，128，136），则利用折半查找关键字128需要比较的关键字个数为（）。
A. 1
B. 2
C. 3
D. 4
11. 按{12，24，36，90，52，30}的顺序构成的二叉排序树，其叶子结点是（）。
A. 30，52
B. 24，36
C. 52，90
D. 12，24
12. 将{12，24，36，90，52，30}6个元素构成平衡二叉排序树，其根结点是（）。
A. 12
B. 24
C. 52
D. 36
13. 对于折半查找法，一般选择（）作为其存储结构。
A. 顺序表
B. 循环表
C. 双链表
D. 单链表
14. 基本有序的序列适合用（）排序算法进行排序。
A. 归并
B. 直接插入
C. 快速
D. 堆
15. 直接插入排序的时间复杂度是（）。
A. O（n2）
B. O（n）
C. O（nlog2n）
D. O（1）
16. 对序列{82 61 43 77}进行从头到尾的冒泡排序，第一趟扫描排序结果为（）。
A. 61 82 43 77
B. 61 43 77 82
C. 61 43 82 77
D. 43 61 77 82
17. 判别下列序列中，不是堆的是（）。
A. （3，7，17，25，36，47，85，29，52）
B. （82，57，63，41，35，48，52，21，30）
C. （5，8，10，12，30，9，17，36，45）
D. （95，43，65，23，38，57，80，15，17）
18. 对序列{45 53 58 36 72 30 48 93}进行归并排序，第二趟两两归并结果为（）。
A. （36 45 53 58） （30 48 72 93）
B. （45 53 58 36）（72 30 48 93）
C. （45 53）（36 58）（30 72）（48 93）
D. （30 36 45 48 53 58 72 93）
19. 下列关于回溯法的描述错误的是（）。
A. 回溯法按照规则去试探
B. 回溯法就是是穷举式搜索
C. 回溯法中候选解满足问题的所有要求，该候选解就是问题的一个解
D. 回溯是指放弃当前的候选解，退到上一步
20. 将大问题化为相互独立的相同的小问题，然后各个击破，解决完小问题后再合成大问题的解是（）算法的算法思想。
A. 动态规划算法
B. 分治法
C. 回溯算法
D. 贪心算法
21. 有n个顶点的有向完全图，有n（n-1）条边。
A. 对
B. 错
22. 有向图的邻接矩阵一定是不对称的。
A. 对
B. 错
23. 邻接表只适于无向图的存储，不适合有向图的存储。
A. 对
B. 错
24. 一个图可以有多个生成树。
A. 对
B. 错
25. n个顶点的连通图G的生成树含有n-1条边。
A. 对
B. 错
26. 如果表中不存在想要查找的关键字，则查找失败。
A. 对
B. 错
27. 如果二叉排序树的左子树不空，则左子树上结点的值均大于根结点的值。
A. 对
B. 错
28. 对于最小堆来说，堆顶结点具有最大值。
A. 对
B. 错
29. 当待排序的记录数目n较小时，适合采用直接插入法进行排序。
A. 对
B. 错
30. N后问题最常用回溯法解决。
A. 对
B. 错