《數(shù)據(jù)結構與算法》期末考試復習題庫（含答案）

PAGEPAGE1《數(shù)據(jù)結構與算法》期末考試復習題庫（含答案）一、單選題1.從一個具有n個結點的單鏈表中查找值為x結點,在查找成功情況下,需平均比較()個結點。A、nB、n/2C、(n-1)/2D、(n+1)/2答案：D2.在邏輯上可以把數(shù)據(jù)結構分成（）。A、動態(tài)結構和靜態(tài)結構B、緊湊結構和非緊湊結構C、線性結構和非線性結構D、內部結構和外部結構答案：C3.鏈式存儲結構所占存儲空間（）A、分兩部分，一部分存儲結點的值，另一部分存放表示結點間關系的指針B、只有一部分，存放結點的值C、只有一部分，存儲表示結點間關系的指針D、分兩部分，一部分存放結點的值，另一部分存放結點所占單元數(shù)答案：A4.算法能正確的實現(xiàn)預定功能的特性稱為算法的（）。A、正確性B、易讀性C、健壯性D、高效性答案：A5.隊列是限定在（）進行操作的線性表。A、中間B、隊首C、隊尾D、端點答案：D6.下列算法的時間復雜度是（）for(i=0;i<n;i++)for(j=0;j<n;j++)C[i][j]=i+j;A、O(2)B、O(n)C、O(log2n)D、O(n)答案：D7.帶頭結點的單鏈表head為空的判定條件是()。A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL答案：B8.計算機算法必須具備輸入、輸出和（）。1A、計算方法B、排序方法C、解決問題的有限運算步驟D、程序設計方法答案：C9.下面程序的時間復雜為（）。for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}A、O(n)B、O(n)C、O(n）D、O(n)答案：B10.同一隊列內各元素的類型()。A、必須一致B、不能一致C、可以不一致D、不限制答案：A11.冒泡排序的方法對n個數(shù)據(jù)進行排序，第一趟排序共需要比較（）次。A、1B、2C、n-1D、n答案：C12.具有64個結點的完全二叉樹的深度為()A、5B、6C、7D、8答案：C13.二叉樹按某種順序線索化后，任一結點均有指向其前趨和后繼的線索，這種說法()。A、正確B、錯誤C、不確定D、不存在答案：B14.數(shù)據(jù)在計算機中存儲器內表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（）。A、存儲結構B、邏輯結構C、順序存儲結構D、鏈式存儲結構答案：C15.下列4種基本邏輯結構中，數(shù)據(jù)元素之間關系最弱的是（）。A、集合B、線性結構C、樹形結構D、圖形結構答案：A16.隊列是一個(C)線性表結構。A、不加限制的B、推廣了的C、加了限制的D、非答案：C17.在一個長度為n的順序存儲線性表中，刪除第i個元素(1...i...n)時，需要從前向后依次前移()個元素。A、n-iB、n-i+1C、n-i-1D、i答案：A18.假定在一棵二叉樹中，雙分支結點數(shù)為15，單分支結點數(shù)為30，則葉子結點數(shù)為（）個。A、45B、15C、16D、31答案：C19.就平均性而言，下面最好的內排序方法是（）排序法A、冒泡排序B、快速排序C、選擇排序D、希爾排序答案：B20.隊列中的元素個數(shù)是()。A、不變的B、可變的C、任意的D、0答案：B21.在按行優(yōu)先順序存儲的三元組表中,下述陳述錯誤的是()。A、同一行的非零元,是按列號遞增次序存儲的B、同一列的非零元,是按行號遞增次序存儲的C、三元組表中三元組行號遞增的D、三元組表中三元組列號遞增的答案：D22.某二叉樹的先序遍歷序列是abdgcefh，中序遍歷序列是dgbaechf，則其后序遍歷序列是（）。A、gdbehfcaB、abcdefghC、gdbaefchD、ghbcdefa答案：A23.動態(tài)查找包括（）查找。A、順序表B、二叉排序樹C、有序表D、索引順序表答案：B24.下列關于算法的說法,正確的是()。A、程序一定是算法。B、算法的可行性是指指令不能有二義性。C、算法可以沒有輸入但必須有1個以上的輸出。D、算法必須是用計算機語言描述的。答案：C25.設指針變量p指向單鏈表中結點A，若刪除單鏈表中結點A，則需要修改指針的操作序列為（）。A、q=p.next；p.data=q.data；p.next=q.next；B、q=p.next；q.data=p.data；p.next=q.next；C、q=p.next；p.next=q.next；D、q=p.next；p.data=q.data；答案：A26.在下列鏈表中不能從當前結點出發(fā)訪問到其余各結點的是()。A、雙向鏈表B、單循環(huán)鏈表C、單鏈表D、雙向循環(huán)鏈表答案：C27.經過下列棧的運算后,x的值是()。InitStack(s)(初始化棧);Push(s,a);Push(s,b);ReadTop(s);Pop(s,x);A、B、C、1D、0答案：B28.在一個長度為n的順序存儲線性表中，向第i個元素(1...i...n)之前插入一個新元素時，需要從后向前依次后移()個元素。.A、n-iB、n-i+1C、n-i-1D、i答案：B解析：；29.非線性結構中的每個結點()。A、無直接前趨結點B、無直接后繼結點C、只有一個直接前趨結點和一個直接后繼結點D、可能有多個直接前趨結點和多個直接后繼結點答案：D30.無向圖頂點v的度是關聯(lián)于該頂點（）的數(shù)目。A、頂點B、邊C、序號D、下標答案：B31.對線性表進行二分查找時，要求線性表必須（）。A、以順序方式存儲B、以鏈接方式存儲，且結點按關鍵字有序排序C、以鏈接方式存儲D、以順序方式存儲，且結點按關鍵字有序排序答案：D32.設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數(shù)至少為()。A、2B、2-1C、2D、h+1答案：B33.數(shù)據(jù)結構通常是研究數(shù)據(jù)的（）及它們之間的相互關系。A、存儲結構和邏輯結構B、存儲和抽象C、聯(lián)系和抽象D、聯(lián)系與邏輯答案：A判斷題1.鏈隊列在一定范圍內不會出現(xiàn)隊滿的情況。A、正確B、錯誤答案：A2.一個棧的輸入序列為：A，B，C，D，可以得到輸出序列：C，A，B，D。A、正確B、錯誤答案：B3.一棵樹中的葉子結點數(shù)一定等于與其對應的二叉樹中的葉子結點數(shù)。A、正確B、錯誤答案：B4.一個數(shù)據(jù)結構是由一個邏輯結構和這個邏輯結構上的一個基本運算集構成的整體。A、正確B、錯誤答案：A5.如果二叉樹中某結點的度為1，則說該結點只有一棵子樹。A、正確B、錯誤答案：A6.在完全二叉樹中,若一個結點沒有左孩子,則它必然是葉子結點。A、正確B、錯誤答案：A7.(10)具有n個葉子結點的哈夫曼樹共有2n-1個結點。A、正確B、錯誤答案：A8.從邏輯關系上講，數(shù)據(jù)結構主要分為線性結構和非線性結構兩類。A、正確B、錯誤答案：A9.在C或C++語言中設順序棧的長度為MAXLEN，則top=MAXLEN時表示隊滿。A、正確B、錯誤答案：B10.1.哈夫曼樹的結點個數(shù)不可能是偶數(shù)。A、正確B、錯誤答案：A11.循環(huán)鏈隊列中無溢出現(xiàn)象。A、正確B、錯誤答案：B12.遞歸定義就是循環(huán)定義。A、正確B、錯誤答案：B13.順序隊和循環(huán)隊關于隊滿和隊空的判斷條件是一樣的。A、正確B、錯誤答案：B14.線性表鏈式存儲的特點是可以用一組任意的存儲單元存儲表中的數(shù)據(jù)元素。A、正確B、錯誤答案：A15.空棧就是所有元素都為0的棧。A、正確B、錯誤答案：B16.棧和隊列都是順序存儲的線性結構。A、正確B、錯誤答案：B17.哈希表是一種將關鍵字轉換為存儲地址的存儲方法。A、正確B、錯誤答案：A18.順序存儲方式的優(yōu)點是存儲密度大，插入、刪除效率高。A、正確B、錯誤答案：B19.子串的定位運算稱為模式匹配。A、正確B、錯誤答案：A20.棧一定是順序存儲的線性結構。A、正確B、錯誤答案：B21.所謂時間復雜度,是指最壞情況下,估算算法執(zhí)行時間的一個上界。編程題如下A、正確B、錯誤答案：A22.串的堆分配存儲是一種動態(tài)存儲結構。A、正確B、錯誤答案：A23.8.為了方便插入和刪除,可以使用雙向鏈表存放數(shù)據(jù)。A、正確B、錯誤答案：A24.圖的遍歷要比樹的遍歷復雜，因為圖中一般存在回路，也就是在訪問了某個頂點后，可能會沿著某條路徑再次回到該頂點。A、正確B、錯誤答案：A25.順序表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。A、正確B、錯誤答案：B26.1.消除遞歸一定需要使用棧。A、正確B、錯誤答案：B27.“DT”是“DATA”的子串。A、正確B、錯誤答案：B28.6.隊列邏輯上是一端既能增加又能減少的線性表。A、正確B、錯誤答案：B29.鏈棧與順序棧相比，其特點之一是通常不會出現(xiàn)棧滿的情況。A、正確B、錯誤答案：A30.在鏈串中為了提高存儲密度，應該增大結點的大小。A、正確B、錯誤答案：A31.判斷順序隊列為空的標準是頭指針和尾指針都指向同一個結點。A、正確B、錯誤答案：A32.數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素本身的內容和形式無關。A、正確B、錯誤答案：A33.9.Hash表的平均查找長度與處理沖突的方法無關。A、正確B、錯誤答案：B34.數(shù)據(jù)的邏輯結構是依賴于計算機的。A、正確B、錯誤答案：B35.在隊列中允許刪除的一端稱為隊尾。A、正確B、錯誤答案：B36.數(shù)據(jù)的存儲結構是數(shù)據(jù)的邏輯結構的存儲映像。A、正確B、錯誤答案：A37.將十進制數(shù)轉換為二進制數(shù)是棧的典型應用之一。A、正確B、錯誤答案：A38.空棧就是所有元素都為0的棧。A、正確B、錯誤答案：B39.鏈表的每個結點都恰好包含一個指針域。A、正確B、錯誤答案：B40.數(shù)據(jù)的邏輯結構和數(shù)據(jù)的存儲結構是相同的。A、正確B、錯誤答案：B41.隊列是限制在兩端進行操作的線性表。A、正確B、錯誤答案：A42.棧是運算受限制的線性表。A、正確B、錯誤答案：A43.在單向循環(huán)鏈表中，若頭指針為h，那么p所指結點為尾結點的條件是p=h。A、正確B、錯誤答案：B44.4.哈夫曼編碼是前綴編碼。A、正確B、錯誤答案：A45.在鏈隊列上做出隊操作時,會改變front指針的值。A、正確B、錯誤答案：B46.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。A、正確B、錯誤答案：B47.6.在線性表的順序存儲結構中,邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。A、正確B、錯誤答案：B48.冒泡排序是不穩(wěn)定的排序。A、正確B、錯誤答案：B49.串是n個字母的有限序列。A、正確B、錯誤答案：B50.在循環(huán)鏈隊列中無溢出現(xiàn)象。A、正確B、錯誤答案：B51.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。A、正確B、錯誤答案：A52.在循環(huán)隊列中，若尾指針rear大于頭指針front，其元素個數(shù)為rear-front。A、正確B、錯誤答案：A53.刪除二叉排序樹中的一個結點，再重新插入上去，一定能得到原來的二叉排序樹。A、正確B、錯誤答案：B54.7.堆是滿二叉樹。A、正確B、錯誤答案：B55.在棧空的情況下，不能作出棧操作，否則產生下溢出。A、正確B、錯誤答案：A56.如果兩個串含有相同的字符，則說明它們相等。A、正確B、錯誤答案：B57.已知一棵樹的先序序列和后序序列，一定能構造出該樹。A、正確B、錯誤答案：B58.程序和算法原則上沒有區(qū)別，所以在討論數(shù)據(jù)結構時可以通用。A、正確B、錯誤答案：B59.在鏈隊列上做出隊操作時，會改變front指針的值。A、正確B、錯誤答案：B60.哈夫曼樹一定是滿二叉樹。A、正確B、錯誤答案：B61.在線性表的鏈式存儲結構中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。A、正確B、錯誤答案：A62.二叉樹中的葉子結點就是二叉樹中沒有左右子樹的結點。A、正確B、錯誤答案：B63.順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。A、正確B、錯誤答案：B64.線性表的鏈式存儲結構優(yōu)于順序存儲。A、正確B、錯誤答案：B65.串中任意個字符組成的子序列稱為該串的子串。A、正確B、錯誤答案：B66.程序一定是算法。A、正確B、錯誤答案：B67.串的數(shù)據(jù)元素是一個字符。A、正確B、錯誤答案：A68.3.在AOE網(wǎng)中,關鍵路徑上某個活動的時間縮短,整個工程的時間也就必定縮短。A、正確B、錯誤答案：B69.數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機內實際的存儲形式。A、正確B、錯誤答案：A70.一個數(shù)據(jù)結構是由一個邏輯結構和這個邏輯結構上的一個基本運算集構成的整體。A、正確B、錯誤答案：A71.串的長度是指串中不同字符的個數(shù)。A、正確B、錯誤答案：B72.棧的特點是“后進先出”。A、正確B、錯誤答案：A73.如果一個串中所有的字母均在另一個串中出現(xiàn)，則說明前者是后者的子串。A、正確B、錯誤答案：B74.插入和刪除操作是數(shù)據(jù)結構中最基本的兩種操作，所以這兩種操作在數(shù)組中也經常使用。A、正確B、錯誤答案：B75.數(shù)據(jù)表示是設想計算機是如何一步一步完成這個任務的。A、正確B、錯誤答案：B76.線性鏈表的刪除算法簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續(xù)的各個單元向前移動。A、正確B、錯誤答案：B77.線性表的順序存儲結構是通過數(shù)據(jù)元素的存儲地址直接反映數(shù)據(jù)元素的邏輯關系。A、正確B、錯誤答案：A78.棧的特點是“后進先出”。A、正確B、錯誤答案：A填空題1.()是被限定為只能在表的一端進行插入運算,在表的另一端進行刪除運算的線性表。答案：隊列2.請完成以下代碼填空：/**判斷帶頭結點的單鏈表是否為空*判斷頭結點是否有后繼引用()*如果頭結點沒有后繼引用()，則表示單鏈表空，返回true，否則返回false*///first為指向頭結點的引用變量public()isEmpty(){if().next==()){//判斷首結點是否為空return();}else{return();}}boolean；first；null；true；false；答案：也就是頭結點的指針域next是否為空|即頭結點的指針域next為空|||（|||3.向一個循環(huán)隊列中插入元素時,首先要判斷(),然后再向指針所指的位置寫入新的數(shù)據(jù)。答案：隊尾指針4.若一個算法中的語句頻度之和為T()=6n+3nlog2n,則算法的時間復雜度為()。O()答案：n||nlog2n5.單鏈表中需知道()才能遍歷整個鏈表。答案：頭指針6.請完成以下代碼填空：//帶頭結點的單鏈表遍歷，依次輸出單鏈表中的結點數(shù)據(jù)//first為指向頭結點的引用變量publicvoidprintList(){//引用變量p初始化，指向首結點()LinkedNode<T>p=();while(){Tdata=();//取出當前結點的數(shù)據(jù)域data的值System.out.print(data+"");//輸出數(shù)據(jù)元素的值p=();//指向后繼結點}System.out.println();}first.next；p.data；p.next；答案：|第一個數(shù)據(jù)元素所在結點||p!=null|||7.完成以下代碼填空：//求帶頭結點單鏈表中的數(shù)據(jù)元素個數(shù)并返回其值，first為指向頭結點的頭引用publicintlength(){intlength=();//計數(shù)器，用來累計結點個數(shù)LinkedNode<T>p=().next;//初始化，引用變量p指向第一個結點()while(){//從首結點向后查找，直到p為空();//若當前結點非空，則結點個數(shù)遞增1p=();//指向后繼結點}returnlength;}；first；length++；p.next；答案：|||首結點|p!=null||8.順序查找、二分查找、分塊查找都屬于（）查找。答案：靜態(tài)9.非連通圖的極大連通子圖稱為（）。答案：連通分量10.由樹轉換成二叉樹時,其根結點無()。答案：右孩子11.解：()先根次序遍歷：ABEFCGDHIJK()后根次序遍歷：EFBGCIJKHDA答案：1|212.有一組字符C={a,b,c,d}，其權值為W={7,5,2,4}：()求其構造的哈夫曼樹()求其哈夫曼樹的WPL()并且對各字符進行哈夫曼編碼。答案：1|2|313.數(shù)據(jù)的存儲結構形式包括:順序存儲、鏈式存儲、索引存儲和()。答案：散列存儲簡答題1.4.葉子權值(5,6,17,8,19)所構造的哈夫曼樹帶權路徑長度為_______________。答案：1212.已知一棵二叉樹的先序遍歷序列為：ABDGHCEFI，中序遍歷序列為：GDHBAECIF，試恢復該二叉樹，并寫出它的后序遍歷的序列。答案：GHDBEIFCA3.1.已知二叉樹有50個葉子結點,則該二叉樹的總結點數(shù)至少是_______________。答案：994.在最壞情況下，在第i趟直接插入排序中，要進行次關鍵字的比較。答案：i-15.5.從長度為n的采用順序存儲結構的線性表中刪除第i個元素(1≤i≤n),需向前移動________個元素。答案：n-i；6.算法的時間復雜度與空間復雜度相比,通常以作為主要度量指標。答案：時間復雜度7.給出下面二叉樹的前序遍歷、中序遍歷、后序遍歷的結果。答案：先序