《数据结构课后题答案.docx》由会员分享，可在线阅读，更多相关《数据结构课后题答案.docx（24页珍藏版）》请在三一办公上搜索。
1、数据结构（C语言版）（第2版）课后习题答案李冬梅第1章 第2章 第3章 第4章 第5章 第6章 第7章 第8章错误!未定义书签。 错误!未定义书签。 错误!未定义书签。 错误!未定义书签。 错误!未定义书签。 错误!未定义书签。 错误!未定义书签。 错误!未定义书签。绪论线性表栈和队列串、数组和广义表树和二叉树图查找排序第1章绪论1. 简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结 构、抽象数据类型。答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的 总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、
2、图像、声音、动画等通过特殊编码定义后的数据。数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些 情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个 学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信 息表中的学号、姓名、性别等都是数据项。数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是 集合N=0，1，2，字母字符数据对象是集合C=A， B，Z，a，b， z，学生基本信息表也可是一个数据对象。数据结构：是相互之间存在一种或多种特定
3、关系的数据元素的集合。换句话说，数据结 构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此， 数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。存储结构：数据对象在计算机中的存储表示，也称为物理结构。抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一 组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操 作的集合。2. 试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。答案：例如有一张学生基本信息表，包括学生的学号、姓名、
4、性别、籍贯、专业等。每个学生 基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性 序列。对于整个表来说，只有一个开始结点（它的前面无记录）和一个终端结点（它的后面无记 录），其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元（如用数组表 示）来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录， 然后用指针进行链接，则称为链式存储结构。即相同的逻辑结构，可以对应不同的存储结构。3. 简述逻辑结构的四种基本关系并画出它
5、们的关系图。答案：（1）集合结构数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是 否为班级成员，只需将班级看做一个集合结构。（2）线性结构数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺 序进行排列，将组成一个线性结构。（3）树结构数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每 位组长管理多名组员，从而构成树形结构。（4）图结构或网状结构数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可 以是朋友，从而构成图形结构或网状结构。其中树结构和图结构都属于非线性结构。四类基本逻辑结构关系图
6、4. 存储结构由哪两种基本的存储方法实现答案：（1）顺序存储结构顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常 借助程序设计语言的数组类型来描述。（2）链式存储结构顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无 需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于 存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。5. 选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。A. 动态结构和静态结构B .紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构答案：
7、C（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。A. 存储结构B .存储实现C.逻辑结构D 运算实现答案：C（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。A. 数据具有同一特点B. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C. 每个数据元素都一样。.数据元素所包含的数据项的个数要相等答案：B(4) 以下说法正确的是()。A-数据元素是数据的最小单位B-数据项是数据的基本单位饥数据结构是带有结构的各数据项的集合D. 一些表面上很不相同的数据可以有相同的逻辑结构答案：D解释：数据元素是数据的基本单位，数据项是数据的最小单位，
8、数据结构是带有结构 的各数据元素的集合。(5) 算法的时间复杂度取决于()。A. 问题的规模B.待处理数据的初态C.计算机的配置D. A和B答案：D解释：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些 排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏 以及平均时间复杂度的评价。(6) 以下数据结构中，()是非线性数据结构A.树 B .字符串 C .队列D .栈答案：A6. 试分析下面各程序段的时间复杂度。(1) x=90; y=100;while(y0)if(x100)x=x-10;y;else x+;答案：O(1)解释：程序的执行次数为常
9、数阶。(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;D. s-next=p-next;
10、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-prio
11、r=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;答案：C2.算法设计题(1) 将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中不允许有重复的数据。题目分析合并后的新表使用头指针 Lc指向，pa和pb分别是链表La和Lb的工作指
12、针，初始化为 相应链表的第一个结点，从第一个结点开始进行比较，当两个链表 La和Lb均为到达表尾结 点时，依次摘取其中较小者重新链接在Lc表的最后。如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后表中无重复的元素。当一个表到达表尾结 点，为空时，将非空表的剩余元素直接链接在 Lc表的最后。算法描述void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)(3C想摘除栈顶结点，并将删除结点的值保存到x中，则应执行操作()。A. x=top-data;top=top-link ；B. top=top-link;x=t
13、op-link ；C. x=top;top=top-link ；D . x=top-link ；答案：A解释：x=top-data将结点的值保存到x中，top=top-link栈顶指针指向栈顶下一结 点，即摘除栈顶结点。(5) 设有一个递归算法如下int fact(int n) (3Cn存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是()。A. top+; Vtop=x;B. Vtop=x; top+;C. top; Vtop=x;D. Vtop=x; top;答案：C解释：初始栈顶指针top为n+1，说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间V1.n中，所以进栈时
14、top指针先下移变为n，之后将元素x存储在Vn。(10 )设计一个判别表达式中左，右括号是否配对出现的算法，采用()数据结构最佳。A.线性表的顺序存储结构B 队列C.线性表的链式存储结构D.栈答案：D解释：利用栈的后进先出原则。(11 )用链接方式存储的队列，在进行删除运算时()。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改答案：D解释：一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指 针也丢失了，因此需对队尾指针重新赋值。(12 )循环队列存储在数组A0.m 中，则入队时的操作为()。A. rear=rear+1B. rear=(rea
15、r+1)%(m-1)C. rear=(rear+1)%mD. rear=(rear+1)%(m+1)答案：D解释：数组A0.m中共含有m+1个元素，故在求模运算时应除以m+1。（13 ）最大容量为n的循环队列，队尾指针是rear,队头是front，则队空的条件是（）。A. （rear+1）%n=frontB. rear=frontC. rear+1=frontD. （rear-l）%n=front答案：B解释：最大容量为n的循环队列，队满条件是（rear+1）%n=front ,队空条件是 rear=front 。（14 ）栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在端
16、点处插入和删除元素D.没有共同点答案：C解释：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头 删除元素。（15） 一个递归算法必须包括（）。A.递归部分B. 终止条件和递归部分C.迭代部分D. 终止条件和迭代部分答案：B2. 算法设计题（1）将编号为0和1的两个栈存放于一个数组空间 Vm中，栈底分别处于数组的两端。 当第0号栈的栈顶指针top0等于-1时该栈为空，当第1号栈的栈顶指针top1等于m时 该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进栈和出栈 等算法的函数。双栈数据结构的定义如下：Typedef struct（int top2,bot
17、2;09090090 0 9 0 IOIIOIOOB. IOOIOIIO C. IIIOIOIO D. IIIOOIOO 通过对的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false （假定被判定的操作序列已存入一维数组中）。答案： A和D是合法序列，B和C是非法序列。 设被判定的操作序列已存入一维数组A中。int Judge（char A）0 0M-1实现循环队列，其中M是队列长度。设队头指针 front和队尾指针 rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义 front=rear时为队 空，（rear+1）%m=front
18、为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标 大的方向发展。算法描述#define M队列可能达到的最大长度typedef structelemtp dataM;int front,rear;cycqueue;elemtp delqueue ( cycqueue Q)012121111212C010102101C100,1.100，设每个数据元素占 2个存储单元，基地址为10，则LOC5,5=()。A. 808B . 818C . 1010D . 1020答案：B解释：以行序为主，则 LOC5,5 = (5-1) *100+ (5-1) *2+10=818。(7) 设有数组Ai,
19、j，数组的每个元素长度为3字节，i的值为1到8，j的值为1到 10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素 A5,8的存储首地址 为( )。A. BA+141B . BA+180C . BA+222D . BA+225答案：B解释：以列序为主，则 LOC5,8 = (8-1) *8+ (5-1) *3+BA=BA+180。(8) 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a”为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为()。11A. 13B. 32C . 33D . 40答案：C(9) 若对n阶对称矩阵A以行序为主序方式将其下三角
20、形的元素 (包括主对角线上所有 元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定a”. (ij )的位置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按行先存储，元素A8,5的起始地址与当A按列先存储时的元素()的起始地址相同。设每个字符占一个字节。A. A8,5B . A3,10C. A5,8D . A0,9答案：B解释：设数组从内存首地址 M开始顺序存
21、放，若数组按行先存储，元素 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 C . i*(j-1)D . j*m+i-1答案：A解释：特殊值法。取i=j=1，易知A1,1的的下标为1,四个选项中仅有A选项 能确定的值为1，故选A。(12) 数组
22、 A0.4,-1.-3,5.7A. 55B . 45答案：B解释：共有5*3*3=45个元素。(13) 广义表 A=(a,b,(c,d),(e,(f,g)()。A. (g)B . (d)答案：D解释：Tail(A) = (b,(c,d),(e,(f,g)Head(Tail(Tail(A)=(c,d)；Head(Tail(Head(Tail(Tail(A)=d 。中含有元素的个数()。C . 36D . 16,则 Head(Tail(Head(Tail(Tail(A) 的值为C . cD . d;Tail(Tail(A) = (c,d),(e,(f,g)；Tail(Head(Tail(Tail(
23、A)=(d)；)，表尾是()。C . (a,b,c,d) D. (b,c,d)也可以是一个子表，由其余元素构成的表，表)。D . 2 和 3(14 )广义表(a,b,c,d)的表头是(A. aB .()答案：C、B解释：表头为非空广义表的第一个元素，可以是一个单原子， (a,b,c,d)的表头为一个子表(a,b,c,d)；表尾为除去表头之外， 为一定是个广义表，(a,b,c,d)的表尾为空表()。(15 )设广义表L=(a,b,c)，则L的长度和深度分别为(A.1 和 1B .1 和 3C .1 和 2答案：C解释：广义表的深度是指广义表中展开后所含括号的层数，广义表的长度是指广义表 中所含元
24、素的个数。根据定义易知 L的长度为1，深度为2。2.应用题(1)已知模式串t=abcaabbabcab 写出用KMP法求得的每个字符对应的 next和nextval 函数值。答案：模式串t的next和nextval值如下:j123456789101112t串abcaabbabcabnextj011122312345nextvalj011021301105(2) 设目标为 t= abcaabbabcabaacbacba ”,模式为 p= “ abcabaa ” 计算模式p的naxtval函数值； 不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。答案： p的nextval函数值为0
25、110132。(p的next函数值为0111232 )。 利用KMP (改进的nextval)算法，每趟匹配过程如下： 第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacba abc(i=7,j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配：abcaabbabcabaac bacba(成功)abcabaa(i=15,j=8)(3) 数组A中，每个元素Ai,j的长度均为32个二进位，行下标从-1到9,列下标从1 到11,从首地址S开始连续存放主存储器中，主存储器字长为16位。求
26、： 存放该数组所需多少单元 存放数组第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)写一个算法统计在输入
27、字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为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; 00 0
28、m, 1.n含有 m*n 个整数。 写一个算法判断a中所有元素是否互不相同输出相关信息（yes/no）； 试分析算法的时间复杂度。题目分析判断二维数组中元素是否互不相同，只有逐个比较，找到一对相等的元素，就 可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次在当前行，每个元 素要同本行后面的元素比较一次（下面第一个循环控制变量P的for循环），然后同第i+1行及以后各行元素比较一次，这就是循环控制变量k和p的二层for循环。算法描述int JudgEqual（ing amn,int m,n）算法讨论对数组中元素各比较一次，比较次数为 n。最佳情况（已排好，正数在前，负 数在后）不
29、发生交换，最差情况（负数均在正数前面）发生n/2次交换。用类c编写，数组界偶 是0.n-1。空间复杂度为O（1）.第5章树和二叉树1. 选择题（1）把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。A.唯一的B.有多种C. 有多种，但根结点都没有左孩子 D.有多种，但根结点都没有右孩子答案：A解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的 形态是唯一的。（2）由3个结点可以构造出多少种不同的二叉树（）A. 2B . 3C . 4D. 5答案：D解释：五种情况如下：AAAAABBBBB C CCCC（3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。A.
30、 250B .500C . 254 D . 501答案：D解释：设度为。结点（叶子结点）个数为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. 11B . 10C . 11 至 1025 之间 D .10 至 1024 之间答案：C 解释：若每层仅有一个结点，则树高h为1025 ；且其最小树高 为 log21025+ 1=11，即 h 在 11 至 1025 之
31、间。（5）深度为h的满m叉树的第k层有（）个结点。（1=k=h）A. mk-1B . mk-1C . mh-1D . mh-1答案：A解释：深度为h的满m叉树共有mh-1个结点，第k层有mk-1个结点。（6）利用二叉链表存储树，则根结点的右指针是（）。A.指向最左孩子B .指向最右孩子C .空 D .非空答案：C解释：利用二叉链表存储树时，右指针指向兄弟结点，因为根节点没有兄弟结点，故根 节点的右指针指向空。（7）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）遍历实现编号。A.先序B.中序C.后序
32、 D.从根开始按层次遍历答案：C解释：根据题意可知按照先左孩子、再右孩子、最后双亲结点的顺序遍历二叉树，即 后序遍历二叉树。（8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用 （）遍历方法最合适。A.前序B .中序C .后序 D .按层次答案：C解释：后续遍历和层次遍历均可实现左右子树的交换，不过层次遍历的实现消耗比后续大，后序遍历方法最合适。（9）在下列存储形式中，（）不是树的存储形式A-双亲表示法B 孩子链表表示法C 孩子兄弟表示法D .顺序存储表示法答案：D解释：树的存储结构有三种：双亲表示法、孩子表示法、孩子兄弟表示法，其中孩子 兄弟表示法是常用的表示法，任
33、意一棵树都能通过孩子兄弟表示法转换为二叉树进行存储。（10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满 足（）。A.所有的结点均无左孩子B .所有的结点均无右孩子C.只有一个叶子结点D .是任意一棵二叉树答案：C解释：因为先序遍历结果是“中左右”，后序遍历结果是“左右中”，当没有左子树时， 就是“中右”和“右中”；当没有右子树时，就是“中左”和“左中”。则所有的结点均无左 孩子或所有的结点均无右孩子均可，所以A、B不能选，又所有的结点均无左孩子与所有的结点均无右孩子时，均只有一个叶子结点，故选C。（11 ）设哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。
34、A. 99B. 100C. 101D. 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.为了能方便的找到双亲
35、D .使二叉树的遍历结果唯一答案：A（14） 设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中 右指针域为空的结点有（）个。A. n 1B. nC. n + 1D. n + 2答案：C（15）n（n32）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（）。A. 该树一定是一棵完全二叉树B. 树中一定没有度为1的结点C. 树中两个权值最小的结点一定是兄弟结点D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值答案：A解释：哈夫曼树的构造过程是每次都选取权值最小的树作为左右子树构造一棵新的二叉树，所以树中一定没有度为 1的结点、两个权值最小的结点一定是兄弟
36、结点、任一非叶结点 的权值一定不小于下一层任一结点的权值。2. 应用题(1) 试找出满足下列条件的二叉树 先序序列与后序序列相同中序序列与后序序列相同 先序序列与中序序列相同中序序列与层次遍历序列相同答案：先序遍历二叉树的顺序是“根一左子树一右子树”，中序遍历“左子树一根一右 子树”，后序遍历顺序是：“左子树一右子树一根，根据以上原则有 或为空树，或为只有根结点的二叉树 或为空树，或为任一结点至多只有左子树的二叉树. 或为空树，或为任一结点至多只有右子树的二叉树. 或为空树，或为任一结点至多只有右子树的二叉树(2) 设一棵二叉树的先序序列：A B D F C E G H ，中序序列：B F D
37、 A G E H C 画出这棵二叉树。 画出这棵二叉树的后序线索树。 将这棵二叉树转换成对应的树(或森林)。答案：，(3) 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为， 试为这8个字母设计赫夫曼编码。 试设计另一种由二进制表示的等长编码方案。 对于上述实例，比较两种方案的优缺点。答案：方案1;哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。w=7,19,2,6,32,3,21,10，按哈夫曼规则:【（2,3），6, （7,10）】，19, 21, 32（100）.（40）.（60）1921 3228）、517）.）.字母编号对应 编码出现频率1110020031111
38、04111051061111170181101字 母编号对应编码出现 频率10002001301040115100610171108111方案 1 的 WPL = 2+4+5+=+=方案 2 的 WPL = 3+=3结论：哈夫曼编码优于等长二进制编码11,试(4) 已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8,填写出其对应哈夫曼树HT的存储结构的初态和终态。答案：初态：weightparentlchildrchild13000212000370004400052000680007110008000900010000110001200013000终态：weightp
39、arentlchildrchild138002121200371000449005280068100071111008595199114810151236112013971227132101347011123. 算法设计题以二叉链表作为二叉树的存储结构，编写以下算法:（1）统计二叉树的叶结点个数。题目分析如果二叉树为空，返回0,如果二叉树不为空且左右子树为空，返回1,如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子 节点个数。算法描述int LeafNodeCount（BiTree T）if（T=NULL）return 0; c;1C1C8C 队列C. 树D .
40、图答案：B解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。（9）用邻接表表示图进行深度优先遍历时，通常借助（）来实现算法。A栈B.队列C. 树D .图答案：A解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。（10）深度优先遍历类似于二叉树的A.先序遍历B.中序遍历答案：A（11）广度优先遍历类似于二叉树的A.先序遍历B.中序遍历答案：D（12）图的BFS生成树的树高比DFS生成树的树高（A.小B .相等C .小或相等答案：C解释：对于一些特殊的图，比如只有一个顶点的图，其BFS）。C .后序遍历）。C .后序遍历）。D.层次遍历D .层次
41、遍历D .大或相等生成树的树高和DFS生成树的树高相等。一般的图，根据图的BFS生成树和DFS生成树的树高小。（13 ）已知图的邻接矩阵如图所示，则从顶点DFS树的算法思想，BFS生成树的树高比v。出发按深度优先遍历的结果是（）。图邻接矩阵（14）已知图的邻接表如图所示，则从顶点vo出发按广度优先遍历的结果是（），按深度优先遍历的结果是（）。图邻接表A. 0 1 3 2B. 0 2 3 1 C. 0 3 2 1D. 0 1 2 3答案：D、D(15)下面()方法可以判断出一个有向图是否有环。A.深度优先遍历B .拓扑排序C .求最短路径D .求关键路径答案：B2.应用题(1)已知图所示的有向图，请给出： 每个顶点的入度和出度； 邻接矩阵； 邻接表； 逆邻接表。图有向图图无向网答案：(2)已知如图所示的无向网，请给出: 邻接矩阵； 邻接表； 最小生成树答案：84388888485598883585888585587654898783888886382888858286_88548868一d5d5e7f3g2h6一f一g5一h4（3）已知图的邻接矩阵如图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
