---------------------------------------------------------

Chào mừng bạn đến với diễn đàn Công Nghệ Thông Tin CK08 Ca Mau Community College.
Hy vọng diễn đàn sẽ là nơi giao lưu học hỏi và chia sẽ niềm đam mê tri thức.
Chúc bạn một ngày an lành và vui vẻ và luôn thành công trong cuộc sống.
################################


 
Trang ChínhTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Bài giải đề thi môn CTDL & Giải Thuật

Go down 
Tác giảThông điệp
truyenITPro
Moderator
Moderator
avatar

Tổng số bài gửi : 153
Join date : 13/07/2011
Age : 30
Đến từ : Phú Hưng - Cái Nước - Cà Mau

Bài gửiTiêu đề: Bài giải đề thi môn CTDL & Giải Thuật   Mon Sep 19, 2011 2:07 pm

Đây là bài giải mình của mình và tham khảo của bạn Tuyền, các bạn có ý kiến gì thì bổ sung thêm cho hoàn chỉnh để lần 2 chúng ta thi đạt kết quả cao hơn. Theo như nhận định của mình thì đề lần 2 môn này chẳng khác gì đề thi lần 1, vì xin đáp án lần 1 không ai cho hết farao
Code:
BÀI 1:
#include<iostream.h>
#define Maxlength 30
typedef int Position;
typedef struct{
    Int gt;
    Int soxo;
  } ketqua;
  typedef ketqua Elementtype ;
  typedef struct{
          Elementtype  element[Maxlength];
          Position Last;
} List;

a.   void MakeNull (List *L)
  {
      L->Last=0;
 }
b.   int Empty (List L)
  {
      Return L.Last==0;
  }
c.   int Full (List L)
      {
          Return L.Last==Maxlength;
      }
d.   Position First (List L)
  {
    Return 1;
  }
e.   Position End (List L)
  {
    Return L.Last+1;
 }
f. void InsertEnd ( int giai, int so, position P, List *L)
{
       if (L->last == Maxlength)
      cout<<"Danh sach day";
   else if (P < 0 || P > L->last +1)
      cout<<"Vi tri khong hop le";
   else
   {
      position Q;
      for (Q=End(*L);Q>=P;Q--)
      {
         L->giai[Q]=L->giai[Q-1];
         L->so[Q]=L->so[Q-1];
      }
      L->last++;
      L->giai[P-1]=giai;
      L->so[P-1]=so;
   }
}
g. void Search (int X, List L)
{
    Position P;
     int Found = 0;
   P = First(L);
        Cout<< “Nhap vao so tren ve so:”; cin>>X;
    while ((P != End(L)) && (Found == 0))
      if (Retrieve(P,L) == X) Found = 1;
        cout<< “Ve so trung giai:”;
      cout<< “so giai ve da trung thuong:”; (giai).//hien thi so thu tu giai thuong ma ve so da trung thuong.
      else P = Next(P, L);
      cout<< “Ve so khong trung giai:”;
}

  Void Nhap ( List *L) // đề cho sẵn
  Void Print (List L) // đề cho sẵn
h. void main()
 {    List L;
    ElementType X;
    Position P;
    cout<< “ Nhap vao so cua ve so can do:”; cin>>X;
    Nhap(&L);
      cout<<"Day so vua nhap: ";
    Print(L);
  Search( &X, L);


BÀI 2:
typedef  int Keytype;
typedef struct Node {
                  Keytype Key;
                  Node *Left;
                  Node *Right;
        };
typedef  Node *Ttree;

a.   void MakeNullTree (TTree *T)
        {
              (*T)=Null;
        }
b.   int EmptyTree (TTree T)
{
    Return T==Null;
}
c.   TTree Left_child (TTree T)
  {
    If ( T!=Null) return T->Left;
    Else return Null;
 }
d.   d. TTree Right_child (TTree T)
  {
    If ( T!=Null) return T->Right;
    Else return Null;
 }
e.   void LNR (TTree T)
{
    If (Left_child(T) !=Null) LNR (Left_child(T));
      Cout<< T->Key;
  If (Right_child(T) !=Null) LNR (Right_child(T));
}
f.   TTree Search (Keytype K, TTree T)
  {
      If (T==Null) return Null;
    Else if (T->Key==X)
    Return T;
    Else if (T->Key <X)
      Return Search (X, T->Right);
  Else
    Return Search (X, T->Left);
}
g.   void DeleteNode ( Keytype X, TTree T)
{  if (T != Null)
  If (X < T->Key ) DeleteNode (X, T->Left)
  Else if (X > T->Key) DeleteNode (X, T->Right)
  Else if ( T-> Left ==Null) && (T-> Right==Null)
      T=Null;
  Else if ( T->Left==Null) T=T-> Right;
  Else if ( T-> Right ==Null) T=T-> Left;
  Else T->Key = DeleteMin (T-> Right);
}
BAI 3:
#include <iostream.h>
#include “Person.cpp”
Class Teacher : public Person {
      Float Hesoluong;
      Char * Hocvi;
Public:
    Teacher();
    Teacher( char*, char*, char*, float, char*);
    Float phucap();
    Float tinhluong();
Friend istream & operator >> (istream & , Teacher & );
Friend ostream & operator  << (ostream &, Teacher & );
};
Teacher::Teacher (): Person()
  {
      Hesoluong=1;
      Strcpy(Hocvi,””);
  }
Teacher::Teacher (char *s1, char *s2, char *s3, float a, char* s4) : Person (s1, s2, s3)
{
      Hesoluong=a;
      Strcpy ( Hocvi, s4);
}
Float Teacher :: phucap()
{
  Float kq;
 If (strcmp (Hocvi, “tiensi”)==0)
 Kq=500;
 Else if (strcmp( Hocvi, “thacsi”)==0)
 Kq=300;
 Else
  Kq=200;
Return kq;
}
Float Teacher :: tinhluong()
{
  Return (Hesoluong * 830) + phucap();
}
Istream & operator >> (istream & is, Teacher & T)
{    char tam[15];
  Is>>*(Person*)&T;
 cout<< “Nhap he so luong:”; is>>T.Hesoluong;
cout<< “Nhap hoc vi:”; is.getline( tam,15);
T.Hocvi=strdup( tam);
Return is;
}
Ostream & operator << (ostream & os, Teacher & T)
{
  os << (Person)T;
  os << “ He so luong:”<<T.Hesoluong<<”\n”;
  os << “Hoc vi:”<<T. Hocvi <<”\n”;
  os<< “phu cap:” <<T.phucap()<<”\n”;
  os<< “Luong:” <<T.tinhluong()<<”\n”;
    Return os;
}
Char * layhocvi () { return Hocvi;}
2. void main()
{
  Teacher *ds;  char ht[50];
  Int i,m;
cout<< “ Nhap so luong giao vien:”; cin>>m;
  ds= New Teacher[m];
      for (i=0; i<m; i++)
        {
            cout<< “ Nhap phan tu thu:”<<i+1<<”\n”;
            cin>>ds[i];
      }
              cout<< endl;
      for (i=0; i<m; i++)
                {
                  cout<< “ Phan tu thu:”<<i+1<<”\n”;
                cout<< ds[i];
              }
cout<< “Nhap ho ten cua giao vien can tim hoc vi:”;
    cin>>ht;
If (strcmp ( ds[i]. Person :: layhoten() , ht)==0)
      cout<< ds[i]. Hocvi;
delete [] ds;
}
Các bạn nào lần 1 thi qua môn này thì góp ý thêm nhé...Vinh or Vương.v.v.v. Thanks vì tập thể
Về Đầu Trang Go down
phuongvu
Thành Viên chính thức
Thành Viên chính thức
avatar

Tổng số bài gửi : 25
Join date : 10/10/2010
Age : 28
Đến từ : Viet Nam

Bài gửiTiêu đề: Re: Bài giải đề thi môn CTDL & Giải Thuật   Wed Sep 21, 2011 7:58 pm

thật không vậy bác!! thế thì phải học kỹ mới được.thi lần 1 lấy kinh nghiệm thi lần 2.haizzzz Cười bò Cười bò Cười bò
Về Đầu Trang Go down
truyenITPro
Moderator
Moderator
avatar

Tổng số bài gửi : 153
Join date : 13/07/2011
Age : 30
Đến từ : Phú Hưng - Cái Nước - Cà Mau

Bài gửiTiêu đề: Re: Bài giải đề thi môn CTDL & Giải Thuật   Wed Sep 21, 2011 9:32 pm

thì mình suy luận zị đó, đề lần 1 như vậy rớt cỡ đó, ra đề lần 2 khác lần 1 nữa chắc chết nữa....Nhưng mà cái bài này mình giải không có hoàn chỉnh đâu nhé, cần mọi người bổ sung hoàn thiện nữa đó, cần 1 số bạn đã vượt qua kỳ lần 1 góp ý thêm...ok


Dạo này chắc bận hết rồi sao ko thấy ai góp ý hết vậy ta??? chắc xóa 1 mình nghiên cứu luôn quá, 1 tuần nữa ko có ai là Del Yêu thế luôn, tự nghiên cứu luôn, not Share nữa :oops:
Về Đầu Trang Go down
phuongvu
Thành Viên chính thức
Thành Viên chính thức
avatar

Tổng số bài gửi : 25
Join date : 10/10/2010
Age : 28
Đến từ : Viet Nam

Bài gửiTiêu đề: Re: Bài giải đề thi môn CTDL & Giải Thuật   Thu Sep 22, 2011 10:37 am

sao thế bác. cứ hay tự kĩ không àh. tiếp tục đi dạo này không có time mà.hi. nói chung là giúp đỡ đi. Yêu thế
Về Đầu Trang Go down
stan



Tổng số bài gửi : 3
Join date : 08/08/2011

Bài gửiTiêu đề: Re: Bài giải đề thi môn CTDL & Giải Thuật   Sat Sep 24, 2011 7:26 pm

Đây là bài giải của Vương. Chúc các bạn thi thành công!
Code:

PHẦN A
Câu 1:
#define Maxlength 30
typedef int Position;
typedef struct
   {
      int gt;
      int soxo;
   }Ketqua;
typedef Ketqua ElementType;
typedef struct
   {
      ElementType Element[Maxlength];
      Position Last;
   }List;
//Câu a
void MakeNull(List *L)
{
   L->Last=0;
}
//Câu b
int Empty(List L)
{
   return L.Last = = 0;
}
//Câu c
int Full(List L)
{
   return L->Last = =Maxlength;
}
//Câu d
Position First(List L)
{
   return 1;
}
//Câu e
Position End(List L)
{
   return L.Last+1;
}
//Hai câu f và g tôi không chắt là đúng
//Câu f
void InsertEnd(int giai, int so, List *L)
{
   If( ! Full(L))
   {
      L.Element[End(L)-1].gt=giai;
      L.Element[End(L)-1].soxo=so;
   }
else
{
   Printf(“Danh sach day !”);
}

}
//Câu g
void Search(int X, List L)
{
Position P;
While(P!=End(L))
{
      if(L.Element[P].soxo = = X )
         printf(“%c”,L.Element[P].gt);
      P=P+1;
}
}
//Câu h
void main()
{
   List L;
   int n;
   Nhap(&L);
   Print(L);
   cout<<”Nhap so cua ve so can do :”;
   cin>>n;
   Search(n,L);
}
Câu 2:
typedef int KeyType;
typedef struct Node

KeyType Key;
       Node *Left;
   Node *Right;
}
typedef Node* TTree;
//Câu a
void MakeNull_Tree(TTree *T)
{
(*T)=NULL;
}
//Câu b
int Empty_Tree(TTree T)
{
return T==NULL;
}
//Câu c
TTree Left_Child(TTree T)
{    
if (T!=NULL)
return T->left;
   else
return NULL;
}
//Câu d
TTree RightChild(TTree T)
 {   
if (T!=NULL)
return T->right;
    else
return NULL;
}
//Câu e
void LNR(TTree T)
{
if (LeftChild(T)=!NULL)
{
LNR(LeftChild(T));
}
     printf("%c ",T->Key);
     if(RightChild(T)!=NULL)
   {
LNR(RightChild(T));
   }
}
//Câu f
Tree Search(KeyType K,Tree T)
{
   if (T = = NULL)
return NULL;
    else if (T->Key == K)
          return T;
    else if (T->Key < K)
              return Search(K,T->right);   
     else
return Search(K,T->left);
 }
//Câu g
void DeleteNode(keyType X,Tree T)
{
if (T != NULL)
     if(X < T->Key)
DeleteNode(X,T->left)
     else if(x > T->Key)
DeleteNode(x,T->right)
else if(T->left==NULL)&&(T->right==NULL)
T=NULL;
     else if(T->left == NULL)
T = T->right
else if(T->right==NULL)
T = T->left
     else
T->Key=DeleteMin(T->right);
}
PHẦN B
Câu 1:
Class Teacher:public Person
{
   float Hesoluong;
   char Hocvi[15];
public:
   Teacher ();
   Teacher(char,char,char,char,float);
   friend istream& operator >>(istream& , Teacher &);
   float Tinhluong();
   int Phucap();
};
Teacher::Teacher():Person ()
{
   Hesoluong=0;
   strcpy(Hocvi,"");
}
Teacher::Teacher(char* s1,char* s2,char* s3,char* s4,float hs):Person(s1,s2,s3)
{
   Hesoluong=hs;
   strcpy(Hocvi,s4);
}
istream& operator >>(istream& is, Teacher& T)
{
   is>>*(Person*)&T;
   cout<<”Nhap he so luong :”; is.ignore();is>>T.Hesoluong;
   cout<<"Nhap hoc vi : ";is.ignore();is.getline(T.Hocvi,15);
   return is;
}
int Teacher::Phucap()
{
   if(Hocvi==”tiensi”)
      return 500;
   else if(Hocvi==”thacsi”)
      return 300;
   else if(Hocvi==”daihoc”)
      return 200;
}
float Teacher::Tinhluong()
{
   return (Hesoluong*830)/Phucap();
}
Câu 2
void main()
{
//Câu a:
   int i,n;
   cout<<"Nhap so giao vien trong danh sach : ";cin>>n;
   Teacher* T=new Teacher[n];
   for(i=0;i<n;i++)
   {
      cout<<"Nhap sinh vien thu "<<i+1<<" : ";
      cin>>T[i];
   }
//Câu b:
char* Hoten[30];
cout<<”Nhap ho ten can tim hoc vi :”;
cin>>Hoten;
for(i=0;i<n;i++)
   {
      if(T[i].hoten==Hoten)
         cout<<T[i].Hocvi;
}
}
Về Đầu Trang Go down
Admin
Administrotor
Administrotor
avatar

Tổng số bài gửi : 877
Join date : 24/07/2010

Bài gửiTiêu đề: Re: Bài giải đề thi môn CTDL & Giải Thuật   Sun Sep 25, 2011 4:27 pm

cảm ơn nha.các bạn cứ post lên bài giải có gì anh em cùng nhau sửa
Về Đầu Trang Go down
http://cntt08.forumvi.com
truyenITPro
Moderator
Moderator
avatar

Tổng số bài gửi : 153
Join date : 13/07/2011
Age : 30
Đến từ : Phú Hưng - Cái Nước - Cà Mau

Bài gửiTiêu đề: Re: Bài giải đề thi môn CTDL & Giải Thuật   Sun Sep 25, 2011 8:43 pm

Nick Stan là của Quốc Vương đó hả, hay bạn là ai, hay Quốc vương Share bài cho bạn post lên Yêu thế??
Về Đầu Trang Go down
Admin
Administrotor
Administrotor
avatar

Tổng số bài gửi : 877
Join date : 24/07/2010

Bài gửiTiêu đề: Re: Bài giải đề thi môn CTDL & Giải Thuật   Mon Sep 26, 2011 6:27 am

truyenITPro đã viết:
Nick Stan là của Quốc Vương đó hả, hay bạn là ai, hay Quốc vương Share bài cho bạn post lên Yêu thế??
Stan vào đây chia sẻ thông tin của bạn nha
http://cntt08.forumvi.com/t589-topic
Về Đầu Trang Go down
http://cntt08.forumvi.com
stan



Tổng số bài gửi : 3
Join date : 08/08/2011

Bài gửiTiêu đề: Re: Bài giải đề thi môn CTDL & Giải Thuật   Mon Sep 26, 2011 4:52 pm

Đúng, nick stan là của Vương.
Về Đầu Trang Go down
lptho42
Thành Viên chính thức
Thành Viên chính thức
avatar

Tổng số bài gửi : 48
Join date : 30/03/2011

Bài gửiTiêu đề: Re: Bài giải đề thi môn CTDL & Giải Thuật   Mon Sep 26, 2011 9:25 pm

Mình nghiên cứu hõm rài đấy. các bạn đống góp ý kiến nha.
ah mới chỉ có câu InsertEnd thôi.

Code:
// vidu.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<string>
#include<stdio.h>
#include<iostream>
#include<conio.h>

using namespace std;

#define Maxlength  30
typedef   int   Position;

typedef   struct
{
      int gt;      //Giải thưởng (Ví dụ giải 1, giải 2…)
      int soxo;   //Kết quả xổ số của giải thưởng đó
   }Ketqua;
typedef      Ketqua   ElementType;
typedef      struct
   {
      ElementType Element[Maxlength];
      Position Last;
   }List;

void Makenull(List *L)
{
   L->Last =0;
}
int First(List L)
{
   return 1;
}
int End(List L)
{
   return L.Last+1;
}
int Next(Position P,List L)
{
   return P+1;
}
ElementType Retrieve(Position P,List L)
{
   return L.Element[P-1];
}
int Full(List L)
{
   return L.Last==Maxlength;
}
int Empty(List L)
{
   return L.Last==0;
}
void InsertEnd(int giai, int so,List *L)
 {
    if (Empty(*L)==1)
    {
      L->Element[L->Last].gt=giai;
      L->Element[L->Last].soxo=so;
      L->Last++;   

    }
    else
       cout<<"Danh sach day";
}


void Xuat(List L)
 {
    Position P;
  for(P=First(L);P!=End(L);P=Next(P,L))
  {
         //printf("%d",L.Element[P-1]);
    printf("%d",Retrieve(P,L));
    getch();
  }
 
 }


void nhap(List *L)
{
   int giai,so;
   cout<<"Nhap ket qua ve so";
     for(int i=1;i<L->Last;i++)
      {
      InsertEnd(giai,so,L);
       }
}



int _tmain(int argc, _TCHAR* argv[])
{
   List L;
   Makenull(&L);
   nhap(&L);
   Xuat(L);
   getch();
   return 0;
}

Về Đầu Trang Go down
truyenITPro
Moderator
Moderator
avatar

Tổng số bài gửi : 153
Join date : 13/07/2011
Age : 30
Đến từ : Phú Hưng - Cái Nước - Cà Mau

Bài gửiTiêu đề: Re: Bài giải đề thi môn CTDL & Giải Thuật   Mon Sep 26, 2011 9:38 pm

nếu là Vương thì mình bấm nút Thanks 1 cái vì tinh thần chia sẻ, các bạn cũng nhớ bấm nút Thanks cho mình zí nhe Yêu thế..
Về Đầu Trang Go down
stan



Tổng số bài gửi : 3
Join date : 08/08/2011

Bài gửiTiêu đề: Re: Bài giải đề thi môn CTDL & Giải Thuật   Tue Sep 27, 2011 11:27 am

Trích dẫn :
gửi bởi lptho42
Code:
...
void InsertEnd(int giai, int so,List *L)
 {
    if (Empty(*L)==1)
    {
      L->Element[L->Last].gt=giai;
      L->Element[L->Last].soxo=so;
      L->Last++; 

    }
    else
      cout<<"Danh sach day";
}
...
Hàm Empty==0 khi trong mảng không có phần tử nào và =1 khi có ít nhất 1 phần tử, vậy hàm InsertEnd ở trên luôn báo là "danh sách đầy" vì hàm makenull lúc nào cũng được gọi trước.
Code:
void Makenull(List *L)
{
  L->Last =0;
}
Sao bạn không dùng hàm Full.
Về Đầu Trang Go down
devil
Moderator
Moderator
avatar

Tổng số bài gửi : 58
Join date : 07/08/2010
Đến từ : Cà Mau

Bài gửiTiêu đề: Re: Bài giải đề thi môn CTDL & Giải Thuật   Wed Sep 28, 2011 11:20 am

stan đã viết:
Trích dẫn :
gửi bởi lptho42
Code:
...
void InsertEnd(int giai, int so,List *L)
 {
    if (Empty(*L)==1)
    {
      L->Element[L->Last].gt=giai;
      L->Element[L->Last].soxo=so;
      L->Last++; 

    }
    else
      cout<<"Danh sach day";
}
...
Cho mình nói ý nghĩa của đoạn code của bạn thọ viết nhe.
Đầu tiên kiểm tra List có rỗng(empty) hay không.
Nếu rỗng(empty()=1) thì thêm vào...sau đó tăng last lên.Ngược lại không rỗng thì báo "Danh sach day".

Hàm Empty==0 khi trong mảng không có phần tử nào và =1 khi có ít nhất 1 phần tử, vậy hàm InsertEnd ở trên luôn báo là "danh sách đầy" vì hàm makenull lúc nào cũng được gọi trước.
Sao bạn không dùng hàm Full.

Mình cho ý kiến chút nhe.
Nói như bạn vương cũng không chính xác. Hàm empty()=0 khi mảng có từ 1 phần tử trở lên.ngược lại empty()=1 khi mảng mới khởi tạo (MakeNull),đồng nghĩa với vị trí last=0.
Code:

void MakeNull(List *L)
{
  L->Last=0;
}

int Empty(List L)
{
  return L.Last = = 0;
}
Vậy lúc này hàm InsertEnd ở trên sẽ thêm vào được chỉ 1 phần tử,và sau đó hàm báo là "danh sách đầy" cho đến hết.
Lý do là vì khi hàm trên thực hiên lần đầu tiên vị trí last tăng lên 1,đồng nghĩa lúc này danh sách không rỗng(not empty) nữa và last != 0.Tiếp đến bạn thêm phần tử thứ 2 vào thì lúc này hàm kiểm tra là mảng(list) không rỗng(not empty) trả về 0...và thực thi đoạn code này
Code:

 else
      cout<<"Danh sach day";
cho đến hết phần tử bạn nhập vào.
Về Đầu Trang Go down
rolex
Thành Viên chính thức
Thành Viên chính thức


Tổng số bài gửi : 22
Join date : 23/07/2011

Bài gửiTiêu đề: Re: Bài giải đề thi môn CTDL & Giải Thuật   Wed Oct 26, 2011 9:20 pm

Có bạn nào còn giữ cái đề hok ??? post lên luôn nha
Về Đầu Trang Go down
truyenITPro
Moderator
Moderator
avatar

Tổng số bài gửi : 153
Join date : 13/07/2011
Age : 30
Đến từ : Phú Hưng - Cái Nước - Cà Mau

Bài gửiTiêu đề: Re: Bài giải đề thi môn CTDL & Giải Thuật   Thu Oct 27, 2011 8:31 am

Rãnh thì chạy qua a e cho mượn phô tô, ai mà ngồi đánh máy, lâu lắm:D Cười bò
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Bài giải đề thi môn CTDL & Giải Thuật   

Về Đầu Trang Go down
 
Bài giải đề thi môn CTDL & Giải Thuật
Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
 :: Ôn Thi Tốt Nghiệp-
Chuyển đến