Đề thi cấu trúc dữ liệu và giải thuật có lời giải [P1]

Đề 1

Câu 1 : (2 điểm)

Thế nào là giải thuật; cấu trúc dữ liệu, mối quan hệ giữa chúng? Hãy nêu một vài cấu trúc dữ liệu tiền
định của ngôn ngữ lập trình mà anh (chị) biết?

Câu 2: (5 điểm )

Giả sử cần quản lý một lớp học bao gồm các sinh viên. Mỗi sinh viên gồm các thông tin sau:
Họ tên, Lớp, Số báo danh, Điểm trung bình. Anh (chị) hãy :

Viết dạng cài đặt danh sách này bằng cấu trúc danh sách liên kết đơn.
Với cấu trúc danh sách đã cài đặt, viết các chương trình con thực hiện các yêu cầu như sau:

a) Nhập vào danh sách gồm n sinh viên.

b) Loại bỏ khỏi danh sách những sinh viên có điểm trung bình < 5.

c) Sắp xếp danh sách theo trường lớp tăng dần.

d) In ra màn hình danh sách sinh viên theo từng lớp.

(n là một số nguyên dương tự nhập từ bàn phím)

Câu 3 : (1 điểm )

Anh (chị) hãy nêu ưu nhược điểm của cách cài đặt danh sách bởi danh sách liên kết đơn?

Bài làm :

Câu 1: (2 điểm)

Cấu trúc dữ liệu là cách tổ chức lưu giữ dữ liệu trong sao cho hiệu quả nhất.

Thuật toán là một phương pháp bao gồm một dãy các bước tính toán để giải quyết một bài toán. Thuật toán có thể được diễn tả dưới dạng ngôn ngữ tự nhiên hay ngôn ngữ lập trình.

Mỗi quan hệ : Thuật toán + Cấu trúc dữ liệu = Chương trình.

Cấu trúc dữ liệu tiền định của ngôn ngữ lập trình C là : int, char, float, double.

Câu 2: (5 điểm )

#include&ltstdio.h&gt
#include&ltstdlib.h&gt

typedef struct Item
{
 char Hoten[30],Lop[30],Sbd[30];

 float Dtb;
};

typedef struct Node
{
 Item Data;
 struct Node *Next;
}Node;

typedef Node* List;

void Insert_first(List *L,Item x);//Chèn phần tử vào đầu danh sách.

void Del_first(List *L,Item *x);//Xóa phần tử đầu danh sách

void Del_k(List *L,Item *x);//Xóa phần tử đầu danh sách

void Nhap_Ds(List *L,int n){
 int i=1;
 Item x;
while(i!= n){

printf("\nHo va ten sinh vien thu %d la :",i);

gets(x.Hoten);

fflush(stdin);

printf("\nSo bao danh sinh vien thu %d la :",i);

gets(x.Sbd);

fflush(stdin);

printf("\nLop sinh vien thu %d la :",i);

gets(x.Lop);

fflush(stdin);

printf("\nDiem trung binh sinh vien thu %d la :",i);

scanf("%f",&x.Dtb);
Insert_first(&L,x);
i++;
}
}

void Loai_Dtb(List *L)

{
  Node *P=L;
      while (P != NULL)

      {
        if (P->data->Dtb < 5) P-Next = P->Next->Next;
        p = P->Next;
       }
}

void sap_xep(List *L)

{
          Node *P=L; *Q, *Tg;
          while (P != NULL)
          {
            Q = P;
              while(Q != NULL)
              {
                   if(P->Data->Lop < Q->Data->Lop)
                    {

                       Tg = Q->Next;

                        Q->Next = P-Next;

                         P-Next = Tg;

                      }

                }

          }

}

void In_man_hinh(List L)

{
    Item x;

    Node *P=L;

     while(P != NULL)

      {

        Del_first(&L,&x);

        printf("\nHo Va Ten : %s",x.Hoten);

        printf("\tSo Bao Danh : %s",x.Sbd);

        printf("\tLop : %s",x.Lop);

        printf("\tDiem Trung Binh : %f",x.Dtb);
        }
}

Câu 3 : (1 điểm )

Ưu nhược điểm của danh sách liên kết đơn.

Ưu điểm :

Tận dụng được không gian bộ nhớ nhỏ để lưu trữ từng nút.
Việc thêm, xóa phần tử trong danh sách liên kết là dễ dàng, chỉ cần thay đổi mối liên
kết của các phần tử với nhau.

Nhược điểm :

Mật độ sử dụng bộ nhớ của danh sách liên kết không tối ưu tuyệt đối (<100%)
Việc truy xuất và tìm kiếm các phần tử trong danh sách liên kết mất nhiều thời gian
vì phải duyệt tuần tự qua các phần tử trong danh sách.
Bộ nhớ cần nhiều vì phải lưu thêm phần tử liên kết, nếu vùng dữ liệu là lớn thì tỷ
lệ mức sử dụng bộ nhớ là cao.

Jundat95

Header Ads

Đề thi cấu trúc dữ liệu và giải thuật có lời giải [P1]