【正文】 域?！　　hile (pnext) p=pnext。5. 在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么?6. 假定有四個元素A, B, C, D依次進棧，進棧過程中允許出棧，試寫出所有可能的出棧序列。11. 在單鏈表中設(shè)置頭結(jié)點的作用是________。4. 要從一個順序表刪除一個元素時，被刪除元素之后的所有元素均需_______一個位置，移動過程是從_______向_______依次移動每一個元素。 D．snext=hs。 A．O(1) B．O(n) C．O(n2) D．O(log2n)15. 設(shè)有一個棧，元素的進棧次序為A, B, C, D, E,下列是不可能的出棧序列__________。B．線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的。 D．pnext=p。D． sprior=p。B． sprior=p。A．一個有限序列，可以為空 B．一個有限序列，不可以為空C．一個無限序列，可以為空 D．一個無限序列，不可以為空2. 在一個長度為n的順序表中刪除第i個元素(0=i=n)時，需向前移動 個元素。while((i=0)amp。for(i=0。j++)x++。12. 衡量算法正確性的標(biāo)準(zhǔn)通常是____________________________________。in。j++)A[i][j]=0。5. 在樹型結(jié)構(gòu)中，樹根結(jié)點沒有__________________結(jié)點，其余每個結(jié)點的有且只有__________________個前趨驅(qū)結(jié)點；葉子結(jié)點沒有__________________結(jié)點；其余每個結(jié)點的后續(xù)結(jié)點可以__________________。（1） （2） ，可移植性和可擴充性 ，確定性和有窮性，有窮性和穩(wěn)定性 ，穩(wěn)定性和安全性7. 數(shù)據(jù)在計算機內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲方式，在存儲空間使用的靈活性上，鏈?zhǔn)酱鎯Ρ软樞虼鎯σ? ）。 4. 設(shè)語句x++的時間是單位時間，則以下語句的時間復(fù)雜度為（ ）。n){if(T){if((!(Tlchild)amp。j++) Lelem[j]=Lelem[j+1]。7分（1）4分A B 1 C 3 2 5 D 4 E F（2）4分(1) 3分 E F A B C D （2）WPL=*3+*3+*2+*3+*3+03*21= (1分)（3）A：010 B：011 C：110 D：111 E：00 F；10 （3分）1AB：（A、B） 1分AC：（A、D、C） 2分AD：（A、D） 1分 AE：（A、D、E） 2分 三，設(shè)計題（20分）(10分)Status ListDelete(Sqlist amp。 }BinNode, *BinTree。其算法函數(shù)頭部如下： Status ListDelete(Sqlist amp。（2） 計算帶權(quán)路徑長度WPL。（3） 畫出對(2)中的遍歷序列進行折半查找過程的判定樹。2． 棧和隊列都是一種 的線性表，棧的插入和刪除只能在 進行。 （B）、p=next。貴州大學(xué)理學(xué)院數(shù)學(xué)系信息與計算科學(xué)專業(yè)《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案(20032004學(xué)年第2學(xué)期)一、 單項選擇題1．對于一個算法，當(dāng)輸入非法數(shù)據(jù)時，也要能作出相應(yīng)的處理，這種要求稱為（ ）。 pnext= next。 （A）、lchild （B）、data （C）、rchild （D）、root二、填空題1． 邏輯結(jié)構(gòu)決定了算法的 ，而存儲結(jié)構(gòu)決定了算法的 。2． 給定表（19,14,22,15,20,21,56,10）.（8分）（1） 按元素在表中的次序，建立一棵二叉排序樹（2） 對(1)中所建立的二叉排序樹進行中序遍歷，寫出遍歷序列。（1） 畫出對應(yīng)的Huffman樹。并求出其算法的平均時間復(fù)雜度。 struct node *lchild, *rchild。5． n(n1)/n16． ADCBFEG、ABCDEFFG7． ABC、ABC二、 應(yīng)用題1 （1）Hash表（4分）地址0123456789101112關(guān)鍵安132164572282412探測次數(shù)171231311（2）查找成功的平均查找長度：（1分） （5*1+1*2+2*3+1*7）/9=20/9查找不成功的平均查找長度：（1分） （2+1+9+8+7+6+5+4+3+2+1）/13=2（1）、構(gòu)造（3分） 19 14 22 10 15 20 56 21(2)、10 14 15 19 20 21 22 56（2分）（3）、（3分）(5分，)ijv1352463374134215218558 初始關(guān)鍵字： [18] 12 25 53 18 第 一 趟：[12 18] 25 53 18第 二 趟：[12 18 25] 53 18第 三 趟：[12 18 25 53] 18第 四 趟：[12 18 18 25 53] （4分） O（n2）（1分）。jLlengthi1。}（10分）voidCountLeaves(BinTree T,int amp。 3. 樹形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（ ）。（1） （2） 6. 計算機算法指的是（1），它具備輸入，輸出和（2）等五個特性。4. 一個算法的效率可分為__________________效率和__________________效率。jn。for(i=0。while(i=n)i=i*3。j=n。3. int i,j,k。k++) c[i][j]=a[i][k]*b[k][j]}4. i=n1。13. 事后統(tǒng)計，事前估計三、算法設(shè)計題 1. O( ) 2. O( ) 3. O(n ) 4. O(n) 5. O(n) 習(xí)題2一、單項選擇題1. 線性表是________。 snext=pnext。 snext=pnext。C．p=pnextnext。 A．線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。 A．插入 B．刪除 C．根據(jù)序號查找 D．根據(jù)元素值查找14. 在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并保持該表有序的時間復(fù)雜度是_______。hsnext=s。3. 順序表中邏輯上相鄰的元素的物理位置________。10. 根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每個結(jié)點所含指針的個數(shù)，鏈表可分為_________和_______；而根據(jù)指針的聯(lián)接方式，鏈表又可分為________和_________。2. 線性表的兩種存儲結(jié)構(gòu)各有哪些優(yōu)缺點？3. 對于線性表的兩種存儲結(jié)構(gòu)，如果有n個線性表同時并存，而且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自動改變，在此情況下，應(yīng)選用哪一種存儲結(jié)構(gòu)？為什么？4. 對于線性表的兩種存儲結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲結(jié)構(gòu)？試說明理由。 p=L。4. 假設(shè)有一個帶表頭結(jié)點的鏈表，表頭指針為head，每個結(jié)點含三個域：data, next和prior。8. 設(shè)順序表L是一個遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。5．設(shè)尾指針比設(shè)頭指針好。每當(dāng)有一個新元素入隊，就將隊列中已有的元素向隊頭移動一個位置，假定空余空間足夠。 if(i0) printf(Can39。amp。 } }}2．由于在單鏈表中只給出一個頭指針，所以只能用遍歷的方法來數(shù)單鏈表中的結(jié)點個數(shù)了。逆置時需將每一個結(jié)點的指針域作以修改，使其原前趨結(jié)點成為后繼。 qnext=s。 //p指向待插入的結(jié)點，初始時指向第一個結(jié)點 while(p!=NULL) { s=head。 //結(jié)點p插入到結(jié)點s和結(jié)點q之間 p=pnext。}while((p!=NULL) amp。 p=pnext。 //鏈接成循環(huán)鏈表}else //否則在隊尾插入p結(jié)點 { pnext=rearnext。if ( (*L).len= maxlen){ printf(“overflow)。 (*L).len++。 7. 若REPLACE（S，S1，S2）表示用字符串S2替換字符串S中的子串S1的操作，則對于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ ）。三、算法設(shè)計題1. 設(shè)有一個長度為s的字符串，其字符順序存放在一個一維數(shù)組的第1至第s個單元中（每個單元存放一個字符）。i++)r[s+i]=r[i]。{ LinkString *ps, *pt。s=ps。 B.(( )) D.(a)7. 廣義表A=((x,(a,B)),(x,(a,B),y))，則運算head(head(tail(A)))的結(jié)果為（ ）。 15. 一個廣義表的表尾總是一個（ ）。7. 設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式以行序為主序存儲，a 為第一個元素，其存儲地址為0，每個元素占有1個存儲地址空間，則a 的地址為______________。（ ）5. 采用壓縮存儲之后，下三角矩陣的存儲空間可以節(jié)約一半。（ ）13. 廣義表不能遞歸定義。A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i1]6. 由權(quán)值分別為3,8,6,2,5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ）。A. 不發(fā)生改變 B. 發(fā)生改變C. 不能確定 D. 以上都不對14. 已知一棵完全二叉樹的結(jié)點總數(shù)為9個，則最后一層的結(jié)點數(shù)為（ ）。 （?。?. 根據(jù)任意一種遍歷序列即可唯一確定對應(yīng)的二叉樹。5. 在一棵二叉排序樹上按_______遍歷得到的結(jié)點序列是一個有序序列。13. 對于一棵具有n個結(jié)點的二叉樹，采用二叉鏈表存儲時，鏈表中指針域的總數(shù)為_________個，其中___________個用于鏈接孩子結(jié)點，_____________個空閑著。四、應(yīng)用題1. 已知一棵樹邊的集合為{i，m，i，n，e，i，b，e，b，d，a，b，g，j，g，k，c，g，c，f，h，l，c，h，a，c}，請畫出這棵樹，并回答下列問題：（1）哪個是根結(jié)點？（2）哪些是葉子結(jié)點？（3）哪個是結(jié)點g的雙親？（4）哪些是結(jié)點g的祖先？（5）哪些是結(jié)點g的孩子？（6）哪些是結(jié)點e的孩子？（7）哪些是結(jié)點e的兄弟？哪些是結(jié)點f的兄弟？（8）結(jié)點b和n的層次號分別是什么？（9）樹的深度是多少？（10）以結(jié)點c為根的子樹深度是多少？2. 一棵度為2的樹與一棵二叉樹有何區(qū)別。3. 寫出在中序線索二叉樹中結(jié)點P的右子樹中插入一個結(jié)點s的算法。（3）編號為n的結(jié)點的第i個孩子結(jié)點如果存在，編號是(n1)*m+i+1。 單選題（每題 2 分，共20分）1. 1. D. HL=p。 若需要利用形參直接訪問實參時，應(yīng)將形參變量說明為（ ）參數(shù)。2. 2.3. 3.4. 4