数据结构复习资料--覆盖所有知识点

数据结构复习及答案

一、选择填空

1. 下面关于线性表的叙述中，错误的是哪一个？（ B ） A）线性表采用顺序存储，必须占用一片连续的存储单元。 B）线性表采用顺序存储，便于进行插入和删除操作。 C）线性表采用链接存储，不必占用一片连续的存储单元。 D）线性表采用链接存储，便于插入和删除操作。

2. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用

（ A ）存储方式最节省时间。

A）顺序表 B）双链表 C）带头结点的双循环链表 D）单循环链表 3. 链表不具有的特点是（ B ）。

A）插入、删除不需要移动元素 C）不必事先估计存储空间

B）可随机访问任一元素 D）所需空间与线性长度成正比

4. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度

为（ C ）(1<=i<=n+1)。 A）O(0) B）O(1)

C）O(n) D）O(n2)

5. 线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂度为（ C ）。

A）O(i) B）O(1) C）O(n) D）O(i-1)

6. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ B ）。 A）p->next=s;s->next=p->next; B） s->next=p->next;p->next=s; C）p->next=s;p->next=s->next; D） p->next=s->next;p->next=s;

7. 设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为( A )。

A）p->next=p->next->next C）p=p->next->next

B） p=p->next D） p->next=p

8. 在双向链表指针p的结点前插入一个指针q的结点操作是（ C ）。

A） p->prior=q;q->next=p;p->prior->next=q;q->prior=q； B） p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior; C） q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;

D） q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;

9. 在双向链表存储结构中，删除p所指的结点时须修改指针（ A ）。 A） (p->prior)->next=p->next (p->next)->prior=p->prior; B） p->prior=(p->prior)->prior (p->prior)->next=p; C） (p->next)->prior=p p->next=(p->next)->next

D） p->next=(p->prior)->prior p->prior=(p->next)->next; 10. ( A )又称为FIFO表；( C )又称为FILO表。

1

A）队列 B）散列表 C）栈 D）哈希表

11. 对于栈操作数据的原则是（B）。

A）先进先出 B）后进先出 C）后进后出 D）不分顺序

12. 用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则

在进行删除操作时( D )。 A）仅修改队头指针

B）仅修改队尾指针

D）队头、队尾指针都可能要修改

C）队头、队尾指针都要修改

13. 假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素

个数为（ A ）。

A）(rear-front+m)%m B）rear-front+1 C）(front-rear+m)%m D）(rear-front)%m 14. 栈和队列的共同点是（ C ）。

A）都是先进先出

B）都是先进后出

C）只允许在端点处插入和删除元素 D）没有共同点

15. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈

后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。 A） 6 B）4 C）3 D）2

16. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储

地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。 A）12

B）33

C）18

D）40

17. 设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组

B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为( B )。 A）i(i-l)/2+j

B）j(j-l)/2+i C）j(j-l)/2+i-1 D）i(i-l)/2+j-1

18. 由3 个结点可以构造出多少种不同的二叉树？( D ) A）2

B）3

C）4

D）5

19. 二叉树中第i(i≥1)层上的结点数最多有( C )个。

A） 2i

B） 2i

C） 2i-1

D） 2i-1

20. 在有n个叶子结点的哈夫曼树中，其结点总数为( D )。

A）不确定

B）2n C）2n+1

D）2n-1

21. 一棵二叉树高度为h，所有结点的度或为0、或为2，则这棵二叉树最少有( A )结点。

A）2h

B）2h-1

C）2h+1

D）h+1

22. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( A )。

A）9

B）11

C）15

D）不确定

23. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为( D )。

A）5

B）6

C）7

D）8

24. 树的后根遍历序列等同于该树对应的二叉树的( B )。

2

A）先序序列 B）中序序列 C）后序序列 25. 在下列存储形式中，哪一个不是树的存储形式？( D )

D.层序序列

A）双亲表示法 B）孩子链表表示法 C）孩子兄弟表示法 D）顺序存储表示法 26. 在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序( B )。

A）都不相同

B）完全相同

D）中序和后序相同，而与先序不同

C）先序和中序相同，而与后序不同

27. 下列哪一种图的邻接矩阵是对称矩阵？( B )

A）有向图 B）无向图 C）AOV网 D）AOE网

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

入度之和等于所有顶点出度之和的( C )倍。 A）1/2

B）2

C）1

D）4

29. 一个有n个顶点的无向图最多有( D )条边。由n个顶点组成的有向图，最多可以有( D )条

边。 A）n*n

B）2n C）n(n-1)

D）n(n-1)/2

30. 下列说法不正确的是( C )。

A）图的遍历是从给定的源点出发每一个顶点仅被访问一次 B）遍历的基本算法有两种：深度遍历和广度遍历 C）图的深度遍历不适用于有向图 D）图的深度遍历是一个递归过程

31. 下面哪一方法可以判断 …… 此处隐藏：4018字，全部文档内容请下载后查看。喜欢就下载吧 ……