浙江大学城市学院软件基础在线测试题

折半查找值为82的结点时，____________次比较后查找成功。 A. 4 B. 2 C. 1 D. 8 正确答案是 ：A

4.

具有65个结点的完全二叉树的高度为__________。 A. 8 B. 7 C. 6 D. 5 正确答案是 ：B

5.

已知一有向图G的邻接表的存储结构如下图所示：（说明：图中的0对应顶点v1，1对应顶点v2，2345分别对应了顶点v3v4v5v6）则基于该存储表示，从顶点v1出发，用广度优先遍历算法得到的顶点序列是_________ 。 A. v1 v2 v3 v5 v4 v6 B. v1 v2 v5 v6 v4 v3

C. v1 v2 v5 v3 v4 v6 D. v1 v2 v3 v4 v5 v6 正确答案是 ：A

6.

设有一个顺序栈S，元素s1， s2， s3， s4， s5， s6依次进栈，如果6个元素的出栈顺序为s2， s3， s4， s6， s5， s1，则顺序栈的容量至少应为_________ A. 2 B. 3 C. 4 D. 5 正确答案是 ：B

7.

若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为____________ A. i B. n=i C. n-i+1 D. 不确定 正确答案是 ：C

8.

把一棵树转换为二叉树后，这棵二叉树的形态是_______。 A. 唯一的

B. 有多种，但根结点都没有左孩子 C. 有多种

D. 有多种，但根结点都没有右孩子 正确答案是 ：A

9.

在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A. 1/2 B. 1 C. 2 D. 4 正确答案是 ：B

10.

有8个结点的无向图最多有 条边。 A. 14 B. 28 C. 56

D. 112 正确答案是 ：B

11.

有8个结点的无向连通图最少有 条边 A. 5 B. 6 C. 7 D. 8 正确答案是 ：C

12.

折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素___比较大小。 A. 28，6，12，20 B. 38,12,20 C. 20

D. 38,70,88,100 正确答案是 ：A

13.

给定n=8，对数组R中的8个元素做升序排列，数组R中的关键字为：（8，3，2，1，7，4，6，5），则简单选择排序过程中第二趟排序结束后关键字的顺序