2025年高等教育工学类自考-02331数据结构考试近5年真题集锦(频考类试题)带答案.docx
(图片大小可自由调整)
2025年高等教育工学类自考-02331数据结构考试近5年真题集锦(频考类试题)带答案
第I卷
一.参考题库(共80题)
1.对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度为()在表尾插入元素的时间复杂度为()
2.请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下:PUSH(ST,X):元素X入ST栈;POP(ST,X):ST栈顶元素出栈,赋给变量X;Sempty(ST):判ST栈空否。那么如何用栈的运算来实现该队列的三个运算:enqueue:插入一个元素入队列;dequeue:删除一个元素出队列;queue_empty:判队列为空。(请写明算法的思想及必要的注释)
3.设有n个关键字具有相同的Hash函数值,则用线性探测法把这n个关键字映射到HASH表中需要做()次线性探测。
A、A
B、B
C、C
D、D
4.假定对线性表(38,25,74,52,48)进行哈希存储,采用H(K)=K%7作为哈希函数,采用线性探测法处理冲突,则平均查找长度为()
5.队列是一种可以在表头和表尾都能进行插入和删除操作的线性表。
6.设以带头结点的双向循环链表表示的线性表L=(a1,a2,…,an)。试写一时间复杂度O(n)的算法,将L改造为L=(a1,a3,…,an,…,a4,a2)。
7.数据结构里,图片不属于数据。
8.在双向链表存储结构中,删除p所指的结点时须修改指针()。
A、p->next->prior=p->prior;?p->prior->next=p->next;
B、p->next=p->next->next;?p->next->prior=p;
C、p->prior->next=p;?p->prior=p->prior->prior;
D、p->prior=p->next->next;?p->next=p->prior->prior;
9.假定一棵二叉树的结点数为19,则它的最小深度为(),最大深度为()
10.设有序表中的元素为(13,18,24,35,47,50,62),则在其中利用二分法查找值为24的元素需要经过()次比较。
A、1
B、2
C、3
D、4
11.在一棵二叉树中,假定每个结点只有左子女,没有右子女,对它分别进行前序遍历和后序遍历,则具有相同的结果。
12.当利用大小为N的一维数组顺序存储一个栈时,假定用top==N表示栈空,则向这个栈插入一个元素时,首先应执行()语句修改top指针。
A、top++
B、top--
C、top=0
D、top
13.()是图的一种连接存储结构。
14.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足()。
A、所有的结点均无左孩子
B、所有的结点均无右孩子
C、只有一个叶子结点
D、是任意一棵二叉树
15.对于一棵完全二叉树采用顺序存储,设一个结点的编号为i(根结点的编号为1,若它的左孩子结点存在,则其编号为()
16.在一棵度为M树中,度为1的结点数为N1,度为2的结点数为N2,……,度为M的结点数为NM,则该数中含有多少个叶子结点?有多少个非终端结点?
17.写出单链表存储结构的C语言描述。
18.索引顺序表的特点是块内可无序,块间要有序。
19.已知一组记录为(46,74,53,14,26,38,86,65,27,34),给出采用堆排序法进行排序时每一趟的排序结果。
20.链表每个结点包含数据域和指针域,其指针域可以有()个。
A、0个
B、1个
C、2个
D、多个
21.矩阵中的行列数往往是不相等的。
22.单链表的主要优点是()
A、便于随机查询
B、存储密度高
C、逻辑上相邻的元素在物理上也是相邻的
D、插入和删除比较方便
23.有100个结点的完全二叉树,深度为()。
24.在一个顺序表的表尾插入一个元素的时间复度的量级为()。
A、O(n)
B、O(1)
C、O(n2)
D、O(log?n)
25.散列函数有一个共同的性质,即函数值应当以()取其值域的每个值。
A、最大概率
B、最小概率
C、平均概率
D