全國自考《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》真題及

精品文檔-下載后可編輯全國自考《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》真題及全國自考《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》真題解析

一、單選題（共30題，共60分）

1.在順序表中查找第i個(gè)元素，時(shí)間效率最高的算法的時(shí)間復(fù)雜度為（）

A.O(1)

B.O(√n)

C.O(log2n)

D.O(n)

2.樹形結(jié)構(gòu)中，度為0的結(jié)點(diǎn)稱為（）

A.樹根

B.葉子

C.路徑

D.二叉樹

3.已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={}，則圖G的拓?fù)湫蛄惺牵ǎ?/p>

A.V1,V3,V4,V6,V2,V5,V7

B.V1,V3,V2,V6,V4,V5,V7

C.V1,V3,V4,V5,V2,V6,V7

D.V1,V2,V5,V3,V4,V6,V7

4.有關(guān)圖中路徑的定義，表述正確的是（）

A.路徑是頂點(diǎn)和相鄰頂點(diǎn)偶對構(gòu)成的邊所形成的序列

B.路徑是不同頂點(diǎn)所形成的序列

C.路徑是不同邊所形成的序列

D.路徑是不同頂點(diǎn)和不同邊所形成的集合

5.串的長度是指（）

A.串中所含不同字母的個(gè)數(shù)

B.串中所含字符的個(gè)數(shù)

C.串中所含不同字符的個(gè)數(shù)

D.串中所含非空格字符的個(gè)數(shù)

6.組成數(shù)據(jù)的基本單位是（）

A.數(shù)據(jù)項(xiàng)

B.數(shù)據(jù)類型

C.數(shù)據(jù)元素

D.數(shù)據(jù)變量

7.程序段的時(shí)間復(fù)雜度為（）

A.O（1）=

B.O（n）

C.O（n2

D.O(n3)

8.與串的邏輯結(jié)構(gòu)不同的數(shù)據(jù)結(jié)構(gòu)是（）

A.線性表

B.棧

C.隊(duì)列

D.樹

9.二叉樹的第i(i≥1)層上所擁有的結(jié)點(diǎn)個(gè)數(shù)最多為（）

A.

B.2i

C.

D.

10.設(shè)單鏈表中指針p指向結(jié)點(diǎn)A，若要刪除A的直接后繼，則所需修改指針的操作為（）

A.p-next=p-next-next

B.p=p-next

C.p=p-next-next

D.p-next=p

11.下列排序算法中，某一趟結(jié)束后未必能選出一個(gè)元素放在其最終位置上的是（）

A.堆排序

B.冒泡排序

C.直接插入排序

D.快速排序

12.設(shè)字符串S1=″ABCDEFG″，S2=″PQRST″，則運(yùn)算S=CONCAT(SUBSTR(S1,2,LENGTH(S2)),SUBSTR(S1,LENGTH(S2),2))后S的結(jié)果為()

A.″BCQR″

B.″BCDEF″

C.″BCDEFG″

D.″BCDEFEF″

13.在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A，并且A的左孩子的平衡因子為-1，右孩子的平衡因子為0，則使其平衡的調(diào)整方法為()

A.LL型

B.LR型

C.RL型

D.RR型

14.如果結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)，而且B為A的雙親，則B的度為（）

A.1

B.3

C.4

D.5

15.數(shù)據(jù)表A中每個(gè)元素距其最終位置較近，則最省時(shí)間的排序算法是（）

A.堆排序

B.插入排序

C.直接選擇排序

D.快速排序

16.在表長為n的順序表上做插入運(yùn)算，平均要移動的結(jié)點(diǎn)數(shù)為（）

A.n/4

B.n/3

C.n/2

D.n

17.順序表中有19個(gè)元素，第一個(gè)元素的地址為200，且每個(gè)元素占一個(gè)字節(jié)，則第14個(gè)元素的存儲地址為()

A.212

B.213

C.214

D.215

18.由頂點(diǎn)V1，V2，V3構(gòu)成的圖的鄰接矩陣為，則該圖中頂點(diǎn)V1的出度為(C)

A.0

B.1

C.2

D.3

19.元素的進(jìn)棧次序?yàn)锳，B，C，D，E，則退棧中不可能的序列是（）

A.A，B，C，D，E

B.B，C，D，E，A

C.E，A，B，C，D

D.E，D，C，B，A

20.由帶權(quán)為9，2，5，7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為（）

A.23

B.37

C.44

D.46

21.在已知尾指針的單循環(huán)鏈表中，插入一個(gè)新結(jié)點(diǎn)使之成為首結(jié)點(diǎn)，其算法的時(shí)間復(fù)雜度為（）

A.O（1）

B.（log2n）

C.O（n）

D.O(n2)

22.已知一個(gè)有序表為(13，18，24，35，47，50，62，83，90，115，134)，當(dāng)二分查找值為90的元素時(shí)，查找成功時(shí)需比較的次數(shù)為（）

A.1

B.2

C.3

D.4

23.在查找順序表各結(jié)點(diǎn)概率相等的情況下，順序按值查找某個(gè)元素的算法時(shí)間復(fù)雜度為（）

A.O(1)

B.O(n)

C.O(√n)

D.O(log2n)

24.下列各項(xiàng)鍵值序列中不是堆的為（）

A.{5，23，16，68，94，72，71，73}

B.{5，16，23，68，94，72，71，73}

C.{5，23，16，73，94，72，71，68}

D.{5，23，16，68，73，71，72，94}

25.在線性表的下列存儲結(jié)構(gòu)中進(jìn)行插入、刪除運(yùn)算，花費(fèi)時(shí)間最多的是（）

A.單鏈表

B.雙鏈表

C.順序表

D.單循環(huán)鏈表

26.在棧中進(jìn)行插入和刪除操作的一端稱為（）

A.棧頂

B.棧底

C.任意位置

D.指定位置

27.用n個(gè)值構(gòu)造一棵二叉排序樹，它的最大高度為

A..n/2

B.n

C.√n

D.log2n

28.冒泡排序的時(shí)間復(fù)雜度是（）

A.O(n2)

B.O(nlog2n)

C.O(n)

D.O(log2n)

29.設(shè)無向圖的鄰接表如題14圖所示，則該圖的邊數(shù)為（）

A.4

B.5

C.10

D.20

30.帶表頭結(jié)點(diǎn)鏈隊(duì)列的隊(duì)頭和隊(duì)尾指針分別為front和rear，則判斷隊(duì)空的條件為（）

A.front==rear

B.front!=NULL

C.rear!=NULL

D.front==NULL

二、填空題（共13題，共26分）

31.下列程序段的時(shí)間復(fù)雜度為________

32.數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)、________、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)4種。

33.線性表中所含結(jié)點(diǎn)的個(gè)數(shù)稱為________。

34.向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)新結(jié)點(diǎn)*p時(shí)，應(yīng)執(zhí)行_____和top=p操作。

35.設(shè)一個(gè)順序棧S，元素s1，s2，s3，s4，s5，s6依次進(jìn)棧，如果6個(gè)元素的退棧順序?yàn)閟2，s3，s4，s6，s5，s1，則順序棧的容量至少為_______。

36.若滿二叉樹的結(jié)點(diǎn)數(shù)為n，則其高度為______。

37.在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中，從樹根起，自上而下、從左到右地給所有結(jié)點(diǎn)編號。若編號為i的結(jié)點(diǎn)有父結(jié)點(diǎn)，那么其父結(jié)點(diǎn)的編號為________。

38.深度為k的二叉樹，結(jié)點(diǎn)數(shù)最多有_______個(gè)。

39.某二叉樹的后根遍歷為ABKCBPM，則該二叉樹的根為_____