數(shù)據(jù)結(jié)構(gòu)-基于Python語(yǔ)言（微課版）-補(bǔ)充內(nèi)容實(shí)驗(yàn)、習(xí)題和答案

1.5本章習(xí)題一.選擇題(1).數(shù)據(jù)的最小單位是（）。A、數(shù)據(jù)項(xiàng) B、數(shù)據(jù)元素C、數(shù)據(jù)類(lèi)型 D、數(shù)據(jù)變量(2).數(shù)據(jù)結(jié)構(gòu)有（）種基本邏輯結(jié)構(gòu)A、1 B、2C、3 D、4(3).下列四種基本的邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是（）。A、集合 B、線性結(jié)構(gòu)C、樹(shù)形結(jié)構(gòu) D、圖狀結(jié)構(gòu)(4).數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的，稱為（）。A、存儲(chǔ)結(jié)構(gòu)B、邏輯結(jié)構(gòu)C、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D、順序存儲(chǔ)結(jié)構(gòu)(5).算法能正確地實(shí)現(xiàn)預(yù)定功能的特性稱為（）。A、正確性 B、易讀性C、健壯性 D、高效率(6).下面關(guān)于算法的說(shuō)法錯(cuò)誤的是（）。A、算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B、為解決某問(wèn)題的算法同為該問(wèn)題編寫(xiě)的程序含義是相同的C、算法的可行性是指指令不能有二義性D、以上幾個(gè)都是錯(cuò)誤的(7).算法的時(shí)間復(fù)雜度是指（）。A、執(zhí)行算法程序所需要的時(shí)間B、算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)C、算法程序的長(zhǎng)度D、算法程序中的指令條數(shù)(8).下列時(shí)間復(fù)雜度中最好的是（）。A、O(1) B、O(n)C、O(log2n) D、O(n2)(9).執(zhí)行下面程序段時(shí)，執(zhí)行S語(yǔ)句的次數(shù)為（）。foriinrange(i,n+1):forjinrange(1,i+1)SA、n2 B、n2/2C、n(n+1) D、n(n+1)/2(10).下面程序段的時(shí)間復(fù)雜度為（）。foriinrange(0,m):forjinrange(0,n):a[i][j]=i*jA、O(m2) B、O(n2)C、O(m*n) D、O(m+n)二.填空題(1).線性結(jié)構(gòu)中元素之間存在關(guān)系；樹(shù)形結(jié)構(gòu)中元素之間存在關(guān)系；圖形結(jié)構(gòu)中元素之間存在關(guān)系。(2).數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類(lèi)，分別是和。(3).算法的五個(gè)重要特性是：、、、、。(4).下面程序段的時(shí)間復(fù)雜度是。whiles<n:i+=1s+=i(5).下面程序段的時(shí)間復(fù)雜度是。i=1whilei<=ni=i*3第1章習(xí)題答案一.選擇題12345678910ADACADBADC二.填空題1.一對(duì)一、一對(duì)多、多對(duì)多2.線性結(jié)構(gòu)、非線性結(jié)構(gòu)3.確定性、有限性、輸入、輸出、可行性4.O(5.O(2.9本章實(shí)驗(yàn)：線性表初探2.9.1實(shí)驗(yàn)?zāi)康呐c要求(1).了解線性表存儲(chǔ)結(jié)構(gòu)的應(yīng)用(2).復(fù)習(xí)結(jié)構(gòu)體類(lèi)型的定義(3).復(fù)習(xí)結(jié)構(gòu)體變量成員的訪問(wèn)方式、函數(shù)定義、線性表存儲(chǔ)(4).理解線性表的定義與存儲(chǔ)特點(diǎn)(5).掌握線性表的插入與刪除操作2.9.2實(shí)驗(yàn)準(zhǔn)備與環(huán)境安裝VC6.0或Visualstudio的PC機(jī)一臺(tái)2.9.3實(shí)驗(yàn)內(nèi)容采用線性表存儲(chǔ)結(jié)構(gòu)定義如下“學(xué)生選課表”，并實(shí)現(xiàn)表的以下基本操作：提示：一條學(xué)生的信息可以用結(jié)構(gòu)體存放。(1).采用線性表存儲(chǔ)結(jié)構(gòu)定義如下學(xué)生選課表；(2).實(shí)現(xiàn)Init函數(shù)，實(shí)現(xiàn)順序表的初始化；(3).實(shí)現(xiàn)Display函數(shù)，實(shí)現(xiàn)表中信息在控制臺(tái)的輸出，并完成數(shù)據(jù)的初始化，如下數(shù)據(jù)內(nèi)容；(4).實(shí)現(xiàn)InsertCourse函數(shù)，實(shí)現(xiàn)在表中任意位置插入學(xué)生選課信息；(5).實(shí)現(xiàn)SearchByNo函數(shù)，實(shí)現(xiàn)根據(jù)學(xué)號(hào)查詢選課情況；(6).實(shí)現(xiàn)DeleteByNo函數(shù)，實(shí)現(xiàn)根據(jù)學(xué)號(hào)刪除選課信息。2.10本章習(xí)題一.選擇題(1).以下關(guān)于線性表的說(shuō)法，不正確的是（）。A、線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類(lèi)型B、線性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的C、線性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前驅(qū)和直接后繼D、存在這樣的線性表，表中各結(jié)點(diǎn)都沒(méi)有直接前驅(qū)和直接后繼(2).在順序表中，只要知道（），就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。A、基地址B、結(jié)點(diǎn)大小C、向量大小D、基地址和結(jié)點(diǎn)大小(3).在一個(gè)長(zhǎng)度為n的順序表中向第i個(gè)(1≤i≤n)位置插入一個(gè)新元素時(shí)，需要從后向前依次后移（）個(gè)元素。A、n-i B、n-i+1C、n-i-1 D、i(4).線形表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）。A、必須是連續(xù)的B、部分地址必須是連續(xù)的C、一定是不連續(xù)的D、連續(xù)或不連續(xù)都可以(5).不帶頭結(jié)點(diǎn)的單鏈表first為空的判定條件是（）。A、first==NoneB、first.next==NoneC、first.next==firstD、first!=None(6).設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data,next)。已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前驅(qū)，若在q與p之間插入結(jié)點(diǎn)s，則應(yīng)執(zhí)行的操作是（）。A、s.next=p.nextp->link=s;B、q.next=ss.next=pC、p.next=s.nexts.next=pD、p.next=ss.next=q(7).在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是（）。A、O(1) B、O(n)C、O(n2) D、O(nlog2n)(8).利用雙向鏈表作線性表的存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是（）。A、便于單向進(jìn)行插入和刪除的操作B、便于雙向進(jìn)行插入和刪除的操作C、節(jié)省空間D、便于銷(xiāo)毀結(jié)構(gòu)釋放空間(9).帶表頭的雙向循環(huán)鏈表的空表滿足（）。A、head=NoneB、head.next==headC、head.prior==NoneD、head.next==None(10).某鏈表中最常用的操作是在最后一個(gè)元素之后a插入一個(gè)元素和刪除最后一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A、單鏈表B、雙鏈表C、單循環(huán)鏈表D、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表二.填空題(1).在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)決定的；在線性表的鏈?zhǔn)酱鎯?chǔ)中，元素之間的邏輯關(guān)系是通過(guò)決定的。(2).當(dāng)對(duì)一個(gè)線性表頻繁進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時(shí)，采用存儲(chǔ)結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則采用存儲(chǔ)結(jié)構(gòu)為宜。(3).根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為和；而根據(jù)指針的鏈接方式，鏈表又可分為和。(4).若設(shè)head指向帶表頭結(jié)點(diǎn)的單鏈表,則語(yǔ)句head.next=head.next.next的作用是。(5).在雙向鏈表中插入和刪除結(jié)點(diǎn)時(shí)，必須修改方向上的指針。三.簡(jiǎn)答題(1).線性表的兩種存儲(chǔ)結(jié)構(gòu)各有哪些優(yōu)缺點(diǎn)？(2).在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么？(3).描述以下三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)和表頭結(jié)點(diǎn)。四.編程題(1).帶頭結(jié)點(diǎn)的單鏈表，其長(zhǎng)度存放在頭結(jié)點(diǎn)的數(shù)據(jù)域中，設(shè)計(jì)一算法求倒數(shù)第k個(gè)結(jié)點(diǎn)的值，并且刪除該結(jié)點(diǎn)。要求：=1\*GB3①.用Python語(yǔ)言描述該單鏈表=2\*GB3②.寫(xiě)出解決該問(wèn)題的Python語(yǔ)言算法過(guò)程進(jìn)行合法性檢查：不合法，返回error；若合法：=1\*GB3①.遍歷鏈表查找倒數(shù)第k個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)；=2\*GB3②.將倒數(shù)第k個(gè)結(jié)點(diǎn)值保存；=3\*GB3③.將倒數(shù)第k個(gè)結(jié)點(diǎn)刪除。第2章習(xí)題答案一.選擇題12345678910CDBDABBBBD二.填空題1.物理存儲(chǔ)位置、鏈域的指針值2.順序、鏈?zhǔn)?.單鏈表、雙鏈表、非循環(huán)鏈表、循環(huán)鏈表4.刪除第一個(gè)結(jié)點(diǎn)5.前驅(qū)和后繼兩個(gè)三.簡(jiǎn)答題1.線性表具有兩種存儲(chǔ)結(jié)構(gòu)，即順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。線性表的順序存儲(chǔ)結(jié)構(gòu)可以直接存儲(chǔ)數(shù)據(jù)元素，方便、靈活、高效，但插入、刪除操作時(shí)將會(huì)引起元素的大量移動(dòng)，因而降低效率。而在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，內(nèi)存采用動(dòng)態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲(chǔ)方便，但結(jié)點(diǎn)的插入、刪除操作比較簡(jiǎn)單。2.設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點(diǎn)的指針，用它來(lái)表示單循環(huán)鏈表，可以使得查找鏈表的開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear.next.next和rear，查找時(shí)間都是O(1)。若用頭指針來(lái)表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。3.頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（即表頭結(jié)點(diǎn)）的指針；在表頭結(jié)點(diǎn)之前附設(shè)的結(jié)點(diǎn)稱為頭結(jié)點(diǎn)；表頭結(jié)點(diǎn)為鏈表時(shí)，存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。三.編程題略3.8討論課：如何選擇合適的線性表解決實(shí)際問(wèn)題？(1).討論主題：如何更好的使用線性表解決實(shí)際問(wèn)題？(2).討論說(shuō)明=1\*GB3①.順序表：順序表是在存儲(chǔ)器中分配一段連續(xù)的存儲(chǔ)空間，邏輯上相鄰的數(shù)據(jù)元素其物理存儲(chǔ)地址也是相鄰的。順序表一旦分配其大小就是固定的無(wú)法更改，表中存儲(chǔ)的元素的個(gè)數(shù)與表的大小未必相同，如分配4個(gè)單元大小的順序表，可能只存儲(chǔ)了3個(gè)元素。如果順序表存儲(chǔ)已滿就無(wú)法再往里存儲(chǔ)元素。在順序存儲(chǔ)中，只要確定了線性表在存儲(chǔ)空間里的起始位置，線性表中任意元素就都可隨機(jī)存取，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的結(jié)構(gòu)。=2\*GB3②.鏈表：在鏈?zhǔn)酱鎯?chǔ)中，結(jié)點(diǎn)之間的存儲(chǔ)單元地址可能是不連續(xù)的。鏈?zhǔn)酱鎯?chǔ)中每個(gè)結(jié)點(diǎn)都包含兩個(gè)部分：存儲(chǔ)元素本身的數(shù)據(jù)域和存儲(chǔ)結(jié)點(diǎn)地址的指針域。結(jié)點(diǎn)中的指針指向的是下一個(gè)結(jié)點(diǎn)，直到最后一個(gè)結(jié)點(diǎn)沒(méi)有后繼結(jié)點(diǎn)而指向空。在鏈表中，這些存儲(chǔ)單元可以是不連續(xù)的，因此它可以提高空間利用率，當(dāng)需要存儲(chǔ)元素時(shí)，哪兒有空閑的空間就在哪兒分配，只要將分配的空間地址保存到上一個(gè)結(jié)點(diǎn)就可以。=3\*GB3③.棧：棧遵循“后進(jìn)先出”的規(guī)則，它是一種受到限制的線性表。棧僅允許在一端進(jìn)行這些操作。棧中允許執(zhí)行插入和刪除操作的一端稱為棧頂，不允許執(zhí)行插入和刪除操作的一端稱為棧底。向一個(gè)棧中插入新元素又稱為入棧、壓棧。入棧之后該元素被放在棧頂元素的上面，成為新的棧頂元素。=4\*GB3④.隊(duì)列：隊(duì)列遵循“先進(jìn)先出”原則。它和棧一樣，也是一種受限制的線性表，只允許在一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作。其中允許刪除的一端稱為隊(duì)首，允許插入的一端稱為隊(duì)尾。向隊(duì)列中插入元素稱為入隊(duì)，從隊(duì)列中刪除元素稱為出隊(duì)。(3).分組形式每5個(gè)人為一個(gè)小組，每個(gè)小組設(shè)置組長(zhǎng)1名，組長(zhǎng)具體負(fù)責(zé)任務(wù)分配協(xié)調(diào)。(4).提交文檔在大量文獻(xiàn)調(diào)研的基礎(chǔ)上，撰寫(xiě)制作一份答辯PPT，闡述自己的觀點(diǎn)。文件命名：第X小組(5).課堂答辯每個(gè)小組派出一名代表進(jìn)行課堂演講，每個(gè)人演講10分鐘，演講內(nèi)容需要圍繞事先準(zhǔn)備好的PPT進(jìn)行。演講結(jié)束后，有5分鐘的自由提問(wèn)和回答時(shí)間。(6).考核方法本次討論課的最終成績(jī)由兩個(gè)部分構(gòu)成：PPT50%，演講50%。3.9本章實(shí)驗(yàn)：棧的定義與應(yīng)用3.9.1實(shí)驗(yàn)?zāi)康呐c要求(1).理解棧的定義與存儲(chǔ)特點(diǎn)(2).掌握順序棧的定義與應(yīng)用3.9.2實(shí)驗(yàn)準(zhǔn)備與環(huán)境安裝VC6.0或Visualstudio的PC機(jī)一臺(tái)3.9.3實(shí)驗(yàn)內(nèi)容(1).實(shí)現(xiàn)順序棧的定義與基本操作；(2).應(yīng)用順序棧實(shí)現(xiàn)回文（PalindromicSequence）判斷,具體如下：試寫(xiě)一個(gè)算法，判斷依次讀入的一個(gè)以@為結(jié)束符的字母序列，是否為形如“序列1&序列2”模式的字符序列。其中序列1和序列2中都不含字符“&”，且序列2是序列1的逆序列。例如，“a+b&b+a”是屬于該模式的字符序列，而“1+3&3-1”則不是。(3).【思考】若采用鏈棧實(shí)現(xiàn)回文，有何不同？3.10本章習(xí)題一.選擇題(1).有六個(gè)元素(6,5,4,3,2,1)的順序進(jìn)棧，問(wèn)下列哪一個(gè)不是合法的出棧序列？（）A、543612B、453126C、346521D、234156(2).在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂，當(dāng)做出棧處理時(shí)，top變化為（）。A、top不變B、top=0C、top-=1D、top+=1(3).鏈棧與順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)，即（）。A、插入操作方便B、通常不會(huì)出現(xiàn)棧滿的情況C、不會(huì)出現(xiàn)?？盏那闆rD、刪除操作更方便(4).一個(gè)隊(duì)列的入隊(duì)列順序是(1,2,3,4)，則隊(duì)列的輸出序列是（）。A、4321B、1234C、1432D、3241(5).循環(huán)隊(duì)列的隊(duì)滿條件為（）。A、(sq.rear+1)%maxsize==(sq.front+1)%maxsizeB、(sq.rear+1)%maxsize==sq.front+1C、sq.(rear+1)%maxsize==sq.frontD、sq.rear==sq.front(6).若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？（）A、1和5B、2和4C、4和2D、5和1(7).棧和隊(duì)列的共同特點(diǎn)是（）。A、都是先進(jìn)先出B、都是先進(jìn)后出C、只允許在端點(diǎn)處插入和刪除元素D、以上都不正確(8).棧和隊(duì)列都是（）。A、順序存儲(chǔ)的線性結(jié)構(gòu)B、鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)C、限制存取點(diǎn)的線性結(jié)構(gòu)D、限制存取點(diǎn)的非線性結(jié)構(gòu)(9).設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。A、線性標(biāo)的順序存儲(chǔ)結(jié)構(gòu)B、棧C、隊(duì)列D、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(10).一個(gè)遞歸算法必須包括（）。A、遞歸調(diào)用B、子程序調(diào)用C、表達(dá)式求值D、以上都是二、填空題(1).棧是的線性表，其運(yùn)算遵循的原則。(2).隊(duì)列是一種限定在表的一端插入，在另一端刪除的線性表，它的特點(diǎn)是。(3).當(dāng)兩個(gè)棧共享一存儲(chǔ)區(qū)時(shí)，棧利用一維數(shù)組stack(1,n)表示，兩棧頂指針為top[1]與top[2]，則當(dāng)棧1空時(shí)，top[1]為，棧2空時(shí),top[2]為，棧滿時(shí)為。(4).區(qū)分循環(huán)隊(duì)列的滿與空，只有兩種方法，它們是和。(5).設(shè)有一個(gè)順序棧S，元素s1,s2,s3,s4,s5,s6依次進(jìn)棧，如果6個(gè)元素的出棧順序?yàn)閟2,s3,s4,s6,s5,s1，則順序棧的容量至少應(yīng)為。三.簡(jiǎn)答題(1).什么是隊(duì)列的上溢現(xiàn)象？一般有幾種解決方法，試簡(jiǎn)述之。(2).假定有四個(gè)元素A,B,C,D依次進(jìn)棧，進(jìn)棧過(guò)程中允許出棧，試寫(xiě)出所有可能的出棧序列。(3).1,2,3,4的四輛車(chē)，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)（棧的大小為4），試寫(xiě)出這四輛車(chē)開(kāi)出站的所有可能的順序（每輛車(chē)入站后出站的時(shí)間未知）。四.編程題(1).判別讀入的字符序列是否為“回文”。例如：abcdedcba、abccba都是回文。=1\*GB3①.算法分析：由于回文的字符序列中分界線不明確，因此無(wú)法判定字符序列的“中間位置”，即只能按照回文的定義，從字符的兩頭出發(fā)進(jìn)行判別。然而，按照題目的要求，這個(gè)字符序列是從外部環(huán)境輸入的，為了在輸入結(jié)束時(shí)，同時(shí)能得到序列的“頭”和“尾”，因此算法中，除了需要使用到棧，還需使用一個(gè)隊(duì)列。=2\*GB3②.算法的基本思想：將依次讀入的字符分別插入棧和隊(duì)列，然后依次比較“棧頂”和“隊(duì)頭”的字符。第3章習(xí)題答案一.選擇題12345678910CCBBCBCCBB二.填空題1.操作受限/限定僅在表尾進(jìn)行插入和刪除操作、后進(jìn)先出2.先進(jìn)先出3.0、n+1、top[1]+1=top[2]4.犧牲一個(gè)存儲(chǔ)單元、設(shè)標(biāo)記5.3三.簡(jiǎn)答題1.在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的容量(即存儲(chǔ)空間的大小)為maxnum。當(dāng)有元素要加入隊(duì)列(即入隊(duì))時(shí)，若rear=maxnum，則會(huì)發(fā)生隊(duì)列的上溢現(xiàn)象，此時(shí)就不能將該元素加入隊(duì)列。對(duì)于隊(duì)列，還有一種“假溢出”現(xiàn)象:即隊(duì)列中尚有足夠的空間，但元素卻不能入隊(duì)，一般是由于隊(duì)列的存儲(chǔ)結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊(duì)列解決。一般地，要解決隊(duì)列的上溢現(xiàn)象，可以用以下幾種方法：可建立一個(gè)足夠大的存儲(chǔ)空間以避免溢出，但這樣做的缺點(diǎn)是:空間使用率低，浪費(fèi)存儲(chǔ)空間。要避免出現(xiàn)“假溢出”現(xiàn)象，可用以下方法解決：采用移動(dòng)元素的方法。每當(dāng)有一個(gè)新元素入隊(duì)，就將隊(duì)列中已有的元素向隊(duì)頭移動(dòng)一個(gè)位置，假定空余空間足夠。每當(dāng)刪除一個(gè)隊(duì)頭元素，則可依次移動(dòng)隊(duì)列中的元素，總是使front智深指向隊(duì)列中的第一個(gè)位置。采用循環(huán)隊(duì)列方式，將隊(duì)頭、隊(duì)尾看作是一個(gè)首尾相接的循環(huán)隊(duì)列，即用循環(huán)數(shù)組實(shí)現(xiàn)，此時(shí)隊(duì)首仍在隊(duì)尾之前，作插入和刪除運(yùn)算時(shí)仍遵循“先進(jìn)先出”原則。2.共有14中可能的出棧序列，分別為：ABCD，ABDC，ACBD，ACDB，BACD，ADCB，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。3.1234，1243，1324，1342，1432，2134，2143，2314，2341，2431，3214，3241，3421，43214.5綜合實(shí)驗(yàn)：校友通訊錄——線性表的應(yīng)用4.5.1實(shí)驗(yàn)?zāi)康呐c要求(1).復(fù)習(xí)順序表和單鏈表(2).理解順序表和單鏈表的優(yōu)缺點(diǎn)及其應(yīng)用4.5.2實(shí)驗(yàn)準(zhǔn)備與環(huán)境安裝VC6.0或Visualstudio的PC機(jī)一臺(tái)4.5.3實(shí)驗(yàn)內(nèi)容(1).功能需求某學(xué)校要開(kāi)發(fā)一個(gè)校友管理系統(tǒng)，其部分功能如下：=1\*GB3①.院系信息列表，如下表所示，通過(guò)輸入編號(hào)、名稱、地址等信息，新增院系信息，并可以根據(jù)輸入的院系編號(hào)進(jìn)行頻繁的查找操作等功能；表1：院系信息列表編號(hào)名稱地址1計(jì)算與信息科學(xué)學(xué)院1號(hào)樓2應(yīng)用科學(xué)與工程學(xué)院3號(hào)樓3商學(xué)院2號(hào)樓………………=2\*GB3②.校友信息列表，如下表所示，通過(guò)輸入院系名稱，姓名，聯(lián)系方式，新增校友信息，并可以根據(jù)輸入的編號(hào)進(jìn)行頻繁的刪除操作等功能。表2：校友信息列表編號(hào)院系姓名畢業(yè)年份聯(lián)系方式11張三20101889999777722李四20141998888666631王五20051336666333343趙六20181773333222253錢(qián)七201316688889999……(2).案例要求：=1\*GB3①.請(qǐng)根據(jù)以上需求，選擇合適的線性表，對(duì)院系信息和校友信息進(jìn)行存儲(chǔ)；=2\*GB3②.完成院系信息的展示；=3\*GB3③.完成院系信息的查找操作：輸入編號(hào)，返回院系詳細(xì)信息；=4\*GB3④.完成校友信息的展示：院系以名稱方式展示；=5\*GB3⑤.完成校友信息的新增操作：輸入院系名稱，姓名，畢業(yè)年份與聯(lián)系方式，將結(jié)果存儲(chǔ)進(jìn)校友信息，院系以編號(hào)方式存儲(chǔ)；=6\*GB3⑥.完成校友信息的刪除操作：輸入編號(hào)，刪除校友信息；4.6本章習(xí)題一.選擇題(1).空串與空格字符組成的串的區(qū)別在于（）。A、沒(méi)有區(qū)別B、兩串的長(zhǎng)度不相等C、兩串的長(zhǎng)度相等D、兩串包含的字符不相同(2).一個(gè)子串在包含它的主串中的位置是指（）。A、子串中最后的那個(gè)字符在主串中的位置B、子串的最后那個(gè)字符在主串中首次出現(xiàn)的位置C、子串中第一個(gè)字符在主串中的位置D、子串的第一個(gè)字符在主串中首次出現(xiàn)的位置(3).下面的說(shuō)法中，只有（）是正確的。A、字符串的長(zhǎng)度是指串中包含的字母的個(gè)數(shù)B、字符串的長(zhǎng)度是指串中包含的不同字符的個(gè)數(shù)C、若T包含在S中,則T一定是S的一個(gè)子串D、一個(gè)字符串不能說(shuō)是其自身的一個(gè)子串(4).下面關(guān)于串的敘述中，哪個(gè)是不正確的？（）。A、串是字符的有限序列B、空串是由空格構(gòu)成的串C、模式匹配是串的一種重要運(yùn)算D、串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)(5).設(shè)有兩個(gè)串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（）。A、求子串B、聯(lián)接C、匹配D、求串長(zhǎng)(6).兩個(gè)字符串相等的條件是（）。A、兩串的長(zhǎng)度相等B、兩串包含的字符相同C、兩串的長(zhǎng)度相等，并且兩串包含的字符相同D、兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同(7).在長(zhǎng)度為n的字符串S的第i個(gè)位置插入另外一個(gè)字符串，i的合法值應(yīng)該是（）。A、i>0B、i≤nC、1≤i≤nD、1≤i≤n+1(8).字符串采用結(jié)點(diǎn)大小為1的鏈表作為其存儲(chǔ)結(jié)構(gòu)，是指（）。A、鏈表的長(zhǎng)度為1B、鏈表只存放1個(gè)字符C、鏈表的每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中不只存放了一個(gè)字符D、鏈表的每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中只存放了一個(gè)字符(9).串是一種特殊的線性表，其特殊性體現(xiàn)在（）。A、可以順序存儲(chǔ)B、數(shù)據(jù)元素是一個(gè)字符C、可以鏈接存儲(chǔ)D、數(shù)據(jù)元素可以是多個(gè)字符(10).串的長(zhǎng)度是指（）。A、串中所含不同字母的個(gè)數(shù)B、串中所含字符的個(gè)數(shù)C、串中所含不同字符的個(gè)數(shù)D、串中所含非空格字符的個(gè)數(shù)二.填空題(1).計(jì)算機(jī)軟件系統(tǒng)中，有兩種處理字符串長(zhǎng)度的方法：一種是，第二種是。(2).兩個(gè)字符串相等的充要條件是和。(3).組成串的數(shù)據(jù)元素只能是。(4).設(shè)正文串長(zhǎng)度為n，模式串長(zhǎng)度為m，則串匹配的KMP算法時(shí)間復(fù)雜度為。(5).設(shè)T和P是兩個(gè)給定的串，在T中尋找等于P的子串的過(guò)程稱為，又稱p為。第4章習(xí)題答案一.選擇題12345678910BDCBCDCDBB二.填空題1.固定長(zhǎng)度；設(shè)置長(zhǎng)度指針2.兩個(gè)串的長(zhǎng)度相等；對(duì)應(yīng)位置的字符相等3.字符4.O(m+n)5.模式匹配；模式串5.5本章習(xí)題一.選擇題(1).若數(shù)組A[0…m][0…n]按列優(yōu)先順序存儲(chǔ)，則aij地址為（）。A、LOC(a00)+[j*m+i]B、LOC(a00)+[j*n+i]C、LOC(a00)+[(j-1)*n+i-1]D、LOC(a00)+[(j-1)*m+i-1](2).已知二維數(shù)組A10×10中，元素a20的地址為560，每個(gè)元素占4個(gè)字節(jié)，則元素a10的地址為（）。A、520B、522C、524D、518(3).設(shè)有廣義表D=(a,b,D)，其長(zhǎng)度為3，深度為（）。A、無(wú)窮大B、3C、2D、5(4).下列廣義表用圖來(lái)表示時(shí)，分支結(jié)點(diǎn)最多的是（）。A、L=((x,(a,B)),(x,(a,B),y))B、A=(s,(a,b))C、B=((x,(a,B),y))D、D=((a,B),(c,(a,B),D)(5).稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（）。A、二維數(shù)組和三維數(shù)組B、三元組和散列C、三元組和十字鏈表D、散列和十字鏈表(6).有一個(gè)100*90的稀疏矩陣，非0元素有10個(gè)，設(shè)每個(gè)整型數(shù)占2個(gè)字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是（）。A、60B、66C、18000D、33(7).對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)的目的是（）。A、便于進(jìn)行矩陣運(yùn)算B、便于輸入和輸出C、節(jié)省存儲(chǔ)空間D、降低運(yùn)算的時(shí)間復(fù)雜度(8).數(shù)組就是矩陣，矩陣就是數(shù)組，這種說(shuō)法（）。A、正確B、錯(cuò)誤C、前句對(duì)，后句錯(cuò)D、后句對(duì)(9).將一個(gè)A[1..100,1..100]的三對(duì)角矩陣，按行序優(yōu)先存入一維數(shù)組B[1..298]中，A中元素A66,65，在B數(shù)組中的位置K為（）。A、198B、195C、197D、196(10).二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，其行下標(biāo)i=0,1,…,8，列下標(biāo)j=1,2,…,10。若A按行優(yōu)先存儲(chǔ)，元素A[8,5]的起始地址與當(dāng)A按行優(yōu)先存儲(chǔ)時(shí)的元素（）的起始地址相同。（設(shè)每個(gè)字符占一個(gè)字節(jié)）A、A[8,5]B、A[3,10]C、A[5,8]D、A[0,9]二.填空題(1).數(shù)組采用存儲(chǔ)。(2).稀疏矩陣的壓縮存儲(chǔ)與特殊矩陣的壓縮存儲(chǔ)不同，稀疏矩陣的數(shù)據(jù)元素分布，其只存儲(chǔ)元素。(3).是一種編程技巧，具體指一個(gè)過(guò)程或函數(shù)在其定義或說(shuō)明中有直接或間接調(diào)用自身的一種方法，作為一種算法思想在程序設(shè)計(jì)語(yǔ)言中應(yīng)用廣泛。(4).當(dāng)廣義表中的每個(gè)元素都是原子時(shí)，廣義表便成了。(5).廣義表(a,(a,b),d,e,((i,j),k))的長(zhǎng)度是，深度是。第5章習(xí)題答案一.選擇題12345678910AAAACBCBBB二.填空題1.順序存儲(chǔ)結(jié)構(gòu)2.沒(méi)有規(guī)律；非零3.遞歸4.線性表5.5；36.6本章實(shí)驗(yàn)：折半查找6.6.1實(shí)驗(yàn)?zāi)康呐c要求(1).理解查找的概念(2).理解折半查找的思想與實(shí)現(xiàn)6.6.2實(shí)驗(yàn)準(zhǔn)備與環(huán)境安裝VC6.0或Visualstudio的PC機(jī)一臺(tái)6.6.3實(shí)驗(yàn)內(nèi)容編寫(xiě)一個(gè)函數(shù)，利用折半查找算法在一個(gè)有序表中插入一個(gè)元素，并保持表的有序性。例如，在一個(gè)有序表｛1，3，5，7，9｝中，查找元素5，因?yàn)樵卮嬖冢瑒t有序表不變；若查找元素6，則該有序表成為｛1，3，5，6，7，9｝。6.7本章習(xí)題一.選擇題(1).采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為（）。A、nB、n/2C、(n+1)/2D、(n-1)/2(2).對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須（）。A、以鏈?zhǔn)椒绞酱鎯?chǔ)B、以順序方式存儲(chǔ)C、以鏈?zhǔn)椒绞酱鎯?chǔ)且結(jié)點(diǎn)按關(guān)鍵字排序D、以順序方式存儲(chǔ)且結(jié)點(diǎn)必須按關(guān)鍵字排序(3).已知一個(gè)有序順序表為(11,15,23,35,45,56,66,85,89,106,127)，當(dāng)折半查找值為89的元素時(shí)，需要（）次比較即可查找成功。A、1B、2C、3D、4(4).采用折半查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為（）。A、O(n2)B、O(nlog2n)C、O(n)D、O(log2n)(5).對(duì)于長(zhǎng)度為18的順序存儲(chǔ)的有序表，若采用折半查找，則查找第15個(gè)元素的比較次數(shù)為（）。A、3B、4C、5D、6(6).下面關(guān)于折半查找的敘述正確的是（）。A、表必須有序，表可以順序方式存儲(chǔ)，也可以鏈?zhǔn)椒绞酱鎯?chǔ)B、表必須有序，而且表中數(shù)據(jù)必須是整型、實(shí)型或字符型C、表必須有序，而且只能從小到大排序D、表必須有序，且表只能以順序方式存儲(chǔ)(7).用折半查找表的元素的速度比用順序法（）。A、必然快B、必然慢C、相等D、不能確定(8).具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長(zhǎng)度為（）。A、3.1B、4C、2.5D、5(9).在索引查找中，若用于保存數(shù)據(jù)元素的主表的長(zhǎng)度為n，它被均分為k個(gè)子表，每個(gè)子表的長(zhǎng)度均為n/k，則索引查找的平均查找長(zhǎng)度為（）。A、n+kB、k+n/kC、(k+n/k)/2D、(k+n/k)/2+1(10).在索引查找中，若用于保存數(shù)據(jù)元素的主表的長(zhǎng)度為144，它被均分為12子表，每個(gè)子表的長(zhǎng)度均為12，則索引查找的平均查找長(zhǎng)度為（）。A、13B、24C、12D、79二.填空題(1).假定一個(gè)順序表的長(zhǎng)度為40，并假定查找每個(gè)元素的概率相同，則在查找成功情況下的平均查找長(zhǎng)度為，在查找不成功情況下的平均查找長(zhǎng)度為。(2).以折半查找方法在一個(gè)查找表上進(jìn)行查找時(shí)，該查找表必須存儲(chǔ)的表。(3).若有序順序表中有1000個(gè)元素，用折半法查找時(shí)，最大的比較次數(shù)是。(4).對(duì)關(guān)鍵字序列(07,12,15,18,27,32,41,92,117,132,148,156)中用折半查找法查找和給定值92相等的關(guān)鍵字，在查找過(guò)程中依次需要與關(guān)鍵字比較。(5).長(zhǎng)度為225的表，采用分塊查找法，每塊的最佳長(zhǎng)度是。第6章習(xí)題答案一.選擇題12345678910CDBDBDDADA二.填空題1.20.5；412.順序；有序3.114.32，117，41，925.157.6本章實(shí)驗(yàn)：冒泡排序改動(dòng)算法7.6.1實(shí)驗(yàn)?zāi)康呐c要求(1).理解冒泡排序算法(2).鍛煉獨(dú)立思考能力。7.6.2實(shí)驗(yàn)準(zhǔn)備與環(huán)境安裝VC6.0或Visualstudio的PC機(jī)一臺(tái)7.6.3實(shí)驗(yàn)內(nèi)容冒泡可以從后向前“冒”，即每次交換都是從記錄集的最后開(kāi)始，將最小記錄“冒”到最前面。編寫(xiě)一個(gè)函數(shù)，假定待排序記錄的關(guān)鍵字均為整數(shù)，均從數(shù)組中下標(biāo)為1的位置開(kāi)始存儲(chǔ)，下標(biāo)為ss0的位置存儲(chǔ)監(jiān)視哨，或空閑不用(1).待排元素的輸入：=1\*GB3①.待排序元素（整數(shù)）可直接在主函數(shù)(main函數(shù))定義；=2\*GB3②.若待排序元素（整數(shù)）通過(guò)控制臺(tái)輸入的方式進(jìn)行輸入，則要求輸入待排序元素的個(gè)數(shù)N與待排元素arry[]。(2).改動(dòng)算法要求以獨(dú)立函數(shù)的形式進(jìn)行定義，通過(guò)在主函數(shù)（main）中調(diào)用，實(shí)現(xiàn)對(duì)待排元素arry[]的排序（從小到大）。(3).排序后元素的輸出：將排序后的元素從小到大在控制臺(tái)上輸出。7.7本章習(xí)題一.選擇題(1).某內(nèi)排序方法的穩(wěn)定性是指（）。A、該排序算法不允許有相同的關(guān)鍵字記錄B、該排序算法允許有相同的關(guān)鍵字記錄C、平均時(shí)間為O(nlogn)的排序方法D、以上都不對(duì)(2).若對(duì)n個(gè)元素進(jìn)行直接插入排序，在進(jìn)行第i趟排序時(shí)，假定元素r[i+1]的插入位置為r[j]，則需要移動(dòng)元素的次數(shù)為（）。A、j-iB、i-j-1C、i-jD、i-j+1(3).冒泡排序最壞的情形時(shí)間復(fù)雜性（）。A、O(1)B、O(n)C、O(n2)D、O(nlog2n)(4).在對(duì)n個(gè)元素進(jìn)行冒泡排序的過(guò)程中，第一趟排序至多需要進(jìn)行（）次相鄰元素之間的交換。A、nB、n-1C、n+1D、n/2(5).在對(duì)n個(gè)元素進(jìn)行快速排序的過(guò)程中，若每次劃分得到的左、右兩個(gè)子區(qū)間中元素的個(gè)數(shù)相等或只差一個(gè)，則整個(gè)排序過(guò)程得到的含兩個(gè)元素的區(qū)間個(gè)數(shù)大致為（）。A、nB、n/2C、log2nD、2n(6).在對(duì)n個(gè)元素進(jìn)行快速排序的過(guò)程中，最好情況下需要進(jìn)行（）趟。A、nB、n/2C、log2nD、2n(7).對(duì)下列四個(gè)序列進(jìn)行快速排序，都以第一個(gè)元素為基準(zhǔn)進(jìn)行第一次劃分，則在該次劃分過(guò)程中需要移動(dòng)元素次數(shù)最多的序列為（）。A、1,3,5,7,9B、9,7,5,3,1C、5,3,1,7,9D、5,7,9,1,3(8).假定對(duì)元素序列(7,3,5,9,1,12,8,15)進(jìn)行快速排序，則進(jìn)行第一次劃分后，得到的左區(qū)間中元素的個(gè)數(shù)為（）。A、2B、3C、4D、5(9).一組記錄的關(guān)鍵碼為(46,79,56,38,40,84)，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（）。A、(38,40,46,56,79,84)B、(40,38,46,79,56,84)C、(40,38,46,56,79,84)D、(40,38,46,84,56,79)(10).對(duì)下列4個(gè)序列用快速排序方法進(jìn)行排序，以序列的第1個(gè)元素為基準(zhǔn)進(jìn)行劃分。在第1趟劃分過(guò)程中，元素移動(dòng)次數(shù)最多的是序列（）A、71,75,82,90,24,18,10,68B、71,75,68,23,10,18,90,82C、82,75,71,18,10,90,68,24D、24,10,18,71,82,75,68,90二.填空題(1).對(duì)n個(gè)記錄進(jìn)行冒泡排序時(shí)，最少的比較次數(shù)為，最少的趟數(shù)為。(2).假定一組記錄為(46,79,56,64,38,40,84,43)，在冒泡排序的過(guò)程中進(jìn)行第一趟排序時(shí)，元素79將最終下沉到其后第個(gè)元素的位置。(3).假定一組記錄為(46,79,56,38,40,84,43)，對(duì)其進(jìn)行快速排序的過(guò)程中，共需要趟排序。(4).假定一組記錄為(46,79,56,38,40,80)，對(duì)其進(jìn)行快速排序的第一次劃分后的結(jié)果為。(以第一個(gè)元素作為基準(zhǔn))(5).假定一組記錄為(46,79,56,38,40,80)，對(duì)其進(jìn)行歸并排序的過(guò)程中，第二趟歸并后的結(jié)果為。第7章習(xí)題答案一.選擇題12345678910DDCBBCDBCA二.填空題1.n-1；12.43.34.[4038]46[567980]5.[38465679][4080]8.9討論課：我該如何學(xué)習(xí)樹(shù)？(1).討論主題我該如何學(xué)習(xí)樹(shù)？(2).討論說(shuō)明=1\*GB3①.二叉樹(shù)的存儲(chǔ)：順序存儲(chǔ)：順序存儲(chǔ)也是用一組連續(xù)的存儲(chǔ)單元來(lái)存放二叉樹(shù)中的節(jié)點(diǎn)元素。對(duì)于完全二叉樹(shù)來(lái)說(shuō)，分配一段相應(yīng)大小的空間，對(duì)樹(shù)中的節(jié)點(diǎn)自上而下，自左至右進(jìn)行存儲(chǔ)。在順序存儲(chǔ)時(shí)，0角標(biāo)位置基本不用，從角標(biāo)1開(kāi)始存儲(chǔ)。這樣既存儲(chǔ)了樹(shù)中的節(jié)點(diǎn)元素，又存儲(chǔ)了節(jié)點(diǎn)之間的邏輯關(guān)系。根據(jù)二叉樹(shù)的性質(zhì)5，知道了某一個(gè)節(jié)點(diǎn)元素的角標(biāo)，那么它的父節(jié)點(diǎn)與孩子節(jié)點(diǎn)就能輕易找到。根據(jù)二叉樹(shù)的性質(zhì)5，知道了某一個(gè)節(jié)點(diǎn)元素的角標(biāo)，那么它的父節(jié)點(diǎn)與孩子節(jié)點(diǎn)就能輕易找到。根據(jù)完全二叉樹(shù)的這個(gè)性質(zhì)，我們可以將順序存儲(chǔ)中的完全二叉樹(shù)還原出來(lái)。二叉鏈：使用二叉鏈表表示樹(shù)，通常樹(shù)中的每個(gè)節(jié)點(diǎn)由三部分組成：數(shù)據(jù)域和左、右指針域。左、右指針?lè)謩e指示節(jié)點(diǎn)的左、右孩子三叉鏈：在二叉鏈表存儲(chǔ)的基礎(chǔ)上，為了能夠順利找到節(jié)點(diǎn)的父節(jié)點(diǎn)，在節(jié)點(diǎn)中添加一個(gè)指向父節(jié)點(diǎn)的指針parent，形成一個(gè)帶父指針的節(jié)點(diǎn)，使用這種節(jié)點(diǎn)構(gòu)建出的二叉樹(shù)稱為三叉鏈表。=2\*GB3②.二叉樹(shù)的遍歷：前序遍歷：先根，再左，最后右中序遍歷：先左，再根，最后右后序遍歷：先左，再右，最后根(3).分組形式每5個(gè)人為一個(gè)小組，每個(gè)小組設(shè)置組長(zhǎng)1名，組長(zhǎng)具體負(fù)責(zé)任務(wù)分配協(xié)調(diào)。(4).提交文檔在大量文獻(xiàn)調(diào)研的基礎(chǔ)上，撰寫(xiě)制作一份答辯PPT，闡述自己的觀點(diǎn)。文件命名：第X小組(5).課堂答辯每個(gè)小組派出一名代表進(jìn)行課堂演講，每個(gè)人演講10分鐘，演講內(nèi)容需要圍繞事先準(zhǔn)備好的PPT進(jìn)行。演講結(jié)束后，有5分鐘的自由提問(wèn)和回答時(shí)間。(6).考核方法本次討論課的最終成績(jī)由兩個(gè)部分構(gòu)成：PPT50%，演講50%。8.10本章實(shí)驗(yàn)：二叉樹(shù)的創(chuàng)建與遍歷8.10.1實(shí)驗(yàn)?zāi)康呐c要求(1).理解二叉樹(shù)的定義與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(2).掌握二叉樹(shù)創(chuàng)建與遍歷的遞歸思想8.10.2實(shí)驗(yàn)準(zhǔn)備與環(huán)境安裝VC6.0或Visualstudio的PC機(jī)一臺(tái)8.10.3實(shí)驗(yàn)內(nèi)容(1).按照二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)的定義，實(shí)現(xiàn)二叉樹(shù)的鏈?zhǔn)蕉x，實(shí)現(xiàn)以下二叉樹(shù)的創(chuàng)建（二叉樹(shù)中存儲(chǔ)的數(shù)據(jù)為字符類(lèi)型數(shù)據(jù)）：(2).分別采用先序、中序、后序輸出上述二叉樹(shù)的節(jié)點(diǎn)數(shù)據(jù)信息。(3).【思考】若二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)，則二叉樹(shù)的創(chuàng)建該如何實(shí)現(xiàn)？8.11本章實(shí)驗(yàn)：二叉樹(shù)的查找8.11.1實(shí)驗(yàn)?zāi)康呐c要求(1).理解二叉樹(shù)的定義(2).掌握二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(3).理解二叉樹(shù)的遞歸結(jié)構(gòu)8.11.2實(shí)驗(yàn)準(zhǔn)備與環(huán)境安裝VC6.0或Visualstudio的PC機(jī)一臺(tái)8.11.3實(shí)驗(yàn)內(nèi)容在二叉樹(shù)中實(shí)現(xiàn)查找，若查找的元素在二叉樹(shù)中存在，則得出該元素所在的層數(shù)，若不存在，則得出0。例如：在鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)的二叉樹(shù)中（如下圖所示），查找元素，(1).若查找元素“H”，則得出所在層數(shù)4；(2).若查找元素“S”，則得出0，表示該元素在樹(shù)中不存在。其他要求如下：(1).二叉樹(shù)中存儲(chǔ)的數(shù)據(jù)為字符類(lèi)型數(shù)據(jù)；(2).查找功能以函數(shù)方式進(jìn)行定義與實(shí)現(xiàn)；(3).二叉樹(shù)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。8.12綜合實(shí)驗(yàn)：校友通訊錄——樹(shù)的應(yīng)用8.12.1實(shí)驗(yàn)?zāi)康呐c要求(1).復(fù)習(xí)樹(shù)和二叉樹(shù)(2).熟悉樹(shù)和二叉樹(shù)的創(chuàng)建、遍歷8.12.2實(shí)驗(yàn)準(zhǔn)備與環(huán)境安裝VC6.0或Visualstudio的PC機(jī)一臺(tái)8.12.3實(shí)驗(yàn)內(nèi)容(1).功能需求某學(xué)校要開(kāi)發(fā)一個(gè)校友管理系統(tǒng)，其部分功能如下：=1\*GB3①.院系信息列表，如下表所示，通過(guò)輸入編號(hào)、名稱、地址等信息，新增院系信息，并可以根據(jù)輸入的院系編號(hào)進(jìn)行頻繁的查找操作等功能；表1：院系信息列表編號(hào)名稱地址1計(jì)算與信息科學(xué)學(xué)院1號(hào)樓2應(yīng)用科學(xué)與工程學(xué)院3號(hào)樓3商學(xué)院2號(hào)樓………………=2\*GB3②.校友信息列表，如下表所示，通過(guò)輸入院系名稱，姓名，聯(lián)系方式，新增校友信息，并可以根據(jù)輸入的編號(hào)進(jìn)行頻繁的刪除操作等功能。表2：校友信息列表編號(hào)院系姓名畢業(yè)年份聯(lián)系方式11張三20101889999777722李四20141998888666631王五20051336666333343趙六20181773333222253錢(qián)七201316688889999……(2).案例要求：=1\*GB3①.請(qǐng)根據(jù)以上需求，選擇合適的樹(shù)結(jié)構(gòu)，對(duì)院系信息和校友信息進(jìn)行存儲(chǔ)；=2\*GB3②.完成校友信息的樹(shù)形展示，院系--校友的鏈接方式；=3\*GB3③.完成校友信息的查找操作：輸入校友姓名，返回院系以及校友的詳細(xì)信息；8.13本章習(xí)題一.選擇題(1).在一棵二叉樹(shù)上第4層的結(jié)點(diǎn)數(shù)最多為（）。A、2B、4C、6D、8(2).在一棵二叉樹(shù)中，共有16個(gè)度為2的結(jié)點(diǎn)，則其共有（）個(gè)葉子結(jié)點(diǎn)。A、15B、16C、17D、18(3).一棵完全二叉樹(shù)中根結(jié)點(diǎn)的編號(hào)為1，而且編號(hào)為23的結(jié)點(diǎn)有左孩子但沒(méi)有右孩子，則此樹(shù)中共有（）個(gè)結(jié)點(diǎn)。A、24B、45C、46D、47(4).設(shè)n,m為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn),在中序遍歷序列中n在m前的條件是（）。A、n在m右子樹(shù)B、n在m左子樹(shù)C、n是m的祖先D、n是m的子孫(5).任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（）。A、不發(fā)生改變B、發(fā)生改變C、不能確定D、以上都不對(duì)(6).根據(jù)先序序列ABDC和中序序列DBAC確定對(duì)應(yīng)的二叉樹(shù)，該二叉樹(shù)（）。A、是完全二叉樹(shù)B、不是完全二叉樹(shù)C、是滿二叉樹(shù)D、不是滿二叉樹(shù)(7).設(shè)有一表示算術(shù)表達(dá)式的二叉樹(shù)如下圖所示，它所表示的算術(shù)表達(dá)式是（）。A、A*B+C/(D*E)+(F-G)B、(A*B+C)/(D*E)+(F-G)C、(A*B+C)/(D*E+(F-G))D、A*B+C/D*E+F-G(8).某二叉樹(shù)的中序序列和后序序列相同，則這棵二叉樹(shù)必然是（）。A、空樹(shù)B、空樹(shù)或任一結(jié)點(diǎn)均無(wú)左孩子的非空二叉樹(shù)C、空樹(shù)或任一結(jié)點(diǎn)均無(wú)右孩子的非空二叉樹(shù)D、空樹(shù)或僅有一個(gè)結(jié)點(diǎn)的二叉樹(shù)(9).二叉線索樹(shù)的目的是（）。A、加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B、為了能在二叉樹(shù)中方便的進(jìn)行插入與刪除C、為了能方便的找到雙親D、使二叉樹(shù)的遍歷結(jié)果唯一(10).線索二叉樹(shù)是一種（）結(jié)構(gòu)。A、邏輯B、邏輯和存儲(chǔ)C、物理D、線性二.填空題(1).在二叉樹(shù)的順序存儲(chǔ)中，對(duì)于下標(biāo)為5的結(jié)點(diǎn)，它的雙親結(jié)點(diǎn)的下標(biāo)為；若它存在左孩子，則左孩子結(jié)點(diǎn)的下標(biāo)為；若它存在右孩子，則右孩子結(jié)點(diǎn)的下標(biāo)為。(2).對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)它為一棵二叉樹(shù)時(shí)具有最小高度，即為；當(dāng)它為一棵單支樹(shù)具有高度，即為。(3).已知用一維數(shù)組存放的一棵完全二叉樹(shù)：ABCDEFGHIJKL，寫(xiě)出該二叉樹(shù)的先序、中和后序。(4).中綴式a+b*3+4*(c-d)對(duì)應(yīng)的前綴式為，若a=1，b=2，c=3，d=4，則后綴式db/cc*a-b*+的運(yùn)算結(jié)果為。(5).空樹(shù)是指，最小的樹(shù)是指。三.簡(jiǎn)答題(1).已知一棵樹(shù)邊的集合為如下：{<i,m>,<i,n>,<e,i>,<b,e>,<b,d>,<a,b>,<g,j>,<g,k>,<c,g>,<c,f>,<g,l>,<c,h>,<a,c>}，請(qǐng)畫(huà)出這棵樹(shù),并回答下列問(wèn)題：=1\*GB3①.哪個(gè)是根結(jié)點(diǎn)？=2\*GB3②.哪些是葉子結(jié)點(diǎn)？=4\*GB3④.哪個(gè)是結(jié)點(diǎn)g的雙親？=5\*GB3⑤.哪些是結(jié)點(diǎn)g的祖先？=6\*GB3⑥.哪些是結(jié)點(diǎn)g的孩子？=7\*GB3⑦.哪些是結(jié)點(diǎn)e的孩子？=8\*GB3⑧.哪些是結(jié)點(diǎn)e的兄弟？哪些是結(jié)點(diǎn)f的兄弟？=9\*GB3⑨.結(jié)點(diǎn)b和n的層次號(hào)分別是什么？=10\*GB3⑩.樹(shù)的深度是多少？(2).將下圖中所示的樹(shù)轉(zhuǎn)換為二叉樹(shù)（給出主要過(guò)程）。(3).如果一棵樹(shù)有n1個(gè)度為1的結(jié)點(diǎn)，有n2個(gè)度為2的結(jié)點(diǎn)，……，nm個(gè)度為m的結(jié)點(diǎn)，試問(wèn)有多少個(gè)度為0的結(jié)點(diǎn)？試推導(dǎo)之。四.編程題(1).給定一棵二叉樹(shù)，用二叉鏈表表示，其根指針為t，試寫(xiě)出求該二叉樹(shù)中結(jié)點(diǎn)n的雙親結(jié)點(diǎn)的算法。若沒(méi)有結(jié)點(diǎn)n或者該結(jié)點(diǎn)沒(méi)有雙親結(jié)點(diǎn)，分別輸出相應(yīng)的信息；若結(jié)點(diǎn)n有雙親，輸出其雙親的值。第8章習(xí)題答案一.選擇題12345678910DCCBAACCAC二.填空題1.2；10；112.完全；；最大；n3.ABDHIEJKCFLG；HDIBJEKALFCG；HIDJKEBLFGCA4.++a*b3*4-cd；185.結(jié)點(diǎn)數(shù)為0的樹(shù)；只有一個(gè)根結(jié)點(diǎn)的樹(shù)三.簡(jiǎn)答題1.根據(jù)給定的邊確定的樹(shù)如圖所示：其中根結(jié)點(diǎn)是a；葉子節(jié)點(diǎn)有：d、m、n、j、k、f、l；c是結(jié)點(diǎn)g的雙親；a、c是結(jié)點(diǎn)g的祖先；j、k是結(jié)點(diǎn)g的孩子；m、n是結(jié)點(diǎn)e的子孫；e是結(jié)點(diǎn)d的兄弟；g、h是結(jié)點(diǎn)f的兄弟；結(jié)點(diǎn)b和n的層次號(hào)分別是2和5；樹(shù)的深度為5。2.樹(shù)轉(zhuǎn)換為二叉樹(shù)的主要過(guò)程有三步，分別為：加線、抹線和旋轉(zhuǎn)。過(guò)程圖示與轉(zhuǎn)換結(jié)果分別如下圖a~d所示。(a)加線 (b)抹線

(c)旋轉(zhuǎn) (d)二叉樹(shù)3.證明：總結(jié)點(diǎn)數(shù)：————①總分支數(shù)：————②將公式①代入公式②，可得：整理后，則有四.編程題略9.5本章習(xí)題選擇題(1).從具有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)中查找一個(gè)元素時(shí)，在平均情況下的時(shí)間復(fù)雜度大致為（）。A、O(n)B、O(1)C、O(log2n)D、O(n2)(2).從具有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)中查找一個(gè)元素時(shí)，在最壞情況下的時(shí)間復(fù)雜度為（）。A、O(n)B、O(1)C、O(log2n)D、O(n2)(3).根據(jù)n個(gè)元素建立一棵二叉排序樹(shù)的時(shí)間復(fù)雜度大致為（）。A、O(n)B、O(1)C、O(nlog2n)D、O(n2)(4).二叉排序樹(shù)的查找效率與二叉樹(shù)的（）有關(guān)。A、高度B、結(jié)點(diǎn)的多少C、樹(shù)型D、結(jié)點(diǎn)的位置(5).二叉排序樹(shù)的查找效率在（）時(shí)，其查找效率最低。A、結(jié)點(diǎn)太多B、完全二叉樹(shù)C、呈單支樹(shù)D、結(jié)點(diǎn)太復(fù)雜(6).二叉排序樹(shù)采用（）遍歷可以得到結(jié)點(diǎn)的有序序列。A、前序B、中序C、后序D、層次(7).若在二叉排序樹(shù)上查找關(guān)鍵字為35的節(jié)點(diǎn)，則所比較關(guān)鍵字的序列有可能是（）。A、{46,36,18,28,35}B、{18,36,28,46,35}C、{46,28,18,36,35}D、{28,36,18,46,35}(8).在一棵平衡二叉樹(shù)中,每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍是（）。A、-1~1B、-2~2C、1~2D、0~1(9).在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應(yīng)作（）型調(diào)整以使其平衡。A、LLB、LRC、RLD、RR(10).對(duì)平衡二叉樹(shù)進(jìn)行插入或刪除一個(gè)元素的操作時(shí)，可能引起不平衡，需要對(duì)其進(jìn)行調(diào)整操作，以恢復(fù)平衡，調(diào)整操作被分為（）中不同的情況。A、2B、3C、4D、5填空題(1).在一棵二叉排序樹(shù)中，每個(gè)分支結(jié)點(diǎn)的左子樹(shù)上所有結(jié)點(diǎn)的值一定該結(jié)點(diǎn)的值，右子樹(shù)上所有結(jié)點(diǎn)的值一定該結(jié)點(diǎn)的值。(2).從一棵二叉排序樹(shù)中查找一個(gè)元素時(shí)，若元素的值等于根結(jié)點(diǎn)的值，則表明，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向查找，若元素的值大于根結(jié)點(diǎn)的值，則繼續(xù)向查找。(3).從空樹(shù)開(kāi)始，依次插入元素52、26、14、32、71、60、93、58、24和41，構(gòu)成一顆二叉排序樹(shù)，在該樹(shù)中查找元素60要進(jìn)行比較的次數(shù)為。(4).平衡因子的定義是。(5).具有5層節(jié)點(diǎn)的平衡二叉樹(shù)至少有個(gè)節(jié)點(diǎn)。第9章習(xí)題答案一.選擇題12345678910CACACBAACC二.填空題1.小于；大于2.查找成功；左子樹(shù)；右子樹(shù)3.34.結(jié)點(diǎn)的左子樹(shù)的高度減去結(jié)點(diǎn)的右子樹(shù)的高度5.1210.5本章習(xí)題一.選擇題(1).在對(duì)n個(gè)元素進(jìn)行簡(jiǎn)單選擇排序的過(guò)程中，需要進(jìn)行（）趟選擇和交換。A、nB、n+1C、n-1D、n/2(2).若對(duì)n個(gè)元素進(jìn)行堆排序，則在構(gòu)成初始堆的過(guò)程中需要進(jìn)行（）次篩運(yùn)算。A、1B、n/2C、nD、n-1(3).若對(duì)n個(gè)元素進(jìn)行堆排序，則每次進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜性為（）。A、O(1)B、O(log2n)C、O(n2)D、O(n)(4).假定對(duì)元素序列(7,3,5,9,1,12)進(jìn)行堆排序，并且采用小根堆，則由初始數(shù)據(jù)構(gòu)成的初始堆為（）。A、1,3,5,7,9,12B、1,3,5,9,7,12C、1,5,3,7,9,12D、1,5,3,9,12,7(5).假定一個(gè)初始堆為(1,5,3,9,12,7,15,10)，則進(jìn)行第一趟堆排序后得到的結(jié)果為（）。A、3,5,7,9,12,10,15,1B、3,5,9,7,12,10,12,1C、3,7,5,9,12,10,15,1D、3,5,7,12,9,10,15,1(6).若一個(gè)元素序列基本有序，則選用（）方法較快。A、直接插入排序B、簡(jiǎn)單選擇排序C、堆排序D、快速排序(7).在平均情況下速度最快的排序方法為（）。A、簡(jiǎn)單選擇排序B、歸并排序C、堆排序D、快速排序(8).下列排算法中，每一趟都能選出一個(gè)元素放到其最終位置上，并且其時(shí)間性能受數(shù)據(jù)初始特性影響的是（）。A、直接插入排序B、快速排序C、直接選擇排序D、堆排序(9).下列排序算法中，（）算法可能在初始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而最多。A、堆排序B、冒泡排序C、快速排序D、插入排序(10).若要從1000個(gè)元素中得到10個(gè)最小值元素，最好采用（）方法。A、直接插入排序B、直接選擇排序C、堆排序D、快速排序二.填空題(1).在所有排序方法中，方法使數(shù)據(jù)的組織采用的是完全二叉樹(shù)的結(jié)構(gòu)。(2).若對(duì)一組記錄(76,38,62,53,80,74,83,65,85)進(jìn)行堆排序，已知除第一個(gè)元素外，以其余元素為根的結(jié)點(diǎn)都已是堆，則對(duì)第一個(gè)元素進(jìn)行篩運(yùn)算時(shí)，它將最終被篩到下標(biāo)為的位置。(3).假定一個(gè)堆為(38,40,56,79,46,84)，則利用堆排序方法進(jìn)行第一趟交換和對(duì)根結(jié)點(diǎn)篩運(yùn)算后得到的結(jié)果為。(4).假定一組記錄為(46,79,56,38,40,84)，則利用堆排序方法建立的初始小根堆為。(5).在快速排序和堆排序中，若待排序記錄序列接近正序或逆序，則應(yīng)該選用；若待排序記錄序列無(wú)序，則應(yīng)該選用。第10章習(xí)題答案一.選擇題12345678910CBBBAADBCC二.填空題1.堆排序2.83.(40,46,56,79,84,38)4.(38,40,56,79,46,84)5.堆排序；快速排序11.6討論課：圖是什么？(1).討論主題圖是什么？(2).討論說(shuō)明=1\*GB3①.深度優(yōu)先遍歷（DepthFirstSearch）是樹(shù)先序遍歷的推廣，它的基本思想是：任意選定圖中一個(gè)頂點(diǎn)v，從頂點(diǎn)v開(kāi)始訪問(wèn)，然后選定v的一個(gè)沒(méi)有被訪問(wèn)過(guò)的鄰接點(diǎn)w，對(duì)頂點(diǎn)w進(jìn)行深度優(yōu)先遍歷，直到圖中與當(dāng)前頂點(diǎn)鄰接的頂點(diǎn)全部被訪問(wèn)為止。如果當(dāng)前仍有頂點(diǎn)尚未訪問(wèn)，則從未訪問(wèn)的頂中任選一個(gè)頂點(diǎn)，執(zhí)行前述遍歷過(guò)程。顯然這個(gè)遍歷過(guò)程是一個(gè)遞歸的過(guò)程。=2\*GB3②.s廣度優(yōu)先遍歷（BreadthFirstSearch）類(lèi)似于樹(shù)的按層遍歷。它的基本思想是：任意選定一個(gè)頂點(diǎn)v開(kāi)始本次訪問(wèn)，在訪問(wèn)過(guò)v之后依次訪問(wèn)v的待訪問(wèn)（尚未被訪問(wèn)）鄰接點(diǎn)，并將已訪問(wèn)的頂點(diǎn)放入隊(duì)列Q。按照Q中頂點(diǎn)的次序，依次訪問(wèn)這些已被訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)。如果隊(duì)首的頂點(diǎn)不存在待訪問(wèn)鄰接點(diǎn)，讓隊(duì)首頂點(diǎn)出隊(duì)，訪問(wèn)新隊(duì)首的待訪問(wèn)鄰接點(diǎn)，如此直到隊(duì)列為空。(3).分組形式每5個(gè)人為一個(gè)小組，每個(gè)小組設(shè)置組長(zhǎng)1名，組長(zhǎng)具體負(fù)責(zé)任務(wù)分配協(xié)調(diào)。(4).提交文檔在大量文獻(xiàn)調(diào)研的基礎(chǔ)上，撰寫(xiě)制作一份答辯PPT，闡述自己的觀點(diǎn)。文件命名：第X小組(5).課堂答辯每個(gè)小組派出一名代表進(jìn)行課堂演講，每個(gè)人演講10分鐘，演講內(nèi)容需要圍繞事先準(zhǔn)備好的PPT進(jìn)行。演講結(jié)束后，有5分鐘的自由提問(wèn)和回答時(shí)間。(6).考核方法本次討論課的最終成績(jī)由兩個(gè)部分構(gòu)成：PPT50%，演講50%。11.7本章實(shí)驗(yàn)：圖的鄰接矩陣的定義與創(chuàng)建11.7.1實(shí)驗(yàn)?zāi)康呐c要求(1).理解圖的鄰接矩陣定義(2).理解圖的創(chuàng)建方式11.7.2實(shí)驗(yàn)準(zhǔn)備與環(huán)境安裝VC6.0或Visualstudio的PC機(jī)一臺(tái)11.7.3實(shí)驗(yàn)內(nèi)容(1).采用鄰接矩陣存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)以下賦權(quán)有向圖的實(shí)現(xiàn)與創(chuàng)建，具體要求如下：(2).要求定義函數(shù)，在函數(shù)中創(chuàng)建賦權(quán)有向圖的鄰接矩陣；(3).要求輸入n個(gè)頂點(diǎn)、e條邊與各條邊的權(quán)值，n、e及權(quán)值由控制臺(tái)輸入。(4).【思考】若實(shí)現(xiàn)賦權(quán)無(wú)向圖，則如何修改上述函數(shù)？(5).【思考】若實(shí)現(xiàn)不帶權(quán)有向圖，則如何修改上述函數(shù)？(6).【思考】請(qǐng)補(bǔ)充賦權(quán)有向圖的其它操作，如加入一條邊、刪除一條邊、增加一個(gè)頂點(diǎn)等。11.8本章實(shí)驗(yàn)：圖的鄰接表的定義與創(chuàng)建11.8.1實(shí)驗(yàn)?zāi)康呐c要求(1).理解圖的鄰接表定義(2).理解圖的創(chuàng)建方式11.8.2實(shí)驗(yàn)準(zhǔn)備與環(huán)境安裝VC6.0或Visualstudio的PC機(jī)一臺(tái)11.8.3實(shí)驗(yàn)內(nèi)容(1).采用鄰接表存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)以下賦權(quán)有向圖的實(shí)現(xiàn)與創(chuàng)建，具體要求如下：=1\*GB3①.要求定義函數(shù)，在函數(shù)中創(chuàng)建賦權(quán)有向圖的鄰接表；=2\*GB3②.要求輸入n個(gè)頂點(diǎn)、e條邊與各條邊的權(quán)值，n、e及權(quán)值由控制臺(tái)輸入。88201210AndC++DeBynd0123(2).【思考】若實(shí)現(xiàn)賦權(quán)無(wú)向圖，則如何修改上述函數(shù)？(3).【思考】若實(shí)現(xiàn)不帶權(quán)有向圖，則如何修改上述函數(shù)？(4).【思考】請(qǐng)補(bǔ)充賦權(quán)有向圖的其它操作，如加入一條邊、刪除一條邊、增加一個(gè)頂點(diǎn)等。11.9綜合實(shí)驗(yàn)：校友通訊錄——圖的應(yīng)用11.9.1實(shí)驗(yàn)?zāi)康呐c要求(1).復(fù)習(xí)圖(2).熟悉圖的存儲(chǔ)結(jié)構(gòu)(3).熟悉圖的應(yīng)用11.9.2實(shí)驗(yàn)準(zhǔn)備與環(huán)境安裝VC6.0或Visualstudio的PC機(jī)一臺(tái)11.9.3實(shí)驗(yàn)內(nèi)容(1).功能需求某學(xué)校要開(kāi)發(fā)一個(gè)校友管理系統(tǒng)，其部分功能如下：=1\*GB3①.院系信息列表，如下表所示，通過(guò)輸入編號(hào)、名稱、地址等信息，新增院系信息，并可以根據(jù)輸入的院系編號(hào)進(jìn)行頻繁的查找操作等功能；表1：院系信息列表編號(hào)名稱地址1計(jì)算與信息科學(xué)學(xué)院1號(hào)樓2應(yīng)用科學(xué)與工程學(xué)院3號(hào)樓3商學(xué)院2號(hào)樓………………=2\*GB3②.校友信息列表，如下表所示，通過(guò)輸入院系名稱，姓名，聯(lián)系方式，新增校友信息，并可以根據(jù)輸入的編號(hào)進(jìn)行頻繁的刪除操作等功能。表2：校友信息列表編號(hào)院系姓名畢業(yè)年份聯(lián)系方式11張三20101889999777722李四20141998888666631王五20051336666333343趙六20181773333222253錢(qián)七201316688889999……(2).案例要求：給定院系之間的交通圖。若院系i和j之間有路可通，則i和j用邊連接，邊上的權(quán)值Wij表示這條道路的長(zhǎng)度。現(xiàn)某位校友打算以某個(gè)院系為起點(diǎn)，訪問(wèn)各個(gè)院系。采用Dijkstra算法完成以下要求：（院系之間為無(wú)向圖，但所寫(xiě)算法對(duì)于其加強(qiáng)命題有向圖也須成立）：=1\*GB3①.找出該校友應(yīng)該以那個(gè)院系為起點(diǎn)，才能使距離該校友最遠(yuǎn)的院系與他的距離最短；=2\*GB3②.找出該校友應(yīng)該以那個(gè)院系為起點(diǎn)，才能使其他所有院系與他的距離綜合最短。(3).提示：=1\*GB3①.對(duì)于第一個(gè)問(wèn)題，可以先求出每個(gè)院系到其它所有院系的最短路徑，保存其最大值（表示假設(shè)該校友在該院系，距離他最遠(yuǎn)的院系的路徑長(zhǎng)度）；然后在這些最大值中找出一個(gè)最小值。=2\*GB3②.對(duì)第二個(gè)問(wèn)題，可以先求出每個(gè)院系到其它所有院系的最短路徑，保存其累加和（表示假設(shè)該校友在該院系，其它所有院系距離他的路徑總和）；然后在這些和中找出一個(gè)最小值。11.10本章習(xí)題一.選擇題(1).具有n個(gè)頂點(diǎn)的無(wú)向完全圖,邊的總數(shù)為（）條。A、n-1B、nC、n+1D、n*(n-1)/2(2).若一個(gè)圖中包含有k個(gè)連通分量，若要按照深度優(yōu)先搜索的方法訪問(wèn)所有頂點(diǎn)，則必須調(diào)用（）次深度優(yōu)先搜索遍歷的算法。A、kB、1C、k-1D、k+1(3).若要把n個(gè)頂點(diǎn)連接為一個(gè)連通圖，則至少需要（）條邊。A、nB、n+1C、n-1D、2n(4).對(duì)于一個(gè)無(wú)向圖，下面（）種說(shuō)法是正確的。A、每個(gè)頂點(diǎn)的入度等于出度B、每個(gè)頂點(diǎn)的度等于其入度與出度之和C、每個(gè)頂點(diǎn)的入度為0D、每個(gè)頂點(diǎn)的出度為0(5).存儲(chǔ)無(wú)向圖的鄰接矩陣一定是一個(gè)（）。A、上三角矩陣B、稀疏矩陣C、對(duì)稱矩陣D、對(duì)角矩陣(6).若一個(gè)圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，則從頂點(diǎn)A開(kāi)始對(duì)該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為（）。A、A,B,C,F,D,EB、A,C,F,D,E,BC、A,B,D,C,F,ED、A,B,D,F,E,C(7).若一個(gè)圖的邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，則從頂點(diǎn)1開(kāi)始對(duì)該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點(diǎn)序列可能為（）。A、1,2,3,4,5B、1,2,4,3,5C、1,2,4,5,3D、1,4,2,5,3(8).以下說(shuō)法中不正確的是（）。A、無(wú)向圖的極大連通子圖稱為連通分量B、連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)C、圖的深度優(yōu)先搜索中一般要采用棧來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)。D、有向圖的遍歷不可采用廣度優(yōu)先搜索方法。(9).已知一個(gè)有向圖的邊集為{<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>}，則由該圖產(chǎn)生的一種可能的拓?fù)湫蛄袨椋ǎ、圖中有奇數(shù)個(gè)結(jié)點(diǎn)B、圖中有偶數(shù)個(gè)結(jié)點(diǎn)C、圖為無(wú)向圖D、圖為有向圖(10).下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（）。A、關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B、任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成C、所有的關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成D、某些關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成二.填空題(1).在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有條邊；在一個(gè)具有n個(gè)頂點(diǎn)的完全有向圖中，包含有條邊。(2).假定一個(gè)有向圖的頂點(diǎn)集為{a,b,c,d,e,f}，邊集為{<a,c>,<a,e>,<c,f>,<d,c>,<e,b>,<e,d>}，則出度為0的頂點(diǎn)個(gè)數(shù)為，入度為1的頂點(diǎn)個(gè)數(shù)為。(3).若一個(gè)圖的頂點(diǎn)集為{a,b,c,d,e,f}，邊集為{(a,b),(a,c),(b,c),(d,e)}，則該圖含有個(gè)連通分量。(4).已知一個(gè)無(wú)向圖如下所示，在該圖的最小生成樹(shù)中，各邊的權(quán)值之和為。(5).對(duì)于如圖所示的無(wú)向圖，，假定采用鄰接矩陣表示，試分別寫(xiě)出從頂點(diǎn)0出發(fā)，按照深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。（注：每一種序列都是唯一的，因?yàn)槎际窃诖鎯?chǔ)結(jié)構(gòu)上得到的）三.簡(jiǎn)答題(1).已知如圖所示的一個(gè)網(wǎng)，按照Prim方法，從頂點(diǎn)V1出發(fā)，求該網(wǎng)的最小生成樹(shù)，并給出產(chǎn)生過(guò)程。(2).已知如圖所示的一個(gè)網(wǎng)，按照Kruskal方法，從頂點(diǎn)V1出發(fā)，求該網(wǎng)的最小生成樹(shù)，并給出產(chǎn)生過(guò)程。(3).下圖中給出了一個(gè)具有15個(gè)活動(dòng)，11個(gè)時(shí)間的工程的A0E網(wǎng)，求其關(guān)鍵路徑。四.編程題(1).編寫(xiě)一個(gè)算法，由依次輸入的頂點(diǎn)數(shù)目、弧的數(shù)目、各頂點(diǎn)的信息和各條弧的信息建立有向圖的鄰接表。第11章習(xí)題答案一.選擇題12345678910DACACBCDDB二.填空題1.n(n-1)/2；n(n-1)2.2；43.34.205.0,1,2,8,3,4,5,6,7,9；0,1,4,2,7,3,8,6,5,9三.簡(jiǎn)答題1.根據(jù)Prim算法生成該網(wǎng)圖最小生成樹(shù)的過(guò)程如下，其中圖(f)為生成的最小生成樹(shù)。 (a) (b) (c) (d) (e) (f)2.根據(jù)Krusral算法生成該網(wǎng)圖最小生成樹(shù)的過(guò)程如下,其中圖(f)為生成的最小生成樹(shù)。 (a) (b) (c) (d) (e) (f)3.