2022年1月全國(guó)統(tǒng)考計(jì)算機(jī)網(wǎng)絡(luò)(獨(dú)立本科段)數(shù)據(jù)結(jié)構(gòu)真題

1、精品word 名師歸納總結(jié) - - - - - - - - - - - -全國(guó) 20XX 年 1 月高等訓(xùn)練自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼： 02331一、單項(xiàng)挑選題 本大題共15 小題，每道題2 分，共 30 分 在每道題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)；錯(cuò)選、多項(xiàng)或未選均無(wú)分；1.以下程序段的時(shí)間復(fù)雜度為 s=0；fori=1 ； i<n ； i+ forj=1 ； j<n ； j+s+=i*j ；A.O1B.On2C.O2nD.On 2.假設(shè)某個(gè)帶頭結(jié)點(diǎn)的單鏈表的頭指針為head，就判定該表為空表的條件是 A.head=NULL ；B.h

2、ead->next=NULL；C.head.=NULL ；D.head->next=head ；3.棧是一種操作受限的線性結(jié)構(gòu)，其操作的主要特點(diǎn)是A. 先進(jìn)先出B. 后進(jìn)先出C.進(jìn)優(yōu)于出D. 出優(yōu)于進(jìn)4.假設(shè)以數(shù)組An 存放循環(huán)隊(duì)列的元素，其頭、尾指針?lè)謩e為front 和 rear；如設(shè)定尾指針指向隊(duì)列中的隊(duì)尾元素，頭指針指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，就當(dāng)前存于隊(duì)列中的元素個(gè)數(shù)為A.rear-front-1 nB.rear-front nC.front-rear+1 nD.rear-front+n n5.判定兩個(gè)串大小的基本準(zhǔn)就是A. 兩個(gè)串長(zhǎng)度的大小B. 兩個(gè)串中首字符的大小C

3、.兩個(gè)串中大寫字母的多少D. 對(duì)應(yīng)的第一個(gè)不等字符的大小6.二維數(shù)組A45 按行優(yōu)先次序儲(chǔ)備，如每個(gè)元素占2 個(gè)儲(chǔ)備單元，且第一個(gè)元素A00的儲(chǔ)備地址為1000，就數(shù)組元素A32 的儲(chǔ)備地址為 A.1012B.1017精選名師 優(yōu)秀名師 - - - - - - - - - -第 1 頁(yè)，共 9 頁(yè) - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -C.1034D.10367.高度為 5 的完全二叉樹(shù)中含有的結(jié)點(diǎn)數(shù)至少為 A.16B.17C.31D.328.已知在一棵度為3 的樹(shù)中，度為2 的結(jié)點(diǎn)數(shù)為4，度為 3 的結(jié)點(diǎn)數(shù)為3，就該樹(shù)

4、中的葉子結(jié)點(diǎn)數(shù)為 A.5B.8C.119.以下所示各圖中是中序線索化二叉樹(shù)的是D.1810.已知含6 個(gè)頂點(diǎn) v 0， v1， v2， v3， v4， v 5的無(wú)向圖的鄰接矩陣如下列圖，就從頂點(diǎn)v 0 動(dòng)身進(jìn)行深度優(yōu)先遍歷可能得到的頂點(diǎn)拜訪序列為A.v 0， v 1， v 2， v5， v4， v3 B.v 0， v1， v 2， v 3， v 4， v5 C.v 0， v1， v 5， v 2， v 3， v4 D.v 0， v 1， v 4， v5， v2， v311.如下列圖有向圖的一個(gè)拓?fù)湫蛄惺?A.ABCDEFB.FCBEAD C.FEDCBA D.DAEBCF12.以下關(guān)鍵字序列中

5、，構(gòu)成大根堆的是A.5 ， 8，1， 3， 9， 6， 2， 7B.9 ， 8， 1， 7，5， 6， 2，33C.9， 8， 6， 3， 5，l ，2， 7D.9 ，8， 6， 7，5， 1， 2， 3 13.對(duì)長(zhǎng)度為15 的有序次序表進(jìn)行二分查找，在各記錄的查找概率均相等的情形下，查找成精選名師 優(yōu)秀名師 - - - - - - - - - -第 2 頁(yè)，共 9 頁(yè) - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -功時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)的平均值為A. 39B. 491515C. 51D. 55151514.已知一個(gè)散列表

6、如下列圖，其散列函數(shù)為Hkey=key 11，采納二次探查法處理沖突，就下一個(gè)插入的關(guān)鍵字49 的地址為 15.數(shù)據(jù)庫(kù)文件是由大量帶有結(jié)構(gòu)的A. 記錄組成的集合B. 字符組成的集合C.數(shù)據(jù)項(xiàng)組成的集合D. 數(shù)據(jù)結(jié)構(gòu)組成的集合二、填空題 本大題共 10 小題，每道題2 分，共 20 分請(qǐng)?jiān)诿康李}的空格中填上正確答案；錯(cuò)填、不填均無(wú)分；16.估算算法時(shí)間復(fù)雜度時(shí)考慮的問(wèn)題規(guī)模通常是指算法求解問(wèn)題的 ；17.在雙向循環(huán)鏈表中插入一個(gè)新的結(jié)點(diǎn)時(shí)，應(yīng)修改 個(gè)指針域的值；18.如進(jìn)棧序列為a， b， c，且進(jìn)棧和出棧可以穿插進(jìn)行，就可能顯現(xiàn) 個(gè)不同的出棧序列；19.鏈串的結(jié)點(diǎn)大小定義為結(jié)點(diǎn)的 中存放的字符

7、個(gè)數(shù)；20.廣義表 a， d， c 的深度為 ；21.在含有3 個(gè)結(jié)點(diǎn)a，b， c 的二叉樹(shù)中，前序序列為abc 且后序序列為cba 的二叉樹(shù)有 棵；22.如用鄰接矩陣表示有向圖，就頂點(diǎn)i 的入度等于矩陣中 ；23.對(duì)關(guān)鍵字序列15， 18，11， 13， 19， 16， 12， 17， 10，8進(jìn)行增量為5 的一趟希爾排序的結(jié)果為 ；24.索引次序查找的索引表由各分塊中的最大關(guān)鍵字及各分塊的 構(gòu)成；25.VSAM文件的實(shí)現(xiàn)依靠于操作系統(tǒng)中的 存取方法的功能；三、解答題 本大題共 4 小題，每道題5 分，共 20 分精選名師 優(yōu)秀名師 - - - - - - - - - -第 3 頁(yè)，共 9

8、頁(yè) - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -26.假設(shè)有一個(gè)形如的 8×8 矩陣，矩陣元素都是整型量次對(duì)角線以上的元素都是0；如將上述矩陣中次對(duì)角線及其以下的元素按行優(yōu)先壓縮儲(chǔ)備在一維數(shù)組B 中，請(qǐng)回答以下問(wèn)題：1B 數(shù)組的體積至少是多少.2 如 a18 儲(chǔ)備在 B0 中， a56 儲(chǔ)備在 Bk 中，就 k 值為多少 . 1227.對(duì)關(guān)鍵字序列5， 8， 1， 3， 9，6， 2， 7按從小到大進(jìn)行快速排序；(1) 寫出排序過(guò)程中前兩趟的劃分結(jié)果；(2) 快速排序是否是穩(wěn)固的排序方法. 1228.假設(shè)通信電文使用

9、的字符集為a ，b，c，d，e，f ，g， h ，各字符在電文中顯現(xiàn)的頻度分別為： 7， 26， 2， 28， 13， 10， 3， 11，試為這8 個(gè)字符設(shè)計(jì)哈夫曼編碼；要求：(1) 畫出你所構(gòu)造的哈夫曼樹(shù)要求樹(shù)中左孩子結(jié)點(diǎn)的權(quán)值不大于右孩子結(jié)點(diǎn)的權(quán)值；(2) 按左分支為0 和右分支為1 的規(guī)章，分別寫出與每個(gè)字符對(duì)應(yīng)的編碼；1229.已知 3 階 B樹(shù)如下列圖，(1) 畫出將關(guān)鍵字6 插入之后的B樹(shù)；(2) 畫出在 1 所得樹(shù)中插入關(guān)鍵字2 之后的 B 樹(shù)； 12四、算法閱讀題 本大題共4 小題，每道題5 分，共 20 分30.假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示線性表，單鏈表的類型定義如下：精選名

10、師 優(yōu)秀名師 - - - - - - - - - -第 4 頁(yè)，共 9 頁(yè) - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -typedefintDataType; typedef struct node DataType data; struct node * next; LinkNode, * LinkList;閱讀以下算法，并回答疑題：(1) 已知初始鏈表如下列圖，畫出執(zhí)行f30head 之后的鏈表；題 30 圖(2) 簡(jiǎn)述算法f30 的功能；void f30 LinkList head LinkListp,r, s;if h

11、ead - > next r = head - > next;p = r->next; r - > next = NULL;while p s =p; p = p->next;if s - > data% 2 = = 0 s - > next = head - > next; head - > next = s; else s - > next = r - > next; r->next = s;r =s;精選名師 優(yōu)秀名師 - - - - - - - - - -第 5 頁(yè)，共 9 頁(yè) - - - - - - - - -

12、-精品word 名師歸納總結(jié) - - - - - - - - - - - -1231.假設(shè)以二叉鏈表表示二叉樹(shù)，其類型定義如下： typedef struct node DataTypedata;struct node * lchild,* rchild;/左右孩子指針* BinTree ;閱讀以下算法，并回答疑題：(1) 已知以 T 為根指針的二叉樹(shù)如下列圖，寫出執(zhí)行f31T 之后的返回值；(2) 簡(jiǎn)述算法f31 的功能；int f31 BinTree Tintd;if . T return 0;d = f31 T - > lchild + f31 T - > rchild ;

13、if T - > lchild && T - > rchildreturnd + 1 ; elsereturnd;1232.設(shè)有向圖鄰接表定義如下： typedef struct VertexNode adjlist MaxVertexNum ;int n ， e；圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)ALGraph ；鄰接表類型其中頂點(diǎn)表結(jié)點(diǎn)VertexNode邊表結(jié)點(diǎn)EdgeNode 結(jié)構(gòu)為：閱讀以下算法，并回答疑題：精選名師 優(yōu)秀名師 - - - - - - - - - -第 6 頁(yè)，共 9 頁(yè) - - - - - - - - - -精品word 名師歸納總結(jié) - - - -

14、- - - - - - - -(1) 已知某有向圖儲(chǔ)備在如下列圖的鄰接 表 G 中，寫出執(zhí)行f32 G 的輸出；(2) 簡(jiǎn)述算法f32 的功能；int visited MaxNum ;void DFSALGraph * G, int i EdgeNode * p;visited i = TRUE ;if G - > adjlist i. firstedge = = NULL printf "% c ", G - > adjlist i. vertex；else p = G - > adjlist i. firstedge; while p . = NULL

15、 if . visitedp -> adjvex DFS G, p - > adjvex ;p = p->next;void f32 ALGraph * G inti;for i = 0; i < G->n; i + visited i = FALSE ;for i = 0; i < G->n; i+if . visitedi DFSG, i ; 1233.以下算法f33 的功能是對(duì)記錄序列進(jìn)行雙向冒泡排序；算法的基本思想為，先從前往后通過(guò)交換將關(guān)鍵字最大的記錄移動(dòng)至后端，然后從后往前通過(guò)交換將關(guān)鍵字最小的記錄 移動(dòng)至前端，如此反復(fù)進(jìn)行，直至整個(gè)序列按

16、關(guān)鍵字遞增有序?yàn)橹?；?qǐng)?jiān)诳杖碧幪钊牒暇x名師 優(yōu)秀名師 - - - - - - - - - -第 7 頁(yè)，共 9 頁(yè) - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -適的內(nèi)容，使其成為完整的算法；#define MAXLEN 100 typedef int KeyType; typedef struct KeyType key; InfoType otherinfo; NodeType ;typedef NodeType SqList MAXLEN ; void f33 SqList R, int nint i,j,k; NodeType t; i =0;j =n-l;while i < j for 1if Rk.key > Rk +l.key t = Rk;Rk = Rk +1; Rk +1 = t;j-;for k =j; k > i; k - if 2 t = Rk;Rk = Rk-1; Rk-1 = t;3;精選名師 優(yōu)秀名師 - - - - - - - - - -第 8 頁(yè)，共 9 頁(yè) - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -