全国2021年10月高等教育自学考试数据结构导论试题

1.请考生按规定用笔将所有试题的答案涂、写在答题纸上。

2.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

选择题部分

注意事项:每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。

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

1.程序段s=i=0;do {i=i+1;s=s+i;}while(i< = n)的时间复杂度为

A. O(n)

B. O( nlogzn)

C. O(n2)

D. 0(1)

2.不属于数据组织三个层次的是

A.数据

B.数据元素

C.数据类型

D.数据项

3.具有先进先出特征的数据结构是

A.堆栈

B.队列

C.最小堆

D.完全二叉树

4.一个栈的输入序列为1234.则下列序列中可能是栈的输出序列的是

A.231 4

B.4123

C.31 24

D.34 1 2

5.设指针变量front表示链队列的队头指针.指针变量rear表示链队列的队尾指针，指针变量s指向将要人队列的结点X.则入队列的操作序列为

A. front->nexl=s; front=s;

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

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

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

6.设一棵完全二叉树中有65个结点,则该完全二叉树的深度为.

A.5

B.6

C.7

D.8

7.有n个叶结点的哈夫曼树的结点总数为

A.2n-1

B.2n

C.2n+1

D.2n2

8.先序遍历与中序遍历结果相同的二叉树

A.根结点无左孩子

B.根结点无右孩子

C.所有结点只有左子树

D.所有结点只有右子树

9.设有一个二维数组a[m][n].假设a[0]C0]存放位置为644.a[2][2]存放位置为676.每个元素占一个存储空间,则a[3][3]存放位置为

A.678

B.688

C.692

D.696

10.线性表若采用链表存储结构.内存中可用存储单位的地址

A.必须是连续的

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

C.一定是不连续的

D.连续不连续都可以

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

A.0

B. n(n-1)/2

C. n(n-1)

D. n(n+1)

12.对于线性表(7.34.55.25.64.46.20.10)进行散列存储时,若散列函数为H(K)=K %9.则散列地址为1的元素个数是

A.1

B.2

C.3

D.4

13.对题13图中的树进行遍历后可以得到序列ABCD的遍历方式是

A.先序遍历

B.中序遍历

C.后序遍历

D.层次遍历

14.设有序表中的元素为(13.18.24.35.47.50.62).则在其中利用二分法查找值为24的元素需要经过比较的次数是

A.1

B.2

C.3

D.4

15.就平均时间性能而言,若需以O(nlog2n)的时间复杂度完成对数组的排序,则可选择的排序方法是

A.快速排序

B.冒泡排序

C.直接选择排序

D.直接插人排序

非选择题部分

注意事项:用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上。

二、 填空题:本大题共13空,每空2分,共26分。

16.根据图的定义,图中顶点的最少数目是      ▲      。

17.1976年瑞士计算机科学家Niklaus Wirth 曾提出一个著名公式:算法十数据结构      ▲      。

18.数据的存储结构有顺序存储链式存储、散列存储和      ▲      存储。

19.一个算法的时空性是指该算法的时间性能和空间性能.其中空间性能是算法需要的      ▲      。

20.用顺序存储实现的线性表称为顺序表，一般使用      ▲      来表示。

21.在单链表中,指针p所指的结点为最后一个结点的条件是      ▲      。

22.循环队列被定义为结构体类型,含有三个域:data. front和rear,则循环队列cQ为空的条      ▲      

23.假设m行n列的矩阵有t个非零元素.当t<<mwn时.则称矩阵为      ▲      。

24.顺序队列需要预先定义队列的容量.一般将数组的首尾相接,形成循环队列.这样可以解决      ▲      问题。

25.树上任一结点所拥有的子树的数目称为该结点的      ▲      。

26.一棵二叉树的最少结点个数为      ▲      。

27.含有n个顶点的连通图中任意一条简单路径.其长度最大为      ▲     。

28.要完全避免散列所产生的“堆积"现象,通常采用      ▲      解 决冲突。

三、应用题:本大题共5小题,每小题6分,共30分。

29.设有编号为1.2,3,4的四辆列车,顺序进人一个栈式结构的站台,若列车2最先开出,则列

车出站可能的顺序有几种?并写出这四辆列车所有可能的出站顺序。

30.将题30图所示的森林转换成二叉树。

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

32.已知题32图所示的二叉排序树中各结点的值分别为1~9.请写出图中结点A~I所对应的值。

33.已知键值序列{11.2.13.26.5.18.4.9),设散列表表长为13.散列函数H(key)= key mod 13处理冲突的方法为线性探测法.请给出散列表。

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

34.读入n=100个整数到一个数组中.写出实现将该组数进行逆置的算法.并分析算法的空间复杂度。

35.试写出二分查找的递归算法。