华夏大地教育网为方便全国自考考生顺利通过2022年10月自学考试,帮助考生自考顺利通过,特准备了“2021年10月自考02142数据结构导论真题及答案”,希望对各位考生有所帮助。更多自考笔记串讲、复习资料请进华夏大地教育网自考频道历年真题获取。
2021年10月自考02142数据结构导论真题及答案
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.2314
B.4123
C.3124
D.3412
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的遍历方式是
image.png
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.直接插人排序
非选择题部分
注意事项:用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上。
16.根据图的定义,图中顶点的最少数目是▲。
17.1976年瑞士计算机科学家NiklausWirth曾提出一个著名公式:算法十数据结构▲。
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图所示的森林转换成二叉树。
2021年10月自考02142数据结构导论真题及答案
31.写出题31图所示的有向带权图的邻接矩阵。
2021年10月自考02142数据结构导论真题及答案
32.已知题32图所示的二叉排序树中各结点的值分别为1~9.请写出图中结点A~I所对应的值。
2021年10月自考02142数据结构导论真题及答案
33.已知键值序列{11.2.13.26.5.18.4.9),设散列表表长为13.散列函数H(key)=keymod13处理冲突的方法为线性探测法.请给出散列表。
四、算法设计题:本大题共2小题,每小题7分,共14分。
34.读入n=100个整数到一个数组中.写出实现将该组数进行逆置的算法.并分析算法的空间复杂度。
35.试写出二分查找的递归算法。
上文资讯是华夏大地教育网整理的关于“2021年10月自考02142数据结构导论真题及答案”的内容,了解其他相关资讯,请来华夏教育。