电大数据结构(本)期末复习指导1018

《电大数据结构(本)期末复习指导1018》由会员分享，可在线阅读，更多相关《电大数据结构(本)期末复习指导1018（25页珍藏版）》请在金锄头文库上搜索。

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

2、据 以数据结构（本）课程教学大纲为依据编制，考核说明是本课程形成性考核和终结性考试命题的基本依据。 3考核方式 采用形成性考核和终结性考试相结合的方式。 4课程总成绩的记分方法 课程总成绩按百分制记分，其中形成性考核所占的比例为 30%，终结性考试占 70。60 分为合格，可以获得课程学分。本课程的学位课程学分为 70 分，即课程总成绩达到 70分及以上者有资格申请专业学位。 5形成性考核的要求、形式及手段 形成性考核主要考核学生形成性作业和实验的完成情况，占课程总成绩的 30%。形成性考核以作业册的形式下发， 由各地电大根据学生作业和实验的完成情况进行考核。 中央电大将不定期随机抽检各地电大

3、学生的形成性作业及课程实验报告。 6终结性考试的要求及方式 （1） 考试要求 考核要求分为了解、理解和掌握三个层次： 了解：是指（1）学习本课程主干知识点所需要的概念、方法、预备知识和相关内容。（2）就大部分学生目前的知识结构和基础理解和掌握有一定困难，有待今后进一步学习的内容。 （3）在主干知识点基础上拓展的内容。这部分不属考核的主要内容。 理解：是指要求学生准确全面领会的概念、方法和思路等。相关内容是本课程的主干知识点，要求学生能融汇贯通，并能利用所学知识分析解决相关问题。这部分是考核的主要范围。 2 掌握：是指本课程最重要的知识点，能充分体现本课程的教学要求，要求学生在理解所学知识的基础

4、上能灵活应用。能结合课程的不同知识点解决综合性的问题和简单应用问题。这部分是考核的重点内容。 （2） 考核方式 中央电大统一命题，闭卷考试。 （3）组卷原则 在考核说明所规定的内容和要求之内命题。 在教学内容范围之内， 按照理论联系实际原则，考察学生对所学知识应用能力的试题，不属于超纲。 试题的难易程度和题量适当，按难易程度分为易、中、难三个层次：易占 25%，中占45%，难占 30%。题量安排以大多数考生能在规定的考试时间内做完并有一定时间检查为原则。 （4）试题类型及试卷结构 试题题型有单项选择题、填空题、综合题和程序填空题四种题型。试卷结构如下： 单项选择题：每小题 2 分，共 30 分

5、 填空题： 每小题 2 分，共 24 分 综合题： 每小题 10 分，共 30 分 程序填空题：每空 2 分，共 16 分 共 100 分 （5）答题时限 答题时限为 90 分钟。 二、考核内容和要求 第 1 章 绪论（2 学时） 考核知识点 1数据结构的基本概念 2算法和算法分析的基本概念 考核要求 1理解数据结构的基本概念 2掌握逻辑结构、物理结构的概念及相互关系 3掌握本书介绍的四种基本结构的特点 4理解算法及其特性 5了解算法分析的一般概念 第 2 章 线性表（8 学时） 考核知识点 1线性表的定义、逻辑结构、顺序存储结构、链式存储结构 2线性表在顺序结构和链式结构上的基本操作和应用

6、3双向链表、循环链表的原理和相关操作 考核要求 1理解线性表的定义及两种存储结构 2理解线性表顺序存储的特点、实现方法和应用。 3掌握顺序表的基本操作（包括建立链表、遍历链表、删除、插入、查找）和应用。特别要求能够利用链表的操作和相关的程序设计技术编制有一定难度的程序。 4了解双向链表、循环链表的原理和相关操作。 第 3 章 栈和队列（6 学时） 3 考核知识点 1栈的定义、栈的存储结构（顺序存储、链式存储）和基本操作、栈的应用 2队列的定义、队列的存储结构（顺序存储、链式存储） 、队列的应用 3循环队列的概念和实现方法 考核要求 1掌握栈和队列的操作特点 2理解顺序栈、顺序队列的基本操作 3

7、了解在实际编程中栈和队列的不同应用。理解循环队列的概念、实现方法。掌握循环队列判空、判满的条件 4能按照后续章节（例如二叉树、排序等）的要求利用递归程序设计技术实现相关算法 第 4 章 串（2 学时） 考核知识点 1串类型定义、C 语言中字符串的特点和处理方法 2串的顺序存储结构和链式存储结构 3串的基本运算和实现方法 考核要求 1理解串的定义和存储方法 2了解串的基本操作和相关算法 3掌握用 C 语言处理字符串的语法规则 第 5 章 数组和广义表（2 学时） 考核知识点 1数组的定义和存储结构 2特殊矩阵和稀疏矩阵的存储结构 3广义表的定义和存储结构 考核要求 1了解数组的存储结构。 2掌握

8、特殊矩阵进行压缩存储的下标转换公式。 3理解稀疏矩阵的压缩存储原理。 4掌握利用三元组表示稀疏矩阵的方法。 5了解广义表的概念和存储结构。 第 6 章 树和二叉树（10 学时） 考核知识点 1树的基本概念 2二叉树的性质和存储结构 3二叉树的遍历和线索二叉树 4哈夫曼树及其应用 考核要求 1了解树和二叉树的定义 2掌握二叉树的基本性质，能利用相关性质解决简单计算问题 3了解二叉树的顺序存储结构 4掌握二叉树的链式存储结构、相关操作 5掌握二叉树的有关算法并能编程实现 6掌握利用遍历序历构造二叉树的规则和具体步骤 4 7掌握哈夫曼树的定义、性质和构造方法 8了解哈夫曼树的应用 第 7 章 图（6

9、 学时） 考核知识点 1图的基本概念 2图的存储结构 3图的遍历 4最小生成树和最短路径。 考核要求 1了解图的基本概念 2掌握图的存储方法（邻接矩阵、邻接表） 3掌握图的深度优先和广度优先遍历的规则和步骤 4理解在连通图中求最小生成树的方法。了解求图的最短路径等相关算法及其应用 第 8 章 查找（6 学时） 考核知识点 1线性表的查找（顺序查找、折半查找、分块查找） 。 2二叉排序树的查找。 3哈希表（哈希表的定义、哈希函数的构造、处理冲突的方法、哈希表的查找和分析） 。 考核要求 1了解查找的相关概念。 2掌握顺序表的查找方法、步骤、程序实现、时间复杂度和平均查找长度。 3掌握在有序的顺序

10、表上进行折半查找的方法、步骤、程序实现。 4掌握折半查找的判定树的构造方法。能利用判定树求平均查找长度。 5掌握二叉排序树的确切定义，掌握建立二叉排序树的步骤和方法。理解在二叉排序树中进行输入、删除操作的规则。 6了解哈希表的相关概念和原理，了解常用哈希函数的构造和处理冲突的方法。理解哈希函数和哈希表的关系及在查找中的应用。 第 9 章 排序（6 学时） 考核知识点 1插入排序（直接插入排序、希尔排序） 2交换排序（冒泡排序、快速排序） 3选择排序（简单选择排序、堆排序） 4归并排序 考核要求 1掌握教材中介绍的各种排序算法的基本原理、步骤。 2能针对小规模具体实例，按相关排序算法的规则人工完

11、成排序；能通过分析排序的中间结果判断所用的排序算法。 3能正确理解相关排序算法的程序实例，并重点掌握算法中的关键步骤和关键语句。 4掌握堆和特殊的完全二叉树的对应关系。掌握建堆、筛选算法和完全二叉树相关操作的对应关系。 三、试题类型及答案 一、单项选择题（每小题 2 分，共 30 分） 1.数据结构中，与所使用的计算机无关的是数据的（ ）结构。 5 A. 逻辑 B. 物理 C. 存储 D. 逻辑与物理 2.下述各类表中可以随机访问的是（ ） 。 A. 单向链表 B. 双向链表 C.单向循环链表 D.顺序表 3.在一个长度为 n 的顺序表中为了删除第 5 个元素，从前到后依次移动了 15 个元素

12、。则原顺序表的长度为（ ） 。 A. 21 B. 20 C. 19 D. 25 4.元素 2 ，4 ，6 按顺序依次进栈，则该栈的不可能的输出序列是（ ） 。 A. 6 4 2 B. 6 2 4 C. 4 2 6 D. 2 6 4 5.一个队列的入队序列是 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 D3 7在一个单链表中，p、q 分别指向表中两个相邻的结点，且 q 所指结点是 p 所指结点的直接后继，现要

13、删除 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 10 . 任何一个无向连通图的最小生成树（ ） 。 A.至少有一棵 B.只有一棵 C.一定有多棵 D.可能不存在 11设有一个 10 阶的对称矩阵 A，采用压缩存储的方式，将其下

14、三角部分以行序为主序存储到一维数组 B 中（数组下标从 1 开始） ，则矩阵中元素 A8,5在一维数组 B 中的下标是（ ） 。 A33 B32 C85 D41 12 . 一组记录的关键字序列为（37，70，47，29，31，85） ，利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ ） 。 A31，29，37，85，47，70 B29，31，37，47，70，85 C31，29，37，70，47，85 D31，29，37，47，70，85 13 . 对 n个元素进行冒泡排序，要求按升序排列，程序中设定某一趟冒泡没有出现元素交换，就结束排序过程。对某 n 个元素的排序共进行了 3

15、n-6次元素间的比较就完成了排序，则（ ） 。 A.原序列是升序排列 图 1 c b c d e f g a 6 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 分，共

16、 24 分） 1 在一个单向链表中 p所指结点之后插入一个 s所指的新结点，应执行s-next=p-next；和_操作。 2 根据数据元素间关系的不同特性， 通常可分为_、 、 、 四类基本结构。 3 在一个链队中， 设 f 和 r 分别为队头和队尾指针， 则删除一个结点的操作为_。 (结点的指针域为 next) 4._遍历二叉排序树可得到一个有序序列。 5.一棵有 2n-1 个结点的二叉树，其每一个非叶结点的度数都为 2，则该树共有_个叶结点。 6.如图 1 所示的二叉树，其中序遍历序列为_ _。 图 1 7.对稀疏矩阵进行压缩存储，矩阵中每个非零元素所对应的三元组包括该元素的_、_和_三项

17、信息。 8 . 有一个有序表2,3,9,13,33,42,45,63,74,77,82,95,110,用折半查找法查找值为82 的结点，经_次比较后查找成功。 9 . 图的深度优先搜索和广度优先搜索序列不是唯一的。此断言是_的。(回答正确或不正确) 10哈希法既是一种存储方法，又是一种 。 1144.在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第 7 个记录65 插入到有序表时，为寻找插入位置需比较_次。 12栈和队列的操作特点分别是_和 _。 e f g i b a c h d 7 三、综合题（每小题 10 分，共 30 分） 1已知序列11，

18、19，5，4，7，13，2，10 ， （1）试给出用归并排序法对该序列作升序排序时的每一趟的结果。 （2）对上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉树描述建堆过程） 。 2设有序表为（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,依次取表中数据，构造一

19、棵二叉排序树. （2） 说明如何通过序列的二叉排序树得到相应序列的排序结果， 对上述二叉排序给出中序遍历的结果. 四、程序填空题（每空 2 分，共 16 分） 1 以下冒泡法程序对存放在 a1，a2，an中的序列进行冒泡排序，完成程序中的空格部分，其中 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=

20、 =0)break; 程序中 flag的功能是（5 ） 7以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为 left 和 right，数据域为 data，其数据类型为字符型，BT 指向根结点） 。 Void Postorder (struct BTree Node *BT) if(BT!=NULL) （1） ; （2） ; （3） ; 8 试题答案； 一、单项选择题（每小题 2 分，共 30 分） 1 A 2D 3B 4B 5A 6C 7C 8B 9A 10A 11A 12D 13D 14A 15D 二、填空题（每小题 2 分，共 24 分） 1.p-n

21、ext=s; 2.集合、线性、树形、图状 3. f=f-next; 4.中序 5.n 6. dgbaechhif 7.行号、列号、元素值 8.4次 9.正确 10查找方法 113 次 12先进后出 先进先出 三、综合题（每小题 10 分，共 30 分） 1 (1) 初始 11，19，5，4，7，13，2，10 第一趟 11，194，57，132，10 第二趟 4，5，11，192，7，10， ，13 第三趟 2，4，5，7，10，11，13，19 (2) 2 10 11 5 19 7 4 13 13 5 10 11 19 7 2 4 7 13 10 13 11 2 5 4 19 2 4 7 1

22、0 5 11 9 2 (1)13,36,63,135 (2) (3)3 次 3 (1) (2)中序遍历 中序 2，3，4，5，6，7，14，16，18 四、程序填空题（每空 2 分，共 16 分） 1 （1 ）j=n-1 （2 ）inext= =head Dhead-next= =NULL 3 链表所具备的特点是（ ） 。 A 可以随机访问任一结点 B占用连续的存储空间 C 插入删除元素的操作不需要移动元素结点 D可以通过下标对链表进行直接访问 4 非空的单向循环链表的尾结点满足（ ） （设头指针为 head，指针 p 指向尾结点） 。 Ap-next = =NULL Bp= =NULL Cp

23、= =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 Di 8 设有一个长度为 n 的顺序表，要删除第 i 个元素需移动元素的个数为（ ） 。 An-i+1 Bn-i Cn-i-1 Di 9 在一个单链表中，p 、q 分别指向表中

24、两个相邻的结点，且 q 所指结点是 p 所指结点的直接后继，现要删除 q 所指结点，可用的语句是（ ） 。 Ap=q-next Bp-next=q Cq-next=NULL Dp-next=q-next 10在一个单链表中 p 所指结点之后插入一个 s 所指的结点时，可执行（ ） 。 Ap=snext Bp next=snext; C s next=pnext; pnext=s; Dp next= s; snext= pnext 11从一个栈顶指针为 top的链栈中删除一个结点时，用变量 x 保存被删结点的植，则执行（ ） 。 A x=top-data; top=topnext; Bx=top

25、-data; C top=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; 11 14元素 1 ，3 ，5 ，7 按顺序依次进栈，则该栈的不可能输出序列是（ ） （进栈

26、出栈可以交替进行） 。 A7 ，5 ，3 ，1 B7 ，5 ，1 ，3 C 3 ，1 ，7 ，5 D 1 ，3 ，5 ，7 15设有一个 18 阶的对称矩阵 A ，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组 B 中（数组下标从 1 开始） ，则矩阵中元素 a10,8在一维数组 B 中的下标是（ ） 。 A 18 B45 C53 D58 16在 C 语言中，顺序存储长度为 3 的字符串，需要占用（ ）个字节。 A4 B3 C6 D12 17一棵有 n 个结点采用链式存储的二叉树中，共有（ ）个指针域为空。 An Bn+1 Cn-1 Dn-2 18在一棵二叉树中，若编号为 i 的

27、结点存在左孩子，则左孩子的顺序编号为（ ） 。 A 2i B2i-1 C2i+1 D2i+2 19设一棵哈夫曼树共有 n 个叶结点，则该树有（ ）个非叶结点。 An B2n Cn-1 Dn+1 20一棵具有 35 个结点的完全二叉树，最后一层有（ ）个结点。 A4 B6 C16 D8 21一棵完全二叉树共有 5 层，且第 5 层上有六个结点，该树共有（ ）个结点。 A30 B20 C21 D23 22在一个无向图中，所有顶点的度数之和等于边数的（ ）倍。 A3 B2 C2.5 D1.5 23已知如图 1 所示的一个图，若从顶点 a 出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（

28、） 。 Aabecdf Bacfebd Caedfcb Daebcfd 图 1 24已知如图 3所示的一个图，若从顶点 V1出发，按广度优先法进行遍历，则可能得到的一种顶点序列为（ ） 。 AV1V2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7 C V1V2V4V8V3V5V6V7 DV1V3V6V7V2V4V5V8 b d f e c a 12 图 3 25在有序表1，3 ，8 ，13，33，42，46，63，76，78，86，97，100中，用折半查找值86 时，经（ ）次比较后查找成功。 A 3 B4 C 6 D8 26对二叉排序树进行（ ）遍历，可以使遍历所得到的序列是

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

30、46，84，56，79 C 40，38，46，56，79，84 D38，40，46，56，79，84 30一组记录的关键字序列为（47，80，57，39，41，46） ，利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（ ） 。 A39，47，46，80，41，57 B39，41，46，80，47，57 C 41，39，46，47，57，80 D39，80，46，47，41，57 二填空题 1把数据存储到计算机中,并具体体现数据之间的逻辑结构称为_ _结构。 2算法的 5 个特征为_。 3结构中的数据元素存在 的关系称为树形结构。 4要求在 n 个数据元素中找其中值最大的元素，设基本操作为

31、元素间的比较。则比较的次数和算法的时间复杂度分别为_和 _ 。 5求两个 n 阶矩阵的乘积，算法的基本操作和时间复杂度分别为_和_ _。 6在一个单向链表中 p 所指结点之后插入一个 s 所指向的结点时，应执行 s-next=p-next;和 的操作。 7设有一个头指针为 head 的单向循环链表，p 指向链表中的结点，若 p-next= = head，则p 所指结点为 。 V6 V7 V1 V2 V3 V8 V4 V5 13 8在一个单向链表中，要删除 p 所指结点，已知 q 指向 p 所指结点的前驱结点。则可以用操作_。 9设有一个头指针为 head 的单向链表，p 指向表中某一个结点，且

32、有 p-next= =NULL,通过操作_,就可使该单向链表构造成单向循环链表。 10向一个栈顶指针为 h 的链栈中插入一个 s 所指结点时，可执行 s-next=h; 和 操作。(结点的指针域为 next) 11从一个栈顶指针为 h 的链栈中删除一个结点时，用 x 保存被删结点的值，可执行 和 h=h-next; (结点的指针域为 next) 。 12在一个链队中，设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的操作为 r-next=s;和 (结点的指针域为 next)。 13在一个链队中，设 f 和 r 分别为队头和队尾指针，则删除一个结点的操作为_。 (结点的指针域为 nex

33、t) 14.两个串相等的充分必要条件是_ _。 15对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_、_和_三项信息。 16在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是_、 、 。 17一棵有 2n-1 个结点的二叉树，其每一个非叶结点的度数都为 2，则该树共有_个叶结点。 18一棵二叉树中有 2n-2 条边（结点间的连线） ，其中每一个非叶结点的度数都为 2，则该树共有_个非叶结点。 19中序遍历二叉排序树可得到一个 。 20如图 1 所示的二叉树，其中序遍历序列为_ _。 21如图 1 所示的二叉树，其先序遍历序列为_。 22如图 1 所示的二叉树，其后序

34、遍历序列为_。 23如图 2 所示的二叉树，其前序遍历序列为_。 24哈希函数是记录关键字值与该记录存储地址之间所构造的对应关系。 25图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是_的。(回答正确或不正确) 26n 个元素进行冒泡法排序，通常需要进行_趟冒泡，第 j 趟冒泡要进行_次图 1 图 2 e f g i b a c h d g f a b d e c 14 元素间的比较。 三、综合题 1设一组记录的关键字序列为（49，83，59，41，43，47） ，采用堆排序算法完成以下操作：（要求小根堆，并画出中间过程） （1）以二叉树描述 6 个元素的初始堆 （2）以二叉树描述逐

35、次取走堆顶元素后，经调整得到的 5 个元素、4 个元素的堆 2已知序列11，19，5，4，7，13，2，10 （1）试给出用归并排序法对该序列作升序排序时的每一趟的结果。 （2）对上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉树描述建堆过程） 。 3一组记录的关键字序列为（46，79，56，38，40，84） （1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要求以升序排列） （2）对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。 4设查找表为(7,15,21,22,40,58,68,80,88,89,120) ,元素的下标依次

36、为 1,2,3,，11. （1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示） （2）说明成功查找到元素 40 需要经过多少次比较？ （3）求在等概率条件下，成功查找的平均比较次数？ 5设查找表为(16,15,20,53,64,7), (1)用冒泡法对该表进行排序（要求升序排列） ，要求写出每一趟的排序过程，通常对 n 个元素进行冒泡排序要进行多少趟冒泡？第 j 趟要进行多少次元素间的比较？ (2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树.(要求以数据元素作为树结点) (3)求在等概率条件下,对上述有序表成功查找的平均查找长度. 6 （1）如果二叉树中任一

37、结点的值均大于其左孩子的值、小于其右孩子的值，则该树为二叉排序树，这种说法是否正确？若认为正确，则回答正确，若认为不正确，则举例说明。 （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)“一棵二叉树若它的根结点的值大于左子树所有结点的值，小于右子树所有结点的值，则该树一定是二叉排序树” 。该说法是否正确，若认为正确，则

38、回答正确，若认为不正确则说明理由？ (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，构造哈夫曼树。 15 （2）同样用上述权值构造另一棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两棵树的带权路径长度。 11如图所示的二叉树 （1）给出中序遍历序列 （2）给出先序遍历序列 （3）给出后序遍历

39、序列 四、程序填空题 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 个结点的单向链表的程序，结点中的数据域从前向后依次为 1,2,3,n，完成程序中空格部分。

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

41、ODE*)malloc(sizeof(NODE); p-next=NULL; head= ; ; for(i=1; idata=i; if(i= =1) p-next=NULL; else p-next= ; q-next= ; return(head); 4设线性表为（6，10，16，4） ，以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。 #define NULL 0 void main( ) NODE a,b,c,d,*head,*p; a.data=6; b.data=10; c.data=16; d.data=4; /*d 是尾结点*/ head= ; a.ne

42、xt=&b; b.next=&c; c.next=&d; ; /*以上结束建表过程*/ p=head; /*p 为工作指针，准备输出链表*/ do printf(“%dn”, ); ; 17 while( ); 5以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为 left 和 right，数据域 data 为字符型，BT 指向根结点） 。 void Preorder (struct BTreeNode *BT) if(BT!=NULL) ; ; ; 6以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为 left 和

43、right，数据域 data 为字符型，BT 指向根结点） 。 void Inorder (struct BTreeNode *BT) if(BT!=NULL) ; ; ; 7以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、右指针域分别为 left 和 right，数据域 data 为字符型，BT 指向根结点） 。 void Postorder (struct BTreeNode *BT) if(BT!=NULL) ; ; ; 8以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为 left 和 right，数据域 data 为字

44、符型，BT 指向根结点） 。 void Inorder (struct BTreeNode *BT) if(BT!=NULL) （1） ; （2） ; Inorder(BT-right); 利用上述程序对右图进行遍历，结果是 ; e f a b c d 18 综合练习题答案 一、单项选择题 1 C 2D 3C 4D 5B 6C 7A 8B 9D 10C 11A 12C 13C 14B 15C 16A 17B 18A 19C 20A 21C 22B 23C 24A 25B 26C 27A 28D 29C 30B 二、填空题 物理（存储） 有穷性、确定性、可行性、零个或多个输入、一个或多个输入 3

45、树形 4n-1,O(n) 5乘法，O(n3) 6s-next=p-next; 7head 8q-next=p-next; 9p-next=head; 10s-next=h; 11h=h-next; 12r-next=s; 13f=f-next; 14串长度相等且对应位置的字符相等 15行下标、列下标、非零元素值 16值域、左指针、右指针 17n 18n-1 19中序 20dgbaechif 21abdgcefhi 22gdbeihfca 23abdefcg 24存储地址 25正确 26n-1,n-j 三、综合题 1 (1) 19 (2) 2 (1) 初始 11，19，5，4，7，13，2，10

46、 第一趟 11，194，57，132，10 第二趟 4，5，11，192，7，10， ，13 49 59 83 41 43 47 83 47 41 43 59 49 49 83 41 43 47 83 43 59 49 41 43 47 83 49 59 41 47 59 59 47 41 49 83 43 43 47 41 59 83 49 59 47 41 43 83 49 47 41 83 59 43 49 47 41 43 83 49 59 20 第三趟 2，4，5，7，11，10，11，13 (2) 3 (1)初始序列 46，79，56，38，40，84 40，79，56，38，40

47、，84 40，79，56，38，79，84 40，38，56，38，79，84 40，38，56，56，79，84 40，38，46，56，79，84 (2) 56 79 38 40 84 46 84 79 38 40 46 562 10 11 5 19 7 4 13 13 5 10 11 19 7 2 4 7 13 10 13 19 11 2 5 4 19 2 4 7 10 5 11 21 4 (1) (2)4 次 (3)ASL=(1+2*2+3*4+4*4)/11=3 5 (1)原序列 16 15 20 53 64 7 15 16 20 53 7 64 n-1 趟 15 16 20 7 5

48、3 64 n-j 次 15 16 7 20 53 64 15 7 16 20 53 64 7 15 16 20 53 64 (2) (3)平均查找长度=（1*1+2*2+3*3）/6=14/6 4 7 11 8 5 2 10 1 3 9 6 7 15 20 64 16 5356 79 38 40 46 79 38 40 84 84 56 46 22 6 (1)不正确，例 (2) 7 (1) (2)中序遍历 中序 2，3，4，5，6，7，14，16，18 8 (1)不正确，二叉排序树要求其子树也是二叉排序树。 1 5 4 2 39 55 92 81 4 101 7 2 40 7329 2 4 6

49、 16 7 3 18 5 14 23 (2) 后续遍历 5，6，4，9，8，18，20，16，7 9 (1) 2 0000 3 0001 4 001 7 10 8 11 9 01 （2）2n-1 个，因为非叶结点数比叶结点数少一个。 10 （1） wpl1=45 9 7 5 8 9 2 4 3 33 1518 5 3 4 18 11 7 6 3 3 1 2 4 6 8 9 5 20 7 16 18 24 （2） wpl2=45 11 （1）dgbaechif （2）abdgcefhi （3）gdbeihfca 四、程序填空题 1 j=n-1 inext p 4 &a dnext= =NULL pdata 18 7 11 3 1 2 3 3 4 6 5 25 p=pnext p!=NULL 5 printf(“%c”,BT-data); Preorder(BT-left); Preorder(BT-right); 6 Inorder(BT-left); printf(“%c”,BT-data); Inorder(BT-right); 7 Postorder(BT-left); Postorder(BT-right); printf(“%c”,BT-data); 8 Inorder(BT-left); printf(“%c”,BT-data); dbeafc