??2021年10月自考02142數(shù)據(jù)結(jié)構(gòu)導論真題及答案

全國2021年10月高等教育自學考試數(shù)據(jù)結(jié)構(gòu)導論試題

課程代碼:02142

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

2.答題前,考生務(wù)必將自己的考試課程名稱、姓名、準考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規(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.不屬于數(shù)據(jù)組織三個層次的是

A.數(shù)據(jù)

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

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

D.數(shù)據(jù)項

3.具有先進先出特征的數(shù)據(jù)結(jié)構(gòu)是

A.堆棧

B.隊列

C.最小堆

D.完全二叉樹

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

A.231 4

B.4123

C.31 24

D.34 1 2

5.設(shè)指針變量front表示鏈隊列的隊頭指針.指針變量rear表示鏈隊列的隊尾指針，指針變量s指向?qū)⒁岁犃械慕Y(jié)點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.設(shè)一棵完全二叉樹中有65個結(jié)點,則該完全二叉樹的深度為.

A.5

B.6

C.7

D.8

7.有n個葉結(jié)點的哈夫曼樹的結(jié)點總數(shù)為

A.2n-1

B.2n

C.2n+1

D.2n2

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

A.根結(jié)點無左孩子

B.根結(jié)點無右孩子

C.所有結(jié)點只有左子樹

D.所有結(jié)點只有右子樹

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

A.678

B.688

C.692

D.696

10.線性表若采用鏈表存儲結(jié)構(gòu).內(nèi)存中可用存儲單位的地址

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

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

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

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

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

A.0

B. n(n-1)/2

C. n(n-1)

D. n(n+1)

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

A.1

B.2

C.3

D.4

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

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.層次遍歷

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

A.1

B.2

C.3

D.4

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

A.快速排序

B.冒泡排序

C.直接選擇排序

D.直接插人排序

非選擇題部分

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

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

16.根據(jù)圖的定義,圖中頂點的最少數(shù)目是      ▲      。

17.1976年瑞士計算機科學家Niklaus Wirth 曾提出一個著名公式:算法十數(shù)據(jù)結(jié)構(gòu)      ▲      。

18.數(shù)據(jù)的存儲結(jié)構(gòu)有順序存儲鏈式存儲、散列存儲和      ▲      存儲。

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

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

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

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

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

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

25.樹上任一結(jié)點所擁有的子樹的數(shù)目稱為該結(jié)點的      ▲      。

26.一棵二叉樹的最少結(jié)點個數(shù)為      ▲      。

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

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

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

29.設(shè)有編號為1.2,3,4的四輛列車,順序進人一個棧式結(jié)構(gòu)的站臺,若列車2最先開出,則列

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

30.將題30圖所示的森林轉(zhuǎn)換成二叉樹。

31.寫出題31圖所示的有向帶權(quán)圖的鄰接矩陣。

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

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

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

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

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