《数据结构》课程复习资料
选择题15分
填空题30分
简答题30分
综合体30分
主观题10分
第一章：数据结构概述（<15分）
1、掌握数据结构的定义:是指互相之间存在着一种或多种关系的数据元素的集合。
即数据结构三要素：数据的逻辑结构、存储结构、数据元素。
2、数据结构包括：逻辑结构和存储结构；
3、数据之间的关系：表（一对一之间的关系）、树（一对多之间的关系）、图（多对多之间的关系）；
4、算法的定义：是对特定问题求解步骤的一种描述，使指令的有限序列。
二叉树定义
算法衡量的标准：时间复杂度和空间复杂度；
5、算法时间复杂度的求法：给定一段程序，求其时间复杂度；
时间复杂度的比较：O(1)< O(log2  n)< O(n)< O(nlog2^n)< O(n^2)< O(n^3)< O(2^n)
6、为什么学习“数据结构”？
之所以要学习数据结构的原因如下：
(1)计算机处理的数据量越来越大；
（2）数据的类型越来越多；
（3）数据的结构越来越复杂。
“数据结构”课程主要学了哪些知识？
第二章：线性表(<10分)
1、线性表按照存储结构不同分为顺序表、链式表；
顺序表的特点：逻辑上相邻的两个元素在物理上也相邻；链式表的特点：逻辑上相邻的两个元素在物理上未必相邻；（“未必”的含义是可相邻也可以不相邻）
2、比较线性表顺序存储和链式存储的优缺点。
顺序存储有以下三个优点:
(1)方法简单，各种高级语言中都有数组，容易实现
（2）不用为表示结点间的逻辑关系而增加额外的存储开销
（3）顺序表具有按元素序号随机访问的特点
缺点：
（1）在顺序表中做插入、删除操作时，移动大量元素，效率低
（2）需要预先分配足够大的存储空间，过大过小都不好。
链表的优缺点恰好与顺序表相反。
第三章：栈和队列（<20分）
1、栈和队列的特点：栈：后进先出，队列：先进先出
2、熟悉栈和队列的基本操作：初始化栈、入栈操作、出栈操作、判断栈是否为空、取栈顶元素等。
如：经过InitQueue（Q）；EnQueue （Q,a）；EnQueue （Q,b）；  DeLQueue（Q,?）队头元素值是（ ）
如：ABC顺序进栈，则出栈的可能性有多少种？
3、根据实例，能够容易的判断出是栈的应用还是队列的应用？
栈的典型应用包括：进制转换，递归，表达式求值。
4、重点掌握栈的应用：进制转换算法的思想或程序。
思想：（1）若N>0,则将（N%R）压入栈S中，执行（2）,；若N=0，则将栈S的内容依次出栈，算法结束。
（2）N/R代替N，转向（1）。
程序：P(49)
第四章：数组（<10分）
1、牢记对称矩阵、三角矩阵、对角矩阵的特点：
对称矩阵：关于主对角线对称；
三角矩阵：上三角或下三角矩阵主对角线以下或以上均为同一个常数；
对角矩阵：以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条
对角线上的元素之外，其余元素均为0。
如：设n阶对称矩阵A采用下三角储存。Aij在储存时所对应的一维数组SA和k的关系（）。
掌握矩阵中的元素Aij与一维数组SA[K]的对应关系。
对称矩阵：K=I*(I+1)/2+J
三角矩阵:上三角：k=i*(2n-i+1)/2+j-i    当i<=j
                      K=n*(n+1)/2            当i>j
          下三角：k= i*(i+1)/2+j        当i>=j
                        K=n*(n+1)/2          当i<j
对角矩阵：k=2*i+j
2、掌握稀疏矩阵的三元组表示法。P（69）
第五章：串（<5分）
1、掌握上课介绍的9种函数名称:求串长，串拷贝，连接操作，串比较，求字串，字串定位，串插入，删除，串替换。
及其实现结果P（81）；
如：设字符串s=“I_am_a_ student！”，那么字符串s的长度为_____。
如：设字符串s1=“I_am”，s2=“a  Teacher”，则strconcat（s1，s2）=（ ）
第六章：树（<20分）
1、二叉树的5个性质:P(92)
(1)二叉树的第i（i>=1）层上最多有（2的i-1次方）个结点；
（2）在一棵深度为k的二叉树中，最多具有（2的k次方）-1个结点；
（3）对于一棵非空二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有：n0=n2+1。
（4）具有n个结点的完全二叉树的深度k为（log2^n取地板+1）。
（5）对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序队所有结点从1开始顺序编号，则对于任意的序号为i的结点有:
(1)若i=1，则该结点为根结点，无双亲；
（2）若i>1，则i结点的双亲为：（i/2的地板）
(3)若2i<=n，则i结点的左孩子为2i，否则没有左孩子；
（4）若2i+1<=n则i结点的右孩子为2i+1，否则没有右孩子；
（5）i结点所在层次为(log2 ^i去地板)+1
如：在具有n个结点完全二叉树中，结点i（i=1）的双亲结点是（  ）
如：对于高度为k的二叉树，其二叉树的结点的总数最多为______。
2、二叉树前序、中序和后序遍历，根据2种遍历结果求第3种遍历结果。
3、完全二叉树定义：当深度为k，含有n个节点的二叉树，当且仅当其每个结点编号与相应满二叉树结点顺序编号从1到n相互对应时，则称这个二叉树为完全二叉树。
满二叉树定义：一棵深度为k，且有（2的k次方）-1个结点的二叉树
哈弗曼树的定义：是指一类带权路径的最短的树。
4、给定一组叶子权值，求带权路径长度最小的多少？
如：设有一颗二叉树有4个结点a，b，c，d，分别带权7,5,2,4，其带权路径最短为为（    ）.
第七章：图（<20分）
1、掌握图的术语：无向完全图、有向完全图、顶点的度等；P（119）
如：n个顶点的无向完全图应该有边的条数为（ ）
如：在有向图中，一个顶点的度等于该项点的（ ）。
2、图的深度优先遍历和广度优先遍历；P（123）
3、图的邻接矩阵存储，给定一个图，求出邻接矩阵；或者给定一个邻接矩阵，构造图；P（120）
4、图的最小生成树；P（126）
第八章：查（<10分）
1、查的定义：在给定一组数据中对某个数值进行查询过程
静态查表：是由数据元素组成的线性表，其存储结构分为顺序存储和链式存储。不改变表的结构，只进行查操作。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。