自學考試數(shù)據(jù)結構

精品文檔-下載后可編輯自學考試數(shù)據(jù)結構自學考試數(shù)據(jù)結構

一、單選題（共50題，共100分）

1.串匹配算法的本質(zhì)是()。

A.串復制

B.串比較

C.子串定位

D.子串鏈接

2.設有一個10階的對稱矩陣A，采用行優(yōu)先壓縮存儲方式，a11為第一個元素，其存儲地址為1，每個元素占一個字節(jié)空間，則a85的地址為()。

A.13

B.18

C.33

D.40

3.若一棵二叉樹的前序遍歷序列與后序遍歷序列相同，則該二叉樹可能的形狀是()。

A.樹中沒有度為2的結點

B.樹中只有一個根結點

C.樹中非葉結點均只有左子樹

D.樹中非葉結點均只有右子樹

4.若根結點的層數(shù)為1，則具有n個結點的二叉樹的最大高度是()。

A.n

B.LIogn2n_I

C.LIogn2n_I+1

D..n/2

5.在圖G中求兩個結點之間的最短路徑可以采用的算法是()。

A.迪杰斯特拉（Dijkstra）算法

B.克魯斯卡爾（Kruskal）算法

C.普里姆(Prim)算法

D.廣度優(yōu)先遍歷(BFS)算法

6.如果在排序過程中不改變關鍵字相同元素的相對位置，則認為該排序方法是()。

A.不穩(wěn)定的

B.穩(wěn)定的

C.基于交換的

D.基于選擇的

7.設有一組關鍵字(19,14,23,1，6，20,4，27,5，11,10,9)，用散列函數(shù)H(key)=key%13構造散列表，用拉鏈法解決沖突，散列地址為1的鏈中記錄個數(shù)為()。

A.1

B.2

C.3

D.4

8.若需高效地查詢多關鍵字文件，可以采用的文件組織方式為()。

A.順序文件

B.索引文件

C.散列文件

D.倒排文件

9.在數(shù)據(jù)的邏輯結構中，樹結構和圖結構都是()。

A.非線性結構

B.線性結構

C.動態(tài)結構

D.靜態(tài)結構

10.在一個長度為n的順序表中插入一個元素的算法的時間復雜度為()。

A.O（1）

B.Ｏ（logn）

C.O（n）

D.O（n2）

11.設棧的初始狀態(tài)為空，入棧序列為1，2，3，4，5，6，若出棧序列為2，4，3，6，5，1，則操作過程中棧中元素個數(shù)最多時為()。

A.2個

B.3個

C.4個

D.6個

12.指針p1和p2分別指向兩個無頭結點的非空單循環(huán)鏈表中的尾結點，要將兩個鏈表鏈接成一個新的單循環(huán)鏈表，應執(zhí)行的操作為()。

A.p1－＞next=p2－＞next;p2－＞next=p1－＞next

B.p2－＞next=p1－＞next;p1－＞next=p2－＞next

C.p=p2－＞next;p1－＞next=p;p2－＞next=p1－＞next

D.p=p1－＞next;p1－＞next=p2－＞next；p2－＞next=p

13.隊列的特點是()。

A.允許在表的任何位置進行插入和刪除

B.只允許在表的一端進行插入和刪除

C.允許在表的兩端進行插入和刪除

D.只允許在表的一端進行插入，在另一端進行刪除

14.廣義表A=(a,B,(a,B,(a,B,??)))的長度為()。

A.1

B.2

C.3

D.無限值

15.已知10×12的二維數(shù)組A，按“行優(yōu)先順序”存儲，每個元素占1個存儲單元，已知A[1][1]的存儲地址為420，則A[5][5]的存儲地址為()。

A.470

B.471

C.472

D.473

16.具有線性結構的數(shù)據(jù)結構是()線性結構有：順序表、棧和隊列、串。

A.樹

B.圖

C.棧和隊列

D.廣義表

17.將長度為n的單鏈表連接在長度為m的單鏈表之后，其算法的時間復雜度為()。

A.O(1)

B.O(m)

C.O(n)

D.O(m+n)

18.在帶頭結點的雙向循環(huán)鏈表中插入一個新結點，需要修改的指針域數(shù)量是()。

A.2個

B.3個

C.4個

D.6個

19.假設以數(shù)組A[60]存放循環(huán)隊列的元素，其頭指針是front=47，當前隊列有50個元素，則隊列的尾指針值為()。

A.3

B.37

C.50

D.97

20.若棧采用鏈式存儲結構，則下列說法中正確的是()。

A.需要判斷棧滿且需要判斷?？?/p>

B.不需要判斷棧滿但需要判斷?？?/p>

C.需要判斷棧滿但不需要判斷棧空

D.不需要判斷棧滿也不需要判斷?？?/p>

21.若串str=”Software”，其子串的數(shù)目是()。

A.8

B.9

C.36

D.37

22.設有一個10階的下三角矩陣A，采用行優(yōu)先壓縮存儲方式，all為第一個元素，其存儲地址為1000，每個元素占一個地址單元，則a85的地址為()。

A.1012

B.1017

C.1032

D.1039

23.允許結點共享的廣義表稱為()。

A.純表

B.線性表

C.遞歸表

D.再入表

24.下列數(shù)據(jù)結構中，不屬于二叉樹的是()。

A.B樹B樹是一種平衡的多叉樹

B.AVL樹AVL樹是自平衡二叉查找樹

C.二叉排序樹

D.哈夫曼樹哈夫曼樹是最優(yōu)二叉樹

25.下列排序算法中不穩(wěn)定的是()。

A.快速排序

B.歸并排序

C.冒泡排序

D.直接插入排序

26.采用ISAM組織文件的方式屬于()。

A.鏈組織

B.順序組織

C.散列組織

D.索引組織

27.數(shù)據(jù)的四種存儲結構是()。

A.順序存儲結構、鏈接存儲結構、索引存儲結構和散列存儲結構

B.線性存儲結構、非線性存儲結構、樹型存儲結構和圖型存儲結構

C.集合存儲結構、一對一存儲結構、一對多存儲結構和多對多存儲結構

D.順序存儲結構、樹型存儲結構、圖型存儲結構和散列存儲結構

28.若對某線性表最常用的操作是在最后一個結點之后插入一個新結點或刪除最后一個結點，要使操作時間最少，下列選項中，應選擇的存儲結構是()。

A.無頭結點的單向鏈表

B.帶頭結點的單向鏈表

C.帶頭結點的雙循環(huán)鏈表

D.帶頭結點的單循環(huán)鏈表

29.若帶頭結點的單鏈表的頭指針為head，則判斷鏈表是否為空的條件是()。

A.head=NULL

B.head-next=NULL

C.head!=NULL

D.head-next!=head

30.若元素的入棧順序為1，2，3，n，如果第2個出棧的元素是n，則輸出的第i(1=i=n)個元素是()。

A.n-i

B..n-i+l

C.n-i+2

D.無法確定

31.高度為5的完全二叉樹中含有的結點數(shù)至少為()。

A.16

B.17

C.31

D.32

32.已知在一棵度為3的樹中，度為2的結點數(shù)為4，度為3的結點數(shù)為3，則該樹中的葉子結點數(shù)為()。

A.5

B.8

C.11

D.18

33.下列關鍵字序列中，構成大根堆的是()。

A.5，8，1，3，9，6，2，7

B.9，8，1，7，5，6，2，33

C.9，8，6，3，5，l，2，7

D.9，8，6，7，5，1，2，3

34.對長度為15的有序順序表進行二分查找，在各記錄的查找概率均相等的情況下，查找成功時所需進行的關鍵字比較次數(shù)的平均值為()。

A.39/15

B.49/15

C.51/15

D.55/15

35.數(shù)據(jù)庫文件是由大量帶有結構的()。

A.記錄組成的集合

B.字符組成的集合

C.數(shù)據(jù)項組成的集合

D.數(shù)據(jù)結構組成的集合

36.按值可否分解，數(shù)據(jù)類型通常可分為兩類，它們是()。

A.靜態(tài)類型和動態(tài)類型

B.原子類型和表類型

C.原子類型和結構類型

D.數(shù)組類型和指針類型

37.指針p、q和r依次指向某循環(huán)鏈表中三個相鄰的結點，交換結點*q和結點*r在表中次序的程序段是()。

A.p-next=r；q-next=r-next；r-next=q

B.p-next=r；r-next=q；q-next=r-next

C.r-next=q；q-next=r-next；p-next=r

D.r-next=q；p-next=r；q-next=r-next

38.若進棧次序為a，b，c，且進棧和出?？梢源┎暹M行，則可能出現(xiàn)的含3個元素的出棧序列個數(shù)是()。

A.3

B.5

C.6

D.7

39.假設以數(shù)組A[n]存放循環(huán)隊列的元素，其頭指針front指向隊頭元素的前一個位置、尾指針rear指向隊尾元素所在的存儲位置，則在少用一個元素空間的前提下，隊列滿的判定條件為()。

A.rear==front

B.(front+1)％n==rear

C.rear+1==front

D.(rear+1)％n==front

40.二維數(shù)組A[10][6]采用行優(yōu)先的存儲方法，若每個元素占4個存儲單元，已知元素A[3][4]的存儲地址為1000，則元素A[4][3]的存儲地址為()。

A.1020

B.1024

C.1036

D.1036

41.已知森林F={T1，T2，T3，T4，T5}，各棵樹Ti(i=1，2，3，4，5)中所含結點的個數(shù)分別為7，3，5，1，2，則與F對應的二叉樹的右子樹中的結點個數(shù)為()。

A.2

B.3

C.8

D.11

42.對關鍵字序列(6，1，4，3，7，2，8，5)進行快速排序時，以第1個元素為基準的一次劃分的結果為()。

A.(5，1，4，3，6，2，8，7)

B.(5，1，4，3，2，6，7，8)

C.(5，1，4，3，2，6，8，7)

D.(8，7，6，5，4，3，2，1)

43.分塊查找方法將表分為多塊，并要求()。

A.塊內(nèi)有序

B.塊間有序

C.各塊等長

D.鏈式存儲

44.便于進行布爾查詢的文件組織方式是()。

A.順序文件

B.索引文件

C.散列文件

D.多關鍵字文件

45.若一個算法的時間復雜度用T(n)表示，其中n的含義是()。

A.問題規(guī)模

B.語句條數(shù)

C.循環(huán)層數(shù)

D.函數(shù)數(shù)量

46.下列程序段的時間復雜度為()。

A.O(1)

B.O(n)

C.O(2n)

D.O(n2^2)

47.假設某個帶頭結點的單鏈表的頭指針為head，則判定該表為空表的條件是()。

A.head==NULL

B.head-next==NULL

C.head!=NULL

D.head-next==head

48.棧是一種操作受限的線性結構，其操作的主要特征是()。

A.先進先出

B.后進先出

C.進優(yōu)于出

D.出優(yōu)于進

49.假設以數(shù)組A[n]存放循環(huán)隊列的元素，其頭、尾指針分