1、 第 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,pop B. push,push,pus
2、h,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 4. 如图所示，可得到一个拓扑排序序列（ ）。 A. v1,v6,v4,v3,v2,v5 B. v1,v2,v6,v4,v3,v5 C. v1,v2,v6,v3,v4,v5 D. v1,v4,v6,v3,v2,v5 5. 下列排序方法中，哪一个是稳定的排序方法？（ ） A. 简单选择排序 B. 堆排序 C. 希尔排序 D. 快速排序 6. 一棵二叉树高度为 h,所有结点的度或为 0，或为 2，则这棵二叉树最少有（ ）结点。 A. 2h B. 2h-
3、1 C. 2h+1 D. h+1 7. 平衡二叉树的平衡因子的取值可能是（ ）。 A. 1 B. 2 C. 3 D. 4 8. 一个有 n个顶点的无向图最多有（ ）条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 9. 在迷宫求解问题中，用（）作为转换过程中的数据存储结构。 A. 线性表 B. 栈 C. 队列 D. 单链表 10. 计算机算法指的是（ ）。 A. 计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 11. 基数排序是（ ）。 A. 稳定的 B. 不稳定的 C. 看具体情况 D. 未知 12. 对（ 70.83.100.65.10.32.7
4、.9）进行简单选择排序，排序后第一趟结果为（ ）。 A. 7.83.100.65.10.32.70.9 B. 7.9.100.65.10.32.70.83 C. 7.9.10.65.100.32.70.83 D. 7.9.10.32.100.65.70.83 13. 对于一个有向图的逆邻接链表表示，第 i 个链表中有 x个结点，则顶点 i的出度为（ ）。 A. x B. x+1 C. x+i D. 无法确定 14. 1348转化为 8 进制结果是（ ）。 A. 2504 B. 2405 C. 4052 D. 2054 15. 二维数组 A 10 20采用按行为主序的存储方式，每个元素占 4个存
5、储单元，若 A 0 0的存储地址为 300，则 A 10 10的地址为（ ）。 A. 700 B. 1120 C. 1180 D. 1140 16. 已知 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的右子树
6、中最左的结点 C. X的左子树中最右结点 D. X的左子树中最右叶结点 18. 在对应于序列 (12， 5， 8， 15， 25， 10， 30， 7)的二叉排序树中查找 30需要进行多少次比较。（ ） A. 1 B. 2 C. 3 D. 4 19. 对长度为 155的顺序表在等概率情况下进行顺序查找的平均查找长度为（ ）。 A. 78 B. 77.5 C. 155 D. 156 20. 对于三个结点的二叉树有多少种形态？ （ ） A. 3 B. 4 C. 5 D. 6 二、判断题（本大题共 40 分，共 20 小题，每小题 2 分） 1. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外
7、，还可以利用求最短路径的 Dijkstra 方法。 2. 在索引顺序表中，实现分块查找，在等概率查找情 况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。 3. 散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。 4. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 5. 一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。 6. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。 7. Hash表的平均查找长度与处理冲突的方法无关。 8. 完全二叉树中，若一个
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，然后立即删除该结点后得到
