??2021年10月自考02142數(shù)據(jù)結(jié)構(gòu)導論真題及答案
摘要:?2021年10月自考剛剛考完,考生們最為關(guān)注的就是自考真題及答案了,全國2021年10月自考02142數(shù)據(jù)結(jié)構(gòu)導論真題已經(jīng)公布,各位考生可以參考。
全國2021年10月高等教育自學考試數(shù)據(jù)結(jié)構(gòu)導論試題
課程代碼: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.不屬于數(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.設指針變量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.設一棵完全二叉樹中有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ù)組a[m][n].假設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.設有序表中的元素為(13.18.24.35.47.50.62).則在其中利用二分法查找值為24的元素需要經(jīng)過比較的次數(shù)是
A.1
B.2
C.3
D.4
15.就平均時間性能而言,若需以O(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.假設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.設有編號為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),設散列表表長為13.散列函數(shù)H(key)= key mod 13處理沖突的方法為線性探測法.請給出散列表。
四、算法設計題:本大題共2小題,每小題7分,共14分。
34.讀入n=100個整數(shù)到一個數(shù)組中.寫出實現(xiàn)將該組數(shù)進行逆置的算法.并分析算法的空間復雜度。
35.試寫出二分查找的遞歸算法。
延伸閱讀
- 2025年4月自考政治經(jīng)濟學(中級)全真模擬試題
- 2023年10月自考00257票據(jù)法真題
- 2023年10月自考00249國際私法真題
- 2023年10月自考00246國際經(jīng)濟法概論真題
- 2023年10月自考00245刑法學真題
- 2023年10月自考00186國際商務談判真題
自考微信公眾號
掃碼添加
自考備考資料免費領取
去領取