​数据结构导论2016年4月真题（02142）

数据结构导论2016年4月真题及答案解析（02142）

数据结构导论2016年4月真题及答案解析（02142），该试卷为数据结构导论自考历年真题试卷，包含答案及详细解析。

一、单项选择题(本大题共15小题。每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。

1.一个公司的组织机构是1名公司经理领导若于名部门负责人、每个部门负责人领导若干名部门员工，则适合于描述该公司组织机构的逻辑结构是(　　)

A.线性表
B.队列
C.树
D.图

2.计算n!(整数n≥0)的递归算法是：int Factorial(int n) { if(n==0) return 1; else return n*Factorial(n-1); }其时间复杂度为(　　)

A.O(n)
B.O(log₂n)
C.O(n^C)
D.O(n²)

3.将一个由指针q指向的结点插在单链表中由指针p所指向的结点之后的操作是(　　)

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

4. 设初始栈为空，s表示入栈操作，x表示出栈操作，则合法的操作序列是(　　)

A.sxxssxxs
B.ssxsxxxs
C.ssxxxssx
D.sssxxxsx

5.将递归形式描述的算法改写为功能等价的非递归形式描述的算法，通常应设置的辅助结构是(　　)

A.顺序表
B.单链表
C.栈
D.队列

6.设长度为n的队列用单循环链表表示(假设表尾结点为当前队列的队尾元素)，若只设头指针，则入队操作、出队操作的时间复杂度分别为(　　)

A.O(n)、O(1)
B.O(1)、O(1)
C.O(1)、O(n)
D.O(n)、O(n)

7.若采用顺序存储(一维数组)结构存储一棵如题7图所示的二叉树，根结点1的下标为1，则结点4的下标为(　　)

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

8.按层序(自顶向下、从左到右)遍历二叉树时需借助队列作辅助结构。对高度为3的满二叉树进行层序遍历时，队列中所出现的元素个数最多是(　　)

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

9.一个数组的第一个元素的存储地址是100，每个元素占2个存储单元，则第5个元素的存储地址是(　　)

A.120
B.110
C.108
D.100

10.已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如题10图所示，则从顶点V0出发进行深度优先搜索可能得到的顶点访问序列为(　　)

A.{v₀，v₁，v₂，v₅，v₄，v₃}
B.{v₀，v₁，v₂，v₃，v₄，v₅}
C.{v₀，v₁，v₅，v₂，v₃，v₄}
D.{v₀，v₁，v₄，v₅，v₂，v₃}

11.“在旅游时从某地出发要去某个目的地，如何选择线路才能使得路程最短”，从图的应用角度，最合理的解决方案是(　　)

A.深度优先搜索
B.最小生成树
C.拓扑排序
D.最短路径

12.二分查找算法的时间复杂度是(　　)

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

13.已知一个散列表如题13图所示，其散列函数为H(key)=key mod11，采用线性探测法处理冲突，则下一个进入散列表的关键字49的地址为(　　)

A.2
B.3
C.8
D.9

14.用冒泡排序方法对n个待排序的键值进行排序，则整个排序过程所历经的趟数是(　　)

A.1
B.n-1
C.n
D.至少为1、至多为n-1

15.现对关键字序列{6，1，4，3，7，2，8，5}进行快速排序，那么以第1个元素6为工作基准的第一趟快速排序结束的结果序列为(　　)

A.{5，1，4，3，2，6，8，7}
B.{5，1，4，3，2，6，7，8}
C.{5，1，4，3，6，2，8，7}
D.{8，7，6，5，4，3，2，1}

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

11.计算机图灵奖获得者N.Wirth曾提出一个著名公式：算法+________=程序。

12.“即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果。”这种评价算法好坏的因素称为________。

13.设某非空双向链表，其结点结构为，若要删除指针q所指向的结点，则需执行如下两条关键语句：q->prior->next=q->next; _________。

14.大小为MaxSize的循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断该循环队列为空的条件表达式是________。

15.对稀疏矩阵进行压缩存储的一种方法是________。

16.若一棵二又树中只有叶结点和左右子树皆非空的结点，设二叉树叶结点个数为s，则左右子树皆非空的结点个数是________。

17.若一棵二叉树的前序、中序、后序遍历的结果序列均相同，则该二叉树一定是________或是只有一个根结点的二叉树。

18.采用邻接表表示一有向图，若图中某顶点的入度和出度分别为D₁和D₂，则该顶点所对应的单链表的结点个数为________。

19.对有序顺序表(07，12，15，18，27，32，46，65，83)用二分法查找，若查找成功，则查找所需比较次数最多的键值是________。

110.由n个键值构造的二叉排序树，在等概率查找的假设下，查找成功的平均查找长度的最大值可能达到________。

111.对关键字序列{26，36，41，38，44，15，68，12，06，51}，设HashSize=13，H(key)=key mod HashSize，并用链地址法解决冲突，则构造得到的散列表中的指针HP[________]所指向的一个单链表(同义词子表)最长。

112.在直接选择、直接插入、冒泡、快速等四种排序方法中，经一趟排序后，任一元素都不能确定其最终位最的排序方法是________。

113.若采用直接选择排序方法对初始关键字序列{5，3，5，1}进行升序排序(其中包括2个值相同的关键字，均为5)，则排序结束后的关键字序列是________。

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

21.如题29图所示，利用同一循环向量空间实现两个队列，其类型Queue2定义如下： typedef struct{ DataType data[MaxSize]; int front[2], length[2]; }Queue2; 对于i=0或1，front[i]和length[i]分别为第i个队列的队头位置和实际长度。分别写出 这两个队列满的条件。

22.将如题30图所示的含有3棵树的森林转换成相应的二又树，并分别给出该森林先序、中序遍历的结果序列和相应的二叉树的先序、中序遍历结果序列，根据所得到的遍历结果序列你会得到什么结论?

23.对一个图G，按顺序输入顶点对<1，3>、<1，2>、<2，4>、<2，3>、<4，3>、<4，2>、<4，1>，根据建立图的邻接表的算法画出相应的邻接表，并写出在该邻接表上，从顶点2开始搜索得到的一个深度优先搜索序列和广度优先搜索序列。

24.设顺序存储的线性表共有100个元素，按分块查找(索引查找)的要求等分成5块。若对索引表采用二分查找来确定块，并在确定的块中进行顺序查找，则在概率相等的情况下，分块查找成功时的平均查找长度是多少(要求利甩∑PiCi来计算并给出详细算式)?

25.若采用堆排序方法对关键字序列{265，301，751，129，937，863，742，694，076，438}进行升序排序，写出其每趟排序结束后的关键字序列。

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

31.假设以带头结点的单链表表示线性表，单链表的类型定义如下：typedef struct node{ int data;    struct node*next; } LinkedNode，*LinkedList;编写算法，删除值无序的线性表中值最大的元素(表中各元素的值互不相同)。

32.假设树的存储结构采用孩子兄弟表示法，写出树的先序遍历算法。该算法的函数头为： void PreOrderTree(TNode*root, void(*Visit)( ))，树的孩子兄弟表示法数据类型定义为：typedef struct tnode {       DataType data;       struct tnode *firstchild, *nextsibling;} TNode, *Tree;