数据结构导论2014年10月真题（02142）

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

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

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

1.下列算法的时间复杂度为(　　)for( i=1; i<=n; i++){  m++;   for(j=1; i<=n; j++)        k*=m;}

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

2.根据数据元素之间关系的不同特性，通常将数据结构分为四类基本结构，即(　　)

A.集合、顺序结构、树形结构、图结构
B.集合、线性结构、链式结构、图结构
C.集合、线性结构、树形结构、图结构
D.线性结构、顺序结构、链式结构、图结构

3.在表长为101的顺序表中做删除运算，平均移动元素的次数为(　　)

A.25
B.50
C.51
D.100

4.在表长为n的顺序表中做插入运算的时间复杂度为(　　)

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

5.单链表与顺序表相比，其特点是(　　)

A.运算算法实现简单
B.便于随机存取数据
C.不需要预先分配存储空间
D.结点个数受到限制

6.关于链栈的说法，正确的是(　　)

A.链栈不用预先考虑容量的大小
B.链栈出栈时不需要判断栈空
C.链栈进栈时需要判断栈满
D.链栈出栈时需要判断栈满

7.循环队列存储在数组A[m]中，则入队列操作中队列尾指针rear的变化为(　　)

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

8.深度为k的二叉树，结点个数最多为(　　)

A.2^k
B.2^k-1
C.2^k-1
D.2k-1

9.已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中的叶结点个数为(　　)

A.

B.

C.

D.

10.具有10个叶结点的哈夫曼树中度为1的结点数为(　　)

A.0个
B.10个
C.19个
D.20个

11.设图的顶点数为n，则采用邻接矩阵作为存储结构的图的深度优先搜索算法的时间复杂度为(　　)

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

12.n个顶点的无向图若采用邻接矩阵存储，则该矩阵的大小是(　　)

A.n×(n-1)
B.(n-1)×(n-1)
C.(n+1)×(n+1)
D.n×n

13.已知一个有序表为(15，19，30，33，49，50，65，88，93，126，164)，当二分查找值为126的元素时，检索成功需进行的比较次数为(　　)

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

14.直接选择排序算法的时间复杂度为(　　)

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

15.下述四种排序算法中，所需辅助存储量最多的是(　　)

A.堆排序
B.快速排序
C.归并排序
D.直接选择排序

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

11.在数据库中，_____又称为字段或域。

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

13.线性表中所含结点的个数称为_______。

14.在带有头结点的循环链表中，头指针为head，判断P所指结点为尾结点的条件是_________

15.链栈LS中，Ls->next指向栈顶结点，则新结点 * P入栈的操作为：P->next=LS->next;和_______;。

16.为了节省存储空间，将矩阵中多个值相同的元素只分配一个存储空间，零元素不存储，这种存储方式通常称为矩阵的________。

17.100个结点的二叉树采用二叉链表存储时，空指针域NULL有______个。

18.已知完全二叉树的第5层有5个结点，则整个完全二叉树有________个叶结点。

19.一个树的最少结点个数为_______。

110.索引顺序表由两部分组成：一个是顺序表，另一个是_______。

111.二叉排序树上的平均查找长度介于________和O(n)之间。

112.二分查找算法的时间复杂度是________。

113.最好情况下，冒泡排序算法的时间复杂度为_______，它是一种稳定的排序方法。

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

21.如题29图所示，在栈的输入端元素的输入顺序为A，5，8，试写出在栈的输出端可以得到的以数字开头的所有输出序列，并写出进栈、出栈的操作过程(用push(X)表示X进栈，pop(x)表示x出栈)。

22.分别写出题30图所示二叉树的先序遍历、中序遍历和后序遍历的结点序列。

23.写出题31图所示有向图顶点的所有拓扑排序序列。

24.将题32图所示的一棵树转换为二叉树。

25.判断序列(28，75，33，68，25，56，47，99，86，36)是否为堆?如果不是，则把它调整为堆(最小堆)。

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

31.单链表的结构定义如下：typedef struct node{  int data;    struct node *next;}Node, *LinkList;试编写算法int CountLinklist(LinkList head,int x)实现在带头结点的单链表head中计算值为x的结点数。

32.假设线性表中结点是按键值递增的顺序排列，试编写一个顺序查找算法，将岗哨设在高下标端。并说明等概率情况下查找成功和不成功时的平均查找长度。