數(shù)據(jù)結(jié)構(gòu)II試卷(B).doc

東 北 大 學(xué) 繼 續(xù) 教 育 學(xué) 院 數(shù)據(jù)結(jié)構(gòu)II 試 卷（作業(yè)考核 線上） B 卷（共 10 頁） 總分題號(hào)一二三四五六七得分一、單選題（每小題2分，共10小題，20分） A 1抽象數(shù)據(jù)類型的三個(gè)組成部分分別為 A數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作 B數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu) C數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素和數(shù)據(jù)類型 D數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型 D 2下列各式中，按增長(zhǎng)率由小至大的順序正確排列的是 A，n！，2n ，n3/2 Bn3/2，2n，nlogn，2100 C2n，log n，nlogn，n3/2 D2100，logn, 2n, nn A 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í)行的語句為 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)先的存儲(chǔ)方法，若每個(gè)元素占2個(gè)存儲(chǔ)單元，且第1個(gè)元素的首地址為200，則元素A89的存儲(chǔ)地址為A374 B576C378 D580 B 5設(shè)有一個(gè)順序棧的入棧序列是a、b、c，則3個(gè)元素都出棧的可能不同排列個(gè)數(shù)為 A4 B5 C. 6 D. 7 D 6. 設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1 則T中的葉子數(shù)為 A5 B6 C7 D8 C 7以下說法不正確的是 A無向圖中的極大連通子圖稱為連通分量 B連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來暫存剛訪問過的頂點(diǎn) C圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點(diǎn) D有向圖的遍歷不可采用廣度優(yōu)先搜索 B 8. 假設(shè)在構(gòu)建散列表時(shí)，采用線性探測(cè)解決沖突。若連續(xù)插入的n個(gè)關(guān)鍵字都是同義詞，則查找其中最后插入的關(guān)鍵字時(shí)，所需進(jìn)行的比較次數(shù)為 A. n-1B. n C. n+lD. n+2 B 9設(shè)置溢出區(qū)的文件是 A索引非順序文件 BISAM文件 CVSAM文件 D順序文件 A 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,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ù)量級(jí)是( log2n )。i=1； WHILE(inest=L-next-next；L-next-next =S）。13無表頭結(jié)點(diǎn)的鏈隊(duì)列Q為空的條件是（Q-real=Q-front=NULL）。14設(shè)Q0.N-1為循環(huán)隊(duì)列，其頭、尾指針分別為P和R，則隊(duì)Q中當(dāng)前所含元素個(gè)數(shù)為（ （R-P+N）% N ）。15一棵含999個(gè)結(jié)點(diǎn)的完全二叉樹的深度為（10）。16在 AOV網(wǎng) 中，存在環(huán)意味著某項(xiàng)活動(dòng)以自己為先決條件；對(duì)程序的數(shù)據(jù)流圖來說，它表明存在（ 死循環(huán) ）。17. 有向圖G可拓?fù)渑判虻呐袆e條件是( 不存在環(huán) )。18如果結(jié)點(diǎn)A有 3個(gè)兄弟，而且B是A的雙親，則B的度是（ 4 ）。19應(yīng)用回溯與分支限界法解決實(shí)際問題時(shí)，在搜索過程中利用判定函數(shù)，也稱為（限界函數(shù)）。20. 若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是( 4231 )。 三、應(yīng)用題（每小題6分，共5小題，30分）21比較線性表和棧的基本操作的不同點(diǎn)。解答：主要區(qū)別是對(duì)插入和刪除操作的限制。 如線性表允許在表內(nèi)任一位置進(jìn)行插入和刪除；而隊(duì)列只允許在表尾一端進(jìn)行插入，在表頭一端進(jìn)行刪除；所以也稱隊(duì)列為受限的線性表。表頭為隊(duì)列頭；表尾為隊(duì)列尾。 插 入 刪 除 線性表 Insert(L,i,x)Delete(L,i) (1in+1) (1in) 隊(duì)列 Insert(L,n+1,x) Delete(L,1)22有一個(gè)二叉樹按層次順序存放在一維數(shù)組中，如下圖所示：試求：（1）該樹的后序遍歷序列。 （2）畫出該樹的后序線索樹。1 2 3 4 5 6 7 8 9 10 11 ACBED解答：（1）后序遍歷序列 C E D B A （2）后序線索樹 ABEDC23分析順序查找算法的“監(jiān)視哨”設(shè)置作用解答：為了考慮查找不成功的情況,在每次進(jìn)行關(guān)鍵字的比較前，首先要判斷循環(huán)變量i是否數(shù)組越界，這對(duì)算法來說是必要的。如果每步省略數(shù)組下標(biāo)是否越界的判斷，則可以大大提高算法運(yùn)行的效率。為此，可以利用預(yù)留的0號(hào)單元，作為所設(shè)的“監(jiān)視哨”控制循環(huán)變量i的出界。 假設(shè)數(shù)據(jù)從后向前比較，監(jiān)視哨設(shè)在數(shù)組低端 L.elem 0 = k 將算法中的判斷語句 while (i next ) / 鏈表不空且 p = L-next; （1） while( knext; +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）k = 1;（2）查找第am個(gè)結(jié)點(diǎn)（3）p-next（4）L-next（5）將第 a1 結(jié)點(diǎn)鏈接到 bn 結(jié)點(diǎn)之后五、算法閱讀題（本題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開始 while(ij) while(i0) i+; while(ij & Aj0) j-; if(iA(1:0)中第一個(gè)大于0的數(shù)，賦給數(shù)組中從A(1:0)-A(1:n)中第一個(gè)小于0的后面第一個(gè)數(shù)組；2.把數(shù)組中從A(1:0)-A(1:n)中第一個(gè)小于0的數(shù)，賦給數(shù)組中從A(1:n)-A(1:0)中第一個(gè)大于0的后面第一個(gè)數(shù)組；（2）指針i和j的作用：解答：I為計(jì)數(shù)器作用，從0開始遞增1關(guān)系，遞增到數(shù)組中從低到高第一個(gè)小于0截止J為計(jì)數(shù)器作用，從大數(shù)開始遞減1關(guān)系，遞減到數(shù)組中從高到低第一個(gè)大于0截止六、算法設(shè)計(jì)題（本題10分）28設(shè)計(jì)算法purge_Sq實(shí)現(xiàn)刪除順序表SqList中重復(fù)元素，指出其算法的時(shí)間復(fù)雜度。解答：void purge_Sq( SqList &L ) / 刪除順序表L中的重復(fù)元素 k = -1;/ k 指示新表的表尾 for (i=0; iL.length; +i) / 順序考察表中每個(gè)元素 j=0; while(jk )/ k=-1 表明當(dāng)前考察的是第一個(gè)元素 L.elem+k = L.elemi; / for L.length = k+1;/ 修改表長(zhǎng) / purge_Sq 此算法的時(shí)間復(fù)雜度為O (L.length2 )。七、算法設(shè)計(jì)題（本題10分）29設(shè)計(jì)算法從圖的鄰接表結(jié)構(gòu)轉(zhuǎn)換成鄰接矩陣結(jié)構(gòu)的算法。解答：#include #include #include int a100100;/鄰接矩陣的載體 typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode; /表結(jié)點(diǎn) typedef struct VNode char data; ArcNode *firstarc; VNode,AdjList20;/頭結(jié)點(diǎn) typedef struct AdjList vertices; int vexnum,arcnum; ALGraph;/鄰接表 int LocateVex(ALGraph G,char e) int i; for(i=0;iG.vexnum;i+) if(G.verticesi.data=e) return i;/找到后 返回i return -1; void CreatAdList(ALGraph &G) /根據(jù)輸入的有向圖G的頂點(diǎn)數(shù)及邊數(shù)，建立圖G的鄰接表 int i,j,k; char v1,v2; ArcNode *s,*p; scanf(%d%d,&G.vexnum,&G.arcnum); getchar(); for(i=0;iG.vexnum;i+) /初始化頭結(jié)點(diǎn) scanf(%c,&G.verticesi.data); getchar(); G.verticesi.firstarc=NULL; for(i=0;iG.vexnum;i+)/輸出一遍這些頭 printf(%c ,G.verticesi.data); printf(n); for(k=0;kadjvex=j; s-nextarc=NULL; p=G.verticesi.firstarc; if(!p) G.verticesi.firstarc = s; else while(p-nextarc) p=p-nextarc; p-nextarc=s; void trans(ALGraph G) /轉(zhuǎn)換函數(shù) int i,j; ArcNode *p; for(i=0;i=G.vexnum;i+)/先初始化，全部賦值為0 for(j=0;j=G.vexnum;j+) aij=0; for(i=0;iadjvex=1; p=p