1、第一章 算法和數據結構一、算法1. 在計算機中，算法是指BA加工方法B解題方案的準確而完整的描述C排序方法D查詢方法2. 算法的復雜度主要包括時間復雜度和 空間 復雜度。3. 算法的時間復雜度是指CA執行算法程序所需要的時間B算法程序的長度C算法執行過程中所需要的根本運算次數D算法程序中的指令條數4. 算法的空間復雜度是指DA算法程序的長度B算法程序中的指令條數C算法程序所占的存儲空間D算法執行過程中所需要的存儲空間5. 算法分析的目的是DA找出數據結構的合理性B找出算法中輸入和輸出之間的關系C分析算法的易懂性和可靠性D分析算法的效率以求改進6. 以下表達正確的選項是CA算法的執行效率與數據的

2、存儲結構無關B算法的空間復雜度是指算法程序中指令或語句的條數C算法的有窮性是指算法必須能在執行有限個步驟之后終止D算法的時間復雜度是指執行算法程序所需要的時間7. 算法一般都可以用哪幾種控制結構組合而成DA循環、分支、遞歸B順序、循環、嵌套C循環、遞歸、選擇D順序、選擇、循環8. 在以下選項中，哪個不是一個算法一般應該具有的根本特征CA確定性B可行性C無窮性D擁有足夠的情報9. 算法的根本特征是可行性、確定性、 有窮性 和擁有足夠的情報。二、 數據結構10. 所謂 數據處理 是指對數據集合中的各元素以各種方式進行運算，包括插入、刪除、查找、更改等運算，也包括對數據元素進行分析。11. 數據結構

3、是指相互有關聯的 數據元素 的集合。12. 數據結構作為計算機的一門學科，主要研究數據的邏輯結構、對各種數據結構進行的運算，以及AA數據的存儲結構B計算方法C數據映象D邏輯存儲13. 數據結構包括數據的 邏輯 結構和數據的存儲結構。線性鏈表屬于 存儲結構 。14. 數據的存儲結構是指BA數據所占的存儲空間量B數據的邏輯結構在計算機中的表示C數據在計算機中的順序存儲方式D存儲在外存中的數據15. 數據結構中，與所使用的計算機無關的是數據的( C )。A.存儲結構 B.物理結構 C.邏輯結構 D.物理和存儲結構16. 以下表達中，錯誤的選項是BA數據的存儲結構與數據處理的效率密切相關B數據的存儲結

4、構與數據處理的效率無關C數據的存儲結構在計算機中所占的空間不一定是連續的D一種數據的邏輯結構可以有多種存儲結構17. 常用的存儲結構有順序、連接、 索引 等存儲結構。18. 順序存儲方法是把邏輯上相鄰的結點存儲在物理位置 相鄰 的存儲單元中。19. 根據數據結構中各數據元素之間前后件關系的復雜程度，一般將數據結構分為CA動態結構和靜態結構B緊湊結構和非緊湊結構C線性結構和非線性結構D內部結構和外部結構20. 數據元素之間的任何關系都可以用 前趨和后繼 關系來描述。三、線性表及其順序存儲結構21. 當線性表采用順序存儲結構實現存儲時，其主要特點是 邏輯結構中相鄰的結點在存儲結構中仍相鄰 。22.

5、 在計算機中存放線性表，一種最簡單的方法是 順序存儲 。23. 在程序設計語言中，通常定義一個 一維數組 來表示線性表的順序存儲空間。24. 對長度為n的線性表進行插入一個新元素或刪除一個元素時，在最壞情況下所需要的比較次數為 n 。25. 長度為n的順序存儲線性表中，當在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數為 n/2 。四、棧和隊列26. 棧和隊列的共同特點是CA都是先進先出B都是先進后出C只允許在端點處插入和刪除元素D沒有共同點 27. 以下數據結構具有記憶功能的是CA隊列 B循環隊列 C棧 D順序表28. 以下數據結構中，按先進后出原那么組織數據的是BA

6、線性鏈表 B棧C循環鏈表 D順序表29. 遞歸算法一般需要利用A實現。A棧 B隊列 C循環鏈表 D雙向鏈表30. 以下關于棧的表達中正確的選項是DA在棧中只能插入數據B在棧中只能刪除數據C棧是先進先出的線性表D棧是先進后出的線性表31. 以下關于棧的表達正確的選項是DA棧是非線性結構B棧是一種樹狀結構C棧具有先進先出的特征D棧具有后進先出的特征32. 棧的根本運算有三種：入棧、退棧與 讀棧頂元素 。33. 棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，那么出棧序列可能是BAABCED BDCBEA CDBCEA DCDABE34. 如果進棧序列為e1,e2,e3

7、,e4，那么可能的出棧序列是BAe3,e1,e4,e2 Be2,e4,e3,e1 Ce3,e4,e1,e2 D任意順序35. 棧通常采用的兩種存儲結構是AA線性存儲結構和鏈表存儲結構B散列方式和索引方式C鏈表存儲結構和數組D線性存儲結構和非線性存儲結構36. 由兩個棧共享一個存儲空間的好處是BA減少存取時間，降低下溢發生的機率B節省存儲空間，降低上溢發生的機率C減少存取時間，降低上溢發生的機率D節省存儲空間，降低下溢發生的機率37. 應用程序在執行過程中，需要通過打印機輸出數據時，一般先形成一個打印作業，將其存放在硬盤中的一個指定B中，當打印機空閑時，就會按先來先效勞的方式從中取出待打印的作業

8、進行打印。A棧 B隊列 C數組 D字符串38. 以下關于隊列的表達中正確的選項是CA在隊列中只能插入數據B在隊列中只能刪除數據C隊列是先進先出的線性表D隊列是先進后出的線性表五、線性鏈表39. 以下表達中，正確的選項是DA線性鏈表中的各元素在存儲空間中的位置必須是連續的B線性鏈表中的表頭元素一定存儲在其他元素的前面C線性鏈表中的各元素在存儲空間中的位置不一定是連續的，但表頭元素一定存儲在其他元素的前面D線性鏈表中的各元素在存儲空間中的位置不一定是連續的，且各元素的存儲順序也是任意的40. 在 線性單鏈表中 ，每一個結點只有一個指針域，由這個指針只能找到后繼結點，但不能找到前驅結點。41. 線性

9、表La1,a2,a3,ai,an，以下說法正確的選項是DA每個元素都有一個直接前件和直接后件B線性表中至少要有一個元素C表中諸元素的排列順序必須是由小到大或由大到小D除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件42. 線性表的順序存儲結構和線性表的鏈式存儲結構分別是BA順序存取的存儲結構、順序存取的存儲結構B隨機存取的存儲結構、順序存取的存儲結構C隨機存取的存儲結構、隨機存取的存儲結構D任意存取的存儲結構、任意存取的存儲結構43. 以下表達中正確的選項是AA線性表是線性結構B棧與隊列是非線性結構C線性鏈表是非線性結構D二叉樹是線性結構44. 棧和隊列通常采用的

10、存儲結構是 鏈式存儲和順序存儲 。45. 在實際應用中，帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存儲結點，這種帶鏈的棧稱為 可利用棧 。46. 線性表假設采用鏈式存儲結構時，要求內存中可用存儲單元的地址DA必須是連續的 B局部地址必須是連續的C一定是不連續的 D連續不連續都可以47. 鏈表不具有的特點是BA不必事先估計存儲空間B可隨機訪問任一元素C插入刪除不需要移動元素D所需空間與線性表長度成正比48. 用鏈表表示線性表的優點是CA便于隨機存取B花費的存儲空間較順序存儲少C便于插入和刪除操作D數據元素的物理順序與邏輯順序相同49. 為了要在線性鏈表中插入一個新元素，首先要給該元素分配一個

11、 新結點 ，以便用于存儲該元素的值。50. 在線性鏈表中刪除一個元素后，只需要改變被刪除元素所在結點的前一個結點的 指針域 即可。51. 在單鏈表中，增加頭結點的目的是AA方便運算的實現B使單鏈表至少有一個結點C標識表結點中的首結點的位置D說明單鏈表是線性表的鏈式存儲實現52. 與單向鏈表相比，雙向鏈表的優點之一是CA更節省存儲空間B便于進行隨機訪問C更容易訪問相鄰結點D可以省略頭指針和尾指針53. 在D中，只要指出表中任何一個結點的位置，就可以從它出發依次訪問到表中其他所有結點。A線性單鏈表B雙向鏈表C線性鏈表D循環鏈表54. 循環鏈表的主要優點是BA不再需要頭指針了B從表中任一結點出發都能

12、訪問到整個鏈表C在進行插入、刪除運算時，能更好的保證鏈表不斷開D某個結點的位置后，能夠容易的找到它的直接前件55. 循環隊列主要有兩種根本運算：入隊運算與退隊運算。每進行一次入隊運算，隊尾指針就 進1 。56. 當循環隊列非空且隊尾指針等于對頭指針時，說明循環隊列已滿，不能進行入隊運算。這種情況稱為 上溢 。57. 在一個容量為25的循環隊列中，假設頭指針front=16，尾指針rear=9，那么該循環隊列中共有 18 個元素。58. 在一個容量為15的循環隊列中，假設頭指針front=6，尾指針rear=9，那么該循環隊列中共有 3 個元素。六、樹與二叉樹59. 以下數據結構屬于非線性數據結

13、構的是CA隊列B線性表C二叉樹D棧60. 樹是結點的集合，它的根結點數目是AA有且只有1 B1或多于1 C0或1 D至少261. 在樹形結構中，樹根結點沒有 前件 。62. 具有3個結點的二叉樹有DA2種形態 B4種形態C7種形態 D5種形態63. 設一棵二叉樹中有3個葉子結點，有8個度為1的結點，那么該二叉樹中總的結點數為 13 。64. 在一棵二叉樹上第8層的結點數最多是C 注：2K-1A8B16C128D25665. 設一棵完全二叉樹共有699個結點，那么在該二叉樹中的葉子結點數為BA349B350C255D35166. 設一棵完全二叉樹共有739個結點，那么在該二叉樹中有 370 個葉

14、子結點。67. 設一棵完全二叉樹共有700個結點，那么在該二叉樹中有 350 個葉子結點。68. 在深度為5的滿二叉樹中，葉子結點的個數為B 注：2n1A32 B31 C16 D1569. 設樹T的度為4，其中度為1，2，3，4的結點個數分別為4，2，1，1。那么T中的葉子結點數為A A8 B7 C6 D570. 在先左后右的原那么下，根據訪問根結點的次序，二叉樹的遍歷可以分為三種：前序遍歷、 中序 遍歷和后序遍歷。71. 設有以下二叉樹，對此二叉樹中序遍歷的結果是BAAB CD E FABCDEFBDBEAFCCABDECFDDEBFCA72. 二叉樹后序遍歷序列是dabec，中序遍歷序列是

15、debac，它的前序遍歷序列是DAacbedBdecab Cdeabc Dcedba73. 一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，那么該二叉樹的后序遍歷為BAGEDHFBCA BDGEBHFCA CABCDEFGH DACBFEDHG74. 假設某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，那么其后序遍歷的結點訪問順序是DAbdgcefha Bgdbecfha Cbdgaechf Dgdbehfca75. 設一棵二叉樹的中序遍歷結果為DBEAFC，前序遍歷結果為ABDECF，那么后序遍歷結果為 DEBFCA 。76. 串的長度

16、是DA串中不同字符的個數B串中不同字母的個數C串中所含字符的個數且字符個數大于零 D串中所含字符的個數77. 設有兩個串p和q，求q在p中首次出現位置的運算稱做BA連接 B模式匹配C求子串 D求串長78. 假設串S="Program"，那么其子串的數目是 29 。 注：n(n+1)/2+179. 假設串S=MathTypes，那么其子串的數目是 46 。80. N個頂點的連通圖中邊的條數至少為CA0 B1CN-1 DN81. N個頂點的強連通圖的邊數至少有CAN-1BN(N-1)CNDN+1七、查找82. 順序查找一般是指在 線性表 中查找指定的元素。83. 在長度為n的有

17、序線性表中進行二分查找。最壞的情況下，需要的比較次數為 log2n 。84. 對長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數為BAN+1 BN C(N+1)/2 DN/2八、排序85. 排序是計算機程序設計中的一種重要操作，常見的排序方法有插入排序、 交換排序 和選擇排序等。86. 快速排序法可以實現通過一次交換而消除多個 逆序 。快速排序法的關鍵是對線性表進行 分割 。87. 最簡單的交換排序方法是DA快速排序 B選擇排序 C堆排序 D冒泡排序88. 在待排序的元素序列根本有序的前提下，效率最高的排序方法是AA冒泡排序 B選擇排序 C快速排序 D歸并排序89. 冒泡排序算法在最好的情況下的元素交換次數為 0 。90. 假設線性表的長度為n，那么在最壞情況下，冒泡排序需要的比較次數為D。或者說在最壞情況下，冒泡排序的時間復雜度為 n(n-1) /2 。Alog2n Bn2CO(n1.5) Dn(n