自考02142《數(shù)據(jù)結(jié)構(gòu)導論》真題（2022.4）-1

精品文檔-下載后可編輯自考02142《數(shù)據(jù)結(jié)構(gòu)導論》真題及（2022.4）自考02142《數(shù)據(jù)結(jié)構(gòu)導論》真題及答案解析（2022.4）

1.[單選題]任意兩個結(jié)點之間都沒有鄰接關(guān)系，組織形式松散，這種組織形式稱為()

A.集合

B.線性結(jié)構(gòu)

C.樹形結(jié)構(gòu)

D.圖結(jié)構(gòu)

2.[單選題]表示數(shù)據(jù)元素之間的關(guān)聯(lián)方式通常采用的存儲方式是()

A.順序存儲方式和索引存儲方式

B.鏈式存儲方式和散列存儲方式

C.順序存儲方式和鏈式存儲方式

D.鏈式存儲方式和索引存儲方式

3.[單選題]下面幾種算法時間復雜度階數(shù)中，最小的是()

A.O(log2n)

B.O(n)

C.O(n2)

D.O(2n)

4.[單選題]雙向循環(huán)鏈表中，在指針P所指結(jié)點的后面插入一個新結(jié)點*t，正確的語句為()

A.t-prior-P;t-next=p-next;p-next-prior=t;p-next=t;

B.t-prior=p;t-next=p-next;p-next=t;

C.t-prior-P;p-next-prior=t;t-next=p-next;P-next=t;

D.p-next--prior=t;p-next=t;

5.[單選題]棧的修改原則是()

A.先進先出

B.后進先出

C.?？談t進

D.棧滿則出

6.[單選題]設有一順序隊列SQ，已知尾指針rear隊列的最大長度-1，則數(shù)據(jù)x進行入隊列操作的語句為()

A.SQ.front=SQ.front+1;

B.SQ.front=SQ.rear+1;

C.SQ.front=SQ.front+1;SQ.dataF[Sq.front]=x;

D.SQ.rear=SQ.rear+1;SQ.datar[SQ.rear]=x;

7.[單選題]一個數(shù)組的第一個元素的存儲地址是100，每個元素占2存儲單元，則第5個元素的存儲地址是()

A.105

B.108

C.115

D.118

8.[單選題]樹中葉子的度是()

A.0

B.1

C.2

D.3

9.[單選題]將一棵有n個結(jié)點的完全二叉樹按層編號，若編號i所對應的結(jié)點為A，且i1，則A的雙親的編號為()

A.i

B.i/2

C.

D.

10.[單選題]含有100個結(jié)點的二叉樹采用二叉鏈表存儲時，空指針域NULL的個數(shù)是()

A.99個

B.100個

C.101個

D.200個

11.[單選題]一個具有n個頂點的有向完全圖的弧數(shù)為()

A.n(n-1)/2

B.n(n-1)

C.n2/2

D.n2

12.[單選題]圖的深度優(yōu)先搜索遍歷類似于樹的()

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.層次遍歷

13.[單選題]靜態(tài)查找表指對查找表只進行兩項操作，即()

A.插入和刪除一個數(shù)據(jù)元素

B.查找表中某一元素和插入一個數(shù)據(jù)元素

C.讀取表中“特定”數(shù)據(jù)元素和刪除一個數(shù)據(jù)元素

D.查找表中某一元素和讀取表中“特定”數(shù)據(jù)元素

14.[單選題]若在線性表中采用二分查找法查找元素，該線性表應該()

A.元素按值有序，且采用鏈式存儲結(jié)構(gòu)

B.元素按值無序，且采用鏈式存儲結(jié)構(gòu)

C.元素按值有序，且采用順序存儲結(jié)構(gòu)

D.元素按值無序，且采用順序存儲結(jié)構(gòu)

15.[單選題]下列排序方法中不穩(wěn)定的是()

A.冒泡排序

B.二路歸并

C.堆排序

D.直接插入排序

16.[填空題]從宏觀上看，數(shù)據(jù)、數(shù)據(jù)元素和_________反映了數(shù)據(jù)組織的三個層次。

17.[填空題]線性表、棧和隊列中的元素具有相同的邏輯結(jié)構(gòu)，即_________。

18.[填空題]一個算法的時空性是指該算法的時間性能和_________。

19.[填空題]為了便于運算的實現(xiàn)，在單鏈表的第一個結(jié)點之前增設一個類型相同的結(jié)點，稱之為_________。

20.[填空題]假設一個8階的上三角矩陣A按照列優(yōu)先順序壓縮存儲在一維數(shù)組8中，則B數(shù)組的大小應為_________。

21.[填空題]在棧中，允許進行插入和刪除操作的一端稱為_________。

22.[填空題]即使輸入非法數(shù)據(jù)，算法也能適當?shù)刈龀龇磻蜻M行處理，不會產(chǎn)生預料不到的運行結(jié)果，這種評價算法好壞的因素稱為_________。

23.[填空題]設棧S的初始狀態(tài)為空，若元素a，b，C，d依次進棧，得到的出棧序列是c，d，b，a，則棧的容量至少是_________。

24.[填空題]若一棵完全二叉樹有14個結(jié)點，則它的深度為_________。

25.[填空題]樹的雙親表示法由一個一維數(shù)組構(gòu)成，數(shù)組的每個分量包含_________和雙親域兩個域。

26.[填空題]如果包含n個頂點的連通圖G的一個子圖G’的邊數(shù)大于n-1，則G’中一定有_________。

27.[填空題]在含有9個元素的有序表(2，4，12，18，23，37，49，51，68)中二分查找關(guān)鍵字（關(guān)鍵字即為數(shù)據(jù)元素的值）為37的元素時，所需進行的比較次數(shù)為_________次。

28.[填空題]從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在已排序序列的合適位置，該排序方法稱為_________排序法。

29.[案例題]設A、B、C、D、E五個元素依次進棧（進棧后可立即出棧），問能否得到下列序列：

（1）A，B，C，D，E；

（2）A，C，E，B，D

若能得到，剛給出該序列的操作過程（用push(A)表示A進棧，pop(A)表示A出棧）；若不能，則說明理由。

30.[案例題]已知一棵二叉樹的先序遍歷結(jié)果為ABDCEF，中序遍歷結(jié)果為DBAECF，試畫出這棵二叉樹，并寫出這棵二叉樹的后序遍歷序列。

31.[案例題]畫出題31圖所示森林經(jīng)轉(zhuǎn)換后所對應的二叉樹。

32.[案例題]已知如題32圖所示的無向帶權(quán)圖，請從結(jié)點A出發(fā)，用普里姆(Prim)算法求其最小生成樹，并畫出過程示意圖。

33.[案例題]將一組鍵值{83，69，41，22，15，33，8，76}應用二路歸并排序算法從小到大排序，試寫出各趟排序的結(jié)果。

34.[案例題]設計一個算法實現(xiàn)以下功能：在整型數(shù)組A[n]中查找值為k的元素，若找到，輸出其位置i(0≤i≤n-1)，否則輸出-1作為標志。

35.[案例題]已知二叉鏈表的類