2025年数据结构期中考试试题及答案 .pdfVIP

老当益壮，宁移白首之心；穷且益坚，不坠青云之志。——唐·王勃

数据结构期中考试

一、单项选择题(本题总分20分，每题2分)在每小题列出的四个选项中只有

一个选项是符合题目要求的，请将正确选项前的字母。

1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为(D)。

A.顺序表B.链表C.索引表D.散列表

采用排除法，顺序表存储位置表示数据元素的顺序关系，跟关键字无法；链表的地址是动态分配的；索引表是

按数据元素的关键字排序所得，它的数据元素是没有规律的

2.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为(A)。

A.n-i+1B.n-iC.iD.i-1

代入计算法，我们知道在i=n+1时不需要移动元素

3.若一棵二叉树的先序遍历序列为a,b,c，则由abc三个结点构成的二叉树个数为(B)。

A.4B.5C.6D.7

4.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存

储地址为130，则元素A[3][4][5]的存储地址为(B)。

A.370B.368C.366D.372

Loc(3,4,5)=loc(0,0,0)+(3*5*6+4*6+5)*2=130+119*2=368;

5.高度为h的二叉树（仅含根结点的二叉树高度为1）的结点最少是多少(D)。

A.h+1B.2hC.2h－1D.h

二叉树性质2

6.将两个各有n个元素的有序表归并成一个有序表，其最多的比较次数是(C)。

A.nB.n+1C.2n-1D.n-1

7.已知一算术表达式的中缀形式为A＋B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为(A)。

A.-+A*BC/DEB.–A+B*CD/E

C.-+*ABC/DED.–A+B*C/DE

根据中缀和后缀表达式可画出表达树如下：

-

+/

A*DE

BC

故前缀表达式为：-+A*BC/DE

共1页第1页

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

8．下面图示的顺序存储结构表示的二叉树是（A）。

本题有两种可能性，第一种位置0是本身是数据，第二种6表示元素个数。

第一种双亲i左孩子2*i+1右孩子2*i+2B.中F应该是D右孩子;D.错的

第二种双亲i左孩子2*i右孩子2*i+1A.正确C.错

9．给定一个有n个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均

需要移动（C）个元素。

A．(n+1)/2B．n/2C．(n-1)/2D．1

2

10．法的时间复杂度表达式为T(n)=an+bnlgn+cn+d，其中n为问题的规模，a、b、c和d为常数，用O表示

其渐进时间复杂度为（D