数据结构练习题1

一、选择题

1.下面说法错误的是一c_。

(1)算法原地工作的含义是指不需要任何额外的辅助空间。

(2)在相同的规模n下，复杂度O(n)的撒在时间上总是优于复杂度0(2。)的算法。

(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。

(4)同一个算法，实现语言的级别越高，执行效率越低。

A、(1)B、(1)(2)C、(1)(4)D、(3)

2.一个递归算法必须包括__B_。

A、递归部分B、终止条件和递归部分

C、迭代部分D、终止条件和迭代部分

3.数据的_C_包括查找、插入、删除、更新、排序等操作类型。

A、存储结构B、逻辑结构

C、基本运算D、算法描述

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

A、动态结构和静态结构B、紧凑结构利非紧凑结构

C、线性结构和非线性结构D、内部结构和外部结构

5.与数据元素本身的形式、内容、相对位置、个数无关的是数据的_C

A、存储结构B、存储实现

C、逻辑结构D、运算实现

6.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着一B_。

A、数据具有同一特点

B、不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要致

C、每个数据元素都一样

D、数据元素所包含的数据项的个数要相等

7.以下说法正确的是__D_»

A、数据元素是数据的最小单位

B、数据项是数据的基本单位

C、数据结构是带有结构的各数据项的集合

D、一些表面上很不相同的数据可以有相同的逻辑结构

8.以下说法错误的是上_o

A、程序设计的实质是数据处理

B、数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式

C、运算实现是完成运算功能的算法或这些算法的设计

D、数据处理方式总是与数据的某种相应表示形式相联系，反之亦然

9.下列程序段的时间复杂度为_B

x=n;

y=o；

while(x>=(y+l)*(y+l))

y=y+i;

A、0(n)B、0(n1/2)C、0(1)D、0(n2)

10.下列叙述中有关好的编程风格的正确描述是一C.。

A、程序中的注释是可有可无的

B、对递归定义的数据结构不要使用递归过程

C、过程应是自封闭的，尽量少使用全程变量

D、多采用一些技巧以提高程序的运行效率

二、填空题

1.一个算法有5个特性：有穷性、确定性、可行性、有零个或多个输入、有一个或

多个输出。

2.算法的时间复杂度是指该算法所求解问题_规模(或频度)的函数。

3.算法的可行性是指每一条_指令都应在有限的时间内完成»

4、线性结构的特征：逻辑上满足有且仅有一个开始结点和一个终端结点，且其余结点有一旦

仅有唯•的•个有接前趋和•个仃接后继一。

5.数据的存储结构被分为一顺序、链接、一索引_和_散列4种。

6.存储结构是逻辑结构的查僮实现，其基本目标是建立数据的一机内表示«

7.数据表示任务是逐步完成的，即数据表示形式的变化过程是：_机外表示f

_逻辑结构f存储结构o

8.数据处理任务也是逐步完成的，即转化过程是：一处理要求一基本运

算_-_篁返»

9.从逻辑关系上讲数据结构主要分为两大类，它们是一线性结构和一非线性结构。

10.数据结构的基本任务是数据结构的一巡L和一实现_。

三、给出下列算法的时间复杂度。

1、Sum(intn)

{

intsum=0,i,j;

for(i=l;i<=n;i++)

{

p=l;

for(j=l;j<=i;j++)

P=P*j；

sum=sum+p;

}

return(sum);

?

T(n)=0(n2)

2、j=l；

while(j<=n)

{j=j*2；

?

O(log2n)

习题二

一、选择题

1.线性表是具有n个_£的有限序列。

A、表元素B、字符C、数据元素

D、数据项E、信息项

2.线性表的静态链表存储结构与顺序存储结构相比优点是一C

A、所有的操作算法实现简单B、便于随机存储

C、便于插入和删除D、便于利用零散的存储器空间

3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂

度为一C.。

A、O(log2n)B、0(1)

C、0(n)D、0(n2)

4.(1)静态链表既有顺序存储的特点，又有动态链表的优点。所以，它存取表中第i个元

素的时间与i无关；

(2)静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加；

(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动.

以上错误的是__B—。

A、(1)、(2)B、(1)C、(1)、(2)、(3)D、(2)

5.将图2-6所示的s所指结点加到p所指结点之后，其语句应为__D__o

A、s—>next=p+l;p—>next=s;

B、(*p).next=s;(*s).next=(*p).next;

C、s—>next=p—>next;p—>next=s—>next;

D、s—>next=p—>next;p->next=s;

P

s

图2-6插入结点示意

6.在双向链表存储结构中，删除p所指的结点时须修改指针A_o

A、p—>next—>prior=p—>prior;p—>prior—>next=p—>next;

B、p—>next=p—>next—>next;p—>next—>prior=p;

C、p—>prioi'■—>next=p;p—>prior=p—>prior—>prior;

D、p—>prior=p—>next—>next;p—>next=p—>prior—>prior;

7.在双向循环链表中，在P指针所指的结点后插入q所指向的新结点，其修改指针的操作

是一£。

A、p—>next=q;q—>prior=p;p—>next—>prior=q;q—>next=q;

B、p—>next=q;p—>next—>prior=q;q—>prior=p;q—>next=p—>next;

C、q—>prior=p;q—>next=p—>next;

p—>next—>prior=q;p—>next=q;

D、q—>next=p—>next;q—>prior=p;p—>next=q;p—>next=q;

8.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是A

A、nb.2n—1c.2nd.n—1

9.在一个长度为n的顺序表中，在第i个元素(l&i&n+l)之前插入一个新元素时须向后

移动__B__个元素。

A、n—iB、n—i+1C、n—i—1D、i

10.线性表L=(ai，a2,……an),下列说法正确的是

A、每个元素有有一个直接前驱和一个直接后继

B、线性表中至少有一个元素

C、表中诸元素的排列必须是由小到大或由大到小。

D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。

11.对单链表表示法，以下说法错误的是__c

A、数据域用于存储线性表的一个数据元素

B、指针域(或链域)用于存放•个指向本结点所含数据元素的直接后继所在结点的指针

C、所有数据通过指针的链接而组织成单链表

D、NULL称为空指针，它不指向任何结点只起标志作用

12.若指定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是_C_

2

A、0(1)B、0(n)A0(n)D、O(nlog2n)

13.以下说法正确的是_o

A、顺序存储方式的优点是存储密度大且插入、删除运算率高

B、链表的每个结点中都恰好包含一个指针

C、线性表的顺序存储结构优于链式存储结构

D、顺序存储结构属于静态结构而链式结构属于动态结构

14.以下说法错误的是_A_

A、对循环链表来说，从表中任一结点出发都能通过前后移操作扫描整个循环链表

B、对单链表来说，只有从头结点开始才能扫描表中全部结点

C、双链表的特点是找结点的前趋和后继都很容易

D、对双链中来说，结点*p的存储位置既存放在其前趋结点的后继指针域中，也存放在它

的后继结点的前趋指针中

15.以下说法错误的是_D

A、求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实

现的效率低

B、序存储的线性表可以随机存取

C、由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活

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

二、判断题

1.线性表采用链表存储时;结点和结点内部的存储空间可以是不连续的。（错）

2.在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。（错）

3.顺序存储的线性表可以随机存取。（对）

4.在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存

储结构。（错）

5.在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。

（对）

6.顺序存储结构属于静态结构，链式结构属于动态结构。（对）

3、简述以下算法的功能：

statusA（linkedistL）

{〃L是无表头结点的单链表

if（L&&L—>next）

{Q=L;L=L—>next;P=L;

while（P—>next）P=P—>next;

P—>next=Q;Q—>next=NULL;

returnok;

}//A

本程序实现的功能就是：如果L的长度不小于2,则将首元结点删去并插入到末尾。

4、写出下列程序段的输出结果。（假设此栈中元素的类型是char）

voidmain()pop(s,x)

{stacks;push(s,'H');

charx,y;while(!stackEmpty(a))

InitStack(a){pop(s,y);

,

x=L'zy='O'printf(y);

push(s,x);)

push(s,x);printf(x)

push(s,y);)

push(s,x);

push(s,'E');

push(s,x);

此题的输出结果是HELOLLL,

5、以下为单链表删除运算，分析算法，请在_______处填上正确的语句。

voiddelete_lkist(lklisthead,inti)

{p=find_lkist(head,i-l);

if(p!=NULL)&&(D->next!=NULL)

{q=D—>next;

p—>next=q—>next;

free(q);

}

elseerror("不存在第i个结点”)

}

6、以下为顺序表的定位运算，分析算法，请在____处用正确的语句予以填充。

intlocate_sqlist(sqlistL,datatypeX)

{0,；

while(i£L>last)&&(Ldata[i-l]!=X)i++;

if(iWL.Iast_)return(i);

elsereturn(O);

}

7、以下为单链表的建表算法，分析算法，请在一处填上正确的语句

Iklistcreate_lklist2()

{head=malloc(size);

p=head;

scanf("%f",%x);

while(x!='$')

{q=malloc(size);

q—>data=x;

p—>next=q;

p=q_；

scanf(

}

_p—>next=NULL_;

return(head);

?

此算法的量级为-0(n)

习题三

一、选择题

1、若用单链表来表示队列，则应该选用一上

A、带尾指针的非循环链表B、带尾指针的循环链表

C、带头指针的非循环链表D、带头指针的循环链表

2、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为。和3。当

从队列中删除•个元素，再加入两个元素后，rear和front的值分别是一上一。

A、1和5B、2和4

C、4和2D、5和1

3、设栈的输入序列为1、2、3、4,则__C_不可能是其出栈序列。

A、1243B、2134C、1432D、4312E、3214

4、已知一算术表达式的中缀形式为A+B*C-D/E,后缀形式为ABC*+DE/-,其前缀形

式为_C_。

A、-A+B*C/DEB、-A+B*CD/E

C、-+*ABC/DED、-4-A*BC/DE

5、设栈的输入序列是1、2、…、n,若输出序列的第一个元素是n,则第i个输出元素

是一上一。

A、不确定B、n-i+1C、iD、n-i

6、假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判队空的条件

是_2_。

A、front+l==rearB、front==rear+l

C、front==0D、front==rear

7、假定一个顺序循环队列存储于数组A[n]中，其队首和队尾指针分别用front和rear

表示，则判断队满的条件是_B

A、(rear-l)%n==frontB、(rear+l)%n==front

C、rear==(front-l)%nD、rear==(front+l)%n

8、一个栈的的输入序列为12345,则下列序列中不可能是栈的输出序列的是_B

A、23415B、54132C、23145D、15432

9、若一个栈的输入序列是1、2、3、…、n,输出序列的第一个元素是i,则第i个输出元

素是__D_。

A.i-j-1B、i-jC、j-i+1D、不确定

10、用单链表表示的链式队列的队头在链表的_上一位置。

A、链头B、链尾C、链中

11、设计一个判别表达式中左、右括号是否配对出现的算法，采用__D_数据结构最佳。

A、线性表的顺序存储结构B、队列

C、线性表的链式存储结构D、栈

12、在下列算法描述中，涉及到队运算的算法是__D_o

A、表达式求值算法B、深度优先搜索

C、二叉树遍历D、广度优先搜索

13、栈的插入和删除操作在一A_进行。

A、栈顶B、栈底C、任意位置D、指定位置

14、在一个顺序循环队列中，队首指针指向队首元素的—A_位置。

A、前一个B、后一个C、当前D、最后

15、当利用大小为N的数组存储顺序循环队列时，该队列的最大长度为卫

A、N-2B、N-lC、ND、N+1

16、如果以链表作为栈的存储结构，则退栈操作时__C_o

A、必须判别栈是否满B、判别栈元素的类型

C、必须判别栈是否空D、对栈不作任何判别

17、链栈与顺序栈相比有一个明显的优点，BP_B

A、插入操作更加方便B、通常不会出现栈满的情况

C、不会出现栈空的情况D、删除操作更加方便

二、填空题

1、中绿式a+b*3+4*(c-d)对应的前缀式为++axb3x4-cd,若

a=l,b=2,c=3,d=4,则后缀式db/cc*a-b*+的运算结果为_18__。

2、用下标0开始的N元数组实现循环队列时，为实现下标变量m加1后在数组有效下标

范围内循环，可采用的表达式是m=(m+1)%n_»

3、表达式求值是_找一应用的一个典型例子。

4、队列是特殊的线性表，其特殊性在于_只允许在表的一端进行元素的插入而在另一端

进行元素的删除_0

5、一个循环队列存于A[M]中，假定队首和队尾指针分别为front和rear,则判断队空的

条件为_front==rear,判断队满的条件为(rear+1)%M==front_。

6、向-一个循环队列存入新元素时，需要首先移动队尾指针然后再向它所指位置一在

入一新元素。

7、_又称为先进先出表。

8、栈是特殊的线性表，其特殊性在于_只允许在栈顶加入或删除元素

9、栈又称为后进先出表，队列又成为_先进先出表。

10、在一个用一维数组A[N]表示的顺序栈中，该栈所含元素的个数最少为_Q_个，最

多为__N_一个。

11、在一个用一维数组A[N]表示的循环队列中，该队列中的元素个数最少为0个，最

多为—Nd.一个。

习题四

一、选择题

1、设有两个串p和q，求q和p中首次出现的位置的运算称作一C_»

A、连接B、求子串C、模式匹配D、求串长

2、若串S='goodstudent’,其子串的数目是_C_。

A、12B、79C、78D、13

3、串是一种特殊的线性表，其特殊性体现在_B_。

A、可以顺序存储B、数据元素是•个字符

C、可以链接存储D、数据元素可以是多个字符

4、串是任意有限个__D

A、符号构成的集合B、符号构成的序列

C、字符构成的集合D、字符构成的序列

5、已知模式串T='abcdabcd',则其next数组值为__B_

A,00123412B、01111234

C、01232412D、11213412

6、二维数组A的每个元素是由6个字符组成的串，其行下标i=0、1......8,列下标n

个]X110=[9i-108n=9j-10]8kl,2.....10。若A按行先存储，元素A[8,5]

的起始地址与当A按列先存储时的元素的—B—的起始地址相同。设每个字符占一个字

节。

A、A[8,5]B、A[3,10]C、A[5,8]D、A[0,9]

7、数组SZ[-3..5O,0..10]含有元素数目为一上一o

A、88B、99C、80D、90

8、稀疏矩阵••般的压缩存储方法有_C_两种。

A、二维数组和三维数组B、三元组和散列表

C、三元组和十字链表D、散列表和十字链表

9、一个nxn的对称矩阵，如果以行或列为主序放入内存，则其容量为_C

A、nxnnxn/2

C、(n+1)xn/2D、(n+1)x(n+l)/2

io、对数组经常进行的两种基本操作是_c

A、建立与删除B、索引与修改

C、查找与修改D、查找与索引

11、二维数组A[1O..2O,5..10]采用行序为主序方式存储，每个数据元素占4个存储单

元，且A[10,5]的存储地址是1000,则A[18,91的地址是A。

A、1208B、1212C、1368D、1364

二、填空题

1、两个字符串相等的充分必要条件是_长度相等且对应位置上字符相同,o

2、字符在串中的位置，即是字符在该序列中的序号。

3、串是指_含n个字符的有限序列且n>=0»

4、设有串S1='Ianastudent7,S2=,st,,index(Sl,S2)=8_»

5、含零个字符的串称为空一串，用油—表示；其他串称为一韭空一串。任何串中所含

的一包的个数称为该串的长度。

6、一个串中任意个连续字符组成的子序列称为该串的一王串，该串称为它的所有子串

的一串。

7、设数组a[1..50,L.80]的基地址为2000,每个元素占2个存储单元，若一行序为主

序顺序存储,则元素a[45,68]的存储地址为9174」若以列序为主序存储,则元素a[45,

68]的存储地址为_8788_»

8、数组结构是由固定数量的且由一个值和一组下标组成的数据元素构成，其元素间的下标

关系具有上下界约束及下标有序。

9、・维数组的逻辑结构是线性结构存储结构是顺序结构_；对二维或多维数组，

分为按以行为主序一和以列为主序_两种不同的存储方式。

10、需要压缩存储的矩阵可分为_特正矩阵和_场置矩阵两种。

11、数组元素间的关系由_W来限定。

12、有一个8x8的下三角矩阵A,若采用行序为主序顺序存储于一维数组a[l..n],则n

的值为_36。

三、判断题

1、稀疏矩阵压缩存储后，必会失去随机存取的功能。（对）

2、数组是同类型值的集合。（错）

3、数组是一种复杂的数据结构；数组元素之间的关系既不是线性的，也不是树形的。（对）

习题五

一、选择题

1、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满

足__C_O

A、所有的结点均无左孩子B、所有的结点均无右孩子

C、只有一个叶子结点D、是任意一棵二叉树

2、一棵完全二叉树上有1001个结点，其中叶子结点的个数是一E一。

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

3、以下说法正确的是—C

A、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序

列中的最后一个结点

B、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列

中的最后一个结点

C、在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一

个子女结点

D、在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点

4、以下说法错误的是_。

A、哈夫曼树是带权路径长度最短得数，路径上权值较大的结点离根较近

B、若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历

序列中的第一个结点

C、已知二叉树的前序遍历和后序遍历并不能唯地确定这棵树，因为不知道树的根结点是

哪一个

D、在前序遍历二叉树的序列中，任何结点其子树的所有结点都是直接跟在该结点之后的

5、一棵有124个叶结点的完全二叉树，最多有_A一个结点。

A、247B、248C、249D、250E、251

6、任何一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次序_A_o

A、不发生变化B、发生变化C、不能确定

7、设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件是—卫

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

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

8、设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数

为_,C

A、k+1B,2kC、2k-lD、2k+l

9、设有13个值，用它们组成•棵哈夫曼树，则该哈夫曼树共有_D_个结点。

A、13B、12C、26D、25

10,下面几个符号串编码集合中，不是前缀编码的是__B

A、{0,10,110,1111}B、{11,10,001,101,0001}

C、｛00,010,0110,1000｝D、｛b,c,aa,ac,aba,abb,abc)

11、欲实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳的方案是二叉树采

用_上一存储结构。

A、三叉链表B、广义表C、二叉链表D、顺序表

12、以下说法错误的是_B

A、存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同

B、二叉树是树的特殊情形

C、由树转换成二叉树，其根结点的右子树总是空的

D、在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树

13、树的基本遍历策略可分为先根遍历和后根遍历，二叉树的基本遍历策略可分为先序、

中序和后序三种遍历。我们把由树转化得到的二叉树称该树对应的二叉树，则下面

_A一是正确的。

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

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

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

D、以上都不对

14、若以二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序。则该二

叉树是__C

A、二叉排序树B、哈夫曼树遍历树cC、堆

15、下列有关二叉树的说法正确的是_B___。

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

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

16、某二叉树中序序列为ABCDEFG,后序序列为BDCAFGE,则前序序列是一旦

A、EGFACDBB、EACBDGF

C、EAGCFBDD、上面的都不对

17＞对二叉排序树进行__B__遍历，可以得到该二叉树所有结点构成的排序序列。

A、前序B、中序C、后序D、按层次

18、由二叉树的前序和后序遍历序列__B_唯一地确定这棵二叉树。

A、能B、不能

19、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的

结点数为2个，则度为0的结点数为一£个。

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

20、在一棵深度为h的完全二叉树中，所含结点的个数不小于_D_»

A、2hB、2h+1C、2h-lD、2h-1

21、在一棵具有n个结点的二叉树第i层上，最多具有__C_个结点。

A、21B、2i+1C、24D、2n

22、在下列情况中，可称为二叉树的是一B

A、每个结点至多有两棵子树的树B、哈夫曼树

C、每个结点至多有两棵子树的有序树D、每个结点只有一棵右子树

E、以上答案都不对

二、填空题

1、8层完全二叉树至少有_.128一个结点，拥有100个结点的完全二叉树的最大层数

为一7__»

2、树在计算机内的表示方式有_双亲表示法、一孩子表示法一、孩子兄弟表示法。

3、,棵有n个结点的满二叉树有_0__个度为1的结点，有_」n/2」一个分支（非终

端）结点和5/2」+1一个叶子，该满二叉树的深度为_Hogzn」+1_。

4、若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是孩子树

的一前序遍历序列中的最后•个结点。

5、一棵共有n个结点的树,其中所有分支结点的度均为k,则该树中的叶子结点个数为（nx

（k-1）+1）/k。

6、深度为k（设根的层数为1）的完全二叉树至少有2kzl个结点，至多有_2k-l个

结点。

7、设只包含根结点的二叉树高度为0,则高度为k的二叉树最大结点数为2k+l-l,

最小结点数为k+l。

8、•棵完全二叉树有999个结点，它的深度为10o

9、对于一棵具有n个结点的树，该树中所有结点的度数之和为jvlo

10、有n个结点并且其高度为n的二叉树有2rvl个。

11、一棵具有n个结点的二叉树，若它有n0个叶子结点，则该二叉树上度为1的结点

nl=_n-2no+1»

12、若一棵二叉树的叶子数为n0,则该二叉树中左、右子树皆非空的结点个数为nQzl。

13、设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有2n0-l个结点。

14、若以｛4、5、6、7、8｝作为叶子结点的权值构造哈夫曼树，则其带权路径长度是69。

三、判断题

1、完全二叉树的某结点若无左孩子，则它必是叶结点。（对）

2、存在这样的二叉树，对它采用任何次序的遍历，结果相同。（对）

3、二叉树就是结点度为2的树。（错）

4、二叉树中不存在度大于2的结点，当某个结点只有•棵子树时无所谓左、右子树。

错）

5、一知二叉树的前序遍历序列和后序遍历序列并不能唯一地确定这棵树，因为不知道树的

根结点是哪一一个。（错）

6、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特

殊处理。（错）

7、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（对）

8、将一棵树转换成二叉树后，根结点没有左子树。（错）

9、用树的前序遍历和中序遍历可以导出树的后序遍历。（对）

10、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（对）

11、不使用递归也能实现二叉树前序、中序和后序遍历。（对

第二部分判断题

1、顺序存储方式的优点是存储密度大，且插入和删除运算效率高（错）

2、循环队列中无上溢现象（错）

3、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置并不•定紧邻。（错）

4、栈和队列都是运算受限的线性表，只允许在表的两端进行运算。（错）

5、数据元素是数据的最小单位。（错）

6、顺序存储的线性表可以随机存储。（对）

7、线性表采用顺序存储，必须占用一片连续的存储单元。（对）

8、算法和程序没有区别，在数据结构中二者是通用的。（错）

9、顺序存储结构方式只能用于存储线性结构。（错）

10、线性表的链式存储结构优于顺序存储结构。（错）

11、线性表的链接存储，表中元素的逻辑顺序与物理顺序定相同。（错）

12、由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活。（错）

13、循环队列只有下溢，没有上溢。（错）

14、如果单链表带有头结点，则插入操作永远不会改变头结点指针的值。（对）

15、在循环单链表中，任何一个结点的指针字段值都不可能为空。（时）

16、空栈没有栈顶指针。（错）

17、无论是顺序队列还是链接队列，插入、删除运算的时间复杂度都是0（1）。（对）

18、在表示稀疏矩阵的三元组顺序表中，各元素的排列顺序与矩阵元素值的大小有关

（错）

19、线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便

成为线性表。（对）

20、稀疏矩阵的特点是矩阵中元素较少。（错）

第三部分填空题

1、q[l..maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置。作进栈操作时必

须判别栈满o如果要把栈顶元素取到x中，需执行下列语

句：a「++toDl=x。

2、带有表头结点的双链表L中，指针P所指结点是第一个结点的条件

是L-->next==Do

3、数据结构的三个要素是逻辑结构、存储结构、操作。

4、单链表中引入头结点的作用是为了方便操作。

5、算法的主要特性有：有穷性、确定性、可行性、输入和输出。

6、设循环队列存放在向量sq.data[0…m]中，队头指针sq.front在循环意义下的加1操

作可用模运算表示为（sa.front+l）%（m+l）；若用牺牲个单元的办法来区分队

满和队空的条件，则队满条件可以表示为（sa.rear+l）%（m+l）==sa.front

8、可以仅由一个尾指针来唯一确定，即从尾指针出发能访问到链表上任何一个结点的链表

有双向链及和循环链及。

9、单链表中，指针p所指结点为最后一个结点的条件是D-->next==NULL。

10、数据的逻辑结构包括线性结构、树型结构和图型结构三种类型。

11、对于长度为n的线性表A[L.n],插入和删除一个元素的时间复杂度为O（n）。

12、用二元组（D,R）来表示数据结构，那么D指数据的集合,R指这些数据

之间的关系的第合o

13、一条语句重复执行的次数称为频度

14、栈的运算主要有入栈、出栈、取栈顶元素、判断栈空、销毁栈等儿种。

15、在带头结点的单链表L中，第一个元素结点的指针为L-->next。

16、为了最快的存取某元素，数据结构宜用顺序存储结构；为了方便插入一个元素，

宜用链接存储结构。

17、带头结点的双链表为空的条件是head->next==NULL。

18、在进栈运算时，应先判别栈是否为满；作退栈运算时，应先判别栈是否为生。

2.选择题

⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的

存储结构。

A随机存取B顺序存取（：索引存取D散列存取

【解答】A,B

【分析】参见2,2.1。

⑵线性表采用链接存储时，其地址（）。

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

C一定是不连续的D连续与否均可以

【解答】D

【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元

可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。

⑶单循环链表的主要优点是（）。

A不再需要头指针了

B从表中任一结点出发都能扫描到整个链表；

C已知某个结点的位置后，能够容易找到它的直接前趋；

D在进行插入、删除操作时，能更好地保证链表不断开。

【解答】B

（4）链表不具有的特点是（）。

A可随机访问任一元素B插入、删除不需要移动元素

C不必事先估计存储空间D所需空间与线性表长度成正比

【解答】A

⑸若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋，则采用（）存储方

法最节省时间。

A顺序表B单链表C双链表D单循环链表

【解答】A

【分析】线性表中最常用的操作是取第i个元素，所以，应选择随机存取结构即顺序表，同

时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，

查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随

机存取。

（6）若链表中最常用的操作是在最后一个结点之后插入•个结点和删除第一个结点，则采用

（）存储方法最节省时间。

A单链表B带头指针的单循环链表C双链表D带尾指针的单循环链表

【解答】D

【分析】在链表中的最后•个结点之后插入一个结点需要知道终端结点的地址，所以，单链

表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第一个

结点，其时间性能是0（1），所以，答案是D。

⑺若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采

用（）存储方法最节省运算时间。

A单链表B循环双链表C单循环链表D带尾指针的单循环链表

【解答】B

【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链

表、单循环链表都不合适，删除最后一个结点需要知道终端结点的前驱结点的地址，所以，

带尾指针的单循环链表不合适，而循环双链表满足条件。

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

A0（1）B0（n）C0（n2）DO（nlog2n）

【解答】B

2.选择题

⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的

存储结构。

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

【解答】A,B

【分析】参见2.2.1。

⑵线性表采用链接存储时，其地址（）。

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

C一定是不连续的D连续与否均可以

【解答】D

【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元

可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。

⑶单循环链表的主要优点是（）。

A不再需要头指针了

B从表中任一结点出发都能扫描到整个链表；

C已知某个结点的位置后，能够容易找到它的直接前趋；

D在进行插入、删除操作时，能更好地保证链表不断开。

【解答】B

（4）链表不具有的特点是（）。

A可随机访问任一元素B插入、删除不需要移动元素

C不必事先估计存储空间D所需空间与线性表长度成正比

【解答】A

⑸若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋，则采用（）存储方

法最节省时间。

A顺序表B单链表C双链表D单循环链表

【解答】A

【分析】线性表中最常用的操作是取第i个元素，所以，应选择随机存取结构即顺序表，同

时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，

查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随

机存取。

⑹若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用

（）存储方法最节省时间。

A单链表B带头指针的单循环链表C双链表D带尾指针的单循环链表

【解答】D

【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链

表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第个

结点，其时间性能是。(1),所以，答案是D。

⑺若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采

用()存储方法最节省运算时间。

A单链表B循环双链表C单循环链表D带尾指针的单循环链表

【解答】B

【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链

表、单循环链表都不合适，删除最后一个结点需要知道终端结点的前驱结点的地址，所以，

带尾指针的单循环链表不合适，而循环双链表满足条件。

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

A0(1)B0(n)C0(n2)DO(nlog2n)

【解答】B

习题六

一、选择题

1、设无向图的顶点个数为n,则该无向图最多有__B一条边。

A、n-1B、n(n-1)/2C、n(n+1)/2

D、0E、n2

2、在下列两种求图的最小生成树的算法中，一_B—算法适合于求边稀疏的网的最小生成

树。

A、PrimB、Kruskal

3、下面的叙述中不正确的是__B_o

A、关键活动不按期完成就会影响整个工程的完成时间

B、任何一个关键活动提前完成，将使整个工程提前完成

C、所有关键活动都提前完成，则整个工程将提前完成

D、某些关键活动若提前完成，将使整个工程提前完成

4、采用邻接表存储的图，其深度优先遍历类似于二叉树的__B_

A、中序遍历B、先序遍历

C、后序遍历D、按层次遍历

5、采用邻接表存储的图，其广度优先遍历类似于二叉树的—A_。

A、按层次遍历B、中序遍历

C、后序遍历D、先序遍历

6、具有n个顶点的有向图最多有__B__条边。

A、nB、n(n-1)C>n(n+1)D、n2

7、•个n个顶点的连通无向图，其边的个数至少为A。

A、n-1B、nC、n+1D、nlog2n

8、下列说法中，正确的有一工_。

A、最小生成树也是哈夫曼树

B、最小生成树唯一

C、普里姆最小生成树算法时间复杂度为。(n2)

D、克鲁斯卡尔最小生成树算法普里姆算法更适合与边稠密的网。

10、判定•个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用一C_o

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

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

11、在一个具有n个顶点的有向图中，若所有顶点的出度之和为s,则所有顶点的入度之

和为_Ao

A、sB、s-1C、s+lD、n

12、在一个无向图中，若两个顶点之间的路径长度为k,则该路径上的顶点数为_B

A、kB、k+1C-.k+2D、2k

13、一个有n个顶点的无向连通图，它所包含的连通分量个数为_B

A>0B、1C>nD、n+1

14、对于一个有向图，若一个顶点的入度为kl、出度k2,则对应邻接表中该顶点单链表

中的结点数为_o

A、klB、k2C、kl-k2D、kl+k2

15、对于一个有向图，若一个顶点的入度为kl、出度k2,则对应逆邻接表中该顶点单链

表中的结点数为一A_o

A、klB、k2C、kl-k2D、kl+k2

16、为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用_Bo

A、顺序存储B、链式存储

C、索引存储D、散列存储

二、填空题

1、具有10个顶点的无向图，边的总数最多为一变o

2、在有n个顶点的有向图中，每个顶点的度最大可达2(n-1)。

3、克鲁斯卡尔算法的时间复杂度为-O(e