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

單項(xiàng)選擇題（每題2分，共10題）1.線性表采用順序存儲(chǔ)時(shí)，其地址（）A.一定連續(xù)B.部分連續(xù)C.不一定連續(xù)D.都不連續(xù)2.棧的特點(diǎn)是（）A.先進(jìn)先出B.先進(jìn)后出C.隨機(jī)進(jìn)出D.只進(jìn)不出3.隊(duì)列的“先進(jìn)先出”特性是指（）A.最早插入隊(duì)列中的元素總是最后被刪除B.當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先C.每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作D.最先插入隊(duì)列中的元素總是最先被刪除4.樹(shù)最適合用來(lái)表示（）A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無(wú)聯(lián)系的數(shù)據(jù)5.具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為（）A.10B.45C.90D.1006.對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間為（）A.O(1)B.O(logn)C.O(n)D.O(n^2)7.哈希表的平均查找長(zhǎng)度（）A.與處理沖突方法有關(guān)而與表的長(zhǎng)度無(wú)關(guān)B.與處理沖突方法無(wú)關(guān)而與表的長(zhǎng)度有關(guān)C.與處理沖突方法有關(guān)且與表的長(zhǎng)度有關(guān)D.與處理沖突方法無(wú)關(guān)且與表的長(zhǎng)度無(wú)關(guān)8.下列排序算法中，平均時(shí)間復(fù)雜度最小的是（）A.冒泡排序B.選擇排序C.插入排序D.快速排序9.若某完全二叉樹(shù)的深度為h，則該完全二叉樹(shù)中至少有（）個(gè)節(jié)點(diǎn)A.2^(h-1)B.2^(h-1)-1C.2^hD.2^h-110.在一個(gè)單鏈表中，若要?jiǎng)h除p節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)，則執(zhí)行（）A.p=p->next;B.p->next=p->next->next;C.p->next=p;D.p=p->next->next;多項(xiàng)選擇題（每題2分，共10題）1.以下屬于線性數(shù)據(jù)結(jié)構(gòu)的有（）A.棧B.隊(duì)列C.樹(shù)D.圖2.順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)有（）A.存儲(chǔ)密度大B.插入操作方便C.邏輯上相鄰的元素物理上也相鄰D.查找操作效率高3.關(guān)于棧的說(shuō)法正確的是（）A.可以作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)B.有進(jìn)棧和出棧操作C.棧頂元素總是最后被插入的元素D.棧底元素總是最先被插入的元素4.以下哪些是隊(duì)列的基本操作（）A.入隊(duì)B.出隊(duì)C.取隊(duì)頭元素D.取隊(duì)尾元素5.樹(shù)的遍歷方式有（）A.前序遍歷B.中序遍歷C.后序遍歷D.層次遍歷6.圖的存儲(chǔ)結(jié)構(gòu)有（）A.鄰接矩陣B.鄰接表C.十字鏈表D.鄰接多重表7.以下排序算法中，穩(wěn)定的排序算法有（）A.冒泡排序B.插入排序C.歸并排序D.選擇排序8.哈希函數(shù)的構(gòu)造方法有（）A.直接定址法B.除留余數(shù)法C.數(shù)字分析法D.平方取中法9.完全二叉樹(shù)的特點(diǎn)有（）A.葉子節(jié)點(diǎn)只能出現(xiàn)在最下兩層B.最下層的葉子節(jié)點(diǎn)一定集中在左部連續(xù)位置C.倒數(shù)第二層若有葉子節(jié)點(diǎn)，一定都在右部連續(xù)位置D.度為1的節(jié)點(diǎn)只有0個(gè)或1個(gè)10.以下關(guān)于雙向鏈表說(shuō)法正確的是（）A.可以雙向遍歷B.插入操作比單鏈表復(fù)雜C.每個(gè)節(jié)點(diǎn)有兩個(gè)指針域D.查找操作效率高于單鏈表判斷題（每題2分，共10題）1.線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（）2.棧和隊(duì)列都是特殊的線性表。（）3.二叉樹(shù)的前序遍歷和中序遍歷結(jié)果不同。（）4.無(wú)向圖中所有頂點(diǎn)的度之和等于邊數(shù)的2倍。（）5.快速排序在最壞情況下的時(shí)間復(fù)雜度為O(n^2)。（）6.哈希表中沖突是不可避免的。（）7.堆排序是一種穩(wěn)定的排序算法。（）8.一棵滿二叉樹(shù)一定是完全二叉樹(shù)。（）9.單鏈表的刪除操作不需要移動(dòng)元素。（）10.隊(duì)列的插入操作在隊(duì)頭進(jìn)行。（）簡(jiǎn)答題（每題5分，共4題）1.簡(jiǎn)述棧和隊(duì)列的區(qū)別。棧是先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，操作在棧頂進(jìn)行；隊(duì)列是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，入隊(duì)在隊(duì)尾，出隊(duì)在隊(duì)頭。2.簡(jiǎn)述圖的鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。鄰接矩陣優(yōu)點(diǎn)是簡(jiǎn)單直觀，便于判斷頂點(diǎn)間是否有邊；缺點(diǎn)是存儲(chǔ)稀疏圖浪費(fèi)空間。鄰接表優(yōu)點(diǎn)是存儲(chǔ)稀疏圖節(jié)省空間；缺點(diǎn)是判斷頂點(diǎn)間是否有邊較復(fù)雜。3.簡(jiǎn)述插入排序的基本思想。將未排序數(shù)據(jù)插入已排序序列的合適位置。初始已排序序列只有第一個(gè)元素，然后依次將后面元素插入已排好序的序列中。4.簡(jiǎn)述二叉樹(shù)的中序遍歷遞歸算法。若二叉樹(shù)為空，返回。否則，先中序遍歷左子樹(shù)，訪問(wèn)根節(jié)點(diǎn)，再中序遍歷右子樹(shù)。討論題（每題5分，共4題）1.討論在不同應(yīng)用場(chǎng)景下如何選擇合適的數(shù)據(jù)結(jié)構(gòu)。在需要頻繁插入、刪除操作時(shí)，鏈?zhǔn)浇Y(jié)構(gòu)合適，如單鏈表；需要快速查找，哈希表或平衡二叉樹(shù)較好；元素有序且訪問(wèn)順序固定，順序表可行；表示層次關(guān)系用樹(shù)，網(wǎng)狀關(guān)系用圖。2.分析排序算法中穩(wěn)定性的重要性。在一些特定應(yīng)用中，穩(wěn)定性很關(guān)鍵。比如按成績(jī)排序?qū)W生記錄，若排序算法不穩(wěn)定，相同成績(jī)學(xué)生記錄順序可能改變，若還有其他關(guān)聯(lián)信息，可能導(dǎo)致錯(cuò)誤結(jié)果，穩(wěn)定排序能保證相同元素原有順序。3.探討哈希表中處理沖突的方法及其優(yōu)缺點(diǎn)。開(kāi)放定址法優(yōu)點(diǎn)是簡(jiǎn)單直觀，缺點(diǎn)是可能形成聚集現(xiàn)象。鏈地址法優(yōu)點(diǎn)是不會(huì)產(chǎn)生聚集，缺點(diǎn)是增加指針空間開(kāi)銷(xiāo)。再哈希法計(jì)算復(fù)雜但可減少?zèng)_突。不同方法適用于不同情況。4.論述樹(shù)和二叉樹(shù)在數(shù)據(jù)表示和處理上的聯(lián)系與區(qū)別。聯(lián)系：二叉樹(shù)是樹(shù)的特殊形式，很多樹(shù)的處理算法可借鑒二叉樹(shù)。區(qū)別：樹(shù)節(jié)點(diǎn)孩子數(shù)無(wú)限制，二叉樹(shù)節(jié)點(diǎn)最多兩個(gè)孩子；二叉樹(shù)有嚴(yán)格左右之分，樹(shù)無(wú)；二叉樹(shù)遍歷方法更豐富規(guī)范。答案單項(xiàng)選擇題1.A2.B3.D4.C5.B6.B7.C8.D9.A10.B多項(xiàng)選擇題1.AB2.AC