《計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 習(xí)題一解答.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 習(xí)題一解答.doc（17頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
線性結(jié)構(gòu) 習(xí)題解答
習(xí)題解答
3.設(shè)n為正整數(shù), 分析下列各程序段中加下劃線的語(yǔ)句的執(zhí)行次數(shù)。
(1) for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
c[i][j] = 0.0;
for (int k = 1; k <= n; k++)
c[i][j] = c[i][j] + a[i][k] * b[k][j];
}
(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(i<100 + n);
【解答】
(1)
(2)
(3)i = 1時(shí)，i = 2，j = j + i = 1 + 2 = 2 + 1，
i = 2時(shí)，i = 3，j = j + i = ( 2 + 1 ) + 3 = 3 + 1 + 2，
i = 3時(shí)，i = 4，j = j + i = ( 3 + 1 + 2 ) + 4 = 4 + 1 + 2 + 3，
i = 4時(shí)，i = 5，j = j + i = ( 4 + 1 + 2 + 3 ) + 5 = 5 + 1 + 2 + 3 + 4，
……
i = k時(shí)，i = k + 1，j = j + i = ( k + 1 ) + ( 1 + 2 + 3 + 4 + … + k )，
解出滿足上述不等式的k值，即為語(yǔ)句i = i + 1的程序步數(shù)。 (4) for語(yǔ)句每執(zhí)行一次，語(yǔ)句i=i+j將執(zhí)行n次，而i的值會(huì)增加
因此，當(dāng)for語(yǔ)句執(zhí)行k次后，i的值將變?yōu)?
故最終for語(yǔ)句的執(zhí)行次數(shù)k為滿足
的最小整數(shù)k，語(yǔ)句i = i + j的程序步數(shù)為n*k。
4.試編寫一個(gè)函數(shù)計(jì)算n!*2n的值，結(jié)果存放于數(shù)組A[arraySize]的第n個(gè)數(shù)組元素中，0 ￡ n ￡ arraySize。若設(shè)計(jì)算機(jī)中允許的整數(shù)的最大值為maxInt，則當(dāng)n>arraySize或者對(duì)于某一個(gè)k (0 ￡ k ￡ n)，使得k!*2k > maxInt時(shí)，應(yīng)按出錯(cuò)處理?？捎腥缦氯N不同的出錯(cuò)處理方式：
(1) 用printf顯示錯(cuò)誤信息及exit(1)語(yǔ)句來(lái)終止執(zhí)行并報(bào)告錯(cuò)誤；
(2) 用返回整數(shù)函數(shù)值0, 1來(lái)實(shí)現(xiàn)算法，以區(qū)別是正常返回還是錯(cuò)誤返回；
(3) 在函數(shù)的參數(shù)表設(shè)置一個(gè)引用型的整型變量來(lái)區(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;T[0]=1;
if ( n != 0 ) {
int edge = MaxInt / n / 2;
for ( i = 1; i < n; i++ ) {
value *= i*2;
T[i] = value;
if ( value > edge ) return 0;
}
value *= n * 2;
}
T[n] = value;
printf("A[ %d ]= %d\n”,n,T[n]);
return 1;
}
void main ( ) {
int A[arraySize];
int i;
for ( i = 0; i < arraySize; i++ )
if ( !calc ( A, i ) ) {
printf("failed at %d .\n", i );
break;
}
}
/*---------順序表結(jié)構(gòu)的定義.為簡(jiǎn)化起見(jiàn)，表元素我們使用整型數(shù)據(jù)-----------
-----------數(shù)據(jù)元素從data[0]處開(kāi)始存儲(chǔ)---------------------------------*/
typedef struct /*注意typedef的使用*/
{
int data[MAXSIZE]; /*數(shù)據(jù)域*/
int length; /*表長(zhǎng)*/
}listtype;
5.設(shè)有一個(gè)線性表 (a0, a1, …, an-2, an-1) 存放在一個(gè)一維數(shù)組A[arraySize]中的前n個(gè)數(shù)組元素位置。請(qǐng)編寫一個(gè)函數(shù)將這個(gè)線性表原地逆置，即將數(shù)組的前n個(gè)原址內(nèi)容置換為 (an-1, an-2, …, a1, a0)。最后分析此算法的時(shí)間復(fù)雜度及空間復(fù)雜度。
【解答】
void inverse (listtype * A) {
int tmp;
int n= A->length;
for( int i = 0; i <= ( n-1 ) / 2; i++ ){
tmp = A->data[i]; A->data[i] = A->data[n-i-1]; A->data[n-i-1] = tmp;
}
}
時(shí)間復(fù)雜度：需進(jìn)行n/2次循環(huán)，因此時(shí)間復(fù)雜度為O(n)；
空間復(fù)雜度：使用一個(gè)整形輔助存儲(chǔ)單元tmp，因此空間復(fù)雜度為O(1)。
6.順序表的插入和刪除要求仍然保持各個(gè)元素原來(lái)的次序。設(shè)在等概率情形下, 對(duì)有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 < L->length ) /*循環(huán), 尋找具有值x的元素并刪除它*/
if (L->data[i] == x ) { /*刪除具有值x的元素, 后續(xù)元素前移*/
for (j = i;j < L->length-1; j++ ) L->data[j] = L->data[j+1];
L-length--; /*表長(zhǎng)減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 < L->length) /*循環(huán), 尋找具有值x的元素并刪除它*/
if (L->data[i]>=s &&L->data[i]<= t){
/*刪除滿足條件的元素, 后續(xù)元素前移*/
for ( j = i; j < L->length-1; j++ ) L->data[j] = L->data[j+1];
L->length--; /*表長(zhǎng)減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 < L->length; i++ ) /*循環(huán), 尋找值 ≥s 的第一個(gè)元素*/
if ( L->data[i] >= s ) break; /*退出循環(huán)時(shí), i指向該元素*/
if ( i < L->length ) {
for (j = 1; i + j < L->length; j++ )/*循環(huán), 尋找值 > t 的第一個(gè)元素*/
if (L->data[i+j] > t ) break; /*退出循環(huán)時(shí), i+j指向該元素*/
for (k = i+j; k < L->length; k++ ) /*刪除滿足條件的元素, 后續(xù)元素前移*/
L->data[k-j] = L->data[k];
L->length-= j; /*表長(zhǎng)減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->data[i];
value2 = LB->data[j];
while (i < LA->length && j < LB->length ) {
/*循環(huán), 兩兩比較, 小者存入結(jié)果表*/
if (value1 <= value2){
LC->data[k] = value1; i++; value1=LA->data[i];}
else {
LC->data[k] = value2; j++; value2=LB->data[j];}
k++;
}
while( i < LA->length){ /*當(dāng)LA表未檢測(cè)完, 繼續(xù)向結(jié)果表傳送*/
LC->data[k] = value1; i++; k++; value1 = LA->data[i];
}
while( j < LB->length){ /*當(dāng)LB表未檢測(cè)完, 繼續(xù)向結(jié)果表傳送*/
LC->data[k] = value2; j++; k++; value2 = LB->data[j];
}
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(“表空\(chéng)n”; exit(1);
}
i=0;
while ( i < L->length ) { /*循環(huán)檢測(cè)*/
j = i + 1;
tmp = L->data[i];
while( j < L->length ) { /*對(duì)于每一個(gè)i, 重復(fù)檢測(cè)一遍后續(xù)元素*/
if( tmp == L->data[j]) { /*如果相等,刪除此結(jié)點(diǎn)，后續(xù)元素前移*/
for( k = j+1; k < L->length; k++ ) L->data[k-1] = L->data[k];
L->length--; /*表最后元素位置減1*/
}
else j++;
}
i++; /*檢測(cè)完L->data[i], 檢測(cè)下一個(gè)*/
}
}
8.線性表可用順序表或鏈表存儲(chǔ)。試問(wèn)：
(1) 兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)?
(2) 如果有n個(gè)表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(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)行過(guò)程中動(dòng)態(tài)分配和釋放，且只要存儲(chǔ)器中還有空間，就不會(huì)產(chǎn)生存儲(chǔ)溢出的問(wèn)題。同時(shí)在插入和刪除時(shí)不需要保持?jǐn)?shù)據(jù)元素原來(lái)的物理順序，只需要保持原來(lái)的邏輯順序，因此不必移動(dòng)數(shù)據(jù)，只需修改它們的鏈接指針，修改效率較高。但存取表中的數(shù)據(jù)元素時(shí)，只能循鏈順序訪問(wèn)，因此存取效率不高。
(2) 如果有n個(gè)表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，表的總數(shù)也可能自動(dòng)改變、在此情況下，應(yīng)選用鏈接存儲(chǔ)表示。
如果采用順序存儲(chǔ)表示，必須在一個(gè)連續(xù)的可用空間中為這n個(gè)表分配空間。初始時(shí)因不知道哪個(gè)表增長(zhǎng)得快，必須平均分配空間。在程序運(yùn)行過(guò)程中，有的表占用的空間增長(zhǎng)得快，有的表占用的空間增長(zhǎng)得慢；有的表很快就用完了分配給它的空間，有的表才用了少量的空間，在進(jìn)行元素的插入時(shí)就必須成片地移動(dòng)其他的表的空間，以空出位置進(jìn)行插入；在元素刪除時(shí)，為填補(bǔ)空白，也可能移動(dòng)許多元素。這個(gè)處理過(guò)程極其繁瑣和低效。
如果采用鏈接存儲(chǔ)表示，一個(gè)表的存儲(chǔ)空間可以連續(xù)，可以不連續(xù)。表的增長(zhǎng)通過(guò)動(dòng)態(tài)存儲(chǔ)分配解決，只要存儲(chǔ)器未滿，就不會(huì)有表溢出的問(wèn)題；表的收縮可以通過(guò)動(dòng)態(tài)存儲(chǔ)釋放實(shí)現(xiàn)，釋放的空間還可以在以后動(dòng)態(tài)分配給其他的存儲(chǔ)申請(qǐng)要求，非常靈活方便。對(duì)于n個(gè)表(包括表的總數(shù)可能變化)共存的情形，處理十分簡(jiǎn)便和快捷。所以選用鏈接存儲(chǔ)表示較好。
(3) 應(yīng)采用順序存儲(chǔ)表示。因?yàn)轫樞虼鎯?chǔ)表示的存取速度快，但修改效率低。若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)采用順序存儲(chǔ)表示較好。
/*---------鏈表結(jié)構(gòu)的定義.為簡(jiǎn)化起見(jiàn)，表元素我們使用整型數(shù)據(jù)-----------
-----------此鏈表帶頭結(jié)點(diǎn)--------------------------------------------*/
typedef struct mynode{
int data; /*數(shù)據(jù)域：整型*/
struct mynode *next; /*指針域*/
} node, linklisttype;
9.試寫出計(jì)算線性鏈表長(zhǎng)度的算法。
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è)算法，通過(guò)遍歷一趟鏈表，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針h指向原鏈表的最后一個(gè)結(jié)點(diǎn)。
【解答】
void 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)的后繼改為指向其原來(lái)的前驅(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分解為L(zhǎng)A、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 < 0){ /*將p鏈入鏈表LB的pb后*/
pb->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é)果鏈表仍使用原來(lái)兩個(gè)鏈表的存儲(chǔ)空間, 不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)。
【解答】
void 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é)果鏈表仍使用原來(lái)兩個(gè)鏈表的存儲(chǔ)空間, 不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)。
【解答】
Linklisttype * 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鏈為L(zhǎng)C的第一個(gè)結(jié)點(diǎn)*/
p = pa->next;
pa->next = LC->next;
LC->next = pa;
pa = p;
}
else{ /*將pa鏈為L(zhǎng)C的第一個(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)之前。
【解答】設(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;
else{
pre = p;
p = p->next;
}
if(p != CL){ /*查找成功*/
per->next = p->next; /*在原來(lái)位置刪除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)，如右圖所示。試問(wèn)：
(1) 設(shè)有編號(hào)為1,2,3,4,5,6的六輛列車, 順序開(kāi)入棧式結(jié)構(gòu)的站臺(tái), 則可能的出棧序列有多少種?
(2) 若進(jìn)站的六輛列車順序如上所述, 那么是否能夠得到435612, 325641, 154623和135426的出站序列, 如果不能, 說(shuō)明為什么不能; 如果能, 說(shuō)明如何得到(即寫出"進(jìn)棧"或"出棧"的序列)。
【解答】
(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可以得到。
3
5
6
2
2
4
4
4
4
1
1
1
1
1
1
1
1
3 32 32 325 325 3256 32564 325641
5
3
4
4
1
2
2
2
2
6
1 1 13 135 1354 13542 13542 135426
17.試證明：若借助?？捎奢斎胄蛄?, 2, 3, …, n得到一個(gè)輸出序列p1, p2, p3, …, pn (它是輸入序列的某一種排列)，則在輸出序列中不可能出現(xiàn)以下情況，即存在i < j < k，使得pj < pk < pi。(提示：用反證法)
【解答】
因?yàn)榻柚鷹Ｓ奢斎胄蛄?, 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 < pi的情形；
18.將編號(hào)為0和1的兩個(gè)棧存放于一個(gè)數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號(hào)棧的棧頂指針top[0]等于-1時(shí)該棧為空，當(dāng)?shù)?號(hào)棧的棧頂指針top[1]等于m時(shí)該棧為空。兩個(gè)棧均從兩端向中間增長(zhǎng)。當(dāng)向第0號(hào)棧插入一個(gè)新元素時(shí)，使top[0]增1得到新的棧頂位置，當(dāng)向第1號(hào)棧插入一個(gè)新元素時(shí)，使top[1]減1得到新的棧頂位置。當(dāng)top[0]+1 == top[1]時(shí)或top[0] == top[1]-1時(shí)，?？臻g滿，此時(shí)不能再向任一棧加入新的元素。試定義這種雙棧(Double Stack)結(jié)構(gòu)的類定義，并實(shí)現(xiàn)判?？?、判棧滿、插入、刪除算法。
【解答】
bot[0] top[0] top[1] bot[1]
雙棧的類型定義如下：
typedef struct{
int top0,top1;
elemtype data[MAXSIZE];
}DoubleStack;
判棧空
int DoubleStackEmpty(DoubleStack * DS,int StackNo){
/*DS：指向雙棧的指針，StackNo:0或1，指定要判斷的是第0棧，還是第一棧
if(StackNo==0)
return(DS->top0 < 0);
else
retrun(DS->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){/*對(duì)第0棧插入*/
DS->top0++;
DS->data[top0]=x;
}
else{/*對(duì)第1棧插入*/
DS->top1--;
DS->data[top1]=x;
}
return(TRUE);
}
刪除算法
elemtype PushDoubleStack(DoubleStack * DS,int StackNo){
/*從StackNo棧中刪除并返回一個(gè)元素，若棧空，則返回NULL*/
if(DoubleStackEmpty(DS,StackNo)) return(NULL);
if(StackNo==0){/*對(duì)0號(hào)棧進(jìn)行操作*/
DS->top0--;
return(DS->data[DS->top0+1]);
}
else{
DS->top1++;
return(DS->data[DS->top1-1]);
}
}
19.改寫順序棧的進(jìn)棧成員函數(shù)Push(x)，要求當(dāng)棧滿時(shí)執(zhí)行一個(gè)stackFull( )操作進(jìn)行棧滿處理。其功能是：動(dòng)態(tài)創(chuàng)建一個(gè)比原來(lái)的棧數(shù)組大二倍的新數(shù)組，代替原來(lái)的棧數(shù)組，原來(lái)?xiàng)?shù)組中的元素占據(jù)新數(shù)組的前MaxSize位置。
【解答】
void push(stack * S,elemtype x) {
if(StackEmpty(S)) stackFull(S); //棧滿，做溢出處理
S->top ++;
S->data[S->top] = x; //進(jìn)棧
}
void stackFull(stack *S){
elemtype *temp;
temp=calloc(3*MAXSIZE,sizeof(elemtype)); //創(chuàng)建體積大二倍的數(shù)組
for ( int i = 0; i <= S->top; i++ ) //傳送原數(shù)組的數(shù)據(jù)
temp[i] = S->data[i];
free(S->data); //刪去原數(shù)組
MAXSIZE *= 3; //數(shù)組最大體積增長(zhǎng)二倍
S->data = temp; //新數(shù)組成為棧的數(shù)組空間
}
20.根據(jù)教案中給出的優(yōu)先級(jí)，回答以下問(wèn)題：
(1) 在表達(dá)式求值的過(guò)程中，如果表達(dá)式e含有n個(gè)運(yùn)算符和分界符，問(wèn)操作數(shù)棧(NS)中最多可存入多少個(gè)元素？
(2) 如果表達(dá)式e含有n個(gè)運(yùn)算符，且括號(hào)嵌套的最大深度為6層，問(wèn)棧中最多可存入多少個(gè)元素？
【解答】
(1) 如果表達(dá)式e含有n個(gè)運(yùn)算符和分界符，則可能的運(yùn)算對(duì)象有n+1個(gè)。因此在利用后綴表達(dá)式求值時(shí)所用到的運(yùn)算對(duì)象棧中最多可存入n+1個(gè)元素。
(2) 同上。
21.表達(dá)式的中綴表示為a * x - b / x^2，試?yán)脳⑺臑楹缶Y表示ax * bx2^/ -。寫出轉(zhuǎn)換過(guò)程中棧的變化。(^表示乘方運(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
1
isp也叫做棧內(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)配對(duì)“)”或棧底的“;”號(hào)與輸入流最后的“;”號(hào)配對(duì)時(shí)。前者將連續(xù)退出位于棧頂?shù)倪\(yùn)算符，直到遇到“(”為止。然后將“(”退棧以對(duì)消括號(hào)，后者將結(jié)束算法。
步序
掃描項(xiàng)
項(xiàng)類型
動(dòng) 作
棧的變化
輸 出
0
F ';' 進(jìn)棧, 讀下一符號(hào)
;
1
a
操作數(shù)
F 直接輸出, 讀下一符號(hào)
;
A
2
*
操作符
F isp ( ' ; ' ) < icp ( ' * ' ), 進(jìn)棧, 讀下一符號(hào)
; *
A
3
x
操作數(shù)
F 直接輸出, 讀下一符號(hào)
; *
a x
4
-
操作符
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 ( '^' ), 進(jìn)棧, 讀下一符號(hào)
; -/^
a x * b x
9
2
操作數(shù)
F 直接輸出, 讀下一符號(hào)
; -/^
a x * b x 2
10
;
操作符
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)過(guò)一系列入隊(duì)和退隊(duì)運(yùn)算后，有：
（1）front=15，rear=46；
（2）front=45，rear=10
問(wèn)在上述兩種情況下，循環(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=35
23.設(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ì)滿的問(wèn)題。
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;/*對(duì)空表插入*/
}
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 /*對(duì)只有一個(gè)元素的隊(duì)列進(jìn)行刪除*/ free(p);
return(x);
}
24.所謂回文，是指從前向后順讀和從后向前倒讀都一樣的不含空白字符的串。例如did，madamimadam，pop即是回文。試編寫一個(gè)算法，以判斷一個(gè)串是否是回文。
【解答1】
將字符串中全部字符進(jìn)棧，然后將棧中的字符逐個(gè)與原字符串中的字符進(jìn)行比較。算法如下：
int palindrome (string S) {
stacktype * st;
int yes = 1, i = 0;
while(S[i] != “\0”){
push (st,S[i]); i++; /*掃描字符串，所有字符進(jìn)棧*/
}
i = 0;
while(S[i] != “\0” ) /*比較字符串*/
if(S[i] == st.GetTop( )){pop(st); i++; }
else {yes = 0; break; }
return(yes);
}
【解答2】
采用遞歸算法，判斷從s到e中的字符串是否回文，通過(guò)函數(shù)返回是或不是。
int palindrome(char A[ ], int start, int end) {
if (A[start] != A[end] ) return 0;
else if ( s > e ) return 1;
else palindrome ( A, start+1, end-1 );
}
25.設(shè)A[n][n]為一個(gè)上三角矩陣，將A中所有非零元素按列序順次存入一維數(shù)組B中，則A與B元素的對(duì)應(yīng)關(guān)系是什么？
【解答】上三角矩陣如下所示
其數(shù)據(jù)元素滿足Aij=0，對(duì)所有的i>j
上三角矩陣正好是一個(gè)下三角矩陣的轉(zhuǎn)秩，我們知道，一個(gè)下三角矩陣按行壓縮存儲(chǔ)時(shí)，矩陣元素與一維數(shù)組的對(duì)應(yīng)關(guān)系為
A[i][j]àB[i*(i+1)/2+j]，對(duì)所有的i>j；
因此，下三角矩陣按列序存儲(chǔ)在一維數(shù)組中的元素對(duì)應(yīng)關(guān)系為
A[i][j]àB[j*(j+1)/2+i]，對(duì)所有的i
下載提示(請(qǐng)認(rèn)真閱讀)
- 1.請(qǐng)仔細(xì)閱讀文檔，確保文檔完整性，對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔，不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請(qǐng)點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)！
下載文檔到電腦，查找使用更方便
32
積分
- 配套講稿：
如PPT文件的首頁(yè)顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制：
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
-
計(jì)算機(jī)軟件技術(shù)基礎(chǔ)
習(xí)題一解答
計(jì)算機(jī)
軟件技術(shù)
基礎(chǔ)
習(xí)題
解答
- 溫馨提示:
1: 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請(qǐng)勿作他用。
計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 習(xí)題一解答.doc
鏈接地址：http://www.820124.com/p-1584476.html