《經(jīng)典數(shù)據(jù)結(jié)構(gòu)習題集含答案》由會員分享，可在線閱讀，更多相關(guān)《經(jīng)典數(shù)據(jù)結(jié)構(gòu)習題集含答案（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<=i<=n）之前插入一個新元素時需向后移動（ D ）個元素。
A）1 B）n-i C）n-i-1 D）n-i+1
4.如果某線性表中最常用的操作是取第i個元素和找第i個元素的前驅(qū)，那么采用
2、（ A ）存儲方式最節(jié)省時間。
A）順序表 B）單鏈表
C）雙鏈表 D）循環(huán)鏈表
5.對順序存儲的線性表，設(shè)其長度為n，且在任何位置上插入或刪除操作都是等概率的。則插入一個元素時平均要移動表中的（A ）個元素。
A）n/2 B）(n+1)/2 C）(n-1)/2 D）n
6.下述哪一條是順序存儲結(jié)構(gòu)的缺點？（ C ）
A）存儲密度太大
B）隨機存取
C）一般要估計最大的需要空間
D）只能應(yīng)用于少數(shù)幾種邏輯結(jié)構(gòu)的存儲表示
7.在單鏈表中，增加頭結(jié)點的目的是（ C ）。
A）使單鏈表至少有一個結(jié)點
B）標志表中首結(jié)點的位置
C）方便運算的實現(xiàn)
D）說明單鏈表是線性表
3、的鏈式存儲表示
8.單鏈表不具有的特點是（ A ）。
A)可隨機訪問任一元素 B)插入和刪除不需要移動元素
C)不必事先估計存儲空間 D)所需空間和線性表長度成正比
9.循環(huán)鏈表的主要優(yōu)點是（ D）。
A）不再需要頭指針了
B）已知某個結(jié)點的位置后，能夠容易找到他的直接前趨
C）在進行插入、刪除運算時，能更好的保證鏈表不斷開
D）從表中的任意結(jié)點出發(fā)都能掃描到整個鏈表
10.鏈表對于數(shù)據(jù)元素的插入與刪除是（ B ）。
A）不需移動結(jié)點，不需改變結(jié)點指針
B）不需移動結(jié)點，只需改變結(jié)點指針
C）只需移動結(jié)點，不需改變結(jié)點指針
D）既需移動結(jié)點，又需改變結(jié)點指針
11
4、.在一個單鏈表中,已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點,若要在q 和p所指結(jié)點之間插入s所指的結(jié)點,則執(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.向一個有115個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（ C ）個元素。
A) 115 B) 114 C) 58 D) 57
13.帶頭結(jié)點的單鏈表Head為空表的判定條件是 ( B ) 。
5、
A) Head->next==Head B) Head->next==NULL
C) Head!=NULL D) Head==NULL
14.若要求能快速地實現(xiàn)在鏈表的末尾插入結(jié)點和刪除第一個結(jié)點的運算，則選擇( B )最合適。
A) 單鏈表 B) 帶尾指針的單循環(huán)鏈表
C) 雙鏈表 D) 雙循環(huán)鏈表
15.給定有n個元素的向量，建立一個有序單鏈表的時間復雜度是( D )。
A)O(n) B)O(log2n) C)O(nlog2n) D. O(n2)
16.線性表采用鏈式存儲時，其位置( C)。
A)必須是連續(xù)的 B)必須是不連續(xù)的
C)連續(xù)與否均可 D)部分位置必須是連續(xù)
6、的
17.在一個具有n個結(jié)點的有序單鏈表中，插入一個新的結(jié)點并使之仍然有序的時間復雜度是(A )。
A)O(n) B)O(log2n) C)O(1) D)O(n2)
排序
1.在下列排序算法中，時間復雜度不受數(shù)據(jù)初始特性影響，恒為O(n2)的是（C ）。
A）插入排序 B）冒泡排序 C）選擇排序 D）堆排序
2.在各種排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為（ C）。
A）希爾排序 B）冒泡排序 C）插入排序 D）選擇排序
3.快速排序方法在（C ）情況下最不利于發(fā)揮其長處。
A）要排序的數(shù)
7、據(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，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、序的方法，以第一個記錄為基準元素得到的一次劃分結(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)進行排序時,元素序列的變化情況如下:
(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ù)組進行穩(wěn)定的排序，則應(yīng)選(C )。
A)快速排序 B)堆排序 C)歸并排序 D)基數(shù)排序
11.下列排序算法的時間復雜度最小的是（D ）。
A)冒泡排序 B)希爾排序
C)簡單選擇排序 D)歸并排序
12.設(shè)有1000個無序的元素,希望用最快的速度挑選出其中前10個最大的元素,最好（ C）排序法。
A)起泡排序 B)快速排序 C)堆排序 D)基數(shù)排序
13.插入排序算法在每一趟都能選取出一個元素放在其最終的位置上。( B
11、 )
A)正確 B)不正確
14.直接插入排序是不穩(wěn)定的排序方法。( B )
A)正確 B)不正確
15.直接插入排序的最壞情況是初始序列為（ B ）序。
A)正 B)反 C)正和反 D)無
16.在各排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為(D )。
A)希爾排序 B)歸并排序 C)插入排序 D)選擇排序
棧和隊列
1.棧的特點是( B )。
A）先進先出 B）后進先出
C）進優(yōu)于出 D）出優(yōu)于進
2.棧和隊列都是（C ）。
A）順序存儲的線性結(jié)構(gòu) B）鏈式存儲的線性結(jié)構(gòu)
C）操作受限的線性結(jié)構(gòu) D）操作受限的
12、非線性結(jié)構(gòu)
3.鏈棧與順序棧相比，有一個比較明顯的優(yōu)點是（B ）。
A）插入操作更加方便 B）通常不會出現(xiàn)棧滿的情況
C）不會出現(xiàn)棧滿的情況 D）刪除操作更加方便
4.一個棧的入棧序列是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)不適合作棧的存儲結(jié)構(gòu)（D ）。
A）數(shù)組 B）
13、單鏈表 C）靜態(tài)鏈表 D）二叉樹結(jié)構(gòu)
7.設(shè)計一個判別表達式中左右括號是否配對出現(xiàn)的算法，最好采用（C ）結(jié)構(gòu)。
A）線性表 B）隊列 C）堆棧 D）樹
8.隊列的操作原則是( A ) 。
A）先進先出 B）先進后出
C）只能進行插入 D）只能進行刪除
9. 判斷一個循環(huán)隊列是空隊列的條件是（ A ）。
A）Q.rear == Q.front
B）Q.front == 0
C）Q.rear == 0
D）(Q.rear+1)%maxsize == Q.front
10.在具有n個單元順序存儲的循環(huán)隊列中，隊滿時共有 （ B ）個元素。
A）n+1 B）n-1
14、C）n D）n+2
11.若一個棧的輸入序列是1,2,3,……,n,輸出序列的第一個元素是n,則第i個輸出元素是( B )。
A) n-i B) n-i+1 C) i D) 不確定
12.判斷當字符序列 x5y 作為字符堆棧的輸入時，輸出長度為3的且可以作為C語言標識符的個數(shù)是（ A ）。
A) 3個 B) 4個 C) 5個 D) 6個
13.采用不帶尾指針的單鏈表方式表示一個棧，便于結(jié)點的插入與刪除。棧頂結(jié)點的插入與刪除通常在鏈表的（ C）進行。
A)任意位置 B)鏈表頭尾兩端
C)鏈表頭一端 D)鏈表尾一端
14.在一個鏈隊列中,若Q.front、Q.rear分別為隊首
15、、隊尾指針，則插入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.front=s;
串和數(shù)組
1.串是一種特殊的線性表，其特殊性體現(xiàn)在( C ) 。
A)可以順序存儲 B)可以用鏈表存儲
C)數(shù)據(jù)元素是一個字符 D)數(shù)據(jù)元素可以是多個字符
2.串是（ D ）。
A）少于一個字母的序列 B）任意個字母的序列
C）不少于一個字符的序列 D）有限個字符的序列
16、3.串的長度是（ D ）。
A）串中不同字母的個數(shù)
B）串中不同字符的個數(shù)
C）串中所含字符的個數(shù)，且大于0
D）串中所含字符的個數(shù)
4.設(shè)有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算(B ).
A）連接 B）模式匹配
C）求子串 D）求串長
5.若某串的長度小于一個常數(shù)，則采用( C )存儲方式最為節(jié)省空間。
A)鏈式 B)堆結(jié)構(gòu) C)順序
6.串中任意多個連續(xù)字符組成的子序列稱為該串的子串(A ).
A)正確 B)不正確
7.如果兩個串含有相同的字符集，則說兩者相等( B ).
A)正確 B)不正確
8.存取數(shù)組中任一元素的時間都是相等的，
17、這種存取方式為（ B）存取方式。
A）順序 B）隨機 C）線性 D）非線性
9.設(shè)一個一維數(shù)組第一個元素的存儲單元的位置是100，每個元素的長度是6，則它的第5個元素的位置是（D ）。
A）130 B）105 C）106 D）124
10.設(shè)n階方陣是一個上三角矩陣，則需要存儲的元素個數(shù)是（ B）。
A）n2/2 B）n(n+1)/2 C）n D）n2
11.對一些特殊矩陣采用壓縮存儲的目的主要是為（B ）。
A）表達變得簡單 B）減少不必要的存儲空間的開銷
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é)點，則此類二叉樹中所包含的結(jié)點數(shù)至多為( A )。
A)2h-1 B)2(h-1) C)2*h-1 D)2*h
3.在一棵二叉樹中，第5層上的結(jié)點數(shù)最多有( C )。
A)10 B)15 C)16 D)32
4.下圖所示的二叉樹中，( C )不是完全二叉樹。
5.有100個結(jié)點的完全二叉樹,葉子結(jié)點的個數(shù)為:( B )。
A)49 B)50 C)51 D)52
6.具有100個結(jié)點的二叉樹中，若用二叉鏈表存儲，其指針域
19、部分用來指向結(jié)點的左、右孩子，其中（ D ）個指針域為空。
A）50 B）99 C）100 D）101
7.首先訪問結(jié)點的左子樹，然后訪問該結(jié)點，最后訪問結(jié)點的右子樹，這種遍歷稱為（C ）。
A）前序遍歷 B）后序遍歷 C）中序遍歷 D）層次遍歷
8.任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷的序列中的相對次序（ A ）。
A）不發(fā)生變化 B）發(fā)生變化
C）不能確定 D）以上都不對
9.某非空二叉樹的前序序列和后序序列正好相反，則二叉樹一定是（B ）的二叉樹。
A）空或只有一個結(jié)點 B）高度等于其結(jié)點數(shù)
C）任一結(jié)點無左孩子 D）任一結(jié)點無右孩子
10.如果某二叉樹的先
20、序遍歷序列是abdcef，中序遍歷序列是dbaefc，則其后序遍歷序列是（ C ）。
A）dbafec B）fecdba C）efcdba D）dbfeca
11.按照二叉樹的定義，具有3個結(jié)點的二叉樹形態(tài)有(C )種。
A）3 B）4 C）5 D）6
12.二叉樹的后序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的前面（B ）。
A）正確 B）錯誤
13.n個結(jié)點深度為h的二叉樹的線索化所需的時間復雜度是(C )。
A)O(1) B)O(hn) C)O(n) D)O(nlog2h)
14.設(shè)a,b為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，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é)點的左孩子均是其前趨，則可判斷定這種序列為中序序列( B )。
A)正確 B)不正確
17.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是（ D ）。
A)acbed B)decab C)deabc D)cedba
18.前序遍歷和中序遍歷結(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ò)整理，供您參考！文檔可復制、編制，期待您的好評與關(guān)注！
7 / 7
經(jīng)典數(shù)據(jù)結(jié)構(gòu)習題集含答案
