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

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

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

一、单项选择题：本大题共15小题，每小题2分，共30分。在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。

1.与数据元素本身的形式、内容、相对位置、个数无关的是数据的()

A.存储结构B.逻辑结构C.类型D.运算实现

2.时间复杂度的阶数中，O(n)表示()

A.常数阶B.线性阶C.多项式阶D.指数阶

3.假设顺序表的长度为n，则在第i(1≤i≤n+1)个元素之前插入一个新元素x所需移动元素的个数为()

A.iB.n-iC.n-i+1D.n

4.在双向循环链表中，设p指向待删结点，删除*p的正确语句为()

A.p->prior->next=p->next; p->next->prior=p->prior; free(p);B.p->next= p->prior->next; p->prior= p->next->prior; free(p);C.p->prior->next=p->next; p->next->prior=-p->prior;D.p->next=p->prior->next; p->prior= p->next->prior;

5.关于栈和队列，下面叙述正确的是()

A.函数的嵌套调用用队列来实现B.操作系统中进程调用用栈来实现C.程序递归的处理用队列来实现D.栈和队列是运算受限的线性表

6.设两个数据元素类型一致的栈共享一维数组空间data[max]成为双栈，两个栈的栈底分别设在数组两端，这两个栈的栈顶变量分别为top1和top2，且top2≥top1，则下列会发生“上溢”情况的是()

A.top1+1=top2B.top1=top2C.top2+1-=top1D.top1+top2=max

7.设有一循环队列SQ，现将数据x进行入队操作，语句为()

A.SQ. front=(SQ. front+1)%maxsize;B.SQ. rear=(SQ. rear+1)%maxsize;C.SQ. front=(SQ. front +1)%maxsize; SQ. data[SQ. front]=x;D.SQ. rear=(SQ. rear+1)%maxsize; SQ. data[SQ.rear]=x;

8.关于树的概念，下面叙述正确的是()

A.树可以没有根结点B.树中结点个数不为0C.树中可以存在多个根节点D.若树中存在多个子树，则子树之间可以相交

9.关于满二叉树和完全二叉树，下面叙述正确的是()

A.完全二叉树结点个数>满二叉树结点个数B.满二叉树一定是完全二叉树C.完全二叉树一定是满二叉树D.含有n个结点的完全二叉树的深度为log2n

10.与二叉链表结构形式完全相同的是()

A.孩子链表B.孩子兄弟链表C.带双亲的孩子链表D.双亲链表

11.一个具有n个顶点的无向完全图的边数为()

A.n2/2B.n2C.n(n-1)/2D.n(n-1)

12.邻接表的存储方法结合了()

A.顺序存储与散列存储B.顺序存储与链式存储C.链式存储与索引存储D.链式存储与散列存储

13.假设顺序表为(b1，b2，b3)，查找b1，b2，b3的概率分别为0.2，0.2，0.6，则顺序查找法的平均查找长度为()

A.1B.1.2C.1.4D.1.6

14.已知一个有序表为(13，18，24，35，47，50，62，83，90，115，134)，当用二分查找方法查找值为90的元素时，查找成功时，键值比较的次数为()

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

15.在插入排序方法中，类似图书馆中整理图书的过程的是()

A.希尔排序B.表插入排序C.折半插入排序D.直接插入排序

二、填空题：本大题共13空，每空2分，共26分。

11.在估算算法空间复杂度时，一般只需要分析_________所占用的空间。

12.对于按位置查找运算，顺序表是随机存取，其时间复杂度为_________。

13.设顺序表A长度为100，若下标从1开始计数，则删除元素A[10]需要移动_________个元素。

14.循环队列的队头指针为front，队尾指针为rear，当_________时表明队列为空。

15.对于一棵包含n个结点的二叉树，用二叉链表存储时，其指针总数为_________个。

16.若对一棵有n(n>0)个结点的完全二叉树从1开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为1的结点存储到A[1]中，其余类推。若i>2，则A[i]的双亲结点为_________。

17.用于描述分类过程的二叉树称为_________。

18.在树形结构中，每一层结点只能和上一层中的至多一个结点相关，而在_________中，任意两个结点之间都可能相关。

19.Dijkstra算法的思想是按照最短路径长度_________的方法产生从一点到其他顶点的最短路径。

110.遍历图的基本方法有深度优先搜索和_________优先搜索两种。

111.作为一种数据结构，查找表的逻辑结构是_________。

112.对于具有n个元素的数据序列，采用二叉排序树查找，平均查找长度介于_________之间。

113.直接插入排序的空间复杂度为_________。

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

21.已知一个7×6的稀疏矩阵如题29图所示，试写出该稀疏矩阵的三元组表示。

22.已知一棵二叉树如题30图所示，试求该二叉树的先序遍历序列、后序遍历序列和层次遍历序列。

23.设有向图的邻接表表示如题31图所示，请给出每个顶点的入度和出度。

24.已知散列表的地址空间为0~10，散列函数为H(key)= key mod11(mod表示求余运算)，采用二次探测法解决冲突，试用键值序列20，38，16，27，5，23，56，29建立散列表，并计算出等概率情况下查找成功的平均查找长度。

25.给出一组关键字(20，29，11，74，35，3，8，56)，写出冒泡排序前两趟的排序结果，并说明冒泡排序算法的稳定性如何?

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

31.设有一n阶方阵A，设计算法实现对该矩阵的转置。

32.已知二叉链表的类型定义如下：typedef struct btnode{  DataType data;   struct btnode *lchild, *rchild;}*BinTree;假定vsit(bt)是一个已定义的过程，其功能是访问指针bt所指结点。设计递归算法preorder( BinTree bt)实现在二叉链表上的先序遍历。