电大数据结构(本)期末复习指导1018.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《电大数据结构(本)期末复习指导1018.pdf》由会员分享,可在线阅读,更多相关《电大数据结构(本)期末复习指导1018.pdf(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 分 填空题:每小题 2 分,共 24 分 综合
5、题:每小题 10 分,共 30 分 程序填空题:每空 2 分,共 16 分 共 100 分 (5)答题时限 答题时限为 90 分钟。二、考核内容和要求 第 1 章 绪论(2 学时)考核知识点 1数据结构的基本概念 2算法和算法分析的基本概念 考核要求 1理解数据结构的基本概念 2掌握逻辑结构、物理结构的概念及相互关系 3掌握本书介绍的四种基本结构的特点 4理解算法及其特性 5了解算法分析的一般概念 第 2 章 线性表(8 学时)考核知识点 1线性表的定义、逻辑结构、顺序存储结构、链式存储结构 2线性表在顺序结构和链式结构上的基本操作和应用 3双向链表、循环链表的原理和相关操作 考核要求 1理解
6、线性表的定义及两种存储结构 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掌握特殊矩阵进行压缩存储的下标转换公式。3理解稀疏矩阵的压缩存储原理。4掌
8、握利用三元组表示稀疏矩阵的方法。5了解广义表的概念和存储结构。第 6 章 树和二叉树(10 学时)考核知识点 1树的基本概念 2二叉树的性质和存储结构 3二叉树的遍历和线索二叉树 4哈夫曼树及其应用 考核要求 1了解树和二叉树的定义 2掌握二叉树的基本性质,能利用相关性质解决简单计算问题 3了解二叉树的顺序存储结构 4掌握二叉树的链式存储结构、相关操作 5掌握二叉树的有关算法并能编程实现 6掌握利用遍历序历构造二叉树的规则和具体步骤 4 7掌握哈夫曼树的定义、性质和构造方法 8了解哈夫曼树的应用 第 7 章 图(6 学时)考核知识点 1图的基本概念 2图的存储结构 3图的遍历 4最小生成树和最
9、短路径。考核要求 1了解图的基本概念 2掌握图的存储方法(邻接矩阵、邻接表)3掌握图的深度优先和广度优先遍历的规则和步骤 4理解在连通图中求最小生成树的方法。了解求图的最短路径等相关算法及其应用 第 8 章 查找(6 学时)考核知识点 1线性表的查找(顺序查找、折半查找、分块查找)。2二叉排序树的查找。3哈希表(哈希表的定义、哈希函数的构造、处理冲突的方法、哈希表的查找和分析)。考核要求 1了解查找的相关概念。2掌握顺序表的查找方法、步骤、程序实现、时间复杂度和平均查找长度。3掌握在有序的顺序表上进行折半查找的方法、步骤、程序实现。4掌握折半查找的判定树的构造方法。能利用判定树求平均查找长度。
10、5掌握二叉排序树的确切定义,掌握建立二叉排序树的步骤和方法。理解在二叉排序树中进行输入、删除操作的规则。6了解哈希表的相关概念和原理,了解常用哈希函数的构造和处理冲突的方法。理解哈希函数和哈希表的关系及在查找中的应用。第 9 章 排序(6 学时)考核知识点 1插入排序(直接插入排序、希尔排序)2交换排序(冒泡排序、快速排序)3选择排序(简单选择排序、堆排序)4归并排序 考核要求 1掌握教材中介绍的各种排序算法的基本原理、步骤。2能针对小规模具体实例,按相关排序算法的规则人工完成排序;能通过分析排序的中间结果判断所用的排序算法。3能正确理解相关排序算法的程序实例,并重点掌握算法中的关键步骤和关键
11、语句。4掌握堆和特殊的完全二叉树的对应关系。掌握建堆、筛选算法和完全二叉树相关操作的对应关系。三、试题类型及答案 一、单项选择题(每小题 2 分,共 30 分)1.数据结构中,与所使用的计算机无关的是数据的()结构。5 A.逻辑 B.物理 C.存储 D.逻辑与物理 2.下述各类表中可以随机访问的是()。A.单向链表 B.双向链表 C.单向循环链表 D.顺序表 3.在一个长度为 n 的顺序表中为了删除第 5 个元素,从前到后依次移动了 15 个元素。则原顺序表的长度为()。A.21 B.20 C.19 D.25 4.元素 2,4,6 按顺序依次进栈,则该栈的不可能的输出序列是()。A.6 4 2
12、 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 所指结点的直接后继,现要删除 q 所指结点,可用语句()。Ap=q-next Bp-next=q Cp-next=q-next Dq-next=NULL 8.设一棵哈夫曼树共有 n 个非叶结点,则该树一共有()个结点。A.2*n-1 B.2*n+
13、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,采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组 B 中(数组下标从 1 开始),则矩阵中元素 A8,5在一维数组 B 中的下标是()。A33 B32 C85 D41 12.一组记录的关键字序列为(37,70,47,29,31,85),利用快速排序,以第一个关键字为分割元素,经过
14、一次划分后结果为()。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 个元素的排序共进行了 3n-6次元素间的比较就完成了排序,则()。A.原序列是升序排列 图 1 c b c d e f g a 6 B.原序列是降序排列 C.对序列只进行了 2 趟冒泡 D.对序列只进行了 3 趟冒泡 14在一个栈顶指针为 top的链栈中删除一个结点时,用 x 保存被删除的结点,应执行()。A.x
15、=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所指的新结点,应执行s-next=p-next;和_操作。2 根据数据元素间关系的不同特性,通常可分为_、四类基本结构。3 在一个链队中,设 f 和 r 分别为队头和队尾指针,则删除一个结点的操作为_。(结点的指针域为 next)4._遍历二叉排序树可得到一个有序序列
16、。5.一棵有 2n-1 个结点的二叉树,其每一个非叶结点的度数都为 2,则该树共有_个叶结点。6.如图 1 所示的二叉树,其中序遍历序列为_ _。图 1 7.对稀疏矩阵进行压缩存储,矩阵中每个非零元素所对应的三元组包括该元素的_、_和_三项信息。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)进行直
17、接插入排序时,当把第 7 个记录65 插入到有序表时,为寻找插入位置需比较_次。12栈和队列的操作特点分别是_和 _。e f g i b a c h d 7 三、综合题(每小题 10 分,共 30 分)1已知序列11,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)画出对上述有序表
18、进行折半查找所对应的判定树(树结点用下标表示)(3)设查找元素 5,需要进行多少次元素间的比较才能确定不能查到.3 (1)设有查找表5,14,2,6,18,7,4,16,3,依次取表中数据,构造一棵二叉排序树.(2)说明如何通过序列的二叉排序树得到相应序列的排序结果,对上述二叉排序给出中序遍历的结果.四、程序填空题(每空 2 分,共 16 分)1 以下冒泡法程序对存放在 a1,a2,an中的序列进行冒泡排序,完成程序中的空格部分,其中 n 是元素个数,程序按升序排列。Void bsort(NODE a,int)NODE temp;int i,j,flag;for(j=1;(1);j+);fla
19、g=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 Postorder(struct BTree Node*BT)if(BT!=NULL)(1);(2);(3);8 试题答案;一、单项选择题(每小题 2 分,共 30 分)1 A 2D 3B 4B 5A 6C 7C 8B 9A 10
20、A 11A 12D 13D 14A 15D 二、填空题(每小题 2 分,共 24 分)1.p-next=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
21、 7 2 4 7 13 10 13 11 2 5 4 19 2 4 7 10 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=N
22、ULL 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 Di 8 设有一个长度为 n 的顺序表,要删除第 i 个元素需移动元素的个数为()。An-i+1 Bn-i Cn-i-1 Di 9 在一个单链表中,p、q 分别指向表中两个
23、相邻的结点,且 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-data;C top=top-nex
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 电大 数据结构 期末 复习 指导 1018
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内