自考數(shù)據(jù)結(jié)構(gòu)歷年試題及答案

1、第一部分 選擇題(30 分) 一、單項選擇題（本大題共 15 小題，每小題 2 分，共 30 分）在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內(nèi)。 7．若目標串的長度為 n，模式串的長度為[n/3]，則執(zhí)行模式匹配算法時，在最壞情況下的時間復雜度是（ ） A．O（ n3） B．O（n） C．O（n2） D．O（n3） 9．假設以帶行表的三元組表表示稀疏矩陣，則

2、和下列行表 0 2 3 3 5 對應的稀疏矩陣是（ ） A.0 8 0 67 0 0 00 0 0 05 0 4 00 0 0 0????? ? ? ? ? ???? ? ? ? ? ?B.0 8 0 67 0 0 05 0 4 00 0 0 00 3 0 0????? ? ? ? ? ???? ? ? ? ? ?C.0 8 0 60 0 0 00 2 0 05 0 4 00 0 0 0????? ? ? ? ? ???? ?

3、 ? ? ? ?D.0 8 0 60 0 0 07 0 0 05 0 4 00 3 0 0????? ? ? ? ? ???? ? ? ? ? ?12．假設一個有 n 個頂點和 e 條弧的有向圖用鄰接表表示,則刪除與某個頂點 vi 相關(guān)的所有弧的時間復雜度是( ) A．O(n) B．O(e) C．O(n+e) D．O(n*e) 13．用某種排序方法對關(guān)鍵字序列（25，84，21，47，15，2

4、7，68，35，20）進行排序時，序列的變化情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采用的排序方法是（ ） A．選擇排序 B．希爾排序 C．歸并排序 D．快速排序 第二部分 非選擇題（共 70 分） 二、填空題（本大題共 10 小題，每小題 2 分，若有兩個空格，每個空格 1

5、 分，共 20 分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯填或不填均無分。 20．假設一個 9 階的上三角矩陣 A 按列優(yōu)先順序壓縮存儲在一維數(shù)組 B 中，其中 B[0]存儲矩陣中第 1 個元素 a1,1,則 B[31]中存放的元素是 。 21．已知一棵完全二叉樹中共有 768 結(jié)點，則該樹中共有 個葉子結(jié)點。 23．在單鏈表上難以實現(xiàn)的排序方法有

6、 和 。 25．多重表文件和倒排文件都歸屬于 多關(guān)鍵字 文件。 三、解答題（本大題共 4 小題，每小題 5 分，共 20 分） ② ； } if( ③ )return－1； if( ④ )return1； ⑤ ； } ① ② ③ ④ ⑤ 31．閱讀下面的算法 LinkList mynote