東 北 大 學(xué) 繼 續(xù) 教 育 學(xué) 院
數(shù)據(jù)結(jié)構(gòu)II X 試 卷（作業(yè)考核 線(xiàn)上2） B 卷
學(xué)習(xí)中心： 院校學(xué)號(hào)： 姓名
（共 8 頁(yè)）
總分 題號(hào) 一 二 三 四 五 六 七
得分
一、單選題（每題2分，共10小題，20分）
[ ] 1．抽象數(shù)據(jù)類(lèi)型的三個(gè)組成部分分別為
A．?dāng)?shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作
B．?dāng)?shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)
C．?dāng)?shù)據(jù)項(xiàng)、數(shù)據(jù)元素和數(shù)據(jù)類(lèi)型
D．?dāng)?shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類(lèi)型
[ ] 2．下列各式中，按增長(zhǎng)率由小至大的順序正確排列的是
A． ，n！，2n ，n3/2 B．n3/2，2n，nlogn，2100
C．2n，log n，nlogn，n3/2 D．2100，logn, 2n, nn
[ ] 3. 已知指針p和q分別指向某單鏈表中第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)。假設(shè)指針s指向另一個(gè)單鏈表中某個(gè)結(jié)點(diǎn)，則在s所指結(jié)點(diǎn)之后插入上述鏈表應(yīng)執(zhí)行的語(yǔ)句為
A. q->next=s->next；s->next=p； B. s->next=p；q->next=s->next；
C. p->next=s->next；s->next=q； D. s->next=q；p->next=s->next；
[ ] 4．二維數(shù)組A[20][10]采用行優(yōu)先的存儲(chǔ)方法，若每個(gè)元素占2個(gè)存儲(chǔ)單元，且第1個(gè)元素的首地址為200，則元素A[8][9]的存儲(chǔ)地址為
A．374 B．576
C．378 D．580
[ ] 5．設(shè)有一個(gè)順序棧的入棧序列是a、b、c，則3個(gè)元素都出棧的可能不同排列個(gè)數(shù)為
A．4 B．5
C. 6 D. 7
[ ] 6. 設(shè)樹(shù)T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1 則T中的葉子數(shù)為
A．5 B．6
C．7 D．8
[ ] 7．以下說(shuō)法不正確的是
A．無(wú)向圖中的極大連通子圖稱(chēng)為連通分量
B．連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫存剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn)
C．圖的深度優(yōu)先搜索中一般要采用棧來(lái)暫存剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn)
D．有向圖的遍歷不可采用廣度優(yōu)先搜索
[ ] 8. 假設(shè)在構(gòu)建散列表時(shí)，采用線(xiàn)性探測(cè)解決沖突。若連續(xù)插入的n個(gè)關(guān)鍵字都是同義詞，則查找其中最后插入的關(guān)鍵字時(shí)，所需進(jìn)行的比較次數(shù)為
A. n-1 B. n C. n+1 D. n+2
[ ] 9．設(shè)置溢出區(qū)的文件是
A．索引非順序文件 B．ISAM文件
C．VSAM文件 D．順序文件
[ ] 10. 已知一組關(guān)鍵字為{25,48,36,72,79,82,23,40,16,35}，其中每相鄰兩個(gè)為有序子序列。對(duì)這些子序列進(jìn)行一趟兩兩歸并的結(jié)果是
A.{25,36,48,72,23,40,79,82,16,35}
B.{25,36,48,72,16,23,40,79,82,35}
C.{25,36,48,72,16,23,35,40,79,82}
D.{16,23,25,35,36,40,48,72,79,82}
二、填空題（每題1分，共10小題，10分）
11.下面程序段中帶下劃線(xiàn)的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是( )。
i=1； WHILE(i<n) i=i*2;
12．假設(shè)帶頭結(jié)點(diǎn)的非空單循環(huán)鏈表中僅設(shè)尾指針L，則在第1個(gè)結(jié)點(diǎn)之前插入指針s所指結(jié)點(diǎn)的語(yǔ)句依次是（ ）。
13．無(wú)表頭結(jié)點(diǎn)的鏈隊(duì)列Q為空的條件是（ ）。
14．設(shè)Q[0..N-1]為循環(huán)隊(duì)列，其頭、尾指針?lè)謩e為P和R，則隊(duì)Q中當(dāng)前所含元素個(gè)數(shù)為（ ）。
15．一棵含999個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（ ）。
16．在AOV網(wǎng) 中，存在環(huán)意味著某項(xiàng)活動(dòng)以自己為先決條件；對(duì)程序的數(shù)據(jù)流圖來(lái)說(shuō)，它表明存在（ ）。
17. 有向圖G可拓?fù)渑判虻呐袆e條件是( )。
18．如果結(jié)點(diǎn)A有 3個(gè)兄弟，而且B是A的雙親，則B的度是（ ）。
19．應(yīng)用回溯與分支限界法解決實(shí)際問(wèn)題時(shí)，在搜索過(guò)程中利用判定函數(shù)，也稱(chēng)為（ ）。
20. 若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是( )。
三、應(yīng)用題（每題6分，共5小題，30分）
21．比較線(xiàn)性表和棧的基本操作的不同點(diǎn)。
22．有一個(gè)二叉樹(shù)按層次順序存放在一維數(shù)組中，如下圖所示：
試求：（1）該樹(shù)的后序遍歷序列。
（2）畫(huà)出該樹(shù)的后序線(xiàn)索樹(shù)。
1 2 3 4 5 6 7 8 9 10 11
A C B E D
23．分析順序查找算法的“監(jiān)視哨”設(shè)置作用
24．對(duì)n個(gè)整數(shù)的序列進(jìn)行直接選擇排序。
（1）算法描述。
（2）并給出實(shí)例（52 49 80 36 14 58 61 23 ）的排序過(guò)程。
25. 已知有一個(gè)10個(gè)頂點(diǎn)的連通圖，頂點(diǎn)編號(hào)為1至10，其邊的關(guān)系集合表示為{（1，2）（1，3），（1，8），（2，4），（3，9），（3，10），（5，7），（6，7），（7，8），（8，9）}，試求：畫(huà)出該連通圖及以頂點(diǎn)1為根的深度優(yōu)先生成樹(shù)。
四、算法閱讀題（本題10分）
26．設(shè)計(jì)算法實(shí)現(xiàn)以鏈表作存儲(chǔ)結(jié)構(gòu)，將線(xiàn)性表中前m個(gè)元素和后n個(gè)元素進(jìn)行整體互換，即(a1,…,am,b1,…,bn) 改變成(b1,…,bn,a1,…,am)。閱讀算法，在橫線(xiàn)處填入語(yǔ)句或注釋。
void exchange_L( Linklist &L，int m ) {
// 本算法實(shí)現(xiàn)單鏈表中前m個(gè)結(jié)點(diǎn)和后n個(gè)結(jié)點(diǎn)的整體互換
if ( m && L->next ) { // 鏈表不空且
p = L->next;
（1）
while( k< m && p ) { //（2）
p = p->next; ++k;
} // while
if (p && （3）) { // n!=0 時(shí)才需要修改指針
ha = L->next; // 以指針 ha 記a1結(jié)點(diǎn)的位置
（4）= p->next; // 將 b1 結(jié)點(diǎn)鏈接在頭結(jié)點(diǎn)之后
p->next = NULL; // 設(shè)am的后繼為空
q = L->next; // 令q 指向 b1結(jié)點(diǎn)
while (q->next)
q = q->next; // 查找 bn 結(jié)點(diǎn)
q->next = ha; // （5）
} // if(p)
} // if(m)
} // exchange_L
（1）
（2）
（3）
（4）
（5）
五、算法閱讀題（本題10分）
27．設(shè)任意n個(gè)整數(shù)存放于數(shù)組A(1:n)中，閱讀算法，指出功能及分析指針i和j的作用。
void Arrange(int A[],int n) {
// n個(gè)整數(shù)存于數(shù)組A中
int i=0,j=n-1,x; // 數(shù)組下標(biāo)從0開(kāi)始
while(i<j){
while(i<j && A[i]>0) i++;
while(i<j && A[j]<0) j--;
if(i<j) { // 交換A[i] 與A[j]
x=A[i]; A[i++]=A[j]; A[j--]=x;
}// if
}// while
}//Arrange
（1）功能：
（2）指針i和j的作用：
六、算法設(shè)計(jì)題（本題10分）
28．設(shè)計(jì)算法purge_Sq實(shí)現(xiàn)刪除順序表SqList中重復(fù)元素，指出其算法的時(shí)間復(fù)雜度。
七、算法設(shè)計(jì)題（本題10分）
29．設(shè)計(jì)算法從圖的鄰接表結(jié)構(gòu)轉(zhuǎn)換成鄰接矩陣結(jié)構(gòu)的算法。
