数据结构课后练习题汇编

更新时间：2023-11-23 20:31:01 阅读量：教育文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

数据结构第二章课后答案推荐度：
相关推荐

数据结构课后练习题

第一章绪论

一、选择题

1、数据结构被形式定义为（D，S），其中D是（）的有限集合，S是D上的（）有限集合。

A、算法 B、数据元素 C、数据操作 D、逻辑关系 E、操作 F、映象 G、存储 H、关系

2、数据结构是一门研究非数值计算的程序设计问题中计算机的（（1））以及它们之间的（ ② ）和运算的学科。

（1）A、操作对象 B、计算方法 C、逻辑存储 D、数据映象（2）A、结构 B、关系 C、运算 D、算法 3、算法分析的目的是（），算法分析的二个主要方面是（）。

A、给出数据结构的合理性 B、研究算法中输入输出的关系 C、空间复杂性和时间复杂性 D、分析算法的效率以求改进 E、正确性和简明性 F、分析算法的易懂性和文档性 4、在数据结构中，从逻辑上可以把数据结构分成（）。

A、动态和静态结构 B、紧凑接和非紧凑结构 C、线性与非线性结构 D、内部结构和外部结构 5、计算机算法指的是（），它必具备输入、输出和（）5个特性。

A、计算方法 B、排序方法 C、解决问题的有限运算序列 D、可行性、可移植性和可扩充性 E、可行性、确定性和有穷性

6、线性表的顺序存储结构是一种（）的存储结构，线性表的链式存储结构是一种（） A、随机存取 B、顺序存取 C、索引存取 D、散列存取 7、算法的时间复杂度取决于（）

A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态 8、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（） A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续不连续都可以 9、在以下的叙述中，正确的是（） A、线性表的线性存储结构优于链式存储结构

B、二维数组是它的每个数据元素为一个线性表的线性表 C、栈的操作方式是先进先出 D、队列的操作方式是先进后出

10、根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式。以下解释错误的是 ( )

A、集合中任何两个结点之间都有逻辑关系但组织形式松散 B、线性结构中结点按逻辑关系依次排列形成一条\锁链\

C、树形结构具有分支、层次特性，其形态有点像自然界中的树

D、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接 11、以下说法正确的是( ) A、数据元素是数据的最小单位 B、数据项是数据的基本单位

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

二、填空题

1、数据逻辑结构包括（）四种类型，树型和图型结构合称（）。 2、对于给定的n个元素，可以构造出的逻辑结构有（）、（）、（）和（）四种。 3、算法的五个重要特性是（）。

4、评价算法的性能从利用计算机资源角度看主要从（）方面进行分析。

5、线性结构中元素之间存在（）关系，树型结构中元素之间存在（）关系，图型结构中元素之间存在（）关系。

6、下面程序段的时间复杂度是（）。

i=s=0; while(s

7、下面程序段的时间复杂度是（）。

s=0; for(I=0;I

8、所谓数据的逻辑结构指的是数据元素之间的 _______。

9、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容________。 10、在线性结构中，开始结点_____前驱结点，其余每个结点有且只有____个结点。

11、在树形结构中，根结点只有______，根结点无前驱，其余每个结点有且只有______前驱结点；叶子结点没有______结点，其余每个结点的后继结点可以_____。

12、在图形结构中，每个结点的前驱结点和后继结点可以有_______。 13、存储结构是逻辑结构的__________实现。

14、从数据结构的观点看，通常所说的\数据\应分成三个不同的层次，即__________、__________和__________。

15、根据需要，数据元素又被称为__________、__________、__________或__________。

16、通常，存储结点之间可以有__________、__________、__________、________四种关联方式，称为四种基本存储方式。

17、通常从___________、___________、___________、___________等几方面评价算法的(包括程序)的质量。 18、一个算法的时空性能是指该算法的________________和________________，前者是算法包含的___________，后者是算法需要的___________。

19、在一般情况下，一个算法的时间复杂性是___________的函数。 20、常见时间复杂性的量级有：常数阶O(___________)、对数阶O(___________)、线性阶O ( ___________)、平方阶O(___________)、和指数阶O(___________)。通常认为，具有指数阶量级的算法是___________的。 21、数据结构的基本任务是数据结构的___________和___________。 22、数据对象是性质相同的的集合。

23、抽象数据类型是指一个以及定义在该模型上的一组操作。三、判断题

1. 数据元素是数据的最小单位。

2. 数据结构是带有结构的数据元素的集合。

3. 数据结构，数据元素，数据项在计算机中的映象分别称为存储结构，结点，数据域。 4. 数据项是数据的基本单位。

5. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。 6. 数据的物理结构是数据在计算机中实际的存储形式。 7. 算法和程序没有区别，所以在数据结构中二者是通用的。 8. 顺序存储结构属于静态结构，链式存储结构属于动态结构。

四、计算应用题

1、设n为正正数。确定下列各程序段中前置以记号@的语句的频度。

（1） I=1;k=0;

While(I

I++;}

k=0;

for(I=1;I<=n;I++) {for(j=I;j<=n;j++) @ k++;} (2) I=1;j=0;

While(I+j<=n) @ {if(I>j)j++;

else I++;}

2、写出下面算法中带标号语句的频度。 Void perm(int a[],k,n)

{ int x,I;

(1) if(k==n)

(2) for(I=1;I<=n;I++) (3) printf(“%d”,a[I]);

else

{(4) for(I=k;I<=n;I++) (5) a[I]+=I*I; (6) perm(a,k+1,n);}}

执行函数调用语句perm(a,1,n)

3、指出下列两个算法的时间复杂度。

（1） int sum1(int n)

{int p=1,sum=0,I;

for(I=1;I<=n;I++){p*=I;sum+=p;} return(sum);}

(2) int sum2(int n) {int sum=0,I,j;

for(I=1;I<=n;I++){p=1;for(j=1;j<=I;j++)p*=j; sum+=p;} returm(sum);}

4、有下列几种用二元组表示的数据结构，画出它们对应的逻辑图形表示，并指出它们属于哪种结构。（1）A=（K，R），其中：K={a,b,c,d,e,f,g,h} R=(r)

r={,,,,,,}

(2) B=(K,R),其中：K={a,b,c,d,e,f,g,h} R=(r) r={,,,,,,} (3)C=(K,R),其中：k={1,2,3,4,5,6} R={r} r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)} (4)D=(K.R), K={48,25,64,57,82,36,75},R={r1,r2}

r1={<25,36>,<36,48>,<48,57>,<57,64>,<64,75>,<75,82>} r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<84,75>}

5、设有如图所示的逻辑结构图，给出它的逻辑结构。

6、简述下列术语：数据，数据元素，数据结构，数据对象。 7、逻辑结构与存储结构是什么关系?

8、将数量级2，n，n2，n3，nlog2n，log2n，2n，n，n!，

10?23?n，n23，按增长率进行排列。

五、算法设计题

1. 已知输入x,y,z三个不相等的整数，设计一个算法，使得这三个数按从大到小输出，并考虑所用算法的比

较次数和元素移动次数。

2. 编写在输入10个数中找出最小或最大的数的算法。

3. 在数组A[n]中查找值为k的元素,若找到则输出其位置i(1≤i≤n),否则输出0作为标志。设计求解此问题

的类C语言算法，并分析其最坏情况时间复杂度。

第二章线性表练习题

一、选择题

1、表长为N的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（），删除一个元素需要移动的元素个数为（）。

A. (N-1)/2 B. N C. N+1 D. N-1 E. N/2 F. (N+1)/2 G. (N-2)/2 2、线性表是具有N个（）的有限序列。

A、表元素 B、字符 C、数据元素 D、数据项 E、信息 3、“线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（）。 A、正确的 B、错误的 C、不一定，与具体结构有关。

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

A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以。 5、带头结点的单链表为空的判定条件是（）。

A、head==NULL B、head->next==NULL C、head->next==head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是（）。

A、head==NULL B、head->next==NULL C、head->next==head D、head!=NULL 7、非空的循环单链表head的尾结点P满足（）。

A、P->NEXT=NULL B、p=NULL C、p->next==head D、p==head

8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。 A、O(1) B、O(n) C、O(n2) D、O(nlog2n)

9、在一个单链表中，若删除P所指结点的后继结点，则执行（）。Ａ、p->next=p->next->next Ｂ、p=p->next;p->next=p->next->next Ｃ、p->next=p->next; Ｄ、p=p->next->next; 10、在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（）。

Ａ、s->next=p;p->next=s; Ｂ、s->next=p->next;p->next=s; Ｃ、s->next=p->next;p=s; Ｄ、p->next=s;s->next=p;

11、在一个单链表中，已知q是p的前趋结点，若q和p之间插入结点s，则执行（）。

Ａ、s-next=p->next;p->next=s; Ｂ、p->next=s->next;s->next=p; Ｃ、q->next=s;s->next=p;Ｄ、p->next=s;s->next=q;

12、假设双链表结点的类型如下： typedef struct linknode{

int data; ／／数据域

struct linknode *llink; ／／指向前趋结点的指针域 struct linknode *rlink; ／／指向后继结点的指针域 }bnode

现将一个q所指新结点作为非空双向链表中的p所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是（）。

Ａ、q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q; Ｂ、p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink Ｃ、q->llink=p->rlink;q->rlink=p;p->llink->rlink=q;p->llink=q; Ｄ、以上都不对

１３、如上题结点结构，如在此非空循环双向链表的结点p之后插入结点s的操作序列是（）。Ａ、p->rlink=s;s->llink=p;p->rlink->llink=s;s->rlink=p->rlink; Ｂ、p->rlink->s;p->rlink->llink=s;s->llink=p;s->rlink=p->rlink; Ｃ、s->llink=p;s->rlink=p->rlink;p->rlink=s;p->rlink->llink=s; Ｄ、s->llink=p;s->rlink=p->rlink;p->rlink->llink=s;p->rlink=s;

14、在一个长度为n的单链表上，设有头和尾两个指针，执行（）操作与链表的长度无关。

Ａ、删除单链表中的第一个元素Ｂ、删除单链表中最后一个元素Ｃ、在单链表第一个元素前插入一个新元素Ｄ、在单链表最后一个元素后插入一个新元素 15、线性结构中的一个结点代表一个（）

A、数据元素 B、数据项 C、数据 D、数据结构 16、非空线性表L=(a1,a2,…,ai,…,an)，下列说法正确的是（） A、每个元素都有一个直接前驱和直接后继 B、线性表中至少要有一个元素

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

D、除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继 17、顺序表是线性表的（）

A、链式存储结构 B、顺序存储结构 C、索引存储结构 D、散列存储结构 18、对于顺序表，以下说法错误的是（）

A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻

D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中

19、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作。

A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n

10、若在一个大小为6的数组上实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（） A、1，5 B、2, 4 C、4，2 D、5，1

11、用单链表表示的链式队列的队头在链表的（）位置 A、链头 B、链尾 C、链中

12、判定一个链队列Q（最多元素为n个）为空的条件是（）

A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13、在链队列Q中，插入s所指结点需顺序执行的指令是（）

A、Q.front->next=s;f=s; B、Q.rear->next=s;Q.rear=s; C、s->next=Q.rear;Q.rear=s; D、s->next=Q.front;Q.front=s;

14、在一个链队列Q中，删除一个结点需要执行的指令是（） A、Q.rear=Q.front->next; B、Q.rear->next=Q.rear->next->next; C、Q.front->next=Q.front->next->next; D、Q.front=Q.rear->next;

15、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）

A、仅修改队头指针 B、仅修改队尾指针 C、队头尾指针都要修改 D、队头尾指针都可能要修改。 16、栈和队列的共同点是（）

A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 17、消除递归（）需要使用栈。 A、一定 B、不一定

18、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是（）

A、2 B、 3 C、 5 D、 6

19、若一个栈的输入序列是a,b,c，则通过入、出栈操作可能得到a,b,c的不同排列个数为（）

A、 4 B、 5 C、 6 D、 7 20、设有一顺序栈已经含有3个元素，如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是（）

A、a3,a1,a4,a2 B、 a3,a2,a4,a1 C、 a3,a4,a2,a1 D、 a4,a3,a2,a1

maxsize-1 0 a1 Top 图3.1 21、链栈和顺序栈相比，有一个比较明显的优势是（）

A、通常不会出现栈满的情况 B、通常不会出现栈空的情况 C、插入操作更容易实现 D、删除操作更加容易实现

22、若一个栈的输入序列是1,2,3,4,?,n，输出序列的第一个元素是n，则第i个输出元素是（）

A、不确定 B、 n-i C、 n-i+1 D、n-i-1 23、以下说法正确的是( )

A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 B、因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 C、对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢” D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。

二、判断题

1、在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。

a2 a3

2、链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。

3、若一个栈的输入序列为1，2，3，?，n，其输出序列的第一个元素为n，则其输出序列的每个元素

ai一定满足ai=i+1(i=1,2, ?,n)。

4、在链队列中，即使不设置尾指针也能进行入队操作。

5、在对链队列（带头指针）做出队操作时，不会改变front指针的值。 6、循环队列中元素个数为rear-front。

7、一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2。 8、一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。 9、若以链表作为栈的存储结构，则进栈需要判断栈是否满。 10、若以链表作为栈的存储结构，则出栈需要判断栈是否空。

三、填空题

1、栈的特点是（），队列的特点是（）。

2、线性表、栈、队列都是（）结构，可以在线性表的（）位置插入和删除元素；对于栈只能在（）插入和删除元素；对于队列只能在（）插入元素和在（）位置删除元素。

3、有程序如下，则此程序的输出结果（栈的元素类型是SelemType为char）是（）。

Void main()

{stack s; char x,y; initstack (s); x=?c?;y=?k?;

push(s,x);push(s,?a?);push(s,y);

pop(s,x);push(s,?t?);push(s,x);pop(s,x);push(s,?s?); while(!stackempty(s)){pop(s,y);printf(y);} printf(x);}

4、在栈顶指针为HS的链栈中，判定栈空的条件是（）。 5、向栈中压入元素的操作是先（）后（）。 6、对栈进行退栈操作是先（）后（）。

7、用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（）和（）；若只设尾指针，则出队和入队的时间复杂度分别是（）和（）。 8、从循环队列中删除一个元素时，其操作是（）。 9、在一个循环队列中，队首指针指向队首元素的（）。

10、在具有n个单元的循环队列中，队满时共有（）个元素。 11、在HQ的链队列中，判断只有一个结点的条件是（）。

12、设栈S和队列Q的出始状态为空，元素a,b,c,d,e,f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b,d,c,f,e,a 则栈S的容量至少应该是（）。

13、有程序如下，则此程序的输出结果（队列的元素类型是QSelemType为char）是（）。

Void main()

{char x=?e?,y=?c?;

enqueue(q,?h?);enqueue(q,?r?);enqueue(q,y);dequeue(q,x);enqueue(q,x);degueue(q,x); enqueue(q,?a?);

while(!queueempty(q)){dequeue(q,y);printf(y);} printf(x);}

14、有如下递归函数：

int dunno(int m)

{int value;if(m==0)value=3;

else value=dunno(m-1)+5;

return(value);}

执行语句printf(“%d\\n”,dunno(3));的结果是（）。四、简答题

1、对于堆栈，给出三个输入项A，B，C，如果输入项序列为ABC，试给出全部可能的输出序列，并写

出每种序列对应的操作。例如：A进B进C进C出B出A出，产生的序列为CBA。 2、简述以下算法的功能（栈的元素类型是SelemType为int）。

（1） status algo1(stack s)

{int I,n,a[255];n=0;while(!stackempty(s)){n++;pop(s,a[n]);} for(I=1;I<=n;I++)push(s,a[I]);}

(2) status algo2(stack s,int e)

{stack t;int d;initstack(t);while(!stackempty(s)){pop(s,d);if(d!=e)push(t,d);} while(!stackempty(t)){pop(t,d);push(s,d);}}

3、内存中一片连续空间（不妨假设地址从0到m-1）提供给两个栈s1和s2使用，怎样分配这部分存储

空间，使得对任一栈仅当这部分空间全满时才发生溢出。 4、有递归过程如下：

void print(int w){int I;if(w!=0){print(w-1)

for(I=1;I<=w;I++)printf(“=”,w);printf(“\\n”);}}

问：调用语句print(4)的结果是什么？

5、简述以下算法的功能（栈和队列的元素类型均为int）

void algo(queue &q) {stack s;int d;initstack(s);

while(!queueempty(q)){dequeue(q,d);push(s,d);} while(!stackempty(s)){pop(s,d);enqueue(q,d);} }

6、假设Q[0，9]是一个非循环线性队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针

的状态变化情况，如果不能入队，请指出其元素，并说明理由。

d,e,b,g,h入队 d,e出队 I,j,k,l,m入队 b出队 n,o,p,q,r入队。

7、按照运算符优先数法，画出对下面算术表达式求值时，操作数栈和运算符栈的变化过程： 9-2*4+(8+1)/3。

8、设栈S＝（1，2，3，4，5，6，7），其中7为栈顶元素。写出调用algo后栈S的状态。 void algo(Stack *S) {int i=0;

Queue Q; Stack T;

InitQueue(Q); InitStack(T); while(!StackEmpty(S))

{if(i%2==0) Push(T,Pop(S)); else EnQueue(Q,Pop(S)); i++;

}

while(!QueueEmpty(Q)) Push(S,DeQueue(Q)); while(!StackEmpty(T)) Push(S,Pop(T)); } 9、试将下列递归过程改写为非递归过程 void digui(int *sum) {scanf(x);

if(x==0) sum=0;

else {digui(sum);sum+=x;} printf(sum);

10、写出下列中缀表达式的后缀形式： (1) A * B * C (2) (A + B)* C -D (3) A* B + C/(D-E) (4) (A + B) * D + E / (F + A * D) + C

11 设表达式的中缀表示为a * x - b / x↑2，试利用栈将它改为后缀表示ax * bx2↑/ -。写出转换过程中栈的变化。五、设计题

1、在栈顶指针为HS的链栈中，写出计算该链栈中结点个数的函数？ 2、求两个正整数m和n的最大公约数可用如下gcd(m,n)公式表示：

gcd(m,n)=m当n=0时，或gcd(n,m%n)当 n>0时（1）编写一个计算gcd(m,n)的递归过程（2）将上述过程转化为非递归过程

（3）画出计算gcd(20,6)的过程及栈的状态变化，给出计算结果。

3、已知Q是一个非空队列，S是一个空栈，使用C语言编写一个算法，仅用队列和栈的ADT函数和少

量工作变量，将队列Q中的所有元素逆置。栈的ADT函数有

void SetEmpty(stack s); //置空栈

void Push(stack s,ElemTye value); //新元素value进栈 ElemType Pop(stack s); //出栈，返回栈顶值 Boolean IsEmptyS(stack s); //判断栈空否

队列ADT的函数有：

void EnQueue(Queue q,ElemType value); //元素入队 ElemType DeQueue(Queue q); //出队列返回队头值 Boolean IsEmptyQ(Queue q); //判断队列是否为空

4、用单链表实现队列，如下图所示，并令front=rear=NULL表示队列为空，编写实现队列的如下五种运

算的函数。

Setnull:将队列置成空队列。 getfirst:返回队列的第一个元素。 enqueue:把元素插入队列的后端。 dequeue:删除队列的第一个元素。 empty:判定队列是否为空。

第四章串复习题

一、选择题

1、设串s1=?ABCDEFG?，s2=?PQRST?，函数Concat(x,y)返回x和y串的连接串，Substr(s,i,j)返回串s从序号I开始的j个字符组成的子串，length(s)返回串s的长度，则Concat(Substr(s1,2,length(s2)),Substr(s1,length(s2),2))的结果串是（）。

A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 2、空串和空格是相同的。A、正确 B、错误

3、若串S1=?ABCDEFG?，S2=?9898?，S3=?###?，S4=?012345?，则执行

replace(s1,Substr(s1,4,length(s3)),s3),Concat(s1,Substr(s4,index(s2,?8?),length(s2)))后，其结果为（）。

A、ABC###G0123 B、ABCD###2345 C、ABC###G2345 D、ABC###2345 E、ABC###G1234 F、ABCD###1234 G、ABC###01234

4、串是一种特殊的线性表，其特殊性体现在（）。

A、可以顺序存储 B、数据元素是一个字符 C、可以链接存储 D、数据元素可以是多个字符 5、设有两个串p和q，求q在p中首次出现的位置的运算称为（）。 A、连接 B、模式匹配 C、求子串 D、求串长

6、下面关于串的的叙述中，哪一个是不正确的？（）

A．串是字符的有限序列 B．空串是由空格构成的串

C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 7、串的长度是指（）

A．串中所含不同字母的个数 B．串中所含字符的个数

C．串中所含不同字符的个数 D．串中所含非空格字符的个数

二、判断题

1、子串定位函数的时间复杂度在最坏的情况下为O（n*m），因此子串定位函数没有实际利用价值。 2、设有两个串p和q，其中q是p的子串，把q在p中首次出现的位置作为子串q在p中的位置的算法

称为匹配。

3、 KMP算法的最大特点是指示主串的指针不需要回朔。

三、填空题

1、设s=?I_AM_A_TEACHER?，其长度为（）。 2、空串是（），其长度为（）。

3、设S1=?GOOD?，S2=?︼?，S3=?BYE!?，则S1、S2和S3连接后的结果是（）。 4、两个串相等的充分必要条件是（）。

23、线索二叉树是一种（）结构。

A、逻辑 B、逻辑和存储 C、物理 D、线性

24、如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的（）。 A、前序 B、中序 C、后序 D、层次序

25、设T是哈夫曼树，具有5个叶结点，树T的高度最高可以是（）。 A、1 B、2 C、3 D、4 E、5 F、6

26、由带权为8，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）。 A、23 B、37 C、46 D、43

27、树的后根遍历序列等同于该树对应的二叉树的（）。 A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 28、以下说法错误的是（）

A、树形结构的特点是一个结点可以有多个直接前趋 B、线性结构中的一个结点至多只有一个直接后继 C、二叉树与树是两种不同的数据结构

D、树(及一切树形结构)是一种“分支层次”结构 29、以下说法错误的是（）

A、二叉树可以是空集 B、二叉树的任一结点都有两棵子树

C、二叉树与树具有相同的树形结构 D、二叉树中任一结点的两棵子树有次序之分 30、以下说法错误的是（）

A、完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B、在三叉链表上，二叉树的求双亲运算很容易实现 C、在二叉链表上，求根，求左、右孩子等很容易实现 D、在二叉链表上，求双亲运算的时间性能很好 31、以下说法错误的是（）

A、一般在哈夫曼树中，权值越大的叶子离根结点越近 B、哈夫曼树中没有度数为1的分支结点

C、若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点

D、若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树

32、将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为（）

A 、10 B、 11 C、 41 D、 20

33、任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置（） A、肯定发生变化 B、有时发生变化 C、肯定不发生变化 D、无法确定 34、下列说法正确的是（）

A、树的先根遍历序列与其对应的二叉树的前序遍历序列相同 B、树的先根遍历序列与其对应的二叉树的后序遍历序列相同 C、树的后根遍历序列与其对应的二叉树的前序遍历序列相同 D、树的后根遍历序列与其对应的二叉树的后序遍历序列相同 35、下列说法中正确的是（）

A、任何一棵二叉树中至少有一个结点的度为2 B、任何一棵二叉树中每个结点的度都为2

C、任何一棵二叉树中的每个结点的度肯定等于2 D、任何一棵二叉树中的每个结点的度都可以小于2

36、一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用（）遍历方式就可以得到这棵二叉树所有结点的递减序

列。

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

37、对含有（）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。

A 、0 B、 1 C 、2 D、不存在这样的二叉树

38、在图6.2中的二叉树中，（）不是完全二叉树。

A、 B、 C、 D、

图6.2

39、树最适合用来表示（）

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

C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据 40、哈夫曼树的带权路径长度是（）

A、所有结点权值之和 B、所有叶结点带权路径长度之和 C、带权结点的值 D、除根以外所有结点权值之和 41、在线索二叉树上，线索是（）

A、两个标志域 B、指向结点前驱和后继的指针 C、数据域 D、指向左、右子树的指针 42、已给出如图6.3所示哈夫曼树，那么电文CDAA的编码是( )

A、110100 B、11011100 C、010110111 D、11111100

C D 图6.3

43、已给出的图6.3所示二叉树，A,B,C,D分别带权值为7，5，2，4则该树的带权路径长度为（ A、46 B、36 C、35 D、都不是 44、在线索化二叉树中，t所指结点没有左子树的充要条件是（）

A、t->lchild==NULL B、t->ltag==1 C、t->ltag==1&&t->lchild==NULL D、以上都不对 45、下列叙述中正确的是（）

A、二叉树是度为2的有序树 B、二叉树中结点只有一个孩子时无左右之分

C、二叉树中必有度为2的结点 D、二叉树中结点最多有两棵子树，并且有左右之分 46、下图6.4所示的几种结构中属于树型结构的是（）

A、 B、 C、 D、

图6.4

）

二、判断题

1、二叉树是树的特殊形式。

2、树和二叉树之间最主要的差别是：二叉树的结点的子树要区分为左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。

3、一棵有n个结点的d度树，若用多重链表表示，树中每个结点都是有d个链域，则在树的n*d个链域中，有n*(d-1)+1个是空链域，只有n-1个是非空的。

4、前序遍历树和前序遍历与该树对应的二叉树，其结果相同。 5、后序遍历树和中序遍历与该树对应的二叉树，其结果不同。 6、前序遍历森林和前序遍历与该森林对应的二叉树，其结果相同。 7、中序遍历森林和中序遍历与该森林对应的二叉树，其结果不同。

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

9、二叉树具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女。 10、在二叉树中，具有一个子女的父结点，在中序遍历中，它没有后继的子女结点。 11、中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。 12、在二叉树中插入结点，该二叉树便不在是二叉树。 13、用一维数组存储二叉树时，总是以前序遍历存储结点。

14、已知二叉树的前序遍历和后序遍历序列不能唯一地确定这棵树。 15、不使用递归，也可以实现二叉树的前序，中序，后序遍历。

16、在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。 17、中序遍历线索二叉树，不必使用栈。

18、对于后序线索二叉树要找到它的任一结点的后继有时是困难的。 19、有n个结点的不同的二叉树有n！棵。

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

三、填空题

1、在树型结构中，树根结点没有（）结点，其余每个结点有且只有（）个前驱结点；叶子结点没有（）结点，其余每个结点的后继结点可以（）。 2、假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为（），树的深度为（），终端结点的个数为（），单分支结点的个数为（），双分支结点的个数为（），三分支结点的个数为（），C的双亲结点为（），其孩子结点为（）。

3、设树T中除叶结点外，任意结点的度数都是3，则T的第I层结点的个数为（）。 4、在具有n(n>=1)个结点的k叉树中，有（）个空指针。 5、一棵含有n个结点的k叉树，可能达到的最大深度为（），最小深度为（）。 6、一棵深度为k的满二叉树的结点总数为（），一棵深度为k的完全二叉树的结点总数的最小值为（），从左到右次序给结点编号（从1开始）则编号最小的叶子结点的编号是（），最大值为（）。

7、设根结点的层次数为0，定义树的高度为树中层次最大的结点的层次加1，则高度为k的二叉树具有的结点数目，最少为（），最多为（）。 8、n个结点的完全二叉树，若按从上到下、从左到右给结点顺序编号，则编号最大的非叶结点编号为（），编号最小的叶结点编号为（）。

9、在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=（）。

10、一棵二叉树的第I层最多有（）个结点，一棵有n个结点的满二叉树共有（）个叶子结点和（）个非终端结点。

11、一棵完全二叉树的第5层有5个结点，则共有（）个结点，其中度为1的结点有（）个，度为0的结点有（）个。

12、具有n个结点的完全二叉树，其叶子结点的个数为（）。

13、对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为（）个，其中（）个用于链接孩子结点，（）个空闲。

14、对于一棵具有n个结点的二叉树，当它为一棵（）二叉树时具有最小高度，高度为（），当它为一棵单支树时具有（）高度，高度为（）。

15、树所对应的二叉树其根结点的（）子树一定为空。

16、从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是（）。 17、结点最少的树为（），结点最少的二叉树为（）。

18、一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前驱为（），后序遍历中结点B的直接后继为（）。

19、某二叉树的中序遍历序列为ABCDEFG，后序序列为BDCAFGE，则该二叉树结点的前序序列为（），该二叉树对应的森林包括（）棵树。

20、在一棵二叉树上按（）遍历得到的结点序列为有序序列。 21、由n个权值构成的哈夫曼树共有（）个结点。

22、由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为（）。

23、设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有（）个。

补充填空题：

1. 树（及一切树形结构）是一种________结构。在树上，________结点没有直接前趋。对树上任一结点X

来说，X是它的任一子树的根结点惟一的________。

2. 一棵树上的任何结点（不包括根本身）称为根的________。若B是A的子孙，则称A是B的________。 3. 二叉树第i(i≥1)层上至多有______个结点。 4. 深度为k(k≥1)的二叉树至多有______个结点。

5. 对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。 6. 满二叉树上各层的结点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树，但反之不然。 7. 具有n个结点的完全二叉树的深度为______。

8. 在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是。 9. 如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1≤i≤n)的结点X有：

（1）若i=1，则结点X是______；若i>1，则X的双亲PARENT(X)的编号为______。

（2）若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。（3）若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。 10. 二叉树通常有______存储结构和______存储结构两类存储结构。

11. 每个二叉链表还必须有一个指向______结点的指针，该指针具有标识二叉链表的作用。 12. 对二叉链表的访问只能从______指针开始。

13. 具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其

余的________个指针域为NULL。

14. 已知二叉树中叶子数为40，仅有一个孩子的结点数为20，则总结点数为。 15. 二叉树有不同的链式存储结构，其中最常用的是________与________。

16. 可通过在非完全二叉树的“残缺”位置上增设 ________ 将其转化为完全二叉树。 17. 具有100个结点的完全二叉树的深度是。 18. 深度为90的满二叉树上，第10层有个结点。

19. 在________遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。

20. 具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编号（根结点为1号），则编号最大的

分支结点序号是________，编号最小的分支结点序号是________，编号最大的叶子结点序号是________，编号最小的叶子结点序号是________。

21. 若一棵二叉树的叶子数为n，则该二叉树中，左、右子树皆非空的结点个数为________。

22. 任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为________个。 23. 设有30个值，用它们构造一棵哈夫曼树，则该哈夫曼树中共有个结点。

24. 现有按中序遍历二叉树的结果为ABC，问有________种不同形态的二叉树可以得到这一遍历结果。 25. 以数据集{4，5，6，7，10}为叶结点的权值所构造的哈夫曼树的带权路径长度为________。

26. 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有________

个叶子结点。 27. 设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶子结点的个数是________。 28. 如果结点a有三个兄弟，而且b是a的双亲，则b的度是______。

29. 一棵树的形状如图6.5所示，它的根结点是________，叶子结点是________，结点H的度是________，

这棵树的度是________，这棵树的深度是________，结点F的儿子结点是________，结点G的父结点是________。

B C D

E G H I F

J K L M N

O P Q R 图6.5

30. 设结点x有左孩子结点y，右孩子结点z，用三种基本遍历方法的到的遍历序列中x______是y的前驱，

x______是z的后继，y______是z的前驱。（填“一定”，“不”，“不一定”）

31. 在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个 ,且存在一条从根到

该结点的。

32. 含有2n个结点的二叉树高度至少是，至多是（仅含根结点的二叉树高度为1）。 33. 设高度为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为，

至多为。

四、附加判断题

1、树中任意结点的子树不必是有序的。（） 2、树可以看成特殊的的无向图。（） 3、可以使用双链表表示树形结构。（） 4、顺序存储方式只能用于存储线性结构。（） 5、完全二叉树的某结点若无左孩子，则必为叶结点。（） 6、如果一个二叉树的结点，或者没有子树，或者恰有两棵非空子树，则此二叉树称为完全二叉树。（） 7、包含两个结点的所有二叉树都是相同的。（）

8、二叉树的前序遍历序列中，任意一个结点均处在其子树结点的前面。（） 9、二叉树的前序和后序遍历能唯一确定一棵二叉树。（）

10、二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索。（） 11、中序线索二叉树中，右线索若不为空，则一定指向其父结点。（）五、简答题

1、二叉树与树有何区别？一棵度为2的树与二叉树有何区别？

2、一棵树有度为1的结点n1个，度为2的结点n2个，…，度为m的结点nm个，问它有多少叶结点？

有多少非终端结点？

3、一棵有n个结点的树中所有非叶子结点的度均为k，求该树中有多少叶子结点？ 4、含有n个结点和n0个叶子结点的完全k叉树的高度各为多少？ 5、将算术表达式((a+b)+c*(d+e)+f)*(g+h)转化为二叉树。

6、对于二叉树T的两个结点n1和n2，应选择前序、中序和后序的哪两个序列来判定结点n1必定是结

点n2的祖先，并给出判断方法。

7、具有7个结点的互不相似的二叉树共有多少棵？

8、具有3个结点的树和二叉树，它们的所有不同形态有哪些？ 9、试找出分别满足下列条件的所有二叉树。

（1）前序和中序遍历序列相同。（2）中序和后序遍历序列相同。（3）前序和后序遍历序列相同。 10、现有按中序遍历二叉树的结果为ABC，问有多少种不同形态的二叉树可以得到这一遍历结果？

画出这些树。 11、已知一棵二叉树的中序遍历序列为CDBAEGF，前序遍历序列为ABCDEFG，问能否唯一确定

一棵树，请画出。若给定前序和后序遍历序列，能否唯一确定，请说明理由。 12、假定先根次序遍历某棵树的结点次序为SACEFBDBHIJK，后根次序遍历该树的结点次序为

CFEABHGIKJDS，画出这棵树。 13、什么是线索二叉树？简述中序线索二叉树中查找指定结点的直接前驱和直接后继的基本思想。 14、有7个带权结点，其权值分别为4，7，8，2，5，16，30，试以它们为叶子结点构造一棵哈夫

曼树（要求按每个结点的左子树根结点的权值小于或等于右子树根结点的权值的次序构造），并计算其带权路径长度。

15、分别画出含3个结点的树与二叉树的所有不同形态。

16、设在树中，结点x是结点y的双亲时，用(x,y)来表示边。已知一棵树边的集合为：{(i,j),(i,k),(b,e),(e,i),(b,d),(a,b),(c,g),(c,f),(c,h),(a,c)}，用树形表示法画出此树，并回答下列问题：

（1）哪个是根结点？（2）哪些是叶子结点？（3）哪个是g 的双亲？（4）哪些是g的祖先？（5）哪些是e的子孙？（6）哪些是f的兄弟？（7）结点b和j的层次各是多少？（8）树的深度是多少？（9）树的度数是多少？

17、任意一个有n(n>0)个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有m-1个度为2，其余度为1。

18、分别画出图6.6所示二叉树的二叉链表、三叉链表和顺序存储结构。 A B D

C E F 图6.6

19、分别写出图6.7所示二叉树的前序、中序和后序序列。

图6.7

A B C D E 20、试分别画出图6.8所示树的孩子链表、孩子兄弟链表和静态双亲链表。

C B D F G H I E J

L K 图6.8

21、将图6.9所示的森林转换成二叉树。 A G J

I K B C D H

F L M N E

图6.9

22、分别画出图6.10所示各二叉树对应的森林。并写出森林的前序和中序遍历序列。 A

B C

D E F

G H I J

图6.10

23、设某密码电文由8个字母组成，每个字母在电文中的出现频率分别是7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈夫曼编码。

24、将代数式：y=3*(x+a)-a/x2 描述成表达式树，并写出前缀式和后缀式来。

25、下述编码{00，01，10，11}，{0，1，00，11，}，{0，10，110，111}哪一组不是前缀码？ 26、将图6.11所示的森林转化成一棵二叉树，并分别按以下要求画出线索二叉树。（1）前序前趋线索化；（2）后序后继线索化；（3）中序全线索化。 A E F

G H I

C D 图6.11

第七章：图练习题

一、选择题

1、一个有n个顶点的无向图最多有（）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n

2、具有6个顶点的无向图至少有（）条边才能保证是一个连通图。 A、5 B、6 C、7 D、8

3、具有n个顶点且每一对不同的顶点之间都有一条边的图被称为（）。 A、线性图 B、无向完全图 C、无向图 D、简单图 4、具有4个顶点的无向完全图有（）条边。 A、6 B、12 C、16 D、20

5、G是一个非连通无向图，共有28条边，则该图至少有（）个顶点 A、6 B、7 C、8 D、9

6、存储稀疏图的数据结构常用的是（）。

A、邻接矩阵 B、三元组 C、邻接表 D、十字链表

7、对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（）。 A、n B、(n-1)2 C、(n+1)2 D、n2

8、设连通图G的顶点数为n，则G的生成树的边数为（）。 A、n-1 B、n C、2n D、2n-1

9、对于一个具有N个顶点和E条边的无向图，若采用邻接表表示，则表头向量的大小为（邻接表中的结点总数是（（2））

（1）A、N B、N+1 C、N-1 D、N+E （2）A、E/2 D、E C、2E D、N+E

10、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为（邻接表的结点总数为（）。

A、n B、n+1 C、n-1 D、2n E、e/2 F、e G、2e H、n+e 11、在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（）。

1））；所有），所有顶点（

A、顶点v的度 B、顶点v的出度 C、顶点v 的入度 D、依附于顶点v的边数

12、已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（）和（）

（1） A、abecdf B、acfebd C、acebfd D、acfdeb （2） A、abcedf B、abcefd C、abedfc D、acfdeb

13、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（）和（）。 A、中序遍历 B、先序遍历 C、后序遍历 D、层次遍历

14、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（）和（）。

A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v2,v3,v5,v4 D、v1,v4,v3,v5,v2

15、已知有8个顶点为A，B，C，D，E，F，G，H的无向图，其邻接矩阵存储结构如下，由此结构，从A点开始深度遍历，得到的顶点序列为（）。 A B C D E F G H A 0 1 0 1 0 0 0 0 B 1 0 1 0 1 1 1 0 C 0 1 0 1 0 0 0 0 D 1 0 1 0 0 0 1 0 E 0 1 0 0 0 0 0 1 F 0 1 0 0 0 0 1 1 G 0 1 0 1 0 1 0 1 H 0 0 0 0 1 1 1 0 A、ABCDGHFE B、ABCDGFHE C、ABGHFECD D、ABFHEGDC E、ABEHFGDC F、ABEHGFCD

16、已知一个图如下，在该图的最小生成树中各边上权值之和为（），在该图的最小生成树中，从v1到v6的路径为（）。

A、31 B、38 C、36 D、43 E、v1,v3,v6 F、v1,v4,v6 G、v1,v5,v4,v6 H、v1,v4,v3,v6

17、关键路径是事件结点网络中的（）。

A、从源点到汇点的最长路径 B、从源点到汇点的最短路径 C、最长的回路 D、最短的回路 18、正确的AOE网必须是（），AOE网中某边权值应当是（），权值为0的边表示（）。（1）A、完全图 B、哈密尔顿图 C、无环图 D、强连通图

（2）A、实数 B、正整数 C、正数 D、非负数（3）A、为决策而增加的活动 B、为计算方便而增加的活动 C、表示活动间的时间顺序关系 D、该活动为关键活动

19、已知一个图如下，则由该图得到的一种拓扑序列为（）。

A、v1,v4,v6,v2,v5,v3 B、v1,v2,v3,v4,v5,v6 C、v1,v4,v2,v3,v6,v5 D、v1,v2,v4,v6,v3,v5

20、下面结论中正确的是（）

A、在无向图中，边的条数是顶点度数之和。 B、在图结构中，顶点可以没有任何前驱和后继。 C、在n个顶点的无向图中，若边数大于n-1，则该图必定是连通图 D、图的邻接矩阵必定是对称矩阵。 21、下面结论中正确的是（）

A、若有向图的邻接矩阵中对角线以下元素均为0，则该图的拓扑排序序列必定存在。 B、网络的最小代价生成树是唯一的。 C、在拓扑排序序列中，任意两个相继顶点vi和vj都存在从vi到vj的路径。 D、在有向图中，从一个顶点到另一个顶点的最短路径是唯一的。 22、下面结论不正确的是（）。

A、无向图的连通分量是该图的极大连通子图。 B、有向图用邻接矩阵表示容易实现求顶点度数的操作。 C、无向图用邻接矩阵表示，图中的边数等于邻接矩阵元素之和的一半。 D、有向图的邻接矩阵必定不是对称矩阵。

23、下面结论中正确的是（）。

A、按深度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。 B、一个图按深度优先搜索遍历的结果是唯一的。 C、若有向图G中包含一个环，则G的顶点间不存在拓扑排序。 D、图的拓扑排序序列是唯一的。

24、下面结论中不正确的是（）。

A、按广度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。 B、一个图按广度优先搜索遍历的结果是唯一的。 C、无向图的邻接表表示法中，表中结点的数目是图中边的条数的2倍。

D、图的多重邻接表表示法中，表中结点数目是图中边的条数。

25、在一个图中，所有顶点的度数之和等于所有边数的（）倍。 A、1/2 B、1 C、2 D、4

26、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A、1/2 B、1 C、2 D、4

27、判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（） A、求关键路径的方法 B、求最短路径的DIJKSTRA方法 C、广度优先遍历算法 D、深度优先遍历算法 28、任何一个带权的无向连通图的最小生成树（）

A、只有一棵 B、有一棵或多棵 C、一定有多棵 D、可能不存在 29、以下说法正确的是（）

A、连通图的生成树，是该连通图的一个极小连通子图。

B、无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。 C、任何一个有向图，其全部顶点可以排成一个拓扑序列。 D、有回路的图不能进行拓扑排序。 30、以下说法错误的是（）

A、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。

B、邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。 C、存储无向图的邻接矩阵是对称的，因此也可以只要存储邻接矩阵的下（或上）三角部分。

D、用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am

的第 i行第j列的元素是否为0即可。 31、以下说法正确的是（）

A、连通分量是无向图中的极小连通子图。 B、强连通分量是有向图中的极大强连通子图。

C、在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。

D、对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。二、判断题

1、用邻接矩阵法存储一个图时，所占用的存储空间大小仅与图中结点个数有关。

2、对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。 3、任何有向网拓扑排序的结果是唯一的。 4、有回路的图不能进行拓扑排序。 5、存储有向图的邻接矩阵是对称的。

6、一个有向图G中若有弧、和, 则在图G的拓扑序列中，顶点vi,vj和vk的相对位置为vi,vj,vk。

7、在AOE网中一定有一条关键路径。

8、含有10个顶点的无向连通图其生成树含有9条边。 9、十字链表是图的一种顺序表示法。

三、填空题

1、对具有n个顶点的图，其生成树有且仅有__________条边，即生成树是图的边数__________的连通图。 2、一个无向图有n个顶点和e条边，则所有顶点的度数之和为（），其邻接矩阵是一个关于__________对称的矩阵。

3、在图形结构中，每个结点的前驱结点和后继结点可以有（）。

4、若无向图G的顶点度数的最小值大于或等于（）时，G至少有一条回路。

5、设无向图G的顶点数为n，图G最少有（）边，最多有（）条边。若G为有向图，有n个顶点，则图G最少有（）条边，最多有（）条边。具有n个顶点的无向完全图，边的总数为（）条，而有n个顶点的有向完全图，边的总数为（）条。

6、在无权图G的邻接矩阵A中，若(vi,vj)或属于G的边/弧的集合，则对应元素A[i][j]等于（），否则等于（）。

7、在无向图G的邻接矩阵A中，若A[i][j]=1，则A[j][i]等于（）。 8、已知一个图的邻接矩阵表示，计算第I个顶点的入度方法为（） 9、在一个图G的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的（），而对于无向图而言等于该顶点的（）。

10、已知图G的邻接表如图7.4所示，其从顶点V1出发的深度优先搜索序列为__________，其从顶点V1出发的广度优先搜索序列为__________。 4 1 3 ∧ 0 V1 1 V2 4 ∧ 2 2 V3 5 ∧ 3 V4 ∧ 4 V5 5 3 2 ∧ 11、n个顶点的弱连通有向图G最多有（）条弧，最少有（）条弧。 5 V6 ∧ 12、在n个顶点e条边的连通图中，连通分量个数为（）。

图7.4

13、任何（）的有向图，其所有结点都可以排在一个拓扑序列中，拓扑排序的方法是先从图中选一个（）为0的结点且输出，然后从图中删除该结点及其（），反复执行，直到所有结点都输出为止。 14、一个连通图的（）是一个极小连通子图。

15、在AOE网中，从源点到汇点各活动时间总和最长的路径为（）。

16、在有向图的邻接矩阵上，由第i行可得到第__________个结点的出度，而由第j列可得到第__________个结点的入度。

17、对无向图，设有n个结点，e条边，则其邻接表表示中需要__________个表结点，对有向图，设有n个顶点，e条弧，则其邻接表表示需要__________个表结点。

18、在无权图G的邻接矩阵A中，若 (Vi,Vj)或属于图G的边集,则对应元素A[i,j]等于__________，否则等于__________。

19、已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是__________。

删除所有从第i个结点出发的边的方法是__________。

20、设无向图G中顶点数为n，则图G最少有__________条边，最多有条边。若G为有向图，有n个顶点，则图至少有__________条边，最多有__________条边。

21、某作业工程表示成网络图，如图7.5所示。事件5的最早完成时间是_______。事件4的最迟开始时间是________。事件5的迟缓时间是________。关键路径是__________。 e4=4 4 1 e8=12 e1=5 e9=6

2 0 9 e5=10 5 e10=10 e2=9

e3=14 e6=3 3 6 e12=5 e11=5 8 e14=8

22、设x,y∈V，若∈E,则表示有向图G中从x到y的一条________，x称为________点，y称为________点。若（x,y）∈E，则在无向图G中x和y间有一条________。

23、在无向图中，如果从顶点v到顶点v?有路径，则称v和v?是_______的。如果对于图中的任意两个顶点vi,vj∈V，且vi和vj都是连通的，则称G为________。 24、连通分量是无向图中的________连通子图。

25、对无向图，若它有n个顶点e条边，则其邻接表中需要________个结点。其中，________个结点构成头结点，________个结点构成边结点表。

26、对有向图，若它有n顶点e条边，则其邻接表中需要________个结点。其中，________个结点构成头结点，________个结点构成边结点表。 27、在邻接表上，无向图中顶点vi的度恰为________________。对有向图，顶点vi的出度是________________。为了求入度，必须遍历整个邻接表，在所有单链表中，其邻接点域的值为________的结点的个数是顶点vi的入度。

28、遍历图的基本方法有________优先搜索和________优先搜索两种。

四、简答题

1、对于一个具有n个顶点的连通无向图，如果它有且只有一个简单回路，此图有几条边？一个具有n

个顶点的弱连通图至少有几条边？

2、已知某图的邻接表，如何建立该图的邻接矩阵？

3、有4个顶点A，B，C，D的无向连通图，按广度和深度搜索遍历结果都为ABCD，画出所有可能的

结构图？

4、简述无向图和有向图有哪几种存储结构，并说明各种结构在图的不同操作中有什么优越性？ 5、什么是AOE网的关键路径？

6、给出下图邻接矩阵、邻接表和邻接多重表存储结构。从顶点1出发进行广度个深度优先搜索遍历。

7、对下图，请给出（1）对应的邻接矩阵，并给出v1,v2,v3三个顶点的出度和入度；（2）邻接表和逆邻

接表表示；（3）强连通分量。

8、试列出图中全部可能的拓扑排序序列。

五、补充应用题

1. 给出无向图如图7.6所示的G1的邻接矩阵和邻接表。

V1 V2 V1 V2 V1 V2

V4 V3 V4 V5 V3 V4 V5 V5

G2 G3

V3 2. 分别给出图7.6所示的G2的邻接矩阵、邻接表和逆邻接表。

G1 7.6 所示的 G 3 从 v 5 出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。图7.6 3. 分别给出图

4. 求出图7.7的连通分量。

V1 V2 V6 V3 V8 V7 V V5 4 图7.7 5. 设有一无向图G=(V,E),其中

V={1,2,3,4,5,6},E={(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)}。 (1)按上述顺序输入后，画出其相应的邻接表；

(2)在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。 6. 已知连通网的邻接矩阵如图7.8所示，顶点集合为{v1,v2,v3,v4,v5}，试画出它所表示的从顶点v1开始

???112510??1 2

利用Prim算法得到的最小生成树。

7. 拓扑排序的结果不是唯一的，对图7.9进行拓扑排序，写出全部不同的拓扑排序序列。 8. 已知图G的邻接表如图7.10所示，顶点V1为出发点，完成要求：（1）深度优先搜索的顶点序列；（2）广度优先搜索的顶点序列；

（3）由深度优先搜索得到的一棵生成树； 1 （4）由广度优先搜索得到的一棵生成树。 1 4 2 3 2 V1 1 3 4 ∧ 5 4 V2 0 2 5 ∧ 3 8 4 V3 1 4 5 ∧ V4 0 4 2 3 V5 0 2 3 5 ∧ 5 6 6 V6 1 2 4 ∧ 4 5

7 图7.10

图7.11

9. 图7.11所示为一无向连通网络，要求根据Prim算法和Kruskal构造出它的最小生成树。

10. 在下图所示的有向图7.12中： V1 V2 V3 V4 图 7.12 （1）该图是强连通图吗？（2）请给出每个顶点的度、入度和出度。（3）给出其邻接矩阵、邻接表及逆邻接表。

11. DFS和BFS遍历采用什么样的数据结构来暂存顶点？当要求连通图的生成树的高度最小，应采用何种

遍历？画出以顶点v1为初始源点遍历图7.13所示的有向图所得到的DFS和BFS生成森林。 V 3 V1 V4 V2 V5 V8 V6 V7

图7.13

12. 对图7.14所示的有向网，试利用Dijkstra算法求从源点1到其他各顶点的最短路径。

10 4 6

5 15 4 30 10 4 15 10 图7.14

2 20 2 1 3

13. 试写出图7.15所示有向图的所有拓扑排序，并指出应用教材中的算法求得的是哪个序列，设邻接表的

边表结点中的邻接点序号是递增的。 V0 V 1

V2 V3

V5 V4 V6 图7.15

14. 已知如图7.16所示的AOE网。求：

（1）每项活动的最早开始时间和最晚开始时间；（2）完成此工程最少需要多少单位时间；（3）关键活动与关键路径。

e3=3 5 2 e8=1

e1=3 e4=2

4 6 1 e7=2 e5=4

e2=2 e6=3 3

图7.16

15. 已知带权连通图，G（V,E）的邻接表如图7.17所示。试画出该图，并分别从顶点1开始的深度优先和

广度优先遍历之，给出遍历中结点的序列，最后画出该图的一棵最小生成树。其中表结点的三个域为

顶点号边上的权值指针

2 8 2 1 8 3 1 10 4 1 11 5 2 13 图 7.17 1 3 3 2 3 10 3 3 4 4 ∧ 11 5 ∧ 13 4 ∧ 4 5 ∧ 7 4 ∧ 7 ?0?116. 已知某图G的邻接矩阵为 ??0??1101001011?0??，顶点集合为{v1,v2,v3,v4} 1??0?（1）由邻接矩阵画出相应的图G；

（2）如果要使用此图成为完全图还要增加哪几条边。

17. 试利用弗洛伊德算法，写出如图7.18所示相应的带权邻接矩阵的变化。

3 8 2 3 9 5 1 1 图 7.18

4 10 2

18. 对于图7.19所示的AOE网络，计算各事件（顶点）的ve(vi)和vl(vj)和活动（边）的e(ai)和l(ai)函数值；

列出各条关键路径和关键活动。 a7=6 A

a1=1 a2=6 B D a8=2 a 9=7 E a11 =8 a20=10 a 17 =4 a13=11 W C a 16 =8 a 3=3 a4=4 F V a5=3 G a6=1 I a10=6 a=12 a 18 =4 22H J a14 =10 a19=9 a15=6 a=9 21K a12=5 图7.19

第8章

一、应用题

动态存储管理

1、假设利用边界标识法首次适配策略分配，已知在某个时刻的可利用空间表的状态如图8.1所示：

pav 802 213 462 604 0 56 0 117 0 122 0 53 0 0 0 0

图8.1

（1）画出当文件系统回收一个起始地址为559、大小为45的空闲块之后的链表状态；

（2）画出系统继而在接受存储块大小为100的请求之后，又回收一块起始地址为515、大小为44的空闲块

之后的链表状态。

注意：存储块头部中大小域的值和申请分配的存储量均包括头和尾的存储空间。

2、组织成循环链表的可利用空间表可附加何条件时，首次适配策略转变为最佳适配策略？

3、设两个大小分别为100和200的空闲块依次顺序链接成可利用空间表。设分配一块时，该块的剩余部分在可利用空间表中保持原链接状态，试分别给出满足下列条件的申请序列：（1）最佳适配策略能够满足全部申请而首次适配策略不能；（2）首次适配策略能够满足全部申请而最佳适配策略不能。 4、考虑边界标志法的两种策略（最佳适配和首次适配）：（1）数据结构的主要区别是什么？（2）分配算法的主要区别是什么？（3）回收算法的主要区别是什么？

5、二进制地址011011110000，大小为（4）2的伙伴的二进制地址是什么？若块的大小为（16）10时又如何？

6、已知一个大小为512字的内存，假设先后由6个用户提出大小分别为：23，45，52，100，11和9的分配请求，此后大小为45，52和11的占用块顺序被释放。假设以伙伴系统实现动态存储管理，（1）画出可利用空间表的初始状态；

（2）画出6个用户进入之后的链表状态以及每个用户所得的存储块的起始地址；（3）画出在回收三个用户释放的存储块之后的链表状态。

7、试求一个满足以下条件的空间申请序列a1,a2,…,an：从可用空间为25的伙伴管理系统的初始状态开始，a1,a2,…,an-1均能满足，而an不能满足，并使

?ai?1ni最小。

第九章：查找复习题

一、

选择题

1、顺序查找一个共有n个元素的线性表，其时间复杂度为（），折半查找一个具有n个元素的有序表，其时间复杂度为（）。

A、O(n) B、O(log2n) C、O(n2) D、O(nlog2n)

2、在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（）。 A、n B、[log2n] C、[log2(n+1)] D、「log2(n+1)

3、采用顺序查找方式查找长度为n的线性表时，平均查找长度为（） A、n B、n/2 C、(n+1)/2 D、(n-1)/2

4、采用折半查找方法检索长度为n的有序表，检索每个元素的平均比较次数（）对应判定树的高度（设高度大于等于2）。

A、小于 B、大于 C、等于 D、大于等于

5、已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，查找成功的比较次数为（）。

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

6、对线性表进行折半查找时，要求线性表必须（）。

A、以顺序方式存储 B、以链接方式存储 C、以顺序方式存储，且结点按关键字有序排序 D、以链接方式存储，且结点按关键字有序排序

7、顺序查找法适合于存储结构为（）的查找表。

A、散列存储 B、顺序或链接存储 C、压缩存储 D、索引存储

8、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（）个结点最佳。 A、10 B、25 C、6 D、625

9、从键盘依次输入关键字的值：t,u,r,b,o,p,a,s,c,l，建立二叉排序树，则其先序遍历序列为（），中序遍历序列为（）。

A、abcloprstu B、alcpobsrut C、trbaoclpsu D、trubsaocpl 10、折半查找和二叉排序树的时间性能（）。 A、相同 B、不相同

11、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。 A、2k-1-1 B、2k-1 C、2k-1+1 D、2k-1

12、利用逐点插入法建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排序树以后，查找元素35要进行（）元素间的比较。

A、4次 B、5次 C、7次 D、10次

13、设Hash地址空间为0到m-1，哈希函数为h(k)=k%p，为了减少发生冲突的可能性，一般取p为（）。 A、小于m的最大奇数 B、小于m的最大素数 C、小于m的最大偶数D、小于m的最大合数。 14、长度为10的按关键字有序的查找表采用顺序组织方式。若采用折半查找方法，则在等概率情况下，查找失败时的ASL值是（）

A、24/10 B、 24/11 C、39/10 D、39/11

15、在表长为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为（）

A、n+1 B、1 C、n D、n-1

16、设哈希函数为H(key)=key%7,一组关键字为(37，21，9，20，30，19和46)，哈希表T的地址空间为0..6,用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为（） A、 0 1 2 3 4 5 6

21 20 21 46 21 19

37 37 9 9 9 37 46 30 30 30 19 46 19 20 20 B、 0 1 2 3 4 5 6 C、 0 1 2 3 4 5 6

D、 0 1 2 3 4 5 6 20 37 30 21 46 19 9 17、设有一个用线性探测法解决冲突得到的哈希表：

T: 0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14 哈希函数为H(key)=key,若要查找元素14，探测的次数是（） A、 3 B、 6 C、7 D、9 18、在哈希函数H(key)=key%m 中，一般来讲，m应取（）

A、奇数 B、偶数 C、素数 D、充分大的数 19、分块查找的时间性能（）

A、低于二分查找 B、高于顺序查找而低于二分查找 C、高于顺序查找 D、低于顺序查找而高于二分查找 20、以下说法错误的是（）

A、哈希法存储的基本思想是由关键字的值决定数据的存储地址 B、哈希表的结点中只包含数据元素自身的信息，不包含任何指针 C、装填因子是哈希法的一个重要参数，它反映哈希表的装填程度

D、哈希表的查找效率主要取决于哈希表造表时选取的散列函数和处理冲突的方法 21、以下说法正确的是（）