數(shù)據(jù)結(jié)構(gòu)期末試題及答案

1、 E 卷一、單項選擇題一、單項選擇題 1、線性表若采用鏈?zhǔn)浇Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址( )。 A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的 C. 一定是不連續(xù)的 D. 連續(xù)不連續(xù)都可以2、判定一個棧ST(最多元素為m0)為空的條件是( )。 A. ST-top!=0 B. ST-top=0 C. ST-top!=m0 D. ST-top=m03、數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從1到8，列j下標(biāo)從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A85的起始地址為( )。 A. SA+141 B. SA+144 C. SA+222 D. SA+225

2、4、設(shè)哈希表長m=14，哈希函數(shù)H(key)=key%11。表中已有4個結(jié)點： addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7 其余地址為空如用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點的地址是( )。 A. 8 B. 3 C. 5 D. 95、在線索化二叉樹中，t所指結(jié)點沒有左子樹的充要條件是( )。 A. t-left=NULL B. t-ltag=1 C. t-ltag=1且t-left=NULL D. 以上都不對6、將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時，通常需要使用( )。 A. 棧 B. 隊列 C. 鏈表 D. 樹7、有一個有序表為1,3,9,1

3、2,32,41,45,62,75,77,82,95,100,當(dāng)二分查找值為82的結(jié)點時，( )次比較后查找成功。 A. 1 B. 2 C. 4 D. 88、對一個滿二叉樹，m個樹葉，n個結(jié)點，深度為h，則( )。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-19、如果要求一個線性表既能較快地查找，又能適應(yīng)動態(tài)變化的要求，可以采用_查找方法。 A. 分塊 B. 順序 C. 二分 D. 散列10、快速排序方法在( )情況下最不利于發(fā)揮其長處。 A. 要排序的數(shù)據(jù)量太大 B. 要排序的數(shù)據(jù)中含有多個相同值 C. 要排序的數(shù)據(jù)已基本有序 D. 要排序的數(shù)據(jù)個數(shù)為奇數(shù)11、在

4、含有n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為_.A.e B.2e C.-e D. -2e2n2n12.假設(shè)一個有n個頂點和e條弧的有向圖用鄰接表表示，則刪除與某個頂點相關(guān)的所有弧的時間復(fù)雜度是_.iVA.O(n) B.O(e) C.O(n+e) D.O(n*e)13. 用某種排序方法對關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進行排序時，序列的變化情況：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84則所采用的排序方法是_.A. 選擇排序 B. 希爾排

5、序 C. 歸并排序 D. 快速排序 14. 適宜于對動態(tài)查找表進行高效率查找的組織結(jié)構(gòu)是_.A.有序表 B. 分塊有序表 C. 三叉排序表 D.線性鏈表15. 不定長文件是指_.A. 文件的長度不固定 B.記錄的長度不固定C. 字段的長度不固定 D.關(guān)鍵字項的長度不固定二、填空題二、填空題16、對數(shù)據(jù)間關(guān)系的描述是數(shù)據(jù)的邏輯結(jié)構(gòu)，形式地可以用一個二元組 B=（D，R）來表示，其中D表示_；R表示_。17、數(shù)據(jù)結(jié)構(gòu)的存儲一有兩種，分為_和_. 18、評價一個數(shù)據(jù)結(jié)構(gòu)，基本來說有兩條，一條是_，二是_。19、棧的類型說明為： typedef struc stack datatype s(maxle

6、n); int len; stack; 則：POP（stack st）;算法是： if st.len=0 printf(“underflow” ) else_;20、二叉樹的第i層上至多有_結(jié)點，深度為k的二叉樹至多有_結(jié)點。21、圖的遍歷主要有_和_兩種.22、在hq的鏈隊中，判定只有一個結(jié)點的條件是_。23、在散列函數(shù)H(key)=key%p中，p應(yīng)取_。24、對于長度為n的線性表，若采用二分法查找，則時間復(fù)雜度為_；若采用分塊查找(假定總塊數(shù)和每塊長度均接近n的平方根)，則時間復(fù)雜度為_。三、三、解答操作題解答操作題（每小題（每小題 5 5 分，共分，共 2020 分）分）2525、已知

7、一個無向圖的頂點集為、已知一個無向圖的頂點集為a,b,c,d,e,a,b,c,d,e,其鄰接矩陣如下所示：其鄰接矩陣如下所示：（1）畫出該圖的圖形。（2）根據(jù)鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，并寫出遍歷序列。26、把下列二叉樹換成二森林，畫出圖形0110110110110000100110010edcba27、已知一個散列表如下表示：35203348590 1 2 3 4 5 6 7 8 9 10 11 12其散列函數(shù)h(key)=key%13, 處理沖突的方法為雙重散列法，探查序列為：=(h(key)+i*h (key)%m i=0,1,m-1ih1其中h (key)=ke

8、y%11+11回答以下問題：（1）對表中關(guān)鍵字35，20，33 和 48進行查找時，所需要進行的比較次數(shù)各為多少？（2）該散列表在等概率查找時查找成功的平均查找長度為多少？28、已知序列17,18,60,40,7,32,73,65,85,請給出采用起泡排序法對該序列作升序排序時的每一趟的結(jié)果。四、算法閱讀題四、算法閱讀題( (每小題每小題 6 6 分，共分，共 1212 分分) )29、面給出了起泡排序算法，請?zhí)顚懰惴ㄖ械目湛颍顾惴ㄕ_。 struct node intkey;datatype info; node,*lnode；int i，j; int flag;nodeX;node Rn

9、; 每循環(huán)一次作一次起泡 循環(huán) i以1為步長，從1到n1，執(zhí)行下列語句 (1)() (2)循環(huán) j以1為步長，()，執(zhí)行 若()Rj.key 則flag 1； XRj；()；Rj1 X (3)若() 則跳出循環(huán) 算法結(jié)束 30、下面給出了在對稱序穿線樹中找指定結(jié)點在后序下的前驅(qū)算法，請?zhí)顚懰惴ㄖ械目湛?，使算法正確。 struct node datatype info;node *llink，*rlink; *lnode； lnode p;p指向指定結(jié)點lnode q;q指向指定結(jié)點在后序下的前驅(qū) 若p-rlink0 則()，算法結(jié)束 否則q p (1)循環(huán) 當(dāng)()時，反復(fù)執(zhí)行 () (2)()

10、 算法結(jié)束五、五、算法設(shè)計題（共算法設(shè)計題（共 8 8 分）分）31.設(shè)有一個循環(huán)雙鏈表，其中有一結(jié)點的指針為 p,編寫一個函數(shù) p 與其右邊的一個結(jié)點進行交換。結(jié)點結(jié)構(gòu)為E 卷一、單項選擇題1. D 2. B 3. C 4. D 5. B 6. A 7. C 8. D 9. A 10. C 11.D 12. C 13. D 14. C 15. B二、填空題16 數(shù)據(jù)集合 數(shù)據(jù)間的關(guān)系 17 順序 非順序 18 時間復(fù)雜度 空間復(fù)雜度 19 st.len=st.len-1 20 2i-1 2k-1 21 深度 廣度 22 hq-front=hq-rear 23 素數(shù) 24 O(log2n) O

11、( n )三、解答操作題（每小題 5 分，共 20 分） 25、 深度優(yōu)先遍歷序列為：abdce; 廣度優(yōu)先遍歷序列為：abedc26、 27、答：（1）比較次數(shù)分別為 3、2、1、1。（2）平均查找長度 ASL=(3+2+1+1+2)/5=1.828、 初始：17，18，60，40，7，32，73，65，85 第 1 趟：17，18，40，7，32，60，65，73，85 第 2 趟：17，18，7，32，40，60，65，73，85 第 3 趟：17，7，18，32，40，60，65，73，85 第 4 趟：7，17，18，32，40，60，65，73，85 第 5 趟：7，17，18，32，40，60，65，73，85四、算法閱讀題（每小題 6 分，共 12 分）29(1)flag = 0； (2)1 到 n-1； (3)Rj1.key； (4)Rj =Rj1；(5)flag030q = p-.rlinkq-link 0q =(1)*(q-llink)q = q-.llink五、