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

1、第一章緒論1.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（A.動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)C）兩大類(lèi)。B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2.在下面的程序段中，對(duì) x 的賦值語(yǔ)句的頻度為（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 .在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除 p 所指的結(jié)點(diǎn)時(shí)須修改指針(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 個(gè)元素和找第 i 個(gè)元素的前趨元素，則采用(B)存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表 B.順序表 C.雙向鏈表 D.單循環(huán)鏈表12 .若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（D）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表 B,僅有頭指針的單循環(huán)鏈表C.雙向鏈表 D.僅有尾指針的單循環(huán)鏈表第三章棧和隊(duì)列1.向一個(gè)棧頂指針為 top 的鏈棧中插入一個(gè) p 所指結(jié)點(diǎn)時(shí)，其操作步驟為（C）。B

4、. p-next=top-next;top-next=p；D.p-next=top；top=top-next;2 .對(duì)于棧操作數(shù)據(jù)的原則是（A.top-next=p；C.p-next=top；top=p；A.先進(jìn)先出 B.后進(jìn)先出C.后進(jìn)后出 D.不分順序3 .若已知一個(gè)棧的入棧序列是 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.采用順序存儲(chǔ)的兩個(gè)棧的共享空間 S1.m,用 topi

5、代表第 i 個(gè)棧（i=1,2）的棧頂,棧 1 的底在 S1,棧 2 的底在 Sm,則棧滿的條件是（B）。A.top2top1=0B.top1+1=top2C.top1+top2=mD.top1=top26 .一個(gè)棧的入棧序列是 a,b,c,d,e,則棧的不可能的輸出序列是（C）。A.edcbaB.decbaC.dceabD.abcde7 .在一個(gè)鏈隊(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)的單鏈表存儲(chǔ)隊(duì)列時(shí)，在進(jìn)行刪除運(yùn)算時(shí)（D）o

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

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

8、下標(biāo) i 從 1 到 8,列下標(biāo) j 從 1 到 10,從首地址SA 開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)， 存放該數(shù)組至少需要的單元個(gè)數(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 .稀疏矩陣采用壓縮存儲(chǔ)，一般有(C)兩種方法。A,二維數(shù)組和三維數(shù)組 B,三元組和散列C.三元組表和十字鏈表 D.散列和十字鏈表第五章樹(shù)結(jié)構(gòu)1 .下列說(shuō)法正確的是

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

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

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

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

13、邊的無(wú)向圖的鄰接多重表的存儲(chǔ)中，邊結(jié)點(diǎn)的個(gè)數(shù)有（A）。A.nB.2nC.n/2D.nn3 .下列哪一種圖的鄰接矩陣是對(duì)稱(chēng)矩陣？（B）A.有向圖 B.無(wú)向圖 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 個(gè)頂點(diǎn)和 e 條邊，進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為(D)A.

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

15、.8B.9C.i0D.ii第七章查找1 .靜態(tài)查找表與動(dòng)態(tài)查找表的根本區(qū)別在于(B)。A.它們的邏輯結(jié)構(gòu)不一樣 B.施加在其上的操作不一樣C.所包含的數(shù)據(jù)元素類(lèi)型不一樣 D.存儲(chǔ)實(shí)現(xiàn)不一樣2.在表長(zhǎng)為 n 的順序表上實(shí)施順序查找，在查找不成功時(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)的最長(zhǎng)路徑C.最長(zhǎng)的回路A)。B.從源點(diǎn)到匯點(diǎn)的最短路徑D.最短的回路5.一個(gè)無(wú)向圖的鄰接表如下圖所示3 .順序查找適用于存儲(chǔ)結(jié)構(gòu)為(C)的線性表。A,散列存儲(chǔ) B.壓縮存儲(chǔ)

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

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

18、奇數(shù) B.偶數(shù) C.素?cái)?shù) D.充分大的數(shù)12 .在采用線性探測(cè)法處理沖突所構(gòu)成的散列表上進(jìn)行查找，可能要探測(cè)多個(gè)位置，在查找成功的情況下，所探測(cè)到的這些位置上的鍵值(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 個(gè)無(wú)序的元素， 希望用最快的速度挑選出其中前

19、 10 個(gè)最大的元素， 最好選用 （C）排序法。A.冒泡排序 B.快速排序 C.堆排序 D.基數(shù)排序3 .具有 12 個(gè)記錄的序列，采用冒泡排序最少的比較次數(shù)是（C）。A.1B.144C.11D.664 .下列四種排序方法中，要求內(nèi)存容量最大的是（D）。A.插入排序 B.選擇排序 C.快速排序 D.歸并排序5 .初始序列已經(jīng)按鍵值有序時(shí)，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為（D）A.n1234B.nlog2nC.log2nD.n16 .下列四種排序方法， 在排序過(guò)程中， 關(guān)鍵碼比較的次數(shù)與記錄的初始排列順序無(wú)關(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,個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為(CA.384046567984B.40C.403846567984D.4040,84）,則利用堆排序的方法建立的初始7956384046567940463840,84）,則利用快速排序的方法，以第一）。384679568438

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