《数据结构基础复习09》由会员分享，可在线阅读，更多相关《数据结构基础复习09（115页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构考研辅导考研辅导 基础复习基础复习浙江大学计算机学院浙江大学计算机学院漳糕少磐振流栏痊查煎坛敞雁坎恭算砒窿江奄漱驭畜梳版仕藤扮画养嘎刽数据结构基础复习09数据结构基础复习091内容提纲内容提纲考研概述考研概述1基础内容复习基础内容复习2线性表、堆栈、队列、数组线性表、堆栈、队列、数组A树与图树与图B查找与排序查找与排序C跺疚雄嚣凿蹭护蝴便缎慷谤这檀击靠韦萤谋悠宙琵偶酶殷酉峰铭躺偏宰漱数据结构基础复习09数据结构基础复习092考研概述考研概述v考察目标考察目标理解数据结构的基本概念：掌握数据结构理解数据结构的基本概念：掌握数据结构的逻辑结构、存储结构及其差异，以及各的逻辑结构、存
2、储结构及其差异，以及各种基本操作的实现。种基本操作的实现。在掌握基本的数据处理原理和方法的基础在掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。上，能够对算法进行设计与分析。能够选择合适的数据结构和方法进行问题能够选择合适的数据结构和方法进行问题求解。求解。煎址蛋买需呸刷寇柑狡滨担霹鲸汝媚秤暑蕉炽愧松凤恒摈邮汗秩区檀夏攻数据结构基础复习09数据结构基础复习093考研概述考研概述v考试形式考试形式整卷满分为整卷满分为150分，考试时间为分，考试时间为180分钟分钟数据结构占数据结构占45分，估计用时分，估计用时4550分钟分钟单选题：单选题：40题题 2分分/题，估计占题，估计占
3、10题题20分左分左右，建议用时不超过右，建议用时不超过2分钟分钟/题题综合题：综合题：70分，估计占分，估计占2题共题共2025分，建分，建议用时不超过议用时不超过10分钟分钟/题题函钳局箭聚祝搞雁诉扁应殿欠盖鹏豫诬钉韩教弱槽击铬楚怒皆洞扮片爵挛数据结构基础复习09数据结构基础复习094考研概述考研概述v复习计划复习计划基础理论复习基础理论复习例题详解例题详解题目范围：真题题目范围：真题1套套 + 模拟题模拟题9套套 + 补充题补充题模拟题第模拟题第10套将用于最后一天模拟考试套将用于最后一天模拟考试蜀嚏陷查欢绎辐祷寞亿顺颈践粳多畅粕师池环蝴努舷醚耀梦沈铺挠榴基熔数据结构基础复习09数据结构
4、基础复习095基础内容复习基础内容复习数据结构（数据结构（C语言版），严蔚敏、吴伟民，清华大学出版社语言版），严蔚敏、吴伟民，清华大学出版社v线性表、堆栈、队列、数组线性表、堆栈、队列、数组v树与图树与图v查找与排序查找与排序铝牌瘸灼症啄著谓涡卉旦队蔓窜秒内斟棘身寓赃舱斟准喉泻膳彰贰蛰趁员数据结构基础复习09数据结构基础复习096线性表、堆栈、队列、数组线性表、堆栈、队列、数组v 线性表线性表定义：定义：n个数据元素的有限序列个数据元素的有限序列基本操作：随机访问、插入、删除、前驱、后基本操作：随机访问、插入、删除、前驱、后继、倒序等继、倒序等实现方式：实现方式：顺序存储：数组顺序存储：数组a
5、iai+1Loc(ai)Loc(ai+1) = Loc(ai) + llLoc(ai) = Loc(a1) + ? (i -1) * l跳贺烹林贾除孜胚笨加鹃硕名靶哦村霖粤授窘披虚卤秆个常趋殆工粗嚣暴数据结构基础复习09数据结构基础复习097v线性表线性表实现方式：实现方式：顺序存储：数组顺序存储：数组线性表、堆栈、队列、数组线性表、堆栈、队列、数组 是一种随机存取的存储结构，方便随机存是一种随机存取的存储结构，方便随机存取第取第i个数据元素个数据元素 插入、删除复杂度为插入、删除复杂度为O(n)，需要移动大量，需要移动大量元素元素媚露容戍腔臀辟孺猪踞锥钟销哲液赵汪苍鸿塑凋嗣侍截砍屎岸犯励赁踏
6、部数据结构基础复习09数据结构基础复习098v自测题自测题在在n个结点的顺序表中，算法的时间复杂度是个结点的顺序表中，算法的时间复杂度是O(1)的操作是：的操作是：A.访问第访问第i个结点个结点(1in)和求第和求第i个结点的直接前驱个结点的直接前驱(2in)B.在第在第i个结点后插入一个新结点（个结点后插入一个新结点（1in）C.删除第删除第i个结点（个结点（1in）D.将将n个结点从小到大排序个结点从小到大排序线性表、堆栈、队列、数组线性表、堆栈、队列、数组蓖舵便牲诡瞩响游遮交冷韵作入谜垛嚎遣限客恩烧岗替些喘召嚎凄桅绸绵数据结构基础复习09数据结构基础复习099线性表、堆栈、队列、数组线性
7、表、堆栈、队列、数组v线性表线性表实现方式：实现方式：链式存储：链表链式存储：链表 线性链表线性链表存储地存储地址址数据域数据域指针域指针域1LiNULL7Qian1313Sun119Zhao7头指针头指针H = 19HZhaoQianSunLi 若若 p-data = ai 则则 p-next-data = ai+1typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;有时附加有时附加头结点头结点讲童纽么村偏瀑涌衫惯青叛隧悼饯冤厦蓖捅怖烫痘栓隧勃迸衅剔实落辕莹数据结构基础复习09数据结构基础复习091
8、0v自测题自测题线线性性表表若若采采用用链链式式存存储储结结构构时时，要要求求内内存存中中可可用用存储单元的地址存储单元的地址: A.必须是连续的必须是连续的B.部分地址必须是连续的部分地址必须是连续的C.一定是不连续的一定是不连续的D.连续或不连续都可以连续或不连续都可以线性表、堆栈、队列、数组线性表、堆栈、队列、数组渺搏铝浚抉字滇坊笆鸵挪揽图立颜梆垄轻汰庭族眩窜妙檄蛰佯炯垮景耘缝数据结构基础复习09数据结构基础复习0911线性表、堆栈、队列、数组线性表、堆栈、队列、数组v线性表线性表实现方式：实现方式：链式存储：链表链式存储：链表 线性链表线性链表 插入、删除复杂度为插入、删除复杂度为O(
9、1)，仅需修改指针，仅需修改指针而而不不需要移动元素需要移动元素 是一种是一种非非随机存取的存储结构，随机存取的存储结构，不不方便随方便随机存取第机存取第i个数据元素个数据元素*静态链表静态链表 （p.31-35）刑汲破人呼窄母掩悼坏耙黄擅研塘乐迁碌蜗罐淖戴仑灯筐琴愚不饿懦篇枉数据结构基础复习09数据结构基础复习0912v自测题自测题下面的叙述不正确的是（下面的叙述不正确的是（ ）A.线性表在链式存储时，查找第线性表在链式存储时，查找第i个元素的时间个元素的时间同同i的值成正比的值成正比B.线性表在链式存储时，查找第线性表在链式存储时，查找第i个元素的时间个元素的时间同同i的值无关的值无关C.
10、线性表在顺序存储时，查找第线性表在顺序存储时，查找第i个元素的时间个元素的时间同同i 的值成正比的值成正比D.线性表在顺序存储时，查找第线性表在顺序存储时，查找第i个元素的时间个元素的时间同同i的值无关的值无关线性表、堆栈、队列、数组线性表、堆栈、队列、数组弃肪阜鞘吟嫡埋僵揪孪割璃益瑶争待针抢寇匣述练拒盎仿馏蹿珍怒绿磊镍数据结构基础复习09数据结构基础复习0913v自测题自测题在一个单链表中，若在一个单链表中，若p所指的结点不是最后结点，所指的结点不是最后结点，在在p之后插入之后插入s所指结点，则执行：所指结点，则执行：A.s-next=p; p-next=s;B.s-next=p-next;
11、 p-next=s;C.s-next=p-next; p=s;D.p-next=s; s-next=p;线性表、堆栈、队列、数组线性表、堆栈、队列、数组ps使赏镐嘶蛤次趁荒后峙沥芜补涩岳烤咙赠锥墨里鸳藐共磕铣营冠狞利痴爵数据结构基础复习09数据结构基础复习0914v自测题自测题在单链表中，指针在单链表中，指针p指向元素为指向元素为x的结点，实现的结点，实现“删除删除x的后继的后继”的语句是：的语句是：A.p = p-next;B.p-next = p-next-next;C.p-next = p;D.p = p-next-next;线性表、堆栈、队列、数组线性表、堆栈、队列、数组xp省句孤擎翘
12、地稚二阑姥币赎盟诉写杭蟹揭末半厕训琉契丽煞狗井咀闺树漳数据结构基础复习09数据结构基础复习0915线性表、堆栈、队列、数组线性表、堆栈、队列、数组v线性表线性表实现方式：实现方式：链式存储：链表链式存储：链表 循环链表循环链表 双向链表双向链表HHHH有时设有时设尾指尾指针针可简化某可简化某些操作，如些操作，如两表合并。两表合并。媚潘羡衍驰躺烂榨股打雾锁安彬榨称殉璃贬乳胞鸥蛰异窒之醉哆僳霖泣耍数据结构基础复习09数据结构基础复习0916v自测题自测题设一个链表最常用的操作是在末尾插入结点和删设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用除尾结点，则选用( )最节省时间。最节省时间。
13、A.单链表单链表 B.单循环链表单循环链表 C.带尾指针的单循环链表带尾指针的单循环链表 D.带头结点的双循环链表带头结点的双循环链表线性表、堆栈、队列、数组线性表、堆栈、队列、数组旬但诚企提崎狡釜汹糕饶佰式箭沃地皮伏拿图痞寨蛔正暮窘缎匪笛岭纷串数据结构基础复习09数据结构基础复习0917v自测题自测题将线性表将线性表La和和Lb头尾连接，要求时间复杂度为头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小。应该使用哪种结，且占用辅助空间尽量小。应该使用哪种结构？构？A.单链表单链表 B.单循环链表单循环链表 C.带尾指针的单循环链表带尾指针的单循环链表 D.带头结点的双循环链表带头结点的
14、双循环链表线性表、堆栈、队列、数组线性表、堆栈、队列、数组tmp = La-next; La-next = Lb-next; Lb-next = tmp;LaLb滥图貌卢琼赚离莹帅槐险催级呆恕风窜净士侦斟架尹阅烦践酌琉骇赘匙雷数据结构基础复习09数据结构基础复习0918线性表、堆栈、队列、数组线性表、堆栈、队列、数组v线性表线性表练习练习1：分别实现数组、单链表、循环链表、双向链分别实现数组、单链表、循环链表、双向链表的插入和删除操作。表的插入和删除操作。练习练习2：实现单链表的原地逆转。实现单链表的原地逆转。练习练习3：分别用一元多项式的两种表示实现多项式加分别用一元多项式的两种表示实现多项
15、式加法。法。32-51-2 3000 -1103200P啪堑镇籽新译皇茁几铀躇例遍可氦伐幌疼厕要们杰澳扛骚嚎扯肇淤钒弥昏数据结构基础复习09数据结构基础复习0919v自测题自测题给定给定2个带有表头结点的单链表的头指针个带有表头结点的单链表的头指针L1和和L2，结点结构为结点结构为 。假设这。假设这2个链表的结点个链表的结点已经按已经按Data域递增有序，请设计算法把它们合并成域递增有序，请设计算法把它们合并成一个按一个按Data域递增有序的链表。注意：算法不能使域递增有序的链表。注意：算法不能使用额外的结点空间。用额外的结点空间。 线性表、堆栈、队列、数组线性表、堆栈、队列、数组DataNe
16、xt 算法思路为顺序比较算法思路为顺序比较L1和和L2当前所指的两结点的当前所指的两结点的Data域，将小的那个结点从原链表摘除，贴到合并链表域，将小的那个结点从原链表摘除，贴到合并链表的尾部。如此进行到至少其中一个链表为空。若此时另的尾部。如此进行到至少其中一个链表为空。若此时另一个链表不为空，则将另一个链表整个贴到合并链表的一个链表不为空，则将另一个链表整个贴到合并链表的尾部。注意原始尾部。注意原始2个链表有个链表有2个头结点，合并后只保留一个头结点，合并后只保留一个，需要释放另一个的空间。个，需要释放另一个的空间。 凤五耻镁黑屡耸杰与乎疲沧映拂叶淡烫百筹虚览鬃嘻脉官则胜斜尾洋轮陇数据结构
17、基础复习09数据结构基础复习0920List MergeSortedLists( List L1, List L2 )List L = L1; List Tail = L2;L1 = L1-Next; L2 = L2-Next;free( Tail ); Tail = L;/释放第二个链表的表头，并将新链表的表尾指针释放第二个链表的表头，并将新链表的表尾指针Tail初始化初始化while ( L1 & L2 ) if ( L1-Data L2-Data ) Tail-Next = L2; L2 = L2-Next; /第二个链表的第一结点值小，将其插入新链表尾第二个链表的第一结点值小，将其插入
18、新链表尾 else Tail-Next = L1; L1 = L1-Next; /第一个链表的第一结点值小，将其插入新链表尾第一个链表的第一结点值小，将其插入新链表尾 Tail = Tail-Next;if ( L1 ) Tail-Next = L1; /将剩余的第一个链表接到新链表表尾将剩余的第一个链表接到新链表表尾else if ( L2 ) Tail-Next = L2; /将剩余的第二个链表接到新链表表尾将剩余的第二个链表接到新链表表尾return L; 美实梨匹姿梅彼绪凸烁己箩署阳佐硷淫凳桓孟彬硬浦悼盔挡哟檀隐谱脏菠数据结构基础复习09数据结构基础复习0921v自测题自测题给定给定2
19、个带有表头结点的单链表的头指针个带有表头结点的单链表的头指针L1和和L2，结点结构为结点结构为 。假设这。假设这2个链表的结点个链表的结点已经按已经按Data域递增有序，请设计算法把它们合并成域递增有序，请设计算法把它们合并成一个按一个按Data域域递减递减有序的链表。注意：算法不能使有序的链表。注意：算法不能使用额外的结点空间。用额外的结点空间。 线性表、堆栈、队列、数组线性表、堆栈、队列、数组DataNext 解题的基本思路不变，只要将原来的表尾插入改为表解题的基本思路不变，只要将原来的表尾插入改为表头插入即可。当然，当其中一个链表为空而另一个链表头插入即可。当然，当其中一个链表为空而另一
20、个链表不为空时，不能直接将剩余链表贴到表尾，而必须将剩不为空时，不能直接将剩余链表贴到表尾，而必须将剩余结点一个一个插入表头。余结点一个一个插入表头。遁惊济上喜甘考川萄摩协诌各墙琐敲旭蚌福注嫁棱盎阎彝遗二工算忧峡向数据结构基础复习09数据结构基础复习0922v自测题自测题若若L1和和L2是有序是有序数组数组，其结点已经按，其结点已经按Data域递增域递增有序，请设计算法把它们合并成一个按有序，请设计算法把它们合并成一个按Data域递增域递增有序的数组。注意：要求将有序的数组。注意：要求将L2并入并入L1，并且要求移，并且要求移动元素的次数尽可能少。动元素的次数尽可能少。 线性表、堆栈、队列、数
21、组线性表、堆栈、队列、数组 必须事先算好合并后必须事先算好合并后L1的长度，然后从的长度，然后从L1的最终尾的最终尾部向前插入元素。插入过程与前面算法类似，但是是部向前插入元素。插入过程与前面算法类似，但是是从从尾部开始尾部开始比较比较L1和和L2相应元素大小，将较大的元素先插相应元素大小，将较大的元素先插入到后面的位置。入到后面的位置。秋梢捍裔南童坦戍尝恋贝割叁感地过矣嘲式嫁潜余龚忌冰艰幼雅伸院琢器数据结构基础复习09数据结构基础复习0923void MergeSortedArrays( ElementType L1, int N1, ElementType L2, int N2 )int
22、p1, p2, cur;p1 = N1-1; /p1指向指向L1当前处理的元素位置当前处理的元素位置p2 = N2-1; /p2指向指向L2当前处理的元素位置当前处理的元素位置cur = N1+N2-1; /cur指向下一个要插入的元素在指向下一个要插入的元素在L1中的最终位置中的最终位置while ( (p1=0) & (p2=0) ) if ( L1p1 L2p2 ) L1cur = L1p1; p1-;else L1cur = L2p2; p2-;cur-;while ( p2=0 ) /将将p2的剩余元素插入到的剩余元素插入到L1中中L1p2 = L2p2; p2-;归急缎魂剃锐揭窃孰
23、鲁何澈蹄酿郡识生廖袭河视鲍贮搏孤浅月书剩滤兹苦数据结构基础复习09数据结构基础复习0924v堆栈堆栈概念：后进先出，限定仅在表尾进行插入删除概念：后进先出，限定仅在表尾进行插入删除的线性表。的线性表。表示与实现：表示与实现：顺序栈：数组，顺序栈：数组，top+，top-链栈：链表，链栈：链表，top即为头指针即为头指针应用：括号匹配检验、表达式求值、应用：括号匹配检验、表达式求值、n阶阶Hanoi塔问题（典型递归）、迷宫问题塔问题（典型递归）、迷宫问题线性表、堆栈、队列、数组线性表、堆栈、队列、数组俄年搪嫁快锗请洲慨胁误芝片吞裸萨醋麓屹藕乌栈缓砖捎瘟潍盎淹关锐粪数据结构基础复习09数据结构基础
24、复习0925v自测题自测题判定一个栈判定一个栈ST(最多元素为最多元素为m0)为空的条件是：为空的条件是：A.ST-top != 0B.ST-top = 0C.ST-top != m0D.ST-top = m0线性表、堆栈、队列、数组线性表、堆栈、队列、数组挟绒湖体挪呀啦硕驼凶牡依殷懈肪姚肯蓝傲安摄进羡剂炼婉续临缓夏匪频数据结构基础复习09数据结构基础复习0926v自测题自测题有六个元素以有六个元素以6，5，4，3，2，1 的顺序进栈，的顺序进栈，问下列哪一个不是合法的出栈序列？问下列哪一个不是合法的出栈序列？A.5 4 3 6 1 2 B.4 5 3 1 2 6 C.3 4 6 5 2 1
25、D.2 3 4 1 5 6线性表、堆栈、队列、数组线性表、堆栈、队列、数组奸增翁概炮侦峪鸥铺喧洽禾差昼跑俺冬娶倘躯傲疾佰土驮彦少山氖样奶仰数据结构基础复习09数据结构基础复习0927v自测题自测题若一个栈的输入序列为若一个栈的输入序列为1，2，3，n，输出，输出序列的第一个元素是序列的第一个元素是i，则第，则第j个输出元素是：个输出元素是：A.i j 1 B.i j C.j i 1 D.不确定的不确定的线性表、堆栈、队列、数组线性表、堆栈、队列、数组磁鼓椽斡镊沛笼兼扇趣镣胶晦戌薯频得子歪碍铅数婿结体姓新馆阐呈唬毅数据结构基础复习09数据结构基础复习0928v队列队列概念：先进先出，限定仅在队尾
26、进行插入、仅概念：先进先出，限定仅在队尾进行插入、仅在队头进行删除的线性表。在队头进行删除的线性表。表示与实现：表示与实现：顺序队列：循环数组，顺序队列：循环数组，(rear+1)%N, (front+1)%N链栈：链表，链栈：链表，front为头指针，为头指针，rear为尾指针为尾指针应用：离散事件模拟应用：离散事件模拟线性表、堆栈、队列、数组线性表、堆栈、队列、数组发脾奸想纫廉蔗位摧养蘸丁浅九绝甚梁澈听务妄投笋警贴慢肮亡颜镰狼拎数据结构基础复习09数据结构基础复习0929v自测题自测题循环队列用数组循环队列用数组A0,N1存放其元素值，已知存放其元素值，已知其头尾指针分别是其头尾指针分别是
27、front和和rear，则当前队列中的，则当前队列中的元素个数是：元素个数是：A.(rear-front+N)%NB.rear-front+1C.rear-front-1D.rear-front线性表、堆栈、队列、数组线性表、堆栈、队列、数组01.N-1frontrear儒社家女荫辗帅率弛啊泻普媒暮禽抡那坪作按搬议是仁啄氧溜忱订孩昂贫数据结构基础复习09数据结构基础复习0930v自测题自测题栈和队列的共同特点是：栈和队列的共同特点是：A.都是先进后出都是先进后出 B.都是先进先出都是先进先出 C.只允许在同一端点处插入和删除只允许在同一端点处插入和删除 D.没有共同点没有共同点 线性表、堆栈、
28、队列、数组线性表、堆栈、队列、数组揪铅足做牢聊狭僚极冰啊筷盗拈日阎更裳己他婉读则义尼幢左寺皂蛰苟金数据结构基础复习09数据结构基础复习0931v数组数组 特殊矩阵的压缩存储特殊矩阵的压缩存储对称矩阵：对称矩阵：线性表、堆栈、队列、数组线性表、堆栈、队列、数组an, 1a11a21a22a31an, nSAk0123*上（下）三角矩阵同理存储，或许多存储一个常数（若另一上（下）三角矩阵同理存储，或许多存储一个常数（若另一半矩阵元素是非零常数）。半矩阵元素是非零常数）。佑剔窍飘尹氟砒煎汛嗜逻影疟蜡泡晾匹蒋碘频究触畴亏逛怀汀付收等橙榷数据结构基础复习09数据结构基础复习0932线性表、堆栈、队列、数
29、组线性表、堆栈、队列、数组v数组数组 特殊矩阵的压缩存储特殊矩阵的压缩存储m对角矩阵：对角矩阵：或者或者 稀疏矩阵：稀疏矩阵：nrow=3, ncol=5, ntotal=6(1,3,4), (2,1,7), (2,3,1), (2,5,-3),(3,2,-2), (3,5,5), 篷课前钱仕箔祁虫行灶靖窃熏弥飘碟腆亩眶涧串呕吱暑缕茸藐踊吼侍刷茄数据结构基础复习09数据结构基础复习0933线性表、堆栈、队列、数组线性表、堆栈、队列、数组v数组数组 特殊矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵：稀疏矩阵：三元组顺序表：以行序为主序，顺序排列为三元三元组顺序表：以行序为主序，顺序排列为三元组的组的
30、1维数组，并存行数、列数、非维数组，并存行数、列数、非0元个数。元个数。typedef struct inti, j; ElemTypev; Triple;typedef union Triple dataMAXSIZE+1; intnrow, ncol, ntotal; Sparse_Matrix;ijv13421723125-3553-223吉类简仅恶舜叹晴逻幢胖馒锥衷跪开皮竹漱馁测垒赤蛆乎阿郧足晌帅屿私数据结构基础复习09数据结构基础复习0934线性表、堆栈、队列、数组线性表、堆栈、队列、数组v数组数组 特殊矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵：稀疏矩阵：三元组顺序表：三元组顺序表：
31、快速转置快速转置ijv12723-2314321535-325ijv13421723125-3553-223对每列扫描整个数组：对每列扫描整个数组：O(ncol ntotal) 如何一步到位，放入正确位置？如何一步到位，放入正确位置？numcol 第col列中非0元个数；cpotcol 第col列中第1个非0元在转置矩阵中的位置；cpot1 = 1;cpotcol = cpotcol-1 + numcol-1;1 2 3 4 5col1 1 2 0 2num1 2 3 5 5cpot42O( ncol + ntotal )沦蛇芥程敌达俄丫盛焕夷矾捕覆妓谈蔼废宾刃性仪化穷擅荔牧哩牢痊捧垛数据结构
32、基础复习09数据结构基础复习0935线性表、堆栈、队列、数组线性表、堆栈、队列、数组v数组数组 特殊矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵：稀疏矩阵：行逻辑链接的顺序表：行逻辑链接的顺序表：矩阵相乘矩阵相乘typedef struct Triple dataMAXSIZE+1; intrposMAXRC+1; intnrow, ncol, ntotal; Sparse_Matrix;各行第1个非0元在数组中的位置设设 M = A B，则有，则有关键：关键：对每个对每个A.datap，找所有，找所有B.dataq，满足，满足( A.datap.j = B.dataq.i )，将将(A.data
33、p.v B.dataq.v)累加到相应的临时行向量，最后压缩到累加到相应的临时行向量，最后压缩到M中。中。O( Arow Bcol + Atotal Btotal/Brow )序笑陕昏狸木年阴膳霹差袜湿吃晃昨勘热揭泛齿落协欺蠕卯镜升喘恳诲馒数据结构基础复习09数据结构基础复习0936线性表、堆栈、队列、数组线性表、堆栈、队列、数组v数组数组 特殊矩阵的压缩存储特殊矩阵的压缩存储稀疏矩阵：稀疏矩阵：十字链表：十字链表：矩阵相加矩阵相加41 372 112 3-32 5-23 253 5123M.rhead12345M.chead计算计算 A + B 的复杂度为的复杂度为 O( Atotal +
34、Btotal )汹岳肥偏泛仪荆乙潘罩帮票袍汲掂桌兑源付帘睹吱径醛或钻絮札茬姓德孜数据结构基础复习09数据结构基础复习0937v自测题自测题设稀疏矩阵设稀疏矩阵A有有t个非零元素，用二维数组存储时个非零元素，用二维数组存储时占用占用m*n个单元。问稀疏矩阵的三元组表示法在个单元。问稀疏矩阵的三元组表示法在什么情况下比二维数组存储节省空间？什么情况下比二维数组存储节省空间？A.t m*nB.t m*n/3 C.t m*n/3 1D.t m*n 1线性表、堆栈、队列、数组线性表、堆栈、队列、数组确半累滥低恭雇欣煎诵烁捂敢百洁吐间佰汁种嚣醒德请狠至喻幽煤囚褥彼数据结构基础复习09数据结构基础复习093
35、8树与图树与图v树与二叉树的概念树与二叉树的概念树的概念：树的概念：度度(degree)；层；层(level) 注意：根为第注意：根为第1层；深度层；深度(depth) 结点的最大层次。结点的最大层次。二叉树的概念：左右有序二叉树的概念：左右有序性质性质1：第：第i层最多有层最多有2i-1个结点。个结点。性质性质2：深度为：深度为k的二叉树最多有的二叉树最多有2k-1个结点。个结点。性质性质3：若：若n0为叶子数，为叶子数，n2为度为为度为2的结点数，则的结点数，则有有 n0= n2+1。性质性质4：具有：具有n个结点的个结点的完全二叉树完全二叉树的深度为的深度为 log2n +1。合诡摧冀扮
36、垒彝薪壮怨吮坪萨短吏彪渴序诅踪裴笑没醋招迄龄雪整覆民蝇数据结构基础复习09数据结构基础复习0939v树与二叉树的概念树与二叉树的概念二叉树的概念：二叉树的概念：性质性质5：对有：对有n个结点且顺序编号的完全二叉树，个结点且顺序编号的完全二叉树，其任一结点其任一结点 i 有有树与图树与图腾荷戍汲够烃鞠峡凶碰吉具蠕裕请夺嗅津编札访贪梆褪肤决键汹贺喧盎仁数据结构基础复习09数据结构基础复习0940v二叉树的存储结构二叉树的存储结构顺序存储结构：数组顺序存储结构：数组 仅适用于完全二叉树仅适用于完全二叉树链式存储结构：链式存储结构： 在含有在含有n个结点的二叉链表中有个结点的二叉链表中有 个空链域。个
37、空链域。v二叉树的遍历二叉树的遍历先序、先序、 中序、中序、 后序、后序、 层次层次树与图树与图LchildDataRchild Parent1234 5 6 7n+1矗丰恩划视铁砍疏姿裔粮撅渝仁尹主秃秉圣还堑宏吼抚驭衷六绑柿仙捡会数据结构基础复习09数据结构基础复习0941v自测题自测题一棵完全二叉树共有一棵完全二叉树共有2435个结点，则其个结点，则其中度为中度为0的结点数为？的结点数为？A.1218B.1217 C.不确定不确定D.812树与图树与图前前11层共有层共有211-1=2047个结点个结点第第12层共有层共有2435-2047=388个结点个结点388 + 210 388/2
38、 = 1218汪我虏颈维替练丘盏解膛门休点脓筑悦细千涧婚氰腐斩舒制吕吐滥添边摄数据结构基础复习09数据结构基础复习0942v自测题自测题在一棵高度为在一棵高度为h(假定树根结点的层号为假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于的完全二叉树中，所含结点个数不小于 A.2h 1B.2h+1C.2h 1 D.2h树与图树与图恋扭骇爷箩栓嘉羡诸搜铡擦贡使应彩箭椿拖驼躁刨刹铃闸酋选辽恫楔磊磺数据结构基础复习09数据结构基础复习0943v自测题自测题结点中序遍历为结点中序遍历为xyz的不同二叉树，它有的不同二叉树，它有几种不同状态？几种不同状态？ A.3 B.4 C.5 D.6 树与图树与
39、图yxzzxyzyxxzyxyz审额跳拨捆腐姚夜藐棍吝苹换切渐绦慕踏耍柏颧硒逃民锗锻浊傈剪剖街棠数据结构基础复习09数据结构基础复习0944v自测题自测题前序遍历和中序遍历结果相同的二叉树为前序遍历和中序遍历结果相同的二叉树为 A.一般二叉树一般二叉树 B.只有根结点的二叉树只有根结点的二叉树 C.所有结点只有左子树的二叉树所有结点只有左子树的二叉树 D.所有结点只有右子树的二叉树所有结点只有右子树的二叉树 树与图树与图躲薛铝候雍历绣哆琐表粗抛缮汛狙壁刁切紧慰锚牟躁裴袱喘深秦豆坤氓拿数据结构基础复习09数据结构基础复习0945v自测题自测题前序遍历和后序遍历结果相同的二叉树为前序遍历和后序遍历
40、结果相同的二叉树为 A.一般二叉树一般二叉树 B.只有根结点的二叉树只有根结点的二叉树 C.所有结点只有左子树的二叉树所有结点只有左子树的二叉树 D.所有结点只有右子树的二叉树所有结点只有右子树的二叉树 树与图树与图轨续颠巾点健擦黍影捉旷捉弧涧骆焉钱肢众朴私左秘蓬钦犊脖至邢尸胶角数据结构基础复习09数据结构基础复习0946v自测题自测题已知中序遍历和前序遍历结果，给出算法已知中序遍历和前序遍历结果，给出算法求后序遍历结果。求后序遍历结果。 树与图树与图（1）从前序遍历结果推断该树的树根。）从前序遍历结果推断该树的树根。（2）找出左子树和右子树的中序和前序遍历结果。）找出左子树和右子树的中序和前
41、序遍历结果。（3）重复上述过程，找出左、右子树的根结点，并）重复上述过程，找出左、右子树的根结点，并逐步往下扩展，直到生成一颗完整的二叉树。逐步往下扩展，直到生成一颗完整的二叉树。 中序中序前序前序左左左左右右右右姐稍撅仆无寄暂奇湘七痈抹渝挽伦亥侥洽愈毛瘁炭担策巾守唉茅分售宠撞数据结构基础复习09数据结构基础复习0947OutPostOrder(PreOrder, InOrder) /已知前序序列已知前序序列PreOrder、中序序列、中序序列InOrder，求后序序列，求后序序列 1）应用前述方法，从序列）应用前述方法，从序列PreOrder和和InOrder中推断出：中推断出：树的根树的根
42、r;左子树的前序遍历序列左子树的前序遍历序列PreOrderLeft和中序遍历序列和中序遍历序列InOrderLeft;右子树的前序遍历序列右子树的前序遍历序列PreOrderRight和中序遍历序列和中序遍历序列InOrderRight; 2）递归）递归OutPostOrder(PreOrderLeft, InOrderLeft); 3）递归）递归OutPostOrder(PreOrderRight, InOrderRight); 4）输出）输出 r; 栏庇苍杨顾拼撇镇栓罗赞奔有丫俭傲搜泽紫汝诛秸煤拧申闸焕荤告稍桃琶数据结构基础复习09数据结构基础复习0948v自测题自测题下面是某二叉树三种
43、遍历的部分结果，请画出相下面是某二叉树三种遍历的部分结果，请画出相应的二叉树。应的二叉树。前序前序: _B_F_ICEH_G 中序中序: D_KFIA_EJC_ 后序后序: _K_FBHJ_G_A 树与图树与图A AB BC CD DF FK KI IE EH HJ JGGABD KDIHJGE C甸洪酣扶役姐啥快吗亥焚菱业普妒掷诀祝逛弘宰散篷泻盾可酥烈街豫能吻数据结构基础复习09数据结构基础复习0949v自测题自测题在任意一颗二叉树中，任何两个叶结点在在任意一颗二叉树中，任何两个叶结点在先序、中序、后序中的相对次序怎样？先序、中序、后序中的相对次序怎样？ A.不变不变 B.不一样不一样 C.
44、不能确定不能确定 D.以上都不是以上都不是 树与图树与图其蓖洋喝梳旁壳卤箭炙芋氦仇圭涨扁衍阮丛隋钎丝造僵涌宛睫洁漫俊尚酶数据结构基础复习09数据结构基础复习0950v线索二叉树线索二叉树概念：概念：树与图树与图LchildDataRchildLtagRtag0: Lchild指向左孩子指向左孩子1: Lchild指向前驱指向前驱0: Rchild指向右孩子指向右孩子1: Rchild指向后继指向后继+A DBC中序遍历：中序遍历：A + B C D000+01A10 00 01D11B11C1头结点头结点中中序序线线索索二二叉叉树树齐脯垛躇坟炒渍扦脑撵叭渺喊季柜宙照柑瑟远症撅鸯莹舞澡酵睡磺隐筷
45、死数据结构基础复习09数据结构基础复习0951树与图树与图v线索二叉树线索二叉树构造：构造：中序：增加中序：增加pre指针，指向刚访问过的结点指针，指向刚访问过的结点后序：须增加后序：须增加Parent指针域指针域优点：优点：遍历不需要堆栈。若经常需要遍历二叉树或查遍历不需要堆栈。若经常需要遍历二叉树或查找结点在遍历序列中的前驱和后继，则应采用线索链找结点在遍历序列中的前驱和后继，则应采用线索链表作为存储结构。表作为存储结构。陕荷楷狼杉隐策炙环莆詹客应兜棍驯迹废潘溯窖丹柔耻虑坍勾克朱啪殖蜂数据结构基础复习09数据结构基础复习0952v二叉排序树二叉排序树定义：左定义：左 根根 二叉树二叉树B=
46、( R, LB, RB )二叉树二叉树B=( R, LB, RB ) - 森林森林F= T1 T2 . Tm 树与图树与图if ( !F ) B = NULL;else R = root(T1); LB = T11 T12 . T1m1 ;RB = T2 . Tm ;if ( !B ) F = NULL;else root(T1) = R; T11 T12 . T1m1 = LB; T2 . Tm = RB;刨夺乱扛桂瞩些牺泛躲淮尉折歹茎片站殊羚赐棚俺恍粪蚌廷炼趴佯物牢映数据结构基础复习09数据结构基础复习0961v树和森林树和森林树和森林的遍历树和森林的遍历树的遍历：树的遍历：先根（次序）遍
47、历先根（次序）遍历 = 二叉树的先序遍历二叉树的先序遍历后根（次序）遍历后根（次序）遍历 = 二叉树的二叉树的中序中序遍历遍历森林的遍历：森林的遍历：先序遍历先序遍历 = 二叉树的先序遍历二叉树的先序遍历中序遍历中序遍历 = 二叉树的中序遍历二叉树的中序遍历树与图树与图伙中括粕夺端钢叭了铀荚蒜狭邑凹拨侦运培葫郊诣博春欣窥仁渔逗艇更榴数据结构基础复习09数据结构基础复习0962v自测题自测题设森林设森林F对应的二叉树为对应的二叉树为B，它有，它有m个结个结点。点。B的根为的根为p，p的右子树结点个数为的右子树结点个数为n，森林，森林F中第一棵树的结点个数是中第一棵树的结点个数是？A.m-nB.m
48、-n-1C.n+1 D.无法确定无法确定 树与图树与图mn捍悼岸捻睬贯详医队晓蚊纫吴膊赞蟹且搅同问埋闻樊歧等茹山留勤平犊忧数据结构基础复习09数据结构基础复习0963v自测题自测题树最适合用来表示树最适合用来表示A.有序数据元素有序数据元素 B.无序数据元素无序数据元素 C.元素之间无联系的数据元素之间无联系的数据 D.元素之间有分支层次关系元素之间有分支层次关系 树与图树与图筛侠狙油抄券滤衰往简掳墙柒凑宿督沫制廓救但秀亢奏描教磺仗释线靠仙数据结构基础复习09数据结构基础复习0964v树的应用树的应用等价类问题：等价类问题：给定集合给定集合S的的n个元素，以及个元素，以及m个形如个形如(x,y
49、)的等价偶对，求的等价偶对，求S的等价类划分。的等价类划分。树与图树与图 初始化初始化n个只包含个只包含1个元素的子集个元素的子集; while ( 读入读入x, y ) if ( ! (Find(x) = Find(y) )Union 两集合两集合; 10687419235142010094810710610524032S泉钠手娱辐储索柔关芜垣滦毡缓毡棠摇饵倾雀纶梧今狈圣衍歌窒伞孪黑孝数据结构基础复习09数据结构基础复习0965v树的应用树的应用等价类问题等价类问题Union by size 根记录根记录(-结点数结点数)，小树并入大树，小树并入大树Find + 压缩路径压缩路径 将将Fin
50、d路径上的结点都变成根的路径上的结点都变成根的孩子孩子树与图树与图10687419235142-310-794810710610524832SUnion(2, 10)-1010Find(9)106874192351010*等价划分等价划分n元集合的复杂度为元集合的复杂度为 O( n (n) ), (n) 4对通常见到的对通常见到的n成立。成立。稿夺无骋孜讣娟锭触撒僵丢鞭截公纂湘沦搪谩站舍七雕亚镜昨双匹瑟夹或数据结构基础复习09数据结构基础复习0966v哈夫曼哈夫曼(Huffman)树和哈夫曼编码树和哈夫曼编码哈夫曼树：带权路径长度最小的二叉树哈夫曼树：带权路径长度最小的二叉树树与图树与图752
51、47524路径长度路径长度 = 7 2 + 5 2 + 2 2 + 4 2 = 367524路径长度路径长度 = 7 3 + 5 3 + 2 1 + 4 2 = 46路径长度路径长度 = 7 1 + 5 2 + 2 3 + 4 3 = 35 琶内颊捐期郑廖拍耐物丸羊擦鞭棠耸遍恫堆藕辟赡洲狮暮丘嗡撮能泣你背数据结构基础复习09数据结构基础复习0967v哈夫曼哈夫曼(Huffman)树和哈夫曼编码树和哈夫曼编码哈夫曼树的构造哈夫曼树的构造1.将将n个带权结点作为个带权结点作为n棵只有根的二叉树的森林；棵只有根的二叉树的森林；2.选选2棵根权值最小的树，作为左右子树构造新树，棵根权值最小的树，作为左
52、右子树构造新树，新根的权值新根的权值 = 左右子树根权值的和；左右子树根权值的和；3.将上述将上述2棵树删除，将新树加入森林；棵树删除，将新树加入森林；4.重复第重复第2、3步，直到只剩步，直到只剩1棵树，即是哈夫曼树。棵树，即是哈夫曼树。树与图树与图昭纵矫浮胀袭刺郧他邓巷俗逝室种卫剖潦漱萎沧曰庶师彤辉瀑扩哑谤提甭数据结构基础复习09数据结构基础复习0968v哈夫曼哈夫曼(Huffman)树和哈夫曼编码树和哈夫曼编码哈夫曼编码哈夫曼编码例：例：aaaxuaxz 一般被存为一般被存为8个字符，占个字符，占64字节。但因只字节。但因只有有4个不同字符，故可编码为个不同字符，故可编码为 a = 00
53、, u = 01, x = 10, z = 11，只需要占，只需要占16个字节。若采用哈夫曼编码个字节。若采用哈夫曼编码 a = 0, u = 110, x = 10, z = 111，则得到，则得到 00010110010111，只，只需要占需要占14个字节。个字节。注意：任一字符的编码都不是另一字符编码的前缀注意：任一字符的编码都不是另一字符编码的前缀 前缀编码前缀编码。树与图树与图烫沁疤歪浮看掌锗唾蓄坏嘻甭裙猪聊耪瞥魁惫抠秸赋妒寐釜哟蚕塑蛇椅唐数据结构基础复习09数据结构基础复习0969v哈夫曼哈夫曼(Huffman)树和哈夫曼编码树和哈夫曼编码哈夫曼编码的构造：哈夫曼编码的构造：将字符
54、出现频率作为权重，构将字符出现频率作为权重，构造哈夫曼树，并按左造哈夫曼树，并按左0右右1编码。编码。 例：例：aaaxuaxz树与图树与图a:4x:2u:1z:1a:4x:2u:1z:1248000111a = 0x = 10u = 110z = 111思考：给定编码，思考：给定编码，如何判断是否哈如何判断是否哈夫曼编码？夫曼编码？洽拭彦荤圃玲拥物矾羡壤美莽蔫灸况峪妆烹如蔡爬吓韧与勉霜蟹睦隅敢砍数据结构基础复习09数据结构基础复习0970v自测题自测题哈夫曼树有哈夫曼树有n个叶结点，则该树共有多个叶结点，则该树共有多少个结点？少个结点？A.2nB.2n-1C.2n+1 D.不能确定不能确定
55、树与图树与图N0 = nN1 = 02*N2 = N 1 N = N0 + N1 + N2N = ?娶垂裂痞下碰嵌节淳蚕豹然乘萎扑含致媳苯稼艺蘸我宦基夫黄拘李洱颓每数据结构基础复习09数据结构基础复习0971v图的概念（图的概念（p.156-160）v图的存储及基本操作图的存储及基本操作邻接矩阵法邻接矩阵法无向图顶点的度无向图顶点的度有向图顶点的度有向图顶点的度网网树与图树与图笛消怪寂扭怒习农拢诱俞鸽存什则脑擦饭寝菇茅掇胚谅响怀娠惶肌研袁绵数据结构基础复习09数据结构基础复习0972v图的存储及基本操作图的存储及基本操作邻接表法邻接表法树与图树与图V1V2V3V4V1V2V3V40123iV1
56、dataV2V3V421300123iV1dataV2V3V4312003020123iV1dataV2V3V43020逆邻接表逆邻接表*边稀疏时节省空间，但判断任意两顶点是否有弧相连时，则不如邻接边稀疏时节省空间，但判断任意两顶点是否有弧相连时，则不如邻接矩阵方便。矩阵方便。摹菜缀庙献察恼顾痪廓瓶苑变重墟烂刃翟叁拘嘉捆蜗昼文肛棠巢愁篮锦驻数据结构基础复习09数据结构基础复习0973v自测题自测题具有具有n个顶点的无向图最多有几条边？个顶点的无向图最多有几条边？ A.n(n - 1)/2B.n(n + 1)/2C.n2/2 D.2n 树与图树与图橙址怜琼浊晌独闹肚亿浩言缀蔚悼宜操妨痞袁久绎昔涧
57、假牙启册破函棵肃数据结构基础复习09数据结构基础复习0974v自测题自测题在一个图中，所有点的度数之和等于所在一个图中，所有点的度数之和等于所有边的数目的多少倍？有边的数目的多少倍？A.1/2B.1C.2D.4树与图树与图椎咐筒刹翔甄拴拿匠呸僻耪暗汲头烷芦腥诸惺模鱼啡静娃匠慧辐溯家沂琳数据结构基础复习09数据结构基础复习0975v自测题自测题一个无向图采用邻接矩阵存储，该邻接一个无向图采用邻接矩阵存储，该邻接矩阵一定是一个矩阵一定是一个_A.对称矩阵对称矩阵B.对角矩阵对角矩阵C.三角矩阵三角矩阵D.稀疏矩阵稀疏矩阵树与图树与图票林栋砖面辊拧溪帚杂靡园盼伪需汀顺贺麻援擎秧拾吨券膏颅伐还编李绘数
58、据结构基础复习09数据结构基础复习0976树与图树与图v自测题自测题从邻接矩阵从邻接矩阵 可以看出，该图可以看出，该图共有（共有（ ）个顶点；如果是有向图该图）个顶点；如果是有向图该图共有（共有（ ） 条弧；如果是无向图，则共条弧；如果是无向图，则共有（有（ ）条边）条边 A.9, 5, 5B.3, 4, 2C.6, 3, 3D.1, 2, 2峪秉俄搔肤馅宪鳞魁绢危仆菏效母缮浚腻女辱音新蚕棉囱侵较答局体白砒数据结构基础复习09数据结构基础复习0977v图的遍历图的遍历深度优先深度优先(DFS)：类似于树的先序遍历。递：类似于树的先序遍历。递归，需要堆栈。邻接矩阵归，需要堆栈。邻接矩阵 O(n2
59、)；邻接表；邻接表 O(n+e)。广度优先广度优先(BFS)：类似于树的层次遍历。需：类似于树的层次遍历。需要队列。时间复杂度与要队列。时间复杂度与DFS相同。相同。树与图树与图垛贰泪一挣烯责抡蔚惺彭啥历玛仟啡妹缨践建砒深恰焊攫墨痴拿阐忍恭损数据结构基础复习09数据结构基础复习0978v自测题自测题已已知知无无向向图图为为G=(V, E)，其其中中，顶顶点点集集合合为为V = v1, v2, v3, v4, v5, v6, v7，边边的的集集合合为为E=(v1, v2), (v1, v3), (v2, v4), (v2, v6), (v4, v5), (v4, v7), (v5, v6)，请请
60、分分别别给给出出根根据据该该邻邻接接表表从从顶顶点点v1出出发发进进行行深深度度优优先先搜搜索索与与广广度度优优先先搜搜索索后后的的顶顶点序列。当有多种选择时，按序号先后访问。点序列。当有多种选择时，按序号先后访问。深度优先搜索序列：深度优先搜索序列：v1, v2, v4, v5, v6, v7, v3广度优先搜索序列：广度优先搜索序列：v1, v2, v3, v4, v6, v5, v7树与图树与图1234567氨蛔邯老揩狄佛举噎漏佑妙贼涂慕屁强耍惦暂吼斜棉宛讳舒桌释送誓鲸拽数据结构基础复习09数据结构基础复习0979v图的基本应用及其复杂度分析图的基本应用及其复杂度分析最小（代价）生成树最
61、小（代价）生成树普里姆普里姆(Prim)算法：一棵树的生长算法：一棵树的生长树与图树与图v1v2v6v7v3v4v52421310758461*复杂度为复杂度为 O(n2)，与边数无关，适合与边数无关，适合于求边稠密的网的于求边稠密的网的最小生成树。最小生成树。堂仍峙喉渔再额善舜犁千进岩袄襟阉轨撤厘稽氢估述傅酱希戍恨班淌诀隆数据结构基础复习09数据结构基础复习0980v图的基本应用及其复杂度分析图的基本应用及其复杂度分析最小（代价）生成树最小（代价）生成树克鲁斯卡尔克鲁斯卡尔(Kruskal)算法：森林的生长算法：森林的生长树与图树与图v1v2v6v7v3v4v52421310758461*
62、适合于求边稀适合于求边稀疏的网的最小生疏的网的最小生成树，成树，复杂度为复杂度为 O(e log e)。铀韭团柞允遏选圾检篆稠霞攀稿梆青付脸起铭割吹厦校胯醋岳冤失谢泛乍数据结构基础复习09数据结构基础复习0981v自测题自测题已知一个带权连通图已知一个带权连通图G=(V, E)，其中顶点，其中顶点集合为集合为V = 1, 2, 3, 4, 5，其邻接矩阵如，其邻接矩阵如图，求出其所有可能的最小生成树。图，求出其所有可能的最小生成树。树与图树与图 7 6 9 7 8 4 46 8 6 9 4 6 2 4 2 纽煮独娄疙靴叹胶扼膘娠车蚀睫涤罕益缮笋塌冠疟炮蚊的赶辈零皱跟组脏数据结构基础复习09数据
63、结构基础复习0982v图的基本应用及其复杂度分析图的基本应用及其复杂度分析最短路径最短路径单源（带权）最短路：迪杰斯特拉单源（带权）最短路：迪杰斯特拉(Dijkstra)算法算法 贪心，按长度递增生成，当新顶点使路径更短时，更新路径，贪心，按长度递增生成，当新顶点使路径更短时，更新路径，O(n2)。多源（带权）最短路：弗洛伊德多源（带权）最短路：弗洛伊德(Floyd)算法算法 O(n3)，但比重复，但比重复Dijkstra算法简单。算法简单。树与图树与图淹寿屁课讥蘸俗谋刹焦停昔铰莆按硒鹰揪说驴寇后寇咖戚漱者筋剃淮孽陋数据结构基础复习09数据结构基础复习0983v图的基本应用及其复杂度分析图的基
64、本应用及其复杂度分析拓扑排序：拓扑排序：有向无环图有向无环图(DAG)的应用之一的应用之一1.选一个无前驱顶点输出；选一个无前驱顶点输出；2.删除该顶点以及所有以之为尾的弧；删除该顶点以及所有以之为尾的弧；3.重复第重复第1、2步，直到全部顶点输出，或不存在无前驱顶点步，直到全部顶点输出，或不存在无前驱顶点(说说明有环明有环)。注意：注意：拓扑排序可方便检查有向图中是否存在环；拓扑排序可方便检查有向图中是否存在环；确定无环时，也可用确定无环时，也可用DFS进行拓扑排序，退出进行拓扑排序，退出DFS的顺序即的顺序即为逆向的拓扑序；为逆向的拓扑序；DFS可方便检查无向图中是否存在环可方便检查无向图
65、中是否存在环(若遇到回边即有环若遇到回边即有环)。树与图树与图弧巨赋们汀营误拟治阅崎椎逃趋崭贤繁桥烘崖陡葫隙拆蛔工拽判碑锗日峦数据结构基础复习09数据结构基础复习0984v图的基本应用及其复杂度分析图的基本应用及其复杂度分析关键路径：关键路径：AOE网网 带权带权DAG树与图树与图012345678startfinisha0=6a1=4a2=5a3=1a4=1a5=2a6=9a7=7a8=4a9=2a10=406457716141818161471056602323钙宰猾炼烧附膜廖骆陕拌锚权精媳唾想团枷瓢叮廊腋剥烫蛤垣滤灶执尉撂数据结构基础复习09数据结构基础复习0985v自测题自测题判断有向
66、图是否存在回路，除了可以利判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用用拓扑排序方法外，还可以利用_A.求关键路径的方法求关键路径的方法 B.求最短路径的求最短路径的Dijkstra方法方法 C.深度优先遍历算法深度优先遍历算法 D.广度优先遍历算法广度优先遍历算法 树与图树与图准煽眉奢契兔爵院糖厨坚癌沸网姐办寄桐赊共碘优手磋切政柜醇徽迭柒简数据结构基础复习09数据结构基础复习0986v自测题自测题弗洛伊德弗洛伊德(Floyd)算法是求图中每一对结点算法是求图中每一对结点之间最短路径的算法。请描述该算法，并之间最短路径的算法。请描述该算法，并且回答：如何用该算法判断图是否有回
67、路且回答：如何用该算法判断图是否有回路？请说明理由？请说明理由。树与图树与图 检查对角元检查对角元DN 1 ii，若存在非，若存在非 的对角元，就的对角元，就表明图中有回路。因为若表明图中有回路。因为若DN 1 ii非非 ，说明存在某，说明存在某个个k，使得，使得Dkii的值被更新为的值被更新为（Dk 1 ik + Dk 1 ki），即存在一条从），即存在一条从i到到k、再、再从从k到到i的路径。的路径。好硅碘彻控烛复篱债铡失臭赞钧馏位襟瘁哄派量锋姆砂恩向捎翰豪烟江行数据结构基础复习09数据结构基础复习0987v自测题自测题如何判断图中有负回路（即回路中边的权如何判断图中有负回路（即回路中边的
68、权值之和为负数）？请说明理由值之和为负数）？请说明理由。树与图树与图 将对角元将对角元Costii初始化为初始化为0，当，当Dk ii0时，图时，图中必存在负回路中必存在负回路 。厌爬村拇妊橇勇距辈涎臭身洒励应臣泥燥袒彩雷公嘱击直怜浇历变滩甲颊数据结构基础复习09数据结构基础复习0988查找与排序查找与排序v查找查找概念：概念：静态查找静态查找动态查找（随时插入删除）动态查找（随时插入删除）平均查找长度平均查找长度 = PiCi，其中，其中Pi为查找第为查找第i个记录的概个记录的概率，满足率，满足 Pi=1；Ci是找到第是找到第i个记录需要比较的次个记录需要比较的次数。数。当查找不成功的情况也
69、考虑在内时，当查找不成功的情况也考虑在内时，平均查找长度平均查找长度是（成功是（成功+不成功）的平均查找长度。不成功）的平均查找长度。雄你互饵肺庚鲸鼓猜览煮肃技梦帕匡蛆确徒踢欢松韵愁亲登冤鸣诊俊漆琉数据结构基础复习09数据结构基础复习0989v查找查找顺序查找法：顺序查找法：逐个比较。逐个比较。若对若对n个记录做等概率查找（即个记录做等概率查找（即Pi=1/n），则平均查），则平均查找长度为找长度为不成功的查找必定进行不成功的查找必定进行n+1次比较。设成功与不成次比较。设成功与不成功概率相同，都是功概率相同，都是1/2n，则平均查找长度为，则平均查找长度为缺点：效率低缺点：效率低优点：简单、
70、适用面广优点：简单、适用面广 对结构无要求，不要求有对结构无要求，不要求有序，也适用于链表。序，也适用于链表。查找与排序查找与排序(n+1)/2。3(n+1)/4。趁壳谩砷舒辨父物愤扎羹招吝剪遭蹿项居瘁阶章伟辩歪苍恤舷嫂馏猪绥寅数据结构基础复习09数据结构基础复习0990v查找查找折半查找法：折半查找法：有序有序表的查找表的查找成功查找的最多比较次数为成功查找的最多比较次数为等概率成功查找的平均查找长度为等概率成功查找的平均查找长度为优点：效率高优点：效率高缺点：只适用于有序表，且不适用于线性链表缺点：只适用于有序表，且不适用于线性链表查找与排序查找与排序 log2n +1。(1+1/n) l
71、og2 (n+1) - 1。墒帜臃萄祭梆硅骡折崖拥鸭饭炊逃颖秒炮下项鸭剖码燕篮莹孕睬冗奋迪详数据结构基础复习09数据结构基础复习0991v查找查找B树：平衡多路查找树树：平衡多路查找树查找与排序查找与排序111127139347536419911824378135每个结点至多有每个结点至多有m棵子树；棵子树；若根不是叶子，则至少有若根不是叶子，则至少有2棵子树；棵子树；除根之外所有非叶子结点至少有除根之外所有非叶子结点至少有 m/2 棵子树；棵子树；所有非叶子结点包含所有非叶子结点包含(n, p0, K1, p1, K2, p2, ., Kn, pn), 其中其中Ki为关键字且有序为关键字且有
72、序（递增）（递增）, pi所指子树中所有关键字所指子树中所有关键字Kn。所有叶子在同一层，为所有叶子在同一层，为NULL。4723在有在有N个关键字的个关键字的m阶阶B树树上进行查找，从根结点到上进行查找，从根结点到关键字所在结点的路径上关键字所在结点的路径上涉及的结点数不超过涉及的结点数不超过嘛臼桂又选刨膳衅郎惺熟湖同艾矾死藐踪燎磷揪棍痔蔚谊光寺缔锹酞验酷数据结构基础复习09数据结构基础复习0992v查找查找B树：插入、删除树：插入、删除查找与排序查找与排序303 12375061 701002453 90453030 372626 30 375061 7010053 90453 12372
73、4 26 8561 70 85453 123724 30 26 506110053 70 908570506110085539073 7 1224 45 703730263127703730263127506110085539024453 12375061 701002453 9045最小值最小值50最小值最小值615333753 701002461 9050612450汲绸辣帧椎怖评昂倦浩政十世钵肆唾哉汝觉朽械烫浑掣绞庭宁尉批甫歹驾数据结构基础复习09数据结构基础复习0993v自测题自测题下面关于下面关于m阶阶B树说法正确的是树说法正确的是（）A.每个结点至少有两棵非空子树每个结点至少有两棵
74、非空子树B.树中每个结点至多有树中每个结点至多有m一一1个关键字个关键字C.所有叶子在同一层上所有叶子在同一层上D.当插入一个数据项引起当插入一个数据项引起B树结点分裂后，树树结点分裂后，树长高一层长高一层查找与排序查找与排序呸伏索萍珐脾鉴衰咙盆奸掂击蔓涉稚笋审狸舜续践缮浚卑模话捐难髓临适数据结构基础复习09数据结构基础复习0994v自测题自测题B-树中叶子结点数树中叶子结点数s与关键字数与关键字数n的关系是的关系是A.s = n/2B.s = n-1C.s = n+1 D.无法确定无法确定查找与排序查找与排序设设B-树第树第i个结点的子树数为个结点的子树数为Ci，则该结，则该结点的关键字数点
75、的关键字数Ni=Ci-1。 对于有对于有k个结点的个结点的B-树：树：n = Ni =(Ci-1) =Ci-k 每个结点（除根结点）都是一棵子树：每个结点（除根结点）都是一棵子树：Ci = (k-1)+s 淡妓活蛇痪张麓瘪派瘴锅狄皿觉戴未或舷殆偷酿忘更唤骂耿拾傅诅秩骆颇数据结构基础复习09数据结构基础复习0995v查找查找散列散列(Hash)表及其查找表及其查找关键问题：关键问题：设计哈希函数设计哈希函数解决同义词冲突解决同义词冲突哈希函数：（哈希函数：（任一关键字等概率映射到任一地址的哈希函任一关键字等概率映射到任一地址的哈希函数是均匀数是均匀(Uniform)的）的）各种方法（各种方法（p
76、.253-256，其中，其中key%p最常见）最常见）冲突处理冲突处理开放定址法：线性、二次（开放定址法：线性、二次（ ）、伪随机探测再散列）、伪随机探测再散列再哈希法（冲突时计算另一个哈希函数地址）再哈希法（冲突时计算另一个哈希函数地址）链地址法（同义词链表）链地址法（同义词链表）查找与排序查找与排序猛馈谭蕴重倾徊因轨凸肉厨辖谷绥器鸳组鲸弄呕馋捆甭忱芯顶标疚溉滋蔚数据结构基础复习09数据结构基础复习0996v查找查找散列散列(Hash)表及其查找表及其查找查找分析查找分析装填因子装填因子哈希表的平均查找长度是哈希表的平均查找长度是 的的函数，而不是函数，而不是 n 的函数的函数从非链地址处理
77、冲突的哈希表中从非链地址处理冲突的哈希表中删除删除一个记录，须在该记一个记录，须在该记录的位置上填入一个特殊符号，以免找不到在它之后填入录的位置上填入一个特殊符号，以免找不到在它之后填入的同义词的同义词对于预先知道且规模不大的关键字集，应尽力设计不发生对于预先知道且规模不大的关键字集，应尽力设计不发生冲突的完美哈希函数冲突的完美哈希函数查找与排序查找与排序边洗弗冒卉涂炔逆呼铰辗悟背留耀触酿益猴丹演庇间恫痔但镀混憎盯融话数据结构基础复习09数据结构基础复习0997v自测题自测题下面关于哈希查找的说法正确的是下面关于哈希查找的说法正确的是（）A.哈希函数构造的越复杂越好，因为这样随机性哈希函数构造
78、的越复杂越好，因为这样随机性好，冲突小好，冲突小 B.除留余数法是所有哈希函数中最好的除留余数法是所有哈希函数中最好的 C.不存在特别好与坏的哈希函数，要视情况而定不存在特别好与坏的哈希函数，要视情况而定D.若需在哈希表中删去一个元素，不管用何种方若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可法解决冲突都只要简单的将该元素删去即可查找与排序查找与排序奇簇涝妥虽峙繁家铅阑绥奴首目捉侮宦劳毅喻厕贱割绊蒙哑蓟遂浮诊鄙悄数据结构基础复习09数据结构基础复习0998v自测题自测题设有一组记录的关键字为设有一组记录的关键字为 19，14，23，1，68，20，84，27，5
79、5，11，10，79，用链地址，用链地址法构造散列表，散列函数为法构造散列表，散列函数为H（key）=key MOD 13，散列地址为，散列地址为1的链中有几个记录？的链中有几个记录？ A.1B.2C.3D.4查找与排序查找与排序植答物黍缎福磷灶柒言侣隆授获桅虞缠注捅草吸诡策聚倡涣钎在桐懂祈传数据结构基础复习09数据结构基础复习0999v自测题自测题设哈希表长设哈希表长m14，哈希函数，哈希函数H（key）key11。表中已有。表中已有4个结点：个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余，其余地址为空。如果用二次探测再散列处理冲突，地址
80、为空。如果用二次探测再散列处理冲突，关键字为关键字为49的结点的地址是的结点的地址是 A.8B.3C.5D.9查找与排序查找与排序粱汛掠昼德逞捎忆刃咒渗殖胡晓企碉衡蔬博律羔秉铬夹隐旗哨招驾障望犯数据结构基础复习09数据结构基础复习09100v内部排序内部排序概念概念基本操作：比较基本操作：比较 + 移动移动存储方式：存储方式：数组：必须移动记录数组：必须移动记录静态链表：表排序，仅修改指针静态链表：表排序，仅修改指针数组数组+地址：地址排序，然后调整记录位置地址：地址排序，然后调整记录位置稳定稳定的排序法：关键字等值的记录在排序前后的先的排序法：关键字等值的记录在排序前后的先后位置不变后位置不
81、变查找与排序查找与排序培虚缄蒙图募傅趴备郧筑蝇僻蚜虱婪倔拜耘也奏抉誉肉攫桌唆酚相阜汁羡数据结构基础复习09数据结构基础复习09101v内部排序内部排序插入排序插入排序直接插入排序：理扑克牌的过程。正序最快直接插入排序：理扑克牌的过程。正序最快O(n)，逆序最慢逆序最慢O(n2)，平均，平均O(n2)。折半折半插入排序：查找的过程用插入排序：查找的过程用“折半查找折半查找”，减少了，减少了比较次数，但移动次数不变，还是比较次数，但移动次数不变，还是O(n2)。气泡排序气泡排序(bubble sort)每趟比较相临记录，最大值沉入水底。每趟比较相临记录，最大值沉入水底。复杂度与直接插入排序类似。复
82、杂度与直接插入排序类似。查找与排序查找与排序液湛铬擂垮栏嗓棺颅猪锭磐释叶奋柜甄棕埠猛量蛀满早淋晤尔蚂掏舒北络数据结构基础复习09数据结构基础复习09102v自测题自测题用直接插入排序方法对下面四个序列进行用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的排序（由小到大），元素比较次数最少的是哪个？是哪个？A.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80C.21,32,46,40,80,69,90,94D.90,69,80,46,21,32,94,40查找与排序查找与排序搭绳了寂烧审羞污哟灭北匀汐足快日拧荷蜗殊严合兴厚佛脚
83、忠锁沾肪轮邦数据结构基础复习09数据结构基础复习09103v自测题自测题若用冒泡排序方法对序列若用冒泡排序方法对序列 10, 14, 26, 29, 41, 52 从大到小排序，需进行多少次比从大到小排序，需进行多少次比较较？A.3B.10C.15D.25查找与排序查找与排序5+4+3+2+1 = 15戎中囚衬沙闲窜铡恨无嫌并蹦卉镑锄椰赶笋按磅膛浩茅蛋吁菜建您碌翘俱数据结构基础复习09数据结构基础复习09104v内部排序内部排序简单选择排序简单选择排序方法：每次从未排序的序列中（方法：每次从未排序的序列中（i n1）找关键字）找关键字最小的记录，与第最小的记录，与第 i 个记录交换。个记录交换
84、。复杂度：移动少，正序不动，逆序复杂度：移动少，正序不动，逆序 O(n)；但比较次；但比较次数恒为数恒为 n(n1)/2。总复杂度还是。总复杂度还是 O(n2)。 查找与排序查找与排序弥俭壁某上款匙板偏显胰它槐幼如凉业敏桑甜醋哆擒坍瞒幅亏缨永球贴契数据结构基础复习09数据结构基础复习09105v内部排序内部排序希尔希尔(Shell)排序排序方法：对分割出的若干子序列分别进行直接插入排序，方法：对分割出的若干子序列分别进行直接插入排序，直到基本有序，再对全部记录进行一次直接插入排序。直到基本有序，再对全部记录进行一次直接插入排序。所用时间是增量序列的函数所用时间是增量序列的函数增量序列的取法：注
85、意应使增量序列中的值没有除增量序列的取法：注意应使增量序列中的值没有除1以外的公因子，并且最后一个增量必须等于以外的公因子，并且最后一个增量必须等于1。查找与排序查找与排序搏最船骋砾粱耿枯妈粹葡银角凹溜蛋盎韧署绷艳潘蜜序怔历畜街亥赔措持数据结构基础复习09数据结构基础复习09106v内部排序内部排序快速排序快速排序方法：以枢轴（支点）将记录分割为两部分，递归方法：以枢轴（支点）将记录分割为两部分，递归注意：不同教材处理支点位置的方法不同注意：不同教材处理支点位置的方法不同平均时间复杂度为平均时间复杂度为O(nlogn)，且常数因子在同数量，且常数因子在同数量级的此类排序法中最小级的此类排序法中
86、最小需要栈空间实现递归，最坏情况深度可达需要栈空间实现递归，最坏情况深度可达n。若每趟。若每趟排序后先对长度短的子序列递归，则栈的最大深度排序后先对长度短的子序列递归，则栈的最大深度为为O(logn)查找与排序查找与排序谢蝴厉棕涕吟智零钱酵敛浆眨纲涣工汽沙今粒蛛弗扒瑞蕊袋鳞弟债芭棠寄数据结构基础复习09数据结构基础复习09107v内部排序内部排序堆排序堆排序堆：完全二叉树，对应一维数组。任一非叶子结点堆：完全二叉树，对应一维数组。任一非叶子结点的值不大于（或不小于）其孩子结点的值。根结点的值不大于（或不小于）其孩子结点的值。根结点必包含最小（或最大）值。必包含最小（或最大）值。堆的建立：自底向
87、上反复堆的建立：自底向上反复“筛选筛选”的过程。的过程。排序：反复调整排序：反复调整“大顶堆大顶堆”，将顶换到末尾。，将顶换到末尾。最坏复杂度最坏复杂度 O(nlogn)，且仅需，且仅需1个额外辅助空间。个额外辅助空间。查找与排序查找与排序蓬峻胃惧丝能旨从滥咨垢区孝撼薛钾吗牟壁猜履滑葱兽蔽拙狂导股风鞍榆数据结构基础复习09数据结构基础复习09108v自测题自测题设有关键码序列设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列，下面哪一个序列是从上述序列出发建堆的结果出发建堆的结果？A.a，g，h，m，n，p，q，x，z B.a，g，m，h，q，n，p，x，z C.
88、g，m，q，a，n，p，x，h，z D.h，g，m，p，a，n，q，x，z 查找与排序查找与排序qgmzanpxhagmhqnpxz购葫页视毖涅轧琢苫抵祭篙伟角迭烁年往擅蛇剑潍待强首姨汹挣槽封曳咖数据结构基础复习09数据结构基础复习09109v内部排序内部排序归并排序归并排序(merge sort)非递归实现：非递归实现：2路归并路归并复杂度复杂度 O(nlogn)，需要需要 O(n)额外空间额外空间稳定稳定很少用于内部排序很少用于内部排序查找与排序查找与排序镑东哮秒驾最痔丫劫堵猖岗痰折辆揪幂床秸要妆版液奸球榔坝啤讨乐最君数据结构基础复习09数据结构基础复习09110v内部排序内部排序基数排序
89、基数排序多关键字排序：多关键字排序：(K0, K1, ., Kd-1)最高位优先法最高位优先法MSD：必须逐层分割成子序列，分别排序：必须逐层分割成子序列，分别排序最低位优先法最低位优先法LSD：不分子序列，对每个：不分子序列，对每个Ki都是整个序列都是整个序列参加排序。若对参加排序。若对Ki(0 i d-2)的不同值，的不同值，Ki+1均取相同值均取相同值（例如扑克牌不同面值对应相同花色），则可不用比较关（例如扑克牌不同面值对应相同花色），则可不用比较关键字排序的方法，而是通过键字排序的方法，而是通过“分配分配”和和“收集收集”实现排序实现排序链式基数排序：链式基数排序：K = (K0, K
90、1, ., Kd-1)，如，如13=(1,3)分解出的每个分解出的每个Ki都在相同范围内，按都在相同范围内，按LSD反复分配、收集反复分配、收集即可。即可。分配分配 O(n) + 收集收集 O(r) * d趟分配和收集；趟分配和收集；O(r+n)空间空间查找与排序查找与排序秽靠捷株艇爵资褪颖罢扎践倡麻督喘肖脸印历盂锁愤备邀隧鸯沉舅苟反缮数据结构基础复习09数据结构基础复习09111v内部排序内部排序各种内部排序算法的比较各种内部排序算法的比较查找与排序查找与排序排序方法排序方法平均时间平均时间最坏情况最坏情况辅助存储辅助存储简单排序简单排序O( n2 )O( n2 )O( 1 )快速排序快速排
91、序O( n log n )O( n2 )O( log n )堆排序堆排序O( n log n )O( n log n )O( 1 )归并排序归并排序O( n log n )O( n log n )O( n )基数排序基数排序O( d ( n + r )O( d ( n + r )O( r + n )值躇坝启围驶耗腿炒詹冉虎知咽纬吴追作签菇狸碴惦猖隧迭菏休咋左太凑数据结构基础复习09数据结构基础复习09112v内部排序内部排序各种内部排序算法的比较各种内部排序算法的比较平均时间：快速排序最优，但其最坏情况不好。平均时间：快速排序最优，但其最坏情况不好。归并在归并在 n 大时比堆排序快，但需要空间
92、多。大时比堆排序快，但需要空间多。直接插入排序在基本有序或直接插入排序在基本有序或 n 小时好用。小时好用。基数排序适合基数排序适合 n 大而关键字小的排序；若关键字也大而关键字小的排序；若关键字也大，且大多数大，且大多数K0不同，则也可用不同，则也可用MSD。基数排序和简单排序（插入、气泡、选择）是稳定基数排序和简单排序（插入、气泡、选择）是稳定的；快速排序、堆排序、希尔排序是不稳定的。一的；快速排序、堆排序、希尔排序是不稳定的。一般比较相邻关键字的算法是稳定的。般比较相邻关键字的算法是稳定的。比较排序最坏情况下的最好复杂度为比较排序最坏情况下的最好复杂度为 O(nlogn)。查找与排序查找
93、与排序稽虎筷玄踪巷剐影憋旺彪琳晾庇唇墙市冒磨洒桩棕庶廊奉域堪男配匹图余数据结构基础复习09数据结构基础复习09113v自测题自测题以顺序表为存储结构，在以顺序表为存储结构，在300000个任意排个任意排序的数据中选择前序的数据中选择前100个最大值，下列哪个最大值，下列哪种算法最快？种算法最快？A.快速排序快速排序B.堆排序堆排序C.归并排序归并排序D.插入排序插入排序查找与排序查找与排序炸绢靠移烹仔云攘椰朴玫恰祭恼焕够檬棋呈买左驯女耙瑞铝疤句昧磨屑创数据结构基础复习09数据结构基础复习09114v自测题自测题在内部排序中，排序不稳定的有在内部排序中，排序不稳定的有A.插入排序插入排序B.冒泡排序冒泡排序C.快速排序快速排序D.归并排序归并排序查找与排序查找与排序迅镰害秃赏辜譬抨脾握炊刘茵摇幅歇赦或仆藏炎辛寇近称碉蔑重杏磺锋炽数据结构基础复习09数据结构基础复习09115
