1、A.原子B.列表C.任何元C.a+top = x;D.atop+=a,b,c,d,eC降低下溢發生的機率降低上溢發生的機率降低上溢發生的機率降低下溢發生的機率則出棧次序不B.d,e,c,b,a1 . 一個非空廣義表的表頭 。A A.不可能是子表 B.只能是子表C.只能是原子 D D.可以是子表或原子2 .在以下的敘述中，正確的是 。A A.二維數組可以看做它的每個數據元素為一個線性表的線性表r B.棧的操作方式是先進先出 C.線性表的線性存儲結構優于鏈表存儲結構 D.隊列的操作方式是先進后出3 .如下陳述中正確的是。A A.串是一種特殊的線性表r B.串的長度必須大于零 C C.串中元素只能是

2、字母D D.空串就是空白串4 .如下陳述中正確的是。A A.串是一種特殊的線性表r B.串的長度必須大于零 c C.串中元素只能是字母D D.兩個串si和s2若長度相同，則這兩個串相等5 .數組A中，每個元素的長度為 3字節，行 下標從1到8,列下標從1到10,從首地址SA 開始連續存放在存儲器中，按行存放時，元素a85 地址為。rrA.SA+141B.SA+1806 rC.SA+222D.SA+2256 .任何一個非空列表其表頭可能是原子， 也可能是列表，而其表尾是 。素 D.空7 .稀疏矩陣一般的壓縮存儲方法有兩種。 A.二維數組和三維數組 B.三元組和散列cC.三元組和十字鏈表DD.散列

3、和十字鏈表8 .常對數組進行的兩種基本操作是。A A.建立和刪除 r B.插入和修改C C.查找和修改 D D.查找和索引9 .假定利用數組aN順序存儲一個棧，用 top表示棧頂指針，top = = 0 表示棧空， 并已知棧未滿， 當元素 x進棧時所執行的操 作為。rrA.a-top = x; B.atop- = x;x;10 .由兩個棧共享一個向量空間的好處是A.減少存取時間 rB.節省存儲空間 G C.減少存取時間 D.節省存儲空間 11.入棧次序是 可能是rA.e,d,c,b,aC.d,c,e,a,bD.a,b,c,d,e12.假定利用數組aN循環順序存儲一個隊列，用front（指向隊首

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

5、尾指針分別為front和rear ,則判斷隊空的條件是A.front=rearB.front!=NULLC C.rear!=NULL D.front=NULL 16.隊和棧的主要區別是 。AA.邏輯結構不同 B.存儲結構不同 C.所包含的運算個數不同"D.限定插入和刪除的位置不同17 .假定一個順序隊列的隊首和隊尾指針 分別為front和rear，則判斷隊空的條件是A.front+1= =rearB.rear+1 =r6=front C.front= =0D.front= =rear18 .鏈式棧與順序棧相比，一個比較明顯的優點是。A.插入操作更加方便GB.通常不會出現棧滿的情況 C

6、.不會出現棧空的情況D.刪除操作更加方便19 .判定一個棧ST (最多元素為 mO為空 的條件是A A.ST->top<>0 B B.ST->top=0rcC.ST->top<>m0 D.ST->top=m020 .下面算法的時間復雜度為 。 int f( unsigned int n ) if ( n=0 | n=1 ) return 1; else return n*f(n-1); A A.O(1) B B.O(n) C C.O(n2)D D.O(n!)21 .在長度為n的順序存儲的線性表中，刪除第i個元素(1Wi wn)時，需要從前向 后依

7、次前移()個元素。(S-CCA.n-IB.n-i+1C.n-i-1r D. i22 .線性表若采用鏈式存儲結構時，要求內 存中可用存儲單元的地址 。A A.必須是連續的BB.部分地址必須是連續的C. 一定是不連續的6 D.連續，不連續都可以23 .計算機識別、存儲和加工處理的對象被 統稱為()岸 A.數據 B B.數據元素0 C.數據結構 D.數據類型24 .算法指的是。AA.計算機程序B B.解決問題的計算方法 C.排序算法6D.解決問題的有限運算序列25 .在n個元素進行快速排序的過程中， 第一趟排序最多需要交換 對元素。r(51rA.n/2B.n-1C.nrD.n+126 .若對n個元素

8、進行直接插入排序，在進 行i趟(2 w i w n)排序時，為尋找插入位置 最多需要進行 次元素的比較。 A.i+1B.i-1* C.iD D.127 .對于哈希函數H(key尸key%13 ,被稱為 同義詞(即沖突)的關鍵字是 A A.35 和 41 B B.23 和 39C.15 和 44,D.25 和 5128 .若一組記錄的排序碼為 (46, 79, 56, 38,40, 84 ),則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為A.38,40,46,56,79,84rB.40,38,46,79,56,84W C.40,38,46,56,79,84rD.40,38,46,8

9、4,56,7929 .在n個元素進行簡單選擇排序的過程 中，需要進行 趟選擇。rccA.n/2B.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,7221, 15,23,27,35,20,47,59,72則所米用的排序方法是A A.選擇排序B B.起泡排序C C.歸并排序D.快速排序31 .設哈希表長為14,哈希函數f (k) =k% 11,已知表中已有4個元素，關鍵字分別為

10、15, 38, 61, 84,存儲位置分別為 4, 5, 6, 7,其它存儲位置為空，如用二次探測再散 列處理沖突，關鍵字為49的存儲位置是cA.8B.3C.5D.932 .對于順序存儲的有序表 (5, 12, 20, 26, 37, 42, 46, 50, 64),哨兵位在前，為查找元素26,若采用順序查找，需要比較次才能查找成功。C C C GA.3B.4C.5D.633 .具有e條邊的無向圖，它的鄰接表中有 個邊結點。rr cA.e-1B.eC.2(e-1)D.2e34 .具有e條邊的有向圖，它的逆鄰接表中有 個弧結點。CCCA.e-1B.eC.2(e-1)D D.2e35 .由權值分別

11、為3, 8, 6, 2, 5 的葉子結 點生成一顆哈夫曼樹，它的帶權路徑長度為A.24B.48C.72'D.5336 .如果某圖的鄰接矩陣是對角線元素以 下元素均為零的上三角矩陣，則此圖是 A.有向完全圖 B B.連通圖 C C.強連通圖 D.有向無環圖37 .下面關于圖的存儲的敘述中，哪一個是正確的。1V A.用鄰接矩陣法存儲圖，占用的存儲空 間數只與圖中結點個數有關，而與邊數無關 B.用鄰接矩陣法存儲圖，占用的存儲空 間數只與圖中邊數有關，而與結點個數無關 C.用鄰接表法存儲圖，占用的存儲空間 數只與圖中結點個數有關，而與邊數無關0 D.用鄰接表法存儲圖，占用的存儲空間數只與圖中邊

12、數有關，而與結點個數無關 38.圖的深度優先遍歷類似于樹的A A.先序遍歷 B B.中序遍歷C.后序遍歷DD.層次遍歷39 . 一個連通圖的生成樹是包含圖中所有 頂點的一個 子圖。A.極小B.連通C.極小連通 D D.無環40 .有向圖的一個頂點的度為該頂點的A A.入度 B B.出度 C.入度與出度之和 D D.(入度+出度)/241 .在一個有向圖中，所有頂點的度數之和等于所有弧數的 倍。car A.3B.2C.1D.1/242 . n個頂點的連通圖至少有 條邊。*A.n-1B.nC.n+1rD.043 .頂點個數為n的無向圖最多有 條邊。A A.n-1B B.n(n-1)/2C C.n(

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

14、 f),則該樹的度為。a C C CA.2B.3C.4D.549 . 一棵樹的廣義表表示為a(b(c), d(e(g(h), f),則該樹的高度為。r r rA.2B.3C.4D.550 .在一棵深度為h的完全二叉樹中，所含 結點個數不少于。c rCA. 2h B. 2h+1 C. 2h-18D D. 2h-1度為1的結點有 6個，那么葉子結點有_6個51.在一棵二叉樹的第5層上，最多具有個結點。8.假定一棵樹的廣義表表示為 A(B(C, D(E, F,G), H(I, J),則結點H的雙親結點為A A.14B B.16C C.31_Bo9.假定一棵二叉樹白結點個數為32,則它D.32的最小深

15、度為_6。10.已知廣義表ls=(a,(b,c,d),e),運用52.在一棵具有n個結點的二叉樹中，所有 結點的空子樹個數等于。head和tail函數取出ls中的原子b的運算是 _head(head(tail(ls) 。A A.nB B.n-16C.n+111.廣義表(A,(a,b),d,e,(i,j),k)，則廣義表的長度為 _5,深度為_3,D D.2*n表頭 為A, 表尾為 _(a,b),d,e,(i,j),k) 。53.數據結構通常是研究數據的及它們之間的聯系。12.稀疏矩陣可用三兀組進行壓縮存儲，存儲時需存儲非零元的_元素值和行、列3A.存儲和邏輯結構B B.存儲和數。13.在串的鏈

16、式存儲方式中， 結點越大，運 算處理越 小方便)，存侏占用里越 小)抽象 'C.理想和抽象' D.理想與14. 一個串的任意個連續的字符組成的子邏輯序列稱為該串的 子串 ，包含該子序列 的串稱為_主串,該子序列在串中的位置用 子串的第一個字符在主串中的位置末去小O15.廣義表(a)的表頭是(a),表尾是在含100個結點的完全二叉樹，葉子結點的 個數為_50。2 . 一棵含有16個結點的完全二叉樹， 對他 按層編號，對于編號為 7的結點，他的雙親 結編號點為_3左孩子編號為_14、右孩子編號為 15。3 .對任何一棵二叉樹，若 n0, n1, n2分別 是度為0 , 1 , 2的

17、結點的個數，則 n0=_n2+1o4 .高度為k的二叉樹具有的結點數目，最 少為 _k_,最多為_2k-1。5 .對干-顆具有 n個結點的二叉樹，對應 二叉鏈表中指針域有 _n-1個用于指向子結點。6 .樹的雙親表示法便于實現涉及到_雙親的操作，孩子表示法便于實現涉及到 孩子的操作。7 .在一棵二叉樹中，度為2的結點有5個，3。16 .廣義表(a) ,a)的表頭是(a),表尾 是(a) o17 .數組A中，每個元素的長度為 3個字節， 行下標從1到8 ,列下標從1到10 ,從首 地址開始連續存放在存儲器內，存放該數組 至少需要的單元數是 240。18 . 棧的特點是后進先出 O19 .對于順序

18、存儲的隊列，存儲空間大小為n,頭指針為F,尾指針為R。若在邏輯上看 一個環，則隊列中元素的個數為 _(R-F+n)%n。20 .隊列又稱為先進先出的線性表。21 .棧結構允許進行刪除操作的一端為棧頂。22 .已知循環隊列的存儲空間為數組 a21,且頭指針(指向隊頭元素)和尾指針(隊尾元素的下一位置)分別為8 和 3，則該隊列的當前長度為_16。23. 在初始為空的隊列中插入元素A,B,C,D以后，緊接著做了兩次刪除操作，此時的隊尾元素是_D。24. 在非空線性表中除第一個元素外，集合中每 個數據 元 素 只 有 一 個 _直接 前驅；除最后一個元素之外，集合中每個數 據元素 均 只 有 一 個

19、 _直接 后繼25. 在雙向鏈表中，每個結點含有兩個指針域， 一個指向_直接前驅結點， 另一個指向_直接后繼結點。26. 在單鏈表設置表頭結點的作用是插入和刪除表中第一個元素時不必對_頭指針進行特殊處理。27. 在一個單鏈表L 中， 若要在指針q 所指結點的后面插入一個由指針p 所指向的結點，則應進行的操作序列為：_p-next=q->next;q一 >next=p 。28. 順序表中邏輯上相鄰的元素的物理位置 _相鄰 ， 單鏈表中邏輯上相鄰的元素的物理位置_不一定相鄰。29. 在以 L 為頭指針的帶頭結點的單鏈表和單循環鏈表中，判斷鏈表是否為空的條件分別 為 _L->nex

20、t=NULL 和_L->next=L 。30. 已知一順序存儲的線性表，每個元素占用 k 個存儲單元，若第一個元素的地址為Loc1 ， 則第 i 個元素的地址為_Loc1+( i-1 )*k 。31. 若經常需要對線性表進行插入與刪除操作， 該線性表最好采用_鏈式 存儲結構。32. 若經常需要對線性表進行查找操作，則最好采用_順序 存儲結構。33. 若 待 散 列 的 序 列 為 (18,25,63,50,42,32,9)， 散 列 函 數 為H(key)=key%9 ，與 18 發生沖突的元素有_63,9 。34. _循環鏈表鏈表從任何一個結點出發，都能訪問到所有結點。35. 假 定

21、一 組 數 據 的 關 鍵 字 為46,79,56,38,40,84 ，則以第一個記錄為樞軸，對其進行第一趟快速排序的結果為_40,38,46,56,79,84 。36. 假 定 一 組 數 據 的 關 鍵 字 為46,79,56,38,40,84 ，則利用堆排序方法建立的初始小頂堆為_38 ， 40， 56， 79， 46，84 。37. 每次直接或通過 “樞軸” 元素間接比較兩個元素，若出現逆序排列時就交換它們的位置，此種排序方法叫做_交換 排序。38. 每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序方法叫做 _插入 排序。39. 每次從無序表中挑選出一個最大或最小元素

22、，把它交換到有序表的一端，此種排序方法叫做_選擇 排序。40. 每次使兩個相鄰的有序表合并成一個有序表的排序方法叫做_2 路歸并排序排序。41. 先將整個待排序列分割成若干子序列分別進行直接插入排序，待整個序列 “基本有序” 時， 再對全體進行一次直接插入排序，此種排序方法叫做_希爾 排序。42. 將一個數據元素(或記錄)的任意序列，重新排列成一個按關鍵字有序的序列叫_排序 。43. 元素關鍵字轉換為該元素存儲位置的函數 f 稱為_哈希函數。44. 數據的邏輯結構包括集合、_線性結構、樹形結構和圖狀結構四種類型。45. 已知有實現同一功能的兩個算法，其時間復雜度分別為O(log2n) 和 O(

23、n) ，哪個算法的效率更高？_O(log2n) 46. 假設在有序線性表a20 上進行折半查找，則比較一次查找成功的結點數為1；比較兩次查找成功的結點數為2 ； 比較四次查找成功的結點數為8 ； 平均查找長度為3.747. 在數據的存放無規律而言的線性表中進行檢索的最佳方法是順序查找48. 元素關鍵字轉換為該元素存儲位置的函數 f 稱為_哈希函數49. 若要對某二叉排序樹進行遍歷，保證輸出元素的值序列按增序排列，應對該二叉排序樹采用_中序_遍歷法。50. 通常用時間復雜度和_空間復雜度 兩種方法衡量算法的效率。51. 在一個無向圖中，所有頂點的度數之和等于所有邊數的_2倍。52. 在無向圖中，

24、若從頂點A到頂點B存在 路徑,則稱A與B之間是連通的。53. 有一個 n 個頂點的有向完全圖的弧數_n（n-1） 。54. 對于一個具有n 個頂點的圖，若采用鄰接矩陣表示，則矩陣大小為_n2。55. 已知一棵樹的前序序列為 ABCDEF后序 序列為CEDFBAW對該樹進行層次遍歷得到 的序列為ABCDFE。_56. 若一棵完全二叉樹含有121 個結點， 則該樹的深度為_7。57. 度數為 0 的結點， 即沒有子樹的結點叫作葉子結點。同一個結點的兒子結點之間互稱為兄弟結點1. 任何一棵二叉樹都有n0=n2+1 的關系式。（，）2. 插入與刪除操作是數據結構中最基本的兩種操作，因此這兩種操作在數組

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

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

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