数据结构课后练习题汇编

数据结构课后练习题

第一章 绪论

一、选择题

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、插入操作 B、结点移动 C、算术表达式 D、删除操作 20、对于顺序表的优缺点，以下说法错误的是（ ）

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、 在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。 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、 若以链表作为栈的存储结构，则进栈需要判断栈是否满。

a2 a3 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、串是一种特殊的线性表，其特殊性体现在（ D ）。

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、两个串相等的充分必要条件是（ 两个串的长度相等且对应位置字符相同 ）。 5、串的两种最基本的存储方式是（ 顺序存储方式和链接存储方式 ）。 6、空格串是_________，其长度等于_________。

7、设有两个串q和p，求q在p中首次出现的算法叫_________。 8、串的连接运算不满足_________，满足_________。交换律、结合律

四、 简答题

1、 已知下列字符串（假设采用定长存储结构）

a=‘this‘,b=‘ ?, c=‘good‘, d=‘ne‘, f=‘a sample‘,g=‘is‘

顺序执行以下操作后，S、T、U、V、Length(s)、Index(v,g)、Index(u,g)各是什么？ S=Concat(a,concat(Substr(f,2,7),Concat(b,Substr(a,3,2)))) T=Replace(f,Substr(f,3,6),c) U=Concat(Substr(c,3,1),d)

V=Concat(S,Concat(b,Concat(T,Concat(b,U)))) 2、 执行以下函数会产生怎样的输出结果？

Void demonstrate()

{Strassign(s,‘this is a book‘);

Replace(s,Substring(s,3,7),‘ese are‘); Strassign(t,Concat(s,‘s‘)); Strassign(u,‘xyxyxyxyxyxy‘); Strassign(v,Substring(u,6,3)); Strassign(w,‘w‘);

Printf(?t=‘,t,‘v=‘,v,‘u=‘,Replace(u,v,w))}

3、 设s=‘I am a student‘，t=‘good‘，q=‘worker‘。求strlength(s)，strlength(t)，substr(s,8,7)，substr(t,2,1)，

index(s,‘a‘)，index(s,t)，replace(s,‘student‘,q)，concat(substr(s,6,2),concat(t,substr(s,7,8)))。 4、 已知s=‘(xyz)+*‘，t=‘(x+z)*y‘，利用连接、求子串和置换等基本操作，将s转化为t。

4.

s1=substr(s,1,5) //s1=‘(xyz)‘ s2=substr(s,3,1) //s2=‘y‘ s3=substr(s,6,1) //s3=‘+‘ s4=substr(s,7,1) //s4=‘*‘

replace(s1,3,1,s3) //s1=‘(x+y)‘ s=s1||s4||s2

五、 算法设计题

1、 串s和t采用堆存储，设计一个函数，求第一个在s而不在t中的字符的序号。 2、 采用堆存储串s，设计函数删除s中第I个字符开始的j个字符。 3、 若x和y是采用堆存储的串，设计一个比较两个串是否相等的函数。

一、int search(Hstring s,Hstring t)

{int I=0,flag=1;

while(I

{if(s.ch[i]!=t.ch[i])flag=0;I++} if(flag) return –1; else return I-1;

} 二、int delij(Hstring &s,int I,int j)

{int k;

if(I<0||j<0) return 0

if(I+j>s.length)j=s.length-I;

for(k=I+j;k

{int I=0,flag=1;

if(x.length!=y.length)return 0; else

{while(I

{if(x.ch[i]!=y.ch[i])flag=0; I++;}

Return flag; } }

第五章复习题

一、 选择题

1、在以下 讲述中，正确的是（ ）。

A、线性表的现行存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作方式是先进先出 D、队列的操作方式是先进后出

2、若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（ ）。

A、正确 B、错误

3、二维数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为（ ）。 A、SA+141 B、SA+180 C、SA+222 D、SA+225

4、数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（ ）。 A、80 B、100 C、240 D、270

5、常对数组进行的两种基本操作是（ ）。

A、建立与删除 B、索引和修改 C、查找和修改 D、查找和索引 6、将一个A[15][15]的下三角矩阵（第一个元素为A[1][1]），按行优先存入一维数组B[120]中，A中元素A[6][5]在B数组中的位置K为（ ）。

A、19 B、26 C、21 D、15

7、若广义表A满足Head(A)=Tail(A)，则A为（ ）。 A、（） B、（（）） C、（（），（）） D、（（），（），（）） 8、广义表（（a）,a）的表头是（ ），表尾是（ ）。 A、a B、b C、(a) D、((a)) 9、广义表（（a,b）,c,d）的表头是（ ），表尾是（ ）。 A、a B、b C、(a,b) D、(c,d) 10、广义表（（a））的表头是（ ），表尾是（ ）。 A、a B、(a) C、() D、((a)) 11、广义表（a,b,c,d）的表头是（ ），表尾是（ ）。 A、a B、(a) C、(a,b) D、(b,c,d) 12、广义表（（a,b,c,d））的表头是（ ），表尾是（ ）。 A、a B、() C、(a,b,c,d) D、((a,b,c,d)) 13、下面结论正确的是（ ）。

A、一个广义表的表头肯定不是一个广义表 B、一个广义表的表尾肯定是一个广义表

C、广义表L=（（），（A，B））的表头为空表 D、广义表中原子个数即为广义表的长度 14、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=( ) A、(G) B、(D) C、C D、 D

15、已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出原子项t的操作是（ ）。

A、Head(Head(Tail(Tail(L)))) B、Tail(Head(Head(Tail(L)))) C、Head(Tail(Head(Tail(L)))) D、Head(Tail(Head(Tail(Tail(L)))))

16、设A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))=( ) A. (g) B.(d) C.c D.d

17、对矩阵压缩存储是为了（ ）

A、方便运算 B、节省空间 C、方便存储 D、提高运算速度 18、稀疏矩阵一般的压缩存储方法有两种，即（ ）

A、二元数组和三元数组 B、三元组和散列 C、三元组和十字链表 D、散列和十字链表

二、 判断题

1． 数组是同类型值的集合。x

2． 数组的存储结构是一组连续的内存单元。v

3． 数组是一种复杂的数据结构，数组元素之间的关系，即不是线性的也不是树形的。

4． 插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使用。 5． 使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。

6． 广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。

7． 线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，则广义表便成为线性表。v 8． 广义表中原子个数即为广义表的长度。 9． 广义表中元素的个数即为广义表的深度。

三、 填空题

四、1、设a是含有N个分量的整数数组，则求该数组中最大整数的递归定义为（ ），最小整数的递归定

义为（ ）。 1、 最大整数的递归定义为：f(k)=a[0](k=0时)||f(k)=max(f(k-1),a[k])(k>0时)

最小整数的递归定义为：f(k)=a[0](k=0时)||f(k)=min(f(k-1),a[k])(k>0时)

2、二维数组A[10][5]采用行序为主方式存储，每个元素占4个存储单元，并且A[5][3]的存储地址是1000，则A[8][2]的地址是（ ）。

3、二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是Loc(A[0][0])，则A[i][j]的地址是（ ）。

4、广义表的（ ）定义为广义表中括弧的重数。 5、设广义表L=（（），（）），则Head(L)=（ ）；Tail(L)=（ ）；L的长度是（ ）；L的深度是（ ）。 6、广义表中的元素可以是（原子或子表 ），其描述宜采用程序设计语言中的（ 链表 ）表示。 7、广义表(((a)))的表头是（ ），表尾是（ ）。 8、广义表((a),((b),c),(((d))))的表头是（ ），表尾是（ ）。 9、设广义表A=(x,((a,b),c,d))，则Head(Head(Tail(A)))=（ ）。 10、设广义表A=(a,b,c),B=(A,(c,d)),C=(a,(B,A),(e,f))，则

（1）Head(A)=( ) (2) Tail(B)=( ) (3) Head(Head(Head(Tail(C))))=( )

11、下三角矩阵A[1..N,1..N]的下三角元素已压缩到一维数组S[1..N*（N+1）/2+1]中，若按行序为主序存储，则A[I,j]对应的S中的存储位置是 。

?0?312、已知一个稀疏矩阵为 ??0??002000?1000?0?? ，则对应的三元组表表示为 。 5??0?13、一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为n(n+1)/2 。 14、三维数组A[c1..d1,c2..d2..,c3..d3]共有 个元素。

15、数组A[1..10,-2..6,2..8]以行优先顺序存储，设基地址为100，每个元素占3个存储单元，则元素A[5,0,7]的存储地址是 。

16、将一个下三角矩阵A[1..100,1..100]按行优先存入一维数组B[1..n]中，A中元素A[66,65]在B数组中的位置为 。 五、 计算题

1、 数组A[8][6][9]以行主序存储，设第一个元素的首地址是54，每个元素的长度为5，求元素A[2][4][5]

的存储地址。

2、 假设二维数组A6x8，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的基地址为1000，

计算：

（1） 数组A的体积（存储量） （2）A的最后一个元素第一个字节的地址

（3）按行存储时，a14的第一个字节的地址 （4）按列存储时，a47的第一个字节的地址。

3、 假设按低下标优先存储整数数组A9x3x5x8时，第一个元素的字节地址是100，每个整数占4个字节。

问下列元素的存储地址是什么？

（1）a0000 （2） a1111 （3） a3125 （4）a8247

4、 按行优先顺序和按列优先顺序分别列出四维数组A[2][2][2][2]所有元素在内存中的存储顺序。 4、四维数组A的按行优先顺序在内存中的存储次序为：A0000、A0001、A0010、A0011、A0100、A0101、A0110、A0111、A1000、A1001、A1010、A1011、A1100、A1101、A1110、A1111；按列优先存储顺序为：A0000、A1000、A0100、A1100、A0010、A1010、A1110、A0001、A1001、A0101、A1101、A0011、A1011、A0111、A1111

5、

6、 一个n阶对称矩阵A采用一维数组S按行序为主序存放其上三角各元素，写出S[k]与A[i,j]的关系公

式。设A[1，1]存于S[1]中。

7、 写出下面稀疏矩阵对应的三元组表示，并画出十字链表表示法。 A=〔（0，0，2，0），（3，0，0，0），（0，0，-1，5），（0，0，0，0）〕 6、（1） 1 1 1 1 ∧

1 ∧ ∧ 0 a 1 ∧ 1 ∧

1 1 1 ∧ ∧

1 ∧ 0 b 0 c

0 d

深度为4 （2） 1 1 ∧ 1 ∧ 1 1 ∧ 1 1 1 1 ∧ 1 ∧ ∧ 0 e 0 f 0 d 1 ∧ 1 ∧ 0 a 0 b

深度为4

六、 简答题

1、 什么是广义表，简述广义表与线性表的主要区别？

2、 利用广义表的Head和Tail运算把原子student从下列广义表中分离出来。

（1） L1=（soldier,teacher,student,worker,farmer） （2） L2=（soldier,(teacher,student),(worker,farmer)）

3、 画出广义表LS=(a,((),b),(((d,e))))的存储结构图，并利用取表头、表尾的操作分离出元子e，写出表的

长度与深度。

4、 已知广义表A=( )，B=(e)，C=(a,(b,c,d))，D=(A,B,C)，它们的存储结构图是怎样的？（按两种结构中

的任一种皆可）

5、 画出广义表(a,(b,(c,( )),(d,e)))的存储图

6、画出下列广义表的存储结构图，并求它的深度。

（1）((( )),a,((b,c)),(((d)))) （2）((((a),(b))),((( ),d),(e,f))) 7、已知图4.4为广义表的存储结构图，写出各图的广义表。 （1） 1 1 ∧

1 1 ∧ 1 ∧ 1 1 ∧

0 x 1 ∧ 1 ∧ 1 ∧

0 y 1 ∧ ∧ 0 z （2） 1 1 1 ∧ ∧ 1 1 ∧ ∧ 1 1 ∧ 1 1 1 ∧ ∧ 0 a 1 ∧ 0 a 0 b 0 b

7、解答：（1）((x,(y)),(((( ))),( ),(z)))

（2）(((a,b,( )),( )),(a,(b)),( ))

七、 设计题

1、 对于二维数组A[m][n]，分别编写相应函数实现如下功能：（1）求数组 A靠边元素之和；（2）求从

A[0][0]开始的互不相邻的各元素之和；（3）当m=n时分别求两条对角线上的元素之和，否则打印出m≠n的信息。

2、 如果矩阵A中的一个元素A[i][j]满足下列条件：A[i][j]是第I行中最小的元素，又是第j列中值最大

的元素，则称之为该矩阵的一个马鞍点。编写函数计算m×n的矩阵A的所有马鞍点，并分析算法

1、下述几种排序方法中，平均查找长度最小的是（ ）。

A、插入排序 B、选择排序 C、快速排序 D、归并排序 2、设关键字序列为（3，7，6，9，7，1，4，5，20），对其进行排序的最小交换次数为（ ）。 A、6 B、7 C、8 D、20

3、下列排序算法中不稳定的有（aefh ）。

A、直接选择排序 B、直接插入排序 C、冒泡排序 D、二叉排序 E、Shell排序 F、快速排序 G、归并排序 H、堆排序 I、基数排序

4、内部排序多个关键字的文件，最坏情况下最快的排序方法是（ c ），相应的时间复杂度为（ e ），该算法是（ i ）排序方法。

A、快速排序 B、插入排序 C、归并排序 D、简单选择排序 E、O(nlog2n) F、O(n2) G、O(n2log2n) H、O(n) I、稳定 J、不稳定

5、对初始状态为递增的表按递增顺序排序，最省时间的是（ c）算法，最费时间的算法是（ b ）。 A、堆排序 B、快速排序 C、插入排序 D、归并排序 6、下述几种排序方法中，要求内存量最大的是（ ）。

A、插入排序 B、选择排序 C、快速排序 D、归并排序

7、在下面的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）。 A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序 8、下列排序中，排序速度与数据的初始排列状态没有关系的是（ ）。 A、直接选择排序 B、基数排序 C、堆排序 D、直接插入排序

9、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法为（ ）。 A、快速排序 B、堆排序 C、归并排序 D、直接插入排序

10、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列正确位置上的方法，称为（ ）。

A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序 11、 每次把待排序的元素划分为左右两个子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，右区间中元素的关键字均大于基准元素的关键字，则此排序方法为（ ）。 A、堆排序 B、快速排序 C、冒泡排序 D、Shell排序

12、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。

A、希尔排序 B、归并排序 C、插入排序 D、选择排序

13、n个记录的直接插入排序所需记录关键码的最大比较次数为（ ）。 A、nlog2n B、n2/2 C、(n+2)(n-1)/2 D、n-1

14、n个记录的直接插入排序所需的记录最小移动次数为（ ）。 A、2(n-1) B、n2/2 C、(n+3)(n-2)/2 D、2n

15、快速排序在（ b ）情况下最不利于发挥其长处，在（ c ）情况下最易发挥其长处。 A、被排序的数据量很大 B、被排序的数据已基本有序 C、被排序的数据完全有序 D、被排序的数据中最大与最小值相差不大 E、要排序的数据中含有多个相同值。 16、直接插入排序和冒泡排序的平均时间复杂度为（ d ），若初始数据有序（正序），则时间复杂度为（ a ）。

A、O(n) B、O(log2n) C、O(nlog2n) D、O(n2) 17、一组记录的关键字为（45，80，55，40，42，85），则利用堆排序的方法建立的初始堆为（ ）。 A、（80，45，55，40，42，85） B、（85，80，55，40，42，45） C、（85，80，55，45，42，40） D、（85，55，80，42，45，40）

补充选择题

1. 快速排序在最坏的情况下的时间复杂度是（ ）

A 、O(log2n) B、O(n log2n) C、O(n*n) D、O(n*n*n) 2. 具有24个记录的序列，采用冒泡排序最少的比较次数为（ ）

A 、1 B、23 C、24 D、529

3. 用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排序，记录序列的变化情况如下：

25 84 21 47 15 27 68 35 20 20 15 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84 则采用的排序方法是（ ）

A、直接选择排序 B、冒泡排序 C、快速排序 D、二路归并排序 4. 在排序过程中，键值比较的次数与初始序列的排序顺序无关的是（ ）

A、直接插入排序和快速排序 B、直接插入排序和归并排序 C、直接选择排序和归并排序 D、快速排序和归并排序

5. （ ）方法是从未排序序列中依次取出元素与已经排序序列中的元素作比较，将其放入已经排序序列的正确位置上。

A、归并排序 B、插入排序 C、快速排序 D、选择排序 6. （ ）方法是从未排序序列中挑选元素，并将其依次放入已经排序序列的一端。 A、归并排序 B、插入排序 C、快速排序 D、选择排序

7. （ ）方法是对序列中的元素通过适当的位置变换将有关元素一次性的放置在其最终位置上。 A、归并排序 B、插入排序 C、快速排序 D、基数排序

8. 将上万个一组无序并且互不相等的正数序列，存储在顺序存储结构中采取（ ）方法能够最快地找到其中最大的正整数。

A、快速排序 B、插入排序 C、选择排序 D、归并排序 9. 以下四种排序方法，要求附加内存空间最大的是（ ）

A、插入排序 B、选择排序 C、快速排序 D、归并排序 10. 以下说法错误的是（ ）

A、直接插入排序的空间复杂度为O(1)。 B、快速排序附加存储开销为O(log2n)。 C、堆排序的空间复杂度为O(n)。

D、二路归并排序的空间复杂度为O(n),需要附加两倍的存储开销。 11. 以下不稳定的排序方法是（ ）

A、直接插入排序 B、冒泡排序 C、直接选择排序 D、二路归并排序 12. 以下稳定的排序方法是（ ）

A、快速排序 B、冒泡排序 C、直接选择排序 D、堆排序

2

13. 以下时间复杂性不是O(n)的排序方法是（ ）

A、直接插入排序 B、二路归并排序 C、冒泡排序 D、直接选择排序 14. 以下时间复杂性不是O(nlog2n)的排序方法是（ ）

A、堆排序 B、直接插入排序 C、二路归并排序 D、快速排序 15. 快速排序方法在（ ）情况下最不利于发挥其长处。 A、 要排序的数据量太大 B、 要排序的数据中含有多个相同值 C、 要排序的数据已基本有序 D、 要排序的数据个数为奇

16. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（ ）排序法。 A、起泡排序 B、快速排序 C、堆排序 D、基数排序 17. 快速排序在最坏的情况下的时间复杂度是（ ）

23

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

18. 一组记录的关键码为（46，79，56，38，40，84）则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）

A、38，40，46，56，79，84 B、40，38，46，79，56，84 C、40，38，46，56，79，84 D、40，38，46，84，56，79

19. 一组记录的排序码为（46，79，56，38，40，84）则利用堆排序的方法建立的初始堆为（ ） A、79，46，56，38，40，84 B、84，79，56，38，40，46 C、84，79，56，46，40，38 D、84，56，79，40，46，38

20. 若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行（ ）次比较。

A、33 B、45 C、70 D、91 21. 一组记录的关键字为（32，41，15，39，77，12，48，30，52），按2－路归并排序的方法对该序列进行一趟归并后的结果为（ ）

A、15,32,41,12,39,77,30,48,52 B、12,15,32,39,41,77,30,48,52 C、32,41,15,39,12,77, 30,48,52 D、12,15,30,32,39,41,48,52,77

二、判断题

1． 如果某种排序算法是不稳定的，则该方法没有实际意义。

2． 当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度

的主要原因之一。

3． 对于n个记录的集合进行冒泡排序，所需要的平均时间是O（nlog2n）。 4． 对于n个记录的集合进行归并排序，所需要的平均时间是O（nlog2n）。 5． 对于n个记录的集合进行快速排序，所需要的平均时间是O（n）。 6． 堆排序所需的时间与待排序的记录个数无关。

7． 外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内

部排序的时间。

8． 外排序过程主要分为两个阶段：生成初始归并段和对归并段进行逐趟归并的阶段。

三、填空题 1、在直接插入和直接选择排序中，若初始数据基本有序，则选用（ ），若初始数据基本反序，则选用（ ）。 2、在对一组记录（50，40，95，20，15，70，60，45，80）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为（ ），在整个排序过程中共需进行（ ）趟才可完成。 3、n个记录的冒泡排序算法所需最大移动次数为（ ），最小移动次数为（ ）。 4、对n个结点进行快速排序，最大比较次数为（ ）。

5、在对一组记录（50，40，95，20，15，70，60，45，80）进行（大根）堆排序时，根据初始记录构成初始堆后，最后4条记录为（ ）。

6、对于直接插入排序、冒泡排序、简单选择排序、堆排序、快速排序有：（1）当文件“局部有序”或文件长度较小时，最佳的内部排序方法是（ ）。（2）快速排序在最坏情况下时间复杂度是（ ）比（ ）性能差；（3）就平均时间而言，（ ）最佳。

7、在堆排序、快速排序和归并排序中，若只从存储时间考虑，则应首先选取（ ）方法，其次选用（ ）方法，最后选用（ ）方法；若只从排序结果的稳定性考虑，则应选取（ ）方法；若只从平均情况下排序最快考虑，则应选取（ ）方法，若只从最坏情况下排序最快并节省内存，则应选取（ ）方法。 8、对于n个记录的集合进行归并排序，所需的附加空间__________________。

9、设表中元素的初始状态是按键值递增的，分别用堆排序，快速排序，冒泡排序，归并排序进行递增排序，则______________最节省时间，________________最费时间。对快速排序来讲，其最好的情况下的时间复杂度为_______________，最坏的时间复杂度为______________。

10、目前以比较为基础的内部排序的时间复杂度T（n）的范围是___________，其比较次数与待排序的记录的初始状态无关的是___________。

11、在内部排序中要求附加的内存容量最大的是_________，排序时不稳定的是___________。

12、从时间上看，快速排序的平均性能优于其他排序方法，但从空间上看，快速排序需要一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个序列，则栈的最大深度为________；在最坏的情况下，栈的深度为______。 13、堆的形状是一棵___________。

14、若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。

15、按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。 16、直接插入排序是稳定的，它的时间复杂性为________，空间复杂度为________。 17、归并排序要求待排序列由若干个___________的子序列组成。 18、二路归并排序的时间复杂度是___________。

19、在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 次。

20、在利用快速排序方法对一组记录（54，38，96，23，15，72，60，45，83）进行快速排序时，递归调用

而使用的所有能达到的最大深度为 ，共需递归调用的次数为 ，其中第二次递归调用是对 组记录进行快速排序。

21、在堆排序和快速排序中，若原始记录接近正序和反序，则选用 ，若原始记录无序，则最好选用 。

22、在插入排序和选择排序中，若初始数据基本正序，则选用 ，若初始数据基本反序，则选用 。

三、 简答题

1、 简要回答下列问题：

（1） 什么是内部排序、外部排序？（2）什么是排序方法的稳定性？ 2、 已知序列（70，83，100，65，10，32，7，9），请给出采用插入排序、快速排序和冒泡排序方法对

该序列做升序排序的每一趟的结果。

3、 有如下一组关键字（25，67，78，24，38，64，55，22，15，48），判定其是否为堆，若不是堆，请

调整为一个小根堆，使堆排序将按关键字从大到小排列，写出调整过程。

四、应用题

1. 一组关键字（19，01，26，92，87，11，43，87，21），进行冒泡排序，试列出每一趟排序后的关键字序列，并统计每遍排序所进行的关键字比较次数。

2. 对上题给出的关键字序列，进行选择排序，列出每一趟排序后关键字序列，并统计每遍排序所进行的关键字比较次数。

3. 从快速排序法的基本原理不难看出，对n个元素组成的线性表进行快速排序时，所须进行的比较次数依赖于这n个元素的初始排列。

（1）试问：当n=7时，在最好情况下须进行多少次比较？说明理由； （2）对n=7给出一个最好情况的初始排列的实例。

4. 对下列一组关键字（46，58，15，45，90，18，10，62）试写出快速排序的每一趟的排序结果，并标出第一趟中各元素的移动方向。

5. 试证明：当输入序列已经呈现为有序状态时，快速排序的时间复杂度为O(n2)。

6. 在快速排序算法中，能否用队列代替栈用来保存子文件中首尾记录的地址（下标）？ 7. 判断以下序列是否为堆，若不是，则调整为堆。 （1）（97，86，48，73，35，39，42，57，66，20）

（2）（12，70，33，65，24，56，48，92，86，31）

（3）(103，97，56，38，66，23，42，12，30，52，06，20) （4）(05，56，20，23，40，38，29，61，35，76，28，99)

8. 设有5000个无序的元素，希望用最快的速度挑选出前10 个大的元素。请说明那种算法最好，并说明理由。

9. 用图示给出关键字序列（92，37，86，33，12，57，25）初始建堆和输出前两个最小关键字后重建堆的过程。

10. 已知8个有链域的记录，其关键字分别为(179，208，306，093，859，984，271，033)试用基数排序法实施排序，描述其排序过程，并说明该法的稳定性，如图10.1所示： H 179 208 306 093 859 984 271 033 图10.1

11. 在什么情况下，基数排序的高位优先法比低位优先法更有效？

12. 假设某旅店共有5000个床位，每天需根据住宿旅客的文件制造一份花名册，该名册要求按省（市）的次序排列，每一省(市)按县（区）排列，又同一县（区）的旅客按姓氏排列。请你为旅店的管理人员设计一个制作这份花名册的方法。

13. 已知一个含有n个记录的序列，其关键字均为介于0和n2之间的整数。若利用堆排序等方法进行排序，则时间复杂度为O(nlogn)。如果将每个关键字Ki认作Ki=Ki1n+Ki2，其中Ki1和Ki2都是范围[0，n]中的整数，则利用基数排序只需O(n)的时间。推广之，若整数关键字的范围为[0，nk]，则可得到只需时间(kn)的排序方法，试讨论如何实现之。

14. 假设我们把n个元素的序列（a1,a2,…an）中满足条件akaj(i

15. 给出一组关键字(17,4,22,56,10,41,6,13,36,8,25)，设内存工作区可容纳4个记录，写出用置换－选择排序得到的全部初始归并段。

16. 设有11个长度不同的初始归并段，它们所包含的记录个数分别为25，40，16，77，64，53，88，9，48和98。试根据它们做4路平衡归并，要求：（1）指出总的归并趟数； （2）构造最佳归并树；（3）根据最佳归并树计算每一趟及总的读记录数。

五、算法设计题

1. 以先查找插入位置，后插入的方法，试在静态链表上实现直接插入排序。 2. 设待排序的文件用单链表作存储结构，头指针为L，试写出选择排序算法。 3. 试设计一个双向冒泡排序算法，即在排序过程中交替改变扫描方向。 4. 写出快速排序的非递归算法。

5. 奇偶交换排序如下所述：第一趟对所有奇数i，将a[i]和a[i+1]进行比较；第二趟对所有的偶数i，将a[i]和a[i+1]进行比较，若a[i]>a[i+1]，则将两者交换；第三趟对奇数i，第四趟对偶数i，…，依次类推直至整个序列有序为止。编写如上所述的奇偶交换排序的算法。

6. 假设由1000个关键字为小于10000的整数的记录序列，请设计一种排序方法，要求以尽可能少的比较次数和移动次数实现排序，并按你的设计编写算法。

7. 荷兰国旗问题：设有一个仅有红、白、蓝 三种颜色的条块组成的条块序列。编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。

8. 已知（k1,k2,…,kp）是堆，则可以写一个时间复杂度为O(logn)的算法将（k1,k2,…,kp,kp+1）调整为堆。试编写“从p=1起逐个插入建堆”的算法，并讨论由此方法建堆的时间复杂度。

9. 2-路归并排序的另一策略是，先对待排序序列扫描一遍，找出并划分为若干个最大有序序列，将这些子列作为初始归并段。试写一个算法在链表结构上实现这一策略。

10. 已知记录序列a[1..n]中的关键字各不相同，可按如下所述实现计数排序：另设数组c[1..n]，对每个记录

14. 15. 16. 17. 18. 19. 20.

21. 22. 23. 24. 25. 26. 27. 28. 29.

余的________个指针域为NULL。

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

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

在________遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。 具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编号（根结点为1号），则编号最大的分支结点序号是________，编号最小的分支结点序号是________，编号最大的叶子结点序号是________，编号最小的叶子结点序号是________。

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

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

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

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

一棵树的形状如图6.5所示，它的根结点是________，叶子结点是________，结点H的度是________，这棵树的度是________，这棵树的深度是________，结点F的儿子结点是________，结点G的父结点是________。

A

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 E C

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

F

图6.7

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

A

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 K

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

B 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 ―n-1‖ 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条边的无向图，若采用邻接表表示，则表向量的大小为（ 1） ）；所有 ），所有顶点

（ 邻接表的结点总数为（ ）。

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

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

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

（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点开始深度遍历，得到的顶点序列为（ b ）。 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到

本文来源：https://www.bwwdw.com/article/eivf.html