数据结构（C语言版）复习题

一、单项选择题：

1、树形结构不具备这样的特点：（ ）

A. 每个节点可能有多个后继（子节点） B. 每个节点可能有多个前驱（父节点）

C. 可能有多个内节点（非终端结点） D. 可能有多个叶子节点（终端节点） 2、二叉树与度数为2的树相同之处包括（ ）。

A. 每个节点都有1个或2个子节点 B. 至少有一个根节点 C. 至少有一个度数为2的节点

D. 每个节点至多只有一个父节点

3、一棵完全二叉树有999 个结点，它的深度为（ ）。

A．9 B．10 C．11 D．12

4、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（ ） A. s->next=p;p->next=s; B. s->next=p->next;p->next=s; C. s->next=p->next;p=s; D. p->next=s;s->next=p;

5、对于一棵具有n个结点、度为5的树来说，（ ） A. 树的高度至多是n-3 B. 树的高度至多是n-4 C. 树的高度至多是n D. 树的高度至多是n-5 6、在顺序队列中，元素的排列顺序（ ）。

A. 由元素插入队列的先后顺序决定

B. 与元素值的大小有关

C. 与队首指针和队尾指针的取值有关 D. 与数组大小有关

7、串是一种特殊的线性表，其特殊性体现在（ ）。

A．可以顺序存储 B．数据元素是一个字符 C．可以链式存储 D．数据元素可以是多个字符若

8、顺序循环队列中（数组的大小为 6），队头指示 front 和队尾指示 rear 的值分别为 3 和 0，当从队列中删除1个元素，再插入2 个元素后，front和 rear的值分别为（ ）。 A．5 和1 B．2和4 C．1和5 D．4 和2

9、一棵完全二叉树上有1001 个结点，其中叶子结点的个数为（ ）。 A．250 B．500 C．254 D．501

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

A．adbefc B．adcefb C．adcebf D．adefbc

第 1 页 共 8 页

11、在一个带权连通图G 中，权值最小的边一定包含在G 的（ ）。 A．最小生成树中 B．深度优先生成树中 C．广度优先生成树中 D．深度优先生成森林中

12、适用于折半查找的表的存储方式及元素排列要求为（ ）。 A．链式方式存储，元素无序 B．链式方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 13、含有27个关键字节点的平衡二叉树（AVL树）（ ）

A. 有13个度数为2的节点 B. 最大高度为6 C. 最低高度是6

D. 有14个度数为0的节点

14、任何一个无向连通图的最小生成树（ ）。

A. 有一棵或多棵 B. 只有一棵 C. 一定有多棵 D. 可能不存在 15、下述几种排序方法中,要求内存量最大的是（ ）。

A．插入排序 B．选择排序 C．快速排序 D．归并排序 16、以下属于逻辑结构的是（ ）

A. 顺序表 B. 哈希表 C. 有序表 D. 单链表 17、一个有n个顶点的无向图最多有（ ）条边。

A. n B. n(n-1) C. n(n-1)/2 D. 2n 18、下面（ ）算法适合构造一个稠密图G的最小生成树。

A． Prim算法 B．Kruskal算法 C．Floyd算法 D．Dijkstra算法 19、下面哪个术语与数据的存储结构无关（ ）。

A．顺序表 B．链表 C．散列表 D．队列

20、无向图G=（V，E）， 其 中 ：V={a,b,c,d,e,f}，E={（a,b），（a,e），（a,c），（b,e） ，（c,f），（f,d），（e,d）}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。

A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 21、如下图所示带权无向图的最小生成树的权为（ ）。 A．14 B．15 C．17 D．18

22、以下排序方法中，不稳定的排序方法是（ ）。

A．直接选择排序 B．二分法插入排序

第 2 页 共 8 页

C．归并排序 D．基数排序

23、下列哪一个选项不是下图所示有向图的拓扑排序结果（ ）。 A．AFBCDE B．FABCDE C．FACBDE D．FADBCE

24、参加排序的记录可以具有相同的关键码。当一个排序方法在排序过程中不改变这种相同关键码记录的原始输入顺序时，称之为稳定的；反之称为不稳定的。下面4种排序方法中，属于不稳定的排序方法是（ ）。

A. 快速排序

B. 冒泡排序 C. 简单选择排序 D. 折半插入排序

25、链式存储设计时，结点内的存储单元地址（ ）

A. 一定连续 B. 一定不连续

C. 不一定连续 D. 部分连续，部分不连续

26、若一个栈的进栈序列是1,2,3,?,n,其输出序列是p1,p2,?,pn,若p1=n,则pi的值是（ ）。

A. i

B. n-i

C. n-i+1

D. 不确定

27、以下有关二叉树的说法正确的是（ ）。

A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任一个结点的度均为2 28、一棵具有5 层的满二叉树所包含的结点个数为（ ）。 A．15 B．31 C．63 D．32

29、在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键字为45、 89 和 12的结点时，所需进行的比较次数分别为（ ）。 A．4，4，3 B．4，3，3 C．3，4，4 D．3，3，4

30、一个序列中有 10000 个元素，若只想得到其中前 10 个最小元素，最好采用（ ）

方法。

A．快速排序 B．堆排序 C．插入排序 D．二路归并排序

31．若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上（ ） A．操作的有限集合 B．映象的有限集合 C．类型的有限集合 D．关系的有限集合

32．在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head，则（ ）

第 3 页 共 8 页

A．p指向头结点 C．*P的直接后继是尾结点

B．p指向尾结点

D． *p的直接后继是头结点

33．在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（ ） A．O(1) B．O(n)

C．O(nlogn) D．O(n2)

34．队列和栈的主要区别是（ ）

A．逻辑结构不同 B．存储结构不同

C．所包含的运算个数不同 D．限定插入和删除的位置不同

35．若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为（ ） A．4 B．5

C．6

D．7

36．一棵含18个结点的二叉树的高度至少为( ) A．3

B．4

C．5

D．6

37．在一个带权连通图G中，权值最小的边一定包含在G的（ ） A．最小生成树中

B．深度优先生成树中 D．深度优先生成森林中

C．广度优先生成树中

二、填空题：

1、 树最适合用来表示具有（ ）性和（ ）性的数据。

2、设有一批数据元素,为了最快的存储某元素,数据结构宜用（ ）结构,为了方便

插入一个元素,数据结构宜用（ ）结构。

3、在顺序表的（ ）后面插入一个元素，不需要移动任何元素。 4、设循环队列的容量为40（ ），队头指针为front，队尾指针为rear；现经过一系列的入队和出队运算后，队头与队尾指针分别指向front=11，rear=19，则可求出循环队列中有（ ）个元素。

5、哈夫曼树是带权路径长度（ ）的二叉树，又称最优二叉树。

6、前序遍历和中序遍历结果相同的二叉树为（ ）；前序遍历和后序遍历结果相同的二叉树为（ ）。

7、在一个长度为n的顺序表中删除第i个元素（ ）时，需向前移动（ ）个元素。 8、线性的数据结构包括：（ ）、（ ）、（ ）和数组、串。 9、访问单向链表的节点，必须顺着（ ）依次进行。

10、设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。 11、数据结构涉及三个方面的内容，即( )、( )和( )。 12、具有4个顶点的无向完全图有( )条边。

三、判断对错题：

第 4 页 共 8 页