計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 習(xí)題一解答.doc
《計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 習(xí)題一解答.doc》由會(huì)員分享,可在線閱讀,更多相關(guān)《計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 習(xí)題一解答.doc(17頁珍藏版)》請?jiān)谘b配圖網(wǎng)上搜索。
線性結(jié)構(gòu)習(xí)題解答習(xí)題解答3.設(shè)n為正整數(shù), 分析下列各程序段中加下劃線的語句的執(zhí)行次數(shù)。(1)for (int i = 1; i = n; i+) for (int j = 1; j = n; j+) cij = 0.0; for (int k = 1; k = n; k+) cij = cij + aik * bkj; (2)x = 0; y = 0; for (int i = 1; i = n; i+) for (int j = 1; j = i; j+) for (int k = 1; k = j; k+) x = x + y;(3)int i = 1, j = 1; while (i=n & j=n) i = i + 1; j = j + i; (4)*int i =1; do for (int j = 1; j = n; j+) i = i + j; while(iarraySize或者對于某一個(gè)k (0 k n),使得k!*2k maxInt時(shí),應(yīng)按出錯(cuò)處理??捎腥缦氯N不同的出錯(cuò)處理方式:(1) 用printf顯示錯(cuò)誤信息及exit(1)語句來終止執(zhí)行并報(bào)告錯(cuò)誤;(2) 用返回整數(shù)函數(shù)值0, 1來實(shí)現(xiàn)算法,以區(qū)別是正常返回還是錯(cuò)誤返回;(3) 在函數(shù)的參數(shù)表設(shè)置一個(gè)引用型的整型變量來區(qū)別是正常返回還是某種錯(cuò)誤返回。試討論這三種方法各自的優(yōu)缺點(diǎn),并以你認(rèn)為是最好的方式實(shí)現(xiàn)它?!窘獯稹?include const int arraySize = 100;const int MaxInt = 0x7fffffff;int calc( int T , int n ) int i, value = 1;T0=1;if ( n != 0 ) int edge = MaxInt / n / 2;for ( i = 1; i edge ) return 0;value *= n * 2;Tn = value;printf(A %d = %dn”,n,Tn);return 1;void main ( ) int AarraySize;int i;for ( i = 0; i length;for( int i = 0; i datai; A-datai = A-datan-i-1; A-datan-i-1 = tmp;時(shí)間復(fù)雜度:需進(jìn)行n/2次循環(huán),因此時(shí)間復(fù)雜度為O(n);空間復(fù)雜度:使用一個(gè)整形輔助存儲(chǔ)單元tmp,因此空間復(fù)雜度為O(1)。6.順序表的插入和刪除要求仍然保持各個(gè)元素原來的次序。設(shè)在等概率情形下, 對有127個(gè)元素的順序表進(jìn)行插入, 平均需要移動(dòng)多少個(gè)元素? 刪除一個(gè)元素, 又平均需要移動(dòng)多少個(gè)元素?【解答】若設(shè)順序表中已有n個(gè)元素。又設(shè)插入或刪除表中各個(gè)元素的概率相等,則在插入時(shí)因有n+1個(gè)插入位置(可以在表中最后一個(gè)表項(xiàng)后面追加),每個(gè)元素位置插入的概率為1/(n+1),但在刪除時(shí)只能在已有n個(gè)表項(xiàng)范圍內(nèi)刪除,所以每個(gè)元素位置刪除的概率為1/n。插入時(shí)平均移動(dòng)元素個(gè)數(shù)AMN(Averagy Moving Number )為刪除時(shí)平均移動(dòng)元素個(gè)數(shù)AMN為 7.利用順序表的操作,實(shí)現(xiàn)以下的函數(shù)。并分析你所編制的函數(shù)的時(shí)間復(fù)雜度,并分析(2)與(3)的時(shí)間復(fù)雜度出現(xiàn)差異的原因。(1) 從順序表中刪除具有給定值x的所有元素。(2) 從順序表中刪除其值在給定值s與t之間(要求s小于t)的所有元素。(3) 從有序順序表中刪除其值在給定值s與t之間(要求s小于t)的所有元素。(4) 將兩個(gè)有序順序表la,lb合并成一個(gè)新的有序順序表lc。(5) 從順序表中刪除所有其值重復(fù)的元素,使表中所有元素的值均不相同?!窘獯稹?1) 從順序表中刪除具有給定值x的所有元素。void DelValue(listtype * L, int x )int i = 0, j;while ( i length )/*循環(huán), 尋找具有值x的元素并刪除它*/if (L-datai = x ) /*刪除具有值x的元素, 后續(xù)元素前移*/for (j = i;j length-1; j+ ) L-dataj = L-dataj+1;L-length-; /*表長減1*/else i+;(2) 實(shí)現(xiàn)刪除其值在給定值s與t之間(要求s小于t)的所有元素的函數(shù)如下:void DelValue_s_to_t (listtype *L,int s, int t)int i,j;if ( L-length = 0 | s = t ) printf(“List is empty or parameters are illegal!n”); exit(1); i = 0;while ( i length)/*循環(huán), 尋找具有值x的元素并刪除它*/if (L-datai=s &L-datai= t)/*刪除滿足條件的元素, 后續(xù)元素前移*/for ( j = i; j length-1; j+ ) L-dataj = L-dataj+1;L-length-; /*表長減1*/else i+;(3) 實(shí)現(xiàn)從有序順序表中刪除其值在給定值s與t之間的所有元素的函數(shù)如下:void DelValue_s_to_t_1 (listtype *L,int s int t)int i,j,k;if ( L-length = 0 | s = t ) printf(“List is empty or parameters are illegal!n”); exit(1); for (i = 0; i length; i+ ) /*循環(huán), 尋找值 s 的第一個(gè)元素*/if ( L-datai = s ) break; /*退出循環(huán)時(shí), i指向該元素*/if ( i length ) for (j = 1; i + j length; j+ )/*循環(huán), 尋找值 t 的第一個(gè)元素*/if (L-datai+j t ) break;/*退出循環(huán)時(shí), i+j指向該元素*/ for (k = i+j; k length; k+ ) /*刪除滿足條件的元素, 后續(xù)元素前移*/L-datak-j = L-datak; L-length-= j; /*表長減j*/(4) 實(shí)現(xiàn)將兩個(gè)有序順序表合并成一個(gè)新的有序順序表的函數(shù)如下:listtype * Merge(listtype *LA,listtype *LB )/*合并有序順序表LA與LB成為一個(gè)新的有序順序表并由函數(shù)返回listtype *LC;int value1,value2;int i,j,k;initiatelist(LC);if (LA-length + LB-length MAXSIZE) printf(“表上溢/n”; exit(1); i = 0, j = 0, k = 0;value1 = LA-datai;value2 = LB-dataj;while (i length & j length ) /*循環(huán), 兩兩比較, 小者存入結(jié)果表*/if (value1 datak = value1; i+; value1=LA-datai; else LC-datak = value2; j+; value2=LB-dataj;k+; while( i length)/*當(dāng)LA表未檢測完, 繼續(xù)向結(jié)果表傳送*/LC-datak = value1; i+; k+; value1 = LA-datai; while( j length)/*當(dāng)LB表未檢測完, 繼續(xù)向結(jié)果表傳送*/LC-datak = value2; j+; k+; value2 = LB-dataj;LC-length = k;return LC;(5) 實(shí)現(xiàn)從表中刪除所有其值重復(fù)的元素的函數(shù)如下:void DelDouble(listtype *L)int i,j,k;int tmp;if(L-length = 0 ) printf(“表空n”; exit(1); i=0;while ( i length ) /*循環(huán)檢測*/j = i + 1; tmp = L-datai;while( j length ) /*對于每一個(gè)i, 重復(fù)檢測一遍后續(xù)元素*/if( tmp = L-dataj) /*如果相等,刪除此結(jié)點(diǎn),后續(xù)元素前移*/ for( k = j+1; k length; k+ ) L-datak-1 = L-datak;L-length-; /*表最后元素位置減1*/else j+; i+;/*檢測完L-datai, 檢測下一個(gè)*/8.線性表可用順序表或鏈表存儲(chǔ)。試問:(1) 兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)?(2) 如果有n個(gè)表同時(shí)并存,并且在處理過程中各表的長度會(huì)動(dòng)態(tài)發(fā)生變化,表的總數(shù)也可能自動(dòng)改變、在此情況下,應(yīng)選用哪種存儲(chǔ)表示?為什么?(3) 若表的總數(shù)基本穩(wěn)定,且很少進(jìn)行插入和刪除,但要求以最快的速度存取表中的元素,這時(shí),應(yīng)采用哪種存儲(chǔ)表示?為什么?【解答】(1) 順序存儲(chǔ)表示是將數(shù)據(jù)元素存放于一個(gè)連續(xù)的存儲(chǔ)空間中,實(shí)現(xiàn)順序存取或(按下標(biāo))直接存取。它的存儲(chǔ)效率高,存取速度快。但它的空間大小一經(jīng)定義,在程序整個(gè)運(yùn)行期間不會(huì)發(fā)生改變,因此,不易擴(kuò)充。同時(shí),由于在插入或刪除時(shí),為保持原有次序,平均需要移動(dòng)一半(或近一半)元素,修改效率不高。鏈接存儲(chǔ)表示的存儲(chǔ)空間一般在程序的運(yùn)行過程中動(dòng)態(tài)分配和釋放,且只要存儲(chǔ)器中還有空間,就不會(huì)產(chǎn)生存儲(chǔ)溢出的問題。同時(shí)在插入和刪除時(shí)不需要保持?jǐn)?shù)據(jù)元素原來的物理順序,只需要保持原來的邏輯順序,因此不必移動(dòng)數(shù)據(jù),只需修改它們的鏈接指針,修改效率較高。但存取表中的數(shù)據(jù)元素時(shí),只能循鏈順序訪問,因此存取效率不高。(2) 如果有n個(gè)表同時(shí)并存,并且在處理過程中各表的長度會(huì)動(dòng)態(tài)發(fā)生變化,表的總數(shù)也可能自動(dòng)改變、在此情況下,應(yīng)選用鏈接存儲(chǔ)表示。如果采用順序存儲(chǔ)表示,必須在一個(gè)連續(xù)的可用空間中為這n個(gè)表分配空間。初始時(shí)因不知道哪個(gè)表增長得快,必須平均分配空間。在程序運(yùn)行過程中,有的表占用的空間增長得快,有的表占用的空間增長得慢;有的表很快就用完了分配給它的空間,有的表才用了少量的空間,在進(jìn)行元素的插入時(shí)就必須成片地移動(dòng)其他的表的空間,以空出位置進(jìn)行插入;在元素刪除時(shí),為填補(bǔ)空白,也可能移動(dòng)許多元素。這個(gè)處理過程極其繁瑣和低效。如果采用鏈接存儲(chǔ)表示,一個(gè)表的存儲(chǔ)空間可以連續(xù),可以不連續(xù)。表的增長通過動(dòng)態(tài)存儲(chǔ)分配解決,只要存儲(chǔ)器未滿,就不會(huì)有表溢出的問題;表的收縮可以通過動(dòng)態(tài)存儲(chǔ)釋放實(shí)現(xiàn),釋放的空間還可以在以后動(dòng)態(tài)分配給其他的存儲(chǔ)申請要求,非常靈活方便。對于n個(gè)表(包括表的總數(shù)可能變化)共存的情形,處理十分簡便和快捷。所以選用鏈接存儲(chǔ)表示較好。(3) 應(yīng)采用順序存儲(chǔ)表示。因?yàn)轫樞虼鎯?chǔ)表示的存取速度快,但修改效率低。若表的總數(shù)基本穩(wěn)定,且很少進(jìn)行插入和刪除,但要求以最快的速度存取表中的元素,這時(shí)采用順序存儲(chǔ)表示較好。/*-鏈表結(jié)構(gòu)的定義.為簡化起見,表元素我們使用整型數(shù)據(jù)-此鏈表帶頭結(jié)點(diǎn)-*/typedef struct mynodeint data; /*數(shù)據(jù)域:整型*/struct mynode *next; /*指針域*/ node, linklisttype;9.試寫出計(jì)算線性鏈表長度的算法。int lengthsl(linklisttype *L)linklisttype * p;int len;if(L = NULL)return 1;p = L-next;/* p指向鏈表L的頭結(jié)點(diǎn)*/len = 0;while(p != NULL)len+;p = p-next;return len;10.設(shè)有一個(gè)表頭指針為h的單鏈表。試設(shè)計(jì)一個(gè)算法,通過遍歷一趟鏈表,將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn),如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針h指向原鏈表的最后一個(gè)結(jié)點(diǎn)?!窘獯稹縱oid LinkListInverse(linklisttype *L)linklisttype *p, *pre, *next;if(L = NULL | L-next = NULL ) return; /*表未初始化,或?yàn)榭毡?/ p = L-next;pre = L;while( p != NULL ) /*循環(huán)修改鏈表中所有結(jié)點(diǎn)的后繼指針的指向*/next = p-next;/*取當(dāng)前結(jié)點(diǎn)的后繼指針*/p-next = pre;/*當(dāng)前結(jié)點(diǎn)的后繼改為指向其原來的前驅(qū)*/pre = p , p=next;/*指針后移*/L-next-next = NULL;/*原第一個(gè)結(jié)點(diǎn)改為最后一個(gè)結(jié)點(diǎn)*/L-next = pre;/*鏈表的頭結(jié)點(diǎn)指向原最后一個(gè)結(jié)點(diǎn)*/11.設(shè)有一線性鏈表,其結(jié)點(diǎn)值均為整數(shù)。試將該線性鏈表分解為兩個(gè)線性鏈表,其中一鏈表中的結(jié)點(diǎn)值均為負(fù)整數(shù),而另一鏈表中結(jié)點(diǎn)的值均為正整數(shù),并刪除結(jié)點(diǎn)值為零的結(jié)點(diǎn)。【解答】void LinkListDispose(linklisttype * L,linklisttype * LA,linklisttype * LB)/*將鏈表L分解為LA、LB兩個(gè)鏈表,其中LA中結(jié)點(diǎn)值均為正,LB中結(jié)點(diǎn)值均為負(fù),并刪除結(jié)點(diǎn)值為零的結(jié)點(diǎn),最后釋放L的頭結(jié)點(diǎn)。*/linklisttype *p , *pt , *pa, * pb;LA = initiatesl();pa = LA;/*指向LA中的最后一個(gè)結(jié)點(diǎn)*/LB = initiatesl();pb = LB;/*指向LB中的最后一個(gè)結(jié)點(diǎn)*/If(L = NULL | L-next = NUUL) return;/*L為空指針或L為空表*/p = L-next;/*p指向鏈表L的第一個(gè)結(jié)點(diǎn)*/while(p != NULL)/*遍歷鏈表L*/if(p-data 0)/*將p鏈入鏈表LA的pa后*/pa-next = p;pa = p;p = p-next;elseif(p-data next = p;pb = p;p = p-next;else/*刪除值為0的結(jié)點(diǎn)*/pt = p-next;/*記錄當(dāng)前結(jié)點(diǎn)的后繼,以便刪除當(dāng)前結(jié)點(diǎn)*/free(p);p = pt;pa-next = NULL;pb-next = NULL;free(L);12設(shè)ha和hb分別是兩個(gè)帶表頭結(jié)點(diǎn)的非遞減有序單鏈表的表頭指針, 試設(shè)計(jì)一個(gè)算法, 將這兩個(gè)有序鏈表合并成一個(gè)非遞減有序的單鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲(chǔ)空間, 不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)?!窘獯稹縱oid linklistMerge(linklisttype *LA,linklisttype *LB )/*合并有序鏈表LA與LB,結(jié)果存入LA中,并釋放LB的頭結(jié)點(diǎn) */linklisttype *pa, *pb , *pre ,*pn;if(LA = NULL | LB = NULL |) return;if(LA-next = NULL)/*LA為空表,則直接將LB鏈入LA即可*/LA-next = LB-next;free(LB);retrun;if(LB-next = NULL) return;/*LB為空表,則直接返回即可*/pa = LA-next, pb = LB-next ,pre=LA;while (pa != NULL & pb != NULL)/*循環(huán), 兩兩比較, 小者存入結(jié)果表*/if(pa-data pb-next)/*將pb鏈入LA,然后pb指針后移*/pre-next = pb;pn = pb-next;pb-next = pa;pb = pn;pre = pre-next else/*pa指針后移*/pa = pa-next;pre = pre-next;if(pb != NULL)/*將pb剩余結(jié)點(diǎn)鏈入LA*/pre-next = pb;free(LB);13設(shè)ha和hb分別是兩個(gè)帶表頭結(jié)點(diǎn)的非遞減有序單鏈表的表頭指針, 試設(shè)計(jì)一個(gè)算法, 將這兩個(gè)有序鏈表合并成一個(gè)非遞增有序的單鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲(chǔ)空間, 不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)?!窘獯稹縇inklisttype * linklistMerge_inverse(linklisttype *LA,linklisttype *LB )/*合并有序鏈表LA與LB,結(jié)果存入LC中,并釋放LA、LB的頭結(jié)點(diǎn) ,函數(shù)返回LC*/linklisttype *pa, *pb , *p;if(LA = NULL | LB = NULL |) return;LC = initiatesl();pa = LA-next, pb = LB-next;while (pa != NULL & pb != NULL)/*循環(huán), 兩兩比較, 大者存入LC*/if(pa-data pb-next)/*將pa鏈為LC的第一個(gè)結(jié)點(diǎn)*/p = pa-next;pa-next = LC-next;LC-next = pa;pa = p; else/*將pa鏈為LC的第一個(gè)結(jié)點(diǎn)*/p = pb-next;pb-next = LC-next;LC-next = pb;pb = p;while(pa != NULL)/*將pa剩余結(jié)點(diǎn)鏈入LC*/p = pa-next;pa-next = LC-next;LC-next = pa;pa = p;while(pb != NULL)/*將pb剩余結(jié)點(diǎn)鏈入LC*/p = pb-next;pb-next = LC-next;LC-next = pb;pb = p;free(LA);free(LB);14.在一個(gè)循環(huán)鏈表中尋找值為x的結(jié)點(diǎn),并將該結(jié)點(diǎn)移到第一個(gè)結(jié)點(diǎn)之前?!窘獯稹吭O(shè)此循環(huán)鏈表為單鏈表,則其類型定義與一般單鏈表相同typedef struct mynode cyclelisttype;void search_movefirst(cyclelisttype *CL, int x)cyclelisttype * p , *pre;if(CL = NULL) return;p = CL-next;pre = CL;while(p != CL)/*查找x,注意與普通單鏈表在判斷是否到表尾上的不同*/if(p-data = x)break;elsepre = p;p = p-next;if(p != CL)/*查找成功*/per-next = p-next;/*在原來位置刪除p*/p-next = CL-next;/*p插入到CL后*/CL-next = p;16.鐵路進(jìn)行列車調(diào)度時(shí), 常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)的站臺(tái),如右圖所示。試問:(1) 設(shè)有編號(hào)為1,2,3,4,5,6的六輛列車, 順序開入棧式結(jié)構(gòu)的站臺(tái), 則可能的出棧序列有多少種?(2) 若進(jìn)站的六輛列車順序如上所述, 那么是否能夠得到435612, 325641, 154623和135426的出站序列, 如果不能, 說明為什么不能; 如果能, 說明如何得到(即寫出進(jìn)?;虺鰲5男蛄??!窘獯稹?1) 可能的不同出棧序列有 種。(2) 不能得到435612和154623這樣的出棧序列。因?yàn)槿粼?, 3, 5, 6之后再將1, 2出棧,則1, 2必須一直在棧中,此時(shí)1先進(jìn)棧,2后進(jìn)棧,2應(yīng)壓在1上面,不可能1先于2出棧。154623也是這種情況。出棧序列325641和135426可以得到。3562244 4411111111 3 32 32 325 325 3256 32564 3256415344122226 1 1 13 135 1354 13542 13542 13542617.試證明:若借助??捎奢斎胄蛄?, 2, 3, , n得到一個(gè)輸出序列p1, p2, p3, , pn (它是輸入序列的某一種排列),則在輸出序列中不可能出現(xiàn)以下情況,即存在i j k,使得pj pk pi。(提示:用反證法)【解答】因?yàn)榻柚鷹S奢斎胄蛄?, 2, 3, , n,可得到輸出序列p1, p2, p3, , pn ,如果存在下標(biāo)i, j, k,滿足i j k,那么在輸出序列中,可能出現(xiàn)如下5種情況: i進(jìn)棧,i出棧,j進(jìn)棧,j出棧,k進(jìn)棧,k出棧。此時(shí)具有最小值的排在最前面pi位置,具有中間值的排在其后pj位置,具有最大值的排在pk位置,有pi pj pk, 不可能出現(xiàn)pj pk pi的情形; i進(jìn)棧,i出棧,j進(jìn)棧,k進(jìn)棧,k出棧,j出棧。此時(shí)具有最小值的排在最前面pi位置,具有最大值的排在pj位置,具有中間值的排在最后pk位置,有pi pk pj , 不可能出現(xiàn)pj pk pi的情形; i進(jìn)棧,j進(jìn)棧,j出棧,i出棧,k進(jìn)棧,k出棧。此時(shí)具有中間值的排在最前面pi位置,具有最小值的排在其后pj位置,有pj pi pk, 不可能出現(xiàn)pj pk pi的情形; i進(jìn)棧,j進(jìn)棧,j出棧,k進(jìn)棧,k出棧,i出棧。此時(shí)具有中間值的排在最前面pi 位置,具有最大值的排在其后pj位置,具有最小值的排在pk位置,有pk pi pj, 也不可能出現(xiàn)pj pk pi的情形; i進(jìn)棧,j進(jìn)棧,k進(jìn)棧,k出棧,j出棧,i出棧。此時(shí)具有最大值的排在最前面pi 位置,具有中間值的排在其后pj位置,具有最小值的排在pk位置,有pk pj pi, 也不可能出現(xiàn)pj pk top0 top1 = MAXSIZE);判棧滿int DoubleStackFull(DoubleStack * DS)return(DS-top1-DS-top0=1);入棧int PopDoubleStack(DoubleStack * DS,int StackNo,elemtype x)/*將數(shù)據(jù)元素x插入到棧StackNo中*/if(DoubleStackFull(DS) return(FALSE);/*棧滿溢出*/if(StackNo=0)/*對第0棧插入*/DS-top0+;DS-datatop0=x;else/*對第1棧插入*/DS-top1-;DS-datatop1=x;return(TRUE);刪除算法elemtype PushDoubleStack(DoubleStack * DS,int StackNo)/*從StackNo棧中刪除并返回一個(gè)元素,若??眨瑒t返回NULL*/if(DoubleStackEmpty(DS,StackNo) return(NULL);if(StackNo=0)/*對0號(hào)棧進(jìn)行操作*/DS-top0-;return(DS-dataDS-top0+1);elseDS-top1+;return(DS-dataDS-top1-1);19.改寫順序棧的進(jìn)棧成員函數(shù)Push(x),要求當(dāng)棧滿時(shí)執(zhí)行一個(gè)stackFull( )操作進(jìn)行棧滿處理。其功能是:動(dòng)態(tài)創(chuàng)建一個(gè)比原來的棧數(shù)組大二倍的新數(shù)組,代替原來的棧數(shù)組,原來?xiàng)?shù)組中的元素占據(jù)新數(shù)組的前MaxSize位置?!窘獯稹縱oid push(stack * S,elemtype x) if(StackEmpty(S) stackFull(S);/棧滿,做溢出處理S-top +;S-dataS-top = x;/進(jìn)棧void stackFull(stack *S)elemtype *temp;temp=calloc(3*MAXSIZE,sizeof(elemtype); /創(chuàng)建體積大二倍的數(shù)組for ( int i = 0; i top; i+ ) /傳送原數(shù)組的數(shù)據(jù)tempi = S-datai;free(S-data);/刪去原數(shù)組MAXSIZE *= 3; /數(shù)組最大體積增長二倍S-data = temp;/新數(shù)組成為棧的數(shù)組空間20.根據(jù)教案中給出的優(yōu)先級(jí),回答以下問題:(1) 在表達(dá)式求值的過程中,如果表達(dá)式e含有n個(gè)運(yùn)算符和分界符,問操作數(shù)棧(NS)中最多可存入多少個(gè)元素?(2) 如果表達(dá)式e含有n個(gè)運(yùn)算符,且括號(hào)嵌套的最大深度為6層,問棧中最多可存入多少個(gè)元素?【解答】(1) 如果表達(dá)式e含有n個(gè)運(yùn)算符和分界符,則可能的運(yùn)算對象有n+1個(gè)。因此在利用后綴表達(dá)式求值時(shí)所用到的運(yùn)算對象棧中最多可存入n+1個(gè)元素。(2) 同上。21.表達(dá)式的中綴表示為a * x - b / x2,試?yán)脳⑺臑楹缶Y表示ax * bx2/ -。寫出轉(zhuǎn)換過程中棧的變化。(表示乘方運(yùn)算)【解答】若設(shè)當(dāng)前掃描到的運(yùn)算符ch的優(yōu)先級(jí)為icp(ch),該運(yùn)算符進(jìn)棧后的優(yōu)先級(jí)為isp(ch),則可規(guī)定各個(gè)算術(shù)運(yùn)算符的優(yōu)先級(jí)如下表所示。 運(yùn)算符 ; ( *,/, % +, - ) isp 0 1 7 5 3 8 icp 0 8 6 4 2 1isp也叫做棧內(nèi)(in stack priority)優(yōu)先數(shù),icp也叫做棧外(in coming priority)優(yōu)先數(shù)。當(dāng)剛掃描到的運(yùn)算符ch的icp(ch)大于isp(stack)時(shí),則ch進(jìn)棧;當(dāng)剛掃描到的運(yùn)算符ch的icp(ch)小于isp(stack)時(shí),則位于棧頂?shù)倪\(yùn)算符退棧并輸出。從表中可知,icp(“(”)最高,但當(dāng)“(”進(jìn)棧后,isp(“(”)變得極低。其它運(yùn)算符進(jìn)入棧中后優(yōu)先數(shù)都升1,這樣可體現(xiàn)在中綴表達(dá)式中相同優(yōu)先級(jí)的運(yùn)算符自左向右計(jì)算的要求。運(yùn)算符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號(hào)配對“)”或棧底的“;”號(hào)與輸入流最后的“;”號(hào)配對時(shí)。前者將連續(xù)退出位于棧頂?shù)倪\(yùn)算符,直到遇到“(”為止。然后將“(”退棧以對消括號(hào),后者將結(jié)束算法。步序掃描項(xiàng)項(xiàng)類型 動(dòng) 作棧的變化 輸 出 0F ; 進(jìn)棧, 讀下一符號(hào); 1 a操作數(shù)F 直接輸出, 讀下一符號(hào);A 2 *操作符F isp ( ; ) icp ( - ), 退棧輸出; a x * F isp ( ; ) icp ( - ), 進(jìn)棧, 讀下一符號(hào); -a x * 5 b操作數(shù)F 直接輸出, 讀下一符號(hào); -a x * b 6 /操作符F isp ( - ) icp ( / ), 進(jìn)棧, 讀下一符號(hào) ; -/a x * b 7 x操作數(shù)F 直接輸出, 讀下一符號(hào); -/a x * b x 8 操作符F isp ( / ) icp ( ; ), 退棧輸出; -/a x * b x 2 F isp ( / ) icp ( ; ), 退棧輸出; -a x * b x 2/ F isp ( - ) icp ( ; ), 退棧輸出; a x * b x 2/ - F 結(jié)束22.設(shè)循環(huán)隊(duì)列的容量為70(序號(hào)從1到70),經(jīng)過一系列入隊(duì)和退隊(duì)運(yùn)算后,有:(1)front=15,rear=46;(2)front=45,rear=10問在上述兩種情況下,循環(huán)隊(duì)列中各有多少個(gè)元素?【解答】(1) 隊(duì)列中元素的個(gè)數(shù)為(MAXSIZE+rear-front) %MAXSIZE = (70+46-15)%70=31(2) 隊(duì)列中元素的個(gè)數(shù)為(MAXSIZE+rear-front) %MAXSIZE = (70+10-45)%70=3523.設(shè)用鏈表表示一個(gè)雙端隊(duì)列,要求可在表的兩端插入,但限制只能在表的一端刪除。試編寫基于此結(jié)構(gòu)的隊(duì)列的插入(enqueue)和刪除(dequeue)算法,并給出隊(duì)列空和隊(duì)列滿的條件。設(shè)此隊(duì)列含頭結(jié)點(diǎn),隊(duì)頭指針front指向頭結(jié)點(diǎn),限定在表頭端刪除隊(duì)列空:隊(duì)尾指針指向頭結(jié)點(diǎn),即rear=front時(shí),隊(duì)空隊(duì)列滿:因?yàn)槭擎湵恚?,只有?nèi)存空間不足時(shí)才會(huì)有隊(duì)滿的問題。void insertqueue(queuetype *Q,int location,elemtype x)/*Q:指向隊(duì)列的指針;location:插入位置,0表示隊(duì)頭,1表示隊(duì)尾;x:數(shù)據(jù)元素*/node *p;p=(node *)malloc(sizeof(node);p-data = x;if(location=0)/*在隊(duì)頭處插入*/p-next = Q-front-next;Q-front-next = p;if(Q-rear=Q-front)Q-rear = p;/*對空表插入*/else/*在隊(duì)尾處插入*/p-next = NULL;Q-rear-next = p;Q-rear = p;elemtype deletequeue(queuetype *Q)elemtype x;node * p;if(Q-rear = Q-front) return(NULL); /*空隊(duì)列*/p = Q-front-next;x = p-data;Q-front-next = p-next;if(Q-rear = p)Q-rear = Q-front/*對只有一個(gè)元素的隊(duì)列進(jìn)行刪除*/free(p);return(x);24.所謂回文,是指從前向后順讀和從后向前倒讀都一樣的不含空白字符的串。例如did,madamimadam,pop即是回文。試編寫一個(gè)算法,以判斷一個(gè)串是否是回文?!窘獯?】將字符串中全部字符進(jìn)棧,然后將棧中的字符逐個(gè)與原字符串中的字符進(jìn)行比較。算法如下:int palindrome (string S) stacktype * st;int yes = 1, i = 0;while(Si != “0”)push (st,Si); i+; /*掃描字符串,所有字符進(jìn)棧*/i = 0;while(Si != “0” )/*比較字符串*/ if(Si = st.GetTop( )pop(st); i+; else yes = 0; break; return(yes);【解答2】采用遞歸算法,判斷從s到e中的字符串是否回文,通過函數(shù)返回是或不是。int palindrome(char A , int start, int end) if (Astart != Aend ) return 0; else if ( s e ) return 1; else palindrome ( A, start+1, end-1 );25.設(shè)Ann為一個(gè)上三角矩陣,將A中所有非零元素按列序順次存入一維數(shù)組B中,則A與B元素的對應(yīng)關(guān)系是什么?【解答】上三角矩陣如下所示其數(shù)據(jù)元素滿足Aij=0,對所有的ij上三角矩陣正好是一個(gè)下三角矩陣的轉(zhuǎn)秩,我們知道,一個(gè)下三角矩陣按行壓縮存儲(chǔ)時(shí),矩陣元素與一維數(shù)組的對應(yīng)關(guān)系為AijBi*(i+1)/2+j,對所有的ij;因此,下三角矩陣按列序存儲(chǔ)在一維數(shù)組中的元素對應(yīng)關(guān)系為AijBj*(j+1)/2+i,對所有的ij.26.編寫串的替換函數(shù)Replace(str,str1,str2),將主串str中所有子串str1替換為str2?!窘獯稹恳姇鴓58第 17 頁 共 16 頁- 1.請仔細(xì)閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
32 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 習(xí)題一解答 計(jì)算機(jī) 軟件技術(shù) 基礎(chǔ) 習(xí)題 解答
鏈接地址:http://www.szxfmmzy.com/p-1584476.html