《數(shù)據(jù)結(jié)構(gòu)》模擬試卷(B卷)

《《數(shù)據(jù)結(jié)構(gòu)》模擬試卷(B卷)》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、山東科技大學(xué)《數(shù)據(jù)結(jié)構(gòu)》模擬試卷（B卷）班級姓名學(xué)號題號一二三四五總得分評卷人審核人得分一、填空題（每空1分，共10分）1、L是一個帶表頭結(jié)點(diǎn)的單鏈表，P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，在P結(jié)點(diǎn)后插入結(jié)點(diǎn)Q的語句序列是Q->next=P->next;(1)___.2、一個算法的時間復(fù)雜度為(3n+nlog2n+n2)，其數(shù)量級表示為(2).3、從穩(wěn)定性來講，快速排序是一種(3)　　　　的排序方法。4、對于一棵二叉樹，滿足(4)是滿二叉樹。5、后綴算式79230+-42/*的值為(5)　　　　　。中綴算式(3+X*Y)-2Y/3對應(yīng)

2、的后綴算式為(6)　　　　　　　。6、順序存儲的循環(huán)隊(duì)列隊(duì)滿的判斷條件是(7)　　　　　　　　　。(Q.rear、Q.front和maxsize分別表示隊(duì)列的隊(duì)頭指針、隊(duì)尾指針和隊(duì)列的存儲單元個數(shù))7、*a是平衡二叉樹中一個子樹的根結(jié)點(diǎn)，其平衡因子為1，現(xiàn)在在*a的左子樹根結(jié)點(diǎn)的左子樹上插入一新的結(jié)點(diǎn)，使*a的平衡因子變?yōu)?8)　　　　，使以*a為根的子樹失去平衡，則需進(jìn)行(9)　　　　　　　的旋轉(zhuǎn)平衡處理。8、利用給出AOV_網(wǎng)中頂點(diǎn)的拓?fù)湫蛄械姆椒梢詸z查(10)　　　　　　　　　　　　。二、單項(xiàng)選擇題（每題2分，共20分）1、深

3、度為k的二叉樹的結(jié)點(diǎn)總數(shù)最多為（　　?。．2k-1B．2k+1C．2k-1D．2k-12、假設(shè)按低下標(biāo)優(yōu)先存儲整數(shù)數(shù)組A6×3×5時，第一個元素的字節(jié)地址是100，每個整數(shù)占四個字節(jié)，則a312的存儲地址是(　　)A.280B.308C.412D.1523、若順序存儲的循環(huán)隊(duì)列的的MaxSize=n,則該隊(duì)列最多可存儲（　?。﹤€元素。A.nB.n-1C.n+1D.不確定4、對n個記錄進(jìn)行堆排序，所需要的輔助存儲空間為()A.O(Log2n)B.O(n)C.O(1)D.O(n2)5、下列關(guān)于B_樹的敘述中，錯誤的是（　　　　）A.一

4、棵m階的B_樹中，每個結(jié)點(diǎn)至多有m棵子樹；B.一棵m階的B_樹中，每個結(jié)點(diǎn)中至多有m個關(guān)鍵字；第3頁共3頁C.一棵m階的B_樹中，除根之外的所有非終端結(jié)點(diǎn)至少有棵子樹；D.一棵m階的B_樹中，若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)則至少有2棵子樹6、下列關(guān)于AOE網(wǎng)的敘述中錯誤的是（　?。〢.從源點(diǎn)到匯點(diǎn)的路徑長度最長的路徑是關(guān)鍵路徑；B.完成工程的最短時間是從源點(diǎn)到匯點(diǎn)的最長路徑長度；C.提前完成某些關(guān)鍵活動可以加快工程的進(jìn)度；D.提前完成某些非關(guān)鍵活動可以加快工程的進(jìn)度7、下列關(guān)于二叉樹遍歷的敘述中，正確的是（　?。〢.若一個樹葉是某二叉樹的中序遍

5、歷的最后一個結(jié)點(diǎn)，則它必是該二叉樹的前序遍歷最后一個結(jié)點(diǎn)；B.若一個結(jié)點(diǎn)是某二叉樹的前序遍歷的最后一個結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷最后一個結(jié)點(diǎn)；C.若一個結(jié)點(diǎn)是某二叉樹的中序遍歷的最后一個結(jié)點(diǎn)，則它必是該二叉樹的前序遍歷最后一個結(jié)點(diǎn)；D.若一個樹葉是某二叉樹的前序遍歷的最后一個結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷最后一個結(jié)點(diǎn)；8、非空的循環(huán)單鏈表first的尾結(jié)點(diǎn)（由p所指向）滿足（　?。〢.p->next=NULLB.p=NULLC.p->next=firstC.p=first9、采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于樹的（　　

6、）A.先序遍歷　　　B.中序遍歷　　　C.后序遍歷　　　D.層序遍歷10、對于一個具有n個頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則所有邊鏈表中邊結(jié)點(diǎn)的總數(shù)為（　?。.e/2B.eC.2eD.n+e三、應(yīng)用題（每題10分，共40分）1、試為下列關(guān)鍵字建立一個裝填因子不小于0.75的哈希表，并寫出你所使用的哈希函數(shù)，以及解決沖突的方法，并計(jì)算你所構(gòu)造的哈希表在等概率的情況下查找成功和不成功時的平均查找長度。（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG）2、輸入序列為(53,31,19,23,14,55,6

7、8,11,13)，請畫出插入所有關(guān)鍵字后的平衡二叉樹。3、已知某二叉樹的每個結(jié)點(diǎn)，要么其左、右子樹皆為空，要么其左、右樹皆不空。又知該二叉樹的前序序列為：JFDBACEHXIK；后序序列為：ACBEDXIHFKJ。畫出相應(yīng)的二叉樹，給出該二叉樹的中序序列，并將此二叉樹轉(zhuǎn)換為樹或森林。4、某帶權(quán)有向圖及它的鄰接表如下：1）試寫出它的深度優(yōu)先搜索序列。2）根據(jù)Prim算法，求它的最小生成樹。第3頁共3頁ABC^BCDEFGHDE^F^CFG^EH^G^HG^^BCEAGDFH234512346523四、算法設(shè)計(jì)題（1題10分，2題20分，

8、共30分）1、試以二叉鏈表作存儲結(jié)構(gòu)，編寫按層次順序遍歷二叉樹的算法。2、編寫算法，求解鄰接表存儲方式下有向圖G的拓?fù)溆行蛐蛄?。?頁共3頁