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

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