数据结构(本)期末复习指导.pdf

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

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

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

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

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

5、空2分，共16分共100分(5)答题时限答题时限为9 0分钟。二、考核内容和要求第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.能按照后续章节（例如二叉树、排序等）

7、的要求利用递归程序设计技术实现相关算法第4章 串（2学时）考核知识点1 .串类型定义、C语言中字符串的特点和处理方法2.串的顺序存储结构和链式存储结构3.串的基本运算和实现方法 考核要求1 .理解串的定义和存储方法2.了解串的基本操作和相关算法3.掌握用C语言处理字符串的语法规则第 5章 数组和广义表（2学时）考核知识点1.数组的定义和存储结构2.特殊矩阵和稀疏矩阵的存储结构3.广义表的定义和存储结构 考核要求1.了解数组的存储结构。2.掌握特殊矩阵进行压缩存储的下标转换公式。3.理解稀疏矩阵的压缩存储原理。4.掌握利用三元组表示稀疏矩阵的方法。5.了解广义表的概念和存储结构。第 6章 树和二

8、叉树（10学时）考核知识点1.树的基本概念2.二叉树的性质和存储结构3.二叉树的遍历和线索二叉树4.哈夫曼树及其应用 考核要求1.了解树和二叉树的定义2.掌握二叉树的基本性质，能利用相关性质解决简单计算问题3.了解二叉树的顺序存储结构4.掌握二叉树的链式存储结构、相关操作5.掌握二叉树的有关算法并能编程实现6 .掌握利用遍历序历构造二叉树的规则和具体步骤7 .掌握哈夫曼树的定义、性质和构造方法8 .了解哈夫曼树的应用第 7章图（6学时）考核知识点1.图的基本概念2.图的存储结构3.图的遍历4.最小生成树和最短路径。考核要求1.了解图的基本概念2.掌握图的存储方法（邻接矩阵、邻接表）3.掌握图的

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

10、序树中进行输入、删除操作的规则。6 .了解哈希表的相关概念和原理，了解常用哈希函数的构造和处理冲突的方法。理解哈希函数和哈希表的关系及在查找中的应用。第 9章 排 序（6学时）考核知识点1 .插入排序（直接插入排序、希尔排序）2 .交换排序（冒泡排序、快速排序）3 .选择排序（简单选择排序、堆排序）4.归并排序 考核要求1 .掌握教材中介绍的各种排序算法的基本原理、步骤。2 .能针对小规模具体实例，按相关排序算法的规则人工完成排序；能通过分析排序的中间结果判断所用的排序算法。3 .能正确理解相关排序算法的程序实例，并重点掌握算法中的关键步骤和关键语句。4 .掌握堆和特殊的完全二叉树的对应关系。

11、掌握建堆、筛选算法和完全二叉树相关操作的对应关系。三、试题类型及答案一、单项选择题（每小题2分，共3 0分）L数据结构中，与所使用的计算机无关的是数据的（）结构。A.逻辑 B.物理 C.存储 D.逻辑与物理2 .下述各类表中可以随机访问的是（）oA.单向链表 B.双向链表 C.单向循环链表 D.顺序表3 .在一个长度为n的顺序表中为了删除第5个元素，从前到后依次移动了 1 5 个元素。则原顺序表的长度为（A.2 1 B.2 0 C.1 9 D.2 54 .元素2,4,6按顺序依次进栈，则该栈的不可能的输出序列是（）。A.6 4 2 B.6 2 4 C.4 2 6 D.2 6 45 .一个队列的

12、入队序列是5,6,7,8,则队列的输出序列是（）。A.5 6 7 8 B.8 7 6 5C.7 8 6 5 D.可能有多种情况6 .串函数 S t r C m p （d ，“D ）的 值 为（）.A.0 B.1 C.-1 D.37 .在一个单链表中，p、q分别指向表中两个相邻的结点，且 q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。A.p=q-n e x t B.p-n e x t=q C.p-n e x t=q-n e x t D.q-n e x t=N U L L8 .设一棵哈夫曼树共有n个非叶结点，则该树一共有（）个结点。A.2*n T B.2*n +1 C.2*n

13、 D.2*（n T）9 .对如图1 所示二叉树进行中序遍历，结 果 是（）。A.df eb a g c B.def b a g c C.def b a c g D.db a ef c g图 11 0 .任何一个无向连通图的最小生成树（A.至少有一棵 B.只有一棵 C.一定有多棵 D.可能不存在1 1 .设有一个1 0 阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1 开始），则矩阵中元素A&5 在一维数组B中的下标是（A.3 3 B.3 2 C.85 D.4 11 2 .一组记录的关键字序列为（3 7,70,4 7,2 9,3 1,85）,利用快速

14、排序，以第一个关键字为分割元素，经过一次划分后结果为（）A.3 1,2 9,3 7,85,4 7,7 0 B.2 9,3 1,3 7,4 7,7 0,85C.3 1,2 9,3 7,7 0,4 7,85 D.3 1,2 9,3 7,4 7,7 0,851 3 .对 n个元素进行冒泡排序，要求按升序排列，程序中设定某一趟冒泡没有出现元素交换，就结束排序过程。对某n个元素的排序共进行了 3 n-6 次元素间的比较就完成了排序，则（）。A.原序列是升序排列B.原序列是降序排列C.对序列只进行了 2 趟冒泡D.对序列只进行了 3 趟冒泡1 4 .在一个栈顶指针为t o p 的链栈中删除一个结点时，用

15、x 保存被删除的结点，应执行（）。A.x=t o p-da t a;t o p=t o p-n ex t;B.t o p=t o p-n ex t ;x=t o p;C.x=t o p;t o p=t o p-n ex t ;D.x=t o p-da t a;1 5 .串函数S t rC a t （a,b）的功能是进行串（）。A.比较 B.复制 C.赋值 D.连接二、填 空 题（每小题2 分，共 2 4 分）1 .在一个单向链表中p 所指结点之后插入一个s 所指的新结点，应执行s-n ex t=p-nex t；和 操作。2 .根据数据元素间关系的不同特性，通常可分为、四类基本结构。3 .在一个

16、链队中，设 f 和 r分别为队头和队尾指针，则删除一个结点的操作为_。（结点的指针域为n ex t）4 .遍历二叉排序树可得到一个有序序列。5 .一棵有2 n-l 个结点的二叉树，其每一个非叶结点的度数都为2,则该树共有个叶结点。6 .如图1 所示的二叉树，其中序遍历序列为。图 17.对稀疏矩阵进行压缩存储，矩阵中每个非零元素所对应的三元组包括该元素的、和_ _ _ _ _ _ _ _ 三项信息。8.有一个有序表 2,3,9,1 3,33,42,45,63,74,77,82,95,1 1 0,用折半查找法查找值为82的结点，经_ _ _ _ _ _ _次比较后查找成功。9.图的深度优先搜索和广

17、度优先搜索序列不是唯一的。此断言是 的。（回答正确或不正确）1 0.哈希法既是一种存储方法，又是一种。1 1 .44.在对一组记录（5 5,39,97,22,1 6,73,65,47,88）进行直接插入排序时，当把第7个记录65 插入到有序表时，为寻找插入位置需比较 次。1 2.栈和队列的操作特点分别是 和。三、综 合 题（每小题1 0分，共 30分）1.已知序列 1 1,1 9,5,4,7,1 3,2,1 0，（1）试给出用归并排序法对该序列作升序排序时的每一趟的结果。（2）对上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉树描述建堆过程）。2.设有序表为（1 3,1 9,25,36,4

18、8,5 1,63,84,91,1 1 6,1 35,200）,元素的下标依次为1,2,1 2.（1）说出有哪几个元素需要经过3 次元素间的比较才能成功查到（2）画出对上述有序表进行折半查找所对应的判定树（树结点用下标表示）（3）设查找元素5,需要进行多少次元素间的比较才能确定不能查到.3.（1）设有查找表 5,1 4,2,6,1 8,7,4,1 6,3,依次取表中数据，构造一棵二叉排序树.（2）说明如何通过序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果.四、程序填空题(每空2分，共 1 6 分)1.以下冒泡法程序对存放在a l ,a 2 L，a n 中的序列进行冒泡排

19、序，完成程序中的空格部分，其中n 是元素个数，程序按升序排列。V o i d b s o r t (N O D E a ,i nt)N O D E t e m p;i nt i,j,f l a g;f o r(.i-l;(1);j+);f l a g=0;f o r (i=l;(2);i+)i f(a i .k e y a i+l .k e y)f l a g=l;t e m p=a i ;(3)：(4);)i f(f l a g=0)b r e a k;)程序中f l a g 的功能是(5)_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _7.以下程序

20、是后序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为l e f t 和 r i g h t,数据域为d a t a,其数据类型为字符型，BT指向根结点)。V o i d P o s t o r d e r (s t r u c t B T r e e N o d e *B T)i f(B T!=N U L L)_(1)_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _；_(2)_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _；(3);试题答案;一、单项选 择 题（每小题2 分，共 3 0 分）1.A 2.D 3.B 4.B5

21、.A 6.C7.C8.B 9.A 1 0.A1 1.A 1 2.D 1 3.D 1 4.A 1 5.D二、填 空 题（每小题2 分，共 2 4 分）1 .p-ne x t=s;2 .集合、线性、树形、图状3 .f=f-ne x t;4 .中序5 .n6 .d g b a e c h h i f7 .行号、列号、元素值8 .4次9 .正确1 0 .查找方法1 1 .3 次1 2 .先进后出先进先出三、综合题(每小题1 0 分，共 3 0 分)1.(1)初始 1 1,1 9,5,4,7,1 3,2,1 0第 一 趟 1 1,1 9 4,5 7,1 3 1 0 第 二 趟 4,5,1 1,1 9 2

22、,7,1 0,1 3 第 三 趟 2,4,5,7,1 0,1 b 1 3,1 9 J(2)2.(1)13,36,63,135(3)3 次(2)中序遍历中序 2,3,4,5,6,7,1 4,1 6,1 8四、程序填 空 题(每空2分，共 1 6 分)1.(1)j =n-l(2)i r i g h t)(3)p r i nt f(c”，B T fd a t a)第二部分期末综合练习题一、单项选择题(每小题2分)1 .针对线性表，在存储后如果最常用的操作是取第i 个结点及其前驱，则 采 用()存储方式最节省时间。A.单链表 B.双链表 C.顺序表 D.单循环链表2.带头结点的单向链表为空的判断条件是

23、()(设头指针为he a d)。A.he a d =N U L L B.he a d!=N U L LC.he a d-n e x t=he a d D.he a d-n e x t=N U L L3.链表所具备的特点是()。A.可以随机访问任一结点 B.占用连续的存储空间C.插入删除元素的操作不需要移动元素结点 D.可以通过下标对链表进行直接访问4.非空的单向循环链表的尾结点满足()(设头指针为he a d,指针p 指向尾结点)。A.p-n e x t =N U L L B.p=N U L L C.p=he a d D.p-n e x t=he a d5.数据结构中，与所使用的计算机无关的是

24、数据的（）结构。A.物理 B.逻辑 C.存储 D.逻辑与物理6.算法的时间复杂度与（）有关。A.所使用的计算机 B,计算机的操作系统C.算法本身 D.数据结构7.设有一个长度为n的顺序表，要在第i 个元素之前插入一个元素（也就是插入元素作为新表的第i 个元素），则移动元素个数为（）。A.n-i+1 B.n-i C.n-i-1 D.i8.设有一个长度为n的顺序表，要删除第i个元素需移动元素的个数为（A.n-i+1 B.n-i C.n-i-1 D.i9.在一个单链表中，p、q分别指向表中两个相邻的结点，且 q所指结点是p 所指结点的直接后继，现要删除q 所指结点，可用的语句是（）。A.p=q-n

25、e x t B.p-n e x t=q C.q-n e x t=N U L L D.p-n e x t=q-n e x t10.在一个单链表中p 所指结点之后插入一个s 所指的结点时，可 执 行（）。A.p=s f n e x t B.p n e x t=s f n e x t;C.s-n e x t=p-n e x t;p-n e x t=s;D.p 今n e x t 二 s;s-n e x t=p-n e x t11.从一个栈顶指针为t o p 的链栈中删除一个结点时，用变量x保存被删结点的植，则执行（）oA.x=t o p-d a t a;t o p=t o p f n e x t;B.

26、x=t o p-d a t a;C.t o p=t o p-n e x t;x=t o p-d a t a;D.t o p=t o p-n e x t;x=d a t a;12.在一个链队中，假 设 f 和 r 分别为队头和队尾指针，则删除一个结点的运算为（）oA.r=f n e x t;B.r=r-n e x t;C.f=f-n e x t;D.f=r-n e x t;13.在一个链队中，假设f 和 r分别为队头和队尾指针，则插入s 所指结点的运算为（）。A.f-n e x t=s;f=s;B.s-n e x t=r;r=s;C.r-n e x t=s;r=s;D.s-n e x t=f;f

27、=s;14.元 素 1,3,5,7 按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A.7,5,3,1 B.7,5,1,3C.3,1,7,5 D.1,3,5,715.设有一个18阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1 开始），则矩阵中元素a m s 在一维数组B中的下标是（）A.18 B.45 C.53 D.5816.在 C语言中，顺序存储长度为3 的字符串，需要占用（）个字节。A.4B.3C.6D.1217.一棵有n个结点采用链式存储的二叉树中，共有A.n B.n+1 C.n-l18.在一棵二叉树中，若编号为i 的

28、结点存在左孩子,A.2i B.2i-l C.2i+l19.设一棵哈夫曼树共有n 个叶结点，则该树有（A.n B.2n C.n-1 D.n+1（）个指针域为空。D.n-2则左孩子的顺序编号为（）。D.2i+2）个非叶结点。20.一棵具有35个结点的完全二叉树，最后一层有（A.4 B.6 C.1621.一棵完全二叉树共有5 层，且第5 层上有六个结点，A.30 Z A B.20 C.212 2.在 一 个 无 向 图 中,点 的 度 数 之 和 等 于 边 数 的（）个结点。D.8该树共有（）个结点。D.23）倍。A.32.52 3.已知O怀&若（/a出发的 一 种 顶 点 序 列/A.a b e

29、 cd f C.D.1.5,按深度优先搜索法进行遍历，则可能得到a e d f c b D.a e b c f d2 4.己 厂)3所 厂 丫 图 厂、)OA.V1V2V4V8W VT_ B.V N 2 V N 5 V 8 V 3 V 6 V 7C.V i V2V.V8V 3 V5/)D.W V 3 V 6 V 7 V 2 V 4 V 5 V 8安广度优先法进行遍历，则可能得到的2 5.在有序表 1,3,8,1 3,3 3,42,4 6,6 3,7 6,7 8,8 6,97,1 0 0 中，用折半查找值 86时，经（）次比较后查找成功。A.3B.4C.6D.82 6.对二叉排序树进行（）遍历，

30、可以使遍历所得到的序列是有序序列。A.按层次B.后序C.中序D.前序2 7.有一个长度为1 2 的有序表,按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（A.3 7/1 2B.3 9/1 2C.4 1/1 2 D.3 5/1 22 8.设已有m个元素有序，在未排好序的序列中挑选第m+1 个元素，并且只经过一次元素的交换就使第m+1 个元素排序到位，该方法是（A.折半排序 B.冒泡排序 C.归并排序 D.简单选择排序2 9.一组记录的关键字序 列 为（4 6,7 9,5 6,3 8,4 0,8 4）,利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。A.4 0,

31、3 8,4 6,7 9,5 6,8 4 B.4 0,3 8,4 6,8 4,5 6,7 9C.4 0,3 8,4 6,5 6,7 9,8 4D.3 8,4 0,4 6,5 6,7 9,8 43 0.一组记录的关键字序 列 为（4 7,8 0,5 7,3 9,4 1,4 6）,利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（）。A.3 9,4 7,4 6,8 0,4 1,5 7C.4 1,3 9,4 6,4 7,5 7,8 0B.3 9,4 1,4 6,8 0,4 7,5 7D.3 9,8 0,4 6,4 7,4 1,5 7二.填空题I .把数据存储到计算机中，并具体体现数据之间的逻辑结构

32、称为 结构。2 .算法的5个特征为.3 .结构中的数据元素存在 的关系称为树形结构。4 .要 求 在 n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为 和。5 .求两个n阶矩阵的乘积，算法的基本操作和时间复杂度分别为 和。6 .在一个单向链表中p所指结点之后插入一个s 所指向的结点时，应执行s-n e x t=p-n e x t;和 的操作。7 .设有一个头指针为h e a d 的单向循环链表，p指向链表中的结点，若 p-n e x t=h e a d,则p所指结点为。8 .在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可

33、以用操作 O9.设有一个头指针为h e a d 的单向链表，p指向表中某一 一 个结点，且有p-n e x t=N U L L,通过操作，就可使该单向链表构造成单向循环链表。1 0 .向一个栈顶指针为h的链栈中插入一个s 所指结点时，可执行s-n e x t=h;和 操作。（结点的指针域为n e x t）1 1 .从一个栈顶指针为h的链栈中删除一个结点时，用 x 保存被删结点的值，可执行和 h=h-n e x t;（结点的指针域为n e x t）。1 2 .在一个链队中，设 f 和 r 分别为队头和队尾指针，则插入s 所指结点的操作为r-n e x t=s;和（结点的指针域为n e x t）。

34、1 3 .在一个链队中，设 f 和 r 分别为队头和队尾指针，则删除一个结点的操作为 o（结点的指针域为n e x t）1 4 .两个串相等的充分必要条件是 o15.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的和_ _ _ _ _ _三项信息。16.在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是、17.一棵有2 n-l个结点的二叉树，其每一个非叶结点的度数都为2,则该树共有 个叶结点。18.一棵二叉树中有2n-2条 边（结点间的连线），其中每一个非叶结点的度数都为2,则该树共有 个非叶结点。19.中 序 遍 历 二 叉 排 序 树 可 得 到 一 个。20.如

35、 图1所示的二叉树，其中序遍历序列为 o图1图221.如 图1所示的二叉树，其 先 序 遍 历 序 列 为。22.如 图1所示的二叉树，其 后 序 遍 历 序 列 为。23.如图2所示的二叉树，其前序遍历序列为 o24.哈希函数是记录关键字值与该记录存储地址之间所构造的对应关系。25.图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是 的。（回答正确或不正确）26.n个元素进行冒泡法排序，通常需要进行 趟冒泡，第j趟冒泡要进行 次元素间的比较。三、综合题1 .设一组记录的关键字序列为(4 9,8 3,5 9,4 1,4 3,4 7),采用堆排序算法完成以下操作：(要求小根堆，并画出中间

36、过程)(1)以二叉树描述6个元素的初始堆(2)以二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆2 .已知序列1 1,1 9,5,4,7,1 3,2,1 0(1)试给出用归并排序法对该序列作升序排序时的每一趟的结果。(2)对上述序列用堆排序的方法建立初始堆(要求小根堆，以二叉树描述建堆过程)。3 .一组记录的关键字序列为(4 6,7 9,5 6,3 8,4 0,8 4)(1)利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果(给出逐次交换元素的过程，要求以升序排列)(2)对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。4 .设查找表为(7,1 5,2

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

38、求在等概率条件下,对上述有序表成功查找的平均查找长度.6 .(1)如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树为二叉排序树，这种说法是否正确？若认为正确，则回答正确，若认为不正确，则举例说明。(2)设有数据集合4 0,2 9,7,7 3,1 0 1,4,5 5,2,8 1,9 2,3 9,依次取集合中各数据，构造一棵二叉排序树.7 .(1)设有查找表5,1 4,2,6,1 8,7,4,1 6,3,依次取表中数据，构造一棵二叉排序树.(2)说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果.8 .(1)“一棵二叉树若它的根结点的值大于左子树

39、所有结点的值，小于右子树所有结点的值，则该树一定是二叉排序树”。该说法是否正确，若认为正确，则回答正确，若认为不正确则说明理由？(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)同样用上述权值构造另一棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两棵树的带权路径长度。1 1.如图所示的二叉树

40、(1)给出中序遍历序列(2)给出先序遍历序列(3)给出后序遍历序列四、程序填空题1.以下冒泡法程序对存放在al,a2.an中的序列进行冒泡排序完成程序中的空格部分，其 中n是元素个数，要求按升序排列。void bsort(NODE a,int n)NODE temp;int i,j,flag;for(j=1 ；j+)；flag=0；for(i=l;i+)if(ai.keyai+l.key)flag=l;temp=ai;if(flag=O)break;程序中flag的功能是2.以下是用尾插法建立带头结点且有n个结点的单向链表的程序，结点中的数据域从前向后依次为1,2,3,n,完成程序中空格部分。

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

42、;：for(i=l;idata=i;if(i=1)p-next=NULL;elsep-next=：q-next=;)return(head);)4.设线性表为(6,10,16,4),以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。#define NULL 0void m ain()NODE a,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4;/*d 是尾结点*/h e a d=;a.next=&b;b.next=&c;c.next=&d;：/*以上结束建表过程*/p=head;/*p为工作指针，准备输出链表*/do

43、Drintf(dn”.):_ _;while(上)5.以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和 rig h t,数据域data为字符型，BT指向根结点)。void Preorder(struct BTreeNode*BT)if(BT!=NULL)；6.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和 rig h t,数据域data为字符型，BT指向根结点)。void Inorder(struct BTreeNode*BT)if(BT!=NULL)7.以下程序是后序遍历二叉树的递归算法的程

44、序，完成程序中空格部分(树结构中，左、右指针域分别为left和 rig h t,数据域data为字符型，BT指向根结点)。void Postorder(struct BTreeNode*BT)if(BT!=NULL)8.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为lefl和 rig h l,数据域data为字符型，BT指向根结点)。void Inorder(struct BTreeNode*BT)if(BT!=NULL)Inorder(BT-right);)利用上述程序对右图进行遍历，结果是综合练习题答案一、单项选择题1.C 2.D 3.C 4.D

45、5.B 6.C 7.A 8.B 9.D 10.C 11.A 12.C13.C 14.B 15.C 16.A 17.B 18.A 19.C 20.A 21.C 22.B 23.C 24.A 25.B 26.C 27.A 28.D 29.C 30.B二、填空题1,物 理（存储）2.有穷性、确定性、可行性、零个或多个输入、一个或多个输入3.树形4.n-l,O（n）5.乘法，0 而）6.s-next=p-next;7.head8.q-next=p-next;9.p-next=head;10.s-next=h;11.h=h-next;12.r-next=s;13.f=f-next;1 4.串长度相等且对

46、应位置的字符相等15.行下标、列下标、非零元素值1 6.值域、左指针、右指针17.n18.n-11 9.中序20.dgbaechif21.abdgcefhi22.gdbeihfca23.abdefcg24.存储地址25.正确26.n-1 ,n-j三、综合题1.(1)(1)初始 1 1,1 9,5,4,7,1 3,2,1 0第 一 趟 1 1,1 9 4,5 J 7,1 3 J 2,1 0 第 二 趟 4,5,1 1,1 9 2,7,1 0,1 3 第 三 趟 2,4,5,7,1 1,1 0,1 1,1 3 3.(1)初始序列46,79,56,38,40,8440,79,56,3 8,圆，844

47、 0,国，56,38,79,8440,38,56,园 79,8440,3 8,园 56,79,8440,38,46,56,79,844.(1)(2)4 次(3)ASL=(1 +2*2+3*4+4*4)/11=35.原序列16 15 20 53 64 715 16 20 53 7 64 n-1 趟15 16 20 7 53 64 n-j 次15 16 720 53 6415 7 16 20 53 647 15 16 20 53 64(3)平均查找长度=(1*1+2*2+3*3)/6=14/67.(2)中序遍历中序 2,3,4,5,6,7,14,16,18(1)不正确，二叉排序树要求其子树也是二叉

48、排序树。后续遍历 5,6,4,9,8,18,20,16,79.(1)2 00003 00014 0017 108 119 01(2)2n-l个，因为非叶结点数比叶结点数少一个。(2)wp12=4 511.(1)dgbaechif(2)abdgcefhi(3)gdbeihfca四、程序填空题1.j=n-linextp4.&a dfnext=NULL pdata p=p今nextp!=NULL5.printf(c”,BT-data);Preorder(BT-left);Preorder(BT-right);6.Inorder(BT-left);printf(“c”,BT-data);Inorder

49、(BT-right);7.Postorder(BT-left);Postorder(BT-right);printf(44%c,BT-data);8.Inorder(BT-left);primf(“c”,BT-data);dbeafc数据结构（本）期末综合练习2015年6月综合练习一一、单项选择题1 .数据结构在计算机内存中的表示是指（）。A.数据元素之间的关系 B.数据的存储结构C.数据元素的类型 D.数据的逻辑结构2 .单向链表所具备的特点是（）。A.可以随机访问任一结点 B.占用连续的存储空间C.插入删除不需要移动元素 D.可以通过某结点的指针域访问其前驱结点3 .结构中的元素之间存在多

50、对多的关系是（）。A.集合 B.线性结构C.树形结构 D.图状结构4 .设有一个长度为1 8 的顺序表，要在第6个元素之前插入一个元素（也就是插入元素作为新表的第6 个元素），则移动元素个数为（）。A.1 2 B.5 C.1 3 D.65 .设有一个长度为2 0 的顺序表，要在第5个元素之前插入1 个 元 素（也就是插入元素作为新表的第5 个元素），则移动元素个数为（）.A.1 5 B.1 6 C.56 .栈和队列的共同特点是（）。A.都是线性结构C.都是先进后出D.4B.元素都可以随机进出1）.都是先进先出7 .在一个尾指针为re a r的不带头结点的单循环链表中,插入一个s 所指的结点，并