數(shù)據(jù)結(jié)構(gòu)考試問答題

1．我們知道計(jì)算機(jī)只能執(zhí)行機(jī)器指令，為什么它能運(yùn)行用匯編語(yǔ)言和高級(jí)語(yǔ)言編寫的程序？答：靠匯編程序?qū)R編語(yǔ)言或高級(jí)語(yǔ)言翻譯轉(zhuǎn)換為目標(biāo)程序〔即機(jī)器語(yǔ)言〕。2.【嚴(yán)題集1.2②】數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎？答：簡(jiǎn)單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。3.簡(jiǎn)述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。答：線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對(duì)多的。1.試比擬順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？答：①順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰〔邏輯與物理統(tǒng)一〕；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲(chǔ)密度大〔＝1？〕，存儲(chǔ)空間利用率高。缺點(diǎn)：插入或刪除元素時(shí)不方便。②鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩局部，一局部存放結(jié)點(diǎn)值，另一局部存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度小〔<1〕，存儲(chǔ)空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。假設(shè)線性表的長(zhǎng)度變化不大，且其主要操作是查找，那么采用順序表；假設(shè)線性表的長(zhǎng)度變化較大，且其主要操作是插入、刪除操作，那么采用鏈表。2.描述以下三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)〔第一個(gè)元素結(jié)點(diǎn)〕。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？答：首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理。頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)〔或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)〕的指針。假設(shè)鏈表中附設(shè)頭結(jié)點(diǎn)，那么不管線性表是否為空表，頭指針均不為空。否那么表示空表的鏈表的頭指針為空。這三個(gè)概念對(duì)單鏈表、雙向鏈表和循環(huán)鏈表均適用。是否設(shè)置頭結(jié)點(diǎn)，是不同的存儲(chǔ)結(jié)構(gòu)表示同一邏輯結(jié)構(gòu)的問題。頭結(jié)點(diǎn)headdatalink頭指針首元結(jié)點(diǎn)簡(jiǎn)而言之，頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)〔或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)〕的指針；頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息〔內(nèi)放頭指針？那還得另配一個(gè)頭指針?。?！〕首元素結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。、線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式?，F(xiàn)有一個(gè)具有五個(gè)元素的線性表L={23，17，47，05，31}，假設(shè)它以鏈接方式存儲(chǔ)在以下100～119號(hào)地址空間中，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)〔占2個(gè)字節(jié)〕和指針〔占2個(gè)字節(jié)〕組成，如下所示：05U17X23V31Y47Z^^100120其中指針X，Y，Z的值分別為多少？該線性表的首結(jié)點(diǎn)起始地址為多少？末結(jié)點(diǎn)的起始地址為多少？〔10分〕答：X=116Y=0Z=100首址=108末址=112

1.說明線性表、棧與隊(duì)的異同點(diǎn)。答：相同點(diǎn)：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表，只是對(duì)插入、刪除運(yùn)算加以限制。不同點(diǎn)：①運(yùn)算規(guī)那么不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入、刪除運(yùn)算，因而是后進(jìn)先出表LIFO；隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。②用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng)，隊(duì)列用于多道作業(yè)處理、指令存放及其他運(yùn)算等等。2.設(shè)有編號(hào)為1，2，3，4的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。答：至少有14種。①全進(jìn)之后再出情況，只有1種：4，3，2，1②進(jìn)3個(gè)之后再出的情況，有3種，3,4,2,13,2,4,13,2,1,4③進(jìn)2個(gè)之后再出的情況，有5種，2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4④進(jìn)1個(gè)之后再出的情況，有5種，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,33.假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’和‘a(chǎn)babab’那么不是回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請(qǐng)分析用線性表、堆棧和隊(duì)列等方式正確輸出其回文的可能性？答：線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)變量〔j--〕從表尾開始打印輸出；堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。哪種方式最好，要具體情況具體分析。假設(shè)正文在機(jī)內(nèi)已是順序存儲(chǔ)，那么直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用POP動(dòng)作實(shí)現(xiàn)?！驳褩Ｊ窍葴p后壓還是……〕假設(shè)正文是單鏈表形式存儲(chǔ)，那么等同于隊(duì)列，需開輔助空間，可以從鏈?zhǔn)组_始入棧，全部壓入后再依次輸出。4.順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿？答：一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。采用循環(huán)隊(duì)列是解決假溢出的途徑。另外，解決隊(duì)滿隊(duì)空的方法有三：設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空；浪費(fèi)一個(gè)元素的空間，用于區(qū)別隊(duì)滿還是隊(duì)空。使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)〔即隊(duì)列長(zhǎng)度〕。我們常采用法②，即隊(duì)頭指針、隊(duì)尾指針中有一個(gè)指向?qū)嵲?，而另一個(gè)指向空閑元素。判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是：f=rear隊(duì)滿標(biāo)志是：f=(r+1)%N5.設(shè)循環(huán)隊(duì)列的容量為40〔序號(hào)從0到39〕，現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)運(yùn)算后，有①front=11，rear=19;②front=19，rear=11；問在這兩種情況下，循環(huán)隊(duì)列中各有元素多少個(gè)？答：用隊(duì)列長(zhǎng)度計(jì)算公式：(N＋r－f)%N①L=〔40＋19－11〕%40=8②L=〔40＋11－19〕%40=32一棵度為2的樹與一棵二叉樹有何區(qū)別？答：度為2的樹從形式上看與二叉樹很相似，但它的子樹是無序的，而二叉樹是有序的。即，在一般樹中假設(shè)某結(jié)點(diǎn)只有一個(gè)孩子，就無需區(qū)分其左右次序，而在二叉樹中即使是一個(gè)孩子也有左右之分。C的結(jié)點(diǎn)類型定義如下：structnodeC的結(jié)點(diǎn)類型定義如下：structnode{chardata;structnode*lchild,rchild;};C算法如下：voidtraversal(structnode*root){if(root){printf(“%c”,root->data);traversal(root->lchild);printf(“%c”,root->data);traversal(root->rchild);}}對(duì)以下二叉樹B，執(zhí)行以下算法traversal(root)，試指出其輸出結(jié)果；假定二叉樹B共有n個(gè)結(jié)點(diǎn)，試分析算法traversal(root)的時(shí)間復(fù)雜度?！补?分〕AABDCFGE二叉樹B解：這是“先根再左再根再右”，比前序遍歷多打印各結(jié)點(diǎn)一次，輸出結(jié)果為：ABCCEEBADFFDGG特點(diǎn)：①每個(gè)結(jié)點(diǎn)肯定都會(huì)被打印兩次；②但出現(xiàn)的順序不同，其規(guī)律是：但凡有左子樹的結(jié)點(diǎn)，必間隔左子樹的全部結(jié)點(diǎn)后再重復(fù)出現(xiàn)；如A，B，D等結(jié)點(diǎn)。反之馬上就會(huì)重復(fù)出現(xiàn)。如C，E，F(xiàn)，G等結(jié)點(diǎn)。時(shí)間復(fù)雜度以訪問結(jié)點(diǎn)的次數(shù)為主，精確值為2*n，時(shí)間漸近度為O(n).3.給定二叉樹的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I；中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫出二叉樹B，并簡(jiǎn)述由任意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹B的思想方法。解：方法是：由前序先確定root，由中序可確定root的左、右子樹。然后由其左子樹的元素集合和右子樹的集合對(duì)應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，那么所有元素都將被唯一確定，問題得解。D ACFEGBHI283328334060085455解：要遵循中序遍歷的軌跡來畫出每個(gè)前驅(qū)和后繼。中序遍歷序列：554025602808335428282540555560330854NILNILNILNIL334060085455五、閱讀分析題〔〕1.試寫出如下圖的二叉樹分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。答：DLR：ABDFJGKCEHILM LDR:BFJDGKACHELIM LRD：JFKGDBHLMIECA2.〔P604-27〕把如下圖的樹轉(zhuǎn)化成二叉樹。答：注意全部兄弟之間都要連線〔包括度為2的兄弟〕,并注意原有連線結(jié)點(diǎn)一律歸入左子樹，新添連線結(jié)點(diǎn)一律歸入右子樹。ABECKFHDLGIMJ答：這是找結(jié)點(diǎn)后繼的程序。共有3處錯(cuò)誤。注：當(dāng)答：這是找結(jié)點(diǎn)后繼的程序。共有3處錯(cuò)誤。注：當(dāng)rtag＝1時(shí)說明內(nèi)裝后繼指針，可直接返回，第一句無錯(cuò)。當(dāng)rtag＝0時(shí)說明內(nèi)裝右孩子指針，但孩子未必是后繼，需要計(jì)算。中序遍歷應(yīng)領(lǐng)先左再根再右，所以應(yīng)當(dāng)找左子樹直到葉子處。r=r->lchild;直到LTag=1；應(yīng)改為：while(!r->Ltag)r=r->Lchild;BiTreeInSucc(BiTreeq){//q是指向中序線索二叉樹上某個(gè)結(jié)點(diǎn)的指針，//本函數(shù)返回指向*q的后繼的指針。r=q->rchild;//應(yīng)改為r=q；if(!r->rtag)while(!r->rtag)r=r->rchild;//應(yīng)改為while(!r->Ltag)r=r->Lchild;returnr;//應(yīng)改為returnr->rchild；}//ISucc4.畫出和以下二叉樹相應(yīng)的森林。答：注意根右邊的子樹肯定是森林，而孩子結(jié)點(diǎn)的右子樹均為兄弟。1.如下圖的有向圖，請(qǐng)給出該圖的:頂點(diǎn)12頂點(diǎn)123456入度出度鄰接矩陣；鄰接表；逆鄰接表。答案：

2.請(qǐng)對(duì)以下圖的無向帶權(quán)圖：寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹；寫出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹。解：設(shè)起點(diǎn)為a?？梢灾苯佑稍紙D畫出最小生成樹，而且最小生成樹只有一種〔類〕!鄰接矩陣為：最小生成樹最小生成樹→PRIM算法〔橫向變化〕：VbcdefghUV-UVexlowcosta4a3a∞a∞a∞a∞a∞{a}{b,c,d,e,f,g,h}Vexlowcosta40c5a∞a∞a∞c5{a,c}{b,d,e,f,g,h}Vexlowcost00c5b9a∞a∞c5{a,c,b}{d,e,f,g,h}Vexlowcost000d7d6d5d4{a,c,b,d}{e,f,g,h}Vexlowcost000d7d6d50{a,c,b,d,h}{e,f,g}Vexlowcost000d7g200{a,c,b,d,h,g}{f,e}Vexlowcost000f3000{a,c,b,d,h,g,f}{e}Vexlowcost0000000{a,c,b,d,h,g,f,e}{}鄰接表為：a→b4→c3b→a4→c5→d5→e9^c→a3→b5→d5→h5^d→b5→c5→e7→f6→g5→h4^e→b9→d7→f3^f→d6→e3→g2^g→d5→f2→h6^h→c5→d4→g6^克魯斯卡爾算法步驟克魯斯卡爾算法步驟(按邊歸并,堆排序)：先羅列：f---2---ga—3--cf—3—ea—4---bd—4—h(a,b,c)(e,f,g)(d,h)取b—5—d,g—5--d就把三個(gè)連通分量連接起來了。3.二維數(shù)組表示的圖的鄰接矩陣如以下圖所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。4.試?yán)肈ijkstra算法求圖中從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)。解：最短路徑為：〔a,c,f,e,d,g,b〕1.對(duì)分〔折半〕查找適不適合鏈表結(jié)構(gòu)的序列，為什么？用二分查找的查找速度必然比線性查找的速度快，這種說法對(duì)嗎？答：不適合！雖然有序的單鏈表的結(jié)點(diǎn)是按從小到大〔或從大到小〕順序排列，但因其存儲(chǔ)結(jié)構(gòu)為單鏈表，查找結(jié)點(diǎn)時(shí)只能從頭指針開始逐步搜索，故不能進(jìn)行折半查找。二分查找的速度在一般情況下是快些，但在特殊情況下未必快。例如所查數(shù)據(jù)位于首位時(shí)，那么線性查找快；而二分查找那么慢得多。2.假定對(duì)有序表：〔3，4，5，7，24，30，42，54，63，72，87，95〕進(jìn)行折半查找，試答復(fù)以下問題：畫出描述折半查找過程的判定樹；假設(shè)查找元素54，需依次與哪些元素比擬？假設(shè)查找元素90，需依次與哪些元素比擬？假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。解：先畫出判定樹如下〔注：mid=(1+12)/2=6〕：30563374287424547295(2)查找元素54，需依次與30,63,42,54等元素比擬；(3)查找元素90，需依次與30,63,87,95,72等元素比擬；〔4〕求ASL之前，需要統(tǒng)計(jì)每個(gè)元素的查找次數(shù)。判定樹的前3層共查找1＋2×2＋4×3=17次；但最后一層未滿，不能用8×4，只能用5×4=20次，所以ASL＝1/12〔17＋20〕＝37/12≈3.083.用比擬兩個(gè)元素大小的方法在一個(gè)給定的序列中查找某個(gè)元素的時(shí)間復(fù)雜度下限是什么?如果要求時(shí)間復(fù)雜度更小,你采用什么方法？此方法的時(shí)間復(fù)雜度是多少?答：查找某個(gè)元素的時(shí)間復(fù)雜度下限，如果理解為最短查找時(shí)間，那么當(dāng)關(guān)鍵字值與表頭元素相同時(shí)，比擬1次即可。要想降低時(shí)間復(fù)雜度，可以改用Hash查找法。此方法對(duì)表內(nèi)每個(gè)元素的比擬次數(shù)都是O〔1〕。4.設(shè)哈希〔Hash〕表的地址范圍為0～17，哈希函數(shù)為：H〔K〕＝KMOD16。K為關(guān)鍵字，用線性探測(cè)法再散列法處理沖突，輸入關(guān)鍵字序列：〔10，24，32，17，31，30，46，47，40，63，49〕造出Hash表，試答復(fù)以下問題：畫出哈希表的示意圖；假設(shè)查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進(jìn)行比擬？假設(shè)查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比擬？假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。解：〔1〕畫表如下：012345678910111213141516173217634924401030314647〔2〕查找63,首先要與H(63)=63%16=15號(hào)單元內(nèi)容比擬，即63vs31,no;然后順移，與46,47,32,17,63相比，一共比擬了6次！〔3〕查找60,首先要與H(60)=60%16=12號(hào)單元內(nèi)容比擬，但因?yàn)?2號(hào)單元為空〔應(yīng)當(dāng)有空標(biāo)記〕，所以應(yīng)當(dāng)只比擬這一次即可?！?〕對(duì)于黑色數(shù)據(jù)元素，各比擬1次；共6次；對(duì)紅色元素那么各不相同，要統(tǒng)計(jì)移位的位數(shù)?！?3”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11〔6＋2＋3×3〕＝17/11=1.5454545454≈1.5510-3在起泡排序過程中，什么情況下關(guān)鍵碼會(huì)朝向與排序相反的方向移動(dòng)，試舉例說明。在快速排序過程中有這種現(xiàn)象嗎？【解答】 如果在待排序序列的后面的假設(shè)干關(guān)鍵碼比前面的關(guān)鍵碼小，那么在起泡排序的過程中，關(guān)鍵碼可能向與最終它應(yīng)移向的位置相反的方向移動(dòng)。例如，574038111334487561997如9向相反方向移動(dòng) 657403811133448757199如19向相反方向移動(dòng) 675740381113344875919 如9向最終方向移動(dòng) 679 574038111334487519 如13向相反方向移動(dòng) 679115740381319344875如13向最終方向移動(dòng) 679111357403819344875如34向相反方向移動(dòng) 679111319574038344875 679111319345740384875 6791113193410-4試修改起泡排序算法，在正反兩個(gè)方向交替進(jìn)行掃描，即第一趟把關(guān)鍵碼最大的對(duì)象放到序列的最后，第二趟把關(guān)鍵碼最小的對(duì)象放到序列的最前面。如此反復(fù)進(jìn)行?！窘獯稹?template<classType>voiddataList<Type>::shake_Sort(){ //奇數(shù)趟對(duì)表Vector從前向后,比擬相鄰的關(guān)鍵碼,遇到逆序即交換,直到把參加比擬關(guān)鍵碼序列//中最大的關(guān)鍵碼移到序列尾部。偶數(shù)趟從后向前,比擬相鄰的關(guān)鍵碼,遇到逆序即交換,直到把//參加比擬關(guān)鍵碼序列中最小的關(guān)鍵碼移到序列前端。 inti=1,j;intexchange; while(i<CurrentSize){ //起泡排序趟數(shù)不超過n-1 exchange=0; //假定元素未交換 for(j=CurrentSize-i;j>=i;j--) //逆向起泡 if(Vector[j-1]>Vector[j]){ //發(fā)生逆序 Swap(Vector[j-1],Vector[j]); //交換,最小關(guān)鍵碼放在Vector[i-1]處exchange=1; //做“發(fā)生了交換”標(biāo)志 } if(exchange==0)break; ////當(dāng)exchange為0那么停止排序 for(j=i;j<=CurrentSize-i-1;j++) //正向起泡 if(Vector[j]>Vector[j+1]){ //發(fā)生逆序 Swap(Vector[j],Vector[j+1]); //交換,最大關(guān)鍵碼放在Vector[n-i]處exchange=