数据结构练习题

练习题

一、判断题

1、线性表中每一个元素都有一个直接前驱和一个直接后继（0）

2、满二叉树的结点个数一定为奇数（1）

3、最短路径一定是简单路径。（1）

4、满二叉树的结点个数不一定为奇数。（0）

5、若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该

子树的前序遍历结果序列的最后一个结点。（0）

6、链表插入排序方法是稳定的。（1）

7、栈和队列的存储方式既可是顺序方式，也可是链接方式。（1）

8、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都合用。（0）

9、直接插入排序中的数据比较次数与数据的初始罗列无关。（0）

10、向栈顺序地输入一个整数序列1,2,345,,6能得到输出序列3,2,5,6,4,（11）

11、满二叉树的结点个数一定为奇数（1）

12、在惟独度为0和度为k的结点的正则k叉树中，设度为0的结点有n个，度为k的结

点有11k个,则有为=%+1。（0）

13、直接插入排序中的数据比较次数与数据的初始罗列无关。（0）

二、选择题

1、对表长为n的顺序表进行顺序搜索，在等概率情况下，搜索成功时的平均搜索长度为

（）。

A.（n+1）/2B.（n-l）/2C.n/2D.n

2、设双向循环链表中结点的结构为（data,ILink,rLink）,且不带头结点，若想在指针p所

指结点之后插入指针s所指的结点，则应执行下列哪个操作序列？（）

A.p->rLink=s；s->lLink=p；p->rLink->ILink=s；s->rLink=p->rLink；

B.p->rLink=s；p->rLink->lLink=s；s->lLink=p；s->rLink=p->rLink；

C.s->lLink=p；s->rLink=p->rLink；p->rLink->lLink=s；p->rLink=s；

D.s->lLink=p；s->rLink=p->rLink；p->rLink=s；p->rLink->lLink=s；

3、设栈S和队列Q的初始状态为空，元素el、e2、e3、e4、e5、e6和e7挨次通过栈S,一个

元素出栈后即进入队列Q,若6个元素出队的的顺序是e2、e4、e3、e6、e5、e7、el,贝ij栈S

的容量至少应该是（）

A.6B.4C.3D.2

4、向一个有127个元素的顺序表插入一个新元素并保持各元素原来的次序不变，则在等概

率情况下平均要挪移()个元素。

A.63.5B.63C.8D.7

5、以下关于链式存储结构的叙述中，()是不正确的。

A.结点除自身信息外还包括指针域

B.逻辑上相邻的结点物理上不必相邻

C.可以通过计算直接确定第i个结点的存储地址

D.插入、删除运算操作方便，不必挪移结点

6、设栈S和队列Q的初始状态为空，元素el、e2、e3、e4、e5和e6挨次入/出栈S,一个元素

出栈后即进入队列Q,若6个元素出队的的顺序是e2、e4、e3、e6、e5、el,则栈S的容量

至少应该是()o

A.6B.4C.2D.3

7、已知广义表的表头为a,表尾为(b,c),则此广义表为()。

A.(a,(b,c))B.(a,b,c)C、((a),b,c)D.((a,b,c))

8、AVL树是一种平衡的二叉搜索树，树中任一结点的()

A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左

子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度

9、在二叉树的前序遍历序列、中序遍历序列和后序遍历序列中，所有叶子结点的先后顺序

()

A.彻底相同B.都不相同

C.前序与中序相同，与后序不同D.中序与后序相同，与前序不同

10、在一个长度为n的线性表中顺序搜索值为x的元素，在等概率情况下，搜索成功时的平

均搜索长度为()

A.nB.n/2C.(n+l)2/D.(n-l)2/

11、若无向连通图G中有n个顶点，则其边数至少为()

A.nB.n-1C.n(n-l)D.n(n-l)/2

12、用直接插入排序方法对下面四个序列进行排序(由小到大),比较次数至少的是()

A.94、32、40、90、80、46、21、69B.32、40、21、46、69、94、90、80

C.21、32、46、40、80、69、90、94D.90、69、80、46、21、32、94、40

13、对有n个结点的顺序表进行快速排序，在最坏情况下其时间复杂度为()

A.O(n)B.O(log")C.O(nlog”)D.O(m)22

14、线性表采用链表存储时，其地址()

A、必须是连续的B、一定是不连续的

C、部份地址必须是连续的D、连续与否均可以

15、设有一个二维数组假，设A⑼[01引放位置在644的八⑵B存]放位置在676(助,每一个元素

占一个空间，则A[4][5在")位置，(⑼表明用10进数表示。

C、709D、724

（10）（10）

16、在一个表头指针为ph的不带头结点的单链表中，若要向表头插入一个由指针p指向的

结点，则应执行（）操作。

A.ph=p；p->next=ph；B.p->next=ph；ph=p；

C.p->next=ph；p=ph；D.p->next=ph->nex；tph->next=p；

17、设单循环链表中结点的结构为（data,linB,且rear是指向非空的带表头结点的单循环

链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪个操作？（）

A.s=rear;rear=rear->link;deletes;

B.rear=rear->link;deleterear;

C.rear=rear->link->link;deleterear;

D.s=rear->link->link;rear->link->link=s->link;deletes;

18、下列陈述中正确的是（）o

A.二叉树是度为2的有序树

B.二叉树中结点惟独一个孩子时无摆布之分

C.二叉树中必有度为2的结点

D.二叉树中最多惟独两棵子树，并且有摆布之分

19、如图所示的4棵树中，不是彻底二叉树的为（）。

20、AVL树是一种平衡的二叉排序树，树中任一结点的（）。

A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1

C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度

21、一个具有n个顶点的无向彻底图的边数为（）。

A.n（n+l）7B.n（n-l）2/

C.n（n-l）D.n（n+l）

22、下面的（）方法可以判断出一个有向图中是否有环（回路）？

A.深度优先遍历B.拓朴排序

C.求最短路径D.求关键路径

23、利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序

树以后，查找元素35要进行()元素间的比较。

A.4次B.5次

C.7次D.10次

24、下面给出的四种排序法中()排序法是不稳定性排序法。

A.直接插入B.冒泡

C.二路归并D.堆

25、二维数组A按行优先顺序存储，其中每一个元素占1个存储单位。若A[l]口的]存储地址

为420,A|3][3的]存储地址为446,则A|5|[5的]存储地址为()。

A.470B.471

C.472D.473

26、设有两个均惟独头指针的单链表，若要将长度为n的单链表链接到长度为m的单链表

之后，则实现该功能的算法的时间复杂度为()。

A.0(1)B.O(n)

C.O(m)D.O(m+n)

27、设单循环链表中结点的结构为(data,linB，且rear是指向非空的带表头结点的单循环链表

的尾结点的指针。若想删除链表第一个结点，则应执行下列哪个操作？()

A.s=rear;rear=rear->link;deletes;

B.rear=rear->link;deleterear;

C.rear=rear->link->link;deleterear;

D.s=rear->link->link;rear->link->link=s->link;deletes;

28、从堆中删除一个元素的时间复杂度为()o

A.0(1)B.O(n)

C.O(log2n)D.O(nlog2n)

29、对于一棵具有n个结点的二叉树，在其二叉链表的存储结构中，所有结点的空指针等于(

)。

A.nB.n-1

C.n+lD.2*n

30、如图所示的4棵二叉树中，不是彻底二叉树的为()o

(A)(B)(C)(D)

31、利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序

树以后，查找元素35要进行()元素间的比较。

A.4次B.5次

C.7次D.10次

32、在一个带权连通图G中，权值最小的边一定包含在G的()中。

A.最小生成树B.生成树

C.广度优先生成树D.深度优先生成树

33、一个有n个顶点和n条边的无向图一定是()。

A.连通的B.不连通的

C.无回路D.有回路

34、对n个关键字的序列进行快速排序，其平均情况下的空间复杂度为().

A.0(1)B.O(logn)

C.0(n)D.O(nlogn)

35、己知广义表的表头为(a,d),表尾为(b,c),则此广义表为()

A.((a,d),(b,c))B.((a,d),b,c)

C.(((a,d)),b,c)D.(((a,d),b,c))

36、在一棵AVL树中，每一个结点的平衡因子的取值范围是()

A.-1-1B.-2-2

C.1~2D.0~1

37、设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是()

人.11在112右方8.11是111的祖先

C.n在m左方D.n是m的子孙

38、若无向连通图G中有n个顶点，则其边数至少为()

A.nB.n-1C.n(n-l)D.n(n-1)/2

39、用直接插入排序方法对下面四个序列进行排序(由小到大)，比较次数至少的是()

A.94、32、40、90、80、46、21、69B.32、40、21、46、69、94、90、80

C.21、32、46、40、80、69、90、94D.90、69、80、46、21、32、94、40

40、关键码比较次数与待排序对象的初始罗列状态无关的排序方法是()

A.直接插入排序B.起泡排序

C.快速排序D.直接选择排序

41、将8个元素的序列｛4列38,65,97,76,13,27,50｝排序为递增有序,()是选择

排序法的第一趟的结果。

A.13,38,65,97,76,49,27,50B.13,27,38,49,50,65,76,97

C.97,76,65,50,49,38,27,13D.13,38,65,50,76,49,27,97

三、填空题

1、在下面的程序段中，语句p*寸的执行次数为（）

inti=0,s=0;

while（++i<n）

{

intp=l;

for（intj=1;j<=i;j++）p*=j;

s=s+p;

）

2、数据结构可定义为DS=（D,R）,其中，D是某一数据对象，口是（）。

3、算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应当具有输

入、输出、确定性、（）和有效性等特性。

4、在一个带头结点的单循环链表中（结点结构为：数据域data,指针域next）,指针p指向

尾结点的直接前驱，则指向头结点的指针head可用p表示为（）o

5、两个字符串相等的充要条件是（）。

6、顺序队列普通应该组织成环状队列的形式，此时普通队头或者队尾应做特殊处理，这样

做的原因是为了（）。

7、递归工作栈中的工作记录通常包括：（卜在本次过程调用时与形参结合的实参值

和本层的局部变量值。

8、一个二叉树按顺序方式存储在一个一维数组中，如图

01,23,4《678210,112131,4

ACDEFC|EIJ

则结点E在二叉树的第（）层。

9、在用于表示有向图的邻接矩阵中，对第j列的元素进行累加，可得到第j个顶点的（

）度。

10、拓扑排序方法可以检测AOV网络中是否存在（）。

11、在一个带头结点的单循环琏表中（结点结构为：数据域data,指针域next）,指针p指

向尾结点，则指向头结点的指针head可用p表示为（）。

12、两个字符串相等的充要条件是（）

13、数据结构是由某一数据对象和该对象中各个数据成员间的关系组成。依据所有数据成员

之间关系的不同，分为两大类：（）和（）。

14、在下面程序段中，s=s+p；语句的执行次数为（）o

inti=0,s=0;

while（++i<=n）

{

intp=1;

for（intj=l;j<=i;j++）p*=j；

s=s+p；

）

15、如果使用循环链表表示的队列的长度为n,且只设立头指针，则进队操作的时间复杂度

为（）。

16、递归工作栈中的工作记录通常包括：（卜在本次过程调用时与形参结合的实

参位和本层的局部变量值。

17、具有n个结点的二叉树，若采用二叉链表的存储结构，共有2n个指针域，其中空指针（

）个。

18、以折半搜索方法搜索一个顺序表时，此顺序表必须是（）o

19、在用于表示有向图的邻接矩阵中，对第J列的元素进行累加，可得到第J个顶点的

（）度。

20、对于一个具有n个顶点和e条边的有向图，在其对应的邻接表中，所含边结点为（

）个6、具有n个结点的二叉树，若采用二叉链表的存储结构，共有2n个指针域，其中空指

针（）个。

21、广义表L=C（xa）,（xa（b,的c）深），度丫）为（）

22、数据结构是由某一数据对象和该对象中各个数据成员间的关系组成。依据视点的不同，

分为数据的（）和（）«23、递归工作栈中的工作记录通常包

括：（）、在本次过程调用时与形参结合的实参值和本层的局部变量值。

24、一个顺序栈存储于一维数组a[m]中，当栈顶指针等于（）时，则为空栈。

25、有42个结点的二叉树的高度最小是（）。

26、在一棵二叉树中，假定度为2的结点有5个，度为1的结点有6个，则叶子结点数有（

）个。

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

28、对于一个具有n个顶点昨e条边的连通图，其生成树中的边数为（）.

010

29、从邻接矩阵A=101可以看出，若该图是有向图，则共有（）条边。010

30、直接插入排序在最好情况下的时间复杂度为（）

31、在单链表中，结点间的逻辑关系不是通过存储单元的顺序来表示的，而是通过

（）来实现的。

32、循环队列用数组A[0……m-l|存放其元素值，已知其头尾指针分别为ftont和rear,则当前

队列中的元素个数为（）

33、深度为k的彻底二叉树，若按自上而下，从左到右的次序给结点编号（从1开始），则编

号最小的叶子结点的编号是（）

34、假定一个有向图的顶点集为｛a,b,c,d,e,f｝,边集合为｛<a,c>,<a,e>,<c,fi>,

<d,c>,<e,b>,<e,d>）,则出度为0的顶点个数为（）。

35、如图所示的有向无环图可以排出（）种不同的拓扑序列。

四、简答与应用题

1、下列整数序列由前序遍历一棵二叉搜索树得到：50,40,30,45,65,55,70,80。试

构造一棵这样的二叉搜索树。

3、已知一棵二叉树如下，请分别写出按前序、中序、后序得到的结点序列。

3、设一组记录的排序码为(46,79,56,38,40,84,50,42),若需利用堆排序方法将其

排序为递增有序，应建立最小堆还是最大堆？并给出建立的初始堆。

4、有一份电文中共使用五个字符：a,b,c,d,e,它们的浮现频率挨次为4,7,529,试画出对应

的Huffman树，并给出每一个字符的Huffman编码。

5、已知一个无向连通网络G,如下图所示，完成以下问题：

(1)画出该连通网的邻接矩阵；

(2)试根据Kruskal算法，画出一棵最小生成树。(要求写出构造过程)

6、有7个带权结点，其权值分别为3,7,8,2,6,10,14,试以它们为叶子结点生成一

棵霍夫曼树，并求出该树的带权路径长度。

7、已知一个图的顶点集V和边集E分别为：

V={0,1,2,3,4,5}；

E={(0,1,8),(0,2,5),(0,3,2),(1,5,6),(2,3,10),(2,4,13),(3,5,9)}：其中边集E的

边结点结构为：(顶点1,顶点2,权值)。试根据Prim算法写出从顶点1出发得到最小生成树的

过程中，挨次选取的各条边，并求最小生成树的权。

8、设有一个10x10的对称矩阵A|10||10],采取按行压缩存储的方式存放于一'■一维数组B|]

中，则数组B[]的容量应该有多大？若设A⑼⑼为第一个元素，存放于B[0],且数组A[][]

的每一个数组元素在数组B口中占一个数组元素位置，则A[8][5]在数组因]中的地址是多少？

9、含有144个叶结点的彻底二叉树最多有多少个结点？试分析之。

10、有一个有序表R[1....13]={1,3,9,12,32,41,45,62,75,77,82,95,100),

当用折半搜索法搜索关键字为82的结点时，经过多少次比较后搜索成功？挨次与哪些关键

字进行了比较？

11、关键字序列｛12,7,18,13,17,29,34,6,8｝是否为堆？若不是，请将其调整为堆

(小根堆)，并统计建堆过程中的交换次数。

12、、已知一个无向连通网络G,如下图所示，完成以下问题：

(1)画出该连通网的邻接矩阵；

(2)试根据Kruskal算法，画出一棵最小生成树。

13、设表示式a+b*(c-d)-e/对f应的语法树如图所示，请写出该语法树的前序、中序、后序遍历

的结果序列。

14、有7个带权结点，其权值分别为3,7,8,2,6,10,14,试以它们为叶子结点生成一

棵霍夫曼树(要求左子女的权值小于右子女)，并求出该树的带权路径长度。

15、已知一个图的顶点集V和边集E分别为:

V={0,1,2,3,4,5)；

E={(0,I,8),(0,2,5),(0,3,2),(1,5,6),(2,3,10),(2,4,13),(3,5,9)}；其中边集E

的边结点结构为：(顶点1,顶点2,权值)。试写出按照普里姆(Prim)算法从顶点1出发得到

最小生成树的过程中，挨次选取的各条边，并求最小生成树的权。

(1)挨次选取的边为：

(2)最小生成树的权为：

16、在实际应用中时常遇到的稀疏矩阵是三对角矩阵，如下图所示。在该矩阵中除主对角线

及在主对角线上下最临近的两条对角线上的元素外，所有其他元素均为0。现在要将三对角

矩阵A中三条对角线上的元素按行优先方式存储在一维数组B中，且a存放于B10J.试给

H

出计算A在三条对角线上的元素a(1乎勺，i-1WjSi+1)在一维数组B中的存放位置

的计算公式。

17、已知彻底二叉树第6层有5个结点(根结点在第1层)，问该彻底二叉树有多少个结点？其

中有多少个叶结点？

18、若一个具有n个顶点，k条边的无向图是一个森林(n>k),则该森林中必有多少棵树。

19、如下图所示的二叉搜索树，画出删除65,再插入65后的二叉搜索树。

20、有一个有序表R[1……13]={1,3,9,12,32,41,45,62,75,77,82,95,100),

当用折半搜索法搜索关键字为82的结点时，经过多少次比较后搜索成功？挨次与哪些关键

字进行了比较？

21、已知一棵满二叉树的结点个数在20与40之间，此二叉树的叶子结点有多少个？

22、任意一个有n个结点的二叉树，已知它有m个叶子结点，试问它有多少个度为2的非叶子

结点？

23、给出以数据序列{4,5,6,7,10,12,18}为结点权值所构造的霍夫曼树，并计算其带

权路径长度。

24、画出对长度为10的有序表A[1……10]进行折半搜索的一棵判定树，并求其等概率时搜

索成功的平均搜索长度。

25、对于一个栈，输入项序列为A、B、C,试给出全部可能的输出序列。

答：ABC、ACB、BAC、BCA、CBA

五、算法填空

1、下面算法的功能是对含有n个互不相同元素的顺序表，经过一趟遍历同时找出最大元素

和最小元素。试填空完成该算法，并分析至少需要进行多少次比较？

voidmaxMin(seqlistr,intn,keytype&min,keytype&max)

(

inti;

min=max=r|0].key;

for(i=l;;i++)

if(r[i].key<min)

Else_____________________

max=r|i|.key;

)

2、下面非递归算法的功能为从BST所指的二叉搜索树中查找出值为item的元素，若查找成

功返回真，否则返回假。

说明：二叉搜索树的结点结构为(lef,tdata,rig"其中指针left和right分别指向结点的摆布子女。

boolFind(BTreeNod*BST,ElemTypeitem)

(

while(BST!=NULL){

if(item==BST->data)(D;

elseif(item<BST->data)@;

else③：

returnfalse;

)

3、下面是从一维数组A[n]中折半查找关键字为K的元素的非递归算法，若查找成功则返回

对应元素的下标，否则返回-1。

说明：一维数组A[n]关于关键字递增有序。

intBinsearch(ElemTypeA[],intn,KeyTypeK)

{//其中ElemType,KeyType分别为数据元素和关键字域的数据类型

intlow=0,high=n-1；

while(low<=high)

(

intmid；

mid=①；_______

if(K==A[mid].key)retummid；

elseif(K<A[mid].key)②；

else③；_________

)

return-1；

)

4、下面是有序顺序表类的折半搜索成员函数的递归实现，以实现在一维数组Element^]中

查找关键字为K的元素，若查找成功则返回对应元素的下标，否则返回

说明：一维数组Element^]关于关键字递增有序。

template<classType>intorderedList<Type>::

BinarySearch(constType&x,constintlow,constinthigh)const{

intmid=-1;

if(low<=high){

mid=(low+high)/2;

if(Element[mid].getKey()<x)//中点的关键码小于给定值

mid=BinarySearch(x,①，②);

elseif(Element]mid].getKey()>x