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