2013年10月自学考试数据结构导论试题

课程代码：02142

请考生按规定用笔将所有试题的答案涂、写在答题纸上。

选择题部分

注意事项：

1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。

一、单项选择题(本大题共15小题，每小题2分，共30分)

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。

1．下列几种算法时间复杂度中，最大的是

A．O（1）                                                  B.O（n）

C.O（nlog₂n）                                             D.O（n²）

2．数据结构中结点按逻辑关系依次排列形成一条“链”的结构是

A．集合                                                      B.图结构

C.树形结构                                                 D.线性结构

3．在表长为100的顺序表中做插入运算，平均移动元素的次数为

A．25                                                         B.33

C.50                                                            D.100

4．已知尾指针的单向循环链表中，在第一个结点后面插入一个新结点，该算法的时间复杂度为

A．O（1）                                                  B.O（log₂n）

C.O（n）                                                    D.O(n²)

5．下列表述正确的是

A．栈空时出栈产生“上溢”，栈满时进栈产生“下溢”

B.栈空时出栈产生“下溢”，栈满时进栈产生“上溢”

C.栈空时出栈和栈满时进栈均产生“上溢”

D.栈空时出栈和栈满时进栈均产生“下溢”

6.队列操作的原则是

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

C.先进后出                                                 D.只进不出

7．一棵深度为6的满二叉树有

A．63个结点                                              B.64个结点

C.127个结点                                               D.128个结点

8.在一棵度为3的树中，度为3的结点有4个，度为2的结点有2个，度为1的结点有3个，则度为0的结点有

A.8个                                                         B.10个

C.11个                                                        D.12个

9．一棵二叉树T，度为2的结点数为20个，则叶子结点数为

A．19个                                                     B.20个

C.21个                                                        D.22个

10．有10个叶结点的哈夫曼树中共有

A．10个结点                                              B.11个结点

C.19个结点                                                 D.21个结点

11．求图中两个结点之间的最短路径采用的算法是

A．广度优先搜索（BFS）算法                    B.克鲁斯卡尔（Kruskal）算法

C.普里姆（Prim）算法                                D.迪杰斯特拉（Dijkstra）算法

12．顺序查找算法的平均查找长度为

A．log₂n                                                      B.（n-1）/2

C.n/2                                                           D.（n+1）/2

13．二叉排序树中，根的

A．左子树是二叉排序树、右子树不一定是二叉排序树

B.左子树是二叉排序树、右子树也是二叉排序树

C.左子树不一定是二叉排序树、右子树是二叉排序树

D.左子树不一定是二叉排序树、右子树也不一定是二叉排序树

14．冒泡排序的时间复杂度为

A．O(n)                                                      B.O(nlog₂n)

C.O(n²)                                                       D.O(log₂n)

15．关于稳定性的表述，正确的是

A．稳定性是排序方法本身的特性，与数据无关

B.稳定性不是排序方法本身的特性，与数据有关

C.稳定性是排序方法本身的特性，与数据有关

D.稳定性不是排序方法本身的特性，与数据无关

非选择题部分

注意事项：

用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

二、填空题(本大题共13小题，每小题2分，共26分)

16．数据中不可分割的最小标识单位是__________。

17．双向循环链表中，在p所指结点的后面插入一个新结点*t，需要修改四个指针，分别为：t->prior=p；__________；p->next->prior=t；p->next=t；。

18.在带有头结点的循环链表中，头指针为head，判断指针p所指结点为首结点的条件是__________。

19．元素的进栈次序为1，2，3，…，n，出栈的第一个元素是n，则第k个出栈的元素是__________。

20．在栈结构中，允许插入和删除的一端称为__________。

21．100个结点的二叉树采用三叉链表存储时，空指针域NULL有__________个。

22.某二叉树的先序遍历序列为ABKLMNO，中序遍历序列为BLKANMO，则该二叉树中结点A的右孩子为结点__________。

23．一个二叉树的最少结点个数为__________。

24．图中第一个顶点和最后一个顶点相同的路径称为回路。除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为__________。

25．设查找表有n个数据元素，则二分查找算法的平均查找长度为__________。

26．用键值通过散列函数获取存储位置的这种存储方式构造的存储结构称为__________。

27．若在线性表中采用二分查找法查找元素，则该线性表必须按值有序，并且采用__________存储结构。

28．堆分为最小堆和最大堆，若键值序列{k₁,k₂,…，k_n}，满足 ，则这n个键值序列{k₁,k₂,…，k_n}是__________。

三、应用题(本大题共5小题，每小题6分，共30分)

29．设一个链栈的输入序列为X，Y，Z，试写出出栈的所有可能的输出序列及其操作步骤。

30．设二叉树的先序遍历序列为DCBAHEIFG，中序遍历序列为ABCHDIEFG，试画出该二叉树并写出后序遍历序列。

31．已知连通带权图如题31图所示，试利用普里姆（Prim）算法，从顶点A出发，构造它的最小生成树，画出构造过程。

32．给定表（28，15，55，3，71，75，10，22，56），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。

33．应用直接选择排序算法，对初始关键字序列为48，35，61，98，82，18，29，48的记录进行从小到大排序，写出排序过程和结果。

四、算法设计题(本大题共2小题，每小题7分，共14分)

34.单链表的结点结构定义如下：

typedef struct node

{ int data;

              struct node *next;

             }Node, *LinkList;

试编写在带头结点的单链表head中查找第1个元素值小于x的结点的实现算法Node *GetLinklist(LinkList head，int x)，若找到，则返回指向该结点的指针，否则返回NULL。

35．假设树采用孩子兄弟链表表示法，其结构定义如下：

typedef struct tnode

{ DataType data;

  struct tnode *son, *brother;

}*Tree;

试编写算法void leveltree(Tree root)实现树的按层次遍历。