TWed2k - 文字海洋 - [求助]誰能幫一下功課...資料結構(朋友幫問的==)

主題: [閒話家常] [求助]誰能幫一下功課...資料結構(朋友幫問的==) [打印本頁]

發表人: bbking 時間: 2005-11-14 01:04 AM 主題: [求助]誰能幫一下功課...資料結構(朋友幫問的==)

資料結構94學年第一學期期中考...
有誰會能幫解答一下嘛=_=||
因為我也不是本科的..
幫朋友問問摟~
如題:
資料結構 94學年第一學期期中考

--------------------------------------------------------------------------------
1.試分析下列程式的複雜度。
fun(int a[],int n)
{
int i,j;
a[1]=0;
for(i=2; i < n; i++) a[i]=1;
for(i=2; i < n/2; i++)
for(j=2; j < n/i; j++)
a[i*j]= 0;
for(i=1; i < n; i++)
if (a[i]) printf("%d\n",i);
}


2.有一一維陣列A[6000],及三維陣列B[30][20][10],試回答下列問題:
1) 若用以列為主(row major)的方式來排列三維陣列則A[2345]對應到B陣列的哪一個元素?
2) 若用以行為主(column major)的方式來排列三維陣列則A[2345]對應到B陣列的哪一個元素?


3.有多項式定義如下:
F(X)=3x^4+5X^2+X+6,P(X)=2X^3-4X^2+19,Q(X)=10X^5-7X^3+19X+10,
試設計程式來計算F(X)+P(X)-Q(X)。


4.試利用堆疊的資料結構與運算,設計一程式來計算下列後序表示式。(參考課本3-26頁)
6 9 3 / - 8 6 2 - / +

5.現有一五層出租套房的各樓層房間圖,如下圖所示:
501 502 503
401 402 403
301 302 303
201 202 203
101 102 103

上述圖例中的每間套房租金是5000元,現在第201,402,303,102,501,302已經交過本月房租,寫一個程式輸入已經交租金的房間號碼,然後列印出未交房租的房間編號和全部已交,未交的房租款項。

發表人: darkstone007 時間: 2005-11-18 01:03 AM

1.試分析下列程式的複雜度。
fun(int a[],int n)
{
      int i,j;
      a[1]=0;
      for(i=2; i < n; i++) a[i]=1;
      for(i=2; i < n/2; i++)
            for(j=2; j < n/i; j++)
                     a[i*j]= 0;
      for(i=1; i < n; i++)
            if (a[i]) printf("%d\n",i);
}

{1}空間複雜度
由於使用了三個int變數n,i,j和一個int陣列
所以用了4byte*3(三個int變數)+4byte*int陣列a[]的元素數目+2byte(其實陣列是一個指標所以還要加一個指標的大小)
(2)時間複雜度
fun(int a[],int n)
{
        int i,j;//0次(因為只有宣告所以只算空間複雜度)
         a[1]=0;//1次
         for(i=2; i < n; i++)
            //for迴圈裡加一次
        a[i]=1;1次
        //for迴圈結束算一次,但是for裡面的要乘上n-2
        for(i=2; i < n/2; i++)
        //for迴圈裡加一次
                 for(j=2; j < n/i; j++)
                    //for迴圈裡加一次
                     a[i*j]= 0;//1次
            //for迴圈結束算一次,但是for裡面的要乘上n/i-2
            //for迴圈結束算一次,但是for裡面的要乘上n/2-2
        for(i=1; i < n; i++)
        //for迴圈裡加一次
            if (a[i]) //if算一次
            printf("%d\n",i);//當陣列a的元素不等於0的時候,printf算一次
            //for迴圈結束算一次,但是for裡面的要乘上n-1
}
所以總共是0+1+(1+1)*(n-2)+1+(1+(1+1)*(n/i-2)+1)*(n/2-2)+1+(1+1)*(n-1)+1+(n-(1到(n/2-1)的所有質數個數))
2.有一一維陣列A[6000],及三維陣列B[30][20][10],試回答下列問題:
1) 若用以列為主(row major)的方式來排列三維陣列則A[2345]對應到B陣列的哪一個元素?

因為排的時候是[0][0][0],[0][0][1],...,[0][0][10],[0][1][0],.......
所以在二維裡每一面有(20+1)*(10+1)個
2345/((20+1)*(10+1))=10餘35
總共排滿10面剩35個,所以對應到B陣列的11面,但是陣列是從0開始的,所以第11面就是[10]
然後在35個在二維裡排的方法是[0][0],[0][1],...,[0][10],[1][0],.....
每條線有10+1個
35/(10+1)=3餘2
所以是排滿三條線,對應到第四條線,但是陣列是從0開始的,所以第四條線就是[3]
剩下2,但是陣列A[2345]也是從0開始的,所以其實還要加1,剩下三個
三個的話就是排到[2]
以列為主的方式來排的話是B[10][3][2]
2) 若用以行為主(column major)的方式來排列三維陣列則A[2345]對應到B陣列的哪一個元素?

行為主的話沒想過....大概是倒過來吧
所以就是這樣排[0][0][0],[1],[0],[0],...,[30][0][0],[0][1][0],.....
所以在二維裡每一面有(30+1)*(20+1)個
2345/((30+1)*(20+1))=3餘392
所以就是[3]
然後在392個在二維裡排的方式是[0][0],[1][0],...,[20][0],[0][1],.....
每條線有20+1個
392/(20+1)=18餘14
所以是[18]
剩下14
就是[14]
寫出來就變成B[14][18][3]
3.有多項式定義如下:
F(X)=3x^4+5X^2+X+6,P(X)=2X^3-4X^2+19,Q(X)=10X^5-7X^3+19X+10,
試設計程式來計算F(X)+P(X)-Q(X)。

//因為三個多項式最高才五次,也不是稀疏的,簡單用array宣告吧
#include using namespace std;

int[] add(int[],int[]);
int[] sub(int[],int[]);

int main(){
int F[5]={6,1,5,0,3,0};
int P[5]={19,0,-4,2,0,0};
int Q[5]={10,19,0,-7,0,10};
int answer[5];
answer=sub(add(F,P),Q);
return 0;
}
int[] add(int a[],int b[]){
int temp[5];
for(int i=0;i<6;i++)
temp[i]=a[i]+b[i];
retrun temp;
}
int[] sub(int a[],int b[]){
int temp[5];
for(int i=0;i<6;i++)
temp[i]=a[i]-b[i];
retrun temp;
}
4.試利用堆疊的資料結構與運算,設計一程式來計算下列後序表示式。(參考課本3-26頁)
6 9 3 / - 8 6 2 - / +

#include using namespace std;

#define STACK_MAX 10
int stack[STACK_MAX];
bool IsFull();
bool IsEmpty();
int pop(int*);
void push(int,int*);
int top=-1;

int main(){
char postfix[11]={'6','9','3','/','-','8','6','2','-','/','+'};
int temp;
for(int i=0;i<12;i++){
if(postfix[i]=='0'){push(0);}
else if(postfix[i]=='1'){push(1);}
else if(postfix[i]=='2'){push(2);}
else if(postfix[i]=='3'){push(3);}
else if(postfix[i]=='4'){push(4);}
else if(postfix[i]=='5'){push(5);}
else if(postfix[i]=='6'){push(6);}
else if(postfix[i]=='7'){push(7);}
else if(postfix[i]=='8'){push(8);}
else if(postfix[i]=='9'){push(9);}
else if(postfix[i]=='+'){push(pop(&top)+pop(&top));}
else if(postfix[i]=='-'){
temp = pop(&top);
push(pop(&top)-temp);
}
else if(postfix[i]=='/'){
temp = pop(&top);
push(pop(&top)/temp);
}
}
int answer = pop(&top);
return 0;
}
bool IsFull(){
if(top>=STACK_MAX)
return true;
else
return false;
}
bool IsEmpty(){
if(top<0)
return true;
else
return false;
}
int pop(int *top){
if(IsEmpty())
cout<<"Stack is empty."< else{
return stack[*top--];
}
}
void push(int item, int *top){
if(IsFull())
cout<<"Stack is full."< else{
stack[++*top]=item;
}
}
5.現有一五層出租套房的各樓層房間圖,如下圖所示:
501 502 503
401 402 403
301 302 303
201 202 203
101 102 103

上述圖例中的每間套房租金是5000元,現在第201,402,303,102,501,302已經交過本月房租,寫一個程式輸入已經交租金的房間號碼,然後列印出未交房租的房間編號和全部已交,未交的房租款項。

//用一個二維陣列表示房租已交未交
#include using namespace std;
int main(){
bool rent[6][4];
rent[2][1]=true;
rent[4][2]=true;
rent[3][3]=true;
rent[1][2]=true;
rent[5][1]=true;
rent[3][2]=true;
int temp;
cout<<"請輸入已交房租號碼(輸入0則結束輸入程序):";
cin>>temp;
while(temp){
if((temp/100)<1||(temp/100)>5||(temp%100)<1||(temp%100)>3){
cout<<"無此房間"< else{
rent[temp/100][temp%100]=true;}
cout<<"請輸入已交房租號碼(輸入0則結束輸入程序):";
cin>>temp;
}
cout<<"未交房租的房間編號:"
for(int i=1;i<6;i++){
for(int j=1;j<4;j++){
if(rent[i][j]==false)
cout<<"["< }
}
cout<<"全部已交未交的房租款項:"< for(int i=5;i>0;i--){
for(int j=1;j<4;j++){
cout<<"["< }
cout< }
return 0;
}

註:
我也是念資訊的
這門課也有修
修的....不是很好....orz
所以答案錯的機率很大.....
希望有標準答案的時候也寫上來唄

[darkstone007 在 2005-11-25 02:51 AM 作了最後編輯]

歡迎光臨 TWed2k (http://twed2k.org/)