清华大学新版数据结构考研要点(新版).doc
《清华大学新版数据结构考研要点(新版).doc》由会员分享,可在线阅读,更多相关《清华大学新版数据结构考研要点(新版).doc(29页珍藏版)》请在咨信网上搜索。
1、1、数据(Data) :是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素(Data Element) :是数据的基本单位,在程序中通常作为一个整体来进行考虑和处理。一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。 数据对象(Data Object):是性质相同的数据元素的集合,是数据的一个子集。如字符集合C=A,B,C, 。数据结构(Data Structure):是指相互之间具有(存在)一定联系(关系)的数据元素
2、的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型,如图1-3所示。 集合:结构中的数据元素除了“同属于一个集合”外,没有其它关系。 线性结构:结构中的数据元素之间存在一对一的关系。 树型结构:结构中的数据元素之间存在一对多的关系。 图状结构或网状结构:结构中的数据元素之间存在多对多的关系。2、顺序结构:数据元素存放的地址是连续的; 链式结构:数据元素存放的地址是否连续没有要求。数据的逻辑结构和物理结构是密不可分的两个方面,一个算法的设计取决于所选定的逻辑结构,而算法的实现依赖于所采用的存储结构。 在C语言中,用一维数组表示顺序存储结构;用结构体
3、类型表示链式存储结构。3、C语言中用带指针的结构体类型来描述typedef struct Lnode ElemType data; /*数据域,保存结点的值 */struct Lnode *next; /*指针域*/LNode; /*结点的类型 */4、循环队列为空:front=rear 。 循环队列满:(rear+1)%MAX_QUEUE_SIZE =front。5、性质1:在非空二叉
4、树中,第i层上至多有2i-1个结点(i1)。性质2:深度为k的二叉树至多有2k-1个结点(k1) 。性质3:对任何一棵二叉树,若其叶子结点数为n0,度为2的结点数为n2,则n0=n2+1。一棵深度为k且有2k-1个结点的二叉树称为满二叉树(Full Binary Tree)。完全二叉树的特点:若完全二叉树的深度为k ,则所有的叶子结点都出现在第k层或k-1层。对于任一结点,如果其右子树的最大层次为l,则其左子树的最大层次为l或l+1。性质4:n个结点的完全二叉树深度为:2n +1。性质5:若对一棵有n个结点的完全二叉树(深度为2n+1)的结点按层(从第1层到第2n +1层)序自左至右进行编号,
5、则对于编号为i(1in)的结点: 若i=1:则结点i是二叉树的根,无双亲结点;否则,若i>1,则其双亲结点编号是 i/2 。 如果2i>n:则结点i为叶子结点,无左孩子;否则,其左孩子结点编号是2i。 如果2i+1>n:则结点i无右孩子;否则,其右孩子结点编号是2i+1。6、线索二叉树:设一棵二叉树有n个结点,则有n-1条边(指针连线) , 而n个结点共有2n个指针域(Lchild和Rchild) ,显然有n+1个空闲指针域未用。则可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息。7、Huffman树:具有n个叶子结点(每个结点的权值为wi) 的二叉树不止一棵,但在
6、所有的这些二叉树中,必定存在一棵WPL值最小的树,称这棵树为Huffman树(或称最优树) 。8、完全无向图:对于无向图,若图中顶点数为n ,用e表示边的数目,则e 0,n(n-1)/2 。具有n(n-1)/2条边的无向图称为完全无向图。完全有向图:对于有向图,若图中顶点数为n ,用e表示弧的数目,则e0,n(n-1) 。具有n(n-1)条边的有向图称为完全有向图。生成树、生成森林:一个连通图(无向图)的生成树是一个极小连通子图,它含有图中全部n个顶点和只有足以构成一棵树的n-1条边,称为图的生成树关于无向图的生成树的几个结论: 1) 一棵有n个顶点的生成树有且仅有n-1条边;2) 如果一个图
7、有n个顶点和小于n-1条边,则是非连通图;3) 如果多于n-1条边,则一定有环; 4) 有n-1条边的图不一定是生成树。9、最小生成树(Minimum Spanning Tree) :带权连通图中代价最小的生成树称为最小生成树。 最小生成树在实际中具有重要用途,如设计通信网。设图的顶点表示城市,边表示两个城市之间的通信线路,边的权值表示建造通信线路的费用。n个城市之间最多可以建n(n-1)/2条线路,如何选择其中的n-1条,使总的建造费用最低?10、工程完成最短时间:从起点到终点的最长路径长度(路径上各活动持续时间之和) 。长度最长的路径称为关键路径,关键路径上的活动称为关键活动。关键活动是影
8、响整个工程的关键。 11、查找方法比较顺序查找折半查找分块查找ASL最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表12、在随机情况下,二叉排序树的平均查找长度ASL和(n)(树的深度)是等数量级的。二叉排序树(Binary Sort Tree或Binary Search Tree) 的定义为:二叉排序树或者是空树,或者是满足下列性质的二叉树。(1) :若左子树不为空,则左子树上所有结点的值(关键字)都小于根结点的值;(2) :若右子树不为空,则右子树上所有结点的值(关键字)都大于根结点的值;(3) :左、右子树都分别是二叉排序树
9、。结论:若按中序遍历一棵二叉排序树,所得到的结点序列是一个递增序列。13、平衡二叉树或者是空树,或者是满足下列性质的二叉树。:左子树和右子树深度之差的绝对值不大于1;:左子树和右子树也都是平衡二叉树。 平衡因子(Balance Factor) :二叉树上结点的左子树的深度减去其右子树深度称为该结点的平衡因子。平衡二叉排序树上进行查找的平均查找长度和2n是一个数量级的,平均时间复杂度为O(2n)。四种平衡化旋转,其正确性容易由“遍历所得中序序列不变”来证明。并且,无论是哪种情况,平衡化旋转处理完成后,形成的新子树仍然是平衡二叉排序树,且其深度和插入前以a为根结点的平衡二
10、叉排序树的深度相同。所以,在平衡二叉排序树上因插入结点而失衡,仅需对失衡子树做平衡化旋转处理。14、一棵m阶B_树,或者是空树,或者是满足以下性质的m叉树: 根结点或者是叶子,或者至少有两棵子树,至多有m棵子树; 除根结点外,所有非终端结点至少有m/2棵子树,至多有m棵子树; 所有叶子结点都在树的同一层上; 每个结点应包含如下信息: (n,A0,K1,A1,K2,A2, ,Kn,An)其中Ki(1in)是关键字,且Ki<Ki+1 (1in-1);Ai(i=0,1, ,n)为指向孩子结点的指针,且Ai-1所指向的子树中所有结点的关键字都小于Ki ,
11、Ai所指向的子树中所有结点的关键字都大于Ki ;n是结点中关键字的个数,且m/2-1nm-1,n+1为子树的棵数。根据m阶B_树的定义,第一层上至少有1个结点,第二层上至少有2个结点;除根结点外,所有非终端结点至少有m/2棵子树,第h层上至少有m/2h-2个结点。在这些结点中:根结点至少包含1个关键字,其它结点至少包含m/2-1个关键字,设s=m/2,则总的关键字数目n满足:因此有: h1+ s(n+1)/2)=1+m/2(n+1)/2) 即在含有n个关键字的B_树上进行查找时,从根结点到待查找记录关键字的结点的路径上所涉及的结点数不超过1
12、+ m/2(n+1)/2) 。15、m阶B+树。 它与B_树的主要不同是叶子结点中存储记录。在B+树中,所有的非叶子结点可以看成是索引,而其中的关键字是作为“分界关键字”,用来界定某一关键字的记录所在的子树。一棵m阶B+树与m阶B_树的主要差异是: 若一个结点有n棵子树,则必含有n个关键字; 所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针,而且叶子结点按关键字的大小从小到大顺序链接; 所有的非叶子结点可以看成是索引的部分,结点中只含有其子树的根结点中的最大(或最小)关键字。16、哈希函数:在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。哈希函数是一
13、种映象,是从关键字空间到存储地址空间的一种映象。可写成:addr(ai)=H(ki) ,其中i是表中一个元素,addr(ai)是ai的地址, ki是ai的关键字。哈希表:应用哈希函数,由记录的关键字确定记录在表中的地址,并将记录放入此地址,这样构成的表叫哈希表。哈希查找(又叫散列查找):利用哈希函数进行查找的过程叫哈希查找。例1 :设散列表长为7,记录关键字组为:15, 14, 28, 26, 56, 23,散列函数:H(key)=key MOD 7,冲突处理采用线性探测法。解:H(15)=15 MOD 7=1 &
14、nbsp; H(14)=14 MOD 7=0 H(28)=28 MOD 7=0 冲突 H1(28)=1 又冲突H2(28)=2 H(26)=26 MOD 7=5 H(56)=56 MOD 7=0 冲突 H1(56)=1 又冲突H2(56)=2 又冲突 H3(56)=3 H(23)=23 MOD
15、7=2 冲突 H1(23)=3 又冲突H3(23)=4各种散列函数所构造的散列表的ASL如下: 17、排序的稳定性 若记录序列中有两个或两个以上关键字相等的记录: Ki =Kj(ij,i, j=1, 2, n),且在排序前Ri先于Rj(i<j),排序后的记录序列仍然是Ri先于Rj,称排序方法是稳定的,否则是不稳定的。排序的分类 待排序的记录数量不同,排序过程中涉及的存储器的不同,有不同的排序分类。 待排序的记录数不太多:所有的记录都能存放在内
16、存中进行排序,称为内部排序; 待排序的记录数太多:所有的记录不可能存放在内存中, 排序过程中必须在内、外存之间进行数据交换,这样的排序称为外部排序。18、插入排序采用的是以 “玩桥牌者”的方法为基础的。即在考察记录Ri之前,设以前的所有记录R1, R2 ,., Ri-1已排好序,然后将Ri插入到已排好序的诸记录的适当位置。=最基本的插入排序是直接插入排序(Straight Insertion Sort) 。 最好情况:若待排序记录按关键字从小到大排列(正序),算法中的内循环无须执行,则一趟排序时:关键字比较次数1次,记录移动次数2次 最坏情况:若待排序记录按关键字从大到小排列(逆序
17、),则一趟排序时:算法中的内循环体执行i-1,关键字比较次数i次,记录移动次数i+1。一般地,认为待排序的记录可能出现的各种排列的概率相同,则取以上两种情况的平均值,作为排序的关键字比较次数和记录移动次数,约为n2/4,则复杂度为O(n2) 。算法实现void straight_insert_sort(Sqlist *L) int i, j ;for (i=2; i<=l->length; i+) L->R0=L->Ri; j=i-1; /* 设置哨兵 */while( LT(L->R
18、0.key, L->Rj.key) ) L->Rj+1=L->Rj; j-; /* 查找插入位置 */L->Rj+1=L->R0; /* 插入到相应位置 */ =折半插入排序当将待排序的记录Ri 插入到已排好序的记录子表R1i-1中时,由于R1, R2 , Ri-1已排好序,则查
19、找插入位置可以用“折半查找”实现,则直接插入排序就变成为折半插入排序。从时间上比较,折半插入排序仅仅减少了关键字的比较次数,却没有减少记录的移动次数,故时间复杂度仍然为O(n2) 。排序示例:设有一组关键字30, 13, 70, 85, 39, 42, 6, 20,采用折半插入排序方法排序的过程 算法实现 void Binary_insert_sort(Sqlist *L) int i, j, low, high, mid ;for (i=2; i<=l->length; i+) L->R0=L->Ri;
20、/* 设置哨兵 */ low=1 ; high=i-1 ; while (low<=high) if="" l-="">R0.key, L->Rmid.key) ) high=mid-1 ; else low=mid+1 ; /* 查找插入位置 &nbs
21、p; */for (j=i-1; j>=high+1; j-)L->Rj+1=L->Rj; L->Rhigh+1=L->R0; /* 插入到相应位置 */= 2-路插入排序排序示例:设有初始关键字集合49, 38, 65, 13, 97, 27, 76 ,采用2-路插入排序的过程例:设有关键字集合49, 38, 65, 97, 76, 13, 27, 49 ,采用表插入排序的过程=希尔排序(Shell Sort,又称缩小增量法)是一种分组插入排序方法。排序示例 设有10个待排序的记录,关键字分别为9, 13, 8, 2, 5
22、, 13, 7, 1, 15, 11,增量序列是5, 3, 1,希尔排序的过程:算法实现 先给出一趟希尔排序的算法,类似直接插入排序。void shell_pass(Sqlist *L, int d) /* 对顺序表L进行一趟希尔排序, 增量为d */ int j, k ;for (j=d+1; j<=l->length; j+) L->R0=L->Rj ; /* 设置监视哨兵 */k=j-
23、d ;while (k>0&<(L->R0.key, L->Rk.key) ) L->Rk+d=L->Rk ; k=k-d ; L->Rk+j=L->R0 ;void shell_sort(Sqlist *L, int dk, int t) /* 按增量序列dk0 t-1,对顺序表L进行希尔排序 */ int m ;for (m=0; m<=t; m+)shll_pass(L, dkm) ;=冒泡排序排序示例
24、 : 设有9个待排序的记录,关键字分别为23, 38, 22, 45, 23, 67, 31, 15, 41,冒泡排序的过程:void Bubble_Sort(Sqlist *L) int j ,k , flag ;for (j=0; jlength; j+) /* 共有n-1趟排序 */ flag=TRUE ; for (k=1; k<=l->length-j; k+) /* 一趟排序 */
25、 if (LT(L->Rk+1.key, L->Rk.key ) ) flag=FALSE ; L->R0=L->Rk ; L->Rk=L->Rk+1 ; L->Rk+1=L->R0 ; if (f
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 清华大学 严蔚敏 新版 数据结构 考研 要点 精华
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。