《經(jīng)典數(shù)據(jù)結(jié)構(gòu)習(xí)題集含答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《經(jīng)典數(shù)據(jù)結(jié)構(gòu)習(xí)題集含答案（7頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、線性表 1.下列有關(guān)線性表的敘述中，正確的是（ A ）。 A）線性表中元素之間的關(guān)系是線性關(guān)系 B）線性表中至少有一個(gè)元素 C）線性表中的任一元素有且僅有一個(gè)直接前趨 D）線性表中的任一元素有且僅有一個(gè)直接后繼 2.下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（A ） A）存儲(chǔ)密度大 B）插入方便 C）刪除方便 D）可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示 3.在一個(gè)長度為n的順序表中，在第i個(gè)元素（1<=i<=n）之前插入一個(gè)新元素時(shí)需向后移動(dòng)（ D ）個(gè)元素。 A）1 B）n-i C）n-i-1 D）n-i+1 4.如果某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前驅(qū)，那么采用

2、（ A ）存儲(chǔ)方式最節(jié)省時(shí)間。 A）順序表 B）單鏈表 C）雙鏈表 D）循環(huán)鏈表 5.對順序存儲(chǔ)的線性表，設(shè)其長度為n，且在任何位置上插入或刪除操作都是等概率的。則插入一個(gè)元素時(shí)平均要移動(dòng)表中的（A ）個(gè)元素。 A）n/2 B）(n+1)/2 C）(n-1)/2 D）n 6.下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)？（ C ） A）存儲(chǔ)密度太大 B）隨機(jī)存取 C）一般要估計(jì)最大的需要空間 D）只能應(yīng)用于少數(shù)幾種邏輯結(jié)構(gòu)的存儲(chǔ)表示 7.在單鏈表中，增加頭結(jié)點(diǎn)的目的是（ C ）。 A）使單鏈表至少有一個(gè)結(jié)點(diǎn) B）標(biāo)志表中首結(jié)點(diǎn)的位置 C）方便運(yùn)算的實(shí)現(xiàn) D）說明單鏈表是線性表

3、的鏈?zhǔn)酱鎯?chǔ)表示 8.單鏈表不具有的特點(diǎn)是（ A ）。 A)可隨機(jī)訪問任一元素 B)插入和刪除不需要移動(dòng)元素 C)不必事先估計(jì)存儲(chǔ)空間 D)所需空間和線性表長度成正比 9.循環(huán)鏈表的主要優(yōu)點(diǎn)是（ D）。 A）不再需要頭指針了 B）已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到他的直接前趨 C）在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好的保證鏈表不斷開 D）從表中的任意結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表 10.鏈表對于數(shù)據(jù)元素的插入與刪除是（ B ）。 A）不需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針 B）不需移動(dòng)結(jié)點(diǎn)，只需改變結(jié)點(diǎn)指針 C）只需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針 D）既需移動(dòng)結(jié)點(diǎn)，又需改變結(jié)點(diǎn)指針 11

4、.在一個(gè)單鏈表中,已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若要在q 和p所指結(jié)點(diǎn)之間插入s所指的結(jié)點(diǎn),則執(zhí)行（B ）。 A）s->next = p->next; p->next = s; B）q->next = s; s->next = p; C）p->next = s; s->next = q; D）p->next = s->next; s->next = p; 12.向一個(gè)有115個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)（ C ）個(gè)元素。 A) 115 B) 114 C) 58 D) 57 13.帶頭結(jié)點(diǎn)的單鏈表Head為空表的判定條件是 ( B ) 。

5、 A) Head->next==Head B) Head->next==NULL C) Head!=NULL D) Head==NULL 14.若要求能快速地實(shí)現(xiàn)在鏈表的末尾插入結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)的運(yùn)算，則選擇( B )最合適。 A) 單鏈表 B) 帶尾指針的單循環(huán)鏈表 C) 雙鏈表 D) 雙循環(huán)鏈表 15.給定有n個(gè)元素的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是( D )。 A)O(n) B)O(log2n) C)O(nlog2n) D. O(n2) 16.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其位置( C)。 A)必須是連續(xù)的 B)必須是不連續(xù)的 C)連續(xù)與否均可 D)部分位置必須是連續(xù)

6、的 17.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中，插入一個(gè)新的結(jié)點(diǎn)并使之仍然有序的時(shí)間復(fù)雜度是(A )。 A)O(n) B)O(log2n) C)O(1) D)O(n2) 排序 1.在下列排序算法中，時(shí)間復(fù)雜度不受數(shù)據(jù)初始特性影響，恒為O(n2)的是（C ）。 A）插入排序 B）冒泡排序 C）選擇排序 D）堆排序 2.在各種排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為（ C）。 A）希爾排序 B）冒泡排序 C）插入排序 D）選擇排序 3.快速排序方法在（C?。┣闆r下最不利于發(fā)揮其長處。 A）要排序的數(shù)

7、據(jù)量太大 B）要排序的數(shù)據(jù)含有多個(gè)相同值 C）要排序的數(shù)據(jù)已基本有序 D）要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù) 4.已知10個(gè)數(shù)據(jù)元素為(54,28,16,34,73,62,95,60,26,43),對該數(shù)列按從小到大排序，經(jīng)過一趟冒泡排序后的序列為（B?。?。 A）16，28，34，54，73，62，60，26，43，95 B）28，16，34，54，62，73，60，26，43，95 C）28，16，34，54，62，60，73，26，43，95 D）16，28，34，54，62，60，73，26，43，95 5.一組記錄的關(guān)鍵字為（46,79,56,38,40,84）,則利用快速排

8、序的方法，以第一個(gè)記錄為基準(zhǔn)元素得到的一次劃分結(jié)果為（ C ）。 A）38,40,46,56,79,84 B）40,38,46,79,56,84 C）40,38,46,56,79,84 D）40,38,46,84,56,79 6.用某種排序方法對線性表(25,84,21,47,15,27,68,35,20)進(jìn)行排序時(shí),元素序列的變化情況如下: (1)20,15,21,25,47,27,68,35,84 (2)15,20,21,25,35,27,47,68,84 (3)15,20,21,25,27,35,47,68,84 則所采用的排序方法是（　D ）。 A）選擇排序 B）

9、希爾排序 C）歸并排序 D）快速排序 7.在待排序的元素序列基本有序的前提下，效率最高的排序方法是（A?。? A）插入排序 B）快速排序 C）歸并排序 D）選擇排序 8.一組記錄的排序碼為（20,29,11,74,35,3,8,56）,則利用堆排序方法建立的初始(小頂)堆為（B　 ）。 A）20,29,11,74,35,3,8,56 B）3,29,8,56,35,11,20,74 C）3,8,11,20,29,35,56,74 D）20,29,3,8,11,35,74,56 9.下列關(guān)鍵碼序列中，屬于堆的是（A　）。 A)（15，30，22，93，52，71） B)（

10、15，71，30，22，93，52） C)（15，52，22，93，30，71） D)（93，30，52，22，15，71） 10.若要求盡可能快地對實(shí)數(shù)數(shù)組進(jìn)行穩(wěn)定的排序，則應(yīng)選(C　)。 A)快速排序 B)堆排序 C)歸并排序 D)基數(shù)排序 11.下列排序算法的時(shí)間復(fù)雜度最小的是（D?。?。 A)冒泡排序 B)希爾排序 C)簡單選擇排序 D)歸并排序 12.設(shè)有1000個(gè)無序的元素,希望用最快的速度挑選出其中前10個(gè)最大的元素,最好（ C）排序法。 A)起泡排序 B)快速排序 C)堆排序 D)基數(shù)排序 13.插入排序算法在每一趟都能選取出一個(gè)元素放在其最終的位置上。( B

11、 ) A)正確 B)不正確 14.直接插入排序是不穩(wěn)定的排序方法。( B ) A)正確 B)不正確 15.直接插入排序的最壞情況是初始序列為（ B ）序。 A)正 B)反 C)正和反 D)無 16.在各排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱為(D )。 A)希爾排序 B)歸并排序 C)插入排序 D)選擇排序 棧和隊(duì)列 1.棧的特點(diǎn)是( B )。 A）先進(jìn)先出 B）后進(jìn)先出 C）進(jìn)優(yōu)于出 D）出優(yōu)于進(jìn) 2.棧和隊(duì)列都是（C?。? A）順序存儲(chǔ)的線性結(jié)構(gòu) B）鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu) C）操作受限的線性結(jié)構(gòu) D）操作受限的

12、非線性結(jié)構(gòu) 3.鏈棧與順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)是（B　）。 A）插入操作更加方便 B）通常不會(huì)出現(xiàn)棧滿的情況 C）不會(huì)出現(xiàn)棧滿的情況 D）刪除操作更加方便 4.一個(gè)棧的入棧序列是a,b,c,d, 則下列序列中不可能的輸出序列是（ D ）。 A）acbd B）dcba C）acdb D）dbac 5.設(shè)有一空棧,現(xiàn)有輸入序列為1,2,3,4,5,經(jīng)過PUSH,PUSH，POP，PUSH，POP，PUSH，PUSH后，輸出序列為（C　 ）。 A）5,4,3,2,1 B）2,1 C）2,3 D）2,4 6.下面哪種數(shù)據(jù)結(jié)構(gòu)不適合作棧的存儲(chǔ)結(jié)構(gòu)（D　 ）。 A）數(shù)組 B）

13、單鏈表 C）靜態(tài)鏈表 D）二叉樹結(jié)構(gòu) 7.設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對出現(xiàn)的算法，最好采用（C　 ）結(jié)構(gòu)。 A）線性表 B）隊(duì)列 C）堆棧 D）樹 8.隊(duì)列的操作原則是( A ) 。 A）先進(jìn)先出 B）先進(jìn)后出 C）只能進(jìn)行插入 D）只能進(jìn)行刪除 9. 判斷一個(gè)循環(huán)隊(duì)列是空隊(duì)列的條件是（　A ）。 A）Q.rear == Q.front B）Q.front == 0 C）Q.rear == 0 D）(Q.rear+1)%maxsize == Q.front 10.在具有n個(gè)單元順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有?。ā ）個(gè)元素。 A）n+1 B）n-1

14、C）n D）n+2 11.若一個(gè)棧的輸入序列是1,2,3,……,n,輸出序列的第一個(gè)元素是n,則第i個(gè)輸出元素是( B )。 A) n-i B) n-i+1 C) i D) 不確定 12.判斷當(dāng)字符序列 x5y 作為字符堆棧的輸入時(shí)，輸出長度為3的且可以作為C語言標(biāo)識(shí)符的個(gè)數(shù)是（ A ）。 A) 3個(gè) B) 4個(gè) C) 5個(gè) D) 6個(gè) 13.采用不帶尾指針的單鏈表方式表示一個(gè)棧，便于結(jié)點(diǎn)的插入與刪除。棧頂結(jié)點(diǎn)的插入與刪除通常在鏈表的（　C）進(jìn)行。 A)任意位置 B)鏈表頭尾兩端 C)鏈表頭一端 D)鏈表尾一端 14.在一個(gè)鏈隊(duì)列中,若Q.front、Q.rear分別為隊(duì)首

15、、隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為（ B ）。 A) Q.front->next=s; Q.front=s; B) Q.rear->next=s; Q.rear=s; C) s->next=Q.front; Q.rear=s; D) s->next=Q.front; Q.front=s; 串和數(shù)組 1.串是一種特殊的線性表，其特殊性體現(xiàn)在( C ) 。 A)可以順序存儲(chǔ) B)可以用鏈表存儲(chǔ) C)數(shù)據(jù)元素是一個(gè)字符 D)數(shù)據(jù)元素可以是多個(gè)字符 2.串是（ D ）。 A）少于一個(gè)字母的序列 B）任意個(gè)字母的序列 C）不少于一個(gè)字符的序列 D）有限個(gè)字符的序列

16、3.串的長度是（ D ）。 A）串中不同字母的個(gè)數(shù) B）串中不同字符的個(gè)數(shù) C）串中所含字符的個(gè)數(shù)，且大于0　　 D）串中所含字符的個(gè)數(shù) 4.設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算(B ). A）連接　　 B）模式匹配 C）求子串　 D）求串長 5.若某串的長度小于一個(gè)常數(shù)，則采用( C )存儲(chǔ)方式最為節(jié)省空間。 A)鏈?zhǔn)健?B)堆結(jié)構(gòu)　 C)順序 6.串中任意多個(gè)連續(xù)字符組成的子序列稱為該串的子串(A ). A)正確 B)不正確 7.如果兩個(gè)串含有相同的字符集，則說兩者相等( B ). A)正確 B)不正確 8.存取數(shù)組中任一元素的時(shí)間都是相等的，

17、這種存取方式為（ B）存取方式。 A）順序 B）隨機(jī) C）線性 D）非線性 9.設(shè)一個(gè)一維數(shù)組第一個(gè)元素的存儲(chǔ)單元的位置是100，每個(gè)元素的長度是6，則它的第5個(gè)元素的位置是（D ）。 A）130 B）105 C）106 D）124 10.設(shè)n階方陣是一個(gè)上三角矩陣，則需要存儲(chǔ)的元素個(gè)數(shù)是（　B）。 A）n2/2 B）n(n+1)/2 C）n D）n2 11.對一些特殊矩陣采用壓縮存儲(chǔ)的目的主要是為（B ）。 A）表達(dá)變得簡單 B）減少不必要的存儲(chǔ)空間的開銷 C）去掉矩陣中的多余元素 D）對矩陣元素的存取變得簡單 二叉樹和樹 1.樹最適合用來表示（C ）。 A)有序

18、數(shù)據(jù)元素 B)無序數(shù)據(jù)元素 C)元素之間具有分支層次關(guān)系的數(shù)據(jù) D)元素之間無了解的數(shù)據(jù) 2.設(shè)深度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至多為( A )。 A)2h-1 B)2(h-1) C)2*h-1 D)2*h 3.在一棵二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最多有( C )。 A)10 B)15 C)16 D)32 4.下圖所示的二叉樹中，( C )不是完全二叉樹。 5.有100個(gè)結(jié)點(diǎn)的完全二叉樹,葉子結(jié)點(diǎn)的個(gè)數(shù)為:( B )。 A)49 B)50 C)51 D)52 6.具有100個(gè)結(jié)點(diǎn)的二叉樹中，若用二叉鏈表存儲(chǔ)，其指針域

19、部分用來指向結(jié)點(diǎn)的左、右孩子，其中（ D ）個(gè)指針域?yàn)榭铡? A）50 B）99 C）100 D）101 7.首先訪問結(jié)點(diǎn)的左子樹，然后訪問該結(jié)點(diǎn)，最后訪問結(jié)點(diǎn)的右子樹，這種遍歷稱為（C ）。 A）前序遍歷 B）后序遍歷 C）中序遍歷 D）層次遍歷 8.任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷的序列中的相對次序（ A ）。 A）不發(fā)生變化 B）發(fā)生變化 C）不能確定 D）以上都不對 9.某非空二叉樹的前序序列和后序序列正好相反，則二叉樹一定是（B ）的二叉樹。 A）空或只有一個(gè)結(jié)點(diǎn) B）高度等于其結(jié)點(diǎn)數(shù) C）任一結(jié)點(diǎn)無左孩子 D）任一結(jié)點(diǎn)無右孩子 10.如果某二叉樹的先

20、序遍歷序列是abdcef，中序遍歷序列是dbaefc，則其后序遍歷序列是（ C ）。 A）dbafec B）fecdba C）efcdba D）dbfeca 11.按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹形態(tài)有(C )種。 A）3 　　 B）4 　　　C）5 　　　D）6 12.二叉樹的后序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面（B ）。 A）正確　 B）錯(cuò)誤 13.n個(gè)結(jié)點(diǎn)深度為h的二叉樹的線索化所需的時(shí)間復(fù)雜度是(C )。 A)O(1) B)O(hn) C)O(n) D)O(nlog2h) 14.設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件是( C

21、)。 A)a是b祖先 B)a是b子孫 C)a在b左方 D)a在b右方 15.關(guān)于二叉樹的三種遍歷，下列說法正確的是( D )。 A)任意兩種遍歷序列都不可以唯一決定該二叉樹 B)任意兩種遍歷序列都可以唯一決定該二叉樹 C)先序遍歷序列和后序遍歷序列可以唯一決定該二叉樹 D)先序遍歷序列和中序遍歷序列可以唯一決定該二叉樹 16.在某棵二叉樹的一種序列中，如果發(fā)現(xiàn)其中每一結(jié)點(diǎn)的左孩子均是其前趨，則可判斷定這種序列為中序序列( B )。 A)正確 B)不正確 17.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是（ D ）。 A)acbed B)decab C)deabc D)cedba 18.前序遍歷和中序遍歷結(jié)果相同的二叉樹為（ B ）。 A)只有根結(jié)點(diǎn)的二叉樹 B)所有非葉子結(jié)點(diǎn)只有右子樹的二叉樹 C)根結(jié)點(diǎn)無右孩子的二叉樹 D)根結(jié)點(diǎn)無左孩子的二叉樹 19.前序遍歷和后序遍歷結(jié)果相同的二叉樹為（ A ）。 A)只有根結(jié)點(diǎn)的二叉樹 B)所有非葉子結(jié)點(diǎn)只有右子樹的二叉樹 C)根結(jié)點(diǎn)無右孩子的二叉樹 D)根結(jié)點(diǎn)無左孩子的二叉樹 Power by YOZOSOFT 友情提示：部分文檔來自網(wǎng)絡(luò)整理，供您參考！文檔可復(fù)制、編制，期待您的好評與關(guān)注！ 7 / 7