數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題和部分答案

1、頁眉內(nèi)容全國2012年1月數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單項選擇題（本大題共15小題，每小題2分，共30分）1 .結(jié)點按邏輯關(guān)系依次排列形成一條鎖鏈”的數(shù)據(jù)結(jié)構(gòu)是（）A.集合B.線性Z構(gòu)C.樹形Z構(gòu)D.圖狀結(jié)構(gòu)2 .下面算法程序段的時間復(fù)雜度為（）for（inti=0;i<m;i+）for（intj=0;j<n;j+）aijl=i*j；A.O（m2）B.O（n2）C.O（mn）D.O（m+n）3 .線性結(jié)構(gòu)是（）A.具有n（n>0個表元素的有窮序列B.具有n（n>0個字符的有窮序列C.具有n（n>Q個結(jié)點的有窮序列D.具有n（n>0個數(shù)據(jù)項的有窮序

2、列4 .單鏈表中刪除由某個指針變量指向的結(jié)點的直接后繼，該算法的時間復(fù)雜度是（）A.O（1）B.0（n）C.O（log2n）D.O（n）5 .關(guān)于串的敘述，正確的是（）A.串是含有一個或多個字符的有窮序列B.空串是只含有空格字符的串C.空串是含有零個字符或含有空格字符的串D.串是含有零個或多個字符的有窮序列6 .棧的輸入序列依次為1,2,3,4,則不可能的出棧序列是（）A.1243B.1432C.2134D.43127 .隊列是（）A.先進(jìn)先出的線性表B.先進(jìn)后出的線性表C.后進(jìn)先出的線性表D.隨意進(jìn)出的線性表8 .10階上三角矩陣壓縮存儲時需存儲的元素個數(shù)為（）A.11B.56C.100D.

3、1019 .深度為k（k>l）的二叉樹，結(jié)點數(shù)最多有（）A.2k個B.（2k-1）個C.2k-1個D.（2k+1）個10 .具有12個結(jié)點的二叉樹的二叉鏈表存儲結(jié)構(gòu)中，空鏈域NULL的個數(shù)為（）A.11B.13C.23D.2511.具有n個頂點的無向圖的邊數(shù)最多為（)A.n+1 B.n(n+1) C.n(n-1)/2 D.2n(n+1)301012.三個頂點V1,V2,V3的圖的鄰接矩陣為)A. 0B. 1 C. 2 D. 3001,該圖中頂點V3的入度為（01013 .順序存儲的表格中有60000個元素，已按關(guān)鍵字值升序排列，假定對每個元素進(jìn)行查找的概率是相同的，且每個元素的關(guān)鍵字值不

4、相同。用順序查找法查找時，平均比較次數(shù)約為（）A.20000B.30000C.40000D.6000014 .外存儲器的主要特點是（）A.容量小和存取速度低B.容量大和存取速度低C.容量大和存取速度高D.容量小和存取速度高15 .在待排數(shù)據(jù)基本有序的前提下，效率最高的排序算法是（）A.直接插入排序B.直接選擇排序C.快速排序D.歸并排序二、填空題（本大題共13小題，每小題2分，共26分）16 .數(shù)據(jù)的不可分割的最小標(biāo)識單位是,它通常不具有完整確定的實際意義，或不被當(dāng)作一個整體對待。17 .運算分為加工型運算和引用型運算，讀取操作是運算。18 .帶有頭結(jié)點的單向循環(huán)鏈表L（L為頭指針）中，指針p

5、所指結(jié)點為尾結(jié)點的條件是。19.在雙鏈表中，前趨指針和后繼指針分別為prior和next。若使指針p往后移動兩個結(jié)點，則需執(zhí)行語句。20 .元素S1,S2,S3,S4,S5,S6依次進(jìn)入順序棧S,如果6個元素的退棧順序為S2,S3,S4,S6,S5,S1,則順序棧的容量至少為。21 .稀疏矩陣一般采用的壓縮存儲方法是。22 .在一棵機中，結(jié)點沒有雙親。23 .一棵具有n個結(jié)點的完全二叉樹中，從樹根起，自上而下、自左至右給所有結(jié)點編號。設(shè)根結(jié)點編號為1,若編號為i的結(jié)點有父結(jié)點，那么其父結(jié)點的編號為。24 .二叉樹的二叉鏈表存儲結(jié)構(gòu)中判斷指針p所指結(jié)點為葉子結(jié)點的條件是。25 .邊稀疏的無向圖采

6、用存儲較省空間。26 .除第一個頂點和最后一個頂點相同外，其余頂點不重復(fù)的回路，稱為。27 .二分查找算法的時間復(fù)雜度是。28 .要將序列51,18,23,68,94,70,73建成堆，則只需把18與相互交換。三、應(yīng)用題（本大題共5小題，每小題6分，共30分）29 .將題29圖所示的一棵二叉樹轉(zhuǎn)換成對應(yīng)的森林。題29圖題31圖題32圖30 .給定權(quán)值3,9,13,5,7,構(gòu)造相應(yīng)的哈夫曼（Huffman）樹，并計算其帶權(quán)路徑長度。31 .寫出題31圖的鄰接矩陣和每個頂點的入度與出度。32 .二叉排序樹的各結(jié)點的值依次為2028,請在題32圖中標(biāo)出各結(jié)點的值。33 .用冒泡排序法對數(shù)據(jù)序列（55

7、,38,65,97,76,138,27,49）進(jìn)行排序，寫出排序過程中的各趟結(jié)果。四、算法設(shè)計題（本大題共2小題，每小題7分，共14分）34 .設(shè)線性表A=（a1，32,am）,B=（b1，b2,，劫，試寫一個按下列規(guī)則合并A,B為線性表C的算法，使得C=（a1，b1,，abm,bm+1,b）當(dāng)m<n時；或者C=（a1,b，na,bn,an+1,，am）當(dāng)m>n時。線性表A,B和C均以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。（注意：單鏈表的長度值m和n均未顯式存儲。）35 .二叉樹的二叉鏈表類型定義如下：typedefStructbtnodedataty

8、pedata;Structbtnode*lchild,*rchild;bitreptr;寫出后根遍歷根指針為t的二叉樹的遞歸算法（voidpoStorder（bitreptr*t）。全國2011年10月數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程彳弋碼:02142一、單項選擇題(本大題共15小題，每小題2分，共30分)1 .設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5和e6依次通過棧S,元素退棧后即進(jìn)入隊列Q,若6個元素的出隊序列是e2,e4,e3,e6,e5,e1,則棧S的容量至少為()A.2B.3C.4D.62 .設(shè)計一個判別表達(dá)式中左右括號是否配對出現(xiàn)的算法，采用的最佳數(shù)據(jù)結(jié)構(gòu)為()A.線性表

9、的順序存儲結(jié)構(gòu)B.隊列C.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)D.棧3 .下列程序段的時間復(fù)雜度為()i=0;s=0;while(s<n)i+;s=s+i;A.O(而)B.O(log2n)C.O(n)D.O(n2)4 .設(shè)A是nxn的對稱矩陣，將A的對角線及對角線上方的元素Aj(1wi,jwn,iwj)以列優(yōu)先順序存放在一維數(shù)組元素B1至Bn(n+1)/2中，則元素Aj(iwj)在B中的位置為()A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-15 .在有向圖G的拓?fù)湫蛄兄?，若頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)的是()A.G中有弧<V

10、i,Vj>B.G中有一條從Vi到Vj的路徑C.G中沒有弧<Vi,Vj>D.G中有一條從Vj到Vi的路徑6 .下列序列中，由第一趟快速排序可得到的序列(排序的關(guān)鍵字類型是字符串)是()A.da,ax,eb,de,bbffha,gcB.cd,eb,ax,daffha,gc,bbC.gc,ax,eb,cd,bbffda,haD.ax,bb,cd,daffeb,gc,ha7 .不穩(wěn)定的排序方法是()A.直接插入排序B.冒泡排序C.堆排序D.二路歸并排序8 .設(shè)散列表表長m=14,散列函數(shù)為h(k)=k%11,表中已有4個記錄，如果用二次探測法處理沖突，關(guān)鍵字為49的記錄的存儲位置是(

11、)012345678910111211538618439 .若元素1,2,3依次進(jìn)棧，則退棧不可能出現(xiàn)的次序是()A.3,2,1B.2,1,3C.3,1,2D.1,3,210 .直接插入排序的時間復(fù)雜度是()A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)11 .稀疏矩B是指()A.元素少的矩陣B.有少量零元素的矩陣C.有少量非零元素的矩陣D.行數(shù)、列數(shù)很少的矩陣12 .深度為k(k>1)的二叉樹，結(jié)點數(shù)最多有()A.2kB.2k-1C.2k-1D.2k-1-113 .由帶權(quán)為9,2,5,7的四個葉子結(jié)點構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為()14 .有n個頂點的有

12、向完全圖的弧數(shù)為()A.n2B.2nC.n(n-1)D.2n(n+1)15.圖的深度優(yōu)先搜索類似于二叉樹的(20.隊列又稱為的線性表。21.順序棧被定義為結(jié)構(gòu)類型，含有兩個域:data和top,則對棧*sq進(jìn)行初始化的操作是22 .對于任何一棵二叉樹 T,如果其終端結(jié)點數(shù)為n0,度為2的結(jié)點數(shù)為n2,則n2=23 .一棵具有n個結(jié)點的二叉樹，采用二叉鏈表存儲，則二叉鏈表中指向孩子結(jié)點的指針有個。24 .若連通圖G的頂點個數(shù)為n,則圖G的生成樹的邊數(shù)為25 .一個具有n個頂點的無向圖的邊數(shù)最多為26 .中根遍歷二叉排序樹所得到的結(jié)點訪問序列是鍵值的序列。27 .冒泡排序的平均時間復(fù)雜度為28 .

13、將序列60, 20, 23, 68, 94, 70, 73建成堆，則只需把三、應(yīng)用題(本大題共5小題，每小題6分，共30分)20與互相交換。29 .如題29圖所示，在棧的輸入端元素的輸入順序為A, B以A開頭和以B開頭的所有輸出序列。C, D,進(jìn)棧過程中可以退棧，寫出在棧的輸出端ab( n題30圖題31圖輸入期題29圖題32圖30.一棵二叉樹如題30圖所示,寫出該二叉樹的先根遍歷序列、中根遍歷序列和后根遍歷序列。31 .將題31圖所示的一棵二叉樹轉(zhuǎn)換成森林。32 .對于有向無環(huán)圖:(1)敘述求拓?fù)渑判蛩惴ǖ幕静襟E;(2)對于題32圖，寫出它的4個不同的拓?fù)渑判蛐蛄小?3 .判別以下序列是否為

14、堆。如果不是，則把它調(diào)整為堆。(1) (100, 86, 48, 73, 35, 39, 42, 57, 66, 21); (2)(12, 70, 33, 65, 24, 5648, 92, 86, 33)。)A.先根遍歷B.中根遍歷C.后根遍歷D.層次遍歷二、填空題(本大題共13小題，每小題2分，共26分)16 .下列程序段的時間復(fù)雜度為for(i=1;i<=n;i+)for(j=1;j<=n;j+)x+;17 .數(shù)據(jù)結(jié)構(gòu)中結(jié)點按邏輯關(guān)系依次排列形成一條“鎖鏈”的結(jié)構(gòu)是18 .在表長為n的順序表上做刪除運算，平均要移動的結(jié)點個數(shù)為19 .在帶有頭結(jié)點的單循環(huán)鏈表head中，指針p

15、所指結(jié)點為尾結(jié)點的條件是7四、算法設(shè)計題(本大題共2小題，每小題7分，共14分)A 1至A n中，試編寫算法實現(xiàn)將順34 .n個結(jié)點的完全二叉樹按結(jié)點編號將值順序存放在一維數(shù)組元素頁眉內(nèi)容序存儲結(jié)構(gòu)轉(zhuǎn)換為二叉鏈表存儲結(jié)構(gòu)，其中根結(jié)點由tree指向。35 .試寫出冒泡排序算法。課程代碼：02142()A.O(1) B.O(.n)C.O(log2n)全國2011年1月數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題一、單項選擇題（本大題共15小題，每小題2分，共30分）1 .在順序表中查找第i個元素，時間效率最高的算法的時間復(fù)雜度為D.O（n）2 .樹形結(jié)構(gòu)中，度為0的結(jié)點稱為（）A.樹根B.葉子C.路彳至D.二叉樹3 .已知有

16、向圖G=（V,E）,其中V=V1,V2,V3,V4,V5,V6,V7,E=<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>,則圖G的拓?fù)湫蛄惺牵ǎ〢.V1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V74 .有關(guān)圖中路徑的定義，表述正確的是（）A.路徑是頂點和相鄰頂點偶對構(gòu)成的

17、邊所形成的序列B.路徑是不同頂點所形成的序列C.路徑是不同邊所形成的序列D.路徑是不同頂點和不同邊所形成的集合5 .串的長度是指（）A.串中所含不同字母的個數(shù)B.串中所含字符的個數(shù)C.串中所含不同字符的個數(shù)D.串中所含非空格字符的個數(shù)6 .組成數(shù)據(jù)的基本單位是（）A.數(shù)據(jù)項B.數(shù)據(jù)類型C.數(shù)據(jù)元素D.數(shù)據(jù)變量7 .程序段i=n;x=0;dox=x+5*i;i-;while（i>0）;的時間復(fù)雜度為（）A.O（1）B.O（n）C.O（n2）D.O（n3）8 .與串的邏輯結(jié)構(gòu)不同的數(shù)據(jù)結(jié)構(gòu)是（）A.線性表B.棧C.隊列D.樹9 .二叉樹的第i（i>1）層上所擁有的結(jié)點個數(shù)最多為（）A.

18、2iB.2iC.2i-1D.2i-110 .設(shè)單鏈表中指針p指向結(jié)點A,若要刪除A的直接后繼，則所需修改指針的操作為（）A.p->next=p->next->nextB.p=p->nextC.p=p->next->nextD.p->next=p11 .下列排序算法中，某一趟結(jié)束后未必能選出一個元素放在其最終位置上的是（）A.堆排序B.冒泡排序C.直接插入排序D.快速排序12 .設(shè)字符串S1=ABCDEFG，S2=PQRST',則運算S=CONCAT（SUBSTR（S1,2,LENGTH（S2）,SUBSTR（S1,LENGTH（S2）,2）后S

19、的結(jié)果為（）A."BCQR"B.BCDEF"C.BCDEFG"D.BCDEFEF"13 .在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為A,并且A的左孩子的平衡因子為-1,右孩子的平衡因子為0,則使其平衡的調(diào)整方法為（）A.LL型B.LR型C.RL型D.RR型14 .如果結(jié)點A有3個兄弟結(jié)點，而且B為A的雙親，則B的度為（）A.1B.3C.4D.515 .數(shù)據(jù)表A中每個元素距其最終位置較近，則最省時間的排序算法是（）A.堆排序B.插入排序C.直接選擇排序D.快速排序二、填空題（本大題共13小題，每小題2分，共26分）16 .下列

20、程序段的時間復(fù)雜度為。i=1；while（i<n）i=i*2；17 .向一個長度為n的順序表中第i（iwiwn）個元素之前插入一個元素時，需向后移動個元素。18 .在循環(huán)雙鏈表中，刪除最后一個結(jié)點，其算法的時間復(fù)雜度為。19 .隊列的插入操作在隊列的部分進(jìn)行。20 .一個棧的輸入序列是1,2,3,，n,輸出序列的第一個元素是n,則第i個輸出元素為。21 .一個10階對稱矩陣A,采用行優(yōu)先順序壓縮存儲下三角，a00為第一個元素，其存儲地址為1,每個元素占有1個存儲地址空間，則強的地址為。22 .設(shè)字符串S="IDAMDADSTUDENT"（其中口表示空格字符），則S的長

21、度為。23 .在樹形結(jié)構(gòu)中，沒有后繼的結(jié)點是結(jié)點。24 .一棵深度為n（n>1）的滿二叉樹中共有個結(jié)點。25 .在無向圖中，如果從頂點v到頂點V有路徑，則稱v和v'是。26 .無向完全圖G采用存儲結(jié)構(gòu)較省空間。27 .在順序查找、二分查找、索引查找和散列查找四種查找方法中，平均查找長度與元素個數(shù)沒有關(guān)系的查找方法是。28 .快速排序最好情況下的時間復(fù)雜度為。三、應(yīng)用題（本大題共5小題，每小題6分，共30分）29 .稀疏矩陣A如下，寫出矩陣A的三元組表及矩陣A的轉(zhuǎn)置矩陣的三元組表。0300010000005-10000000040-30000030 .一棵二叉樹的前根遍歷序列為AB

22、CDEFG，中根遍歷序列為CBDAEGF，試構(gòu)造出該二叉樹。31 .下述矩陣表示一個無向連通網(wǎng)，試畫出它所表示的連通網(wǎng)及該連通網(wǎng)的最小生成樹。1125101891282594102432 .給定表（80，90，50，70，75，60，40，100），試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r為空的二叉排序樹，畫出插入完成后的二叉排序樹。33 .試寫出一組鍵值（46，58，15，45，90，18，10，62）應(yīng)用直接插入排序算法從小到大排序后各趟的結(jié)果。四、算法設(shè)計題（本大題共2小題，每小題7分，共14分）34 .試分別寫出二叉樹的先根遍歷和中根遍歷的遞歸算法。頁眉內(nèi)容35 .試編寫以單鏈表為

23、存儲結(jié)構(gòu)實現(xiàn)直接選擇排序的算法。2011年1月全國自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論參考答案20H年1月高等教育自學(xué)考試全國統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題答案及評分參考（課程代碼02142）5H 應(yīng)A 15, B】電0 2L42 2d 密-散列查找一、單項選擇題（本大題共】5小跋,每小題2分.共30分）LA2.BRAd.A«.C7.BR.D&.C1LC1111-13,E34,C二、填空馳；本大題共13小題.每小屜2分，共26分）16.J7,ni119.隊尾（或尾都）現(xiàn)n-iHl經(jīng).1421葉子（簽端）E工建通的2乳旬1按期降28,（Xnk岬h）三、我用慰；率文惠共5小題,悠小匙£分，受

24、分）的.Mi軾疏靖年A.的三元組我如下：、分JiJV123113153274匚V451一31一稀荀走降A(chǔ)的痔置矩陣的二元組表加下:4分）tjV131-32132JO1546|1_L.J數(shù)據(jù)結(jié)構(gòu)導(dǎo)論拭鼠善案及評分妻名第1頁（共？頁）#頁眉內(nèi)容133Q*解1（左子樹3分，6子捌m分）誓如圖3L解:連通網(wǎng)為:最小生成樹為;數(shù)據(jù)結(jié)構(gòu)等論試題答篥及評分蠢考第2頁（共3頁）32（注:左于樹3分，右子豺彳分）33,解:初始序列上46列正第一趣46,5出/$"3需。，1810,62（1分）第二趟；L1246,581羽.30,18-0,62（1分）第二趟15,45,46忑8，9心理.10,62（1分）

25、血四趟；RI51451d6,犯9。3和.孫62（1分）第五趟上15,1845,46,5瓦901門。，62（1分）鬼六越：145,46,5£9。二”2索七柳工口。,15.18,45,4668,62,9門門分）四承法設(shè)計遁(本大題共2小題，每小題7分洪14分1力4上山EFT*'f.-WT244鼾：兀欣;sa."曲口開胃：Voidprccrdrtbitreptrr)if(r!NUUJvisit(r>)prerirderCr>lchild匕preor«4er(r->rcliild)：；Q分)中根遍歷遞歸算法丁V<?idortr<bit

26、reptrr)if(rlNULL)inordcr(i一二"Ichild)1visit(r);inorderCr>rchild)j)"分)35.群voidLinkedLisi_S«Ject_Sort(Liak*dUst&L)單鏈表上的直按選擇俳序算法fortp=L?p'Auer->nmxtfp=pAnu工。(1分)q=p-Anc如xhq>datw；CJ分)foHj"=q,j?=qir>n0t；r=rAncx»在q后面守找元素值最小的結(jié)點if(r2>nex<->data-<x)(1分)

27、(工三r2>next->><lata；s=r；(1分)iKs!-q)找到值比R更小的結(jié)點s->n«t(p->next-sjS>n?xt=q?(1分)t=q->ncxt*0-riext=p->nw->nextj(1分)p>nexL>nextL“交換q和L>nKt兩個結(jié)辰Cl分)/for/I.JnkdList_SelectSort數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題答案及評分叁考第m頁（共3頁）2010年10月數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單項選擇題（本大題共15小題，每小題2分，共30分）1 下列描述中正確的是（）A.

28、數(shù)據(jù)元素是數(shù)據(jù)的最小單位B.數(shù)據(jù)結(jié)構(gòu)是具有結(jié)構(gòu)的數(shù)據(jù)對象C. 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合D. 算法和程序原則上沒有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時兩者是通用的2歸并排序的時間復(fù)雜度是（）AO（n2）B.O（nlog2n）C.O（n）D.O（log2n）3二分查找的時間復(fù)雜度是（）AO（n2）B.O（nlog2n）C.O（n）D.O（log2n）4 順序存儲的表中有90000個元素，已按關(guān)鍵字值升序排列，假設(shè)對每個元素進(jìn)行查找的概率相同，且每個元素的關(guān)鍵字值皆不相同，用順序查找法查找時，需平均比較的次數(shù)為（）A25000B.30000C.45000D.900005 .散列文

29、件是一種（）A.順序文件B.索引文件C.鏈接文件D.計算尋址文件6 .兩個矩陣A:mxn,B:nXp相乘，其時間復(fù)雜度為（）A.O（n）B.O（mnp）C.O（n2）D.O（mp）7 .常用于函數(shù)調(diào)用的數(shù)據(jù)結(jié)構(gòu)是（）A.棧B.隊列C.鏈表D.數(shù)組8 .二維數(shù)組Anm以列優(yōu)先順序存儲，數(shù)組A中每個元素占用1個字節(jié)，A11為首元素，其地址為0,則元素Aij的地址為（）A.（i-1）xm+（j-1）B.（j-1）Xn+（i-1）C.（j-1）Xn+ID.jxn+i9 .圖的廣度優(yōu)先搜索使用的數(shù)據(jù)結(jié)構(gòu)是（）A.隊列B.樹C.棧D.集合10序列（21,19,37,5,2）經(jīng)冒泡排序法由小到大排序，在第一

30、次執(zhí)行交換后所得結(jié)果為（）A（19，21，37，5，2）B.（21，19，5，37，2）C.（21，19，37，2，5）D.（2，21，19，37，5）11數(shù)據(jù)在計算機存儲器內(nèi)表示時，根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址，這種方法稱為（）A.索引存儲方法B.順序存儲方法C.鏈?zhǔn)酱鎯Ψ椒―.散列存儲方法12在單鏈表中，存儲每個結(jié)點有兩個域，一個是數(shù)據(jù)域，另一個是指針域，指針域指向該結(jié)點的（）A.直接前趨B.直接后繼C.開始結(jié)點D.終端結(jié)點13在已知頭指針的單鏈表中，要在其尾部插入一新結(jié)點，其算法所需的時間復(fù)雜度為（）AO（1）B.O（log2n）C.O（n）D.O（n2）14在鏈隊列中執(zhí)行

31、入隊操作，（）A.需判別隊是否空B.需判別隊是否滿C.限制在鏈表頭p進(jìn)行D.限制在鏈表尾p進(jìn)行15一整數(shù)序列26，59，77，31，51，11，19，42，以二路歸并排序從小到大排序，第一階段的歸并結(jié)果為（）A.31，51，11，42，26，77，59，19B.26，59，31，77，11，51，19，42C.11，19，26，31，42，59，51，77D.26，11，19，31，51，59，77，42二、填空題（本大題共13小題，每小題2分，共26分）16下列程序段的時間復(fù)雜度為。i=0；s=0；while（s<n）i+；s=s+i；17數(shù)據(jù)的存儲結(jié)構(gòu)被分為順序存儲結(jié)構(gòu)、散列存儲結(jié)構(gòu)

32、和索引存儲結(jié)構(gòu)4種。18.從一個長度為n的順序表中刪除第i個元素（iwiwn）時，需向前移動個元素。19在單鏈表中，插入一個新結(jié)點需修改個指針。20在隊列結(jié)構(gòu)中，允許插入的一端稱為。頁眉內(nèi)容21 .稀疏矩陣采用的壓縮存儲方法是。22 .向一個棧頂指針為top的鏈棧中插入一個新結(jié)點*p時，應(yīng)執(zhí)行p->next=top和操作。23 .有m個葉結(jié)點的哈夫曼樹所具有的結(jié)點數(shù)為。24 .在一棵具有n個結(jié)點的完全二叉樹中，從樹根起，自上而下、自左至右地給所有結(jié)點編號。設(shè)根結(jié)點編號為1。若編號為i的結(jié)點有右孩子，那么其右孩子的編號為。25 .在一棵樹中，結(jié)點沒有前驅(qū)結(jié)點。26 .一個具有n個頂點的有向

33、完全圖的弧數(shù)是。27 .n個頂點的無向圖G用鄰接矩陣Ann存儲，其中第i列的所有元素之和等于頂點Vi的。28 .選擇排序的平均時間復(fù)雜度為。三、應(yīng)用題（本大題共5小題，每小題6分，共30分）29 .在棧的輸入端元素的輸入順序為1,2,3,4,5,6,進(jìn)棧過程中可以退棧，則退棧時能否排成序列3,2,5,6,4,1和1,5,4,6,2,3,若能，寫出進(jìn)棧、退棧過程，若不能，簡述理由。（用push（x）表示x進(jìn)棧，pop（x）表示x退棧）30 .已知一棵二叉樹的中根遍歷序列為CBEDFAGH,后根遍歷序列為CEFDBHGA,畫出該二叉樹。31 .給定表（15,11,8,20,14,13）,試按元素在

34、表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r為空的二叉排序樹，畫出插入完成后的二叉排序樹，并判斷該二叉排序樹是否為平衡二叉排序樹，若為非平衡二叉排序樹，將它調(diào)整為平衡二叉排序樹。32 .如題32圖所示無向圖，（1）寫出其鄰接矩陣；（2）寫出三種以頂點A為起點的深度優(yōu)先搜索頂點序列。33 .用冒泡排序法對數(shù)據(jù)序列（49,38,65,97,76,134,27,49）進(jìn)行排序，寫出排序過程。并說明冒泡排序是否為穩(wěn)定排序。四、算法設(shè)計題（本大題共2小題，每小題7分，共14分）34 .編寫計算二叉樹中葉子結(jié)點數(shù)目的算法。35 .開散列表的類型定義如下：typedefstructtagnodekeytypekey;structtagnode*next;*pointer,node;typedefpointeropenhashn;試寫出開散列表上的查找算法。15頁眉內(nèi)容2010年10月自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論