數(shù)據(jù)結(jié)構(gòu)大作業(yè)參考答案

數(shù)據(jù)結(jié)構(gòu)大作業(yè)只收手工紙面版，統(tǒng)一用學(xué)院的實驗稿紙。自留底稿，不退。十一、討論題：順序存儲和鏈表存儲的優(yōu)缺點對比分析。答：順序存儲的優(yōu)點是可以做到“隨機訪問”，缺點是動態(tài)操作時間效率低下；鏈表存儲的優(yōu)點是動態(tài)操作高效，不會引起數(shù)據(jù)的移動，缺點是只能進行“順序訪問”，不能進行“隨機訪問”。十二、討論題：循環(huán)隊列解決了什么問題？優(yōu)點是什么？如何巧妙地實現(xiàn)環(huán)狀？答：循環(huán)隊列解決了簡單的隊列的順序存儲的“假溢出”問題。它的優(yōu)點是：相對于一般的順序存儲隊列，它不用移動數(shù)據(jù)就解決了“假溢出”問題，這樣就提高了時間效率，此外，它通過求模運算可以成功求出入隊、出隊的地址，通過犧牲一個空間成功判斷了隊空和隊滿兩種情況。實現(xiàn)過程：通過求模運算求出入隊、出隊的地址：rear=(rear+1)%MaxSize；front=(front+1)%MaxSize（front為隊頭，rear為隊尾，MaxSize為循環(huán)隊列的長度）。犧牲一個空間區(qū)分了隊空和隊滿兩種情況：front=rear則隊空rear+1=front則隊滿。十三、討論題：一般而言，如何比較遞歸和非遞歸算法的優(yōu)缺點？答：遞歸在算法上比非遞歸更為簡單，且比非遞歸更為容易理解；而非遞歸算法也有它的好處，遞歸用到了棧，要重復(fù)調(diào)用自己，重復(fù)調(diào)用自己就意味著要循環(huán)，這樣，時間效率就低下，非遞歸算法與之相比，效率就比較高。十四、討論題：常規(guī)的排序算法的共同點是什么？答：常規(guī)的排序算法的共同點是：逐步縮小待排空間，每次增加一個已排空間。十五、討論題：字符串和線性表的關(guān)系是什么？字符串的操作主要體現(xiàn)在什么方面？答：字符串和線性表的關(guān)系是：字符串是一種特殊的線性表。字符串的操作主要體現(xiàn)在：一次性處理大量字符。十六、討論題：棧和隊列的工作原理以及各自的應(yīng)用范例？答：棧的工作原理：只允許在棧頂進行數(shù)據(jù)的插入、刪除操作，進棧、出棧也只能在棧頂進行，數(shù)據(jù)擁有“后進先出”的性質(zhì)。應(yīng)用范例：用于產(chǎn)生數(shù)據(jù)逆序，如象棋的悔棋功；也用于保護現(xiàn)場，如遞歸函數(shù)的實現(xiàn)。隊列的工作原理：在隊尾插入數(shù)據(jù)，在對頭刪除數(shù)據(jù)，數(shù)據(jù)從隊尾進隊，從隊投出隊，數(shù)據(jù)擁有“先進先出”的性質(zhì)。應(yīng)用范例：基于時間公平的機制所必需的數(shù)據(jù)結(jié)構(gòu)；是任何需要進行緩沖區(qū)處理的比較好的實現(xiàn)方案。十七、討論題：索引存儲的特點和優(yōu)點？答：索引存儲的特點：在原始數(shù)據(jù)外，增加一些所謂的管理家數(shù)據(jù)，合起來構(gòu)成一種存儲結(jié)構(gòu)，既保存了數(shù)據(jù)，又保存了關(guān)系。索引存儲的優(yōu)點：與鏈表相比，它可以做到數(shù)據(jù)的隨機訪問；與線性表相比，它在近行插、刪操作時不會引起大批數(shù)據(jù)的移動；此外，它還可以在一個字符串內(nèi)部進行插、刪操作。十八、討論題：諸如迷宮、八皇后、棋盤等課題使用什么數(shù)據(jù)結(jié)構(gòu)是比較好的選擇？為什么？答：諸如迷宮、八皇后、棋盤等課題使用二維數(shù)組比較好。因為迷宮、八皇后、棋盤等課題數(shù)據(jù)之間存在各個方向上的關(guān)系，二維數(shù)組可很好反映這些關(guān)系。此外，棋盤問題涉及到悔棋，故需用到棧；迷宮問題是一個試探和回溯的過程，也應(yīng)用到棧。十九、討論題：圖的鄰接表中，掛鏈的結(jié)點中為什么不能存放實際要處理的數(shù)據(jù)？答：圖的鄰接表中，掛鏈的結(jié)點中不能存放實際要處理的數(shù)據(jù)是因為：掛鏈的結(jié)點反映的是各結(jié)點之間的關(guān)系（可達或不可達），一般關(guān)系不變，它是不會改變的，但若存放實際要處理的數(shù)據(jù)，結(jié)點數(shù)據(jù)改變，即使關(guān)系不變，它也要改變。二十、討論題：哈希存儲法真的能做到O（1）級的查找算法嗎？為什么？你如何評價這樣的思路。答：哈希存儲法不能完全做到O（1）級的查找算法。哈希存儲法是利用函數(shù)計算出數(shù)據(jù)應(yīng)該存放的地址，存入數(shù)據(jù)，之后在需要查找數(shù)據(jù)的時候，還使用同樣的函數(shù)。表面上看，是O（1）級的查找算法，但是，由于無論哪一種函數(shù)，它在計算地址時，或多或少都會產(chǎn)生沖突，這就需要通過拉鏈法或建立一個公共溢出區(qū)來解決，而在查找的過程中，對于沖突的數(shù)據(jù)，就不能通過函數(shù)一次找到，而還要進行比較，這樣，算法就不為O（1）級的。雖然哈希存儲法不能完全做到O（1）級的查找算法，但由于所選函數(shù)往往能保證大部分數(shù)據(jù)不會發(fā)生沖突，沖突的只是少部分，最終的查找效率依然是很高的。單選題復(fù)習(xí)用1、數(shù)據(jù)結(jié)構(gòu)除了研究數(shù)據(jù)本身如何表示和存儲外，還需要重點研究數(shù)據(jù)___________D_____。(A)的數(shù)量(B)的質(zhì)量(C)的屬性(D)之間的關(guān)系2、以下哪種邏輯結(jié)構(gòu)重點表示數(shù)據(jù)之間的層次關(guān)系。B(A)線性結(jié)構(gòu)(B)樹形結(jié)構(gòu)(C)圖形結(jié)構(gòu)(D)集合結(jié)構(gòu)3、以下哪種存儲結(jié)構(gòu)主要是通過增加新的管理數(shù)據(jù)來同時保證讀取數(shù)據(jù)的高速和動態(tài)修改數(shù)據(jù)的高速。C(A)順序存儲(B)鏈接存儲(C)索引結(jié)構(gòu)(D)哈希存儲4、遍歷操作是對某個數(shù)據(jù)結(jié)構(gòu)中所有數(shù)據(jù)需要做到__A____的訪問。(A)至少一次且至多一次(B)可以多次(C)大部分一次，部分可以重復(fù)(D)二次5、下面哪一句話是正確的。C(A)算法就是可以運行的程序(B)算法是程序的總結(jié)，只能用中文表示(C)算法是表示一種解決問題的思路(D)算法最好用英語表示，這樣可以很快切換成程序。6、一個滿二叉樹共有三層，問有幾個結(jié)點？C(A)5(B)6(C)7(D)87、結(jié)點個數(shù)為4個的無向完全圖的邊數(shù)是多少條？B(A)5(B)6(C)7(D)88、實現(xiàn)函數(shù)調(diào)用返回點管理應(yīng)該用數(shù)據(jù)結(jié)構(gòu)__C_____。(A)二叉樹(B)圖(C)棧(D)隊列1、二分查找法適合__C____。(A)適合順序表和鏈表等結(jié)構(gòu)(B)數(shù)據(jù)不需要排序，但是必須順序存儲(C)僅僅把數(shù)據(jù)排序后的順序表(D)二叉樹和圖2、在字符串結(jié)構(gòu)中，哪一個是進行查找操作？D(A)求子串(B)串比較(C)串遍歷(D)子串定位3、在字符串的索引結(jié)構(gòu)中，哪一個操作沒有對原始數(shù)據(jù)區(qū)進行處理？A(A)插入字符(B)刪除字符串(C)刪除行(D)修改字符4、一個m*n的矩陣，用列優(yōu)先存儲，元素A(i，j)存儲在位置k上，在橫向關(guān)系上的直接前驅(qū)在一維數(shù)組中一般地址為（約定每一個元素僅僅占一個單元）：(A)k+1(B)k-1(C)k+m(D)k-m5、用建立大根堆來進行排序，最后的結(jié)果是什么？B(A)升序(B)降序(C)逆序(D)不一定6、圖結(jié)構(gòu)的遍歷操作中，一般采用什么機制可以最簡單地避免再次訪問已經(jīng)被訪問過的結(jié)點。C(A)計算是否有環(huán)路(B)計數(shù)器(C)標(biāo)志位(D)哈希函數(shù)7、如果一個程序在內(nèi)存中某批數(shù)據(jù)時進行插入和刪除操作非常頻繁，則建議使用哪種存儲結(jié)構(gòu)？C(A)順序(B)鏈接(C)索引(D)哈希8、下面哪個操作不是動態(tài)操作？D(A)修改(B)插入(C)刪除(D)查找9、如果一個算法的時間效率和數(shù)據(jù)量無關(guān)，用哪種符號表示？A(A)O(c)(B)O(1)(C)O(n)(D)O(x)10、遞歸的算法包括哪兩個環(huán)節(jié)C(A)前進和撤退(B)上升和下降(C)進入和回退(D)變大和變小11、二叉樹的一種遍歷名稱，其編程實現(xiàn)時一般需要隊列的幫助。D(A)先根遍歷(B)后根遍歷(C)深度遍歷(D)層次遍歷12、遞歸程序看似簡潔，但是其運行必須啟用下面的某種數(shù)據(jù)結(jié)構(gòu)來管理。B(A)字符串(B)棧(C)森林(D)最優(yōu)二叉樹13、在一個帶權(quán)連通圖G中，權(quán)值最小的邊一定包含在G的_____生成樹中。D(A)廣度優(yōu)先(B)深度優(yōu)先(C)最小(D)任何14、對稱矩陣如果只存儲下三角的數(shù)據(jù)時，可以減少存儲量：C(A)一半(B)多于一半(C)少于一半(D)大約2/315、稀疏矩陣m*n中有k個非零元素，用三元組存儲時，需要多少單元的存儲量？D(A)m*n*3(B)k+3(C)k*3(D)k*3+316、迷宮程序位置移動如果也考慮斜向45度關(guān)系，那么某一個位置可以移動走的坐標(biāo)(不考慮邊界等意外因素)有幾個？D(A)2(B)4(C)6(D)817、圖的鄰接表中存儲關(guān)系數(shù)據(jù)采用了什么存儲結(jié)構(gòu)？C(A)順序存儲結(jié)構(gòu)(B)鏈式存儲結(jié)構(gòu)(C)索引存儲結(jié)構(gòu)(D)散列存儲結(jié)構(gòu)18、三個數(shù)據(jù)(A,B,C)通過棧的處理(一次進棧和出棧)不能得到的一種出棧序列是:C(A)(A,B,C)(B)(A,C,B)(C)(C,A,B)(D)(C,B,A)1、計數(shù)器減一D(A)i++(B)i=k-1(C)i=count(i)-1(D)i=i-1；2、c語言程序開始運行的入口函數(shù)為D(A)intopen()(B)intstart()(C)intmian()(D)intmain()3、地址編號為10100的一個語句調(diào)用了一個函數(shù)，那么為了能正確的返回，必須啟用什么機制？C(A)在被調(diào)用函數(shù)最后一句寫上return(10101)(B)啟用一個標(biāo)志位，管理返回點(C)啟用一個棧，管理返回點(D)通知機房工作人員，請求幫助4、以下的語句是什么功能？p=p->next;A(A)指針p向其直接后繼移動(B)p的值減去next的值(C)指針p向其直接前驅(qū)移動(D)判斷p是否大于next的值5、c語言(不是c++)中申請一個新結(jié)點是什么語句？D(A)newnode=NEWnode；(B)newnode=NewOneNode;(C)newnode=malloc(Node)；(D)newnode=(Link*)malloc(sizeof(Node));6、c語言(不是c++)中輸出結(jié)點中的數(shù)據(jù)是什么語句？B(A)printdata；(B)printf("[%d,%d],Pointer->Number,Pointer->Total);(C)print(p->data);(D)cout(p->data);7、c語言(不是c++)中輸入數(shù)據(jù)是什么語句？C(A)inputdata；(B)cin(data):(C)scanf("%d",&data);(D)scanf("%d",data);8、順序棧進棧的主要動作為：B(A)先寫入數(shù)據(jù)，再移動top(B)直接填入數(shù)據(jù)到合法地址即可(C)先移動top，再寫入數(shù)據(jù)(D)把數(shù)據(jù)填入最邊界的單元中9、哪一個是合法的一維順序表地址計算公式？B(A)locAi=locA1+i(B)ai=loc(a0)+i*d(C)i=loc(A0)-d(D)Loc(Ai)=Loc(A1)-(i-1)*d10、環(huán)隊結(jié)構(gòu)出隊產(chǎn)生下一個合法地址的語句是：D(A)f=f+1(B)f=(f+1)%MaxSize(C)f=f+MaxSize(D)rear=(rear+1)%M1、Windows操作系統(tǒng)中在外存硬盤上的文件采用的哪種數(shù)據(jù)結(jié)構(gòu)的構(gòu)造思想？(A)線性鏈表(B)哈希表(C)十字鏈表(D)索引文件2、象棋程序中棋盤表示、悔棋功能、復(fù)盤功能對應(yīng)的三種底層數(shù)據(jù)結(jié)構(gòu)為：C(A)廣義表+樹+三元組(B)線性表+棧+字符串(C)二維數(shù)組+棧+隊列(D)圖+隊列+最優(yōu)二叉樹3、一個小型機的機房中，有10位老師在做科研，有30位博士和碩士在做設(shè)計，有300名學(xué)生在做實驗。請問對該小型機的CPU時間片管理應(yīng)該采用哪種策略是最佳方案？(A)啟用先到先服務(wù)的隊列機制(B)啟用能表示層次結(jié)構(gòu)的樹(C)啟用分塊的哈希表(D)啟用優(yōu)先級系數(shù)和隊列排隊結(jié)構(gòu)4、(c語言中)從鍵盤輸入一個數(shù)學(xué)表達式，現(xiàn)在要把該表達式進行存儲，此時如何定義這個結(jié)構(gòu)的數(shù)據(jù)類型？B(A)二叉樹(B)字符串(C)字符數(shù)組(D)整型5、AOV網(wǎng)需要產(chǎn)生拓撲排序，其數(shù)據(jù)結(jié)構(gòu)必須是？(A)無向圖(B)有向無環(huán)圖(C)森林(D)線性表6、如果要求編程計算多項式的和，存儲多項式的最佳存儲結(jié)構(gòu)是什么？A(A)鏈表(B)數(shù)組(C)哈希(D)集合7、如果一個無向圖，需要用相對節(jié)省空間的方式存儲其中的關(guān)系信息，那么建議采用什么方案？D(A)設(shè)法使該圖的邊非常少，從而可以啟用三元組(B)有邊的才用鏈表表示，臨時申請結(jié)點(C)繼續(xù)用二維數(shù)組存儲，但是遇到0的時候空置其存儲單元(D)先用二維數(shù)組表示然后改為只存儲下三角矩陣的數(shù)據(jù)結(jié)構(gòu)8、推箱子小游戲、迷宮等底層設(shè)計中布局應(yīng)該啟用什么數(shù)據(jù)結(jié)構(gòu)？C(A)圖(B)集合(C)二維數(shù)組(D)一維數(shù)組9、哪種高級語言的代碼構(gòu)造結(jié)構(gòu)是廣義表？(A)c++(B)Lisp(C)c(D)java10、為了表示軍隊、公司等層次化管理機制，應(yīng)該采用哪種數(shù)據(jù)結(jié)構(gòu)表示？C(A)圖(B)二叉樹(C)樹(D)字符串一、已知有4個元素為：12，33，40，51。用單鏈表（約定頭指針為head,新結(jié)點指針為new,搜索指針為p）從左到右依次存儲。分別畫出（1）進棧39（2）進隊39（3）有序表插入39等三種情況的工作示意圖。并標(biāo)注上改鏈的次序和主要的工作語句。（1）進棧39head12334051123340513939new主要的工作語:new->next=head->next;head->next=new;（2）進隊39head5140331251403312rear3939new主要的工作語:new->next=NULL;rear->next=new;rear=new;（3）有序表插入39headp51403312514033123939new主要的工作語:new->next=p->next;p->next=new;二、自己畫一個6*7的稀疏矩陣（比如：非0元只有4個）。畫出三元組表示法。并畫出對應(yīng)的轉(zhuǎn)置矩陣的三元組。6770421012182653445215536770111282514024345536250000200 10000000800005000040000000000010030稀疏矩陣三元組壓縮存儲轉(zhuǎn)置矩陣的三元組三、畫出表達式8-6*3/（2-1）的二叉樹表示。寫出四種遍歷的結(jié)果。畫出利用棧進行計算的完整過程。表達式8-6*3/（2-1）的二叉樹表示圖————/8/8——*——*13621362前根遍歷：-8/*63–21中根遍歷：8–6*3/2-1后根遍歷：863*21-/-利用棧進行計算的完整過程:操作數(shù)8，6，3依次進棧top863863操作數(shù)3，6出棧，計算6*3，結(jié)果進棧top818818操作數(shù)2,1依次進棧top8182181821操作數(shù)1，2出棧，計算2-1，結(jié)果進棧top81818181 計算結(jié)果1，18出棧，計算18/1，結(jié)果進棧top818818計算結(jié)果18，操作數(shù)8出棧，計算8-18結(jié)果進棧top-10-10-10出棧即為表達式的值。四、圖的存儲結(jié)構(gòu)。自己畫一個圖，至少五個結(jié)點，多條邊。畫出鄰接矩陣和鄰接表示意圖。DD1D2D4D2D4 001001 010001D5D3D5D3 000000D6 000010D6有向圖鄰接矩陣42D1D2D3D4D5D6142D1D2D3D4D5D663 26362

3625455565鄰接表示意圖五、樹、二叉樹、森林的互相轉(zhuǎn)換。自己畫一個有三層深度、樹的度為3的一棵樹，改劃成二叉樹。有三層深度、樹的度為3的一棵樹212142860428602424912912改鏈212142860428602424129129拉直212142860428601292412924旋轉(zhuǎn)形成二叉樹212160602482484242991212六、最優(yōu)二叉樹的建立。權(quán)值序列：25、12、27、6、1518181815 25271818181261263325 27 3315181518121126121126 523352332725181527251815612112612112272515272515612112612112生成的最優(yōu)二叉樹、七、二分查找法的示意圖。自己產(chǎn)生十個數(shù)據(jù)。畫出其中一個元素查找成功的過程。126181521282530369查找30。1261815212825303691