2015年珍藏答案

1、1)填空題：序號(hào)1-80【1 , 1 , 2】線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中兀素之間存在多對(duì)多關(guān)系?！?, 1 , 2】為了最快地存取數(shù)據(jù)元素，物理結(jié)構(gòu)宜采用_順序存儲(chǔ)_結(jié)構(gòu)?！?, 1 , 2】數(shù)據(jù)結(jié)構(gòu)的三要素是 邏輯結(jié)構(gòu)，物理結(jié)構(gòu)，操作?！?, 1, 2】數(shù)據(jù)的邏輯結(jié)構(gòu)可形式地用一個(gè)二元組B= (K, R)來表示，其中K是_數(shù)據(jù)元素的有限集合R是 K上關(guān)系的有限集_?！?, 1 ,2】存儲(chǔ)結(jié)構(gòu)可根據(jù)數(shù)據(jù)元素在機(jī)器中的位置是否一定連續(xù)分為順序存儲(chǔ)結(jié)構(gòu)_,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?！?, 1 , 4】度量算法效率可通過時(shí)間復(fù)雜度來進(jìn)行?！?, 1 , 4】算

2、法的五個(gè)重要特性是確定性、 可行性 、 有窮性、輸入和輸出?！?, 1, 4】設(shè)n為正整數(shù)，則下面程序段的時(shí)間復(fù)雜度是0(n)。i=1; k=0;while(i< n)k=k+10*i ； i+；【9, 1 , 4】設(shè)n為正整數(shù)，下面程序段中前置以記號(hào) 的語句的頻度是 n(n +1)/2 。for (i=0; i<n; i+)for (j=0; j< n; j+)if (i+j=n-1)aij=0;【10 , 1, 4】設(shè)n為正整數(shù)，試確定下列各程序段中前置以記號(hào)的語句的頻度：(1) i=1;k=0;while (i<=n-1)i+; k+=10 * i; /語句的頻度

3、是 n-1。 k=0;for (i=1;i<=n ;i+)for (j=i; j<=n ;j+)k+;/語句的頻度是 n(n+1)/2?！?1 , 1, 4】按增長率由大到小排列下列函數(shù)的結(jié)果是_ n2n logy n_ n1/2logy_iogz(iogg n),。2 1/2log2 (log2 n), n Iog2 n, n2, n , log2 n, n【12,2,1】當(dāng)線性表的規(guī)模比較大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，一般以采用動(dòng)態(tài)鏈表的存儲(chǔ)結(jié)構(gòu)為好。【13, 2, 1】線性表(a1, a2,，an)有兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，請(qǐng)就這兩種存儲(chǔ)結(jié)構(gòu)完成下列填充：順序存

4、儲(chǔ)密度較大:順序存儲(chǔ)利用率較高:順序可以隨機(jī)存取:鏈?zhǔn)讲豢梢噪S機(jī)存?。绘?zhǔn)讲迦牒蛣h除操作比較方便?！?4, 2, 2】從一個(gè)長度為n的順序表中刪除第i個(gè)元素(Ki于耐，需向前移動(dòng) _ n-i 個(gè)元素。【15 , 2, 3】帶頭結(jié)點(diǎn)的雙鏈表L為空的條件是 L->next=L或L->prior=L ?！?6, 2, 3】帶頭結(jié)點(diǎn)的單鏈表Head為空的條件是 Head-next=NULL。【17 , 2, 3】非空單循環(huán)鏈表L中*p是尾結(jié)點(diǎn)的條件是p->next=L。【18 , 2, 3】在一個(gè)單鏈表中p所指結(jié)點(diǎn)(p所指不是最后結(jié)點(diǎn))之后插入一個(gè)由指針s所指結(jié)點(diǎn)，應(yīng)執(zhí)行 s->

5、;next=_ p->next;禾口 p->next= s_ 的操作?！?9, 2, 3】在一個(gè)單鏈表中的指針p所指結(jié)點(diǎn)之前插入一個(gè)由指針s所指結(jié)點(diǎn)，可執(zhí)行以下操作序列：s->next=p->next ； ;p_>n ext=s;t=p->data;p->data= s->data:;s->data=t;【20 , 2, 3】在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：q= p_>n ext;p->data= p->n ext->data;p->n ext=p->next->next :free

6、(q);P所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的語句是P->next【21 , 2 , 3】在單鏈表中，刪除指針P->n ext- >n ext;?！?2 , 2, 3】帶頭結(jié)點(diǎn)的單循環(huán)鏈表Head 的判空條件是 _ Head-next = Head;不帶頭結(jié)點(diǎn)的單循環(huán)鏈表的判空條件是.Head = NULL; _。_Head->next = Head = Head【23，2，3】刪除帶頭結(jié)點(diǎn)的單循環(huán)鏈表Head的第一個(gè)結(jié)點(diǎn)的操作是Head-next-next: ；刪除不帶頭結(jié)點(diǎn)的單循環(huán)鏈表的第一個(gè)結(jié)點(diǎn)的操作是->n ext; ?！?4，2, 3】已知L是帶表頭結(jié)點(diǎn)的非空單鏈表 ，

7、且P結(jié)點(diǎn)既然不首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)， 試從下列提供的答案中選擇合適的語句序列。a. 刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是1012811414b. 刪除結(jié)點(diǎn) P的語句序列是 10127314c. 刪除尾元結(jié)點(diǎn)的語句序列是9 113 14。(1) P = P-> next;(2) P->next = P;(3) P->next = P->n ext ->n ext;(4) P = P->next ->n ext;(5) while (P != NULL) P = P->next; while (Q-> next != NULL)P = Q;

8、 Q = Q-> next;(7) while (P-> next != Q) P = P-> next;(8) while (P-> next-next != Q) P = P-> next;(9) while (P-> next-next != NULL) P = P-> next;(10) Q = P;(11) Q = P-> next;(12) P = L;(13) L = L-> next;(14) free (Q);【25，3，1】棧操作的原則是 先進(jìn)后出/后進(jìn)先出【26，3，1】對(duì)一個(gè)棧，給定輸入的順序是A、B C，則全部不可

9、能的輸出序列有不可能得到的輸出序列有 CAB?！?7，3，1】數(shù)據(jù)A、B、C、D依次進(jìn)棧后，再從棧中取一數(shù)據(jù)，則它是 則本棧得到 DCBA的輸出序列，其理由是根據(jù)后進(jìn)先出的原則， 首先得到D，在棧內(nèi)的數(shù)由底到頂依 次是A、B C,而出棧的次序剛好相反，即 DCBA= _?！?8，3，1】.在棧頂指針為 HS的鏈棧中，判定?？盏臈l件是 head->n ext=NULL【30, 3, 2】下列程序把十進(jìn)制數(shù)轉(zhuǎn)換為十六進(jìn)制數(shù)，請(qǐng)?zhí)顚懞线m的語句成分。(每空2 分)void con versio n10_16() In itStack(&s);scanf( “ d' ，&N

10、);while(N) Push(s, N%16);N = N/16; while(!StackEmpty(s) Pop(s, e);if(e<=9)printf(“ d' ,e);else printf(“+'A,e); /* conversion */【31 , 3, 4】若一個(gè)棧的輸入序列為1,2,3,，n輸出序列的第一個(gè)元素為 n,則第i個(gè)輸出兀素是 n i+ 1 o【32 , 3, 4】若用一個(gè)大小為 6個(gè)元素的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 rear=0和front=3。 當(dāng)從隊(duì)列中刪除一個(gè)元素， 再加入兩個(gè)元素后，rear和front的值分別是 _2和_4?！?3

11、, 3, 4】已知一個(gè)棧的輸入序列為1, 2, 3,，n,輸出序列為a1,a2,a3,盟 那么a2=n的輸出序列共有_ n-1種?！?4 ,3 ,4】堆棧和隊(duì)列都是線性表，堆棧是后進(jìn)先出的線性表，而隊(duì)列是先進(jìn)先出 的線性表。【35 , 3 , 4】從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先移動(dòng)隊(duì)首元素，后取出元素?！?6, 3 , 4】若用一個(gè)大小為6個(gè)元素的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 rear=0和front=3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別是 2 和4。【37 , 3, 4】下面是關(guān)于循環(huán)隊(duì)列的操作，請(qǐng)?jiān)趧澗€空白處填寫合適語句成分。Status En

12、Queue(SqQueue &Q, QelemType e)if(Q.rear+1)%MAXSIZE=Q.front) retrunERROR;Q.base(Q.rear) = e;Q.rear=(Q.rear+1)%MAXSIZE;return OK; / En Queue【38 , 4, 1】空串是 零個(gè)字符的串 ，其長度為 零。【39 , 4 , 1 】 設(shè)串 s仁"teachers and “ ,s2= ” stude nt則"StrLe ngth(s2)=8Concat(s1,s2)="teachers and stude nts"?！?/p>

13、40, 4, 1 】設(shè) s ='AM A TEACHER 其長度是 14?！?1 , 4, 1】兩個(gè)串相等的充分必要條件是 兩個(gè)串的長度相等且對(duì)應(yīng)位置的字符相同。【42 , 4 , 2】串的兩種最基本的存儲(chǔ)方式是順序存儲(chǔ)方式和鏈接存儲(chǔ)方式?！?3, 4, 3】令有串 u=” aabcaab和 v=” abcaabcaabcaaba",(1) 求 Index(v,u,5)的值：Index(v,u,5)=8; (2 分)(2) 求出u作為模式串時(shí)在 KMP算法中的nextj值。(2分)j1234567uaabcaabn extj0121123【44 , 5, 1】二維數(shù)組 A10

14、20采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元，并且A00的存儲(chǔ)地址是 200,則 A610的地址是 332?！?5 , 5, 1】設(shè)每個(gè)元素需要8個(gè)字節(jié)，順序存儲(chǔ)100個(gè)元素，若首地址是2500 ,那么第50個(gè)元素的地址是2892。【46 , 5, 2】已知二維數(shù)組Amn采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC(A00)，則Aij的地址是 _LOC (A00) + (n*i + j) k【47 , 5, 2】C語言采用行優(yōu)先方式存放數(shù)組元素，數(shù)組下標(biāo)從0開始。設(shè)維數(shù)為(5,6,7)的數(shù)組 A5x6x7的起始存儲(chǔ)地址為 Loc000=1000，每個(gè)數(shù)組元

15、素占用 4個(gè)字節(jié)。則元素 A444所在的地址 Loc444= 1800?！?8 , 5, 2】按行優(yōu)先次序列出三維數(shù)組A232的所有12個(gè)元素在內(nèi)存中的存儲(chǔ)次序，它們依次是：A000A001A010A011A020A021A100A101A110A111A120A121【49 , 5, 3】對(duì)一個(gè)10階對(duì)稱矩陣A,采用壓縮存儲(chǔ)方式(以行序?yàn)橹餍?，且A00的地址為1)，則A85的地址是 34?！?0，5，3】對(duì)一個(gè)10階三對(duì)角矩陣 A，采用壓縮存儲(chǔ)方式(以行序?yàn)橹餍?，且A00的地址為1，每個(gè)元素占4個(gè)字節(jié))，則A65的地址是 69?！?1，5, 3】對(duì)一個(gè)對(duì)稱矩陣A( aj=aji,O<=

16、i,j<=n)，采用下三角壓縮存儲(chǔ)方式存儲(chǔ)在一維數(shù)組S1.M中(以行序?yàn)橹餍?，且A00=S1),則Aij (i>=j)對(duì)應(yīng)S中的下標(biāo)是 i*(i+1)/2+ j+1;一維數(shù)組 S的大小 M至少為(n +1)*(n+1) ?！?2，6，1】已知一棵樹邊的集合是<a,d>,<d,c>,<d,j>,<e,a>,<f,g>,<d,b>,<g,h>,<g,i>,<e,f>。那么根結(jié)點(diǎn)是e，結(jié)點(diǎn) b的雙親是 d，結(jié)點(diǎn) a的子孫有 bcdj ，樹的深度是 4，樹的度是 3，結(jié)點(diǎn)g在樹的第

17、3層。【53，6，2】通常使用 二叉鏈表 來表示二叉樹結(jié)構(gòu)?！?4，6, 2】從概念上講，樹與二叉樹是二種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本的目的是 .樹可采 用二叉 樹的存儲(chǔ) 結(jié)構(gòu)并利 用二 叉樹的已 有算法解 決樹 的有關(guān)問題?！?5，6, 2】在圖1至圖5中，1,2,3,4,5是樹，1,2,3,4是叉樹，123是完全二叉樹， 13是滿二叉樹。圖4圖5【56 , 6, 3】在圖4中，結(jié)點(diǎn)H在這棵樹的前序、中序和后序遍歷次序中分別是6_、第_5 和第 3個(gè)結(jié)點(diǎn)。【57，6, 2】滿三叉樹的第i層的結(jié)點(diǎn)個(gè)數(shù)為 3i-1，深度為h時(shí)該樹中共有 3h-1結(jié)點(diǎn)?！?8，6, 2】在圖4中，A是_

18、根_結(jié)點(diǎn)，D是_葉子_結(jié)點(diǎn)，B是E的_父親，B是G的祖先，D是E的兄弟。這棵樹的度是 6，深度是_4。【59，6, 2】程序填空：下列算法是求以二叉鏈表存儲(chǔ)的二叉樹中的最小值，設(shè)數(shù)據(jù)域的類 型為int。void minnode(BiTree T, int *min)if(T!=NULL)if( *min>T->data ) *min = T->data;mi nno de(T->lchild,mi n);minnode(T->rchild,min);【60, 6，2】已知一棵完全二叉樹有56個(gè)葉子結(jié)點(diǎn)，從上到下、從左到右對(duì)它的結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)為 1號(hào)。則該完全

19、二叉樹總共結(jié)點(diǎn)有111個(gè)；有7_層；第91號(hào)結(jié)點(diǎn)的雙親結(jié)點(diǎn)是 45號(hào)；第63號(hào)結(jié)點(diǎn)的左孩子結(jié)點(diǎn)是 號(hào)?！?1 , 6, 2】下列表示的圖中，共有 _5個(gè)是樹；有 3個(gè)是二叉樹；有_2個(gè)是完全二叉樹?！?2 , 6 , 3】下列二叉樹的中序遍歷序列是DBNGOAE ;后序遍歷序列是DNIGBECA。【63 , 6, 3】一棵二叉樹的中序遍歷序列是DBNGOAEC后序遍歷序列是 DNOGBECA則其先序遍歷的序列中的第一個(gè)元素是_ A_，第五個(gè)元素是_N_，最后一個(gè)元素是_E_【64，6，3】下列二叉樹的先序遍歷序列的第5個(gè)結(jié)點(diǎn)是 _N_;第8個(gè)結(jié)點(diǎn)是_E后序遍歷序列的第 2個(gè)結(jié)點(diǎn)是_N;第6個(gè)結(jié)

20、點(diǎn)是_E_。ACE【65，6, 3】如果某二叉樹的后序遍歷序列是ABCDEFGHJ中序遍歷序列是 ACBIDFEHG則【66，6, 3】程序填空：設(shè)算法 歷算法。下列算法是判斷無向圖其先序遍歷序列的第一個(gè)字母是 I ，最后一個(gè)字母是 G。DFS(Mgraph *G, int i)是無向圖G從i頂點(diǎn)開始的深度優(yōu)先遍G是否是連通的。int isc onn ect(Mgraph *G) int i,k=0;for(i=0; i<G->vex num; i+)visitedi = 0;for(i=0; i<G->vex num; i+)if(!visitedi)k+；DFS(G

21、, i);if(k=1) return 1;else return 0;【67, 7, 2】圖有鄰接矩陣和鄰接表_等存儲(chǔ)結(jié)構(gòu)?！?8 , 7, 2】設(shè)無權(quán)圖G的鄰接矩陣為 人，若(vi,vj)屬于圖G的邊集合，則對(duì)應(yīng)元素Aij等于_ 1_，設(shè)無向圖G的鄰接矩陣為 A，若Aij等于0,則Aji等于0_。【69，乙2】若一個(gè)圖用鄰接矩陣表示，則計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是 _求矩陣第i列非零元素之和。【70，乙2】若一個(gè)圖用鄰接矩陣表示，則刪除從第 i個(gè)頂點(diǎn)出發(fā)的所有邊的方法是_矩陣第i行全部置為零_?！?1，7，4】n個(gè)頂點(diǎn)的連通圖至少有_n 1_條邊。【72 ,乙4】設(shè)一個(gè)圖 G=V,A,V=

22、a,b,c,d,e,f,A=<a,b>,<b,e>,<a,e>,<c,a>,<e,d>,<d,f>,<f,c>。那么頂點(diǎn)e 的入度是2;出度是 _1_ ;通過頂點(diǎn)f的簡單回路有 2_條；就連通性而言，該圖是強(qiáng)連通 _圖；它的強(qiáng)連通分量有_ 1 _個(gè)；其生成樹可能的最大深度是_5_。【73 ,乙5】下面有向圖共有 4_個(gè)頂點(diǎn)；從v3到v2的最短簡單路徑之一是 _v3 v4 v2; v1的出度是_2;包含所有頂點(diǎn)的簡單路徑之一是 v3v4 v1 v2?！?4 , 9, 2】n個(gè)結(jié)點(diǎn)的二叉排序樹的最大深度是_n，最小

23、深度為 log 2n+1【75 ,9, 3】設(shè)有一組關(guān)鍵字9,01,23,14,55,20,84,27，采用哈希函數(shù)：H(key)=key mod 7,表長為10,用開放地址法的二次探測再哈希方法Hi=(H(key)+di) mod 10(di = 12,22,32,)解決沖突。要求：對(duì)該關(guān)鍵字序列構(gòu)造哈希表，并計(jì)算查找成功的平均查找 長度。哈希 地址0123456789關(guān)鍵字140192384275520比較 次數(shù)11123412平均查找長度： ASL = (1+1+1+2+3+4+1+2)層=158以關(guān)鍵字 27 為例，H(27)=27%7=8(沖突)，H仁(6+1)%10=7(沖突)，H

24、2=(6+22)%10=0(沖突)， H3=(6+33)%10=5，所以比較了 4 次?！?6，10，1】排序過程一般需經(jīng)過兩個(gè)基本操作，它們是_比較 _和移動(dòng)_?！?7，10，2】結(jié)點(diǎn)的關(guān)鍵字序列是(F,B,J,G,E,A,I,D,C,)對(duì)它按字母的字典序進(jìn)行排列。 如果采用 Shell排序方法，那么步長取5時(shí)，第一次掃描結(jié)果的前5個(gè)字母分別是(A,B,D,C,E)?！?8，10, 2】在對(duì)一組關(guān)鍵字是(54,38,96,45,15,72,60,23,83 )的記錄進(jìn)行直接插入排序時(shí)，當(dāng)把第七個(gè)記錄(關(guān)鍵字是60 )插入到有序表時(shí)，為尋找插入位置需比較_3_次?！?9，10，3】在利用快速排

25、序方法對(duì)一組關(guān)鍵字是(54,38,96,45,15,72,60,23,83 )的記錄進(jìn)行排序時(shí)，需要遞歸調(diào)用partition函數(shù)，遞歸的最大深度(設(shè)第一次調(diào)用深度為 1)為_3_， 共需5次遞歸調(diào)用，其中第二次遞歸調(diào)用是對(duì)關(guān)鍵字是 (23，38，15，45)_的一組記錄進(jìn)行的?！?0， 10， 4】插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序、和基數(shù)排 序方法中，不穩(wěn)定的排序方法有希爾排序、快速排序、堆排序 _。4)分析計(jì)算作圖題：序號(hào)1-55 (選自數(shù)據(jù)結(jié)構(gòu)題集 一嚴(yán)蔚敏等 編)【1，1，4】(選自數(shù)據(jù)結(jié)構(gòu)題集1.8,選做題)設(shè)n為正整數(shù)，試確定下列各段程序中前置以記號(hào)的語句的

26、頻度(語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù))。(1)i=1; k=0;while (i<=n-1)i+；k+=10*i;答：該語句的頻度為n-1(2)x=91;y=100;while(y>0)if(x>100) x-=10; y-;else x+;答：在循環(huán)中，if語句為真1次，else語句執(zhí)行10次，所以if語句執(zhí)行11次y 的值減1。該語句的頻度為100x(1+10) = 1100【2，1，4】(選自數(shù)據(jù)結(jié)構(gòu)題集1.9,選做題)假設(shè)n為2的乘幕，并且n>2,試求下列算法的時(shí)間復(fù)雜度及變量count的值(以n函數(shù)形式表示)int Time (int n) count

27、=0; x=2;while( x<n/ 2 )x*=2; cou nt+;return (cou nt); / Time答：從while的循環(huán)控制可以看出，n每增加一倍,count的值增加1。所以該算 法的時(shí)間復(fù)雜度為O(log2 n)，根據(jù)初值，變量count的值為Iog2 (n-2)-12.6,必做題)P既不是首元結(jié)點(diǎn)也不是尾元結(jié)點(diǎn)，試(4) (1)(7) (11) ( 8) (4) (1) .(5)(12) (9) (1) ( 6) 【3， 2, 3】(選自數(shù)據(jù)結(jié)構(gòu)題集 已知L是無表頭結(jié)點(diǎn)的單鏈表，且 從下列提供的答案中選擇合適的語句序列a.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是 b .

28、在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是 c.在表首插入S結(jié)點(diǎn)的語句序列是 _ d .在表尾插入S結(jié)點(diǎn)的語句序列是 _(1) P > n ext = S ;(2)P -> n ext=P >next > n ext;(3)P -> n ext=S >next;(4)S -> n ext=P >next ;(5)S -> n ext=L;(6)S -> n ext=NULL;(7)Q=P;(8)while (P> next !=Q) P = P -> n ext ;(9)while (P> next !=NULL) P =P

29、> next ;(10)P=Q;(11)P=L;(12)L=S;(13)L=P;【4,2, 2】(選自數(shù)據(jù)結(jié)構(gòu)題集2.10,選做題)指出以下算法中的錯(cuò)誤和低效(即費(fèi)時(shí))之處，并將它改寫為一個(gè)既正確又 高效的算法。Status DeleteK ( SqList &a， int i，int k)/本過程從順序存儲(chǔ)結(jié)構(gòu)的線性表a中刪除第i個(gè)元素起的k個(gè)元素if( i < 1| k < 0| i + k > a.length)return INFEASIBLE; / 參數(shù)不合法else for (count = 1; count < k ; count + ) /

30、刪除一個(gè)元素for (j = a.length ； j >= i +1 ； j) a.elemj 1 = a.elemj；a. len gth;return OK ; / DeleteK答：錯(cuò)誤之處：題中有下劃線處應(yīng)改為：for (j = i+1; j <= a.length; j+)a.elemj 1 = a.elemj;低效費(fèi)時(shí)之處：該算法每刪除一個(gè)元素，其后所有的元素都向前移一位，包括 將要?jiǎng)h除的元素，比較耗時(shí)間。(其中n = a.length)下 劃 線 的 語 句 的 頻 度 為：>1 i + (n i X)十+ i k 1 kn ij 丄改進(jìn)方法是將k個(gè)元素在一個(gè)

31、循環(huán)內(nèi)刪除，算法如下：Status DeleteK (SqList &a, int i，int k) /本過程從順序存儲(chǔ)結(jié)構(gòu)的線性表a中刪除第i個(gè)元素起的k個(gè)元素if (i < 1| k < 0 | i + k > a.length) return INFEASIBLE / 參數(shù)不合法else for (count = 0; count < a.length k i; count +) a.elemi-1+ count = a.elemk + i-1 + cou nt ;/刪除k個(gè)元素a.len gth = a.len gth k;return OK； / De

32、leteK5， 3，1】（選自數(shù)據(jù)結(jié)構(gòu)題集 3.4，必做題） 簡述以下算法的功能（棧的元素類型SEIemType為int）（ 1） Status algo1（ Stack S）int i， n ， A255 ；n = 0;whiIe （！ StackEmpty （S） n +；Pop（S，An ）； for （i = 1; i < = n ; i +） Push （S, Ai）;功能：利用數(shù)組A,將棧中所有的元素倒置。( 2) Status aIgo2( Stack S, int e ) Stack T； int d ；InitStack ( T)；whiIe (！ StackEmpty

33、 ( S) Pop( S, d )；if (d != e) Push (T, d);whiIe (！ StackEmpty ( T) Pop( T, d)；Push( S, d)；功能：將棧S中與e相同的元素刪除。【 6,3, 1】(選自數(shù)據(jù)結(jié)構(gòu)題集 3.15,選做題)假設(shè)以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)一個(gè)雙向棧, 即在一堆數(shù)組的存儲(chǔ)空間中存在著兩 個(gè)棧,它們的棧底分別設(shè)在數(shù)組的兩個(gè)端點(diǎn)。 試編寫實(shí)現(xiàn)這個(gè)雙向棧 tws 的三個(gè) 操作：初始化 inistack (tws)、入棧 push (tws, i, x)和出棧 pop (tws, i)的算 法，其中i為0或1,用以分別指示設(shè)在數(shù)組兩端的兩個(gè)棧，并討論

34、按過程(正 / 誤狀態(tài)變量可設(shè)為變參)或函數(shù)設(shè)計(jì)這些操作算法各有什么優(yōu)缺點(diǎn)。typedef struct SEIemType *base2;SEIemType *top2;int stacksize; SqStack;Status initstack ( SqStack &tws) / 初始化,構(gòu)造一個(gè)空棧 twstws. base0 = ( SElemType *) malloc (STACK_INIT_SIZE * sizeo();if(！ tws.base0 ) exit ( OVERFLOW)； / 存儲(chǔ)分配失敗tws. stacksize = STACK_INIT_SIZEt

35、ws. base1 = tws. base0 + tws.stacksize 1;tws. top0 = tws. baseO;tws. top1 = tws. base1;return OK； / initstackStatus push(SqStack &tws，int i ， ElemType x) / 插入元素 x 為新的棧頂元素 if(tws.top0 base0 + tws.top1 base1 >= tws.stacksize) / 棧滿，追加存儲(chǔ)空間in creme ntO = tws.top0 base0; / 0端的元素個(gè)數(shù)in creme nt1 = tws

36、.top1 base1; / 1端的元素個(gè)數(shù)tws . base0 = ( SEIemType *) realloc (tws.base0 ,(tws.base0+STACKINCREMENT) * sizeo(f ElemType)；if (！tws.base0) exit(OVERFLOW)； / 存儲(chǔ)分配失敗tws.stzcksize += STACKINCREMENT; temp=tws.base1;tws. base1 = tws . base0 + tws.stacksize 1;for(i=0; i<increment1; i+)*(tws.base1 - i) = *(t

37、emp - i);/把1端棧中元素移到新的雙向棧的1端tws . top0 = tws. base0 + in creme ntO;tws . top1 = tws . base1 -in creme nt1;if(i)* tws.top1 - = x ；else* tws.topO + = x ；return OK; / pushStatus pop ( SqStack &tws， int i )/若棧不空，則刪除tws的棧頂元素，并返回 OK;否則返回ERRORif(tws.top0 = base0 | tws.top1 = base1) return ERROR; if(i)+

38、tws.top1 ;else tws.topO ;return OK;/ pop7， 3，4】(選自數(shù)據(jù)結(jié)構(gòu)題集 3.13，必做題) 簡述以下算法的功能(棧和隊(duì)列的元素類型均為 int ) void algo3(Queue &Q)Stack S; int d;InitStack (S);while (!QueueEmpty (Q) DeQueue (Q, d); Push (S,d);while (!StackEmpty (S) Pop (S, d); EnQueue(Q, d);答：將隊(duì)列Q中的元素變成倒置排列 【 8， 3，2】（選自數(shù)據(jù)結(jié)構(gòu)題集 3.19，選做題） 假設(shè)一個(gè)算術(shù)表

39、達(dá)式中可以包含三種括號(hào)：圓括號(hào)“ （”和“）”，方括號(hào)“ 和“ ”和花括號(hào)“ ”和“ ”，且這三種括號(hào)可以按任意的次序嵌套使用（如:（）。編寫判別給定表達(dá)式所含括號(hào)是 否正確配對(duì)出現(xiàn)的算法（已知表達(dá)式已存入數(shù)據(jù)元素為字符的順序表中） 。 解：算法如下：Status MatchBrackets ( ) SqStack &S;InitStack (S); while (c=getchar()!= if(!StackEmpty (S) && (c='n')')'&& GetTop (S)= '('| c='

40、; ' && GetTop (S)= ' ' | c='' && GetTop (S)= ' ' ) )Pop (S); / else判斷括號(hào)是否匹配if(IsLeftBracket(c) Push (S, c)； / 判斷是否是括號(hào)if(!StackEmpty(S) return ERROR; else return TRUE;9， 4，1】(選自數(shù)據(jù)結(jié)構(gòu)題集 4.3，必做題)設(shè) s = 'I AM A STUDENT ,t = GOO',q = WORKER 求： StrLength(s

41、), StrLength(t), SubString(s,8,7), SubString(t,2,1), Index(s, ' A' ), Index(s, t), Replace(s,' STUDEN'T,q ),Concat(SubString(s,6,2),Concat(t,SubString(s,7,8) 答： StrLength(s) = 14, StrLength(t) = 4,SubString(s,8,7) =' STUDEN'T, SubString(t,2,1) =' O'Index(s,' A'

42、; ) = 3, Index(s, t) = 0,Replace(s, 'STUDEN'T,q ) ='I AM A WORKER',Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)=' A GOOD STUDE'NT10， 5，1】（選自數(shù)據(jù)結(jié)構(gòu)題集 5.1，必做題）假設(shè)有兩維數(shù)組A6X8，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)按字節(jié)編址。 已知A的起始地址為1000,計(jì)算：（1）數(shù)組A的存儲(chǔ)量；=6x8x6 = 288字節(jié)）（2）數(shù)組A的最后一個(gè)元素a57的第一個(gè)字節(jié)的地址；=1000+288-6

43、=1282（3）按行存儲(chǔ)時(shí)，元素ai4的第一個(gè)字節(jié)的地址；=1000+（8x1+4）x6=1072 按列存儲(chǔ)時(shí)，元素 347的第一個(gè)字節(jié)的地址；=1000+（7x6+4）x6=1276【11,6, 11 （選自數(shù)據(jù)結(jié)構(gòu)題集6.1,必做題）已知一棵樹邊的集合為<1, M>，<1, N>, <E, l>, <B, E>, <B, D>, <A, B>, <G, J>, <G, K>, <C, G>, <C, F>, <H, L>, <C, H>, <

44、A, C>,請(qǐng)畫出這棵樹， 并回答下列問題：（1）哪個(gè)是根結(jié)點(diǎn)？（2）哪些是葉子結(jié)點(diǎn)？（3）哪個(gè)是結(jié)點(diǎn)G的雙親？（4）哪些是結(jié)點(diǎn)G的祖先？（5）哪些是結(jié)點(diǎn)G的孩子？（6）哪些是結(jié)點(diǎn)E的子孫？（7）哪些是結(jié)點(diǎn)E的兄弟？哪些是結(jié)點(diǎn)F的兄弟？（8）結(jié)點(diǎn)B和N的層次號(hào)分別是什么？（9）樹的深度是多少？（10）以結(jié)點(diǎn)C為根的子樹的深度是多少？解：這棵樹為：（M）®所以，根結(jié)點(diǎn)為A；葉子結(jié)點(diǎn)是D, M, N, F, J, K, L；結(jié)點(diǎn)G雙親為C；結(jié)點(diǎn)G的祖先為A, C；結(jié)點(diǎn)E的子孫為I, M., N；結(jié)點(diǎn)E的兄弟有D,結(jié)點(diǎn)F的兄弟有G, H；結(jié)點(diǎn)B和N的層次號(hào)分別是2, 5；樹的深度是5

45、；以結(jié)點(diǎn)C為根的子樹的深度為3?！?2, 6 , 1】（選自數(shù)據(jù)結(jié)構(gòu)題集6.4,選做題）一棵深度為H的滿k叉樹有如下性質(zhì)第H層上的結(jié)點(diǎn)都是葉子節(jié)點(diǎn)，其余各 層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹。如果按層次順序從1開始對(duì)全部結(jié)點(diǎn)編號(hào)，問:（1）各層的結(jié)點(diǎn)數(shù)目是多少？（2）編號(hào)為p的父結(jié)點(diǎn)（若存在）的編號(hào)是多少？（3）編號(hào)為p的結(jié)點(diǎn)的第i個(gè)兒子結(jié)點(diǎn)（若存在）的編號(hào)是多少？（4）編號(hào)為p的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟的編號(hào)是多少？解：（1）各層的結(jié)點(diǎn)數(shù)為（n= 1, 2,，H）;（2） 首先，p二1時(shí)，沒有父結(jié)點(diǎn)，匸-丄時(shí)，通過歸納可得，編號(hào)為a的結(jié) 點(diǎn)，它的所有子結(jié)點(diǎn)的編號(hào)為從 上、L I二到，則編

46、號(hào)為P的結(jié)點(diǎn)的父 結(jié)點(diǎn)為丄1（3） 由上可得，第i個(gè)兒子結(jié)點(diǎn)的編號(hào)為I +一 +】I（4）p有右兄弟，即p不為最右的結(jié)點(diǎn)，條件為* I % r門，右兄弟的 編號(hào)為p+ 1?！?3， 6, 2】（選自數(shù)據(jù)結(jié)構(gòu)題集6.5,選做題）已知一棵度為k的樹中有個(gè)度為1的結(jié)點(diǎn)，：個(gè)度為2的結(jié)點(diǎn)，：二個(gè) 度為k的結(jié)點(diǎn)，問該樹中有多少個(gè)葉子結(jié)點(diǎn)？解：設(shè)結(jié)點(diǎn)總數(shù)為n，則有n= no+m+n2+-+nk，因?yàn)槌烁Y(jié)點(diǎn)外，所有結(jié)點(diǎn)都有邊進(jìn)入，所以有n=B+1,而B = 1*n 1+2*n2+k*nk =刀i*ni 所以有no+n 1+n2+-+ n = 刀 i*ni + 1no = X（ i-1） *n i + 1

47、【14， 6, 3】（選自數(shù)據(jù)結(jié)構(gòu)題集6.13，必做題）假設(shè)n和m為二叉樹中的兩結(jié)點(diǎn)，用“ 1 ”、“0”、“”（分別表示肯定、恰 恰相反或者不一定）填寫下表：已知問答：前序遍歷時(shí) n在m前？中序遍歷時(shí) n在m前？后序遍歷時(shí) n在m前？n在m左方111n在m右方000n是m祖先10n是m子孫01注：如果（1）離a和b最近的共同祖先p存在，且（2） a在p的左子樹中，b 在p的右子樹中，則稱a在b的左方（即b在a的右方）【15, 6, 3】（選自數(shù)據(jù)結(jié)構(gòu)題集6.14，選做題） 找出所有滿足下列條件的二叉樹：（a）它們在先序遍歷和中序遍歷時(shí)，得到的結(jié)點(diǎn)訪問序列相同；（b）它們在后序遍歷和中序遍歷時(shí)

48、，得到的結(jié)點(diǎn)訪問序列相同；（c）它們在先序遍歷和后序遍歷時(shí)，得到的結(jié)點(diǎn)訪問序列相同；答：（a）除葉子結(jié)點(diǎn)外所有結(jié)點(diǎn)都只有右孩子的樹或只有根結(jié)點(diǎn)的樹;（b）只有根結(jié)點(diǎn)以及除葉子結(jié)點(diǎn)外所有結(jié)點(diǎn)都只有左孩子的樹；（c）只有根結(jié)點(diǎn)的樹?！?6, 6, 4】（選自數(shù)據(jù)結(jié)構(gòu)題集6.19,必做題） 分別畫出和下列樹對(duì)應(yīng)的各二叉樹：(a)(b)(c)(d)答：用孩子兄弟表示法將樹表示成二叉樹，二叉樹的左右結(jié)點(diǎn)分別為第一個(gè)孩 子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)，表示如下：【17，6, 3】（選自數(shù)據(jù)結(jié)構(gòu)題集6.23，選做題）畫出和下列已知序列對(duì)應(yīng)的樹T樹的先根次序訪問序列為GFKDAIEBCHJ樹的后根次序訪問序列為DIA

49、EKFCJHBG解：對(duì)應(yīng)的樹如下：B【18, 6, 5】（選自數(shù)據(jù)結(jié)構(gòu)題集6.26，必做題）假設(shè)用于通信的電文僅有 8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為 0.07, 0.19，0.02，0.06，0.32，0.03, 0.21，0.10試為這 8 個(gè)字母設(shè)計(jì)哈夫曼編 碼。使用0-7的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種 方案的優(yōu)缺點(diǎn)。解：哈夫曼編碼樹如下：0? 1所以編碼如下:字母0.070.190.020.060.320.030.210.10編碼1010001000010011110001011011帶權(quán)路徑長度 WPL= 0.19X 2+ 0.21 X 2+ 0.0

50、2X 5 + 0.03X 5+ 0.06X 4 + 0.07X 4 + 0.10X 4+ 0.32 X 2 = 2.61，而采用等長編碼時(shí)，每個(gè)字母至少 3位，故帶權(quán)路 徑長度WPL= 3.采用哈夫曼編碼可以大大提高通信信道的利用率?！?9， 6, 2】（選自數(shù)據(jù)結(jié)構(gòu)題集6.29,必做題）假設(shè)一棵二叉樹的層序序列為 ABCDEFGH和中序序列為DBGEHJACIF請(qǐng)畫 出該樹。解：該二叉樹如下：BEFH：GJJ【20, 7 , 2】(選自數(shù)據(jù)結(jié)構(gòu)題集7.1,必做題) 已知如右圖所示的有向圖，請(qǐng)給出該圖的(1) 每個(gè)頂點(diǎn)的入/出度；(2) 鄰接矩陣；(3) 鄰接表；(4) 逆鄰接表；(5) 強(qiáng)連

51、通分量。123456100000021001003 d01r 000140010115 110:00006110010答：(1)各頂點(diǎn)的入/出度如下：頂點(diǎn)1： 30;頂點(diǎn)2: 22 ；頂點(diǎn)3： 1/2;頂點(diǎn)4: 1/2； 頂點(diǎn)5： 21 ;頂點(diǎn)6: 23。(2)鄰接矩陣如下：(3)鄰接表如下:12一 1rJiNT 2丨入14nT 5 丨 T0s-62 (4)逆鄰接表如下:2（I2CD©GBCL©li6i答：其廣義優(yōu)先生成森林如下:【21, 7, 3】（選自數(shù)據(jù)結(jié)構(gòu)題集7.4,選做題） 試對(duì)教科書7.1節(jié)中圖7.3（a）所示的無向圖（如下圖），畫出其廣度優(yōu)先生成森林。（5）有以下3個(gè)強(qiáng)連通分量234；/X2064XX【22, 7, 4】(選自數(shù)