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

1、全國2012年1月數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單項選擇題(本大題共15小題，每小題2分，共30分)1 .結(jié)點按邏輯關(guān)系依次排列形成一條鎖鏈”的數(shù)據(jù)結(jié)構(gòu)是()A.集合 B.線性結(jié)構(gòu)C.樹形結(jié)構(gòu)D.圖狀結(jié)構(gòu)2 .下面算法程序段的時間復(fù)雜度為()for ( int i=0; i<m; i+)for ( int j=0; j<n; j+)a ijl =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>Q個字符的有窮序列C.具有n (n>Q個結(jié)點的有窮序列D.具有

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

3、矩陣壓縮存儲時需存儲的元素個數(shù)為9 .深度為k (k>l)的二叉樹，結(jié)點數(shù)最多有 (10 .具有12個結(jié)點的二叉樹的二叉鏈表存儲結(jié)構(gòu)中,()A.11B.56C.100D.101)A.2k 個B.(2k-1)個C.2k-1 個D.(2k+1)個空鏈域 NULL的個數(shù)為()A. 11B.13 C. 23 D.2511.具有n個頂點的無向圖的邊數(shù)最多為()A.n+1B.n(n+1)C.n(n-1)/2D.2n(n+1)0 1 012.三個頂點V1,V2,V3的圖的鄰接矩陣為)A. 0 B. 1 C. 2 D.0 0 1 ，該圖中頂點V3的入度為(0 1 0313 .順序存儲的表格中有 6000

4、0個元素，已按關(guān)鍵字值升序排列，假定對每個元素進(jìn)行查找的概率是相同的，且 每個元素的關(guān)鍵字值不相同。用順序查找法查找時，平均比較次數(shù)約為()A.20000 B.30000 C.40000D.6000014 .外存儲器的主要特點是()A.容量小和存取速度低B.容量大和存取速度低C.容量大和存取速度高D.容量小和存取速度高15 .在待排數(shù)據(jù)基本有序的前提下，效率最高的排序算法是()A.直接插入排序 B.直接選擇排序C.快速排序D.歸并排序二、填空題(本大題共13小題，每小題2分，共26分)16 .數(shù)據(jù)的不可分割的最小標(biāo)識單位是 ,它通常不具有完整確定的實際意義，或不被當(dāng)作一個整體對待。17 .運算

5、分為加工型運算和引用型運算，讀取操作是 運算。18 .帶有頭結(jié)點的單向循環(huán)鏈表 L （L為頭指針）中，指針 p所指結(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é)點沒有雙親。1,23 .一棵具有n個結(jié)點的完全二叉樹中，從樹根起，自上而下、自左至右給所有結(jié)點編號。設(shè)根結(jié)點編號為若編號為i的結(jié)點有父結(jié)點，那么其父結(jié)點的

6、編號為24 .二叉樹的二叉鏈表存儲結(jié)構(gòu)中判斷指針p所指結(jié)點為葉子結(jié)點的條件是25.邊稀疏的無向圖采用存儲較省空間。26 .除第一個頂點和最后一個頂點相同外，其余頂點不重復(fù)的回路，稱為27 .二分查找算法的時間復(fù)雜度是相互交換。28 .要將序列51 , 18, 23, 68, 94, 70, 73建成堆，則只需把 18與三、應(yīng)用題（本大題共5小題，每小題6分，共30分）29 .將題29圖所示的一棵二叉樹轉(zhuǎn)換成對應(yīng)的森林。題31圖題32圖30 .給定權(quán)值 3, 9, 13,5, 7,構(gòu)造相應(yīng)的哈夫曼（Huffman ）樹，并計算其帶權(quán)路徑長度。31 .寫出題31圖的鄰接矩陣和每個頂點的入度與出度。

7、32 .二叉排序樹的各結(jié)點的值依次為2028,請在題32圖中標(biāo)出各結(jié)點的值。33 .用冒泡排序法對數(shù)據(jù)序列（55, 38, 65, 97, 76, 138, 27, 49）進(jìn)行排序，寫出排序過程中的各趟結(jié)果。四、算法設(shè)計題（本大題共2小題，每小題7分，共14分）34 .設(shè)線性表A = （a1， a2,sm）, B= （b1，b2,b）,試寫一個按下列規(guī)則合并A, B為線性表C的算法,使得C= (a1，b1,，abm ,bm+1, ,b)當(dāng) m<n時;或者C= (a1, b1,，na,bn ,an+1,m) 當(dāng) m>n 時。線性表A,B和C均以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)，且 C表利

8、用A表和B表中的結(jié)點空間構(gòu)成。（注意：單鏈表的長度值 m和n均未顯式存儲。）35 .二叉樹的二叉鏈表類型定義如下:typedef struct btnode datatype data;struct btnode *lchild,*rchild; bitreptr;寫出后根遍歷根指針為 t的二叉樹的遞歸算法（void postorder （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)入隊

9、列 Q, 若6個元素的出隊序列是 e2, e4, e3, e6, e5, e1,則棧S的容量至少為()A.2B.3C.4D.62 .設(shè)計一個判別表達(dá)式中左右括號是否配對出現(xiàn)的算法，采用的最佳數(shù)據(jù)結(jié)構(gòu)為()A.線性表的順序存儲結(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(1 w i,j w n,i w j)以列優(yōu)先順序存放在一維數(shù)組元素B 1至B n(n+1)/2中，則元素

10、 Aj(iwj)在B中的位置為()A.i(i-l)/2+jB.j(j-l)/2+i C.j(-l)/2+i-1D.i(i-l)/2+j-15 .在有向圖G的拓?fù)湫蛄兄?，若頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)的是()A.G中有弧<Vi, Vj>B.G中有一條從Vi到Vj的路徑C.G中沒有弧<Vi, Vj>D.G中有一條從Vj到Vi的路徑6 .下列序列中，由第一趟快速排序可得到的序列(排序的關(guān)鍵字類型是字符串)是()A. da,ax,eb,de,bbff ha,gcB. cd,eb,ax,daffha, gc,bbC. gc,ax,eb,cd,bbff da,haD

11、. 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的記錄的存儲位置是()01234567891011121315386184A.3B.5C.8D.99 .若元素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 (l

12、og2n)11 .稀疏矩B是指()A.元素少的矩陣B.有少量零元素的矩陣C.有少量非零元素的矩陣D.行數(shù)、列數(shù)很少的矩陣12 .深度為 k (k>1)的二叉樹，結(jié)點數(shù)最多有()A.2k B.2k-1C.2k-1D.2k-1-113 .由帶權(quán)為9, 2, 5, 7的四個葉子結(jié)點構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為()A.23 B.37 C.44D.4614 .有n個頂點的有向完全圖的弧數(shù)為( )A.n2 B.2n C.n(n-1)D.2n (n+1)15 .圖的深度優(yōu)先搜索類似于二叉樹的()A.先根遍歷B.中根遍歷C.后根遍歷 D.層次遍歷二、填空題(本大題共13小題，每小題2分，共26

13、分)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所指結(jié)點為尾結(jié)點的條件是 。20 .隊列又稱為 的線性表。21 .順序棧被定義為結(jié)構(gòu)類型，含有兩個域：data和top,則對棧*sq進(jìn)行初始化的操作是 。22 .對于任何一棵二叉樹 T,如果其終端結(jié)點數(shù)為n0,度為2的結(jié)點數(shù)為n2,則n2=。23 .一棵具有n個結(jié)點的二叉樹，采用二叉鏈表存儲

14、，則二叉鏈表中指向孩子結(jié)點的指針有 個。24 .若連通圖G的頂點個數(shù)為n,則圖G的生成樹的邊數(shù)為 。25 .一個具有n個頂點的無向圖的邊數(shù)最多為 。26 .中根遍歷二叉排序樹所得到的結(jié)點訪問序列是鍵值的 序列。27 .冒泡排序的平均時間復(fù)雜度為 。28 .將序列60, 20, 23, 68, 94, 70, 73建成堆，則只需把 20與 互相交換。三、應(yīng)用題(本大題共5小題，每小題6分，共30分)29 .如題29圖所示，在棧的輸入端元素的輸入順序為A, B, C, D,進(jìn)棧過程中可以退棧，寫出在棧的輸出端以A開頭和以B開頭的所有輸出序列。題29圖題30圖題31圖題32圖30 .一棵二叉樹如題3

15、0圖所示，寫出該二叉樹的先根遍歷序列、中根遍歷序列和后根遍歷序列。31 .將題31圖所示的一棵二叉樹轉(zhuǎn)換成森林。32 .對于有向無環(huán)圖：(1)敘述求拓?fù)渑判蛩惴ǖ幕静襟E；(2)對于題32圖，寫出它的4個不同的拓?fù)渑判蛐蛄小?3 .判別以下序列是否為堆。如果不是，則把它調(diào)整為堆。(1) (100, 86, 48, 73, 35, 39, 42, 57, 66, 21); (2) (12, 70, 33, 65, 24, 56, 48, 92, 86, 33)。 四、算法設(shè)計題(本大題共2小題，每小題7分，共14分)34 .n個結(jié)點的完全二叉樹按結(jié)點編號將值順序存放在一維數(shù)組元素A 1至A n中

16、，試編寫算法實現(xiàn)將順序存儲結(jié)構(gòu)轉(zhuǎn)換為二叉鏈表存儲結(jié)構(gòu)，其中根結(jié)點由tree指向。35 .試寫出冒泡排序算法。全國2011年1月數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單項選擇題（本大題共15小題，每小題2分，共30分）1 .在順序表中查找第i個元素，時間效率最高的算法的時間復(fù)雜度為（）A.O（1）B.O（而）C.O（log2n）D.O（n）2 .樹形結(jié)構(gòu)中，度為 0的結(jié)點稱為（）A.樹根 B.葉子C.路彳至D.二叉樹3 .已知有向圖 G=（V,E）,其中 V=V 1,V2,V3,V4,V5,V6,V7 , E=<V 1,V2> , <V1,V3> , <V1,V4

17、> , <V 2,V5> , <V3,V5>,<V3,V6>, <V4,V6>, <V5,V7>, 76丫7>,則圖 G 的拓?fù)湫蛄惺牵ǎ〢.V 1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V4,V5,V7 C.V 1,V3,V4,V5,V2,V 6,V7D.V 1,V2,V5,V3,V4,V6,V74 .有關(guān)圖中路徑的定義，表述正確的是 （）A.路徑是頂點和相鄰頂點偶對構(gòu)成的邊所形成的序列B.路徑是不同頂點所形成的序列C.路徑是不同邊所形成的序列D.路徑是不同頂點和不同邊所形成的集合5 .串的長度是

18、指（）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.2i B.2i C.2i-1D.2i-110 .設(shè)單鏈表中指針p指向結(jié)點A,若要刪除A的

19、直接后繼，則所需修改指針的操作為（）A.p->next=p->next->next B.p=p->next C.p=p->next->next D.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 的結(jié)果為（）A." BCQR" B. BCD

20、EF" 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 .下列程序段的時間復(fù)雜度為 。i

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

22、符），則S的長度為。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)置矩陣的三元組表。030001000000 5-1 0 0 0 0 00

23、0040 -30 0 0 0 030 .一棵二叉樹的前根遍歷序列為ABCDEFG ，中根遍歷序列為CBDAEGF ，試構(gòu)造出該二叉樹。31 .下述矩陣表示一個無向連通網(wǎng)，試畫出它所表示的連通網(wǎng)及該連通網(wǎng)的最小生成樹。1 12 51018912 82594102 432 .給定表（80， 90， 50， 70， 75， 60， 40， 100） ，試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r為空的二叉排序樹，畫出插入完成后的二叉排序樹。33 .試寫出一組鍵值（46， 58， 15， 45， 90， 18， 10， 62）應(yīng)用直接插入排序算法從小到大排序后各趟的結(jié)果。四、算法設(shè)計題（本大題共2 小

24、題，每小題7 分，共 14 分 ）34 .試分別寫出二叉樹的先根遍歷和中根遍歷的遞歸算法。35 .試編寫以單鏈表為存儲結(jié)構(gòu)實現(xiàn)直接選擇排序的算法。2011年1月全國自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論參考答案2011年1月高等教育自學(xué)考試全國統(tǒng),一命題考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題答案及評分參考（課程代碼 02142）一、單項選擇題（本大題共15小跋,每小題Z分.共30分）1. AZ-B3. A4, A5. BG. C7, B8. D生 C1G, A11.C12.1)'13, B14tCIt. B二、填空50；奉大題共13小益，每小建2分.共26分）16. CKh>&n)ni-118.0(1)19.隊

25、尾（或尾部）20. n-i4* 121+42ZZ. 1421葉于f卷羯24.25.連逋的28.鄰接矩陣2工散列查找2&. （Xnlog! n）二、底對黑；本人黑共5小段,耳小息6分，& 3!分） 29.稀疏用陣A.的三,元蛆我第下：（？分）11334._3. J2612rV31574一 3稀疏短降A(chǔ)的轉(zhuǎn)置矩陣訪三元組表卻下分）1tjV1515213231544611數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試鼠舉案及評分翡.名第】頁（共？頁30.解：（左子樹3分，石子樹3分）答30圖31.解，連通網(wǎng)為:獻(xiàn)小生成樹為;數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題答案及評分參考第2頁（共3頁）32 一答能圖(注2左子期3分1右子樹三分)M

26、3.解;初始序列146, 5 fhi5*43矢1,10,62第趣上4£戶幻5T必需(j,1E,1O,MC1分)一二一山5,4彘5町.45 .蛇社gJ(M2(1分)第二的J15H55&5叼國。,】£門黑62(1分)第四趟：門 5,4516,58*90,卻 ,1362(1分)東直.口5,1孔席次;洱鈾。,鹿(1分)第六越；10,必,46.5機9口，鹿第七糖工16.1殖1%，品4/簫工2 .就(1步)四，算法諛計遢(本大翅共2小題,每小題¥分.共14分)力中 拓n "三川盧d-.W >*口4斛i無醉HL囚度戶丹西:Void preorSE“hit

27、i"邛trr) ifirJNUUJ visit(r>p pruorderCr >lchild)» pteorfler r- >rcliilcl)；)(3 分),根追加遞歸算法Vcid orcfcrCrjittptrr)< ifCrl-NULL) i.nordcr(i-> I child) visit(r ；inordertr-C>rchjltD j )«仍3友好void U nke dLisi_Se1 Mt_SoTt (Li nkTI_ k t & L) 單鏈.表上的玄拄逸擇排序克旅 (fottp Ljp >nEX

28、t->n總、Hp=p>n”t)tl 分)( q=pAnuxtjKNqAdata*Cl 分)"=烏福二世一 Aucxt打=rAn；Kt)/7在q后面尋找元素值最小的輔點 if(r>nexi - >data<xj (1 £ x= r> nesct-* > data ；r ；(1 分)if(s! =q)找到了值比q>das更小的結(jié)點=->n«t (p-AuE3tt=sAiwxt”一>nrtxi=q；Cl 分)t - q- >rKj*t«q->nexi.-"p -> nest

29、 >next； (1 分p>next-Augxil j/交換 q 和 s>riKt 的個結(jié)點(1 分)f" /JUnkedList_SelectScrt數(shù)娼結(jié)構(gòu)導(dǎo)論試題答案及評分參考第3頁(共3頁)2010年10月數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142、單項選擇題（本大題共15小題，每小題2分，共30分）1 下列描述中正確的是（）A. 數(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（nlo

30、g2n）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ù)為（ ）A 25000 B.30000 C.45000D.900005 .散列文件是一種（ ）A .順序文件B.索引文件 C.鏈接文件D.計算尋址文件6 .兩個矩陣 A : mxn, B: nXp 相乘，其時間復(fù)雜度為 （ ）A. O（n） B.O（mnp） C.O（n2） D.O （mp）7 .常用于函

31、數(shù)調(diào)用的數(shù)據(jù)結(jié)構(gòu)是（ ）A.棧B.隊列C.鏈表 D.數(shù)組8 .二維數(shù)組 A n m以列優(yōu)先順序存儲，數(shù)組 A中每個元素占用1個字節(jié)，A 1 1為首元素，其地 址為 0,則元素 A i j的地址為（）A. （i-1） x m+（j-1）B.（j-1） Xn+（i-1）C.（j-1）Xn+I D.j x n+i9 .圖的廣度優(yōu)先搜索使用的數(shù)據(jù)結(jié)構(gòu)是（ ）A.隊列 B.樹 C.棧 D.集合10序列（21,19,37,5,2）經(jīng)冒泡排序法由小到大排序，在第一次執(zhí)行交換后所得結(jié)果為（）A （19， 21， 37， 5， 2） B.（21， 19， 5， 37， 2） C.（21， 19， 37， 2，

32、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ù)雜度為（）A O（ 1）B.O（ log2n）C.O（ n）D.O（ n2）14在鏈隊列中執(zhí)行入隊操作，（）A.需判別隊是否空B.需判別隊是否滿C.限制在鏈表頭p進(jìn)行D.限制在鏈表尾p進(jìn)行15

33、 一整數(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)和索引存儲結(jié)構(gòu)4 種。18.從一個長度為n的順序表中刪除

34、第i個元素（iwiwn）時，需向前移動 個元素。19在單鏈表中，插入一個新結(jié)點需修改個指針。20在隊列結(jié)構(gòu)中，允許插入的一端稱為。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個頂點的有向完全圖的弧數(shù)是 。27 . n個頂點的無向圖 G用鄰接

35、矩陣A n n存儲，其中第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）,試按

36、元素在表中的順序?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 .開散列表的類型定義如下：typedef struct tagnodekeytype key;struct tagnode*next;*pointer,node;typedef pointer openhash n;試寫出開散列表上的查找算法。2010年10月自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論參考答案201