數(shù)據(jù)結(jié)構(gòu)試題,模擬考試題(可編輯)

1、數(shù)據(jù)結(jié)構(gòu)試題,模擬考試題 數(shù)據(jù)結(jié)構(gòu)試題單選題 b 靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu) c 線性結(jié)構(gòu)與非線性結(jié)構(gòu) d 緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)2采用線性鏈表表示一個(gè)向量時(shí)要求占用的存儲(chǔ)空間地址d a 必須是連續(xù)的 b 部分地址必須是連續(xù)的 c 一定是不連續(xù)的 d 可連續(xù)可不連續(xù)3采用順序搜索方法查找長(zhǎng)度為n的順序表時(shí)搜索成功的平均搜索長(zhǎng)度為 d a n b n2 c n-1 2 d n1 24在一個(gè)單鏈表中若q結(jié)點(diǎn)是p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)若在q與p之間插入結(jié)點(diǎn)s則執(zhí)行 d a slink plink plink s b plink s slink qc plink slink slink p d qlink s slin

2、k p5如果想在4092個(gè)數(shù)據(jù)中只需要選擇其中最小的5個(gè)采用 c 方法最好 a 起泡排序 b 堆排序 c 錦標(biāo)賽排序 d 快速排序 6設(shè)有兩個(gè)串t和p求p在t中首次出現(xiàn)的位置的運(yùn)算叫做 b a 求子串 b 模式匹配 c 串替換 d 串連接7在數(shù)組a中每一個(gè)數(shù)組元素aij占用3個(gè)存儲(chǔ)字行下標(biāo)i從1到8列下標(biāo)j從1到10所有數(shù)組元素相繼存放于一個(gè)連續(xù)的存儲(chǔ)空間中則存放該數(shù)組至少需要的存儲(chǔ)字?jǐn)?shù)是 c a 80 b 100 c 240 d 2708將一個(gè)遞歸算法改為對(duì)應(yīng)的非遞歸算法時(shí)通常需要使用 a a 棧 b 隊(duì)列 c 循環(huán)隊(duì)列 d 優(yōu)先隊(duì)列9一個(gè)隊(duì)列的進(jìn)隊(duì)列順序是1 2 3 4則出隊(duì)列順序?yàn)?c

3、10在循環(huán)隊(duì)列中用數(shù)組a0m-1 存放隊(duì)列元素其隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是 d a front - rear 1 m b rear - front 1 mc front - rear m m d rear - front m m11一個(gè)數(shù)組元素ai與 a 的表示等價(jià)a ai b ai c ai d ai 12若需要利用形參直接訪問(wèn)實(shí)參則應(yīng)把形參變量說(shuō)明為 b 參數(shù)a 指針 b 引用 c 值 d 變量13下面程序段的時(shí)間復(fù)雜度為 c for int i 0i mi for int j 0j nj aij ija o m2 b o n2 c o mn d o

4、mn 14下面程序段的時(shí)間復(fù)雜度為 b int f unsigned int n if n 0 n 1 return 1 else return nf n-1 a o 1 b o n c o n2 d o n 15線性表若是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)要求內(nèi)存中可用存儲(chǔ)單元的地址 d a 必須是連續(xù)的b 部分地址必須是連續(xù)的c 一定是不連續(xù)的d 連續(xù)或不連續(xù)都可以16數(shù)據(jù)結(jié)構(gòu)的定義為 ds 其中d是 b 的集合a 算法 b數(shù)據(jù)元素 c 數(shù)據(jù)操作 d 邏輯結(jié)構(gòu)17算法分析的目的是 a a 找出數(shù)據(jù)結(jié)構(gòu)的合理性b 研究算法中輸入和輸出的關(guān)系c 分析算法的效率以求改進(jìn)d 分析算法的易懂性和文檔性18在一個(gè)單鏈

5、表中若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)在p之后插入s所指結(jié)點(diǎn)則執(zhí)行 b a s- link pp- link sb s- link p- linkp- link sc s- link p- linkp sd p- link ss- link p19設(shè)單鏈表中結(jié)點(diǎn)結(jié)構(gòu)為 datalink 已知指針q所指結(jié)點(diǎn)是指針p所指結(jié)點(diǎn)的直接前驅(qū)若在q與p之間插入結(jié)點(diǎn)s則應(yīng)執(zhí)行下列哪一個(gè)操作 b a s- link p- link p- link s b q- link s s- link pc p- link s- links- link p d p- link s s- link q20設(shè)單鏈表中結(jié)點(diǎn)結(jié)構(gòu)為 dat

6、alink 若想摘除結(jié)點(diǎn)p的直接后繼則應(yīng)執(zhí)行下列哪一個(gè)操作 a a p- link p- link- link b p p- link p- link p- link- linkc p- link p- link d p p- link- link21設(shè)單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為datalink且rear是指向非空的帶表頭結(jié)點(diǎn)的單循環(huán)鏈表的尾結(jié)點(diǎn)的指針若想刪除鏈表第一個(gè)結(jié)點(diǎn)則應(yīng)執(zhí)行下列哪一個(gè)操作 d a s rear rear rear- link delete s b rear rear- link delete rear c rear rear- link- link delete rear

7、 d s rear- link- link rear- link- link s- link delete s22設(shè)單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為datalink且first為指向鏈表表頭的指針current為鏈表當(dāng)前指針在循環(huán)鏈表中檢測(cè)current是否達(dá)到鏈表表尾的語(yǔ)句是 d a current- link null b first- link currentc first current d current- link first23一個(gè)棧的入棧序列為abc則出棧序列不可能的是 c a cba b bac c cab d acb24棧的數(shù)組表示中top為棧頂指針棧空的條件是 a a top 0

8、 b top size c top size d top -125棧和隊(duì)列的共同特點(diǎn)是 c a 都是先進(jìn)后出 b 都是先進(jìn)先出c 只允許在端點(diǎn)處插入和刪除 d 沒(méi)有共同點(diǎn)26假定一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e為f和r 則判斷隊(duì)空的條件為 d a f1 r b r1 f c f 0 d f r27當(dāng)利用大小為n 的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)該隊(duì)列的最大長(zhǎng)度為 b a n-2 b n-1 c n d n128當(dāng)利用大小為n 的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)假定用top n 表示棧空則向這個(gè)棧插入一個(gè)元素時(shí)首先應(yīng)執(zhí)行 語(yǔ)句修改top指針a top b top- c top 0 d top29設(shè)鏈?zhǔn)綏Ｖ?/p>

9、結(jié)點(diǎn)的結(jié)構(gòu)為data link且top是指向棧頂?shù)闹羔樔粝胝準(zhǔn)綏５臈ｍ斀Y(jié)點(diǎn)并將被摘除結(jié)點(diǎn)的值保存到x中則應(yīng)執(zhí)行下列 a 操作a x top- data top top- link b top top- link x top- data c x top top top- link d x top- data30設(shè)循環(huán)隊(duì)列的結(jié)構(gòu)是 const int size 100 typedef int data type typedef struct data type datasize int front rear queue若有一個(gè)queue類型的隊(duì)列q試問(wèn)判斷隊(duì)列滿的條件應(yīng)是下列哪一個(gè)語(yǔ)句 d a

10、 qfront qrear b qfront - qrear size c qfront qrear size d qfront qrear1 size31設(shè)有一個(gè)遞歸算法如下int fact int n if n 0 return 1else return nfact n-1 下面正確的敘述是 b a 計(jì)算fact n 需要執(zhí)行n次遞歸 b fact 7 5040 c 此遞歸算法最多只能計(jì)算到fact 8 d 以上結(jié)論都不對(duì)32設(shè)有一個(gè)遞歸算法如下int x int n if n 3 return 1else return x n-2 x n-4 1 試問(wèn)計(jì)算 x x 8 時(shí)需要計(jì)算 d 次

11、x函數(shù)a 8 次 b 9次 c 16次 d 18次33設(shè)有廣義表d abd 其長(zhǎng)度為 b 深度為 a a b 3 c 2 d 534廣義表a a 則表尾為 c a a b c 空表 d a35下列廣義表是線性表的有 c a ea bc b e ae c e ab d e al 36遞歸表再入表純表線性表之間的關(guān)系為 c a 再入表 遞歸表 純表 線性表 b 遞歸表 線性表 再入表 純表 c 遞歸表 再入表 純表 線性表 d遞歸表 再入表 線性表 純表37某二叉樹(shù)的前序和后序序列正好相反則該二叉樹(shù)一定是b的二叉樹(shù)a 空或只有一個(gè)結(jié)點(diǎn) b 高度等于其結(jié)點(diǎn)數(shù) c 任一結(jié)點(diǎn)無(wú)左孩子 d 任一結(jié)點(diǎn)無(wú)右孩

12、子38對(duì)于任何一棵二叉樹(shù)t如果其終端結(jié)點(diǎn)數(shù)為n0度為2的結(jié)點(diǎn)為n2則 a a n0 n21 b n2 n01 c n0 2n21 d n2 2n01 39 由權(quán)值分別為118625的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)它的帶權(quán)路徑長(zhǎng)度為a 24 b 73 c 48 d 5340已知一個(gè)順序存儲(chǔ)的線性表設(shè)每個(gè)結(jié)點(diǎn)需占m個(gè)存儲(chǔ)單元若第一個(gè)結(jié)點(diǎn)的地址為da1則第i 個(gè)結(jié)點(diǎn)的地址為aa da1 i-1 m b da1im c da1-im d da1 i1 m4134 具有35個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 a a 5 b 6 c 7 d 842對(duì)線性表進(jìn)行折半搜索時(shí)要求線性表必須 c a 以鏈接方式存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵

13、碼有序排列 b 以數(shù)組方式存儲(chǔ) c 以數(shù)組方式存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵碼有序排列 d以鏈接方式存儲(chǔ)43順序搜索算法適合于存儲(chǔ)結(jié)構(gòu)為 b 的線性表a 散列存儲(chǔ) b 順序存儲(chǔ)或鏈接存儲(chǔ) c 壓縮存儲(chǔ) d 索引存儲(chǔ)44采用折半搜索算法搜索長(zhǎng)度為n的有序表時(shí)元素的平均搜索長(zhǎng)度為 c a on2 b on log2n c olog2n d on45對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖進(jìn)行拓?fù)渑判驎r(shí)總的時(shí)間為 a a n b n1 c n-1 d ne46判斷一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ膺€可以利用c a 求關(guān)鍵路徑的方法 b 求最短路徑的dijkstra方法 c 深度優(yōu)先遍歷算法 d 廣度優(yōu)先

14、遍歷算法47在10階b-樹(shù)中根結(jié)點(diǎn)所包含的關(guān)鍵碼個(gè)數(shù)最多為c 最少為 a a 1 b 2 c 9 d 1048對(duì)包含n 個(gè)元素的散列表進(jìn)行搜索平均搜索長(zhǎng)度為 c a olog2n b onc 不直接依賴于n d 上述都不對(duì)填空題1數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu) 四種2數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為順序結(jié)構(gòu)鏈接結(jié)構(gòu)索引結(jié)構(gòu)散列結(jié)構(gòu) 四種3一種抽象數(shù)據(jù)類型包括數(shù)據(jù) 和操作 兩個(gè)部分設(shè)有兩個(gè)串p和q求p在q中首次出現(xiàn)的位置的運(yùn)算稱為模式匹配 棧隊(duì)列邏輯上都是線性存儲(chǔ)結(jié)構(gòu)線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一的圖中的數(shù)據(jù)元素之間的關(guān)系是多對(duì)多的樹(shù)形結(jié)構(gòu)中數(shù)據(jù)元素間的關(guān)系是一對(duì)多的棧中存取數(shù)據(jù)

15、的原則后進(jìn)先出隊(duì)列中存取數(shù)據(jù)的原則先進(jìn)先出8abccdcdccbaa模式p cdcc則第6次匹配成功10i 1為 i-1 2 1617已知具有n個(gè)元素的一維數(shù)組采用順序存儲(chǔ)結(jié)構(gòu)每個(gè)元素占k個(gè)存儲(chǔ)單元第一個(gè)元素的地址為loc a1 那么loc ai loc a1 18在霍夫曼編碼中若編碼長(zhǎng)度只允許小于等于4則除掉已對(duì)兩個(gè)字符編碼為0和10外還可以最多對(duì) 4 個(gè)字符編碼19設(shè)高度為h的空二叉樹(shù)的高度為-1只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的高度為0若設(shè)二叉樹(shù)只有度為2上度為0的結(jié)點(diǎn)則該二叉樹(shù)中所含結(jié)點(diǎn) 21以折半搜索方法搜索一個(gè)線性表時(shí)此線性表必須是順序存儲(chǔ)的有序表22已知完全二叉樹(shù)的第8層有8個(gè)結(jié)點(diǎn)則其葉子結(jié)

16、點(diǎn)數(shù)是68若完全二叉樹(shù)的第7有10個(gè)葉子結(jié)點(diǎn)則整個(gè)二叉樹(shù)的結(jié)點(diǎn)數(shù)最多是23523對(duì)于折半搜索所對(duì)應(yīng)的判定樹(shù)它既是一棵二叉搜索樹(shù)又是一棵理想平衡樹(shù)24假定對(duì)長(zhǎng)度n 50的有序表進(jìn)行折半搜索則對(duì)應(yīng)的判定樹(shù)高度為判定樹(shù)中前層的結(jié)點(diǎn)數(shù)為最后一層的結(jié)點(diǎn)數(shù)為25在一個(gè)無(wú)向圖中所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的倍在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中包含有 n n-1 2 條邊在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中包含有 n n-1 條邊26對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的連通圖其生成樹(shù)中的頂點(diǎn)數(shù)和邊數(shù)分別為n和n-127設(shè)線性表中元素的類型是實(shí)型其首地址為1024則線性表中第6個(gè)元素的存儲(chǔ)位置是 1044 28在插入和選

17、擇排序中若初始數(shù)據(jù)基本正序則選擇插入排序若初始數(shù)據(jù)基本反序則最好選擇選擇排序29算法是對(duì)特定問(wèn)題的求解步驟的一種描述它是指令的有限序列每一條指令表示一個(gè)或多個(gè)操作30對(duì)于一個(gè)具有n個(gè)頂點(diǎn)肯e 條邊的無(wú)向圖進(jìn)行拓樸排序時(shí)總的進(jìn)間為n31構(gòu)造哈希函數(shù)有三種方法分別為 平方取中 法 除留余數(shù) 法 折迭移位 法32處理沖突的三種方法分別為 線性探測(cè) 隨機(jī)探測(cè) 鏈地址法33對(duì)于含有n個(gè)頂點(diǎn)和e條邊的無(wú)向連通圖利用普里姆算法產(chǎn)生的最小生成樹(shù)其時(shí)間復(fù)雜度為 n2 利用克魯斯卡爾算法產(chǎn)生的最小生成樹(shù)其時(shí)間復(fù)雜度為elog2e 34快速排序在平均情況下的時(shí)間復(fù)雜度為nlog2n在最壞情況下的時(shí)間復(fù)雜度為n2快速

18、排序在平均情況下的空間復(fù)雜度為log2n在最壞情況下的空間復(fù)雜度為n35假定一組記錄的排序碼為對(duì)其進(jìn)行歸并排序的過(guò)程中第二趟排序后的結(jié)果是36假定一組記錄的排序碼為對(duì)其進(jìn)行快速排序的第一次劃分的結(jié)果是37一個(gè)結(jié)點(diǎn)的子樹(shù)的 個(gè)數(shù) 稱為該結(jié)點(diǎn)的度度為 零 的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)度不為 零 的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)樹(shù)中各結(jié)點(diǎn)度的 最大值 稱為樹(shù)的度38設(shè)ki kj 1 i n 1 j nj i 且在排序前的序列中ri領(lǐng)先于rj i j 若排序后的序列中ri仍領(lǐng)先于rj則這種排序方法是穩(wěn)定的反之是不穩(wěn)定的40 在堆排序的過(guò)程中對(duì)任一分支結(jié)點(diǎn)進(jìn)行調(diào)整運(yùn)算的時(shí)間復(fù)雜度為log2n整個(gè)排序過(guò)程的時(shí)

19、間復(fù)雜度為nlog2n41在索引表中每個(gè)索引項(xiàng)至少包含有關(guān)鍵碼值域和子表地址域這兩項(xiàng)42假定一個(gè)線性表為abcdbaabdbcefcfgahijbkwteccdtaayb若按照字符串的第一個(gè)字母進(jìn)行劃分使得同一個(gè)字母被劃分在一個(gè)子表中則得到的abc三個(gè)子表的長(zhǎng)度分別為43對(duì)于包含個(gè)關(guān)鍵碼的階b-樹(shù)其最小高度為最大高度為44從一棵b-樹(shù)刪除關(guān)鍵碼的過(guò)程若最終引起樹(shù)根結(jié)點(diǎn)的合并則新樹(shù)比原樹(shù)的高度減45假定要對(duì)長(zhǎng)度n 100的線性表進(jìn)行散列存儲(chǔ)并采用開(kāi)散列法處理沖突則對(duì)于長(zhǎng)度m 20的散列表每個(gè)散列地址的同義詞子表的長(zhǎng)度平均為46在散列存儲(chǔ)中裝載因子又稱為裝載系數(shù)若用m表示散列表的長(zhǎng)度n表示待散列存

20、儲(chǔ)的元素的個(gè)數(shù)則等于nm47在有向圖的鄰接矩陣中第i行中1的個(gè)數(shù)是第i個(gè)頂點(diǎn)的出度第i列中1的個(gè)數(shù)是第i個(gè)頂點(diǎn)的入度在無(wú)向圖的鄰接矩陣中第i行列中1的個(gè)數(shù)是第i個(gè)頂點(diǎn)的度矩陣中1的個(gè)數(shù)的一半是圖中的邊數(shù)48在對(duì)m階b-樹(shù)中每個(gè)非根結(jié)點(diǎn)的關(guān)鍵碼數(shù)最少為m2-1個(gè)最多為m-1個(gè)其子樹(shù)棵數(shù)最少為m2最多為m判斷題數(shù)據(jù)元素是數(shù)據(jù)的最小單位數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系是用戶按使用需要建立的 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體從邏輯關(guān)系上講數(shù)據(jù)結(jié)構(gòu)主要分為兩大類線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性表的邏輯順序與物理順序總是一致的二維數(shù)組是其數(shù)組元素為線性表的線性表每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備

21、三種基本運(yùn)算插入刪除搜索非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接前驅(qū)元素 空串與由空格組成的串沒(méi)有區(qū)別 將t在s中首次出現(xiàn)的位置作為t在s中的位置的操作稱為串的模式匹配深度為h的非空二叉樹(shù)的第層最多有2h-1個(gè)結(jié)點(diǎn) 完全二叉樹(shù)就是滿二叉樹(shù)已知一棵二叉樹(shù)的前序序列和中序序列可以唯一地構(gòu)造出該二叉樹(shù) 帶權(quán)連通圖的最小生成樹(shù)的權(quán)值之和一定小于它的其它生成樹(shù)的權(quán)值之和若有一個(gè)結(jié)點(diǎn)是二叉樹(shù)中某個(gè)子樹(shù)的中序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)則它一定是該子樹(shù)的前序遍歷結(jié)果序列的最后一個(gè)結(jié)點(diǎn)17任一棵二叉搜索樹(shù)的平均搜索時(shí)間都小于用順序搜索法搜索同樣結(jié)點(diǎn)的順序表的平均搜索時(shí)間18最優(yōu)二叉搜索樹(shù)一定是平衡的二叉搜

22、索樹(shù)19aoe網(wǎng)是一種帶權(quán)的無(wú)環(huán)連通圖 22線性表中所有結(jié)點(diǎn)的類型必須相同n個(gè)結(jié)點(diǎn)的有向圖若它有n n1 條邊則它一定是強(qiáng)連通的任何無(wú)環(huán)的有向圖其結(jié)點(diǎn)都可以排在一個(gè)拓?fù)湫蛄欣?27用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)在不考慮壓縮存儲(chǔ)的情況下所占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)而與圖的邊數(shù)無(wú)關(guān)28鄰接表只能用于有向圖的存儲(chǔ)鄰接矩陣對(duì)于有向圖和無(wú)向圖的存儲(chǔ)都適用29連通分量是無(wú)向圖中的極小連通子圖30在網(wǎng)絡(luò)中一定只有一條關(guān)鍵路徑31關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間32平衡二叉樹(shù)的左右子樹(shù)深度之差的絕對(duì)值不超過(guò)1 33快速排序是對(duì)起泡排序的一種改進(jìn) 34直接選擇排序穩(wěn)定35堆排序占用的輔助空間很大

23、36在散列法中采取開(kāi)散列法來(lái)解決沖突時(shí)其裝載因子的取值一定在之間37b-樹(shù)是一種動(dòng)態(tài)索引結(jié)構(gòu)它既適用于隨機(jī)搜索也適用于順序搜索38在散列法中一個(gè)可用散列函數(shù)必須保證絕對(duì)不產(chǎn)生沖突39任何一個(gè)關(guān)鍵活動(dòng)延遲那么整個(gè)工程將會(huì)延遲40任何一個(gè)關(guān)鍵活動(dòng)提前完成那么整個(gè)工程將會(huì)提前完成四運(yùn)算應(yīng)用題 1在一個(gè)有n個(gè)元素的順序表的第i個(gè)元素1 i n之前插入一個(gè)新元素時(shí)需要向后移動(dòng)多少個(gè)元素答案需要向后移動(dòng) n- i 1個(gè)元素當(dāng)一個(gè)棧的進(jìn)棧序列為1234567時(shí)可能的出棧序列有多少種6457321是否是合理的出棧序列答案 可能的出棧序列有 種6457321不是合理的出棧序列簡(jiǎn)單直接選擇排序是一種穩(wěn)定的排序方法

24、嗎試舉例說(shuō)明答案是不穩(wěn)定的排序方法下面就是不穩(wěn)定的例子只要能舉出反例即可 275 275 512 061 i 1 061 275 512 275 i 2 061 275 512 275 i 3 061 275 275 512 4 20 30 40 50 60 70 采用折半搜索時(shí)搜索成功的平均搜索長(zhǎng)度是多少答案 aslsucc 11 22 34 7 17 75 在結(jié)點(diǎn)個(gè)數(shù)為n n 1 的各棵樹(shù)中高度最小的樹(shù)的高度是多少它有多少個(gè)葉結(jié)點(diǎn)多少個(gè)分支結(jié)點(diǎn)高度最大的樹(shù)的高度是多少它有多少個(gè)葉結(jié)點(diǎn)多少個(gè)分支結(jié)點(diǎn)答案結(jié)點(diǎn)個(gè)數(shù)為n時(shí)高度最小的樹(shù)的高度為1有2層它有n-1個(gè)葉結(jié)點(diǎn)1個(gè)分支結(jié)點(diǎn)高度最大的樹(shù)的高度

25、為n-1有n層它有1個(gè)葉結(jié)點(diǎn)n-1個(gè)分支結(jié)點(diǎn)6 一棵高度為h的滿k叉樹(shù)有如下性質(zhì) 第h層上的結(jié)點(diǎn)都是葉結(jié)點(diǎn) 其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹(shù) 如果按層次自頂向下 同一層自左向右 順序從1開(kāi)始對(duì)全部結(jié)點(diǎn)進(jìn)行編號(hào) 試問(wèn) 1 各層的結(jié)點(diǎn)個(gè)數(shù)是多少 2 編號(hào)為i的結(jié)點(diǎn)的父結(jié)點(diǎn) 若存在 的編號(hào)是多少 3 編號(hào)為i的結(jié)點(diǎn)的第m個(gè)孩子結(jié)點(diǎn) 若存在 的編號(hào)是多少 4 編號(hào)為i的結(jié)點(diǎn)有右兄弟的條件是什么 其右兄弟結(jié)點(diǎn)的編號(hào)是多少 5 若結(jié)點(diǎn)個(gè)數(shù)為 n 則高度h是n 的什么函數(shù)關(guān)系答案1各層的結(jié)點(diǎn)個(gè)數(shù)是ki i 012h 2編號(hào)為i的結(jié)點(diǎn)的父結(jié)點(diǎn) 若存在 的編號(hào)是 ik-2 k3編號(hào)為i的結(jié)點(diǎn)的第m個(gè)孩子結(jié)點(diǎn)

26、若存在 的編號(hào)是 i-1 km14當(dāng) i-1 k 0時(shí)有右兄弟 右兄弟的編號(hào)為 i15若結(jié)點(diǎn)個(gè)數(shù)為 n 則高度h和n 的關(guān)系為h logk n k-1 1 -1 n 0時(shí)h -1 7 1 a - b c 2 a b d e f a d c 3 a b e f 注按c的優(yōu)先級(jí) 4 a b c c d c e 答案各中綴表達(dá)式的后綴形式如下 1ab-c 2 abdefadc 3 abef 4 abc ce 8 1 d a c b e c a l b c d 2 j1 j2 j1 a j3 j1 j3 j1 答案廣義表1的圖形表示為廣義表2的圖形表示為廣義表1的存儲(chǔ)表示為廣義表2的存儲(chǔ)表示為9題目1

27、1將下面的森林變換成二叉樹(shù)7分答案10將算術(shù)表達(dá)式 ab c de f gh 轉(zhuǎn)化為二叉樹(shù)答案11答案其中的一個(gè)拓?fù)湫蛄袨関1v2v3v4v5v6v7 12 將給定的圖簡(jiǎn)化為最小的生成樹(shù)要求從頂點(diǎn)1出發(fā)7分答案 13某子系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符其出現(xiàn)的概率分別為005029007008014023003011試設(shè)計(jì)赫夫曼編碼答案為方便起見(jiàn)設(shè)各種字符的權(quán)值w 529781423311 因?yàn)閚 8所以要構(gòu)造的赫夫曼樹(shù)共有m 2n-1 28-1 15個(gè)結(jié)點(diǎn)生成的赫夫曼樹(shù)為下圖所示赫夫曼編碼為概率為023的字符編碼為00概率為011的字符編碼為010概率為005的字符編碼為0110概率為00

28、3的字符編碼為0111概率為029的字符編碼為10 概率為014的字符編碼為110 概率為007的字符編碼為1110 概率為008的字符編碼為111114已知一棵二叉樹(shù)的前序遍歷的結(jié)果是abecdfghij 中序遍歷的結(jié)果是ebcdafhigj 試畫(huà)出這棵二叉樹(shù)并給出這棵二叉樹(shù)的后序遍歷序列答案根據(jù)前序序列和中序序列能得到唯一的二叉樹(shù)所得二叉樹(shù)如圖這棵二叉樹(shù)的后序遍歷序列為edcbihjgfa15在結(jié)點(diǎn)個(gè)數(shù)為n n 1 的各棵樹(shù)中高度最小的樹(shù)的高度是多少它有多少個(gè)葉結(jié)點(diǎn)多少個(gè)分支結(jié)點(diǎn)高度最大的樹(shù)的高度是多少它有多少個(gè)葉結(jié)點(diǎn)多少個(gè)分支結(jié)點(diǎn)答案結(jié)點(diǎn)個(gè)數(shù)為n時(shí)高度最小的樹(shù)的高度為1有2層它有n-1個(gè)

29、葉結(jié)點(diǎn)1個(gè)分支結(jié)點(diǎn)高度最大的樹(shù)的高度為n-1有n層它有1個(gè)葉結(jié)點(diǎn)n-1個(gè)分支結(jié)點(diǎn)16 對(duì)于一個(gè)高度為h的avl樹(shù)其最少結(jié)點(diǎn)數(shù)是多少反之對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的avl樹(shù) 其最大高度是多少 最小高度是多少答案設(shè)高度為h 空樹(shù)的高度為-1 的avl樹(shù)的最少結(jié)點(diǎn)為nh則nh fh3 -1fh 是斐波那契數(shù)又設(shè)avl樹(shù)有n個(gè)結(jié)點(diǎn)則其最大高度不超過(guò)32log2 n1 最小高度為log2 n1 -1177-7 設(shè)有序順序表中的元素依次為017 094 154 170 275503 509 512 553 612 677 765 897 908試畫(huà)出對(duì)其進(jìn)行折半搜索時(shí)的判定樹(shù) 并計(jì)算搜索成功的平均搜索長(zhǎng)度和搜索不

30、成功的平均搜索長(zhǎng)度答案折半搜索時(shí)的判定樹(shù)為aslsucc 1141223447 4514aslunsucc 11531414 591518試對(duì)下圖所示的aoe網(wǎng)絡(luò) 1 這個(gè)工程最早可能在什么時(shí)間結(jié)束 2 求每個(gè)事件的最早開(kāi)始時(shí)間vei和最遲開(kāi)始時(shí)間vli 3 求每個(gè)活動(dòng)的最早開(kāi)始時(shí)間e 和最遲開(kāi)始時(shí)間l 4 確定哪些活動(dòng)是關(guān)鍵活動(dòng)畫(huà)出由所有關(guān)鍵活動(dòng)構(gòu)成的圖指出哪些活動(dòng)加速可使整個(gè)工程提前完成答案按拓樸有序的順序計(jì)算各個(gè)頂點(diǎn)的最早可能開(kāi)始時(shí)間ve和最遲允許開(kāi)始時(shí)間vl然后再計(jì)算各個(gè)活動(dòng)的最早可能開(kāi)始時(shí)間e和最遲允許開(kāi)始時(shí)間l根據(jù)l-e是否等于0來(lái)確定關(guān)鍵活動(dòng)從而確定關(guān)鍵路徑ve019152938

31、43vl01915373843 12 13 32 24 25 35 46 56 e00151919152938l170152719273738l-e1700801280此工程最早完成時(shí)間為43關(guān)鍵路徑為 13 32 25 56 19已知有五個(gè)待排序的記錄其關(guān)鍵字分別為256301751129937863742694076438請(qǐng)用快速排序的方法將它們從小到大排列答案第一次排序076129256751937863742694301439第二次排序076129256438301694742751863937第三次排序076129256301438694742751863937第四次排序076129

32、256301438694742751863937第五次排序07612925630143869474275186393720設(shè)有150個(gè)記錄要存儲(chǔ)到散列表中 并利用線性探查法解決沖突 要求找到所需記錄的平均比較次數(shù)不超過(guò)2次試問(wèn)散列表需要設(shè)計(jì)多大 設(shè) 是散列表的裝載因子則有aslsucc 11 1- 2 答案已知要存儲(chǔ)的記錄數(shù)為n 150查找成功的平均查找長(zhǎng)度為aslsucc 2則有aslsucc 12111- 2 解得 23 又有 nm 150m兩式聯(lián)立得150m23解得m225所以散列表需要設(shè)計(jì)225個(gè)單位五算法分析題1給出下列遞歸過(guò)程的執(zhí)行結(jié)果 void unknown int w if

33、w unknown w-1 for int i 1 i w i cout w cout endl 調(diào)用語(yǔ)句為 unknown 4 答案 1 1 2 23 3 3 4 4 4 4 2給出遞歸過(guò)程的執(zhí)行結(jié)果 void unknown int n cout n 10 if int n 10 unknown int n 10 調(diào)用語(yǔ)句為unknown 582 答案 2853給出遞歸過(guò)程的執(zhí)行結(jié)果int unknown int m int value if m value 3 else value unknown m-1 5 return value 執(zhí)行語(yǔ)句為 cout unknown 3 答案 18

34、 4 amn假設(shè)a00存放位置在64410a22存放位置在67610a33101010進(jìn)制表示答案設(shè)數(shù)組元素aij存放在起始地址為loc ij 的存儲(chǔ)單元中 因?yàn)閘oc 22 loc 00 2n2 6442n2 676 所以n 676-2-644 2 15 所以loc 33 loc 00 3153 644453 6925設(shè)單鏈表結(jié)構(gòu)為 struct listnode int data listnode link 下面的程序是以單鏈表為存儲(chǔ)結(jié)構(gòu) 實(shí)現(xiàn)二路歸并排序的算法 要求鏈表不另外占用存儲(chǔ)空間 排序過(guò)程中不移動(dòng)結(jié)點(diǎn)中的元素 只改各鏈結(jié)點(diǎn)中的指針 排序后r仍指示結(jié)果鏈表的第一個(gè)結(jié)點(diǎn)在初始狀態(tài)下

35、所有待排序記錄鏈接在一個(gè)以r為頭指針的單鏈表中例如在算法實(shí)現(xiàn)時(shí)利用了一個(gè)隊(duì)列做為輔助存儲(chǔ) 存儲(chǔ)各有序鏈表構(gòu)成的歸并段的鏈頭指針初始時(shí) 各初始?xì)w并段為只有一個(gè)結(jié)點(diǎn)的有序鏈表隊(duì)列的數(shù)據(jù)類型為queue 其可直接使用的相關(guān)操作有 置空隊(duì)列操作makeempty 將指針x加入到隊(duì)列的隊(duì)尾操作enqueue listnode x 退出隊(duì)頭元素 其值由函數(shù)返回的操作listnode dlqueue 判隊(duì)列空否的函數(shù) 空則返回1 不空則返回0int isempty 解決方法提示 程序首先對(duì)待排序的單鏈表進(jìn)行一次掃描 將它劃分為若干有序的子鏈表 其表頭 指針存放在一個(gè)指針隊(duì)列中 當(dāng)隊(duì)列不空時(shí) 從隊(duì)列中退出兩個(gè)

36、有序子鏈表 對(duì)它們進(jìn)行二路歸并 結(jié)果鏈表的表頭指針存放到隊(duì)列中 如果隊(duì)列中退出一個(gè)有序子鏈表后變成空隊(duì)列 則算法結(jié)束這個(gè)有序子鏈表即為所求在算法實(shí)現(xiàn)時(shí)有 6 處語(yǔ)句缺失請(qǐng)閱讀程序后補(bǔ)上 1 兩路歸并算法void merge listnode ha listnode hb listnode hc listnode pa pb pc if hadata hbdata hc ha pa halink pb hb else hc hb pb hblink pa ha pc hc while pa pb if padata pbdata pclink pa pc pa pa palink else pc

37、link pb pc pb pb pblink if pa pclink pa else pclink pb 2 歸并排序主程序void mergesort listnode r listnode s t queue q if r returns r qenqueue r while s t slink while t 0 sdata tdata s t t tlink if t slink 0 s t qenqueue s while qisempty r qdlqueue if qisempty break s qdlqueue merge r s t qenqueue t 6請(qǐng)讀下列程序

38、該程序是在單鏈表中刪除一個(gè)結(jié)點(diǎn)的算法為空出的地方填上正確的語(yǔ)句7分 void demo2 linklist headlistnode p head 是帶頭結(jié)點(diǎn)的單鏈表刪除p指向的結(jié)點(diǎn) listnode q head while - next p q q- next if q error p not in head q- next p- next free p 已知一完全二叉樹(shù)從根結(jié)點(diǎn)開(kāi)始自頂向下同一層自左向右連續(xù)編號(hào)根結(jié)點(diǎn)的編號(hào)為0閱讀以下程序請(qǐng)回答該程序所實(shí)現(xiàn)的功能 template void linkedtosequent bintreenode ttype a int i if t nu

39、ll a t- getdata linkedtosequent t- getleftchild a2i1 linkedtosequent t- getrightchild a2i2 主程序調(diào)用方式linkedtosequent troota0 答案該程序的功能是將用二叉鏈表表示的完全二叉樹(shù)轉(zhuǎn)換為二叉樹(shù)的順序數(shù)組表示8設(shè)散列表為ht13 散列函數(shù)為 h key key 13用閉散列法解決沖突 對(duì)下列關(guān)鍵碼序列 12 23 45 57 20 03 78 31 15 36 造表 1 采用線性探查法尋找下一個(gè)空位 畫(huà)出相應(yīng)的散列表 并計(jì)算等概率下搜索成功的平均搜索長(zhǎng)度和搜索不成功的平均搜索長(zhǎng)度 2 采

40、用雙散列法尋找下一個(gè)空位 再散列函數(shù)為 rh key 7key 10 1 尋找下一個(gè)空位的公式為 hi hi-1 rh key 13 h1 h key 畫(huà)出相應(yīng)的散列表 并計(jì)算等概率下搜索成功的平均搜索長(zhǎng)度答案使用散列函數(shù)h key key mod 13 有h12 12 h23 10h45 6h57 5h20 7h03 3h78 0h31 5h15 2h36 10利用線性探查法造表0123456789101112781503574520312336121111114121搜索成功的平均搜索長(zhǎng)度為aslsucc 1101111114121 1410 搜索不成功的平均搜索長(zhǎng)度為aslunsucc

41、1132132154321543 3613 利用雙散列法造表 hi hi-1 rh key 13 hi h key 01234567891011127815035745203136231211111135119閱讀下面程序指出其算法的功能并求出其時(shí)間復(fù)雜度int prime int n int i 2x int sqrt n while i x if ni 0 breaki if i x return 1else return 0 2 int sum1 int n int p 1s 0 for int i 1i ni p is p return s 答案1程序功能是判斷n是否是一個(gè)素?cái)?shù)若是則返

42、回?cái)?shù)值1否則返回?cái)?shù)值0該算法的時(shí)間復(fù)雜度為osqrt n 2程序功能是計(jì)算ni 1i該算法的時(shí)間復(fù)雜度為on10判斷一個(gè)帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表l是否對(duì)稱相等的算法如下所示請(qǐng)?jiān)谒惴ǖ?處填入正確的語(yǔ)句 int symmetry dbllist dl int sym 1 dblnode p dl- rlinkq dl- llink while p qp- llink q sym 1 if p- data q- data p p- rlink q q- llink else sym 0 return sym 11閱讀下面程序指出其算法的功能 include stackh int basetrans

43、 int nint b int iresult 0stack s while n 0 i nbn nbspush i while sisempty i sgettop spop result result10i return result 答案該算法是將一個(gè)非負(fù)的十進(jìn)制整數(shù)n轉(zhuǎn)換為另一個(gè)基數(shù)為b的b進(jìn)制數(shù)12閱讀下面程序指出其算法的功能template void binarytree binsearchtree bintreenode tint bs if t null if t- letfchild nullt- data t- leftchild- data t- rightchild n

44、ullt- data t- rightchild- data bs 1binsearchtree t- leftchildbs if bs binsearchtree t- rightchildbs else bs 0 答案該算法是判別給定的以二叉鏈表存儲(chǔ)的二叉樹(shù)是否是二叉搜索樹(shù)采用遞歸算法對(duì)樹(shù)中的所有結(jié)點(diǎn)檢查是否左子樹(shù)上結(jié)點(diǎn)的關(guān)鍵碼都小于它的關(guān)鍵碼右子樹(shù)上結(jié)點(diǎn)的關(guān)鍵碼都大于它的關(guān)鍵碼如滿足上述條件則是二叉搜索樹(shù)六綜合算法題1試設(shè)計(jì)一個(gè)實(shí)現(xiàn)下述要求的查找運(yùn)算函數(shù)locate設(shè)有一個(gè)帶表頭結(jié)點(diǎn)的雙向鏈表l 每個(gè)結(jié)點(diǎn)有4個(gè)數(shù)據(jù)成員指向前驅(qū)結(jié)點(diǎn)的指針llink指向后繼結(jié)點(diǎn)的指針rlink存放字符數(shù)據(jù)

45、的成員data和訪問(wèn)頻度f(wàn)req所有結(jié)點(diǎn)的freq 初始時(shí)都為0每當(dāng)在鏈表上進(jìn)行一次locate l x 操作時(shí)令元素值為x的結(jié)點(diǎn)的訪問(wèn)頻度f(wàn)req加1并將該結(jié)點(diǎn)前移鏈接到與它的訪問(wèn)頻度相等的結(jié)點(diǎn)后面使得鏈表中所有結(jié)點(diǎn)保持按訪問(wèn)頻度遞減的順序排列以使頻繁訪問(wèn)的結(jié)點(diǎn)總是靠近表頭 答案 1 定義鏈表結(jié)構(gòu) struct doublelistnode char data int freq doublelistnode llink rlink 初始時(shí)所有結(jié)點(diǎn)的freq域的值都為0 2 定義函數(shù)doublelistnode locate doublelistnode f char x doublelistnode