數據結構題庫

1、1. 一個非空廣義表的表頭 _。A. 不可能是子表B. 只能是子表C. 只能是原子D. 可以是子表或原子2. 在以下的敘述中，正確的是 _。 A. 二維數組可以看做它的每個數據元素為一個線性表的線性表B. 棧的操作方式是先進先出C. 線性表的線性存儲結構優(yōu)于鏈表存儲結構D. 隊列的操作方式是先進后出3. 如下陳述中正確的是 _。A. 串是一種特殊的線性表B. 串的長度必須大于零C. 串中元素只能是字母D. 空串就是空白串4. 如下陳述中正確的是 _。A. 串是一種特殊的線性表B. 串的長度必須大于零C. 串中元素只能是字母D. 兩個串 s1 和 s2 若長度相同， 則這兩個串相等5. 數組 A

2、 中, 每個元素的長度為 3 字節(jié) , 行下標從 1 到 8, 列下標從 1 到 10, 從首地址 SA 開始連續(xù)存放在存儲器中 , 按行存放時 , 元素 a85 地址為 。A.SA+141B.SA+180C.SA+222D.SA+2256. 任何一個非空列表其表頭可能是原子，也可能是列表，而其表尾是。A. 原子B. 列表C. 任何元素D.空7.稀疏矩陣一般的壓縮存儲方法有兩種。A. 二維數組和三維數組B. 三元組和散列C. 三元組和十字鏈表D. 散列和十字鏈表8. 常對數組進行的兩種基本操作是。A. 建立和刪除B.插入和修改C. 查找和修改D. 查找和索引9. 假定利用數組 aN 順序存儲一

3、個棧，用top 表示棧頂指針，top = = 0表示?？?，并已知棧未滿， 當元素 x 進棧時所執(zhí)行的操作為 _。A.a-top= x;B.atop-= x;C.a+top = x;D.atop+ =x;10. 由兩個棧共享一個向量空間的好處是_。A. 減少存取時間, 降低下溢發(fā)生的機率B. 節(jié)省存儲空間, 降低上溢發(fā)生的機率C. 減少存取時間, 降低上溢發(fā)生的機率D. 節(jié)省存儲空間, 降低下溢發(fā)生的機率11. 入棧次序是 a,b,c,d,e ，則出棧次序不可能是 _A.e,d,c,b,aB.d,e,c,b,aC.d,c,e,a,bD.a,b,c,d,e12. 假定利用數組 aN 循環(huán)順序存儲一

4、個隊列，用 front( 指向隊首元素 ) 和 rear( 指向隊尾元素的下一位置 ) 分別表示隊首和隊尾指針， 并已知隊列未空，當出隊并返回隊首元素時所執(zhí)行的操作為 _。1A.returna+rear%N;B.returna-rear%N;C.return a+front%N;D.return afront+%N;13. 當利用大小為 N的一維數組存儲一個循環(huán)隊列時，則該隊列的最大長度為 _。A.N-2B.N-1C.ND. N+114. 假定一個長度為 n的循環(huán)順序隊列的隊首和隊尾指針分別為f 和 r ，則判斷隊滿的條件是 _。A.(f+1)%n=rB.(r+1)%n=fC.f=0D.f=r

5、15. 假定一個鏈隊列的隊首和隊尾指針分別為 front 和 rear ，則判斷隊空的條件是_。A.front=rearB.front!=NULLC.rear!=NULLD.front=NULL16. 隊和棧的主要區(qū)別是 _。A. 邏輯結構不同B. 存儲結構不同C. 所包含的運算個數不同D. 限定插入和刪除的位置不同17. 假定一個順序隊列的隊首和隊尾指針分別為 front 和 rear ，則判斷隊空的條件是_。A.front+1=rearB.rear+1=frontC.front= =0D.front=rear18. 鏈式棧與順序棧相比， 一個比較明顯的優(yōu)點是 _。A. 插入操作更加方便B.

6、 通常不會出現棧滿的情況C. 不會出現?？盏那闆rD. 刪除操作更加方便19. 判定一個棧 ST（最多元素為 m0）為空的條件是 _A.ST-top0B.ST-top=0C.ST-topm0D.ST-top=m020. 下面算法的時間復雜度為_ 。 int f( unsigned int n ) if ( n=0 | n=1 ) return 1; else return n*f(n-1); A.O(1)B.O(n)C.O(n2)D.O(n!)21. 在長度為 n 的順序存儲的線性表中， 刪除第 i 個元素（ 1 i n）時，需要從前向后依次前移 ( ) 個元素。A.n-IB.n-i+1C.n-

7、i-1D. i22. 線性表若采用鏈式存儲結構時， 要求內存中可用存儲單元的地址 _。A. 必須是連續(xù)的B. 部分地址必須是連續(xù)的C. 一定是不連續(xù)的D. 連續(xù)，不連續(xù)都可以23. 計算機識別、 存儲和加工處理的對象被統(tǒng)稱為 ()A. 數據B. 數據元素C. 數2據結構D. 數據類型24. 算法指的是 。A. 計算機程序B. 解決問題的計算方法C. 排序算法D. 解決問題的有限運算序列25. 在對 n 個元素進行快速排序的過程中，第一趟排序最多需要交換 _對元素。A.n/2B.n-1C.nD.n+126.若對 n 個元素進行直接插入排序，在進行 i 趟 (2 i n) 排序時，為尋找插入位置最

8、多需要進行 _次元素的比較。A.i+1B.i-1C.iD.127. 對于哈希函數 H(key)=key%13 ，被稱為同義詞（即沖突）的關鍵字是 _A.35 和 41B.23 和 39C.15 和 44D.25 和 5128. 若一組記錄的排序碼為 （ 46, 79, 56, 38, 40, 84 ），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為_A.38,40,46,56,79,84B.40,38,46,79,56,84C.40,38，46,56,79,84D.40,38,46,84,56,7929. 在對 n 個元素進行簡單選擇排序的過程中，需要進行 _趟選擇。A.n/2B

9、.n-1C.nD.n+130. 用某種排序方法對關鍵字序列 （23，72，21，47，15，27，59，35，20）進行排序時，前三趟的結果情況如下 _： 23 ，21，47， 15， 27， 59， 35， 20， 72 21， 23， 15，27， 47， 35， 20， 59， 72 21， 15， 23， 27，35， 20， 47， 59， 72 則所采用的排序方法是 _A. 選擇排序B. 起泡排序C.歸并排序D. 快速排序31. 設哈希表長為 14，哈希函數 f（ k）=k 11，已知表中已有4 個元素， 關鍵字分別為15，38， 61，84，存儲位置分別為4，5，6，7，其它存儲

10、位置為空，如用二次探測再散列處理沖突，關鍵字為49 的存儲位置是_。A.8B.3C.5D.932.對于順序存儲的有序表(5,12, 20, 26,37, 42, 46, 50, 64)，哨兵位在前，為查找元素26 ，若采用順序查找，需要比較_次才能查找成功。A.3B.4C.5D.633. 具有 e 條邊的無向圖， 它的鄰接表中有_個邊結點。A.e-1B.eC.2(e-1)D.2e34. 具有 e 條邊的有向圖， 它的逆鄰接表中有 _個弧結點。A.e-1B.eC.2(e-1)D.2e35.由權值分別為3, 8, 6, 2, 5的葉子結點生成一顆哈夫曼樹，它的帶權路徑長度為_。A.24B.48C.

11、723D.5336. 如果某圖的鄰接矩陣是對角線元素以下元素均為零的上三角矩陣，則此圖是_。A. 有向完全圖B. 連通圖C.強連通圖D. 有向無環(huán)圖37. 下面關于圖的存儲的敘述中， 哪一個是正確的。A. 用鄰接矩陣法存儲圖 , 占用的存儲空間數只與圖中結點個數有關 , 而與邊數無關B. 用鄰接矩陣法存儲圖 , 占用的存儲空間數只與圖中邊數有關 , 而與結點個數無關C. 用鄰接表法存儲圖， 占用的存儲空間數只與圖中結點個數有關，而與邊數無關D. 用鄰接表法存儲圖， 占用的存儲空間數只與圖中邊數有關，而與結點個數無關38. 圖的深度優(yōu)先遍歷類似于樹的_。A.先序遍歷B.中序遍歷C. 后序遍歷D.

12、 層次遍歷39. 一個連通圖的生成樹是包含圖中所有頂點的一個 _ 子圖。A. 極小B. 連通C. 極小連通D. 無環(huán)40. 有向圖的一個頂點的度為該頂點的_。A. 入度B. 出度C. 入度與出度之和D.( 入度出度 )/241. 在一個有向圖中， 所有頂點的度數之和等于所有弧數的 _倍。A.3B.2C.1D.1/242. n 個頂點的連通圖至少有 _條邊。A.n-1B.nC.n+1D.043. 頂點個數為 n 的無向圖最多有 _條邊。A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)44. 樹中所有結點的度數之和等于結點總數加 _。A.0B.1C.-1D.245. 在一棵樹中，

13、 每個結點最多有 _個直接前驅結點。A.0B.1C.2D. 任意多個46. 將一棵有 40 個結點的完全二叉樹從上到下，從左到右依次對結點進行編號， 根結點的編號為 1，則編號為 15 的結點的左孩子的編號為 _。A.30B.31C.16D.3247. 一 棵 樹 的 廣 義 表 表 示 為 a(b(c),d(e(g(h),f)，則該樹的度為2 的結點數為 _。A.2B.3C.4D.548. 一 棵 樹 的 廣 義 表 表 示 為 a(b(c),d(e(g(h), f)，則該樹的度為 _。A.2B.3C.4D.549. 一 棵 樹 的 廣 義 表 表 示 為 a(b(c),d(e(g(h),

14、f)，則該樹的高度為_。A.2B.3C.4D.550. 在一棵深度為 h 的完全二叉樹中， 所含結點個數不少于 _ 。A. 2hB. 2h+1C. 2h-14D. 2h-151. 在一棵二叉樹的第5 層上，最多具有_個結點。A.14B.16C.31D.3252. 在一棵具有 n 個結點的二叉樹中， 所有結點的空子樹個數等于 _。A.nB.n-1C.n+1D.2*n53.數據結構通常是研究數據的及它們之間的聯系。A. 存儲和邏輯結構B. 存儲和抽象C. 理想和抽象D. 理想與邏輯在含 100 個結點的完全二叉樹， 葉子結點的個數為 _50_ 。2. 一棵含有 16 個結點的完全二叉樹， 對他按層

15、編號，對于編號為 7 的結點， 他的雙親結編號點為_3_左孩子編號為_14_、右孩子編號為_15_。3. 對任何一棵二叉樹，若 n0，n1，n2 分別是度為 0，1，2 的結點的個數，則n0=_n2+1_。4. 高度為 k 的二叉樹具有的結點數目，最少為 _k_, 最多為 _2k-1_ 。5. 對于一顆具有 n 個結點的二叉樹，對應二叉鏈表中指針域有 _n-1_ 個用于指向子結點。6. 樹的雙親表示法便于實現涉及到_雙親_的操作，孩子表示法便于實現涉及到孩子的操作。7.在一棵二叉樹中，度為 2 的結點有5 個，度為 1 的結點有6 個，那么葉子結點有_6_ 個8. 假定一棵樹的廣義表表示為A(

16、B(C, D(E,F,G), H(I, J)，則結點 H 的雙親結點為_B_。9. 假定一棵二叉樹的結點個數為32，則它的最小深度為 _6_。10. 已知廣義表ls=(a,(b,c,d),e),運用head 和 tail函數取出 ls 中的原子 b 的運算是 _head(head(tail(ls)_。11.廣義表 （ A,(a,b),d,e,(i,j),k)）, 則廣義表的長度為_5_，深度為 _3_，表頭為_A_，表尾為_（ (a,b),d,e,(i,j),k)） _ 。12.稀疏矩陣可用三元組進行壓縮存儲，存儲時需存儲非零元的_元素值 _和行、列數。13. 在串的鏈式存儲方式中， 結點越大

17、， 運算處理越 _不方便），存儲占用量越 _?。?4. 一個串的任意個連續(xù)的字符組成的子序列稱為該串的 _子串 _，包含該子序列的串稱為 _主串 _，該子序列在串中的位置用 _子串的第一個字符在主串中的位置_ 來表示。15. 廣義表（ a）的表頭是（ a） , 表尾是（） 。16. 廣義表（ a）,a ）的表頭是（ a），表尾是（ a) 。17. 數組 A 中，每個元素的長度為 3 個字節(jié)，行下標從 1 到 8 ，列下標從 1 到 10 ，從首地址開始連續(xù)存放在存儲器內， 存放該數組至少需要的單元數是 240 。18. 棧的特點是_后進先出_ 。19. 對于順序存儲的隊列， 存儲空間大小為n，

18、頭指針為F，尾指針為R。若在邏輯上看一個環(huán)，則隊列中元素的個數為_(R-F+n)%n_ 。20. 隊列又稱為 _先進先出 _的線性表。21. 棧結構允許進行刪除操作的一端為_棧頂 _。22. 已知循環(huán)隊列的存儲空間為數組a21 ，且頭指針（指向隊頭元素）和尾指5針（隊尾元素的下一位置）分別為8和3，46,79,56,38,40,84，則以第一個記錄為則該隊列的當前長度為 _16_ 。樞軸，對其進行第一趟快速排序的結果為23.在初始為空的隊列中插入元素A,B,C,D_40,38,46,56,79,84_。以后，緊接著做了兩次刪除操作，此時的隊36.假定一組數據的關鍵字為尾元素是 _D_。46,7

19、9,56,38,40,84，則利用堆排序方法24.在非空線性表中除第一個元素外，集合建立的初始小頂堆為 _38 ，40，56，79，46，中每個數據元素只有一個_直接前驅84_ 。_；除最后一個元素之外， 集合中每37.每次直接或通過 “樞軸” 元素間接比較個數據元素均只有一個_直接后繼兩個元素， 若出現逆序排列時就交換它們的_。位置，此種排序方法叫做_交換 _排序。25.在雙向鏈表中， 每個結點含有兩個指針38.每次從無序表中取出一個元素， 把它插域，一個指向 _直接前驅 _結點， 另一入到有序表中的適當位置，此種排序方法叫個指向 _直接后繼 _結點。做 _插入 _排序。26.在單鏈表設置表

20、頭結點的作用是插入39.每次從無序表中挑選出一個最大或最和刪除表中第一個元素時不必對_頭指針小元素， 把它交換到有序表的一端，此種排_進行特殊處理。序方法叫做 _選擇 _排序。27.在一個單鏈表 L 中，若要在指針 q 所指40.每次使兩個相鄰的有序表合并成一個結點的后面插入一個由指針p所指向的結有序表的排序方法叫做_2 路歸并排序 _點，則應進行的操作序列為：排序。_p-next=q-next_;q41.先將整個待排序列分割成若干子序列一next=p 。分別進行直接插入排序，待整個序列 “基本28.順序表中邏輯上相鄰的元素的物理位有序”時，再對全體進行一次直接插入排序，置_相鄰 _，單鏈表中

21、邏輯上相鄰的元此種排序方法叫做 _希爾 _排序。素的物理位置 _不一定相鄰 _。42.將一個數據元素 （或記錄）的任意序列，29.在以 L 為頭指針的帶頭結點的單鏈表和重新排列成一個按關鍵字有序的序列叫_排單循環(huán)鏈表中， 判斷鏈表是否為空的條件分序 _。別為_L-next=NULL_和43.元素關鍵字轉換為該元素存儲位置的_L-next=L_ 。函數 f 稱為 _哈希函數 _。30.已知一順序存儲的線性表，每個元素占44.數據的邏輯結構包括集合、_線性結構用 k個存儲單元，若第一個元素的地址為_、樹形結構和圖狀結構四種類型。Loc1，則第 i個元素的地址為 _Loc1+（ i-1 ）45.已知

22、有實現同一功能的兩個算法，其時*k_ 。間復雜度分別為 O(log2n)和 O(n) ，哪個算31.若經常需要對線性表進行插入與刪除法的效率更高？ _O(log2n) _操作，該線性表最好采用_鏈式 _ 存儲46.假設在有序線性表a20上進行折半查結構。找，則比較一次查找成功的結點數為1；比32.若經常需要對線性表進行查找操作，則較兩次查找成功的結點數為2；比較四次查最好采用 _順序 _存儲結構。找成功的結點數為 8；平均查找長度為3.733. 若 待 散 列 的 序 列 為47. 在數據的存放無規(guī)律而言的線性表中(18,25,63,50,42,32,9)，散列函數為進行檢索的最佳方法是順序查

23、找H(key)=key%9 ，與 18發(fā)生沖突的元素有48. 元素關鍵字轉換為該元素存儲位置的_63,9_ 。函數 f 稱為 _哈希函數34. _循環(huán)鏈表 _鏈表從任何一個結點49. 若要對某二叉排序樹進行遍歷，保證輸出發(fā)，都能訪問到所有結點。出元素的值序列按增序排列，應對該二叉排35. 假定一組數據的關鍵字為序樹采用 _中序 _遍歷法。650. 通常用時間復雜度和_ 空間復雜度_ 兩種方法衡量算法的效率。51. 在一個無向圖中， 所有頂點的度數之和等于所有邊數的_2_倍。52. 在無向圖中， 若從頂點 A 到頂點 B 存在_路徑 _，則稱 A 與 B 之間是連通的。53. 有一個 n 個頂點

24、的有向完全圖的弧數_n(n-1)_。54. 對于一個具有 n 個頂點的圖， 若采用鄰接矩陣表示，則矩陣大小為 _n2_。55. 已知一棵樹的前序序列為 ABCDEF，后序序列為 CEDFBA，則對該樹進行層次遍歷得到的序列為 _ABCDFE。56.若一棵完全二叉樹含有121 個結點， 則該樹的深度為 _7_ 。57. 度數為 0 的結點，即沒有子樹的結點叫作葉子結點。 同一個結點的兒子結點之間互稱為兄弟結點1. 任何一棵二叉樹都有 n0=n2+1 的關系式。( )2. 插入與刪除操作是數據結構中最基本的兩種操作， 因此這兩種操作在數組中也經常被使用。（）3. 在完全二叉樹中 , 若某結點無左孩

25、子 , 則它必是葉結點。 （）4. 用樹的前序遍歷和中序遍歷可以導出樹的后序遍歷。（）5. 已知一棵二叉樹的前序序列和后序序列可以唯一地構造出該二叉樹。 （）6. 將一棵樹轉換成二叉樹后，根結點沒有左子樹。（）7. 設與一棵樹 T 所對應的二叉樹為 BT，則與 T 中的葉子結點所對應的 BT 中的結點也一定是葉子結點。 （）8. 滿二叉樹也是完全二叉樹。 （）9. 哈夫曼樹一定是滿二叉樹。 （）10. 樹的帶權路徑長度最小的二叉樹中必定沒有度為 1 的結點。（）11. 度為二的有序樹等價于二叉樹。 （）12. 在一棵二叉樹中， 假定每個結點只有左子女，沒有右子女， 對它分別進行中序遍歷和后序遍

26、歷，則具有相同的結果。 （）13. 算法和程序都應具有下面一些特征： 輸入，輸出，確定性，有窮性，可行性。 （）14. 二叉樹是一棵無序樹。 （）15. 數據元素是數據的最小單位。 （）16. 廣義表的表頭和表尾既可以是單元素,也可以是廣義表。 （）17. 如果兩個串中含有相同的字符， 則這兩個串相等。（）18. 稀疏矩陣壓縮存儲后， 必會失去隨機存取功能。（）19. 在對雙向循環(huán)鏈表做刪除一個結點操作時，應先將被刪除結點的前驅結點和后繼結點鏈接好再執(zhí)行刪除結點操作。 （）20. 只有用面向對象的計算機語言才能描述數據結構算法。 （）21. 棧和隊列都是順序存取的線性表 , 但它們對存取位置的

27、限制不同。 （）22. 棧和隊列都是限制取點的線性結構。（）23. 若某堆棧的輸入序列為1,2,3,4 ，則4,3,1,2不可能是堆棧的輸出序列之一。（）24. 數據的邏輯結構是指各數據元素之間的邏輯關系，是用戶根據應用需要建立的。（）25. 單鏈表形式的隊列， 頭指針 F 指向隊列的第一個結點， 尾指針 R 指向隊列的最后一個結點。 （）26. 堆棧、隊列和數組的邏輯結構都是線性表結構。（）27. 鏈式棧與順序棧相比 , 一個明顯的優(yōu)點是通常不會出現棧滿的情況。 （）28. 遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行效率也高。 （）29. 順序表和一維數組一樣， 都可以按下標隨機（或直接）訪問。 （）30. 堆排序是所需輔助空間最少的排序。（）31. 在采用線性探測法處理沖突的散列表中 , 所有同義詞在表中一定相鄰。（）32. 對 n 個元素的表用堆排序法進行排序，時間復雜度是 O(log2n) 。（）33. 散列法存儲的基本思想是由關鍵字的值決定數據的存儲地址。 （）34. 快速排序法是一種穩(wěn)定性排序法