1、全國2011年1月自學考試數(shù)據(jù)結構導論試題課程代碼：02142、單項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。1 .在順序表中查找第i個元素，時間效率最高的算法的時間復雜度為（）A.O（1）B.O（、n）C.O（log2n）D.O（n）2 .樹形結構中，度為0的結點稱為（）A.樹根B.葉子C.路徑D.二叉樹3 .已知有向圖G=(V,E),其中V=V1,V2,V3,V4,V5,V6,V7,E=<V1,V2>,<V1,V3>,<V1,V4>,<V

2、2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>,則圖G的拓撲序列是A.V1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V4,V5,V7B.串中所含字符的個數(shù)D.串中所含非空格字符的個數(shù)B.數(shù)據(jù)類型D.數(shù)據(jù)變量B.O(n)D.O(n3)B.棧D.樹C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V74 .有關圖中路徑的定義，表述正確的是（）A.路徑是頂點和相鄰頂點偶對構成的邊所形成的序列B.路徑是不同頂點所形成的序列C.路徑是不同邊

3、所形成的序列D.路徑是不同頂點和不同邊所形成的集合5 .串的長度是指（）A.串中所含不同字母的個數(shù)C.串中所含不同字符的個數(shù)6 .組成數(shù)據(jù)的基本單位是（）A.數(shù)據(jù)項C.數(shù)據(jù)元素7程序段i=n;x=0;dox=x+5*i;i-;while（i>0）;的時間復雜度為（）A.O（1）2、C.O（n2）8 .與串的邏輯結構不回的,數(shù)據(jù)結構是（A.線性表C.隊列9 .二叉樹的第i(i>1)層上所擁有的結點個數(shù)最多為(B.2ii-1C.2A.2iD.2-110 .設單鏈表中指針p指向結點A,若要刪除A的直接后繼，則所需修改指針的操作為A.p->next=p->next->ne

4、xtB.p=p->nextC.p=p->next->nextD.p->next=p11 .下列排序算法中，某一趟結束后未必能選出一個元素放在其最終位置上的是A.堆排序B.冒泡排序C.直接插入排序D.快速排序12 .設字符串S1=ABCDEFG，S2=PQRST",則運算S=CONCAT(SUBSTR(S1,2,LENGTH(S2),SUBSTR(S1,LENGTH(S2),2)后S的結果為(A.BCQRB.BCDEF"C."BCDEFGD.BCDEFEF”13 .在平衡二叉樹中插入一個結點后造成了不平衡,設最低的不平衡結點為A,并且A的左孩

5、子的平衡因子為-1,孩子的平衡因子為0,則使其平衡的調整方法為A.LL型B.LR型C.RL型D.RR型14 .如果結點A有3個兄弟結點，而且B為A的雙親，則B的度為(A.1B.3C.4D.515 .數(shù)據(jù)表A中每個元素距其最終位置較近，則最省時間的排序算法是A.堆排序B.插入排序C.直接選擇排序D.快速排序二、填空題(本大題共13小題，每小題2分，共26分)請在每小題的空格中填上正確答案。錯填、不填均無分。16 .下列程序段的時間復雜度為i=1；while(i<n)i=i*2;17 .向一個長度為n的順序表中第i(1wiwn)個元素之前插入一個元素時,需向后移動個元素。18.在循環(huán)雙鏈表中

6、，刪除最后一個結點，其算法的時間復雜度為19.隊列的插入操作在隊列的部分進行。20 .一個棧的輸入序列是1,2,3,n,輸出序列的第一個元素是n,則第i個輸出元素為21 .一個10階對稱矩陣A,采用行優(yōu)先順序壓縮存儲下三角，a。為第一個元素，其存儲地址為1,每個元素占有個存儲地址空間，則a85的地址為22 .設字符串S=，zIDAMDADSTUDENT"(其中口表示空格字符)，則S的長度為。23 .在樹形結構中，沒有后繼的結點是結點。24 .一棵深度為n(n>1)的滿二叉樹中共有個結點。25 .在無向圖中，如果從頂點v到頂點v'有路徑，則稱v和v'是。26 .無

7、向完全圖G采用存儲結構較省空間。27 .在順序查找、二分查找、索引查找和散列查找四種查找方法中，平均查找長度與元素個數(shù)沒有關系的查找方法是28 .快速排序最好情況下的時間復雜度為。三、應用題(本大題共5小題，每小題6分，共30分)29 .稀疏矢I陣A如下，寫出矩陣A的三元組表及矩陣A的轉置矩陣的三元組表。"0300010000005-10000000040-30000030 .一棵二叉樹的前根遍歷序列為ABCDEFG,中根遍歷序列為CBDAEGF，試構造出該二叉樹。31 .下述矩陣表示一個無向連通網(wǎng)，試畫出它所表示的連通網(wǎng)及該連通網(wǎng)的最小生成樹。po1125101oo89°

8、o12888259|4100024g32 .給定表(80,90,50,70,75,60,40,100),試按元素在表中的順序將它們依次插入一棵初始時為空的二叉排序樹，畫出插入完成后的二叉排序樹。33 .試寫出一組鍵值(46,58,15,45,90,18,10,62)應用直接插入排序算法從小到大排序后各趟的結果。四、算法設計題(本大題共2小題，每小題7分，共14分)34 .試分別寫出二叉樹的先根遍歷和中根遍歷的遞歸算法。35 .試編寫以單鏈表為存儲結構實現(xiàn)直接選擇排序的算法。2011年1月全國自考數(shù)據(jù)結構導論參考答案2011年1月高等教育自學考試全國統(tǒng)一命題考試數(shù)據(jù)結構導論試題答案及評分參考（課

9、程代碼02142）一、單項選擇品f本大題共15小題，每小題之分，排30分）LA2.B3.A4.A5,BG.C7.BStDS.C10,AIkC12.1)13.B風C15.B二、填空我（本大題共13小題，每小題2分.共2G分）1£.OU*n)17.ni+lIS.(_K1)11隊尾£或尾部）加.n-i十12L4222.142工咻子儂端）£4.中一25.連通的獨O(nlng:n)愿.鄰接矩陣2散列查找三、政用題（本大題共5小建，每小組5分，共加分）雙帆灣疏矩陣A的三元組表如下43分）iijV1z!3151-31q32i454_517稀疏矩陣A的得置矩陣的二元絹表如下：3分

10、）1-faV13二rn一13211a23-i544_J11數(shù)據(jù)結構導論獻題答案史評分奏忐第1頁（共3頁）30,解*售30圖3L解，連通網(wǎng)為:最小生成樹為;數(shù)據(jù)第構導的試題答第及評分參考第2頁（共3貫）32809050答32圖(注:左子樹3分，方子樹3分)3解工分分分分分初始序列：16,58,15.45,90,18,10*62第一趟上46,己8，15"5,9318.10,62(1第二卷113,46,5孫虻，9。Jg10,62(1第三趟工口5,45,46,5叼,9。JB,10,62(1第四趟：15,43,46,58,90,18,10,52(1第五趟J15門8,45,46,38,9gj0.

11、G2(1第六荔工10,15,18.45,46,58,90/62第七ahl(hl5J8,45,46,58,62,沏<1分)四、算法慢計題(本大題共2小題,每小題7分，共14分)。|fmM-MJ»IfTn-、al-3JTM-a-L斛：幾恤膽川Ji空爐開量:Voidprcorder(hitreptiT)i£(r!=NULL)visit(r>jpmordtrCr>kbild八preor<ir(r一child)彳(2分)中根遍街遞歸算法Voidordtr(bitreptrr)if(r!-NULL)in0rdet(r->Ichiid)*visit(r)辛i

12、nnrder(r->rchild)j)(4分)35.解：void1二點溫口與_6電口_80日。：1比11式&1)單鏈表上的直接選擇排序算法forCp=L»p>next-Anexlip=p-(1分)(q=p-2>next;x-q>datai(1分)for(T=q,$=qr>neKt；r=r>n息xt)在q后面尋找兀素值最小的結點if(r>next->dara<x)(1分)xr>rLexL>dfita；s=r；(1分)if(s*Kq)找到了值比qAdata更小的結點s>npxtp-next-s>&quo

13、t;next；j(1分)r=q->ncxlq?>riexi=P'-S>next->nexh(I分)p>next>口©4=CJ/交換q和布一>口后洪兩個結點(1分)fdr/LinkedList_SelactSort數(shù)據(jù)緒構導論試題答案及評分參考第3頁（共3頁）全國2010年10月自學考試數(shù)據(jù)結構導論試題課程代碼：02142一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。1 .下列描述中正確的是()A.數(shù)據(jù)元素是數(shù)據(jù)的最小單位

14、B.數(shù)據(jù)結構是具有結構的數(shù)據(jù)對象C.數(shù)據(jù)結構是指相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合D.算法和程序原則上沒有區(qū)別，在討論數(shù)據(jù)結構時兩者是通用的2 .歸并排序的時間復雜度是()A.O(n2)B.O(nlogzn)C.O(n)D.O(logzn)3 .二分查找的時間復雜度是()A.O(n2)B.O(nlogzn)C.O(n)D.O(log2n)4 .順序存儲的表中有90000個元素，已按關鍵字值升序排列，假設對每個元素進行查找的概率相同，且每個元素的關鍵字值皆不相同，用順序查找法查找時，需平均比較的次數(shù)為()A.25000B.30000D.90000C.450005 .散列文件是一種()

15、A.順序文件B.索引文件C.鏈接文件D.計算尋址文件6 .兩個矩陣A：mxn,B：nXp相乘，其時間復雜度為()A.O(n)B.O(mnp)C.O(n2)D.O(mp)7 .常用于函數(shù)調用的數(shù)據(jù)結構是()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ù)結構是()B.樹D.集合A.隊列C.棧10 .序列(21,19,37,5,2)經(jīng)冒泡排序法由小到大排序，在第一次執(zhí)行交

16、換后所得結果為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ù)在計算機存儲器內表示時，根據(jù)結點的關鍵字直接計算出該結點的存儲地址，這種方法稱為()A.索引存儲方法B.順序存儲方法C.鏈式存儲方法D.散列存儲方法12 .在單鏈表中，存儲每個結點有兩個域，一個是數(shù)據(jù)域，另一個是指針域，指針域指向該結點的()A.直接前趨B.直接后繼C.開始結點D.終端結點13 .在已知頭指針的單鏈表中，要在其尾部插入一新結點，其算法所需的時間復雜度為()A.O(1)B.O(logzn)C.O(n)D.O(n2)14 .在鏈隊

17、列中執(zhí)行入隊操作，()A.需判別隊是否空B.需判別隊是否滿C.限制在鏈表頭p進行D.限制在鏈表尾p進行15 .一整數(shù)序列26,59,77,31,51,11,19,42,以二路歸并排序從小到大排序，第一階段的歸并結果為(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 .下列程序段的時間復雜度為。i=0;s=0;while(s<n)i+

18、；s=s+i;17 .數(shù)據(jù)的存儲結構被分為順序存儲結構、散列存儲結構和索引存儲結構4種。18 .從一個長度為n的順序表中刪除第i個元素(1Wiwn)時，需向前移動個元素。19 .在單鏈表中，插入一個新結點需修改個指針。20 .在隊列結構中，允許插入的一端稱為。21 .稀疏矩陣采用的壓縮存儲方法是。22 .向一個棧頂指針為top的鏈棧中插入一個新結點*p時，應執(zhí)行p->next=top和操作。23 .有m個葉結點的哈夫曼樹所具有的結點數(shù)為。24 .在一棵具有n個結點的完全二叉樹中，從樹根起，自上而下、自左至右地給所有結點編號。設根結點編號為1若編號為i的結點有右孩子，那么其右孩子的編號為。

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

20、叉樹。31 .給定表（15,11,8,20,14,13）,試按元素在表中的順序將它們依次插入一棵初始時為空的二叉排序樹，畫出插入完成后的二叉排序樹，并判斷該二叉排序樹是否為平衡二叉排序樹，若為非平衡二叉排序樹，將它調整為平衡二叉排序樹。32.如題32圖所示無向圖，（1）寫出其鄰接矩陣；（2）寫出三種以頂點A為起點的深度優(yōu)先搜索頂點序列。33 .用冒泡排序法對數(shù)據(jù)序列（49,38,65,97,76,134,27,49）進行排序，寫出排序過程。并說明冒泡排序是否為穩(wěn)定排序。四、算法設計題（本大題共2小題，每小題7分，共14分）34 .編寫計算二叉樹中葉子結點數(shù)目的算法。35 .開散列表的類型定義如

21、下：typedefstructtagnodekeytypekey;structtagnode*next;*pointer,node;typedefpointeropenhashn;試寫出開散列表上的查找算法。2010年10月自考數(shù)據(jù)結構導論參考答案2010年10月高等教育自學考試全國統(tǒng)一命題考試數(shù)據(jù)結構導論試題答案及評分參考（課程代碼02142）一單項選擇題（本大題共15小題，每小題2分共30分）l.C6.B11,D2.B7.A12.B3.D13.C二”填空題（本大題共13小題，每小題2分，共26分）4.C9.A14.D5.D10,A15.B16.0編)19.222rtop=p25.報28,O

22、(n2)17.鏈式存儲結揭20.隊尾23.2m126bn(n1)18力.三元組表24,2i+l"度三.應用題【本大題共5小JH.銀小題6分盤30分）29.解.“能"成序列3,2,5,641過程1pushpush（2）tpush（3hpop：poppush（4箝push（5；pop才push（6）ipop（6）jpop（4）；pop（1）（3分）不能排成序列1,5,4,6,2,W理由：在2,3依次進棧后，根據(jù)棧結構的特征不能產(chǎn)生排列入工（3分）3。.解：A（左子樹4分，右子樹2分）答觸圖31.解:二又排序樹為:數(shù)據(jù)結構導論試題答案及評分參考第1頁（共£頁）不平衡口分

23、），調整后的平衡二叉排序將為IAro32.解D：E10000答非圖一212分）010000（3分）AHBDGECFAHBEGDCFiAHCFBDGE*ABDGECFHTABEGDCFH；ACFBDGEH；ACFBEGDHjACFHBIXEtACFHBEGD等等只寫其中三個）C3分）初始關鍵字493R659776134274g第一趟38496576972749134第二超38496576274997134第三超38496527497697134第四趟384927496576&7134蒐五趟3B274949"5576S7134第六趟27384949657697134（5分）冒泡排

24、序是穩(wěn)定排序.。分）四.算法設計題1本大題共2小窟，將小盤7分，共14分）34.解；intLeafCouptCBitreftT）求二又樹中葉子結點的數(shù)目（i£（IT）return。1（2分）ekeif（T-T->rchild）rEtum11（2分）elsereturnLeaf_Count（T>lchild）H-Ltaf_Count（T>rchild）；C3分）/LeafCount_EiTree35.解，Pointerresearchopenhash（keytypeKtopenli&shHP）i=Hg（l分）P=HP口（1分）while«p!=NUL

25、L）&&（p-Al«¥l=K）“2分）p=p->nextt<2分）retum（p）t（l分）數(shù)據(jù)結構導論試題答案及兩分參考第E頁（共E頁）2005年10月自考試卷數(shù)據(jù)結構導論2005年1。月高等教育自學考試全國統(tǒng)一命題考試數(shù)據(jù)結構導論試卷（課程代碼2142）本試卷共8頁,需分10。分：考試時間1S。分鐘o總分卜題號1-11三明核分人題分30263014復置入褊分得分評卷入復查人一單項選擇就本大屋共15小蝎,每小超2分,共30分）在每小題列出的四個選項中只有一個是符合星目要求的r請招其代碼填寫在題后的括號內。錯選、摹選或未選均無分口1,若要描述數(shù)據(jù)

26、處理的變化過程T其正確的次序立為A,處理要求、基本運算和運算、算法B.處理要求、算法、基本運算和運算C.基本運算和運算、處理要求、算法D.算法，處理要求、基本運算和運算2.從運算類型角度考慮,屬于引用型的運算是A.插入、刪除民刪除.爆改C.查找、讀取D.查找、刪除以若在長度為n的順序表中插入一個結點，則其轉點的移動次數(shù)A.最少為口,最多為n民量少為1,最零為nC.最少為0,最多為n+1D,最少為1*最需為n+14.在一個單鏈表中，若P所指結點是q所指結點的前驅結點，則在結點PE之間播入結點寫的正確操作是I1A. s一>n£Kt=q.priiit=SE>nEKtB. pne

27、xtq?p->-next=sC*s>ne?tt=q>nextfp>next=sDts->neKt=>next?p->next=s->next5.若有一串數(shù)字5、6.7出人棧，則其不平整的輸出序列為A.5、6J、8R8J.6,5C.8、7、5、6D+5.8,7（219）數(shù)據(jù)結構導論試卷第1頁（共8頁）6 .FORTRAN語言對數(shù)組元素的存放方式通常采用(】A.按行為主的存儲結構B.按列為主的存儲結構Q按行或列為主的存儲結構D.按行和列為主的存儲結構7 .樹是n個結點的有窮集合，(1A,樹的結點個數(shù)可以為0,此時稱該樹為空樹8 .樹至少含有一個根結點

28、，不能為空C.樹至少含有一個根結點和一個葉子結點D.樹至少含有一個根結點和兩個葉子結點8 .深度為k的二叉樹至多有I】A.2k個葉子B,2'-】個葉子C.2上一1個葉子D.21】一1個葉子9 .具有10個頂點的有向完全圖應具有I1A.20條弧B.5Q條瓠C90條孤D.100條弧10 .從Vi出發(fā)，對題10圖按廣度優(yōu)先搜索遍歷，則可能得到的一種頂點序列為t】A.VMV3V5V.V&B,ViVMVsV&V,CVM/RV&V,CVDVMV6V4V5V£題10圖IL適用于靜態(tài)的查找方法為I】A,二分查找.二叉排序樹查找B.二分查找、索引順序表查找C.二叉排序樹

29、查找，索引順序表查找D.二叉排序樹查找、散列法查找12 .采用二分查找法，若當前取得的中間位置MID的元索值小于被查找值，則表明待查元素可能在表的后半部分,下次查找的起始位置通常應(1A.從M1D/2位置開始B.從MID位置開始C從MID1位置開始D.從MID+1位置開始13 .磁盤是一種廣泛使用的外部存儲設備，對磁盤的存取操作r1A.只能用順序方式B.只能用隨機方式C既能用順序方式也能用隨機方式D.方式取決于具體的機器(219)數(shù)據(jù)結構導論試卷第2頁(共8頁)14 .當待排序序列中記錄數(shù)較少或基本有序時，最適合的排序方法為】A,直接插入排序法R快速排序法C.堆排序法D.歸并排序法15 .若對

30、序列（26,90,23,53,16,34,69,39,22）進行一趟排序后所得到的結果為（22,16,23,26,53,34,69,39,90）,則該排序可能使用的方法是（】A.插入排序B,冒泡排序C.快速排序D選擇排序得分評卷入復查人二,填空IK（本大題共13小題，羯小題2分，共26分）請在每小題的空格中填上正確答案。錯填、不填均無分。16 .算法通?？煞譃槌绦?、偽語言算法和三種類型.17 .時間復雜性描述量級中，若某算法達到量級，則該算法通常是不可計算的。18 .對順序表執(zhí)行刪除操作，其刪除算法的平均時間復雜性為,19 .若head表示循環(huán)鏈表的頭指針，t表示尾結點，則頭指針head與尾結

31、點t之間的關系可表示為，20 .我們通常把隊列中允許刪除的一端稱為a21 .二維數(shù)組A56采用按列為主序的存儲方式，每個元索占3個存儲單元，若A0兀0的存儲地址是100,則A43：l的存儲地址是.22 .樹在數(shù)據(jù)結構中常采用孩子鏈表表示法,三種存儲結構表示.23 .若某二叉樹中度為1的結點數(shù)為4,度為2的結點數(shù)為6,則該樹葉子結點數(shù)為.24 .對于n個頂點的生成樹,其邊的個數(shù)為,25 .對于具有n個元案的數(shù)據(jù)序列，若采用二分查找法，當n的值較大時其平均查找長度為26 .解決散列所引起沖突的方案中,法是介于開散列表與閉散列表之間的一種方法.iI.27 .多關鍵字文件是指同時對兩部分都建立索引的文

32、件組織形式.28 .排序通常可分為內部排序和外部排序，其中內部排序是指排序的整個過程中，數(shù)據(jù)全部存放在計算機的中.（219）數(shù)據(jù)結構導論試卷第3頁（共8頁）得分評卷人復查人三、應用題(本大題共5小題，每小題6分，共30分)29 .對于如題29圖所示二叉樹，分別寫出其先根遍歷、中根遍歷和后根遍歷的結點訪問序列,30 .設散列函數(shù)為H(key)=key%ll,散列表長度為11(散列地址空間為18.在給定表(SUN,MON,TUE,WED,THU,FR,SAT)中，取單詞的第一個字母在英語字母表中的序號為鍵值K,構造一散列表，并用線性探測法解決有關的地址沖突。3L成給出題31圖的鄰接矩陣和鄰接表表示

33、.題31圖32.已知一組鍵值序列(32,44,38,65,53,42,29,57),試采用堆排序法對該組序列作升序排序，給出建立的初始堆以及第一次輸出堆元索后篩選調整的堆。33.已知一組鍵值序列(13,12J6,17,15,14,11),試采用二路歸并排序法對該組序列作升序排序，并給出每一趟的排序結果.得分評卷入復查人四,設計總（本大題共2小圍，每小第7分，排14分）34.若循環(huán)單鏈表長度大于l,p為指向鏈表中某結點的指骨，試編寫一算法刪除p結點的前驅結點。35.若二叉樹用二叉鏈表表示，試編寫一算法計算一棵二叉樹的葉子思數(shù)（可采用遞歸算法描述L2005年10月自考數(shù)據(jù)結構導論答案2005年10

34、月高等教育自學考試全國統(tǒng)一命題考試數(shù)據(jù)結構導論試題答案及評分參考（課程代碼2142）單項選擇題（本大題共15小鹿，銀小題2分，共39分）二、填空題（本大題共13小鹿，每小頻2分,共26分）16.非形式算法1工指數(shù)19.t>next=head20.隊頭21.15722.孩子兄弟鏈表和雙親表示法24.N-I25.Log2(n+1)-1施.建立公共溢出區(qū)27.主關健字和次關鍵字28 .內存儲器三、應用題（本大題共5小題，每小題6分，共3。分）29 .先根遍歷士ABDEFC（2分）中根遍毋；BFEDAC（2分）后根遍歷：FEDBCA（£分）30 .門）根據(jù)字母的順序.所產(chǎn)生的序列為；1

35、9,13120,23,20,6/9q分）調散列表：01234i67fi&019231361920T20JJ：_L_I31.鄰接短陣,數(shù)據(jù)結構導論試題答案及評分參考第1頁（共3頁）3QO8oo8OOCO888QO7118OO813gCOQQ848、C3分）鄰接表:2932初始堆:輸出堆頂后的調整堆：32443344385753423857534265（3分）33.初始：13121617151411第一趟：12131171411（2分）第二越：12131617111415（2分）第三趟，口1121314151617（2分）（3分）2965四，設計髓（本大黑共2小題，悠小題7分，共14分34

36、. Node*deleteCp）Node*p；node*q,*r?（1分）（1分）（1分）while<r->nexl!=q）r=r>next：（1分r->next=p事（1分）free（q）i（1分）數(shù)據(jù)結構導論試題答案及評分參考第2頁（共3頁）return(p)?35. voidcountleaf<bitreptrt»int*count)(分)(if(ti=NULL)(1分)(if(t>lchild=匚NULL)&->rchild=NULL)(2分)*count-F4-t(分)countleaf(t-2>IchiId,coun

37、t)j(1分)countleaf(t-l>rchild,count)?(l分)全國2004年10月高等教育自學考試數(shù)據(jù)結構導論試題課程代碼：02142一、單項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。1 .要將現(xiàn)實生活中的數(shù)據(jù)轉化為計算機所能表示的形式，其轉化過程依次為（）A.邏輯結構、存儲結構、機外表示B.存儲結構、邏輯結構、機外表示C.機外表示、邏輯結構、存儲結構D.機外表示、存儲結構、邏輯結構2 .若評價算法的時間復雜性，比較對數(shù)階量級與線性階量級，通常（）A.對數(shù)階量級

38、復雜性大于線性階量級B.對數(shù)階量級復雜性小于線性階量級C.對數(shù)階量級復雜性等于線性階量級D.兩者之間無法比較3 .下列關于線性表的基本操作中，屬于加工型的操作是（）A.初始化、求表長度、插入操作B.初始化、插入、刪除操作C.求表長度、讀元素、定位操作D.定位、插入、刪除操作4 .在一個單鏈表中，若p所指結點不是最后結點，s指向已生成的新結點，則在p之后插入s所指結點的正確操作是（）A.s>next=p>next;p9next=s;B.p>next=snext;s>next=p;C.s9next=p;pnext=s;D.s>next=pnext;p=s;5 .若有三

39、個字符的字符串序列執(zhí)行入棧操作，則其所有可能的輸出排列共有（）A.3種B.4種C.5種D.6種6 .C語言對數(shù)組元素的存放方式通常采用（）A.按行為主的存儲結構B.按列為主的存儲結構C.按行或列為主的存儲結構D.具體存儲結構無法確定7 .根據(jù)定義，樹的葉子結點其度數(shù)（）A.必大于0B.必等于0C.必等于1D.必等于28 .二叉樹若采用二叉鏈表Z構表示，則對于n個結點的二叉樹一定有（A.2n個指針域其中n個指針為NULLB.2n個指針域其中n+1個指針為NULLC.2n-1個指針域其中n個指針為NULLD.2n-1個指針域其中n+1個指針為NULL9 .在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)

40、的（）A.1倍B.2倍C.3倍D.4倍10 .若采用鄰接表存儲結構，則圖的廣度優(yōu)先搜索類似于二叉樹的（）A.先根遍歷B.中根遍歷C.后根遍歷D.層次遍歷11 .采用順序查找法，若在表頭設置崗哨，則正確的查找方式通常為（）A.從第0個元素開始往后查找該數(shù)據(jù)元素B.從第1個元素開始往后查找該數(shù)據(jù)元素C.從第n個元素開始往前查找該數(shù)據(jù)元素D.從第n+1個元素開始往前查找該數(shù)據(jù)元素12 .下列查找中，效率最高的查找方法是（）A.順序查找B.折半查找C.索引順序查找D.分塊查找13 .索引文件通常由索引表和主文件兩部分構成，其中（）A.索引表和主文件均必須是有序文件B.索引表和主文件均可以是無序文件C.

41、索引表必須是有序文件D.主文件必須是有序文件14 .直接插入排序算法，其時間復雜性為（）A.O（1）B.O（n）C.O（nlog2n）D.O（n2）15 .下列排序方法中，屬于穩(wěn)定的排序方法是（）A.直接插入排序法B.快速排序法C.冒泡排序法D.堆排序法二、填空題（本大題共13小題，每小題2分，共26分）請在每小題的空格中填上正確答案。錯填、不填均無分。16 .從數(shù)據(jù)結構的觀點，數(shù)據(jù)通?？煞譃槿齻€層次，即：數(shù)據(jù)、數(shù)據(jù)元素和。17 .用程序設計語言、偽程序設計語言并混合自然語言描述的算法稱為算法。18 .對順序表執(zhí)行插入操作，其插入算法的平均時間復雜性為。19 .在具有n個單元、且采用順序存儲的循環(huán)隊列中，隊滿時共有個元素。20 .若front和rear分別表示循環(huán)隊列Q的頭指針和尾