2011年山東省數(shù)據(jù)結構試題大全考試答題技巧(精)

1、1、有向圖采用鄰接矩陣存儲，某一行中非零元素的個數(shù)等于 A 對應頂點 v 的度 B.對應頂點 v 的出度 C.對應頂點 v 的入度 D.依附于對應頂點 v 的邊數(shù) 2、在一個長度為 n (n1)的單鏈表上，設有頭和尾兩個指針，執(zhí)行 B 操作與鏈表 的長度有關。A 刪除單鏈表中的第一個元素 B 刪除單鏈表中的最后一個元素 C.在單鏈表第一個元素前插入一個新元素 D.在單鏈表最后一個元素后插入一個 新元素 3、需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結構 是 B。A .單鏈表 B.靜態(tài)鏈表 C.線性鏈表 D .順序存儲結構 4、在二維數(shù)組 a910中：每個數(shù)組元素占用 3 個存儲

2、空間，從首地址 SA 開始按行優(yōu)先 連續(xù)存 放，則元素 a85的起始地址是 A. SA+141 B. SA+144 C. SA+222 D. SA+255 5、鏈表不具備的特點是 A o A .可隨機訪問任一結點 B .插入刪除不需要移動元 素 C.不必事先估計存儲空間 D .所需空間與其長度成正比 6、棧采用不同的存儲 方式時，下列關于出棧過程的敘述中，正確的是 A .順序棧需要判定?？眨湕Ｒ?需要判定 B.順序棧需要判定?？?，而鏈棧不需要判定 C.順序棧不需要判定棧 空，而鏈棧需要判定 D.順序棧不需要判定棧空，鏈棧也不需要判定 7、向一個長 度為 n 的順序表中插人一個新元素的平均時間

3、復雜度為 (。A . O(n B. 0(1 C. 0(n2 D. O(10g2n 8、深度為 k 的完全二叉樹所含葉結點的個數(shù)最多為(B)。 A) 2k B) 2k-1 C) k D) 2k 9、若進棧序列為 1, 2, 3, 4,則不可能得到的出棧 序列是(C )o A) 3, 2，1, 4 B) 3，2, 4，1 C) 4, 2, 3，1 D) 2，3, 4，1 10、已知關鍵字序列為66 , 82, 25, 51, 98, 108，利用快速排序方法，以第一 個元素為基準得到的一趟排序結果為 A . 25 , 51, 66, 82, 98, 108 B . 25 , 51, 66, 98,

4、 82, 108 C. 51 , 25, 66, 108, 98, 82 D . 51 , 25, 66, 82, 98, 108 11、已知關鍵字序列為66, 82, 25, 51, 98, 108，利用快速排序方 法，以第一個元素為基準得到的一趟排序結果為 A. 25 , 51, 66, 82, 98, 108 B. 25 , 51, 66, 98, 82, 108 C. 51 , 25, 66, 108, 98, 82 D . 51 , 25, 66, 82, 98, 108 12、棧采用不同的存儲方式時，下列關于出棧過程的敘述中， 正確的是 A .順序棧需要判定棧空，鏈棧也需要判定 B

5、 .順序棧需要判定?？眨?鏈棧不需要判定 C.順序棧不需要判定?？?，而鏈棧需要判定 D .順序棧不需要判定?？?，鏈棧也不需要判定 13、如果最常用的操作是取第 i 個結點及其前驅，則采 用 D存儲方式 最節(jié)省時間。 A 單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表14、 在一個 長度為n (n1)的單鏈表上，設有頭和尾兩個指針，執(zhí)行 B 操作與鏈表的長度有 關。A .刪除單鏈表中的第一個元素 B.刪除單鏈表中的最后一個元素 C.在單鏈 表第一個元素前插入一個新元素 D.在單鏈表最后一個元素后插入一個新元素 15、下述排序方法中，時間性能和待排序記錄的初始狀態(tài)無關的是( )A 插入排 序和快速排序

6、 B 歸并排序和快速排序 C 選擇排序和歸并排序 D 插入排序和歸并排 序 16、對于圖 1 所示的二叉樹， 其后序序列為(C )。 A) ABDECFG B ) DBEAFCG C ) DEBFGCA D ) GFCEBDA 17、在存儲數(shù)據(jù)時，通常不僅要存儲各 數(shù)據(jù)元素的值，而且還要存儲 C。A .數(shù)據(jù)的處理方法 B .數(shù)據(jù)元素的類型 C.數(shù) 據(jù)元素之間的關系 D.數(shù)據(jù)的存儲方法 18、長度為 n 的順序表，刪除位置 i 上的元 素(0 i 一 1,需要移動的元素個數(shù)為 A . n i B. ni I C . i D . i+1 19、在數(shù) 據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的 A 結

7、構。A .邏輯 B.存儲 C.邏 輯和存儲 D.物理 20、長度為 n 的順序表，刪除位置 i 上的元素(0 1)的 單鏈表上，設有頭和尾兩個指針，執(zhí)行 B 操作與鏈表的長度有關。 A .刪除單鏈 表中的第一個元素 B.刪除單鏈表中的最后一個元素 C .在單鏈表第一個元素前插 入一個新元素 D.在單鏈表最后一個元素后插入一個新元素 22、在一個具有 n 個 結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是 B。A . O (1) B . O (n) C . O (n2) D . O ( nlog2n) 23、深度為 k 的完全二叉樹所含葉 結點的個數(shù)最多為(B)o A) 2k B)

8、 2k-1 C) k D) 2k 24、棧采用不同的存儲方 式時，下列關于出棧過程的敘述中，正確的是 A .順序棧需要判定?？?，鏈棧也需 要判定 B .順序棧需要判定?？?，而鏈棧不需要判定 C .順序棧不需要判定?？?， 而鏈棧需要判定 D.順序棧不需要判定?？眨湕Ｒ膊恍枰卸?25、由權值分別 為 3, 8, 6, 2，5 的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為 (。A . 24 B . 48 C . 72 D . 53 26、下列選項中，符合堆定義的是 A . 102, 24, 55, 60, 89, 93 B . 24, 89, 55, 60, 93, 102 C . 102,

9、93, 55, 60, 89, 24 D. 102 , 60。89, 93, 55, 24 27、需要分配較大空間，插入和刪除不需要移動 元素的線性表，其存儲結構是 B。 A 單鏈表 B 靜態(tài)鏈表 C.線性鏈表 D.順序存儲結構 28、下列選項中，符 合堆定義的是 A. 102，24，55，60，89，93 B . 24，89，55，60，93，102 C. 102，93，55，60，89，24 D . 102，60。89，93，55，24 29、當一個作為 實際傳遞的對象占用的存儲空間較大并可能需要修改時，應最好把它說明為 （參 數(shù)，以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。 A.整形 B.引

10、用型 C.指針型 D.常 值引用型？ 30、下述排序方法中，時間性能和待排序記錄的初始狀態(tài)無關的是（ ） A 插入排序和快速排序 B 歸并排序和快速排序 C 選擇排序和歸并排序 D 插入排序 和歸并排序 31、從一棵二叉搜索樹中查找一個元素時，其時間復雜度大致為 （。 A. O（1 B.O（n C.O（1Ogz n D.O（ n2 32、不帶頭結點的單鏈表 head 為空的判定條件是 A。 A. head = NULL B head-next =NULL C . head-next =head D head!=NULL 33、非空的循環(huán)單鏈表 head 的尾結點（由 p 所指向）滿足 C。A.

11、 p- next = NULL B . p = NULL C . p-next =head D. p = head 34 由權值分別為 3, 8, 6, 2, 5 的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為 （。A . 24 B. 48 C. 72 D. 53 35、當一個作為實際傳遞的對象占用的存儲空間較大并可能 需要修改時，應最好把它說明為（參數(shù)，以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空 間。A.整形 B.引用型 C.指針型 D.常值引用型？ 36 由權值分別為 3, 8, 6, 2, 5 的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為 （。A . 24 B. 48 C. 72 D. 53

12、 37、一棵左子樹為空的二叉樹在前序線索化后，其空指針域個數(shù)為 A. 0 B . 1 C . 2 D .不確定 38、一個棧的入棧序列是 1,2,3,4,5,則不可能的出棧序列是 （A 5,4,3,2,1 B 4,5,3,2,1 C 4,3,5,1,2 D 1,2,3,4,5 39 在平衡二叉樹中插入一個結點后 造成不平衡，設最低的不平衡結點為 A，并已知 A 的左孩子平衡因子為 0,右孩子 平衡因子為 1,則應該做（）型調整以使其平衡 A LL B LR C RL D RR 40、若某 表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點，則采用 D 存儲方式最節(jié)省運算時間。 A

13、 .單鏈表 B.給出表頭指針的單循環(huán)鏈表 C.雙鏈 表 D.帶頭結點的雙循環(huán)鏈表 41、若進棧序列為 1, 2, 3, 4,則不可能得到的出棧序列是（C ）。A） 3, 2, 1, 4 B） 3, 2, 4, 1 C） 4, 2, 3, 1 D） 2, 3, 4, 1 42、與單鏈表相比，雙鏈表的優(yōu)點之一是 D o A 插入、刪除操作更簡單 B 可以進行隨機訪問 C 可以省略表頭指針或表尾指針 D 順序訪問相鄰結 點更靈活 43、在二維數(shù)組 a910中：每個數(shù)組元素占用 3 個存儲空間，從首地址 SA 開始按行優(yōu)先 連續(xù)存放，則元素 a85的起始地址是 A. SA+141 B. SA+144

14、C. SA+222 D. SA+255 44、衡量查找算法效率的主要標準是（ C ）。A）元素個 數(shù) B）所需的存儲量 C）平均查找長度 D）算法難易程度 45、下列選項中，符合 堆定義的是 A. 102 , 24, 55, 60, 89, 93 B . 24, 89, 55, 60, 93, 102 C. 102, 93, 55, 60, 89, 24 D . 102 , 60。89, 93, 55, 24 46、在數(shù)據(jù)結構 中，從邏輯上可以把數(shù)據(jù)結構分為 C o A 動態(tài)結構和靜態(tài)結構 B 緊湊結構和 非緊湊結構 C線性結構和非線性結構D 內部結構和外部結構 47、 若進棧序列 為 1,

15、2, 3, 4,則不可能得到的出棧序列是 （C ）o A） 3, 2, 1, 4 B） 3, 2, 4, 1 C） 4, 2, 3, 1 D） 2, 3, 4, 1 48、下列選項中，符合堆定義的是 A. 102, 24, 55, 60, 89, 93 B . 24 , 89, 55, 60, 93, 102 C . 102 , 93, 55, 60, 89, 24 D . 102, 60。89, 93, 55, 24 49、在存儲數(shù)據(jù)時，通常不僅 要存儲各數(shù)據(jù)元素的值，而且還要存儲 C o A .數(shù)據(jù)的處理方法 B .數(shù)據(jù)元素的 類型 C.數(shù)據(jù)元素之間的關系 D 數(shù)據(jù)的存儲方法 50、如果最

16、常用的操作是取第 i 個結點及其前驅，則采用 D 存儲方式最節(jié)省時間。A .單鏈表 B.雙鏈表 C.單 循環(huán)鏈表 D.順序表 51、需要分配較大空間，插入和刪除不需要移動元素的線性 表，其存儲結構是 B o A 單鏈表 B靜態(tài)鏈表 C線性鏈表 D 順序存儲結構 52、當一個作為實際傳遞的對象占用的存儲空間較大并可能需要修改時，應最好把 它說明為（參數(shù)，以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。 A.整形 B.引用型 C. 指針型 D.常值引用型？ 53、不帶頭結點的單鏈表 head 為空的判定條件是 A o A. head = NULL B head-next =NULL C . head-ne

17、xt =head D head!=NULL 54、對于圖 1 所示的二叉樹，其后序序列為（C ）o A） ABDECFG B ） DBEAFCG C ） DEBFGCA D ） GFCEBDA 55、在數(shù)據(jù)結構中，從邏輯上可以把數(shù) 據(jù)結構分為 C o A 動態(tài)結構和靜態(tài)結構 B 緊湊結構和非緊湊結構 C.線性結構 和非線性結構 D.內部結構和外部結構 56、如果最常用的操作是取第 i 個結點及其 前驅，則采用 D 存儲方式最節(jié)省時間。A 單鏈表 B 雙鏈表 C單循環(huán)鏈表 D. 順序表 57、深度為 k 的完全二叉樹至多有()個結點 A B C D 58、在一個具有 n 個結點的有序單鏈表中插入

18、一個新結點并仍然保持有序的 時間復雜度是 B o A. O (1) B. O (n) C. O (n 2) D. O (n Iog2 n) 59、若某 表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點，則采用 D 存儲方式最節(jié)省運算時間。 A .單鏈表 B.給出表頭指針的單循環(huán)鏈表 C.雙鏈 表 D.帶頭結點的雙循環(huán)鏈表 60、在二維數(shù)組 a910中：每個數(shù)組元素占用 3 個 存儲空間，從首地址 SA 開始按行優(yōu)先連續(xù)存放，則元素 a85的起始地址是 A. SA+141 B. SA+144 C. SA+222 D. SA+255 61、一個棧的入棧序列是 1,2,3,4,5,貝

19、U 不可能的出棧序列是(A 5,4,3,2,1 B 4,5,3,2,1 C 4,3,5,1,2 D 1,2,3,4,5 62 在一個單鏈表HL 中，若要向表頭插入一個由指針 p 指向的結點，則執(zhí)行(。 A. HL = ps pnext= HL B . p 一next= HL ; HL = p3 C. p 一next= Hl; p= HL; D . p 一next= HL 一next;HL 一next= p 63、如果對線性表的操作只有兩 種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用 B。 A .只有表頭指針沒有表尾指針的循環(huán)單鏈表 B.只有表尾指針沒有表頭指針的循 環(huán)單鏈表

20、 C.非循環(huán)雙鏈表 D .循環(huán)雙鏈表 64、以下說法正確的是 D。A .數(shù)據(jù) 項是數(shù)據(jù)的基本單位 B.數(shù)據(jù)元素是數(shù)據(jù)的最小單位 C .數(shù)據(jù)結構是帶結構的數(shù)據(jù) 項的集合 D. 些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結構 65、在以下的敘 述中，正確的是 Bo A .線性表的順序存儲結構優(yōu)于鏈表存儲結構 B .二維數(shù)組 是其數(shù)據(jù)元素為線性表的線性表 C.棧的操作方式是先進先出 D .隊列的操作方式 是先進后出 66、對于圖 1 所示的二叉樹，其后序序列為(C )o A) ABDECFG B) DBEAFCG C ) DEBFGCA D ) GFCEBDA 67、已知關鍵字序列為66，82， 25,

21、 51，98，108，利用快速排序方法，以第一個元素為基準得到的一趟排序結果 為 A. 25，51，66，82，98，108 B . 25，51，66，98，82，108 C. 51， 25，66，108，98，82 D . 51，25，66，82，98，108 68、如果對線性表的操作 只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用 B。 A .只有表頭指針沒有表尾指針的循環(huán)單鏈表 B.只有表尾指針沒有表頭指針 的循環(huán)單鏈表 C.非循環(huán)雙鏈表 D .循環(huán)雙鏈表 69、算法分析的目的是 C ,算法 分析的兩個主要方面是 A。 （1） A 找出數(shù)據(jù)結構的合理性 B 研究算

22、法中的輸 入和輸出的關系 C分析算法的效率以求改進 C 分析算法的易讀性和文檔性 （2） A.空間復雜度和時間復 雜度 B正確性和簡明性 C可讀性和文檔性 D數(shù)據(jù)復雜性和程序復雜性 70、由權值分別為 3, 8, 6, 2, 5 的葉子結點生成一棵哈夫曼樹，它的帶權路徑長 度為（。A. 24 B. 48 C. 72 D. 53 71、在循環(huán)雙鏈表的 p 所指的結點之前插入 s 所指結點的操作是 D。A. p-prior = s; s-next = p； p-prior-next = s； s-prior =p-prior B . p-prior = s; p-prior-next = s; s

23、-next = p； s-prior = p-prior C. s-next = p； s-prior = p-prior ； p-prior = s; p-prior-next = s D . s-next = p； s-prior = p-prior； p-prior-next = s； p-prior = s 72、在數(shù)據(jù)結構中，從邏輯 上可以把數(shù)據(jù)結構分為 C o A .動態(tài)結構和靜態(tài)結構 B .緊湊結構和非緊湊結構 C. 線性結構和非線性結構 D.內部結構和外部結構 73、由權值分別為 3, 8, 6, 2, 5 的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為 （。A . 24 B

24、. 48 C. 72 D. 53 74、在數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的 A 結構。A .邏輯 B. 存儲 C.邏輯和存儲 D.物理 75、衡量查找算法效率的主要標準是（C ）o A）元素個數(shù) B）所需的存儲量 C）平均查找長度 D）算法難易程度 76、數(shù)據(jù)結構 在計算機內存中的表示是指 A。A.數(shù)據(jù)的存儲結構 B .數(shù)據(jù)結構 C.數(shù)據(jù)的邏 輯結構 D.數(shù)據(jù)元素之間的關系 77、下述排序方法中，時間性能和待排序記錄的 初始狀態(tài)無關的是（）A 插入排序和快速排序 B 歸并排序和快速排序 C 選擇排序 和歸并排序 D 插入排序和歸并排序78、非空的循環(huán)單鏈表 head 的尾結點（由 p

25、 所 指向）滿足 C。A. p-next = NULL B . p = NULL C . p-next =head D. p = head 79 不帶頭結點的單鏈表 head 為空的判定條件是 A。A. head = NULL B head-next =NULL C . head-next =head D head!=NULL 80 若某線性表中最常 用的操作是取第 i 個元素和找第 i 個元素的前驅，則采用（存儲方法最節(jié)省時間 A 順序表 B 單鏈表 C 雙鏈表 D 單循環(huán)鏈表 81、通常要求同一邏輯結構中的所有數(shù)據(jù) 元素具有相同的特性，這意味著 Bo A .數(shù)據(jù)元素具有同一特點 B .不僅數(shù)據(jù)元 素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應的數(shù)據(jù)項的類型要一致 C.每個數(shù)據(jù)元 素都一樣 D.數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等 82、在數(shù)據(jù)結構中，從邏輯 上可以把數(shù)據(jù)結構分為 C。A .動態(tài)結構和靜態(tài)結構 B .緊湊結構和非緊湊結構 C. 線性結構和非線性結構 D.內部結構和外部結構 83、