2025年数据结构与算法期中考试题 .pdfVIP

天将降大任于斯人也，必先苦其心志，劳其筋骨，饿其体肤，空乏其身，行拂乱其所为。——《孟子》

数据结构与算法期中考试题

一、单选题,从可供选择的4个答案中,选择一个正确的答案,将其

前面的字母填写在()中,共40分,每小题4分。

1.在一个单链表中，已知q所指结点是p所指结点的前驱结点，

若在q和p

之间插入s结点，则执行()。

A.s-next=p-next;p-next=s;

B.q-next=s;s-next=p;

C.p-next=s-next;s-next=p;

D.p-next=s;s-next=q;

2.带头结点的单链表为空的判定条件是()。

A.head==NULL

B.head-next==NULL

C.head-next==head

D.head!=NULL

3.若一棵完全二叉树中某结点无左孩子，则该结点一定是（）。

A．度为１的结点B．度为２的结点C．叶子结点D．分支结点

4.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的

条件是()。

A．a在b的右

方B．a在b的左方C．a是b的祖

先D．a是b的子孙5．在长度为n的线性表中查找值为x的数据

元素的时间复杂度为：（）。

A.O(0)

B.O(1)

C.O(n)

D.O(n2)

6．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的出栈序列是

（）。

非淡泊无以明志，非宁静无以致远。——诸葛亮

A.edcba

B.cdeba

C.debca

D.abcde

7．前序遍历和中序遍历结果相同的二叉树是（）。

A.根结点无左孩子的二叉树

B.根结点无右孩子的二叉树

C.所有结点只有左子树的二叉树

D.所有结点只有右子树的二叉树

8.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组

A[1]~A[n]

中，结点A[i]若有左子树，则左子树的根结点是（）。

A.A[2i-1]

B.A[2i+1]

C.A[i/2]

D.A[2i]

9.对任何一棵四叉树T，如果其终端结点的个数为n0，度为2的

结点个数为

n2，度为3的结点个数为n3,度为4的结点个数为n4,则（）。

A.n0=n2+n3+n4+1

B.n0=n2+2n3+3n4+1

C.n0=n1+n2+2n3+3n4+1

D.没有规律

10.算法指的是（）。

A.对特定问题求解步骤的一种描述

B.计算机程序

C.解决问题的计算方法

D.数据处理

二、填空题,请将答案填写在题目的()内。（共24分，每小题6