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

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

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

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

4、中的葉子結(jié)點數(shù)為 A.5B.8C.119.以下所示各圖中是中序線索化二叉樹的是D.1810.已知含6 個頂點 v 0， v1， v2， v3， v4， v 5的無向圖的鄰接矩陣如下列圖，就從頂點v 0 動身進行深度優(yōu)先遍歷可能得到的頂點拜訪序列為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.如下列圖有向圖的一個拓撲序列是 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.對長度為15 的有序次序表進行二分查找，在各記錄的查找概率均相等的情形下，查找成精選名師 優(yōu)秀名師 - - - - - - - - - -第 2 頁，共 9 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -功時所需進行的關(guān)鍵字比較次數(shù)的平均值為A. 39B. 491515C. 51D. 55151514.已知一個散列表

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

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

8、頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -26.假設(shè)有一個形如的 8×8 矩陣，矩陣元素都是整型量次對角線以上的元素都是0；如將上述矩陣中次對角線及其以下的元素按行優(yōu)先壓縮儲備在一維數(shù)組B 中，請回答以下問題：1B 數(shù)組的體積至少是多少.2 如 a18 儲備在 B0 中， a56 儲備在 Bk 中，就 k 值為多少 . 1227.對關(guān)鍵字序列5， 8， 1， 3， 9，6， 2， 7按從小到大進行快速排序；(1) 寫出排序過程中前兩趟的劃分結(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 個字符設(shè)計哈夫曼編碼；要求：(1) 畫出你所構(gòu)造的哈夫曼樹要求樹中左孩子結(jié)點的權(quán)值不大于右孩子結(jié)點的權(quán)值；(2) 按左分支為0 和右分支為1 的規(guī)章，分別寫出與每個字符對應(yīng)的編碼；1229.已知 3 階 B樹如下列圖，(1) 畫出將關(guān)鍵字6 插入之后的B樹；(2) 畫出在 1 所得樹中插入關(guān)鍵字2 之后的 B 樹； 12四、算法閱讀題 本大題共4 小題，每道題5 分，共 20 分30.假設(shè)以帶頭結(jié)點的單鏈表表示線性表，單鏈表的類型定義如下：精選名

10、師 優(yōu)秀名師 - - - - - - - - - -第 4 頁，共 9 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -typedefintDataType; typedef struct node DataType data; struct node * next; LinkNode, * LinkList;閱讀以下算法，并回答疑題：(1) 已知初始鏈表如下列圖，畫出執(zhí)行f30head 之后的鏈表；題 30 圖(2) 簡述算法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 頁，共 9 頁 - - - - - - - - -

12、-精品word 名師歸納總結(jié) - - - - - - - - - - - -1231.假設(shè)以二叉鏈表表示二叉樹，其類型定義如下： typedef struct node DataTypedata;struct node * lchild,* rchild;/左右孩子指針* BinTree ;閱讀以下算法，并回答疑題：(1) 已知以 T 為根指針的二叉樹如下列圖，寫出執(zhí)行f31T 之后的返回值；(2) 簡述算法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)前頂點數(shù)和弧數(shù)ALGraph ；鄰接表類型其中頂點表結(jié)點VertexNode邊表結(jié)點EdgeNode 結(jié)構(gòu)為：閱讀以下算法，并回答疑題：精選名師 優(yōu)秀名師 - - - - - - - - - -第 6 頁，共 9 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - -

14、- - - - - - - -(1) 已知某有向圖儲備在如下列圖的鄰接 表 G 中，寫出執(zhí)行f32 G 的輸出；(2) 簡述算法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 的功能是對記錄序列進行雙向冒泡排序；算法的基本思想為，先從前往后通過交換將關(guān)鍵字最大的記錄移動至后端，然后從后往前通過交換將關(guān)鍵字最小的記錄 移動至前端，如此反復(fù)進行，直至整個序列按

16、關(guān)鍵字遞增有序為止；請在空缺處填入合精選名師 優(yōu)秀名師 - - - - - - - - - -第 7 頁，共 9 頁 - - - - - - - - - -精品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 頁，共 9 頁 - - - - - - - - - -精品word 名師歸納總結(jié) - - - - - - - - - - - -