Đề Thi Cấu Trúc Dữ Liệu 1 DH9TH

UBND TỈNH AN GIANG
TRƯỜNG ĐẠI HỌC AN GIANG
-------------------- CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc
----------------------
ĐỀ THI KẾT THÚC HỌC PHẦN
Môn: CẤU TRÚC DỮ LIỆU 1
Mã số học phần: COS304 Lớp: DH9TH
Thời gian làm bài: 90 phút
Hình thức thi: Viết
Ngày thi: 22/12/2009
Câu 1 (3 điểm)
Hãy trình bày ý tưởng giải thuật của phương pháp sắp xếp nổi bọt (Bubble Sort) áp dụng cho mảng các số nguyên, kết quả là một dãy có thứ tự tăng dần.
Minh họa giải thuật này thông qua việc thực hiện sắp xếp dãy số sau:
77 33 99 11 44 55 88 22
Viết hàm thực hiện sắp xếp tăng dần một mảng các phần tử số nguyên theo phương pháp nổi bọt.
Câu 2 (7 điểm)
Sử dụng danh sách liên kết (cài đặt bằng con trỏ) để viết chương trình quản lý đa thức, trong đó mõi phần tử danh sách là một cấu trúc (struct) có 2 trường Hangtu và trường Next trỏ đến phần tử kế tiếp. Cách lưu trữ đảm bảo thứ tự giảm dần theo số mũ của từng hạng tử của từng đa thức.

Giả sử có các khai báo và các hàm đã được cài đặt hoàn chỉnh:
typedef struct Hangtu {
int heso;
int somu;
};
typedef Hangtu Elementtype;
typedef struct Node
{
Elementtype Emlement;
Node * Next;
};
typedef Node *PtrToNode;
typedef PtrToNode Position;
typedef PtrToNode List;
void Makenull_List(List L); //Tạo danh sách rỗng
int IsEmptry_List(List L); // Kiểm Tra danh sách rỗng
int IsLast (Position P, List L); //Hàm Trả về vị trí cuối danh sách.
Position Locate (ElementType X, List L);
// Locate trả ve vi tri dau tien trong danh sách co chua X
void Delete_List (ElementType x, List L); //xóa tại vị trí p
Position LocatePrevious (ElementType X, List L);
void Insert_List (Element X, List L, Position P);
//Insert_List Chèn X vào danh sách tại vi trí p
Position Header (List L); // Trả về vị trí đầu tiên trong danh sách
ElementType Retrieve (Position P);// Giá trị tại vị trí p
Sử dụng các hàm trên để cài dặt thêm các hàm thực hiện yêu cầu:
- Nhập vào 2 đa thức L1,L2.
- In ra 2 đa thức danh sách vừa nhập.
- Sắp xếp 2 đa thức giảm dần theo số mũ.
- Cộng 2 đa thức L1,L2; Kết quả là đa thức L3.
- Nhân 2 đa thức L1, L2; Kết quả là đa thức L4.
Anh (chị) hãy khai báo bổ sung các biến cần thiết và sử dụng các hàm đã cài đặt để viết chương trình chính để minh họa thực hiện những chức năng ở trên.

BÀI LÀM
(Lê Nguyên Đức)
Câu 1:
- Ý tưởng giải thuật của thuật toán sắp xếp nổi bọt (Bubble Sort) áp dụng cho mảng các số nguyên kết quả mảng có thứ tự tăng dần:
Xuất phát từ cuối dãy, xét các cặp phần tử kế cận để đưa phần tử nhỏ hơn dần dần di chuyển về đầu dãy và đúng vị trí. Sau đó không xét nó nữa ở các bước sau vì vậy ở lần xử lý thứ i thì phần tử đầu dãy là phần tử thứ i.
Quá trình sắp xếp phần tử nào có giá trị nhỏ sẽ được đưa về đầu dãy.
- Minh họa cho dãy thuật Bubble Sort qua dãy số: 77 33 99 11 44 55 88 22:
Lần xử lí thứ 1:
i=1.
j=7.
77 33 99 11 44 55 22 88
j=6.
77 33 99 11 44 22 55 88
j=5.
77 33 99 11 22 44 55 88
j=4.
77 33 99 11 22 44 55 88
j=3.
77 33 11 99 22 44 55 88
j=2.
77 11 33 99 22 44 55 88

j=1.
11 77 33 99 22 44 55 88

Lần xử lí thứ 2:
i=2.
j=7.
11 77 33 99 22 44 55 88
j=6.
11 77 33 99 22 44 55 88
j=5.
11 77 33 99 22 44 55 88
j=4.
11 77 33 22 99 44 55 88
j=3.
11 77 22 33 99 44 55 88
j=2.
11 33 77 22 99 44 55 88
Qua 2 lần xử lí đã đưa được 2 phần tử về đúng vị trí 11 và 33 thực hiện 4 lần tương tự ta được dãy sắp xếp tăng dần là: 11 22 33 44 55 77 88.
- Hàm BubbleSort:
void BubbleSort (int mang[],int n)
{
for(int i=1;i<n;i++)
for (int j=n; j>i; j--)
{
if (mang[j]<mang[j-1])
{
int xtam;
xtam = mang[j];
mang[j]=mang[j-1];
mang[j-1]=xtam;
}
}
}

 
Câu 2:
// Hàm nhập da thức.
void Nhap(List L)
{ printf(“Nhap 0 0 de ngung nhap”);
Position P;
P=Header(L);
do
{
int heso, somu;
printf(“Nhap vao he so va so mu: ”);
scanf(“%d%d”,&heso,&somu);
if (heso==somu==0) break;
else
{
List ListNode= new Node;
ListNode->Element.Heso=heso;
ListNode->Element.Somu=somu;
ListNode->Next=P->Next;
P->Next=ListNode;
P=ListNode;
}

}


}
void Xuat (List L)
{
Position P;
P=Header(L);
if(P->Next==NULL) printf(“Da Thuc Rong”);
else
while(P->Next!=NULL)
{
P=P->Next;
if(P->Element.Heso>0)
{ printf(“ + ”);
printf(“%d^%d”,P->Element.Heso,P->Element.Somu);
}
else printf(“%d^%d”,P->Element.Heso,P->Element.Somu);
}
}
 
void Sapxep(List L)
{ // Phương pháp chèn trực tiếp
Position P;
P=Header(L);
List ListNode;
while(!IsLast(L))
{
P=P->Next;
Element tam;// luu gia tri nut dang xet
tam.Heso=P->Element.Heso;
tam.Somu=P->Element.Somu;
Position Pchay=LocatePrevious (P->Element,L);
While(P->Element.Somu<Pchay.Element.SoMu)
Pchay=LocatePrevious(Pchay->Element,L);
Insert_List(tam, L, Pchay);
Delete_List(P->Element,L);

}
}
void CongDaThuc(List L1, List L2, List L3)
{
Sapxep(L1);
Sapxep(L2);
Position P1,P2,P3;
P1=Frist(L1);
P2=Frist(L2);
P3=Header(L3)->Next;
while(!IsLast(L1)&&!IsLast(L2))
{
List ListNode=new Node;
if (P1!=NULL&&P2!=NULL)
{
ListNode.Heso=P1->Element.Heso+P2->Element.Heso;
ListNode.Somu=P1->Element.Somu;
}
else if (P1==NULL)
{
ListNode.Heso=P2->Element.Heso;
ListNode.Somu=P2->Element.Somu;
}
else
{
ListNode.Heso=P2->Element.Heso;
ListNode.Somu=P2->Element.Somu;
}
InSert_List(ListNode.Element,L3, P3);
P1=P1->Next;
P2=P2->Next;
}
}
void NhanDaThuc(List L1, List L2, List L4)
{
Sapxep(L1);
Sapxep(L2);
Position P1,P2,P4;
P1=Frist(L1);
P2=Frist(L2);
P3=Header(L4)->Next;
while(P1!=NULL)
{
while(P2!=NULL)
{
ElementType ketqua;
ketqua.Element=
}
}
}