数据结构(C++版)doc.doc

133数据结构(C+版)数据结构(C+版)第1章 绪论1.1 数据结构的重要性图 1-11.2 面向对象程序设计1.2.1 面向对象程序设计方法1. 面向对象2. 面向对象程序设计方法的特征1.2.2 C+的特征及基本概念1.3 基本术语图1-2 数据元素和数据项1.4 抽象数据类型1.5 数据结构的概念1.6 数据的逻辑结构图1-3 一周七天数据结构图示1.7 数据的存储结构1. 顺序存储方法2. 链式存储方法图1-5 线性结构的链接存储3. 索引存储方法4. 散列存储方法1.8 数据的运算1.9 数据的逻辑结构、存储结构及数据的运算的关系1.10 算法的描述小结习题1. 填空题(1) 数据的逻辑结构可形式地用一个二元组B(K，R)来表示，其中K是，R是。(2) 存储结构可根据数据元素在机器中的位置是否连续分为，。(3) 是数据的基本单位，有时一个由若干个组成，在这种情况下，称为记录，是数据的最小单位，而由记录生成的线性表称为。(4) 算法的基本要求有，。 (5) 度量算法效率可通过，两方面进行。(6) 在C+中建立参数类型和参数个数不同的同名函数是可能的，这称为函数。2. 综合题(1) 简述下列术语:数据 数据元素 数据对象 数据结构 存储结构 数据类型 抽象数据类型(2) 常用的存储表示方法有哪几种？(3) 举例说明一下数据结构和算法的关系。(4) 设有数据逻辑结构为B=(K，R)，K=k1，k2，k9,R=， 画出逻辑结构图，并确定相对于R哪些结点是开始结点，哪些结点是终端结点？(5) 试举一个数据结构的例子，并叙述其逻辑结构、存储结构、运算三方面的内容。(6) 什么是算法？详述算法设计的目的和算法必须满足的条件。第2章 算法分析2.1 算法分析的概念图2-1 小规模输入时的运行时间图2-2 中等规模输入时的运行时间2.2 算法运行时间举例2.3 最大连续子序列之和问题2.3.1 简单易懂的O(n3)算法2.3.2 一个改进的O(n2)算法2.3.3 一个线性算法2.4 静态搜索问题2.4.1 顺序搜索2.4.2 二分搜索2.4.3 插值搜索2.5 检验一个算法分析2.6 Big|Oh分析法的限制小结习题1. 简答题 (1) 如定理2-1所描述的,从盒子中往外取球,在A)D)所给的答案中，哪一个是定理中变量i，j，k对应的值？ A) red，5，6 B) blue，5，6 C) blue，3，red D) 6，5，red(2) 基于定理2-2的描述，为什么不能充分获得一个最大连续子序列之和的次平方运行时间？(3) 假设T1(n) = O(F(n)，T2(n) = O(F(n)，下列哪一个正确？ A) T1 (n)+ T2 (n) = O(F(n)B) T1 (n)- T2 (n) = O(F(n) C) T1 (n)/ T2 (n) = O(1)D) T1 (n) = O(T2 (n)(4) 将下列各式组合成与Big|Oh相等的函数。 x2，x2 + x，x2 - x，x3/(x - 1)(5) 程序A和程序B经分析，有不超过150nlogn和n2的最坏情况下的运行时间，如可能，分别回答下列各问题: A) 当n值很大时(n 10 000),哪个程序对运行时间有保证？ B) n值较小(n 1000)时，哪一个程序对运行时间有更好的保证？ C) 在n = 1000的平均情况下，哪个程序运行更好？ D) 在所有可能的输入中，程序B总比程序A运行的快吗？(6) 对于算法2-4的二分搜索，写出用以下代码片段替换的结果。 A) 第13行(测试): low highB) 第15行(赋值): mid = low+high/2 C) 第18行(赋值): low = midD) 第20行(赋值): high = mid2. 理论题(1) 采用典型算法用手工来计算下述问题，确定其运行时间。 A) 两个n位整数相加B) 两个n位整数相乘 C) 两个n位整数相除(2) 对于n个项来说，以下计算xn的算法运行时间是多少？ double power(double x，int n) double result = 1.0; for(int i = 0; i right， *q=DL-left;while(p!=q & p-left=q & ) if(p-data=q-data) ; ;else sym=0;return sym;2. 综合题(1) 线性表可用顺序表或链表存储。试问: 两种存储方式各有哪些主要优缺点？ 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变。在此情况下，应选用哪种存储表？为什么？ 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，应采用哪种存储表？为什么？(2) 描述以下3个概念的区别: 头指针、头结点、第一个结点。(3) 试写出一个计算线性链表P中结点个数的算法，其中指针p指向该表中第一个结点，尾结点的指针域为空。(4) 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?(5) 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?(6) 设有一个线性表(u1，u2，,un)，试编写一个函数将这个线性表原地逆置，即线性表为(un，,u2，u1)，并要求算法的空间复杂度为O(1)。(7) 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?(8) 假设La、Lb为两个递增有序的线性链表，试写出将这两个线性链表归并成一个线性链表Lc的操作算法。(9) 将学生成绩按成绩高低排列建立了一个有序单链表，每个结点包括: 学号、姓名和课程成绩。 输入一个学号，如果与链表中的结点的学号相同，则将此结点删除； 在链表中插入一个学生的记录，使得插入后链表仍然按成绩有序排列。(10) 某仓库中有一批零件，按其价格从低到高的顺序构成一个单链表存于计算机内，链表的每一个结点说明同样价格的若干个零件。现在又有m个价格为s的零件需要进入仓库，试写出仓库零件链表增加零件的算法。链表结点结构如下:数量价格指针 (11) 设指针p指向单链表的首结点，指针x指向单链表中的任意一个结点，写出在x前插入一个结点i的算法。(12) 设多项式A和B采用线性链表的存储方式存放，试写出两个多项式相加的算法，要求把相加结果存放在A中。(13) 设a和b是两个用带有表头结点的循环链表表示的稠密多项式。试编写一个算法，计算这两个多项式的乘积c=ab，要求计算后多项式a与b保持原状。如果这两个多项式的项数分别为n与m，试说明该算法的执行时间为O(nm)。(14) 设指针a和b分别为两个带头结点的单链表的头指针，编写实现从单链表La中删除自第i个数据元素起，共length个数据元素，并把它们插入到单链表Lb中第j个元素之前的算法。(15) 设La和Lb是两个有序的循环链表，Pa和Pb分别指向两个表的表头结点，试写一个算法将这两个表归并为一个有序的循环链表。(16) 已知有一个单向循环链表，其每个结点中含3个域: pre、data和next，其中data为数据域，next为指向后继结点的指针域，pre也为一个指针域，但是它的值为空(NULL)，试编写一个算法将此单链表改为双向循环链表，即使pre成为指向前驱结点的指针域。(17) 设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，要求逆转的结果链表的表头指针h指向原链表的最后一个结点。(18) 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。(19) 设计一个函数，删除带头结点的单链表类对象L中数据元素等于item的所有结点:template void delete(const Chain & L，Type item)(20) 设A=(a1，am)和B=(b1，bn)均为线性表，A1和B1分别为A和B中除去最大前缀后的子表(例如，A=(x，y，y，z，x，z)，B=(x，y，y，z，y，x，x，z)，则A1=(x，z)，B1=(y，x，x，z)，以顺序表为存储结构，编写求A1和B1的算法。(21) 假设以两个按元素递增有序排列的单链表A和B分别表示集合。现要求另辟空间构成一个单链表C，其元素值为A和B中元素值的交集，且在C中也依值递增有序排列，试编写求得C的算法。(22) 试写出用单链表表示的字符串类及字符串结点类的定义，并依次实现它的构造函数，以及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员函数。要求每个字符串结点中只存放一个字符。第4章 栈和队列4.1 栈4.1.1 栈的定义图4-1 栈的示意图4.1.2 栈的顺序存储结构图4-2 栈顶指针和栈中元素之间的关系4.1.3 栈的链式存储结构图4-4 链栈示意图4.1.4 顺序栈和链式栈的比较4.2 栈的应用4.2.1 迷宫问题图4-6 迷宫问题的矩阵表示图4-8 为迷宫增加一圈障碍物4.2.2 表达式求值图4-10 算术表达式运算栈的变化过程4.2.3 汉诺塔问题图4-11 汉诺塔问题4.2.4 数制转换4.2.5 行编辑4.3 队列4.3.1 队列的定义图4-12 队列示意图图4-13 双端队列示意图4.3.2 队列的顺序存储1. 顺序队列图4-14 空顺序队列图4-15 非空顺序队列图4-16 删除前的队列图4-17 删除元素A后的示意图图4-18 待插入队列图4-19 在队尾添加元素G后的示意图图4-20 队列已满的示意图图4-21 头、尾指针和队列中元素之间的关系2. 循环队列图4-22 循环队列示意图图4-23 循环队列的头尾指针 图4-24 队空时循环队列的指针4.3.3 队列的链式存储图4-25 空链队列图4-26 非空链队列图4-27 队列运算指针变化情况4.3.4 顺序队列与链式队列的比较4.3.5 优先队列4.4 队列的应用4.4.1 解决设备速度不匹配问题4.4.2 舞伴问题4.4.3 火车车厢重排图4-28 三个缓冲铁轨的重排示例小结习题1. 填空题(1) 设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳个元素。(2) 一个栈的输入序列为1，2，3，4，5则下列序列中不可能是栈的输出序列的是。 A) 2，3，4，1，5 B) 5，4，1，3，2 C) 2，3，1，4，5 D) 1，5，4，3，22. 综合题(1) 对于下面的每一步画出栈中元素及栈顶指针的示意图: 空栈； 元素A入栈； 元素B入栈； 删除栈顶元素； 元素C入栈； 元素D入栈。(2) 比较栈和队列的相同点和不同点，举例说明。(3) 解释LIFO和FIFO，并结合现实生活中的实际例子说明栈和队列的实用性。(4) 对于算术表达式3*(5-2)+7，用栈存储运算对象和运算符，试说明该算术表达式的运算过程。(5) 若依次输入数据元素序列a，b，c，d，e，f，g进栈，出栈操作可以和入栈操作间隔进行，则下列哪些元素序列可以由出栈序列得到？ d，e，c，f，b，g，a； f，e，g，d，a，c，b； e，f，d，g，b，c，a； c，d，b，e，f，a，g。(6) 编写一个算法，用来判别表达式中开、闭括号是否配对出现。(7) 链栈中为何不设头指针？(8) 循环队列的优点是什么？如何判断它的空和满？(9) 试述队列的链式存储结构和顺序存储结构的优缺点。(10) 假设以一维数组sn存储循环队列的元素，若要使这n个存储空间都得到利用，需另设一个标志flag，以flag为0或1来区分队头指针和队尾指针相同时队列是空还是满。编写与此结构相对应的初始化、入队列和出队列的算法。(11) 试编写算法将下面的中缀表达式转换为后缀表达式: (a*(b+c)+(b/d)*a。(12) 分别在栈和队列(至少含有3个结点)中实现删除紧邻栈顶或队头的结点，并用P返回其值。(13) 试编写下面定义的递归函数的递归算法，并根据算法画出求G(5，2)时栈的变化过程。G(m,n)=0m=0,n0G(m-1,2,n)m0,n0 (14) 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题: 若入、出栈次序为push(1)，pop()，push(2)，push(3)，pop()，pop()，push(4)，pop()，则出栈的数字序列是什么(这里push(i)表示i进栈，pop()表示出栈)？ 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。 在1、2、3、4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的?(15) 回文是指正读反读均相同的字符序列，如abba和abdba均是回文，但good不是回文。试写一个算法判定给定的字符向量是否为回文。(提示: 将一半字符入栈)(16) 假设以数组qm存放循环队列中的元素，同时以rear和length分别指示循环队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的插入(enQueue)和删除(deQueue)元素的操作。(17) 试借助栈实现单链表上的逆置运算。(18) 编写一个算法，将一个非负的十进制整数N转换为另一个基为B的B进制数。(19) 以下栈操作的输出是什么？ SeqStack s; int x = 5， y = 3; s.push (8); s.push (9); s.push (y); x = s.pop(); s.push (18); x = s.pop(); s.push (22); while (! s.empty() y = s.pop(); cout y endl;cout x endl;(20) 以下队列操作的输出是什么？ LinkQueue q; int x = 5， y = 3; q.enQueue (8); q.enQueue (9); q.enQueue (y); x = q.deQueue(); q.enQueue (18); x = q.deQueue(); q.enQueue (22); while (! q.empty() y = q.deQueue(); cout y endl;cout x endl;(21) 扩充LinkStack类的定义，增加以下操作。 把堆栈拆分成两个部分，第一部分包含从栈底开始的一半元素，第二部分包含其余的元素。 合并两个堆栈，把第二个堆栈的所有元素放到第一个堆栈的顶部，并且第二个堆栈中元素的相对次序不发生变化。合并完成之后，第二个堆栈为空。(22) 扩充队列的ADT，增加以下函数: 把一个队列分解成两个队列，其中一个队列包含原队列中的第1，3，5，2n-1，奇数个元素，另一个队列包含其余元素。 合并两个队列，在新队列中，从第一个队列开始，两个队列的元素轮流排队，若某个队列中的元素先用完，则将另一个队列中的剩余元素依次插入新队列的尾部。合并完成之后，各元素之间的相对次序应与合并前的相对次序相同。(23) 试用一个数组实现两个栈，并要求只有两个栈中元素的总和超过这个数组的长度限制时，才产生上溢错误。(24) 用非递归算法解决迷宫问题。(25) 试用反证法证明: 若借助栈可由输入序列1，2，,n得到一输出序列p1，p2，pn， 则在输出序列中可能出现以下情况，即存在ijk，使得pjpkpi。第5章 串5.1 C+语言的字符和字符串5.2 串的基本概念5.3 串的存储结构5.3.1 串的顺序存储结构1. 紧凑格式2. 非紧凑格式3. 串的字节存储5.3.2 串的链式存储结构1. 结点大小为1的链式存储结构图5-4 链式存储结构2. 结点大小为K的链式存储图5-5 块链存储结构5.3.3 串的索引存储结构1. 带长度的名字表图5-6 带长度的名字表2. 带末指针的名字表图5-7 带末指针的名字表5.4 串的操作5.4.1 常用的C+字符串函数5.4.2 串的抽象数据类型的描述5.4.3 串的类定义5.4.4 部分成员函数的实现5.5 串的基本运算与实现5.5.1 串插入1. 顺序串上的插入图5-8 顺序串的插入(i=3)2. 链串上的插入图5-9 链串上的插入(i=3)5.5.2 串删除1. 顺序串上的删除2. 链串上的删除图5-11 链串上的删除(i=2,j=3时的情形)5.6 模式匹配5.6.1 模式匹配的BF算法图5-12 模式匹配过程图5-13 模式匹配的一般性过程5.6.2 模式匹配的KMP算法图5-14 模式匹配示例图 5-15 模式串的右滑图5-16 求nextj+1的模式匹配5.7 串在文本编辑中的应用习题1. 判断题(1) 数组是同类型值的集合。( )(2) 数组是一组相继的内存单元。( )(3) 数组是一种复杂的数据结构，数组元素之间的关系，既不是线性的，也不是树形的。( )(4) 插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。( )(5) 使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。( )(6) 广义表是由零或多个单元素或子表所组成的有序列，所以广义表可能为空表。( )(7) 线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。( )(8) 线性表的逻辑顺序与物理顺序总是一致的。( )(9) 线性表的顺序存储表示优于链式存储表示。( )(10) 每种数据结构都应具备三种基本运算: 插入、删除和搜索。( )2. 单选题(1) 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为( )。 A) 13 B) 33C) 18D) 40 (2) 一个nn的对称矩阵，如果以行或列为主序存入内存，则其容量为( )。 A) n2 B) n2/2 C) n(n+1)/2 D) (n+1)(n+1)/2 E) (n-1)n/2 F) n(n-1) (3) 二维数组a的每个元素是由6个字符组成的串，行下标i的范围从08，列下标j的范围是从110。从供选择的答案中选出正确答案填入下列关于数据存储叙述中的( )内。 存放a至少需要( )字节。 A) 90 B) 180 C) 240 D) 270 E) 540 a的第8列和第5行共占( )字节。 A) 108 B) 114 C) 54 D) 60 E) 150 若a按行存放，元素a8，5的起始地址与当a按列存放的元素( )的起始地址一致。 A) a8，5 B) a3，10 C) a5，8 D) a0，9 (4) 已知广义表LS=(a，(b，c，d)，e)，运用head和tail函数取出LS中单元素b的运算是( )。 A) head(head(LS) B) tail(head(LS) C) head(head(tail(LS) D) head(tail(LS) (5) 已知广义表A=(a，b，c)，(d，e，f)，从A中取出单元素e的运算是( )。 A) tail(head(A) B) head(tail(A) C) head(tail(tail(head(A) D) head(tail(head(tail(A)3. 综合题(1) 画出下列广义表的图形表示和它们的存储表示: D(A(c)， B(e)， C(a， L(b， c， d) J1(J2(J1， a， J3(J1)， J3(J1) (2) 利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来: L1(apple， pear， banana， orange) L2(apple， pear)， (banana， orange) L3(apple)， (pear)， (banana)， (orange) L4(apple)， (pear)， (banana)， orange) L5(apple)， pear)， banana)， orange) L6(apple， (pear， (banana)， orange) (3) 广义表具有可共享性，因此在遍历一个广义表时必须为每一个结点增加一个标志域mark，以记录该结点是否访问过。一旦某一个共享的子表结点被作了访问标志，以后就不再访问它。 试定义该广义表的类结构。 采用递归的算法对一个非递归的广义表进行遍历。 试使用一个栈，实现一个非递归算法，对一个非递归广义表进行遍历。(4) 编写函数，对一个下三角矩阵和一个上三角矩阵进行乘法运算(两个矩阵都是按行的方式存储在一个一维数组中)，所得到的结果用一个二维数组来描述。函数的时间复杂性是多少？(5) 假设有一个1010的对称矩阵A1010，采用按行压缩存储的方式存放于一个一维数组B中，则数组B的容量应有多大？若设A00为第一个元素，存放于B0， 并且矩阵A的每一个数组元素在数组B中占一个数组元素的位置，则A85 在数组B中的位置是多少？(6) 画图及计算题 给定一奇数n，构造一个n阶魔阵。n阶魔阵是一个n阶方阵，其元素由自然数1，2，3，n组成。魔阵的每行元素之和，每列元素之和以及主、副对角线之和均相等。即对于给定的奇数n以及i=1，2，n，魔阵A满足条件:nk=1aik=nk=1aki=nk=1akk=nk=1ak,n-k+1 设有一每行每列都有8个正方格的棋盘。试用8个棋子分布到格子上，要求满足以下条件: 任意两个棋子不在同一行和同一列； 任意两个棋子不在同一斜线上。问有多少种摆法。 设B(nm)是一个二维对称数组，为节省存储单元，只将上三角的元素存于内存中，试推导元素Bi，j(0in，0jm)的位置的公式。 求三维数组按行优先顺序存储的地址公式。 求下列广义表运算的结果 head(p，h，w)； tail(b，k，p，h)； head(tail (a，b)，(c，d)。 画出下列广义表的图形表示: D(A()，B(e)，C(a，L(b，c，d)； M1(a，(b，c，d)，e)。4. 算法设计题(1) 设有三对角矩阵Ann，将其三条对角线上的元素逐行地存储到向量B0.3n-3中，使得Bk=aij，求: 用i，j 表示k的下标变换公式; 用 k 表示 i，j 的下标变换公式。 (2) 当三角矩阵采用题(1)所述的压缩存储时，写一算法求三对角矩阵在这种压缩存储表示下的转置矩阵。(3) 当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。第6章 数组和广义表6.1 C+中数组的定义及抽象数据类型表示6.1.1 C+中数组的定义6.1.2 数组的抽象数据类型表示6.2 数组的顺序存储结构6.3 矩阵的压缩存储6.3.1 特殊矩阵的压缩存储1. 对称矩阵的压缩存储2. 三角矩阵的压缩存储3. 对角矩阵的压缩存储图6-7 对角矩阵6.3.2 稀疏矩阵的压缩存储1. 三元组顺序表2. 十字链表6.4 广义表的概念图6-9 广义表的图形表示6.5 广义表的存储结构表示图6-10 广义表的存储结构示例6.6 广义表的运算1. 广义表结点类的存取成员函数2. 求广义表的深度depth(LS)3. 广义表的复制算法4. 广义表的删除算法图6-11 广义表的删除示例5. 从字符串s建立广义表的链表表示ls图6-12 从字符串建立的广义链表小结习题1. 判断题(1) 数组是同类型值的集合。( )(2) 数组是一组相继的内存单元。( )(3) 数组是一种复杂的数据结构，数组元素之间的关系，既不是线性的，也不是树形的。( )(4) 插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。( )(5) 使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。( )(6) 广义表是由零或多个单元素或子表所组成的有序列，所以广义表可能为空表。( )(7) 线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。( )(8) 线性表的逻辑顺序与物理顺序总是一致的。( )(9) 线性表的顺序存储表示优于链式存储表示。( )(10) 每种数据结构都应具备三种基本运算: 插入、删除和搜索。( )2. 单选题(1) 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为( )。 A) 13 B) 33C) 18D) 40 (2) 一个nn的对称矩阵，如果以行或列为主序存入内存，则其容量为( )。 A) n2 B) n2/2 C) n(n+1)/2 D) (n+1)(n+1)/2 E) (n-1)n/2 F) n(n-1) (3) 二维数组a的每个元素是由6个字符组成的串，行下标i的范围从08，列下标j的范围是从110。从供选择的答案中选出正确答案填入下列关于数据存储叙述中的( )内。 存放a至少需要( )字节。 A) 90 B) 180 C) 240 D) 270 E) 540 a的第8列和第5行共占( )字节。 A) 108 B) 114 C) 54 D) 60 E) 150 若a按行存放，元素a8，5的起始地址与当a按列存放的元素( )的起始地址一致。 A) a8，5 B) a3，10 C) a5，8 D) a0，9 (4) 已知广义表LS=(a，(b，c，d)，e)，运用head和tail函数取出LS中单元素b的运算是( )。 A) head(head(LS) B) tail(head(LS) C) head(head(tail(LS) D) head(tail(LS) (5) 已知广义表A=(a，b，c)，(d，e，f)，从A中取出单元素e的运算是( )。 A) tail(head(A) B) head(tail(A) C) head(tail(tail(head(A) D) head(tail(head(tail(A)3. 综合题(1) 画出下列广义表的图形表示和它们的存储表示: D(A(c)， B(e)， C(a， L(b， c， d) J1(J2(J1， a， J3(J1)， J3(J1) (2) 利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来: L1(apple， pear， banana， orange) L2(apple， pear)， (banana， orange) L3(apple)， (pear)， (banana)， (orange) L4(apple)， (pear)， (banana)， orange) L5(apple)， pear)， banana)， orange) L6(apple， (pear， (banana)， orange) (3) 广义表具有可共享性，因此在遍历一个广义表时必须为每一个结点增加一个标志域mark，以记录该结点是否访问过。一旦某一个共享的子表结点被作了访问标志，以后就不再访问它。 试定义该广义表的类结构。 采用递归的算法对一个非递归的广义表进行遍历。 试使用一个栈，实现一个非递归算法，对一个非递归广义表进行遍历。(4) 编写函数，对一个下三角矩阵和一个上三角矩阵进行乘法运算(两个矩阵都是按行的方式存储在一个一维数组中)，所得到的结果用一个二维数组来描述。函数的时间复杂性是多少？(5) 假设有一个1010的对称矩阵A1010，采用按行压缩存储的方式存放于一个一维数组B中，则数组B的容量应有多大？若设A00为第一个元素，存放于B0， 并且矩阵A的每一个数组元素在数组B中占一个数组元素的位置，则A85 在数组B中的位置是多少？(6) 画图及计算题 给定一奇数n，构造一个n阶魔阵。n阶魔阵是一个n阶方阵，其元素由自然数1，2，3，n组成。魔阵的每行元素之和，每列元素之和以及主、副对角线之和均相等。即对于给定的奇数n以及i=1，2，n，魔阵A满足条件:nk=1aik=nk=1aki=nk=1akk=nk=1ak,n-k+1 设有一每行每列都有8个正方格的棋盘。试用8个棋子分布到格子上，要求满足以下条件: 任意两个棋子不在同一行和同一列； 任意两个棋子不在同一斜线上。问有多少种摆法。 设B(nm)是一个二维对称数组，为节省存储单元，只将上三角的元素存于内存中，试推导元素Bi，j(0in，0jm)的位置的公式。 求三维数组按行优先顺序存储的地址公式。 求下列广义表运算的结果 head(p，h，w)； tail(b，k，p，h)； head(tail (a，b)，(c，d)。 画出下列广义表的图形表示: D(A()，B(e)，C(a，L(b，c，d)； M1(a，(b，c，d)，e)。4. 算法设计题(1) 设有三对角矩阵Ann，将其三条对角线上的元素逐行地存储到向量B0.3n-3中，使得Bk=aij，求: 用i，j 表示k的下标变换公式; 用 k 表示 i，j 的下标变换公式。 (2) 当三角矩阵采用题(1)所述的压缩存储时，写一算法求三对角矩阵在这种压缩存储表示下的转置矩阵。(3) 当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。第7章 树7.1 树的基本概念7.1.1 树的定义图7-1 树的示例图7-2 非树结构的示例7.1.2 树的表示形式图7-3 树的其他表示形式7.1.3 树的常用术语7.1.4 树的基本操作7.1.5 一个树的接口7.1.6 树的基本算法7.2 二叉树7.2.1 二叉树的定义图7-4 二叉树示意图图7-5 二叉树的五种基本形态图7-6 满二叉树图7-7 完全二叉树和非完全二叉树7.2.2 二叉树的性质图7-8 完全二叉树中结点i和i+1的左、右孩子7.2.3 二叉树的接口7.2.4 二叉树的存储结构1. 顺序存储结构图7-9 带有结点编号的完全二叉树图7-10 二叉树的顺序存储结构图7-11 添上虚结点后的完全二叉树2. 链式存储结构图7-12 二叉树的结点及其存储结构图7-13 二叉树的二叉链表及三叉链表存储结构图7.2.5 二叉树的遍历1. 前序遍历二叉树(DLR)2. 中序遍历二叉树(LDR)3. 后序遍历二叉树(LRD)4. 二叉树的层次遍历7.2.6 二叉树遍历的应用图7-14 表达式(a+b*(c-d)-e/f)的二叉树7.3 线索二叉树7.3.1 线索二叉树的类定义图7-15 中序线索二叉树及其存储结构图7-16 后序后继线索二叉树(虚线表示线索)7.3.2 中序线索二叉树1. 建立中序线索二叉树2. 中序线索化二叉树中的部分成员函数的实现3. 在中序线索树二叉树上插入结点7.4 树、森林和二叉树的关系7.4.1 树的存储结构1. 双亲表示法图7-17 树的双亲表示法示例2. 孩子表示法图7-18 图7-17(a)中树的另外两种表示法3. 孩子兄弟表示法图7-19 图7-17中树的孩子兄弟链表7.4.2 森林与二叉树的转换1. 树、森林转换成二叉树图7-20 树与二叉树之间的关系图7-21 森林与二叉树的关系图7-22 图7-21(a)的森林转换为二叉树的过程2. 二叉树转换成树、森林图7-23 图7-21(c)的二叉树转换为森林7.4.3 树和森林的遍历1. 前序遍历森林2. 后序遍历森林图7-24 森林和对应的二叉树7.5 霍夫曼树及其应用7.5.1 霍夫曼树的定义图7-25 具有不同带权路径长度的二叉树7.5.2 霍夫曼树的构造图7-26 一棵霍夫曼树的构造过程7.5.3 霍夫曼树在编码问题中的应用图7-27 前缀编码示例小结习题1. 判断题(1) 二叉树是树的特殊形式。( )(2) 由树转换成二叉树，其根结点的右子树总是空的。( )(3) 前序遍历树和前序遍历与该树对应的二叉树，其结果不同。( )(4) 后序遍历树和中序遍历与该树对应的二叉树，其结果不同。( )(5) 前序遍历森林和前序遍历与该森林对应的二叉树，其结果不同。( )(6) 后序遍历森林和中序遍历与该森林对应的二叉树，其结果不同。( )(7) 在二叉树中插入结点后，该二叉树就不是二叉树。( )(8) 霍夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。( )(9) 用一维数组存放二叉树时，总是以前序遍历存储结点。( )2. 选择题(1) 有一棵二叉树，如图7-28所示该二叉树是( )。图7-28 A) 二叉平衡树B) 二叉排序树 C) 堆的形状 (2) 线索化二叉树中某结点没有孩子的充要条件是( )。 A) D.leftChild=NULL B) D.leftTag=1 C) D.leftTag=0 (3) 如果结点A有3个兄弟，而且B是A的双亲，则B的度是( )。 A) 4 B) 5 C) 1 (4) 树B的层号表示1a，2b，3d，3e，2c 对应于下面的( )。 A) 1a2b3d，3e，2c B) abd，e，c C) ab，de，c D) abd，e，c (5) 某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1，2，,n。且有如下性质: T中任意结点V，其编号等于左子树上的最小编号减1，而V的右子