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

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

課程代碼:02142

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

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

選擇題部分

注意事項(xiàng):每小題選出答案后,用2B鉛筆把答題紙上對(duì)應(yīng)題目的答案標(biāo)號(hào)涂黑。如需改動(dòng),用橡皮擦干凈后,再選涂其他答案標(biāo)號(hào)。不能答在試題卷上。

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

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

A. O(n)

B. O( nlogzn)

C. O(n2)

D. 0(1)

2.不屬于數(shù)據(jù)組織三個(gè)層次的是

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

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

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

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

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

A.堆棧

B.隊(duì)列

C.最小堆

D.完全二叉樹

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

A.231 4

B.4123

C.31 24

D.34 1 2

5.設(shè)指針變量front表示鏈隊(duì)列的隊(duì)頭指針.指針變量rear表示鏈隊(duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁岁?duì)列的結(jié)點(diǎn)X.則入隊(duì)列的操作序列為

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個(gè)結(jié)點(diǎn),則該完全二叉樹的深度為.

A.5

B.6

C.7

D.8

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

A.2n-1

B.2n

C.2n+1

D.2n2

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

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

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

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

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

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

A.678

B.688

C.692

D.696

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

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

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

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

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

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

A.0

B. n(n-1)/2

C. n(n-1)

D. n(n+1)

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

A.1

B.2

C.3

D.4

13.對(duì)題13圖中的樹進(jìn)行遍歷后可以得到序列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.就平均時(shí)間性能而言,若需以O(shè)(nlog2n)的時(shí)間復(fù)雜度完成對(duì)數(shù)組的排序,則可選擇的排序方法是

A.快速排序

B.冒泡排序

C.直接選擇排序

D.直接插人排序

非選擇題部分

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

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

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

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

18.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)、散列存儲(chǔ)和      ▲      存儲(chǔ)。

19.一個(gè)算法的時(shí)空性是指該算法的時(shí)間性能和空間性能.其中空間性能是算法需要的      ▲      。

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

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

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

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

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

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

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

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

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

三、應(yīng)用題:本大題共5小題,每小題6分,共30分。

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

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

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

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

32.已知題32圖所示的二叉排序樹中各結(jié)點(diǎn)的值分別為1~9.請(qǐng)寫出圖中結(jié)點(diǎn)A~I所對(duì)應(yīng)的值。

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

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

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

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