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

1、精品自學(xué)考試資料推薦全國 2019 年 10 月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼： 02331一、單項(xiàng)選擇題(本大題共15 小題，每小題2 分，共 30 分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請將其代碼填寫在題干的括號內(nèi)。錯(cuò)選、多選或未選均無分。1下列各式中，按增長率由小至大的順序正確排列的是()A n ， n！， 2n ， n3/2B n3/2 ，2n， nlogn ，2100C2n， log n ， nlogn ， n3/2D 2100， logn, 2 n, nn2若要在單鏈表中的結(jié)點(diǎn) *p 之后插入一個(gè)結(jié)點(diǎn)*s ，則應(yīng)執(zhí)行的語句是 ()A s-next=p-nex

2、t; p-next=s;B p-next=s; s-next=p-next;Cp-next=s-next; s-next=p;D s-next=p; p-next=s-next;3若要在 O（ 1）的時(shí)間復(fù)雜度上實(shí)現(xiàn)兩個(gè)循環(huán)鏈表頭尾相接，則應(yīng)對兩個(gè)循環(huán)鏈表各設(shè)置一個(gè)指針，分別指向()A 各自的頭結(jié)點(diǎn)B 各自的尾結(jié)點(diǎn)C各自的第一個(gè)元素結(jié)點(diǎn)D 一個(gè)表的頭結(jié)點(diǎn)，另一個(gè)表的尾結(jié)點(diǎn)4棧的兩種常用存儲結(jié)構(gòu)分別為()A 順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)B 順序存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu)C鏈?zhǔn)酱鎯Y(jié)構(gòu)和索引存儲結(jié)構(gòu)D 鏈?zhǔn)酱鎯Y(jié)構(gòu)和散列存儲結(jié)構(gòu)5已知循環(huán)隊(duì)列的存儲空間為數(shù)組data21 ，且當(dāng)前隊(duì)列的頭指針和尾指針的值

3、分別為8和 3，則該隊(duì)列的當(dāng)前長度為()A 5B 6C16D 176已知在如下定義的鏈串結(jié)點(diǎn)中，每個(gè)字符占1 個(gè)字節(jié)，指針占4 個(gè)字節(jié)，則該鏈串的存儲密度為typedef struct node char data8;struct node *next; LinkStrNode;A 1/4B 1/21精品自學(xué)考試資料推薦C2/3D 3/47應(yīng)用簡單的匹配算法對主串s= BDBABDABDAB與子串 t= BDA 進(jìn)行模式匹配，在匹配成功時(shí)，進(jìn)行的字符比較總次數(shù)為()A 7B 9C10D 128二維數(shù)組 A2010 采用列優(yōu)先的存儲方法，若每個(gè)元素占2 個(gè)存儲單元，且第1 個(gè)元素的首地址為200

4、，則元素 A89 的存儲地址為 ()A 574B 576C578D 5809對廣義表 L=(a,b),c,d) 進(jìn)行操作 tail(head(L) 的結(jié)果是 ()A （ c,d）B (d)CbD (b)10.已知一棵樹的前序序列為ABCDEF ，后序序列為CEDFBA ，則對該樹進(jìn)行層次遍歷得到的序列為 ()A ABCDEFB ABCEFDCABFCDED ABCDFE11一個(gè)含 n 個(gè)頂點(diǎn)和 e 條弧的有向圖以鄰接矩陣表示法為存儲結(jié)構(gòu)，則計(jì)算該有向圖中某個(gè)頂點(diǎn)出度的時(shí)間復(fù)雜度為()A O(n)B O(e)CO(n+e)D O(n 2)12在關(guān)鍵字序列 (12， 23， 34， 45， 56，

5、 67， 78， 89， 91)中二分查找關(guān)鍵字為45、 89和 12 的結(jié)點(diǎn)時(shí)，所需進(jìn)行的比較次數(shù)分別為()A 4， 4， 3B 4， 3， 3C3， 4， 4D 3， 3， 413下列排序方法中，最好與最壞時(shí)間復(fù)雜度不相同的排序方法是()A 冒泡排序B 直接選擇排序C堆排序D 歸并排序14已知含 10 個(gè)結(jié)點(diǎn)的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在等概率情況下查找成功的平均查找長度等于()A 1.0B 2.9C3.4D 5.515在下列各種文件中，不能進(jìn)行順序查找的文件是()A 順序文件B 索引文件C散列文件D 多重表文件2精品自學(xué)考試資料推薦二、填空題 (本大題共10 小題，每小題

6、2 分，共 20 分 )16抽象數(shù)據(jù)類型是指數(shù)據(jù)邏輯結(jié)構(gòu)及與之相關(guān)的_。17已知在結(jié)點(diǎn)個(gè)數(shù)大于 1 的單循環(huán)鏈表中，指針 p 指向表中某個(gè)結(jié)點(diǎn)，則下列程序段執(zhí)行結(jié)束時(shí)，指針 q 指向結(jié)點(diǎn) *p 的 _ 結(jié)點(diǎn)。q=p;while(q-next!=p)q=q-next;18假設(shè) S 和 X 分別表示進(jìn)棧和出棧操作，由輸入序列“ABC ”得到輸出序列“BCA ”的操作序列為SSXSXX ，則由“ a*b+c/d ”得到“ ab*cd/+ ”的操作序列為_。19在文本編輯程序中查找某一特定單詞在文本中出現(xiàn)的位置，可以利用串的 _運(yùn)算。20假設(shè)以行優(yōu)先順序?qū)⒁粋€(gè)n 階的 5 對角矩陣壓縮存儲到一維數(shù)組Q

7、 中，則數(shù)組Q 的大小至少為 _。21在含 100 個(gè)結(jié)點(diǎn)的完全二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為_。22在無向圖中，若從頂點(diǎn)a 到頂點(diǎn) b 存在 _，則稱 a 與 b 之間是連通的。23如果排序過程不改變_之間的相對次序，則稱該排序方法是穩(wěn)定的。24索引順序查找適宜對_的順序表進(jìn)行查找。25文件的檢索操作可按檢索條件不同分為下列四種詢問，它們是簡單詢問、范圍詢問、函數(shù)詢問及 _。三、解答題 (本大題共4 小題，每小題5 分，共 20 分 )26畫出下圖所示二叉樹的中序線索鏈表的存儲表示。27已知圖G= （ V ， E），其中：V=a,b,c,d,e,E=(a,b),(b,d),(c,b),(c,d)

8、,(d,e),(e,a),(e,c)。（ 1）畫出圖 G；（ 2）畫出圖 G 的鄰接表。（ 1）（ 2）28已知自頂向下的二路歸并排序的算法如下所示，按此算法對關(guān)鍵字序列（55，28，73，3精品自學(xué)考試資料推薦91， 37，64，19，82，46）進(jìn)行排序，列出算法執(zhí)行過程中前5 次調(diào)用 Merge 函數(shù)進(jìn)行歸并之后的關(guān)鍵字序列。void MergeSorDC(SeqList R, int low, int high)/用分治法對Rlow.high 進(jìn)行二路歸并排序int mid;if (lownext=Lc;while(p!=L)if(p-datac)pre-next=p-next;(2)

9、 ;Lc-next=p; p=pre-next;else4精品自學(xué)考試資料推薦pre=p;(3) ;return Lc;(1)(2)(3)31 設(shè)棧 S=(1,2,3,4,5,6,7), 其中 7 為棧頂元素。（ 1）寫出調(diào)用 f31(&S) 后的 S；（ 2）簡述函數(shù) f31 中第 1 個(gè)循環(huán)語句的功能。void f31 (Stack *S)Queue Q;Stack T;int i=0;InitQueue(&Q);InitStack(&T);while(!StackEmpty(S)if (i=!t)!=0) Push(&T,Pop(S);else EnQueue(&Q, Pop(S);wh

10、ile(!StackEmpty(&T)Push(S,PoP(&T);while(!QieueEmpty(&Q)Push(S,DeQueue(&Q);(1)(2)32圖的鄰接矩陣表示描述如下：#define MaxNum20/圖的最大頂點(diǎn)數(shù)typedef structchar vexsMaxNum;/字符類型的頂點(diǎn)表int edgesMaxNumMaxNum;/鄰接矩陣5精品自學(xué)考試資料推薦int n, e;/圖的頂點(diǎn)數(shù)和邊數(shù) MGraph;/ 圖的鄰接矩陣結(jié)構(gòu)描述閱讀下列算法，并回答問題：（ 1）對于下列圖G 的鄰接矩陣，寫出函數(shù)調(diào)用f32(&G ,3)的返回值；011110010000010

11、1100000110（ 2）簡述函數(shù) f32 的功能；（ 3）寫出函數(shù) f32 的時(shí)間復(fù)雜度。int f32(MGraph *G , int i)int d=0,j;for(j=0;jn;j+)if (G-edgesij) d+;if (G-edgesji) d+;return d;(1)(2)(3)33閱讀下列算法并回答問題：（ 1）設(shè)數(shù)組 L1.8 的初值為（ 4， -3，7，-1， -2，2，5， -8），寫出執(zhí)行函數(shù)調(diào)用f33(L,8)之后的 L1.8 中的元素值；（ 2）簡述函數(shù)f33 的功能。void f33(int R, int n)int x=R1;int low=1, high=n;while(lowhigh)6精品自學(xué)考試資料推薦while(low=0)high -;if (lowhigh)Rlow+=Rhigh;while (lowhigh& Rlow0)low+;Rhigh-=Rlow;Rlow=x;(1)(2)五、算法設(shè)計(jì)題(本大題 10 分)34假設(shè)以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，其結(jié)點(diǎn)結(jié)構(gòu)為：lchilddatarchi