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

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

2、A. 插入操作更加方便B. 刪除操作更加方便C.不會出現(xiàn)下溢的情況D.不會出現(xiàn)上溢的情況5.采用兩類不同存儲結(jié)構(gòu)的字符串可分別簡稱為()A. 主串和子串B.順序串和鏈串C.目標串和模式串D.變量串和常量串6.在目標串 T 0.n-1= xwxxyxy 中，對模式串P 0.m-1= xy 進行子串定位操作的結(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)先順序存儲，其中每個元素占1 個存儲單元。若A 1 1的存儲地址為 420， A 3 3的存

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

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

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

6、對長度為20 的有序表進行二分查找的判定樹的高度為_。25.在多重表文件中，次關(guān)鍵字索引的組織方式是將_的記錄鏈接成一個鏈表。2三、解答題 (每小題 5 分，共 20 分 )26.對于單鏈表、單循環(huán)鏈表和雙向鏈表，如果僅僅知道一個指向鏈表中某結(jié)點的指針p，能否將 p 所指結(jié)點的數(shù)據(jù)元素與其確實存在的直接前驅(qū)交換?請對每一種鏈表作出判斷，若可以，寫出程序段；否則說明理由。單鏈表和單循環(huán)鏈表的結(jié)點結(jié)構(gòu)為datenext雙向鏈表的結(jié)點結(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)請根據(jù)哈夫曼編碼畫出此哈夫曼樹，并在葉子結(jié)點中標注相應(yīng)字符；(2)若這些字符在電文中出現(xiàn)的頻度分別為： 3， 35，13，15，20，5 和 9，求該哈夫曼樹的帶權(quán)路徑長度。28.當采用鄰接表作為圖的存儲結(jié)構(gòu)時，也可將鄰接表中的頂點表由順序結(jié)構(gòu)改為鏈表結(jié)構(gòu)。(1)請分別畫出這種鄰接表的頂點鏈表結(jié)點和邊表結(jié)點，并說明結(jié)點中各個域的作用；(2)對如圖所示的有向圖畫出這種鄰接表。29.已知 4 階 B-樹如圖所示。(1)分別畫出將關(guān)鍵字23 和 89 相繼插入之后的B- 樹。(2)畫出從插入之前的B- 樹中刪除關(guān)鍵字51 之后的 B-

8、 樹。四、算法閱讀題(每小題 5 分，共 20 分 )30.閱讀下列函數(shù)algo,并回答問題：(1)假設(shè)隊列q 中的元素為 (2,4,5,7,8), 其中“ 2”為隊頭元素。寫出執(zhí)行函數(shù)調(diào)用algo(&q) 后的隊列 q；3(2)簡述算法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)已知如圖所示的二叉樹以二叉鏈表作存儲結(jié)構(gòu)，rt

9、為指向根結(jié)點的指針。寫出執(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.已知鄰接表的頂點表結(jié)點結(jié)構(gòu)為vertexfirstedge邊表結(jié)點 EdgeNode 的結(jié)構(gòu)為adjvexnext下列算法計算有向圖 G 中頂點 vi 的入度。 請在空缺處填入合適的內(nèi)容

10、，使其成為一個完整的算法。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é)點結(jié)構(gòu)為datanext下列算法對帶頭結(jié)點的單鏈表L 進行簡單選擇排序，使得L 中的元素按值從小到大排列。請在空缺處填入合適的內(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);