复习题一及答案.pdfVIP

复习题一

1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复

杂度为(A)。

A.O(n)B.O(n/2)

2

C.O(1)D.O(n)

2.在有向图中每个顶点的度等于该顶点的(C)。

A.入度B.出度

C.入度与出度之和D.入度与出度之差

3.下列排序算法中(C)是不稳定的排序算法。

A.冒泡排序B.合并排序

C.快速排序.D.插入排序

4.在单链表中，q指向待删除结点的前驱，p指向待删除的结点，则删

除节点的操作是(B)。

A.p=q-next；q-next=p-next;free(p);

B.q-next=p;q-next=p-next;free(p);.

C.p=q-next;free(p);q-next=p-next;

D.p=q-next;p=p-next;free(p);

5.栈操作的基本原则(B).

第1页共9页

A.先进先出B.先进后出

C.只能进行插入D.只能进行删除

6.设有一个顺序栈S，元素S1，S2，S3，S4，S5，S6依次入栈，若有6

个元素出栈的顺序是S2，S3，S4，S6，S5，S1。则该栈的容量至少应

该是（B）。

A．2B．3C．4D．5

9.具有50个结点的完全二叉树，编号为19的结点的左孩子编号为

(C)

A.46B.39

C.38D.不存在

10.若一棵二叉树具有10个度为2的节点，5个度为1的节点，则度为

零的节点个数是(B).

A.9B.11

C.15D.不确定

11.有n个顶点的无向图最多有(B)条边。

A.n-1B.n*(n-1)/2

C.n*(n+1)/2D.n*n

12.对下图G，若从顶点a出发，按深度有哪些信誉好的足球投注网站法，进行遍历，则可能得到

的一种顶点序列为(D)，按广度有哪些信誉好的足球投注网站法进行遍历，则可能得到的一种

顶点序列为(B)。

第2页共9页

A.abecfdB.abcefd

C.aebcfdD.aedfcb

13.在一个无向图中，所有顶点度数之和等于所有边数(B)倍，在一个

有向图中，所有顶点入度数之和等于所有顶点出度之和的(C)倍。

A.1/2B.2

C.1D.4

二、填空题：（每空1分，共10分）

1.选择合适的存储结构，通常考虑的指标是空间复杂度和_时间复杂度

__。

2.对