Board logo

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

發表人: 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/) Powered by Discuz! 4.1.0