数据结构课后练习题
第一章 绪论
一、选择题
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={ 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、对于顺序表的优缺点，以下说法错误的是（ ） A、无需为表示结点间的逻辑关系而增加额外的存储空间 B、可以方便地随机存取表中的任一结点 C、插入和删除运算较方便 D、由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配) 21、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。 A、顺序表 B、单链表 C、双链表 D、单循环链表 22、循环链表主要优点是（ ） A、不再需要头指针了 B、已知某个结点的位置后，能够容易找到它的直接前趋 C、在进行插入、删除运算时，能更好地保证链表不断开 D、从表中任一结点出发都能扫描到整个链表 23、在线性表的下列存储结构中，读取元素花费时间最少的是（ ） A、单链表 B、双链表 C、循环链表 D、顺序表 二、填空题 １、在线性结构中，第一个结点（ ）前趋结点，其余每个结点有且只有（ ）个前趋结点。 ２、在顺序表中插入或删除一个元素，需要平均移动（ ）元素，具体移动的元素个数与（ ）有关。 ３、已知Ｌ是无表头结点的单链表，试从下列提供的答案中选择合适的语句序列，分别实现： （１）表首插入Ｓ结点的语句序列是（ ）。 （２）表尾插入Ｓ结点的语句序列是（ ）。 Ａ、Ｐ->next=S; Ｂ、P=L; Ｃ、L=S; Ｄ、P->next=S->next; Ｅ、S->next=P->next; Ｆ、S->next=L; Ｇ、S->next=NULL; Ｈ、while(P->next!=Q)p=p->next; Ｉ、while(P->next!=NULL)P=P->next; 4、已知L是带表头结点的非空单链表，试从下列提供的答案中选择合适的语句序列。 （1）删除首元结点的语句序列是（ ） ,（2）删除尾元结点的语句序列是（ ） A、P=P->next; B、P->next=P->next->next; C、while(P!=NULL)p=p->next; D、while(Q->next!=NULL){P=Q;Q=Q->next;} E、while(P->next!=Q)P=P->next; F、Q=P; G、Q=P->next; H、P=L; I、L=L->next; J、free(Q); 5、已知L是带表头结点的非空链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 （1）删除P结点的直接后继结点的语句序列是（ ）, （2）删除P结点的直接前趋结点的语句序列是（ ） A、P->next=P->next->next; B、P=P->Pnext->next; C、while(P->next!=Q)P=P->next; D、while(P->next->next=Q)P=P->next; E、Q=P; F、Q=P->next; G、P=L; H、L=L->next; I、free(Q); 6、已知结点编号，在各结点查找概率相等的情况下，从n个结点的单链表中查找一个结点，平均要访问（ ）个结点，从n个结点的双链表中查找一个结点，平均要访问（ ）个结点。 7、对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是（ ）；在值域为给定值的结点后插入一个新结点的时间复杂度是（ ）。 8、单链表是（ ）的链接存储表示。 9、单链表中设置头结点的作用是（ ）。 10、在单链表中，除首元结点外，任一结点的存储位置由（ ）指示。 11、在非空双向循环链表中，在结点q的前面插入结点p的过程如下： p->prior=q->prior; q->prior->next=p;p->next=q;( ); 12、在双向链表中，每个结点有两个指针域，一个指向（ ），另一个指向（ ）。 13、顺序表中逻辑上相邻的元素的物理位置（ ）相邻。单链表中逻辑上相邻的元素的物理位置（ ）相邻。 14、为了便于讨论，有时将含n(n≥0)个结点的线性结构表示成(a1，a2,?,an)，其中每个ai代表一个______。a1称为______结点，an称为______结点，i称为ai在线性表中的________。对任意一对相邻结点ai、ai┼1(1≤i 15、线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接______外，其他结点有且仅有一个直接______；除终端结点没有直接______外，其它结点有且仅有一个直接______. 16、所有结点按1对1的邻接关系构成的整体就是______结构。 17、线性表的逻辑结构是______结构。其所含结点的个数称为线性表的__________。 18、在单链表中，指针p所指结点为最后一个结点的条件是___________。 三、判断题 1. 顺序存储的线性表可以随机存取。 2. 顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要 移动。 3. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据 对象。 4. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。 5. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 6. 在单链表中，可以从头结点进行查找任何一个元素。 7. 线性表的链式存储结构优于顺序存储结构。 8. 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。 9. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 10. 顺序存储方式只能用于存储线性结构。 四、简答题 1、 若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用哪种存储结构？为什么？ 2、 描述概念：头指针、头结点、首元结点的区别？ 3、 设A是一个线性表（a1a2…an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需 要移动的元素个数为多少？若元素插在ai与ai+1之间（0<=I<=n-1）的概率为2(n-i)/(n(n+1))，则平均每插入一个元素所要移动的元素个数又是多少？ 4、为什么在单循环链表中设置尾指针比设置头指针更好？ 5、双链表和单循环链表中，若仅知道指针p指向某个结点，不知道头指针，能否将结点*p从相应的链表中删除？若可以，其时间复杂度各为多少？ 6、下列算法的功能是什么？ LinkedList test1(LinkedList L) {//L是无头结点的单链表 ListNode *q,*p; if(L&&L->next) {q=L ; L=L->next; p=L; while(p->next) p=p->next; p->next=q; q->next=NULL; } return L; } 7、如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构。为什么？ 8、若线性表的总数基本稳定，且很少进行插入删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构。为什么？ 9、设有多项式a(x)=9+8x+9x4+5x10 b(x)=-2x+22x7-5x10 （1） 用单链表给出a(x)、b(x)的存储表示； （2） 设c (x)=a(x)+b(x)，求得c(x)并用单链表给出其存储表示。 五、设计题 1、编写一个函数将一个顺序表A（有多个元素且任何元素不为0）分拆成两个顺序表，使A中大于0的元素存放在B中，小于0的元素存放在C中。 2、设顺序表L中的数据元素递增有序。试写一算法，将e插入到顺序表的适当位置，插入后保持该表的有序性。 3、A、B为元素递增有序排列的单链表（同一表中可能有相同元素），编写算法另建一单链表C，保存两个表的公共元素，要求C的元素值各不相同且递增有序。 4、设有一个由正整数组成的无序单链表，编写算法实现下列功能： （1） 找出最小值结点，且显示该数值。 （2） 若该数值为奇数，则将其与直接后继结点的数值交换。 （3） 若为偶数，则将其直接后继结点删除。 六、编程附加题 1. 试分别用顺序表和单链表作为存储结构，实现将线性表（a0,a1,a2,….an-1）就地逆置的操作，所谓“就地” 指辅助空间为O（1）。 2. 设顺序表L是一个递增（允许有相同的值）有序表，试写一算法将x 插入L中，并使L仍为一个有序 表。 3. 设单链表L是一个非递减有序表，试写一个算法将x插入其中后仍保持L的有序性。 4. 试写出在无头结点的单链表的第i个元素之前插入一个元素的算法。 5. 设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。试写一算法分别以顺序存储和链式 存储将A和B归并成一个仍按元素值递增有序的线性表C，请分析算法的时间复杂度。 6. 设指针la和lb分别指向两个无头结点的单链表的首结点，设计从表la中删除第i个元素起共len个元素， 并将这些元素插入到lb中第j个结点之前的算法。 7. 单链表L是一个递减有序表，试写一高效算法，删除表中值大于min且小于max的结点（若表中有这样 的结点），同时释放被删结点空间，这里min和max是两个给定的参数。请分析你的时间复杂度。 8. 编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和 pb，使得A链表中含有链表A中的序号为奇数的元素，而B链表中含有原链表A中的序号为偶数的元素，且保持原来的相对顺序。 9. 假设以两个元素依值递增有序排列的线性表A,B分别表示两个集合，先要求另辟空间构造一个线性表 C,其元素为两集合的交集，且表C中的元素也依值递增有序排列。是对顺序表编写求C的算法。 10. 设有线性表A=(a1,a2,.. .,am)和B=(b1,b2,.. .,bn)。试写合并A、B为线性表C的算法，使得： C=??(a1,b1,...,am,bm,bm?1,bn)当m?n; (a,b,...,a,b,a,...,a)当m?n;nnn?1m?11线性表A,B和C均以单链表作存储结构，且C表利用A表和B表的结点空间。 11. 假设在长度大于1的单循环链表中，既无头结点也无头指针。S为指向链表中某个结点的指针，试编写 算法删除结点*s 的直接前驱结点。 12. 计算带头结点的循环链表的结点个数。 13. 已知由单链表表示的线性表中，含有三类字符的数据元素（如：字母字符、数字字符和其他字符），试 编写算法构造三个以循环链表表示的线性表使得每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 14. 已知A,B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C 表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注：题中没特别指明同一表中的元素值各不相同）。 15. 双向循环链表中，设计满足下列条件的算法。 （1）在值为x的结点之前插入值为y的结点。 （2）删除值为x的结点。 16. 设有一个循环双链表，其中有一结点的指针为P，编写算法将P与其右边的一个结点进行交换。 17. 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个可访问频度域freq，在链表被 起用之前，其值均初始为0。每当链表进行一次LocateNode（L，x）运算时令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减次序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode的运算的算法。 18. 给出用单链表存储多项式的结构，并编写一个按指数值递增次序输入所产生的多项式链表的过程。 19. 根据上题的多项式链表结构，编写一个过程实现两个多项式相加的运算。 20. （Josephus环）任给正整数n、k，按下述方法可得排列1，2，?，n的一个置换:将数字1，2，?，n 环形排列，按顺时针方向从1开始 计数；计满K时输出该位置上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，n=10，k=3时，输出的置换是3，6，9，2，7，1，8，5，10。分别以数组和以不带头结点的、已知尾指针的单循环链表为存储结构解决上述问题。 21 已知在一维数组A[1..m+n]中依次存放着两个向量（a1,a2,….am）和（b1,b2,….bn），编写算法将两个向量的位置互换，即把（b1,b2,….bn）放到（a1,a2,….am）之前。 22 给定一个不带头结点的单链表，编写计算此链表长度的算法。 23 设ha和hb分别是两个带头结点的非递减有序单链表的表头指针， 试设计一个算法， 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。 24 设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法： (1)找出最小值结点，且打印该数值； (2)若该数值是奇数，则将其与直接后继结点的数值交换； (3)若该数值是偶数，则将其直接后继结点删除； 25 利用顺序表的操作，实现以下的函数。 (1) 从顺序表中删除具有最小值的元素并由函数返回被删元素的值，空出的位置由最后一个元素填补。 (2) 从顺序表中删除具有给定值x的所有元素。 (3) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。 26 如果以单链表表示集合，设计算法建立先后输入的两个集合的差。 27 已知一个线性表中的元素按元素值非递减有序排列，分别以顺序存储和链式存储编写一个算法删除表中多余的值相同的元素。 28 设A=（a1,a2,a3,......an）和B=(b1,b2,.. .,bm)是两个顺序表（假定所含数据元素均为整数）。若n=m且ai=bi(i=1,.. .,n),则称A=B;若ai=bi(i=1,...,j)且aj+1 29 已知一个循环单链表如图2.1所示，编写一个算法将所有箭头方向取反。 head a1 a2 an ? 图2.1 30 假设有一个单循环链表，其结点含有三个域：prior，data，和next。其中data为数据域，next指向后继结点，prior为指针域，它的值为空指针，试编写算法将此表改为双向循环链表。 31 设A是一个双向循环链表，其表中元素递增有序。试写一算法插入一个元素x，使表A中的元素依然递增有序。 32写出将双向循环链表倒置的算法。 33 设计一算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式各自仅有奇次幂或偶次幂项，并要求利用原链表中的结点空间来构造这两个链表。 34 设以带头结点的双向链表表示的线性表L=(a1,a2,…,an)，试写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,…,an,a4,a2)。 35 设一单向链表的头指针为head，链表的记录中包含着整数类型的key域，试设计算法，将此链表的记录按照key 递增的顺序进行就地排序。 第三章栈与队列 练习题 一、 选择题 1、栈结构通常采用的两种存储结构是（ ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2、设栈ST用顺序存储结构表示，则栈ST为空的条件是（ ） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3、向一个栈顶指针为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; 4、从一个栈顶指针为HS的链栈中删除一个结点，用x保存被删除结点的值，则执行（ ） A、x=HS;HS=HS->next; B、HS=HS->next;x=HS->data; C、x=HS->data;HS=HS->next; D、s->next=Hs;Hs=HS->next; 5、表达式a*(b+c)-d的后缀表达式为（ ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6、中缀表达式A-（B+C/D）*E的后缀形式是（ ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7、一个队列的入列序列是1，2，3，4， 则队列的输出序列是（ ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8、循环队列SQ采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为空的条件是（ ） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9、循环队列SQ采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为满的条件是（ ） 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、 在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。 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、 有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据 结构是（ ） A、向量 B、树 C、图 D、二叉树 2、树最适合用来表示（ ） A、有序数据元素 B、元素之间具有分支层次关系的数据 C、无序数据元素 D、元素之间无联系的数据 3、树B的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ ） A、1a(2b(3d,3e),2c) B、a(b(D,e),c) C、a(b(d,e),c) D、a(b,d(e),c) 4、对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ ）次序的遍历实现二叉树的结点编号。 A、先序 B、中序 C、后序 D、从根开始按层次遍历 5、按照二叉树的定义，具有3个结点的二叉树有（ ）种。 A、3 B、4 C、5 D、6 6、在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为 n0，则数的最大高度为（n0+n1+n2 ），其叶结点数为（ n2+1 ）；树的最小高度为（[ log2n]+1 ），若采用链表存储结构，则有（n+1 ）个空链域。 A、n/2 B、[ log2n]+1 C、log2n D、n E、n0+n1+n2 F、n1+n2 G、n2+1 H、1 I、n+1 J、n1 K、n2 L、n1+1 7、对一棵满二叉树，m个树叶，n个结点，深度为h，则（ ） A、n=m+h B、h+m=2n C、m=h-1 D、n=2h-1 8、设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ），至多为（ ）。 A、2h B、2h-1 C、2h-1 D、2h-1 9、在一棵二叉树上第5层的结点数最多为（ ）（假设根结点的层数为1） A、8 B、16 C、15 D、32 10、深度为5的二叉树至多有（ ）个结点。 A、16 B、32 C、31 D、10 11、一棵有124个叶结点的完全二叉树，最多有（ ）个结点 A、247 B、248 C、249 D、250 12、含有129个叶子结点的完全二叉树，最少有（ ）个结点 A、254 B、255 C、256 D、257 13、假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）个。 A、15 B、16 C、17 D、47 n2+1=n0 16、用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结点（ ）。 A、R[2i+1] B、R[2i] C、R[i/2] D、R[2i-1] 17、在一棵非空二叉树的中序遍历序列中，根结点的右边（ ）。 A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的所有结点 D、只有左子树上的部分结点 18、任何一棵二叉树的叶结点在先序、中序和后序遍历中的相对次序（ ）。 A、不发生改变 B、发生改变 C、不能确定 D、以上都不对 19、设n、m为一棵树上的两个结点，在中序遍历时，n在m前的条件是（ ）。 A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙 20、一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前驱为（ ），后序遍历中结点B的直接后继是（ ）。 A、B B、D C、A D、I E、F F、C 21、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ ）。 A、acbed B、decab C、deabc D、cedba 22、若二叉树采用二叉链表作存储结构，要交换其所有分支结点左右子树的位置，利用（ ）遍历方法最合适。 A、前序 B、中序 C、后序 D、层次 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 A B 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个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其 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到 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网必须是（ c ），AOE网中某边权值应当是（ d ），权值为0的边表示（ b ）。 （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、用邻接矩阵法存储一个图时，所占用的存储空间大小仅与图中结点个数有关。v 2、对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。x 3、任何有向网拓扑排序的结果是唯一的。x 4、有回路的图不能进行拓扑排序。v 5、存储有向图的邻接矩阵是对称的。x 6、一个有向图G中若有弧 7、在AOE网中一定有一条关键路径。v 8、含有10个顶点的无向连通图其生成树含有9条边。v 9、十字链表是图的一种顺序表示法。x 三、 填空题 1、对具有n个顶点的图，其生成树有且仅有__________条边，即生成树是图的边数__________的连通图。 2、一个无向图有n个顶点和e条边，则所有顶点的度数之和为（ ），其邻接矩阵是一个关于__________对称的矩阵。 3、在图形结构中，每个结点的前驱结点和后继结点可以有（ ）。 4、若无向图G的顶点度数的最小值大于或等于（ ）时，G至少有一条回路。 5、设无向图G的顶点数为n，图G最少有（ ）边，最多有（ ）条边。若G为有向图，有n个顶点，则图G最少有（ ）条边，最多有（ ）条边。具有n个顶点的无向完全图，边的总数为（ ）条，而有n个顶点的有向完全图，边的总数为（ ）条。 6、在无权图G的邻接矩阵A中，若(vi,vj)或 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 V 4 ∧ 2 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)或 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 e=10 e2=9 10 e3=14 e6=3 3 6 e12=5 e11=5 8 e13=8 e14=8 22、设x,y∈V，若 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开始 利用Prim算法得到的最小生成树。 ?? 1 12 510??1?89??? ??128??2? ? ? ?59??4? ??10?24??? 图7.8 1 4 2 7 6 8 5 3 图7.9 9 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 V5 0 2 3 5 ∧ 5 2 6 3 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 V6 V8 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开始的深度优先和 广度优先遍历之，给出遍历中结点的序列，最后画出该图的一棵最小生成树。其中表结点的三个域为 顶点号 边上的权值 指针 1 2 8 3 10 4 ∧ 11 2 1 8 3 3 5 ∧ 13 3 1 10 2 3 4 ∧ 4 4 1 11 3 4 5 ∧ 7 5 2 13 4 ∧ 7 图 7.17 ?0?116. 已知某图G的邻接矩阵为 ??0??1101001011?0??，顶点集合为{v1,v2,v3,v4} 1??0?（1）由邻接矩阵画出相应的图G； （2）如果要使用此图成为完全图还要增加哪几条边。 17. 试利用弗洛伊德算法，写出如图7.18所示相应的带权邻接矩阵的变化。 6 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 D a12=5 B 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 图7.19 第8章 一、应用题 动态存储管理 1、 假设利用边界标识法首次适配策略分配，已知在某个时刻的可利用空间表的状态如图8.1所示： pav 802 213 462 604 0 56 0 117 0 122 0 53 0 0 0 0 （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个元素的线性表，其时间复杂度为（a ），折半查找一个具有n个元素的有序表，其时间复杂度为（b ）。 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，建立二叉排序树，则其先序遍历序列为（ c ），中序遍历序列为（ a ）。 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 20 37 37 37 9 30 9 9 37 21 46 30 30 46 30 19 46 19 19 20 20 9 B、 0 1 2 3 4 5 6 C、 0 1 2 3 4 5 6 D、 0 1 2 3 4 5 6 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、以下说法正确的是（ ） A、前序遍历二叉排序树的结点就可以得到排好序的结点序列 B、任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间 C、对具有相同关键字集合的任一插入序列，得到的二叉排序树的形态都是相同的 D、采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要 22、已知采用开放地址法解决哈希表冲突，要从此哈希表中删除一个记录，正确的做法是（ ） A、将该元素所在的存储单元清空 B、将该元素用一个特殊的符号代替 C、将与该元素有相同Hash地址的后继元素顺次前移一个位置 D、用与该元素有相同Hash地址的最后插入表中的元素替代 23、设哈希表长为M=14，哈希函数H（key）=key。表中已有4个结点： ADDR(15)=4 ADDR(38)=5 ADDR(61)=6 ADDR(84)=7 其余地址为空，如用二次探测再散列处理冲突，现插入关键字为50的结点的地址应是（ ） A、3 B、8 C、9 D、10 24、有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素查找概率相同的情况下，查找成功所需的平均比较次数为（ ） A、32/12 B、35/12 C、37/12 D、39/12 25、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应（ ）个结点最佳。 A、25 B、10 C、6 D、625 26、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用（ ）查找方法。 A、分块 B、顺序 C、折半 D、散列 27、深度为6的AVL树至少有（ ）个结点。 A、10 B、12 C、20 D、21 28、哈希表的平均查找长度（ ） A、与处理冲突的方法有关而与表的长度无关 B、与处理冲突的方法无关而与表的长度有关 C、与处理冲突的方法有关且与表的长度有关 D、与处理冲突的方法无关且与表的长度无关 29、若为查找表长度为m的闭散列表采用二次探测再散列处理冲突，对一个元素第1次计算的哈希地址为d，则第3次计算的哈希地址为（ ） A、(d+1)%m B、(d-1)%m C、(d+4)%m D、(d-4)%m 30、以下说法正确的是（ ） A、数字分析法需事先知道所有可能出现的键值及所有键值的每一位上各数字的分布情况，并且键值的位数比散列地址的位数多 B、除余法要求事先知道全部键值 C、平方取中法需要事先掌握键值的全部分布情况 D、随机数法适用于键值不相等的场合 31、有数据(49,32,40,6,45,12,56)，从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小，则应选择下列哪个输入序列（ ） A、45，12，49，6，40，56，32 B、40，12，6，32，49，45，56 C、6，12，32，40，45，49，56 D、32，12，6，40，45，56，49 32、在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（ ） A、n B、log2n C、(h+1)/2 D、h 二、 判断题 1、 分块查找方法的平均查找长度低于顺序查找，高于折半查找。v 2、 采用线性探测再散列法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位 置置为空，因为这会影响以后的查找。v 3、 m阶B-树每一个结点的子树个数都小于或等于m。v 4、 m阶B-树每一个结点的子树个数都大于或等于?m/2?。x 5、 m阶B-树具有k个子树的非叶子结点含有k-1个关键字。v 6、 m阶B-树的任何一个结点的左、右子树的高度都相等。v 7、 前序遍历二叉排序树的结点就可以得到排好序的结点序列。x 8、 在任一二叉排序树上查找某个结点都小于用顺序查找法查找同样结点的线性表的查找时间。x 9、 虽然关键字的序列的顺序不一样，但依次生成的二叉排序树却是一样的。x 10、 对二棵具有相同关键字集合的形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一 样的。v 11、 在二叉排序树上插入新的结点时，不必移动其他结点，仅需要改动某个结点的指针，由空变为 非空即可。v 12、 在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置 空即可。x 三、 填空题 1、折半查找效率较高，但要求结点（ ）并且要求线性表（ ）；而对于顺序查找，则线性表的存储方式（ ）。 2、假设在有序线性表A[0]—A[9]上进行折半查找，则比较一次查找成功的结点数为（ ），比较二次查找成功的结点数为（ ），比较三次查找成功的结点数为（ ），比较四次查找成功的结点数为（ ），比较五次查找成功的结点数为（ ），平均查找长度为（ ）。 3、在n个记录的有序顺序表中进行折半查找，最大的比较次数是（ ）。 4、折半查找判定树既是一种（ ），也是一种（ ）。 5、顺序查找法的平均查找长度为（ ）；折半查找法的平均查找长度为（ ）；分块查找法（以顺序查找确定块）的平均查找长度为（ ）；分块查找法（以折半查找确定块）的平均查找长度为（ ）；哈希表查找法采用链接法处理冲突时的平均查找长度为（ ）。 6、对于长度为n的线性表，若进行顺序查找，则时间复杂度为（ ）；若进行折半查找，则时间复杂度为（ ）；若采用分块查找（假定总块数和每块长度均接近n的开方），则时间复杂度为（ ）。 7、用二分法查找一个线性表时，该线性表必须具有的特点是（ ），而分块查找法要求将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间（ ）。 8、采用散列技术来实现查找，需要解决的问题有：（ ）和（ ）。 9、在散列存储中，处理冲突有（ ）和（ ）两类方法。 10、（ ）法构造的哈希函数肯定不会发生冲突。 11、在各种查找方法中，平均查找长度与结点个数无关的查找方法为（ ）。 12、在集合这种逻辑结构中，任何结点之间都不存在________关系，这是集合这种逻辑结构的基本特点。 13、在开散列表上查找键值等于K的结点，首先必须计算该键值的 ，然后在通过指针查找该结点。 14、在索引顺序表上，对于顺序表中的每一块，索引表中有相应的一个\索引项\。每个索引项有两个域：块内最大________值和块________位置。 15、索引顺序表上的查找分两个阶段：一、________；二、________。该查找方法称为________查找。 16、二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值________于其左孩子（及其子孙）的键值且________于其右孩子（及其子孙）的键值。 17、在表示一棵二叉排序树的二叉链表上，要找键值比某结点X的键值________的结点，只需通过结点X的右指针到它的右子树中去找。 18、中序遍历一棵二叉排序树所得的结点访问序列是键值的________序列。 19、二叉排序树上的查找长度不仅与________有关，也与二叉排序树的________有关。 20、二叉排序树的查找效率与树的形态有关。当二叉排序树退化为一条单支树时，查找算法退化为________查找，平均查找长度上升为________。 21、有n个结点的AVL树的深度与________是同数量级的，因而在它上面进行查找的平均查找长度也与________同数量级。 22、________查找法的平均查找长度与元素个数n个数无关。 23、在具有20个元素的有序表上进行折半查找，则比较一次查找成功的结点数为________，比较二次查找成功的结点数为________，比较五次查找成功的结点数为________。总的平均查找长度为________。 24、当所有结点的值都相等时，用这些结点构造的二叉排序树上只有________。 25、折半查找方法仅适用于这样的表：表中的记录必须________，其存储结构必须是________。 26、考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于或等于其右子树上的一切结点的值。现把9个数1，2，3，4，5，6，7，8，9填入如图9.1所示的二叉树中，并使之满足上述性质。（圆圈旁边的数字表示插入结点的序号） 1 3 2 4 6 5 8 9 7 图9.1 27、设线性表L=（a1,a2,?,an）(n>2),表中元素按值的递增顺序排列。对一个给定的值k，分别用顺序查找和 折半查找与k相等的元素，比较次数分别为s和b ，若检索不成功，则s和b的数量关系是________。 28、某顺序存储的表，其中有10000个元素，已按关键字的值升序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字都不相同。用顺序查找法查找时，查找成功时的平均比较次数为__________，最大比较次数为__________。现把10000个元素按排列顺序划分成若干组，使得每一组中有g个元素（最后一组可能小于g）。查找时，先从头一组开始，通过比较各组的最后一个元素的关键项值，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的比较次数最小的g是__________，此时的平均比较次数是__________。 29、如果m阶B-树中具有n个关键字，则叶子结点即查找不成功的结点为__________。M阶的B-树的生成是从空树开始的，逐个插入关键字。但由于B-树所有非终端结点（除根结点）中的关键字个数必须大于或等于__________，因此，每次插入一个关键字不是在树中添加一个__________结点，而是首先在最低层的某个__________结点添加一个关键字，若该结点的关键字个数不超过__________，则插入完成，否则要产生结点的__________。反之，若在m阶的B-树上删除一个关键字，则首先找到该关键字所在的结点，并从中删除之。若该结点为最下层的__________结点，且其中的关键字数目不少于__________，则删除完成，否则要进行__________结点的操作。 30、长度为225的表，采用分块查找法，每块的最佳长度是__________，应分 块，若每块的长度为10，则平均查找长度为 。 31、已知有序表为(13,17,20,32,48,54,65,79,86,91,97)，当采用折半查找法查找86时需进行 次比较可确定查找成功。查找48时需进行 次比较可确定查找成功，查找100时需进行 次比较才能确定查找不成功。 32、在平衡二叉树上删除一个结点后可以通过旋转使其平衡，最坏情况下需要进行 次旋转。 33、高度为5（包括叶子层）的三阶B-树至少有 个结点。 34、在B-树上进行查找的过程是一个 和 交叉进行的过程。 35、向一棵m阶B-树插入结点时，当结点的关键字个数为 时，需要进行分裂该结点。删除时，结点中关键字个数为 时，可能需要和左或右兄弟合并。 四、 简答题 1、 简述顺序查找、折半查找和分块检索法对被检索表中元素中的要求。若检索表中每个元素概率相同， 则对一个长度为n的表，用上面三种方法检索时平均查找长度为多少？ 2、 画出长度为10的有序表进行折半查找的一棵判定树，并求其等概率下的平均查找长度。 3、 有一个10000项线性表，若采用分区查找，问分成多少块较理想？平均查找长度为多少？若每块为 40 ，则平均查找长度为多少？ 4、 输入一组关键字{17，31，13，11，20，35，25，8，4，11，24，40，27}，画出由此生成的二叉排 序树，如果对每个结点的查找概率相等，求其ASL，并分别画出下列操作后的二叉排序树。（1）插入数据9；（2）删除结点17；（3）再删除结点13。 5、 设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H(key)=key， 采用开放地址法的线性探测再散列方法解决冲突，试在0到18的Hash地址空间中对该关键字序列构造Hash表。 6、 若哈希表的地址范围为0到9，Hash函数为H(key)=(key2+2)mod 9,并采用链地址法处理冲突，画出 元素7，4，5，3，6，2，8，9依次插入哈希表以后该哈希表的状态。 7、已知有长度为9的表(16,29,32,5,89,41,14,65,34)，它们存储在一个哈希表中，利用线性探测再散列，要求它在等概率情况下查找成功的平均查找长度不超过3，（1）该哈希表的长度m应设计多大?（2）设计相应的哈希函数；（3）将数据填入到哈希表中；（4）计算查找成功时的平均查找长度。 8、试推导含有12个结点的平衡二叉树的最大深度，并画出一棵这样的树。 9、假定有n个关键字，它们具有相同的哈希函数值，用线性探测方法把这n个关键字存入到哈希表中要做多少次探测？ 10、地址空间为0—14的散列表中，对关键字序列(JAN，FEB，MAR，APR，MAY，JUN，JUL，AUG，SEP，OCT，NOV，DEC)构造哈希函数：H(Key)=?i/2?，其中i为关键字中第一个字母在字母表中的序号。用如下两种处理冲突的方法：（1）线性探测法（2）链地址法 分别求出这两个哈希表在等概率情况下查找成功和不成功的平均查找长度。 11、有一个400项的表，欲采用索引顺序查找方法进行查找，问 （1）分成多少块最为理想？（2）每块的理想长度是什么？（3）平均查找长度是多少？ 12、设有一组关键字(19，05，21，24，45，20，68，27，70，11，10)，采用哈希函数： H(Key)=Key，采用线性探测再散列方法解决冲突，试在0到14的散列地址空间中对该关键字序列构造哈希函数。并求查找成功和不成功时的平均查找长度。 13、线性表的关键字集合(47，26，120，08，39，68，96，23，70，63，57)，已知散列函数为：H(Key)=Key，采用拉链法处理冲突。设计出这种链表结构，并计算该表的查找成功和不成功的平均查找长度。 14、建立一棵具有13个结点的判定树，并求其成功和不成功的平均查找长度值各为多少。 15、分别画出在线性表(06，10，19，24，37，42，50，83)中进行折半查找，查找关键字10和30的过程。 16、已知关键字序列为(10，20，52，58，60，70，75)，依照此顺序建立一棵３阶B-树（2-3树），画出建立的主要过程及结果树。 17、设二叉排序树中的关键字由1到100内的整数构成，现要查找关键字为63的结点，下述关键字序列哪一个是不可能在二叉排序树上查找到的序列。 （1）12，25，71，68，33，34，37，63 （2）92，20，91，24，88，25，36，63 （3）95，22，91，24，94，25，63 （4）21，89，77，29，36，38，41，47，63 18、给定表(25，18，48，07，76，52，81，70，92，15)。 （1）试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成之后的二叉排序树。 （2）按表中元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。 19、二叉排序树中关键字互不相同，则其中最小元无左孩子，最大元无右孩子，此命题是否正确？最小元 和最大元一定是叶子吗？一个新结点总是插在二叉排序树的某叶子上吗？ 20、画出依次插入z,v,w,y到图9.2所示的5阶B-树的过程。再画出依次删除t,m,b到图9.2所示的5阶B-树的过程。 i c f l o r a b d e g h j k s t u x m n p q 图9.2 21、试证明：高度为h的2-3树（3阶B-树）中叶子结点的数目在2h-1与3h-1之间。 22、在含有n个关键字的m阶B-树中进行查找时，最多访问多少个结点？ 五、算法设计题 1. 假设顺序表按关键字从小到大有序，设计顺序查找算法，将监视哨兵设在高下标端，然后分别求出等概率情况下查找成功和不成功的平均查找长度。 2. 若线性表中各结点的查找概率不相等，则可用以下策略提高顺序查找的效率：若找到指定的结点，将该结点和其后继结点交换，使得经常被查到的结点尽量位于表的后端。试设计线性表的顺序存储结构下实现上述策略的查找算法。 3. 假设顺序表按关键字从小到大有序，设计折半查找的递归算法。 4. 设单链表（不带头结点）的结点是按关键字从小到大排列的，试写出对此链表的查找算法，并说明是否可以采用二分查找。 5. 已知某哈希表的装填因子小于1，哈希函数h（key）为key的第一个字母在字母表中的序号，处理冲突的方法为线性探测法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。 6. 设计一个算法，求出指定结点在给定的二叉排序树中所在的层。 7. 试写一个判别给定二叉树是否为二叉排序树的算法，设二叉树以二叉树链表存储表示。 8. 试写一递归算法，从大到小输出二叉排序树中所有其值不小于x的关键字。 9. 试编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结点A、B中，A是B的祖先，则认为A、B的最近公共祖先就是A）。 10. 已知一棵二叉排序树上所有关键字中的最小值为-max,最大值为max，又-max 12 已知二叉树T的结点形式为(lchild,data,count,rchild),在树中查找值为x的结点，若找到，则记数count加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。 13 二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。 14 试设计在二叉排序树中删除关键字为k的结点的算法。 15 考虑用双向链表来实现一个有序表，使得能在这个表中进行正向和反向搜索。若指针p总是指向最后成功搜索到的结点，搜索可以从p指示的结点出发沿任一方向进行。试根据这种情况编写一个函数search(head,p,key)，检索具有关键字key的结点，并相应地修改p。 第十章：内部排序练习题 一、 选择题 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）中满足条件ak 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]，对每个记录