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

數(shù)據(jù)結(jié)構(gòu)試題及答案一、單項選擇題(1) 一個算法應(yīng)該是（ ） 。A) 程序 B) 問題求解步驟的描述 C) 要滿足五個基本屬性 D) A 和 C(2) 算法指的是（ ） 。A) 計算機程序 B) 解決問題的計算方法C) 排序算法 D) 解決問題的有限運算序列。(3) 與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（ ） 。A) 存儲結(jié)構(gòu) B) 邏輯結(jié)構(gòu) C) 算法 D)操作(4) 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類。A) 動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B) 順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C) 線性結(jié)構(gòu)、非線性結(jié)構(gòu) D) 初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu) (5) 下列敘述中正確的是( )。 A）一個邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲結(jié)構(gòu)B）數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲結(jié)構(gòu)屬于非線性結(jié)構(gòu) C）一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理的效率 D）一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率(6) 數(shù)據(jù)的基本單位是（ ）A) 數(shù)據(jù)項 B) 數(shù)據(jù)類型 C) 數(shù)據(jù)元素 D) 數(shù)據(jù)變量(7) 下列程序的時間復(fù)雜度為（ ）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 為正整數(shù)，則最后一行的語句頻度在最壞情況下是（ ） 。A) O(n） B) O(nlogn) C) O(n3) D) O(n2) (12) 設(shè)有一個遞歸算法如下：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）時，需向前移動的元素的個數(shù)是（ ） 。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） ，當(dāng)二分檢索值為90 的元素時，檢索成功需比較的次數(shù)是（ ） 。A)1 B)2 C)3 D)4(19) 假設(shè)以行優(yōu)先順序存儲三維數(shù)組 R696，其中元素 R000的地址為 2100，且每個元素占 4 個存儲單元，則存儲地址為 2836 的元素是（ ） 。A) R333 B) R334 C) R435 D) R434(20) 設(shè)有一個 10 階的對稱矩陣 A，采用壓縮存儲方式以行序為主序存儲， a00 為第一個元素，其存儲地址為 0，每個元素占有 1 個存儲地址空間，則 a45 的地址為（ ） 。A) 13 B) 35 C) 17 D) 36(21) 線性表采用鏈?zhǔn)酱鎯r，節(jié)點的存儲的地址（ ） 。A) 必須是不連續(xù)的 B) 連續(xù)與否均可C) 必須是連續(xù)的 D) 和頭節(jié)點的存儲地址相連續(xù)(22) 用鏈表表示線性表的優(yōu)點是（ ） 。A) 便于隨機存取 B) 花費的存儲空間比順序表少 C) 數(shù)據(jù)元素的物理順序與邏輯順序相同 D) 便于插入與刪除(23) 鏈表不具有的特點是（ ） 。A) 插入、刪除不需要移動元素 B) 可隨機訪問任一元素 C) 不必事先估計存儲空間 D) 所需空間與線性長度成正比(24) 在長度為 n 的順序表中刪除第 i 個元素(1in)時，元素移動的次數(shù)為( )。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 的單鏈表之后的算法的時間復(fù)雜度為（ ） 。A) O(1) B) O(n) C) O(m) D) O(m+n)(27) 若不帶頭結(jié)點的單鏈表的頭指針為 head，則該鏈表為空的判定條件是( )。A) head=NULL B) head-next=NULL C) head!=NULL D) head-next=head(28) 某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ ）存儲方式最節(jié)省運算時間。A) 單鏈表 B) 僅有頭指針的單循環(huán)鏈表C) 雙鏈表 D) 僅有尾指針的單循環(huán)鏈表(29) 若允許表達(dá)式內(nèi)多種括號混合嵌套，則為檢查表達(dá)式中括號是否正確配對的算法，通常選用的輔助結(jié)構(gòu)是（ ） 。A) 棧 B) 線性表 C) 隊列 D) 二叉排序樹(30) 順序棧 S 中 top 為棧頂指針，指向棧頂元素所在的位置，elem 為存放棧的數(shù)組，則元素 e進(jìn)棧操作的主要語句為（ ） 。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) 循環(huán)隊列 sq 中，用數(shù)組 elem025存放數(shù)據(jù)元素，sq.front 指示隊頭元素的前一個位置，sq.rear 指示隊尾元素的當(dāng)前位置，設(shè)當(dāng)前 sq.front 為 20，sq.rear 為 12，則當(dāng)前隊列中的元素個數(shù)為（ ） 。A) 8 B) 16 C) 17 D) 18(32) 鏈?zhǔn)綏Ｅc順序棧相比，一個比較明顯的優(yōu)點是（ ） 。A) 插入操作更加方便 B) 通常不會出現(xiàn)棧滿的情況C) 不會出現(xiàn)?？盏那闆r 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) 若進(jìn)棧序列為 1，2，3 ，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則不可能出現(xiàn)的出棧序列是( )。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) 對于棧操作數(shù)據(jù)的原則是（ ） 。A) 先進(jìn)先出 B) 后進(jìn)先出 C) 后進(jìn)后出 D) 不分順序(38) 棧和隊列的共同點是（ ） 。A) 都是先進(jìn)先出 B) 都是先進(jìn)后出 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) 設(shè)數(shù)組 datam作為循環(huán)隊列 SQ 的存儲空間，front 為隊頭指針，rear 為隊尾指針，則執(zhí)行出對操作后其頭指針 front 值為（ ） 。A) front=front+1 B) front=(front+1)%(m-1) C) front=(front-1)%m D) front=(front+1)%m(41) 引起循環(huán)隊列隊頭位置發(fā)生變化的操作是( )。A) 出隊 B) 入隊 C) 取隊頭元素 D) 取隊尾元素(2) 設(shè)以數(shù)組 Am存放循環(huán)隊列的元素，其頭尾指針分別為 front 和 rear，則當(dāng)前隊列中的元素個數(shù)為（ ）。A）(rear-front+m)%m B）rear-front+1 C）(front-rear+m)%m D）(rear-front)%m(42) 二維數(shù)組 A1218采用列優(yōu)先的存儲方法，若每個元素各占 3 個存儲單元，且 A00地址為 150，則元素 A97的地址為( )。A) 429 B) 432 C) 435 D) 438(43) 設(shè)有一個 10 階的對稱矩陣 A1010，采用壓縮方式按行將矩陣中下三角部分的元素存入一維數(shù)組 B中，A00存入 B0中，則 A85在 B中（ ）位置。A) 32 B) 33 C) 41 D) 65(44) 若對 n 階對稱矩陣 A 以行序為主序方式將其下三角形的元素 (包括主對角線上所有元素)依次存放于一維數(shù)組 B1.(n(n+1)/2中，則在 B 中確定 aij（i, ,G 的拓?fù)湫蛄惺牵?） 。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) 關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（ ） 。A) 從源點到匯點的最長路徑 B) 從源點到匯點的最短路徑C) 最長回路 D) 最短回路(82) 有 n 個結(jié)點的有向完全圖的弧數(shù)是（ ） 。A) n2 B) 2n C) n(n-1) D) 2n(n+1)(83) 設(shè)圖的鄰接鏈表如題 12 圖所示，則該圖的邊的數(shù)目是（ ） 。A) 4 B) 5 C) 10 D) 20(84) 在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的（ ）倍。83 題圖A) 1/2 B) 1 C) 2 D) 4 (85) 在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（ ）倍。A) 1/2 B) 1 C) 2 D) 4 (86) 有 8 個結(jié)點的無向圖最多有（ ）條邊。A) 14 B) 28 C) 56 D) 112 (87) 有 8 個結(jié)點的無向連通圖最少有（ ）條邊。A) 5 B) 6 C) 7 D) 8 (88) 有 8 個結(jié)點的有向完全圖有（ ）條邊。A) 14 B) 28 C) 56 D) 112 (89) 用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時，通常是采用（ ）來實現(xiàn)算法的。A) 棧 B) 隊列 C) 樹 D) 圖 (90) 用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時，通常是采用（ ）來實現(xiàn)算法的。A) 棧 B) 隊列 C) 樹 D) 圖 (91) 已知圖的鄰接矩陣，根據(jù)算法思想，則從頂點 0 出發(fā)按深度優(yōu)先遍歷的結(jié)點序列是（ ） 。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，根據(jù)算法，則從頂點 0 出發(fā)，按深度優(yōu)先遍歷的結(jié)點序列是（ ） 。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，根據(jù)算法，則從頂點 0 出發(fā)，按廣度優(yōu)先遍歷的結(jié)點序列是（ ） 。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，根據(jù)算法，則從頂點 0 出發(fā)，按廣度優(yōu)先遍歷的結(jié)點序列是（ ） 。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) 已知圖的鄰接表如下所示，根據(jù)算法，則從頂點 0 出發(fā)按深度優(yōu)先遍歷的結(jié)點序列是（ ） 。A) 1 3 2 B) 0 2 3 1 C) 0 3 2 1 D) 0 1 2 3(96) 已知圖的鄰接表如下所示，根據(jù)算法，則從頂點 0 出發(fā)按廣度優(yōu)先遍歷的結(jié)點序列是（ ） 。A) 0 3 2 1 B) 0 1 2 3 C) 0 1 3 2 D) 0 3 1 2(97) 深度優(yōu)先遍歷類似于二叉樹的（ ） 。A) 先序遍歷 B) 中序遍歷 C) 后序遍歷 D) 層次遍歷(98) 廣度優(yōu)先遍歷類似于二叉樹的（ ） 。A) 先序遍歷 B) 中序遍歷 C) 后序遍歷 D) 層次遍歷(99) 任何一個無向連通圖的最小生成樹（ ） 。A) 只有一棵 B) 一棵或多棵 C) 一定有多棵 D) 可能不存在（注，生成樹不唯一，但最小生成樹唯一，即邊權(quán)之和或樹權(quán)最小的情