全國自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題及答案(4套)

1、高等教育自學(xué)考試全國統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題、答案及評分參考全國2011年1月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。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=V1,V2,V3,V4,V5,V6,V7，E=<V1,V2>，<

2、;V1,V3>，<V1,V4>，<V2,V5>，<V3,V5>,<V3,V6>，<V4,V6>，<V5,V7>,，<V6,V7>，則圖G的拓?fù)湫蛄惺? )A.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)成的邊所形成的序列B.路徑是不同頂點所形成的序列C.路徑是不同邊所形成的序列D.路徑是不同頂點和不同邊所形成

3、的集合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（i1）層上所擁有的結(jié)點個數(shù)最多為( )A.2iB.2iC.2i-1D.2i-110.設(shè)單鏈表中指針p指向結(jié)點A，若要刪除A的直接后繼，則所需修改指針的

4、操作為( )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的結(jié)果為( )A.BCQRB.BCDEFC.BCDEFGD.BCDEFEF13.在平衡二叉樹中插入一個結(jié)點后造成了不平衡

5、，設(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=1；while（i<n）i=i*2；17.向一個長度為n的順序表中第i（1in）個元素之前插入一

6、個元素時，需向后移動_個元素。18.在循環(huán)雙鏈表中，刪除最后一個結(jié)點，其算法的時間復(fù)雜度為_。19.隊列的插入操作在隊列的_部分進(jìn)行。20.一個棧的輸入序列是1，2，3，n，輸出序列的第一個元素是n，則第i個輸出元素為_。21.一個10階對稱矩陣A，采用行優(yōu)先順序壓縮存儲下三角，a00為第一個元素，其存儲地址為1，每個元素占有1個存儲地址空間，則a85的地址為_。22.設(shè)字符串S=IAMASTUDENT（其中表示空格字符），則S的長度為_。23.在樹形結(jié)構(gòu)中，沒有后繼的結(jié)點是_結(jié)點。24.一棵深度為n(n>1)的滿二叉樹中共有_個結(jié)點。25.在無向圖中，如果從頂點v到頂點v有路徑，則稱v

7、和v是_。26.無向完全圖G采用_存儲結(jié)構(gòu)較省空間。27.在順序查找、二分查找、索引查找和散列查找四種查找方法中，平均查找長度與元素個數(shù)沒有關(guān)系的查找方法是_。28.快速排序最好情況下的時間復(fù)雜度為_。三、應(yīng)用題(本大題共5小題，每小題6分，共30分)29.稀疏矩陣A如下，寫出矩陣A的三元組表及矩陣A的轉(zhuǎn)置矩陣的三元組表。30.一棵二叉樹的前根遍歷序列為ABCDEFG，中根遍歷序列為CBDAEGF，試構(gòu)造出該二叉樹。31.下述矩陣表示一個無向連通網(wǎng)，試畫出它所表示的連通網(wǎng)及該連通網(wǎng)的最小生成樹。32.給定表（80，90，50，70，75，60，40，100），試按元素在表中的順序?qū)⑺鼈円来尾迦?/p>

8、一棵初始時為空的二叉排序樹，畫出插入完成后的二叉排序樹。33.試寫出一組鍵值（46，58，15，45，90，18，10，62）應(yīng)用直接插入排序算法從小到大排序后各趟的結(jié)果。四、算法設(shè)計題(本大題共2小題，每小題7分，共14分)34.試分別寫出二叉樹的先根遍歷和中根遍歷的遞歸算法。35.試編寫以單鏈表為存儲結(jié)構(gòu)實現(xiàn)直接選擇排序的算法。2011年1月全國自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論參考答案全國2010年10月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分

9、。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（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.45

10、000D.900005散列文件是一種( )A順序文件B.索引文件C.鏈接文件D.計算尋址文件6兩個矩陣A：m×n，B：n×p相乘，其時間復(fù)雜度為( )AO(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）×m+(j-1)B.(j-1)×n+(i-1)C.(j-1)×n+iD.j×n+i9.圖的廣度優(yōu)先搜索使用的數(shù)據(jù)結(jié)構(gòu)是( )A隊列B.樹C

11、.棧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，5)D.(2，21，19，37，5)11數(shù)據(jù)在計算機(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ù)雜

12、度為( )AO（1）B.O（log2n）C.O（n）D.O（n2）14在鏈隊列中執(zhí)行入隊操作，( )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

13、下列程序段的時間復(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的順序表中刪除第i個元素（1in）時，需向前移動_個元素。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é)點編

14、號為1。若編號為i的結(jié)點有右孩子，那么其右孩子的編號為_。25在一棵樹中，_結(jié)點沒有前驅(qū)結(jié)點。26一個具有n個頂點的有向完全圖的弧數(shù)是_。27n個頂點的無向圖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

15、，后根遍歷序列為CEFDBHGA，畫出該二叉樹。31給定表（15，11，8，20，14，13），試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r為空的二叉排序樹，畫出插入完成后的二叉排序樹，并判斷該二叉排序樹是否為平衡二叉排序樹，若為非平衡二叉排序樹，將它調(diào)整為平衡二叉排序樹。32如題32圖所示無向圖，（1）寫出其鄰接矩陣；（2）寫出三種以頂點A為起點的深度優(yōu)先搜索頂點序列。題32圖33用冒泡排序法對數(shù)據(jù)序列（49，38，65，97，76，134，27，49）進(jìn)行排序，寫出排序過程。并說明冒泡排序是否為穩(wěn)定排序。四、算法設(shè)計題(本大題共2小題，每小題7分，共14分)34.編寫計算二叉樹中葉子結(jié)點數(shù)

16、目的算法。35.開散列表的類型定義如下：typedef struct tagnodekeytype key; struct tagnode*next;*pointer,node;typedef pointer openhashn;試寫出開散列表上的查找算法。2010年10月自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論參考答案2005年10月自考試卷數(shù)據(jù)結(jié)構(gòu)導(dǎo)論第 18 頁高等教育自學(xué)考試全國統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題、答案及評分參考2005年10月自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論答案第 21 頁高等教育自學(xué)考試全國統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題、答案及評分參考全國2004年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單

17、項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1.要將現(xiàn)實生活中的數(shù)據(jù)轉(zhuǎn)化為計算機(jī)所能表示的形式，其轉(zhuǎn)化過程依次為（）A.邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、機(jī)外表示B.存儲結(jié)構(gòu)、邏輯結(jié)構(gòu)、機(jī)外表示C.機(jī)外表示、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)D.機(jī)外表示、存儲結(jié)構(gòu)、邏輯結(jié)構(gòu)2.若評價算法的時間復(fù)雜性，比較對數(shù)階量級與線性階量級，通常（）A.對數(shù)階量級復(fù)雜性大于線性階量級B.對數(shù)階量級復(fù)雜性小于線性階量級C.對數(shù)階量級復(fù)雜性等于線性階量級D.兩者之間無法比較3.下列關(guān)于線性表的基本操作中，屬于加工型的操作是（）A.

18、初始化、求表長度、插入操作B.初始化、插入、刪除操作C.求表長度、讀元素、定位操作D.定位、插入、刪除操作4.在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，s指向已生成的新結(jié)點，則在p之后插入s所指結(jié)點的正確操作是（）A.s>next=p>next; p>next=s;B.p>next=s>next; s>next=p;C.s>next=p; p>next=s;D.s>next=p>next; p=s;5.若有三個字符的字符串序列執(zhí)行入棧操作，則其所有可能的輸出排列共有（）A.3種B.4種C.5種D.6種6.C語言對數(shù)組元素的存放方式通常

19、采用（）A.按行為主的存儲結(jié)構(gòu)B.按列為主的存儲結(jié)構(gòu)C.按行或列為主的存儲結(jié)構(gòu)D.具體存儲結(jié)構(gòu)無法確定7.根據(jù)定義，樹的葉子結(jié)點其度數(shù)（）A.必大于0B.必等于0C.必等于1D.必等于28.二叉樹若采用二叉鏈表結(jié)構(gòu)表示，則對于n個結(jié)點的二叉樹一定有（）A.2n個指針域其中n個指針為NULLB.2n個指針域其中n+1個指針為NULLC.2n-1個指針域其中n個指針為NULLD.2n-1個指針域其中n+1個指針為NULL9.在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的（）A.1倍B.2倍C.3倍D.4倍10.若采用鄰接表存儲結(jié)構(gòu)，則圖的廣度優(yōu)先搜索類似于二叉樹的（）A.先根遍歷B.中根遍歷C.后根

20、遍歷D.層次遍歷11.采用順序查找法，若在表頭設(shè)置崗哨，則正確的查找方式通常為（）A.從第0個元素開始往后查找該數(shù)據(jù)元素B.從第1個元素開始往后查找該數(shù)據(jù)元素C.從第n個元素開始往前查找該數(shù)據(jù)元素D.從第n+1個元素開始往前查找該數(shù)據(jù)元素12.下列查找中，效率最高的查找方法是（）A.順序查找B.折半查找C.索引順序查找D.分塊查找13.索引文件通常由索引表和主文件兩部分構(gòu)成，其中（）A.索引表和主文件均必須是有序文件B.索引表和主文件均可以是無序文件C.索引表必須是有序文件D.主文件必須是有序文件14.直接插入排序算法，其時間復(fù)雜性為（）A.O(1)B.O(n)C.O(nlog2n)D.O(n

21、2)15.下列排序方法中，屬于穩(wěn)定的排序方法是（）A.直接插入排序法B.快速排序法C.冒泡排序法D.堆排序法二、填空題（本大題共13小題，每小題2分，共26分）請在每小題的空格中填上正確答案。錯填、不填均無分。16.從數(shù)據(jù)結(jié)構(gòu)的觀點，數(shù)據(jù)通常可分為三個層次，即：數(shù)據(jù)、數(shù)據(jù)元素和_。17.用程序設(shè)計語言、偽程序設(shè)計語言并混合自然語言描述的算法稱為_算法。18.對順序表執(zhí)行插入操作，其插入算法的平均時間復(fù)雜性為_。19.在具有n個單元、且采用順序存儲的循環(huán)隊列中，隊滿時共有_個元素。20.若front和rear分別表示循環(huán)隊列Q的頭指針和尾指針，m0表示該隊列的最大容量，則循環(huán)隊列為空的條件是_。

22、21.二維數(shù)組A1020采用按行為主序的存儲方式，每個元素占4個存儲單元，若A00的存儲地址為300，則A1010的地址為_。22.樹的遍歷主要有先根遍歷、后根遍歷和_三種。23.深度為k的完全二叉樹至少有_個結(jié)點。24.若圖的鄰接矩陣是一個對稱矩陣，則該圖一定是一個_。25.對于具有n個元素的數(shù)據(jù)序列，采用二叉排序樹查找，其平均查找長度為_。26.要完全避免散列所產(chǎn)生的“堆積”現(xiàn)象，通常采用_法。27.ISAM其中文含義為_方法。28.在最好的情況下，對于具有n個元素的有序序列，若采用冒泡排序，所需的比較次數(shù)為_次。三、應(yīng)用題（本大題共5小題，每小題6分，共30分）29.已知某二叉樹如下圖所示，試給出其二叉鏈表及順序存儲結(jié)構(gòu)表示。30.若某無向圖G的鄰接表如圖所示，試給