数据结构C语言版第2版课后习题答案.pdf

数据结构（C语言版）（第2版）课后习题答案 李冬梅 目 录 第1章 绪论.错误!未定义书签。第2章 线性表.错误!未定义书签。第3章 栈和队列.错误!未定义书签。第4章 串、数组和广义表.错误!未定义书签。第5章 树和二叉树.错误!未定义书签。第6章 图.错误!未定义书签。第7章 查找.错误!未定义书签。第8章 排序.错误!未定义书签。第 1 章 绪论 1简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合 N=0，1，2，字母字符数据对象是集合 C=A，B，Z，a，b，z，学生基本信息表也可是一个数据对象。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。存储结构：数据对象在计算机中的存储表示，也称为物理结构。抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。2试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。即相同的逻辑结构，可以对应不同的存储结构。3简述逻辑结构的四种基本关系并画出它们的关系图。答案：（1）集合结构 数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。（2）线性结构 数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。（3）树结构 数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每位组长管理多名组员，从而构成树形结构。（4）图结构或网状结构 数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图形结构或网状结构。其中树结构和图结构都属于非线性结构。4存储结构由哪两种基本的存储方法实现 答案：（1）顺序存储结构 顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。（2）链式存储结构 顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。四类基本逻辑结构关系图 5选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构 答案：C（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。A存储结构 B存储实现 C逻辑结构 D运算实现 答案：C（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。A数据具有同一特点 B不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C每个数据元素都一样 D数据元素所包含的数据项的个数要相等 答案：B（4）以下说法正确的是（）。A数据元素是数据的最小单位 B数据项是数据的基本单位 C数据结构是带有结构的各数据项的集合 D一些表面上很不相同的数据可以有相同的逻辑结构 答案：D 解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。（5）算法的时间复杂度取决于（）。A问题的规模 B待处理数据的初态 C计算机的配置 DA 和 B 答案：D 解释：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。（6）以下数据结构中，（）是非线性数据结构 A树 B字符串 C队列 D栈 答案：A 6试分析下面各程序段的时间复杂度。（1）x=90;y=100;while(y0)if(x100)x=x-10;y-;else x+;答案：O(1)解释：程序的执行次数为常数阶。（2）for(i=0;in;i+)for(j=0;jm;j+)aij=0;答案：O(m*n)解释：语句 aij=0;的执行次数为 m*n。（3）s=0;for i=0;in;i+)for(j=0;jn;j+)s+=Bij;sum=s;答案：O(n2)解释：语句 s+=Bij;的执行次数为 n2。（4）i=1;while(i=n)i=i*3;答案：O(log3n)解释：语句 i=i*3;的执行次数为 log3n。（5）x=0;for(i=1;in;i+)for(j=1;jnext=p-next;p-next=s-next;Ds-next=p-next;p-next=s;答案：D (14)在双向链表存储结构中，删除 p 所指的结点时须修改指针（）。Ap-next-prior=p-prior;p-prior-next=p-next;Bp-next=p-next-next;p-next-prior=p;Cp-prior-next=p;p-prior=p-prior-prior;Dp-prior=p-next-next;p-next=p-prior-prior;答案：A(15)在双向循环链表中，在 p 指针所指的结点后插入 q 所指向的新结点，其修改指针的操作是（）。Ap-next=q;q-prior=p;p-next-prior=q;q-next=q;Bp-next=q;p-next-prior=q;q-prior=p;q-next=p-next;Cq-prior=p;q-next=p-next;p-next-prior=q;p-next=q;Dq-prior=p;q-next=p-next;p-next=q;p-next-prior=q;答案：C 2算法设计题（1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中不允许有重复的数据。题目分析 合并后的新表使用头指针 Lc 指向，pa 和 pb 分别是链表 La 和 Lb 的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表 La 和 Lb 均为到达表尾结点时，依次摘取其中较小者重新链接在 Lc 表的最后。如果两个表中的元素相等，只摘取 La表中的元素，删除 Lb 表中的元素，这样确保合并后表中无重复的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在 Lc 表的最后。算法描述 void MergeList(LinkList&La,LinkList&Lb,LinkList&Lc)想摘除栈顶结点，并将删除结点的值保存到 x 中,则应执行操作（）。Ax=top-data;top=top-link；Btop=top-link;x=top-link；Cx=top;top=top-link；Dx=top-link；答案：A 解释：x=top-data 将结点的值保存到 x 中，top=top-link 栈顶指针指向栈顶下一结点，即摘除栈顶结点。（5）设有一个递归算法如下 int fact(int n)n存储，初始栈顶指针 top 设为 n+1，则元素 x进栈的正确操作是()。Atop+;Vtop=x;BVtop=x;top+;Ctop-;Vtop=x;DVtop=x;top-;答案：C 解释：初始栈顶指针 top 为 n+1，说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间 V1.n中，所以进栈时 top 指针先下移变为 n，之后将元素 x 存储在 Vn。（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A线性表的顺序存储结构 B队列 C.线性表的链式存储结构 D.栈 答案：D 解释：利用栈的后进先出原则。（11）用链接方式存储的队列，在进行删除运算时（）。A.仅修改头指针 B.仅修改尾指针 C.头、尾指针都要修改 D.头、尾指针可能都要修改 答案：D 解释：一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值。（12）循环队列存储在数组 A0.m中，则入队时的操作为（）。A.rear=rear+1 B.rear=(rear+1)%(m-1)C.rear=(rear+1)%m D.rear=(rear+1)%(m+1)答案：D 解释：数组 A0.m中共含有 m+1 个元素，故在求模运算时应除以 m+1。（13）最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是（）。A.(rear+1)%n=front B.rear=front Crear+1=front D.(rear-l)%n=front 答案：B 解释：最大容量为 n 的循环队列，队满条件是(rear+1)%n=front，队空条件是rear=front。（14）栈和队列的共同点是（）。A.都是先进先出 B.都是先进后出 C.只允许在端点处插入和删除元素 D.没有共同点 答案：C 解释：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头删除元素。（15）一个递归算法必须包括（）。A.递归部分 B.终止条件和递归部分 C.迭代部分 D.终止条件和迭代部分 答案：B 2算法设计题（1）将编号为 0 和 1 的两个栈存放于一个数组空间 Vm中，栈底分别处于数组的两端。当第 0 号栈的栈顶指针 top0等于-1 时该栈为空，当第 1 号栈的栈顶指针 top1等于 m 时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下：Typedef struct int top2,bot2;IOIIOIOO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO 通过对的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回 true，否则返回 false（假定被判定的操作序列已存入一维数组中）。答案：A 和 D 是合法序列，B 和 C 是非法序列。设被判定的操作序列已存入一维数组 A 中。int Judge(char A)M-1实现循环队列，其中 M 是队列长度。设队头指针 front 和队尾指针 rear，约定 front 指向队头元素的前一位置，rear 指向队尾元素。定义 front=rear 时为队空，(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。算法描述#define M 队列可能达到的最大长度 typedef struct elemtp dataM;int front,rear;cycqueue;elemtp delqueue(cycqueue Q)100,1.100，设 每个数据元素占 2 个存储单元，基地址为 10，则 LOC5,5=（）。A808 B818 C1010 D1020 答案：B 解释：以行序为主，则 LOC5,5=（5-1）*100+（5-1）*2+10=818。（7）设有数组 Ai,j，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1 到10，数组从内存首地址 BA 开始顺序存放，当用以列为主存放时，元素 A5,8的存储首地址为（）。ABA+141 BBA+180 CBA+222 DBA+225 答案：B 解释：以列序为主，则 LOC5,8=（8-1）*8+（5-1）*3+BA=BA+180。（8）设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a85的地址为（）。A13 B32 C33 D40 答案：C （9）若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组 B1.(n(n+1)/2中，则在 B 中确定 aij（ij）的位置 k 的关系为（）。Ai*(i-1)/2+j Bj*(j-1)/2+i Ci*(i+1)/2+j Dj*(j+1)/2+i 答案：B（10）二维数组 A 的每个元素是由 10 个字符组成的串，其行下标 i=0,1,8,列下标j=1,2,10。若 A 按行先存储，元素 A8,5的起始地址与当 A 按列先存储时的元素（）的起始地址相同。设每个字符占一个字节。AA8,5 BA3,10 C.A5,8 DA0,9 答案：B 解释：设数组从内存首地址 M 开始顺序存放，若数组按行先存储，元素 A8,5的起始地址为：M+（8-0）*10+（5-1）*1=M+84；若数组按列先存储，易计算出元素 A3,10的起始地址为：M+（10-1）*9+（3-0）*1=M+84。故选 B。（11）设二维数组 A1.m，1.n（即 m 行 n 列）按行存储在数组 B1.m*n中，则二维数组元素 Ai,j在一维数组 B 中的下标为（）。A(i-1)*n+j B(i-1)*n+j-1 Ci*(j-1)Dj*m+i-1 答案：A 解释：特殊值法。取 i=j=1，易知 A1,1的的下标为 1，四个选项中仅有 A 选项能确定的值为 1，故选 A。（12）数组 A0.4,-1.-3,5.7中含有元素的个数（）。A55 B45 C36 D16 答案：B 解释：共有 5*3*3=45 个元素。（13）广义表 A=(a,b,(c,d),(e,(f,g)，则 Head(Tail(Head(Tail(Tail(A)的值为（）。A(g)B(d)Cc Dd 答案：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)的表头是（），表尾是（）。Aa 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 的长度和深度分别为（）。A1 和 1 B1 和 3 C1 和 2 D2 和 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 nextj 0 1 1 1 2 2 3 1 2 3 4 5 nextvalj 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 中，每个元素 Ai,j的长度均为 32 个二进位,行下标从-1 到 9，列下标从 1到 11，从首地址 S 开始连续存放主存储器中，主存储器字长为 16 位。求：存放该数组所需多少单元 存放数组第 4 列所有元素至少需多少单元 数组按行存放时，元素 A7,4的起始地址是多少 数组按列存放时，元素 A4,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（）是字符串输入结束标志 InvertStore(A);Ai+=ch;m,1.n 含有 m*n 个整数。写一个算法判断 a 中所有元素是否互不相同输出相关信息(yes/no)；试分析算法的时间复杂度。题目分析判断二维数组中元素是否互不相同，只有逐个比较,找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次在当前行，每个元素要同本行后面的元素比较一次（下面第一个循环控制变量 p 的 for 循环），然后同第 i+1行及以后各行元素比较一次，这就是循环控制变量 k 和 p 的二层 for 循环。算法描述 int JudgEqual(ing amn,int m,n)算法讨论对数组中元素各比较一次，比较次数为 n。最佳情况(已排好,正数在前,负数在后)不发生交换，最差情况(负数均在正数前面)发生 n/2 次交换。用类 c 编写，数组界偶是 0.n-1。空间复杂度为 O(1).第 5 章 树和二叉树 1选择题（1）把一棵树转换为二叉树后，这棵二叉树的形态是（）。A唯一的 有多种 C有多种，但根结点都没有左孩子 有多种，但根结点都没有右孩子 答案：A 解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。（2）由 3 个结点可以构造出多少种不同的二叉树（）A2 B3 C4 D5 答案：D 解释：五种情况如下：ACB ACB ACB ACB ACB（3）一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（）。A250 B 500 C254 D501 答案：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 为（）。A11 B10 C11 至 1025 之间 D10 至 1024 之间 答案：C 解 释：若 每 层 仅 有 一 个 结 点，则 树 高h为1025；且 其 最 小 树 高为 log21025+1=11，即 h 在 11 至 1025 之间。（5）深度为 h 的满 m 叉树的第 k 层有（）个结点。(1=k=h)Amk-1 Bmk-1 Cmh-1 Dmh-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 个结点，则该哈夫曼树中有（）个叶子结点。A99 B100 C101 D102 答案：B 解释：在哈夫曼树中没有度为 1 的结点，只有度为 0（叶子结点）和度为 2 的结点。设叶子结点的个数为 n0，度为 2 的结点的个数为 n2，由二叉树的性质 n0=n2+1，则总结点数 n=n0+n2=2*n0-1，得到 n0=100。（12）若 X 是二叉中序线索树中一个有左孩子的结点，且 X 不为根，则 X 的前驱为（）。AX 的双亲 BX 的右子树中最左的结点 CX 的左子树中最右结点 DX 的左子树中最右叶结点 答案：C（13）引入二叉线索树的目的是（）。A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除 C为了能方便的找到双亲 D使二叉树的遍历结果唯一 答案：A（14）设 F 是一个森林，B 是由 F 变换得的二叉树。若 F 中有 n 个非终端结点，则 B 中右指针域为空的结点有（）个。An 1 Bn Cn+1 Dn+2 答案：C（15）n（n2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（）。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 个字母组成，字母在电文中出现的频率分别为，。试为这 8 个字母设计赫夫曼编码。A B F D C E H G AEDCBHGFAEDCBHGFnull 试设计另一种由二进制表示的等长编码方案。对于上述实例，比较两种方案的优缺点。答案：方案 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 000 2 001 3 010 字母编号 对 应编码 出现频率 1 1100 2 00 3 11110 0 1 0 1 0 1 19 21 32 0 1 0 1 0 1 方案 1 的 WPL2+4+5+=+=方案 2 的 WPL3+=3 结论：哈夫曼编码优于等长二进制编码 （4）已知下列字符 A、B、C、D、E、F、G 的权值分别为 3、12、7、4、2、8，11，试填写出其对应哈夫曼树 HT 的存储结构的初态和终态。答案：初态:终态：3算法设计题 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 以二叉链表作为二叉树的存储结构，编写以下算法：（1）统计二叉树的叶结点个数。题目分析如果二叉树为空，返回 0，如果二叉树不为空且左右子树为空，返回 1，如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数。算法描述 int LeafNodeCount(BiTree T)if(T=NULL)return 0;c;队列 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）已知图的邻接矩阵如图所示，则从顶点v0出发按深度优先遍历的结果是（）。图 邻接矩阵（14）已知图的邻接表如图所示，则从顶点v0出发按广度优先遍历的结果是（），按深度优先遍历的结果是（）。图 邻接表 A0 1 3 2 B0 2 3 1 C0 3 2 1 D0 1 2 3 答案：D、D（15）下面（）方法可以判断出一个有向图是否有环。A深度优先遍历 B拓扑排序 C求最短路径 D求关键路径 答案：B 2应用题 （1）已知图所示的有向图，请给出：每个顶点的入度和出度；邻接矩阵；邻接表；逆邻接表。图 有向图 图 无向网 答案：（2）已知如图所示的无向网，请给出：邻接矩阵；邻接表；最小生成树 答案：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 6456252363794567555553955434 （3）已知图的邻接矩阵如图所示。试分别画出自顶点 1 出发进行遍历所得的深度优先生成树和广度优先生成树。（4）有向网如图所示，试用迪杰斯特拉算法求出从顶点 a 到其他各顶点间的最短路径，完成表。图 邻接矩阵 图 有向网 表 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 12 11 11 图 邻接矩阵 (a,d)(a,d)(a,c,f,d)(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）试对图所示的 AOE-网：求这个工程最早可能在什么时间结束；求每个活动的最早开始时间和最迟开始时间；确定哪些活动是关键活动 答案：按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间 e 和最迟允许开始时间l，根据l-e=0 来确定关键活动，从而确定关键路径。1 2 3 4 5 6 Ve 0 19 15 29 38 43 图 AOE-网 Vl 0 19 15 37 38 43 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。关键路径为 3算法设计题（1）分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作：增加一个新顶点v，InsertVex(G,v)；删除顶点 v 及其相关的边，DeleteVex(G,v);增加一条边，InsertArc(G,v,w);删除一条边，DeleteArc(G,v,w)。算法描述 假设图 G 为有向无权图，以邻接矩阵作为存储结构四个算法分别如下：增加一个新顶点v Status Insert_Vex(MGraph&G,char v)dj=0;return OK;dj)j.adj=1;+;return OK;dj)j.adj=0;return OK;余算法类似。Status Insert_Arc(ALGraph&G,char v,char w)irstarc;p;p=p-nextarc，level-)level+;k=p-adjvex;if(!visitedk&exist_path(k,j)return 1;irstarc;p;p=p-nextarc)l=p-adjvex;if(!visitedl)if(exist_path_len(G,l,j,k-1)return 1;ey=k）return （mid）；else if（rmid.keyk）return （BinSrch（r,k，mid+1，high）;503010060808 2035 40 图 3 阶 B-树 else return （BinSrch（r,k，low，mid-1）;else return （0）；ey=3)k-;ey=1)ey=2)if(ik 为止。算法片段如下：int i=1,j=1,k=n;while(j=k)if(rj=1)n中。若查找成功，则输出该记录在 r 数组中的位置及其值，否则显示“not find”信息。请简要说明算法思想并编写算法。题目分析把待查记录看作枢轴，先由后向前依次比较，若小于枢轴，则从前向后，直到查找成功返回其位置或失败返回 0 为止。算法描述 int index(RecType R,int l,h,datatype key)int i=l,j=h;while(ij)while(ikey)j-;if(Rj.key=key)return j;while(i=j&Ri.keykey)i+;if(Ri.key=key)return i;2574031 3 1 61 11 51 11 1 cout“Not find”;return 0;eyai.key)cnt+;ount=0;eyaj.key)aj.count+;else ai.count+;