2024年1月4日发(作者：)
C语言版）（第课后习题答案李冬梅
2015.3
版）
数据结构（ 2
目 录
第 1 章
第 2 章
第 3 章
第 4 章
第 5 章
第 6 章
第 7 章
第 8 章
绪论 .............................................................................................................................................................................................................................
1
线性表 .......................................................................................................................................................................................................................
5
栈和队列 ..............................................................................................................................................................................................................
13
串、数组和广义表 ......................................................................................................................................................................................
26
树和二叉树 ........................................................................................................................................................................................................
33
...................................................................................................................................................................................................................................
43
查找 ..........................................................................................................................................................................................................................
54
排序 ..........................................................................................................................................................................................................................
65
II
图
第1章
绪论
1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结
答案：
数据 ：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的
构、抽象数据类型。
总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素
：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些
情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项 ：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信
息表中的学号、姓名、性别等都是数据项。
数据对象
：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是
C={‘A’，‘ B’， , ，‘ Z’，
‘ a’，
集合 N={0 ，± 1，± 2，, } ，字母字符数据对象是集合
‘ b’， , ，‘
z ’} ，学生基本信息表也可是一个数据对象。
数据结构
：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结
“结构”就是指数据元素之间存在的关系。
构是带“结构”的数据元素的集合，
逻辑结构 ：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构： 数据对象在计算机中的存储表示，也称为
物理结构 。
抽象数据类型 ：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
答案：
例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性
序列。 对于整个表来说，
只有一个开始结点
( 它的前面无记录
) 和一个终端结点
( 它的后面无记
录 ) ，其他的结点则各有一个也只有一个直接前趋和直接后继。
定了学生表的逻辑结构，即线性结构。
学生记录之间的这种关系就确
这些学生记录在计算机中的存储表示就是存储结构。
如果用连续的存储单元
( 如用数组表
示 ) 来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。
即相同的逻辑结构，可以对应不同的存储结构。
3．简述逻辑结构的四种基本关系并画出它们的关系图。
1
答案：
（ 1）集合结构
数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。
（ 2）线性结构
数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。
（ 3）树结构
数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每位组长管理多名组员，从而构成树形结构。
（ 4）图结构或网状结构
数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图形结构或网状结构。
其中树结构和图结构都属于非线性结构。
四类基本逻辑结构关系图
4．存储结构由哪两种基本的存储方法实现？
答案：
（ 1）顺序存储结构
顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常
借助程序设计语言的数组类型来描述。
（ 2）链式存储结构
顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无
需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于
存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。
5．选择题
（ 1）在数据结构中，从逻辑上可以把数据结构分成（
A．动态结构和静态结构
B
．紧凑结构和非紧凑结构
2
）。
C．线性结构和非线性结构
答案： C
D
．内部结构和外部结构
（ 2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（
A．存储结构
C．逻辑结构
答案： C
（ 3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（
A ．数据具有同一特点
B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样
D．数据元素所包含的数据项的个数要相等
答案： B
（ 4）以下说法正确的是（
A．数据元素是数据的最小单位
B．数据项是数据的基本单位
C．数据结构是带有结构的各数据项的集合
D．一些表面上很不相同的数据可以有相同的逻辑结构
答案： D
）。
）。
B
D
．存储实现
．运算实现
）。
解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。
（ 5）算法的时间复杂度取决于（
A．问题的规模
C．计算机的配置
答案： D
）。
B．待处理数据的初态
D． A 和 B
解释：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些
排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏
以及平均时间复杂度的评价。
（ 6）以下数据结构中，
A．树
答案： A
6．试分析下面各程序段的时间复杂度。
（ 1） x=90; y=100;
while(y>0)
（
）是非线性数据结构
B
．字符串
C
．队列
D
．栈
if(x>100)
{x=x-10;y--;}
else x++;
答案： O(1)
解释：程序的执行次数为常数阶。
3
（
2） for (i=0; i for (j=0; j a[i][j]=0; 答案： O(m*n) 解释：语句 a[i][j]=0; 的执行次数为 m*n 。 （ 3） s=0; for i=0; i for(j=0; j s+=B[i][j]; sum=s; 2 解释：语句 s+=B[i][j]; 的执行次数为 n2 。 （ 4） i=1; while(i<=n) i=i*3; 3 答案： O(log n) 解释：语句 i=i*3; 的执行次数为 log 3 n 。 （ 5） x=0; for(i=1; i for (j=1; j<=n-i; j++) x++; 2 解释：语句 x++; 的执行次数为 n-1+n-2+ ,, ＋ （ 6） x=n; //n>1 y=0; while(x ≥ (y+1)* (y+1)) y ++; 答案： O( n ) 解释：语句 y++; 的执行次数为 n 。 4 1= n(n-1)/2 。 第2章 线性表 1．选择题 （1）顺序表中 第一个 元素的存储 地址是 100，每个元素的 长度为 2，则第 5 个元素的 地址是（ ）。 A． 110 答案： B B ． 108 C． 100 D ． 120 解释：顺序表中的数据连续存储，所以第 （ 2）在 n 个结点的顺序表中，算法的时间复杂度是 5 个元素的地址为： O(1) 的操作是（ 100+2*4=108 。 ）。 A ．访问第 i 个结点（ 1≤ i ≤ n）和求第 i 个结点的直接前驱（ B ．在第 i 个结点后插入一个新结点（ C ．删除第 i 个结点（ 1≤ i ≤ n） 1≤ i ≤ n） 2≤ i≤ n） D ．将 n 个结点从小到大排序 答案： A 解释： 在顺序表中插入 or delete 一个结点的时间复杂度都是 O(n) ，排序的时间复杂度 i 个结点的直接前 为 O(n 2 )或 O(nlog 2n)。顺序表是一种随机存取结构，访问第 驱都可以直接通过数组的下标直接定位，时间复杂度是 （ 3） 向一个有 动 的元素个数为（ i 个结点和求第 O(1) 。 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移 ）。 A． 8 B．63.5 C．63 D．7 答案： B 解释：平均要移动的元素个数为： （ 4）链接存储的存储结构所占存储空间（ n/2 。 ）。 A ．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B ．只有一部分，存放结点值 C ．只有一部分，存储表示结点间关系的指针 D ．分两部分，一部分存放结点值，另一部分存放结点所占单元数 答案： A （ 5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ A ．必须是连续的 C ．一定是不连续的 B ．部分地址必须是连续的 D ．连续或不连续都可以 ）。 答案： D （ 6）线性表Ｌ在（ ）情况下适用于使用链式结构实现。 Ｂ．需不断对Ｌ进行删除插入 Ｄ．Ｌ中结点结构复杂 A ．需经常修改Ｌ中的结点值 C ．Ｌ中含有大量的结点 答案： B 5 解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。 （ 7）单链表的存储密度（ A ．大于 1 ）。 B ．等于 1 C．小于 1 D ．不能确定 答案： C 解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空 间之比，假设单链表一个结点本身所占的空间为 D ，指针域所占的空间为 N ，则存储密度为： D/(D+N) ，一定小于 1。 （ 8）将两个各有 A ． n n 个元素的有序表归并成一个有序表，其最少的比较次数是（ B ． 2n-1 C． 2n D ． n-1 ）。 答案： A 解释：当第一个有序表中所有的元素都小于（或大于）第二个表中的元素，只需 n 次。 （ 9）在一个长度为 须向后移动（ 要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较 n 的顺序表中，在第 i 个元素（ ）个元素。 B ． n-i+1 C． n-i-1 D ． I 1 ≤ i ≤ n+1 ）之前插入一个新元素时 A ． n-i 答案： B (10) 线性表 L=(a 1 ， a2 ,,, an) ，下列说法正确的是（ ）。 A ．每个元素都有一个直接前驱和一个直接后继 B ．线性表中至少有一个元素 C ．表中诸元素的排列必须是由小到大或由大到小 D ．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接 后继。 答案： D (11) 创建一个包括 A ． O(1) n 个结点的有序单链表的时间复杂度是（ B ． O(n) C ． O(n 2 ) ）。 D ． O(nlog 2 n) 答案： C 解释：单链表创建的时间复杂度是 O(n) ，而要建立一个有序的单链表，则每生成 ，所以时间复杂度是 一个新结点时需要和已有的结点进行比较，确定合适的插入位置 O(n2) 。 (12) 以下说法错误的是（ ）。 A ．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 B ．顺序存储的线性表可以随机存取 C ．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 D ．线性表的链式存储结构优于顺序存储结构 答案： D 解释： 链式存储结构和顺序存储结构各有优缺点，有不同的适用场合。 (13) 在单链表中，要将 s 所指结点插入到 p 所指结点之后，其语句应为（ 6 ）。 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 2．算法设计题 （ 1）将两个递增的有序链表合并为一个递增的有序链表。 链表的存储空间 要求结果链表仍使用原来两个 , 不另外占用其它的存储空间。表中不允许有重复的数据。 [ 题目分析 ] 合并后的新表使用头指针 Lc 指向， pa 和 pb 分别是链表 La 和 Lb 的工作指针 , 初始化为 相应链表的第一个结点，从第一个结点开始进行比较，当两个链表 点时，依次摘取其中较小者重新链接在 表中的元素，删除 La 和 Lb 均为到达表尾结 La Lc 表的最后。如果两个表中的元素相等，只摘取 Lb 表中的元素，这样确保合并后表中无重复的元素。当一个表到达表尾结 Lc 表的最后。 点，为空时，将非空表的剩余元素直接链接在 [ 算法描述 ] void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) {// 合并链表 //pa La 和 Lb ，合并后的新表使用头指针 La 和 Lb 的工作指针 Lc 指向 , 初始化为相应链表的第一个结点 pa=La->next; pb=Lb->next; 和 pb 分别是链表 Lc=pc=La; // while(pa && pb) {if(pa->data // 取较小者 La 中的元素，将 pa 链接在 pc 的后面， pa 指针后移 else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;} // 取较小者 Lb 中的元素，将 pb 链接在 pc 的后面， pb 指针后移 7 用 La 的头结点作为 Lc 的头结点 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; } （ 2）将两个非递减的有序链表合并为一个非递增的有序链表。 , 不另外占用其它的存储空间。表中允许有重复的数据。 要求结果链表仍使用原来 插入剩余段 // 释放 Lb 的头结点 两个链表的存储空间 [ 题目分析 ] 合并后的新表使用头指针 Lc 指向， pa 和 pb 分别是链表 La 和 Lb 的工作指针 , 初始化为 相应链表的第一个结点，从第一个结点开始进行比较，当两个链表 点时，依次摘取其中较小者重新链接在 摘取 La 表中的元素，保留 余元素依次摘取，链接在 [ 算法描述 ] void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, ) {// 合并链表 La 和 Lb ，合并后的新表使用头指针 La 和 Lb 的工作指针 Lc 指向 pa=La->next; pb=Lb->next; //pa 和 pb 分别是链表 Lc=pc=La; // Lc->next=NULL; while(pa||pb ) {// 只要存在一个非空表，用 La 和 Lb 均为到达表尾结 Lc 表的表头结点之后，如果两个表中的元素相等，只 Lb 表中的元素。当一个表到达表尾结点，为空时，将非空表的剩 Lc 表的表头结点之后。 , 初始化为相应链表的第一个结点 用 La 的头结点作为 Lc 的头结点 q 指向待摘取的元素 if(!pa) {q=pb; pb=pb->next;} q 指向 pb ， pb 指针后移 //La 表为空，用 else if(!pb) {q=pa; pa=pa->next;} q 指向 pa ， pa 指针后移 La 中的元素，用 //Lb 表为空，用 else if(pa->data<=pb->data) {q=pa; pa=pa->next;} 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 的头结点 } 8 （ 3）已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。请设计算法求出 A 与 B 的交集，并存放于 [ 题目分析 ] A 链表中。 只有同时出现在两集合中的元素才出现在结果表中 La 和 Lb 的工作指针 , 合并后的新表使用头指针 Lc 指向。 pa 和 pb 分别是链表 , 初始化为相应链表的第一个结点， 从第一个结点开 始进行比较，当两个链表 La 表中的元素，删除 La 和 Lb 均为到达表尾结点时，如果两个表中相等的元素时，摘取 Lb 表中的元素；如果其中一个表中的元素较小时，删除此表中较小的 元素，此表的工作指针后移。当链表 La 和 Lb 有一个到达表尾结点，为空时，依次删除另一个非空表中的所有元素。 [ 算法描述 ] void Mix(LinkList& La, LinkList& Lb, LinkList& Lc) { pa=La->next;pb=Lb->next; pa 和 pb 分别是链表 Lc=pc=La; // while(pa&&pb) { if(pa->data==pb- >data) ∥交集并入结果表中。 La 和 Lb 的工作指针 , 初始化为相应链表的第一个结点 用 La 的头结点作为 Lc 的头结点 { pc->next=pa;pc=pa;pa=pa->next; u=pb;pb=pb->next; delete u;} else if(pa->data else {u=pb; pb=pb->next; delete u;} } while(pa) {u=pa; pa=pa->next; delete while(pb) {u=pb; pb=pb->next; delete u pc- >next=null; ∥置链表尾标记。 delete Lb; // } （ 4）已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。请设计算法求出两个集 A 中出现而不在 B 中出现的元素所构成的集合） ，并以同样的形 u;} ∥ 释放结点空间 ;} ∥释放结点空间 释放 Lb 的头结点 合 A 和 B 的差集（即仅由在 式存储，同时返回该集合的元素个数。 [ 题目分析 ] 求两个集合 A 和 B 的差集是指在 A 中删除 A 和 B 中共有的元素，即删除链表中的相应结 pre 指向前驱结点。 pa 和 pb 分别是链表 La 和 点 , 所以要保存待删除结点的前驱，使用指针 Lb 的工作指针 , 初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表 La 表中的元素小于 Lb 表中的元素， pre 置为 La 表的工 La 和 Lb 均为到达表尾结点时，如果 此表的工作指针后移。 [ 算法描述 ] 作指针 pa 删除 Lb 表中的元素；如果其中一个表中的元素较小时，删除此表中较小的元素， 当链表 La 和 Lb 有一个为空时， 依次删除另一个非空表中的所有元素。 9 void Difference （ LinkList& La, LinkList& Lb,int *n ） 0 { ∥差集的结果存储于单链表 pa=La->next; pb=Lb->next; ∥ pa 和 pb 分别是链表 pre=La; while （ pa&&pb ） La 中， *n 是结果集合中元素个数，调用时为 La 和 Lb 的工作指针 , 初始化为相应链表的第一个结点 ∥ pre 为 La 中 pa 所指结点的前驱结点的指针 ） {pre=pa;pa=pa->next;*n++;} {if （ pa->data ∥ A 链表中当前结点指针后移 else if （ pa->data>q->data ） q=q->next; ∥ B 链表中当前结点指针后移 else {pre->next=pa->next; u=pa; pa=pa->next; delete u;} } } （ 5）设计算法将一个带头结点的单链表 A 表中值小于零的结点，而 ∥处理 A， B 中元素值相同的结点，应删除 ∥删除结点 A 分解为两个具有相同结构的链表 C 表的结点为 A 表中值大于零的结点（链表 B、C，其中 B A 中的元 表的结点为 素为非零整数，要求 [ 题目分析 ] B、 C 表利用 A 表的结点） 。 B 表的头结点使用原来 A 表的头结点，为 p，判断结点 C 表。 C 表新申请一个头结点。从 A 表的第一个结点 0 的结点插入 开始，依次取其每个结点 p 的值是否小于 0，利用前插法，将小于 B 表 , 大于等于 0 的结点插入 [ 算法描述 ] void DisCompose(LinkedList A) { B=A; B->next= NULL; C=new p=A->next; while(p!= NULL) { r=p->next; if(p->data<0) {p->next=B->next; B- else } } （ 6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。 [ 题目分析 ] 10 ∥ B 表初始化 LNode;∥为 C 申请结点空间 ∥ C 初始化为空表 ∥ p 为工作指针 C->next=NULL; ∥暂存 p 的后继 >next=p; } ∥将小于 C- >next=p; 0 的结点链入 B 表 , 前插法 C 表 , 前插法 {p->next=C->next; } ∥将大于等于 0 的结点链入 p=r; ∥p 指向新的待处理结点。 假定第一个结点中数据具有最大值，依次与下一个元素比较，若其小于下一个元素，则 [ 算法描述 ] ElemType Max (LinkList L ){ if(L->next==NULL) return NULL; pmax=L->next; // p=L->next->next; while(p != NULL ){// p=p->next;// } return pmax->data; （ 7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的如果下一个结点存在 假定第一个结点中数据具有最大值 设其下一个元素为最大值，反复进行比较，直到遍历完该链表。 if(p->data > pmax->data) pmax=p;// 遍历链表 如果 p 的值大于 pmax 的值，则重新赋值 存储空间。 [ 题目分析 ] 从首元结点开始，逐个地把链表 [ 算法描述 ] void inverse(LinkList &L) {// 逆置带头结点的单链表 p=L->next; L->next=NULL; while ( p) { q=p->next; // q p->next=L->next; L->next=p; p = q; } } // *p L L 的当前结点 p 插入新的链表头部。 指向 *p 的后继 插入在头结点之后 （ 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; } // if (p) 11 查找第一个值 >mink 的结点 {while (p && p->data // q=pre->next; pre->next=p; // while (q!=p) { s=q->next; delete q; q=s; } // }//if } （ 9）已知 p 指向双向循环链表中的一个结点， change(p), [ 题目分析 ] 知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（ p 结点，前驱结点，前 其结点结构为 data 、prior 、next 三个域， 释放结点空间 查找第一个值 ≥ maxk 的结点 修改指针 写出算法 交换 p 所指向的结点和它的前缀结点的顺序。 驱的前驱结点，后继结点）六条链。 [ 算法描述 ] void Exchange {q=p->llink ； ； ； ； ； ∥ p 的前驱的前驱之后继为 ∥ p 的前驱指向其前驱的前驱。 （ LinkedList p ） p 所指结点与其前驱结点交换。 ∥ p 是双向循环链表中的一个结点，本算法将 q->llink->rlink=p p->llink=q->llink q->rlink=p->rlink q->llink=p ； p->rlink->llink=q p->rlink=q ； p ∥ p 的前驱的后继为 ∥ p 与其前驱交换 p 的后继。 p 的前驱 ∥ p 的后继的前驱指向原 ∥ p 的后继指向其原来的前驱 } ∥算法 exchange 结束。 （ 10 ）已知长度为 n 的线性表 A 采用顺序存储结构，请写一时间复杂度为 item 的数据元素。 O (n) 、空间复 杂度为 O(1) 的算法，该算法删除线性表中所有值为 [ 题目分析 ] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第 i+1 至第 n 个元素要依次前移） i 个元素，第 item 的数据元素，并未要 。本题要求删除线性表中所有值为 求元素间的相对位置不变。因此可以考虑设头尾两个指针（ 凡遇到值 item 的数据元素时，直接将右端元素左移至值为 i=1 ， j=n ），从两端向中间移动， item 的数据元素位置。 [ 算法描述 ] void Delete （ ElemType A[ ] ， int n ） A 中所有值为 。 item 的元素。 ∥ A 是有 n 个元素的一维数组，本算法删除 {i=1 ； j=n ；∥设置数组低、高端指针（下标） while （ i ） {while if if （ i ） i++ ； ∥若值不为 item ，左移指针。 item ，指针左移 （ i ） while （ i （ i ） A[i++]=A[j--] ； } ） j-- ；∥若右端元素为 12 第 3章 栈和队列 1．选择题 （ 1）若让元素 1， 2， 3 ， 4， 5 依次进栈，则出栈次序不可能出现在（ B．2，1，5， 4， 3 C． 4，3，1，2， 5 ）种情况。 A．5，4，3， 2， 1 答案： C D． 2， 3，5，4，1 解释：栈是后进先出的线性表，不难发现 C 选项中元素 1 比元素 2 先出栈，违背了栈 的后进先出原则，所以不可能出现 （ 2）若已知一个栈的入栈序列是 ）。 C 选项所示的情况。 1， 2， 3，, ， n，其输出序列为 p1 ， p2 ， p3 ，, ， pn ， 若 p1=n ，则 pi 为（ A． i 答案： C B ． n-i C ． n-i+1 D ．不确定 解释：栈是后进先出的线性表，一个栈的入栈序列是 n ，说明 1，2 ，3，, ， n 一次性全部进栈， 1， 2， 3，, ， n ，而输出序列的 再进行输出， 所以 p1=n ，p2=n-1 ，, ， 第一个元素为 pi=n-i+1 。 （ 3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾 元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）。 A． r-f 答案： D B ． (n+f-r)%n C ． n+r-f D ．（ n+r-f)%n 解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列， 所以需要将差值加上 MAXSIZE （本题为 n），然后与 MAXSIZE （本题为 n） 差值可能为负数， 求余，即（ n+r-f)%n 。 （ 4）链式栈结点为： (data,link) ， top 指向栈顶 .若想摘除栈顶结点，并将删除结点的值 ）。 保存到 x 中 ,则应执行操作（ A． x=top->data;top=top->link C． x=top;top=top->link 答案： A ； ； B． top=top->link;x=top->link D． x=top->link ； ； 解释： x=top->data 将结点的值保存到 即摘除栈顶结点。 x 中，top=top->link 栈顶指针指向栈顶下一结点， （ 5）设有一个递归算法如下 int fact(int n) { //n 大于等于 0 } ）。 C． n D． n+2 if(n<=0) return 1; else return n*fact(n-1); 则计算 fact(n) 需要调用该函数的次数为（ A． n+1 答案： A 13 B． n-1 解释：特殊值法。设 （ 6）栈在 （ A．递归调用 答案： D n=0 ，易知仅调用一次 fact(n) 函数，故选 A 。 ）中有所应用。 B．函数调用 C．表达式求值 D．前三个选项都有 解释：递归调用、函数调用、表达式求值均用到了栈的后进先出性质。 （ 7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻 辑结构应该是（）。 A．队列 答案： A B ．栈 C． 线性表 D．有序表 解释：解决缓冲区问题应利用一种先进先出的线性表，而队列正是一种先进先出的线 （ 8）设栈 S 和队列 Q 的初始状态为空，元素 Q ，若 6 个元素出队的序列是 e1、 e2 、 e3、 e4 、 e5 和 e6 依次进入栈 性表。 S， 一个元素出栈后即进入 量至少应该是（ e2、 e4 、e3 、 e6、 e5 和 e1 ，则栈 S 的容 ）。 B．3 C．4 D． 6 A．2 答案： B 解释：元素出队的序列是 e2、 e4 、 e3 、 e6、 e5 和 e1 ，可知元素入队的序列是 e2 、 e4、 e3 、 e6、 e5 和 e1，而元素 3 个元素，故栈 top 设为 n+1 ，则元素 e2、 e4、 e3、 e6、 e5 和 e1，即元素出栈的序列也是 e4、 e5 和 e6 依次进入栈，易知栈 （ 9）若一个栈以向量 )。 A． top++; V[top]=x; C． top--; V[top]=x; 答案： C 解释：初始栈顶指针 存储在向量空间 e1、 e2 、 e3、 S 中最多同时存在 S 的容量至少为 3。 ] 存储，初始栈顶指针 x 进栈的正确操 作是( B． V[top]=x; top++; D． V[top]=x; top--; top 为 n+1 ，说明元素从数组向量的高端地址进栈，又因为元素 top 指针先下移变为 n，之后将元素 x 存储在 V[n] 。 ）数据结构最 ] 中，所以进栈时 （ 10 ）设计一个判别表达式中左，右括号是否配对出现的算法，采用（ 佳。 A．线性表的顺序存储结构 C. 线性表的链式存储结构 答案： D 解释：利用栈的后进先出原则。 B ．队列 D. 栈 （ 11）用链接方式存储的队列，在进行删除运算时（ A. 仅修改头指针 C. 头、尾指针都要修改 答案： D B. D. ）。 仅修改尾指针 头、尾指针可能都要修改 14 解释：一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值。 （ 12 ）循环队列存储在数组 A. rear=rear+1 C. rear=(rear+1)%m 答案： D 解释：数组 ] ] 中，则入队时的操作为（ ）。 B. rear=(rear+1)%(m-1) D. rear=(rear+1)%(m+1) 中共含有 m+1 个元素，故在求模运算时应除以 m+1。 ）。 （ 13 ）最大容量为 n 的循环队列， 队尾指针是 A. (rear+1)%n==front C． rear+1==front 答案： B 解 释 ： 最 大 容 量 为 n 队 满 条 件 是 (rear+1)%n==front 。 ）。 rear ，队头是 front ，则队空的条件是 （ B. rear==front D. (rear-l)%n==front 的 循 环 队 列 ， ， 队 空 条 件 是 rear==front （ 14 ）栈和队列的共同点是（ A. 都是先进先出 C. 只允许在端点处插入和删除元素 答案： C B. D. 都是先进后出 没有共同点 解释：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头 （ 15 ）一个递归算法必须包括（ A. 递归部分 C. 迭代部分 答案： B B. D. 删除元素。 ）。 终止条件和递归部分 终止条件和迭代部分 2．算法设计题 （ 1）将编号为 0 和 1 的两个栈存放于一个数组空间 top[0] 等于 -1 时该栈为空，当第 V[m] 中，栈底分别处于数组的两端。 1 号栈的栈顶指针 top[1] 等于 m 时该 当第 0 号栈的栈顶指针 栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下： Typedef struct {int top[2],bot[2]; SElemType *V; int m; }DblStack [ 题目分析 ] 两栈共享向量空间，将两栈栈底设在向量两端，初始时，左栈顶指针为 -1 ，右栈顶为 m。 // 栈顶和栈底指针 // 栈数组 // 栈最大可容纳元素个数 两栈顶指针相邻时为栈满。两栈顶相向、迎面增长，栈顶指针指向栈顶元素。 [ 算法描述 ] 15 (1) 栈初始化 int Init() {[0]=-1; [1]=m; return 1; // 初始化成功 } (2) 入栈操作： int push(stk S ,int i,int x) ∥ i 为栈号， i=0 表示左栈， {if(i<0||i>1){ cout<< i=1 为右栈， x 是入栈元素。入栈成功返回 1，失败返回 0 “栈号输入不对 ”< if([1]-[0]==1) {cout<< “栈已满 ”< switch(i) {case 0: S.V[++[0]]=x; return(1); break; case 1: S.V[--[1]]=x; return(1); } } ∥ push (3) 退栈操作 ElemType pop(stk S,int i) ∥退栈。 i 代表栈号， ∥否则返回 -1 {if(i<0 || i>1){cout<< switch(i) {case 0: if([0]==-1) {cout<< else return(S.V[[0]--]); case 1: if([1]==m { cout<< else return(S.V[[1]++]); } ∥ switch } ∥算法结束 (4) 判断栈空 int Empty(); {return ([0]==-1 && [1]==m); } [ 算法讨论 ] 请注意算法中两栈入栈和退栈时的栈顶指针的计算。左栈是通常意义下的栈，而右栈入 1），退栈时，栈顶指针右移（加 1）。 “栈空 ”< i=0 时为左栈， i=1 时为右栈。退栈成功时返回退栈元素 “栈号输入错误 ”< “栈空 ”< 栈操作时，其栈顶指针左移（减 （ 2）回文是指正读反读均相同的字符序列，如“ abba ”和“ abdba ”均是回文，但“ (提示：将一半字符入栈 ) good ” 不是回文。试写一个算法判定给定的字符向量是否为回文。 16 [ 题目分析 ] 将字符串前一半入栈，然后，栈中元素和字符串后一半进行比较。即将第一个出栈元素 ,, ，直至 是回文。 和后一半串中第一个字符比较，若相等，则再出栈一个元素与后一个字符比较， 栈空，结论为字符序列是回文。在出栈元素与串中字符比较不等时，结论字符序列不 [ 算法描述 ] #define StackSize 100 // typedef char DataType;// typedef struct {DataType data[StackSize]; int top; }SeqStack; int IsHuiwen( char *t) {// 判断 t 字符向量是否为回文，若是，返回 SeqStack s; int i , len; char temp; InitStack( &s); len=strlen(t); // for ( i=0; i Push( &s, t[i]); while( !EmptyStack( &s)) {// 每弹出一个字符与相应字符比较 求向量长度 将一半字符入栈 假定预分配的栈空间最多为 假定栈元素的数据类型为字符 100 个元素 1，否则返回 0 temp=Pop (&s); if( temp!=S[i]) return 0 ;// 不等则返回 0 else i++; } return 1 ; // } （ 3）设从键盘输入一整数的序列： ai ≠ -1 时，将 a1 , a2, a3 ， ⋯ ， an ，试编写算法实现：用栈结构存储 ai =-1 时，输出栈顶整数并出栈。算法应对异常情 比较完毕均相等则返回 1 输入的整数，当 ai 进栈；当 况（入栈满等）给出相应的信息。 [ 算法描述 ] #define maxsize 栈空间容量 void InOutS(int s[maxsize]) //s 是元素为整数的栈，本算法进行入栈和退栈操作。 {int top=0; //top 为栈顶指针，定义 个整数序列作处理。 top=0 时为栈空。 for(i=1; i<=n; i++) //n 17 {cin>>x); // if(x!=-1) // 从键盘读入整数序列。 读入的整数不等于 入栈。 -1 时入栈。 ｛ if(top==maxsize-1){cout<< else s[++top]=x; //x ｝ else // 读入的整数等于 “栈满” < -1 时退栈。 << s[top--]< {if(top==0){ cout<< else cout<< } }// 算法结束。 “栈空” < “出栈元素是” （ 4）从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式 $符作为输入结束，操作数之间用空格分隔 234 34+2*$ 。 , 操作符只可能有 + 、 - 、 * 、 的长度不超过一行，以 / 四种运算。例如： [ 题目分析 ] 逆波兰表达式 ( 即后缀表达式 ) 求值规则如下：设立运算数栈 OPND,对表达式从左到右扫 OPND退出两个数， 描 ( 读入 ) ，当表达式中扫描到数时，压入 进行相应运算，结果再压入 OPND栈。当扫描到运算符时，从 OPND 栈。这个过程一直进行到读出表达式结束符 $，这时 OPND 栈中只有一个数，就是结果。 [ 算法描述 ] float expr( ) // 从键盘输入逆波兰表达式，以‘ ｛ float OPND[30]; // OPND init(OPND); cin>>x;//x // float num=0.0; // $ ’表示输入结束，本算法求逆波兰式表达式的值。 是操作数栈。 两栈初始化。 数字初始化。 是字符型变量。 while(x!= ’$’) {switch {case ‘0’<=x<=’9’: while((x>= ’0’&&x<=’9’)||x== ’. ’) // if(x!= ’. ’) else // // 处理整数 拼数 {num=num*10+ （ ord(x)- {scale=10.0; cin>>x; while(x>= ’0’&&x<=’9’) {num=num+(ord(x)- }//else 18 ord( ‘0’) ） ; cin>>x;} 处理小数部分。 ord( ‘0’)/scale; scale=scale*10; cin>>x; } push(OPND,num); num=0.0;// case x= case x= case x= case x= case x= default: }// }// // ‘ ’:break; // 数压入栈，下个数初始化 遇空格，继续读下一个字符。 ‘+’:push(OPND,pop(OPND)+pop(OPND));break; ‘ - ’ :x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break; ‘* ’:push(OPND,pop(OPND)*pop(OPND));break; ‘ / ’ :x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break; 其它符号不作处理。 结束 switch 读入表达式中下一个字符。 结束 while （ x！ =‘$’） < cin>>x;// cout<< “后缀表达式的值为” }// 算法结束。 [ 算法讨论 ] 假设输入的后缀表达式是正确的，未作错误检查。算法中拼数部分是核心。 0 ’且小于等于‘ 9’的字符，认为是数。这种字符的序号减去字符‘ 0’的 若遇到大于等于‘ 序号得出数。对于整数，每读入一个数字字符，前面得到的部分数要乘上 10 再加新读入的数 得到新的部分数。当读到小数点，认为数的整数部分已完，要接着处理小数部分。小数部分 的数要除以 10 （或 10 的幂数）变成十分位，百分位，千分位数等等，与前面部分数相加。 num 恢复为 0， 在拼数过程中，若遇非数字字符，表示数已拼完，将数压入栈中，并且将变量 准备下一个数。这时对新读入的字符进入‘ 处理数字字符的 case 后，不能加入 break 语句。 +’、‘ - ’、‘ * ’、‘ / ’及空格的判断，因此在结束 （ 5）假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操 I 和 O 组成的序列， 称可以操作的序列为合法序列， D. IIIOOIOO 若合法， 返回 true ， 否则称为非法序列。 作序列可表示为仅由 ①下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO ②通过对①的分析，写出一个算法，判定所给的操作序列是否合法。 false （假定被判定的操作序列已存入一维数组中） 。 否则返回 答案： ① A 和 D 是合法序列， int Judge(char A[]) // {i=0; j=k=0; while(A[i]!= {switch(A[i]) {case ‘I ’: j++; break; // 入栈次数增 19 B 和 C 是非法序列。 A 中。 ②设被判定的操作序列已存入一维数组 判断字符数组 false 。 //i //j A 中的输入输出序列是否是合法序列。如是，返回 为下标。 true ，否则返回 和 k 分别为 I 和字母 O 的的个数。 ‘ 0’) // 当未到字符数组尾就作。 1。 case } i++; // if(j!=k) {cout<< else { cout<< }// [ ‘O’: k++; if(k>j){ cout<< “序列非法” < 不论 A[i] 是‘ I ’或‘ O’，指针 i 均后移。 } “序列非法” “序列合法” < < I ’和‘ O’组成的字符串）的任一位置，入栈次数 O’的个数） ，否则视作非法序列，立即给出 0 ’），入栈次数必须等 算法结束。 算法讨论 ] 在入栈出栈序列（即由‘ （‘ I ’的个数）都必须大于等于出栈次数（即‘ 信息，退出算法。整个序列（即读到字符数组中字符串的结束标记‘ 于出栈次数（题目中要求栈的初态和终态都为空） ，否则视为非法序列。 (6 ）假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点 、入队和出队等算法。 ( 注意不 设头指针 ) ，试编写相应的置空队、判队空 [ 题目分析 ] 置空队就是建立一个头节点，并把头尾指针都指向头节点，头节点是不存放数据的；判 1还是等于 1的 队空就是当头指针等于尾指针时，队空；入队时，将新的节点插入到链队列的尾部，同时将 尾指针指向这个节点；出队时，删除的是队头节点，要注意队列的长度大于 情况，这个时候要注意尾指针的修改，如果等于 1 ，则要删除尾指针指向的节点。 [ 算法描述 ] // 先定义链队结构 {Datatype data; struct queuenode *next; }QueueNode; // 以上是结点类型的定义 typedef struct {queuenode *rear; }LinkQueue; // 只设一个指向队尾元素的指针 : typedef struct queuenode (1) 置空队 void InitQueue( LinkQueue *Q) { // 置空队：就是使头结点成为队尾元素 QueueNode *s; Q->rear = Q->rear->next;// {s=Q->rear->next; Q->rear->next=s->next; delete s; }// 回收结点空间 20 将队尾指针指向头结点 当队列非空，将队中元素逐个出队 while (Q->rear!=Q->rear->next)// } (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) {// 当队列中只有一个结点时， Q->rear = Q->rear->next; Q->rear->next=p->next; } else Q->rear->next->next=p->next;// delete p;// 释放被删结点 return x; } p 结点出队后，要将队尾指针指向头结点 摘下结点 p 21 （ 7）假设以数组 Q[ m]存放循环队列中的元素 , 同时设置一个标志 tag ，以 tag == 0 和 tag “空 ”还是 “满 ”。试编写与 == 1 来区别在队头指针 (front )和队尾指针 ( rear )相等时，队列状态为 此结构相应的插入 [ 算法描述 ] (1) 初始化 (enqueue )和删除 (dlqueue )算法。 SeQueue QueueInit(SeQueue Q) {// 初始化队列 ==0; =0; return Q; } (2) 入队 SeQueue QueueIn(SeQueue Q,int e) {// 入队列 if((==1) && (==)) cout<<" else {=(+1) % m; []=e; if(==0) =1; // } return Q; } (3) 出队 ElemType QueueOut(SeQueue Q) {// 出队列 if(==0) { cout<<" else {=(+1) % m; e=[]; if(==) =0; // } return(e); } (8 ）如果允许在循环队列的两端都可以进行插入和删除操作。要求： ① 写出循环队列的类型定义； ② 写出“从队尾删除”和“从队头插入”的算法。 [ 题目分析 ] 用一维数组 和队尾指针 rear ，约定 v[0..M-1] front 实现循环队列，其中 指向队头元素的前一位置， 22 队列已满 "< 队列已不空 队列为空 "< 空队列 M 是队列长度。设队头指针 rear 指向队尾元素。定义 front front=rear 时为队空， (rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展， 队尾端入队向下标大的方向发展。 [ 算法描述 ] ① #define M typedef struct {elemtp data[M]; int front,rear; }cycqueue; ② elemtp delqueue ( cycqueue Q) //Q 是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素， 否则给出出错信息。 {if (==) { cout<<" =(-1+M)%M; }// 从队尾删除算法结束 // return([(+1+M)%M]); // 队列空 "< 修改队尾指针。 返回出队元素。 队列可能达到的最大长度 void enqueue (cycqueue Q, elemtp x) // Q 是顺序存储的循环队列，本算法实现“从队头插入”元素 {if (==(-1+M)%M) { cout<<" []=x; }// //x 入队列 修改队头指针。 x。 队满 "< =(-1+M)%M; // 结束从队头插入算法。 （ 9）已知 Ackermann 函数定义如下 : ① 写出计算 ② 写出计算 [ 算法描述 ] int Ack(int m,n) Ack(m,n) 的递归算法，并根据此算法给出出 Ack(m,n) 的非递归算法。 Ack(2,1) 的计算过程。 {if (m==0) return(n+1); else if(m!=0&&n==0) return(Ack(m-1,1)); else return(Ack(m-1,Ack(m,m-1)); }// 算法结束 ① Ack(2,1) 的计算过程 23 Ack(2,1)= Ack(1,Ack(2,0)) = Ack(1,Ack(1,1)) // // // // // // // // 因 m<>0,n<>0 而得 因 m<>0,n=0 而得 因 m<>0,n<>0 而得 因 m<>0,n=0 而得 因 m=0 而得 因 m=0 而得 = Ack(1,Ack(0,Ack(1,0))) = Ack(1,Ack(0,Ack(0,1))) = Ack(1,Ack(0,2)) = Ack(1,3) = Ack(0,Ack(1,2)) = Ack(0,Ack(0,Ack(1,1))) 因 m<>0,n<>0 而得 因 m<>0,n<>0 而得 因 m<>0,n<>0 而得 因 m<>0,n=0 而得 因 m=0 而得 因 m=0 而得 = Ack(0,Ack(0,Ack(0,Ack(1,0)))) // = Ack(0,Ack(0,Ack(0,Ack(0,1)))) // = Ack(0,Ack(0,Ack(0,2))) = Ack(0,Ack(0,3)) = Ack(0,4) // // // // 因 n=0 而得 因 n=0 而得 =5 ② int Ackerman(int m, int n) {int akm[M][N];int i,j; for(j=0;j for(i=1;i {akm[i][0]=akm[i-1][1]; for(j=1;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 24 { 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; } } 25 第 4 章 串、数组和广义表 1．选择题 （ 1）串是一种特殊的线性表，其特殊性体现在（ A ．可以顺序存储 C ．可以链式存储 答案： B （ 2）串下面关于串的的叙述中， A ．串是字符的有限序列 C．模式匹配是串的一种重要运算 答案： B （ ）是不正确的？ B ．空串是由空格构成的串 D ．串既可以采用顺序存储，也可以采用链式存储 ）。 B ．数据元素是一个字符 D ．数据元素可以是多个字符若 解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串，零个字符的串成为空串，其长度为零。 （ 3）串“ ababaaababaa ”的 next 数组为（ A ． 答案： C （ 4）串“ ababaabab ”的 nextval 为（ A ． 010104101 答案： A （ 5）串的长度是指（ ）。 ）。 ）。 B ． C． D ． 5 B ． 010102101 C ． 010100011 D ． 010101011 A ．串中所含不同字母的个数 C ．串中所含不同字符的个数 答案： B 解释：串中字符的数目称为串的长度。 （ 6）假设以行序为主序存储二维数组 10 ，则 LOC[5,5]= （ B． 818 B ．串中所含字符的个数 D ．串中所含非空格字符的个数 A=array[1..100,1..100] ）。 ，设每个数据元素占 2 个存 储单元，基地址为 A． 808 答案： B C． 1010 D ． 1020 解释：以行序为主，则 LOC[5,5]=[ （ 5-1 ） *100+ （ 5-1 ） ]*2+10=818 。 3 字节， i 的值为 1 到 8，j 的值为 1 到 10 ， ）。 （ 7）设有数组 A[i,j] ，数组的每个元素长度为 BA 开始顺序存放， 数组从内存首地址 A ． BA+141 答案： B 当用以列为主存放时， 元素 A[5,8] 的存储首地址为 （ D ． BA+225 B ． BA+180 C． BA+222 解释：以列序为主，则 （ 8）设有一个 LOC[5,8]=[ （ 8-1 ） *8+ （ 5-1 ） ]*3+BA=BA+180 。 A ，采用压缩存储方式，以行序为主存储， a85 的地址为（ 26 ）。 10 阶的对称矩阵 a11 为第一元 素，其存储地址为 1，每个元素占一个地址空间，则 A． 13 答案： C B． 32 C． 33 D． 40 （ 9）若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的元素 (包括主对角线上所有 元素 ) 依次存放于一维数组 B[1..(n(n+1))/2] 中，则在 B 中确定 a（ i ）。 ij A ． i*(i-1)/2+j 答案： B B ． j*(j-1)/2+i C ． i*(i+1)/2+j 10 个字符组成的串，其行下标 D ． j*(j+1)/2+i （ 10 ）二维数组 A 的每个元素是由 j=1,2, , ,10 。若 A 按行先存储，元素 i=0,1, , ,8, 列下标 ） A[8,5] 的起始地址与当 A 按列先存储时的元素（ 的起始地址相同。设每个字符占一个字节。 A ． A[8,5] 答案： B 解释：设数组从内存首地址 M 开始顺序存放，若数组按行先存储，元素 A[8,5] 的起 A[3,10] 的 B ． A[3,10] C. A[5,8] D ． A[0,9] 始地址为： M+[ （ 8-0 ） *10+ （ 5-1 ） ]*1=M+84 ；若数组按列先存储，易计算出元素 起始地址为： M+[ （ 10-1 ） *9+ （ 3-0 ） ]*1=M+84 。故选 B。 （ 11）设二维数组 A[1.. m ， 1.. n] （即 m 行 n 列）按行存储在数组 B 中的下标为（ ）。 B[1.. m*n] 中，则二维 数组元素 A[i,j] 在一维数组 A ． (i-1)*n+j 答案： A B ． (i-1)*n+j-1 C． i*(j-1) D ． j*m+i-1 解释：特殊值法。取 i=j=1 ，易知 A[1,1] 的的下标为 1，四个选项中仅有 A 选项能确定的值为 1，故选 A 。 （ 12 ）数组 A[0..4,-1..-3,5..7] 中含有元素的个数（ C．36 ）。 A．55 答案： B 解释：共有 B．45 5*3*3=45 个元素。 D．16 （ 13 ）广义表 A=(a,b,(c,d),(e,(f,g))) A ． (g) 答案： D 解释： Tail(A)=(b,(c,d),(e,(f,g))) ，则 Head(Tail(Head(Tail(Tail(A))))) C ． c ； Tail(Tail(A))=( (c,d),(e,(f,g))) D． d 的值为（ ）。 B ． (d) ； Head(Tail(Tail(A)))= 。 D ． (b,c,d) (c,d) ； Tail(Head(Tail(Tail(A))))=(d) ； Head(Tail(Head(Tail(Tail(A)))))=d ），表尾是（ ）。 （ 14 ）广义表 ((a,b,c,d)) 的表头是（ A ． a 答案： C、 B B ． ( ) C． (a,b,c,d) 解释：表头为非空广义表的第一个元素，可以是一个单原子，也可以是一个子表， ((a,b,c,d)) 的表头为一个子表 (a,b,c,d) ；表尾为除去表头之外，由其余元素构成的表，表为一定是个广义表， ((a,b,c,d)) 的表尾为空表 ( ) 。 （ 15 ）设广义表 L=((a,b,c)) ，则 L 的长度和深度分别为（ A．1和1 答案： C 27 ）。 B．1和 3 C．1和 2 D．2和3 解释：广义表的深度是指广义表中展开后所含括号的层数，广义表的长度是指广义表 中所含元素的个数。根据定义易知 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 13 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，列下标从 到 11 ，从首地址 S 开始连续存放主存储器中，主存储器字长为 16 位。求： ① 存放该数组所需多少单元？ ② 存放数组第 4 列所有元素至少需多少单元？ ③ 数组按行存放时，元素 A[7,4] 的起始地址是多少？ ④ 数组按列存放时，元素 A[4,7] 的起始地址是多少？ 答案： 每个元素 32 个二进制位，主存字长 16 位，故每个元素占 2 个字长，行下标可平移至 到 11。 （ 1） 242 （ 2） 22 （ 3） s+182 （ 4） s+142 28 1 1 (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 个数字）。 10 个共 36 个，所以设一长 36 的整型数组， 余下存放字母出现的次数。 [ 题目分析 ] 由于字母共 26 个，加上数字符号 前 10 个分量存放数字字符出现的次数， 时，字符的 从字符串中读出数字字符 ASCII 代码值减去数字字符 ‘0’的 ASCII 代码值，得出其数值 (0..9) ，字母的 ASCII 代码值减去字符‘ [ 算法描述 ] void Count （） A’的 ASCII 代码值加上 10 ，存入其数组的对应下标分量中。遇其它 符号不作处理，直至输入字符串结束。 // 统计输入字符串中数字字符和字母字符的个数。｛ 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<< “数字” < for （ i ＝ 10 ； i<36 ； i++ ） // cout<< “字母字符” ｝ “的个数 = ” < 求出字母字符的个数 < “的个数 =” < （ 2）写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。 [ 题目分析 ] 实现字符串的逆置并不难，但本题“要求不另设串存储空间”来实现字符串 [ 算法描述 ] void InvertStore( char A[]) 逆序存储，即第一个输入的字符最后存储，最后输入的字符先存储，使用递归可容易做到。 // 字符串逆序存储的递归算法。 { char ch; static cin>>ch; if (ch!= '.') // 规定 '.' 是字符串输入结束标志 29 int i = 0;// 需要使用静态变量 {InvertStore(A); A[i++] = ch;// } A[i] = '0'; // } 字符串结尾标记 字符串逆序存储 （ 3）编写算法，实现下面函数的功能。函数 字符串 t 插入到字符串 void insert(char*s,char*t,int pos) pos 。假设分配给字符串 s 的空间足够让字符串 将 t t 。首 t 的长 s 中，插入位置为 插入。（说明：不得使用任何库函数） [ 题目分析 ] 本题是字符串的插入问题，要求在字符串 s 的 pos 位置，将第 t 复制到字符串 pos 个字符到字符串 s 的第 pos 位置后。 1 或大于串 s 的长度均为非法，因题目假设给字 s 的 pos 位置，插入字符串 s 尾的子串向后移动字符串 先应查找字符串 度，然后将字符串 对插入位置 pos 要验证其合法性，小于 符串 s 的空间足够大，故对插入不必判溢出。 [ 算法描述 ] void insert(char *s,char *t,int pos) // 将字符串 t 插入字符串 s 的第 pos 个位置。 ， q 分别为字符串 < {int i=1,x=0; char *p=s,*q=t; //p if(pos<1) {cout<< while(*p!= ’ // 若 pos 小于串 else // 0’&&i s 长度，则查到 s 和 t 的工作指针 “pos 参数位置非法” 查 pos 位置 pos 位置时， i=pos 。 位置大于字符串 s 的长度 ";exit(0);} if(*p == '/0') { cout< 查找字符串的尾 while(*p!= while(*q!= '/0') '0') {p++; i++;} // {q++; x++; } // 查到尾时， i 为字符 ‘ 0 ’的下标， p 也指向 ‘ 0 ’。 查找字符串 t 的长度 x ，循环结束时 q 指向 '0' 。 串 s 的 pos 后的子串右移，空出串 t 的位 for(j=i;j>=pos ;j--){*(p+x)=*p; p--;}// 置。 q--; // 指针 q 回退到串 t 的最后一个字符 将 t 串插入到 s 的 pos 位置上 也后移了，而串 t 的结尾标记不应插入到 format(s1,s2,s3,n), S3。 for(j=1;j<=x;j++) *p--=*q--; // [ 算法讨论 ] 串 s 的结束标记 ('0') （ 4）已知字符串 s 中。 S1 中存放一段英文，写出算法 S2, 其多余的字符送 s1 拆分成字符串 ，即长度为 s3 中。 将其按给定的长 度 n 格式化成两端对齐的字符串 [ 题目分析 ] 本题要求字符串 s2 和字符串 s3 ，要求字符串 s2“按给定长 度 n 格式化成两端对齐的字符串” 描字符串 然后将余下字符复制到字符串 [ 算法描述 ] n 且首尾字符不得为空格字符。 n ，第 n 个拷入字符串 算法从左到右扫 s1 ，找到第一个非空格字符，计数到 s2 的字符不得为空格， 30 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 为空串或空格串 "< } while( *p!='0' && i // 字符串 s1 向字符串 s2 中复制 if(*p =='0'){cout<<" 字符串 s1 没有 "< "< if(*(--q)==' ' ) // 若最后一个字符为空格，则需向后找到第一个非空格字符 {p-- ; //p 指针也后退 while(*p==' '&&*p!='0') p++;// 往后查找一个非空格字符作串 s2 的尾字符 if(*p=='0') {cout<<"s1 串没有 "< "< *q=*p; // 字符串 s2 最后一个非空字符 *(++q)='0'; // 置 s2 字符串结束标记 } *q=s3;p++; // 将 s1 串其余部分送字符串 s3 。 while (*p!= '0') {*q=*p; q++; p++;} *q='0'; // 置串 s3 结束标记 } （ 5）设二维数组 , 1..n] 含有 m*n 个整数。 ① 写一个算法判断 a 中所有元素是否互不相同 ? 输出相关信息 (yes/no) ； ② 试分析算法的时间复杂度。 ① [ 题目分析 ] 判断二维数组中元素是否互不相同， 只有逐个比较 , 找到一对相等的元素， 可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次？在当前行，每个 元素要同本行后面的元素比较一次（下面第一个循环控制变量 p 的 for 循环），然后同第 行及以后各行元素比较一次，这就是循环控制变量k 和 p 的二层 for 循环。 [ 算法描述 ] int JudgEqual(ing a[m][n],int m,n) // 判断二维数组中所有元素是否互不相同，如是，返回 1；否则，返回 0。 {for(i=0;i for(j=0;j {for(p=j+1;p 和同行其它元素比较 if(a[i][j]==a[i][p]) {cout<< “no” ; return(0); } // 只要有一个相同的，就结论不是互不相同 31 就 i+1 for(k=i+1;k for(p=0;p if(a[i][j]==a[k][p]) { cout<< }// for(j=0;j cout<< “ yes ” ; return(1); // }// 算法 JudgEqual 结束 和第 i+1 行及以后元素比较 “no” ; return(0); } 元素互不相同 ②二维数组中的每一个元素同其它元素都比较一次，数组中共 2 个元素同其它 m*n 个元素，第 1 个元素同 其它 m*n-1 个元素比较，第 +2+1=（ m*n）(m*n-1)/2 同 , 设在 (m*n-1) 复杂度是 O(n 4 ) 。 m*n-2 个元素比较， ,, ，第 , 可能第一次比较就相同 m*n-1 个元素同最 后 一 个 元 素 (m*n) 比 较 一 次 , 所以 在 元 素互 不相 等 时 总 的 比 较 次 数 为 (m*n-1)+(m*n-2)+ , 。在有相同元素时 , 也可能最后一次比较时相 m*n ）(m*n-1)/4 ，总的时间 个位置上均可能相同 , 这时的平均比较次数约为（ (6) 设任意 n 个整数存放于数组A(1:n) 中，试编写算法，将所有正数排在所有负数前面 0(n) ）。 [ 题目分析 ] 本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针 j 自大至小搜索到正数停止。然后 i 和 j 所指数据交换， （要求算法复杂度为 i 和 j ，i 自小至大搜索到负数停止， 继续以上过程，直到 [ 算法描述 ] void Arrange(int A[],int n) //n 个整数存于数组 {int i=0,j=n-1,x; // while(i {while(i while(i if(i }// while(i }// 算法 Arrange 结束 . i=j 为止。 A 中，本算法将数组中所有正数排在所有负数的前面 用类 C 编写，数组下标从 0 开始 交换 A[i] 与 A[j] [ 算法讨论 ] 对数组中元素各比较一次，比较次数为 ( 负数均在正数前面 O(1). n。最佳情况 ( 已排好 , 正数在前 , 负数 ) 发生 n/2 次交换。用类 c 编写，数组界偶是 在后 ) 不发生交换，最差情况 0..n-1 。空间复杂度为 32 第 5 章 树和二叉树 1．选择题 （ 1）把一棵树转换为二叉树后，这棵二叉树的形态是（ A．唯一的 C．有多种，但根结点都没有左孩子 答案： A Ｂ．有多种 Ｄ．有多种，但根结点都没有右孩子 ）。 解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。 （ 2）由 3 个结点可以构造出多少种不同的二叉树？（ ） D． 5 A． 2 答案： D B ． 3 C ． 4 解释：五种情况如下： A A B C C B B C C A A B A B C ）。 （ 3）一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（ C ．254 D ．501 A．250 答案： D B ． 500 解释：设度为 0 结点（叶子结点）个数为 A，度为 1 的结点个数为 B，度为 2 的结点个 B=0 或 1，又因 数为 C，有 A=C+1， A+B+C=1001 ，可得 2C+B=1000 ，由完全二叉树的性质可得 为 C 为整数，所以 （ 4）一个具有 A．11 答案： C 解释：若每层仅有一个结点，则树高 h 为 1025 ；且其最小树高为 B B=0， C=500 ， A=501 ，即有 501 个叶子结点。 1025 个结点的二叉树的高 ．10 C h 为（ ）。 ．11 至 1025 之间 D ．10 至 1024 之间 log 2 1025 + 1=11 ， 即 h 在 11 至 1025 之间。 （ 5）深度为 k-1 h 的满 m叉树的第 k 层有（ k ）个结点。 h-1 (1= h A． m 答案： A B ． m-1 C h ． m D ． m-1 k-1 解释：深度为 h 的满 m 叉树共有 m -1 个结点，第 k 层有 m 个结点。 （ 6）利用二叉链表存储树，则根结点的右指针是（ ）。 A．指向最左孩子 答案： C B ．指向最右孩子 C ．空 D．非空 33 解释：利用二叉链表存储树时，右指针指向兄弟结点，因为根节点没有兄弟结点，故根节点的右指针指向空。 （ 7）对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的 ）遍历实 编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ 现编号。 A．先序 答案： C 解释：根据题意可知按照先左孩子、再右孩子、最后双亲结点的顺序遍历二叉树，即 （ 8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用 ）遍历方法最合适。 A．前序 答案： C B. 中序 C. 后序 D. 从根开始按层次遍历 后序遍历二叉树。 （ B ．中序 C ．后序 D ．按层次 解释：后续遍历和层次遍历均可实现左右子树的交换 （ 9）在下列存储形式中， A．双亲表示法 答案： D （ ，不过层次遍历的实现消耗比后 续大，后序遍历方法最合适。 ）不是树的存储形式？ B ．孩子链表表示法 C ．孩子兄弟表示法 D ．顺序存储表示法 解释：树的存储结构有三种：双亲表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵树都能通过孩子兄弟表示法转换为二叉树进行存储。 （ 10 ）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）。 A．所有的结点均无左孩子 C．只有一个叶子结点 答案： C D B ．所有的结点均无右孩子 ．是任意一棵二叉树 解释：因为先序遍历结果是“中左右” ，后序遍历结果是“左右中” ，当没有左子树时， 。则所有的结点均无左 就是“中右”和“右中” ；当没有右子树时，就是“中左”和“左中” 孩子或所有的结点均无右孩子均可，所以 点均无右孩子时，均只有一个叶子结点，故选 （ 11）设哈夫曼树中有 A． 99 C． 101 答案： B 解释：在哈夫曼树中没有度为 叶子结点的个数为 A、B 不能选，又所有的结点均无左孩子与所有的结 C。 ）个叶子结点。 199 个结点，则该哈夫曼树中有（ B． 100 D． 102 1 的结点，只有度为 0（叶子结点）和度为 2 的结点。设 n= n0 ，度为 2 的结点的个数为 n2 ，由二叉树的性质 n0=n2+1 ，则总结点数 n0+n2=2*n0-1 ，得到 n0=100 。 （ 12 ）若 X 是二叉中序线索树中一个有左孩子的结点， A． X 的双亲 B 且 X 不为根， 则 X 的前驱为 （ ）。 ． X 的右子树中最左的结点 34 C． X 的左子树中最右结点 答案： C （ 13 ）引入二叉线索树的目的是（ D ． X 的左子树中最右叶结点 ）。 A．加快查找结点的前驱或后继的速度 C．为了能方便的找到双亲 答案： A D B ．为了能在二叉树中方便的进行插入与删 除 ．使二叉树的遍历结果唯一 （ 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 ①画出这棵二叉树。 ②画出这棵二叉树的后序线索树。 ③将这棵二叉树转换成对应的树（或森林） 。 答案： 35 ）。 A A B C B C A C B E D EH D E null G ① H D F G F F G H ② ③ （ 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}，按哈夫曼规则： （ 100 ） （ 40） 19 【 [ （ 2,3 ）， 6], (7,10) 】 , ,,19, 21, 32 （ 60） 21 32 （ 28） （17） （ 11） 7 10 6 2 （ 5） 3 0 0 19 1 0 21 32 1 1 0 0 7 1 0 10 6 1 1 1 36 0 23 方案比较： 字 对 应 出现 字 对应 出 现 母编号 编码 频率 母编号 编码 频率 1 1100 0.07 1 000 0.07 2 00 0.19 2 001 0.19 3 11110 0.02 3 010 0.02 4 1110 0.06 4 011 0.06 5 10 0.32 5 100 0.32 6 11111 0.03 6 101 0.03 7 01 0.21 7 110 0.21 8 1101 0.10 8 111 0.10 方案 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 37 终态： 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，如果二叉树不为空且左右子树为空，返回 二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数。 [ 算法描述 ] int LeafNodeCount(BiTree T) { if(T==NULL) return 0; // 如果是空树，则叶子结点个数为 0 else if(T->lchild==NULL&&T->rchild==NULL) return 1; // 判断结点是否是叶子结点（左孩子右孩子都为空） ，若是则返回 1 else return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild); } （ 2）判别两棵树是否相等。 38 ，如果 1 [ 题目分析 ] 先判断当前节点是否相等 前节点不相等， 右孩子是否相等。 [ 算法描述 ] 直接返回两棵树不相等 ( 需要处理为空、是否都为空、是否相等 ; 如果当前节点相等， ) ，如果当 那么就递归的判断他们的左 int compareTree(TreeNode* tree1, TreeNode* tree2) // 用分治的方法做，比较当前根，然后比较左子树和右子树 {bool tree1IsNull = (tree1==NULL); bool tree2IsNull = (tree2==NULL); if(tree1IsNull != tree2IsNull) { return 1; } if(tree1IsNull && tree2IsNull) {// 如果两个都是 return 0; }// 如果根节点不相等，直接返回不相等，否则的话，看看他们孩子相等不相等 NULL ，则相等 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->lchild==NULL&&T->rchild==NULL) return; else { temp = T->lchild; T->lchild = T->rchild; T->rchild = temp; 39 }// 交换左右孩子 ChangeLR(T->lchild); ChangeLR(T->rchild); } （ 4）设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问// 递归交换左子树 //递归交换右子树 这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。 [ 题目分析 ] 若树为空，返回；若某结点为叶子结点，则仅输出该结点；否则先输出该结 [ 算法描述 ] void DoubleTraverse(BiTree T) { if(T == NULL) return; else if(T->lchild==NULL&&T->rchild==NULL) cout< else { cout< DoubleTraverse(T->lchild); // cout< DoubleTraverse(T->rchild); // } } （ 5）计算二叉树最大的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大 递归遍历右子树 递归遍历左子树 点，递归遍历其左子树，再输出该结点，递归遍历其右子树。 // 叶子结点输出 值）。 [ 题目分析 ] 求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法，记下各层 结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。 [ 算法描述 ] int Width(BiTree bt)// {if (bt==null) return (0); // else {BiTree Q[];//Q 是队列，元素为二叉树结点指针，容量足够大 求二叉树 bt 的最大宽度 空二叉树宽度为 0 front=1;rear=1;last=1; //front 队头指针 ,rear //temp // 队尾指针 ,last 根结点入队列 同层最右结点在队列中的位置 temp=0; maxw=0; Q[rear]=bt; while(front<=last) 记局部宽度 , maxw 记最大宽度 40 {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 的结点数目。 [ 题目分析 ] 若某个结点左子树空右子树非空或者右子树空左子树非空，则该结点为度为 [ 算法描述 ] 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< 出队 , 访问结点 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[]; 41 的结点1 //l, s int i 是栈，元素是二叉树结点指针， ， top=0,tag[],longest=0; l 中保留当前最长路径中的结点 while(p || top>0) {while(p) {s[++top]=p if(tag[top]==1) // if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;} // 保留当前最长路径到 } else if(top>0) {tag[top]=1; p=s[top].Rc;} // }//while(p!=null||top>0) }// 结束 LongestPath （ 8）输出二叉树中从每个叶子结点到根结点的路径。 [ 题目分析 ] 采用先序遍历的递归方法， 当找到叶子结点 b->data 值。 *b 时，由于 *b 叶子结点尚未添加 沿右子分枝向下 ； tag[top]=0; p=p->Lc;} // 当前结点的右分枝已遍历 沿左分枝向下 {if(!s[top]->Lc && !s[top]->Rc) // 只有到叶子结点时，才查看路径长度 l 栈，记住最高栈顶指针，退栈 到 path 中，因此在输出路径时还需输出 [ 算法描述 ] void AllPath(BTNode *b,ElemType path[],int pathlen) {int i; if (b!=NULL) {if (b->lchild==NULL && b->rchild==NULL) //*b {cout << " " << b->data << " for (i=pathlen-1;i>=0;i--) cout << endl; } else {path[pathlen]=b->data; pathlen++; AllPath(b->lchild,path,pathlen); AllPath(b->rchild,path,pathlen); pathlen--; } }// if (b!=NULL) }// 算法结束 // 将当前结点放入路径中 为叶子结点 到根结点路径 :" << b->data; //路径长度增 1 // 递归扫描左子树 // 递归扫描右子树 // 恢复环境 42 第6章图 1．选择题 （ 1）在一个图中，所有顶点的度数之和等于图的边数的（ A．1/2 答案： C （ 2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ A．1/2 答案： B 解释：有向图所有顶点入度之和等于所有顶点出度之和。 （ 3）具有 n 个顶点的有向图最多有（ A ． n 答案： B 解释：有向图的边有方向之分， B ． n(n-1) ）倍。 B．1 C．2 D．4 ）倍。 B．1 C．2 D．4 ）条边。 C． n(n+1) D． n2 即为从 n 个顶点中选取 2 个顶点有序排列， 结果为 n(n-1) 。 （ （ 4） n 个顶点的连通图用邻接距阵表示时，该距阵至少有 A ． n 答案： B B ． 2(n-1) ）个非零元素。 D． n2 ）个顶点。 D．10 C． n/2 （ 5） G 是一个非连通无向图，共有 A ． 7 答案： C 28 条边，则该图至少有（ C． 9 B ． 8 解释： 8 个顶点的无向图最多有 8*7/2=28 条边，再添加一个点即构成非连通无向图，故 至少有 9 个顶点。 （ 6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点， 则该图一定是（ ）图。 B ．连通 C．强连通 D ．有向 A ．非连通 答案： B 解释：即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。 （ 7）下面（ ）算法适合构造一个稠密图 B ． Kruskal 算法 G 的最小生成树。 C． Floyd 算法 G 的最小生成树， D ． Dijkstra 算法 Kruskal 算法适合构造一个稀疏 A ． Prim 算法 答案： A 解释： Prim 算法适合构造一个稠密图 图 G 的最小生成树。 （ 8）用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。 A．栈 答案： B B. 队列 C. 树 D．图 解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。 43 （ 9）用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。 A．栈 答案： A B. 队列 C. 树 D．图 解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。 （ 10 ）深度优先遍历类似于二叉树的（ A ．先序遍历 答案： A （ 11）广度优先遍历类似于二叉树的（ ）。 ）。 B ．中序遍历 C．后序遍历 D．层次遍历 A ．先序遍历 答案： D B ．中序遍历 C．后序遍历 DFS 生成树的树高（ C ．小或相等 D ．层次遍历 （ 12 ）图的 BFS 生成树的树高比 ）。 A ．小 答案： C B ．相等 D ．大或相等 解释：对于一些特殊的图，比如只有一个顶点的图，其 BFS 生成树的树高和 DFS 树的算法思想， DFS 生 成树的树高相等。一般的图，根据图的 BFS 生成树和 BFS 生成树的树 高比 DFS 生成树的树高小。 （ 13 ）已知图的邻接矩阵如图 （ 6.30 所示，则从顶点 v0 出发按深度优先遍历的结果是 ）。 图 6.30 邻接矩阵 （ 14 ）已知图的邻接表如图 6.31 所示，则从顶点 ）。 v0 出发按广度优先遍历的结果是 （ ）， 按深度优先遍历的结果是（ 图 6.31 邻接表 A．0132 答案： D、 D B．0231 C．0321 D．0123 44 （ 15 ）下面（ ）方法可以判断出一个有向图是否有环。 A ．深度优先遍历 答案： B B ．拓扑排序 C ．求最短路径 D ．求关键路径 2．应用题 （ 1）已知图 6.32 所示的有向图，请给出： ① 每个顶点的入度和出度； ② 邻接矩阵； ③ 邻接表； ④ 逆邻接表。 图 6.32 有向图 图 6.33 无向网 答案： （ 2）已知如图 6.33 所示的无向网，请给出： ① 邻接矩阵； ② 邻接表； ③ 最小生成树 答案： 45 ① ③ 4 4 3 5 5 9 3 5 5 5 9 5 7 7 6 5 5 4 5 5 4 6 3 3 2 2 6 6 ② a → b 4 → b → a 4 → c c 3 5 → d c → a 3 → b 5 → d d → b 5 → c 5 → e e f 5 → e 9 5 → h 7 → f 3 2 6 5 6 → g 5 → h 4 → → → b d d g 9 → 6 → 5 → d e f 7 → 3 → 2 → f g h （ 3）已知图的邻接矩阵如图 。 6.34 所示。试分别画出自顶点 1 出发进行遍历所得的深度 优先生成树和广度优先生成树 迪 杰 斯特 拉 算 法 求 出 从 顶 点 a 到其 他 （ 4）有向网如图6.35 所示，试用 各顶点间的最短路径，完成表 图 6.28 6.9 。 邻接矩阵 46 图 6.34 邻接矩阵 图 6.35 有向网 表 6.9 D 终点 i=1 i=2 i=3 i=4 i=5 i=6 15 (a,b) 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) 10 (a,c,e) 11 (a,c,f,d) 10 (a,c,e) 11 (a,c,f,d) 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- 网： ① 求这个工程最早可能在什么时 间结束； ② 求每个活动的最早开始时间和最迟开始时间； ③ 确定哪些活动是关键活动 47
发布者：admin，转转请注明出处：http://www.yc00.com/web/1704379145a1347042.html
评论列表（0条）