●某有向图中含有n个顶点，则其有向边的数目最多为(5)。对于n个顶点k条边的无向连通图，利用Prim算法生成最小生成树的时间复杂度为(6)，利用Kruskal算法生成最小生成树的时间复杂度为(7)。
(5)A.n-1
B.n
C.n(n一1)
D.n(n一1)/2
(6)A.0((n+1)2)
B.0(n2+1)
C.0(n2-1)
D.0(n2)
(7)A.O(log2k)
B.O(log2k-1)
C.0(klog2k)
D.以上都错
答案：(5)C(6)D(7)C
解析：边最多的情况是：每个顶点到其他点均有一条边。此时没点有n一1条边，于是n个点共有n(n-1)条，由于是有向图，各边并不重复。利用Prim算法生成最小生成树的时间复杂度只与顶点数有关，复杂度为o(n2);Kruskal算法生成最小生成树的时间复杂度只与边数有关，为0(klog2k)。
●某二叉树上的两个结点a、b，在(8)情况下，中序序列中a在b之前。
(8)A.a在b的右子树上
B.a在b的左子树上
C.a是b的祖先
D.a是b的子孙
答案：(8)B
解析：中序序列中，根结点总是在它的左子树的结点之后，右子树的结点之前。
●某线索二叉链表有k个结点中，则线索指针个数为(9)。
(9)A.k
B.k-1
C.k+1
D.k+10
答案：(9)C
解析.二叉链表中。线索指针个数比结点个数多1。
●某无向图有n个顶点e条边，则它的邻接表边表结点总数为(10)。
(10)A.n
B.e
C.2e
D.n+e
答案：(10)C
解析：一条边显然与两个顶点相联系，所以被记录2次。因此边表结点总数为2e。
●在某关键字互不相同的二叉排序树中，命题：最小元必无左孩子，最大元必无右孩子。是(11)。最小元和最大元一定是(12)。
(11)A.不正确
B.正确
C.命题错误
D.无法确定
(12)A.不是叶子节点
B.叶子节点
C.无法确定
D.以上都错
答案：(11)B(12)C
解析：在关键字互不相同的二叉排序树中，若最小元有左孩子，则左孩子小于该结点，与它是最小元矛盾。同理可知，最大元必无右孩子。最大元和最小元不一定是叶子结点。最小元可以有右结点，最大元可以有左孩子。
●某hash函数散列地址空间为0…n-1，k为关键字，假定散列函数为h(k)=k%P，当P为(13)时，冲突最小。
(13)A.小于n的最大素数
B.小于n的最大奇数
C.小于n的最大合数
D.小于n的最大偶数
答案：(13)A
解析：当P为小于n的最大素数时。散列函数的冲突比较小。
