1、東 北 大 學(xué) 繼 續(xù) 教 育 學(xué) 院數(shù)據(jù)結(jié)構(gòu)II X試 卷（作業(yè)考核 線上2）B卷學(xué)習(xí)中心：院校學(xué)號：姓名（共 8 頁）總分題號一二三四五六七得分一、單選題（每小題2分，共10小題，20分） A 1抽象數(shù)據(jù)類型的三個組成部分分別為A數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作B數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)C數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素和數(shù)據(jù)類型D數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型 D 2下列各式中，按增長率由小至大的順序正確排列的是A，n！，2，nBn，2，n，2C2，log n，n，nD2，logn, 2, n A3. 已知指針p和q分別指向某單鏈表中第一個結(jié)點(diǎn)和最后一個結(jié)點(diǎn)。假設(shè)指針s指向另一個單鏈表中某個結(jié)點(diǎn)，則在s所

2、指結(jié)點(diǎn)之后插入上述鏈表應(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； C 4二維數(shù)組A2010采用行優(yōu)先的存儲方法，若每個元素占2個存儲單元，且第1個元素的首地址為200，則元素A89的存儲地址為A374 B576C378 D580 B 5設(shè)有一個順序棧的入棧序列是a、b、c，則3個元素都出棧的可能不同排列個數(shù)為A4 B5C. 6 D. 7 D 6. 設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個數(shù)分別為4，2，1，

3、1 則T中的葉子數(shù)為A5 B6C7 D8 C 7以下說法不正確的是A無向圖中的極大連通子圖稱為連通分量B連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來暫存剛訪問過的頂點(diǎn)C圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點(diǎn)D有向圖的遍歷不可采用廣度優(yōu)先搜索 B 8. 假設(shè)在構(gòu)建散列表時，采用線性探測解決沖突。若連續(xù)插入的n個關(guān)鍵字都是同義詞，則查找其中最后插入的關(guān)鍵字時，所需進(jìn)行的比較次數(shù)為A. n-1 B. n C. n+l D. n+2 D 9設(shè)置溢出區(qū)的文件是A索引非順序文件 BISAM文件CVSAM文件 D順序文件 A 10. 已知一組關(guān)鍵字為25,48,36,72,79,82,23,40,16

4、,35，其中每相鄰兩個為有序子序列。對這些子序列進(jìn)行一趟兩兩歸并的結(jié)果是A.25,36,48,72,23,40,79,82,16,35B.25,36,48,72,16,23,40,79,82,35C.25,36,48,72,16,23,35,40,79,82D.16,23,25,35,36,40,48,72,79,82二、填空題（每小題1分，共10小題，10分）11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是( log2n )。i=1； WHILE(inext=L-next-next;L-next-next=S）。13無表頭結(jié)點(diǎn)的鏈隊(duì)列Q為空的條件是（ Q-real=Q-front=NUL

5、L）。14設(shè)Q0.N-1為循環(huán)隊(duì)列，其頭、尾指針分別為P和R，則隊(duì)Q中當(dāng)前所含元素個數(shù)為（ (R-P+N)%N ）。15一棵含999個結(jié)點(diǎn)的完全二叉樹的深度為（ 10 ）。16在 AOV網(wǎng) 中，存在環(huán)意味著某項(xiàng)活動以自己為先決條件；對程序的數(shù)據(jù)流圖來說，它表明存在（ 死循環(huán) ）。17. 有向圖G可拓?fù)渑判虻呐袆e條件是( 不存在環(huán) )。18如果結(jié)點(diǎn)A有 3個兄弟，而且B是A的雙親，則B的度是（4）。19應(yīng)用回溯與分支限界法解決實(shí)際問題時，在搜索過程中利用判定函數(shù)，也稱為（限界函數(shù)）。20. 若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出

6、序列是( 4231 )。三、應(yīng)用題（每小題6分，共5小題，30分）21比較線性表和棧的基本操作的不同點(diǎn)。答：主要區(qū)別是對插入和刪除操作的限制。如線性表允許在表內(nèi)任一位置進(jìn)行插入和刪除；而隊(duì)列只允許在表尾一端進(jìn)行插入，在表頭一端進(jìn)行刪除；所以也稱隊(duì)列為受限的線性表。表頭為隊(duì)列頭；表尾為隊(duì)列尾。插入 刪除線性表 lnsert(L,i,x) De1ete(L,i)(lin+l) (lin)隊(duì)列 lnsert(L,n+1，x) De1ete(L,1)22有一個二叉樹按層次順序存放在一維數(shù)組中，如下圖所示：試求：（1）該樹的后序遍歷序列。（2）畫出該樹的后序線索樹。1 2 345 6 7 8 9 10

7、11ACBED答：（1)后序遍歷序列CEDBA（2）后序線索樹23分析順序查找算法的“監(jiān)視哨”設(shè)置作用答：為了考慮查找不成功的情況，在每次進(jìn)行關(guān)鍵字的比較前，首先要判斷循環(huán)變量i是否數(shù)組越界，這對算法來說是必要的。如果每步省略數(shù)組下標(biāo)是否越界的判斷，則可以大大提高算法運(yùn)行的效率。為此，可以利用預(yù)留的0號單元，作為所設(shè)的“監(jiān)視哨”控制循環(huán)變量i的出界。假設(shè)數(shù)據(jù)從后向前比較，監(jiān)視哨設(shè)在數(shù)組低端L.elem0=k將算法中的判斷語句while(inext ) /鏈表不空且p = L-next;（1）while( knext; +k; / whileif (p &（3）) / n!=0時才需要修改指針h

8、a = 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）k= 1;（2）查找第am個節(jié)點(diǎn)（3）p-next（4）l-next（5）將第a1結(jié)點(diǎn)鏈接到bn節(jié)點(diǎn)之后五、算法閱讀題（本題10分）27設(shè)任意n個整數(shù)存放于數(shù)組A(1:n)中，閱讀算法，指出功能及分析指針i和j的作用。void Arran

9、ge(int A,int n) / n個整數(shù)存于數(shù)組A中int i=0,j=n-1,x; / 數(shù)組下標(biāo)從0開始while(ij)while(i0) i+;while(ij & Aj0) j-;if(ij) / 交換Ai 與Ajx=Ai; Ai+=Aj; Aj-=x;/ if/ while/Arrange（1）功能：答：1.把數(shù)組中從A(1:n)A(1:0）中第一個大于0的數(shù)，賦給數(shù)組中從A(1:0)（1：n)中第一個小于0的后面第一個數(shù)組；2.把數(shù)組中從A(1:0)A(1:n）中第一個小于0的數(shù),賦給數(shù)組中從A(1:n)A(1:0）中第一個大于0的后面第一個數(shù)組；（2）指針i和j的作用：答：I

10、為計數(shù)器作用，從0開始遞增1關(guān)系，遞增到數(shù)組中從低到高第一個小于0截止J為計數(shù)器作用，從大數(shù)開始遞減1關(guān)系，遞減到數(shù)組中從高到低第一個大于0截止六、算法設(shè)計題（本題10分）28設(shè)計算法purge_Sq實(shí)現(xiàn)刪除順序表SqList中重復(fù)元素，指出其算法的時間復(fù)雜度。答：voidpurge-Sq（SqList&L）/刪除順序表L中的重復(fù)元素k=-1；/指示新表的表尾for(i=0;iL.length；+I)/順序考察表中每個元素j=0;while(jk）/k=-1表明當(dāng)前考察的是第一個元素L.elem+k=L.e1emi；L.length=k+l;/修改表長此算法的時間復(fù)雜度為0(L.1ength2）。七、算法設(shè)計題（本題10分）29設(shè)計算法從圖的鄰接表結(jié)構(gòu)轉(zhuǎn)換成鄰接矩陣結(jié)構(gòu)的算法。答：voidAdjLi