数据结构附部分答案

一、 选择题

1、下面关于线性表的叙述错误的是( C )。

A.线性表采用顺序存储必须占用一片连续的存储空间 B.线性表采用链式存储不必占用一片连续的存储空间 C.线性表采用链式存储便于插入和删除操作的实现 D.线性表采用顺序存储便于插入和删除操作的实现

2、栈是一种特殊的线性表,具有( B )性质 A.先进先出 B.先进后出 C.后进后出 D.顺序进出

3、顺序循环队列中(数组大小为n),队头指示front指向队列的第一个元素,队尾指示

rear指向队列最后一个元素的后一个位置,则循环队列中存放了n-1个元素,即循环队列满的条件是 ( B )。

A.(rear+1)%n=front-1 B.(rear+1)%n=front C. (rear)%n=front D.rear+1=front

4、在一个单链表中,若删除p所指结点的后续结点,则执行( A )。 A. p->next=p->next->next B. p=p->next;p->next->next C.p->next=p->next D.p=p->next->next

5、设某二叉树中度数为0的结点数为N0,度数为1的结点数为Nl,度数为2的结点数为N2,

则下列等式成立的是( A )。

A. N0=N2+1 B.N0=Nl+N2 C. N0=N1+1 D.N0=2N1+l

6、设有6个结点的无向图,该图至少应有( D )条边才能确保是一个连通图。

A.8 B.6 C.7 D.5

7、设有向无环图G中的有向边集合E={<1,2>,<2,3>,<3,4>,<1,4>},则下列属于该

有向图G的一种拓扑排序序列的是( A )。

A.1,2,3,4 B. 2,3,4,1 C.1,4,2,3 D. 1,2,4,3

8、已知一个有向图如下所示,则从顶点a出发进行深度优先遍历,不可能得到的DFS序列为( A )。

A.a d b e f c B. a d c e f b C.a d c e b f D.a d e f b c

b

a 第 1 页 共 11 页 c e f d

9、适用于折半查找的表的存储方式及元素排列要求是( D )

A.链式方式存储,元素无序 B.链式存储方式,元素有序 C.顺序存储方式,元素无序 D.顺序存储方式,元素有序

10、设一组初始记录关键字序列为(345,253,674,924,627),则用基数排序需要进行

( C )趟的分配和回收才能使得初始关键字序列变成有序序列。 A. 5 B. 4 C. 3 D. 8 11、栈和队列的共同特点是( A )。

A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点

12、用链接方式存储的队列,在进行插入运算时( D ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改

13、以下数据结构中哪一个是非线性结构?( D )

A. 队列 B. 栈 C. 线性表 D. 二叉树

14、树最适合用来表示( C )。

A.有序数据元素 B.无序数据元素

C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 15、二叉树的第k层的结点数最多为( D ).

kk-1

A. 2-1 B.2K+1 C.2K-1 D. 2

16、设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为( A )。 (A) BADC (B) BCDA (C) CDAB (D) CBDA

前序遍历先访问根,所以C为根,在中序遍历中先访问左子树,再访问根,最后访问右子树,所以在中序序列中,C前面的为左子树,第二个访问的是左子树的根A以此类推可得这样的一棵二叉树:

第 2 页 共 11 页

17、下列四种排序中( D )的空间复杂度最大。 (A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序

18、对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K %9作为散列函数,则散列地址为1的元素有( D )个,

A. 1 B.2 C.3 D.4 分别是:55,64,46,10.

H(K)= K%9,表示除以9的余数。由于地址重叠造成冲突,所以散列存储时,通常还要有解决冲突的办法,如线性探查法等等。

19、设有6个结点的无向图,该图至少应有( A )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8

20、设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有( B )个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m

21. 对一个算法的评价,不包括如下( B )方面的内容。

A.健壮性和可读性 B.并行性 C.正确性 D.时空复杂度 22. 在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点,则执行( A )。

A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL;

23. 对线性表,在下列哪种情况下应当采用链表表示?( B )

A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变

24. 一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是( C )

A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 25. AOV网是一种( D )。

A.有向图 B.无向图 C.无向无环图 D.有向无环图

26. 下面程序的时间复杂为(B )

for(i=1,s=0; i<=n; i++) {t=1;for(j=1;j<=i;j++) t=t*j;s=s+t;}

234

(A) O(n) (B) O(n) (C) O(n) (D) O(n)

27.设某有向图的邻接表中有n个头结点和m个表结点,则该图中有(C )条有向边。 C (A) n (B) n-1 (C) m (D) m-1 有向图 m个表结点对应m条边,每条边都是有向的

第 3 页 共 11 页

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4