Đề thi cơ sở dữ liệu và giải thuật 4

Đây là Đề thi cơ sở dữ liệu và giải thuật gửi đến các bạn sinh viên tham khảo.
Nội dung trích xuất từ tài liệu:
Đề thi cơ sở dữ liệu và giải thuật 4 Đề 4 (K46)Câu1 . a.Đặc tả //DL.h // Giải thích về lớp #ifndef _DL_H_ #define _DL_H_ #include class node { int data; node * next; node(int x) { data = x; next = NULL; }; } class DL { public : DL() // Khởi tạo danh sách rỗng // Precondition // Postcondition {Head = NULL ; Tail = NULL; length = 0}; DL(const DL & _dl); // Hàm kiến tạo copy // // ~ DL(); // Hàm hủy // // DL& operator = (const DL & _dl); // Toán tử gán // // bool Empty() const ; // Xác định xem danh sách có rỗng kô // Precondition : // Postcondition: Trả về true nếu danh sách rỗng int Length() const; // bool IsExist(int x); // Kiểm tra xem danh sách có chứa số nguyên x kô // Precondition : danh sách khác rỗng // Postcondition : trả về true……. void Insert(int x); // // // friend DL& KetHop(const DL& dl1 , const DL& dl2); // // // private : node * Head; node * Tail; int length;}#endifb.Cài đặtvoid DL :: Insert (int x){ node * Q = new node(x); if (Empty()) { Head = Q ; Tail = Q; length = 1; } node * Pre , P ; Pre = P = Head; While (Pre != Tail) { if ( x data ) break; Pre = P; P = P->next; } if (P == Head) // Chèn vào đầu { Q -> next = Head; Head = Q; } else if (P == NULL) // Chèn vào cuối { Pre ->next = Q; } else //Chèn vào giữa { Q ->next = P; Pre ->next = Q; } }Câu 2 a.Mô tả //HUT.h // Giải thích về lớp #ifndef _ HUT _H_ #define _ HUT _H_ #include template class node { item data; int key; node(const & item _data , const int & _key) { data = _data ; key = _key; }; friend class HUT; }template class HUT{ public : static const int SIZE = 1000; HUT() // Khởi tạo danh sách rỗng // Precondition // Postcondition HUT (const HUT & _dl); // Hàm kiến tạo copy // // HUT (node * _element , int n) // Xây dựng hàng ưu tiên từ n phần từ lưu trong mảng _element ~ HUT (); // Hàm hủy // // HUT & operator = (const HUT & _dl); // Toán tử gán // // bool Empty() const ; // Xác định xem danh sách có rỗng kô // Precondition : // Postcondition: Trả về true nếu danh sách rỗng int Length() const; // void Insert(node _data); // // // node & FindMin() const; // // // node & DeleteMin(); // Loại đối tượng có độ ưu tiên nhỏ nhất // // Trả về đối tượng có độ ưu tiên nhỏ nhất private : node element[SIZE]; int last; void ShiftDown(int i); // Đẩy dữ liệu trong đỉnh i xuống vị trí thích hợp // // } #endif b.Cài đặt template node& HUT :: DeleteMin() { assert(last >= 0); element[0] = element[last]; ShiftDown(0); }Câu 3 a1.Mô tả //ChainHash.h // Giải thích về lớp #ifndef _ ChainHash _H_ #define _ ChainHash _H_ #include typedef int keyType; template class ChainHash { public : static const int SIZE = 1000; ChainHash () // Khởi tạo danh sách rỗng // Precondition // Postcondition ChainHash (const ChainHash & _dl); // Hàm kiến tạo copy // // ~ ChainHash (); // Hàm hủy // // ChainHash & operator = (const ChainHash & _dl); // Toán tử gán // // bool Search(keyType k , Item & I) const; // // // void Insert(const item & _data); // // // void & Delete (keyType k); // Loại đối tượng có độ ưu tiên nhỏ nhất // // Trả về đối tượng có độ ưu tiên nhỏ nhất private : struct CELL { item data; CELL * next; } CELL element[SIZE];}#endifa2.Cài đặt template void ChainHash:: Inse ...