[计算机]杭州电子科技大学 数据结构 期末复习 大纲 习题.doc
《[计算机]杭州电子科技大学 数据结构 期末复习 大纲 习题.doc》由会员分享,可在线阅读,更多相关《[计算机]杭州电子科技大学 数据结构 期末复习 大纲 习题.doc(5页珍藏版)》请在三一文库上搜索。
1、第一章 绪论 杭州电子科技大学一 基本概念和术语数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。术语:数据、数据元素、数据对象、数据结构、抽象数据类型、算法。数据结构的形式定义(二元组)数据的逻辑结构:线性结构 非线性结构数据的存储结构(物理结构):主要有顺序存储结构 链式存储结构抽象数据类型(三元组)算法(5个重要特性)二 算法的时间复杂度和空间复杂度算法的评价:正确性、可读性、健壮性、高效率、低存储量第二章 线性表一 线性表的定义线性结构的特点二 线性表的存储结构1 顺序存储结构(顺序表)插入/删除元素时,需移动元素2 链式存储结构(链表,分为
2、单向链表、双向链表)带头结点的链表和不带头结点的链表;循环链表;链表空与非空的情况。3 两种存储结构的优缺点比较,各适合那些场合。三 线性表操作的实现(算法描述)插入元素、删除元素、查找、判表是否满足某种特性例:判断题:1. 线性表的逻辑顺序与存储顺序总是一致的。F 2. 线性结构的基本特征是:每个结点有且仅有一个直接前驱和一个直接后继。F 3. 线性表的链式存储结构优于顺序存储结构。F选择题:线性表L在( B )情况下适于使用链表结构实现。 A. 不需修改L的结构 B. 需不断对L进行删除、插入 C. 需经常修改L中结点值 D. L中含有大量结点填空题:1. 对于顺序表中,在第i个元素前插入
3、一个元素需移动 n-i+1 个元素,要删除第i个元素,需移动 n-i 个元素。2. 在双向循环链表中某结点(由指针p指示)之后插入s指针所指结点的操作是: ; ; ; ;。第三章 栈和队列一 栈1 栈的定义2 栈的存储结构:顺序存储结构 链式存储结构3 栈的应用:二叉树的先序、中序、后序遍历算法 图的深度优先遍历算法(将递归算法改写为非递归算法可借助栈来完成;递归算法的执行需用栈来实现)二 队列1 队列的定义2 队列的存储结构:顺序存储结构(循环队列),链式存储结构3 队列的应用:二叉树层序遍历 图的广度优先遍历算法4 循环队列:队空、队满的判断条件求队列的长度循环队列通常用front和rea
4、r来指示队头和队尾的位置来表示一个队列;如果用front指示队头,用length表示队列的长度,也可以表示一个队列。相应的有关操作怎样实现?例:判断题:因为栈是特殊的线性表,所以对线性表的所有操作都可以用于对栈操作。填空题:循环队列队满的条件是 rear-front 。第四章 串一 串的定义二 串的术语:长度、子串三 串的基本操作:求串的长度、求子串、串联接、串替换、串匹配(子串定位)例:已知下列字符串:a=THIS, b= (一个空格), c=GOOD, d=NE, f=A SAMPLE,执行如下操作: s=Concat (a , Concat (Concat (b , SubString
5、(a ,3 ,2) , SubString (f , 2 , SubLength(f);t=Replace (f , SubString (f ,3 ,6) , c);u=Concat (SubString (c ,3 ,1) , d);v=Concat (s , Concat (b ,Concat (t , Concat (b , u);试问:s,t,u,v,LENGTH(s)各是什么?第五章 数组和广义表一 数组数组的顺序存储:行主顺序法,列主顺序法。元素存储地址计算特殊矩阵的压缩存储 元素存储地址计算二 广义表1. 广义表的概念:广义表,长度,深度,表头,表尾;2. 广义表的头尾链表存储
6、结构第六章 树和二叉树一 树、二叉树的定义二 二叉树1 二叉树的性质(5条)2 二叉树的存储结构:顺序存储结构(按层序存放) 链式存储结构(二叉链表、三叉链表)(空指针域的个数)3 遍历二叉树:先序、中序、后序、层序应用:给定二叉树的先序和中序(或后序和中序)序列,画出相应的二叉树4 线索二叉树:先序、中序、后序线索化三 树和森林1 树的存储结构:双亲表示法 孩子表示法 孩子-兄弟(二叉树)表示法2 树(森林)与二叉树的相互转换3 树的遍历:先根、后根次序遍历4 森林的遍历:先序、中序遍历四 赫夫曼树及其应用1 最优二叉树(赫夫曼树),求WPL2 赫夫曼编码五 各种二叉树概念的区分1 满二叉树
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 计算机杭州电子科技大学 数据结构 期末复习 大纲 习题 杭州 电子科技大学 期末 复习
链接地址:https://www.31doc.com/p-1991026.html