数据结构(殷人昆)练习题答案附在后边

《数据结构(殷人昆)练习题答案附在后边》由会员分享，可在线阅读，更多相关《数据结构(殷人昆)练习题答案附在后边（25页珍藏版）》请在装配图网上搜索。

1、第一章 绪论1-1什么是数据? 它与信息是什么关系?1-2什么是数据结构? 有关数据结构的讨论涉及哪三个方面?1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、 栈、队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？1-4什么是抽象数据类型？试用C+的类声明定义“复数”的抽象数据类型。要求(1) 在复数内部用浮点数定义它的实部和虚部。(2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。(3) 定义获取和修改复数的实部和虚部，以及+、-

2、、*、/等运算的成员函数。(4) 定义重载的流函数来输出一个复数。1-5 用归纳法证明：(1) (2) (3) 1-6 什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。1-7 设n为正整数, 分析下列各程序段中加下划线的语句的程序步数。 (1) for (int i = 1; i = n; i+) (2) x = 0; y = 0; for (int j = 1; j = n; j+) for (int i = 1; i = n; i+) cij = 0.0; for (int j = 1; j = i; j+) for (int k = 1; k = n; k+)

3、for (int k = 1; k = j; k+) cij = cij + aik * bkj; x = x + y; (3) int i = 1, j = 1; (4) int i =1; while (i=n & j=n) do i = i + 1; j = j + i; for (int j = 1; j = n; j+) i = i + j; while ( i arraySize或者对于某一个k (0 k n)，使得k!*2k maxInt时，应按出错处理。可有如下三种不同的出错处理方式：(1) 用cerr及exit (1)语句来终止执行并报告错误；(2) 用返回整数函数值0, 1

4、来实现算法，以区别是正常返回还是错误返回；(3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。1-9 (1) 在下面所给函数的适当地方插入计算count的语句：void d (ArrayElement x , int n ) int i = 1; do xi += 2; i +=2; while (i = n ); i = 1; while ( i = (n/2) ) xi += xi+1; i+; (2) 将由(1)所得到的程序化简。使得化简后的程序与化简前的程序具有相同的count值。(3) 程序执行结

5、束时的count值是多少？(4) 使用执行频度的方法计算这个程序的程序步数，画出程序步数统计表。 1-10 设有3个值大小不同的整数a、b和c，试求(1) 其中值最大的整数；(2) 其中值最小的整数；(3) 其中位于中间值的整数。第二章 数组2-1作为抽象数据类型数组的类声明。#include /在头文件“array.h”中#include const int DefaultSize = 30;template class Array /数组是数据类型相同的n（size）个元素的一个集合, 下标范围从0到n-1。对数组中元素/可按下标所指示位置直接访问。private: Type *eleme

6、nts;/数组 int ArraySize;/元素个数public: Array ( int Size = DefaultSize );/构造函数 Array ( const Array & x );/复制构造函数 Array ( ) delete elements; /析构函数 Array & operator = ( const Array & A );/数组整体赋值 (复制) Type& operator ( int i );/按下标访问数组元素 int Length ( ) const return ArraySize; /取数组长度 void ReSize ( int sz );/修

7、改数组长度顺序表的类定义#include /定义在头文件“seqlist.h”中#include template class SeqList private: Type *data;/顺序表的存放数组 int MaxSize;/顺序表的最大可容纳项数 int last;/顺序表当前已存表项的最后位置 int current;/顺序表的当前指针（最近处理的表项）public: SeqList ( int MaxSize );/构造函数 SeqList ( ) delete data; /析构函数 int Length ( ) const return last+1; /计算表长度 int Fi

8、nd ( Type& x ) const;/定位函数: 找x在表中位置，置为当前表项 int IsIn ( Type& x );/判断x是否在表中，不置为当前表项 Type *GetData ( ) return current = -1？NULL : datacurrent; /取当前表项的值 int Insert ( Type& x );/插入x在表中当前表项之后，置为当前表项 int Append ( Type& x );/追加x到表尾，置为当前表项 Type * Remove ( Type& x );/删除x，置下一表项为当前表项 Type * First ( ); /取表中第一个表项

9、的值，置为当前表项 Type * Next ( ) return current 0 ? &data-current : NULL; /取当前表项的前驱表项的值，置为当前表项 int IsEmpty ( ) return last = -1; /判断顺序表空否, 空则返回1; 否则返回0 int IsFull ( ) return last = MaxSize-1; /判断顺序表满否, 满则返回1; 否则返回02-1 设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，如此反复直到所有的人全部出局为止。下面要解

10、决的Josephus问题是：对于任意给定的n, s和m，求出这n个人的出局序列。请以n = 9, s = 1, m = 5为例，人工模拟Josephus的求解过程以求得问题的解。2-2 试编写一个求解Josephus问题的函数。用整数序列1, 2, 3, , n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。2-3 设有一个线性表 (e0, e1, , en-2

11、, en-1) 存放在一个一维数组AarraySize中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为 (en-1, en-2, , e1, e0)。2-4 假定数组AarraySize中有多个零元素, 试写出一个函数, 将A 中所有的非零元素依次移到数组A的前端Ai（0 i arraySize）。2-5 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素?2-6 若矩阵Amn中的某一元素Aij是第i行中的最小值，同时又是第j列中的

12、最大值，则称此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵，试编写一个函数，确定鞍点在数组中的位置（若鞍点存在时），并分析该函数的时间复杂度。2-7 设有一个二维数组Amn，假设A00存放位置在644(10)，A22存放位置在676(10)，每个元素占一个空间，问A33(10)存放在什么位置？脚注(10)表示用10进制表示。2-8 利用顺序表的操作，实现以下的函数。(1) 从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。 (2) 从顺序表中删除第i个元素并由函数返回被删元素的值。如果i不合理或顺序表为空则显示出错信息

13、并退出运行。(3) 向顺序表中第i个位置插入一个新的元素x。如果i不合理则显示出错信息并退出运行。(4) 从顺序表中删除具有给定值x的所有元素。(5) 从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。(6) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。(7) 将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。(8) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。2-9 设有一个nn的对称矩阵A，如图(a)所示。为了节约

14、存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，如图(b)和图(c)所示。并称之为对称矩阵A的压缩存储方式。试问：(1) 存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？(2) 若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存上三角部分的情形下(图(b)应存于一维数组的什么下标位置？给出计算公式。(3) 若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存下三角部分的情形下(图(c)应存于一维数组的什么下标位

15、置？给出计算公式。2-10 设A和B均为下三角矩阵，每一个都有n行。因此在下三角区域中各有n(n+1)/2个元素。另设有一个二维数组C，它有n行n+1列。试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式。2-11 在实际应用中经常遇到的稀疏矩阵是三对角矩阵，如右图所示。在该矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其它元素均为0。现在要将三对角矩阵A中三条对角线上的元素按行存

16、放在一维数组B中，且a11存放于B0。试给出计算A在三条对角线上的元素aij （1 i n, i-1 j i+1）在一维数组B中的存放位置的计算公式。2-12 设带状矩阵是nn阶的方阵，其中所有的非零元素都在由主对角线及主对角线上下各b条对角线构成的带状区域内，其它都为零元素。试问：(1) 该带状矩阵中有多少个非零元素？(2) 若用一个一维数组B按行顺序存放各行的非零元素，且设a11存放在B0中，请给出一个公式，计算任一非零元素aij在一维数组B中的存放位置。2-13 稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。稀疏矩阵有多少行，在行指针数组中就有多少个元素：第i个元素的数组下标i代表

17、矩阵的第i行，元素的内容即为稀疏矩阵第i行的第一个非零元素在二元组表中的存放位置。二元组表中每个二元组只记录非零元素的列号和元素值，且各二元组按行号递增的顺序排列。试对右图所示的稀疏矩阵，分别建立它的三元组表和带行指针数组的二元组表。2-14 字符串的替换操作replace (String &s, String &t, String &v)是指：若t是s的子串，则用串v替换串t在串s中的所有出现；若t不是s的子串，则串s不变。例如，若串s为“aabbabcbaabaaacbab”，串t为“bab”，串v为“abdc”，则执行replace操作后，串s中的结果为“aababdccbaabaaac

18、abdc”。试利用字符串的基本运算实现这个替换操作。2-15 编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。2-16 设串s为“aaab”，串t为“abcabaa”，串r为“abcaabbabcabaacbacba”，试分别计算它们的失效函数f (j)的值。2-17 设定整数数组Bm+1n+1的数据在行、列方向上都按从小到大的顺序排序，且整型变量x中的数据在B中存在。试设计一个算法，找出一对满足Bij = x的i, j值。要求比较次数不超过m+n。第三章 链表单链表的结点类(ListNode class)和链表类(List cla

19、ss)的类定义。template class List;/前视的类定义template class ListNode /链表结点类的定义friend class List;/List类作为友元类定义private: Type data;/数据域 ListNode *link;/链指针域public: ListNode ( ) : link (NULL) /仅初始化指针成员的构造函数 ListNode ( const Type& item ) : data (item), link (NULL) /初始化数据与指针成员的构造函数 ListNode * getNode ( const Type&

20、item, ListNode *next = NULL ) /以item和next建立一个新结点 ListNode * getLink ( ) return link; /取得结点的下一结点地址 Type getData ( ) return data; /取得结点中的数据 void setLink ( ListNode * next ) link = next; /修改结点的link指针 void setData ( Type value ) data = value; /修改结点的data值;template class List /单链表类定义private: ListNode *fir

21、st, *current;/链表的表头指针和当前元素指针public: List ( const Type& value ) first = current = new ListNode ( value ); /构造函数 List ( ) MakeEmpty ( ); delete first; /析构函数 void MakeEmpty ( );/将链表置为空表 int Length ( ) const;/计算链表的长度 ListNode * Find ( Type value );/搜索含数据value的元素并成为当前元素 ListNode * Locate( int i );/搜索第i个元

22、素的地址并置为当前元素 Type * GetData ( );/取出表中当前元素的值 int Insert ( Type value );/将value插在表当前位置之后并成为当前元素 Type *Remove ( );/将链表中的当前元素删去, 填补者为当前元素 ListNode * Firster ( ) current = first; return first; /当前指针定位于表头结点 Type *First ( );/当前指针定位于表中第一个元素并返回其值 Type *Next ( );/将当前指针进到表中下一个元素并返回其值 int NotNull ( ) return curr

23、ent != NULL; /表中当前元素空否？空返回1, 不空返回0 int NextNotNull ( ) return current != NULL & current-link != NULL; /当前元素下一元素空否？空返回1, 不空返回0;3-1线性表可用顺序表或链表存储。试问：(1) 两种存储表示各有哪些主要优缺点?(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？3-2 针对带

24、表头结点的单链表，试编写下列函数。(1) 定位函数Locate：在单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL。(2) 求最大值函数max：通过一趟遍历在单链表中确定值最大的结点。(3) 统计函数number：统计单链表中具有给定值x的所有元素。(4) 建立函数create：根据一维数组an建立一个单链表，使单链表中各元素的次序与an中各元素的次序相同，要求该程序的时间复杂性为O(n)。(5) 整理函数tidyup：在非递减有序的单链表中删除值相同的多余结点。3-3 设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将

25、这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。3-4 设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。3-5 从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆转，如右图所示。在图中的指针p指向当前正在访问的结点，指针pr指向指针p所指结点的左侧的结点。此时，指针p所指结点左侧的所有结点的链接方向都已逆转。(1) 编写一个算法，从任一给定的位置(pr, p)开

26、始，将指针p右移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最右边的结点上。(2) 编写一个算法，从任一给定的位置(pr, p)开始，将指针p左移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最左边的结点上。3-6 试写出用单链表表示的字符串类及字符串结点类的定义，并依次实现它的构造函数、以及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员函数。要求每个字符串结点中只存放一个字符。3-7 如果用循环链表表示一元多项式，试编写一个函数Polynomial : Calc(x)，计算多项式在x处的值。3-8 设a和b是两个用带有表头结点的循环链

27、表表示的多项式。试编写一个算法，计算这两个多项式的乘积c = a*b，要求计算后多项式a与b保持原状。如果这两个多项式的项数分别为n与m, 试说明该算法的执行时间为O(nm2)或O(n2m)。但若a和b是稠密的, 即其很少有系数为零的项, 那么试说明该乘积算法的时间代价为O(nm)。3-9 计算多项式 Pn (x) = a0 xn + a1 xn-1 + a2 xn-2 + + an-1 x + an的值，通常使用的方法是一种嵌套的方法。它可以描述为如下的迭代形式：b0 = a0 , bi+1 = x * bi + ai+1, i = 0, 1, , n-1。若设bn = pn （x）. 则问

28、题可以写为如下形式：Pn (x) = x * Pn-1 (x) + an ，此处， Pn-1 (x) = a0 xn-1 + a1 xn-2 + + an-2 x + an-1，这是问题的递归形式。试编写一个递归函数，计算这样的多项式的值。3-10 试设计一个实现下述要求的Locate运算的函数。设有一个带表头结点的双向链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次Locate (L, x)操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链

29、接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。3-11 利用双向循环链表的操作改写2-2题，解决约瑟夫(Josephus)问题。3-12 试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的rLink域中，并利用lLink域把所有结点按照其值从小到大的顺序连接起来。第四章 栈与队列4-1 改写顺序栈的进栈成员函数Push (x )，要求当栈满时执行一个stackFull ( )操作进行栈满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前Ma

30、xSize位置。4-2 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问：(1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种?(2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出进栈或出栈的序列)。4-3 试证明：若借助栈可由输入序列1, 2, 3, , n得到一个输出序列p1, p2, p3, , pn (它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在i j k，

31、使得pj pk F) /*注：按C+的优先级*/(6) !(A & !( (B D) ) )|(C ( )接收用广义表表示的树作为输入，建立广义表的存储表示；(2) 复制构造函数用另一棵表示为广义表的树初始化一棵树；(3) operator = ( )测试用广义表表示的两棵树是否相等；(4) operator 1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 6-6 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。6-7 如果一棵树有n1个度为1的结点, 有n2个度为2的结点, , nm个度为m

32、的结点, 试问有多少个度为0的结点? 试推导之。6-8 试分别找出满足以下条件的所有二叉树:(1) 二叉树的前序序列与中序序列相同;(2) 二叉树的中序序列与后序序列相同;(3) 二叉树的前序序列与后序序列相同。6-9 若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：(1) 统计二叉树中叶结点的个数。(2) 以二叉树为参数，交换每个结点的左子女和右子女。6-10 一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问:(1) 各层的结点个数是多少?(2)

33、编号为i的结点的父结点(若存在)的编号是多少?(3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少?(4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少?(5) 若结点个数为 n, 则高度h是n 的什么函数关系?6-11 试用判定树的方法给出在中序线索化二叉树上：6-11 已知一棵完全二叉树存放于一个一维数组Tn中，Tn中存放的是各结点的值。试设计一个算法，从T0开始顺序读出各结点的值，建立该二叉树的二叉链表表示。6-12 试编写一个算法，把一个新结点l作为结点s的左子女插入到一棵线索化二叉树中，s原来的左子女变成l的左子女。6-13 写出向堆中加入数据4, 2, 5

34、, 8, 3, 6, 10, 14时，每加入一个数据后堆的变化。6-14 判断以下序列是否是最小堆? 如果不是, 将它调整为最小堆。(1) 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 (2) 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 (3) 103, 97, 56, 38, 66, 23, 42, 12, 30, 52, 06, 20 (4) 05, 56, 20, 23, 40, 38, 29, 61, 35, 76, 28, 100 6-15 请画出右图所示的树所对应的二叉树。 6-16 在森林的二叉树表示中，用lli

35、nk存储指向结点第一个子女的指针，用rlink存储指向结点下一个兄弟的指针，用data存储结点的值。如果我们采用静态二叉链表作为森林的存储表示，同时按森林的先根次序依次安放森林的所有结点，则可以在它们的结点中用只有一个二进位的标志ltag代替llink，用rtag代替rlink。并设定若ltag = 0，则该结点没有子女，若ltag 0，则该结点有子女；若rtag = 0，则该结点没有下一个兄弟，若rtag 0，则该结点有下一个兄弟。试给出这种表示的结构定义，并设计一个算法，将用这种表示存储的森林转换成用llink - rlink表示的森林。6-17 二叉树的双序遍历(Double-order

36、 traversal)是指：对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树。试写出执行这种双序遍历的算法。6-18 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。6-19 已知一棵树的先根次序遍历的结果与其对应二叉树表示(长子-兄弟表示)的前序遍历结果相同, 树的后根次序遍历结果与其对应二叉树表示的中序遍历结果相同。试问利用树的先根次序遍历结果和后根次序遍历结果能否唯一确定一棵树? 举例说明。6-20 给定权值集合 15, 03, 14, 02, 06,

37、09, 16, 17 , 构造相应的霍夫曼树, 并计算它的带权外部路径长度。6-21 假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。试为这8个字母设计不等长Huffman编码, 并给出该电文的总码数。6-22 给定一组权值: 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 试构造一棵具有最小带权外部路径长度的扩充4叉树, 要求该4叉树中所有内部结点的度都是4, 所有外部结点的度都是0。这棵扩充4叉树的带权外部路径长度是多

38、少? (提示：如果权值个数不足以构造扩充4叉树，可补充若干值为零的权值，再仿照霍夫曼树的思路构造扩充4叉树)6-12 已知一棵完全二叉树存放于一个一维数组Tn中，Tn中存放的是各结点的值。试设计一个算法，从T0开始顺序读出各结点的值，建立该二叉树的二叉链表表示。6-14 写出向堆中加入数据4, 2, 5, 8, 3, 6, 10, 14时，每加入一个数据后堆的变化。6-16 请画出右图所示的树所对应的二叉树。6-17 在森林的二叉树表示中，用llink存储指向结点第一个子女的指针，用rlink存储指向结点下一个兄弟的指针，用data存储结点的值。如果我们采用静态二叉链表作为森林的存储表示，同时

39、按森林的先根次序依次安放森林的所有结点，则可以在它们的结点中用只有一个二进位的标志ltag代替llink，用rtag代替rlink。并设定若ltag = 0，则该结点没有子女，若ltag 0，则该结点有子女；若rtag = 0，则该结点没有下一个兄弟，若rtag 0，则该结点有下一个兄弟。试给出这种表示的结构定义，并设计一个算法，将用这种表示存储的森林转换成用llink - rlink表示的森林。6-18 二叉树的双序遍历(Double-order traversal)是指：对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树。

40、试写出执行这种双序遍历的算法。6-19 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。6-20 已知一棵树的先根次序遍历的结果与其对应二叉树表示(长子-兄弟表示)的前序遍历结果相同, 树的后根次序遍历结果与其对应二叉树表示的中序遍历结果相同。试问利用树的先根次序遍历结果和后根次序遍历结果能否唯一确定一棵树? 举例说明。6-22 假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。试为这8个字母设计不

41、等长Huffman编码, 并给出该电文的总码数。6-23 给定一组权值: 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 试构造一棵具有最小带权外部路径长度的扩充4叉树, 要求该4叉树中所有内部结点的度都是4, 所有外部结点的度都是0。这棵扩充4叉树的带权外部路径长度是多少?第7章 集合与搜索7-1 设A = 1, 2, 3 , B = 3, 4, 5 ，求下列结果：(1) A + B(2) A * B(3) A - B(4) A.Contains (1)(5) A.AddMember (1)(6) A.DelMember (1)(7) A.Min (

42、)7-2 试编写一个算法，打印一个有穷集合中的所有成员。要求使用集合抽象数据类型中的基本操作。如果集合中包含有子集合，各个子集合之间没有重复的元素，采用什么结构比较合适。7-3 当全集合可以映射成1到N之间的整数时，可以用位数组来表示它的任一子集合。当全集合是下列集合时，应当建立什么样的映射？用映射对照表表示。(1) 整数0, 1, , 99(2) 从n到m的所有整数，n m(3) 整数n, n+2, n+4, , n+2k(4) 字母 a, b, c, , z(5) 两个字母组成的字符串, 其中， 每个字母取自 a, b, c, , z。7-4 试证明：集合A是集合B的子集的充分必要条件是集

43、合A和集合B的交集是A。7-5 试证明：集合A是集合B的子集的充分必要条件是集合A和集合B的并集是B。7-6 设+、*、-是集合的或、与、差运算，试举一个例子，验证A + B = (A - B) + (B - A) + A * B7-7 给定一个用无序链表表示的集合，需要在其上执行operator+( ), operator*( ), operator- ( ), Contains(x), AddMember (x), DelMember(x), Min( )，试写出它的类声明，并给出所有这些成员函数的实现。7-8 设有序顺序表中的元素依次为017, 094, 154, 170, 275, 5

44、03, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的二叉搜索树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。7-9 若对有n个元素的有序顺序表和无序顺序表进行顺序搜索, 试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同?(1) 搜索失败;(2) 搜索成功, 且表中只有一个关键码等于给定值k的对象;(3) 搜索成功, 且表中有若干个关键码等于给定值k的对象, 要求一次搜索找出所有对象。7-10 假定用一个循环链表来实现一个有序表，并让指针head指向具有最小关键码的结点。指针current初始时等于head

45、，每次搜索后指向当前检索的结点，但如果搜索不成功则current重置为head。试编写一个函数search(head, current, key)实现这种搜索。当搜索成功时函数返回被检索的结点地址，若搜索不成功则函数返回空指针0。请说明如何保持指针current以减少搜索时的平均搜索长度。7-11 考虑用双向链表来实现一个有序表，使得能在这个表中进行正向和反向搜索。若指针p总是指向最后成功搜索到的结点，搜索可以从p指示的结点出发沿任一方向进行。试根据这种情况编写一个函数search(head, p, key)，检索具有关键码key的结点，并相应地修改p。最后请给出搜索成功和搜索不成功时的平均搜

46、索长度。p7-12 在一棵表示有序集S的二叉搜索树中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S1；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S = S1 S2 S3。若对于任意的a S1, b S2, c S3， 是否总有a b c？为什么？7-13 请给出下列操作序列运算的结果：Union(1, 2), Union(3, 4), Union(3, 5), Union(1, 7), Union(3, 6), Union(8, 9), Union(1, 8), Union(3, 10), Union(3, 11), Union(3, 12), Union(3, 13), Union(14, 15), Union(16, 17), Union(14, 16), Union(1, 3), Union(1, 14)，要求(1) 以任意方式执行Union；(2) 根据树的高度执行Union； (3) 根据树中结点个数执行Union。7-14 有n个结点的二叉搜索树具有多少种不同形态?7-15 设有一个输入数据的序列是 46, 25, 78, 62, 12, 37, 70, 29 , 试画出从空树起，逐个输入各个数据