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

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

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