數(shù)據(jù)結(jié)構(gòu)與算法張曉莉習(xí)題

1、第一章 緒論1. 從邏輯上可以把數(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)2. 在下面的程序段中，對x的賦值語句的頻度為（ ）。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在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針（ ）。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é)點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個元素和找第i個元素的前趨元素，則采用（ ）存儲方式最節(jié)省運算時間。A單鏈表 B順序表 C雙向鏈表 D單循環(huán)鏈表12. 若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ ）存儲方式最節(jié)省運算時間。A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙向鏈表 D僅有尾指針的單循環(huán)鏈表

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

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

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

7、. 二維數(shù)組M的成員是6個字符（每個字符占一個存儲單元，即一個字節(jié)）組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10，則存放M至少需要（1）（ ）個字節(jié)；M的第8列和第5行共占（2）（ ）個字節(jié)；若M按行優(yōu)先方式存儲，元素M85的起始地址與當(dāng)M按列優(yōu)先方式存儲時的（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中，每個元素的存儲占3個單元，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存

8、放該數(shù)組至少需要的單元個數(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. 稀疏矩陣采用壓縮存儲，一般有（ ）兩種方法。A二維數(shù)組和三維數(shù)組 B三元組和散列C三元組表和十字鏈表 D散列和十字鏈表第五章 樹結(jié)構(gòu)1. 下列說法正確的是（ ）。A二叉樹中任何一個結(jié)點的度都為2 B二叉樹的度為2C一棵二

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

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

11、N39. 任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷序列中的相對次序（ ）。A. 不發(fā)生改變 B. 發(fā)生改變 C. 不能確定 D. 以上都不對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é)點均無左孩子 B. 所有的結(jié)點均無右孩子C. 只有一個葉子結(jié)點 D. 是一棵滿二叉樹13. 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為（ ）。A. 2h B. 2h1 C. 2h1 D. h114. 一個具有567個結(jié)點的二叉樹的高h(yuǎn)為（ ）。A. 9 B. 10 C. 9566之間 D. 10567之間第六章 圖結(jié)構(gòu)1. n條邊的無向圖的鄰接表的存儲中，邊結(jié)點的個數(shù)有（ ）。A. n B. 2n C. n/2 D. nn2. n條邊的無向圖的鄰接多重表的存儲中，邊結(jié)點的個數(shù)有（ ）。A. n B. 2n C. n/2 D. nn3. 下列哪

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

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

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

16、A. 散列存儲 B. 壓縮存儲C. 順序存儲或鏈?zhǔn)酱鎯?D. 索引存儲4. 用順序查找法對具有n個結(jié)點的線性表查找一個結(jié)點的時間復(fù)雜度為（ ）。AO(log2n2) B. O(nlog2n) C. O(n) D. O(log2n)5. 適用于折半查找的表的存儲方式及元素排列要求為（ ）。A. 鏈接方式存儲，元素?zé)o序B. 鏈接方式存儲，元素有序C. 順序方式存儲，元素?zé)o序D. 順序方式存儲，元素有序6. 有一個長度為12的有序表，按折半查找法對該表進行查找，在表內(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上進行折半查找關(guān)鍵字為82的數(shù)據(jù)元素需要比較（ ）次。A. 1 B. 2 C. 4 D. 58. 設(shè)散列表長為14，散列函數(shù)為H（key）= key % 11。當(dāng)前表中已有4個結(jié)點：addr (15)=4，addr (38)=5，addr (61)=6，addr (84)=7。如用二次探測再散列處理沖突，則關(guān)鍵字為49的結(jié)點的地址是（ ）。A. 8 B. 3 C. 5 D. 99. 散列函數(shù)有一個共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以（ ）取其值域的每個值。A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率10. 假定有k個

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

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