数据结构复习题目.docx

数据结构复习题目.docx

《数据结构复习题目.docx》由会员分享，可在线阅读，更多相关《数据结构复习题目.docx（25页珍藏版）》请在冰点文库上搜索。

数据结构复习题目

数据结构复习题

（打星号内容可以不考虑）

习题1绪论

1.1单项选择题

1.数据结构是一门研究非数值计算的课程，它研究程序设计问题中数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。

①A．操作对象　　　Ｂ．计算方法　　Ｃ．逻辑结构　　Ｄ．数据映象

②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法

2.数据结构DS（DataStruct）可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。

①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象

②A．操作Ｂ．映象Ｃ．存储Ｄ．关系

3.在数据结构中，从逻辑上可以把数据结构分成。

A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构

Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构

4.算法分析的目的是①，算法分析的两个主要方面是②。

①A.找出数据结构的合理性B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进D.分析算法的易懂性和文档性

②A.空间复杂性和时间复杂性B.正确性和简明性

C.可读性和文档性D.数据复杂性和程序复杂性

5.计算机算法指的是①，它必具备输入、输出和②等五个特性。

①A.计算方法B.排序方法

C.解决问题的有限运算序列D.调度方法

②A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性

C.确定性、有穷性和稳定性D.易读性、稳定性和安全性

1.2填空题（将正确的答案填在相应的空中）

1.数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。

2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。

3.在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。

4.在图形结构中，每个结点的前驱结点数和后续结点数可以。

5.线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。

6.算法的五个重要特性是____,____,____,____,____。

7.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是____。

for（i=0;i

for（j=0;j

A[i][j]=0;

8.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是____。

for（i=0;i

for（j=0;j

A[i][j]=0;

9.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是____。

s=0;

for（i=0;i

for（j=0;j

for（k=0;k

s=s+B[i][j][k];

sum=s;

10.分析下面算法（程序段）给出最大语句频度，该算法的时间复杂度是____。

i=s=0;

while（s

{i++;

s+=i;//s=s+i

}

11.分析下面算法（程序段）给出最大语句频度，该算法的时间复杂度是____。

i=1;

while（i<=n）

i=i*2;

习题2线性表

2.1单项选择题

1.一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是____。

A.110B.108C.100D.120

2.线性表的顺序存储结构是一种___的存储结构，而链式存储结构是一种___的存储结构。

A．随机存取B．索引存取C．顺序存取D．散列存取

3.线性表的逻辑顺序与存储顺序总是一致的，这种说法___。

A.正确B.不正确

4.线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。

A.必须是连续的B.部分地址必须是连续的

C.一定是不连续的D.连续或不连续都可以

5.在以下的叙述中，正确的是___。

A.线性表的顺序存储结构优于链表存储结构

B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况

C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况

D.线性表的链表存储结构优于顺序存储结构

6.每种数据结构都具备三个基本运算：

插入、删除和查找，这种说法___。

A.正确B.不正确

7.不带头结点的单链表head为空的判定条件是____。

A.head==NULLB.head->next==NULL

C.head->next==headD.head!

=NULL

8.带头结点的单链表head为空的判定条件是____。

A.head==NULLB.head->next==NULL

C.head->next==headD.head!

=NULL

9.非空的循环单链表head的尾结点（由p所指向）满足____。

A.p->next==NULLB.p==NULL

C.p->next==headD.p==head

10.在双向循环链表的p所指结点之后插入s所指结点的操作是____。

A.p->right=s;s->left=p;p->right->left=s;s->right=p->right;

B.p->right=s;p->right->left=s;s->left=p;s->right=p->right;

C.s->left=p;s->right=p->right;p->right=s;p->right->left=s;

D.s->left=p;s->right=p->right;p->right->left=s;p->right=s;

11.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。

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

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

12.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。

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

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

13.在一个单链表中，若删除p所指结点的后续结点，则执行____。

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

C.p=p->next;D.p=p->next->next；

14.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较____个结点。

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

15.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是____。

A.O

（1）B.O（n）C.O（n2）D.O（nlog2n）

16.给定有n个元素的向量，建立一个有序单链表的时间复杂度是____。

A.O

（1））B.O（n）C.O（n2）D.O（n*log2n）

2.2填空题（将正确的答案填在相应的空中）

1.单链表可以做____的链接存储表示。

2.在双链表中，每个结点有两个指针域，一个指向______，另一个指向_____。

3.在一个单链表中p所指结点之前插入一个s（值为e）所指结点时，可执行如下操作：

q=head;

while（q->next!

=p）q=q->next;

s=newNode;s->data=e;

q->next=;//填空

s->next=;//填空

4.在一个单链表中删除p所指结点的后继结点时，应执行以下操作：

q=p->next;

p->next=____;//填空

delete;//填空

5.在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=____和p->next=____的操作。

6.对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是____；在给定值为x的结点后插入一个新结点的时间复杂度是____。

习题3栈和队列

3.1单项选择题

1.一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是____。

A.edcbaB.decbaC.dceabD.abcde

2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为____。

A.iB.n-iC.n-i+1D.不确定

3.栈结构通常采用的两种存储结构是____。

A.顺序存储结构和链式存储结构

B.散列方式和索引方式

C.链表存储结构和数组

D.线性存储结构和非线性存储结构

4.判定一个顺序栈ST（最多元素为m0）为空的条件是____。

A.top!

=0B.top==0C.top!

=m0D.top==m0-1

5.判定一个顺序栈ST（最多元素为m0）为栈满的条件是____。

A.top！

=0B.top==0C.top！

=m0D.top==m0-1

6.栈的特点是____，队列的特点是____。

A.先进先出B.先进后出

7.向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行____。

（不带空的头结点）

A.HS—＞next=s;

B.s—＞next=HS—＞next;HS—＞next=s;

C.s—＞next=HS;HS=s;

D.s—＞next=HS;HS=HS—＞next;

8.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行____。

（不带空的头结点）

A.x=HS;HS=HS—＞next;B.x=HS—＞data;

C.HS=HS—＞next;x=HS—＞data;D.x=HS—＞data;HS=HS—＞next;

9.一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是____。

A.4，3，2，1B.1，2，3，4

C.1，4，3，2D.3，2，4，1

10.判定一个循环队列QU（最多元素为m0）为空的条件是____。

A.rear-front==m0B.rear-front-1==m0

C.front==rearD.front==rear+1

11.判定一个循环队列QU（最多元素为m0,m0==Maxsize-1）为满队列的条件是____。

A.（（rear-front）+Maxsize）%Maxsize==m0

B.rear-front-1==m0C.front==rearD.front==rear+1

12.循环队列用数组A[m]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。

A.（rear-front+m）%mB.rear-front+1

C.rear-front-1D.rear-front

13.栈和队列的共同点是____。

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

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

3.2填空题（将正确的答案填在相应的空中）

1.向量、栈和队列都是____结构，可以在向量的____位置插入和删除元素；对于栈只能在____插入和删除元素；对于队列只能在____插入元素和____删除元素。

2.向一个长度为n的向量的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动____个元素。

3.向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动____个元素。

4.栈顶指针指向栈顶元素，向栈中压入元素的操作是先________，后。

5.栈顶指针指向栈顶元素，对栈进行退栈时的操作是先________，后____。

6.在一个循环队列中，队尾指针指向队尾元素，队首指针指向____位置。

7.从循环队列中删除一个元素时，其操作是先________，后____。

8.在具有n个单元的循环队列中，队满时共有____个元素。

9.一个栈的输入序列是12345，则栈的输出序列43512是____。

10.一个栈的输入序列是12345，则栈的输出序列12345是____。

习题5数组和*广义表

5.1单项选择题

1.常对数组进行的两种基本操作是____。

A.建立与删除B.索引和修改

C.对数据元素的存取和修改D.查找与索引

2.二维数组M的元素是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从0到9，则存放M至少需要①__个字节；M数组的第8列和第5行共占②____个字节。

①A.90B.180C.240D.540

②A.108B.114C.54D.60

3.二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是____。

A.80B.100C.240D.270

4.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为____。

A.SA+141B.SA+144C.SA+222D.SA+225

5.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为____。

A.SA+141B.SA+180C.SA+222D.SA+225

5.2填空题（将正确的答案填在相应的空中）

1.已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC（A[0][0]），则A[i][j]的地址是_______。

2.二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是____。

3.二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是____。

*4．求下列广义表操作的结果：

（1）GetTail[GetHead[（（a,b）,c,d）]];

（2）GetTail[GetTail[（（a,b）,c,d）]]

*5.利用广义表的GetHead和GetTail操作写出如上题的函数表达式,把原子banana分别从下列广义表中分离出来.

（1）L1=（（（apple））,（（pear））,（banana）,orange）;

（2）L2=（apple,（（banana,）pear,orange））;

*6.画出下面广义表的两种存储结构图示

（（（a,b）,（d,（）））,（（e,（f））））

*7.写出下图存储结构所示的广义表（表达式），

习题6树和二叉树

6.1单项选择题

1.有关二叉树下列说法正确的是

A．二叉树的度为2B．一棵二叉树的度可以小于2

C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为2

2.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为个。

A．15B．16C．17D．47

3.按照二叉树的定义，具有3个结点的不同形状的二叉树有____种。

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

4.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有____种。

A.5B.6C.30D.32

5.深度为5的二叉树至多有____个结点。

A.16B.32C.31D.10

6.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。

A.2hB.2h-1C.2h+1D.h+1

7.对一个满二叉树，m个树叶，n个结点，深度为h，则____。

A.n=h+mB.h+m=2nC.m=h-1D.n=2h-1

8.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序____。

A.不发生改变B.发生改变C.不能确定D.以上都不对

9.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为____。

A.uwvtsB.vwutsC.wuvtsD.wutsv

10.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法____。

A.正确B.错误

11.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是____。

A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca

12.在一非空二叉树的中序遍历序列中，根结点的右边____。

A.只有右子树上的所有结点B.只有右子树上的部分结点

C.只有左子树上的部分结点D.只有左子树上的所有结点

13.如图6.1所示二叉树的中序遍历序列是____。

A.abcdgefB.dfebagcC.dbaefcgD.defbagc

图6.1

14.一棵二叉树如图6.2所示，其中序遍历的序列为____。

A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh

15．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是。

A．a在b的右方B．a在b的左方

C．a是b的祖先D．a是b的子孙

16.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____。

A.acbedB.decabC.deabcD.cedba

17.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是____

A．9B．11C．15D．不确定

18.如图6.3所示的4棵二叉树，____不是完全二叉树。

19.一棵完全二叉树上有1001个结点，其中叶子结点的个数是

A．250B．500C．254D．505E．以上答案都不对

20.在线索化二叉树中，t所指结点没有左子树的充要条件是____。

A.t—＞left=NULLB.t—＞ltag=1

C.t—＞ltag=1且t—＞left=NULLD.以上都不对

21.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法____。

A.正确B.错误

22.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。

这种说法____。

A.正确B.错误

23.一个具有1025个结点的二叉树的高h为____。

A．11B．10C．11至1025之间D．10至1024之间

24.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。

这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。

结论____是正确的。

A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同

B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同

C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同

D.以上都不对

25.树最适合用来表示____。

A.有序数据元素B.无序数据元素

C.元素之间具有分支层次关系的数据D.元素之间无联系的数据

6.2填空题（将正确的答案填在相应的空中）

1.有一棵树如图6.5所示，回答下面的问题：

⑴这棵树的根结点是____；

⑵这棵树的叶子结点是____；

⑶结点k3的度是____；

⑷这棵树的度是____；

⑸这棵树的深度是____；

⑹结点k3的子女是____；

⑺结点k3的父结点是____；

2.指出树和二叉树的两个主要差别____、____。

3.树可采用做存储结构，并利用解决树的有关问题。

4.一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图6.6所示，则该二叉树的链接表示形式为____。

5.深度为k的完全二叉树至少有____个结点。

至多有____个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是____。

6.在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0=____。

7.一棵二叉树的第i（i≥1）层最多有____个结点；一棵有n（n>0）个结点的满二叉树共有____个叶子和____个非终端结点。

8.一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为______。

9.现有按中序遍历二叉树的结果为abc，问有____种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是____（作图）。

10.由如图6.7所示的二叉树，回答以下问题：

⑴其中序遍历序列为____；

⑵其前序遍历序列为____；

⑶其后序遍历序列为____；

11.给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为__________，带权路径长度WPL的值为__________。

6.3简答题

1.根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。

2.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。

请画出该树。

3.由如图6.7所示的二叉树，回答以下问题：

（1）画出该二叉树的中序线索二叉树；

（2）画出该二叉树对应的森林。

4.已知一棵树如图6.8所示，转化为一棵二叉树，表示为___

5.以数据集{4，5，6，7，10，12，18}为结点权值，画出构造Huffman树的每一步图示，计算其带权路径长度为。

6.用一维数组存放的一棵完全二叉树如下图所示：

A

B

C

D

E

F

G

H

I

J

K

L

写出后序遍历该二叉树时访问结点的顺序。

习题7图

7.1单项选择题

1．在一个无向图中，所有顶点的度数之和等于所有边数的____倍。

A.1/2B.1C.2D.4

2．