數(shù)據(jù)結(jié)構(gòu)考試題目及答案一、選擇題（每題2分，共30分）1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的（）以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。A.操作對(duì)象B.計(jì)算方法C.邏輯存儲(chǔ)D.數(shù)據(jù)映象答案：A。數(shù)據(jù)結(jié)構(gòu)研究的是數(shù)據(jù)的操作對(duì)象、對(duì)象間的關(guān)系以及對(duì)對(duì)象的運(yùn)算，計(jì)算方法側(cè)重于算法設(shè)計(jì)，邏輯存儲(chǔ)和數(shù)據(jù)映象是數(shù)據(jù)結(jié)構(gòu)中的一部分概念，并非核心研究?jī)?nèi)容。2.算法分析的目的是（）。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易讀性和文檔性答案：C。算法分析主要是對(duì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度等效率指標(biāo)進(jìn)行分析，目的是找出算法的優(yōu)劣并進(jìn)行改進(jìn)，數(shù)據(jù)結(jié)構(gòu)的合理性是設(shè)計(jì)階段考慮的，輸入輸出關(guān)系不是分析的主要目的，易讀性和文檔性是算法設(shè)計(jì)的附加要求。3.以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)。A.棧B.隊(duì)列C.完全二叉樹D.線性表答案：C。棧、隊(duì)列和線性表都是線性數(shù)據(jù)結(jié)構(gòu)，元素之間是一對(duì)一的線性關(guān)系，而完全二叉樹是樹形結(jié)構(gòu)，元素之間是一對(duì)多的關(guān)系，屬于非線性數(shù)據(jù)結(jié)構(gòu)。4.若進(jìn)棧序列為1,2,3,4，進(jìn)棧過程中可以出棧，則下列不可能的一個(gè)出棧序列是（）。A.1,4,3,2B.2,3,4,1C.3,1,4,2D.3,4,2,1答案：C。對(duì)于進(jìn)棧序列1,2,3,4，選項(xiàng)A可以1進(jìn)棧1出棧，2、3、4進(jìn)棧，4、3、2出棧；選項(xiàng)B可以1、2進(jìn)棧，2出棧，3進(jìn)棧3出棧，4進(jìn)棧4出棧，1出棧；選項(xiàng)D可以1、2、3進(jìn)棧，3出棧，4進(jìn)棧4出棧，2、1出棧；而選項(xiàng)C若3先出棧，此時(shí)棧內(nèi)元素為1、2（棧底到棧頂），接下來不可能1出棧，所以該出棧序列不可能。5.循環(huán)隊(duì)列用數(shù)組A[0…m1]存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（）。A.(rearfront+m)%mB.rearfront+1C.rearfront1D.rearfront答案：A。在循環(huán)隊(duì)列中，為了區(qū)分隊(duì)空和隊(duì)滿的情況，采用取模運(yùn)算來計(jì)算隊(duì)列元素個(gè)數(shù)。當(dāng)rear>=front時(shí)，元素個(gè)數(shù)為rearfront；當(dāng)rear<front時(shí)，元素個(gè)數(shù)為rearfront+m，綜合起來就是(rearfront+m)%m。6.若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。A.順序表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表答案：A。順序表可以通過數(shù)組下標(biāo)直接存取指定序號(hào)的元素，時(shí)間復(fù)雜度為O(1)，在最后進(jìn)行插入和刪除操作的時(shí)間復(fù)雜度也為O(1)；而鏈表（雙鏈表、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表、單循環(huán)鏈表）存取指定序號(hào)元素需要從頭節(jié)點(diǎn)開始遍歷，時(shí)間復(fù)雜度為O(n)。7.一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為（）。A.?log?n?+1B.log?nC.?log?n?D.?log?n?+1答案：A。根據(jù)完全二叉樹的性質(zhì)，設(shè)完全二叉樹的深度為h，則2^(h1)<=n<2^h，對(duì)不等式兩邊取對(duì)數(shù)可得h1<=log?n<h，所以h=?log?n?+1。8.已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，則它的前序遍歷序列是（）。A.acbedB.decabC.deabcD.cedba答案：D。后序遍歷的最后一個(gè)元素是根節(jié)點(diǎn)，所以根節(jié)點(diǎn)為c；在中序遍歷中，根節(jié)點(diǎn)將序列分為左子樹和右子樹，所以左子樹的中序遍歷為deba，右子樹為空；根據(jù)后序遍歷可知左子樹的根節(jié)點(diǎn)為e，再結(jié)合中序遍歷可進(jìn)一步劃分左右子樹，逐步構(gòu)建出二叉樹，得到前序遍歷序列為cedba。9.對(duì)于有向圖，其鄰接矩陣表示相比鄰接表表示更適用于（）。A.求一個(gè)頂點(diǎn)的所有鄰接頂點(diǎn)B.確定邊的數(shù)目C.進(jìn)行圖的廣度優(yōu)先遍歷D.求一個(gè)頂點(diǎn)的度答案：B。鄰接矩陣是一個(gè)二維數(shù)組，矩陣中元素為1表示有邊，通過統(tǒng)計(jì)矩陣中非零元素的個(gè)數(shù)可以很方便地確定邊的數(shù)目；而求一個(gè)頂點(diǎn)的所有鄰接頂點(diǎn)、進(jìn)行圖的廣度優(yōu)先遍歷，鄰接表更高效；對(duì)于有向圖，鄰接矩陣求一個(gè)頂點(diǎn)的入度和出度需要遍歷一行和一列，鄰接表求入度和出度也有相應(yīng)的方法，所以鄰接矩陣在求頂點(diǎn)度方面沒有明顯優(yōu)勢(shì)。10.采用折半查找法查找長(zhǎng)度為n的有序表時(shí)，查找每個(gè)元素的平均查找長(zhǎng)度為（）。A.O(n2)B.O(nlog?n)C.O(log?n)D.O(n)答案：C。折半查找每次將查找范圍縮小一半，其時(shí)間復(fù)雜度為O(log?n)，所以查找每個(gè)元素的平均查找長(zhǎng)度也為O(log?n)。11.排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱為（）。A.希爾排序B.歸并排序C.插入排序D.選擇排序答案：D。選擇排序的基本思想是每次從待排序序列中選擇最?。ɑ蜃畲螅┑脑?，將其與待排序序列的第一個(gè)元素交換位置，重復(fù)這個(gè)過程直到整個(gè)序列有序，也就是從未排序序列中挑選元素放入已排序序列的一端；希爾排序是按照一定的增量對(duì)序列進(jìn)行分組插入排序；歸并排序是將兩個(gè)或多個(gè)有序子序列合并成一個(gè)有序序列；插入排序是將未排序元素插入到已排序序列的合適位置。12.已知一組關(guān)鍵字為(25,48,36,72,79,82,23,40,16,35)，其中每相鄰兩個(gè)為有序子序列。對(duì)這些子序列進(jìn)行一趟兩兩歸并的結(jié)果是（）。A.25,36,48,72,23,40,79,82,16,35B.25,36,48,72,16,23,40,79,82,35C.25,48,36,72,79,82,23,40,16,35D.25,36,48,72,23,40,82,79,16,35答案：A。兩兩歸并是將相鄰的兩個(gè)有序子序列合并成一個(gè)有序序列。原序列中相鄰的有序子序列為(25,48)、(36,72)、(79,82)、(23,40)、(16,35)，將它們兩兩歸并得到(25,36,48,72)、(23,40,79,82)、(16,35)，即25,36,48,72,23,40,79,82,16,35。13.散列技術(shù)中的沖突指的是（）。A.兩個(gè)元素具有相同的序號(hào)B.兩個(gè)元素的鍵值不同，而其他屬性相同C.數(shù)據(jù)元素過多D.不同鍵值的元素對(duì)應(yīng)于相同的存儲(chǔ)地址答案：D。散列技術(shù)是通過散列函數(shù)將鍵值映射到存儲(chǔ)地址，沖突就是不同的鍵值經(jīng)過散列函數(shù)計(jì)算后得到相同的存儲(chǔ)地址。14.若一個(gè)有向圖的鄰接矩陣中，主對(duì)角線以下的元素均為零，則該圖的拓?fù)渑判颍ǎ?。A.一定存在B.一定不存在C.不一定存在D.無法確定是否存在答案：A。主對(duì)角線以下的元素均為零的有向圖是一個(gè)有向無環(huán)圖（DAG），有向無環(huán)圖一定存在拓?fù)渑判颉?5.在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應(yīng)作（）型調(diào)整以使其平衡。A.LLB.LRC.RLD.RR答案：C。根據(jù)平衡二叉樹的調(diào)整規(guī)則，當(dāng)最低不平衡結(jié)點(diǎn)A的左孩子平衡因子為0，右孩子平衡因子為1時(shí)，需要進(jìn)行RL型調(diào)整。二、填空題（每題2分，共20分）1.數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，樹形結(jié)構(gòu)屬于______結(jié)構(gòu)。答案：非線性。樹形結(jié)構(gòu)中節(jié)點(diǎn)之間是一對(duì)多的關(guān)系，不符合線性結(jié)構(gòu)一對(duì)一的關(guān)系特點(diǎn)，所以屬于非線性結(jié)構(gòu)。2.算法的時(shí)間復(fù)雜度是指算法執(zhí)行過程中所需要的______，通常用大O表示法來描述。答案：基本運(yùn)算次數(shù)。時(shí)間復(fù)雜度是衡量算法執(zhí)行效率的一個(gè)指標(biāo)，通過計(jì)算算法中基本運(yùn)算的次數(shù)來確定。3.設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6依次通過棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)的順序是e2,e4,e3,e6,e5,e1，則棧S的容量至少應(yīng)該是______。答案：3。根據(jù)出隊(duì)順序反推出棧順序?yàn)閑2,e4,e3,e6,e5,e1，進(jìn)棧和出棧過程為：e1、e2進(jìn)棧，e2出棧，e3、e4進(jìn)棧，e4出棧，e3出棧，e5、e6進(jìn)棧，e6出棧，e5出棧，e1出棧，在這個(gè)過程中棧中最多同時(shí)存在3個(gè)元素，所以棧S的容量至少應(yīng)該是3。4.線性表L=(a1,a2,…,an)用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是______。答案：(n1)/2。若刪除第i個(gè)元素，需要移動(dòng)ni個(gè)元素，刪除每個(gè)元素的概率為1/n，平均移動(dòng)元素個(gè)數(shù)為∑(ni)/n（i從1到n），計(jì)算可得(n1)/2。5.深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為______。答案：16。滿二叉樹的葉子節(jié)點(diǎn)都在最后一層，深度為h的滿二叉樹最后一層的節(jié)點(diǎn)數(shù)為2^(h1)，當(dāng)h=5時(shí)，葉子節(jié)點(diǎn)個(gè)數(shù)為2^(51)=16。6.設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，則其鄰接表中表頭結(jié)點(diǎn)的個(gè)數(shù)為______，表結(jié)點(diǎn)的個(gè)數(shù)為______。答案：n；2e。鄰接表中表頭結(jié)點(diǎn)的個(gè)數(shù)等于圖的頂點(diǎn)數(shù)n，對(duì)于無向圖，每條邊在鄰接表中會(huì)出現(xiàn)兩次，所以表結(jié)點(diǎn)的個(gè)數(shù)為2e。7.已知有序表為(12,18,24,35,47,50,62,83,90,115,134)，當(dāng)用折半查找法查找90時(shí)，需進(jìn)行______次比較可確定查找成功。答案：2。折半查找的過程：首先取中間元素50，90大于50，在右半部分查找；右半部分的中間元素為90，找到目標(biāo)元素，共進(jìn)行了2次比較。8.對(duì)n個(gè)記錄的表進(jìn)行簡(jiǎn)單選擇排序，所需要進(jìn)行的關(guān)鍵字間的比較次數(shù)為______。答案：n(n1)/2。簡(jiǎn)單選擇排序在第i趟排序中需要從ni+1個(gè)元素中選擇最小的元素，需要進(jìn)行ni次比較，總的比較次數(shù)為∑(ni)（i從1到n1），計(jì)算可得n(n1)/2。9.散列函數(shù)有一個(gè)共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以______取其值域的每個(gè)值。答案：均勻的概率。散列函數(shù)的設(shè)計(jì)要求是盡量使不同的鍵值均勻地映射到值域的各個(gè)位置，以減少?zèng)_突的發(fā)生。10.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的連通圖，其提供樹中的頂點(diǎn)數(shù)和邊數(shù)分別為______和______。答案：n；n1。提供樹是連通圖的極小連通子圖，包含圖的所有頂點(diǎn)且邊數(shù)最少，對(duì)于有n個(gè)頂點(diǎn)的連通圖，其提供樹的邊數(shù)為n1。三、判斷題（每題1分，共10分）1.數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。（）答案：正確。數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。2.算法的時(shí)間復(fù)雜度都可以用大O表示法準(zhǔn)確地表示出來。（）答案：錯(cuò)誤。大O表示法是一種漸進(jìn)上界的表示方法，有些算法的時(shí)間復(fù)雜度可能無法用簡(jiǎn)單的大O表示法準(zhǔn)確描述。3.棧和隊(duì)列都是線性表，只是在插入和刪除操作時(shí)受到了一些限制。（）答案：正確。棧是后進(jìn)先出的線性表，隊(duì)列是先進(jìn)先出的線性表，它們?cè)诓迦牒蛣h除操作上有特定的規(guī)則。4.線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更有利于進(jìn)行插入和刪除操作。（）答案：錯(cuò)誤。線性表的順序存儲(chǔ)結(jié)構(gòu)在插入和刪除操作時(shí)需要移動(dòng)大量元素，時(shí)間復(fù)雜度較高；而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只需要修改指針，更適合插入和刪除操作。5.完全二叉樹一定是滿二叉樹。（）答案：錯(cuò)誤。滿二叉樹是完全二叉樹的一種特殊情況，完全二叉樹不一定是滿二叉樹。6.有向圖的鄰接矩陣一定是不對(duì)稱的。（）答案：錯(cuò)誤。有向圖的鄰接矩陣可能是對(duì)稱的，當(dāng)有向圖是對(duì)稱有向圖時(shí)，鄰接矩陣是對(duì)稱的。7.折半查找只適用于有序表，且要求表采用順序存儲(chǔ)結(jié)構(gòu)。（）答案：正確。折半查找需要通過中間元素來縮小查找范圍，所以要求表是有序的，并且通過數(shù)組下標(biāo)隨機(jī)訪問元素，需要順序存儲(chǔ)結(jié)構(gòu)。8.快速排序的平均時(shí)間復(fù)雜度為O(nlog?n)，因此它是一種穩(wěn)定的排序算法。（）答案：錯(cuò)誤。快速排序的平均時(shí)間復(fù)雜度為O(nlog?n)，但它是一種不穩(wěn)定的排序算法，在排序過程中可能會(huì)改變相同元素的相對(duì)順序。9.散列函數(shù)越復(fù)雜越好，因?yàn)檫@樣可以減少?zèng)_突的發(fā)生。（）答案：錯(cuò)誤。散列函數(shù)并不是越復(fù)雜越好，過于復(fù)雜的散列函數(shù)會(huì)增加計(jì)算時(shí)間，而且不一定能有效減少?zèng)_突，一個(gè)好的散列函數(shù)應(yīng)該在計(jì)算簡(jiǎn)單和減少?zèng)_突之間取得平衡。10.拓?fù)渑判虻慕Y(jié)果是唯一的。（）答案：錯(cuò)誤。拓?fù)渑判虻慕Y(jié)果不一定是唯一的，對(duì)于一個(gè)有向無環(huán)圖，可能存在多種拓?fù)渑判虻慕Y(jié)果。四、簡(jiǎn)答題（每題5分，共20分）1.簡(jiǎn)述線性結(jié)構(gòu)和非線性結(jié)構(gòu)的區(qū)別。答案：線性結(jié)構(gòu)中元素之間存在一對(duì)一的線性關(guān)系，即除了第一個(gè)元素和最后一個(gè)元素外，每個(gè)元素都有唯一的前驅(qū)和后繼。常見的線性結(jié)構(gòu)有線性表、棧、隊(duì)列等。而非線性結(jié)構(gòu)中元素之間的關(guān)系不是一對(duì)一的，可能是一對(duì)多或多對(duì)多的關(guān)系。例如樹形結(jié)構(gòu)中一個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)，圖結(jié)構(gòu)中節(jié)點(diǎn)之間的關(guān)系更為復(fù)雜。線性結(jié)構(gòu)在存儲(chǔ)和操作上相對(duì)簡(jiǎn)單，通?？梢酝ㄟ^順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)，操作主要圍繞元素的線性順序進(jìn)行；非線性結(jié)構(gòu)的存儲(chǔ)和操作相對(duì)復(fù)雜，需要根據(jù)具體的結(jié)構(gòu)特點(diǎn)設(shè)計(jì)合適的算法。2.什么是棧的上溢和下溢？如何避免？答案：棧的上溢是指當(dāng)棧滿時(shí)再進(jìn)行入棧操作，導(dǎo)致?？臻g不足的情況。棧的下溢是指當(dāng)?？諘r(shí)再進(jìn)行出棧操作，出現(xiàn)錯(cuò)誤的情況。為了避免棧的上溢，可以在入棧操作前檢查棧是否已滿，如果棧已滿則給出相應(yīng)的提示信息或者進(jìn)行擴(kuò)容操作。對(duì)于順序棧，可以動(dòng)態(tài)增加數(shù)組的大??；對(duì)于鏈?zhǔn)綏＃灰獌?nèi)存允許可以不斷添加節(jié)點(diǎn)。為了避免棧的下溢，在出棧操作前檢查棧是否為空，如果棧為空則給出相應(yīng)的提示信息，不進(jìn)行出棧操作。3.簡(jiǎn)述二叉排序樹的定義和特點(diǎn)。答案：二叉排序樹（BinarySearchTree，BST）是一種二叉樹，對(duì)于樹中的每個(gè)節(jié)點(diǎn)，其左子樹中的所有節(jié)點(diǎn)的值都小于該節(jié)點(diǎn)的值，其右子樹中的所有節(jié)點(diǎn)的值都大于該節(jié)點(diǎn)的值，并且左子樹和右子樹也分別是二叉排序樹。二叉排序樹的特點(diǎn)包括：中序遍歷二叉排序樹可以得到一個(gè)有序的序列；插入和刪除操作的時(shí)間復(fù)雜度與樹的高度有關(guān)，在平均情況下為O(log?n)，但在最壞情況下（樹退化為鏈表）為O(n)；可以方便地進(jìn)行查找操作，查找一個(gè)元素的時(shí)間復(fù)雜度同樣與樹的高度有關(guān)。4.簡(jiǎn)述圖的深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）的基本思想。答案：深度優(yōu)先搜索（DFS）的基本思想是從圖的某個(gè)頂點(diǎn)v出發(fā)，首先訪問該頂點(diǎn)，然后遞歸地訪問v的一個(gè)未被訪問的鄰接頂點(diǎn)，接著再?gòu)倪@個(gè)鄰接頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索，直到圖中所有與v有路徑相通的頂點(diǎn)都被訪問到。如果此時(shí)圖中還有未被訪問的頂點(diǎn)，則另選一個(gè)未被訪問的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問。廣度優(yōu)先搜索（BFS）的基本思想是從圖的某個(gè)頂點(diǎn)v出發(fā)，首先訪問v，然后依次訪問v的所有未被訪問的鄰接頂點(diǎn)，再依次訪問這些鄰接頂點(diǎn)的未被訪問的鄰接頂點(diǎn)，如此逐層進(jìn)行，直到圖中所有與v有路徑相通的頂點(diǎn)都被訪問到。如果此時(shí)圖中還有未被訪問的頂點(diǎn)，則另選一個(gè)未被訪問的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問。通常使用隊(duì)列來輔助實(shí)現(xiàn)廣度優(yōu)先搜索。五、算法設(shè)計(jì)題（每題10分，共20分）1.設(shè)計(jì)一個(gè)算法，將一個(gè)帶頭結(jié)點(diǎn)的單鏈表就地逆置。```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverseList(head):ifnotheadornothead.next:returnheadprev=Nonecurr=head.nextwhilecurr:next_node