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

單項(xiàng)選擇題（每題2分，共10題）1.線(xiàn)性表采用鏈?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.一個(gè)棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是（）。A.54321B.45321C.43512D.123454.若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（）。A.9B.11C.15D.不確定5.深度為5的二叉樹(shù)至多有（）個(gè)結(jié)點(diǎn)。A.16B.32C.31D.106.具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有（）條邊才能確保是一個(gè)連通圖。A.5B.6C.7D.87.對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為（）。A.O(1)B.O(n)C.O(logn)D.O(n^2)8.在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行（）。A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;C.s->next=p->next;p=s;D.p->next=s;s->next=p;9.順序查找法適用于存儲(chǔ)結(jié)構(gòu)為（）的線(xiàn)性表。A.順序存儲(chǔ)B.鏈?zhǔn)酱鎯?chǔ)C.順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)D.索引存儲(chǔ)10.已知一個(gè)有序表為{12,18,24,35,47,50,62,83,90,115,134}，當(dāng)用折半查找90時(shí)，需進(jìn)行（）次比較可找到。A.2B.3C.4D.5答案：1.D2.C3.C4.B5.C6.A7.C8.B9.C10.B多項(xiàng)選擇題（每題2分，共10題）1.以下屬于線(xiàn)性數(shù)據(jù)結(jié)構(gòu)的是（）。A.棧B.隊(duì)列C.二叉樹(shù)D.鏈表2.關(guān)于隊(duì)列的描述，正確的是（）。A.先進(jìn)先出B.先進(jìn)后出C.可以在隊(duì)頭刪除元素D.可以在隊(duì)尾插入元素3.二叉樹(shù)的遍歷方式有（）。A.前序遍歷B.中序遍歷C.后序遍歷D.層次遍歷4.以下哪些排序算法是穩(wěn)定的（）。A.冒泡排序B.選擇排序C.插入排序D.歸并排序5.圖的存儲(chǔ)結(jié)構(gòu)有（）。A.鄰接矩陣B.鄰接表C.十字鏈表D.廣義表6.線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)有（）。A.順序存儲(chǔ)B.鏈?zhǔn)酱鎯?chǔ)C.索引存儲(chǔ)D.散列存儲(chǔ)7.棧的應(yīng)用場(chǎng)景有（）。A.表達(dá)式求值B.括號(hào)匹配C.深度優(yōu)先搜索D.廣度優(yōu)先搜索8.以下關(guān)于樹(shù)和二叉樹(shù)的說(shuō)法正確的是（）。A.樹(shù)中每個(gè)結(jié)點(diǎn)有零個(gè)或多個(gè)子結(jié)點(diǎn)B.二叉樹(shù)中每個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)C.樹(shù)和二叉樹(shù)是同一概念D.二叉樹(shù)是樹(shù)的特殊情況9.查找算法中，平均查找長(zhǎng)度與數(shù)據(jù)規(guī)模有關(guān)的有（）。A.順序查找B.折半查找C.哈希查找D.分塊查找10.以下哪些操作可以在線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上高效完成（）。A.插入B.刪除C.隨機(jī)訪(fǎng)問(wèn)D.順序訪(fǎng)問(wèn)答案：1.ABD2.ACD3.ABCD4.ACD5.ABC6.AB7.ABC8.ABD9.ABD10.ABD判斷題（每題2分，共10題）1.線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更節(jié)省存儲(chǔ)空間。（）2.棧是一種特殊的線(xiàn)性表，它的操作遵循先進(jìn)后出原則。（）3.完全二叉樹(shù)一定是滿(mǎn)二叉樹(shù)。（）4.圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷都需要借助隊(duì)列。（）5.快速排序是一種穩(wěn)定的排序算法。（）6.順序查找適用于任何存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表。（）7.二叉排序樹(shù)的中序遍歷序列是一個(gè)有序序列。（）8.哈希表的查找效率主要取決于哈希函數(shù)和處理沖突的方法。（）9.循環(huán)隊(duì)列中，隊(duì)頭指針和隊(duì)尾指針都有可能指向同一個(gè)位置。（）10.鏈表中的每個(gè)結(jié)點(diǎn)只能包含一個(gè)數(shù)據(jù)域和一個(gè)指針域。（）答案：1.×2.√3.×4.×5.×6.√7.√8.√9.√10.×簡(jiǎn)答題（每題5分，共4題）1.簡(jiǎn)述棧和隊(duì)列的區(qū)別。答案：棧是先進(jìn)后出，操作在棧頂進(jìn)行；隊(duì)列是先進(jìn)先出，在隊(duì)頭刪除、隊(duì)尾插入元素，二者操作規(guī)則和應(yīng)用場(chǎng)景不同。2.簡(jiǎn)述二叉樹(shù)的前序遍歷過(guò)程。答案：先訪(fǎng)問(wèn)根結(jié)點(diǎn)，再遞歸前序遍歷左子樹(shù)，最后遞歸前序遍歷右子樹(shù)。3.簡(jiǎn)述選擇排序的基本思想。答案：在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。4.簡(jiǎn)述哈希表的概念。答案：哈希表是根據(jù)關(guān)鍵碼值（Keyvalue）而直接進(jìn)行訪(fǎng)問(wèn)的數(shù)據(jù)結(jié)構(gòu)，通過(guò)哈希函數(shù)將關(guān)鍵碼映射到表中位置，可快速查找數(shù)據(jù)。討論題（每題5分，共4題）1.討論在不同應(yīng)用場(chǎng)景下，如何選擇合適的排序算法。答案：數(shù)據(jù)規(guī)模小且基本有序選插入排序；對(duì)穩(wěn)定性有要求，規(guī)模不大選冒泡排序；數(shù)據(jù)規(guī)模大，不要求穩(wěn)定選快速排序；數(shù)據(jù)規(guī)模大且要求穩(wěn)定選歸并排序。2.討論線(xiàn)性表順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的優(yōu)缺點(diǎn)。答案：順序存儲(chǔ)優(yōu)點(diǎn)是隨機(jī)訪(fǎng)問(wèn)快，缺點(diǎn)是插入刪除操作效率低、需連續(xù)空間；鏈?zhǔn)酱鎯?chǔ)優(yōu)點(diǎn)是插入刪除靈活，缺點(diǎn)是隨機(jī)訪(fǎng)問(wèn)慢、需額外指針空間。3.討論圖的遍歷算法（深度優(yōu)先和廣度優(yōu)先