?數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2011年1月真題（02142）

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2011年1月真題及答案解析（02142）

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2011年1月真題及答案（02142），該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考歷年真題試卷，包含答案及詳細解析。

一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。

1.在順序表中查找第i個元素，時間效率最高的算法的時間復(fù)雜度為(　　)

A.O(1)

B.

C.

2.樹形結(jié)構(gòu)中，度為0的結(jié)點稱為(　　)

A.樹根
B.葉子
C.路徑
D.二叉樹

3.已知有向圖G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E={，，，，，，，，}，則圖G的拓撲序列是(　　)

A.V1，V3，V4，V6，V2，V5，V7
B.V1，V3，V2，V6，V4，V5，V7
C.V1，V3，V4，V5，V2，V6，V7
D.V1，V2，V5，V3，V4，V6，V7

4.有關(guān)圖中路徑的定義，表述正確的是(　　)

A.路徑是頂點和相鄰頂點偶對構(gòu)成的邊所形成的序列
B.路徑是不同頂點所形成的序列
C.路徑是不同邊所形成的序列
D.路徑是不同頂點和不同邊所形成的集合

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;           do{ x=x+5*i; i--; }while( i>0 );的時間復(fù)雜度為(　　)

A.O(1)
B.O(n)

C.

D.

8.與串的邏輯結(jié)構(gòu)不同的數(shù)據(jù)結(jié)構(gòu)是(　　)

A.線性表
B.棧
C.隊列
D.樹

9.二叉樹的第i(i≥1)層上所擁有的結(jié)點個數(shù)最多為(　　)

A.

C.

D.-1

10.設(shè)單鏈表中指針p指向結(jié)點A，若要刪除A的直接后繼，則所需修改指針的操作為(　　)

A.p->next=p->next->next
B.p=p->next
C.p=p->next->next
D.p->next=p

11.下列排序算法中，某一趟結(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.″BCDEF″
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.1
B.3
C.4
D.5

15.數(shù)據(jù)表A中每個元素距其最終位置較近，則最省時間的排序算法是(　　)

A.堆排序
B.插入排序
C.直接選擇排序
D.快速排序

二、填空題(本大題共13小題，每小題2分，共26分)請在每小題的空格中填上正確答案。錯填、不填均無分。

11.下列程序段的時間復(fù)雜度為________。i=1;while( i <n)          i=i*2;

12.向一個長度為n的順序表中第i(1≤i≤n)個元素之前插入一個元素時，需向后移動________個元素。

13.在循環(huán)雙鏈表中，刪除最后一個結(jié)點，其算法的時間復(fù)雜度為________。

14.隊列的插入操作在隊列的________部分進行。

15.一個棧的輸入序列是1，2，3，…，n，輸出序列的第一個元素是n，則第i個輸出元素為________。

16.一個10階對稱矩陣A，采用行優(yōu)先順序壓縮存儲下三角，a00為第一個元素，其存儲地址為1，每個元素占有1個存儲地址空間，則a85的地址為________。

17.設(shè)字符串S=″I□AM□A□STUDENT″(其中□表示空格字符)，則S的長度為________。

18.在樹形結(jié)構(gòu)中，沒有后繼的結(jié)點是________結(jié)點。

19.一棵深度為n(n>1)的滿二叉樹中共有________個結(jié)點。

110.在無向圖中，如果從頂點v到頂點v"有路徑，則稱v和v′是________。

111.無向完全圖G采用________存儲結(jié)構(gòu)較省空間。

112.在順序查找、二分查找、索引查找和散列查找四種查找方法中，平均查找長度與元素個數(shù)沒有關(guān)系的查找方法是________。

113.快速排序最好情況下的時間復(fù)雜度為________。

三、應(yīng)用題(本大題共5小題，每小題6分，共30分)

21.稀疏矩陣A如下，寫出矩陣A的三元組表及矩陣A的轉(zhuǎn)置矩陣的三元組表。

22.一棵二叉樹的前根遍歷序列為ABCDEFG，中根遍歷序列為CBDAEGF，試構(gòu)造出該二叉樹。

23.下述矩陣表示一個無向連通網(wǎng)，試畫出它所表示的連通網(wǎng)及該連通網(wǎng)的最小生成樹。

24.給定表(80，90，50，70，75，60，40，100)，試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r為空的二叉排序樹，畫出插入完成后的二叉排序樹。

25.試寫出一組鍵值(46，58，15，45，90，18，10，62)應(yīng)用直接插入排序算法從小到大排序后各趟的結(jié)果。

四、算法設(shè)計題(本大題共2小題，每小題7分，共14分)

31.試分別寫出二叉樹的先根遍歷和中根遍歷的遞歸算法。

32.試編寫以單鏈表為存儲結(jié)構(gòu)實現(xiàn)直接選擇排序的算法。