数据结构试题(含答案)

数据结构试题12、若需要利用形参直接访问实参，则应把形参变量说明为(B)参数。

一、单选题A指针B引用C值D变量

1、在数据结构的讨论中把数据结构从逻辑上分为(C)13、下面程序段的时间复杂度为(C)

A内部结构与外部结构B静态结构与动态结构tbr(inti=0;(m；i++)

C线性结构与非线性结构D紧凑结构与非紧凑结构.for(intj=0y<n：j++)

2、采用线性链表表示…个向量时，要求占用的存储空间地址(D)Aa[i][j]=i*j；

必须是连续的B部份地址必须是连续的A0(m2)B0(n2)CO(m*n)DO(m+n)

C一定是不连续的D可连续可不连续14、下面程序段的时间复杂度为(B)

3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为(D)。Aintf(unsignedintn)|

nBn/2C(n--1)/2D(n+l)/2iRn==011n==1)return1；

4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点S,则执行(elsereturnn*f(n-1);

D)0)

As—>link=p—>link;p—link=s：A0(1)BO(n)C0(n2)D0(n!)

Bp—>link=s；s一link二q;15、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址(D)o

Cp—>link=s—>link;s—►link=p;A必须是连续的

Dq—►link=s；s—link=p;B部份地址必须是连续的

5、如果想在4092个数据中只需要选择其中最小的5个，采用(C)方法最好。A起C一定是不连续的

泡排序B堆排序C锦标赛排序D快速排序D连续或者不连续都可以

6、设有两个串t和p,求p在t中首次浮现的位置的运算叫做(B).16、数据结构的定义为(D,S),其中口是(B)的集合.

A求子串B模式匹配C串替换D串联接A算法B数据元素C数据操作D逻辑结构

7、在数组A中，每一个数组元素A川印占用3个存储字，行下标i从1到8,列下标j从1到10。所17、算法分析的目的是(A)o

有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是(C)A找出数据结构的合理性

B研究算法中输入和输出的关系

A80B100C240D270C分析算法的效率以求改进

8、将一个递归算法改为对应的非递归算法时，通常需要使用(A)o

D分析算法的易懂性和文档性

A栈B队列C循环队列D优先队列

18、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行(B)。

9、一个队列的进队列顺序是1,2,3,,4则出队列顺序为(C)o

As—)link=p；p->link=s；Bs-〉link=p—>link；p—>link=s；

10、在循环队列中用数组A[0。。m-1]存放队列元素，其队头和队尾指针分别为front和rear,

Cs->link=p—>link；p=s;Dp—〉link=s;s-)link=p;

则当前队列中的元素个数是(

D)o19、设单链表中结点结构为(dataJinR。已知指针q所指结点是指针p所指结点的直接前驱，若

A(front-rear+1)%mB(rear-firont+1)%m

在*q与*p之间插入结点*s,则应执行下列哪一个操作(B)

C(front-rear+m)%mD(rear-front+m)%m

As—>link=p->link;p->link=s；Bq->link=s;s->link=p

11、一个数组元素@[”与(A)的表示等价。

Cp->link=s->link;s->link=p：Dp->link=s;s-〉link=q；

A*(a+i)Ba+iC*a+iD&a+i

20、设单链表中结点结构为(data,link)。若想摘除结点*p的直接后继，则应执行下列哪♦个操constintMaxsize=100:

作(A)typedefintDataType;

Ap—>link=p—〉link—>link;Bp=p—〉link；p-)link=p->link->link；typedefstruct{

Cp—>link=p—>link；Dp=p—)link-)link；DataTypedata[Maxsize]：

21、设单循环链表中结点的结构为(datajink),且rear是指向非空的带表头结点的单循环链表的Intfront,rear;

尾结点的指针.若想删除链表第一个结点，则应执行下列哪一个操作(D)}Queue;

As=rear;rear=rear—〉link；deletes：Brear=rear-)link;deleterear;若有一个Queue类型的队列Q,试问判断队列满的条件应是下列哪一个语句(D)

AQcfront==Q.rear：BQ.front-Q。rear==Maxsize；

Crear=rear->link-)link：deleterear;Ds=rear—)link->link;rear->linkCQofront+Q.rear==Maxsize;DQ.front==(Q.rear+1)%Maxsize;

、设有一个递归算法如下：

—>link=s-)link;deletes；31

22>设单循环链表中结点的结构为(data,link),旦first为指向链表表头的指针，current为intfact(intn)

{if(n<=0)return1；

链表当前指针，在循环链表中检测current是否达到链表表尾的语句是(D)。

elsereturnn*fact(n—1)；

Acurrent->link=nullBfirst)-link=current

)

Cfirst=currentDcurrent-)link二first

下面正确的叙述是(B)

23、一个栈的入栈序列为a,b,c,则出栈序列不可能的是(C)o

A计算fact(n)需要执行n次递归Bfact(7)=5040

Ac,b,aBb,a,cCc,a,bDa>c,b

C此递归算法最多只能计算到facl(8)D以上结论都不对

24、栈的数组表示中,top为栈顶指针,栈空的条件是(A)。

32、设有一个递归算法如下

Atop=0Btop=maxSizeCtop=maxSizeDtop=-1

intx(intn)(

25、栈和队列的共同特点是(C)o

if(n(=3)return1；

A都是先进后出B都是先进先出

elsereturnx(n—2)+x(n-4)+1;

C只允许在端点处插入和删除D没有共同点

)

26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r,则判断队空的条件为(D).

试问计算x(x(8))时需要计算(D)次x函数。

Af+l==rBr+l==fCf==0Df==r

A8次B9次C16次D18次

27、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为(B)

33、设有广义表D(a,b,D),其长度为(B),深度为(A)

An—2Bn—1CnDn+l

AsB3C2D5

28、当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一

34、广义表A(a),则表尾为(C)

个元素时，首先应执行()语句修改top指针。

AaB(())C空表D(a)

Atop++；Btop—；Ctop=0；Dtop;

35、下列广义表是线性表的有(C)

29、设链式栈中结点的结构为(dala,link),且top是指向栈顶的指针。若想摘除链式栈的栈顶

AE(a,(b,c))BE(a,E)CE(a,b)DE(a,L())

结点，并将被摘除结点的值保存到x中，则应执行下列(A)操作。

36、递归表、再入表、纯表、线性表之间的关系为(C)

Ax=top->data;top=top—〉link；Btop=top->link；x=top—〉data；

A再入表>递归表〉纯表〉线性表B递归表>线性表〉再入表〉纯表

Cx=top；top=top—〉link；Dx=top->data;

C递归表》再入表〉纯表〉线性表D递归表〉再入表〉线性表,纯表

30、设循环队列的结构是：

37、某二叉树的前序和后序序列正好相反，则该二叉树一定是（B）的二叉树。4、设有两个串p和q,求p在q中首次浮现的位置的运算称为（模式匹配）

A空或者惟独一个结点B高度等于其结点数5、栈、队列逻辑上都是（线性存储）结构。

C任一结点无左孩子D任一结点无右孩子6、线性结构反映结点间的逻辑关系是（一对一）的，图中的数据元素之间的关系是（多对多）的，

38、对于任何一棵二叉树T,如果其终端结点数为n席为2的结豆为n。，贝女A）树形结构中数据元素间的关系是（一对多）的。

B2n=n+l0=C2n2n+l,0Dn=2n+l7、栈中存取数据的原则（后进先出），队列中存取数据的原则（先进先出）

、由权值分别为的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）

3911,8,6,2,5B8、串是由（零个或者多个）字符组成的序列。（长度为零的串）称为空串，（由一个或者多个

A24B73C48D53空格组成的串）称为空格串。

40、已知一个顺序存储的线性表，设每•个结点需占m个存储单元，若第•个结点的地址为dal,9、设目标串，模式则第（6）次匹配成功。

则第1个结点的地址为（A）。10、一维数组的逻辑结构是（线性结构），存储结构是（顺序存储表示）。对于二维数组，有（行优

（一）（）

Ada1+11*mBdal+I*mCdal-I*mDdal+I+l*m先顺序）和（列优先顺序）两种不同的存储方式，对于一个二维数组A[m][n],若采用按行优先存放的

41、34具有35个结点的彻底二叉树的深度为（A）

方式，则任一数组元素A[i]Hj相对于A[0][0]的地址为（n*i+j）«

A5B6C7D8

11、向一个顺序栈插入一个元素时，首先使（栈顶指针）后移一个位置，然后把待插入元素（写）到这

、对线性表进行折半搜索时，要求线性表必须（）

42C个位置上。从一个顺序栈删除元素时,需要前移一位（栈顶指针）。

A以链接方式存储且结点按关键码有序罗列B以数组方式存储

12^在一个循环队列Q中，判断队空的条件为（Q.front==Q。rear）,判断队满的条件为（（Q。rear+1）

C以数组方式存储且结点按关键码有序罗列D以链接方式存储

%MaxSize==q.front）

43、顺序搜索算法适合于存储结构为（B）的线性表。

13、对于一棵具有n个结点的树，该树中所有结点的度数之和为（n—1）。

A散列存储B顺序存储或者链接存储

14、一棵高度为5的满二叉树中的结点数为（63）个，一棵高度为3满四叉树中的结点数为（85

C压缩存储D索引存储

）个。

44、采用折半搜索算法搜索长度n为的有序表时，元素的平均搜索长度为C（）

15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组中，即编号为0的

AO（n2）BO（nlogn）CO^logn）D0（n）

结点存储到a[0]中，其余类推，则a[i]元素的左子女结点为（2*i+l）,右子女结点为（2

45、对于一个具有n个顶点和e条边Q无向图，进.拓扑排序时，总的时间为（A）

*i+2）,双亲结点（i>=1）为（「（i-l）/2-|）.

AnBn+1Cn—1Dn+e

16、在一个最大堆中，堆顶结点的值是所有结点中的（最大值），在一个最小堆中，堆顶结点的

46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（C）。

值是所有结点中的（最小值）。

A求关键路径的方法B求最短路径的Dijkstra方法

17、已知具有n个元素的一维数组采用顺序存储结构，每一个元素占k个存储单元，第一个元素的

C深度优先遍历算法D广度优先遍历算法

地址为LOC（al）,那末，LOC（为）=LOC（al）+（i-l）*k。

47、在10阶B—树中根结点所包含的关键码个数最多为（C）,至少为（A）

18、在霍夫曼编码中，若编码长度只允许小于等于4,则除掉已对两个字符编码为0和10外，还可

A1B2C9D10

以最多对（4）个字符编码。

48、对包含n个元素的散列表进行搜索，平均搜索长度为（C）

19、设高度为h的空二叉树的高度为-1,惟独一个结点的二叉树的高度为0,若设二叉树惟独度

AO（logn）2BO（n）C不直接依赖于nD上述都不对

为2上度为0的结点，则该二叉树中所含结点至少有（2h+l）个。

二、填空题o

20、由一棵二叉树的前序序列和（中序序列）可惟一确定这棵二叉树。

1、数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构四种

21、以折半搜索方法搜索一个线性表时，此线性表必须是（顺序）存储的（有序）表。

2、数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构四种

22、已知彻底二叉树的第8层有8个结点，则其叶子结点数是（68）。若彻底二叉树的第7有10

3、一种抽象数据类型包括（数据）和（操作）两个部份。

个叶子结点，则整个二叉树的结点数最多是（235）

23、对于折半搜索所对应的判定树，它既是一棵（二叉搜索树），又是一棵（理想平衡树）。41、在索引表中，每一个索引项至少包含有（关键码值）域和（子表地址）域这两项.

24、假定对长度n=50的有序表进行折半搜索，则对应的判定树高度为（5）,判定树中前5层的42、假定一■个线性表为（"abed"，’baabd”,“beef',",'','bkwte","ccdt'',"

结点数为（31）,最后一层的结点数为（19）。），若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的

25、在一个无向图中，所有顶点的度数之和等于所有边数的（2）倍。在一个具有n个顶点的无向a.b,c三个子表的长度分别为（3）,3（）,（2）。

彻底图中，包含有（n（n—1）/2）条边，在一个具有n个顶点的有向彻底图中，包含有（n（n—1））条43、对于包含50个关键码的3阶B-树，其最小高度为（4）,最大高度为（5）。

边。44、从•棵B-树删除关键码的过程，若最终引起树根结点的合并，则新树比原树的高度（减1）45

26、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（n）和（n-1）、假定要对长度n=100的线性表进行散列存储,并采用开散列法处理冲突，则对于长度m=20的散

列表，每一个散列地址的同义词子表的长度平均为（5）。

27、设线性表中元素的类型是实型，其首地址为1024,则线性表中第6个元素的存储位置是（

1044）。46、在散列存储中，装载因子a又称为装载系数，若用m表示散列表的长度，n表示待散列存储的

28、在插入和选择排序中，若初始数据基本正序，则选择（插入排序），若初始数据基本反序，则最好元素的个数，则a等于（n/m）.

选择（选择排序）.47、在有向图的邻接矩阵中，第i行中"的个数是第i个顶点的（出度），第i列中“1”的个数是第i个

29、算法是对特定问题的求解步骤的一种描述，它是（指令）的有限序列,每一条（指令）表示一个或顶点的（入度）。在无向图的邻接矩阵中，第i行（列）中“1”的个数是第i个顶点的（度），矩阵中“I”

者多个操作.的个数的一半是图中的（边数）。

30、对于一个具有n个顶点肯e条边的无向图，进行拓朴排序时，总的进间为（n）48、在对m阶B—树中，每一个非根结点的关键码数至少为（「m/2-j-l）个，最多为（m-1）个，其子

31、构造哈希函数有三种方法，分别为（平方取中）法、（除留余数）法、（折迭移位）法。32树棵数至少为（［rn/2-］）,最多为（m）。

、处理冲突的三种方法，分别为（线性探测）、（随机探测）、（链地址法）。三、判断题

33、对于含有n个顶点和e条边的无向连通图，利用普里姆算法产生的最小生成树，其时间复杂1、数据元素是数据的最小单位（）。

2

度为（O（m）卜利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（0（eloge））2、数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的（力。

34、快速排序在平均情况下的时间复杂度为（0（nlogn））?在最坏情况下的时间复杂度为（03、数据结构是指相互之间存在一种或者多种关系的数据元素的全体（）.

（m））：快速排序在平均情况下的空间复杂度为（O（logn）以在最坏情况下的空间复杂度4、从逻辑关系上讲,数据结构主要分为两大类：线性结构和非线性结构（力。

为（0（n））.5、线性表的逻辑顺序与物理顺序总是一致的（）.

35、假定一组记录的排序码为（46,79,56,38,40,80）,对其进行归并排序的过程中，第6、二维数组是其数组元素为线性表的线性表（）.

二趟排序后的结果是（［38465679］［4080］）7、每种数据结构都应具备三种基本运算：插入、删除、搜索（力。

36、假定一组记录的排序码为（46,79,56,38,40,80）,对其进行快速排序的第一次划分的结8、非空线性表中任意一个数据元素都有且仅有一个直接前驱元素.（）

果是（［3840J46［567980］）.9、空串与由空格组成的串没有区别。（）

37、一个结点的子树的（个数）称为该结点的度。度为（零）的结点称为叶结点或者终端结点10、将T在S中首次浮现的位置作为T在S中的位置的操作称为串的模式匹配。（力

。度不为（零）的结点称为分支结点或者非终端结点.树中各结点度的（最大值）称为树的度11、深度为h的非空二叉树的第h层最多有2h-l个结点（）

12、彻底二叉树就是满二叉树。（）

38、设K邛（l<=i<=n.l<=j<=nj0i）耳在弓序前的序列中R率先于R（i（j）,若排序后13、已知一棵二叉树的前序序列和中序序列可以惟一地构造出该二叉树。（<）

的序列中Rj仍率先于R.则这种排序方法是（稳定的），反之是（不稳定的）。14、带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。（力15、

40、在堆&序的过程中：对任一分支结点进行调整运算的时间复杂度为（0（logn〃，整个

线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。

排序过程的时间复杂度为（O（nlogn）X)

16、若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子出栈序列?答案：可能的出栈序列有种，6457321不是合理的出栈序列。

树的前序遍历结果序列的最后一个结点。(小3、简单(直接)选择排序是一种稳定的排序方法吗？试举例说明？

17、任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索答案：是不稳定的排序方法.卜面就是不稳定的例子。只要能举出反例即可。

时间。()(275275*512061}i=1

18、最优二叉搜索树一定是平衡的二叉搜索树。N){061275*512275)i=2

19、AOE网是一种带权的无环连通图.«){061275*512275}i=3

20、对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是{061275*275512}

、设有序顺序表为{采用折半搜索时，搜索成功的平均

相同的().410,20,30,40,50,60,70},

21、二叉排序树可以是一棵空树(Y)搜索长度是多少？

22、线性表中所有结点的类型必须相同。(4)答案：ASL心=(1*1+2*2+3*4”7=17/7

、在结点个数为的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分

23、n个结点的有向图，若它有n(n—l)条边，则它一定是强连通的。(Y)5n(n>1)

支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？

24、任何无环的有向图，其结点都可以排在一个拓扑序列里。(()

答案：结点个数为n时，高度最小的树的高度为1,有2层；它有n—I个叶结点，I个分支结点；高

25、队列逻辑上是一个下端口和上端能增加又能减少的线性表()

26、二叉树是树的一种特殊情况(<)度最大的树的高度为n-l,有n层；它有I个叶结点"1个分支结点。

6、一棵高度为h的满k叉树有如下性质:第h层上的结点都是叶结点,其余各层上每一个结点都有k

27、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点

棵非空子树，如果按层次自顶向下，同一层自左向右,顺序从1开始对全部结点进行编号，试问：

个数有关，而与图的边数无关N).

⑴各层的结点个数是多少？

28、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都合用。()

(2)编号为i的结点的父结点(若存在)的编号是多少？

29、连通分量是无向图中的极小连通子图。()

(3)编号为i的结点的第m个孩子结点(若存在)的编号是多少？

30、在AOE网络中一定惟独一条关键路径。()

(4)编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？

31、关犍活动不按期完成就会影响整个工程的完成时间.(外

(5)若结点个数为n,则高度h是n的什么函数关系？

32、平衡二叉树的摆布子树深度之差的绝对值不超过1。(Y)

答案：⑴各层的结点个数是k“i=0,I,2,.h)

33、快速排序是对起泡排序的一种改进.(7)

(2)编号为i的结点的父结点(若存在)的编号是L(i+k—2)/kJ

弘、直接选择排序稳定。()

(3)编号为i的结点的第m个孩子结点(若存在)的编号是(i-1)*k+m+1

35、堆排序占用的辅助空间很大.()

(4)当(i-l)%k<>0时有右兄弟，右兄弟的编号为i+1

36、在散列法中采取开散列法来解决冲突时，其装载因子的取值一定在(0,1)之间。()

(5)若结点个数为n,则高度h和n的关系为：h=log(n*(k-l]+l)I(n=0

37、B一树是一种动态索引结构，它既合用于随机搜索，也合用于顺序搜索。()

时h=4)

38、在散列法中，一个可用散列函数必须保证绝对不产生冲突。()

、写出下列中缀表达式的后缀形式：

39、任何一个关键活动延迟，那末整个工程将会延迟。(<)7

(1)A*-B+C(2)(A+B)*D+E/(F+A*D)+C

40、任何一个关键活动提前完成，那末整个工程将会提前完成。()

(3