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

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;
}

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;
}
}

// 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;
}

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

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

int Empty(List L)
{
  return L.Last = = 0;
}

 else
      cout<<"Danh sach day";