国家开放大学《数据结构与算法》形考作业2答案最新答案

题目1：无向图的顶点个数为n，则图中边数的最大值为（ ）。
A. n× (n-1)
B. n× (n-1)/2
C. n-1
D. n
答案： n× (n-1)/2
题目2：在一个无向图中，所有顶点的度数之和等于所有边数的（ ）。
A. 3倍
B. 2倍
C. 1倍
D. 0.5倍
答案： 2倍
题目3：在图的邻接矩阵存储结构中删除一个顶点，下列说法错误的是（ ）。
A. 直接在删除顶点处做删除标记即可
B. 删除顶点顺序表中的该顶点
C. 删除邻接矩阵中该顶点所在的行
D. 删除邻接矩阵中该顶点所在的列
答案： 直接在删除顶点处做删除标记即可
题目4：一个有e条边的无向图，邻接表中包含的边结点的总数是（ ）。
A. e
B. e-1
C. e+1
D. 2e
答案： 2e
题目5：对于下图的无向图，插入一个顶点E后，顶点顺序表为（ ）。
A. 选项A
B. 选项B
C. 选项C
D. 选项D
答案： 选项C
题目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. 错