东软数据结构,树和二叉树复习题

精选文库树和二叉树：纸质作业一、已知二叉树T逻辑结构如下图所示，请分别用顺序存储和二叉链表存储法表示此树。二、将下面的森林F=T1，T2，T3转换为对应的二叉树，并写出相应二叉树的先根遍历序列。三、将下列由三棵树组成的森林转换为二叉树，并写出相应二叉树的中根遍历序列NPGHJMOLIKEDFBAC四、已知树T的孩子链表存储结构如图所示，试画出此树逻辑结构，以及此树转换成的二叉树逻辑结构，并写出二叉树的后根遍历序列五、设一棵二叉树的先序序列为：A B D F C E G H 中序遍历序列为： B F D A G E H C（1）画出这棵二叉树。（2）将这棵二叉树转换成对应的树（或森林）。六、给定集合15,3,14,2,6,9,16,17（1）构造相应的huffman树（规定：二叉树中两个结点，权值小的结点居左）（2）计算它的带权路径长度（3）写出它的huffman编码：（规定：左子树编码为0，右子树编码为1,左小右大）七、假设通信电文使用的字符集为a,b,c,d,e,f，各字符在电文中出现的频度分别为：0.34，0.05，0.12，0.23，0.08，0.18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子节点的权值小于右孩子节点的权值，左分支表示字符“0”，右分支表示字符“1”)，然后分别写出每个字符对应的编码。八、假定教室中有A、B、C、D、E五个设备，需编写一套指令集对五个设备进行自动开关控制，五个设备一天中的使用次数分别是7，5，2，4，9次。为使得指令集长度最短，请对五个设备进行编码，要求画出哈夫曼树，并写出五个设备所对应的哈夫曼编码。九、假定用于通讯的电文仅有8个字母C1，C2，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树，并写出8个字符的哈夫曼编码十、A,B,C,D,E的权值为3, 2, 4, 5, 1，用此权值构造哈夫曼（Huffman）树，并求此哈夫曼（Huffman）树和各个字符的哈夫曼编码（左分支为0，右分支为1）纸质作业2：排序一、初始关键字序列如下：49，38， 65，97，76，13，27，49，55 04，请写出它们的希尔排序的全过程(其中d=5,3,1）二、给定的关键字序列21，22，27，78，40，05，47，69，12，99，要按升序排序，请写出采用冒泡排序法前3趟的结果，和用堆排序法选择出最大和次大关键字的结果（图）三、已知某文件的记录关键字集为50，10，75，40，45，85，80，写出快速排序方法进行排序的前2次划分的结果四、已知某文件的记录关键字集为50，10，30，40，45，85，80，要从小到大进行排序，请分别写出直接插入排序的前2趟结果和直接选择排序的前3趟结果。五、设要将序列（17,8,3,25,16,1,13,19,18,4,6,24）中的关键字按升序重新排列，请给出对该序列进行冒泡排序的第一趟排序结果、及以第一个元素为枢轴的快速排序的第一次划分的结果。纸质作业3：查找一、设哈希（Hash）表的地址范围为013，哈希函数为：H（K）K MOD 13。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （23，24，32，4，31，30，46，47）造出Hash表，试回答下列问题：（1） 画出哈希表的示意图；（2） 若查找关键字30，需要依次与哪些关键字进行比较？（3） 若查找关键字14，需要依次与哪些关键字比较？假定每个关键字的查找概率相等，求查找成功时的平均查找长度。二、请用序列（45，24，53，12，37，93）建立一棵二叉排序树，画出该树，并求在等概率情况下，查找成功的平均查找长度。三、选取哈希函数H(key)key Mod 11，用线性探测再散列开放定址法解决冲突。试在010的散列地址空间内对关键字序列19、11、31、23、17、27、41、13、91、61构造哈希表，并计算在等概率下成功查找的平均查找长度。四、设有一组关键字9,1,23,14,55,20,84,27，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的线性探测再散列方法解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。五、设哈希（Hash）表的地址范围为017，哈希函数为：H （K）=K MOD 16，K为关键字，用线性探测再散列法处理冲突，输入关键字序列：10，24，32，17，31，30，46，47，40，63，49造出哈希表，试回答下列问题： （1） 画出哈希表示意图； （2） 若查找关键字63，需要依次与哪些关键字比较?（3） 若查找关键字60，需要依次与哪些关键字比较?（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。六、对于序列：12，16，23，34，45，57，78，91，95，100，112进行二分法查找：（1）画出二分查找判定树（2）求出等概率情况下，该二分查找的ASL？ （3）查找元素95需要经过几次比较？和哪些元素比较？ （4）查找元素20需要经过几次比较确定找不到？和哪些元素比较？ 七、已知如下所示长度为12的表(34,25,68,72,21,15,49,29,77,8,19,102)（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树（2）并求其在等概率的情况下查找成功的平均查找长度。习题一参考答案2试述数据结构研究的3个方面的内容。参考答案: 数据结构研究的3个方面分别是数据的逻辑结构、数据的存储结构和数据的运算（操作）。3试述集合、线性结构、树型结构和图型结构四种常用数据结构的特性。参考答案: 集合结构：集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其它关系，它们之间的关系是松散性的。 线性结构：线性结构中数据元素之间存在“一对一”的关系。即若结构非空，则它有且仅有一个开始结点和终端结点，开始结点没有前趋但有一个后继，终端结点没有后继但有一个前趋，其余结点有且仅有一个前驱和一个后继。 树形结构：树形结构中数据元素之间存在“一对多”的关系。即若结构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点有且仅有一个前驱，所有结点都可以有多个后继。 图形结构：图形结构中数据元素之间存在“多对多”的关系。即若结构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。4设有数据的逻辑结构的二元组定义形式为B=(D,R)，其中D=a1,a2,an，R=| i=1,2,，n-1，请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。参考答案: 顺序存储结构示意图如下： 链式存储结构示意图如下：5设一个数据结构的逻辑结构如图1.9所示，请写出它的二元组定义形式。图1.9 第5题的逻辑结构图参考答案: 它的二元组定义形式为B=（D，R），其中D=k1,k2,k3,k4,k5,k6,k7,k8,k9，R=, 。6设有函数f (n)=3n2-n+4，请证明f (n)=O(n2)。习题二参考答案一、选择题1. 链式存储结构的最大优点是（ ）。A.便于随机存取B.存储密度高 C.无需预分配空间D.便于进行插入和删除操作 2. 假设在顺序表a0,a1,an1中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是（）。A. 106 B. 107 C.124 D.1283. 在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ ）存储方式。A.顺序表B. 带头结点的单链表C.不带头结点的单链表D. 循环单链表4. 在链表中若经常要删除表中第一个结点或在最后一个结点之后插入一个新结点，则宜采用（ ）存储方式。A. 顺序表B. 用头指针标识的循环单链表C. 用尾指针标识的循环单链表D. 双向链表5. 在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为S,则修改链的java语句序列是（ ）。A. s.setNext(p); q.setNext(s); B. p.setNext(s.getNext(); s.setNext(p);C. q.setNext(s.getNext(); s.setNext(p); D. p.setNext(s); s.setNext(q);6. 在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ ）。A. O(1) B. O(log2n) C. O(n) D. O(n2)7. 要将一个顺序表a0,a1,an-1中第i个数据元素ai(0in-1)删除，需要移动（ ）个数据元素。A. i B. n-i-1 C. n-i D. n-i+18. 在带头结点的双向循环链表中的p结点之后插入一个新结点s，其修改链的java语句序列是（ ）。A. p.setNext(s); s.setPrior(p); p.getNext().setPrior(s); s.setNext(p.getPrior();B. p.setNext(s); p.getNext().setPrior(s); s.setPrior(p); s.setNext(p.getNext();C. s.setPrior(p); s.setNext(p.getNext(); p.setNext(s); p.getNext().setPrior(s);D. s.setNext(p.getNext(); s.setPrior(p); p.getNext().setPrior(s); p.setNext(s);9. 顺序表的存储密度是（ ），而单链表的存储密度是（ ）。A小于1 B. 等于1 C. 大于1 D. 不能确定10. 对于图2.29所示的单链表，下列表达式值为真的是（ ）。ABCE headDP1P2图2.29 单链表head的存储结构图A. head.getNext().getData()=C B. head.getData()=BC. P1.getData()=D D. P2.getNext()=null二、填空题1. 线性表是由n（n0）个数据元素所构成的有限序列 ，其中n为数据元素的个数，称为线性表的长度 ，n=0的线性表称为空表 。2. 线性表中有且仅有一个开始结点和终端结点，除开始结点和终端结点之外，其它每一个数据元素有且仅有一个前驱 ，有且仅有一个 后继。3. 线性表通常采用顺序存储 和链式存储 两种存储结构。若线性表的长度确定或变化不大，则适合采用顺序 存储结构进行存储。4. 在顺序表a0,a1,an-1中的第i(0in-1)个位置之前插入一个新的数据元素，会引起n-i 个数据元素的移动操作。5. 在线性表的单链表存储结构中，每一个结点有两个域，一个是数据域，用于存储数据元素值本身，另一个是指针域 ，用于存储后继结点的地址。6. 在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中则只能进行顺序 存取。7. 顺序表中逻辑上相邻的数据元素，其物理位置一定 相邻，而在单链表中逻辑上相邻的数据元素，其物理位置不一定 相邻。8. 在仅设置了尾指针的循环链表中，访问第一个结点的时间复杂度是o（1） 。9. 在含有n个结点的单链表中，若要删除一个指定的结点p，则首先必须找到指针结点的前驱 ，其时间复杂度为o（n） 。10. 若将单链表中的最后一个结点的指针域值改为单链表中头结点的地址值，则这个链表就构成了循环单链表 。一、单项选择题1. 下面描述错误的是 （ ）A HTML文件由开头，标记结束。B 文档头信息包含在与之间。C 在和之间可以包含和等信息。D 文档体包含在和标记之间2. 是标题标记。 （ ） A标记 B标记 C标记 D3. 超级链接是互联网的灵魂，下面哪个是正确的链接标记 （ ）A新浪网 B新浪网 C http:/wwwsinacom Dhttp:/wwwsinacom4. 下面不属于标记中的 type 属性取值的是 （ ）Apassword Btext Csubmit Dtextarea 5. 标记中的 type 属性为 时表示单选按钮 （ ）Apassword Bsubmit Cradio Dtext 6. 在html标记中，哪个标记用于设置当前页面的标题。 （ ）A. head B. name C. title D. html7. 下列标签中没有自动换行作用的是 （ ）A. a B h1 C. p D li8. HTML语言中，表格标记符是 （ ）A B.C. D.9. CSS是 的缩写。 （ ）A. Computer Style Sheets B.Cascading Style Sheets C. Creative Style Sheets D.Colorful Style Sheets10. 能在浏览器的地址栏中看到提交数据的表单提交方式是 （ B ）Asubmit Bget Cpost Dout11. CSS 选择器通过被规则指定的标记，对文档中使用该标记的内容进行统一的 外观控制。下面那些不是 CSS 选择器。 （ ）A 标签选择器 BClass选择器 CID 选择器 D名称选择器 12. 引用外部样式表的格式是（）。ABCmystyle.cssD13. 引用外部样式表的元素应该放在（）。AHTML文档的开始的位置BHTML文档的结束的位置C在head元素中D在body元素中14. 下列哪一项是css正确的语法构成Abody:color=black Bbody;color:black Cbody color: black; Dbody:color=black(body15. 下列哪种方式是用类选择符定义样式Apcolor:red;B.onecolor:red;C#twocolor:red;Dp,h1color:red;16. 如果要在不同的网页中应用相同的样式表定义，应该（）。A直接在HTML的元素中定义样式表B在HTML的标签中定义样式表C通过一个外部样式表文件定义样式表D以上都可以17. 在网页元素内部定义样式表时使用的属性名是（）。AstyleBclassCstylesDfont18. 超级链接的功能是从一个页面链接到另一个页面，属性 用来定义具体链接到那一页。（ ） Aanchor B src Chref DAddress19. 在HTML中，表格的基本标记是 。 （ ） A table B border Ctr D td20. 在HTML中，图片的基本标记是 。 （ ） A img B image Cpicture D pic21. 当表单各项添写完毕，鼠标单击提交按钮时可以触发_事件。 （ ）A. onenter B. onsubmit C. onmouseDrag D. onmouseOver22. 下面可以作为客户端脚本语言的是 。 （ ） A. java B. c# C. PHP D. JavaScript23. JavaScript是弱类型语言，变量定义时使用下列哪个关键字。 （ ）A. define B. var C. variant D. 以上都不是24. JavaScript中函数的定义使用下列哪个关键字。 （ ）A. method B. var C. function D. 以上都不是25. JavaScript中，window的哪个方法可以弹出一个警告消息框。 （ ）A. alert B. confirm C. prompt D. write26. JavaScript中，当元素获得焦点时激发的事件是 。 （ ）A. load B. click C. mouseover D. focus习题三参考答案备注: 红色字体标明的是与书本内容有改动的内容。一、选择题9. 在栈中存取数据的原则是（ ）。A 先进先出 B. 先进后出 C. 后进后出 D. 没有限制2若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（ ）。A1234 B. 1324 C. 4321 D. 14233在链栈中，进行出栈操作时（ ）。A需要判断栈是否满 B. 需要判断栈是否为空C. 需要判断栈元素的类型 D. 无需对栈作任何差别4在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是（ ）。 Atop=0 B.top=-1 C. top=maxSize D.top=maxSize-15在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ ）。 Atop=0 B.top=-1 C. top=maxSize D.top=maxSize-16在队列中存取数据元素的原则是（ ）。A先进先出 B. 先进后出 C. 后进先出 D. 没有限制7在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是（ ）。 Afront=rear B. front!=rearC. front=rear+1 D. front=(rear+1)% maxSize 8在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是（ ）。 Afront=rear B. front!=rearC. front=rear+1 D. front=(rear+1)% maxSize9. 在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（ ）。 Arear-front B. rear-front+1C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize10.设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度为（ ）。 AO(1) BO(n) CO(log2n) DO(n2)二、填空题1. 栈是一种操作受限的特殊线性表，其特殊性体现在其插入和删除操作都限制在表尾进行。允许插入和删除操作的一端称为栈顶 ，而另一端称为栈底 。栈具有 先进后出的特点。2. 栈也有两种存储结构，一种是顺序存储 ，另一种是链式存储 ；以这两种存储结构存储的栈分别称为顺序栈 和链栈。3. 在顺序栈中，假设栈顶指针top是指向栈顶元素的下一个存储单元，则顺序栈判空的条件是 top=0 ; 栈顶元素的访问形式是stacktop-1 ;4. 在不带表头结点的链栈中，若栈顶指针top直接指向栈顶元素，则将一个新结点p入栈时修改链的两个对应语句为top.next=p ；top=p; 。5. 在不带表头结点的链栈中，若栈顶指针top直接指向栈顶元素，则栈顶元素出栈时的修改链的对应语句为top=top.next 。6.7. 队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为 对首，允许删除的一端称为队尾 。队列具有先进先出 的特点。8. 由于队列的删除和插入操作分别在队首和队尾进行，因此，在链式存储结构描述中分别需要设置两个指针分别指向对首结点 和队尾结点 ，这两个指针又分别称为队首指针和队尾指针 。8. 循环顺序队列是将顺序队列的存储区域看成是一个首尾相连的环，首尾相连的状态是通过数学上的求模 运算来实现的。9. 在循环顺序队列中，若规定当front=rear时，循环队列为空；当front=(rear+1)%maxSize时，循环队列为满，则入队操作时的队尾指针变化的相应语句是 rear=(rear+1)% maxSize ；出队操作时的队首指针变化的相应语句是 front=(front+1)%maxSize 。无论是顺序栈还是顺序队列，插入元素时必须先进行验满 判断，删除元素时必须先进行验空判断；而链栈或链队列中，插入元素无需进行栈或队列是否为满的判断，只要在删除元素时先进行验空 判断。第3章1. 指令标识通常以“”标记结束。 （ 对 ）2. JavaScript代码的执行必须要有Tomcat服务器支持。 （ 错 ）3. Servlet是服务器端技术。 （ 对 ）4. out 对象可以向客户端的浏览器输出数据，与表达式的作用基本相同。 （ 对 ）5. JSP脚本中的表达式末尾必须用分号;结束。 （ 错 ）6. 如果页面处理了exception对象，那么该页面的isErrorPage属性值为true。 （ ）二 单选题红色为正确答案1. JSP源文件的后缀名是（ ）。 Ajava Bjsp Cclass Dhtml2. 能够用来声明全局变量的是（ ）。 A B C D 3. 能够在网页源代码显示的注释是（ ）。AJSP注释 BHTML注释CJSP注释和HTML注释 DJAVA注释4. （ ）可在JSP页面出现该指令的位置处，静态插入一个文件。Apage指令标签 Bpage指令的import属性Cinclude指令标签 Dinclude动作标签5. JSP程序段的基本语法是（ ）。AVBScript语言语法 BJavaScript语言语法CJava语法语言 DC语言语法6. JSP的英文单词全称是 。 A. Java Servlet B. Java Server Pages C. JavaScript D.Java Bean7. 下列哪一种不是JSP页面的组成元素.（ D ）。AJSP标签，如指令标签 B普通的HTML标记符CJava表达式 DC语言程序8. Page 指令用于定义 JSP 文件中的全局属性，下列关于该指令用法的描述不正确的是：（D ） A. 作用于整个 JSP 页面。 B. 可以在一个页面中使用多个指令。 C. 为增强程序的可读性，建议将指令放在 JSP 文件的开头，但不是必须的。 D. 指令中的属性只能出现一次。 9. 不是 JSP 运行必须的是（D. A.操作系统 B.JavaJDK C.支持 Jsp 的 Web 服务器 D.数据库 10. 在JSP中如果要导入 java.io.* 包，应该使用page指令的 属性 。 （ ）A. language B. session C. import D. info11. 可以在以下哪个（ ）标记之间插入 Java 程序片？（A. A. B. C. D. 12. JSP 的 Page 编译指令的属性 Language 的默认值是：（A. A.Java B.C C.C D.SQL 13. 可以在以下哪个（ ）标记之间插入变量与方法声明？（B. A. B. C. D.14. 能在浏览器的地址栏中看到提交数据的表单提交方式是（ B ） A.submit B.get C.post D.out 15. 给定JSP程序源码如下： 以下（B.语句可以在下划线处插入，并且运行后输出结果是：1。 A: B: C: D:三 简答题1. 请简述JSP运行原理。2. 请简述include指令与include动作之间的区别。3. JSP中可以有哪些种注释？请写出具体格式。4. 请列出三个JSP标准动作，并说明这些动作完成的功能.第四章选择题1. 以下对象中的（ ）不是JSP的内置对象。Arequest BsessionCapplication Dbean2. 在JSP中，内置对象（ ）封装了用户提交的信息，使用该对象可以获取用户提交的信息。Asession BrequestCresponse Dout3. request对象可以使用（ ）方法获取表单中某输入框提交的信息。AgetParameter(String s) BgetValue(String s)CgetParameterNames(String s) DgetParameterValue(String s)4. JSP的内置对象中（ ）对象可对客户的请求作出动态响应，向客户端发送数据。Aresponse BrequestCapplication Dout5. 以下方法，哪个可使session无效？（ ）。Asession.removeAttribute(String key)Bsession.invalidate()Csession.setAttribute(String key)Dsession.getAttribute(String key)6. application对象能在（ ）间共享。A某个访问者所访问的当前页面B某个访问者所访问的网站的各个页面之间C该服务器上的所有的访问者的所有jsp页面D该服务器上的所有的访问者的所有jsp页面和Java程序7. request.getRemoteAddr()方法的作用是：（ ）。A获取客户提交的信息 B获取客户的IPC获取客户机的名称 D获取服务器的IP8. 下面不属于 JSP 内置对象的是（D） A）out 对象 B）respone 对象 C）application 对象 D）page 对象 9. 调用 getCreationTime（）可以获取 session 对象创建的时间，该时间的单位 是（C）。 A）秒 B）分秒 C）毫秒 D）微秒 10. 可以利用 JSP 动态改变客户端的响应，使用的语法是（A）A）response.setHeader() B）response.outHeader()C）response.writeHeader()D）response.handlerHeader()11. 页面程序片中可以使用下列哪个方法将 strNumx=request.getParamter(“ix”) JSP 得到的数据类型转换为 Double 类型（ ）A）Double.parseString(strNumx) B） Double.parseDouble(strNumx) C) Double.parseInteger(strNumx) D）Double.parseFloat(strNumx)简答题1. JSP的内置对象方法、作用。2. 运行session1.jsp，写出其运行结果！s1.jsps2.jsp 您的信息为：用户名：密码：3. 用户在reg.html中输入：用户名Tom；密码123；选择爱好为游泳、阅读，请写出程序的运行结果。reg.html user:psw:爱好：游泳音乐阅读register.jsp user:psw:hobby：%String h=request.getParameterValues(h); for(int i=0;i 习题五参考答案备注: 红色字体标明的是与书本内容有改动的内容 一、选择题1对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行（ ）遍历操作相同。B 先根 B. 中根 C. 后根 D. 层次2在哈夫曼树中，任何一个结点它的度都是（ ）。C 0或1 B. 1或2 C. 0或2 D. 0或1或23对一棵深度为h的二叉树，其结点的个数最多为（ ）。A 2h B. 2h-1 C. 2h-1 D. 2h-14一棵非空二叉树的先根遍历与中根遍历正好相同，则该二叉树满足（ ）A 所有结点无左孩子 B. 所有结点无右孩子 C. 只有一个根结点 D. 任意一棵二叉树5一棵非空二叉树的先根遍历与中根遍历正好相反，则该二叉树满足（ ）B 所有结点无左孩子 B. 所有结点无右孩子 C. 只有一个根结点 D. 任意一棵二叉树6假设一棵二叉树中度为1的结点个数为5，度为2的结点个数为3，则这棵二叉树的叶结点的个数是（ ）A2 B. 3 C. 4 D. 57若某棵二叉树的先根遍历序列为ABCDEF，中根遍历序列为CBDAEF，则这棵二叉树的后根遍历序列为（ ）。AFEDCBA B. CDBFEA C. CDBEFA D. DCBEFA8若某棵二叉树的后根遍历序列为DBEFCA，中根遍历序列为DBAECF，则这棵二叉树的先根遍历序列为（ ）。AABCDEF B. ABDCEF C. ABCDFE D. ABDECF9根据以权值为2，5，7，9，12构造的哈夫曼树所构造的哈夫曼编码中最大的长度为（ ）A2 B. 3 C. 4 D. 510在有n个结点的二叉树的二叉链表存储结构中有（ ）个空的指针域。An-1 B. n C. n+1 D. 0二、填空题1. 在一棵度为m的树中，若度为1的结点有n1个，度为2的结点有n2个，度为m的结点有nm个，则这棵树中的叶结点的个数为 。2. 一棵具有n个结点的二叉树，其深度最多为 ，最少为 。3. 一棵具有100个结点的完全二叉树，其叶结点的个数为 。4. 以5，9，12，13，20，30为叶结点的权值所构造的哈夫曼树的带权路径长度是 。5. 有m个叶结点的哈夫曼树中，结点的总数是 。6. 若一棵完全二叉树的第4层(根结点在第0层)有7个结点，则这棵完全二叉树的结点总数是 。7. 在深度为k的完全二叉树中至少有个结点，至多有 个结点。8. 对一棵树转换成的二叉树进行先根遍历所得的遍历序列为ABCDEFGH,则对这棵树进行先根遍历所得的遍历序列为 。9. 二叉树常用的存储结构是 ，树常用的存储结构是 。10. 对森林进行后根遍历操作等同于从左到右对森林中的每一棵树进行 遍历操作，并且对森林的后根遍历序列与对森林所对应的二叉树的 遍历序列相同。习题七 参考答案一、选择题1内部排序算法的稳定性是指( D )。A该排序算法不允许有相同的关键字记录B该排序算法允许有相同的关键字记录C平均时间为0（n log n）的排序方法D以上都不对2下面给出的四种排序算法中，( B )是不稳定的排序。 A插入排序 B堆排序 C二路归并排序 D冒泡排序3. 在下列排序算法中，哪一种算法的时间复杂度与初始排序序列无关（ D ）。 A直接插入排序 B冒泡排序 C快速排序 D直接选择排序4关键字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( C )的两趟排序后的结果。A选择排序 B.冒泡排序 C.插入排序 D.堆排序5下列排序方法中，( D )所需的辅助空间最大。A选择排序 B希尔排序 C快速排序 D归并排序6一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为支点得到的一次划分结果为（ C ）。 A(38,40,46,56,79,84) B(40,38,46,79,56,84)C(40,38,46,56,79,84) D(40,38,46,84,