數(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) 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)2. 在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為（ ）。For（k=1；k=n；k+） For（j=1；jnext=s；s-next=p-next；Bs-next=p-next；p-next=s；Cp-next=s；p-next=s-next；Dp-next=s-next；p-next=s；9在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（ ）。A（p- prior)- next = p-next ; （p-next）-prior =p- prio

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

3、next;Cs- prior =p; s- next = p-next; p- next =s; p- next- prior =s;Ds- prior =p; s- next = p-next; p- next- prior =s;p- next =s; 11. 若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A單鏈表 B順序表 C雙向鏈表 D單循環(huán)鏈表12. 若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙向鏈表 D僅有尾指針的單循環(huán)鏈表

4、第三章 棧和隊(duì)列1向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)p所指結(jié)點(diǎn)時(shí)，其操作步驟為（ ）。Atop-next=p； Bp-next=top-next；top-next=p；Cp-next=top；top=p； Dp-next=top；top=top-next；2對(duì)于棧操作數(shù)據(jù)的原則是（ ）。A先進(jìn)先出 B后進(jìn)先出C后進(jìn)后出 D不分順序3若已知一個(gè)棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若pn 是n，則Pi為（ ）。Ai Bni Cnil D不確定4表達(dá)式a *（bc）d的后綴表達(dá)式是（ ）。Aabcd* Babc*dCabc*d D*abcd5采用順序存儲(chǔ)的兩個(gè)棧的共

5、享空間S1.m，用topi代表第i個(gè)棧（i=1，2）的棧頂，棧1的底在S1，棧2的底在Sm，則棧滿的條件是（ ）。Atop2top1=0 Btop11= top2Ctop1top2 =m Dtop1= top26一個(gè)棧的入棧序列是a，b，c，d，e，則棧的不可能的輸出序列是（ ）。Aedcba Bdecba Cdceab Dabcde7在一個(gè)鏈隊(duì)列中，若f、r分別為隊(duì)首、隊(duì)尾指針，則插入p所指結(jié)點(diǎn)的操作為（ ）。Af-next=p；f=p Br-next=p；r=pCp-next=r；r=p Dp-next=f；f=p8用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí)，在進(jìn)行刪除運(yùn)算時(shí)（ ）。A僅修改頭指針 B

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

7、. 二維數(shù)組M的成員是6個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元，即一個(gè)字節(jié)）組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10，則存放M至少需要（1）（ ）個(gè)字節(jié)；M的第8列和第5行共占（2）（ ）個(gè)字節(jié)；若M按行優(yōu)先方式存儲(chǔ)，元素M85的起始地址與當(dāng)M按列優(yōu)先方式存儲(chǔ)時(shí)的（3）（ ）元素的起始地址一致。（1）A. 90 B. 180 C. 240 D. 540（2）A. 108 B. 114 C. 54 D. 60（3）A. M85 B. M310 C. M58 D. M095. 數(shù)組A中，每個(gè)元素的存儲(chǔ)占3個(gè)單元，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，存

8、放該數(shù)組至少需要的單元個(gè)數(shù)是（1）（ ）；若該數(shù)組按行存放，元素A85的起始地址為（2）（ ）；若該數(shù)組按列存放，元素A85的起始地址為（3）（ ）。（1）A. 80 B. 100 C.240 D. 270（2）A. SA+141 B. SA+144 C. SA+222 D. SA+225（3）A. SA+141 B. SA+180 C. SA+117 D. SA+2256. 稀疏矩陣采用壓縮存儲(chǔ)，一般有（ ）兩種方法。A二維數(shù)組和三維數(shù)組 B三元組和散列C三元組表和十字鏈表 D散列和十字鏈表第五章 樹結(jié)構(gòu)1. 下列說(shuō)法正確的是（ ）。A二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2 B二叉樹的度為2C一棵二

9、叉樹的度可小于2 D任何一棵二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為22. 以二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中（n0），空鏈域的個(gè)數(shù)為（ ）。A2n1 Bn1 Cnl D2nl3. 線索化二叉樹中，某結(jié)點(diǎn)*p沒(méi)有孩子的充要條件是（ ）。A. p-lchild=NULL B. p-ltag=1且p-rtag=1C. p-ltag=0 D. p-lchild=NULL且p-ltag=14. 如果結(jié)點(diǎn)A有3個(gè)兄弟，而且B是A的雙親，則B的度是（ ）。A3 B4 C5 D15. 某二叉樹T有n個(gè)結(jié)點(diǎn)，設(shè)按某種順序?qū)中的每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)值為1，2，n，且有如下性質(zhì)：T中任意結(jié)點(diǎn)v，其

10、編號(hào)等于左子樹上的最小編號(hào)減1，而v的右子樹的結(jié)點(diǎn)中，其最小編號(hào)等于v左子樹上結(jié)點(diǎn)的最大編號(hào)加1，這是按（ ）編號(hào)的。A. 中序遍歷序列 B. 先序遍歷序列 C. 后序遍歷序列 D. 層次順序6. 設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn)，B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（ ）個(gè)。An1 Bn Cnl Dn27. 一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ ）。A500 B501 C490 D4958. 設(shè)森林F中有3棵樹，第1、第2和第3棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為N1，N2和N3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是（ ）。AN1 BN1N2 CN2 DN2

11、N39. 任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（ ）。A. 不發(fā)生改變 B. 發(fā)生改變 C. 不能確定 D. 以上都不對(duì)10. 若一棵二叉樹的后序遍歷序列為dabec，中序遍歷序列為debac，則先序遍歷序列為（ ）。A. cbed B. decab C. deabc D. cedba11. 若一棵二叉樹的先序遍歷序列為abdgcefh，中序遍歷的序列為dgbaechf，則后序遍歷的結(jié)果為（ ）。A. gcefha B. gdbecfha C. bdgaechf D. gdbehfca12. 一棵非空二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（ ）。

12、A. 所有的結(jié)點(diǎn)均無(wú)左孩子 B. 所有的結(jié)點(diǎn)均無(wú)右孩子C. 只有一個(gè)葉子結(jié)點(diǎn) D. 是一棵滿二叉樹13. 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（ ）。A. 2h B. 2h1 C. 2h1 D. h114. 一個(gè)具有567個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（ ）。A. 9 B. 10 C. 9566之間 D. 10567之間第六章 圖結(jié)構(gòu)1. n條邊的無(wú)向圖的鄰接表的存儲(chǔ)中，邊結(jié)點(diǎn)的個(gè)數(shù)有（ ）。A. n B. 2n C. n/2 D. nn2. n條邊的無(wú)向圖的鄰接多重表的存儲(chǔ)中，邊結(jié)點(diǎn)的個(gè)數(shù)有（ ）。A. n B. 2n C. n/2 D. nn3. 下列哪

13、一種圖的鄰接矩陣是對(duì)稱矩陣？（ ）A. 有向圖 B. 無(wú)向圖 C. AOV網(wǎng) D. AOE網(wǎng)4. 最短路徑的生成算法可用（ ）。A. 普利姆算法 B. 克魯斯卡爾算法 C. 迪杰斯特拉算法 D. 哈夫曼算法5. 一個(gè)無(wú)向圖的鄰接表如下圖所示。（1）從頂點(diǎn)v0出發(fā)進(jìn)行深度優(yōu)先搜索，經(jīng)歷的結(jié)點(diǎn)順序?yàn)椋?）。A. v0，v3，v2，v1 B. v0，v1，v2，v3C. v0，v2，v1，v3 D. v0，v1，v3，v2（2）從頂點(diǎn)v0出發(fā)進(jìn)行廣度優(yōu)先搜索，經(jīng)歷的結(jié)點(diǎn)順序?yàn)椋?）。A. v0，v3，v2，v1 B. v0，v1，v2，v3C. v0，v2，v1，v3 D. v0，v1，v3，v26

14、. 設(shè)有向圖n個(gè)頂點(diǎn)和e條邊，進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為（ ）。A. O(nlog2e) B. O(en) C. O(elog2n) D. O(ne)7. 含有n個(gè)頂點(diǎn)e條邊的無(wú)向連通圖，利用Kruskal算法生成最小生成樹，其時(shí)間復(fù)雜度為（ ）。A. O(elog2e) B. O(en) C. O(elog2n) D. O(nlog2n)8. 關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（ ）。A. 從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 B. 從源點(diǎn)到匯點(diǎn)的最短路徑C. 最長(zhǎng)的回路 D. 最短的回路9. 下面關(guān)于求關(guān)鍵路徑的說(shuō)法，不正確的是（ ）。A. 求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的B. 一個(gè)事件的最早開始時(shí)間同以該事件

15、為尾的弧的活動(dòng)最早開始時(shí)間相同C. 一個(gè)事件的最遲開始時(shí)間為以該事件為尾的弧的活動(dòng)最遲開始時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差D. 關(guān)鍵活動(dòng)一定位于關(guān)鍵路徑上10. 有10個(gè)結(jié)點(diǎn)的無(wú)向圖至少有（ ）條邊才能確保其是連通圖。A. 8 B. 9 C. 10 D. 11第七章 查找1. 靜態(tài)查找表與動(dòng)態(tài)查找表的根本區(qū)別在于（ ）。A. 它們的邏輯結(jié)構(gòu)不一樣 B. 施加在其上的操作不一樣C. 所包含的數(shù)據(jù)元素類型不一樣 D. 存儲(chǔ)實(shí)現(xiàn)不一樣2. 在表長(zhǎng)為n的順序表上實(shí)施順序查找，在查找不成功時(shí)與關(guān)鍵字比較的次數(shù)為（ ）。A. n B. 1 C. n+1 D. n-13. 順序查找適用于存儲(chǔ)結(jié)構(gòu)為（ ）的線性表。

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

17、序表1，3，9，12，32，41，62，75，77，82，95，100上進(jìn)行折半查找關(guān)鍵字為82的數(shù)據(jù)元素需要比較（ ）次。A. 1 B. 2 C. 4 D. 58. 設(shè)散列表長(zhǎng)為14，散列函數(shù)為H（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)的地址是（ ）。A. 8 B. 3 C. 5 D. 99. 散列函數(shù)有一個(gè)共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以（ ）取其值域的每個(gè)值。A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率10. 假定有k個(gè)

18、關(guān)鍵字互為同義詞，若用線性探測(cè)法把這k個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行（ ）次探測(cè)。A. k1次 B. k次 C. k1次 D. k（k1）/2次11. 在散列函數(shù)H（k）= k % m中，一般來(lái)講，m應(yīng)?。?）。A. 奇數(shù) B. 偶數(shù) C. 素?cái)?shù) D. 充分大的數(shù)12. 在采用線性探測(cè)法處理沖突所構(gòu)成的散列表上進(jìn)行查找，可能要探測(cè)多個(gè)位置，在查找成功的情況下，所探測(cè)到的這些位置上的鍵值（ ）。A. 一定是同義詞 B. 一定不是同義詞C. 都相同 D. 不一定都是同義詞第八章 排序1. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ）。A. 插入排序 B. 選擇排序 C. 快速排

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