《數(shù)據(jù)結(jié)構(gòu)-學(xué)期樣卷與考研樣題.pdf》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、學(xué)期樣卷學(xué)期樣卷一一、簡答問題(15分,每小題5分)1．說明在帶頭結(jié)點(diǎn)單鏈表L中以下三個(gè)概念的關(guān)系:頭指針,頭結(jié)點(diǎn),首元素結(jié)點(diǎn)。2．簡述在圖的遍歷中,設(shè)置訪問標(biāo)志數(shù)組的作用。3．說明具有n個(gè)結(jié)點(diǎn)的二叉樹Bt,若采用二叉鏈表存儲表示法,其空鏈域的數(shù)目,并寫出求解過程。二、單項(xiàng)選擇題(10分,每小題1分)1．有一個(gè)帶頭結(jié)點(diǎn)的單鏈表HEAD,則判斷其是否為空鏈表的條件是。A．HEAD==NULLB．HEAD->NEXT==NULLC．HEAD->NEXT==HEADD．HEAD!=NULL2．若線性表最常用的操作是存取第i個(gè)元素及其前趨的值,可采用存儲方式最節(jié)

2、省時(shí)間。A．單向鏈表B．雙向鏈表C．單向循環(huán)鏈表D．順序表3．某個(gè)棧的入棧的序列為A,B,C,D,E,則可能的出棧序列是。A．ADBECB．EBCADC．BCDEAD．EABCD4．廣義表(a,(b),((c)))的表尾是。A．((c))B．(((c)))C．(c)D．((b),((c)))5．設(shè)串s1=′ABCDEFG′,s2=′PQRST′,函數(shù)con(x,y)返回x和y串的連接串,subs(s,i,j)返回串s的從序號i的字符開始的j個(gè)字符組成的子串,len(s)返回串s的長度,則con(subs(s1,2,len(s2)),subs(s1,len

3、(s2),2))的結(jié)果串是。A．BCDEFB．BCDEFGC．BCPQRSTD．BCDEFEF6．一棵深度為h的二叉樹,其結(jié)點(diǎn)總數(shù)最多為。A．2hB．2h+1C．2h-1D．2h-17．AVL樹是一種平衡的二叉排序樹,樹中任一結(jié)點(diǎn)的。A．左、右子樹的高度均相同B．左、右子樹高度差的絕對值不超過1C．左子樹的高度均大于右子樹的高度D．左子樹的高度均小于右子樹的高度8．在關(guān)鍵字隨機(jī)分布的前提下,用二叉排序樹的方法進(jìn)行查找,其平均查找長度同數(shù)量級相當(dāng)。A．順序查找B．折半查找C．快速查找D．都不正確9．對于一個(gè)有向圖,若一個(gè)頂點(diǎn)的度為k,出度為k,則對應(yīng)的鄰接

4、表中,該結(jié)點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)12為。A．kB．kC．k-kD．k+k121212學(xué)期樣卷一·367·10．下列關(guān)鍵字序列中,是堆。A．16,72,31,23,94,53,B．94,23,31,72,16,53C．16,53,23,94,31,72D．16,23,53,31,94,72三、填空題(20分,每空2分)1．如下程序段:for(i=1;i?n-1;i++)for(j=i+1;j?n;j++)x=x+1;其中語句x=x+1執(zhí)行的語句頻度為。2．在循環(huán)單鏈表La(La為頭指針)中,指針p所指結(jié)點(diǎn)為表尾結(jié)點(diǎn)的條件是。3．在一棵度為3的樹中,其中度為3

5、的結(jié)點(diǎn)數(shù)為2個(gè),度為2的結(jié)點(diǎn)數(shù)為1個(gè),度為1的結(jié)點(diǎn)數(shù)為2個(gè),則度為0的結(jié)點(diǎn)數(shù)為個(gè)。4．已知一個(gè)有向圖G的鄰接矩陣表示G．a(chǎn)rcs[M][M],要刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的弧,則需要做的運(yùn)算是。5．在待排序的元素序列基本有序的前提下,效率最高的排序方法是。6．當(dāng)兩個(gè)對頂棧共享一個(gè)存儲區(qū)時(shí),可利用一維數(shù)組stack[M]實(shí)現(xiàn)(下標(biāo)從0到M-1),兩個(gè)棧的棧頂指針分別為top[1]與top[2],則棧滿的條件是。7．若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列,且當(dāng)前的rear和front的值為0和3,當(dāng)從隊(duì)列中刪除1個(gè)元素后,front的值為,再加入2個(gè)元素后,re

6、ar的值為。8．設(shè)有一個(gè)二維數(shù)組A[1．．12,1．．10],采用以行序?yàn)橹餍虼鎯?每個(gè)數(shù)據(jù)元素占有2個(gè)字節(jié),該數(shù)組的首元素A[1][1]的地址為1200,則A[6,5]的地址為。9．設(shè)一哈希表表長M為100,用除留余數(shù)法構(gòu)造哈希函數(shù),即H(K)=K%P,為使函數(shù)具有較好性能,P應(yīng)選。四、構(gòu)造題(25分,每小題5分)1．給定權(quán)值{8,12,4,5,26,16,9},構(gòu)造一棵帶權(quán)路徑長度最短的二叉樹,并計(jì)算其帶權(quán)路徑長度。2．將如下所示二叉樹轉(zhuǎn)換成相應(yīng)的森林。3．已知關(guān)鍵字集合(12,2,16,30,8,28,4,10,20,6,18),用快速排序從小到大

7、排序(選第一個(gè)記錄為基準(zhǔn)進(jìn)行劃分),寫出第一趟排序結(jié)束時(shí)的序列。4．對以下關(guān)鍵字序列建立一個(gè)長度為10的哈希表(SUN,MON,TUE,WED,THU,FRI,SAT),哈希函數(shù)為H(K)=(K中第一個(gè)字母在字母表中的序號)%7,用線性探測法處理沖突,并計(jì)算在等概率情況下查找成功時(shí)的平均查找長度。5．已知無向網(wǎng)如下所示,用普里姆算法給出最小生成樹(從結(jié)點(diǎn)A開始)?！?68·學(xué)期樣卷五、算法分析題(10分)閱讀下面函數(shù)段,并回答有關(guān)問題。其中BiTree為二叉鏈表類型,并假設(shè)二叉樹root有n個(gè)結(jié)點(diǎn)。1．簡要說明程序功能。(5分)2．進(jìn)隊(duì)操作、出隊(duì)操作和打

8、印操作各執(zhí)行了多少次?(3分)3．給出算法的時(shí)間復(fù)雜度。(2分)voidproc