全國2011年1月自學考試數(shù)據(jù)結(jié)構(gòu)導論試題和答案
課程代碼：02142
一、單項選擇題(本大題共15小題，每小題2分，共30分)
在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。
1.在順序表中查找第i個元素，時間效率最高的算法的時間復雜度為( )
A.O(1) B.O(n) C.O(log2n)
2.樹形結(jié)構(gòu)中，度為0的結(jié)點稱為( )
A.樹根 B.葉子 C.路徑 D.二叉樹 D.O(n)
3.已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={
A.V1,V3,V4,V6,V2,V5,V7
C.V1,V3,V4,V5,V2,V6,V7 B.V1,V3,V2,V6,V4,V5,V7 D.V1,V2,V5,V3,V4,V6,V7
4.有關圖中路徑的定義，表述正確的是( )
A.路徑是頂點和相鄰頂點偶對構(gòu)成的邊所形成的序列 B.路徑是不同頂點所形成的序列
C.路徑是不同邊所形成的序列 D.路徑是不同頂點和不同邊所形成的集合
5.串的長度是指( )
A.串中所含不同字母的個數(shù)
C.串中所含不同字符的個數(shù)
6.組成數(shù)據(jù)的基本單位是( )
A.數(shù)據(jù)項 B.數(shù)據(jù)類型 C.數(shù)據(jù)元素 D.數(shù)據(jù)變量
7.程序段 i=n；x=0；
do{x=x+5*i；i--；}while （i>0）；
的時間復雜度為( )
A.O（1） B.O（n） C.O（n2） D.O(n3) B.串中所含字符的個數(shù) D.串中所含非空格字符的個數(shù)
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-1 D.2i-1
10.設單鏈表中指針p指向結(jié)點A，若要刪除A的直接后繼，則所需修改指針的操作為
( )
A.p->next=p->next->next
C.p=p->next->next B.p=p->next D.p->next=p
11.下列排序算法中，某一趟結(jié)束后未必能選出一個元素放在其最終位置上的是( )
A.堆排序 B.冒泡排序 C.直接插入排序 D.快速排序
12.設字符串S1=″ABCDEFG″，S2=″PQRST″，則運算
S=CONCAT(SUBSTR(S1,2,LENGTH(S2)),SUBSTR(S1,LENGTH(S2),2))
后S的結(jié)果為( )
A.″BCQR″ B.″BCDEF″ C.″BCDEFG″ D.″BCDEFEF″
13.在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設最低的不平衡結(jié)點為A，并且A的左孩子的平衡因子為-1，右孩子的平衡因子為0，則使其平衡的調(diào)整方法為( )
A.LL型 B.LR型 C.RL型 D.RR型
14.如果結(jié)點A有3個兄弟結(jié)點，而且B為A的雙親，則B的度為( )
A.1 B.3 C.4 D.5
15.數(shù)據(jù)表A中每個元素距其最終位置較近，則最省時間的排序算法是( )
A.堆排序 B.插入排序 C.直接選擇排序 D.快速排序
二、填空題(本大題共13小題，每小題2分，共26分)
請在每小題的空格中填上正確答案。錯填、不填均無分。
16.下列程序段的時間復雜度為_____o(log2n)______。
i=1；
while（i
i=i*2；
17.向一個長度為n的順序表中第（i1≤i≤n）個元素之前插入一個元素時，需向后移動_______n-i+1____個元素。
18.在循環(huán)雙鏈表中，刪除最后一個結(jié)點，其算法的時間復雜度為_____o(1)______。
19.隊列的插入操作在隊列的___________部分進行。
20.一個棧的輸入序列是1，2，3，…，n，輸出序列的第一個元素是n，則第i個輸出元素為______n-i+1_____。
21.一個10階對稱矩陣A，采用行優(yōu)先順序壓縮存儲下三角，a00為第一個元素，其存儲地址為1，每個元素占有1個存儲地址空間，則a85的地址為____9*(9-1)/2+6{0是第一行，1是第二行有2個元素，2是第3行有3個元素。。。。。n再加上a00起始地址}_______。
22.設字符串S=″I□AM□A□STUDENT″（其中□表示空格字符），則S的長度為___________。
23.在樹形結(jié)構(gòu)中，沒有后繼的結(jié)點是___________結(jié)點。
24.一棵深度為n(n>1)的滿二叉樹中共有___________個結(jié)點。
25.在無向圖中，如果從頂點v到頂點v′有路徑，則稱v和v′是___________。
26.無向完全圖G采用___________存儲結(jié)構(gòu)較省空間。
27.在順序查找、二分查找、索引查找和散列查找四種查找方法中，平均查找長度與元素個數(shù)沒有關系的查找方法是___________。
28.快速排序最好情況下的時間復雜度為___________。
三、應用題(本大題共5小題，每小題6分，共30分)
29.稀疏矩陣A如下，寫出矩陣A的三元組表及矩陣A的轉(zhuǎn)置矩陣的三元組表。
0 3 0 0 0 1 0 0 0 0 0 0 5 -1 0 0 0 0 0 0 0 0 4 0 -3 0 0 0 0 0
30.一棵二叉樹的前根遍歷序列為ABCDEFG，中根遍歷序列為CBDAEGF，試構(gòu)造出該二叉樹。
31.下述矩陣表示一個無向連通網(wǎng)，試畫出它所表示的連通網(wǎng)及該連通網(wǎng)的最小生成樹。
1 12 5 10 1 8 9 12 8 2 5 9 4 10 2 4
32.給定表（80，90，50，70，75，60，40，100），試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r為空的二叉排序樹，畫出插入完成后的二叉排序樹。
33.試寫出一組鍵值（46，58，15，45，90，18，10，62）應用直接插入排序算法從小到大排序后各趟的結(jié)果。
四、算法設計題(本大題共2小題，每小題7分，共14分)
34.試分別寫出二叉樹的先根遍歷和中根遍歷的遞歸算法。
35.試編寫以單鏈表為存儲結(jié)構(gòu)實現(xiàn)直接選擇排序的算法。
咨詢在線客服