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

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

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

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

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

5、分為加工型運(yùn)算和引用型運(yùn)算，讀取操作是 運(yùn)算。18 .帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表 L （L為頭指針）中，指針 p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是19 .在雙鏈表中，前趨指針和后繼指針分別為prior和next。若使指針p往后移動(dòng)兩個(gè)結(jié)點(diǎn)，則需執(zhí)行語句20 .元素S1,S2,S3,S4,S5,S6依次進(jìn)入順序棧S,如果6個(gè)元素的退棧順序?yàn)镾2,S3,S4,S6,S5,S1 ,則順序棧的容量至少為21 .稀疏矩陣一般采用的壓縮存儲(chǔ)方法是22.在一棵樹中,結(jié)點(diǎn)沒有雙親。1,23 .一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中，從樹根起，自上而下、自左至右給所有結(jié)點(diǎn)編號(hào)。設(shè)根結(jié)點(diǎn)編號(hào)為若編號(hào)為i的結(jié)點(diǎn)有父結(jié)點(diǎn)，那么其父結(jié)點(diǎn)的

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

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

8、用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。（注意：單鏈表的長度值 m和n均未顯式存儲(chǔ)。）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一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)1 .設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素 e1, e2, e3, e4, e5和e6依次通過棧S,元素退棧后即進(jìn)入隊(duì)

9、列 Q, 若6個(gè)元素的出隊(duì)序列是 e2, e4, e3, e6, e5, e1,則棧S的容量至少為()A.2B.3C.4D.62 .設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對(duì)出現(xiàn)的算法，采用的最佳數(shù)據(jù)結(jié)構(gòu)為()A.線性表的順序存儲(chǔ)結(jié)構(gòu)B.隊(duì)列C.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.棧3 .下列程序段的時(shí)間復(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的對(duì)稱矩陣，將A的對(duì)角線及對(duì)角線上方的元素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ù)湫蛄兄校繇旤c(diǎn)Vi在頂點(diǎn)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個(gè)記錄，如果用二次探測(cè)法處理沖突，關(guān)鍵字為49的記錄的存儲(chǔ)位置是()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 .直接插入排序的時(shí)間復(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é)點(diǎn)數(shù)最多有()A.2k B.2k-1C.2k-1D.2k-1-113 .由帶權(quán)為9, 2, 5, 7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為()A.23 B.37 C.44D.4614 .有n個(gè)頂點(diǎ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 .下列程序段的時(shí)間復(fù)雜度為 。for(i=1;i<=n;i+)for(j=1;j<=n;j+) x+;17 .數(shù)據(jù)結(jié)構(gòu)中結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一條“鎖鏈”的結(jié)構(gòu)是 。18 .在表長為n的順序表上做刪除運(yùn)算，平均要移動(dòng)的結(jié)點(diǎn)個(gè)數(shù)為 。19 .在帶有頭結(jié)點(diǎn)的單循環(huán)鏈表head中，指針p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是 。20 .隊(duì)列又稱為 的線性表。21 .順序棧被定義為結(jié)構(gòu)類型，含有兩個(gè)域：data和top,則對(duì)棧*sq進(jìn)行初始化的操作是 。22 .對(duì)于任何一棵二叉樹 T,如果其終端結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n2=。23 .一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲(chǔ)

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

15、0圖所示，寫出該二叉樹的先根遍歷序列、中根遍歷序列和后根遍歷序列。31 .將題31圖所示的一棵二叉樹轉(zhuǎn)換成森林。32 .對(duì)于有向無環(huán)圖：(1)敘述求拓?fù)渑判蛩惴ǖ幕静襟E；(2)對(duì)于題32圖，寫出它的4個(gè)不同的拓?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è)計(jì)題(本大題共2小題，每小題7分，共14分)34 .n個(gè)結(jié)點(diǎn)的完全二叉樹按結(jié)點(diǎn)編號(hào)將值順序存放在一維數(shù)組元素A 1至A n中

16、，試編寫算法實(shí)現(xiàn)將順序存儲(chǔ)結(jié)構(gòu)轉(zhuǎn)換為二叉鏈表存儲(chǔ)結(jié)構(gòu)，其中根結(jié)點(diǎn)由tree指向。35 .試寫出冒泡排序算法。全國2011年1月數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）1 .在順序表中查找第i個(gè)元素，時(shí)間效率最高的算法的時(shí)間復(fù)雜度為（）A.O（1）B.O（而）C.O（log2n）D.O（n）2 .樹形結(jié)構(gòu)中，度為 0的結(jié)點(diǎn)稱為（）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.路徑是頂點(diǎn)和相鄰頂點(diǎn)偶對(duì)構(gòu)成的邊所形成的序列B.路徑是不同頂點(diǎn)所形成的序列C.路徑是不同邊所形成的序列D.路徑是不同頂點(diǎn)和不同邊所形成的集合5 .串的長度是

18、指（）A.串中所含不同字母的個(gè)數(shù) B.串中所含字符的個(gè)數(shù)C.串中所含不同字符的個(gè)數(shù)D.串中所含非空格字符的個(gè)數(shù)6 .組成數(shù)據(jù)的基本單位是（）A.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)類型C.數(shù)據(jù)元素D.數(shù)據(jù)變量7 .程序段 i=n ; x=0 ;dox=x+5*i ; i-; while （i>0）;的時(shí)間復(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.隊(duì)列D.樹9 .二叉樹的第i （i>1）層上所擁有的結(jié)點(diǎn)個(gè)數(shù)最多為（）A.2i B.2i C.2i-1D.2i-110 .設(shè)單鏈表中指針p指向結(jié)點(diǎn)A,若要?jiǎng)h除A的

19、直接后繼，則所需修改指針的操作為（）A.p->next=p->next->next B.p=p->next C.p=p->next->next D.p->next=p11 .下列排序算法中，某一趟結(jié)束后未必能選出一個(gè)元素放在其最終位置上的是（）A.堆排序B.冒泡排序C.直接插入排序D.快速排序12 .設(shè)字符串 S1 = ABCDEFG ，S2= PQRST',則運(yùn)算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 .在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A,并且A的左孩子的平衡因子為-1 ,右孩子的平衡因子為 0,則使其平衡的調(diào)整方法為（）A.LL 型 B.LR 型 C.RL 型 D.RR 型14 .如果結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)，而且 B為A的雙親，則B的度為（）A.1B.3C.4D.515 .數(shù)據(jù)表A中每個(gè)元素距其最終位置較近，則最省時(shí)間的排序算法是（）A.堆排序B.插入排序C.直接選擇排序D.快速排序二、填空題（本大題共13小題，每小題2分，共26分）16 .下列程序段的時(shí)間復(fù)雜度為 。i

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

22、符），則S的長度為。23 .在樹形結(jié)構(gòu)中，沒有后繼的結(jié)點(diǎn)是結(jié)點(diǎn)。24 .一棵深度為n（n>1）的滿二叉樹中共有 個(gè)結(jié)點(diǎn)。25 .在無向圖中，如果從頂點(diǎn)v到頂點(diǎn)v'有路徑，則稱 v和v'是。26 .無向完全圖G 采用 存儲(chǔ)結(jié)構(gòu)較省空間。27 .在順序查找、二分查找、索引查找和散列查找四種查找方法中，平均查找長度與元素個(gè)數(shù)沒有關(guān)系的查找方法是 。28 .快速排序最好情況下的時(shí)間復(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 .下述矩陣表示一個(gè)無向連通網(wǎng)，試畫出它所表示的連通網(wǎng)及該連通網(wǎng)的最小生成樹。1 12 51018912 82594102 432 .給定表（80， 90， 50， 70， 75， 60， 40， 100） ，試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r(shí)為空的二叉排序樹，畫出插入完成后的二叉排序樹。33 .試寫出一組鍵值（46， 58， 15， 45， 90， 18， 10， 62）應(yīng)用直接插入排序算法從小到大排序后各趟的結(jié)果。四、算法設(shè)計(jì)題（本大題共2 小

24、題，每小題7 分，共 14 分 ）34 .試分別寫出二叉樹的先根遍歷和中根遍歷的遞歸算法。35 .試編寫以單鏈表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)直接選擇排序的算法。2011年1月全國自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論參考答案2011年1月高等教育自學(xué)考試全國統(tǒng),一命題考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題答案及評(píng)分參考（課程代碼 02142）一、單項(xiàng)選擇題（本大題共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.隊(duì)

25、尾（或尾部）20. n-i4* 121+42ZZ. 1421葉于f卷羯24.25.連逋的28.鄰接矩陣2工散列查找2&. （Xnlog! n）二、底對(duì)黑；本人黑共5小段,耳小息6分，& 3!分） 29.稀疏用陣A.的三,元蛆我第下：（？分）11334._3. J2612rV31574一 3稀疏短降A(chǔ)的轉(zhuǎn)置矩陣訪三元組表卻下分）1tjV1515213231544611數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試鼠舉案及評(píng)分翡.名第】頁（共？頁30.解：（左子樹3分，石子樹3分）答30圖31.解，連通網(wǎng)為:獻(xiàn)小生成樹為;數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題答案及評(píng)分參考第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機(jī)9口，鹿第七糖工16.1殖1%，品4/簫工2 .就(1步)四，算法諛計(jì)遢(本大翅共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后面尋找元素值最小的輔點(diǎn) if(r>nexi - >data<xj (1 £ x= r> nesct-* > data ；r ；(1 分)if(s! =q)找到了值比q>das更小的結(jié)點(diǎn)=->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 的個(gè)結(jié)點(diǎn)(1 分)f" /JUnkedList_SelectScrt數(shù)娼結(jié)構(gòu)導(dǎo)論試題答案及評(píng)分參考第3頁(共3頁)2010年10月數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）1 下列描述中正確的是（）A. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位B. 數(shù)據(jù)結(jié)構(gòu)是具有結(jié)構(gòu)的數(shù)據(jù)對(duì)象C. 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合D. 算法和程序原則上沒有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時(shí)兩者是通用的2歸并排序的時(shí)間復(fù)雜度是（）AO（n2）B.O（nlo

30、g2n）C.O（n）D.O（log2n）3二分查找的時(shí)間復(fù)雜度是（）AO（n2）B.O（nlog2n）C.O（n）D.O（log2n）4順序存儲(chǔ)的表中有90000 個(gè)元素，已按關(guān)鍵字值升序排列，假設(shè)對(duì)每個(gè)元素進(jìn)行查找的概率相同，且每個(gè)元素的關(guān)鍵字值皆不相同，用順序查找法查找時(shí)，需平均比較的次數(shù)為（ ）A 25000 B.30000 C.45000D.900005 .散列文件是一種（ ）A .順序文件B.索引文件 C.鏈接文件D.計(jì)算尋址文件6 .兩個(gè)矩陣 A : mxn, B: nXp 相乘，其時(shí)間復(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.隊(duì)列C.鏈表 D.數(shù)組8 .二維數(shù)組 A n m以列優(yōu)先順序存儲(chǔ)，數(shù)組 A中每個(gè)元素占用1個(gè)字節(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.隊(duì)列 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ù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址，這種方法稱為（）A.索引存儲(chǔ)方法B.順序存儲(chǔ)方法C.鏈?zhǔn)酱鎯?chǔ)方法D.散列存儲(chǔ)方法12在單鏈表中，存儲(chǔ)每個(gè)結(jié)點(diǎn)有兩個(gè)域，一個(gè)是數(shù)據(jù)域，另一個(gè)是指針域，指針域指向該結(jié)點(diǎn)的（）A.直接前趨B.直接后繼C.開始結(jié)點(diǎn)D.終端結(jié)點(diǎn)13在已知頭指針的單鏈表中，要在其尾部插入一新結(jié)點(diǎn)，其算法所需的時(shí)間復(fù)雜度為（）A O（ 1）B.O（ log2n）C.O（ n）D.O（ n2）14在鏈隊(duì)列中執(zhí)行入隊(duì)操作，（）A.需判別隊(duì)是否空B.需判別隊(duì)是否滿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下列程序段的時(shí)間復(fù)雜度為。i=0； s=0；while （ s<n） i+； s=s+i； 17數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為順序存儲(chǔ)結(jié)構(gòu)、散列存儲(chǔ)結(jié)構(gòu)和索引存儲(chǔ)結(jié)構(gòu)4 種。18.從一個(gè)長度為n的順序表中刪除

34、第i個(gè)元素（iwiwn）時(shí)，需向前移動(dòng) 個(gè)元素。19在單鏈表中，插入一個(gè)新結(jié)點(diǎn)需修改個(gè)指針。20在隊(duì)列結(jié)構(gòu)中，允許插入的一端稱為。21稀疏矩陣采用的壓縮存儲(chǔ)方法是。22向一個(gè)棧頂指針為top 的鏈棧中插入一個(gè)新結(jié)點(diǎn)*p 時(shí)，應(yīng)執(zhí)行p->next=top 和 操作。23有m 個(gè)葉結(jié)點(diǎn)的哈夫曼樹所具有的結(jié)點(diǎn)數(shù)為。24 .在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中，從樹根起，自上而下、自左至右地給所有結(jié)點(diǎn)編號(hào)。設(shè)根結(jié)點(diǎn)編號(hào) 為1。若編號(hào)為i的結(jié)點(diǎn)有右孩子，那么其右孩子的編號(hào)為 。25 .在一棵樹中， 結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)。26 . 一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖的弧數(shù)是 。27 . n個(gè)頂點(diǎn)的無向圖 G用鄰接

35、矩陣A n n存儲(chǔ)，其中第i列的所有元素之和等于頂點(diǎn) Vi的。28 .選擇排序的平均時(shí)間復(fù)雜度為 。三、應(yīng)用題（本大題共5小題，每小題6分，共30分）29 .在棧的輸入端元素的輸入順序?yàn)?, 2, 3, 4, 5, 6,進(jìn)棧過程中可以退棧，則退棧時(shí)能否排成序列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(shí)為空的二叉排序樹， 畫出插入完成后的二叉排序樹，并判斷該二叉排序樹是否為平衡二叉排序樹，若為非平衡二叉排序樹，將它 調(diào)整為平衡二叉排序樹。32 .如題32圖所示無向圖，（1）寫出其鄰接矩陣；（2）寫出三種以頂點(diǎn) A為起點(diǎn)的深度優(yōu)先搜索頂點(diǎn)序列。33 .用冒泡排序法對(duì)數(shù)據(jù)序列（49, 38, 65, 97, 76, 134, 27, 49）進(jìn)行排序，寫出排序過程。并說明冒泡排 序是否為穩(wěn)定排序。四、算法設(shè)計(jì)題（本大題共2小題，每小題7分，共14分）34 .編寫計(jì)算二叉樹中葉子結(jié)點(diǎn)數(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