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

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

1.[單選題]一個公司的組織機構(gòu)是1名公司經(jīng)理領導若干名部門負責人，每個部門負責人領導若干名部門員工，則適合于描述該公司組織機構(gòu)的邏輯結(jié)構(gòu)是()

A.線性表

B.隊列

C.樹

D.圖

2.[單選題]計算n！整數(shù)n≥0）的遞歸算法是：intFactorial(intn){if(n==0)return1;elsereturnn*Factorial(n-1);}其時間復雜度為()

A.O(n)

B.O(log2n)

C.O(nC)

D.O(n2)

3.[單選題]將一個由指針q指向的結(jié)點插在單鏈表中由指針p所指向的結(jié)點之后的操作是()

A.p=q;

B.p-next=q;

C.q-next=p-next;p-next=q;

D.p-next=q;q-next=p-next;

4.[單選題]設初始棧為空，s表示入棧操作，x表示出棧操作，則合法的操作序列是()

A.sxxssxxs

B.ssxsxxxs

C.ssxxxssx

D.sssxxxsx

5.[單選題]將遞歸形式描述的算法改寫為功能等價的非遞歸形式描述的算法，通常應設置的輔助結(jié)構(gòu)是()

A.順序表

B.單鏈表

C.棧

D.隊列

6.[單選題]設長度為n的隊列用單循環(huán)鏈表表示（假設表尾結(jié)點為當前隊列的隊尾元素），若只設頭指針，則入隊操作、出隊操作的時間復雜度分別為()

A.O(n)、O(1)

B.O(1)、O(1)

C.O(1)、O(n)

D.O(n)、O(n)

7.[單選題]若采用順序存儲（一維數(shù)組）結(jié)構(gòu)存儲一棵如題7圖所示的二叉樹，根結(jié)點1的下標為1，則結(jié)點4的下標為()

A.4

B.5

C.6

D.7

8.[單選題]按層序（自頂向下、從左到右）遍歷二叉樹時需借助隊列作輔助結(jié)構(gòu)。對高度為3的滿二叉樹進行層序遍歷時，隊列中所出現(xiàn)的元素個數(shù)最多是()

A.1

B.2

C.3

D.4

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

A.120

B.110

C.108

D.100

10.[單選題]已知含6個頂點(v0，v1，v2，v3，v4，v5)的無向圖的鄰接矩陣如題10圖所示，則從頂點V0出發(fā)進行深度優(yōu)先搜索可能得到的頂點訪問序列為()

A.{v0，v1，v2，v5，v4，v3}

B.{v0，v1，v2，v3，v4，v5}

C.{v0，v1，v5，v2，v3，v4}

D.{v0，v1，v4，v5，v2，v3}

11.[單選題]“在旅游時從某地出發(fā)要去某個目的地，如何選擇線路才能使得路程最短”，從圖的應用角度，最合理的解決方案是()

A.深度優(yōu)先搜索

B.最小生成樹

C.拓撲排序

D.最短路徑

12.[單選題]二分查找算法的時間復雜度是()

A.O(n2)

B.O(nlog2n)

C.O(n)

D.O(log2n)

13.[單選題]已知一個散列表如題13圖所示，其散列函數(shù)為H(key)=keymod11，采用線性探測法處理沖突，則下一個進入散列表的關鍵字49的地址為()

A.2

B.3

C.8

D.9

14.[單選題]用冒泡排序方法對n個待排序的鍵值進行排序，則整個排序過程所歷經(jīng)的趟數(shù)是()

A.1

B.n-1

C.n

D.至少為1、至多為n-1

15.[單選題]現(xiàn)對關鍵字序列{6，1，4，3，7，2，8，5}進行快速排序，那么以第1個元素6為工作基準的第一趟快速排序結(jié)束的結(jié)果序列為()

A.{5，1，4，3，2，6，8，7}

B.{5，1，4，3，2，6，7，8}

C.{5，1，4，3，6，2，8，7}

D.{8，7，6，5，4，3，2，1}

16.[填空題]計算機圖靈獎獲得者N.Wirth曾提出一個著名公式：算法+________=程序。

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

18.[填空題]設某非空雙向鏈表，其結(jié)點結(jié)構(gòu)為，若要刪除指針q所指向的結(jié)點，則需執(zhí)行如下兩條關鍵語句：q-prior-next=q-next;_________。

19.[填空題]大小為MaxSize的循環(huán)隊列中，若front與rear分別表示隊頭元素和隊尾元素的位置，則判斷該循環(huán)隊列為空的條件表達式是________。

20.[填空題]對稀疏矩陣進行壓縮存儲的一種方法是________。

21.[填空題]若一棵二又樹中只有葉結(jié)點和左右子樹皆非空的結(jié)點，設二叉樹葉結(jié)點個數(shù)為s，則左右子樹皆非空的結(jié)點個數(shù)是________。

22.[填空題]若一棵二叉樹的前序、中序、后序遍歷的結(jié)果序列均相同，則該二叉樹一定是________或是只有一個根結(jié)點的二叉樹。

23.[填空題]采用鄰接表表示一有向圖，若圖中某頂點的入度和出度分別為D1和D2，則該頂點所對應的單鏈表的結(jié)點個數(shù)為________。

24.[填空題]對有序順序表(07，12，15，18，27，32，46，65，83)用二分法查找，若查找成功，則查找所需比較次數(shù)最多的鍵值是________。

25.[填空題]由n個鍵值構(gòu)造的二叉排序樹，在等概率查找的假設下，查找成功的平均查找長度的最大值可能達到________。

26.[填空題]對關鍵字序列{26，36，41，38，44，15，68，12，06，51}，設HashSize=13，H(key)=keymodHashSize，并用鏈地址法解決沖突，則構(gòu)造得到的散列表中的指針HP[________]所指向的一個單鏈表(同義詞子表)最長。

27.[填空題]在直接選擇、直接插入、冒泡、快速等四種排序方法中，經(jīng)一趟排序后，任一元素都不能確定其最終位最的排序方法是________。

28.[填空題]若采用直接選擇排序方法對初始關鍵字序列{5，3，5，1}進行升序排序（其中包括2個值相同的關鍵字，均為5），則排序結(jié)束后的關鍵字序列是________。

29.[案例題]如題29圖所示，利用同一循環(huán)向量空間實現(xiàn)兩個隊列，其類型Queue2定義如下：typedefstruct{DataTypedata[MaxSize];intfront[2],length[2];}Queue2;對于i=0或1，front[i]和length[i]分別為第i個隊列的隊頭位置和實際長度。分別寫出這兩個隊列滿的條件。

30.[案例題]將如題30圖所示的含有3棵樹的森林轉(zhuǎn)換成相應的二又樹，并分別給出該森林先序、中序遍歷的結(jié)果序列和相應的二叉樹的先序、中序遍歷結(jié)果序列，根據(jù)所得到的遍歷結(jié)果序列你會得到什么結(jié)論？

31.[案例題]對一個圖G，按順序輸入頂點對1，3、1，2、2，4、2，3、4，3、4，2、4，1，根據(jù)建立圖的鄰接表的算法畫出相應的鄰接表，并寫出在該鄰接表上，從頂點2開始搜索得到的一個深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列。

32.[案例題]設順序存儲的線性表共有100個元素，按分塊查找（索引查找）的要求等分成5塊。若對索引表采用二分查找來確定塊，并在確定的塊中進行順序查找，則在概率相等的情況下，分塊查找成功時的平均查找長度是多少（要求利甩∑PiCi來計算并給出詳細算式）？

33.[案例題]若采用堆排序方法對關鍵字序列{265，301，751，129，937，863，742，694，076，438}進行升序排序，寫出其每趟排序結(jié)束后的關鍵字序列。

34.[案例題]假設以帶頭結(jié)點的單鏈表表示線性表，單鏈表的類型定義如下：

typedefstructnode{intdata;

structnode*next;}LinkedNode，*LinkedList;

編寫算法，刪除值無序的線性表中值最大的元素（表中各元素的值互不相同）。

35.[案例題]假設樹的存儲結(jié)構(gòu)采用孩子兄弟表示法，寫出樹的先序