??2021年10月自考02142數據結構導論真題及答案

全國2021年10月高等教育自學考試數據結構導論試題

課程代碼:02142

1.請考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。

2.答題前,考生務必將自己的考試課程名稱、姓名、準考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規(guī)定的位置上。

選擇題部分

注意事項:每小題選出答案后,用2B鉛筆把答題紙上對應題目的答案標號涂黑。如需改動,用橡皮擦干凈后,再選涂其他答案標號。不能答在試題卷上。

一、單項選擇題:本大題共15小題，每小題2分,共30分。在每小題列出的備選項中只有一項是最符合題目要求的,請將其選出。

1.程序段s=i=0;do {i=i+1;s=s+i;}while(i< = n)的時間復雜度為

A. O(n)

B. O( nlogzn)

C. O(n2)

D. 0(1)

2.不屬于數據組織三個層次的是

A.數據

B.數據元素

C.數據類型

D.數據項

3.具有先進先出特征的數據結構是

A.堆棧

B.隊列

C.最小堆

D.完全二叉樹

4.一個棧的輸入序列為1234.則下列序列中可能是棧的輸出序列的是

A.231 4

B.4123

C.31 24

D.34 1 2

5.設指針變量front表示鏈隊列的隊頭指針.指針變量rear表示鏈隊列的隊尾指針，指針變量s指向將要人隊列的結點X.則入隊列的操作序列為

A. front->nexl=s; front=s;

B. s->next= rear;rear=s;

C. rear->next= s;rear= s;

D. s->next = front; front=s;

6.設一棵完全二叉樹中有65個結點,則該完全二叉樹的深度為.

A.5

B.6

C.7

D.8

7.有n個葉結點的哈夫曼樹的結點總數為

A.2n-1

B.2n

C.2n+1

D.2n2

8.先序遍歷與中序遍歷結果相同的二叉樹

A.根結點無左孩子

B.根結點無右孩子

C.所有結點只有左子樹

D.所有結點只有右子樹

9.設有一個二維數組a[m][n].假設a[0]C0]存放位置為644.a[2][2]存放位置為676.每個元素占一個存儲空間,則a[3][3]存放位置為

A.678

B.688

C.692

D.696

10.線性表若采用鏈表存儲結構.內存中可用存儲單位的地址

A.必須是連續(xù)的

B.有一部分必須是連續(xù)的

C.一定是不連續(xù)的

D.連續(xù)不連續(xù)都可以

11.一個具有n個頂點的無向完全圖的邊數為

A.0

B. n(n-1)/2

C. n(n-1)

D. n(n+1)

12.對于線性表(7.34.55.25.64.46.20.10)進行散列存儲時,若散列函數為H(K)=K %9.則散列地址為1的元素個數是

A.1

B.2

C.3

D.4

13.對題13圖中的樹進行遍歷后可以得到序列ABCD的遍歷方式是

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.層次遍歷

14.設有序表中的元素為(13.18.24.35.47.50.62).則在其中利用二分法查找值為24的元素需要經過比較的次數是

A.1

B.2

C.3

D.4

15.就平均時間性能而言,若需以O(nlog2n)的時間復雜度完成對數組的排序,則可選擇的排序方法是

A.快速排序

B.冒泡排序

C.直接選擇排序

D.直接插人排序

非選擇題部分

注意事項:用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上,不能答在試題卷上。

二、 填空題:本大題共13空,每空2分,共26分。

16.根據圖的定義,圖中頂點的最少數目是      ▲      。

17.1976年瑞士計算機科學家Niklaus Wirth 曾提出一個著名公式:算法十數據結構      ▲      。

18.數據的存儲結構有順序存儲鏈式存儲、散列存儲和      ▲      存儲。

19.一個算法的時空性是指該算法的時間性能和空間性能.其中空間性能是算法需要的      ▲      。

20.用順序存儲實現的線性表稱為順序表，一般使用      ▲      來表示。

21.在單鏈表中,指針p所指的結點為最后一個結點的條件是      ▲      。

22.循環(huán)隊列被定義為結構體類型,含有三個域:data. front和rear,則循環(huán)隊列cQ為空的條      ▲      

23.假設m行n列的矩陣有t個非零元素.當t<<mwn時.則稱矩陣為      ▲      。

24.順序隊列需要預先定義隊列的容量.一般將數組的首尾相接,形成循環(huán)隊列.這樣可以解決      ▲      問題。

25.樹上任一結點所擁有的子樹的數目稱為該結點的      ▲      。

26.一棵二叉樹的最少結點個數為      ▲      。

27.含有n個頂點的連通圖中任意一條簡單路徑.其長度最大為      ▲      。

28.要完全避免散列所產生的“堆積"現象,通常采用      ▲      解 決沖突。

三、應用題:本大題共5小題,每小題6分,共30分。

29.設有編號為1.2,3,4的四輛列車,順序進人一個棧式結構的站臺,若列車2最先開出,則列

車出站可能的順序有幾種?并寫出這四輛列車所有可能的出站順序。

30.將題30圖所示的森林轉換成二叉樹。

31.寫出題31圖所示的有向帶權圖的鄰接矩陣。

32.已知題32圖所示的二叉排序樹中各結點的值分別為1~9.請寫出圖中結點A~I所對應的值。

33.已知鍵值序列{11.2.13.26.5.18.4.9),設散列表表長為13.散列函數H(key)= key mod 13處理沖突的方法為線性探測法.請給出散列表。

四、算法設計題:本大題共2小題,每小題7分,共14分。

34.讀入n=100個整數到一個數組中.寫出實現將該組數進行逆置的算法.并分析算法的空間復雜度。

35.試寫出二分查找的遞歸算法。