第 2 次作业一、单项选择题（本大题共 60 分，共 20 小题，每小题 3 分）1. 按克鲁斯卡尔算法建的最小生成树（ ）。A. 只有一种B. 有多种C. 不确定2. 以下关于单链表的叙述中，错误的是（ ）。A. 在单链表中插入一个结点必须先找到其前驱结点B. 在单链表中删除一个结点必须先找到其前驱结点C. 在单链表中只能通过结点的 next 指针向后查找结点D. 在单链表中查找第 i 个结点的时间复杂度是 O(1)3. 输入序列为 ABC，可以变为 CBA 时，经过的栈操作为（ ）。A. push,pop,push,pop,push,popB. 5D. 6二、判断题（本大题共 40 分，共 20 小题，每小题 2 分）1. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用求最短路径的 Dijkstra 方法。2. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。3. 散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。4. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。5. 一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。6. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。7. Hash 表的平均查找长度与处理冲突的方法无关。8. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。9. 一个稀疏矩阵 Am*n 采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把 m 和 n 的值互换，则就完成了 Am*n 的转置运算。10. 图的遍历要求从图的某一顶点出发，访遍图中的其余顶点，且每个顶点仅被访问一次。11. 迷宫求解问题中经常用到顺序表来存储数据。12. 邻接多重表的建立及其各种基本操作的实现和邻接表相似13. 建立十字链表和建立邻接表的时间复杂度是相同的。14. 用链表(llink-rlink)存储包含 n 个结点的二叉树，结点的 2n 个指针区域中有 n-1 个空指针。15. 表达式求值问题中经常用到顺序表来存储数据。16. 在待排数据基本有序的情况下，快速排序效果最好。17. 括号匹配的检验中经常用到单链表来存储数据。18. 哈希表的结点中只包含数据元素自身的信息，不包含任何指针。19. 设 T 为一棵平衡树，在其中插入一个结点 n，然后立即删除该结点后得到T1，则 T 与 T1 必定相同。20. 最佳二叉树是 AVL 树（平衡二叉树）答案： 一、单项选择题（60 分，共 20 题，每小题 3 分）1. C 2. D 3. B 4. A 5. A 6. B 7. A 8. C 9. B 10. C 11. A 12. A 13. D 14. A 15. D 16. D 17. B 18. B 19. A 20. C 二、判断题（40 分，共 20 题，每小题 2 分）1. × 2. √ 3. √ 4. √ 5. √ 6. × 7. × 8. √ 9. × 10. √ 11. × 12. √ 13. √ 14. × 15. × 16. × 17. × 18. × 19. × 20. √ push,push,push,pop,pop,popC. push,push,pop,pop,push,popD. push,pop,push,push,pop,pop4. 如图所示，可得到一个拓扑排序序列（ ）。A. v1,v6,v4,v3,v2,v5B. v1,v2,v6,v4,v3,v5C. v1,v2,v6,v3,v4,v5D. v1,v4,v6,v3,v2,v5 5. 下列排序方法中，哪一个是稳定的排序方法？（ 　） A. 简单选择排序 B. 堆排序C. 希尔排序 D. 快速排序6. 一棵二叉树高度为 h,所有结点的度或为 0，或为 2，则这棵二叉树最少有（ ）结点。A. 2h B. 2h-1C. 2h+1D. h+17. 平衡二叉树的平衡因子的取值可能是（ ）。A. 1B. 2C. 3D. 48. 一个有 n 个顶点的无向图最多有（ ）条边。A. n　B. n(n-1)C. n(n-1)/2　D. 2n9. 在迷宫求解问题中，用（）作为转换过程中的数据存储结构。A. 线性表B. 栈C. 队列 D. 单链表10. 计算机算法指的是（ ）。A. 计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法11. 基数排序是（ ）。A. 稳定的B. 不稳定的C. 看具体情况 D. 未知 12. 对（70.83.100.65.10.32.7.9）进行简单选择排序，排序后第一趟结果为（ ）。A. 7.83.100.65.10.32.70.9B. 7.9.100.65.10.32.70.83C. 7.9.10.65.100.32.70.83D. 7.9.10.32.100.65.70.8313. 对于一个有向图的逆邻接链表表示，第 i 个链表中有 x 个结点，则顶点 i 的出度为（ ）。A. xB. x+1C. x+iD. 无法确定14. 1348 转化为 8 进制结果是（ ）。A. 2504B. 2405C. 4052D. 205415. 二维数组 A［10］［20］采用按行为主序的存储方式，每个元素占 4 个存储单元，若 A［0］［0］的存储地址为 300，则 A［10］［10］的地址为（ ）。A. 700B. 1120C. 1180D. 114016. 已知 Head(Tail([Head(S),Head(Tail(Tail(S)))]))=[a]，广义表 S 满足上式，则 S 为（ ）(其中，方括号表示广义表，圆括号表示函数，如[a,b]表示由a,b 构成的广义表，而 Head()表示取广义表的头部）。A. [[a,b],b,a] B. [[b,a],[a],[b]] C. [[a],[a,b],[b]]D. [[b],[b,a],[a]]17. 若 X 是二叉中序线索树中一个有左孩子的结点，且 X 不为根，则 x 的前驱为（ ）。A. X 的双亲B. X 的右子树中最左的结点 C. X 的左子树中最右结点 D. X 的左子树中最右叶结点18. 在对应于序列(12，5，8，15，25，10，30，7)的二叉排序树中查找 30需要进行多少次比较。（ ）A. 1B. 2 C. 3D. 419. 对长度为 155 的顺序表在等概率情况下进行顺序查找的平均查找长度为（ ）。A. 78B. 77.5C. 155D. 15620. 对于三个结点的二叉树有多少种形态？ （ ）A. 3B. 4C.