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

数据结构导论年月真题

0214220174

1、【单选题】任意两个结点之间都没有邻接关系，组织形式松散，这种组织形式称为

集合

线性结构

A:

树形结构

B:

图结构

C:

答D:案：A

解析：数据的逻辑结构分为4种基本类型：①集合。集合中任何两个数据元素之间都没有

逻辑关系，组织形式松散。②线性结构。线性结构中的结点按逻辑关系依次排列形成一个

“锁链”。③树形结构。树形结构具有分支、层次特性，其形态有点像自然界中的树。④

图状结构。图状结构中的结点按逻辑关系互相缠绕，任何两个结点都可以邻接。

2、【单选题】表示数据元素之间的关联方式通常采用的存储方式是

顺序存储方式和索引存储方式

链式存储方式和散列存储方式

A:

顺序存储方式和链式存储方式

B:

链式存储方式和索引存储方式

C:

答D:案：C

解析：存储结构的主要部分是数据元素之间关联方式的表示。存储结点之间可以有四种关

联方式，称为四种基本存储方式：①顺序存储方式；②链式存储方式；③索引存储方式；

④散列存储方式。表示数据元素之间的关联方式通常采用的存储方式是顺序存储方式和链

式存储方式。

3、【单选题】下面几种算法时间复杂度阶数中，最小的是

O(log2?n)

O(n)

A:

O(n2)

B:

O(2n)

C:

答D:案：A

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

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

4、【单选题】双向循环链表中，在指针P所指结点的后面插入一个新结点*t，正确的语句为

A:

B:

C:

答D:案：A

5、【单选题】栈的修改原则是

先进先出

后进先出

A:

栈空则进

B:

栈满则出

C:

答D:案：B

解析：栈的修改原则是后进先出；队列的修改原则是先进先出。

6、【单选题】设有一顺序队列SQ，已知尾指针rear<队列的最大长度-1，则数据x进行入队

列操作的语句为

SQ.frontSQ.front+1；

SQ.front=SQ.rear+1；

A:

SQ.front=SQ.front+1;SQ.data[SQ.front]=x；

B:

SQ.rear=SQ.rear+1;SQ.data[SQ.rear]=x；

C:

答D:案：D

解析：入队列操作的操作：SQ.rear=（SQ.rear+1）%maxsize；SQ.data[SQ.rear]=x；题

中尾指针rear<队列的最大长度-1，SQ.rear+1不会越界，所以选项D符合。

7、【单选题】一个数组的第一个元素的存储地址是100，每个元素占2存储单元，则第5个

元素的存储地址是

105

108

A:

115

B:

118

C:

答D:案：B

解析：第5个元素的存储地址=100+4*2=108

8、【单选题】树中叶子的度是

0

1

A:

2

B:

3

C:

答D:案：A

解析：树中叶子的度是0。

9、【单选题】将一棵有n个结点的完全二叉树按层编号，若编号i所对应的结点为A，且

i>1，则A的双亲的编号为

i

i/2

A:

B:

C:

答D:案：D

解析：

二叉树性质五：如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i（1≤

i≤n）的结点X有：若i=1，则结点X是根；若i>1，则X的双亲的编号为

​，若2i>n，则结点X无左孩子（且无右孩子）；否则，X的左孩子编号

为2i。若2i+1>n，则结点X无右孩子；否则，X的右孩子的编号为2i+1。

10、【单选题】含有100个结点的二叉树采用二叉链表存储时，空指针域NULL的个数是

99个

100个

A:

101个

B:

200个

C:

答D:案：C

解析：当二叉树有n个结点时，其二叉链表上共有2n个指针域，其中只有n-1个指针域

用于存放其左、右孩子的指针，剩下的n+l个指针域为空。

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

n(n-1)/2

n(n-1)

A:

n2/2

B:

n2

C:

答D:案：B

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

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

12、【单选题】图的深度优先搜索遍历类似于树的

先序遍历

中序遍历

A:

后序遍历

B:

层次遍历

C:

答D:案：A

解析：图的深度优先搜索遍历类似于树的先序遍历；图的广度优先搜索遍历类似于树的层

次遍历。

13、【单选题】静态查找表指对查找表只进行两项操作，即

插入和删除一个数据元素

查找表中某一元素和插入一个数据元素

A:

读取表中“特定”数据元素和删除一个数据元素

B:

查找表中某一元素和读取表中“特定”数据元素

C:

答D:案：D

解析：静态查找表指对查找表只进行两项操作查找表中某一元素和读取表中“特定”数据

元素。而动态查找表则包括查找、读表元、插入、删除、初始化五种基本运算。

14、【单选题】若在线性表中采用二分查找法查找元素，该线性表应该

元素按值有序，且采用链式存储结构

元素按值无序，且采用链式存储结构

A:

元素按值有序，且采用顺序存储结构

B:

元素按值无序，且采用顺序存储结构

C:

答D:案：C

解析：若在线性表中采用二分查找法查找元素，该线性表必须元素按值有序，且采用顺序

存储结构。

15、【单选题】下列排序方法中不稳定的是

冒泡排序

二路归并

A:

堆排序

B:

直接插入排序

C:

答D:案：C

16、【问答题】从宏观上看，数据、数据元素和_________反映了数据组织的三个层次。

答案：数据项

17、【问答题】线性表、栈和队列中的元素具有相同的逻辑结构，即_________。

答案：线性结构

18、【问答题】一个算法的时空性是指该算法的时间性能和_________。

答案：空间性能

19、【问答题】为了便于运算的实现，在单链表的第一个结点之前增设一个类型相同的结

点，称之为_________。

答案：头结点

20、【问答题】假设一个8阶的上三角矩阵A按照列优先顺序压缩存储在一维数组B中，则

B数组的大小应为_________。

答案：36

21、【问答题】在栈中，允许进行插入和删除操作的一端称为_________。

答案：栈顶

22、【问答题】即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不

到的运行结果，这种评价算法好坏的因素称为_________。

答案：健壮性

23、【问答题】设栈S的初始状态为空，若元素a，b，c，d依次进栈，得到的出栈序列是

c，d，b，a，则栈S的容量至少是_________。

答案：3

24、【问答题】若一棵完全二叉树有l4个结点，则它的深度为_________。

答案：4

25、【问答题】树的双亲表示法由一个一维数组构成，数组的每个分量包含_________和双

亲域两个域。

答案：数据域

26、【问答题】如果包含n个顶点的连通图G的一个子图G’的边数大于n-1，则G’中一定

有_________。

答案：环

27、【问答题】在含有9个元素的有序表(2，4，12，18，23，37，49，51，68)中二分查找

关键字（关键字即为数据元素的值）为37的元素时，所需进行的比较次数为_________次。

答案：3

28、【问答题】从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然

后将其放在已排序序列的合适位置，该排序方法称为_________排序法。

答案：直接插入

29、【问答题】设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈)，问能否得到下列

序列：（1）A，B，C，D，E；（2）A，C，E，B，D若能得到，刚给出该序列的操作过程(用

push(A)表示A进栈，pop(A)表示A出栈)；若不能，则说明理由。

答案：（1）能（2）不能（1）操作过程为PUSH(A)POP(A)PUSH(B),POP(B)PUSH(C),

POP(C),PUSH(D),POP(D)，PUSH(E),POP(E).（2）不能的理由:对序列(2)中的E,B,D而

言,E最先出栈,此时B和D均在栈中，由于B先于D进栈，所以应有D先出栈。

30、【问答题】将一组键值{83，69，41，22，15，33，8，76}应用二路归并排序算法从小

到大排序，试写出各趟排序的结果。

答案：初始键值:[83][69][41][22][15][33][8][76]第一题:[6983][2241][1533][8

76]第二楼:[22416983][8153376]第三道:[815223341697683]

31、【问答题】设计一个算法实现以下功能：在整型数组A[n]中查找值为k的元素，若找

到，则输出其位置i(0≤i≤n-1)，否则输出-1作为标志。

答案：

32、【问答题】已知二叉链表的类型定义如下：typedefstructbtnode{DataTypedat