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

1、-2010 年 1 月高等教育考試數(shù)據(jù)結(jié)構(gòu)試題和答案課程代碼：02331一、單項(xiàng)選擇題( 本大題共15 小題，每小題2 分，共30 分 )在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1若一個(gè)算法的時(shí)間復(fù)雜度用 T(n) 表示，其中n 的含義是（A ）A問題規(guī)模B語句條數(shù)C循環(huán)層數(shù)D函數(shù)數(shù)量2具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（C ）A樹B圖C棧和隊(duì)列D廣義表線性結(jié)構(gòu)有：順序表、棧和隊(duì)列、串3將長(zhǎng)度為 n 的單鏈表連接在長(zhǎng)度為m 的單鏈表之后，其算法的時(shí)間復(fù)雜度為（C ）A O(1)B O(m)C O(n)D O(m+n)4在帶頭結(jié)點(diǎn)的雙向循環(huán)

2、鏈表中插入一個(gè)新結(jié)點(diǎn)，需要修改的指針域數(shù)量是（D ）A2 個(gè)B3 個(gè)C4 個(gè)D6 個(gè)P28 中void DInsertBefore(DListNode *p,DataType x)/在帶頭結(jié)點(diǎn)的雙鏈表中，將值為x 的新結(jié)點(diǎn)插入結(jié)點(diǎn)*p之前，設(shè) p NULLDListNode *s=malloc(sizeof(ListNode);s-data=x;s-prior=p-prior;s-next=p;p-prior-next=s;p-prior=s;5假設(shè)以數(shù)組 A60 存放循環(huán)隊(duì)列的元素，其頭指針是 front=47，當(dāng)前隊(duì)列有 50個(gè)元素，則隊(duì)列的尾指針值為（D ）-A 3B 37C 50D 9

3、7輔導(dǎo)書P22 中對(duì)于循環(huán)向量中的循環(huán)隊(duì)列，寫出通過隊(duì)頭隊(duì)尾指針表示的隊(duì)列長(zhǎng)度公式。（front指向?qū)嶋H隊(duì)頭，rear指向?qū)嶋H隊(duì)尾的下一元素位置。）當(dāng)rear front時(shí)，隊(duì)列長(zhǎng)度L=rear-front；當(dāng)rearfront時(shí)，L=m+(rear-front)。這兩種情況可統(tǒng)一為L(zhǎng)=(m+(rear-front)%m，這里m 為向量的大小。本題m=60中6若棧采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則下列說法中正確的是（B ）A 需要判斷棧滿且需要判斷?？誃 不需要判斷棧滿但需要判斷?？誄 需要判斷棧滿但不需要判斷?？誅不需要判斷棧滿也不需要判斷棧空P36 中因?yàn)殒湕Ｖ械慕Y(jié)點(diǎn)是動(dòng)態(tài)分配的，可以不考慮上溢，所以無

4、需定義stackFull運(yùn)算。7若串 str= ”Software ”，其子串的數(shù)目是（D ）A 8B 9C 36D 37P51 中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串。8設(shè)有一個(gè) 10 階的下三角矩陣 A ，采用行優(yōu)先壓縮存儲(chǔ)方式，all 為第一個(gè)元素，其存儲(chǔ)地址為1000 ，每個(gè)元素占一個(gè)地址單元，則a85 的地址為（ C ）A 1012B 1017C 1032D 1039P61 中在 n 階方陣 A 這個(gè)下三角矩陣中，第i （ i 從 0 開始）行（ 0 in ）有 i+1個(gè)元素，元素總數(shù)為：n(n+1)/2，并將元素放在一個(gè)向量sa0. n(n+1)/2-1中。若 i j ，則 a

5、ij在左下三角矩陣中，sak與 aij 的對(duì)應(yīng)關(guān)系是 k=i(i+1)/2+j。若 iK，則由表的有序性可知Rmid.n.keys 均大于K，因此若表中存在關(guān)鍵字等于 K 的結(jié)點(diǎn)，則該結(jié)點(diǎn)必定是在位置mid 左邊的子表R1.mid-1中，故新的查找區(qū)間是左子表R1.mid-1；類似地，若 Rmid.keydataS-top；19在串匹配中，一般將主串稱為目標(biāo)串，將子串稱為_模式串 _。 P5520已知廣義表C=(a(b ， c) ， d) ，則： tail(head(tail(C)= _() _。P66 中-若廣義表LS 非空（ n 1 ）（通常用圓括號(hào)將廣義表括起來，用逗號(hào)分割其中的元素。用

6、大寫字母表示廣義表，用小寫字母表示原子。），則 a1 是 LS 的表頭，其余元素組成的表稱為L(zhǎng)S 的表尾。長(zhǎng)度：元素的個(gè)數(shù)深度：表展開后所含括號(hào)的層數(shù)（從最里面往最外面數(shù)）21 用 6 個(gè)權(quán)值分別為6、13 、 18、30 、 7 和 16 的結(jié)點(diǎn)構(gòu)造一棵哈夫曼(Huffman) 樹，該樹 的帶權(quán)路徑長(zhǎng)度為_231_ 。P90 中結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度，是該結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。WPL=30 1+18 2+16 3+13 4+6 5+7 5=30+36+48+52+30+35=23122 已知有向圖如下所示，其中頂點(diǎn)A 到頂點(diǎn) C 的最短路徑長(zhǎng)度是_35_ 。P90 中樹的路徑

7、長(zhǎng)度是從樹根到樹中每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。顯然，在結(jié)點(diǎn)數(shù)目相同的二叉樹中，完全二叉樹的路徑長(zhǎng)度最短。P122 中源點(diǎn) s 到終點(diǎn) v 的最短路徑長(zhǎng)度簡(jiǎn)稱為最短距離。P73 中完全二叉樹（Complete Binary Tree，見圖 6.7 的 b）若一顆二叉樹至多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)（P70 中，一個(gè)結(jié)點(diǎn)擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度Degree 。一顆樹的度是指該樹中的結(jié)點(diǎn)的最大度數(shù)。度為零的結(jié)點(diǎn)稱為葉子Leaf或終端結(jié)點(diǎn)。）可以小于2，而且最下層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。23 對(duì)序列55 ， 46 ， 13 ， 05 ， 94 ， 17 ， 4

8、2 進(jìn)行基數(shù)排序，第一趟排序后的結(jié)果是42,13,94,55,05,46,17。P162 中基數(shù)排序的基本思想是：從低位到高位依次對(duì)Kj （j=d-1,d-2,d-3?,0 ）進(jìn)行箱排序。在d 趟箱排序中，所需的箱子數(shù)就是基數(shù)rd 。K如被排序的記錄關(guān)鍵字i 取值范圍是0-99 間整數(shù)的例子，就是一個(gè)基數(shù)radix為 10 ， d 為 2 的基數(shù)排序。-箱號(hào)0123456789第一次裝箱 (a)42139455,054617內(nèi)容第二次裝箱 (b)箱號(hào)0123456789513,1742,465594內(nèi)容24 高度為 3 的 3 階 B- 樹最少的關(guān)鍵字總數(shù)是_7_ 。輔導(dǎo)書 P147中（最多關(guān)

9、鍵字總數(shù)的解答）一顆高度為h 的 k 階 B- 樹中最多可容納多少個(gè)關(guān)鍵字？解 要使高為 h 的 k 階 B- 樹容納最多的關(guān)鍵字，則每個(gè)結(jié)點(diǎn)中的關(guān)鍵自數(shù)據(jù)就必須達(dá)到最大值k-1. 因此這時(shí)的B- 樹實(shí)際上可看成是滿k 叉樹。不妨設(shè)根的層數(shù)為1，則第1 層只有1 個(gè)根結(jié)點(diǎn)，第2 層上共有 k 個(gè)結(jié)點(diǎn)，第3 層上共有 k2個(gè)結(jié)點(diǎn)， ?，第h 層上共有 kh-1個(gè)結(jié)點(diǎn)，樹中結(jié)點(diǎn)總數(shù)為：由每個(gè)結(jié)點(diǎn)可容納k-1 關(guān)鍵字可知，樹中可容納的關(guān)鍵字總數(shù)為：n=(k-1) m=(k-1)=kh-1以 h=3 ， k=101為例，相應(yīng)的B- 樹最多可容納101 3-1=100+10100+1020100=103

10、0300個(gè)關(guān)鍵字，樹中結(jié)點(diǎn)總數(shù)為3( 101 -1)/100=1+101+10201=10303。示意圖如下：第 1 層：1 個(gè)結(jié)點(diǎn)100 個(gè)關(guān)鍵字第 2 層： 101 個(gè)結(jié)點(diǎn)101100=10100個(gè)關(guān)鍵字2第 3 層： 101 =10201 個(gè)結(jié)點(diǎn)10201100=1020100個(gè)關(guān)鍵字P182 中（最少關(guān)鍵字總數(shù)的解答）一顆 m（ m 3）階的 B-樹，每個(gè)非根結(jié)點(diǎn)中所包含的關(guān)鍵字個(gè)數(shù)j 滿足： m/2-1 j m-1 。即每個(gè)非根結(jié)點(diǎn)至少應(yīng)有 m/2-1 個(gè)關(guān)鍵字，至多有m-1 個(gè)關(guān)鍵字。（注： m/2是指不小于（即大于等于）m/2 的最小整數(shù)。）h一顆高度為h 的 m 階 B- 樹中

11、最少可容納的關(guān)鍵字總數(shù)為： m/2 -1 ，最少可容納的結(jié)點(diǎn)總數(shù)為h m/2 -1- m/2 -1以 h=3 ， m=3 為例，相應(yīng)的B-樹最少可容納的關(guān)鍵字總數(shù)為第 1 層：1 個(gè)結(jié)點(diǎn) m/2 -1=1 個(gè)關(guān)鍵字第 2 層：2 個(gè)結(jié)點(diǎn)h 3 m/2 -1= 2 -1=7 個(gè)。示意圖如下：2個(gè)關(guān)鍵字2第 3 層：2 =4 個(gè)結(jié)點(diǎn)4個(gè)關(guān)鍵字25 VSAM 通常作為大型索引順序文件的標(biāo)準(zhǔn)組織，其動(dòng)態(tài)索引結(jié)構(gòu)采用的是_B+樹 _。 P214三、解答題 ( 本大題共4 小題，每小題5 分，共20 分)26 假設(shè)二叉樹的RNL 遍歷算法定義如下：若二叉樹非空，則依次執(zhí)行如下操作：(1)遍歷右子樹；(2)

12、訪問根節(jié)點(diǎn)；(3)遍歷左子樹。已知一棵二叉樹如圖所示，請(qǐng)給出其RNL 遍歷的結(jié)果序列。GCFABDP77 頁圖 6.11 中的中序序列LNR 、前序序列NLR 、后序序列LRN27 已知一個(gè)無向圖G=(V ，E) ，其中V=A ， B，C， D， E ， F ，鄰接矩陣表示如下所示。請(qǐng)回答下列問題：(1) 請(qǐng)畫出對(duì)應(yīng)的圖 G 。 P103 中的圖 7.7012345ABCDEF0 A0101001 B1011102 C0100013 D110010-4E0101015F001010(2) 畫出圖 G 的鄰接表存儲(chǔ)結(jié)構(gòu)。P105 中圖 7.8vertexfirstedgeadjvexnext28

13、 已知一18 ，012345A13B0234C15D014E135F24頂點(diǎn)表邊表組待排記錄的關(guān)鍵字序列為(16 ， 12，60，15， 36， 14， 18， 25， 85) ，用堆排序方法建小根堆，請(qǐng)給出初始建堆后的序列。P154 中，注： n=10 ，從第 n/2 （ 1 i ）個(gè)結(jié)點(diǎn)起進(jìn)行調(diào)整。若i=5 ，則與 i=10或 i=11進(jìn)行互換；即 i 與 2i或 2i+1中的關(guān)鍵字進(jìn)行互換。P152 中，堆排序利用了大根堆( 或小根堆 ) 堆頂記錄的關(guān)鍵字最大( 或最小 ) 這一特征，大根堆排序結(jié)果是遞增有序的，小根堆排序結(jié)果是遞減有序的。161612181218601536141815

14、3614182585602585123456789101234567891016121860153614182585161218181536146025851612i=5 ，不調(diào)整i=4，調(diào)整12141514181636181815361860258512345678910161214181536186025856025851234567891012151418163618602585i=2，不調(diào)整i=1，調(diào)整i=3 ，調(diào)整小根堆初始建堆后的序列-29 已知一棵二叉排序樹如圖所示。請(qǐng)回答下列問題：(1) 畫出插入元素 23 后的樹結(jié)構(gòu)；23(2) 請(qǐng)畫出在原圖中刪除元素57 后的樹結(jié)構(gòu)。P17

15、4 中二叉排序樹(Binary Sort Tree)性質(zhì) (BST性質(zhì)) ：若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；-左右子樹本身又各是一棵二叉排序樹。二叉排序樹BST 的特點(diǎn)（ 1） 二叉排序樹中任一結(jié)點(diǎn)x，其左 ( 右 ) 子樹中任一結(jié)點(diǎn)y( 若存在 ) 的關(guān)鍵字必小( 大 ) 于 x 的關(guān)鍵字。（ 2） 二叉排序樹中，各結(jié)點(diǎn)關(guān)鍵字（我理解是中間節(jié)點(diǎn)，即N）是惟一的。還有另外一個(gè)重要性質(zhì)：按中序遍歷LNR 該樹所得到的中序序列是一個(gè)遞增有序序列，RNL 則得到一個(gè)遞減有序序列。四、算法閱讀題(本大題共4 小題，每小

16、題5 分，共20 分 )30 已知下列程序，Ls 指向帶頭結(jié)點(diǎn)的單鏈表。Typedef struct node DataType data;struct node * next; * LinkList;void f30( LinkList Ls ) LinkList p, q; q= Ls-next;if ( q & q-next ) Ls-next = q-next; p=qwhile ( p-next )p = p-next;p-next = q;q-next = NULL;請(qǐng)回答下列問題：(1) 當(dāng) Ls 指向的鏈表如下圖所示，請(qǐng)畫出執(zhí)行本函數(shù)之后的鏈表的結(jié)果。(2) 請(qǐng)簡(jiǎn)述算法的功能。

17、-刪除單鏈表的中間結(jié)點(diǎn)和尾結(jié)點(diǎn)。31 已知字符串處理函數(shù)f31 程序如下。int f31(char*strl， char*str2) while(*strl=*str2&(*strl!= 0 )strl+；str2+；return(*strl-*str2 ? l 0) ；請(qǐng)回答下列問題：(1) 若調(diào)用語句是f31( ” abcde ”，” abcdf ” ) ，則函數(shù)的返回值是什么?答：A 的 ASCII 065 A 的 ASCII 097由于 e 對(duì)應(yīng)的ASCII 碼是 101 ， f 對(duì)應(yīng)的ASCII 碼是 102 ，則 e f=101 102=-1再按照條件表達(dá)式的形式為邏輯表達(dá)式？表達(dá)

18、式1 ：表達(dá)式2若邏輯表達(dá)式的值為非零，則條件表達(dá)式的值等于表達(dá)式1 的值；若邏輯表達(dá)式的值為零，則條件表達(dá)式的值等于表達(dá)式2的值。則函數(shù)的返回值是1 。若調(diào)用語句是f31( ”abcde ”，” abcde ”) ，則函數(shù)的返回值是什么?答：由于字符串結(jié)束標(biāo)識(shí)0 對(duì)應(yīng)的 ASCII 碼是 0，則 *strl-*str2=0再按照條件表達(dá)式的形式為邏輯表達(dá)式？表達(dá)式1 ：表達(dá)式 2若邏輯表達(dá)式的值為非零，則條件表達(dá)式的值等于表達(dá)式1 的值；若邏輯表達(dá)式的值為零，則條件表達(dá)式的值等于表達(dá)式2的值。則函數(shù)的返回值是0。(2) 簡(jiǎn)述該函數(shù)的功能。答：如果兩個(gè)字符串結(jié)點(diǎn)*strl和 *strl中的字符

19、相等，且字符串結(jié)點(diǎn)*strl中的字符不等于字符串結(jié)束標(biāo)識(shí) 0，則兩個(gè)字符串結(jié)點(diǎn)*strl和*strl中的字符指針自加運(yùn)算。如果條件不滿足，則字符串結(jié)點(diǎn)*strl和 *strl中的字符相減。若邏輯表達(dá)式的值為非零，則條件表達(dá)式的值等于1；若邏輯表達(dá)式的值為零，則條件表達(dá)式的值等于0。32 數(shù)組A 中存儲(chǔ)有n 個(gè)整數(shù)，請(qǐng)閱讀下列程序。void f32(intA， int n)- int i ， j ， k， x； k=n-l ；while(k0)i=k； k=0 ；for(j=O； jAj+1)x=Aj；Aj=Aj+l；Aj+1=x；k=j； end of if end of while retu

20、rn ；請(qǐng)回答下列問題：(1)當(dāng) A=10 ， 8， 2， 4， 6， 7 時(shí)，執(zhí)行f32(A ， 6) 后，數(shù)組A 中存儲(chǔ)的結(jié)果是什么?答：數(shù)組 A 中存儲(chǔ)的結(jié)果是10。(2)說明該算法的功能。答：數(shù)組A 中存儲(chǔ)有n 個(gè)整數(shù)，當(dāng)k=n-1 時(shí)，則第k 個(gè)向量是最后一個(gè)整數(shù)。當(dāng) k0 時(shí)，即數(shù)組A 非空時(shí)，設(shè)i=k ， k=0 ，如果 j=0 ，且 ji （即 j 小于 k ）時(shí)， j 自加（即數(shù)組下標(biāo)自加）；同時(shí)比較第j 個(gè)整數(shù)和第j+1 個(gè)整數(shù)。如果第j 個(gè)整數(shù)大于第j+1 個(gè)整數(shù)，則通過語句x=Aj；Aj=Aj+l；Aj+1=x；進(jìn)行交換，同時(shí)令k=j 。如果 j 大于等于i （即 j

21、大于等于k）時(shí)，則結(jié)束執(zhí)行if語句和while 語句，并返回。33 下面程序?qū)崿F(xiàn)二分查找算法。Typedef structKeyType key；InfoType otherinfo；SeqListN+1；int BinSearch(SeqList R, int n， KeyType K) int low=1，high=n；while( (1)lowK)high=mid-1；else(3)low=mid+1；return O； BinSearch請(qǐng)?jiān)诳瞻滋幪顚戇m當(dāng)內(nèi)容，使該程序功能完整。(1) lowlchild)+ SumNodes(T-rchild)+1;-輔導(dǎo)書P66 P76 第四題的第

22、2 小題中問：寫一遞歸算法求二叉樹中度為2 的結(jié)點(diǎn)總數(shù)答：二叉樹中度2 度結(jié)點(diǎn)數(shù)的遞歸定義如下：當(dāng) T 為空或 T 是葉子時(shí)，以T 為根的二叉樹的2 度結(jié)點(diǎn)數(shù)為 0 ；當(dāng) T 是 2 度結(jié)點(diǎn)時(shí)，以T 為根的二叉樹的2度結(jié)點(diǎn)數(shù)為T 的左右子樹中2 度結(jié)點(diǎn)數(shù)之和再加上T 結(jié)點(diǎn)本身；當(dāng) T 是 1 度結(jié)點(diǎn)時(shí)，以T 為根的二叉樹中2度結(jié)點(diǎn)數(shù)為T 的左右子樹中2 度結(jié)點(diǎn)數(shù)之和。算法如下：int D2Nodes(BinTree T)if(! T ! T-lchild & ! T-rchild)/ 邏輯運(yùn)算符的執(zhí)行優(yōu)先次序是：！非 -& 與 - 或，即 T 為空或 T 是葉子return 0;if(T-lc

23、hild & T-rchild)/T是2度結(jié)點(diǎn)return 1+D2Nodes(T-lchild)+D2Nodes(T-rchild);else /T是 1 度結(jié)點(diǎn)return D2Nodes(T-lchild)+D2Nodes(T-rchild);二、在任何事情上都不要覺得自己受了多大的委屈，哭哭啼啼和別別扭扭改變不了糟糕的現(xiàn)狀。心子開一點(diǎn)，認(rèn)真地該干啥干啥，反倒走得順暢許多?？傅米《嗌贃|西，最后就會(huì)得到多少東西，大致就是這么個(gè)理兒吧。三、生命本沒有意義，你要能給他什么意義，他就有什么意義。與其終日冥想人生有何意義，不如試用此生做點(diǎn)有意義的事。四、愛怕沉默。太多的人，以為愛到深處是無言。其實(shí)

24、，愛是很難描述的一種情感，需要詳盡的表達(dá)和傳遞。五、有些路，只能一個(gè)人走。六、有一種落差是，你配不上自己的野心，也辜負(fù)了所受的苦難。七、有些決定，只需要一分鐘，可是，卻會(huì)用一輩子，去后悔那一分鐘。八、“忽然想通了”, 這五個(gè)字說來簡(jiǎn)單，要做到可真不容易。我佛如來在菩堤樹下得道，就因?yàn)樗昂鋈幌胪恕边_(dá) . 摩祖師面壁十八年，才總算“忽然想通了”無 . 論什么事，你只要能“忽然想通了”, 你就不會(huì)有煩惱，但達(dá)到這地步之前，你一定已不知道有過多少煩惱。九、如果他總為別人撐傘，你何苦非為他等在雨中。-十、我對(duì)前任的感覺很簡(jiǎn)單，哪怕他的女朋友來我面前秀恩愛，我也不會(huì)覺得煩。就像在看別人吃一碗很香的鹵肉

25、飯，吧唧嘴巴弄得很大聲，但我自己心里是明白的：我吃過那種飯，其實(shí)沒那么好吃。十一、為什么我們總是不懂得珍惜眼前人？在未可預(yù)知的重逢里，我們以為總會(huì)重逢，總會(huì)有緣再會(huì)，總以為有機(jī)會(huì)說一聲對(duì)不起，卻從沒想過每一次揮手道別，都可能是訣別，每一聲嘆息，都可能是人間最后的一聲嘆息。十二、我在最好的時(shí)候碰到你，是我的運(yùn)氣?？上覜]時(shí)間了。想想，說人生無悔，都是賭氣的話。人生若無悔，那該多無趣啊。我心里有過你。可我也只能到喜歡為止了。十三、我說不出來為什么愛你，但我知道，你就是我不愛別人的理由。十四、當(dāng)你在轉(zhuǎn)圈的時(shí)候，這個(gè)世界很大，當(dāng)你勇往直前，這個(gè)世界就很小。十五、現(xiàn)在男女之間的戀愛，總是答應(yīng)太快，結(jié)果分手也快。人性的規(guī)律是容易得到的就容易放棄。凡是通過努力得到的，不管是感情還是物品，都會(huì)使人頓生珍惜之感。所以在感情上，當(dāng)-有人追求時(shí)，內(nèi)心的一份矜持是必要的，即使心里很愛，也需要給追求者時(shí)間和難