2017年10月自考02142数据结构导论试题及答案含解析

数据结构导论年月真题

02142201710

1、【单选题】与数据元素本身的形式、内容、相对位置、个数无关的是数据的

存储结构

逻辑结构

A:

类型

B:

运算实现

C:

答D:案：B

解析：数据元素之间的逻辑关系的整体就称为数据的逻辑结构，其与数据元素本身的形

式、内容、相对位置、个数无关。

2、【单选题】时间复杂度的阶数中，O(n)表示

常数阶

线性阶

A:

多项式阶

B:

指数阶

C:

答D:案：B

解析：常见时间复杂性的量级从小到大：常数阶O(1)（即算法的时间复杂性与输入规模n

无关或n恒为常数）、对数阶O(log2n)、线性阶O(n)、平方阶O(n2)和指数阶O(2n)。

3、【单选题】假设顺序表的长度为n，则在第i(l≤i小于等于n+l)个元素之前插入一个新

元素x所需移动元素的个数为

i

n-i

A:

n-i+1

B:

n

C:

答D:案：C

解析：顺序表插入算法分析：①合法的插入位置共n+1个，即第1个位置到第n+1个位

置。②最坏情况是插入到第1个位置，共需要移动n个元素。故插入算法的最坏情况时间

复杂性量级是O(n)。在第i(1≤i小于等于n+1)个元素之前插入一个新元素x所需移动元

素的个数为n-i+1。

4、【单选题】在双向循环链表中，设p指向待删结点，删除*p的正确语句为

p->prior->next=p->next;p->next->prior=p->prior;free(p);

p->next=p->prior->next;p->prior=p->next->prior;free(p);

A:

p->prior->next=p->next;p->next->prior=p->prior；

B:

p->next=p->prior->next;p->prior=p->next->prior;

C:

答D:案：A

解析：

在双链表上，链域prior和next分别指向本结点的直接前趋和直接后继。若p指向待删

除的结点，则删除*p需要执行的操作如图2-3所示。具体操作步骤为：①p->prior-

>next=p->next；②p->next->prior=p->prior。

5、【单选题】关于栈和队列，下面叙述正确的是

函数的嵌套调用用队列来实现

操作系统中进程调用用栈来实现

A:

程序递归的处理用队列来实现

B:

栈和队列是运算受限的线性表

C:

答D:案：D

解析：函数的嵌套调用用栈来实现，操作系统中进程调用用队列来实现，程序递归的处理

用栈来实现，栈和队列是运算受限的线性表。

6、【单选题】设两个数据元素类型一致的栈共享一维数组空间data[max]成为双栈，两个栈

的栈底分别设在数组两端，这两个栈的栈顶变量分别为top1和top2,且top2≥top1,则下列

会发生“上溢”情况的是

top1+1==top2

top1==top2

A:

top2+1==top1

B:

top1+top2==max

C:

答D:案：A

解析：两个栈的栈顶变量分别为top1和top2,且top2≥top1；当top1+1==top2会发生

“上溢”情况。

7、【单选题】设有一循环队列SQ，现将数据x进行入队操作，语句为

SQ.front=(SQ.front+1)%maxsize;

SQ.rear=(SQ.rear+1)%maxsize;

A:

B:

SQ.front=(SQ.front+1)%maxsize;SQ.data[SQ.front]=x;

SQ.rear=(SQ.rear+1)%maxsize;SQ.data[SQ.rear]=x;

C:

答D:案：D

解析：循环队列SQ,现将数据x进行入队操作：先移动队尾SQ.rear=(SQ.rear+1)%

maxsize;再插入元素SQ.data[SQ.rear]=x;

8、【单选题】关于树的概念，下面叙述正确的是

树可以没有根结点

树中结点个数不为0

A:

树中可以存在多个根节点

B:

若树中存在多个子树，则子树之间可以相交

C:

答D:案：A

9、【单选题】关于满二叉树和完全二叉树，下面叙述正确的是

完全二叉树结点个数〉满二叉树结点个数

满二叉树一定是完全二叉树

A:

完全二叉树一定是满二叉树

B:

含有n个结点的完全二叉树的深度为log2?n

C:

答D:案：B

解析：

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树，由n个结点构成的完全二叉

树，其深度为。

10、【单选题】与二叉链表结构形式完全相同的是

孩子链表

孩子兄弟链表

A:

带双亲的孩子链表

B:

双亲链表

C:

答D:案：B

解析：二叉链表结构形式完全相同的是孩子兄弟链表。

11、【单选题】一个具有n个顶点的无向完全图的边数为

n2/2

A:

n2

n(n-1)/2

B:

n(n-1)

C:

答D:案：C

解析：具有n个顶点的无向完全图中边的数目为n（n-1）/2，具有n个顶点的有向完全图

中边（弧）的数目为n（n-1）。

12、【单选题】邻接表的存储方法结合了

顺序存储与散列存储

顺序存储与链式存储

A:

链式存储与索引存储

B:

链式存储与散列存储

C:

答D:案：B

解析：邻接表的存储方法结合了顺序存储与链式存储。

13、【单选题】假设顺序表为（b1，b2，b3)，查找b1，b2，b3的概率分别为0.2,0.2,

0.6，则顺序查找法的平均查找长度为

1

1.2

A:

1.4

B:

1.6

C:

答D:案：D

解析：0.2*3+0.2*2+0.6*1=1.6

14、【单选题】已知一个有序表为(13,18,24,35,47,50,62,83,90,115,134)，当用二分查找

方法查找值为90的元素时，查找成功时，键值比较的次数为

2

3

A:

4

B:

5

C:

答D:案：A

解析：二分查找方法过程：首先，假设表中元素是按升序排列，将表中间位置记录的关键

字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、

后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则

进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子

表不存在为止，此时查找不成功。第一次比较50，第二次比较90。

15、【单选题】在插入排序方法中，类似图书馆中整理图书的过程的是

希尔排序

表插入排序

A:

折半插入排序

B:

直接插入排序

C:

答D:案：D

解析：图书馆中整理图书的过程的是1本书插到已经有序的一排书中间，使得整体有序，

这个过程类似于直接插入排序。

16、【问答题】在估算算法空间复杂度时，一般只需要分析_________所占用的空间。

答案：辅助变量

17、【问答题】对于按位置查找运算，顺序表是随机存取，其时间复杂度为_________。

答案：O(1)

18、【问答题】设顺序表A长度为100，若下标从1开始计数，则删除元素A[10]需要移动

_________个元素。

答案：90

19、【问答题】循环队列的队头指针为front,队尾指针为rear，当_________时表明队列为

空。

答案：REAR==FRONT

20、【问答题】对于一棵包含n个结点的二叉树，用二叉链表存储时，其指针总数为

_________个。

答案：2N

21、【问答题】用于描述分类过程的二叉树称为_________

答案：判定树

22、【问答题】在树形结构中，每一层结点只能和上一层中的至多一个结点相关，而在

_________中，任意两个结点之间都可能相关。

答案：图结构

23、【问答题】Dijkstra算法的思想是按照最短路径长度_________的方法产生从点到其他

顶点的最短路径。

答案：递增

24、【问答题】遍历图的基本方法有深度优先搜索和_________优先搜索两种。

答案：广度

25、【问答题】作为一种数据结构，查找表的逻辑结构是_________。

答案：集合

26、【问答题】对于具有n个元素的数据序列，采用二叉排序树查找，平均查找长度介于

_________之间。

答案：O(N)和O(LOG2N)

27、【问答题】直接插入排序的空间复杂度为_________。

答案：O(1)

28、【问答题】已知一个7×6的稀疏矩阵如题29图所示，试写出该稀疏矩阵的三元组表

示。

答案：该稀疏矩阵可表示为如下三元组表：(（0，0，16)，(0，5，-16)，(1，2，3)，

(2，3，-8)，(4，0，91)，(6，2，15)）

29、【问答题】已知一棵二叉树如题30图所示，试求该二叉树的先序遍历序列、后序遍

历序列和层次遍历序列。

答案：先序遍历序列为：ABDGCHF后序遍历序列为：GDBHFCA层次遍历序列为：ABCDHFG

30、【问答题】已知散列表的地址空间为0～10,散列函数为H(key)=keymodll(mod表示

求余运算），采用二次探测法解决冲突，试用键值序列20,38,16,27,5,23,56,29建立散列

表，并计算出等概率情况下查找成功的平均查找长度。

答案：键值序列20，38，16，27，5，23，56，29构成的散列表如

图：等概率情况下查找成

功的平均查找长度=（1+1+2+3+5+2+3+1）/8=9/4

31、【问答题】给出一组关键字(20,29，11，74,35,3,8,56)，写出冒泡排序前两趟的排序

结果，并说明冒泡排序算法的稳定性如何？

答案：第一趟(20，11，29，35，3，8，56)，74第二趟（11，20，29，3，8，35)，56，

74冒泡排序算法是稳定的排序算法。

32、【问答题】设有一n阶方阵A，设计算法实现对该矩阵的转置。

答案：VOIDMM（INTA[N][N]）{INTI,J,TEMP;FOR（I=0;I<N;I++)FOR

（J=0;J<I;J++){TEMP=A[I][J];A[I][J]=A[J][I];A[J][I]=TEMP;}}

33、【问答题】已知二叉链表的类型定义如下：typed