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

《2022年数据结构复习提纲计算机本科.docx》由会员分享，可在线阅读，更多相关《2022年数据结构复习提纲计算机本科.docx（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 数据结构 复习提纲 大作业在后面 运算机本科（ 2004 年 11 月）第一部分 题型1单项题： 2 分 14=28 分2判定题： 1 分 10=10 分3填空题： 2 分 10=20 分4应用题： 8 分 4=32 分5程序题： 5 分 2=10 分其次部分复习提纲 不分题型, 弄清原理,不要死记硬背 1简洁复杂性的判定：1i=n；whilei=1i=i/2；其中 i=n,n/2,n/2 2, ,n/2 k, 需 n/2 k=1,即 2 k=n,所以复杂性为 Olog 2n 2i=1；whilei=n i=i+2；其中 i=1,3,5, ,2

2、k-1, 需 2k-1=n ,就频度 k=n+1/2,复杂性为 On 3i=1；whilei=n i=i*3；其中 i=1,3,3 2, ,3 k, 需 3 k=n,就频度 k=log 3n,复杂性为 Olog3n 4i=1；whilei*i=n i+；其中 i=1,2,3, ,k ,需 k 2=n,就频度 k=n 1/2,复杂性为 On 1/2 2四种基本储备方式的特点？什么时候规律关系可以由储备地址表示？什么时候由指针表示？什么时候储备地址与结点内容有关系？3规律结构、储备结构、运算、算法、算法复杂性等,哪些与运算机有关？无关？1次序表、单链表的储备、插入、删除运算特点？是否可以随机存取？

3、次序存取？2单链表中插入结点的基本步骤？3有头结点、无头结点的循环、非循环单链表为空的条件分别是什么？4用尾指针表示循环单链表有什么好处？5例：删除次序表中全部的正数,要求移动次数小；解：搜寻次序表,对每一个正数,先不删除,而是累计当前正数个数 性前移 s 位；算法复杂性为 O（n）；voiddelssqlist *L int s,i；s,于是,对每个非正数,将它一次s=0；/ 正数计数器fori=0；in ；i+ ifL-datai0 s+；/ 累计当前正数else ifs0 L-datai-s=l-datai；/ 向前移动 s位L-n=L-n-s ；/ 调整表长 6例：将次序表中全部负数移

4、动到表的前端,要求移动次数小；1 / 8 名师归纳总结 - - - - - - -第 1 页,共 8 页精选学习资料 - - - - - - - - - 解：双向扫描：从前向后找一个正数,再从后向前找一个负数,然后交换两者位置；复杂性为 O（n）；voidmovessqlist *L int i,j；/ 删除 A1 到An 的全部零元素 , 设数组 datatype xi=1 ；j=L-n ；下标从 1开头 whileidatai0 & idataj=0 & ij j- -；/ 从后向前找负数ifidatai；L-datai=L-dataj；L-dataj=x；/ 交换i+ ；j - ； 1链

5、队列、链栈是否都有必要设置头结点？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；在广义表中取某个元素,需要将该元素所在的子表逐步分别出来,直到所求的元素成

6、为某个子表的表头,再用取表头运算取出；留意,最终取出某个元素时,不能用取表尾,由于它得到的是该元素组成 的子表,而不是元素本身；本例的运算过程为取表尾 tailA：得到 B=a,b,c,y 取表头 headB ：得到 C=a,b,c 取表尾 tailC：得到 D=b,c 取表头 headD ：得到 b 总的过程为： headtailheadtailA；1树全部结点的度数之和与结点数有何关系？与边数有何关系？解：边数度数和结点数1；由于度数就是孩子数,而根不是孩子,故度数和比结点总数少1；2只有 3 个结点的二叉排序树有几种形状？解：有 5 种,见下图所示；2 / 8 名师归纳总结 - - -

7、- - - -第 2 页,共 8 页精选学习资料 - - - - - - - - - 3二叉树是否是树的特殊情形？是否是有序树的特殊情形？解：都不是4树和二叉树的度有何特点？二叉树的度确定为 2 吗？解：二叉树每个结点最多两个孩子,即结点的度最大为 2,但也可能全部结点的度都不为 2,如只有 1 个结点,或单枝树等,所以二叉树的度并不肯定是 2；5某完全二叉树有 600 个结点,就叶子数有多少？度 1 结点有多少？解：由层次编号规律,结点 i 的左孩子编号为 2i ,如结点 i 为叶子,就它没有左孩子,即 2in ,即in/2 300 的结点为叶子,叶子号为301,302, ,600 ,共 3

8、00 个；由于 n0=n2+1,现在 n0=300,所以 n2=299；另外,结点总数n=n0+n1+n2,所以 n1 6003002991 1 的6二叉树每层只有一个结点,就高度为k 的二叉树有多少种？2 k-1 种情形,故有2k-1 种；解：每种这样的二叉树只能有一个叶子,在最底层,而叶子可能有7完全二叉树有6 个叶子,就结点总数就是11 吗？解：已知叶子数的完全二叉树一般有两棵,结点数差1,见下图：AABCBCDEFGDEFGHIJKHIJKL一般,结点数n n0n1 n2,而 n0n21 二叉树性质 ,所以 n2n01 n1；完全二叉树树中度为结点最多只有1 个,即 n11 或 0,所

9、以 n2n0或 n2n 01；8二叉树各结点在先、中、后序序列中的相对位置是否不变？解：如是叶子结点,就在先、中、后序序列中的相对位置不变,其它结点未必；9给定二叉树先、中、后序序列中的任意两个,是否就可仍原出二叉树？解：如给定的是先序和后序,就由于不能确定根,也就不能仍原出二叉树 不唯独 ；10如何由先序中序、后序中序仍原出二叉树？解：由遍历方法以下几点是明显的：对前序序列,序列的第一个点就是整个二叉树的根；对后序序列,序列的最终一个点就是整个二叉树的根；对中序序列,以根为界,序列的前一部分结点在根的左子树中,后一部分结点在根的右子树中；并且,由前一部分构成的子序列是左子树的中序序列,由后一

10、部分构成的子序列是右子树的中序序列；如给定了前序和中序序列,反复利用上面的和,就可获得结点完整的规律信息,即由前序序列 找到根,由中序序列得到左、右子树；再在对每个子树由前序序列找到子树的根,由中序序列得到子树的左、右子树,等等类推,每次都可得到一个点 原和构造出该二叉树；这个过程参见下图； 子树的根 ,从而逐步获得树的全部信息,也就可以仍前序遍历序列：根根左子树根根右子树peps中序遍历序列：is左子树右子树iei例：已知二叉树的中序和后序序列分别为：BCDAFEHJIG、DCBFJIHGEA,画出该二叉树；解：由后序序列可知,整个二叉树的根为 A,再从中序序列找到结点 A,其左边为 BCD

11、,对应 A 的左子树,右边为 FEHJIG,对应根的右子树；对每个子树进行同样分析即可画出此二叉树；比如对左子树BCD,从原后序序列可找到它对应的后根序列为 DCB,于是左子树的根为 B,然后再由中序序列 BCD可知 B的左子树为空,CD在 B的右子树,等等连续下去,直到每个结点都画出来；11完全二叉树的深度为 log 2 n 1 或 log 2 n 1,是否是说深度有两种可能？3 / 8 名师归纳总结 - - - - - - -第 3 页,共 8 页精选学习资料 - - - - - - - - - 解：只一种,它们的具体值相等；12树的常用储备方法有哪些？如何将树转换为二叉树？树的遍历与对应

12、二叉树的遍历有何关系？13怎样知道线索二叉树某结点是否有左右孩子,是否为叶子？解：看结点的线索标志位,比如左线索标志位ltag=1就无左孩子,左右线索标志位都为1 就为叶子；14如何画中序、先序、后序线索二叉链表？线索二叉链表是否就没有空指针了？解：以中序线索二叉链表为例,以下二叉树的中序线索二叉链表如下列图；具体过程见课本；0A0ADBEC1D10B01E01C1NULLNULLF1F115线索二叉树上求结点的前趋和后继时,是否可不再需要遍历了？16什么是前缀码？17哈夫曼树如何构造？WPL 如何求？其结点总数可以为 1000 吗？其中有度 1 结点吗？解：哈夫曼树的结点总数为 2n-1 ,

13、必为奇数,不行能为偶数；其中 n 为叶子数；构造过程是每次两个结点合并,故不会显现度 1 的结点；18例：求二叉树中度为 1 的结点数；解：设二叉树结点类型为 bitree,函数名为 sum1,函数返回结点数；int sum1bitree t int L,R；/ 当前树为空,递归出口ift=NULL return 0L= sum1t-lchild/ 求左子树中相应结点数R= sum1t-rchild / 求右子树中相应结点数ift-lchild=NULL & t-rchild.=NULL | t-lchild.=NULL & t-rchild=NULL / 当前结点度为也1 return L+

14、R+1； / 度 1 结点数 =左子树中度1 结点数 +右子树中度1 结点数 +1 else return L+R； 19例：求二叉树中度为2 的结点数；sum2,函数返回结点数；解：设二叉树结点类型为bitree,函数名为int sum2bitree t int L,R；ift=NULL return 0；/ 当前树为空,递归出口L= sum1t-lchild；/ 求左子树中相应结点数R= sum1t-rchild / 求右子树中相应结点数ift-lchild.=NULL & t-rchild.=NULL / 当前结点度为也 2 return L+R+1； / 度 2 结点数 =左子树中度

15、2 结点数 +右子树中度 2 结点数 +1 else return L+R； 1图的 DFS和 BFS遍历分别用到什么数据结构？解：栈、队列4 / 8 名师归纳总结 - - - - - - -第 4 页,共 8 页精选学习资料 - - - - - - - - - 2一个图有 n 个顶点,就每个顶点的度最大是多少？解：对无向图,最大为n-1 ；对有向图,最大可为2n-1 ,由于每个顶点到其余n-1 顶点都可有一条入边和出边；3连通图假如没有回路,就最多多少条边？多少条边后确定有回路？解：无回路时,最多 n1 条边,即生成树；4连通重量含义？连通图有多少连通重量？5强连通图至少多少条边？最多多少边

16、？6度、出度、入度的概念和关系？7邻接矩阵、邻接表、逆邻接表的特点,如怎样求边数、出度、入度等？8生成树和最小生成树的概念,是否唯独？9什么时候不能拓扑排序？解：存在有向回路时不能；1为什么要对数据进行排序？排序算法可分为哪几类？2哪些排序思想或方法可用来找序列中前几个最大或最小？提示：堆排序、挑选排序、快速排序 基准位置为第几就是第几大 3哪些排序方法的效率与序列的初始状态基本无关？有关？4哪些是稳固的？不稳固的？5各种排序算法的复杂度如何？6各种排序方法步骤如何？要会写每趟的结果；难点：快速排序、堆排序、希尔排序；7排序效率如何评判？关键字比较次数越少,排序就越快吗？解：除了关键字比较,仍

17、有关键字移动问题；假如移动次数多、结点内容又多,就排序时间也会较长；特殊地,基数排序不需比较,但执行时间并不肯定比需要比较的排序快；1200 个结点的有序表二分查找,最多比较次数如何？解：判定树的高度,log 2n12二叉排序树的形状与什么有关？解：取决于关键字输入次序；3在 n 个结点的二叉排序树上查找,最多比较多少次？最少比较多少次？解：不超过树的高度,最大为 n 此时为单枝树 ；4二叉排序树中删除一个结点后立刻再插入,二叉树是否不变？解：如删除的是叶子,就不变；其它会变；5什么叫 AVL树？特点？7B 树、 B树概念？如何识别？如何判定树的阶数？谁既可随机查找,又可次序查找？8什么叫冲突

18、？9线性探测法解决冲突时,同义词分布是否是连续的？10散列表的查找效率主要取决哪些因素？是否取决于关键字的个数？11在 10000 个结点中查找,确定比在10 个结点中查找的平均时间慢吗？提示：假如采纳散列方法组织数据,查找效率不直接取决于数据个数 n；12例：已知关键字输入序列 10,17,6,9,20 ,画出相应的二叉排序树,并求在等概率下查找胜利和不成功时的平均查找长度；解：对应的二叉排序树见右图插入过程见课本；查找胜利时平均查找长度为123456ASL=1 12 23 25=1152.2 查找不胜利时有图中虚线所示的几种情形即20 ,所以平均查找长度为ASL un=2 23 46=16

19、62.67 5 / 8 名师归纳总结 - - - - - - -第 5 页,共 8 页精选学习资料 - - - - - - - - - 留意这里指关键字比较,不包含空树的空指针比较；13例：在 6 个结点的有序表中进行二分查找,在等概率下查找胜利和不胜利时的平均查找长度如何？；解：先画出6 个结点二分查找的判定树,右图；明显,假如要查找的点正好在第i 层,就经过i 次关键字的比较,对此题,每层的结点数分别为1、2、3 个,所以查找胜利时平均查找长度为ASL 1 12 23 361462.33 所示的7种情况即69101720查找不成功时有图中虚线KeyA6,所以平均查找长度为ASL un2 1

20、 3 672072.86 留意这里指关键字比较,不包含空树的空指针比较；14例：对关键字序列11,78,10,1,3,2,4,21构造散列表,取散列地址为HT0.10,散列函数为HKK 11,试用线性探查法冲突,画出相应的闭散列表,并分别求查找胜利和不胜利时的平均查找长度；解：第一求出散列地址,见下图a,据此得到闭散列表见下图b；查找胜利的平均比较次数为：ASL1 12 1328l 82.375 查找不胜利的平均查找长度为：ASLunsucc 8 76543 21119 114.273 14例：对关键字序列11,78,10,1,3,2,4,21构造散列表,取散列地址为HT0.10,散列函数为H

21、KK 11,试用拉链法解决冲突,画出相应的开散列表,并分别求查找胜利和不胜利时的平均查找长度；解：散列地址同上题,开散列表分别见下图 c ；查找胜利的平均比较次数为：ASL1 62 2 8l.25 查找不胜利的平均查找长度为：ASLunsucc 1 21110 00002 110.727 关键字 K01117810153284921HTkeynext1不胜利比较次数 011178210110132410散列地址 K11221a331267104413450散列表11781324211110610210胜利比较次数11213281170不胜利比较次数8765432980b90102胜利比较次数1

22、2c第三部分 数据结构大作业题目：排序算法 改进 综合试验1实现基本排序方法：直接插入、希尔、直接挑选、冒泡、快速、堆、二路归并；2对每种基本排序方法尽量给出改进算法；3给出改进前后的试验结果：6 / 8 名师归纳总结 - - - - - - -第 6 页,共 8 页精选学习资料 - - - - - - - - - （1）随机生成如干个随机数进行排序（如n103,2103,104, 等）,记录每个排序的时间耗费；（2）分别给出正序和反序的初始序列进行排序（如n104）,检验算法对初始序列的敏锐程度；（ 3）给出试验结果、缘由分析、结论等（如改进成效明显或不明显的缘由？算法的实际时间增长速度如排

23、序算法试验比较单位：秒 1042*1041052*105正序105 n 1032*103方法逆序直接插入排序 改进 1 改进 2 冒泡排序 改进 1 改进 2 直接挑选排序 改进 1 改进 2 Shell 排序 改进 1 改进 2 快速排序 改进 1 改进 2 归并排序 改进 1 改进 2 堆排序 改进 1 改进 2 何？复杂性相当的算法之间快慢如何？等等）（4）全部试验结果聚集成一张表,参考格式如下：运算条件：CPU：（如 AMD XP2000+,P4 2.0A 等,不要超频）内存：（如 HY DDR333512M等,不要超频）主板：（如牌型号）操作系统：（如 Windows 98,Wind

24、ows XP 等）编译软件：（如 VC 6.0 等）其它： 对运算结果有影响的需要说明的软、硬件情形 4留意事项：（1） 不接受以前布置的大作业题目；（2）使用标准 C或 C+语言,不要采纳开发工具；（3）独立完成,不要相互抄袭,否就记 0 分；（4）伪造试验数据者,记 0 分；（ 5）各种算法的改进要尽量有、尽量多些（可分析效率低的缘由、存在的问题等有针对性地改进,比如直接挑选排序起初始序列已经有序时仍要执行n-1趟,是没有必要的）,假如只有基本算法,而几乎没有改进算法,就做得再好,也没有高分；（6）汇总表中规模n 的大小不肯定取10 3105,可依据自己的运算机情形调整和增加,以使排序时间

25、不要太小或太大；如有的算法时间太长 如大于 10 分钟 ,可中途终止,并在汇总表中注明；7 / 8 名师归纳总结 - - - - - - -第 7 页,共 8 页精选学习资料 - - - - - - - - - （7）各个教案点的作业,集中后上交,其中的盘可以集中刻录到一张光盘上（并自留备份）（ 8）作业上交形式：纸质文档盘；其中,文档部分不是程序的使用说明书,也 不是程序的简洁打印,要比较具体地讲明算法原理和方法,程序部分要有必要的注释；盘上要有全部的程序和纸质文档的电子原文（如 word 文件）；（9）文档可以双面打印,字号和行距不要太大,如5 号字和单行间距就可；（10）不要在同一张盘上

26、存放其它作业！（如操作系统、数据库等）（11）下学期开学第 2 周交；（12）文档开头写明：教案点：学号：姓名：email ：电话：附录：参考学问1排序时间：由clock函数得到时钟数,排序前后的时钟数之差每秒的时钟数,即得时间（秒）#include InsertSortR,n； t2=clock； cout 时间： floatt2-t1/CLK_TCKendl；2随机数的生成#include fori=1；i=n ；i+ Ri.key=rand；/ 生成 0-RAND_MAX之间的随机数但 rand 只生成 0-RAND_MAX（一般为 65535）之间的随机数；当问题规模 n 较大时,将生成许多重复的随机数；比较合适的方法是生成 0n 之间的随机数,这要用 randomint num 函数；它可生成 0任意数 num之间的随机数；但该函数在VC中没有定义,可自己定义如下：int randomint num return rand*num/RAND_MAX+1； fori=1；i=n ；i+ Ri.key=randomn；/ 生成 0-n 之间的随机数3各个算法单独运行会很繁,可分别调通后编一个菜单程序集中起来；8 / 8 名师归纳总结 - - - - - - -第 8 页,共 8 页