李冬梅 2015.3
目 录 第1章 绪论 1 第2章 线性表 5 第3章 栈和队列 13 第4章 串、数组和广义表 26 第5章 树和二叉树 33 第6章 图 43 第7章 查找 54 第8章 排序 65
1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’， ‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。
3．简述逻辑结构的四种基本关系并画出它们的关系图。
答案： （1）集合结构 数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。 （2）线性结构 数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。 （3）树结构 数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每位组长管理多名组员，从而构成树形结构。 （4）图结构或网状结构 数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图形结构或网状结构。 其中树结构和图结构都属于非线性结构。
4．存储结构由哪两种基本的存储方法实现？
答案： （1）顺序存储结构 顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。 （2）链式存储结构 顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。
答案：C
（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。 A．存储结构 B．存储实现 C．逻辑结构 D．运算实现答案：C
（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等答案：B
（4）以下说法正确的是（ ）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构答案：D 解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。
（5）算法的时间复杂度取决于（ ）。 A．问题的规模 B．待处理数据的初态 C．计算机的配置 D．A和B答案：D 解释：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。
（6）以下数据结构中，（ ）是非线性数据结构 A．树 B．字符串 C．队列 D．栈答案：A
6．试分析下面各程序段的时间复杂度。 （1）x=90; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++;答案：O(1) 解释：程序的执行次数为常数阶。
（2）for (i=0; i<n; i++) for (j=0; j<m; j++) a[i][j]=0;答案：O(mn) 解释：语句a[i][j]=0;的执行次数为mn。
（3）s=0; for i=0; i<n; i++) for(j=0; j<n; j++) s+=B[i][j]; sum=s;答案：O(n2) 解释：语句s+=B[i][j];的执行次数为n2。
（4）i=1; while(i<=n) i=i*3;答案：O(log3n) 解释：语句i=i*3;的执行次数为 log3n。
（5）x=0; for(i=1; i<n; i++) for (j=1; j<=n-i; j++) x++;答案：O(n2) 解释：语句x++;的执行次数为n-1+n-2+……＋1= n(n-1)/2。
（6）x=n; //n>1 y=0; while(x≥(y+1)* (y+1)) y++;答案：O( ) 解释：语句y++;的执行次数为 。
答案：B 解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。
（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。 A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B．在第i个结点后插入一个新结点（1≤i≤n） C．删除第i个结点（1≤i≤n） D．将n个结点从小到大排序答案：A 解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。
（3） 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 的元素个数为（ ）。 A．8 B．63.5 C．63 D．7答案：B 解释：平均要移动的元素个数为：n/2。
（4）链接存储的存储结构所占存储空间（ ）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A
（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。 A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续或不连续都可以答案：D
（6）线性表Ｌ在（ ）情况下适用于使用链式结构实现。 A．需经常修改Ｌ中的结点值 Ｂ．需不断对Ｌ进行删除插入 C．Ｌ中含有大量的结点 Ｄ．Ｌ中结点结构复杂答案：B 解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。
（7）单链表的存储密度（ ）。 A．大于1 B．等于1 C．小于1 D．不能确定答案：C 解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为：D/(D+N)，一定小于1。
（8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。 A．n B．2n-1 C．2n D．n-1答案：A 解释：当第一个有序表中所有的元素都小于（或大于）第二个表中的元素，只需要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较n次。
（9）在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（ ）个元素。 A．n-i B．n-i+1 C．n-i-1 D．I答案：B
(10) 线性表L=(a1，a2,……an)，下列说法正确的是（ ）。 A．每个元素都有一个直接前驱和一个直接后继 B．线性表中至少有一个元素 C．表中诸元素的排列必须是由小到大或由大到小 D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。答案：D
(11) 创建一个包括n个结点的有序单链表的时间复杂度是（ ）。 A．O(1) B．O(n) C．O(n2) D．O(nlog2n)答案：C 解释：单链表创建的时间复杂度是O(n)，而要建立一个有序的单链表，则每生成一个新结点时需要和已有的结点进行比较，确定合适的插入位置，所以时间复杂度是O(n2)。
(12) 以下说法错误的是（ ）。 A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 B．顺序存储的线性表可以随机存取 C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 D．线性表的链式存储结构优于顺序存储结构答案：D 解释：链式存储结构和顺序存储结构各有优缺点，有不同的适用场合。
(13) 在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（ ）。 A．s->next=p+1; p->next=s; B．(*p).next=s; (*s).next=(*p).next; C．s->next=p->next; p->next=s->next; D．s->next=p->next; p->next=s;答案：D
(14) 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。 A．p->next->prior=p->prior; p->prior->next=p->next; B．p->next=p->next->next; p->next->prior=p; C．p->prior->next=p; p->prior=p->prior->prior; D．p->prior=p->next->next; p->next=p->prior->prior;答案：A
(15) 在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ ）。 A．p->next=q; q->prior=p; p->next->prior=q; q->next=q; B．p->next=q; p->next->prior=q; q->prior=p; q->next=p->next; C．q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; D．q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;答案：C
（1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。
[题目分析] 合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后表中无重复的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在Lc表的最后。 [算法描述]
void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) {//合并链表La和Lb，合并后的新表使用头指针Lc指向 pa=La->next; pb=Lb->next; //pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa && pb) {if(pa->data<pb->data){pc->next=pa;pc=pa;pa=pa->next;} //取较小者La中的元素，将pa链接在pc的后面，pa指针后移 else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;} //取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移 else //相等时取La中的元素，删除Lb中的元素 {pc->next=pa;pc=pa;pa=pa->next; q=pb->next;delete pb ;pb =q; } } pc->next=pa?pa:pb; //插入剩余段 delete Lb; //释放Lb的头结点 }（2）将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。
[题目分析] 合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的表头结点之后，如果两个表中的元素相等，只摘取La表中的元素，保留Lb表中的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素依次摘取，链接在Lc表的表头结点之后。 [算法描述]
void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, ) {//合并链表La和Lb，合并后的新表使用头指针Lc指向 pa=La->next; pb=Lb->next; //pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 Lc=pc=La; //用La的头结点作为Lc的头结点 Lc->next=NULL; while(pa||pb ) {//只要存在一个非空表，用q指向待摘取的元素 if(!pa) {q=pb; pb=pb->next;} //La表为空，用q指向pb，pb指针后移 else if(!pb) {q=pa; pa=pa->next;} //Lb表为空，用q指向pa，pa指针后移 else if(pa->data<=pb->data) {q=pa; pa=pa->next;} //取较小者（包括相等）La中的元素，用q指向pa，pa指针后移 else {q=pb; pb=pb->next;} //取较小者Lb中的元素，用q指向pb，pb指针后移 q->next = Lc->next; Lc->next = q; //将q指向的结点插在Lc 表的表头结点之后 } delete Lb; //释放Lb的头结点 }（3）已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出A与B的交集，并存放于A链表中。
[题目分析] 只有同时出现在两集合中的元素才出现在结果表中,合并后的新表使用头指针Lc指向。pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，如果两个表中相等的元素时，摘取La表中的元素，删除Lb表中的元素；如果其中一个表中的元素较小时，删除此表中较小的元素，此表的工作指针后移。当链表La和Lb有一个到达表尾结点，为空时，依次删除另一个非空表中的所有元素。 [算法描述]
void Mix(LinkList& La, LinkList& Lb, LinkList& Lc) { pa=La->next;pb=Lb->next; pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa&&pb) { if(pa->data==pb->data)∥交集并入结果表中。 { pc->next=pa;pc=pa;pa=pa->next; u=pb;pb=pb->next; delete u;} else if(pa->data<pb->data) {u=pa;pa=pa->next; delete u;} else {u=pb; pb=pb->next; delete u;} } while(pa) {u=pa; pa=pa->next; delete u;}∥ 释放结点空间 while(pb) {u=pb; pb=pb->next; delete u;}∥释放结点空间 pc->next=null;∥置链表尾标记。 delete Lb; //释放Lb的头结点 }（4）已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B 的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。
[题目分析] 求两个集合A和B的差集是指在A中删除A和B中共有的元素，即删除链表中的相应结点,所以要保存待删除结点的前驱，使用指针pre指向前驱结点。pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，如果La表中的元素小于Lb表中的元素，pre置为La表的工作指针pa删除Lb表中的元素；如果其中一个表中的元素较小时，删除此表中较小的元素，此表的工作指针后移。当链表La和Lb有一个为空时，依次删除另一个非空表中的所有元素。 [算法描述]
void Difference（LinkList& La, LinkList& Lb,int *n） {∥差集的结果存储于单链表La中，*n是结果集合中元素个数，调用时为0 pa=La->next; pb=Lb->next; ∥pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 pre=La; ∥pre为La中pa所指结点的前驱结点的指针 while（pa&&pb） {if（pa->data<q->data）{pre=pa;pa=pa->next;*n++;} ∥ A链表中当前结点指针后移 else if（pa->data>q->data）q=q->next; ∥B链表中当前结点指针后移 else {pre->next=pa->next; ∥处理A，B中元素值相同的结点，应删除 u=pa; pa=pa->next; delete u;} ∥删除结点 } }（5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）。
[题目分析] B表的头结点使用原来A表的头结点，为C表新申请一个头结点。从A表的第一个结点开始，依次取其每个结点p，判断结点p的值是否小于0，利用前插法，将小于0的结点插入B表,大于等于0的结点插入C表。 [算法描述]
void DisCompose(LinkedList A) { B=A; B->next= NULL; ∥B表初始化 C=new LNode;∥为C申请结点空间 C->next=NULL; ∥C初始化为空表 p=A->next; ∥p为工作指针 while(p!= NULL) { r=p->next; ∥暂存p的后继 if(p->data<0) {p->next=B->next; B->next=p; }∥将小于0的结点链入B表,前插法 else {p->next=C->next; C->next=p; }∥将大于等于0的结点链入C表,前插法 p=r;∥p指向新的待处理结点。 } }（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。
[题目分析] 假定第一个结点中数据具有最大值，依次与下一个元素比较，若其小于下一个元素，则设其下一个元素为最大值，反复进行比较，直到遍历完该链表。 [算法描述]
ElemType Max (LinkList L ){ if(L->next==NULL) return NULL; pmax=L->next; //假定第一个结点中数据具有最大值 p=L->next->next; while(p != NULL ){//如果下一个结点存在 if(p->data > pmax->data) pmax=p;//如果p的值大于pmax的值，则重新赋值 p=p->next;//遍历链表 } return pmax->data;（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。
[题目分析] 从首元结点开始，逐个地把链表L的当前结点p插入新的链表头部。 [算法描述]
void inverse(LinkList &L) {// 逆置带头结点的单链表 L p=L->next; L->next=NULL; while ( p) { q=p->next; // q指向*p的后继 p->next=L->next; L->next=p; // *p插入在头结点之后 p = q; } }（8）设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同 ）。
[题目分析] 分别查找第一个值>mink的结点和第一个值 ≥maxk的结点，再修改指针，删除值大于mink且小于maxk的所有元素。 [算法描述]
void delete(LinkList &L, int mink, int maxk) { p=L->next; //首元结点 while (p && p->data<=mink) { pre=p; p=p->next; } //查找第一个值>mink的结点 if (p) {while (p && p->data<maxk) p=p->next; // 查找第一个值 ≥maxk的结点 q=pre->next; pre->next=p; // 修改指针 while (q!=p) { s=q->next; delete q; q=s; } // 释放结点空间 }//if }（9）已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，写出算法change§,交换p所指向的结点和它的前缀结点的顺序。
[题目分析] 知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（p结点，前驱结点，前驱的前驱结点，后继结点）六条链。 [算法描述]
void Exchange（LinkedList p） ∥p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。 {q=p->llink； q->llink->rlink=p； ∥p的前驱的前驱之后继为p p->llink=q->llink； ∥p的前驱指向其前驱的前驱。 q->rlink=p->rlink； ∥p的前驱的后继为p的后继。 q->llink=p； ∥p与其前驱交换 p->rlink->llink=q； ∥p的后继的前驱指向原p的前驱 p->rlink=q； ∥p的后继指向其原来的前驱 }∥算法exchange结束。（10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。
[题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。 [算法描述]
void Delete（ElemType A[ ]，int n） ∥A是有n个元素的一维数组，本算法删除A中所有值为item的元素。 {i=1；j=n；∥设置数组低、高端指针（下标）。 while（i<j） {while（i<j && A[i]!=item）i++； ∥若值不为item，左移指针。 if（i<j）while（i<j && A[j]==item）j--；∥若右端元素为item，指针左移 if（i<j）A[i++]=A[j--]；}答案：C 解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。 （2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ）。 A．i B．n-i C．n-i+1 D．不确定 答案：C 解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。 （3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）。 A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n 答案：D 解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。 （4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（ ）。 A．x=top->data;top=top->link； B．top=top->link;x=top->link； C．x=top;top=top->link； D．x=top->link； 答案：A 解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。 （5）设有一个递归算法如下 int fact(int n) { //n大于等于0 if(n<=0) return 1; else return n*fact(n-1); } 则计算fact(n)需要调用该函数的次数为（ ）。 A． n+1 B． n-1 C． n D． n+2 答案：A 解释：特殊值法。设n=0，易知仅调用一次fact(n)函数，故选A。 （6）栈在 （ ）中有所应用。 A．递归调用 B．函数调用 C．表达式求值 D．前三个选项都有 答案：D 解释：递归调用、函数调用、表达式求值均用到了栈的后进先出性质。 （7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。 A．队列 B．栈 C． 线性表 D．有序表 答案：A 解释：解决缓冲区问题应利用一种先进先出的线性表，而队列正是一种先进先出的线性表。 （8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（ ）。 A．2 B．3 C．4 D． 6 答案：B 解释：元素出队的序列是e2、e4、e3、e6、e5和e1，可知元素入队的序列是e2、e4、e3、e6、e5和e1，即元素出栈的序列也是e2、e4、e3、e6、e5和e1，而元素e1、e2、e3、e4、e5和e6依次进入栈，易知栈S中最多同时存在3个元素，故栈S的容量至少为3。 （9）若一个栈以向量V[1…n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是( )。 A．top++; V[top]=x; B．V[top]=x; top++; C．top–; V[top]=x; D．V[top]=x; top–; 答案：C 解释：初始栈顶指针top为n+1，说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间V[1…n]中，所以进栈时top指针先下移变为n，之后将元素x存储在V[n]。 （10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。 A．线性表的顺序存储结构 B．队列 C. 线性表的链式存储结构 D. 栈 答案：D 解释：利用栈的后进先出原则。 （11）用链接方式存储的队列，在进行删除运算时（ ）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 答案：D 解释：一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值。 （12）循环队列存储在数组A[0…m]中，则入队时的操作为（ ）。 A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) 答案：D 解释：数组A[0…m]中共含有m+1个元素，故在求模运算时应除以m+1。 （13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。 A. (rear+1)%nfront B. rearfront C．rear+1front D. (rear-l)%nfront 答案：B 解释：最大容量为n的循环队列，队满条件是(rear+1)%nfront，队空条件是rearfront。 （14）栈和队列的共同点是（ ）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 答案：C 解释：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头删除元素。 （15）一个递归算法必须包括（ ）。 A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部分 答案：B
2．算法设计题 （1）将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下： Typedef struct {int top[2],bot[2]; //栈顶和栈底指针 SElemType *V; //栈数组 int m; //栈最大可容纳元素个数 }DblStack [题目分析] 两栈共享向量空间，将两栈栈底设在向量两端，初始时，左栈顶指针为-1，右栈顶为m。两栈顶指针相邻时为栈满。两栈顶相向、迎面增长，栈顶指针指向栈顶元素。 [算法描述] (1) 栈初始化 int Init() {S.top[0]=-1; S.top[1]=m; return 1; //初始化成功 } (2) 入栈操作： int push(stk S ,int i,int x) ∥i为栈号，i=0表示左栈，i=1为右栈，x是入栈元素。入栈成功返回1，失败返回0 {if(i<0||i>1){ cout<<“栈号输入不对”<<endl;exit(0);} if(S.top[1]-S.top[0]1) {cout<<“栈已满”<<endl;return(0);} switch(i) {case 0: S.V[++S.top[0]]=x; return(1); break; case 1: S.V[–S.top[1]]=x; return(1); } }∥push (3) 退栈操作 ElemType pop(stk S,int i) ∥退栈。i代表栈号，i=0时为左栈，i=1时为右栈。退栈成功时返回退栈元素 ∥否则返回-1 {if(i<0 || i>1){cout<<“栈号输入错误”<<endl；exit(0);} switch(i) {case 0: if(S.top[0]-1) {cout<<“栈空”<<endl；return（-1）；} else return(S.V[S.top[0]–]); case 1: if(S.top[1]m { cout<<“栈空”<<endl; return(-1);} else return(S.V[S.top[1]++]); }∥switch }∥算法结束 (4) 判断栈空 int Empty(); {return (S.top[0]-1 && S.top[1]==m); } [算法讨论] 请注意算法中两栈入栈和退栈时的栈顶指针的计算。左栈是通常意义下的栈，而右栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。
（2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) [题目分析] 将字符串前一半入栈，然后，栈中元素和字符串后一半进行比较。即将第一个出栈元素和后一半串中第一个字符比较，若相等，则再出栈一个元素与后一个字符比较，……，直至栈空，结论为字符序列是回文。在出栈元素与串中字符比较不等时，结论字符序列不是回文。 [算法描述] #define StackSize 100 //假定预分配的栈空间最多为100个元素 typedef char DataType;//假定栈元素的数据类型为字符 typedef struct {DataType data[StackSize]; int top; }SeqStack;
int IsHuiwen( char *t) {//判断t字符向量是否为回文，若是，返回1，否则返回0 SeqStack s; int i , len; char temp; InitStack( &s); len=strlen(t); //求向量长度 for ( i=0; i<len/2; i++)//将一半字符入栈 Push( &s, t[i]); while( !EmptyStack( &s)) {// 每弹出一个字符与相应字符比较 temp=Pop (&s); if( temp!=S[i]) return 0 ;// 不等则返回0 else i++; } return 1 ; // 比较完毕均相等则返回 1 } （3）设从键盘输入一整数的序列：a1, a2, a3，…，an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。 [算法描述] #define maxsize 栈空间容量 void InOutS(int s[maxsize]) //s是元素为整数的栈，本算法进行入栈和退栈操作。 {int top=0; //top为栈顶指针，定义top=0时为栈空。 for(i=1; i<=n; i++) //n个整数序列作处理。 {cin>>x); //从键盘读入整数序列。 if(x!=-1) // 读入的整数不等于-1时入栈。 ｛if(topmaxsize-1){cout<<“栈满”<<endl;exit(0);} else s[++top]=x; //x入栈。 ｝ else //读入的整数等于-1时退栈。 {if(top0){ cout<<“栈空”<<endl;exit(0);} else cout<<“出栈元素是”<< s[top–]<<endl;} } }//算法结束。
（4）从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行，以 符 作 为 输 入 结 束 ， 操 作 数 之 间 用 空 格 分 隔 , 操 作 符 只 可 能 有 + 、 − 、 ∗ 、 / 四 种 运 算 。 例 如 ： 23434 + 2 ∗ 符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2* 符作为输入结束，操作数之间用空格分隔,操作符只可能有+、−、∗、/四种运算。例如：23434+2∗。 [题目分析] 逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈OPND,对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPND栈。当扫描到运算符时，从OPND退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符 ， 这 时 O P N D 栈 中 只 有 一 个 数 ， 就 是 结 果 。 [ 算 法 描 述 ] f l o a t e x p r ( ) / / 从 键 盘 输 入 逆 波 兰 表 达 式 ， 以 ‘ ，这时OPND栈中只有一个数，就是结果。 [算法描述] float expr( ) //从键盘输入逆波兰表达式，以‘ ，这时OPND栈中只有一个数，就是结果。[算法描述]floatexpr()//从键盘输入逆波兰表达式，以‘’表示输入结束，本算法求逆波兰式表达式的值。 ｛float OPND[30]; // OPND是操作数栈。 init(OPND); //两栈初始化。 float num=0.0; //数字初始化。 cin>>x;//x是字符型变量。 while(x!=’KaTeX parse error: Expected '}', got '&' at position 51: …: while((x>=’0’&̲&x<=’9’)||x==’.…’） cout<<“后缀表达式的值为”<<pop(OPND); }//算法结束。 [算法讨论]假设输入的后缀表达式是正确的，未作错误检查。算法中拼数部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符，认为是数。这种字符的序号减去字符‘0’的序号得出数。对于整数，每读入一个数字字符，前面得到的部分数要乘上10再加新读入的数得到新的部分数。当读到小数点，认为数的整数部分已完，要接着处理小数部分。小数部分的数要除以10（或10的幂数）变成十分位，百分位，千分位数等等，与前面部分数相加。在拼数过程中，若遇非数字字符，表示数已拼完，将数压入栈中，并且将变量num恢复为0，准备下一个数。这时对新读入的字符进入‘+’、‘-’、‘*’、‘/’及空格的判断，因此在结束处理数字字符的case后，不能加入break语句。
（5）假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 ①下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO ②通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。 答案： ①A和D是合法序列，B和C 是非法序列。 ②设被判定的操作序列已存入一维数组A中。 int Judge(char A[]) //判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。 {i=0; //i为下标。 j=k=0; //j和k分别为I和字母O的的个数。 while(A[i]!=‘\0’) //当未到字符数组尾就作。 {switch(A[i]) {case‘I’: j++; break; //入栈次数增1。 case‘O’: k++; if(k>j){cout<<“序列非法”<<ednl；exit(0);} } i++; //不论A[i]是‘I’或‘O’，指针i均后移。} if(j!=k) {cout<<“序列非法”<<endl；return(false);} else { cout<<“序列合法”<<endl；return(true);} }//算法结束。 [算法讨论]在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置，入栈次数（‘I’的个数）都必须大于等于出栈次数（即‘O’的个数），否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串的结束标记‘\0’），入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空），否则视为非法序列。
(6）假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。 [题目分析] 置空队就是建立一个头节点，并把头尾指针都指向头节点，头节点是不存放数据的；判队空就是当头指针等于尾指针时，队空；入队时，将新的节点插入到链队列的尾部，同时将尾指针指向这个节点；出队时，删除的是队头节点，要注意队列的长度大于1还是等于1的情况，这个时候要注意尾指针的修改，如果等于1，则要删除尾指针指向的节点。 [算法描述] //先定义链队结构: typedef struct queuenode {Datatype data; struct queuenode *next; }QueueNode; //以上是结点类型的定义 typedef struct {queuenode *rear; }LinkQueue; //只设一个指向队尾元素的指针
(1) 置空队 void InitQueue( LinkQueue *Q) { //置空队：就是使头结点成为队尾元素 QueueNode *s; Q->rear = Q->rear->next;//将队尾指针指向头结点 while (Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队 {s=Q->rear->next; Q->rear->next=s->next; delete s; }//回收结点空间 }
(2) 判队空 int EmptyQueue( LinkQueue *Q) { //判队空。当头结点的next指针指向自己时为空队 return Q->rear->next->next==Q->rear->next; }
(3) 入队 void EnQueue( LinkQueue *Q, Datatype x) { //入队。也就是在尾结点处插入元素 QueueNode *p=new QueueNode;//申请新结点 p->data=x; p->next=Q->rear->next;//初始化新结点并链入 Q-rear->next=p; Q->rear=p;//将尾指针移至新结点 }
(4) 出队 Datatype DeQueue( LinkQueue *Q) {//出队,把头结点之后的元素摘下 Datatype t; QueueNode *p; if(EmptyQueue( Q )) Error(“Queue underflow”); p=Q->rear->next->next; //p指向将要摘下的结点 x=p->data; //保存结点中数据 if (p==Q->rear) {//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点 Q->rear = Q->rear->next; Q->rear->next=p->next; } else Q->rear->next->next=p->next;//摘下结点p delete p;//释放被删结点 return x; }
（7）假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。 [算法描述] (1)初始化 SeQueue QueueInit(SeQueue Q) {//初始化队列 Q.front=Q.rear=0; Q.tag=0; return Q; } (2)入队 SeQueue QueueIn(SeQueue Q,int e) {//入队列 if((Q.tag1) && (Q.rearQ.front)) cout<<“队列已满”<<endl; else {Q.rear=(Q.rear+1) % m; Q.data[Q.rear]=e; if(Q.tag0) Q.tag=1; //队列已不空 } return Q; } (3)出队 ElemType QueueOut(SeQueue Q) {//出队列 if(Q.tag0) { cout<<“队列为空”<<endl; exit(0);} else {Q.front=(Q.front+1) % m; e=Q.data[Q.front]; if(Q.front==Q.rear) Q.tag=0; //空队列 } return(e); }
(8）如果允许在循环队列的两端都可以进行插入和删除操作。要求： ① 写出循环队列的类型定义； ② 写出“从队尾删除”和“从队头插入”的算法。 [题目分析] 用一维数组 v[0…M-1]实现循环队列，其中M是队列长度。设队头指针 front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队空，(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。 [算法描述] ① #define M 队列可能达到的最大长度 typedef struct {elemtp data[M]; int front,rear; }cycqueue; ② elemtp delqueue ( cycqueue Q) //Q是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，否则给出出错信息。 {if (Q.front==Q.rear) { cout<<“队列空”<<endl; exit(0);} Q.rear=(Q.rear-1+M)%M; //修改队尾指针。 return(Q.data[(Q.rear+1+M)%M]); //返回出队元素。 }//从队尾删除算法结束
void enqueue (cycqueue Q, elemtp x) // Q是顺序存储的循环队列，本算法实现“从队头插入”元素x。 {if (Q.rear==(Q.front-1+M)%M) { cout<<“队满”<<endl; exit(0)😉 Q.data[Q.front]=x; //x 入队列 Q.front=(Q.front-1+M)%M; //修改队头指针。 }// 结束从队头插入算法。
（9）已知Ackermann函数定义如下:
① 写出计算Ack(m,n)的递归算法，并根据此算法给出出Ack(2,1)的计算过程。 ② 写出计算Ack(m,n)的非递归算法。 [算法描述] int Ack(int m,n) {if (m0) return(n+1); else if(m!=0&&n0) return(Ack(m-1,1)); else return(Ack(m-1,Ack(m,m-1)); }//算法结束 ① Ack(2,1)的计算过程 Ack(2,1)= Ack(1,Ack(2,0)) //因m<>0,n<>0而得 = Ack(1,Ack(1,1)) //因m<>0,n=0而得 = Ack(1,Ack(0,Ack(1,0))) // 因m<>0,n<>0而得 = Ack(1,Ack(0,Ack(0,1))) // 因m<>0,n=0而得 = Ack(1,Ack(0,2)) // 因m=0而得 = Ack(1,3) // 因m=0而得 = Ack(0,Ack(1,2)) //因m<>0,n<>0而得 = Ack(0,Ack(0,Ack(1,1))) //因m<>0,n<>0而得 = Ack(0,Ack(0,Ack(0,Ack(1,0)))) //因m<>0,n<>0而得 = Ack(0,Ack(0,Ack(0,Ack(0,1)))) //因m<>0,n=0而得 = Ack(0,Ack(0,Ack(0,2))) //因m=0而得 = Ack(0,Ack(0,3)) //因m=0而得 = Ack(0,4) //因n=0而得 =5 //因n=0而得 ② int Ackerman(int m, int n) {int akm[M][N];int i,j; for(j=0;j<N;j++) akm[0][j]=j+1; for(i=1;i<m;i++) {akm[i][0]=akm[i-1][1]; for(j=1;j<N;j++) akm[i][j]=akm[i-1][akm[i][j-1]]; } return(akm[m][n]); }//算法结束
（10）已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法： ① 求链表中的最大整数； ② 求链表的结点个数； ③ 求所有整数的平均值。 [算法描述] ① int GetMax(LinkList p) { if(!p->next) return p->data; else { int max=GetMax(p->next); return p->data>=max ? p->data:max; } } ② int GetLength(LinkList p) { if(!p->next) return 1; else { return GetLength(p->next)+1; } } ③ double GetAverage(LinkList p , int n) { if(!p->next) return p->data; else { double ave=GetAverage(p->next,n-1); return (ave*(n-1)+p->data)/n; } }
第4章 串、数组和广义表 1．选择题 （1）串是一种特殊的线性表，其特殊性体现在（ ）。 A．可以顺序存储 B．数据元素是一个字符 C．可以链式存储 D．数据元素可以是多个字符若 答案：B （2）串下面关于串的的叙述中，（ ）是不正确的？ A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 答案：B 解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串，零个字符的串成为空串，其长度为零。 （3）串“ababaaababaa”的next数组为（ ）。 A．012345678999 B．012121111212 C．011234223456 D．0123012322345 答案：C （4）串“ababaabab”的nextval为（ ）。 A．010104101 B．010102101 C．010100011 D．010101011 答案：A （5）串的长度是指（ ）。 A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 答案：B 解释：串中字符的数目称为串的长度。 （6）假设以行序为主序存储二维数组A=array[1…100,1…100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（ ）。 A．808 B．818 C．1010 D．1020 答案：B 解释：以行序为主，则LOC[5,5]=[（5-1）100+（5-1）]2+10=818。 （7）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（ ）。 A．BA+141 B．BA+180 C．BA+222 D．BA+225 答案：B 解释：以列序为主，则LOC[5,8]=[（8-1）8+（5-1）]3+BA=BA+180。 （8）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 A．13 B．32 C．33 D．40 答案：C （9）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1…(n(n+1))/2]中，则在B中确定aij（i<j）的位置k的关系为（ ）。 A．i(i-1)/2+j B．j(j-1)/2+i C．i(i+1)/2+j D．j(j+1)/2+i 答案：B （10）二维数组A的每个元素是由10个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。 A．A[8,5] B．A[3,10] C. A[5,8] D．A[0,9] 答案：B 解释：设数组从内存首地址M开始顺序存放，若数组按行先存储，元素A[8,5]的起始地址为：M+[（8-0）*10+（5-1）]1=M+84；若数组按列先存储，易计算出元素A[3,10]的起始地址为：M+[（10-1）9+（3-0）]1=M+84。故选B。 （11）设二维数组A[1… m，1… n]（即m行n列）按行存储在数组B[1… mn]中，则二维数组元素A[i,j]在一维数组B中的下标为（ ）。 A．(i-1)n+j B．(i-1)n+j-1 C．i(j-1) D．jm+i-1 答案：A 解释：特殊值法。取i=j=1，易知A[1,1]的的下标为1，四个选项中仅有A选项能确定的值为1，故选A。 （12）数组A[0…4,-1…-3,5…7]中含有元素的个数（ ）。 A．55 B．45 C．36 D．16 答案：B 解释：共有533=45个元素。 （13）广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。 A．(g) B．(d) C．c D．d 答案：D 解释：Tail(A)=(b,(c,d),(e,(f,g)))；Tail(Tail(A))=( (c,d),(e,(f,g)))； Head(Tail(Tail(A)))= (c,d)；Tail(Head(Tail(Tail(A))))=(d)；Head(Tail(Head(Tail(Tail(A)))))=d。 （14）广义表((a,b,c,d))的表头是（ ），表尾是（ ）。 A．a B．( ) C．(a,b,c,d) D．(b,c,d) 答案：C、B 解释：表头为非空广义表的第一个元素，可以是一个单原子，也可以是一个子表，((a,b,c,d))的表头为一个子表(a,b,c,d)；表尾为除去表头之外，由其余元素构成的表，表为一定是个广义表，((a,b,c,d))的表尾为空表( )。 （15）设广义表L=((a,b,c))，则L的长度和深度分别为（ ）。 A．1和1 B．1和3 C．1和2 D．2和3 答案：C 解释：广义表的深度是指广义表中展开后所含括号的层数，广义表的长度是指广义表中所含元素的个数。根据定义易知L的长度为1，深度为2。
2．应用题 （1）已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。 答案： 模式串t的next和nextval值如下： j 1 2 3 4 5 6 7 8 9 10 11 12 t串 a b c a a b b a b c a b next[j] 0 1 1 1 2 2 3 1 2 3 4 5 nextval[j] 0 1 1 0 2 1 3 0 1 1 0 5
（2）设目标为t=“abcaabbabcabaacbacba”,模式为p=“abcabaa” ① 计算模式p的naxtval函数值； ② 不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。 答案： ① p的nextval函数值为0110132。（p的next函数值为0111232）。 ② 利用KMP(改进的nextval)算法，每趟匹配过程如下： 第一趟匹配： abcaabbabcabaacbacba abcab(i=5,j=5) 第二趟匹配： abcaabbabcabaacbacba abc(i=7,j=3) 第三趟匹配： abcaabbabcabaacbacba a(i=7,j=1) 第四趟匹配： abcaabbabcabaac bacba (成功) abcabaa(i=15,j=8)
（3）数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求： ① 存放该数组所需多少单元？ ② 存放数组第4列所有元素至少需多少单元？ ③ 数组按行存放时，元素A[7,4]的起始地址是多少？ ④ 数组按列存放时，元素A[4,7]的起始地址是多少？ 答案： 每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。 （1）242 （2）22 （3）s+182 （4）s+142
(4)请将香蕉banana用工具 H( )—Head( )，T( )—Tail( )从L中取出。 L=(apple,(orange,(strawberry,(banana)),peach),pear) 答案：H（H（T（H（T（H（T（L）））））））
3．算法设计题 （1）写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。 [题目分析] 由于字母共26个，加上数字符号10个共36个，所以设一长36的整型数组，前10个分量存放数字字符出现的次数，余下存放字母出现的次数。从字符串中读出数字字符时，字符的ASCII代码值减去数字字符 ‘0’的ASCII代码值，得出其数值(0…9)，字母的ASCII代码值减去字符‘A’的ASCII代码值加上10，存入其数组的对应下标分量中。遇其它符号不作处理，直至输入字符串结束。 [算法描述] void Count（） //统计输入字符串中数字字符和字母字符的个数。 ｛int i，num[36]； char ch； for（i＝0；i<36；i++）num[i]＝０；// 初始化 while（（ch＝getchar（））!=‘#’） //‘#’表示输入字符串结束。 if（‘0’<=ch<=‘9’）｛i=ch－48;num[i]++；｝ // 数字字符 else if（‘A’<=ch<=‘Z’）｛i=ch-65+10;num[i]++；｝// 字母字符 for（i=0；i<10；i++） // 输出数字字符的个数 cout<<“数字”<<i<< “的个数=”<<num[i]<<endl; for（i＝10；i<36；i++）// 求出字母字符的个数 cout<<“字母字符”<<i+55<< “的个数=”<<num[i]<<endl; ｝
（2）写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。 [题目分析]实现字符串的逆置并不难，但本题“要求不另设串存储空间”来实现字符串逆序存储，即第一个输入的字符最后存储，最后输入的字符先存储，使用递归可容易做到。 [算法描述] void InvertStore(char A[]) //字符串逆序存储的递归算法。 {char ch; static int i = 0;//需要使用静态变量 cin>>ch; if (ch!= ‘.’) //规定’.'是字符串输入结束标志 {InvertStore(A); A[i++] = ch;//字符串逆序存储 } A[i] = ‘\0’; //字符串结尾标记 }
（3）编写算法，实现下面函数的功能。函数void insert(chars,chart,int pos)将字符串t插入到字符串s中，插入位置为pos。假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数） [题目分析]本题是字符串的插入问题，要求在字符串s的pos位置，插入字符串t。首先应查找字符串s的pos位置，将第pos个字符到字符串s尾的子串向后移动字符串t的长度，然后将字符串t复制到字符串s的第pos位置后。 对插入位置pos要验证其合法性，小于1或大于串s的长度均为非法，因题目假设给字符串s的空间足够大，故对插入不必判溢出。 [算法描述] void insert(char *s,char *t,int pos) //将字符串t插入字符串s的第pos个位置。 {int i=1,x=0; char *p=s,*q=t; //p，q分别为字符串s和t的工作指针 if(pos<1) {cout<<“pos参数位置非法”<<endl;exit(0);} while(*p!=’\0’&&i<pos) {p++;i++;} //查pos位置 //若pos小于串s长度，则查到pos位置时，i=pos。 if(*p == ‘/0’) { cout<<pos<<“位置大于字符串s的长度”;exit(0);} else //查找字符串的尾 while(*p!= ‘/0’) {p++; i++;} //查到尾时，i为字符‘\0’的下标，p也指向‘\0’。 while(q!= ‘\0’) {q++; x++; } //查找字符串t的长度x，循环结束时q指向’\0’。 for(j=i;j>=pos ;j–){(p+x)=*p; p–;}//串s的pos后的子串右移，空出串t的位置。 q–; //指针q回退到串t的最后一个字符 for(j=1;j<=x;j++) *p–=*q–; //将t串插入到s的pos位置上 [算法讨论] 串s的结束标记(’\0’)也后移了，而串t的结尾标记不应插入到s中。
（4）已知字符串S1中存放一段英文，写出算法format(s1,s2,s3,n),将其按给定的长度n格式化成两端对齐的字符串S2, 其多余的字符送S3。 [题目分析]本题要求字符串s1拆分成字符串s2和字符串s3，要求字符串s2“按给定长度n格式化成两端对齐的字符串”，即长度为n且首尾字符不得为空格字符。算法从左到右扫描字符串s1，找到第一个非空格字符，计数到n，第n个拷入字符串s2的字符不得为空格，然后将余下字符复制到字符串s3中。 [算法描述] void format (char *s1,*s2,*s3) //将字符串s1拆分成字符串s2和字符串s3，要求字符串s2是长n且两端对齐 {char *p=s1, *q=s2; int i=0; while(*p!= ‘\0’ && *p== ’ ‘) p++;//滤掉s1左端空格 if(*p== ‘\0’) {cout<<“字符串s1为空串或空格串”<<endl;exit(0); } while( *p!=’\0’ && i<n){*q=*p; q++; p++; i++;} //字符串s1向字符串s2中复制 if(p ==’\0’){cout<<“字符串s1没有”<<n<<“个有效字符”<<endl; exit(0);} if((–q)’ ’ ) //若最后一个字符为空格，则需向后找到第一个非空格字符 {p-- ; //p指针也后退 while(*p’ ‘&&*p!=’\0’) p++;//往后查找一个非空格字符作串s2的尾字符 if(*p==’\0’) {cout<<“s1串没有”<<n<<“个两端对齐的字符串”<<endl; exit(0);} *q=*p; //字符串s2最后一个非空字符 *(++q)=’\0’; //置s2字符串结束标记 } *q=s3;p++; //将s1串其余部分送字符串s3。 while (*p!= ‘\0’) {*q=*p; q++; p++;} *q=’\0’; //置串s3结束标记 }
（5）设二维数组a[1…m, 1…n] 含有mn 个整数。 ① 写一个算法判断a中所有元素是否互不相同?输出相关信息(yes/no)； ② 试分析算法的时间复杂度。 ① [题目分析]判断二维数组中元素是否互不相同，只有逐个比较,找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次？在当前行，每个元素要同本行后面的元素比较一次（下面第一个循环控制变量p的for循环），然后同第i+1行及以后各行元素比较一次，这就是循环控制变量k和p的二层for循环。 [算法描述] int JudgEqual(ing a[m][n],int m,n) //判断二维数组中所有元素是否互不相同，如是，返回1；否则，返回0。 {for(i=0;i<m;i++) for(j=0;j<n-1;j++) {for(p=j+1;p<n;p++) //和同行其它元素比较 if(a[i][j]==a[i][p]) {cout<<“no”; return(0); } //只要有一个相同的，就结论不是互不相同 for(k=i+1;k<m;k++) //和第i+1行及以后元素比较 for(p=0;p<n;p++) if(a[i][j]==a[k][p]) { cout<<“no”; return(0); } }// for(j=0;j<n-1;j++) cout<<“yes”; return(1); //元素互不相同 }//算法JudgEqual结束 ②二维数组中的每一个元素同其它元素都比较一次，数组中共mn个元素，第1个元素同其它mn-1个元素比较，第2个元素同其它mn-2 个元素比较，……，第mn-1个元素同最后一个元素(mn)比较一次,所以在元素互不相等时总的比较次数为 (mn-1)+(mn-2)+…+2+1=（mn）(mn-1)/2。在有相同元素时,可能第一次比较就相同,也可能最后一次比较时相同,设在(mn-1)个位置上均可能相同,这时的平均比较次数约为（mn）(m*n-1)/4，总的时间复杂度是O(n4)。
(6)设任意n个整数存放于数组A(1:n)中，试编写算法，将所有正数排在所有负数前面（要求算法复杂度为0(n)）。 [题目分析]本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i和j，i自小至大搜索到负数停止，j自大至小搜索到正数停止。然后i和j所指数据交换，继续以上过程，直到 i=j为止。 [算法描述] void Arrange(int A[],int n) //n个整数存于数组A中，本算法将数组中所有正数排在所有负数的前面 {int i=0,j=n-1,x; //用类C编写，数组下标从0开始 while(i<j) {while(i<j && A[i]>0) i++; while(i<j && A[j]<0) j–; if(i<j) {x=A[i]; A[i++]=A[j]; A[j–]=x; }//交换A[i] 与A[j] }// while(i<j) }//算法Arrange结束. [算法讨论]对数组中元素各比较一次，比较次数为n。最佳情况(已排好,正数在前,负数在后)不发生交换，最差情况(负数均在正数前面)发生n/2次交换。用类c编写，数组界偶是0…n-1。空间复杂度为O(1).
第5章 树和二叉树 1．选择题 （1）把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。 A．唯一的 Ｂ．有多种 C．有多种，但根结点都没有左孩子 Ｄ．有多种，但根结点都没有右孩子 答案：A 解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。 （2）由3个结点可以构造出多少种不同的二叉树？（ ） A．2 B．3 C．4 D．5 答案：D 解释：五种情况如下：
（3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。 A．250 B． 500 C．254 D．501 答案：D 解释：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉树的性质可得B=0或1，又因为C为整数，所以B=0，C=500，A=501，即有501个叶子结点。 （4）一个具有1025个结点的二叉树的高h为（ ）。 A．11 B．10 C．11至1025之间 D．10至1024之间 答案：C 解释：若每层仅有一个结点，则树高h为1025；且其最小树高为 log21025 + 1=11，即h在11至1025之间。 （5）深度为h的满m叉树的第k层有（ ）个结点。(1=<k=<h) A．mk-1 B．mk-1 C．mh-1 D．mh-1 答案：A 解释：深度为h的满m叉树共有mh-1个结点，第k层有mk-1个结点。 （6）利用二叉链表存储树，则根结点的右指针是（ ）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 答案：C 解释：利用二叉链表存储树时，右指针指向兄弟结点，因为根节点没有兄弟结点，故根节点的右指针指向空。 （7）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 答案：C 解释：根据题意可知按照先左孩子、再右孩子、最后双亲结点的顺序遍历二叉树，即后序遍历二叉树。 （8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。 A．前序 B．中序 C．后序 D．按层次 答案：C 解释：后续遍历和层次遍历均可实现左右子树的交换，不过层次遍历的实现消耗比后续大，后序遍历方法最合适。 （9）在下列存储形式中，（ ）不是树的存储形式？ A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 答案：D 解释：树的存储结构有三种：双亲表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵树都能通过孩子兄弟表示法转换为二叉树进行存储。 （10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）。 A．所有的结点均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是任意一棵二叉树 答案：C 解释：因为先序遍历结果是“中左右”，后序遍历结果是“左右中”，当没有左子树时，就是“中右”和“右中”；当没有右子树时，就是“中左”和“左中”。则所有的结点均无左孩子或所有的结点均无右孩子均可，所以A、B不能选，又所有的结点均无左孩子与所有的结点均无右孩子时，均只有一个叶子结点，故选C。 （11）设哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。 A．99 B．100 C．101 D．102 答案：B 解释：在哈夫曼树中没有度为1的结点，只有度为0（叶子结点）和度为2的结点。设叶子结点的个数为n0，度为2的结点的个数为n2，由二叉树的性质n0=n2+1，则总结点数n= n0+n2=2*n0-1，得到n0=100。 （12）若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（ ）。 A．X的双亲 B．X的右子树中最左的结点 C．X的左子树中最右结点 D．X的左子树中最右叶结点 答案：C （13）引入二叉线索树的目的是（ ）。 A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 答案：A （14）设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。 A．n−1 B．n C．n + 1 D．n + 2 答案：C （15）n（n≥2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（ ）。 A．该树一定是一棵完全二叉树 B．树中一定没有度为1的结点 C．树中两个权值最小的结点一定是兄弟结点 D．树中任一非叶结点的权值一定不小于下一层任一结点的权值 答案：A 解释：哈夫曼树的构造过程是每次都选取权值最小的树作为左右子树构造一棵新的二叉树，所以树中一定没有度为1的结点、两个权值最小的结点一定是兄弟结点、任一非叶结点的权值一定不小于下一层任一结点的权值。
2．应用题 （1）试找出满足下列条件的二叉树 ① 先序序列与后序序列相同 ②中序序列与后序序列相同 ③ 先序序列与中序序列相同 ④中序序列与层次遍历序列相同 答案：先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则有 ① 或为空树，或为只有根结点的二叉树 ② 或为空树，或为任一结点至多只有左子树的二叉树． ③ 或为空树，或为任一结点至多只有右子树的二叉树． ④ 或为空树，或为任一结点至多只有右子树的二叉树
（2）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C ①画出这棵二叉树。 ②画出这棵二叉树的后序线索树。 ③将这棵二叉树转换成对应的树（或森林）。 答案：
① ②（3） 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 ① 试为这8个字母设计赫夫曼编码。 ② 试设计另一种由二进制表示的等长编码方案。 ③ 对于上述实例，比较两种方案的优缺点。 答案：方案1；哈夫曼编码 先将概率放大100倍，以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ¬……19, 21, 32
（100） （40） （60） 19 21 32 （28） （17） （11） 7 10 6 （5） 2 3
方案比较：
方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 结论：哈夫曼编码优于等长二进制编码
（4）已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。 答案： 初态: weight parent lchild rchild 1 3 0 0 0 2 12 0 0 0 3 7 0 0 0 4 4 0 0 0 5 2 0 0 0 6 8 0 0 0 7 11 0 0 0 8 0 0 0 9 0 0 0 10 0 0 0 11 0 0 0 12 0 0 0 13 0 0 0
终态： weight parent lchild rchild 1 3 8 0 0 2 12 12 0 0 3 7 10 0 0 4 4 9 0 0 5 2 8 0 0 6 8 10 0 0 7 11 11 0 0 8 5 9 5 1 9 9 11 4 8 10 15 12 3 6 11 20 13 9 7 12 27 13 2 10 13 47 0 11 12
3．算法设计题 以二叉链表作为二叉树的存储结构，编写以下算法： （1）统计二叉树的叶结点个数。 [题目分析]如果二叉树为空，返回0，如果二叉树不为空且左右子树为空，返回1，如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数。 [算法描述] int LeafNodeCount(BiTree T) { if(TNULL) return 0; //如果是空树，则叶子结点个数为0 else if(T->lchildNULL&&T->rchildNULL) return 1; //判断结点是否是叶子结点（左孩子右孩子都为空），若是则返回1 else return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild); } （2）判别两棵树是否相等。 [题目分析]先判断当前节点是否相等(需要处理为空、是否都为空、是否相等)，如果当前节点不相等，直接返回两棵树不相等;如果当前节点相等，那么就递归的判断他们的左右孩子是否相等。 [算法描述] int compareTree(TreeNode* tree1, TreeNode* tree2) //用分治的方法做，比较当前根，然后比较左子树和右子树 {bool tree1IsNull = (tree1NULL); bool tree2IsNull = (tree2==NULL); if(tree1IsNull != tree2IsNull) { return 1; } if(tree1IsNull && tree2IsNull) {//如果两个都是NULL，则相等 return 0; }//如果根节点不相等，直接返回不相等，否则的话，看看他们孩子相等不相等 if(tree1->c != tree2->c) { return 1; } return (compareTree(tree1->left,tree2->left)&compareTree(tree1->right,tree2->right)) (compareTree(tree1->left,tree2->right)&compareTree(tree1->right,tree2->left)); }//算法结束
（3）交换二叉树每个结点的左孩子和右孩子。 [题目分析]如果某结点左右子树为空，返回，否则交换该结点左右孩子，然后递归交换左右子树。 [算法描述] void ChangeLR(BiTree &T) { BiTree temp; if(T->lchildNULL&&T->rchildNULL) return; else { temp = T->lchild; T->lchild = T->rchild; T->rchild = temp; }//交换左右孩子 ChangeLR(T->lchild); //递归交换左子树 ChangeLR(T->rchild); //递归交换右子树 } （4）设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。 [题目分析]若树为空，返回；若某结点为叶子结点，则仅输出该结点；否则先输出该结点，递归遍历其左子树，再输出该结点，递归遍历其右子树。 [算法描述] void DoubleTraverse(BiTree T) { if(T == NULL) return; else if(T->lchildNULL&&T->rchildNULL) cout<data; //叶子结点输出 else { cout<data; DoubleTraverse(T->lchild); //递归遍历左子树 cout<data; DoubleTraverse(T->rchild); //递归遍历右子树 } } （5）计算二叉树最大的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。 [题目分析] 求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。 [算法描述] int Width(BiTree bt)//求二叉树bt的最大宽度 {if (bt==null) return (0); //空二叉树宽度为0 else {BiTree Q[];//Q是队列，元素为二叉树结点指针，容量足够大 front=1;rear=1;last=1; //front队头指针,rear队尾指针,last同层最右结点在队列中的位置 temp=0; maxw=0; //temp记局部宽度, maxw记最大宽度 Q[rear]=bt; //根结点入队列 while(front<=last) {p=Q[front++]; temp++; //同层元素数加1 if (p->lchild!=null) Q[++rear]=p->lchild; //左子女入队 if (p->rchild!=null) Q[++rear]=p->rchild; //右子女入队 if (front>last) //一层结束， {last=rear; if(temp>maxw) maxw=temp; //last指向下层最右元素, 更新当前最大宽度 temp=0; }//if }//while return (maxw); }//结束width
（6）用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目。 [题目分析] 若某个结点左子树空右子树非空或者右子树空左子树非空，则该结点为度为1的结点 [算法描述] int Level(BiTree bt) //层次遍历二叉树，并统计度为1的结点的个数 {int num=0; //num统计度为1的结点的个数 if(bt){QueueInit(Q); QueueIn(Q,bt);//Q是以二叉树结点指针为元素的队列 while(!QueueEmpty(Q)) {p=QueueOut(Q); cout<data; //出队,访问结点 if(p->lchild && !p->rchild ||!p->lchild && p->rchild)num++; //度为1的结点 if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入队 if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入队 } // while(!QueueEmpty(Q)) }//if(bt) return(num); }//返回度为1的结点的个数
（7）求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。 [题目分析]因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。 [算法描述] void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度 {BiTree p=bt,l[],s[]; //l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点 int i，top=0,tag[],longest=0; while(p || top>0) {while§ {s[++top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下 if(tag[top]==1) //当前结点的右分枝已遍历 {if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时，才查看路径长度 if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top–;} //保留当前最长路径到l栈，记住最高栈顶指针，退栈 } else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下 }//while(p!=null||top>0) }//结束LongestPath
（8）输出二叉树中从每个叶子结点到根结点的路径。 [题目分析]采用先序遍历的递归方法，当找到叶子结点b时，由于b叶子结点尚未添加到path中，因此在输出路径时还需输出b->data值。 [算法描述] void AllPath(BTNode *b,ElemType path[],int pathlen) {int i; if (b!=NULL) {if (b->lchildNULL && b->rchildNULL) //*b为叶子结点 {cout << " " << b->data << “到根结点路径:” << b->data; for (i=pathlen-1;i>=0;i–) cout << endl; } else {path[pathlen]=b->data; //将当前结点放入路径中 pathlen++; //路径长度增1 AllPath(b->lchild,path,pathlen); //递归扫描左子树 AllPath(b->rchild,path,pathlen); //递归扫描右子树 pathlen–; //恢复环境 } }// if (b!=NULL) }//算法结束
第6章 图
1．选择题 （1）在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。 A．1/2 B．1 C．2 D．4 答案：C （2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A．1/2 B．1 C．2 D．4 答案：B 解释：有向图所有顶点入度之和等于所有顶点出度之和。 （3）具有n个顶点的有向图最多有（ ）条边。 A．n B．n(n-1) C．n(n+1) D．n2 答案：B 解释：有向图的边有方向之分，即为从n个顶点中选取2个顶点有序排列，结果为n(n-1)。 （4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（ ）个非零元素。 A．n B．2(n-1) C．n/2 D．n2 答案：B （5）G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。 A．7 B．8 C．9 D．10 答案：C 解释：8个顶点的无向图最多有8*7/2=28条边，再添加一个点即构成非连通无向图，故至少有9个顶点。 （6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。 A．非连通 B．连通 C．强连通 D．有向 答案：B 解释：即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。 （7）下面（ ）算法适合构造一个稠密图G的最小生成树。 A． Prim算法 B．Kruskal算法 C．Floyd算法 D．Dijkstra算法 答案：A 解释：Prim算法适合构造一个稠密图G的最小生成树，Kruskal算法适合构造一个稀疏图G的最小生成树。 （8）用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。 A．栈 B. 队列 C. 树 D．图 答案：B 解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。 （9）用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。 A．栈 B. 队列 C. 树 D．图 答案：A 解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。 （10）深度优先遍历类似于二叉树的（ ）。 A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 答案：A （11）广度优先遍历类似于二叉树的（ ）。 A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 答案：D （12）图的BFS生成树的树高比DFS生成树的树高（ ）。 A．小 B．相等 C．小或相等 D．大或相等 答案：C 解释：对于一些特殊的图，比如只有一个顶点的图，其BFS生成树的树高和DFS生成树的树高相等。一般的图，根据图的BFS生成树和DFS树的算法思想，BFS生成树的树高比DFS生成树的树高小。 （13）已知图的邻接矩阵如图6.30所示，则从顶点v0出发按深度优先遍历的结果是（ ）。
图6.30 邻接矩阵（14）已知图的邻接表如图6.31所示，则从顶点v0出发按广度优先遍历的结果是（ ），按深度优先遍历的结果是（ ）。
图6.31 邻接表 A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3 答案：D、D （15）下面（ ）方法可以判断出一个有向图是否有环。 A．深度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径 答案：B 2．应用题 （1）已知图6.32所示的有向图，请给出： ① 每个顶点的入度和出度； ② 邻接矩阵； ③ 邻接表； ④ 逆邻接表。
图6.32 有向图 图6.33 无向网答案：
（2）已知如图6.33所示的无向网，请给出： ① 邻接矩阵； ② 邻接表； ③ 最小生成树 答案：
① ③
②
a → b 4 → c 3 b → a 4 → c 5 → d 5 → e 9 c → a 3 → b 5 → d 5 → h 5 d → b 5 → c 5 → e 7 → f 6 → g 5 → h 4 e → b 9 → d 7 → f 3 f → d 6 → e 3 → g 2 g → d 5 → f 2 → h 6
（3）已知图的邻接矩阵如图6.34所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
（4）有向网如图6.35所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。
图6.34 邻接矩阵 图6.35 有向网表6.9 D 终点 i=1 i=2 i=3 i=4 i=5 i=6 b 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) c 2 (a,c) d 12 (a,d) 12 (a,d) 11 (a,c,f,d) 11 (a,c,f,d) e ∞ 10 (a,c,e) 10 (a,c,e) f ∞ 6 (a,c,f) g ∞ ∞ 16 (a,c,f,g) 16 (a,c,f,g) 14 (a,c,f,d,g) S 终点集 {a,c} {a,c,f} {a,c,f,e} {a,c,f,e,d} {a,c,f,e,d,g} {a,c,f,e,d,g,b}
（5）试对图6.36所示的AOE-网： ① 求这个工程最早可能在什么时间结束； ② 求每个活动的最早开始时间和最迟开始时间； ③ 确定哪些活动是关键活动
答案：按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径。
1 2 3 • 4 5 6 Ve 0 19 15 29 38 43 Vl 0 19 15 37 38 43
<1, 2> <1, 3> <3, 2> <2, 4> <2, 5> <3, 5> <4, 6> <5, 6>e 0 0 15 19 19 15 29 38 l 17 0 15 27 19 27 37 38 -e 17 0 0 8 0 12 8 0 此工程最早完成时间为43。关键路径为<1, 3><3, 2><2, 5><5, 6>
3．算法设计题 （1）分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作： ① 增加一个新顶点v，InsertVex(G, v)； ② 删除顶点v及其相关的边，DeleteVex(G, v); ③ 增加一条边<v，w>，InsertArc(G, v, w); ④ 删除一条边<v，w>，DeleteArc(G, v, w)。 [算法描述] 假设图G为有向无权图，以邻接矩阵作为存储结构四个算法分别如下： ① 增加一个新顶点v Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v { if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v; return OK; }//Insert_Vex
② 删除顶点v及其相关的边， Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上删除顶点v { n=G.vexnum; if((m=LocateVex(G,v))<0) return ERROR; G.vexs[m]<->G.vexs[n]; //将待删除顶点交换到最后一个顶点 for(i=0;i<n;i++) { G.arcs[m]=G.arcs[n]; G.arcs[m]=G.arcs[n]; //将边的关系随之交换 } G.arcs[m][m].adj=0; G.vexnum–; return OK; }//Delete_Vex 分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加。
③ 增加一条边<v，w> Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(i==j) return ERROR; if(!G.arcs[j].adj) { G.arcs[j].adj=1; G.arcnum++; } return OK; }//Insert_Arc
④ 删除一条边<v，w> Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[j].adj) { G.arcs[j].adj=0; G.arcnum–; } return OK; }//Delete_Arc
以邻接表作为存储结构，本题只给出Insert_Arc算法.其余算法类似。 Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; p=new ArcNode; p->adjvex=j;p->nextarc=NULL; if(!G.vertices.firstarc) G.vertices.firstarc=p; else { for(q=G.vertices.firstarc;q->q->nextarc;q=q->nextarc) if(q->adjvex==j) return ERROR; //边已经存在 q->nextarc=p; } G.arcnum++; return OK; }//Insert_Arc
（2）一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。 [算法描述] Void DFSn(Graph G,int v) { //从第v个顶点出发非递归实现深度优先遍历图G Stack s; SetEmpty(s); Push(s,v); While(!StackEmpty(s)) { //栈空时第v个顶点所在的连通分量已遍历完 Pop(s,k); If(!visited[k]) { visited[k]=TRUE; VisitFunc(k); //访问第k个顶点 //将第k个顶点的所有邻接点进栈 for(w=FirstAdjVex(G,k);w;w=NextAdjVex(G,k,w)) { if(!visited[w]&&w!=GetTop(s)) Push(s,w); //图中有环时w==GetTop(s) } } }
（3）设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点，设v可达其余各个顶点。 [题目分析] 利用Dijkstra算法求v0到其它所有顶点的最短路径，分别保存在数组D[i]中，然后求出D[i]中值最大的数组下标m即可。 [算法描述] int ShortestPath_MAX(AMGraph G, int v0){ //用Dijkstra算法求距离顶点v0的最短路径长度最大的一个顶点m n=G.vexnum; //n为G中顶点的个数 for(v = 0; v<n; ++v){ //n个顶点依次初始化 S[v] = false; //S初始为空集 D[v] = G.arcs[v0][v]; //将v0到各个终点的最短路径长度初始化 if(D[v]< MaxInt) Path [v]=v0; //如果v0和v之间有弧，则将v的前驱置为v0 else Path [v]=-1; //如果v0和v之间无弧，则将v的前驱置为-1 }//for S[v0]=true; //将v0加入S D[v0]=0; //源点到源点的距离为0 /开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集/ for(i=1;i<n; ++i){ //对其余n−1个顶点，依次进行计算 min= MaxInt; for(w=0;w<n; ++w) if(!S[w]&&D[w]<min) {v=w; min=D[w];} //选择一条当前的最短路径，终点为v S[v]=true; //将v加入S for(w=0;w<n; ++w) //更新从v0到V−S上所有顶点的最短路径长度 if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])){ D[w]=D[v]+G.arcs[v][w]; //更新D[w] Path [w]=v; //更改w的前驱为v }//if }//for /*最短路径求解完毕，设距离顶点v0的最短路径长度最大的一个顶点为m */ Max=D[0]; m=0; for(i=1;i<n;i++) if(Max<D[i]) m=i; return m; } （4）试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。 [题目分析] 引入一变量level来控制递归进行的层数 [算法描述] int visited[MAXSIZE]; //指示顶点是否在当前路径上 int level＝1;//递归进行的层数 int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 { if(ij) return 1; //i就是j else { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc，level–) { level++; k=p->adjvex; if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径 }//for }//else if (level1) return 0; }//exist_path_DFS （5）采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。 [算法描述] int visited[MAXSIZE]; int exist_path_len(ALGraph G,int i,int j,int k) //判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径 {if(ij&&k0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) {visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) {l=p->adjvex; if(!visited[l]) if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else return 0; //没找到 }//exist_path_len
第7章 查找 1．选择题 （1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。 A．(n-1)/2 B． n/2 C．(n+1)/2 D．n 答案：C 解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。 （2）适用于折半查找的表的存储方式及元素排列要求为（ ）。 A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 答案：D 解释：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。 （3）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用( )查找法。 A．顺序查找 B．折半查找 C．分块查找 D．哈希查找 答案：C 解释：分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。由于块内是无序的，故插入和删除比较容易，无需进行大量移动。如果线性表既要快速查找又经常动态变化，则可采用分块查找。 （4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败。 A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50 答案：A 解释：表中共10个元素，第一次取(1+10)/2=5，与第五个元素20比较，58大于20，再取(6+10)/2=8，与第八个元素70比较，依次类推再与30、50比较，最终查找失败。 （5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ ）次关键字。 A．3 B．4 C．5 D．6 答案：B 解释：22个记录的有序表，其折半查找的判定树深度为 log222 + 1=5，且该判定树不是满二叉树，即查找失败时至多比较5次，至少比较4次。 （6）折半搜索与二叉排序树的时间性能（ ）。 A．相同 B．完全不同 C．有时不相同 D．数量级都是O(log2n) 答案：C （7）分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ ）。 A．（100，80， 90， 60， 120，110，130） B．（100，120，110，130，80， 60， 90） C．（100，60， 80， 90， 120，110，130） D．(100，80， 60， 90， 120，130，110) 答案：C 解释：A、B、C、D四个选项构造二叉排序树都以100为根，易知A、B、D三个序列中第一个比100小的关键字为80，即100的左孩子为80，而C选项中100的左孩子为60，故选C。 （8）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（ ）型调整以使其平衡。 A．LL B．LR C．RL D．RR 答案：C （9）下列关于m阶B-树的说法错误的是（ ）。 A．根结点至多有m棵子树 B．所有叶子都在同一层次上 C．非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树 D．根结点中的数据是有序的 答案：D （10）下面关于B-和B+树的叙述中，不正确的是（ ）。 A．B-树和B+树都是平衡的多叉树 B．B-树和B+树都可用于文件的索引结构 C．B-树和B+树都能有效地支持顺序检索 D．B-树和B+树都能有效地支持随机检索 答案：C （11）m阶B-树是一棵（ ）。 A．m叉排序树 B．m叉平衡排序树 C．m-1叉平衡排序树 D．m+1叉平衡排序树 答案：B （12）下面关于哈希查找的说法，正确的是（ ）。 A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的 C．不存在特别好与坏的哈希函数，要视情况而定 D．哈希表的平均查找长度有时也和记录总数有关 答案：C （13）下面关于哈希查找的说法，不正确的是（ ）。 A．采用链地址法处理冲突时，查找一个元素的时间是相同的 B．采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的 C．用链地址法处理冲突，不会引起二次聚集现象 D．用链地址法处理冲突，适合表长不确定的情况 答案：A 解释：在同义词构成的单链表中，查找该单链表表中不同元素，所消耗的时间不同。 （14）设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（ ）。 A．8 B．3 C．5 D．9 答案：D 解释：关键字15放入位置4，关键字38放入位置5，关键字61放入位置6，关键字84放入位置7，再添加关键字49，计算得到地址为5，冲突，用二次探测法解决冲突得到新地址为6，仍冲突，再用用二次探测法解决冲突，得到新地址为4，仍冲突，再用用二次探测法解决冲突，得到新地址为9，不冲突，即将关键字49放入位置9。 （15）采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字 ( )。 A．不一定都是同义词 B．一定都是同义词 C．一定都不是同义词 D．都相同 答案：A 解释：所探测的这些关键字可能是在处理其它关键字冲突过程中放入该位置的。
2．应用题 （1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题： ① 画出描述折半查找过程的判定树； ② 若查找元素54，需依次与哪些元素比较？ ③ 若查找元素90，需依次与哪些元素比较？ ④ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 答案： ①先画出判定树如下（注：mid=(1+12)/2=6）： 30 5 63 3 7 42 87 4 24 54 72 95 ②查找元素54，需依次与30, 63, 42, 54 元素比较； ③查找元素90，需依次与30, 63,87, 95元素比较； ④求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次； 但最后一层未满，不能用8×4，只能用5×4=20次， 所以ASL＝1/12（17＋20）＝37/12≈3.08
（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。 答案： 12 7 17 2 11 16 21 4 9 13 验算方法： 用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17,21
（3）已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） ① 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 ② 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。 ③ 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 答案：
（4）对图7.31所示的3阶B-树，依次执行下列操作，画出各步操作的结果。 ① 插入90 ② 插入25 ③ 插入45 ④ 删除60
（5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题： ① 画出哈希表的示意图； ② 若查找关键字63，需要依次与哪些关键字进行比较？ ③ 若查找关键字60，需要依次与哪些关键字比较？ ④ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 答案： ①画表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 ②查找63,首先要与H(63)=63%16=15号单元内容比较，即63与31比较 ,不匹配; 然后顺移，与46,47,32,17,63相比，一共比较了6次！ ③查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。 ④对于黑色数据元素，各比较1次；共6次； 对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次， 所以ASL=1/11（6＋2＋3×3+6）＝23/11
（6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key %7 ，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 答案： 散列地址 0 1 2 3 4 5 6 7 8 9 关键字 14 1 9 23 84 27 55 20 比较次数 1 1 1 2 3 4 1 2 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8 以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）%10=7（冲突） H2=（6+22）%10=0（冲突） H3=（6+33）%10=5 所以比较了4次。
（7）设哈希函数H（K）=3 K mod 11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。 ① 线性探测法； ② 链地址法。 答案： ① 散列地址 0 1 2 3 4 5 6 7 8 9 10 关键字 4 12 49 38 13 24 32 21 比较次数 1 1 1 2 1 2 1 2 ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8 ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11
②
ASLsucc =（15+23）/8=11/8 ASLunsucc=（1+2+1+2+3+1+3+1+3+1+1）/11=19/11
3．算法设计题 （1）试写出折半查找的递归算法。 [算法描述] int BinSrch（rectype r[ ]，int k，low，high） //在长为n的有序表中查找关键字k，若查找成功，返回k所在位置，查找失败返回0。 {if（low≤high） //low和high分别是有序表的下界和上界 {mid=（low+high）/2； if（r[mid].keyk）return （mid）； else if（r[mid].key>k）return （BinSrch（r,k，mid+1，high））; else return （BinSrch（r,k，low，mid-1））; } else return （0）；//查找失败。 }//算法结束 （2）试写一个判别给定二叉树是否为二叉排序树的算法。 [题目分析] 根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。 [算法描述] #define true 1 #define false 0 typedef struct node {datatype data; struct node *lchild,*rchild;} *BTree; void JudgeBST（BTree T,int flag） // 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 { if（T!=null && flag） { Judgebst（T->lchild,flag）；// 中序遍历左子树 if（prenull）pre=T；// 中序遍历的第一个结点不必判断 else if（pre->datadata）pre=T；//前驱指针指向当前结点 else{flag=flase；} //不是完全二叉树 Judgebst （T->rchild,flag）；// 中序遍历右子树 }//JudgeBST算法结束
（3）已知二叉排序树采用二叉链表存储结构，根结点的指针为T，链结点的结构为（lchild,data,rchild），其中lchild，rchild分别指向该结点左、右孩子的指针，data域存放结点的数据信息。请写出递归算法，从小到大输出二叉排序树中所有数据值>=x的结点的数据。要求先找到第一个满足条件的结点后，再依次输出其他满足条件的结点。 [题目分析]本题算法之一是如上题一样，中序遍历二叉树，在“访问根结点”处判断结点值是否≥x，如是则输出，并记住第一个≥x值结点的指针。这里给出另一个算法，利用二叉排序树的性质，如果根结点的值>=x,则除左分枝中可能有<x的结点外都应输出。所以从根结点开始查找，找到结点值<x的结点后，将其与双亲断开输出整棵二叉排序树。如果根结点的值<x,则沿右子树查找第一个≥x的结点，找到后，与上面同样处理。 void Print（BSTree t） // 中序输出以t为根的二叉排序树的结点 {if（t）{Print（t->lchild）； Cout<<t-data； Print（t->rchild）； } } void PrintAllx(BSTree bst，datatype x） //在二叉排序树bst中，查找值≥x的结点并输出 {p=bst； if（p） {while（p && p->data<x）p=p->rchild；//沿右分枝找第一个值≥x的结点 bst=p; //bst所指结点是值≥x的结点的树的根 if（p） {f=p; p=p->lchild ；//找第一个值<x的结点 while（p && p->data≥x）//沿左分枝向下，找第一个值<x的结点 {f=p；p=p->lchild ；} //f是p的双亲结点的指针，指向第一个值≥x的结点 if§ f->lchild=null; //双亲与找到的第一个值<x的结点断开 Print(bst)；//输出以bst为根的子树 }//while }//内层if（p） }//第一层if（p） }//PrintAllx
（4）已知二叉树T的结点形式为（lling,data,count,rlink），在树中查找值为X的结点，若找到，则记数（count）加1，否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。 [算法描述] void SearchBST(BiTree &T,int target){ BiTree s,q,f; //以数据值target,新建结点s s=new BiTNode; s->data.x=target; s->data.count=0; s->lchild=s->rchild=NULL;
if(!T){ T=s; return ; } //如果该树为空则跳出该函数 f=NULL; q=T; while (q){ if (q->data.x==target){ q->data.count++; return ; } //如果找到该值则计数加一 f=q; if (q->data.x>target) //如果查找值比目标值大，则为该树左孩子 q=q->lchild; else //否则为右孩子 q=q->rchild; } //将新结点插入树中 if(f->data.x>target) f->lchild=s; else f->rchild=s;} （5）假设一棵平衡二叉树的每个结点都表明了平衡因子b，试设计一个算法，求平衡二叉树的高度。 [题目分析] 因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左右一分枝向下查找，若b不为0，则沿左（当b=1时）或右（当b=-1时）向下查找。 [算法描述] int Height（BSTree t） // 求平衡二叉树t的高度 {level=0；p=t； while（p） {level++； // 树的高度增1 if（p->bf<0）p=p->rchild；//bf=-1 沿右分枝向下 //bf是平衡因子，是二叉树t结点的一个域，因篇幅所限，没有写出其存储定义 else p=p->lchild； //bf>=0 沿左分枝向下 }//while return （level）；//平衡二叉树的高度 } //算法结束
（6）分别写出在散列表中插入和删除关键字为K的一个记录的算法，设散列函数为H，解决冲突的方法为链地址法。 [算法描述] bool insert(){ int data; cin>>data; int ant=hash(data); LinkList p=HT[ant]; //初始化散列表 while (p->next){ if(p->next->data==data) return false; p=p->next; } //找到插入位置 LinkList s; s=new LNode; s->data=data; s->next=p->next; p->next=s; //插入该结点 return true; }
bool deletes(){ int data; cin>>data; int ant=hash(data); LinkList p=HT[ant]; //初始化散列表 while (p->next){ if(p->next->data==data){ LinkList s=p->next; p->next=s->next; delete s; //删除该结点 return true; } //找到删除位置 p=p->next； //遍历下一个结点 } return false; }
第8章 排序 1．选择题 （1）从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ ）。 A．归并排序 B．冒泡排序 C．插入排序 D．选择排序 答案：C （2）从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。 A．归并排序 B．冒泡排序 C．插入排序 D．选择排序 答案：D （3）对n个不同的关键字由小到大进行冒泡排序，在下列（ ）情况下比较的次数最多。 A．从小到大排列好的 B．从大到小排列好的 C．元素无序 D．元素基本有序 答案：B 解释：对关键字进行冒泡排序，关键字逆序时比较次数最多。 （4）对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（ ）。 A．n+1 B．n C．n-1 D．n(n-1)/2 答案：D 解释：比较次数最多时，第一次比较n-1次，第二次比较n-2次……最后一次比较1次，即(n-1)+(n-2)+…+1= n(n-1)/2。 （5）快速排序在下列（ ）情况下最易发挥其长处。 A．被排序的数据中含有多个相同排序码 B．被排序的数据已基本有序 C．被排序的数据完全无序 D．被排序的数据中的最大值和最小值相差悬殊 答案：C 解释：B选项是快速排序的最坏情况。 （6）对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（ ）。 A．O(n) B．O(n2) C．O(nlog2n) D．O(n3) 答案：B 解释：快速排序的平均时间复杂度为O(nlog2n)，但在最坏情况下，即关键字基本排好序的情况下，时间复杂度为O(n2)。 （7）若一组记录的排序码为（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 答案：C （8）下列关键字序列中，（ ）是堆。 A．16，72，31，23，94，53 B．94，23，31，72，16，53 C．16，53，23，94，31，72 D．16，23，53，31，94，72 答案：D 解释：D选项为小根堆 （9）堆是一种（ ）排序。 A．插入 B．选择 C．交换 D．归并 答案：B （10）堆的形状是一棵（ ）。 A．二叉排序树 B．满二叉树 C．完全二叉树 D．平衡二叉树 答案：C （11）若一组记录的排序码为（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 答案：B （12）下述几种排序方法中，要求内存最大的是（ ）。 A．希尔排序 B．快速排序 C．归并排序 D．堆排序 答案：C 解释：堆排序、希尔排序的空间复杂度为O(1)，快速排序的空间复杂度为O(log2n)，归并排序的空间复杂度为O(n)。 （13）下述几种排序方法中，（ ）是稳定的排序方法。 A．希尔排序 B．快速排序 C．归并排序 D．堆排序 答案：C 解释：不稳定排序有希尔排序、简单选择排序、快速排序、堆排序；稳定排序有直接插入排序、折半插入排序、冒泡排序、归并排序、基数排序。 （14）数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )算法最节省时间。 A．冒泡排序 B．快速排序 C．简单选择排序 D．堆排序 答案：D （15）下列排序算法中，（ ）不能保证每趟排序至少能将一个元素放到其最终的位置上。 A．希尔排序 B．快速排序 C．冒泡排序 D．堆排序 答案：A 解释：快速排序的每趟排序能将作为枢轴的元素放到最终位置；冒泡排序的每趟排序能将最大或最小的元素放到最终位置；堆排序的每趟排序能将最大或最小的元素放到最终位置。 2．应用题 （1）设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。 ① 直接插入排序 ② 折半插入排序 ③ 希尔排序（增量选取5，3，1） ④ 冒泡排序 ⑤ 快速排序 ⑥ 简单选择排序 ⑦ 堆排序 ⑧ 二路归并排序 答案： ①直接插入排序 [2 12] 16 30 28 10 16* 20 6 18 [2 12 16] 30 28 10 16* 20 6 18 [2 12 16 30] 28 10 16* 20 6 18 [2 12 16 28 30] 10 16* 20 6 18 [2 10 12 16 28 30] 16* 20 6 18 [2 10 12 16 16* 28 30] 20 6 18 [2 10 12 16 16* 20 28 30] 6 18 [2 6 10 12 16 16* 20 28 30] 18 [2 6 10 12 16 16* 18 20 28 30]
② 折半插入排序 排序过程同①
③ 希尔排序（增量选取5，3，1） 10 2 16 6 18 12 16* 20 30 28 （增量选取5） 6 2 12 10 18 16 16* 20 30 28 （增量选取3） 2 6 10 12 16 16* 18 20 28 30 （增量选取1）
④ 冒泡排序 2 12 16 28 10 16* 20 6 18 [30] 2 12 16 10 16* 20 6 18 [28 30] 2 12 10 16 16* 6 18 [20 28 30] 2 10 12 16 6 16* [18 20 28 30] 2 10 12 6 16 [16* 18 20 28 30] 2 10 6 12 [16 16* 18 20 28 30] 2 6 10 [12 16 16* 18 20 28 30] 2 6 10 12 16 16* 18 20 28 30]
⑤ 快速排序 12 [6 2 10] 12 [28 30 16* 20 16 18] 6 [2] 6 [10] 12 [28 30 16* 20 16 18 ] 28 2 6 10 12 [18 16 16* 20 ] 28 [30 ] 18 2 6 10 12 [16* 16] 18 [20] 28 30 16* 2 6 10 12 16* [16] 18 20 28 30 左子序列递归深度为1，右子序列递归深度为3
⑥ 简单选择排序 2 [12 16 30 28 10 16* 20 6 18] 2 6 [16 30 28 10 16* 20 12 18] 2 6 10 [30 28 16 16* 20 12 18] 2 6 10 12 [28 16 16* 20 30 18] 2 6 10 12 16 [28 16* 20 30 18] 2 6 10 12 16 16* [28 20 30 18] 2 6 10 12 16 16* 18 [20 30 28] 2 6 10 12 16 16* 18 20 [28 30] 2 6 10 12 16 16* 18 20 28 [30]
⑧ 二路归并排序 2 12 16 30 10 28 16 * 20 6 18 2 12 16 30 10 16* 20 28 6 18 2 10 12 16 16* 20 28 30 6 18 2 6 10 12 16 16* 18 20 28 30
（2）给出如下关键字序列｛321，156，57，46，28，7，331，33，34，63｝，试按链式基数排序方法，列出每一趟分配和收集的过程。 答案： 按最低位优先法 →321→156→57→46→28→7→331→33→34→63 分配 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 321 33 34 156 57 28 331 63 46 7 收集 →321→331→33→63→34→156→46→57→7→28 （3）对输入文件（101，51，19，61，3，71，31，17，19，100，55，20，9，30，50，6，90）；当k=6时，使用置换-选择算法，写出建立的初始败者树及生成的初始归并段。 答案： 初始败者树
初始归并段：R1:3,19,31,51,61,71,100,101 R2:9,17,19,20,30,50,55,90 R3:6
3．算法设计题 （1）试以单链表为存储结构，实现简单选择排序算法。 [算法描述]： void LinkedListSelectSort(LinkedList head) //本算法一趟找出一个关键字最小的结点，其数据和当前结点进行交换;若要交换指针，则须记下 //当前结点和最小结点的前驱指针 p=head->next; while(p!=null) {q=p->next; r=p; //设r是指向关键字最小的结点的指针 while (q!=null) {if(q->datadata) r=q; q:=q->next; } if(r!=p) r->data<–>p->data; p=p->next; }
（2）有n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向冒泡排序即相邻两趟排序向相反方向冒泡）。 [算法描述]： typedef struct node { ElemType data; struct node *prior,*next; }node，*DLinkedList; void TwoWayBubbleSort(DLinkedList la) //对存储在带头结点的双向链表la中的元素进行双向起泡排序。 {int exchange=1; // 设标记 DLinkedList p,temp,tail; head=la //双向链表头，算法过程中是向下起泡的开始结点 tail=null; //双向链表尾，算法过程中是向上起泡的开始结点 while (exchange) {p=head->next; //p是工作指针，指向当前结点 exchange=0; //假定本趟无交换 while (p->next!=tail) // 向下（右）起泡，一趟有一最大元素沉底 if (p->data>p->next->data) //交换两结点指针，涉及6条链 {temp=p->next; exchange=1;//有交换 p->next=temp->next;temp->next->prior=p //先将结点从链表上摘下 temp->next=p; p->prior->next=temp; //将temp插到p结点前 temp->prior=p->prior; p->prior=temp; } else p=p->next; //无交换，指针后移 tail=p; //准备向上起泡 p=tail->prior; while (exchange && p->prior!=head) //向上（左）起泡，一趟有一最小元素冒出 if (p->dataprior->data) //交换两结点指针，涉及6条链 {temp=p->prior; exchange=1; //有交换 p->prior=temp->prior;temp->prior->next=p； //先将temp结点从链表上摘下 temp->prior=p; p->next->prior=temp; //将temp插到p结点后（右） temp->next=p->next; p->next=temp; } else p=p->prior; //无交换，指针前移 head=p; //准备向下起泡 }// while (exchange) } //算法结束
（3）设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红，白，蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。 [题目分析]利用快速排序思想解决。由于要求“对每粒砾石的颜色只能看一次”，设3个指针i，j和k，分别指向红色、白色砾石的后一位置和待处理的当前元素。从k=n开始，从右向左搜索，若该元素是兰色，则元素不动，指针左移（即k-1）；若当前元素是红色砾石，分i>=j（这时尚没有白色砾石）和i<j两种情况。前一情况执行第i个元素和第k个元素交换，之后i+1；后一情况，i所指的元素已处理过（白色），j所指的元素尚未处理，应先将i和j所指元素交换，再将i和k所指元素交换。对当前元素是白色砾石的情况，也可类似处理。 为方便处理，将三种砾石的颜色用整数1、2和3表示。 [算法描述]： void QkSort(rectype r[],int n) { // r为含有n个元素的线性表，元素是具有红、白和兰色的砾石，用顺序存储结构存储， //本算法对其排序，使所有红色砾石在前，白色居中，兰色在最后。 int i=1,j=1,k=n,temp; while (k!=j){ while (r[k].key3) k–;// 当前元素是兰色砾石，指针左移 if (r[k].key1) // 当前元素是红色砾石 if (i>=j){temp=r[k];r[k]=r[i];r[i]=temp; i++;} //左侧只有红色砾石，交换r[k]和r[i] else {temp=r[j];r[j]=r[i];r[i]=temp; j++; //左侧已有红色和白色砾石，先交换白色砾石到位 temp=r[k];r[k]=r[i];r[i]=temp; i++; //白色砾石（i所指）和待定砾石（j所指） } //再交换r[k]和r[i]，使红色砾石入位。 if (r[k].key==2) if (i<=j) { temp=r[k];r[k]=r[j];r[j]=temp; j++;} // 左侧已有白色砾石，交换r[k]和r[j] else { temp=r[k];r[k]=r[i];r[i]=temp; j=i+1;} //i、j分别指向红、白色砾石的后一位置 }//while if (r[k]==2) j++; /* 处理最后一粒砾石 else if (r[k]==1) { temp=r[j];r[j]=r[i];r[i]=temp; i++; j++; } //最后红、白、兰色砾石的个数分别为: i-1;j-i;n-j+1 }//结束QkSor算法 [算法讨论]若将j（上面指向白色）看作工作指针，将r[1…j-1]作为红色，r[j…k-1]为白色，r[k…n]为兰色。从j=1开始查看，若r[j]为白色，则j=j+1；若r[j]为红色，则交换r[j]与r[i]，且j=j+1，i=i+1；若r[j]为兰色，则交换r[j]与r[k];k=k-1。算法进行到j>k为止。 算法片段如下： int i=1,j=1,k=n; while(j<=k) if (r[j]==1) //当前元素是红色 {temp=r[i]; r[i]=r[j]; r[j]=temp; i++;j++; } else if (r[j]==2) j++; //当前元素是白色 else //(r[j]==3 当前元素是兰色 {temp=r[j]; r[j]=r[k]; r[k]=temp; k–; } 对比两种算法，可以看出，正确选择变量（指针）的重要性。
（4）编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求： ① 采用顺序存储结构，至多使用一个记录的辅助存储空间； ② 算法的时间复杂度为O(n)。 [算法描述] void process (int A[n]){ low = 0; high = n-1; while ( low<high ){ while (low<high && A[low]<0) low++; while (low<high && A[high]>0) high++; if (low<high){ x=A[low]; A[low]=A[high]; A[high]=x; low++; high–; } } return; }
（5）借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l…n]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。请简要说明算法思想并编写算法。 [题目分析]把待查记录看作枢轴，先由后向前依次比较，若小于枢轴，则从前向后，直到查找成功返回其位置或失败返回0为止。 [算法描述] int index (RecType R[],int l,h,datatype key) {int i=l,j=h; while (i<j) { while (i<=j && R[j].key>key) j–; if (R[j].keykey) return j; while (i<=j && R[i].key<key) i++; if (R[i].keykey) return i; } cout<<“Not find”; return 0; }//index
（6）有一种简单的排序算法，叫做计数排序。这种排序算法对一个待排序的表进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。 ① 给出适用于计数排序的顺序表定义； ② 编写实现计数排序的算法； ③ 对于有n个记录的表，关键字比较次数是多少？ ④ 与简单选择排序相比较，这种方法是否更好？为什么？ [算法描述] ① typedef struct {int key; datatype info }RecType ② void CountSort(RecType a[],b[],int n) //计数排序算法，将a中记录排序放入b中 {for(i=0;i<n;i++) //对每一个元素 {for(j=0,cnt=0;j<n;j++) if(a[j].key<a[i].key) cnt++; //统计关键字比它小的元素个数 b[cnt]=a[i]; } }//Count_Sort ③ 对于有n个记录的表，关键码比较n2次。 ④ 简单选择排序算法比本算法好。简单选择排序比较次数是n(n-1)/2,且只用一个交换记录的空间；而这种方法比较次数是n2，且需要另一数组空间。 [算法讨论]因题目要求“针对表中的每个记录，扫描待排序的表一趟”，所以比较次数是n2次。若限制“对任意两个记录之间应该只进行一次比较”，则可把以上算法中的比较语句改为： for(i=0;i<n;i++) a[i].count=0;//各元素再增加一个计数域，初始化为0 for(i=0;i<n;i++) for(j=i+1;j<n;j++) if(a[i].key<a[j].key) a[j].count++; else a[i].count++;
