2020中國(guó)傳媒大學(xué)824數(shù)據(jù)結(jié)構(gòu)真題回憶

Rachel_R

六、代碼題（40分）
1.判斷一棵樹(shù)是二叉排序樹(shù)，寫(xiě)出算法設(shè)計(jì)思想，寫(xiě)出代碼，計(jì)算時(shí)間復(fù)雜度
2.圖的深度優(yōu)先搜索遍歷的非遞歸算法，寫(xiě)出算法設(shè)計(jì)思想和代碼
3.兩個(gè)數(shù)組（a1...am）和（b1...bn）存儲(chǔ)在線性表A[1…m+n]中，要求將兩個(gè)數(shù)組位置互換，寫(xiě)出算法設(shè)計(jì)思想和代碼

五、應(yīng)用題（4*5）
1.給出一組數(shù)進(jìn)行非遞減排序，增量序列d=｛5,3,1｝，寫(xiě)出希爾排序過(guò)程和結(jié)果
2.給出一組數(shù)和裝填因子，用線性探查法解決沖突，要求寫(xiě)出哈希函數(shù)，畫(huà)出哈希表，計(jì)算等概率情況下的查找成功和失敗情況下的平均查找長(zhǎng)度
3.給出中序遍歷序列和后序遍歷序列，要求畫(huà)出二叉樹(shù)，并寫(xiě)出先序遍歷序列
4.忘記了

四、填空題（10*2）
1.程序的＿＿性是指，對(duì)輸入數(shù)據(jù)進(jìn)行判斷，避免對(duì)輸入的錯(cuò)誤數(shù)據(jù)進(jìn)行計(jì)算后得出亂七八糟的結(jié)果
2.三元組和＿＿可以用來(lái)存儲(chǔ)特殊矩陣和稀疏矩陣
3.給出一組數(shù)和排序過(guò)程，判斷是什么排序
4.計(jì)算下列代碼的時(shí)間復(fù)雜度，代碼大概是
while（i＜n）? i=i*2；
5.一個(gè)二維數(shù)組m*n（m和n是具體數(shù)字），按列優(yōu)先存儲(chǔ)在一維數(shù)組中，每個(gè)元素占兩個(gè)字節(jié)，開(kāi)始位置1024，計(jì)算某個(gè)具體位置的元素的存儲(chǔ)位置
6.給出一組數(shù)，計(jì)算這組數(shù)構(gòu)成的赫夫曼樹(shù)的最短帶權(quán)路徑長(zhǎng)度
7.一維數(shù)組A[m,n]存儲(chǔ)在循環(huán)隊(duì)列中，隊(duì)列滿(mǎn)的判斷條件是

三、判斷題（10*2）
1.折半查找判定樹(shù)是一棵完全二叉樹(shù)
2.一個(gè)關(guān)于大頂堆中元素大小的表述，具體忘記了

二、多選題（10*2）
1.以下時(shí)間復(fù)雜度相同的是
A. 克魯斯卡爾算法?????????? B. 冒泡排序
C. 迪杰斯特拉算法?????????? D. 拓?fù)渑判?br /> 2.對(duì)B-樹(shù)的特性描述正確的是
A. 葉子結(jié)點(diǎn)不在同一層
B. 葉子結(jié)點(diǎn)有指針連接
其他兩個(gè)正確選項(xiàng)不記得了
3.給出一組數(shù)的第二趟排序結(jié)果，可能是以下哪種排序
4.給出進(jìn)棧序列，以及第幾個(gè)（具體第幾忘記了）出棧的元素是a，以下可能的出棧序列是
5.以下排序算法，排序趟數(shù)與初始狀態(tài)無(wú)關(guān)的是

一、單選題（15*2）
1.對(duì)一個(gè)有n個(gè)頂點(diǎn)，e條邊的無(wú)向圖，刪除某個(gè)頂點(diǎn)及其鄰接邊的時(shí)間復(fù)雜度是
A. ne?? B. n+e?? C. n??? D. 不記得了
2.第六層有24個(gè)葉子結(jié)點(diǎn)的完全二叉樹(shù)最多有幾個(gè)結(jié)點(diǎn)
3.高度為h的完全二叉樹(shù)只有度為0和2的結(jié)點(diǎn)，則這棵樹(shù)有幾個(gè)結(jié)點(diǎn)
4.有n個(gè)分支節(jié)點(diǎn)的二叉樹(shù)高度是
5.一個(gè)只有尾指針rear的帶頭節(jié)點(diǎn)的單鏈表，刪除第一個(gè)元素的算法是
選項(xiàng)中給出具體的算法語(yǔ)句
6.若一個(gè)鏈表只有四種操作：刪除第一個(gè)結(jié)點(diǎn)，刪除最后一個(gè)結(jié)點(diǎn)，在第一個(gè)結(jié)點(diǎn)前插入元素，在最后一個(gè)結(jié)點(diǎn)后插入元素，則最好用以下哪種鏈表儲(chǔ)存
A. 只有尾指針的帶頭節(jié)點(diǎn)的循環(huán)雙鏈表
B. 只有尾指針的帶頭節(jié)點(diǎn)的循環(huán)單鏈表
C. 只有頭指針的循環(huán)單鏈表
D. 只有尾指針的帶頭節(jié)點(diǎn)的非循環(huán)雙鏈表
7.一個(gè)100*100的三對(duì)角矩陣，按行優(yōu)先存儲(chǔ)在下標(biāo)從0開(kāi)始的一維數(shù)組中，A25,26的存儲(chǔ)位置是
8.給出一組數(shù)是一個(gè)堆（題目沒(méi)說(shuō)但可判斷是小頂堆），插入一個(gè)元素調(diào)整后得到的堆是
9.對(duì)串的描述錯(cuò)誤的是
（具體選項(xiàng)忘記了，串在2020大綱里只涉及模式匹配，但還是考了串的基本概念）
10.有n個(gè)頂點(diǎn)的圖的最小生成樹(shù)是指
A. 有n個(gè)頂點(diǎn)的權(quán)值最小的連通子圖
B. 有n-1條邊的權(quán)值最小的連通子圖
C. D選項(xiàng)忘記了
來(lái)源: [url=forum.php?mod=viewthread&tid=9794842]2020中國(guó)傳媒大學(xué)824數(shù)據(jù)結(jié)構(gòu)真題回憶[/url]

來(lái)自Android客戶(hù)端

淺黛微妝粉

可以輔導(dǎo)數(shù)據(jù)結(jié)構(gòu)專(zhuān)業(yè)課嗎

來(lái)自iPhone客戶(hù)端

半半子

請(qǐng)問(wèn)樓主有824歷年真題嗎