數(shù)據(jù)結(jié)構(gòu)C試題庫(kù)及答案

單項(xiàng)選擇題（每題2分，共10題）1.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址（）A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可2.棧和隊(duì)列的共同特點(diǎn)是（）A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素D.沒(méi)有共同點(diǎn)3.具有10個(gè)葉結(jié)點(diǎn)的二叉樹(shù)中有（）個(gè)度為2的結(jié)點(diǎn)。A.8B.9C.10D.114.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（）A.以順序方式存儲(chǔ)B.以鏈?zhǔn)椒绞酱鎯?chǔ)C.以順序方式存儲(chǔ)，且數(shù)據(jù)元素有序D.以鏈?zhǔn)椒绞酱鎯?chǔ)，且數(shù)據(jù)元素有序5.無(wú)向圖的鄰接矩陣是一個(gè)（）A.對(duì)稱矩陣B.上三角矩陣C.下三角矩陣D.對(duì)角矩陣6.快速排序在最壞情況下的時(shí)間復(fù)雜度為（）A.O(n)B.O(n^2)C.O(nlogn)D.O(logn)7.順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是（）A.存儲(chǔ)密度大B.插入和刪除操作方便C.可以隨機(jī)訪問(wèn)D.A和C8.一個(gè)棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是（）A.54321B.45321C.43512D.123459.樹(shù)最適合用來(lái)表示（）A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C.元素之間具有層次關(guān)系的數(shù)據(jù)D.元素之間無(wú)聯(lián)系的數(shù)據(jù)10.哈希表的平均查找長(zhǎng)度（）A.與處理沖突方法有關(guān)而與表的長(zhǎng)度無(wú)關(guān)B.與處理沖突方法無(wú)關(guān)而與表的長(zhǎng)度有關(guān)C.與處理沖突方法和表的長(zhǎng)度都有關(guān)D.與處理沖突方法和表的長(zhǎng)度都無(wú)關(guān)多項(xiàng)選擇題（每題2分，共10題）1.以下屬于線性數(shù)據(jù)結(jié)構(gòu)的有（）A.棧B.隊(duì)列C.二叉樹(shù)D.線性表2.以下關(guān)于二叉樹(shù)的說(shuō)法正確的有（）A.二叉樹(shù)的每個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)B.滿二叉樹(shù)是完全二叉樹(shù)C.完全二叉樹(shù)一定是滿二叉樹(shù)D.二叉樹(shù)的度可以為0、1、23.排序算法中，時(shí)間復(fù)雜度為O(n^2)的有（）A.冒泡排序B.選擇排序C.插入排序D.歸并排序4.以下屬于圖的存儲(chǔ)結(jié)構(gòu)的有（）A.鄰接矩陣B.鄰接表C.十字鏈表D.順序表5.棧的操作特性有（）A.先進(jìn)先出B.先進(jìn)后出C.后進(jìn)先出D.后進(jìn)后出6.以下哪些操作可以在線性表中進(jìn)行（）A.插入元素B.刪除元素C.查找元素D.排序元素7.下列關(guān)于隊(duì)列的說(shuō)法正確的是（）A.隊(duì)列是先進(jìn)先出的線性表B.循環(huán)隊(duì)列可以避免假溢出C.隊(duì)列只能在隊(duì)尾插入元素，在隊(duì)頭刪除元素D.隊(duì)列的存儲(chǔ)結(jié)構(gòu)只能是順序存儲(chǔ)8.以下關(guān)于樹(shù)和二叉樹(shù)的轉(zhuǎn)換說(shuō)法正確的是（）A.任何一棵樹(shù)都可以唯一地轉(zhuǎn)換為一棵二叉樹(shù)B.樹(shù)轉(zhuǎn)換為二叉樹(shù)后，根結(jié)點(diǎn)的右子樹(shù)為空C.二叉樹(shù)轉(zhuǎn)換為樹(shù)后，二叉樹(shù)的根結(jié)點(diǎn)成為樹(shù)的根結(jié)點(diǎn)D.樹(shù)轉(zhuǎn)換為二叉樹(shù)后，二叉樹(shù)的左子樹(shù)表示原樹(shù)結(jié)點(diǎn)的長(zhǎng)子9.哈希函數(shù)的構(gòu)造方法有（）A.直接定址法B.除留余數(shù)法C.平方取中法D.折疊法10.以下哪些是平衡二叉樹(shù)的特點(diǎn)（）A.左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1B.左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)C.平衡二叉樹(shù)是完全二叉樹(shù)D.平衡二叉樹(shù)的查找效率比一般二叉樹(shù)高判斷題（每題2分，共10題）1.線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更節(jié)省存儲(chǔ)空間。（）2.棧和隊(duì)列都是特殊的線性表。（）3.完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必是葉結(jié)點(diǎn)。（）4.圖的深度優(yōu)先搜索遍歷類似于樹(shù)的前序遍歷。（）5.快速排序是一種穩(wěn)定的排序算法。（）6.二叉排序樹(shù)的中序遍歷序列是有序序列。（）7.隊(duì)列的插入操作在隊(duì)頭進(jìn)行，刪除操作在隊(duì)尾進(jìn)行。（）8.無(wú)向圖的鄰接表表示中，頂點(diǎn)vi的度等于第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)。（）9.哈希表的查找效率主要取決于哈希函數(shù)和處理沖突的方法。（）10.堆排序是一種不穩(wěn)定的排序算法。（）簡(jiǎn)答題（每題5分，共4題）1.簡(jiǎn)述線性表順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的優(yōu)缺點(diǎn)。順序存儲(chǔ)優(yōu)點(diǎn)：存儲(chǔ)密度大，可隨機(jī)訪問(wèn)；缺點(diǎn)：插入、刪除操作效率低。鏈?zhǔn)酱鎯?chǔ)優(yōu)點(diǎn)：插入、刪除操作方便；缺點(diǎn)：存儲(chǔ)密度小，不能隨機(jī)訪問(wèn)。2.簡(jiǎn)述棧和隊(duì)列的應(yīng)用場(chǎng)景。棧常用于表達(dá)式求值、括號(hào)匹配等。隊(duì)列常用于廣度優(yōu)先搜索、打印隊(duì)列、任務(wù)調(diào)度等場(chǎng)景。3.簡(jiǎn)述二叉排序樹(shù)的性質(zhì)。二叉排序樹(shù)左子樹(shù)所有結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值，右子樹(shù)所有結(jié)點(diǎn)的值大于根結(jié)點(diǎn)的值，左右子樹(shù)也分別是二叉排序樹(shù)。4.簡(jiǎn)述圖的兩種遍歷方式（深度優(yōu)先遍歷和廣度優(yōu)先遍歷）的基本思想。深度優(yōu)先遍歷：從某頂點(diǎn)出發(fā)，盡可能深地探索，訪問(wèn)完一個(gè)分支后回溯。廣度優(yōu)先遍歷：從某頂點(diǎn)出發(fā)，先訪問(wèn)其鄰接頂點(diǎn)，再依次訪問(wèn)這些鄰接頂點(diǎn)的鄰接頂點(diǎn)。討論題（每題5分，共4題）1.在實(shí)際應(yīng)用中，如何選擇合適的排序算法？要考慮數(shù)據(jù)規(guī)模、數(shù)據(jù)初始狀態(tài)、穩(wěn)定性要求等。小規(guī)模數(shù)據(jù)可選插入排序等；大規(guī)模數(shù)據(jù)，若要求穩(wěn)定可選歸并排序，不要求穩(wěn)定可選快速排序等。2.對(duì)比線性表、棧和隊(duì)列在數(shù)據(jù)處理上的差異。線性表操作靈活，可在任意位置插入刪除；棧是后進(jìn)先出，主要操作在棧頂；隊(duì)列是先進(jìn)先出，插入在隊(duì)尾，刪除在隊(duì)頭，應(yīng)用場(chǎng)景各有不同。3.分析哈希表在不同沖突處理方法下的性能。開(kāi)放定址法簡(jiǎn)單，但易產(chǎn)生堆積現(xiàn)象影響性能；鏈地址法處理沖突靈活，存儲(chǔ)利用率高，在元素較多時(shí)性能較好，不同方法適用于不同數(shù)據(jù)特點(diǎn)。4.討論樹(shù)和二叉樹(shù)在數(shù)據(jù)表示和處理上的聯(lián)系與區(qū)別。聯(lián)系：樹(shù)可轉(zhuǎn)換為二叉樹(shù)，方便統(tǒng)一處理。區(qū)別：二叉樹(shù)每個(gè)結(jié)點(diǎn)最多兩個(gè)子結(jié)點(diǎn)，樹(shù)結(jié)點(diǎn)子結(jié)點(diǎn)數(shù)任意；二叉樹(shù)有嚴(yán)格的左右子樹(shù)之分，樹(shù)無(wú)此限制，處理方法也有差異。答案單項(xiàng)選擇題1.D2.C3.B4.C5.A6.B7.D8.C9.C10.C多項(xiàng)選擇題1.ABD