10月全國(guó)數(shù)據(jù)結(jié)構(gòu)自考試題及答案解析.doc

1、全國(guó) 2019 年 10 月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼： 02331一、單項(xiàng)選擇題(在每小題的四個(gè)備選答案中，選出一個(gè)正確答案，并將正確答案的序號(hào)填在題干的括號(hào)內(nèi)。每小題2 分，共 30 分)1.計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱為()A. 數(shù)據(jù)B. 數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D. 數(shù)據(jù)類型2.在具有n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并使鏈表仍然有序的時(shí)間復(fù)雜度是()A.O(1)B.O(n)C.O(nlogn)D.O(n 2)3.隊(duì)和棧的主要區(qū)別是 ()A. 邏輯結(jié)構(gòu)不同B. 存儲(chǔ)結(jié)構(gòu)不同C.所包含的運(yùn)算個(gè)數(shù)不同D.限定插入和刪除的位置不同4.鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是()

2、A. 插入操作更加方便B. 刪除操作更加方便C.不會(huì)出現(xiàn)下溢的情況D.不會(huì)出現(xiàn)上溢的情況5.采用兩類不同存儲(chǔ)結(jié)構(gòu)的字符串可分別簡(jiǎn)稱為()A. 主串和子串B.順序串和鏈串C.目標(biāo)串和模式串D.變量串和常量串6.在目標(biāo)串 T 0.n-1= xwxxyxy 中，對(duì)模式串P 0.m-1= xy 進(jìn)行子串定位操作的結(jié)果是 ()A.0B.2C.3D.57.已知廣義表的表頭為 a，表尾為 (b,c)，則此廣義表為 ()A.(a,(b,c)B.(a,b,c)C.(a),b,c)D.(a,b,c)8.二維數(shù)組 A 按行優(yōu)先順序存儲(chǔ)，其中每個(gè)元素占1 個(gè)存儲(chǔ)單元。若A 1 1的存儲(chǔ)地址為 420， A 3 3的存

3、儲(chǔ)地址為446，則 A 55的存儲(chǔ)地址為 ()A.470B.471C.472D.4739.二叉樹中第5 層上的結(jié)點(diǎn)個(gè)數(shù)最多為()A.8B.15C.16D.3210.下列編碼中屬前綴碼的是 ()A.1,01,000,001B.1,01,011,010C.0,10,110,11D.0,1,00,1111.如果某圖的鄰接矩陣是對(duì)角線元素均為零的上三角矩陣，則此圖是()1A. 有向完全圖B. 連通圖C.強(qiáng)連通圖D. 有向無環(huán)圖12.對(duì) n 個(gè)關(guān)鍵字的序列進(jìn)行快速排序，平均情況下的空間復(fù)雜度為()A.O(1)B.O(logn)C.O(n)D.O(n logn)13.對(duì)表長(zhǎng)為 n 的順序表進(jìn)行順序查找，在

4、查找概率相等的情況下，查找成功的平均查找長(zhǎng)度為 ()n - 1nA.B.22n 1D.nC.214.對(duì)于哈希函數(shù) H(key)=key%13, 被稱為同義詞的關(guān)鍵字是 ()A.35 和 41B.23 和 39C.15 和 44D.25 和 5115.稠密索引是在索引表中 ()A. 為每個(gè)記錄建立一個(gè)索引項(xiàng)B.為每個(gè)頁(yè)塊建立一個(gè)索引項(xiàng)C.為每組記錄建立一個(gè)索引項(xiàng)D.為每個(gè)字段建立一個(gè)索引項(xiàng)二、填空題（每小題 2 分，若有兩個(gè)空格，每個(gè)空格1 分，共 20分）16.當(dāng)問題的規(guī)模 n 趨向無窮大時(shí)，算法執(zhí)行時(shí)間T(n)的數(shù)量級(jí)被稱為算法的 _。17.在鏈表的結(jié)點(diǎn)中，數(shù)據(jù)元素所占的存儲(chǔ)量和整個(gè)結(jié)點(diǎn)所占

5、的存儲(chǔ)量之比稱作_。18.已知鏈棧的結(jié)點(diǎn)結(jié)構(gòu)為datenext棧頂指針為 top，則實(shí)現(xiàn)將指針 p 所指結(jié)點(diǎn)插入棧頂?shù)恼Z(yǔ)句依次為 _和 _。19.空串的長(zhǎng)度是 _；空格串的長(zhǎng)度是 _。20.假設(shè)一個(gè) 6 階的下三角矩陣B 按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組A 中，其中 A 0存儲(chǔ)矩陣的第一個(gè)元素 b11,則 A 14存儲(chǔ)的元素是 _。21.在一棵度為3 的樹中，度為2 的結(jié)點(diǎn)個(gè)數(shù)是1，度為 0 的結(jié)點(diǎn)個(gè)數(shù)是6，則度為 3 的結(jié)點(diǎn)個(gè)數(shù)是 _。22.如圖所示的有向無環(huán)圖可以排出_種不同的拓?fù)湫蛄小?3.利用篩選法將關(guān)鍵字序列(37， 66， 48， 29， 31， 75)建成的大根堆為(_) 。24.

6、對(duì)長(zhǎng)度為20 的有序表進(jìn)行二分查找的判定樹的高度為_。25.在多重表文件中，次關(guān)鍵字索引的組織方式是將_的記錄鏈接成一個(gè)鏈表。2三、解答題 (每小題 5 分，共 20 分 )26.對(duì)于單鏈表、單循環(huán)鏈表和雙向鏈表，如果僅僅知道一個(gè)指向鏈表中某結(jié)點(diǎn)的指針p，能否將 p 所指結(jié)點(diǎn)的數(shù)據(jù)元素與其確實(shí)存在的直接前驅(qū)交換?請(qǐng)對(duì)每一種鏈表作出判斷，若可以，寫出程序段；否則說明理由。單鏈表和單循環(huán)鏈表的結(jié)點(diǎn)結(jié)構(gòu)為datenext雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為priordatenext(1)單鏈表(2)單循環(huán)鏈表(3)雙向鏈表27.假設(shè)通信電文使用的字符集為a,b,c,d,e,f,g ，字符的哈夫曼編碼依次為：0110

7、， 10， 110，111， 00， 0111 和 010。(1)請(qǐng)根據(jù)哈夫曼編碼畫出此哈夫曼樹，并在葉子結(jié)點(diǎn)中標(biāo)注相應(yīng)字符；(2)若這些字符在電文中出現(xiàn)的頻度分別為： 3， 35，13，15，20，5 和 9，求該哈夫曼樹的帶權(quán)路徑長(zhǎng)度。28.當(dāng)采用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，也可將鄰接表中的頂點(diǎn)表由順序結(jié)構(gòu)改為鏈表結(jié)構(gòu)。(1)請(qǐng)分別畫出這種鄰接表的頂點(diǎn)鏈表結(jié)點(diǎn)和邊表結(jié)點(diǎn)，并說明結(jié)點(diǎn)中各個(gè)域的作用；(2)對(duì)如圖所示的有向圖畫出這種鄰接表。29.已知 4 階 B-樹如圖所示。(1)分別畫出將關(guān)鍵字23 和 89 相繼插入之后的B- 樹。(2)畫出從插入之前的B- 樹中刪除關(guān)鍵字51 之后的 B-

8、 樹。四、算法閱讀題(每小題 5 分，共 20 分 )30.閱讀下列函數(shù)algo,并回答問題：(1)假設(shè)隊(duì)列q 中的元素為 (2,4,5,7,8), 其中“ 2”為隊(duì)頭元素。寫出執(zhí)行函數(shù)調(diào)用algo(&q) 后的隊(duì)列 q；3(2)簡(jiǎn)述算法algo 的功能。void algo(Queue *Q)Stack S;InitStack(&S);while (!QueueEmpty(Q)Push(&S, DeQueue(Q);while (! StackEmpty(&S)nQueue(Q,Pop(&S);(1)(2)31.閱讀下列函數(shù)F，并回答問題：(1)已知如圖所示的二叉樹以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，rt

9、為指向根結(jié)點(diǎn)的指針。寫出執(zhí)行函數(shù)調(diào)用 F(rt) 的輸出結(jié)果。(2)說明函數(shù)F 的功能。void F(BinTree T)Stack S;if(T)InitStack(&S);Push(&S,NULL);while(T)printf(%c, T-data);if(T-rchild) Push(&S,T-rchild);if(T-lchild)T=T-lchild;else T=Pop(&S);(1)(2)32.已知鄰接表的頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)為vertexfirstedge邊表結(jié)點(diǎn) EdgeNode 的結(jié)構(gòu)為adjvexnext下列算法計(jì)算有向圖 G 中頂點(diǎn) vi 的入度。 請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容

10、，使其成為一個(gè)完整的算法。int FindDegree(ALGraph *G ,int i)/ALGraph為圖的鄰接表類型4int dgree, j;EdgeNode *p;degree=(1);for(j=0;jn;j+)p=G-adjlist j . firstedge;while (2)if(3)degree+;break;p=p-next;return degree;(1)(2)(3)33.已知單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為datanext下列算法對(duì)帶頭結(jié)點(diǎn)的單鏈表L 進(jìn)行簡(jiǎn)單選擇排序，使得L 中的元素按值從小到大排列。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為完整的算法。void SelectSort(LinkedList L)LinkedList p,q,min;DataType rcd;p=(1);while(p!=NULL) min=p;q=p-next;while(q!=NULL)if(2)min=q;q=q-next;if(3)rcd=p-data;p-data=min-data;min-data=rcd;5(4);