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

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

1.[單選題]線(xiàn)性表若采用鏈表存儲(chǔ)結(jié)構(gòu)，內(nèi)存中可用存儲(chǔ)單位的地址

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

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

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

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

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

A.678

B.688

C.692

D.696

3.[單選題]先序遍歷與中序遍歷結(jié)果相同的二叉樹(shù)

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

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

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

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

4.[單選題]有n個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為

A.2n－1

B.2n

C.2n＋1

D.2n2

5.[單選題]設(shè)一棵完全二叉樹(shù)中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹(shù)的深度為

A.5

B.6

C.7

D.8

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

A.front-next=s;front=s;

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

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

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

7.[單選題]一個(gè)棧的輸入序列為1234,則下列序列中可能是棧的輸出序列的是

A.2314

B.4123

C.3124

D.3412

8.[單選題]具有先進(jìn)先出特征的數(shù)據(jù)結(jié)構(gòu)是

A.堆棧

B.隊(duì)列

C.最小堆

D.完全二叉樹(shù)

9.[單選題]不屬于數(shù)據(jù)組織三個(gè)層次的是

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

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

C.數(shù)據(jù)類(lèi)型

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

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

A.O(n)

B.O(nlog2n)

C.O(n2)

D.O(1)

11.[單選題]對(duì)題13圖中的樹(shù)進(jìn)行遍歷后可以得到序列ABCD的遍歷方式是

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.層次遍歷

12.[單選題]對(duì)于線(xiàn)性表(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.[單選題]一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖的邊數(shù)為

A.0

B.n(n-1)/2

C.n(n-1)

D.n(n+1)

14.[單選題]就平均時(shí)間性能而言,若需以O(shè)(nlog2n)的時(shí)間復(fù)雜度完成對(duì)數(shù)組的排序,則可選擇的排序方法是

A.快速排序

B.冒泡排序

C.直接選擇排序

D.直接插入排序

15.[單選題]設(shè)有序表中的元素為(13,18,24,35,47,50,62)，則在其中利用二分法查找值為24的元素需要經(jīng)過(guò)比較的次數(shù)是

A.1

B.2

C.3

D.4

16.[案例題]根據(jù)圖的定義，圖中頂點(diǎn)的最少數(shù)目是______。

17.[案例題]一棵二叉樹(shù)的最少結(jié)點(diǎn)個(gè)數(shù)為()。

18.[填空題]要完全避免散列所產(chǎn)生的“堆積”現(xiàn)象，通常采用（）解決沖突。

19.[填空題]含有n個(gè)頂點(diǎn)的連通圖中任意一條簡(jiǎn)單路徑，其長(zhǎng)度最大為（）。

20.[填空題]樹(shù)上任一結(jié)點(diǎn)所擁有的子樹(shù)的數(shù)目稱(chēng)為該結(jié)點(diǎn)的（）。

21.[填空題]順序隊(duì)列需要預(yù)先定義隊(duì)列的容量，一般將數(shù)組的首尾相接，形成循環(huán)隊(duì)列，這樣可以解決“（）”問(wèn)題。

22.[填空題]假設(shè)m行n列的矩陣有t個(gè)非零元素，當(dāng)t

31.[問(wèn)答題]寫(xiě)出題31圖所示的有向帶權(quán)圖的鄰接矩陣。

32.[問(wèn)答題]將題30圖所示的森林轉(zhuǎn)換成二叉樹(shù)。

33.[問(wèn)答題]設(shè)有編號(hào)為1,2,3,4的四輛列車(chē),順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái),若列車(chē)2最先開(kāi)出,則列車(chē)出站可能的順序有幾種?并寫(xiě)出這四輛列車(chē)所有可能