计算机基础知识 - 岳阳电大

1、辅导教师：刘文英数据结构（本）期末复习和例题选讲课程教学基本要求1掌握常用的数据结构的逻辑关系、存储结构、操作特点及有关应用。2掌握迭代、递归等程序设计技术，了解他们与相关的数据结构的关系。3掌握常用的查找、排序算法的基本原理和实现步骤。4能有效合理地利用所学数据结构，程序设计技术和相关算法解决简单实际应用问题。5了解数据结构在后续课程中的作用。 登录三级平台登录中央电大课程讨论打开中央电大开放教育在线平台（）登录（学号为中央电大学号，如：20081430060312 ，密码为生日的8位数）在课程论坛列表中选择课程输入发贴内容。 湖南电大BBS讨论省电大BBS讨论：登录省电大在线平台（）实时交

2、流（页面上端）进入相应的讨论室进行提问。 省电大非实时交流：登录省电大在线平台（）选择相关课程（页面左侧）页面右上方点击“进入”，进入相应的课程论坛点击“发新贴”进行提问。（相关课程责任教师将在三天内回复） 岳阳电大BBS讨论岳阳电大BBS讨论：登录岳阳电大平台（ ）公开讨论区（页面右侧）公共论坛（页面左侧）选择专业（计算机本科）进行提问。 岳阳电大非实时交流：登录岳阳电大平台（ ）我的提问（页面右侧）进行提问。（相关课程责任教师将在三天内回复） 考 核1考核对象 2007年秋季起入学的计算机科学与技术专业（本科）学生。2考核依据 以数据结构（本）课程教学大纲为依据编制，考核说明是本课程形成性

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

4、试。 组卷原则：在考核说明所规定的内容和要求之内命题。在教学内容范围之内，按照理论联系实际原则，考察学生对所学知识应用能力的试题，不属于超纲。试题的难易程度和题量适当，按难易程度分为易、中、难三个层次：易占25%，中占45%，难占30%。题量安排以大多数考生能在规定的考试时间内做完并有一定时间检查为原则。 试题类型及试卷结构：试题题型有单项选择题、填空题、综合题和程序填空题四种题型。试卷结构如下： 单项选择题：每小题2分，共30分 填空题：每小题2分，共24分 综合题：每小题10分，共30分 程序填空题：每空2分，共16分 共100分 答题时限：答题时限为90分钟。考核知识点1数据结构的基本概

5、念2算法和算法分析的基本概念考核要求1理解数据结构的基本概念2掌握逻辑结构、物理结构的概念及相互关系3掌握本书介绍的四种基本结构的特点4理解算法及其特性5了解算法分析的一般概念第1章 绪论1.数据结构：(数据元素间的关系称为结构)，相互间存在一种或多种特定关系的数据元素的集合称为数据结构。逻辑结构：元素间的逻辑关系，与计算机无关。物理结构：把数据存储到计算机中，并具体体现数据之间的关系。简言之，是逻辑结构在计算机中的表示(包括数据元素和关系的表示)，同一种逻辑结构可以对应不同的物理结构。重点掌握的知识点举例集合：属于同一集合。线形：一对一，数据元素之间存在一对一的关系，线性表除第一个元素和最后

6、一个元素外每个元素有一个直接前驱和直接后继。树形：一对多。图：多对多。2.基本的数据结构算法：解决特定问题的方法算法的5个特征 有穷、确定、可行、零个或多个输入、一个或多个输出时间复杂度 基本操作、频度、问题规模、数量级、时间复杂度与实现算法的软、硬件无关。 n个矩阵的乘积算法的基本操作为乘法，时间复杂度为O(n3) 要在n个数据元素中找最大元素，基本操作为比较，比较次数为n-1，时间复杂度为O(n)3.算法：考核知识点1线性表的定义、逻辑结构、顺序存储结构、链式存储结构2线性表在顺序结构和链式结构上的基本操作和应用 3双向链表、循环链表的原理和相关操作考核要求1理解线性表的定义及两种存储结构

7、2理解线性表顺序存储的特点、实现方法和应用。3掌握顺序表的基本操作（包括建立链表、遍历链表、删除、插入、查找）和应用。特别要求能够利用链表的操作和相关的程序设计技术编制有一定难度的程序。4了解双向链表、循环链表的原理和相关操作。第2章 线性表1.线性表的定义：属于同一个数据对象的数据元素的有限序列。2.顺序存储(顺序表)：逻辑结构与存储结构一致，可用数组或指针实现，能随机访问，如果线性表存储后最常用的操作是取第i个结点及其前驱，采用顺序表较方便，但顺序表插入删除操作平均而言移动元素次数较多，效率很低. 插入位置i，移动元素次数为n-i+1.删除位置是i，移动次数n-i。3.链式存储(链表)：以

8、结构变量存储结点，动态生成结点，以指针链接结点，能有效利用存储空间，插入删除方便，但不能随机访问.单向链表可从某结点访问到后继结点。重点掌握的知识点举例建立链表的头插法：指针变量p开辟单元，生成结点，指针变量q始终指向头结点，操作为： p-next=q-next; q-next=p; 尾插法：指针变量q始终指向尾结点，p指针开辟单元，生成结点. q-next=p; q=p; 4.单向链表操作的关键步骤：插入：p所指向结点的后面插入新结点s所指结点 s-next=p-next; p-next=s; 删除：p，q指向相邻结点，q所指结点是p所指结点的后继，删除q所指结点， p-next=q-nex

9、t;遍历：p=p-next; 插入、删除、遍历：单向链表中，如果有p-next=NULL，令 p-next=head；则成为单向循环链表，可从某结点访问到任一结点，但访问前驱要通过头结点.单向循环链表中，若p指向尾结点，则p-next=head5.单向循环链表：6.双向链表：每个结点有两个指针域，一个指向直接后继，一个指向直接前驱.头结点的prio指向尾结点，尾结点的next指向头结点，从任一结点可访问前驱和后继7.单向链表为空的判断条件是head=NULL,但带头结点的单向链表为空的判断条件为head-next=NULL 8.链式存储的线性表都不能随机访问考核知识点1栈的定义、栈的存储结构（

10、顺序存储、链式存储）和基本操作、栈的应用2队列的定义、队列的存储结构（顺序存储、链式存储）、队列的应用3循环队列的概念和实现方法考核要求1掌握栈和队列的操作特点2理解顺序栈、顺序队列的基本操作3了解在实际编程中栈和队列的不同应用。理解循环队列的概念、实现方法。掌握循环队列判空、判满的条件4能按照后续章节（例如二叉树、排序等）的要求利用递归程序设计技术实现相关算法。第3章 栈和队列1.栈和队列是运算受限制的线性表。2.栈：后进先出(LIFO)，栈的插入删除操作在栈顶进行 例:进栈顺序为b, c, d, e, f .出栈可能为 f, e, d, c, b; b, c, d, e, f ; c, b

11、, e, d, f 但不可能是e, d, f, b, c3.顺序栈：相当于线性表的顺序存储结构，可用一维数组实现设置栈顶指针top，在栈顶进行操作(插入、删除等)重点掌握的知识点举例4.链栈：相当于线性表的链式存储结构，设头指针变量为top 出栈：用x保存被删结点的值，在栈中删除结点. x=top-data; top=top-next; 进栈：设栈顶指针为h，要插入s所指结点，操作为s-next=h;h=s;相当于在单向链表的头插法5.队列：（FIFO） 入队：1,2,3,4,5 出队：1,2,3,4,56.顺序队列：可以用一维数组来实现设置指针front、rear分别指向队列的队头元素和队尾

12、元素7.链队列：是在表头删除在表尾插入的单链表设置头指针front,尾指针rear在链队中插入s所指结点的操作为： rear-next=s; rear=s;在链队中删除结点相当于删除链表中的第一个结点（若要保存被删结点，可先保留，再删除）考核知识点1串类型定义、C语言中字符串的特点和处理方法2串的顺序存储结构和链式存储结构3串的基本运算和实现方法考核要求1理解串的定义和存储方法2了解串的基本操作和相关算法3掌握用C语言处理字符串的语法规则第4章 串1.每个字符占一个字节,串的最基本的存储方式是顺序存储、链式存储。字符串的特点是在串尾自动加一个结束符。3.有关串的运算的函数（求串长、复制、连接、

13、比较、查找字符、查找子串），要求能掌握函数的功能.例StrCmp (“a”,“A”)的值为1，上述函数是字符串比较函数.两个串相等的充要条件是串长相等，对应位置字符相等.例StrCat (“ab”,“cd”)的功能是串连接。4.从字符串中查找子串的方法称为模式匹配算法，例求串q在p中首先出现的位置。重点掌握的知识点举例考核知识点1数组的定义和存储结构2特殊矩阵和稀疏矩阵的存储结构3广义表的定义和存储结构考核要求1了解数组的存储结构。2掌握特殊矩阵进行压缩存储的下标转换公式。3理解稀疏矩阵的压缩存储原理。4掌握利用三元组表示稀疏矩阵的方法。5了解广义表的概念和存储结构。第章 数组和广义表1.特殊

14、矩阵,如对称矩阵的压缩存储结构，矩阵元素与一维数组元素的对应。 设数组下标从开始,矩阵元素， ，(1+2+3)+3=9,， 对应一维数组下标为9.7，6对应一维数组下标为(1+2+3+6)+6=27.i，j对应下标为i(i-1)/2+j。2.稀疏矩阵的三元组存储结构（行，列，非零元）重点掌握的知识点举例考核知识点1树的基本概念2二叉树的性质和存储结构3二叉树的遍历和线索二叉树4哈夫曼树及其应用考核要求1了解树和二叉树的定义2掌握二叉树的基本性质，能利用相关性质解决简单计算问题3了解二叉树的顺序存储结构4掌握二叉树的链式存储结构、相关操作5掌握二叉树的有关算法并能编程实现6掌握利用遍历序历构造二

15、叉树的规则和具体步骤7掌握哈夫曼树的定义、性质和构造方法8了解哈夫曼树的应用第6章 树和二叉树1.树的定义： 连通不含回路的图 树的边数m和顶点数n有关系n=m+1，顶点数等于边数加1重点掌握的知识点举例2. 二叉树的性质：二叉树上终端结点数(叶结点数)等于双分子结点数(度数为的结点数)加.例有n个叶结点的二叉树，每个结点度数为2，则有2n-1个结点二叉树第i层上至多有2i-1个结点深度为h的二叉树至多有2h-1个结点二叉树中编号为i的结点，左孩子结点编号为2i，右孩子结点为2i+1满二叉树、完全二叉树 设有一棵完全二叉树有18个结点,最高层有18-(1+2+4+8)=3个结点。 例有一棵二叉

16、树，有2n-2条边，每一个非叶结点度数都为2，则共有2n-2+1=2n-1个顶点，有n个叶结点，n-1个非叶结点。1354213542673.二叉树的存储结构顺序存储： 对结点编号，以编号为下标把结点存储到一维数组中链式存储结构：链式存储的二叉树的空指针域： 设结点数为n，共有2n个指针域，有n-1个指针域指向n-1个结点（根结点除外）所以有2n-(n-1)个指针没有指向（空指针域），即n+1个空指针域。二叉树的遍历： 访问每个结点一次且只一次leftdataright值域、左指针、右指针遍历树的三个子问题：根结点、左子树、右子树。规定先左后右，以根结点的访问顺序分为先、中、后序遍历.另外还有

17、层次遍历，共四种遍历方法 二叉树的递归遍历算法.递归调用、输出结点信息结点的权和带权路径长度： 从根结点到该结点的路径长度与该结点上权的乘积 第6章 树和二叉树重点掌握的知识点举例3.二叉树的存储结构树的带权路径长度： 树中所有叶子结点的带权路径长度之和 WPL= WiLi第6章 树和二叉树重点掌握的知识点举例3.二叉树的存储结构哈夫曼树(最优树)： n个带权叶结点构成的所有二叉树中，带权路径长度WPL最小的二叉树重点掌握的知识点举例3.二叉树的存储结构构造Huffman树的算法： 设n个权值w1,w2,wn, (1)在权值集合中取权值最小的作为结点，以它们的权值之和作为它们的父结点的权值第6

18、章 树和二叉树重点掌握的知识点举例3.二叉树的存储结构构造Huffman树的算法： (2)在剩余的权值集合中，加入上述父结点的权值得到新权值集合，重复步骤(1),直到权值集合中只剩下一个权值，生成一棵有n个结点的Huffman树第6章 树和二叉树重点掌握的知识点举例3.二叉树的存储结构哈夫曼编码： 在Huffman树中，让每个分支结点的左、右分支分别用0、1编码，从根结点到叶结点的路径上所经分支的0、1编码序列为该叶结点的二进制编码，所有叶结点的编码集合为哈夫曼编码第6章 树和二叉树重点掌握的知识点举例3.二叉树的存储结构哈夫曼编码： Huffman树的特点之一：除叶结点外，每一个结点度数都为

19、2.设一棵哈夫曼树有n个非叶结点，则有n+1个叶结点，共有2n+1个结点第6章 树和二叉树重点掌握的知识点举例 例1 ： (1)以1，2，5，6，7，8作为叶结点的 权，构造一棵哈夫曼树，给出相应权重值叶结点的哈夫曼编码。 (2) 一棵哈夫曼树有n个叶结点，它一共有多少个结点？简述理由？第6章 树和二叉树重点掌握的知识点举例 答案： (1)1：0000 2：0001 5：001 6：10 7：11 8：01 (2)2n-1个，因为非叶结 点数比叶结点数少一个。29132176538816重点掌握的知识点举例例2 ：如图所示的二叉树（1）给出中序遍历序列（2）给出先序遍历序列（3）给出后序遍历序

20、列 (1)abcdjefhgi (2)eadcbjfghi (3)bcjdahigfeefhbgjcdai考核知识点1图的基本概念2图的存储结构3图的遍历4最小生成树和最短路径。考核要求1了解图的基本概念2掌握图的存储方法（邻接矩阵、邻接表）3掌握图的深度优先和广度优先遍历的规则和步骤4理解在连通图中求最小生成树的方法。了解求图的最短路径等相关算法及其应用第7章 图重点掌握的知识点举例1.图的存储结构2.图的遍历：图的广度优先遍历的规则和步骤： (1)访问vi ,访问vi的所有未被访问过的邻接点 vi1、vi2、vit2.图的遍历：图的广度优先遍历的规则和步骤： (2)按照vi1、vi2、vi

21、t的次序，访问每一个顶点所有未被访问过的邻接点，依次类推直到和vi有路径相通的顶点都访问过为止第7章 图重点掌握的知识点举例2.图的遍历：图的深度优先遍历的规则和步骤： 访问vi(初始点)，从vi的任一个未被访问过的邻接点出发继续深度优先搜索遍历，若搜索过程中某一结点的邻接点全被访问过，则退回上一个结点，继续深度搜索遍历，直到退回到初始点且没有未被访问过的邻接点第7章 图重点掌握的知识点举例3.图的最小生成树生成树： 设有连通图G，取G的全部顶点和部分边构成子图G,若G连通且不含有回路，则G是生成树第7章 图重点掌握的知识点举例3.图的最小生成树带权图： 边上带有权的图连通图一定存在生成树，且

22、不一定唯一树权： 树中所有边的权值之和第7章 图重点掌握的知识点举例3.图的最小生成树最小生成树： 连通图中具有最小权的生成树带权连通图一定存在最小生成树，且不一定唯一第7章 图 重点掌握的知识点举例 例1 已知如图所示的一个图，若从顶点V1出发，按深度优先法进行遍历，则可能得到的一种顶点序列为（ ）。 AV1V2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7 CV1V2V4V8V3V5V6V7 DV1V3V6V7V2V4V5V8V6V7v1V2V3V8V4V5答案：A 重点掌握的知识点举例 例2 已知如图所示的一个图，若从顶点V1出发，按广优先搜索法进行遍历，则可能得到的一种顶

23、点序列为（ ）。 AV1V2V3V6V7V4 V5V8 BV1V2V3V4V5V8V6V7 CV1V2V3V4V5V6V7V8 DV1V2V3V4V8V5V6V7V6V7v1V2V3V8V4V5答案：C考核知识点1线性表的查找（顺序查找、折半查找、分块查找）。2二叉排序树的查找。3哈希表（哈希表的定义、哈希函数的构造、处理冲突的方法、哈希表的查找和分析）。考核要求1了解查找的相关概念。2掌握顺序表的查找方法、步骤、程序实现、时间复杂度和平均查找长度。3掌握在有序的顺序表上进行折半查找的方法、步骤、程序实现。4掌握折半查找的判定树的构造方法。能利用判定树求平均查找长度。5掌握二叉排序树的确切定义

24、，掌握建立二叉排序树的步骤和方法。理解在二叉排序树中进行输入、删除操作的规则。6了解哈希表的相关概念和原理，了解常用哈希函数的构造和处理冲突的方法。理解哈希函数和哈希表的关系及在查找中的应用。第8章 查找重点掌握的知识点举例1.查找表、关键字：主关键字2.线性表的查找：顺序查找：从表的某一端开始逐次进行比较折半查找：针对有序的顺序表，设置low、high，令mid=( low+high)/23.折半查找对应的判定树： 树中结点相应于查找表中的记录，结点值相应于记录在查找表中的位置4.利用折半查找的判定树，求成功查找到某一元素、查不到某一元素的比较次数、等概率条件下成功查找的平均查找长度第8章

25、查找重点掌握的知识点举例5.分块查找的数据结构 查找表分块索引表(块内最大关键字值、块起始地址)第8章 查找重点掌握的知识点举例6.二叉排序树二叉排序树定义： 若左子树非空，则左子树所有结点的值小于根结点的值； 若右子树非空，则右子树所有结点的值大于根结点的值；第8章 查找重点掌握的知识点举例6.二叉排序树二叉排序树定义： 左、右子树也分别是一棵二叉排序树(每个结点的值都大于它的左子树上所有结点的值，小于它的右子树上所有结点的值)二叉排序树中任一棵子树也是二叉排序树。第8章 查找重点掌握的知识点举例6.二叉排序树二叉排序树的建立： 实际上是从空树逐次插入的过程二叉排序树的查找二叉排序树的插入

26、第8章 查找重点掌握的知识点举例6.二叉排序树7.哈希函数： 记录的关键字值与该记录存储地址之间构造的对应关系第8章 查找重点掌握的知识点举例例1 设查找表为( 8,16,22,23,50,59,69,81,89, 90, 121 ),元素的下标依次为1,2,3,11.(1)画出对上述查找表进行折半查找所对应的 判定树（树中结点用下标表示）(2)说明成功查找到元素50需要经过多少次比 较？(3)求在等概率条件下，成功查找的平均比较 次数？重点掌握的知识点举例例1 答案：(1)(2)4次(3)ASL=(1+2*2 +3*4+4*4)/11=34711852101396重点掌握的知识点举例 例2

27、设查找表为 (51,61,76,86,97,99,106,111,121, 131) , (1)说出成功查找到元素121需要进行多少 次元素间的比较？ (2)为了查找元素95，经过多少次元素间的 比较才能确定不能查到？ (3)画出对上述有序表进行折半查找所对应 的判定树(要求以数据元素作为树结点)重点掌握的知识点举例例2 答案：(1)3次(2)4次(3)如图 977699131106865111112161例3 设查找表为(17,16,21,54,65,8), (1)用冒泡法对该表进行排序(要求升序排列),要求写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次

28、元素间的比较？ (2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树.(要求以数据元素作为树结点) (3)求在等概率条件下,对上述有序表成功查找 的平均查找长度.例3 答案：(1)原序列 17 16 21 54 65 8 16 17 21 54 8 65 n-1趟 16 17 21 8 54 65 n-j次 16 17 8 21 54 65 16 8 17 21 54 65 8 16 17 21 54 65 (2)如右图(3)平均查找长度=（1*1+2*2+3*3）/6=14/681621651754 例4（1）如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树

29、为二叉排序树，这种说法是否正确？若认为正确，则回答正确，若认为不正确，则举例说明。（2）设有数据集合41，30，8，74，102，5，56，3，82，93，40，依次取集合中各数据，构造一棵二叉排序树。 例4 答案： (1)不正确，例 (2) 如右图15424056938215102834107430 例5 （1）对给定数列8,17,5,9,21,10,7,19,6,依次取数列中的数据，构造一棵二叉排序树。 (2 )对一个给定的查找值,简述针对二叉排序树进行查找的算法步骤,在上述二叉树中查找元素21共要进行多少次元素的比较? 例5 答案： (1)如右图： (2)先将给定值与根结点比较，若相等则

30、查找成功，否则若小于根结点则在左子树中继续查找，大于根结点在右子树中查找，查找20共进行3次比较。 5791068172119 例6 (1)“一棵二叉树若它的根结点的值大于左子树所有结点的值，小于右子树所有结点的值，则该树一定是二叉排序树”。该说法是否正确，若认为正确，则回答正确，若认为不正确则说明理由？ (2)设有查找表6，15，3，7，19，8，5，17，4，依次取表中数据构造一棵二叉排序树. 对上述二叉树给出后序遍历的结果。 例6 答案： (1)不正确，二叉排序树要求其子树也是二叉排序树。 (2) 4,5,3,8,7,17,19,15,6357841961517考核知识点1插入排序（直接

31、插入排序、希尔排序）2交换排序（冒泡排序、快速排序）3选择排序（简单选择排序、堆排序）4归并排序考核要求1掌握教材中介绍的各种排序算法的基本原理、步骤。2能针对小规模具体实例，按相关排序算法的规则人工完成排序；能通过分析排序的中间结果判断所用的排序算法。3能正确理解相关排序算法的程序实例，并重点掌握算法中的关键步骤和关键语句。4掌握堆和特殊的完全二叉树的对应关系。掌握建堆、筛选算法和完全二叉树相关操作的对应关系。第9章 排序重点掌握的知识点举例1.插入排序：直接插入： 第i趟插入是指前i-1个已有序，第i个元素逐次与前i-1个元素比较找到插入位置.插入后得到有i个元素的有序序列。折半插入： 采

32、用折半查找法找到插入位置，加快了查找速度第9章 排序重点掌握的知识点举例2.交换排序：冒泡排序： n个元素通常需要n-1趟冒泡 第i趟冒泡要进行n-i次元素比较 某趟冒泡中若没有进行元素的交换，则表 明已排好序，可设立标志位结束冒泡过程第9章 排序重点掌握的知识点举例2.交换排序：快速排序： 一趟划分执行步骤：设置分割元素(第一个元素)，逐次轮换从后向前、从前向后扫描，必要时交换记录位置，最终使划分元素到位，完成一次分割，递归调用一趟划分函数，实现快速排序 第9章 排序重点掌握的知识点举例3.选择排序：简单选择排序： 逐次从n个元素、n-1个元素，查找最小元素的位置，并逐一排序到位 第9章 排

33、序重点掌握的知识点举例3.选择排序：堆排序： 大根堆、小根堆 堆与特殊完全二叉树的对应 筛选：输出堆顶元素(存入到最后一个元素的位置)，以最后一个元素替换，并自顶向下重新调整为堆 建初始堆：从最后一个非叶子结点开始直到第一个结点，从下到上逐次筛选 第9章 排序重点掌握的知识点举例4.归并排序：归并：把两个有序序列合成一个有序序列(逐次比较)一趟归并算法对待排序列逐次施行(1,1)归并、(2,2)归并， 最终完成排序 第9章 排序例1设一组记录的关键字序列为（59，93，69，51，53，57），采用堆排序算法完成以下操作：（要求小根堆，并画出中间过程）（1）以二叉树描述6个元素的初始堆（2）以

34、二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆例1 答案：(1) 596993515357935751536959595157935369595153439383594957699353515357935969例1 答案：(2)695751599353535751699359695751539359575193695359575153935969例2 一组记录的关键字序列为（47，80，57，39，41，85）（1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要求以升序排列）（2）对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描

35、述建堆过程。例2 答案：(1)初始序列 47，80，57，39，41，85 47 41，80，57，39，41，85 41，80，57，39，80，85 41，39，57，39，80，85 41，39，57，57，80，85 41，39，47，57，80，85 例2 答案：(2) 5780394185478580394147575780394147803941858557471.能阅读书中给出的相关程序2.重点掌握单向链表的头插法、尾插法、静态法建链表的程序、单向链表的插入和删除程序、顺序表的插入、删除程序、二分查找程序、冒泡排序程序、栈的出栈、进栈程序.队列的出队、入队程序、二叉树的前序、中

36、序、后序遍历程序（递归法）等第10章 有关程序的要求一、单项选择题（每小题2分，共30分）1.数据结构中，与所使用的计算机无关的是数据 （ ）结构。 A. 逻辑 B. 物理 C. 存储 D. 逻辑与物理 答案：A2.下述各类表中可以随机访问的是（ ）。 A. 单向链表 B. 双向链表 C.单向循环链表 D.顺序表 答案：D习题选讲3.在一个长度为n的顺序表中为了删除第5个元素，由第6个元素开始从后到前依次移动了15个元素。则原顺序表的长度为（ ）。 A. 21 B. 20 C. 19 D. 25 答案：B4.元素2，4，6按顺序依次进栈，则该栈的不可能的输出序列是（ ）。 A. 6 4 2 B

37、. 6 2 4 C. 4 2 6 D. 2 6 4 答案：B5.一个队列的入队序列是5，6，7，8，则队列的输出序列是（ ）。 A. 5 6 7 8 B. 8 7 6 5 C. 7 8 6 5 D.可能有多种情况 答案：A6. 串函数StrCmp（“d”，“D”）的值为（ ）。 A0 B1 C-1 D3 答案：B7在一个单链表中，p、q分别指向表中两个相邻的结点,且q所指结点是p所指结点的直接后继，现要删除q所指结点,可用语句（ ）。 Ap=q-next ; BP-next=q ; CP-next=q-next ; D. q-next=NULL ; 答案：C8.设一棵哈夫曼树共有n个非叶结点，

38、则该树一共有（ ）个结点。 A. 2*n-1 B. 2*n +1 C. 2*n D. 2*(n-1) 答案：B9.对如图1所示二叉树进行中序遍历,结果是( ) A. dfebagc B. defbagc C. defbacg D. dbaefcg 答案：Aadgbfec10 . 任何一个无向连通图的最小生成树（ ）。 A.至少有一棵 B.只有一棵 C.一定有多棵 D.可能不存在 答案：A11设有一个10阶的对称矩阵A，采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始）,则矩阵中元素A8,5在一维数组B中的下标是（ ）。 A33 B32 C85 D41 答案：A

39、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 答案：D13 . 对n个元素进行冒泡排序，要求按升序排列，程序中设定某一趟冒泡没有出现元素交换，就结束排序过程。对某n个元素的排序共进行了3n-6次元素间的比较就完成了排序，则（ ）。 A.原序列是升序排列 B.原序列是降序排列 C.对序列只进行了2趟冒泡 D. 对序列只进行了3趟冒泡 答案：D14在一个栈顶指针为top的链栈中删除一个结点时,用x保存被删除的结点,应执行（ ）。 =top-data;top=top-next; B. top=top-next ; x=top; =top;top=top-next ; D. x=top-data; 答案：A15在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ ）。 A2i B2i-1 C2i+2 D2i