电大数据结构本期末复习指导.docx

《电大数据结构本期末复习指导.docx》由会员分享，可在线阅读，更多相关《电大数据结构本期末复习指导.docx（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 中央播送电视高校数据构造（本）期末复习指导第一局部 课程考核说明一、考核说明数据构造（本）是中央播送电视高校计算机科学与技术（本科）专业的一门统设必修、学位课程。4学分，72学时，其中试验24学时，开设一学期。课程主要内容包括：数据构造与算法的根本概念、线性表、栈与队列、串、数组与广义表、树与图、查找与排序等。目的是使学生通过该课程的学习，深化地理解数据的逻辑构造与物理构造以与有关算法，驾驭根本的程序设计技能，学会编制高效牢靠的程序，为学习后续课程奠定根底。现将有关考核的几个问题说明如下：1考核对象2007年秋季起入学的计算机科学与技术专业（本科）学生。2考核根据以数据构造（本）课程教学大纲

2、为根据编制，考核说明是本课程形成性考核与终结性考试命题的根本根据。3考核方式承受形成性考核与终结性考试相结合的方式。4课程总成果的记分方法课程总成果按百分制记分，其中形成性考核所占的比例为30%，终结性考试占70。60分为合格，可以获得课程学分。本课程的学位课程学分为70分，即课程总成果到达70分与以上者有资格申请专业学位。5形成性考核的要求、形式与手段形成性考核主要考核学生形成性作业与试验的完成状况，占课程总成果的30%。形成性考核以作业册的形式下发，由各地电大根据学生作业与试验的完成状况进展考核。中央电大将不定期随机抽检各地电高校生的形成性作业与课程试验报告。6终结性考试的要求与方式（1）

3、 考试要求考核要求分为理解、理解与驾驭三个层次：理解：是指（1）学习本课程主干学问点所须要的概念、方法、预备学问与相关内容。（2）就大局部学生目前的学问构造与根底理解与驾驭有确定困难，有待今后进一步学习的内容。（3）在主干学问点根底上拓展的内容。这局部不属考核的主要内容。理解：是指要求学生精确全面领悟的概念、方法与思路等。相关内容是本课程的主干学问点，要求学生能融汇贯穿，并能利用所学学问分析解决相关问题。这局部是考核的主要范围。驾驭：是指本课程最重要的学问点，能充分表达本课程的教学要求，要求学生在理解所学学问的根底上能灵敏应用。能结合课程的不同学问点解决综合性的问题与简洁应用问题。这局部是考核

4、的重点内容。（2） 考核方式中央电大统一命题，闭卷考试。（3）组卷原则在考核说明所规定的内容与要求之内命题。在教学内容范围之内，根据理论联络实际原则，考察学生对所学学问应用实力的试题，不属于超纲。试题的难易程度与题量适当，按难易程度分为易、中、难三个层次：易占25%，中占45%，难占30%。题量支配以大多数考生能在规定的考试时间内做完并有确定时间检查为原则。（4）试题类型与试卷构造试题题型有单项选择题、填空题、综合题与程序填空题四种题型。试卷构造如下：单项选择题：每小题2分，共30分填空题： 每小题2分，共24分综合题： 每小题10分，共30分程序填空题：每空2分，共16分共100分 （5）答

5、题时限答题时限为90分钟。二、考核内容与要求 第1章 绪论（2学时）考核学问点1数据构造的根本概念2算法与算法分析的根本概念考核要求1理解数据构造的根本概念2驾驭逻辑构造、物理构造的概念与互相关系3驾驭本书介绍的四种根本构造的特点4理解算法与其特性5理解算法分析的一般概念第2章 线性表（8学时）考核学问点1线性表的定义、逻辑构造、依次存储构造、链式存储构造2线性表在依次构造与链式构造上的根本操作与应用 3双向链表、循环链表的原理与相关操作考核要求1理解线性表的定义与两种存储构造2理解线性表依次存储的特点、实现方法与应用。3驾驭依次表的根本操作（包括建立链表、遍历链表、删除、插入、查找）与应用。

6、特殊要求可以利用链表的操作与相关的程序设计技术编制有确定难度的程序。4理解双向链表、循环链表的原理与相关操作。第3章 栈与队列（6学时）考核学问点1栈的定义、栈的存储构造（依次存储、链式存储）与根本操作、栈的应用2队列的定义、队列的存储构造（依次存储、链式存储）、队列的应用3循环队列的概念与实现方法考核要求1驾驭栈与队列的操作特点2理解依次栈、依次队列的根本操作3理解在实际编程中栈与队列的不同应用。理解循环队列的概念、实现方法。驾驭循环队列判空、判满的条件4能根据后续章节（例如二叉树、排序等）的要求利用递归程序设计技术实现相关算法第4章 串（2学时）考核学问点1串类型定义、C语言中字符串的特点

7、与处理方法2串的依次存储构造与链式存储构造3串的根本运算与实现方法考核要求1理解串的定义与存储方法2理解串的根本操作与相关算法3驾驭用C语言处理字符串的语法规则第5章 数组与广义表（2学时）考核学问点1数组的定义与存储构造2特殊矩阵与稀疏矩阵的存储构造3广义表的定义与存储构造考核要求1理解数组的存储构造。2驾驭特殊矩阵进展压缩存储的下标转换公式。3理解稀疏矩阵的压缩存储原理。4驾驭利用三元组表示稀疏矩阵的方法。5理解广义表的概念与存储构造。第6章 树与二叉树（10学时）考核学问点1树的根本概念2二叉树的性质与存储构造3二叉树的遍历与线索二叉树4哈夫曼树与其应用考核要求1理解树与二叉树的定义2驾

8、驭二叉树的根本性质，能利用相关性质解决简洁计算问题3理解二叉树的依次存储构造4驾驭二叉树的链式存储构造、相关操作5驾驭二叉树的有关算法并能编程实现6驾驭利用遍历序历构造二叉树的规则与详细步骤7驾驭哈夫曼树的定义、性质与构造方法8理解哈夫曼树的应用第7章 图（6学时）考核学问点1图的根本概念2图的存储构造3图的遍历4最小生成树与最短途径。考核要求1理解图的根本概念2驾驭图的存储方法（邻接矩阵、邻接表）3驾驭图的深度优先与广度优先遍历的规则与步骤4理解在连通图中求最小生成树的方法。理解求图的最短途径等相关算法与其应用第8章 查找（6学时）考核学问点1线性表的查找（依次查找、折半查找、分块查找）。2

9、二叉排序树的查找。3哈希表（哈希表的定义、哈希函数的构造、处理冲突的方法、哈希表的查找与分析）。考核要求1理解查找的相关概念。2驾驭依次表的查找方法、步骤、程序实现、时间困难度与平均查找长度。3驾驭在有序的依次表上进展折半查找的方法、步骤、程序实现。4驾驭折半查找的断定树的构造方法。能利用断定树求平均查找长度。5驾驭二叉排序树的精确定义，驾驭建立二叉排序树的步骤与方法。理解在二叉排序树中进展输入、删除操作的规则。6理解哈希表的相关概念与原理，理解常用哈希函数的构造与处理冲突的方法。理解哈希函数与哈希表的关系与在查找中的应用。第9章 排序（6学时）考核学问点1插入排序（干脆插入排序、希尔排序）2

10、交换排序（冒泡排序、快速排序）3选择排序（简洁选择排序、堆排序）4归并排序考核要求1驾驭教材中介绍的各种排序算法的根本原理、步骤。2能针对小规模详细实例，按相关排序算法的规则人工完成排序；能通过分析排序的中间结果推断所用的排序算法。3能正确理解相关排序算法的程序实例，并重点驾驭算法中的关键步骤与关键语句。4驾驭堆与特殊的完全二叉树的对应关系。驾驭建堆、选择算法与完全二叉树相关操作的对应关系。三、试题类型与答案一、单项选择题（每小题2分，共30分）1.数据构造中，与所运用的计算机无关的是数据的（ ）构造。A. 逻辑 B. 物理 C. 存储 D. 逻辑与物理2.下述各类表中可以随机访问的是（ ）。

11、A. 单向链表 B. 双向链表 C.单向循环链表 D.依次表3.在一个长度为n的依次表中为了删除第5个元素，从前到后依次挪动了15个元素。则原依次表的长度为（ ）。A. 21 B. 20 C. 19 D. 254.元素2，4，6按依次依次进栈，则该栈的不行能的输出序列是（ ）。A. 6 4 2 B. 6 2 4 C. 4 2 6 D. 2 6 45.一个队列的入队序列是5，6，7，8，则队列的输出序列是（ ）。A. 5 6 7 8 B. 8 7 6 5 C. 7 8 6 5 D.可能有多种状况6. 串函数StrCmp（“d”，“D”）的值为（ ）。 A0 B1 C-1 D37在一个单链表中，p

12、、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的干脆后继，现要删除q所指结点，可用语句（ ）。 Ap=q-next Bp-next=q Cp-next=q-next Dq-next=NULL 8.设一棵哈夫曼树共有n个非叶结点，则该树一共有（ ）个结点。A. 2*n-1 B. 2*n +1 C. 2*n D. 2*(n-1)9.对如图1所示二叉树进展中序遍历，结果是（ ）。A. dfebagc B. defbagc C. defbacg D.dbaefcg图1cbcdefga10 . 任何一个无向连通图的最小生成树（ ）。A.至少有一棵 B.只有一棵 C.确定有多棵 D.可能不存在1

13、1设有一个10阶的对称矩阵A，承受压缩存储的方式，将其下三角局部以行序为主序存储到一维数组B中（数组下标从1开场），则矩阵中元素A8,5在一维数组B中的下标是（ ）。A33 B32 C85 D4112 . 一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ ）。 A31，29，37，85，47，70 B29，31，37，47，70，85C31，29，37，70，47，85 D31，29，37，47，70，8513 . 对n个元素进展冒泡排序，要求按升序排列，程序中设定某一趟冒泡没有出现元素交换，就完毕排序过程。对某n个元

14、素的排序共进展了3n-6次元素间的比拟就完成了排序，则（ ）。A.原序列是升序排列B.原序列是降序排列C.对序列只进展了2趟冒泡D. 对序列只进展了3趟冒泡14在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行（ ）。A.x=top-data;top=top-next; B. top=top-next ; x=top;C.x=top;top=top-next ; D. x=top-data;15串函数StrCat（a,b）的功能是进展串（ ）。 A比拟 B复制 C赋值 D连接二、填空题（每小题2分，共24分）1在一个单向链表中p所指结点之后插入一个s所指的新结点，应执行

15、s-next=p-next；与_操作。2根据数据元素间关系的不同特性，通常可分为_、 、 、 四类根本构造。3在一个链队中，设f与r分别为队头与队尾指针，则删除一个结点的操作为_。 (结点的指针域为next)4._遍历二叉排序树可得到一个有序序列。5.一棵有2n-1个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有_个叶结点。6.如图1所示的二叉树，其中序遍历序列为_ _。efgibachd 图17.对稀疏矩阵进展压缩存储，矩阵中每个非零元素所对应的三元组包括该元素的_、_与_三项信息。8 . 有一个有序表2,3,9,13,33,42,45,63,74,77,82,95,110,用折半查

16、找法查找值为82的结点，经_次比拟后查找胜利。9 .图的深度优先搜寻与广度优先搜寻序列不是唯一的。此断言是_的。(答复正确或不正确) 10哈希法既是一种存储方法，又是一种 。1144.在对一组记录(55,39,97,22,16,73,65,47,88)进展干脆插入排序时，当把第7个记录65插入到有序表时，为找寻插入位置需比拟_次。12栈与队列的操作特点分别是_与 _。三、综合题（每小题10分，共30分）1已知序列11，19，5，4，7，13，2，10 ，（1）试给出用归并排序法对该序列作升序排序时的每一趟的结果。（2）对上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉树描绘建堆过程）。2设

17、有序表为（13，19，25，36，48，51，63，84，91，116，135，200），元素的下标依次为1,2,12. （1）说出有哪几个元素须要经过3次元素间的比拟才能胜利查到（2）画出对上述有序表进展折半查找所对应的断定树（树结点用下标表示）（3）设查找元素5，须要进展多少次元素间的比拟才能确定不能查到.3 (1) 设有查找表5,14,2,6,18,7,4,16,3,依次取表中数据，构造一棵二叉排序树.（2）说明如何通过序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果.四、程序填空题（每空2分，共16分）1以下冒泡法程序对存放在a1，a2，an中的序列进展冒泡排序

18、，完成程序中的空格局部，其中n是元素个数，程序按升序排列。Void bsort (NODE a , int) NODE temp; int i,j,flag; for(j=1; （1） ;j+); flag=0; for(i=1; （2） ;i+) if(ai.keyai+1.key)flag=1; temp=ai; （3） ; （4） ;if(flag= =0)break;程序中flag的功能是（5） 7以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格局部（树构造中左、右指针域分别为left与right，数据域为data，其数据类型为字符型，BT指向根结点）。Void Postord

19、er (struct BTree Node *BT) if(BT!=NULL) （1） ; （2） ; （3） ;试题答案；一、单项选择题（每小题2分，共30分）1A 2D 3B 4B 5A 6C 7C 8B 9A 10A 11A 12D 13D 14A 15D二、填空题（每小题2分，共24分）1.p-next=s; 2.集合、线性、树形、图状 3. f=f-next;4.中序5.n6. dgbaechhif 7.行号、列号、元素值8.4次9.正确10查找方法113次12先进后出 先进先出三、综合题（每小题10分，共30分）1(1) 初始 11，19，5，4，7，13，2，10第一趟 11，1

20、94，57，132，10第二趟 4，5，11，192，7，10，13 第三趟 2，4，5，7，10，11，13，19135101119724(2)2101151974137131013191125419247105112 (1)13,36,63,135471285211110639(2) (3)3次53(1)14218647163(2)中序遍历中序 2，3，4，5，6，7，14，16，18四、程序填空题（每空2分，共16分）1（1）j=n-1（2）inext= =head Dhead-next= =NULL3链表所具备的特点是（ ）。A可以随机访问任一结点 B占用连续的存储空间C插入删除元素的

21、操作不须要挪动元素结点 D可以通过下标对链表进展干脆访问4非空的单向循环链表的尾结点满意（ ）（设头指针为head，指针p指向尾结点）。 Ap-next = =NULL Bp= =NULL Cp= =head Dp-next= =head 5数据构造中，与所运用的计算机无关的是数据的（ ）构造。 A物理 B逻辑 C存储 D逻辑与物理 6算法的时间困难度与（ ）有关。 A所运用的计算机 B计算机的操作系统 C算法本身 D数据构造7设有一个长度为n的依次表，要在第i个元素之前插入一个元素（也就是插入元素作为新表的第i个元素），则挪动元素个数为（ ）。 An-i+1 Bn-i Cn-i-1 Di8设

22、有一个长度为n的依次表，要删除第i个元素需挪动元素的个数为（ ）。 An-i+1 Bn-i Cn-i-1 Di9在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的干脆后继，现要删除q所指结点，可用的语句是（ ）。 Ap=q-next Bp-next=q Cq-next=NULL Dp-next=q-next10在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（ ）。 Ap=snext Bpnext=snext; Csnext=pnext; pnext=s; Dpnext= s; snext= pnext11从一个栈顶指针为top的链栈中删除一个结点时，用变量

23、x保存被删结点的植，则执行（ ）。 Ax=top-data; top=topnext; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data;12在一个链队中，假设f与r分别为队头与队尾指针，则删除一个结点的运算为（ ）。 Ar=fnext; Br=rnext; Cf=fnext; Df=rnext;13在一个链队中，假设f与r分别为队头与队尾指针，则插入s所指结点的运算为（ ）。 Af-next=s; f=s; Bs-next=r;r=s; Cr-next=s;r=s; Ds-next=f;f=s;14元素1，3，5，7按

24、依次依次进栈，则该栈的不行能输出序列是（ ）（进栈出栈可以交替进展）。 A7，5，3，1 B7，5，1，3C3，1，7，5 D1，3，5，7 15设有一个18阶的对称矩阵A，承受压缩存储的方式，将其下三角局部以行序为主序存储到一维数组B中（数组下标从1开场），则矩阵中元素a10,8在一维数组B中的下标是（ ）。A18 B45 C53 D58 16在C语言中，依次存储长度为3的字符串，须要占用（ ）个字节。 A4 B3 C6 D1217一棵有n个结点承受链式存储的二叉树中，共有（ ）个指针域为空。 An Bn+1 Cn-1 Dn-218在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的依次编

25、号为（ ）。 A2i B2i-1 C2i+1 D2i+219设一棵哈夫曼树共有n个叶结点，则该树有（ ）个非叶结点。 An B2n Cn-1 Dn+1 20一棵具有35个结点的完全二叉树，最终一层有（ ）个结点。 A4 B6 C16 D821一棵完全二叉树共有5层，且第5层上有六个结点，该树共有（ ）个结点。 A30 B20 C21 D2322在一个无向图中，全部顶点的度数之与等于边数的（ ）倍。 A3 B2 C2.5 D1.5 23已知如图1所示的一个图，若从顶点a动身，按深度优先搜寻法进展遍历，则可能得到的一种顶点序列为（ ）。 Aabecdf Bacfebd Caedfcb Daebcf

26、d bdfeca 图124已知如图3所示的一个图，若从顶点V1动身，按广度优先法进展遍历，则可能得到的一种顶点序列为（ ）。 AV1V2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7CV1V2V4V8V3V5V6V7 DV1V3V6V7V2V4V5V8V6V7V1V2V3V8V4V5 图325在有序表1，3，8，13，33，42，46，63，76，78，86，97，100中，用折半查找值86时，经（ ）次比拟后查找胜利。A3 B4 C6 D8 26对二叉排序树进展（ ）遍历，可以使遍历所得到的序列是有序序列。 A按层次 B后序 C中序 D前序27有一个长度为12的有序表，按折半查

27、找对该表进展查找，在等概率状况下查找胜利的平均比拟次数为（ ）。A37/12 B39/12 C41/12 D35/1228设已有m个元素有序，在未排好序的序列中选择第m+1个元素，并且只经过一次元素的交换就使第m+1个元素排序到位，该方法是（ ）。 A折半排序 B冒泡排序 C归并排序 D简洁选择排序29一组记录的关键字序列为（46，79，56，38，40，84），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ ）。 A40，38，46，79，56，84 B40，38，46，84，56，79 C40，38，46，56，79，84 D38，40，46，56，79，8430一组记录的

28、关键字序列为（47，80，57，39，41，46），利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（ ）。 A39，47，46，80，41，57 B39，41，46，80，47，57C41，39，46，47，57，80 D39，80，46，47，41，57二填空题1把数据存储到计算机中,并详细表达数据之间的逻辑构造称为_ _构造。2算法的5个特征为_。3构造中的数据元素存在 的关系称为树形构造。4要求在n个数据元素中找其中值最大的元素，设根本操作为元素间的比拟。则比拟的次数与算法的时间困难度分别为_与 _ 。5求两个n阶矩阵的乘积，算法的根本操作与时间困难度分别为_与_ _。6在一个单向

29、链表中p所指结点之后插入一个s所指向的结点时，应执行s-next=p-next;与 的操作。7设有一个头指针为head的单向循环链表，p指向链表中的结点，若p-next= = head，则p所指结点为 。8在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用操作_。9设有一个头指针为head的单向链表，p指向表中某一个结点，且有p-next= =NULL,通过操作_,就可使该单向链表构造成单向循环链表。10向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s-next=h; 与 操作。(结点的指针域为next)11从一个栈顶指针为h的链栈中删除一个结点时，用x保存被

30、删结点的值，可执行 与h=h-next; (结点的指针域为next) 。12在一个链队中，设f与r分别为队头与队尾指针，则插入s所指结点的操作为r-next=s;与 (结点的指针域为next)。13在一个链队中，设f与r分别为队头与队尾指针，则删除一个结点的操作为_。 (结点的指针域为next)14.两个串相等的充分必要条件是_ _。15对稀疏矩阵进展压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_、_与_三项信息。16在二叉树的链式存储构造中，通常每个结点中设置三个域，它们是_、 、17一棵有2n-1个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有_个叶结点。18一棵二叉树中有

31、2n-2条边（结点间的连线），其中每一个非叶结点的度数都为2，则该树共有_个非叶结点。19中序遍历二叉排序树可得到一个 。20如图1所示的二叉树，其中序遍历序列为_ _。gfabdecefgibachd图1图221如图1所示的二叉树，其先序遍历序列为_。22如图1所示的二叉树，其后序遍历序列为_。23如图2所示的二叉树，其前序遍历序列为_。24哈希函数是记录关键字值与该记录存储地址之间所构造的对应关系。25图的深度优先搜寻与广度优先搜寻序列不愿定是唯一的。此断言是_的。(答复正确或不正确) 26n个元素进展冒泡法排序，通常须要进展_趟冒泡，第j趟冒泡要进展_次元素间的比拟。三、综合题1设一组记

32、录的关键字序列为（49，83，59，41，43，47），承受堆排序算法完成以下操作：（要求小根堆，并画出中间过程）（1）以二叉树描绘6个元素的初始堆（2）以二叉树描绘逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆2已知序列11，19，5，4，7，13，2，10 （1）试给出用归并排序法对该序列作升序排序时的每一趟的结果。（2）对上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉树描绘建堆过程）。3一组记录的关键字序列为（46，79，56，38，40，84）（1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要求以升序排列）（2）对上述序列用堆排

33、序的方法建立大根堆，要求以二叉树逐次描绘建堆过程。4设查找表为(7,15,21,22,40,58,68,80,88,89,120) ,元素的下标依次为1,2,3,，11. （1）画出对上述查找表进展折半查找所对应的断定树（树中结点用下标表示）（2）说明胜利查找到元素40须要经过多少次比拟？（3）求在等概率条件下，胜利查找的平均比拟次数？5设查找表为(16,15,20,53,64,7), (1)用冒泡法对该表进展排序（要求升序排列），要求写出每一趟的排序过程，通常对n个元素进展冒泡排序要进展多少趟冒泡？第j趟要进展多少次元素间的比拟？ (2)在排序后的有序表的根底上，画出对其进展折半查找所对应的

34、断定树.(要求以数据元素作为树结点)(3)求在等概率条件下,对上述有序表胜利查找的平均查找长度.6（1）假设二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树为二叉排序树，这种说法是否正确？若认为正确，则答复正确，若认为不正确，则举例说明。 （2）设有数据集合40，29，7，73，101，4，55，2，81，92，39，依次取集合中各数据，构造一棵二叉排序树.7 (1) 设有查找表5,14,2,6,18,7,4,16,3,依次取表中数据，构造一棵二叉排序树.（2）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果.8(1)“一棵二叉树若它的根结点的

35、值大于左子树全部结点的值，小于右子树全部结点的值，则该树确定是二叉排序树”。该说法是否正确，若认为正确，则答复正确，若认为不正确则说明理由？(2)设有查找表7，16，4，8，20，9，6，18，5，依次取表中数据构造一棵二叉排序树. 对上述二叉树给出后序遍历的结果.9 (1)以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树，给出相应权重值叶结点的哈夫曼编码。(2) 一棵哈夫曼树有n个叶结点，它一共有多少个结点？简述理由？10（1）对给定权值2，1，3，3，4，5，构造哈夫曼树。（2）同样用上述权值构造另一棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两棵树的带权途径长度。giabce

36、hfd11如图所示的二叉树 （1）给出中序遍历序列 （2）给出先序遍历序列 （3）给出后序遍历序列四、程序填空题1以下冒泡法程序对存放在a1，a2，an中的序列进展冒泡排序完成程序中的空格局部，其中n是元素个数，要求按升序排列。void bsort (NODE a , int n) NODE temp; int i,j,flag; for(j=1; ;j+); flag=0; for(i=1; ;i+) if(ai.keyai+1.key)flag=1; temp=ai;if(flag= =0)break;程序中flag的功能是 2以下是用尾插法建立带头结点且有n个结点的单向链表的程序，结点中

37、的数据域从前向后依次为1,2,3,n，完成程序中空格局部。NODE *create(n)NODE *head , *p, *q; int i; p=(NODE*)malloc(sizeof(NODE);head= ; ;pnext=NULL; /*建立头结点*/for(i=1; idata=i; p-next=NULL; q-next= ;return(head);3以下是用头插法建立带头结点且有n个结点的单向链表的程序，要求结点中的数据域从前向后依次为n,n-1,1，完成程序中空格局部。NODE *create2(n)NODE *head , *p, *q; int i; p=(NODE*)malloc(sizeof(NODE);p-next=NULL;head= ;for(i=1