四川广播电视大学</ti= tle> <o:SmartTagType namespaceuri=3D"urn:schemas-microsoft-com:office:smarttags" name=3D"chsdate"/>  <style>  </style>  </head> <body bgcolor=3Dsilver lang=3DZH-CN style=3D'tab-interval:21.25pt;text-just= ify-trim: punctuation'> <div class=3DSection1 style=3D'layout-grid:14.3pt'> 四川广播电෇= 0;大学<o:p></o:p> <p class=3DMsoNormal align=3Dcenter style=3D'margin-top:0cm;margin-right:-8= 9.85pt; margin-bottom:0cm;margin-left:21.0pt;margin-bottom:.0001pt;text-align:cente= r; mso-line-height-alt:17.0pt;mso-outline-level:1'>《数据结构Ӎ= 9;<o:p= ></o:p> <p class=3DMsoNormal align=3Dcenter style=3D'margin-top:0cm;margin-right:-8= 9.85pt; margin-bottom:0cm;margin-left:21.0pt;margin-bottom:.0001pt;text-align:cente= r; mso-line-height-alt:17.0pt;mso-outline-level:1'>期末总复习ࡡ= 0;考题类型</= span><o:p= ></o:p> <o:p> </o:p> <![if !supportLists]>第= ;一章 = <![endif]>ಱ= 0;论<o:p></o:p> = <s= pan style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman"'>数据结构研究的= 是数据的表示和数据= 0043;间的关系，逻辑上෸= 2;，数据结构有集合、&= #32447;性，树和图四种。= 412;章主要介绍数据结构= ;课程中一些常用术语&#= 30340;含义，常用数据结ĉ= 00;的表示，面向对象的= 概念（抽象数据类型= 1450;数据抽象和信息隐൒= 9;原则），C++语言= 中一些常用系统头文= 0214;的作用及各种数据౲= 7;型的使用（简单类型&= #65292;数组，字符串，记= 405;，文件），函数参数= ;的传递方式及函数和&#= 36816;算符重载的使用，ļ= 39;法的时间复杂度和空= 间复杂度评价方法等= 0869;容。通过本章学习ᦁ= 2;要求同学们： <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握集合、线性= 结构、树和图的二元= 2452;及图形表示<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>了解抽象数据类= 型的定义和应用<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>复习C++语= 5328;中的有关知识，重୅= 7;是指针概念，数据类&= #22411;（重点是简单类= 型、数组、记录，了= 5299;字符串、文件），࠲= 9;数参数的传递方式，&= #20102;解函数重载和运算= 526;重载的使用<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握评价算法的= 一般规则，算法时间= 2797;杂度的定义和数量ಪ= 3;表示，了解最好、平&= #22343;、最差的含义，了#= 299;空间复杂度的定义及= ;表示<o:p></o:p> <o:p> </o:p> 例题<o:p></o:p> <o:p> = ;</o:p> 1<s= pan style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman"'>．设a是一个一维数组= 1517;，则= a+i਷= 9;下标为= i௚= 0;元素的＿＿，＊(a+i) 是下标为= i௚= 0;元素的＿＿<o:p></o:p> 分析：弄懂C++中地= 址与指针的概念，单= 9420;一个数组名的含义ᦁ= 2;地址与一个整数相加&= #30340;含义 <o:p> = ;</o:p> 2<s= pan style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman"'>．求时间复杂度：= 如以下的求n!௚= 0;递归函数<o:p></o:p> long f(i= nt n) { if (n=3D=3D0) re= turn 1; else</sp= an> re= turn n*f(n-1); }</= p> 分析：由于每执行Ç= 68;次递归调用就是执行= 一条条件语句，执行= 5972;个算法需要进行n+1次调= 用，所以其时间复杂= 4230;为Ｏ(n) <o:p>&= nbsp;</o:p> 3</spa= n>．下面程序段的= 时间复杂度为＿＿．</s= pan> for <= /span>（i= nt i=3D0; i</sp= an><m; i++）<= /p> for (int j=3D0; j<n; j++) a[i][j]=3Di*j; 结果：n(n+1)/2 <o:p>&= nbsp;</o:p> <![if !supportLists]>第= ;二章 = <![endif]>ಬ= 7;性表<o:p></o:p> <o:p>&= nbsp;</o:p> 本章主要介绍线= 性表的定义和它的抽= 5937;数据类型，线性表௚= 0;顺序存储结构及每种&= #32447;性表操作在顺序结= 500;上的具体实现，链接= ;存储的概念，线性表&#= 30340;链接存储结构及每ķ= 81;线性表操作在链接存= 储结构上的具体实现= 1561;内容。通过本章学ߖ= 4;，要求同学们： <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握线性表的顺= 序存储结构（类型定= 0041;为List,它含有两个域&#= 65306;一个为数组list域，用于存储= 2447;性表的所有元素，ࡣ= 8;一个为变量size域，用于存储= 2447;性表的长度，即元ಃ= 2;的个数）和抽象数据&= #31867;型中定义的每一种= 805;作的含义，在顺序存= ;储方式下每一种操作&#= 30340;算法描述和相应的ą= 02;间复杂度<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握链接存储的= 概念（包括线性表的= 1333;、双向、循环、带༆= 8;加表头结点的链接存&= #20648;结构），单链表的= 420;立结点（类型定义为= ;LNode,</= span>它包含两个域data和next，Ñ= 98;别用于存储一个元素= 和一个指向后继结点= 0340;指针）链接存储结ਗ਼= 0;，在此方式下每一种&= #25805;作的算法描述和相= 212;的时间复杂度<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>了解单链表的数= 组结点（类型定义为<sp= an class=3DSpellE>ALNode,<= /span>它包含两个域data和next，Ñ= 98;别用于存储一个元素= 和一个后继结点的下= 6631;）链接存储结构，ࢷ= 2;此方式下每一种操作&= #30340;算法描述和相应的= 102;间复杂度<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>了解顺序存储和= 单链表的独立结点存= 0648;结构下的其它一些ਔ= 5;作的算法描述<o:p></o:p> <o:p> </o:p> 例题<o:p></o:p> 在熟练掌握线性表į= 40;各种操作的基础上，= 应注意针对不同情况= 9979;的灵活应用。 1．在线性表的顺序é= 84;储中，若一个元素的= 下标为i，则它的前驱元素į= 40;下标为＿＿，后继元= 素的下标为＿＿。 2. HL</spa= n>为表头指针的带= 表头附加结点的单链= 4920;和循环单链表中，໦= 2;表为空的条件分别为<= /span>______________和<= span lang=3DEN-US>_______________。<= /p> 3. 在循= 环双向链表中表头结= 8857;的左指针域指向＿ᦆ= 3;＿结点，表尾结点的&= #21491;指针域指向＿＿＿ = 467;点。 4. 在线性表单链接存Î= 48;中，若一个元素所在= 结点的地址为p，则其后&#= 32487;结点的地址为＿＿ʌ= 92;若假定p为一个数&#= 32452;a中的下标&#= 65292;则其后继结点的下Ċ= 31;为＿＿。 5<s= pan style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman"'>．设L是具有List౲= 7;型的一个线性表，写&= #20986;把表尾元素删除并= 351;之插入到表头位置的= ;算法<o:p></o:p> 分析：首先要排除</spa= n>L是空表的&#= 24773;况，然后要保存表ì= 14;元素到一个变量中，= 再按照插入一个元素= 1040;表头的方法，从后ࡨ= 1;前依次后移每个元素&= #65292;最后将该变量赋给"= 920;头元素 void delete(list& L)</spa= n> { if L.s= ize=3D=3D0 { cerr<<”empty list!”<<endl; exit(</s= pan>1);} elemtype x=3DL.list[size-1]; for (<s= pan class=3DSpellE>int i=3DL.size-1; i>=3D0; i--) L.list[i+1]=3DL.list[i]; L.list[0]=3Dx; }</= p> 注意：此循环中循Ĩ= 15;次数是size, 移动= 元素的个数是size（而= 非size-1）<= /p> 补充：在一个长度È= 26;n 的顺序存&#= 20648;线性表中，向第i个元素（1<=3Di<=3Dn+1）之前插入一个= 新元素时，需要从后= 1521;前依次后移＿＿个ࠠ= 3;素． 　　　　</= span>A．= n-i </spa= n>　　 B．n-i+1　<= span lang=3DEN-US> C</= span>．n-i-1 　　 D．i</span= > <o:p> = ;</o:p> 6<s= pan style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman"'>．在一个单链表<= span lang=3DEN-US style=3D'mso-fareast-font-family:SimHei'>(ಮ= 7;点类型为= LNode) ᦄ= 0;Ｌ中，写出删除由指&= #38024;q৓= 2;指结点的后继结点的&= #31639;法<o:p></o:p> 分析：可以先定义Ç= 68;个指针变量p，使其指&#= 21521;q的后继结&#= 28857;，然后让q的指针域&#= 25351;向p的后继结&#= 28857;，最后释放p结点 void delete(LNode*& HL, LNode* q)= <o:p></o:p> { if q->next=3D=3DNULL{<o:p></o:p> cerr</s= pan><<”q has no next node!”<<endl;<o:p></o:p= > exit(</s= pan>1);}<o:p></o:p> LNode* p=3Dq->next;<o:p></o:p> q->next=3Dp->next;<o:p></o:p>= delete p= ; <o:p></o:p> return ;= <o:p></o:p> }<o:p></o:p>= 思考：①如果是要在q结点后插&#= 20837;一个结点p 呢？②= ;在表头后插入一= 个结点p 呢？ 结果：①应执行 p->next=3Dq->next; q->next=3Dp; <sp= an style=3D'font-family:SimSun;mso-hansi-font-family:"Times New Roman"'>②= ;应执行 p->next=3DHL; HL=3Dp; <o:p> </o:p> P94,= 习题<st1:chsdate IsROCDate=3D"False" IsLunarDate=3D"False" Day=3D"30" Month=3D"12" Year=3D"1899" w:st=3D"on"><sp= an lang=3DEN-US>2.3.4</st1:chsdate>, 2.3.5, 2.4.7, 2.3.7 <o:p>&= nbsp;</o:p> <![if !supportLists]>第= ;三章 <!= [endif]>ళ= 2;疏矩阵和广义表<o:p></o:p> <o:p>&= nbsp;</o:p> 本章主要介绍稀ு= 5;矩阵的概念和存储结&= #26500;以及相应运算的算= 861;，广义表的概念和存= ;储结构以及相应运算&#= 30340;算法。通过本章学È= 64;，要求同学们： <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握稀疏矩阵的= 定义，三元组线性表= 4920;示，顺序存储结构ࡴ= 4;每一种链接存储结构<= span lang=3DEN-US><o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>了解对稀疏矩阵= 进行的每一种运算的= 6041;法和时间复杂度，ߚ= 2;解相应的算法描述<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握广义表的定= 义，它的链接存储结= 6500;，以及求广义表长ॷ= 0;，深度的方法和递归&= #31639;法<o:p></o:p> <o:p> </o:p> 例题<o:p></o:p> １．在稀疏矩&#= 38453;的十字链接存储中ʌ= 92;每个行单链表中的结= 点都具有相同的＿＿= 5292;每个列单链表中的ಮ= 7;点都具有相同的＿＿<= /span> 分析：存储稀疏= 矩阵的元素是三元组= 4418;式，即非零元素的ඡ= 2;号，列号及元素值。&= #39034;序存储是将三元组= 803;素存储在一个一维数= ;组中；带行指针链接&#= 23384;储是将具有相同行Ö= 95;的三元组结点按列号= 从小到大顺序存储在= 1508;个行单链表中，共੍= 7;m（= m为稀疏矩阵行数= ）个行单链表；十字= 8142;接存储是将三元组ಮ= 7;点既存于行单链表中&= #65292;又存于列单链表中A= 307;因此行单链表中的结= ;点都具有相同行号，&#= 21015;单链表中的结点都Ð= 55;有相同列号 <o:p> </o:p> 2. 在一个稀疏矩阵中ʌ= 92;每个非零元素所对应= 的三元组包括该元素= 0340;_______、<= span lang=3DEN-US>_______和<= span lang=3DEN-US>________三项= 。 <o:p> </o:p> <![if !supportLists]>第= ;四章 <!= [endif]>੧= 2;和队列<o:p></o:p> <o:p>&= nbsp;</o:p> 本章主要介绍栈௚= 0;定义和它的抽象数据&= #31867;型，栈的存储结构= 644;进行操作的算法描述= ;，利用栈求表达式的&#= 20540;，栈在递归算法执Ŝ= 92;中的作用，队列的定= 义和它的抽象数据类= 2411;，队列的存储结构ࡴ= 4;进行操作的算法描述&= #31561;内容。通过本章学= 064;，要求同学们： <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握在栈的抽象= 数据类型中定义的每= 9968;种操作在顺序存储ࡴ= 4;链接存储上分别实现&= #30340;算法，以及相应的= 102;间复杂度<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握算术表达式= 的中缀表示和后缀表= 1034;及其相互转换的规࠵= 7;，进行后缀表达式求&= #20540;的方法，把中缀表$= 798;式转换为后缀表达式= ;的方法，了解栈在递&#= 24402;算法执行中作用<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握队列的定义= 及顺序存储结构和链= 5509;存储结构，队列的ે= 9;一种操作在顺序存储&= #21644;链接存储上分别实= 616;的算法，以及相应的= ;时间复杂度<o:p></o:p> <o:p> </o:p> 例题<o:p></o:p> 在熟练掌握栈，队Ò= 15;的各种操作的基础上= ，应注意针对不同情= 0917;下的灵活应用。 <o:p> = ;</o:p> １．当利用大小为ʍ= 26;的数组顺序存储一个= 栈时，假定用top=3D=3DN表示= 栈空，则向这个栈插= 0837;一个元素时，首先ॵ= 2;执行＿＿＿语句修改<= /span>top指针= ． 答案：top-- ２．෶= 5;算后缀算术表达式<s= pan lang=3DEN-US style=3D'mso-fareast-font-family:SimHei'>8 5= 6＋2ᦁ= 0;＋１０／＠的值<o:p></o:p> 分析：从左到右扫ÿ= 51;表达式，并按规则进= 行处理： 规则１当是操作数ą= 02;，则压入栈中 规则２当是运算符ą= 02;，则弹出栈中两个操= 作数并计算，结果再= 1387;入栈中 <table class=3DMsoNormalTable border=3D1 cellspacing=3D0 cellpadding=3D0 style=3D'margin-left:28.9pt;border-collapse:collapse;border:none;mso-borde= r-alt: solid windowtext 3.0pt;mso-padding-alt:0cm 5.4pt 0cm 5.4pt;mso-border-insi= deh: 3.0pt solid windowtext;mso-border-insidev:3.0pt solid windowtext'> <tr style=3D'mso-yfti-irow:0;mso-yfti-firstrow:yes;page-break-inside:avoid; height:15.9pt'> <td width=3D50 valign=3Dtop style=3D'width:37.3pt;border:solid windowtext= 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:15.9pt'> 6= </td> <td width=3D51 rowspan=3D3 valign=3Dtop style=3D'width:37.9pt;border:soli= d windowtext 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:15.9pt'> <o:p> </o:p><= /p> </td> <td width=3D56 valign=3Dtop style=3D'width:42.3pt;border:solid windowtext= 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:15.9pt'> <o:p> </o:p><= /p> </td> <td width=3D49 rowspan=3D3 valign=3Dtop style=3D'width:36.5pt;border:soli= d windowtext 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:15.9pt'> <o:p> </o:p><= /p> </td> <td width=3D55 valign=3Dtop style=3D'width:41.3pt;border:solid windowtext= 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:15.9pt'> 2 </td> <td width=3D45 rowspan=3D3 valign=3Dtop style=3D'width:33.9pt;border:soli= d windowtext 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:15.9pt'> <o:p> </o:p><= /p> </td> <td width=3D56 valign=3Dtop style=3D'width:42.3pt;border:solid windowtext= 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:15.9pt'> <o:p> </o:p><= /p> </td> </tr> <tr style=3D'mso-yfti-irow:1;page-break-inside:avoid;height:17.0pt'> <td width=3D50 valign=3Dtop style=3D'width:37.3pt;border:solid windowtext= 3.0pt; border-top:none;mso-border-top-alt:solid windowtext 3.0pt;padding:0cm 5.4= pt 0cm 5.4pt; height:17.0pt'> 5= </td> <td width=3D56 valign=3Dtop style=3D'width:42.3pt;border-top:none;border-= left:none; border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3.0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:17.0pt'> 11 </td> <td width=3D55 valign=3Dtop style=3D'width:41.3pt;border-top:none;border-= left:none; border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3.0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:17.0pt'> 11 </td> <td width=3D56 valign=3Dtop style=3D'width:42.3pt;border-top:none;border-= left:none; border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3.0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:17.0pt'> 22 </td> </tr> <tr style=3D'mso-yfti-irow:2;mso-yfti-lastrow:yes;page-break-inside:avoid; height:16.75pt'> <td width=3D50 valign=3Dtop style=3D'width:37.3pt;border:solid windowtext= 3.0pt; border-top:none;mso-border-top-alt:solid windowtext 3.0pt;padding:0cm 5.4= pt 0cm 5.4pt; height:16.75pt'> 8= </td> <td width=3D56 valign=3Dtop style=3D'width:42.3pt;border-top:none;border-= left:none; border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3.0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:16.75pt'> 8 </td> <td width=3D55 valign=3Dtop style=3D'width:41.3pt;border-top:none;border-= left:none; border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3.0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:16.75pt'> 8 </td> <td width=3D56 valign=3Dtop style=3D'width:42.3pt;border-top:none;border-= left:none; border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3.0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:16.75pt'> 8 </td> </tr> </table> <o:p> = ;</o:p> <table class=3DMsoNormalTable border=3D1 cellspacing=3D0 cellpadding=3D0 style=3D'margin-left:28.9pt;border-collapse:collapse;border:none;mso-borde= r-alt: solid windowtext 3.0pt;mso-padding-alt:0cm 5.4pt 0cm 5.4pt;mso-border-insi= deh: 3.0pt solid windowtext;mso-border-insidev:3.0pt solid windowtext'> <tr style=3D'mso-yfti-irow:0;mso-yfti-firstrow:yes;page-break-inside:avoid; height:24.0pt'> <td width=3D63 valign=3Dtop style=3D'width:47.0pt;border:solid windowtext= 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:24.0pt'> <o:p>&nb= sp;</o:p> </td> <td width=3D78 rowspan=3D3 valign=3Dtop style=3D'width:58.5pt;border:soli= d windowtext 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:24.0pt'> <o:p> </o:p><= /p> </td> <td width=3D54 valign=3Dtop style=3D'width:40.2pt;border:solid windowtext= 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:24.0pt'> <o:p> </o:p><= /p> </td> <td width=3D83 rowspan=3D3 valign=3Dtop style=3D'width:62.25pt;border:sol= id windowtext 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:24.0pt'> <o:p> </o:p><= /p> </td> <td width=3D49 valign=3Dtop style=3D'width:36.45pt;border:solid windowtex= t 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:24.0pt'> <o:p> </o:p><= /p> </td> </tr> <tr style=3D'mso-yfti-irow:1;page-break-inside:avoid;height:16.75pt'> <td width=3D63 valign=3Dtop style=3D'width:47.0pt;border:solid windowtext= 3.0pt; border-top:none;mso-border-top-alt:solid windowtext 3.0pt;padding:0cm 5.4= pt 0cm 5.4pt; height:16.75pt'> <o:p>&nb= sp;</o:p> </td> <td width=3D54 valign=3Dtop style=3D'width:40.2pt;border-top:none;border-= left:none; border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3.0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:16.75pt'> 10 </td> <td width=3D49 valign=3Dtop style=3D'width:36.45pt;border-top:none;border= -left: none;border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3= .0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:16.75pt'> <o:p> </o:p><= /p> </td> </tr> <tr style=3D'mso-yfti-irow:2;mso-yfti-lastrow:yes;page-break-inside:avoid; height:16.65pt'> <td width=3D63 valign=3Dtop style=3D'width:47.0pt;border:solid windowtext= 3.0pt; border-top:none;mso-border-top-alt:solid windowtext 3.0pt;padding:0cm 5.4= pt 0cm 5.4pt; height:16.65pt'> 30</span= > </td> <td width=3D54 valign=3Dtop style=3D'width:40.2pt;border-top:none;border-= left:none; border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3.0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:16.65pt'> 30 </td> <td width=3D49 valign=3Dtop style=3D'width:36.45pt;border-top:none;border= -left: none;border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3= .0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:16.65pt'> 3 </td> </tr> </table> <![if !supportLists]>8 <![endif]>5 6ᦁ= 1;2ᦁ= 0;＋10ᦁ= 5;＠=3D3<o:p></o:p></span= > <o:p> </o:p> ３．ࠥ= 5;有nߑ= 0;元素的一维数组存储&= #19968;个循环队列，则该= 490;环队列最大长度为＿= ;＿<o:p></o:p> 分析：在队列的顺ò= 07;存储结构中，队首指= 针front是指= 向它的前一个位置，= 5813;位置不存储队列元ಃ= 2;，这样便于判断队列&= #20026;空或为满的情况，= 240;此队列最大长度为= n-1 <= span style=3D'font-family:SimSun;mso-ascii-font-family:Arial;mso-hansi-font-fami= ly: Arial'>注意：顺序存储队= 015;为空或为满的条件= <o:p> </o:p> <![if !supportLists]>第= ;五章 <!= [endif]>੨= 1;<o:p></o:p> 本章主要介绍树ࡴ= 4;二叉树的概念，存储&= #32467;构和运算，每一种$= 816;算的算法描述，二叉= ;排序树的定义以及查&#= 25214;、插入和删除的方Ė= 61;，哈夫曼树的定义，= 构造哈夫曼树的方法= 1644;进行哈夫曼编码的ਬ= 1;法，一般树的存储结&= #26500;和运算等内容。通$= 807;本章学习，要求同学= ;们： <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握树的定义，= 树的各种表示方法，= 6641;的常用术语的含义ࡴ= 4;树的一些基本性质，&= #20108;叉树的定义和性质A= 292;二叉树的顺序存储结= ;构和链接存储结构<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握二叉树的建= 立、遍历（前序、中= 4207;、后序、按层）、๛= 5;出、求深度、清除等&= #21508;种运算的方法和算= 861;描述，以及相应的时= ;间复杂度<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>了解线索二叉树= 的定义和存储结构，= 0197;及利用线索进行遍࡚= 2;的方法和算法描述<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>掌握二叉排序树= 的定义和它的抽象数= 5454;类型，对二叉排序੨= 1;进行查找、更新、插&= #20837;和删除元素的方法= 644;算法描述，以及相应= ;的时间复杂度<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握哈夫曼树的= 定义，构造哈夫曼树= 0340;方法，能够计算树௚= 0;带权路径长度，了解&= #36827;行哈夫曼编码的方= 861;<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>了解一般树的存= 储结构和运算<o:p></o:p> 应熟练掌握树，= 二叉树的各种性质，= 0108;叉树的各种运算（ດ= 5;点是各种遍历算法）<= /span> <o:p> = ;</o:p> 例题<o:p></o:p> 对二叉树&#= 30340;各种遍历方法请大ê= 78;自己复习<o:p></o:p> <o:p> </o:p> １．对于一棵具有</spa= n>n个结点的&#= 26641;，该树中所有结点į= 40;度数之和为＿＿．<= /p> 分析：根据树的= 性质１得知为n-1 <o:p> = ;</o:p> ２．૓= 4;二叉树第= iह= 8;上最大结点数，从１&= #21040;= iह= 8;的最大结点数<o:p></o:p> 分析：根据二叉树į= 40;性质２和性质３得知= ，应分别为２的（i-1）次= 方，２的i次方减１ <o:p> = ;</o:p> ３．ल= 5;于顺序存储的二叉树&= #65292;如某结点下标为= i,࠵= 7;其双亲结点下标为＿&= #65343;,ॣ= 8;孩子结点下标为＿＿<= /span>,ࡥ= 1;孩子结点下标为＿＿<= /span><o:p></o:p> 分析：根据顺序存Î= 48;二叉树的编号规则可= 知，应分别为［i/2］，= ２i，２i＋１ <o:p> = ;</o:p> ４．ஸ= 1;权值分别为5ᦁ= 2;10ᦁ= 2;3ᦁ= 2;9ᦁ= 2;12ᦁ= 2;15௚= 0;叶子结点生成一棵哈&= #22827;曼树，求此树的带= 435;路径长度ＷＰＬ<o:p></o:p> 分析：过程略，结ĉ= 24;为133 <o:p>&= nbsp;</o:p> ５．编写算法，求Ɔ= 34;序存储的完全二叉树= 的编号为ｉ的结点的= 1452;亲和所有孩子 请参考第五章习= 题５．５ <o:p>&= nbsp;</o:p> ６．假定一棵树的ñ= 91;义表表示为Ａ（Ｂ（= Ｃ，Ｄ（Ｅ，Ｆ，Ｇ= 5289;，Ｈ（Ｉ，Ｊ））ᦀ= 9;，则树中所含的结点&= #25968;为＿＿个，树的深= 230;为＿＿，树的度为＿= ;＿． 自己解答 7．<![if !vml]><img width=3D37 height=3D23 src=3D"jjjg.files/image001.gif" v:shapes=3D"_x0000_s1027"><![endif]>= <![if !vml]><img width=3D51 height=3D23 src=3D"jjjg.files/image002.gif" v:shapes=3D"_x0000_s1026"><![endif]>= <![if !vml]><sp= an style=3D'mso-ignore:vglayout;position:absolute;z-index:6;left:0px;margin-le= ft: 153px;margin-top:9px;width:23px;height:23px'><img width=3D23 height=3D23 src=3D"jjjg.files/image003.gif" v:shapes=3D"_x0000_s1031"><![endif]>= <![if !vml]><img width=3D30 height=3D23 src=3D"jjjg.files/image004.gif" v:shapes=3D"_x0000_s1029"><![endif]>= <![if !vml]><sp= an style=3D'mso-ignore:vglayout;position:absolute;z-index:3;left:0px;margin-le= ft: 265px;margin-top:9px;width:23px;height:23px'><img width=3D23 height=3D23 src=3D"jjjg.files/image003.gif" v:shapes=3D"_x0000_s1028"><![endif]>= <![if !vml]><img width=3D23 height=3D23 src=3D"jjjg.files/image005.gif" v:shapes=3D"_x0000_s1032"><![endif]>= <![if !vml]><img width=3D23 height=3D23 src=3D"jjjg.files/image003.gif" v:shapes=3D"_x0000_s1030"><![endif]>= 见P205，5.13 8. P189, 二叉排序树的插ࠣ= 7;算法 <![if !supportLists]>9. = <![endif]>P179, 求二= 叉树深度的递归算法</s= pan> <o:p> </o:p> <![if !supportLists]>第= ;六章 <!= [endif]>ࢳ= 0;<o:p></o:p> 本章主要介绍图௚= 0;概念，图的邻接矩阵&= #65292;邻接表和边集数组"= 920;示，图的深度优先搜= ;索和广度优先搜索遍&#= 21382;方法，求图的最小ī= 83;成树的普里姆算法和= 克鲁斯卡尔算法，最= 0701;路径的求法，有向ࢳ= 0;的拓扑排序，关键路&= #24452;的求法等内容。通$= 807;本章学习，要求同学= ;们： <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握图的基本概= 念，图的每一种存储= 2467;构的定义、空间复੓= 4;度和生成算法，从图&= #30340;每一种存储结构中= 597;找一个顶点的邻接点= ;或所有邻接点的时间&#= 22797;杂度<o:p></o:p> <![if !supportLists]>★ <![endif]>掌握图的深度优= 先，广度优先搜索遍= 1382;的方法及分别针对๹= 1;接矩阵和邻接表算法&= #65292;相应的时间复杂度= 644;空间复杂度<o:p></o:p> <![if !supportLists]>★ <![endif]>掌握图的生成树= 、树的权和最小生成= 6641;的概念，掌握求图௚= 0;最小生成树的普里姆算法和克= 鲁斯卡尔算法，能够= 0011;出一个图的最小生ৎ= 4;树或写出依次得到的&= #21508;条边，以及求出最= 567;生成树的权<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>了解= 最短路径的求法<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>掌握= 进行图的拓扑排序的= 6041;法，能够根据图的๹= 1;接表得到唯一一种拓&= #25169;序列<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>了解= 关键路径的求法<o:p></o:p> <o:p> </o:p> 例题<o:p></o:p> １．求５个顶&#= 28857;的完全无向图的边ă= 68;。<o:p></o:p> 分析：因为每条= 边的度数为２，所以= 0840;部顶点的度数和为๟= 3;数的２倍，而对于完&= #20840;无向图，则每个顶= 857;的度数为全部顶点数= ;减１，即结果为全部&#= 39030;点的度数和（４＊ʍ= 01;），再除以２。即ｎ= 个顶点的完全无向图= 0013;，边为n(n-1)/2条<= /p> <o:p> </o:p> ２．ल= 5;于一个具有nߑ= 0;顶点和e੖= 5;边的连通图，求其生&= #25104;树中的顶点数和边= 968;<o:p></o:p> 分析：按照生成树į= 40;定义及构造方法，其= 顶点是取原图中的全= 7096;顶点，因此顶点数਷= 9;n；构造方&#= 27861;是除第一个顶点是Õ= 33;独加入外，以后每加= 入一个顶点，必加入= 9968;条边且只能一条边ᦁ= 2;因此边数为n-1 <![if !supportLists]>3. = <![endif]>见P250, 6.6题 <o:p>&nbs= p;</o:p> <![if !supportLists]>4. = <![endif]>P218, 深度= 优先搜索遍历图的算= 7861; <o:p> </o:p> <![if !supportLists]>第= ;七章 <!= [endif]>੣= 7;找<o:p></o:p> 本章主要介绍数ৱ= 4;处理中的各种查找方&= #27861;，包括顺序查找、= 108;分查找、索引查找、= ;散列查找、B-树查找等&#= 12290;同时介绍建立索引ŝ= 20;，散列表和B- 树的= 方法。通过本章学习= 5292;要求同学们： <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握在顺序表上= 进行顺序查找的方法和算= 法，相应的时间复杂= 4230;和空间复杂度，相ॵ= 2;的平均查找长度<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握二分查找的条件，二= 分查找的方法和算法= 5292;相应的时间复杂度ࡴ= 4;空间复杂度，对应的&= #21028;定树和查找每个元 = 032;的查找路径，对应的= ;平均查找长度和查找&#= 26576;个元素的查找长度</spa= n><o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>了解= 索引表的概念，索引= 6597;找的方法和算法，࠳= 8;块查找的方法和算法&= #65292;索引（分块）查找= 340;平均查找长度和时间= ;复杂度<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>了解= 散列表的概念，采用= 8500;留余数法构造散列࠲= 9;数的方法，采用线性&= #25506;查法和链接法处理= 914;突的方法，能够根据= ;已知数据构造散列表&#= 21644;计算出平均查找长ò= 30;，了解在散列表上进= 行各种运算的算法<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>了解= 平衡树，B-树的概念&#= 65292;在B-树上查找&#= 30340;过程，向B-树中插入&#= 20803;素和从中删除元素į= 40;方法<o:p></o:p> <o:p> </o:p> 例题<o:p></o:p> <![if !supportLists]>1.&n= bsp; <![endif]>以二分查找方法从&= 271;度为２０的有序表中= ;查找一个元素时，求&#= 26368;长查找长度<o:p></o:p> 分析：根&#= 25454;二分查找的判定树Ö= 87;知，其最长长度为<= span lang=3DEN-US>h=3D[<![if !vml]><img width=3D55 height=3D27 src=3D"jjjg.files/image008.gif" v:shapes=3D"_x0000_i1025"><![endif]><= !--[if gte mso 9]><xml> <o:OLEObject Type=3D"Embed" ProgID=3D"Equation.3" ShapeID=3D"_x0000_i1025" DrawAspect=3D"Content" ObjectID=3D"_1306935240"> </o:OLEObject> </xml><![endif]-->]+1,因此= 为５ <o:p> </o:p> <![if !supportLists]>2. <![endif]>在线= 性表的散列存储中，= 2788;理冲突有_______和<= span lang=3DEN-US>_______两种= 方法。 <o:p> </o:p> <![if !supportLists]>第= ;八章 <!= [endif]>৵= 0;序<o:p></o:p> 本章主要介绍数ৱ= 4;处理中各种排序方法&= #65292;包括插入排序（直= 509;插入排序、希尔排序= ;）、选择排序（直接&#= 36873;择排序、堆排序）z= 89;交换排序（气泡排序= 、快速排序）和归并= 5490;序等方法。通过本౉= 6;学习，要求同学们：<= /span> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握每一种排序= 方法在最好、平均和= 6368;坏情况下的时间复੓= 4;度和空间复杂度<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握每一种排序= 方法的机理，能够写= 0986;对已知一组数据的ຓ= 9;用每一种排序方法的&= #20855;体排序过程，能够= 011;出建立初始堆所对应= ;的完全二叉树和快速&#= 25490;序过程所对应的二Ö= 49;排序树<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>了解每一种排序= 方法所对应的具体算= 7861;描述<o:p></o:p> <o:p> </o:p> 例题<o:p></o:p> １．॥= 0;知一维数组Ａ中数据&= #22914;下，写出在快速排= 207;过程中，每层划分后= ;数据的排列情况<o:p></o:p> 20,38,16,25,19,42,55,73,24,83<o:p></o:p></span= > 解答：<o:p></o:p> ①［19,16］20［25 38 42 55 73 24 83］<o:p></o= :p> ②16 19 20 24 25［42 55 73 38 83= ］<o:p></o:p> ③16 19 20 24 25 38 42［73 55 83= ］<o:p></o:p> ④16 19 20 24 25 38 42 55 73 83<o:p></o:p> <o:p> = ;</o:p> 2．已知数&#= 32452;Ａ中的数据如下，Ð= 89;出在二路归并排序过= 程中，每趟归并后数= 5454;的排列情况<o:p></o:p> 45,36,18,53,72,30,48,93,28,66<o:p></o:p></span= > 解答：<o:p></o:p> ①［36 45］［18 53= 5341;［30 72］［48 93= 5341;［28 66］<o:p></o:p></spa= n> ②［18 36 45 53］［30 48 72 = 93］［28 66］<o:p></o:p></spa= n> ③［18 30 36 45 48 53 72 93］［28 66］<o:p></o:p> ④［18 28 30 36 45 48 53 66 93］<o= :p></o:p> 3. 已知一组元素的排ò= 07;码为（36，= 25，48，12，65，20），用直接插入= 排序法每次向前面有= 4207;表插入一个元素后௚= 0;排列结果。（5分） 第1次：［２&#= 65301;　３６］　４８　ʌ= 97;２　６５　２０ 第2次：［２&#= 65301;　３６　４８］　ʌ= 97;２　６５　２０ 第3次：［１&#= 65298;　２５　３６　４ʍ= 04;］　６５　２０ 第4次：［１&#= 65298;　２５　３６　４ʍ= 04;　６５］　２０ <p class=3DMsoNormal style=3D'margin-top:0cm;margin-right:-1.35pt;margin-bo= ttom: 0cm;margin-left:18.8pt;margin-bottom:.0001pt;mso-para-margin-top:0cm; mso-para-margin-right:-1.35pt;mso-para-margin-bottom:0cm;mso-para-margin-le= ft: 1.79gd;mso-para-margin-bottom:.0001pt;text-indent:21.0pt;mso-char-indent-co= unt: 2.0'>第= 5次：［１２　２= ０　２５　３６　４= 5304;　６５］ 4. 在一个小根堆中ᦁ= 2;堆顶结点的值是所有&= #32467;点中的________，在= 一个大根堆中，堆顶= 2467;点的值是所有结点ߑ= 3;的________。<= /p> 另外要求能写出堆þ= 90;序、直接选择排序、= 直接插入排序、气泡= 5490;序的每次排列情况</span= > <o:p= > </o:p> <p class=3DMsoNormal style=3D'margin-top:0cm;margin-right:-1.35pt;margin-bo= ttom: 0cm;margin-left:18.8pt;margin-bottom:.0001pt;mso-para-margin-top:0cm; mso-para-margin-right:-1.35pt;mso-para-margin-bottom:0cm;mso-para-margin-le= ft: 1.79gd;mso-para-margin-bottom:.0001pt;text-indent:21.0pt;mso-char-indent-co= unt: 2.0'>有关阅读</= span>C++算法= 的例题: 1． Stac= k S; InitStack(S); &n= bsp; Push(S,3); &n= bsp; Push(S,4); &n= bsp; Push(S,5); &n= bsp; int x=3DPop(S)+2*Pop(S);</= span> &n= bsp; Push(S,x); &n= bsp; int i= ,a[4]=3D{5,8,12,15}; &n= bsp; for (i=3D0;i<4;i++) Pus= h(S,a[i]); &n= bsp; while(!StackEmpty(S)) cout<<Pop(S)<<’’; <o:p> </o:p> 结果为：</= span>_________________________________。<o:p></o:p> <o:p> </o:p> 2． List L;</= span> InitList(L); int a[]=3D{45,21,56,38,63,76} for(i</s= pan>=3D0;i<6;i++) Insert(L,a[i]); InsertRear(L,Delet= eFront(L)); for(i</s= pan>=3D1;i<=3D3;i++){ int x=3DGetElem(<sp= an class=3DSpellE>L,i); if(</spa= n>x%2=3D=3D0) Delete(L,x); }</spa= n> <o:p>&= nbsp;</o:p> 线性表<sp= an lang=3DEN-US>L中的内容&#= 20026;：________________________________。 <o:p> </o:p> 3. Queue Q; InitQueue</spa= n>(Q);</spa= n> &n= bsp; int a[4]=3D{5,8,12,15};</s= pan> &n= bsp; for(int I=3D0;I<4;I++) = QInsert(Q,a[I]);</= p> &n= bsp; QInsert(Q,Qdelete(Q)); &n= bsp; QInsert(Q,30); &n= bsp; QInsert(Q,Qdelete(Q)+10); &n= bsp; int i= ,a[4]=3D{5,8,12,15}; &n= bsp; while(!QueueEmpty(Q)) cout<<QDelete(Q)<= ;<’’; <o:p> </o:p> 结果为：</= span>_________________________________。 <o:p> </o:p> 4. List L; InitList(L); InsertRear(L,30); InsertFront(L,50); Int a[</s= pan>4]=3D{5,8,12,15}; for(i</s= pan>=3D1;i<=3D4;i++) InsertRear(<sp= an class=3DSpellE>L,a[I]); <o:p> </o:p> 线性表<sp= an lang=3DEN-US>L中的内容&#= 20026;：________________________________。 <o:p>&= nbsp;</o:p> 数据结构考题类型= <o:p></o:p> <![if !supportLists]>一．<![en= dif]>单选题(20</s= pan>分) <o:p>&= nbsp;</o:p> <![if !supportLists]>二．<![endif]>填空题(20</s= pan>分)<o:p><= /o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>三．<![endif]>໾= 2;答题(30分)<o:p></o:p></span= > <o:p> </o:p> <![if !supportLists]>四．<![endif]>౛= 9;法填空（10分）<o:p></o:p>= <o:p> </o:p> <![if !supportLists]>五．<![endif]>ༀ= 5;读算法（10分）<o:p></o:p>= <o:p>&= nbsp;</o:p> <![if !supportLists]>六．<![endif]>ವ= 4;程题(10分)<o:p></o:p></span= > </div> </body> </html> ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/image008.gif Content-Transfer-Encoding: base64 Content-Type: image/gif R0lGODlhNwAbAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAMABgAv ABEAgAAAAAAAAAJdRAKpy+3/DoK02nSu3irzX3mYxEgT6JFierLihkyxfBp0V2txZ48Li0O1fL0g 8aX7HWsrUwTJiwKNOcewwSQWm6aqsqTs4pBdaPSrvVS9BlDICndTyHG23ObE5i0FADs= ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/oledata.mso Content-Transfer-Encoding: base64 Content-Type: application/x-mso 0M8R4KGxGuEAAAAAAAAAAAAAAAAAAAAAPgADAP7/CQAGAAAAAAAAAAAAAAABAAAAAQAAAAAAAAAA EAAAAgAAAAEAAAD+////AAAAAAAAAAD///////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////9 /////v////7///8EAAAA/v////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////1IA bwBvAHQAIABFAG4AdAByAHkAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAWAAUA//////////8BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAHBRzKq68MkB AwAAAIACAAAAAAAAXwAxADMAMAA2ADkAMwA1ADIANAAwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAABgAAgH///////////////8AAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAVQIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAP///////////////wAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA//////// ////////AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAQAA AAIAAAADAAAABAAAAAUAAAAGAAAABwAAAAgAAAAJAAAA/v////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////8ADAAA eJztVb1v00AUfxenSHWJaCNgqBi8ILE4ipO4SRwJIdFEygBIsLI4jdMe8lfsS2mEkFBZ2OBfYIWF jwkkJIRYAKl0QCxdYGFmYCXhXXIubobKQSxV87POfu/ee/q9e3f3vPt56dvj58vfYQIXQYLBcB5O xOaIGCMsAqSEPhgOh9H0cIYjhd840mIPozHD8cF18PBhoEAdXPwG0J9sBYfiLMzt33neD1I7qdH8 27G5Efd9tPfuyeufH4iE8j0S9ZRrYIM1FWccMqRIfD1J405DxH8Z1++Aj3m04NbU/Fnk50vha0rK z/2pkCXB28TqdzCTf+HnvOkp+HmuaSEPxL5Fd39OyDMcD5Dxb/wAtsgZaFmB6nshZdRzDdvqsFpG nnfMYJ26KlcNTc+VdZ8RPC2SPD57k3d/GV9X6FrghV6HKa+efnyjFHN55evuzvtnP+AkWldvKPVu z+QksIB6pOSK8Kv6ohtPygk91aYhU2nb0MulfFUvVcq1DD/NwsD6vmVs9FsBbY+SjQKY5fi2ySyM DA21kterxUKpoGjVSkUrnANegE97FwTN4ssmfHnYHN8TQiQik+y2DdltD8c6SKcILJDUgwLAEsjZ +y73WymvVCtlTa/dzciXOKVil7Bmm5atYR53RolwTXV7Dq9rxwsckxlta406pq12erat3qZttrGf 9sibWVvMOK/dbDTy9QmL2VJD5vlGqZDL++ygUZAcunl/4+rQhR6Y2Pkpdh8X/wNXhbaZqCsrWL34 eUrSf3jvWU3imBDT8v9vHGX+Pw8VnwoAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/image001.gif Content-Transfer-Encoding: base64 Content-Type: image/gif R0lGODlhJQAXAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAEAAQAj ABUAgAAAAAAAAAIwDI6pyxzWonSz1mdzw7oj6HVcqI2kBZ5XqkpmG70wNbtsrcj4t293D9D1fkPi 7lEAADs= ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/image002.gif Content-Transfer-Encoding: base64 Content-Type: image/gif R0lGODlhMwAXAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAEAAQAx ABUAgAAAAAAAAAI8hI+py33hopShzouNzTzuDiYVFJYaaYZjWn5s577YKnNxPd24Q+856qMAg40e sTg8LnTKB7MJeDaNUEUBADs= ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/image003.gif Content-Transfer-Encoding: base64 Content-Type: image/gif R0lGODlhFwAXAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAEAAQAV ABUAgAAAAAAAAAIkDI6pa+venjxxvmpZlnij7gGgN25ldlrptHKh9ibtFcv1d1MFADs= ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/image004.gif Content-Transfer-Encoding: base64 Content-Type: image/gif R0lGODlhHgAXAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAEAAQAc ABUAgAAAAAAAAAIrhI+pGutvGpxI0hnsfXq77iVZyJEfaAJoupJjKsKMXLWhfdPHq+Oef+HpCgA7 ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/image005.gif Content-Transfer-Encoding: base64 Content-Type: image/gif R0lGODlhFwAXAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAEAAQAV ABUAgAAAAAAAAAIlhI+Zoa3sIoCy0bqw1Y9nf1yeyJGaiaGVKrGR68AbaMgdPeFGAQA7 ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/image006.wmz Content-Transfer-Encoding: base64 Content-Type: application/x-ms-wmz H4sIAAAAAAACC7t+9tgsBghgUWBi4gQxjCMYGYAM5htANhODKFiSFYg5mcDKQKKMjGARRqb///+D RfQYJcAihkyMUNXcTDB9PEwKTAwsQkCWGhs/gxTDf5AmBgEg/wCQtQyIDzAzMBwDauSGquFh8E0s yQipLEhlYAgAu+A3U8M/iDMnMIJsYGFiEAjJzE0tVvBLLVcIys9NzGNg2AxyiS5QmgNIG3E1MHIy g9TmQU1Q+A8zgYGACYxgP32Am3SG0QbsLyMMtzAQdAvEJHCIgt1kwgD0LENOfjoDF9S3XOAQARsF DpXfTAIM7GDeHlAYtjEyMSkFVxaXpOYytKG7jxmsDgASVf0pxgEAAA== ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/filelist.xml Content-Transfer-Encoding: quoted-printable Content-Type: text/xml; charset="utf-8" <xml xmlns:o=3D"urn:schemas-microsoft-com:office:office"> <o:MainFile HRef=3D"../jjjg.htm"/> <o:File HRef=3D"image001.gif"/> <o:File HRef=3D"image002.gif"/> <o:File HRef=3D"image003.gif"/> <o:File HRef=3D"image004.gif"/> <o:File HRef=3D"image003.gif"/> <o:File HRef=3D"image005.gif"/> <o:File HRef=3D"image003.gif"/> <o:File HRef=3D"image006.wmz"/> <o:File HRef=3D"image008.gif"/> <o:File HRef=3D"oledata.mso"/> <o:File HRef=3D"filelist.xml"/> </xml> ------=_NextPart

MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_NextPart_01C9F0FD.B8BD84F0" 此文档为“单个文件网页”，也称为“Web 档案”文件。如果您看到此消息，但是您的浏览器或编辑器不支持“Web 档案”文件。请下载支持“Web 档案”的浏览器，如 Microsoft Internet Explorer。 ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.htm Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset="us-ascii" 四川广播电视大学</ti= tle> <o:SmartTagType namespaceuri=3D"urn:schemas-microsoft-com:office:smarttags" name=3D"chsdate"/>  <style>  </style>  </head> <body bgcolor=3Dsilver lang=3DZH-CN style=3D'tab-interval:21.25pt;text-just= ify-trim: punctuation'> <div class=3DSection1 style=3D'layout-grid:14.3pt'> 四川广播电෇= 0;大学<o:p></o:p> <p class=3DMsoNormal align=3Dcenter style=3D'margin-top:0cm;margin-right:-8= 9.85pt; margin-bottom:0cm;margin-left:21.0pt;margin-bottom:.0001pt;text-align:cente= r; mso-line-height-alt:17.0pt;mso-outline-level:1'>《数据结构Ӎ= 9;<o:p= ></o:p> <p class=3DMsoNormal align=3Dcenter style=3D'margin-top:0cm;margin-right:-8= 9.85pt; margin-bottom:0cm;margin-left:21.0pt;margin-bottom:.0001pt;text-align:cente= r; mso-line-height-alt:17.0pt;mso-outline-level:1'>期末总复习ࡡ= 0;考题类型</= span><o:p= ></o:p> <o:p> </o:p> <![if !supportLists]>第= ;一章 = <![endif]>ಱ= 0;论<o:p></o:p> = <s= pan style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman"'>数据结构研究的= 是数据的表示和数据= 0043;间的关系，逻辑上෸= 2;，数据结构有集合、&= #32447;性，树和图四种。= 412;章主要介绍数据结构= ;课程中一些常用术语&#= 30340;含义，常用数据结ĉ= 00;的表示，面向对象的= 概念（抽象数据类型= 1450;数据抽象和信息隐൒= 9;原则），C++语言= 中一些常用系统头文= 0214;的作用及各种数据౲= 7;型的使用（简单类型&= #65292;数组，字符串，记= 405;，文件），函数参数= ;的传递方式及函数和&#= 36816;算符重载的使用，ļ= 39;法的时间复杂度和空= 间复杂度评价方法等= 0869;容。通过本章学习ᦁ= 2;要求同学们： <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握集合、线性= 结构、树和图的二元= 2452;及图形表示<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>了解抽象数据类= 型的定义和应用<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>复习C++语= 5328;中的有关知识，重୅= 7;是指针概念，数据类&= #22411;（重点是简单类= 型、数组、记录，了= 5299;字符串、文件），࠲= 9;数参数的传递方式，&= #20102;解函数重载和运算= 526;重载的使用<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握评价算法的= 一般规则，算法时间= 2797;杂度的定义和数量ಪ= 3;表示，了解最好、平&= #22343;、最差的含义，了#= 299;空间复杂度的定义及= ;表示<o:p></o:p> <o:p> </o:p> 例题<o:p></o:p> <o:p> = ;</o:p> 1<s= pan style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman"'>．设a是一个一维数组= 1517;，则= a+i਷= 9;下标为= i௚= 0;元素的＿＿，＊(a+i) 是下标为= i௚= 0;元素的＿＿<o:p></o:p> 分析：弄懂C++中地= 址与指针的概念，单= 9420;一个数组名的含义ᦁ= 2;地址与一个整数相加&= #30340;含义 <o:p> = ;</o:p> 2<s= pan style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman"'>．求时间复杂度：= 如以下的求n!௚= 0;递归函数<o:p></o:p> long f(i= nt n) { if (n=3D=3D0) re= turn 1; else</sp= an> re= turn n*f(n-1); }</= p> 分析：由于每执行Ç= 68;次递归调用就是执行= 一条条件语句，执行= 5972;个算法需要进行n+1次调= 用，所以其时间复杂= 4230;为Ｏ(n) <o:p>&= nbsp;</o:p> 3</spa= n>．下面程序段的= 时间复杂度为＿＿．</s= pan> for <= /span>（i= nt i=3D0; i</sp= an><m; i++）<= /p> for (int j=3D0; j<n; j++) a[i][j]=3Di*j; 结果：n(n+1)/2 <o:p>&= nbsp;</o:p> <![if !supportLists]>第= ;二章 = <![endif]>ಬ= 7;性表<o:p></o:p> <o:p>&= nbsp;</o:p> 本章主要介绍线= 性表的定义和它的抽= 5937;数据类型，线性表௚= 0;顺序存储结构及每种&= #32447;性表操作在顺序结= 500;上的具体实现，链接= ;存储的概念，线性表&#= 30340;链接存储结构及每ķ= 81;线性表操作在链接存= 储结构上的具体实现= 1561;内容。通过本章学ߖ= 4;，要求同学们： <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握线性表的顺= 序存储结构（类型定= 0041;为List,它含有两个域&#= 65306;一个为数组list域，用于存储= 2447;性表的所有元素，ࡣ= 8;一个为变量size域，用于存储= 2447;性表的长度，即元ಃ= 2;的个数）和抽象数据&= #31867;型中定义的每一种= 805;作的含义，在顺序存= ;储方式下每一种操作&#= 30340;算法描述和相应的ą= 02;间复杂度<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握链接存储的= 概念（包括线性表的= 1333;、双向、循环、带༆= 8;加表头结点的链接存&= #20648;结构），单链表的= 420;立结点（类型定义为= ;LNode,</= span>它包含两个域data和next，Ñ= 98;别用于存储一个元素= 和一个指向后继结点= 0340;指针）链接存储结ਗ਼= 0;，在此方式下每一种&= #25805;作的算法描述和相= 212;的时间复杂度<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>了解单链表的数= 组结点（类型定义为<sp= an class=3DSpellE>ALNode,<= /span>它包含两个域data和next，Ñ= 98;别用于存储一个元素= 和一个后继结点的下= 6631;）链接存储结构，ࢷ= 2;此方式下每一种操作&= #30340;算法描述和相应的= 102;间复杂度<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>了解顺序存储和= 单链表的独立结点存= 0648;结构下的其它一些ਔ= 5;作的算法描述<o:p></o:p> <o:p> </o:p> 例题<o:p></o:p> 在熟练掌握线性表į= 40;各种操作的基础上，= 应注意针对不同情况= 9979;的灵活应用。 1．在线性表的顺序é= 84;储中，若一个元素的= 下标为i，则它的前驱元素į= 40;下标为＿＿，后继元= 素的下标为＿＿。 2. HL</spa= n>为表头指针的带= 表头附加结点的单链= 4920;和循环单链表中，໦= 2;表为空的条件分别为<= /span>______________和<= span lang=3DEN-US>_______________。<= /p> 3. 在循= 环双向链表中表头结= 8857;的左指针域指向＿ᦆ= 3;＿结点，表尾结点的&= #21491;指针域指向＿＿＿ = 467;点。 4. 在线性表单链接存Î= 48;中，若一个元素所在= 结点的地址为p，则其后&#= 32487;结点的地址为＿＿ʌ= 92;若假定p为一个数&#= 32452;a中的下标&#= 65292;则其后继结点的下Ċ= 31;为＿＿。 5<s= pan style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman"'>．设L是具有List౲= 7;型的一个线性表，写&= #20986;把表尾元素删除并= 351;之插入到表头位置的= ;算法<o:p></o:p> 分析：首先要排除</spa= n>L是空表的&#= 24773;况，然后要保存表ì= 14;元素到一个变量中，= 再按照插入一个元素= 1040;表头的方法，从后ࡨ= 1;前依次后移每个元素&= #65292;最后将该变量赋给"= 920;头元素 void delete(list& L)</spa= n> { if L.s= ize=3D=3D0 { cerr<<”empty list!”<<endl; exit(</s= pan>1);} elemtype x=3DL.list[size-1]; for (<s= pan class=3DSpellE>int i=3DL.size-1; i>=3D0; i--) L.list[i+1]=3DL.list[i]; L.list[0]=3Dx; }</= p> 注意：此循环中循Ĩ= 15;次数是size, 移动= 元素的个数是size（而= 非size-1）<= /p> 补充：在一个长度È= 26;n 的顺序存&#= 20648;线性表中，向第i个元素（1<=3Di<=3Dn+1）之前插入一个= 新元素时，需要从后= 1521;前依次后移＿＿个ࠠ= 3;素． 　　　　</= span>A．= n-i </spa= n>　　 B．n-i+1　<= span lang=3DEN-US> C</= span>．n-i-1 　　 D．i</span= > <o:p> = ;</o:p> 6<s= pan style=3D'font-family:SimSun;mso-ascii-font-family:"Times New Roman";mso-han= si-font-family: "Times New Roman"'>．在一个单链表<= span lang=3DEN-US style=3D'mso-fareast-font-family:SimHei'>(ಮ= 7;点类型为= LNode) ᦄ= 0;Ｌ中，写出删除由指&= #38024;q৓= 2;指结点的后继结点的&= #31639;法<o:p></o:p> 分析：可以先定义Ç= 68;个指针变量p，使其指&#= 21521;q的后继结&#= 28857;，然后让q的指针域&#= 25351;向p的后继结&#= 28857;，最后释放p结点 void delete(LNode*& HL, LNode* q)= <o:p></o:p> { if q->next=3D=3DNULL{<o:p></o:p> cerr</s= pan><<”q has no next node!”<<endl;<o:p></o:p= > exit(</s= pan>1);}<o:p></o:p> LNode* p=3Dq->next;<o:p></o:p> q->next=3Dp->next;<o:p></o:p>= delete p= ; <o:p></o:p> return ;= <o:p></o:p> }<o:p></o:p>= 思考：①如果是要在q结点后插&#= 20837;一个结点p 呢？②= ;在表头后插入一= 个结点p 呢？ 结果：①应执行 p->next=3Dq->next; q->next=3Dp; <sp= an style=3D'font-family:SimSun;mso-hansi-font-family:"Times New Roman"'>②= ;应执行 p->next=3DHL; HL=3Dp; <o:p> </o:p> P94,= 习题<st1:chsdate IsROCDate=3D"False" IsLunarDate=3D"False" Day=3D"30" Month=3D"12" Year=3D"1899" w:st=3D"on"><sp= an lang=3DEN-US>2.3.4</st1:chsdate>, 2.3.5, 2.4.7, 2.3.7 <o:p>&= nbsp;</o:p> <![if !supportLists]>第= ;三章 <!= [endif]>ళ= 2;疏矩阵和广义表<o:p></o:p> <o:p>&= nbsp;</o:p> 本章主要介绍稀ு= 5;矩阵的概念和存储结&= #26500;以及相应运算的算= 861;，广义表的概念和存= ;储结构以及相应运算&#= 30340;算法。通过本章学È= 64;，要求同学们： <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握稀疏矩阵的= 定义，三元组线性表= 4920;示，顺序存储结构ࡴ= 4;每一种链接存储结构<= span lang=3DEN-US><o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>了解对稀疏矩阵= 进行的每一种运算的= 6041;法和时间复杂度，ߚ= 2;解相应的算法描述<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握广义表的定= 义，它的链接存储结= 6500;，以及求广义表长ॷ= 0;，深度的方法和递归&= #31639;法<o:p></o:p> <o:p> </o:p> 例题<o:p></o:p> １．在稀疏矩&#= 38453;的十字链接存储中ʌ= 92;每个行单链表中的结= 点都具有相同的＿＿= 5292;每个列单链表中的ಮ= 7;点都具有相同的＿＿<= /span> 分析：存储稀疏= 矩阵的元素是三元组= 4418;式，即非零元素的ඡ= 2;号，列号及元素值。&= #39034;序存储是将三元组= 803;素存储在一个一维数= ;组中；带行指针链接&#= 23384;储是将具有相同行Ö= 95;的三元组结点按列号= 从小到大顺序存储在= 1508;个行单链表中，共੍= 7;m（= m为稀疏矩阵行数= ）个行单链表；十字= 8142;接存储是将三元组ಮ= 7;点既存于行单链表中&= #65292;又存于列单链表中A= 307;因此行单链表中的结= ;点都具有相同行号，&#= 21015;单链表中的结点都Ð= 55;有相同列号 <o:p> </o:p> 2. 在一个稀疏矩阵中ʌ= 92;每个非零元素所对应= 的三元组包括该元素= 0340;_______、<= span lang=3DEN-US>_______和<= span lang=3DEN-US>________三项= 。 <o:p> </o:p> <![if !supportLists]>第= ;四章 <!= [endif]>੧= 2;和队列<o:p></o:p> <o:p>&= nbsp;</o:p> 本章主要介绍栈௚= 0;定义和它的抽象数据&= #31867;型，栈的存储结构= 644;进行操作的算法描述= ;，利用栈求表达式的&#= 20540;，栈在递归算法执Ŝ= 92;中的作用，队列的定= 义和它的抽象数据类= 2411;，队列的存储结构ࡴ= 4;进行操作的算法描述&= #31561;内容。通过本章学= 064;，要求同学们： <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握在栈的抽象= 数据类型中定义的每= 9968;种操作在顺序存储ࡴ= 4;链接存储上分别实现&= #30340;算法，以及相应的= 102;间复杂度<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握算术表达式= 的中缀表示和后缀表= 1034;及其相互转换的规࠵= 7;，进行后缀表达式求&= #20540;的方法，把中缀表$= 798;式转换为后缀表达式= ;的方法，了解栈在递&#= 24402;算法执行中作用<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握队列的定义= 及顺序存储结构和链= 5509;存储结构，队列的ે= 9;一种操作在顺序存储&= #21644;链接存储上分别实= 616;的算法，以及相应的= ;时间复杂度<o:p></o:p> <o:p> </o:p> 例题<o:p></o:p> 在熟练掌握栈，队Ò= 15;的各种操作的基础上= ，应注意针对不同情= 0917;下的灵活应用。 <o:p> = ;</o:p> １．当利用大小为ʍ= 26;的数组顺序存储一个= 栈时，假定用top=3D=3DN表示= 栈空，则向这个栈插= 0837;一个元素时，首先ॵ= 2;执行＿＿＿语句修改<= /span>top指针= ． 答案：top-- ２．෶= 5;算后缀算术表达式<s= pan lang=3DEN-US style=3D'mso-fareast-font-family:SimHei'>8 5= 6＋2ᦁ= 0;＋１０／＠的值<o:p></o:p> 分析：从左到右扫ÿ= 51;表达式，并按规则进= 行处理： 规则１当是操作数ą= 02;，则压入栈中 规则２当是运算符ą= 02;，则弹出栈中两个操= 作数并计算，结果再= 1387;入栈中 <table class=3DMsoNormalTable border=3D1 cellspacing=3D0 cellpadding=3D0 style=3D'margin-left:28.9pt;border-collapse:collapse;border:none;mso-borde= r-alt: solid windowtext 3.0pt;mso-padding-alt:0cm 5.4pt 0cm 5.4pt;mso-border-insi= deh: 3.0pt solid windowtext;mso-border-insidev:3.0pt solid windowtext'> <tr style=3D'mso-yfti-irow:0;mso-yfti-firstrow:yes;page-break-inside:avoid; height:15.9pt'> <td width=3D50 valign=3Dtop style=3D'width:37.3pt;border:solid windowtext= 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:15.9pt'> 6= </td> <td width=3D51 rowspan=3D3 valign=3Dtop style=3D'width:37.9pt;border:soli= d windowtext 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:15.9pt'> <o:p> </o:p><= /p> </td> <td width=3D56 valign=3Dtop style=3D'width:42.3pt;border:solid windowtext= 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:15.9pt'> <o:p> </o:p><= /p> </td> <td width=3D49 rowspan=3D3 valign=3Dtop style=3D'width:36.5pt;border:soli= d windowtext 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:15.9pt'> <o:p> </o:p><= /p> </td> <td width=3D55 valign=3Dtop style=3D'width:41.3pt;border:solid windowtext= 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:15.9pt'> 2 </td> <td width=3D45 rowspan=3D3 valign=3Dtop style=3D'width:33.9pt;border:soli= d windowtext 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:15.9pt'> <o:p> </o:p><= /p> </td> <td width=3D56 valign=3Dtop style=3D'width:42.3pt;border:solid windowtext= 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:15.9pt'> <o:p> </o:p><= /p> </td> </tr> <tr style=3D'mso-yfti-irow:1;page-break-inside:avoid;height:17.0pt'> <td width=3D50 valign=3Dtop style=3D'width:37.3pt;border:solid windowtext= 3.0pt; border-top:none;mso-border-top-alt:solid windowtext 3.0pt;padding:0cm 5.4= pt 0cm 5.4pt; height:17.0pt'> 5= </td> <td width=3D56 valign=3Dtop style=3D'width:42.3pt;border-top:none;border-= left:none; border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3.0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:17.0pt'> 11 </td> <td width=3D55 valign=3Dtop style=3D'width:41.3pt;border-top:none;border-= left:none; border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3.0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:17.0pt'> 11 </td> <td width=3D56 valign=3Dtop style=3D'width:42.3pt;border-top:none;border-= left:none; border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3.0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:17.0pt'> 22 </td> </tr> <tr style=3D'mso-yfti-irow:2;mso-yfti-lastrow:yes;page-break-inside:avoid; height:16.75pt'> <td width=3D50 valign=3Dtop style=3D'width:37.3pt;border:solid windowtext= 3.0pt; border-top:none;mso-border-top-alt:solid windowtext 3.0pt;padding:0cm 5.4= pt 0cm 5.4pt; height:16.75pt'> 8= </td> <td width=3D56 valign=3Dtop style=3D'width:42.3pt;border-top:none;border-= left:none; border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3.0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:16.75pt'> 8 </td> <td width=3D55 valign=3Dtop style=3D'width:41.3pt;border-top:none;border-= left:none; border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3.0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:16.75pt'> 8 </td> <td width=3D56 valign=3Dtop style=3D'width:42.3pt;border-top:none;border-= left:none; border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3.0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:16.75pt'> 8 </td> </tr> </table> <o:p> = ;</o:p> <table class=3DMsoNormalTable border=3D1 cellspacing=3D0 cellpadding=3D0 style=3D'margin-left:28.9pt;border-collapse:collapse;border:none;mso-borde= r-alt: solid windowtext 3.0pt;mso-padding-alt:0cm 5.4pt 0cm 5.4pt;mso-border-insi= deh: 3.0pt solid windowtext;mso-border-insidev:3.0pt solid windowtext'> <tr style=3D'mso-yfti-irow:0;mso-yfti-firstrow:yes;page-break-inside:avoid; height:24.0pt'> <td width=3D63 valign=3Dtop style=3D'width:47.0pt;border:solid windowtext= 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:24.0pt'> <o:p>&nb= sp;</o:p> </td> <td width=3D78 rowspan=3D3 valign=3Dtop style=3D'width:58.5pt;border:soli= d windowtext 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:24.0pt'> <o:p> </o:p><= /p> </td> <td width=3D54 valign=3Dtop style=3D'width:40.2pt;border:solid windowtext= 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:24.0pt'> <o:p> </o:p><= /p> </td> <td width=3D83 rowspan=3D3 valign=3Dtop style=3D'width:62.25pt;border:sol= id windowtext 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:24.0pt'> <o:p> </o:p><= /p> </td> <td width=3D49 valign=3Dtop style=3D'width:36.45pt;border:solid windowtex= t 3.0pt; border-left:none;mso-border-left-alt:solid windowtext 3.0pt;padding:0cm 5= .4pt 0cm 5.4pt; height:24.0pt'> <o:p> </o:p><= /p> </td> </tr> <tr style=3D'mso-yfti-irow:1;page-break-inside:avoid;height:16.75pt'> <td width=3D63 valign=3Dtop style=3D'width:47.0pt;border:solid windowtext= 3.0pt; border-top:none;mso-border-top-alt:solid windowtext 3.0pt;padding:0cm 5.4= pt 0cm 5.4pt; height:16.75pt'> <o:p>&nb= sp;</o:p> </td> <td width=3D54 valign=3Dtop style=3D'width:40.2pt;border-top:none;border-= left:none; border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3.0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:16.75pt'> 10 </td> <td width=3D49 valign=3Dtop style=3D'width:36.45pt;border-top:none;border= -left: none;border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3= .0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:16.75pt'> <o:p> </o:p><= /p> </td> </tr> <tr style=3D'mso-yfti-irow:2;mso-yfti-lastrow:yes;page-break-inside:avoid; height:16.65pt'> <td width=3D63 valign=3Dtop style=3D'width:47.0pt;border:solid windowtext= 3.0pt; border-top:none;mso-border-top-alt:solid windowtext 3.0pt;padding:0cm 5.4= pt 0cm 5.4pt; height:16.65pt'> 30</span= > </td> <td width=3D54 valign=3Dtop style=3D'width:40.2pt;border-top:none;border-= left:none; border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3.0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:16.65pt'> 30 </td> <td width=3D49 valign=3Dtop style=3D'width:36.45pt;border-top:none;border= -left: none;border-bottom:solid windowtext 3.0pt;border-right:solid windowtext 3= .0pt; mso-border-top-alt:solid windowtext 3.0pt;mso-border-left-alt:solid windo= wtext 3.0pt; padding:0cm 5.4pt 0cm 5.4pt;height:16.65pt'> 3 </td> </tr> </table> <![if !supportLists]>8 <![endif]>5 6ᦁ= 1;2ᦁ= 0;＋10ᦁ= 5;＠=3D3<o:p></o:p></span= > <o:p> </o:p> ３．ࠥ= 5;有nߑ= 0;元素的一维数组存储&= #19968;个循环队列，则该= 490;环队列最大长度为＿= ;＿<o:p></o:p> 分析：在队列的顺ò= 07;存储结构中，队首指= 针front是指= 向它的前一个位置，= 5813;位置不存储队列元ಃ= 2;，这样便于判断队列&= #20026;空或为满的情况，= 240;此队列最大长度为= n-1 <= span style=3D'font-family:SimSun;mso-ascii-font-family:Arial;mso-hansi-font-fami= ly: Arial'>注意：顺序存储队= 015;为空或为满的条件= <o:p> </o:p> <![if !supportLists]>第= ;五章 <!= [endif]>੨= 1;<o:p></o:p> 本章主要介绍树ࡴ= 4;二叉树的概念，存储&= #32467;构和运算，每一种$= 816;算的算法描述，二叉= ;排序树的定义以及查&#= 25214;、插入和删除的方Ė= 61;，哈夫曼树的定义，= 构造哈夫曼树的方法= 1644;进行哈夫曼编码的ਬ= 1;法，一般树的存储结&= #26500;和运算等内容。通$= 807;本章学习，要求同学= ;们： <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握树的定义，= 树的各种表示方法，= 6641;的常用术语的含义ࡴ= 4;树的一些基本性质，&= #20108;叉树的定义和性质A= 292;二叉树的顺序存储结= ;构和链接存储结构<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握二叉树的建= 立、遍历（前序、中= 4207;、后序、按层）、๛= 5;出、求深度、清除等&= #21508;种运算的方法和算= 861;描述，以及相应的时= ;间复杂度<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>了解线索二叉树= 的定义和存储结构，= 0197;及利用线索进行遍࡚= 2;的方法和算法描述<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>掌握二叉排序树= 的定义和它的抽象数= 5454;类型，对二叉排序੨= 1;进行查找、更新、插&= #20837;和删除元素的方法= 644;算法描述，以及相应= ;的时间复杂度<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握哈夫曼树的= 定义，构造哈夫曼树= 0340;方法，能够计算树௚= 0;带权路径长度，了解&= #36827;行哈夫曼编码的方= 861;<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>了解一般树的存= 储结构和运算<o:p></o:p> 应熟练掌握树，= 二叉树的各种性质，= 0108;叉树的各种运算（ດ= 5;点是各种遍历算法）<= /span> <o:p> = ;</o:p> 例题<o:p></o:p> 对二叉树&#= 30340;各种遍历方法请大ê= 78;自己复习<o:p></o:p> <o:p> </o:p> １．对于一棵具有</spa= n>n个结点的&#= 26641;，该树中所有结点į= 40;度数之和为＿＿．<= /p> 分析：根据树的= 性质１得知为n-1 <o:p> = ;</o:p> ２．૓= 4;二叉树第= iह= 8;上最大结点数，从１&= #21040;= iह= 8;的最大结点数<o:p></o:p> 分析：根据二叉树į= 40;性质２和性质３得知= ，应分别为２的（i-1）次= 方，２的i次方减１ <o:p> = ;</o:p> ３．ल= 5;于顺序存储的二叉树&= #65292;如某结点下标为= i,࠵= 7;其双亲结点下标为＿&= #65343;,ॣ= 8;孩子结点下标为＿＿<= /span>,ࡥ= 1;孩子结点下标为＿＿<= /span><o:p></o:p> 分析：根据顺序存Î= 48;二叉树的编号规则可= 知，应分别为［i/2］，= ２i，２i＋１ <o:p> = ;</o:p> ４．ஸ= 1;权值分别为5ᦁ= 2;10ᦁ= 2;3ᦁ= 2;9ᦁ= 2;12ᦁ= 2;15௚= 0;叶子结点生成一棵哈&= #22827;曼树，求此树的带= 435;路径长度ＷＰＬ<o:p></o:p> 分析：过程略，结ĉ= 24;为133 <o:p>&= nbsp;</o:p> ５．编写算法，求Ɔ= 34;序存储的完全二叉树= 的编号为ｉ的结点的= 1452;亲和所有孩子 请参考第五章习= 题５．５ <o:p>&= nbsp;</o:p> ６．假定一棵树的ñ= 91;义表表示为Ａ（Ｂ（= Ｃ，Ｄ（Ｅ，Ｆ，Ｇ= 5289;，Ｈ（Ｉ，Ｊ））ᦀ= 9;，则树中所含的结点&= #25968;为＿＿个，树的深= 230;为＿＿，树的度为＿= ;＿． 自己解答 7．<![if !vml]><img width=3D37 height=3D23 src=3D"jjjg.files/image001.gif" v:shapes=3D"_x0000_s1027"><![endif]>= <![if !vml]><img width=3D51 height=3D23 src=3D"jjjg.files/image002.gif" v:shapes=3D"_x0000_s1026"><![endif]>= <![if !vml]><sp= an style=3D'mso-ignore:vglayout;position:absolute;z-index:6;left:0px;margin-le= ft: 153px;margin-top:9px;width:23px;height:23px'><img width=3D23 height=3D23 src=3D"jjjg.files/image003.gif" v:shapes=3D"_x0000_s1031"><![endif]>= <![if !vml]><img width=3D30 height=3D23 src=3D"jjjg.files/image004.gif" v:shapes=3D"_x0000_s1029"><![endif]>= <![if !vml]><sp= an style=3D'mso-ignore:vglayout;position:absolute;z-index:3;left:0px;margin-le= ft: 265px;margin-top:9px;width:23px;height:23px'><img width=3D23 height=3D23 src=3D"jjjg.files/image003.gif" v:shapes=3D"_x0000_s1028"><![endif]>= <![if !vml]><img width=3D23 height=3D23 src=3D"jjjg.files/image005.gif" v:shapes=3D"_x0000_s1032"><![endif]>= <![if !vml]><img width=3D23 height=3D23 src=3D"jjjg.files/image003.gif" v:shapes=3D"_x0000_s1030"><![endif]>= 见P205，5.13 8. P189, 二叉排序树的插ࠣ= 7;算法 <![if !supportLists]>9. = <![endif]>P179, 求二= 叉树深度的递归算法</s= pan> <o:p> </o:p> <![if !supportLists]>第= ;六章 <!= [endif]>ࢳ= 0;<o:p></o:p> 本章主要介绍图௚= 0;概念，图的邻接矩阵&= #65292;邻接表和边集数组"= 920;示，图的深度优先搜= ;索和广度优先搜索遍&#= 21382;方法，求图的最小ī= 83;成树的普里姆算法和= 克鲁斯卡尔算法，最= 0701;路径的求法，有向ࢳ= 0;的拓扑排序，关键路&= #24452;的求法等内容。通$= 807;本章学习，要求同学= ;们： <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握图的基本概= 念，图的每一种存储= 2467;构的定义、空间复੓= 4;度和生成算法，从图&= #30340;每一种存储结构中= 597;找一个顶点的邻接点= ;或所有邻接点的时间&#= 22797;杂度<o:p></o:p> <![if !supportLists]>★ <![endif]>掌握图的深度优= 先，广度优先搜索遍= 1382;的方法及分别针对๹= 1;接矩阵和邻接表算法&= #65292;相应的时间复杂度= 644;空间复杂度<o:p></o:p> <![if !supportLists]>★ <![endif]>掌握图的生成树= 、树的权和最小生成= 6641;的概念，掌握求图௚= 0;最小生成树的普里姆算法和克= 鲁斯卡尔算法，能够= 0011;出一个图的最小生ৎ= 4;树或写出依次得到的&= #21508;条边，以及求出最= 567;生成树的权<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>了解= 最短路径的求法<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>掌握= 进行图的拓扑排序的= 6041;法，能够根据图的๹= 1;接表得到唯一一种拓&= #25169;序列<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>了解= 关键路径的求法<o:p></o:p> <o:p> </o:p> 例题<o:p></o:p> １．求５个顶&#= 28857;的完全无向图的边ă= 68;。<o:p></o:p> 分析：因为每条= 边的度数为２，所以= 0840;部顶点的度数和为๟= 3;数的２倍，而对于完&= #20840;无向图，则每个顶= 857;的度数为全部顶点数= ;减１，即结果为全部&#= 39030;点的度数和（４＊ʍ= 01;），再除以２。即ｎ= 个顶点的完全无向图= 0013;，边为n(n-1)/2条<= /p> <o:p> </o:p> ２．ल= 5;于一个具有nߑ= 0;顶点和e੖= 5;边的连通图，求其生&= #25104;树中的顶点数和边= 968;<o:p></o:p> 分析：按照生成树į= 40;定义及构造方法，其= 顶点是取原图中的全= 7096;顶点，因此顶点数਷= 9;n；构造方&#= 27861;是除第一个顶点是Õ= 33;独加入外，以后每加= 入一个顶点，必加入= 9968;条边且只能一条边ᦁ= 2;因此边数为n-1 <![if !supportLists]>3. = <![endif]>见P250, 6.6题 <o:p>&nbs= p;</o:p> <![if !supportLists]>4. = <![endif]>P218, 深度= 优先搜索遍历图的算= 7861; <o:p> </o:p> <![if !supportLists]>第= ;七章 <!= [endif]>੣= 7;找<o:p></o:p> 本章主要介绍数ৱ= 4;处理中的各种查找方&= #27861;，包括顺序查找、= 108;分查找、索引查找、= ;散列查找、B-树查找等&#= 12290;同时介绍建立索引ŝ= 20;，散列表和B- 树的= 方法。通过本章学习= 5292;要求同学们： <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握在顺序表上= 进行顺序查找的方法和算= 法，相应的时间复杂= 4230;和空间复杂度，相ॵ= 2;的平均查找长度<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握二分查找的条件，二= 分查找的方法和算法= 5292;相应的时间复杂度ࡴ= 4;空间复杂度，对应的&= #21028;定树和查找每个元 = 032;的查找路径，对应的= ;平均查找长度和查找&#= 26576;个元素的查找长度</spa= n><o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>了解= 索引表的概念，索引= 6597;找的方法和算法，࠳= 8;块查找的方法和算法&= #65292;索引（分块）查找= 340;平均查找长度和时间= ;复杂度<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>了解= 散列表的概念，采用= 8500;留余数法构造散列࠲= 9;数的方法，采用线性&= #25506;查法和链接法处理= 914;突的方法，能够根据= ;已知数据构造散列表&#= 21644;计算出平均查找长ò= 30;，了解在散列表上进= 行各种运算的算法<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>了解= 平衡树，B-树的概念&#= 65292;在B-树上查找&#= 30340;过程，向B-树中插入&#= 20803;素和从中删除元素į= 40;方法<o:p></o:p> <o:p> </o:p> 例题<o:p></o:p> <![if !supportLists]>1.&n= bsp; <![endif]>以二分查找方法从&= 271;度为２０的有序表中= ;查找一个元素时，求&#= 26368;长查找长度<o:p></o:p> 分析：根&#= 25454;二分查找的判定树Ö= 87;知，其最长长度为<= span lang=3DEN-US>h=3D[<![if !vml]><img width=3D55 height=3D27 src=3D"jjjg.files/image008.gif" v:shapes=3D"_x0000_i1025"><![endif]><= !--[if gte mso 9]><xml> <o:OLEObject Type=3D"Embed" ProgID=3D"Equation.3" ShapeID=3D"_x0000_i1025" DrawAspect=3D"Content" ObjectID=3D"_1306935240"> </o:OLEObject> </xml><![endif]-->]+1,因此= 为５ <o:p> </o:p> <![if !supportLists]>2. <![endif]>在线= 性表的散列存储中，= 2788;理冲突有_______和<= span lang=3DEN-US>_______两种= 方法。 <o:p> </o:p> <![if !supportLists]>第= ;八章 <!= [endif]>৵= 0;序<o:p></o:p> 本章主要介绍数ৱ= 4;处理中各种排序方法&= #65292;包括插入排序（直= 509;插入排序、希尔排序= ;）、选择排序（直接&#= 36873;择排序、堆排序）z= 89;交换排序（气泡排序= 、快速排序）和归并= 5490;序等方法。通过本౉= 6;学习，要求同学们：<= /span> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握每一种排序= 方法在最好、平均和= 6368;坏情况下的时间复੓= 4;度和空间复杂度<o:p></o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>★ <![endif]>掌握每一种排序= 方法的机理，能够写= 0986;对已知一组数据的ຓ= 9;用每一种排序方法的&= #20855;体排序过程，能够= 011;出建立初始堆所对应= ;的完全二叉树和快速&#= 25490;序过程所对应的二Ö= 49;排序树<o:p></o:p> <o:p> </o:p> <![if !supportLists]>★ <![endif]>了解每一种排序= 方法所对应的具体算= 7861;描述<o:p></o:p> <o:p> </o:p> 例题<o:p></o:p> １．॥= 0;知一维数组Ａ中数据&= #22914;下，写出在快速排= 207;过程中，每层划分后= ;数据的排列情况<o:p></o:p> 20,38,16,25,19,42,55,73,24,83<o:p></o:p></span= > 解答：<o:p></o:p> ①［19,16］20［25 38 42 55 73 24 83］<o:p></o= :p> ②16 19 20 24 25［42 55 73 38 83= ］<o:p></o:p> ③16 19 20 24 25 38 42［73 55 83= ］<o:p></o:p> ④16 19 20 24 25 38 42 55 73 83<o:p></o:p> <o:p> = ;</o:p> 2．已知数&#= 32452;Ａ中的数据如下，Ð= 89;出在二路归并排序过= 程中，每趟归并后数= 5454;的排列情况<o:p></o:p> 45,36,18,53,72,30,48,93,28,66<o:p></o:p></span= > 解答：<o:p></o:p> ①［36 45］［18 53= 5341;［30 72］［48 93= 5341;［28 66］<o:p></o:p></spa= n> ②［18 36 45 53］［30 48 72 = 93］［28 66］<o:p></o:p></spa= n> ③［18 30 36 45 48 53 72 93］［28 66］<o:p></o:p> ④［18 28 30 36 45 48 53 66 93］<o= :p></o:p> 3. 已知一组元素的排ò= 07;码为（36，= 25，48，12，65，20），用直接插入= 排序法每次向前面有= 4207;表插入一个元素后௚= 0;排列结果。（5分） 第1次：［２&#= 65301;　３６］　４８　ʌ= 97;２　６５　２０ 第2次：［２&#= 65301;　３６　４８］　ʌ= 97;２　６５　２０ 第3次：［１&#= 65298;　２５　３６　４ʍ= 04;］　６５　２０ 第4次：［１&#= 65298;　２５　３６　４ʍ= 04;　６５］　２０ <p class=3DMsoNormal style=3D'margin-top:0cm;margin-right:-1.35pt;margin-bo= ttom: 0cm;margin-left:18.8pt;margin-bottom:.0001pt;mso-para-margin-top:0cm; mso-para-margin-right:-1.35pt;mso-para-margin-bottom:0cm;mso-para-margin-le= ft: 1.79gd;mso-para-margin-bottom:.0001pt;text-indent:21.0pt;mso-char-indent-co= unt: 2.0'>第= 5次：［１２　２= ０　２５　３６　４= 5304;　６５］ 4. 在一个小根堆中ᦁ= 2;堆顶结点的值是所有&= #32467;点中的________，在= 一个大根堆中，堆顶= 2467;点的值是所有结点ߑ= 3;的________。<= /p> 另外要求能写出堆þ= 90;序、直接选择排序、= 直接插入排序、气泡= 5490;序的每次排列情况</span= > <o:p= > </o:p> <p class=3DMsoNormal style=3D'margin-top:0cm;margin-right:-1.35pt;margin-bo= ttom: 0cm;margin-left:18.8pt;margin-bottom:.0001pt;mso-para-margin-top:0cm; mso-para-margin-right:-1.35pt;mso-para-margin-bottom:0cm;mso-para-margin-le= ft: 1.79gd;mso-para-margin-bottom:.0001pt;text-indent:21.0pt;mso-char-indent-co= unt: 2.0'>有关阅读</= span>C++算法= 的例题: 1． Stac= k S; InitStack(S); &n= bsp; Push(S,3); &n= bsp; Push(S,4); &n= bsp; Push(S,5); &n= bsp; int x=3DPop(S)+2*Pop(S);</= span> &n= bsp; Push(S,x); &n= bsp; int i= ,a[4]=3D{5,8,12,15}; &n= bsp; for (i=3D0;i<4;i++) Pus= h(S,a[i]); &n= bsp; while(!StackEmpty(S)) cout<<Pop(S)<<’’; <o:p> </o:p> 结果为：</= span>_________________________________。<o:p></o:p> <o:p> </o:p> 2． List L;</= span> InitList(L); int a[]=3D{45,21,56,38,63,76} for(i</s= pan>=3D0;i<6;i++) Insert(L,a[i]); InsertRear(L,Delet= eFront(L)); for(i</s= pan>=3D1;i<=3D3;i++){ int x=3DGetElem(<sp= an class=3DSpellE>L,i); if(</spa= n>x%2=3D=3D0) Delete(L,x); }</spa= n> <o:p>&= nbsp;</o:p> 线性表<sp= an lang=3DEN-US>L中的内容&#= 20026;：________________________________。 <o:p> </o:p> 3. Queue Q; InitQueue</spa= n>(Q);</spa= n> &n= bsp; int a[4]=3D{5,8,12,15};</s= pan> &n= bsp; for(int I=3D0;I<4;I++) = QInsert(Q,a[I]);</= p> &n= bsp; QInsert(Q,Qdelete(Q)); &n= bsp; QInsert(Q,30); &n= bsp; QInsert(Q,Qdelete(Q)+10); &n= bsp; int i= ,a[4]=3D{5,8,12,15}; &n= bsp; while(!QueueEmpty(Q)) cout<<QDelete(Q)<= ;<’’; <o:p> </o:p> 结果为：</= span>_________________________________。 <o:p> </o:p> 4. List L; InitList(L); InsertRear(L,30); InsertFront(L,50); Int a[</s= pan>4]=3D{5,8,12,15}; for(i</s= pan>=3D1;i<=3D4;i++) InsertRear(<sp= an class=3DSpellE>L,a[I]); <o:p> </o:p> 线性表<sp= an lang=3DEN-US>L中的内容&#= 20026;：________________________________。 <o:p>&= nbsp;</o:p> 数据结构考题类型= <o:p></o:p> <![if !supportLists]>一．<![en= dif]>单选题(20</s= pan>分) <o:p>&= nbsp;</o:p> <![if !supportLists]>二．<![endif]>填空题(20</s= pan>分)<o:p><= /o:p> <o:p>&= nbsp;</o:p> <![if !supportLists]>三．<![endif]>໾= 2;答题(30分)<o:p></o:p></span= > <o:p> </o:p> <![if !supportLists]>四．<![endif]>౛= 9;法填空（10分）<o:p></o:p>= <o:p> </o:p> <![if !supportLists]>五．<![endif]>ༀ= 5;读算法（10分）<o:p></o:p>= <o:p>&= nbsp;</o:p> <![if !supportLists]>六．<![endif]>ವ= 4;程题(10分)<o:p></o:p></span= > </div> </body> </html> ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/image008.gif Content-Transfer-Encoding: base64 Content-Type: image/gif R0lGODlhNwAbAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAMABgAv ABEAgAAAAAAAAAJdRAKpy+3/DoK02nSu3irzX3mYxEgT6JFierLihkyxfBp0V2txZ48Li0O1fL0g 8aX7HWsrUwTJiwKNOcewwSQWm6aqsqTs4pBdaPSrvVS9BlDICndTyHG23ObE5i0FADs= ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/oledata.mso Content-Transfer-Encoding: base64 Content-Type: application/x-mso 0M8R4KGxGuEAAAAAAAAAAAAAAAAAAAAAPgADAP7/CQAGAAAAAAAAAAAAAAABAAAAAQAAAAAAAAAA EAAAAgAAAAEAAAD+////AAAAAAAAAAD///////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////9 /////v////7///8EAAAA/v////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////1IA bwBvAHQAIABFAG4AdAByAHkAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAWAAUA//////////8BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAHBRzKq68MkB AwAAAIACAAAAAAAAXwAxADMAMAA2ADkAMwA1ADIANAAwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAABgAAgH///////////////8AAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAVQIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAP///////////////wAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA//////// ////////AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAQAA AAIAAAADAAAABAAAAAUAAAAGAAAABwAAAAgAAAAJAAAA/v////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////8ADAAA eJztVb1v00AUfxenSHWJaCNgqBi8ILE4ipO4SRwJIdFEygBIsLI4jdMe8lfsS2mEkFBZ2OBfYIWF jwkkJIRYAKl0QCxdYGFmYCXhXXIubobKQSxV87POfu/ee/q9e3f3vPt56dvj58vfYQIXQYLBcB5O xOaIGCMsAqSEPhgOh9H0cIYjhd840mIPozHD8cF18PBhoEAdXPwG0J9sBYfiLMzt33neD1I7qdH8 27G5Efd9tPfuyeufH4iE8j0S9ZRrYIM1FWccMqRIfD1J405DxH8Z1++Aj3m04NbU/Fnk50vha0rK z/2pkCXB28TqdzCTf+HnvOkp+HmuaSEPxL5Fd39OyDMcD5Dxb/wAtsgZaFmB6nshZdRzDdvqsFpG nnfMYJ26KlcNTc+VdZ8RPC2SPD57k3d/GV9X6FrghV6HKa+efnyjFHN55evuzvtnP+AkWldvKPVu z+QksIB6pOSK8Kv6ohtPygk91aYhU2nb0MulfFUvVcq1DD/NwsD6vmVs9FsBbY+SjQKY5fi2ySyM DA21kterxUKpoGjVSkUrnANegE97FwTN4ssmfHnYHN8TQiQik+y2DdltD8c6SKcILJDUgwLAEsjZ +y73WymvVCtlTa/dzciXOKVil7Bmm5atYR53RolwTXV7Dq9rxwsckxlta406pq12erat3qZttrGf 9sibWVvMOK/dbDTy9QmL2VJD5vlGqZDL++ygUZAcunl/4+rQhR6Y2Pkpdh8X/wNXhbaZqCsrWL34 eUrSf3jvWU3imBDT8v9vHGX+Pw8VnwoAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/image001.gif Content-Transfer-Encoding: base64 Content-Type: image/gif R0lGODlhJQAXAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAEAAQAj ABUAgAAAAAAAAAIwDI6pyxzWonSz1mdzw7oj6HVcqI2kBZ5XqkpmG70wNbtsrcj4t293D9D1fkPi 7lEAADs= ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/image002.gif Content-Transfer-Encoding: base64 Content-Type: image/gif R0lGODlhMwAXAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAEAAQAx ABUAgAAAAAAAAAI8hI+py33hopShzouNzTzuDiYVFJYaaYZjWn5s577YKnNxPd24Q+856qMAg40e sTg8LnTKB7MJeDaNUEUBADs= ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/image003.gif Content-Transfer-Encoding: base64 Content-Type: image/gif R0lGODlhFwAXAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAEAAQAV ABUAgAAAAAAAAAIkDI6pa+venjxxvmpZlnij7gGgN25ldlrptHKh9ibtFcv1d1MFADs= ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/image004.gif Content-Transfer-Encoding: base64 Content-Type: image/gif R0lGODlhHgAXAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAEAAQAc ABUAgAAAAAAAAAIrhI+pGutvGpxI0hnsfXq77iVZyJEfaAJoupJjKsKMXLWhfdPHq+Oef+HpCgA7 ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/image005.gif Content-Transfer-Encoding: base64 Content-Type: image/gif R0lGODlhFwAXAHcAMSH+GlNvZnR3YXJlOiBNaWNyb3NvZnQgT2ZmaWNlACH5BAEAAAAALAEAAQAV ABUAgAAAAAAAAAIlhI+Zoa3sIoCy0bqw1Y9nf1yeyJGaiaGVKrGR68AbaMgdPeFGAQA7 ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/image006.wmz Content-Transfer-Encoding: base64 Content-Type: application/x-ms-wmz H4sIAAAAAAACC7t+9tgsBghgUWBi4gQxjCMYGYAM5htANhODKFiSFYg5mcDKQKKMjGARRqb///+D RfQYJcAihkyMUNXcTDB9PEwKTAwsQkCWGhs/gxTDf5AmBgEg/wCQtQyIDzAzMBwDauSGquFh8E0s yQipLEhlYAgAu+A3U8M/iDMnMIJsYGFiEAjJzE0tVvBLLVcIys9NzGNg2AxyiS5QmgNIG3E1MHIy g9TmQU1Q+A8zgYGACYxgP32Am3SG0QbsLyMMtzAQdAvEJHCIgt1kwgD0LENOfjoDF9S3XOAQARsF DpXfTAIM7GDeHlAYtjEyMSkFVxaXpOYytKG7jxmsDgASVf0pxgEAAA== ------=_NextPart_01C9F0FD.B8BD84F0 Content-Location: file:///C:/2686B5A7/jjjg.files/filelist.xml Content-Transfer-Encoding: quoted-printable Content-Type: text/xml; charset="utf-8" <xml xmlns:o=3D"urn:schemas-microsoft-com:office:office"> <o:MainFile HRef=3D"../jjjg.htm"/> <o:File HRef=3D"image001.gif"/> <o:File HRef=3D"image002.gif"/> <o:File HRef=3D"image003.gif"/> <o:File HRef=3D"image004.gif"/> <o:File HRef=3D"image003.gif"/> <o:File HRef=3D"image005.gif"/> <o:File HRef=3D"image003.gif"/> <o:File HRef=3D"image006.wmz"/> <o:File HRef=3D"image008.gif"/> <o:File HRef=3D"oledata.mso"/> <o:File HRef=3D"filelist.xml"/> </xml> ------=_NextPart_01C9F0FD.B8BD84F0--