全國(guó)自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試卷

1、全國(guó) 20XX 年 1 月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼： 02331一、單項(xiàng)選擇題（本大題共15 小題，每小題2 分，共 30 分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。1抽象數(shù)據(jù)類型的三個(gè)組成部分分別為（A）A 數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作B數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)C數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素和數(shù)據(jù)類型D數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型2若算法中語(yǔ)句的最大頻度為2C ）T(n)=2006n+6nlogn+29log n,則其時(shí)間復(fù)雜度為（A O(logn)B O(n)C O(nlogn)D O(log 2n)3若線性表的插入和

2、刪除操作頻繁地在表頭或表尾位置進(jìn)行，則更適宜采用的存儲(chǔ)結(jié)構(gòu)為（B）A 無(wú)頭結(jié)點(diǎn)的雙向鏈表B 帶尾指針的循環(huán)鏈表C無(wú)頭結(jié)點(diǎn)的單鏈表D 帶頭指針的循環(huán)鏈表4上溢現(xiàn)象通常出現(xiàn)在（A）A 順序棧的入棧操作過(guò)程中B 順序棧的出棧操作過(guò)程中C鏈棧的入棧操作過(guò)程中D 鏈棧的出棧操作過(guò)程中5已知串s= aabacbabcaccab，串t1= abc串,t2= cba,函數(shù) index(s,t)的返回值為串中首次出現(xiàn)的位置，則能求得串a(chǎn)bcacba的操作序列為（C）t 在串sA substr (s1,s,6,index(s,t1); substr (s2,s,index(s,t1),1);strcat(s1,s

3、2);B substr (s1,s,7,index(s,t1); substr (s2,s,index(s,t1),1);strcat(s2,s1);C substr(s1,s,6,index(s,t2); substr(s2,s,index(s,t2),3);strcat(s1,s2);D substr(s1,s,6,index(s,t2); substr(s2,s,index(s,t2),3);strcat(s2,s1);6對(duì)廣義表L=(a,b),(c,d),(e,f)執(zhí)行head(tail(head(tail(L)操作的結(jié)果是（D）A dB eC (e)D (e,f )7已知一棵完全二叉

4、樹有64 個(gè)葉子結(jié)點(diǎn)，則該樹可能達(dá)到的最大深度為（B）A 7B 8C 9D 108若一棵二叉樹有11 個(gè)葉子結(jié)點(diǎn)，則該二叉樹中度為2 的結(jié)點(diǎn)個(gè)數(shù)是（A）A10B 11C 12D 不確定的9對(duì)于有向圖，其鄰接矩陣表示相比鄰接表表示更易于進(jìn)行的操作為（B）A 求一個(gè)頂點(diǎn)的鄰接點(diǎn)C深度優(yōu)先遍歷B 求一個(gè)頂點(diǎn)的度D 廣度優(yōu)先遍歷10若用鄰接矩陣表示帶權(quán)有向圖，則頂點(diǎn)i 的入度等于矩陣中（D）A 第 i 行非 元素之和B 第 i 列非 元素之和C第 i 行非 元素個(gè)數(shù)D 第 i 列非 元素個(gè)數(shù)11對(duì)關(guān)鍵字序列（5， 1，4， 3，7，2， 8，6）進(jìn)行快速排序時(shí)，以第一個(gè)元素5 為基準(zhǔn)的一次劃分的結(jié)果為

5、（C）A （ 1， 2， 3， 4， 5， 6，7， 8）B（ 1，4， 3， 2，5， 7， 8， 6）C（ 2，1， 4， 3，5， 7， 8， 6）D（ 8， 7， 6， 5， 4， 3，2， 1）12下列二叉樹中，不 平衡的二叉樹是（C）13下列序列中，不 構(gòu)成堆的是（D）A （ 1， 2， 5， 3， 4， 6，7， 8， 9，10）B（ 10，5， 8， 4， 2， 6，7， 1， 3）C（ 10，9， 8， 7， 3， 5，4， 6， 2）D（ 1， 2， 3， 4， 10， 9， 8， 7， 6， 5）14主關(guān)鍵字能唯一標(biāo)識(shí)（A）A 一個(gè)記錄B 一組記錄C一個(gè)類型D 一個(gè)文件1

6、5稀疏索引是指在文件的索引表中（D）A 為每個(gè)字段設(shè)一個(gè)索引項(xiàng)B為每個(gè)記錄設(shè)一個(gè)索引項(xiàng)C為每組字段設(shè)一個(gè)索引項(xiàng)D為每組記錄設(shè)一個(gè)索引項(xiàng)二、填空題（本大題共10 小題，每小題2 分，共 20 分）請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是借助_指針 _來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。17假設(shè)帶頭結(jié)點(diǎn)的非空單循環(huán)鏈表中僅設(shè)尾指針L ，則在第 1 個(gè)結(jié)點(diǎn)之前插入指針s 所指結(jié)點(diǎn)的語(yǔ)句依次是 _s->next=L->next->next_； _L->next->next=s_ 。18無(wú)表頭結(jié)點(diǎn)的鏈隊(duì)列Q 為空的條件是 _Q.front=NUL

7、L_ 。 (或 Q->front=NULL)19不 含任何字符的串稱為_(kāi)空串 _。20假設(shè)按行優(yōu)先順序?qū)⒁粋€(gè)20 階的三對(duì)角矩陣A 壓縮存儲(chǔ)在一維數(shù)組 Q 中，其中 Q0存放矩陣的第 1 個(gè)元素 a1,1，那么矩陣元素 a3,4 在 Q 中的存儲(chǔ)位置 k=_ _7_ 。21前序序列和中序序列不 相同的二叉樹的特征是_樹中至少含有一個(gè)具有非空右子樹的結(jié)點(diǎn)_。（或樹中存在具有右孩子的結(jié)點(diǎn)）22在含有 n 個(gè)頂點(diǎn)的連通圖中，任意兩個(gè)不同頂點(diǎn)之間的簡(jiǎn)單路徑的最大長(zhǎng)度為_(kāi)n-1_ 。23用 _冒泡 _排序方法對(duì)關(guān)鍵字序列（20， 25，12， 47， 15， 83， 30， 76）進(jìn)行排序時(shí)，前三

8、趟排序的結(jié)果為：20， 12， 25， 15， 47， 30， 76，8312， 20， 15， 25， 30， 47， 76，8312， 15， 20， 25， 30， 47， 76，8324哈希表常用的兩類解決沖突的方法是開(kāi)放定址法和_拉鏈法 _ 。25倒排文件和多重表文件的主要區(qū)別在于次關(guān)鍵字索引的結(jié)構(gòu)不同。三、解答題（本大題共4 小題，每小題5 分，共 20 分）26已知主串為 ccgcgccgcgcbcb，模式串為 cgcgcb。下表所列為按照樸素的串匹配算法進(jìn)行的前兩趟匹配。請(qǐng)繼續(xù)完成余下各趟匹配，直至結(jié)束。c c g c g c c g c g c b c bi=0c g匹配失敗

9、時(shí) j=1i=1c g cgcb匹配失敗時(shí) j=5i=2c匹配失敗時(shí) j=0i=3cgcg匹配失敗時(shí) j=3i=4c匹配失敗時(shí) j=0i=5cg匹配失敗時(shí) j=1i=6c g c g c b匹配成功27已知帶權(quán)圖G 如圖所示，畫出圖G 的一棵最小生成樹。去掉： (A,B),(A,D),(C,F),(C,E),(C,H),(D,E),(E,H)保留： (A,C),(B,C),(B,F),(F,H),(C,D),(D,K),(K,E),28對(duì)于直接插入排序，希爾排序，冒泡排序，快速排序，直接選擇排序，堆排序和歸并排序等排序方法，分別寫出：（ 1）平均時(shí)間復(fù)雜度低于 O（ n2）的排序方法；（ 2）

10、所需輔助空間最多的排序方法；（ 3）最好情況和最壞情況下的時(shí)間復(fù)雜度相同的排序方法。（ 1）希爾排序、快速排序、堆排序和歸并排序（ 2）歸并排序（ 3）直接選擇排序、堆排序和歸并排序29已知一棵線索化的二叉排序樹如圖所示。（ 1）說(shuō)明該樹的線索化是基于何種遍歷次序的；（ 2）在該樹中插入元素值為 53 的結(jié)點(diǎn)并修改相應(yīng)線索，畫出修改之后的樹。（ 1）中序（ 2）53四、算法閱讀題（本大題共4 小題，每小題5 分，共20 分）30假設(shè)線性表采用順序存儲(chǔ)結(jié)構(gòu)，表中元素值為整型。閱讀算法f 30，并回答下列問(wèn)題：（1）設(shè)順序表L=(3,7,3,2,1,1,8,7,3), 寫出執(zhí)行算法f 30后的L;

11、（ 2）簡(jiǎn)述算法 f 30 的功能。 void f 30(SeqList *L) int i,j,k; k=0;for(i=0;i<L->length;i+) for(j=0;j<k && L->datai!=L->dataj;j+); if(j=k) if(k!=i)L->datak=L->datai;k+;L->length=k;(1) L=(3,7,2,1,8)(2) 刪除順序表 L 中的重復(fù)元素31閱讀算法f 31, 并回答下列問(wèn)題：（ 1）設(shè)隊(duì)列 Q=（ 1， 3，5， 2， 4，6）。寫出執(zhí)行算法 f 31 后的隊(duì)列

12、Q;（ 2）簡(jiǎn)述算法 f 31 的功能。voidf 31(Queue *Q)DataTypee;if (!QueueEmpty(Q)e=DeQueue(Q);f 31(Q);EnQueue(Q,e);(1) Q=(6,4,2,5,3,1)(2) 逆置隊(duì)列 Q32已知樹的存儲(chǔ)結(jié)構(gòu)為孩子兄弟鏈表，其類型定義如下：typedef struct CSTNode char data;struct CSTNode leftmostchild ,* rightsibling; CSTNode, *CSTree;閱讀函數(shù)f 32,并回答下列問(wèn)題：（1）對(duì)于如圖所示樹，寫出函數(shù)調(diào)用f 32(T) 的返回值；（2

13、）簡(jiǎn)述樹T 非空時(shí)函數(shù)f 32 返回值的含義。int f32(CSTree T)int c;CSTree p;if (!T->leftmostchild) return 1;else c=0;for(p=T->leftmostchild;p;p=p->rightsibling)c+=f32(p);return c;(1) 5(2) 樹 T 的葉子結(jié)點(diǎn)個(gè)數(shù)33已知數(shù)組R1.p-1 中的元素序列為一個(gè)大根堆，函數(shù) Adjust(R,p) 將 R1.p 重新調(diào)整為一個(gè)大根堆。（ 1）在函數(shù) Adjust 的空缺處填入適當(dāng)內(nèi)容，使其成為一個(gè)完整的函數(shù)；（ 2）簡(jiǎn)述函數(shù) f33(R,n

14、) 的功能。voidAdjust(SeqList R,int p) int i,j;RecType temp=Rp; i=p;j=i/2;while(j>=1&& Rj.key<temp.key) Ri=Rj;i=j; j=i/2;(或 j=j/2 )Ri=temp;void f33(SeqList R,int n) int k; for(k=2;k<=n;k+)Adjust(R,k);(1)(2) 從數(shù)組的前端開(kāi)始，通過(guò)逐個(gè)插入元素建堆五、算法設(shè)計(jì)題（本大題 10 分）34已知有向圖的鄰接表表示的形式描述如下：#defineMaxNum50/ 圖的最大頂點(diǎn)數(shù)typedef struct ArcNodeintadjvex;/鄰接點(diǎn)域struct ArcNode *nextArc;/鏈域 ArcNode;/弧