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

1、【精品文檔】如有侵權(quán)，請聯(lián)系網(wǎng)站刪除，僅供學(xué)習(xí)與交流數(shù)據(jù)結(jié)構(gòu)與算法(張曉莉)習(xí)題：選擇題、判斷題.精品文檔.第一章 緒論1. 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ C ）兩大類。A動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈式結(jié)構(gòu)C線性結(jié)構(gòu)、非線性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2. 在下面的程序段中，對x的賦值語句的頻度為（ C ）。For（k=1；k<=n；k+） For（j=1；j<=n；j+）x=x1；AO(2n) BO(n) CO(n2) DO(log2n)3. 采用順序存儲結(jié)構(gòu)表示數(shù)據(jù)時，相鄰的數(shù)據(jù)元素的存儲地址（ A ）。A一定連續(xù) B一定不連續(xù)C不一定連續(xù) D部分連續(xù)、部分不連續(xù)4. 下

2、面關(guān)于算法的說法，正確的是（ D ）。A算法的時間復(fù)雜度一般與算法的空間復(fù)雜度成正比B解決某問題的算法可能有多種，但肯定采用相同的數(shù)據(jù)結(jié)構(gòu)C算法的可行性是指算法的指令不能有二義性D同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低5. 在發(fā)生非法操作時，算法能夠作出適當處理的特性稱為（ B ）。A正確性 B健壯性 C可讀性 D可移植性第二章 線性表1. 線性表是（ A ）。A一個有限序列，可以為空 B一個有限序列，不能為空C一個無限序列，可以為空 D一個無限序列，不能為空2對順序存儲的線性表，設(shè)其長度為n，在任何位置上插入或刪除操作都是等概率的。插入一個元素時平均要移動表中的（ A ）個元素。An

3、/2 B（n1）/2 C（n1）/2 Dn 3線性表采用鏈式存儲時，其地址（ D ）。A必須是連續(xù)的 B部分地址必須是連續(xù)的 C一定是不連續(xù)的 D連續(xù)與否均可以 4用鏈表表示線性表的優(yōu)點是（ C ）。A便于隨機存取 B花費的存儲空間較順序存儲少C便于插入和刪除 D數(shù)據(jù)元素的物理順序與邏輯順序相同5鏈表中最常用的操作是在最后一個元素之后插入一個元素和刪除最后一個元素，則采用（ C ）存儲方式最節(jié)省運算時間。A單鏈表 B雙鏈表 C單循環(huán)鏈表 D帶頭結(jié)點的雙向循環(huán)鏈表6下面關(guān)于線性表的敘述，錯誤的是（ B ）。A線性表采用順序存儲，必須占用一片地址連續(xù)的單元B線性表采用順序存儲，便于進行插入和刪除操

4、作C線性表采用鏈式存儲，不必占用一片地址連續(xù)的單元D線性表采用鏈式存儲，不便于進行插入和刪除操作7單鏈表中，增加一個頭結(jié)點的目的是為了（ C ）。A使單鏈表至少有一個結(jié)點 B標識表結(jié)點中首結(jié)點的位置C方便運算的實現(xiàn) D說明單鏈表是線性表的鏈式存儲8在單鏈表指針為p的結(jié)點之后插入指針為s結(jié)點，正確的操作是（ B ）。Ap->next=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=

5、s；9在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針（ A ）。A（p-> prior)-> next = p->next ; （p->next）->prior =p-> prior ;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-> pr

6、ior =（p-> next）-> next10. 完成在雙向循環(huán)鏈表結(jié)點p之后插入s的操作是（ D ）。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-> next;Cs-> prior =p; s-> next = p->next; p-> next =s; p-> next

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

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

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

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

11、母的個數(shù) B串中所含字符的個數(shù)C串中所含不同字符的個數(shù) D串中所含非空格字符的個數(shù)3.4. 二維數(shù)組M的成員是6個字符（每個字符占一個存儲單元，即一個字節(jié)）組成的串，行下標i的范圍從0到8，列下標j的范圍從1到10，則存放M至少需要（1）（ D ）個字節(jié)；M的第8列和第5行共占（2）（ A ）個字節(jié)；若M按行優(yōu)先方式存儲，元素M85的起始地址與當M按列優(yōu)先方式存儲時的（3）（ C ）元素的起始地址一致。（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中，每

12、個元素的存儲占3個單元，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元個數(shù)是（1）（ C ）；若該數(shù)組按行存放，元素A85的起始地址為（2）（ D ）；若該數(shù)組按列存放，元素A85的起始地址為（3）（ B ）。（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. 稀疏矩陣采用壓縮存儲，一般有（ C ）兩種方法。A二維數(shù)組和三維數(shù)組 B三元組和散列C三元組表和十字鏈表 D

13、散列和十字鏈表第五章 樹結(jié)構(gòu)1. 下列說法正確的是（ C ）。A二叉樹中任何一個結(jié)點的度都為2 B二叉樹的度為2C一棵二叉樹的度可小于2 D任何一棵二叉樹中至少有一個結(jié)點的度為22. 以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，在具有n個結(jié)點的二叉鏈表中（n0），空鏈域的個數(shù)為（ C ）。A2n1 Bn1 Cnl D2nl3. 線索化二叉樹中，某結(jié)點*p沒有孩子的充要條件是（ B ）。A. p->lchild=NULL B. p->ltag=1且p->rtag=1C. p->ltag=0 D. p->lchild=NULL且p->ltag=14. 如果結(jié)點A有3個兄弟，

14、而且B是A的雙親，則B的度是（ B ）。A3 B4 C5 D15. 某二叉樹T有n個結(jié)點，設(shè)按某種順序?qū)中的每個結(jié)點進行編號，編號值為1，2，n，且有如下性質(zhì)：T中任意結(jié)點v，其編號等于左子樹上的最小編號減1，而v的右子樹的結(jié)點中，其最小編號等于v左子樹上結(jié)點的最大編號加1，這是按（ B ）編號的。A. 中序遍歷序列 B. 先序遍歷序列 C. 后序遍歷序列 D. 層次順序6. 設(shè)F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非終端結(jié)點，B中右指針域為空的結(jié)點有（ C ）個。An1 Bn Cnl Dn27. 一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（ C ）。A500 B50

15、1 C490 D4958. 設(shè)森林F中有3棵樹，第1、第2和第3棵樹的結(jié)點個數(shù)分別為N1，N2和N3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（ D ）。AN1 BN1N2 CN2 DN2N39. 任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷序列中的相對次序（ A ）。A. 不發(fā)生改變 B. 發(fā)生改變 C. 不能確定 D. 以上都不對10. 若一棵二叉樹的后序遍歷序列為dabec，中序遍歷序列為debac，則先序遍歷序列為（ D ）。A. cbed B. decab C. deabc D. cedba11. 若一棵二叉樹的先序遍歷序列為abdgcefh，中序遍歷的序列為dgbaechf

16、，則后序遍歷的結(jié)果為（ D ）。A. gcefha B. gdbecfha C. bdgaechf D. gdbehfca12. 一棵非空二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（ B ）。A. 所有的結(jié)點均無左孩子 B. 所有的結(jié)點均無右孩子C. 只有一個葉子結(jié)點 D. 是一棵滿二叉樹13. 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為（ B ）。A. 2h B. 2h1 C. 2h1 D. h114. 一個具有567個結(jié)點的二叉樹的高h為（ D ）。A. 9 B. 10 C. 9566之間 D. 10567之間第六章 圖結(jié)構(gòu)1. n

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

18、. v0，v1，v2，v3C. v0，v2，v1，v3 D. v0，v1，v3，v2（2）從頂點v0出發(fā)進行廣度優(yōu)先搜索，經(jīng)歷的結(jié)點順序為（ D ）。A. v0，v3，v2，v1 B. v0，v1，v2，v3C. v0，v2，v1，v3 D. v0，v1，v3，v26. 設(shè)有向圖n個頂點和e條邊，進行拓撲排序時，總的計算時間為（ D ）。A. O(nlog2e) B. O(e×n) C. O(elog2n) D. O(ne)7. 含有n個頂點e條邊的無向連通圖，利用Kruskal算法生成最小生成樹，其時間復(fù)雜度為（ A ）。A. O(elog2e) B. O(e×n) C.

19、 O(elog2n) D. O(nlog2n)8. 關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（ A ）。A. 從源點到匯點的最長路徑 B. 從源點到匯點的最短路徑C. 最長的回路 D. 最短的回路9. 下面關(guān)于求關(guān)鍵路徑的說法，不正確的是（ C ）。A. 求關(guān)鍵路徑是以拓撲排序為基礎(chǔ)的B. 一個事件的最早開始時間同以該事件為尾的弧的活動最早開始時間相同C. 一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差D. 關(guān)鍵活動一定位于關(guān)鍵路徑上10. 有10個結(jié)點的無向圖至少有（ B ）條邊才能確保其是連通圖。A. 8 B. 9 C. 10 D. 11第七章 查找1. 靜態(tài)查找表與動態(tài)

20、查找表的根本區(qū)別在于（ B ）。A. 它們的邏輯結(jié)構(gòu)不一樣 B. 施加在其上的操作不一樣C. 所包含的數(shù)據(jù)元素類型不一樣 D. 存儲實現(xiàn)不一樣2. 在表長為n的順序表上實施順序查找，在查找不成功時與關(guān)鍵字比較的次數(shù)為（ A ）。A. n B. 1 C. n+1 D. n-13. 順序查找適用于存儲結(jié)構(gòu)為（ C ）的線性表。A. 散列存儲 B. 壓縮存儲C. 順序存儲或鏈式存儲 D. 索引存儲4. 用順序查找法對具有n個結(jié)點的線性表查找一個結(jié)點的時間復(fù)雜度為（ C ）。AO(log2n2) B. O(nlog2n) C. O(n) D. O(log2n)5. 適用于折半查找的表的存儲方式及元素排

21、列要求為（ D ）。A. 鏈接方式存儲，元素無序B. 鏈接方式存儲，元素有序C. 順序方式存儲，元素無序D. 順序方式存儲，元素有序6. 有一個長度為12的有序表，按折半查找法對該表進行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為（ B ）。A. 35/12 B. 37/12 C. 39/12 D. 43/127. 在有序表1，3，9，12，32，41，62，75，77，82，95，100上進行折半查找關(guān)鍵字為82的數(shù)據(jù)元素需要比較（ C ）次。A. 1 B. 2 C. 4 D. 58. 設(shè)散列表長為14，散列函數(shù)為H（key）= key % 11。當前表中已有4個結(jié)點：addr

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

23、素數(shù) D. 充分大的數(shù)12. 在采用線性探測法處理沖突所構(gòu)成的散列表上進行查找，可能要探測多個位置，在查找成功的情況下，所探測到的這些位置上的鍵值（ B ）。A. 一定是同義詞 B. 一定不是同義詞C. 都相同 D. 不一定都是同義詞第八章 排序1. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ A ）。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序2. 設(shè)有1000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好選用（ C ）排序法。A. 冒泡排序 B. 快速排序 C. 堆排序 D. 基數(shù)排序3. 具有12個記錄的序列，采用冒泡排序最少的比較次數(shù)

24、是（ C ）。A. 1 B. 144 C. 11 D. 664. 下列四種排序方法中，要求內(nèi)存容量最大的是（ D ）。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序5. 初始序列已經(jīng)按鍵值有序時，用直接插入算法進行排序，需要比較的次數(shù)為（ D ）。An2 B. nlog2n C. log2n D. n16. 下列四種排序方法，在排序過程中，關(guān)鍵碼比較的次數(shù)與記錄的初始排列順序無關(guān)的是（ C ）。A. 直接插入排序和快速排序 B. 快速排序和歸并排序C. 直接選擇排序和歸并排序 D. 直接插入排序和歸并排序7. 一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排

25、序的方法建立的初始堆為（ B ）。A. 79，46，56，38，40，84 B. 84，79，56，38，40，46C. 84，79，56，46，40，38 D. 84，56，79，40，46，388. 一組記錄的排序碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為（ C ）。A. 38，40，46，56，79，84 B. 40，38，46，79，56，84C. 40，38，46，56，79，84 D. 40，38，46，84，56，799. 用某種排序方法對線性表（ 25，84，21，47，15，27，68，35，20）進行排序時，元素序列的變化情況如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84則所采用的排序方法是（ D ）。