數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題：選擇題、判斷題

1、第一章緒論1.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（A.動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)C）兩大類。B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2.在下面的程序段中，對 x 的賦值語句的頻度為（C）。For（k=1；k=n；k+）For（j=1；jnext=s；s-next=p-next;B. s-next=p-next;p-next=s；C. p-next=s；p-next=s-next;D. p-next=s-next;p-next=s；9 .在雙向鏈表存儲結(jié)構(gòu)中，刪除 p 所指的結(jié)點(diǎn)時須修改指針(A)prior)-next=p-next;(p-next)-prior=p-prior;B

2、. p-prior=(p-prior)-prior;(p-prior)-next=p;C. (p-next)-prior=p;p-rlink=(p-next)-next;D. p-next=(p-prior)-prior;p-prior=(p-next)-next10 .完成在雙向循環(huán)鏈表結(jié)點(diǎn) p 之后插入 s 的操作是(D)。A.p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;B. p-next-prior=s;p-next=s;s-prior=p;s-next=p-next;C. s-prior=p;s-next=p-next;p-next=

3、s;p-next-prior=s;D. s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;11 .若某線性表中最常用的操作是取第 i 個元素和找第 i 個元素的前趨元素，則采用(B)存儲方式最節(jié)省運(yùn)算時間。A.單鏈表 B.順序表 C.雙向鏈表 D.單循環(huán)鏈表12 .若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（D）存儲方式最節(jié)省運(yùn)算時間。A.單鏈表 B,僅有頭指針的單循環(huán)鏈表C.雙向鏈表 D.僅有尾指針的單循環(huán)鏈表第三章棧和隊(duì)列1.向一個棧頂指針為 top 的鏈棧中插入一個 p 所指結(jié)點(diǎn)時，其操作步驟為（C）。B

4、. p-next=top-next;top-next=p；D.p-next=top；top=top-next;2 .對于棧操作數(shù)據(jù)的原則是（A.top-next=p；C.p-next=top；top=p；A.先進(jìn)先出 B.后進(jìn)先出C.后進(jìn)后出 D.不分順序3 .若已知一個棧的入棧序列是 1,2,3,，n,其輸出序列為 pi,p2,p3,，pn,若 pn是 n,則 Pi為（D）。A.iB.n-iC.n-i+lD,不確定4 .表達(dá)式 a*（b-c）+d 的后綴表達(dá)式是（B）。A.abcd*+B.abc*d+C. abc*d+D.+*abcd5.采用順序存儲的兩個棧的共享空間 S1.m,用 topi

5、代表第 i 個棧（i=1,2）的棧頂,棧 1 的底在 S1,棧 2 的底在 Sm,則棧滿的條件是（B）。A.top2top1=0B.top1+1=top2C.top1+top2=mD.top1=top26 .一個棧的入棧序列是 a,b,c,d,e,則棧的不可能的輸出序列是（C）。A.edcbaB.decbaC.dceabD.abcde7 .在一個鏈隊(duì)列中，若 f、r 分別為隊(duì)首、隊(duì)尾指針，則插入 p 所指結(jié)點(diǎn)的操作為（B）A.f-next=p；f=pB.r-next=p；r=pC.p-next=r；r=pD.p-next=f;f=p8 .用不帶頭結(jié)點(diǎn)的單鏈表存儲隊(duì)列時，在進(jìn)行刪除運(yùn)算時（D）o

6、A.僅修改頭指針 B,僅修改尾指針C.頭、尾指針都要修改 D.頭、尾指針可能都要修改9 .遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（C）的數(shù)據(jù)結(jié)構(gòu)。第四章字符串及線性結(jié)構(gòu)的擴(kuò)展1 .下面關(guān)于用的敘述，錯誤的是（C）。A.用是字符的有限序列B.用既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯.空用是由空格構(gòu)成的用D.模式匹配是用的一種重要運(yùn)算2 .用的長度是指（B）。A.用中所含不同字母的個數(shù) B,用中所含字符的個數(shù)C.用中所含不同字符的個數(shù) D.用中所含非空格字符的個數(shù) 3.4 .二維數(shù)組 M 的成員是 6 個字符(每個字符占一個存儲單元，即一個字節(jié))組成的申，行下標(biāo)A.隊(duì)列 B.靜態(tài)

7、鏈表C.棧 D.順序表10.棧和隊(duì)都是（C）。A.順序存儲的線性結(jié)構(gòu)C.限制存取點(diǎn)的線性結(jié)構(gòu)B.鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu)D.限制存取點(diǎn)的非線性結(jié)構(gòu)i 的范圍從 0 到 8,列下標(biāo) j 的范圍從 1 至 IJ10,則存放 M 至少需要(1)(D)個字節(jié)；M 的第 8 列和第 5 行共占 02(A)個字節(jié)；若 M 按行優(yōu)先方式存儲，元素 M85的起始地址與當(dāng) M 按列證方式存儲時的 3.(C)元素的起始地址一致。(1) A.90B.180C.240D.540(2) A.108B.114C.54D.60(3) A.M85B.M310C.M58D.M095 .數(shù)組 A 中，每個元素的存儲占 3 個單元，行

8、下標(biāo) i 從 1 到 8,列下標(biāo) j 從 1 到 10,從首地址SA 開始連續(xù)存放在存儲器內(nèi)， 存放該數(shù)組至少需要的單元個數(shù)是 4(C);若該數(shù)組按行存放， 元素 A85的起始地址為21(D);若該數(shù)組按列存放，元素 A85的起始地址為(B)。(1) A.80B.100C.240D.270(2) A.SA+141B.SA+144C.SA+222D.SA+225(3) A.SA+141B.SA+180C.SA+117D.SA+2256 .稀疏矩陣采用壓縮存儲，一般有(C)兩種方法。A,二維數(shù)組和三維數(shù)組 B,三元組和散列C.三元組表和十字鏈表 D.散列和十字鏈表第五章樹結(jié)構(gòu)1 .下列說法正確的是

9、(C)。A.二叉樹中任何一個結(jié)點(diǎn)的度都為 2B.二叉樹的度為 2C.一棵二叉樹的度可小于 2D,任何一棵二叉樹中至少有一個結(jié)點(diǎn)的度為 22 .以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，在具有 n 個結(jié)點(diǎn)的二叉鏈表中(n0),空鏈域的個數(shù)為(C)。A.2n1B.n-1C.n+lD,2n+l3 .線索化二叉樹中，某結(jié)點(diǎn)*p 沒有孩子的充要條件是(B)0A.p-lchild=NULLB.p-ltag=1 且 p-rtag=1C.p-ltag=0D.p-lchild=NULL 且 p-ltag=14 .如果結(jié)點(diǎn) A 有 3 個兄弟，而且 B 是 A 的雙親，則 B 的度是(B)。A.3B.4C.5D.15 .某

10、二叉樹 T 有 n 個結(jié)點(diǎn)，設(shè)按某種順序?qū)?T 中的每個結(jié)點(diǎn)進(jìn)行編號，編號值為 1,2,n,且有如下性質(zhì)：T 中任意結(jié)點(diǎn) v,其編號等于左子樹上的最小編號減 1,而 v 的右子樹的結(jié)點(diǎn)中，其最小編號等于 v 左子樹上結(jié)點(diǎn)的最大編號加 1,這是按(B)編號 IA.中序遍歷序列 B.先序遍歷序列 C.后序遍歷序列 D.層次順序6 .設(shè) F 是一個森林，B 是由 F 轉(zhuǎn)換得到的二叉樹，F(xiàn) 中有 n 個非終端結(jié)點(diǎn)，B 中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有(C)個。7 .一棵完全二叉樹上有 1001 個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個數(shù)是（C）。A.500B.501C.490D.4958 .設(shè)森林 F 中有 3 棵樹，第 1、

11、第 2 和第 3 棵樹的結(jié)點(diǎn)個數(shù)分別為 N1,N2和 N3。與森林 F 對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個數(shù)是（D）。A.N1B,N1+N2C.N2D,N2+N39 .任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序（A）。A.不發(fā)生改變 B.發(fā)生改變 C.不能確定 D.以上都不對10 .若一棵二叉樹的后序遍歷序列為 dabec,中序遍歷序列為 debac,則先序遍歷序列為（D）。A.cbedB.decabC.deabcD.cedba11 .若一棵二叉樹的先序遍歷序列為 abdgcefh,中序遍歷的序列為 dgbaechf,則后序遍歷的結(jié)果為（D）。A.gcefhaB.gdbec

12、fhaC.bdgaechfD.gdbehfca12 .一棵非空二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（B）。A.所有的結(jié)點(diǎn)均無左孩子 B.所有的結(jié)點(diǎn)均無右孩子C.只有一個葉子結(jié)點(diǎn) D.是一棵滿二叉樹13 .設(shè)高度為 h 的二叉樹上只有度為 0 和度為 2 的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（B）。A.2hB.2h-1C.2h+1D.h+114 .一個具有 567 個結(jié)點(diǎn)的二叉樹的高八為（D）。A.9B.10C.9566 之間 D.10567 之間第六章圖結(jié)構(gòu)1 .n 條邊的無向圖的鄰接表的存儲中，邊結(jié)點(diǎn)的個數(shù)有（A）。A.nB.2nC.n/2D.nn2 .n 條

13、邊的無向圖的鄰接多重表的存儲中，邊結(jié)點(diǎn)的個數(shù)有（A）。A.nB.2nC.n/2D.nn3 .下列哪一種圖的鄰接矩陣是對稱矩陣？（B）A.有向圖 B.無向圖 C.AOV 網(wǎng) D.AOE 網(wǎng)4 .最短路徑的生成算法可用（C）。A.普利姆算法 B.克魯斯卡爾算法 C.迪杰斯特拉算法 D.哈夫曼算法B.nC.n+lD.n+2A.nB.iC.n+iD.n-iA.V0,V3,V2,ViB.V0,Vi,V2,V3C.V0,V2,Vi,V3D.V0,Vi,V3,V2(2)從頂點(diǎn) V0 出發(fā)進(jìn)行廣度優(yōu)先搜索，經(jīng)歷的結(jié)點(diǎn)順序?yàn)?D)06 .設(shè)有向圖 n 個頂點(diǎn)和 e 條邊，進(jìn)行拓?fù)渑判驎r，總的計(jì)算時間為(D)A.

14、O(nlog2e)B.O(e 苗 C.O(elog2n)D.O(n+e)7 .含有 n 個頂點(diǎn) e 條邊的無向連通圖，利用 Kruskal 算法生成最小生成樹，其時間復(fù)雜度為(A)oA.O(elog2e)B.O(e 為 C.O(elog2n)D.O(nlog2n)9 .下面關(guān)于求關(guān)鍵路徑的說法，不正確的是(C)。A.求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的B. 一個事件的最早開始時間同以該事件為尾的弧的活動最早開始時間相同C. 一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差D.關(guān)鍵活動一定位于關(guān)鍵路徑上10 .有 i0 個結(jié)點(diǎn)的無向圖至少有(B)條邊才能確保其是連通圖A

15、.8B.9C.i0D.ii第七章查找1 .靜態(tài)查找表與動態(tài)查找表的根本區(qū)別在于(B)。A.它們的邏輯結(jié)構(gòu)不一樣 B.施加在其上的操作不一樣C.所包含的數(shù)據(jù)元素類型不一樣 D.存儲實(shí)現(xiàn)不一樣2.在表長為 n 的順序表上實(shí)施順序查找，在查找不成功時與關(guān)鍵字比較的次數(shù)為(A)。A. V0,V3,V2,viC.V0,V2,vi,V3B. V0,Vi,V2,V3D.V0,Vi,V3,V28.關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中(A.從源點(diǎn)到匯點(diǎn)的最長路徑C.最長的回路A)。B.從源點(diǎn)到匯點(diǎn)的最短路徑D.最短的回路5.一個無向圖的鄰接表如下圖所示3 .順序查找適用于存儲結(jié)構(gòu)為(C)的線性表。A,散列存儲 B.壓縮存儲

16、C.順序存儲或鏈?zhǔn)酱鎯?D.索引存儲4 .用順序查找法對具有 n 個結(jié)點(diǎn)的線性表查找一個結(jié)點(diǎn)的時間復(fù)雜度為(C)。.-2一一，.、一一，、一一八、A.O(log2n)B.O(nlog2n)C.O(n)D.O(log2n)5 .適用于折半查找的表的存儲方式及元素排列要求為(D)。A.鏈接方式存儲，元素?zé)o序B.鏈接方式存儲，元素有序C.順序方式存儲，元素?zé)o序D.順序方式存儲，元素有序6.有一個長度為 12 的有序表，按折半查找法對該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為(B)。A.35/12B.37/12C.39/12D.43/128 .設(shè)散列表長為 14,散列函數(shù)為 H

17、(key)=key%11。當(dāng)前表中已有 4 個結(jié)點(diǎn)：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7。如用二次探測再散列處理沖突,則關(guān)鍵字為 49 的結(jié)點(diǎn)的地址是(D)。A.8B.3C.5D.99 .散列函數(shù)有一個共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以(D)取其值域的每個值A(chǔ).最大概率 B.最小概率 C.平均概率 D.同等概率10 .假定有 k 個關(guān)鍵字互為同義詞，若用線性探測法把這 k 個關(guān)鍵字存入散列表中，至少要進(jìn)行(D)次探測。A.k1 次 B.k 次 C.k+1 次 D.k(k+1)/2 次11 .在散列函數(shù) H(k)=k%m 中，一般來講，m 應(yīng)取(C)A.

18、奇數(shù) B.偶數(shù) C.素?cái)?shù) D.充分大的數(shù)12 .在采用線性探測法處理沖突所構(gòu)成的散列表上進(jìn)行查找，可能要探測多個位置，在查找成功的情況下，所探測到的這些位置上的鍵值(B)。A.一定是同義詞 B.一定不是同義詞C.都相同 D.不一定都是同義詞7.在有序表1,3,9,12,32,41,62,為 82 的數(shù)據(jù)元素需要比較（C）次。A.1B.2C.4D.575,77,82,95,100上進(jìn)行折半查找關(guān)鍵字第八章排序1 .在待排序的元素序列基本有序的前提下，效率最高的排序方法是（A）0A.插入排序 B.選擇排序 C.快速排序 D.歸并排序2 .設(shè)有 1000 個無序的元素， 希望用最快的速度挑選出其中前

19、 10 個最大的元素， 最好選用 （C）排序法。A.冒泡排序 B.快速排序 C.堆排序 D.基數(shù)排序3 .具有 12 個記錄的序列，采用冒泡排序最少的比較次數(shù)是（C）。A.1B.144C.11D.664 .下列四種排序方法中，要求內(nèi)存容量最大的是（D）。A.插入排序 B.選擇排序 C.快速排序 D.歸并排序5 .初始序列已經(jīng)按鍵值有序時，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為（D）A.n1234B.nlog2nC.log2nD.n16 .下列四種排序方法， 在排序過程中， 關(guān)鍵碼比較的次數(shù)與記錄的初始排列順序無關(guān)的是 （C） 。A.直接插入排序和快速排序 B.快速排序和歸并排序C.直接選擇排

20、序和歸并排序 D.直接插入排序和歸并排序125,84,21,47,220,15,21,25,315,20,21,25,415,20,21,25,7. 一組記錄的排序碼為(46,79,56,38,堆為(B)。A.79,46,56,38,40,84B.84,C.847956464038D.848. 一組記錄的排序碼為(46,79,56,38,個記錄為基準(zhǔn)得到的一次劃分結(jié)果為(CA.384046567984B.40C.403846567984D.4040,84）,則利用堆排序的方法建立的初始7956384046567940463840,84）,則利用快速排序的方法，以第一）。384679568438

21、468456799 .用某種排序方法對線性表（25,84,21,47,15,27,68,35,20）進(jìn)行排序時,元素序列的變化情況如下：1527683520472768358435274768842735476884則所采用的排序方法是（D）10 .快速排序方法在（C）情況下最不利于發(fā)揮其長處。A.要排序的數(shù)據(jù)量太大 B.要排序的數(shù)據(jù)中含有多個相同值C.要排序的數(shù)據(jù)已基本有序 D.要排序的數(shù)據(jù)個數(shù)為奇數(shù)第一章緒論1 1 . .數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各個數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。2 2 .順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。3 3 . .數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的次序關(guān)系，它依賴于數(shù)據(jù)的存