經(jīng)典數(shù)據(jù)結(jié)構(gòu)習(xí)題集含答案

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

1、線性表1.下列有關(guān)線性表的敘述中，正確的是（ A ）。A）線性表中元素之間的關(guān)系是線性關(guān)系B）線性表中至少有一個元素C）線性表中的任一元素有且僅有一個直接前趨D）線性表中的任一元素有且僅有一個直接后繼2.下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？（A ）A）存儲密度大 B）插入方便C）刪除方便 D）可方便地用于各種邏輯結(jié)構(gòu)的存儲表示3.在一個長度為n的順序表中，在第i個元素（1=inext = 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.向一個有

2、115個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（ C ）個元素。A) 115 B) 114 C) 58 D) 57 13.帶頭結(jié)點的單鏈表Head為空表的判定條件是 ( B ) 。A) Head-next=Head B) Head-next=NULLC) Head!=NULL D) Head=NULL14.若要求能快速地實現(xiàn)在鏈表的末尾插入結(jié)點和刪除第一個結(jié)點的運算，則選擇( B )最合適。A) 單鏈表 B) 帶尾指針的單循環(huán)鏈表C) 雙鏈表 D) 雙循環(huán)鏈表15.給定有n個元素的向量，建立一個有序單鏈表的時間復(fù)雜度是( D )。A)O(n) B)O(log2n) C)O(

3、nlog2n) D. O(n2)16.線性表采用鏈?zhǔn)酱鎯r，其位置( C)。A)必須是連續(xù)的 B)必須是不連續(xù)的C)連續(xù)與否均可 D)部分位置必須是連續(xù)的17.在一個具有n個結(jié)點的有序單鏈表中，插入一個新的結(jié)點并使之仍然有序的時間復(fù)雜度是(A )。A)O(n) B)O(log2n) C)O(1) D)O(n2) 排序1.在下列排序算法中，時間復(fù)雜度不受數(shù)據(jù)初始特性影響，恒為O(n2)的是（C ）。A）插入排序 B）冒泡排序 C）選擇排序 D）堆排序2.在各種排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為（ C）。A）

4、希爾排序 B）冒泡排序 C）插入排序 D）選擇排序3.快速排序方法在（C）情況下最不利于發(fā)揮其長處。A）要排序的數(shù)據(jù)量太大 B）要排序的數(shù)據(jù)含有多個相同值C）要排序的數(shù)據(jù)已基本有序 D）要排序的數(shù)據(jù)個數(shù)為奇數(shù)4.已知10個數(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，95B）28，16，34，54，62，73，60，26，43，95C）28，16，34，54，62，60，73，26，43，95D）16，28，34，54，62，60，73，26，43，9

5、55.一組記錄的關(guān)鍵字為（46,79,56,38,40,84）,則利用快速排序的方法，以第一個記錄為基準(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)行排序時,元素序列的變化情況如下:(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則所采

6、用的排序方法是（D ）。A）選擇排序 B）希爾排序 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,56B）3,29,8,56,35,11,20,74C）3,8,11,20,29,35,56,74D）20,29,3,8,11,35,74,569.下列關(guān)鍵碼序列中，屬于堆的是（A）。A)（15，30，22，93，52，71） B)（15，7

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

8、排序方法。( B )A)正確 B)不正確15.直接插入排序的最壞情況是初始序列為（ B ）序。A)正 B)反 C)正和反 D)無16.在各排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為(D )。A)希爾排序 B)歸并排序 C)插入排序 D)選擇排序棧和隊列1.棧的特點是( B )。A）先進(jìn)先出 B）后進(jìn)先出C）進(jìn)優(yōu)于出 D）出優(yōu)于進(jìn)2.棧和隊列都是（C）。 A）順序存儲的線性結(jié)構(gòu) B）鏈?zhǔn)酱鎯Φ木€性結(jié)構(gòu)C）操作受限的線性結(jié)構(gòu) D）操作受限的非線性結(jié)構(gòu)3.鏈棧與順序棧相比，有一個比較明顯的優(yōu)點是（B）。A）插入操作更加方便 B）通常不會出現(xiàn)棧滿的情況

9、C）不會出現(xiàn)棧滿的情況 D）刪除操作更加方便4.一個棧的入棧序列是a,b,c,d, 則下列序列中不可能的輸出序列是（ D ）。A）acbd B）dcbaC）acdb D）dbac5.設(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)不適合作棧的存儲結(jié)構(gòu)（D ）。A）數(shù)組 B）單鏈表 C）靜態(tài)鏈表 D）二叉樹結(jié)構(gòu)7.設(shè)計一個判別表達(dá)式中左右括號是否配對出現(xiàn)的算法，最好采用（C ）結(jié)構(gòu)。A）線性表 B）隊列 C）堆棧 D）樹8.隊列

10、的操作原則是( A ) 。A）先進(jìn)先出 B）先進(jìn)后出C）只能進(jìn)行插入 D）只能進(jìn)行刪除 9. 判斷一個循環(huán)隊列是空隊列的條件是（A ）。 A）Q.rear = Q.front B）Q.front = 0C）Q.rear = 0 D）(Q.rear+1)%maxsize = Q.front10.在具有n個單元順序存儲的循環(huán)隊列中，隊滿時共有（B ）個元素。A）n+1 B）n-1 C）n D）n+211.若一個棧的輸入序列是1,2,3,n,輸出序列的第一個元素是n,則第i個輸出元素是( B )。A) n-i B) n-i+1 C) i D) 不確定 12.判斷當(dāng)字符序列 x5y 作為字符堆棧的輸入

11、時，輸出長度為3的且可以作為C語言標(biāo)識符的個數(shù)是（ A ）。A) 3個 B) 4個 C) 5個 D) 6個 13.采用不帶尾指針的單鏈表方式表示一個棧，便于結(jié)點的插入與刪除。棧頂結(jié)點的插入與刪除通常在鏈表的（C）進(jìn)行。A)任意位置 B)鏈表頭尾兩端C)鏈表頭一端 D)鏈表尾一端14.在一個鏈隊列中,若Q.front、Q.rear分別為隊首、隊尾指針，則插入s所指結(jié)點的操作為（ 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.

12、front=s;串和數(shù)組1.串是一種特殊的線性表，其特殊性體現(xiàn)在( C ) 。 A)可以順序存儲 B)可以用鏈表存儲 C)數(shù)據(jù)元素是一個字符 D)數(shù)據(jù)元素可以是多個字符2.串是（ D ）。 A）少于一個字母的序列 B）任意個字母的序列C）不少于一個字符的序列 D）有限個字符的序列3.串的長度是（ D ）。A）串中不同字母的個數(shù) B）串中不同字符的個數(shù)C）串中所含字符的個數(shù)，且大于0D）串中所含字符的個數(shù)4.設(shè)有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算(B ). A）連接 B）模式匹配C）求子串 D）求串長5.若某串的長度小于一個常數(shù)，則采用( C )存儲方式最為節(jié)省空間。A)鏈?zhǔn)?B)堆結(jié)

13、構(gòu) C)順序6.串中任意多個連續(xù)字符組成的子序列稱為該串的子串(A ).A)正確 B)不正確7.如果兩個串含有相同的字符集，則說兩者相等( B ). A)正確 B)不正確8.存取數(shù)組中任一元素的時間都是相等的，這種存取方式為（ B）存取方式。A）順序 B）隨機(jī) C）線性 D）非線性 9.設(shè)一個一維數(shù)組第一個元素的存儲單元的位置是100，每個元素的長度是6，則它的第5個元素的位置是（D ）。A）130 B）105 C）106 D）12410.設(shè)n階方陣是一個上三角矩陣，則需要存儲的元素個數(shù)是（B）。A）n2/2 B）n(n+1)/2 C）n D）n211.對一些特殊矩陣采用壓縮存儲的目的主要是為

14、（B ）。A）表達(dá)變得簡單 B）減少不必要的存儲空間的開銷C）去掉矩陣中的多余元素 D）對矩陣元素的存取變得簡單 二叉樹和樹1.樹最適合用來表示（C ）。 A)有序數(shù)據(jù)元素 B)無序數(shù)據(jù)元素C)元素之間具有分支層次關(guān)系的數(shù)據(jù)D)元素之間無了解的數(shù)據(jù)2.設(shè)深度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至多為( A )。A)2h-1 B)2(h-1) C)2*h-1 D)2*h3.在一棵二叉樹中，第5層上的結(jié)點數(shù)最多有( C )。A)10 B)15 C)16 D)32 4.下圖所示的二叉樹中，( C )不是完全二叉樹。5.有100個結(jié)點的完全二叉樹,葉子結(jié)點的個數(shù)為:(

15、B )。A)49 B)50 C)51 D)526.具有100個結(jié)點的二叉樹中，若用二叉鏈表存儲，其指針域部分用來指向結(jié)點的左、右孩子，其中（ D ）個指針域為空。A）50 B）99 C）100 D）1017.首先訪問結(jié)點的左子樹，然后訪問該結(jié)點，最后訪問結(jié)點的右子樹，這種遍歷稱為（C ）。 A）前序遍歷 B）后序遍歷 C）中序遍歷 D）層次遍歷8.任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷的序列中的相對次序（ A ）。A）不發(fā)生變化 B）發(fā)生變化C）不能確定 D）以上都不對9.某非空二叉樹的前序序列和后序序列正好相反，則二叉樹一定是（B ）的二叉樹。A）空或只有一個結(jié)點 B）高度等于其結(jié)點數(shù)

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

17、件是( C )。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é)點的左孩子均是其前趨，則可判斷定這種序列為中序序列( B )。A)正確 B)不正確17.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是（ D ）。A)acbed B)decab C)deabc D)cedba18.前序遍歷和中序遍歷結(jié)果相同的二叉樹為（ B ）。A)只有根結(jié)點的二叉樹 B)所有非葉子結(jié)點只有右子樹的二叉樹C)根結(jié)點無右孩子的二叉樹D)根結(jié)點無左孩子的二叉樹 19.前序遍歷和后序遍歷結(jié)果相同的二叉樹為（ A ）。A)只有根結(jié)點的二叉樹B)所有非葉子結(jié)點只有右子樹的二叉樹C)根結(jié)點無右孩子的二叉樹D)根結(jié)點無左孩子的二叉樹Power by YOZOSOFT友情提示：部分文檔來自網(wǎng)絡(luò)整理，供您參考！文檔可復(fù)制、編制，期待您的好評與關(guān)注！7 / 7