Widget Recent Comment No.

Home Document ĐỀ THI CẤU TRÚC DỮ LIỆU & GIẢI THUẬT ( Có đáp án)

ĐỀ THI CẤU TRÚC DỮ LIỆU & GIẢI THUẬT ( Có đáp án)




CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
                                /*DE SO 1*/
                          /*DUNG DANH SACH LIEN KET*/
Câu a.         Định nghĩa danh sách liên kết đơn dùng để quản lý danh sách các học sinh, với cấu trúc mỗi học sinh gồm có hai phần dữ liệu chính:
-         Họ tên học sinh, là một chuỗi không quá 80 ký tự.
-         Ngày tháng năm sinh của học sinh, theo cấu trúc dữ liệu thể hiện ngày DATE gồm có 3 trường ngày, tháng, và năm được định nghĩa riêng.
Câu b.         Viết hàm nhập vào một danh sách các học sinh từ bàn phím, với quá trình nhập kết thúc khi người dùng không nhập tên học sinh mới nữa. Danh sách học sinh này được lưu vào danh sách liên kết đã định nghĩa. Chú ý thêm: Chương trình không kiểm tra tính chính xác của ngày tháng năm sinh, và mặc định là dữ liệu nhập đúng.
Câu c.         Viết hàm sắp xếp danh sách học sinh theo thứ tự alphabet họ tên, và viết các hàm hỗ trợ thao tác khởi tạo danh sách rỗng, in danh sách học sinh hiện hành, cũng như hàm hủy toàn bộ học sinh.
Câu d. Sử dụng các hàm đã viết viết hàm main thực hiện việc nhập vào một danh sách học sinh từ bàn phím, in danh sách đó ra, sắp xếp các học sinh theo họ tên, và in lại danh sách đã sắp xếp ra màn hình. Cuối cùng huỷ danh sách học sinh và kết thúc chương trình.



#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>

struct date
{
       unsigned int ngay;
       unsigned int thang;
       unsigned int nam;      
};
typedef struct sv
{
        char hoten[80];
        struct date ngaysinh;       
}sv;

typedef struct nodesv
{
        sv info;
        struct nodesv *next;       
}nodesv;

typedef struct list
{
        nodesv *dau;
        nodesv *cuoi;
}list;
/*---------khai bao cac ham---------- */
void taolist(list &l);
nodesv *taosv();
void nhapsv(list &l);
void xuat(list l);
void huy(list &l);
void sapsep(list &l);
/*-------------------------------------*/
          
main()
{
      int a;
      list l;
      taolist(l);
      nodesv *p;
      for(;;)
      {
             printf("\n1nhap sinh vien");
             printf("\n2xuat sinh vien");
             printf("\n3.huy");
             printf("\n4.sap xep");
             printf("\n0.thoat");
             printf("\nnhap lua chon: ");
             scanf("%d",&a);
             switch(a)
             {
                               case 1:
                                    {
                                        
                                       nhapsv(l);
                                        break;      
                                    }
                               case 2:
                                    {
                                        xuat(l);
                                        break;   
                                    }
                               case 3:
                                    {
                                        huy(l);
                                        break;   
                                    }
                               case 4:
                                    {
                                        sapsep(l);
                                        xuat(l);
                                        break;   
                                    }
                               case 0: return 0;
                               default: break;
                                    
             }
             system("cls");                 
      }
      getch();    
}
void taolist(list &l)
{
     l.dau=NULL;
     l.cuoi=NULL;    
}


nodesv *taosv()
{
       nodesv *p;
       sv t;
       p=new nodesv;
       if(p==NULL) exit(1);
       printf("\nnhap ten sinh vien: ");fflush(stdin);
       gets(t.hoten);
       strcpy(p->info.hoten,t.hoten);
      
       printf("ngay sinh (dd mm yy): ");
       scanf("%d %d %d",&t.ngaysinh.ngay,&t.ngaysinh.thang,&t.ngaysinh.nam);
      
       p->info.ngaysinh.ngay=t.ngaysinh.ngay;
       p->info.ngaysinh.thang=t.ngaysinh.thang;    
       p->info.ngaysinh.nam=t.ngaysinh.nam;
      
       p->next=NULL;
      
       return p;           
}

void themdau(list &l,nodesv *p)
{
     if(l.dau==NULL)
     {
         l.dau=p;
         l.cuoi=l.dau;
     }
     else
     {
         p->next=l.dau;
         l.dau=p;   
     }   
}

void nhapsv(list &l)
{
     int a,i;
     nodesv *p;   
     printf("so sinh vien can nhap: ");
     scanf("%d",&a);
     for(i=0;i<a;i++)
     {
         printf("\nsinh vien thu %d",i+1);
      
         themdau(l,taosv());        
     }    
}

void xuat(list l)
{
     nodesv *p;
     p=l.dau;
     printf("\n+---------------------+-------------------+");
     printf("\n|TEN SINH VIEN        |   NGAY SINH       |");
     printf("\n+---------------------+-------------------+");
     while(p)
     {
printf("\n|%-20s |   %-2d-%-2d-%-4d      |",p->info.hoten,p->info.ngaysinh.ngay,p->info.ngaysinh.thang,p->info.ngaysinh.nam);
      p=p->next;
                
     }
     printf("\n+---------------------+-------------------+");  
     getch();
}

void huy(list &l)
{
    nodesv *p;
    while(l.dau!=NULL)
    {
                p=l.dau;
                l.dau=p->next;
                delete p;           
    }    
}

void sapsep(list &l)
{
     sv t;
     for (nodesv *p=l.dau;p!=NULL;p=p->next)
                     for (nodesv *q=p->next; q!= NULL;q=q->next)
                           if (stricmp(p->info.hoten,q->info.hoten)> 0)
                            {
                                  t = p->info;
                                  p->info = q->info;
                                  q->info = t;
                           }
}




                            /*DE 2*/
                            /*cay nhi phan tim kiem*/
Viết chương trình thực hiện các việc sau:
1.    Tạo cây nhị phân tìm kiếm
2.    Duyệt cây nhị phân tìm kiếm theo thứ tự giảm dần
Ví dụ: Nhập cây nhị phân tìm kiếm như sau:


 

 





Kết quả xuất ra màn hình là: 18   15         14      12      10      8        6        2
3.    Đếm số nút lá trên cây nhị phân tìm kiếm
4.    Xóa tất cả các node có giá trị là số nguyên tố trên cây

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

typedef struct node
{
    int key;
    struct node *trai;
    struct node *phai;       
}node;

typedef node *tree;
/*-------------khai bao cac ham------------*/
void taocay(tree &t);
int themnode(tree &t,int x);
void RNL(tree t);
void nhap(tree &t);

void huynode(tree &t,int x);
void thaythe(tree &p,tree &t);
int SNT(int x);
void huySNT(tree &t);
void demla(tree t,int &count);

/*------------------------------------------*/

main()
{
      int a,count=0;
      tree t;
      taocay(t);
      for(;;)
      {
             printf("\n1.nhap node");
             printf("\n2.xuat theo chieu giam dan");
             printf("\n3.huy cac so nguyen to trong cay");
             printf("\n4.dem la");
             printf("\n0.thoat");
             printf("\nnhap lua chon: ");
             scanf("%d",&a);
             switch(a)
             {
                               case 1:
                                    {
                                        nhap(t);  
                                        break;      
                                    }
                               case 2:
                                    {
                                        RNL(t);
                                        getch();
                                        break;   
                                    }
                               case 3:
                                    {
                                      huySNT(t);
                                      RNL(t);
                                      getch();
                                      break;   
                                    }
                               case 4:
                                    {
                                        demla(t,count);
                                        printf("\nso la cua cay la : %d",count);
                                        getch();
                                    }
                               case 0: return 0;
                               default: break;
                                   
             }
             system("cls");                 
      }
      getch();    
}

void taocay(tree &t)
{
     t=NULL;    
}

int themnode(tree &t,int x)
{
   if(t!=NULL)
   {
       if(t->key==x) return 0;
       if(t->key>x) return themnode(t->trai,x);
       else return themnode(t->phai,x);     
   }
   t=new node;
   if(t==NULL) return -1;
   t->key=x;
   t->trai=t->phai=NULL;
   return 1;
}

void RNL(tree t)
{
     if(t)
     {
          RNL(t->phai);
          printf("%4d",t->key);
          RNL(t->trai);    
     }    
}
void nhap(tree &t)
{
    int n,x;
    printf("so node can nhap: ");
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        printf("so thu %d: ",i+1);
        scanf("%d",&x);
        themnode(t,x);
    }    
}
int SNT(int x)
{
        int i;
        for(i=2;i<x;i++)
        {
              if(x%i==0) return 0;
        }
        return 1;
}

void huynode(tree &t,int x)
{
    if(t)
    {
        if(t->key<x) huynode(t->phai,x);
        else
        {
            if(t->key>x) huynode(t->trai,x);
            else
            {
                node *p;
                p=t;
                if(t->trai==NULL) t=t->phai;
                else
                {
                    if(t->phai==NULL) t=t->trai;
                    else thaythe(p,t->phai); //tim nho nhat ben nhanh phai  
                }
                delete p;       
            }    
        }
    
    }  
    else printf("\nkhong tim thay so can tim ");  
}

void thaythe(tree &p,tree &t)
{
     if(t->trai)
               thaythe(p,t->trai);
     else
     {
         p->key=t->key;
         p=t;
         t=t->phai;   
     }   
}

void huySNT(tree &t)
{
     if(t)
     {
          huySNT(t->trai);
          huySNT(t->phai);
          if(SNT(t->key)==1) huynode(t,t->key);
            
     }
}

void demla(tree t,int &count)
{
          if(t)
          {
               if(t->phai==NULL&&t->trai==NULL) count++;
               else
               {
               demla(t->trai,count);
               demla(t->phai,count);
               }
          }
}


























ĐỀ THI CẤU TRÚC DỮ LIỆU & GIẢI THUẬT ( Có đáp án) ĐỀ THI CẤU TRÚC DỮ LIỆU & GIẢI THUẬT ( Có đáp án) Reviewed by thanhtranminh on June 29, 2014 Rating: 5

Business

Powered by Blogger.