數據結構試題及答案一、單項選擇題(1) 一個算法應該是（ ） 。A) 程序 B) 問題求解步驟的描述 C) 要滿足五個基本屬性 D) A 和 C(2) 算法指的是（ ） 。A) 計算機程序 B) 解決問題的計算方法C) 排序算法 D) 解決問題的有限運算序列。(3) 與數據元素本身的形式、內容、相對位置、個數無關的是數據的（ ） 。A) 存儲結構 B) 邏輯結構 C) 算法 D)操作(4) 從邏輯上可以把數據結構分為（ ）兩大類。A) 動態結構、靜態結構 B) 順序結構、鏈式結構 C) 線性結構、非線性結構 D) 初等結構、構造型結構 (5) 下列敘述中正確的是( )。 A）一個邏輯數據結構只能有一種存儲結構B）數據的邏輯結構屬于線性結構，存儲結構屬于非線性結構 C）一個邏輯數據結構可以有多種存儲結構，且各種存儲結構不影響數據處理的效率 D）一個邏輯數據結構可以有多種存儲結構，且各種存儲結構影響數據處理的效率(6) 數據的基本單位是（ ）A) 數據項 B) 數據類型 C) 數據元素 D) 數據變量(7) 下列程序的時間復雜度為（ ）i=0；s=0；while（s=n ; i+)for ( j=1; j=n ; j+)x:=x+1;A) O(2n) B)O(n) C) O(n2) D) O(log2n) (11) 程序段 for ( i:=n-1; i=i ; j+)if (ajaj+1 ) t=aj; aj= aj+1; aj+1= t; 其中 n 為正整數，則最后一行的語句頻度在最壞情況下是（ ） 。A) O(n） B) O(nlogn) C) O(n3) D) O(n2) (12) 設有一個遞歸算法如下：int fact(int n) /* 大于等于 0 */if ( nnext= =head B) rear-next-next= =headC) head-next= =rear D) head-next-next= =rear(17) 從一個長度為 n 的順序表中刪除第 i 個元素（1i n）時，需向前移動的元素的個數是（ ） 。A)n-i B)n-i+1 C)n-i-1 D)i(18) 已知一個有序表為（13 ，18，24，35，47，50，62，83，90，115，134） ，當二分檢索值為90 的元素時，檢索成功需比較的次數是（ ） 。A)1 B)2 C)3 D)4(19) 假設以行優先順序存儲三維數組 R696，其中元素 R000的地址為 2100，且每個元素占 4 個存儲單元，則存儲地址為 2836 的元素是（ ） 。A) R333 B) R334 C) R435 D) R434(20) 設有一個 10 階的對稱矩陣 A，采用壓縮存儲方式以行序為主序存儲， a00 為第一個元素，其存儲地址為 0，每個元素占有 1 個存儲地址空間，則 a45 的地址為（ ） 。A) 13 B) 35 C) 17 D) 36(21) 線性表采用鏈式存儲時，節點的存儲的地址（ ） 。A) 必須是不連續的 B) 連續與否均可C) 必須是連續的 D) 和頭節點的存儲地址相連續(22) 用鏈表表示線性表的優點是（ ） 。A) 便于隨機存取 B) 花費的存儲空間比順序表少 C) 數據元素的物理順序與邏輯順序相同 D) 便于插入與刪除(23) 鏈表不具有的特點是（ ） 。A) 插入、刪除不需要移動元素 B) 可隨機訪問任一元素 C) 不必事先估計存儲空間 D) 所需空間與線性長度成正比(24) 在長度為 n 的順序表中刪除第 i 個元素(1in)時，元素移動的次數為( )。A) n-i+1 B) i C) i+1 D) n-i(25) 采用順序搜索方法查找長度為 n 的順序表示，搜索成功的平均搜索長度為（ ） 。A) n B) n/2 C) (n-1)/2 D) (n+1)/2(26) 將長度為 n 的單鏈表鏈接在長度為 m 的單鏈表之后的算法的時間復雜度為（ ） 。A) O(1) B) O(n) C) O(m) D) O(m+n)(27) 若不帶頭結點的單鏈表的頭指針為 head，則該鏈表為空的判定條件是( )。A) head=NULL B) head-next=NULL C) head!=NULL D) head-next=head(28) 某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ ）存儲方式最節省運算時間。A) 單鏈表 B) 僅有頭指針的單循環鏈表C) 雙鏈表 D) 僅有尾指針的單循環鏈表(29) 若允許表達式內多種括號混合嵌套，則為檢查表達式中括號是否正確配對的算法，通常選用的輔助結構是（ ） 。A) 棧 B) 線性表 C) 隊列 D) 二叉排序樹(30) 順序棧 S 中 top 為棧頂指針，指向棧頂元素所在的位置，elem 為存放棧的數組，則元素 e進棧操作的主要語句為（ ） 。A) s.elemtop=e； s.top=s.top+1； B) s.elemtop+1=e；s.top=s.top+1； C) s.top=s.top+1； s.elemtop+1=e； D) s.top=s.top+1；s.elem top=e； (31) 循環隊列 sq 中，用數組 elem025存放數據元素，sq.front 指示隊頭元素的前一個位置，sq.rear 指示隊尾元素的當前位置，設當前 sq.front 為 20，sq.rear 為 12，則當前隊列中的元素個數為（ ） 。A) 8 B) 16 C) 17 D) 18(32) 鏈式棧與順序棧相比，一個比較明顯的優點是（ ） 。A) 插入操作更加方便 B) 通常不會出現棧滿的情況C) 不會出現棧空的情況 D) 刪除操作更加方便(33) 一個遞歸的定義可以用遞歸過程求解，也可以用非遞歸過程求解，但單從運行時間來看，通常遞歸過程比非遞歸過程（ ） 。A) 較快 B) 較慢 C) 相同 D) 不定(34) 若已知一個棧的入棧序列是 1,2,3,4n，其輸出序列為 p1,p2,p3,pn，若 p1= =n,則 pi為（ ） 。A) i B) n= =i C) n-i+1 D) 不確定(35) 一個棧的入棧序列是 a,b,c,d,e，則棧的不可能的輸出序列是( ) 。A) edcba B) decba C) dceab D) abcde(36) 若進棧序列為 1，2，3 ，4，5，6，且進棧和出棧可以穿插進行，則不可能出現的出棧序列是( )。A) 2，4 ，3，1 ，5，6 B) 3，2，4，1，6，5C) 4，3，2，1，5，6 D) 2，3，5 ，1，6，4(37) 對于棧操作數據的原則是（ ） 。A) 先進先出 B) 后進先出 C) 后進后出 D) 不分順序(38) 棧和隊列的共同點是（ ） 。A) 都是先進先出 B) 都是先進后出 C) 只允許在端點處插入和刪除元素 D) 沒有共同點(39) 一個隊列的入隊序列是 1，2，3，4，則隊列的輸出序列是（ ） 。A) 4,3,2,1 B) 1,2,3,4 C)1,4,3,2 D) 3,2,4,1(40) 設數組 datam作為循環隊列 SQ 的存儲空間，front 為隊頭指針，rear 為隊尾指針，則執行出對操作后其頭指針 front 值為（ ） 。A) front=front+1 B) front=(front+1)%(m-1) C) front=(front-1)%m D) front=(front+1)%m(41) 引起循環隊列隊頭位置發生變化的操作是( )。A) 出隊 B) 入隊 C) 取隊頭元素 D) 取隊尾元素(2) 設以數組 Am存放循環隊列的元素，其頭尾指針分別為 front 和 rear，則當前隊列中的元素個數為（ ）。A）(rear-front+m)%m B）rear-front+1 C）(front-rear+m)%m D）(rear-front)%m(42) 二維數組 A1218采用列優先的存儲方法，若每個元素各占 3 個存儲單元，且 A00地址為 150，則元素 A97的地址為( )。A) 429 B) 432 C) 435 D) 438(43) 設有一個 10 階的對稱矩陣 A1010，采用壓縮方式按行將矩陣中下三角部分的元素存入一維數組 B中，A00存入 B0中，則 A85在 B中（ ）位置。A) 32 B) 33 C) 41 D) 65(44) 若對 n 階對稱矩陣 A 以行序為主序方式將其下三角形的元素 (包括主對角線上所有元素)依次存放于一維數組 B1.(n(n+1)/2中，則在 B 中確定 aij（i, ,G 的拓撲序列是（ ） 。A) V1,V3,V4,V6,V2,V5,V7 B) V1,V3,V2,V6,V4,V5,V7C) V1,V3,V4,V5,V2,V6,V7 D) V1,V2,V5,V3,V4,V6,V7(81) 關鍵路徑是事件結點網絡中（ ） 。A) 從源點到匯點的最長路徑 B) 從源點到匯點的最短路徑C) 最長回路 D) 最短回路(82) 有 n 個結點的有向完全圖的弧數是（ ） 。A) n2 B) 2n C) n(n-1) D) 2n(n+1)(83) 設圖的鄰接鏈表如題 12 圖所示，則該圖的邊的數目是（ ） 。A) 4 B) 5 C) 10 D) 20(84) 在一個圖中，所有頂點的度數之和等于圖的邊數的（ ）倍。83 題圖A) 1/2 B) 1 C) 2 D) 4 (85) 在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（ ）倍。A) 1/2 B) 1 C) 2 D) 4 (86) 有 8 個結點的無向圖最多有（ ）條邊。A) 14 B) 28 C) 56 D) 112 (87) 有 8 個結點的無向連通圖最少有（ ）條邊。A) 5 B) 6 C) 7 D) 8 (88) 有 8 個結點的有向完全圖有（ ）條邊。A) 14 B) 28 C) 56 D) 112 (89) 用鄰接表表示圖進行廣度優先遍歷時，通常是采用（ ）來實現算法的。A) 棧 B) 隊列 C) 樹 D) 圖 (90) 用鄰接表表示圖進行深度優先遍歷時，通常是采用（ ）來實現算法的。A) 棧 B) 隊列 C) 樹 D) 圖 (91) 已知圖的鄰接矩陣，根據算法思想，則從頂點 0 出發按深度優先遍歷的結點序列是（ ） 。A) 0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C) 0 4 2 3 1 6 5 D) 0 3 6 1 5 4 2建議：0 1 3 4 2 5 6(92) 已知圖的鄰接矩陣同上題 8，根據算法，則從頂點 0 出發，按深度優先遍歷的結點序列是（ ） 。A) 0 2 4 3 1 5 6 B) 0 1 3 5 6 4 2 C) 0 4 2 3 1 6 5 D) 0 1 3 4 2 5 6(93) 已知圖的鄰接矩陣同上題 8，根據算法，則從頂點 0 出發，按廣度優先遍歷的結點序列是（ ） 。A) 0 2 4 3 6 5 1 B) 0 1 3 6 4 2 5 C) 0 4 2 3 1 5 6 D) 0 1 3 4 2 5 6（建議：0 1 2 3 4 5 6）(94) 已知圖的鄰接矩陣同上題 8，根據算法，則從頂點 0 出發，按廣度優先遍歷的結點序列是（ ） 。0110011A) 0 2 4 3 1 6 5 B) 0 1 3 5 6 4 2 C) 0 1 2 3 4 6 5 D) 0 1 2 3 4 5 6(95) 已知圖的鄰接表如下所示，根據算法，則從頂點 0 出發按深度優先遍歷的結點序列是（ ） 。A) 1 3 2 B) 0 2 3 1 C) 0 3 2 1 D) 0 1 2 3(96) 已知圖的鄰接表如下所示，根據算法，則從頂點 0 出發按廣度優先遍歷的結點序列是（ ） 。A) 0 3 2 1 B) 0 1 2 3 C) 0 1 3 2 D) 0 3 1 2(97) 深度優先遍歷類似于二叉樹的（ ） 。A) 先序遍歷 B) 中序遍歷 C) 后序遍歷 D) 層次遍歷(98) 廣度優先遍歷類似于二叉樹的（ ） 。A) 先序遍歷 B) 中序遍歷 C) 后序遍歷 D) 層次遍歷(99) 任何一個無向連通圖的最小生成樹（ ） 。A) 只有一棵 B) 一棵或多棵 C) 一定有多棵 D) 可能不存在（注，生成樹不唯一，但最小生成樹唯一，即邊權之和或樹權最小的情