第 2 次作业一、单项选择题（本大题共 60 分，共 20 小题，每小题 3 分）1. 已知图 G 的邻接表如图所示，其从 v1 顶点出发的广度优先搜索序列为（）。A. 1、2、5、4、3、6B. 1、2、3、6、5、4C. 1、4、3、6、2、5D. 1、2、6、5、4、32. 在数制转换中，用（ ）作为转换过程中的数据存储结构。A. 线性表 C. 3D. 420. 对长度为 155 的顺序表在等概率情况下进行顺序查找的平均查找长度为（ ）。A. 78B. 77.5C. 155D. 156二、判断题（本大题共 40 分，共 20 小题，每小题 2 分）1. 带头结点的双循环链表 L 为空表的条件是：L->next==L。2. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用求最短路径的 Dijkstra 方法。3. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。4. 散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。5. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 6. 一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。7. 数制转换过程中经常用到栈来存储数据。8. Hash 表的平均查找长度与处理冲突的方法无关。9. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。10. 一个稀疏矩阵 Am*n 采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把 m 和 n 的值互换，则就完成了 Am*n 的转置运算。11. 图的遍历要求从图的某一顶点出发，访遍图中的其余顶点，且每个顶点仅被访问一次。12. 排序算法中的比较次数与初始元素序列的排列无关。13. 一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。14. 邻接多重表的建立及其各种基本操作的实现和邻接表相似15. 用链表(llink-rlink)存储包含 n 个结点的二叉树，结点的 2n 个指针区域中有 n-1 个空指针。16. 表达式求值问题中经常用到顺序表来存储数据。17. 迷宫求解问题结束时，若栈空，则表明没有路径存在。18. 从一个地方到另一个地方的路径长度表示该路径上各边的权值之和。19. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。20. 括号匹配的检验中经常用到单链表来存储数据。答案：一、单项选择题（60 分，共 20 题，每小题 3 分）1. A 2. B 3. B 4. D 5. A 6. C 7. D 8. B 9. A 10. B 11. C 12. D 13. C 14. C 15. A 16. D 17. B 18. A 19. B 20. A 二、判断题（40 分，共 20 题，每小题 2 分）1. × 2. × 3. √ 4. √ 5. √ 6. √ 7. √ 8. × 9. √ 10. × 11. √ 12. × 13. √ 14. √ 15. × 16. × 17. √ 18. √ 19. × 20. × B. 栈C. 队列D. 单链表3. 下面程序段的时间复杂度是（ ）。 i ＝ 0； while（i<=n） i = i * 3； A. O（3n） B. O(log3n) C. O(n3) D. O(n2) 4. n 个节点无向连通图的最小生成树有（ ）条边。A. n(n-1)/2B. n(n-1) C. nD. n-15. 如图所示，可得到一个拓扑排序序列（ ）。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 6. 下列（ ）不是算法设计的原则。A. 正确性B. 可读性C. 可行性D. 健壮性7. 用链接方式存储的队列，在进行删除运算时（ ）。A. 仅修改头指针B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改8. 利用栈求表达式的值时，设立运算符栈 OPEN。假设 OPEN 只有 2 个存储单元，在下列表达式中，不发生溢出的是（）。A. A-B*(C-D)B. (A-B)*C-DC. (A-B*C)-DD. (A-B)*(C-D)9. 平衡二叉树的平衡因子的取值可能是（ ）。A. 1B. 2C. 3D. 410. 可以用数据对象、（ ）和基本操作集定义一个完整的抽象数据类型。A. 数据元素B. 数据关系 C. 原子类型D. 存储结构11. 一个有 n 个顶点的无向图最多有（ ）条边。A. n　B. n(n-1)C. n(n-1)/2　D. 2n12. 某线性表中最常用的操作是在最后一个元素之后插入一个元素或者删除最后一个元素，则采用（ ）存储方式最节省运算时间。A. 单链表B. 仅有头指针的单循环链表C. 双向链表D. 带头结点的双单循环链表13. 快速排序算法是对什么算法的改进？（ ） A. 直接插入排序 B. 希尔排序C. 起泡排序D. 以上答案都不对14. 有六个元素 6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列。（）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 615. 对（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.8316. 已知 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. 在一棵二叉树中，度为 2 的结点有 2 个，那么，该树有（ ）个叶结点。A. 3B. 4C. 5D. 619. 在对应于序列(12，5，8，15，25，10，30，7)的二叉排序树中查找 30需要进行多少次比较。（ ）A. 1B. 2