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

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

2、個(gè)數(shù)據(jù)元素，若第一種元素的存儲(chǔ)地址是1000，則最后一種元素地址是1036，第5個(gè)元素的地址是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)隊(duì)列的論述中,錯(cuò)誤的是A.隊(duì)列是一種先進(jìn)先出的線性表B.隊(duì)列是一種后進(jìn)后出的線性表C.循環(huán)隊(duì)列中進(jìn)行出隊(duì)操作時(shí)要判斷隊(duì)列與否為空D.在鏈隊(duì)列中進(jìn)行入隊(duì)操作時(shí)要判斷隊(duì)列與否為滿5.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)的目的是A.便于運(yùn)算B.節(jié)省存儲(chǔ)空間C.便于輸入輸出D.減少時(shí)間復(fù)雜度6.一棵二叉樹(shù)的第7層上最多具有的

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

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

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

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

7、出從頂點(diǎn)v1出發(fā)圖的廣度優(yōu)先搜索遍歷序列。29.（1）一種排序措施穩(wěn)定的含義是什么？（2）迅速排序是穩(wěn)定的嗎？舉例闡明。四、算法閱讀題（本大題共4小題,每題5分,共20分）30.閱讀下列算法,并回答問(wèn)題：void f30（SeqStack S） int k=0；CirQueue Q；SeqStack T；InitQueue（&Q）； /初始化隊(duì)列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） /第二個(gè)循環(huán)Push（&S, DeQueue（&Q）;while（!StackEmpty（&T） /第三個(gè)循環(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和隊(duì)列Q中的內(nèi)容各是什么？（2）第三個(gè)循環(huán)語(yǔ)句結(jié)束后,棧S中的內(nèi)容是什么？31.二叉樹(shù)的二叉鏈表類(lèi)型定義如下：typedef struct node DataType data；struct node *lchild, *rchild; BinNode;typedef BinNode *BinTree；閱讀下列算法,并回答問(wèn)題：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）如下算法功能與否等價(jià)于上面的算法？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.單鏈表類(lèi)型定義如下：typedef struct node int dat

10、a;struct node *next; ListNode;typedef ListNode *LinkList;用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)待排數(shù)據(jù),鏈表頭指針為head。下列直接選擇排序算法對(duì)鏈表按升序進(jìn)行排序,請(qǐng)?jiān)诖痤}紙相應(yīng)位置填寫(xiě)合適內(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.實(shí)現(xiàn)二分查找的遞歸章法如下,在答題紙相應(yīng)位置填寫(xiě)合適的內(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è)計(jì)題（