自考02142《数据结构导论》真题及(2022.10).pdfVIP

自考02142《数据结构导论》真题及（2022.10）

自考02142《数据结构导论》真题解析（2022.10）

1.[单选题]线性表若采用链表存储结构，内存中可用存储单位的地址

A.必须是连续的

B.有一部分必须是连续的

C.一定是不连续的

D.连续不连续都可以

2.[单选题]设有一个二维数组a[m][n]，假设a[0][0]存放位置为644，

a[2][2]存放位置为676，每个元素占一个存储空间，则a[3][3]存放位

置为

A.678

B.688

C.692

D.696

3.[单选题]先序遍历与中序遍历结果相同的二叉树

A.根结点无左孩子

B.根结点无右孩子

C.所有结点只有左子树

D.所有结点只有右子树

4.[单选题]有n个叶结点的哈夫曼树的结点总数为

A.2n－1

1

B.2n

C.2n＋1

D.2n2

5.[单选题]设一棵完全二叉树中有65个结点，则该完全二叉树的深

度为

A.5

B.6

C.7

D.8

6.[单选题]设指针变量front表示链队列的队头指针，指针变量rear

表示链队列的队尾指针，指针变量s指向将要入队列的结点X，则入

队列的操作序列为

A.front-next=s;front=s;

B.s-next=rear;rear=s;

C.rear-next=s;rear=s;

D.s-next=front;front=s;

7.[单选题]一个栈的输入序列为1234,则下列序列中可能是栈的输

出序列的是

A.2314

B.4123

C.3124

D.3412

2

8.[单选题]具有先进先出特征的数据结构是

A.堆栈

B.队列

C.最小堆

D.完全二叉树

9.[单选题]不属于数据组织三个层次的是

A.数据

B.数据元素

C.数据类型

D.数据项

10.[单选题]程序段s=i=0;do{i=i+1;s=s+i;}while(i=n)的时间复杂度为

A.O(n)

B.O(nlog2n)

C.O(n2)

D.O(1)

11.[单选题]对题13图中的树进行遍历后可以得到序列ABCD的遍历

方式是

A.先序遍历

B.中序遍历

C.后序遍历

D.层次遍历

3

12.[单选题]对于线性表(7,34,55,25,64,46,20,10)进行散列存储时，若

散列函数为H(K)=K%9，则散列地址为1的元素个数是

A.1

B.2

C.3

D.4

13.[单选题]一个具有n个顶点的无向完全图的边数为

A.0

B.n(n-1)/2

C.n(n-1)

D.n(n+1)

14.[单选题]就平均时间性能而言,若需以O(nlog2n)的时间复杂度完

成对数组的排序,则可选择的排序方法是

A.快速排序

B.冒泡排序

C.直接选择排序

D.直接插入排序

15.[单选题]设有序表中的元素为(13,18,24,35,47,50,62)，则在其中利

用二分法查找值为24的元素需要经过比较的次数是

A.1

B.2

C.3

4

D.4

16.[案例题]根据图的定义，图中顶点的最少数目是______。

17.[案例题]一棵二叉树的最少结点个数为()。

18.[填空题]要完全避免散列所产生的“堆积”现象，通常采用（）解

决冲突。

19.[填空题]含有n个顶点的连通图中任意一条简单路径，其长度最

大为（）。

20.[填空题]树上任一结点所拥有的子树的数目称为该结点的（）。

21.[填空题]顺序队列需要预先定义队列的容量，一般将数组的首尾

相接，形成循环队列，这样可以解决“（）”问题。

22.[填空题]假设m行n列的矩阵有t个非零元素，当t

31.[问答题]写出题31图所示的有向带权图的邻接矩阵。

32.[问答题]将题30图所示的森林转换成二叉树。

33.[问答题]设有编号为1,2,3,4的四辆列车,顺序进入一个栈式结构

的站台,若列车2最先开出,则列车出站可能的顺序有几种?并写出这

四辆列车所有可能的出站顺序。

34.[设计题]试写出二分查找的递归算法。

3