杭电[数据结构(c语言版本)]

《杭电[数据结构(c语言版本)]》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、——杭州電子科技大學——数据结构复习提纲(附：期末复习题及期末样卷)第一章绪论一．基本概念和术语　　数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。术语：数据、数据元素、数据对象、数据结构、抽象数据类型、算法。数据结构的形式定义（二元组）数据的逻辑结构：线性结构非线性结构数据的存储结构（物理结构）：主要有顺序存储结构链式存储结构抽象数据类型（三元组）算法（5个重要特性）二．算法的时间复杂度和空间复杂度算法的评价：正确性、可读性、健壮性、高效率、低存储量第二章线性表

2、一．线性表的定义线性结构的特点二．线性表的存储结构1．顺序存储结构（顺序表）插入/删除元素时，需移动元素2．链式存储结构（链表，分为单向链表、双向链表）带头结点的链表和不带头结点的链表；循环链表；链表空与非空的情况。3．两种存储结构的优缺点比较，各适合那些场合。三．线性表操作的实现（算法描述）插入元素、删除元素、查找、判表是否满足某种特性例：判断题：1.线性表的逻辑顺序与存储顺序总是一致的。F2.线性结构的基本特征是：每个结点有且仅有一个直接前驱和一个直接后继。F3.线性表的链式存储结构优于顺序存储结构。F选

3、择题：线性表L在(B)情况下适于使用链表结构实现。A.不需修改L的结构B.需不断对L进行删除、插入C.需经常修改L中结点值D.L中含有大量结点填空题：1.对于顺序表中，在第i个元素前插入一个元素需移动n-i+1个元素，要删除第i个元素，需移动n-i个元素。2.在双向循环链表中某结点（由指针p指示）之后插入s指针所指结点的操作是：；；；；。第三章栈和队列一．栈1．栈的定义2．栈的存储结构：顺序存储结构链式存储结构Copyright©澤豬2012-05-16——杭州電子科技大學——1．栈的应用：二叉树的先序、中序

4、、后序遍历算法图的深度优先遍历算法（将递归算法改写为非递归算法可借助栈来完成；递归算法的执行需用栈来实现）二．队列1．队列的定义2．队列的存储结构：顺序存储结构（循环队列），链式存储结构3．队列的应用：二叉树层序遍历图的广度优先遍历算法4．循环队列：·队空、队满的判断条件·求队列的长度·循环队列通常用front和rear来指示队头和队尾的位置来表示一个队列；如果用front指示队头，用length表示队列的长度，也可以表示一个队列。相应的有关操作怎样实现？例：判断题：因为栈是特殊的线性表，所以对线性表的所有操

5、作都可以用于对栈操作。填空题：循环队列队满的条件是rear->front。第二章串一．串的定义二．串的术语：长度、子串三．串的基本操作：求串的长度、求子串、串联接、串替换、串匹配（子串定位）例：已知下列字符串：a='THIS',b=''（一个空格）,c='GOOD',d='NE',f='ASAMPLE',执行如下操作：s=Concat(a,Concat(Concat(b,SubString(a,3,2)),SubString(f,2,SubLength(f))));t=Replace(f,SubString(

6、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.广义表的头尾链表存储结构第四章树和二叉树一．树、二叉树的定义二．二叉树1．二叉树的性质（5条）2．二叉树的存储结构：顺

7、序存储结构（按层序存放）链式存储结构（二叉链表、三叉链表）（空指针域的个数）3．遍历二叉树：先序、中序、后序、层序应用：给定二叉树的先序和中序（或后序和中序）序列，画出相应的二叉树4．线索二叉树：先序、中序、后序线索化Copyright©澤豬2012-05-16——杭州電子科技大學——一．树和森林1．树的存储结构：双亲表示法孩子表示法孩子-兄弟（二叉树）表示法2．树（森林）与二叉树的相互转换3．树的遍历：先根、后根次序遍历4．森林的遍历：先序、中序遍历二．赫夫曼树及其应用1．最优二叉树（赫夫曼树），求WPL2

8、．赫夫曼编码三．各种二叉树概念的区分1．满二叉树2．完全二叉树3．正则二叉树（严格二叉树）4．最优二叉树5．（折半查找的）判定树6．二叉排序树7．平衡二叉树8．堆四．二叉树有关的递归算法例：判断题：1.已知二叉树的先序序列和后序序列并不能唯一地确定这棵二叉树，因为不知道二叉树的根结点是哪一个。f2.一般二叉树的第i层上有2i-1个结点，深度为k的二叉树有2k-1个结点。f选择题：1.下列二叉树中，(