新数据结构讲义(9)
更新时间:2024-07-11 07:15:01 阅读量: 综合文库 文档下载
第九讲
总复习课
我们回顾一下学过的内容,数据结构是一门专业课。本课程的目的和任务是使学生较全面地掌握各种常用的数据结构,为学习后续软件课程提供必要的基础,提高运用数据结构解决实际问题的能力。
第一章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义,要求了解本章介绍的各种基本概念和术语,掌握算法描述和分析的方法。
第二章的目的是介绍线性表的逻辑结构和各种存储表示方法,以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求能够针对具体应用问题的要求和性质,选择合适的存储结构设计出相应的有效算法,解决与线性表相关的实际问题。
第三章的目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算,重点是掌握栈和队列在两种存储结构上实现的基本运算。
第四章的目的是介绍串的逻辑结构,存储结构及其串上的基本运算,重点是掌握串上实现的模式匹配算法。
第五章的目的是介绍多维数组的逻辑结构特征及其存储方式,特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念。重点是熟悉多维数组的存储方式,矩阵的压缩存储方式,广义表的定义及其求表头和表尾的运算。
1
第六章的目的是介绍二叉树的定义,性质,存储结构,遍历,线索化,树的定义,存储结构,遍历,树和森林与二叉树的转换,哈夫曼树及哈夫曼编码等内容。重点是掌握二叉树的遍历算法及其 有关应用。
第七章的目的是介绍图的基本概念,两种常用的存储结构,两种遍历算法以及图的应用算法,要求重点掌握在图的两种存储结构上实现的遍历算法。难点是图的应用算法:求最小生成树,求最短路径以及拓扑排序。
第八章的目的是介绍五类内部排序方法的基本思想,排序过程,算法实现,时间和空间性能的分析以及各种排序方法的比较和选择。重点掌握快速排序,堆排序,归并排序和基数排序的基本思想及排序过程,难点是这四个排序算法的实现。
第九章的目的是介绍线性表,树和散列表的查找方法,算法实现和各种查找方法的时间性能分析。重点掌握顺序查找,二分查找,二叉查找树上查找以及散列表上查找的基本思想和算法实现。
第十章的目的是介绍存储在外存上的数据结构(即文件)的有关概念,各种文件的特点,组织方法及查询和更新操作,要求对这些内容做一般性的了解。
本课程内容多,难度大,要求具有较强的程序设计能力及离散数学,C语言基础,从数据结构的逻辑结构,存储结构和数据的运算三个方面去理解各种数据结构的异同之处及相互之间的关系,懂得从定义和实现两个层次去分析各种数据结构。通过多练习多动手,培养自
2
己的程序设计经验和素质,多做算法设计题来理解,消化和巩固所学的知识,提高分析问题,解决问题的能力以及编程能力。设计较复杂算法的方法和步骤是:首先明确算法要解决的问题目标,选择合适的数据结构,确定在所选的数据结构上必须有哪些操作,写出抽象的算法;然后确定存储结构,对抽象算法中每个操作逐步求精地写出最终的程序。
要求全面系统地学习各章节内容,弄懂和记住各种概念,方法,结论的内涵和外延,注意区分相仿的概念,方法,结论,掌握它们之间的联系。
一、 单项选择题
1、线性表的链接实现有利于 运算。
A、插入 B、读表元 C、查找 D、定位 2、串的逻辑结构与 的逻辑结构不同。
A、线性表 B、栈 C、队列 D、树
3、设单链表中指针P指着结点A,若要删除A之后的结点(若存在),则需要修改指针的操作为 。
A、P→next=P→next→next B、P= P→next C、P=P→next→next D、P→next=P
4、设一数列的顺序为:1,2,3,4,5,6,通过栈结构不可能排成的顺序数列为 。
A、3,2,5,6,4,1 B、1,5,4,6,2,3
3
C、2,4,3,5,1,6 D、4,5,3,6,2,1
5、如果结点A有3个兄弟,而且B为A的双亲,则B的度为 。
A、3 B、4 C、5 D、1
6、线索化二叉树中某结点D,没有左孩子的主要条件是 。
A、D→Lchild=Null B、D→ltag=1 C、D→Rchild=Null D、D→ltag=0 7、下面的序列中, 是堆。
A、1,2,8,4,3,9,10,5 B、1,5,10,6,7,8,9,2 C、9,8,7,6,4,8,2,1 D、9,8,7,6,5,4,3,7 8、具有n个顶点的完全有向图的边数为 。
A、n(n-1)/2 B、n(n-1) C、2n D、(n+1)(n-1) 9、具有2000个节点的二叉树,其高度至少为 。
A、9 B、10 C、11 D、12
10、若给定的关键字集合为{20,15,14,18,21,36,40,10},一趟快速排列结束时,键值的排列为 。
A、10,15,14,18,20,36,40,21 B、10,15,14,18,20,40,36,21 C、10,15,14,20,18,40,36,21 D、15,10,14,18,20,36,40,21 11、有一棵二叉树如下图,该树是 。
4
A、二叉平衡树 B、二叉排序树 C、堆的形状 D、以上都不是
12、设有100个元素,用二分法查找时,最大比较次数是 ,最小比较次数是 。
A、25 B、7 C、10 D、1 13、在内部排序中,排序时不稳定的有 。
A、插入排序 B、冒泡排序 C、快速排序 D、归并排序 14、对于下图V1的度为 。
5
正在阅读:
新数据结构讲义(9)07-11
高中化学公式大全03-22
山西省康杰中学等四校2015届高三第二次联考语文试题06-28
重庆市社会保险业务申报数据报盘操作说明书09-29
2018中考英语必备1600个词汇06-12
软件项目管理实验三 项目规模成本估算 - 软件0801何飞10-02
浅谈邓小平的社会主义观06-05
宇宙-南京邮电大学社会与人口学院03-08
复旦大学856经济学综合基础考前冲刺最后三套卷(二)【圣才出品】04-15
金融全部思考题01-30
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 数据结构
- 讲义