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

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

2、和下列行表 0 2 3 3 5 對(duì)應(yīng)的稀疏矩陣是（ ） 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．假設(shè)一個(gè)有 n 個(gè)頂點(diǎn)和 e 條弧的有向圖用鄰接表表示,則刪除與某個(gè)頂點(diǎn) vi 相關(guān)的所有弧的時(shí)間復(fù)雜度是( ) A．O(n) B．O(e) C．O(n+e) D．O(n*e) 13．用某種排序方法對(duì)關(guān)鍵字序列（25，84，21，47，15，2

4、7，68，35，20）進(jìn)行排序時(shí)，序列的變化情況如下： 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 分，若有兩個(gè)空格，每個(gè)空格 1

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

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