2022年数据结构复习提纲计算机本科 .pdf

1 / 8 数据结构复习提纲 (大作业在后面) 计算机本科（ 2004 年 11 月）第一部分题型1单选题： 2 分 14=28 分2判断题： 1 分 10=10 分3填空题： 2 分 10=20 分4应用题： 8 分 4=32 分5程序题： 5 分 2=10 分第二部分复习提纲 ( 不分题型， 弄清原理，不要死记硬背) 1简单复杂性的判断：(1)i=n。while(i=1)i=i/2。其中 i=n,n/2,n/22, ,n/2k, 需 n/2k=1，即 2k=n，所以复杂性为O(log2n) (2)i=1。while(i=n) i=i+2。其中 i=1,3,5,(2k-1),需 2k-1=n ，则频度k=(n+1)/2，复杂性为O(n) (3)i=1。while(i=n) i=i*3。其中 i=1,3,32, ,3k, 需 3k=n，则频度k=log3n，复杂性为O(log3n) (4)i=1。while(i*i=n) i+。其中 i=1,2,3,k ，需 k2=n，则频度k=n1/2，复杂性为O(n1/2) 2四种基本存储方式的特点？什么时候逻辑关系可以由存储地址表示？什么时候由指针表示？什么时候存储地址与结点内容有关系？3逻辑结构、存储结构、运算、算法、算法复杂性等，哪些与计算机有关？无关？1顺序表、单链表的存储、插入、删除运算特点？是否可以随机存取？顺序存取？2单链表中插入结点的基本步骤？3有头结点、无头结点的循环、非循环单链表为空的条件分别是什么？4用尾指针表示循环单链表有什么好处？5例：删除顺序表中所有的正数，要求移动次数小。解：搜索顺序表，对每一个正数，先不删除，而是累计当前正数个数s，于是，对每个非正数，将它一次性前移 s 位。算法复杂性为O （n）。voiddels(sqlist *L) int s,i。s=0。/ 正数计数器for(i=0。in 。i+) if(L-datai0 s+。/ 累计当前正数else if(s0) L-datai-s=l-datai。/ 向前移动 s位L-n=L-n-s 。/ 调整表长 6例：将顺序表中所有负数移动到表的前端，要求移动次数小。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 8 页2 / 8 解：双向扫描：从前向后找一个正数，再从后向前找一个负数，然后交换两者位置。复杂性为O（n）。voidmoves(sqlist *L) int i,j。 datatype x。i=1 。j=L-n 。/ 删除 A1 到An 的所有零元素 , 设数组下标从 1开始 while(idatai0 & idataj=0 & ij) j- -。/ 从后向前找负数if(idatai。L-datai=L-dataj。L-dataj=x。/ 交换i+ 。j - 。 1链队列、链栈是否都有必要设置头结点？2循环队列Am 中，已知头指针、尾指针与元素个数中的任意两个，求另一个？队满条件？len=(rear-front+m)%m。rear=(front+len)%m。front=(rear-len+m)%m。队满： front=(rear+1)%m 3串长、空串、空白串、串连接、子串定位（模式匹配）等是何意？1稀疏矩阵、特殊矩阵的含义？为什么要对矩阵进行压缩存储？2三元组含义？一般矩阵按三元组存储能否节省空间？3广义表可分成几种？它们的图形表示特点如何？4例：从广义表A=(x,(a,b,c),y) 中取出原子b。在广义表中取某个元素，需要将该元素所在的子表逐步分离出来，直到所求的元素成为某个子表的表头，再用取表头运算取出。注意，最终取出某个元素时，不能用取表尾，因为它得到的是该元素组成的子表，而不是元素本身。本例的运算过程为取表尾tail(A)：得到 B=(a,b,c),y) 取表头head(B) ：得到 C=(a,b,c) 取表尾tail(C)：得到 D=(b,c) 取表头head(D) ：得到 b 总的过程为：head(tail(head(tail(A)。1树所有结点的度数之和与结点数有何关系？与边数有何关系？解：边数度数和结点数1。因为度数就是孩子数，而根不是孩子，故度数和比结点总数少1。2只有 3 个结点的二叉排序树有几种形态？解：有 5 种，见下图所示。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 8 页3 / 8 3二叉树是否是树的特殊情形？是否是有序树的特殊情形？解：都不是4树和二叉树的度有何特点？二叉树的度肯定为2 吗？解：二叉树每个结点最多两个孩子，即结点的度最大为2，但也可能所有结点的度都不为2，如只有1 个结点，或单枝树等，所以二叉树的度并不一定是2。5某完全二叉树有600 个结点，则叶子数有多少？度1 结点有多少？解：由层次编号规律，结点i的左孩子编号为2i ，若结点i为叶子，则它没有左孩子，即2in ，即in/2 300 的结点为叶子，叶子号为301，302， ,600 ，共 300 个。由于 n0=n2+1，现在 n0=300，所以 n2=299。另外，结点总数n=n0+n1+n2，所以 n1 6003002991 6二叉树每层只有一个结点，则高度为k 的二叉树有多少种？解：每种这样的二叉树只能有一个叶子，在最底层，而叶子可能有2k-1种情况，故有2k-1种。7完全二叉树有6个叶子，则结点总数就是11 吗？解：已知叶子数的完全二叉树一般有两棵，结点数差1，见下图：ABCDEFGHIJKABCDEFGHIJKL一般，结点数n n0n1 n2，而 n0n21( 二叉树性质 ) ，所以 n2n01 n1。完全二叉树树中度为1 的结点最多只有1 个，即 n11 或 0，所以 n2n0或 n2n01。8二叉树各结点在先、中、后序序列中的相对位置是否不变？解：若是叶子结点，则在先、中、后序序列中的相对位置不变，其它结点未必。9给定二叉树先、中、后序序列中的任意两个，是否就可还原出二叉树？解：若给定的是先序和后序，则由于不能确定根，也就不能还原出二叉树( 不唯一 ) 。10如何由先序中序、后序中序还原出二叉树？解：由遍历方法以下几点是显然的：对前序序列，序列的第一个点就是整个二叉树的根；对后序序列，序列的最后一个点就是整个二叉树的根；对中序序列，以根为界，序列的前一部分结点在根的左子树中，后一部分结点在根的右子树中；并且，由前一部分构成的子序列是左子树的中序序列，由后一部分构成的子序列是右子树的中序序列。若给定了前序和中序序列，反复利用上面的和，就可获得结点完整的逻辑信息，即由前序序列找到根，由中序序列得到左、右子树；再在对每个子树由前序序列找到子树的根，由中序序列得到子树的左、右子树，等等类推，每次都可得到一个点( 子树的根 ) ，从而逐渐获得树的全部信息，也就可以还原和构造出该二叉树。这个过程参见下图。中序遍历序列：左子树根右子树前序遍历序列：左子树根右子树根根pspeisiei例：已知二叉树的中序和后序序列分别为：BCDAFEHJIG 、DCBFJIHGEA ，画出该二叉树。解：由后序序列可知，整个二叉树的根为A，再从中序序列找到结点A，其左边为BCD ，对应A 的左子树，右边为FEHJIG，对应根的右子树。对每个子树进行同样分析即可画出此二叉树。比如对左子树BCD ，从原后序序列可找到它对应的后根序列为DCB ，于是左子树的根为B ，然后再由中序序列BCD可知 B的左子树为空，CD在 B的右子树，等等继续下去，直到每个结点都画出来。11完全二叉树的深度为1nlog2或1)(nlog2，是否是说深度有两种可能？精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 8 页4 / 8 解：只一种，它们的具体值相等。12树的常用存储方法有哪些？如何将树转换为二叉树？树的遍历与对应二叉树的遍历有何关系？13怎样知道线索二叉树某结点是否有左右孩子，是否为叶子？解：看结点的线索标志位，比如左线索标志位ltag=1则无左孩子，左右线索标志位都为1 则为叶子。14如何画中序、先序、后序线索二叉链表？线索二叉链表是否就没有空指针了？解：以中序线索二叉链表为例，下列二叉树的中序线索二叉链表如图所示。详细过程见课本。ABCDEFC11B00D11E01A00F11NULLNULL15线索二叉树上求结点的前趋和后继时，是否可不再需要遍历了？16什么是前缀码？17哈夫曼树如何构造？WPL 如何求？其结点总数可以为1000 吗？其中有度1结点吗？解：哈夫曼树的结点总数为2n-1 ，必为奇数，不可能为偶数。其中n 为叶子数。构造过程是每次两个结点合并，故不会出现度1 的结点。18例：求二叉树中度为1的结点数。解：设二叉树结点类型为bitree，函数名为sum1 ，函数返回结点数。int sum1(bitree t) int L,R。if(t=NULL) return 0。/ 当前树为空，递归出口L= sum1(t-lchild)。/ 求左子树中相应结点数R= sum1(t-rchild) / 求右子树中相应结点数if(t-lchild=NULL & t-rchild!=NULL) | (t-lchild!=NULL & t-rchild=NULL) / 当前结点度为也1 return L+R+1。 / 度 1 结点数 =左子树中度1 结点数 +右子树中度1 结点数 +1 else return L+R。 19例：求二叉树中度为2的结点数。解：设二叉树结点类型为bitree，函数名为sum2 ，函数返回结点数。int sum2(bitree t) int L,R。if(t=NULL) return 0。/ 当前树为空，递归出口L= sum1(t-lchild)。/ 求左子树中相应结点数R= sum1(t-rchild) / 求右子树中相应结点数if(t-lchild!=NULL & t-rchild!=NULL) / 当前结点度为也2 return L+R+1。 / 度 2 结点数 =左子树中度2 结点数 +右子树中度2 结点数 +1 else return L+R。 1图的 DFS和 BFS遍历分别用到什么数据结构？解：栈、队列精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 8 页5 / 8 2一个图有n 个顶点，则每个顶点的度最大是多少？解：对无向图，最大为n-1；对有向图，最大可为2(n-1) ，因为每个顶点到其余n-1 顶点都可有一条入边和出边。3连通图如果没有回路，则最多多少条边？多少条边后肯定有回路？解：无回路时，最多n1 条边，即生成树。4连通分量含义？连通图有多少连通分量？5强连通图至少多少条边？最多多少边？6度、出度、入度的概念和关系？7邻接矩阵、邻接表、逆邻接表的特点，如怎样求边数、出度、入度等？8生成树和最小生成树的概念，是否唯一？9什么时候不能拓扑排序？解：存在有向回路时不能。1为什么要对数据进行排序？排序算法可分为哪几类？2哪些排序思想或方法可用来找序列中前几个最大或最小？提示：堆排序、选择排序、快速排序( 基准位置为第几就是第几大) 3哪些排序方法的效率与序列的初始状态基本无关？有关？4哪些是稳定的？不稳定的？5各种排序算法的复杂度如何？6各种排序方法步骤如何？要会写每趟的结果。难点：快速排序、堆排序、希尔排序。7排序效率如何评价？关键字比较次数越少，排序就越快吗？解：除了关键字比较，还有关键字移动问题。如果移动次数多、结点内容又多，则排序时间也会较长。特别地，基数排序不需比较，但执行时间并不一定比需要比较的排序快。1200 个结点的有序表二分查找，最多比较次数如何？解：判定树的高度，1nlog22二叉排序树的形态与什么有关？解：取决于关键字输入顺序。3在 n 个结点的二叉排序树上查找，最多比较多少次？最少比较多少次？解：不超过树的高度，最大为n(此时为单枝树) 。4二叉排序树中删除一个结点后马上再插入，二叉树是否不变？解：若删除的是叶子，则不变。其它会变。5什么叫AVL树？特点？7B树、 B 树概念？如何识别？如何判断树的阶数？谁既可随机查找，又可顺序查找？8什么叫冲突？9线性探测法解决冲突时，同义词分布是否是连续的？10散列表的查找效率主要取决哪些因素？是否取决于关键字的个数？11在 10000 个结点中查找，肯定比在10 个结点中查找的平均时间慢吗？提示：如果采用散列方法组织数据，查找效率不直接取决于数据个数n。12例：已知关键字输入序列10,17,6,9,20 ，画出相应的二叉排序树，并求在等概率下查找成功和不成功时的平均查找长度。解：对应的二叉排序树见右图(插入过程见课本)。查找成功时平均查找长度为ASL=(1 12232)5=1152.2 查找不成功时有图中虚线所示的几种情况(即20) ，所以平均查找长度为ASLun=(2234)6=1662.67 153264精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 8 页6 / 8 注意这里指关键字比较，不包含空树的空指针比较。13例：在6 个结点的有序表中进行二分查找，在等概率下查找成功和不成功时的平均查找长度如何？。解：先画出6 个结点二分查找的判定树，右图。显然，如果要查找的点正好在第i 层，则经过i 次关键字的比较，对本题，每层的结点数分别为1、2、3 个，所以查找成功时平均查找长度为ASL (112233)61462.33 查找不成功时有图中虚线所示的7种情况(即KeyA6)，所以平均查找长度为ASLun(21 36)72072.86 注意这里指关键字比较，不包含空树的空指针比较。14例：对关键字序列11,78,10,1,3,2,4,21构造散列表，取散列地址为HT0.10，散列函数为H(K)K 11，试用线性探查法冲突，画出相应的闭散列表，并分别求查找成功和不成功时的平均查找长度。解：首先求出散列地址，见下图(a)，据此得到闭散列表见下图(b)。查找成功的平均比较次数为：ASL(112 1328l) 82.375 查找不成功的平均查找长度为：ASLunsucc (8 76543 21119) 114.273 14例：对关键字序列11,78,10,1,3,2,4,21构造散列表，取散列地址为HT0.10，散列函数为H(K)K 11，试用拉链法解决冲突，画出相应的开散列表，并分别求查找成功和不成功时的平均查找长度。解：散列地址同上题，开散列表分别见下图(c)。查找成功的平均比较次数为：ASL(1 622) 8l.25 查找不成功的平均查找长度为：ASLunsucc (1 21110 00002) 110.727 01783成功比较次数11关键字 K1010散列地址 K1111218231(a)(b)3456789101201110211散列表(c)78124312410213244100123781HTkeynext4567389成功比较次数101112不成功比较次数 11100000221221不成功比较次数87692341115第三部分数据结构大作业题目：排序算法改进综合实验1实现基本排序方法：直接插入、希尔、直接选择、冒泡、快速、堆、二路归并；2对每种基本排序方法尽量给出改进算法；3给出改进前后的实验结果：61710920精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 8 页7 / 8 （1）随机生成若干个随机数进行排序（如n103，2103，104，等），记录每个排序的时间耗费。（2）分别给出正序和反序的初始序列进行排序（如n104），检验算法对初始序列的敏感程度。（ 3）给出实验结果、原因分析、结论等（如改进效果明显或不明显的原因？算法的实际时间增长速度如何？复杂性相当的算法之间快慢如何？等等）（4）所有实验结果汇集成一张表，参考格式如下：计算条件：CPU ：（如AMD XP2000+,P4 2.0A 等，不要超频）内存：（如HY DDR333512M等，不要超频）主板：（如牌型号）操作系统：（如Windows 98,Windows XP 等）编译软件：（如VC 6.0 等）其它：(对计算结果有影响的需要说明的软、硬件情况) 4注意事项：（1） 不接受以前布置的大作业题目。（2）使用标准C或 C+ 语言，不要采用开发工具；（3）独立完成，不要互相抄袭，否则记0 分。（4）伪造实验数据者，记0 分。（ 5）各种算法的改进要尽量有、尽量多些（可分析效率低的原因、存在的问题等有针对性地改进，比如直接选择排序当初始序列已经有序时仍要执行n-1趟，是没有必要的），如果只有基本算法，而几乎没有改进算法，则做得再好，也没有高分。（6）汇总表中规模n 的大小不一定取103105，可根据自己的计算机情况调整和增加，以使排序时间不要太小或太大。若有的算法时间太长( 如大于 10 分钟 ) ，可中途终止，并在汇总表中注明。排序算法实验比较(单位：秒 ) n 方法1032*1031042*1041052*105105正序逆序直接插入排序改进 1 改进 2 冒泡排序改进 1 改进 2 直接选择排序改进 1 改进 2 Shell排序改进 1 改进 2 快速排序改进 1 改进 2 归并排序改进 1 改进 2 堆排序改进 1 改进 2 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 8 页8 / 8 （7）各个教案点的作业，集中后上交，其中的盘可以集中刻录到一张光盘上（并自留备份）（ 8）作业上交形式：纸质文档盘。其中，文档部分不是程序的使用说明书，也 不是程序的简单打印，要比较详细地讲明算法原理和方法，程序部分要有必要的注释。盘上要有所有的程序和纸质文档的电子原文（如word 文件）。（9）文档可以双面打印，字号和行距不要太大，如5 号字和单行间距就可。（10）不要在同一张盘上存放其它作业！（如操作系统、数据库等）（11）下学期开学第2 周交。（12）文档开头写明：教案点：学号：姓名：email ：电话：附录：参考知识1排序时间：由clock()函数得到时钟数，排序前后的时钟数之差每秒的时钟数，即得时间（秒）#include InsertSort(R,n)。 t2=clock()。 cout时间： float(t2-t1)/CLK_TCKendl。2随机数的生成#include for(i=1。i=n 。i+) Ri.key=rand()。/ 生成 0-RAND_MAX 之间的随机数但 rand() 只生成0-RAND_MAX（一般为65535）之间的随机数。当问题规模n 较大时，将生成很多重复的随机数。比较合适的方法是生成0n 之间的随机数，这要用random(int num)函数。它可生成0任意数 num之间的随机数。但该函数在VC 中没有定义，可自己定义如下：int random(int num) return rand()*num/(RAND_MAX+1)。 for(i=1。i=n 。i+) Ri.key=random(n)。/ 生成 0-n 之间的随机数3各个算法单独运行会很繁，可分别调通后编一个菜单程序集中起来。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 8 页