1、第 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. 线性表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(
2、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,v56. 下列（ ）不是算法设计的原则。A. 正确性B. 可读性C. 可行性D. 健壮性7. 用链接方式存储的队列，在进行删除运算时（ ）。A. 仅修改头指针B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改8. 利用栈求表达式的值时，设立运算符栈 OPEN。假设 OPEN只有 2个存储单元，在下列表达式中，不发生溢出的是
3、（）。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.
4、 带头结点的双单循环链表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.8
5、3D. 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,bD. b,b,a,a17. 若 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. 2C. 3D. 420. 对长度为 155的顺序表在等概率情况下进行顺序查找的平均查找长度为（ ）。A. 78B. 77.5C. 155D. 156
