2022年自考本科數(shù)據(jù)結(jié)構(gòu)模擬真題

1、全國4月自學(xué)考試數(shù)據(jù)構(gòu)造試題課程代碼：02331請考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。選擇題部分注意事項：1.答題前，考生務(wù)必將自己的考試課程名稱、姓名、準考證號用黑色筆跡的簽字筆或鋼筆填寫在答題紙規(guī)定的位置上。2.每題選出答案后，用2B鉛筆把答題紙上相應(yīng)題目的答案標號涂黑。如需改動，用橡皮擦干凈后，再選涂其她答案標號。不能答在試題卷上。一、單選題（本大題共15小題，每題2分，共30分）在每題列出的四個備選項中只有一種是符合題目規(guī)定的，請將其選出并將“答題紙”的相應(yīng)代碼涂黑。錯涂、多涂或未涂均無分。1.與數(shù)據(jù)存儲構(gòu)造無關(guān)的概念是A.棧B.鏈表C.順序表D.二叉鏈表2.順序表中有10

2、個數(shù)據(jù)元素，若第一種元素的存儲地址是1000，則最后一種元素地址是1036，第5個元素的地址是A1010B.1016C.1018D.10193.設(shè)棧的初始狀態(tài)為空，元素1、2、3、4、5、6依次入棧，得到的出棧序列是（2,4,3,6,5,1）,則棧的容量至少是A.2B.3C.4D.64.下列有關(guān)隊列的論述中,錯誤的是A.隊列是一種先進先出的線性表B.隊列是一種后進后出的線性表C.循環(huán)隊列中進行出隊操作時要判斷隊列與否為空D.在鏈隊列中進行入隊操作時要判斷隊列與否為滿5.對稀疏矩陣進行壓縮存儲的目的是A.便于運算B.節(jié)省存儲空間C.便于輸入輸出D.減少時間復(fù)雜度6.一棵二叉樹的第7層上最多具有的

3、結(jié)點數(shù)為A.14B.64C.127D.1287.下列選項為完全二叉樹的是8.用鄰接表表達n個頂點e條邊的無向圖,其邊表結(jié)點的總數(shù)是A. neB. eC. 2eD. n+e9.無向圖中所有頂點的度數(shù)之和與所有邊數(shù)之比是A.1/2B.1C.2D.410.采用鄰接矩陣存儲圖時,廣度優(yōu)先搜索遍歷算法的時間復(fù)雜度為A. O（n）B. O（n+e）C. O（n2）D. O（n3）11.對序列（15,9,7,8,20,-1,4）進行排序,若一趟排序后的成果為（-1,15,9,7,8,20,4）,則采用的排序措施是A.歸并排序B.迅速排序C.直接選擇排序D.冒泡排序12.比較次數(shù)與待排序列初始狀態(tài)無關(guān)的排序措

4、施是A.迅速排序B.冒泡排序C.直接插入排序D.直接選擇排序13.查找較快,且插入和刪除操作也比較以便的查找措施是A.分塊查找B.二分查找C.順序查找D.折半查找14.下列有關(guān)m階B樹的論述中,錯誤的是A.根結(jié)點至多有m棵子樹B.所有葉子都在同一層次上C.每個非根內(nèi)部結(jié)點至少有棵子樹D.結(jié)點內(nèi)部的核心字可以是無序的15.在散列查找中解決沖突時,可以采用開放定址法。下列不是開放定址法的是A.線性探查法B.二次探查法C.雙重散列法D.拉鏈法非選擇題部分注意事項：用黑色筆跡的簽字筆或鋼筆將答案寫在答題紙上,不能答在試題卷上。二、填空題（本大題共10小題,每題2分,共20分）16.數(shù)據(jù)構(gòu)造研究的內(nèi)容涉

5、及數(shù)據(jù)的邏輯構(gòu)造、_和數(shù)據(jù)的運算。17.頭指針為L的帶頭結(jié)點的雙循環(huán)鏈表,結(jié)點的前趨指針域為prior,后繼指針域為next,判斷該鏈表為空的條件是_。18.普里姆（Prim）算法完畢的功能是求圖的_。19.若三維數(shù)組a456的基地址是100,每個元素占用2個存儲單元,則數(shù)組a中最后一種元素的存儲地址是_。20.二叉樹的線索鏈表運用_寄存遍歷時得到的前趨或后繼結(jié)點的指針。21.采用鄰接矩陣存儲n個頂點e條邊的無向圖,其鄰接矩陣的大小為_。22.若無向圖中任意兩個不同的頂點間均有途徑,則稱該圖為_。23.在直接插入排序、冒泡排序和迅速排序中,平均時間性能最佳的是_。24.假設(shè)m個核心字互為同義詞

6、,若用線性探查法把這m個核心字存入散列表中,至少要進行的探查次數(shù)是_。25.順序查找算法的平均時間復(fù)雜度為_。三、解答題（本大題共4小題,每題5分,共20分）26.用X代表進棧操作,S代表出棧操作。給出運用棧將字符串a(chǎn)*b-c變化為ab*c-的操作環(huán)節(jié)。例如：將ABC變化為BCA,則其操作環(huán)節(jié)為XXSXSS。27.19,6,12,5,38,3,13,4）,為這8個字符設(shè)計哈夫曼編碼。畫出哈夫曼樹并給出編碼。規(guī)定在構(gòu)造哈夫曼樹的過程中,權(quán)值較小結(jié)點放在左側(cè),編碼時左分支生成代碼0,右分支生成代碼1。28.設(shè)圖以鄰接表存儲,如題28圖所示。（1）寫出從頂點v1出發(fā)圖的深度優(yōu)先搜索遍歷序列。（2）寫

7、出從頂點v1出發(fā)圖的廣度優(yōu)先搜索遍歷序列。29.（1）一種排序措施穩(wěn)定的含義是什么？（2）迅速排序是穩(wěn)定的嗎？舉例闡明。四、算法閱讀題（本大題共4小題,每題5分,共20分）30.閱讀下列算法,并回答問題：void f30（SeqStack S） int k=0；CirQueue Q；SeqStack T；InitQueue（&Q）； /初始化隊列QInitStack（&T）； /初始化棧Twhile （!StackEmpty（&S） k+;if （k%2!=0） Push（&T, Pop（&S）;else EnQueue（&Q, Pop（&S）; /第一種循環(huán)while （!QueueEmpt

8、y（&Q） /第二個循環(huán)Push（&S, DeQueue（&Q）;while（!StackEmpty（&T） /第三個循環(huán)Push（&S,Pop（&T）；設(shè)棧S=（1,2,3,4,5,6,7）,其中7為棧頂元素。調(diào)用函數(shù)f30（S）后,（1）第一種循環(huán)結(jié)束后,棧T和隊列Q中的內(nèi)容各是什么？（2）第三個循環(huán)語句結(jié)束后,棧S中的內(nèi)容是什么？31.二叉樹的二叉鏈表類型定義如下：typedef struct node DataType data；struct node *lchild, *rchild; BinNode;typedef BinNode *BinTree；閱讀下列算法,并回答問題：voi

9、d f31（BinTree BT） BinNode *s;if （BT） s=BT-lchild；BT-lchild=BT-rchild;BT-rchild=s；f31（BT-lchild）；f31（BT-rchild）；（1）該算法的功能是什么？（2）如下算法功能與否等價于上面的算法？void f3la（BinTree BT） BinNode *s;if（BT） f31a（BT-lchild）；f31a（BT-rchild）；s=BT-lchild;BT-lchild=BT-rchild;BT-rchild=s；32.單鏈表類型定義如下：typedef struct node int dat

10、a;struct node *next; ListNode;typedef ListNode *LinkList;用不帶頭結(jié)點的單鏈表存儲待排數(shù)據(jù),鏈表頭指針為head。下列直接選擇排序算法對鏈表按升序進行排序,請在答題紙相應(yīng)位置填寫合適內(nèi)容使算法完整。void f32（LinkList head） ListNode *p, *q, *r;int tmp;p=head;while（p） q=p；r=-next;while（ (1) ） if（ (2) ） q=r；r=r-next;tmp=q-data;q-data=p-data;p-data=tmp;p= (3) ；33.實現(xiàn)二分查找的遞歸章法如下,在答題紙相應(yīng)位置填寫合適的內(nèi)容使算法完整。typedef structKeyType key;InfoType otherinfo;NodeType;typedef NodeType SeqListn+l;int f33（SeqList R, int low, int high, KeyType K） int mid;if（lowhigh）return 0；mid= （1） ；if（Rmid.key=K）return （2） ；if（Rmid.keyK）f33（R, mid+l, high, K）；else (3) ；五、算法設(shè)計題（