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

Chia sẻ: Nguyen Van Huan | Ngày: | Loại File: DOC | Số trang:7

Thêm vào BST

Báo xấu

200
lượt xem 34
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đâ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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề 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; } #endif b.Cài đặt void 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]; } #endif a2.Cài đặt
template void ChainHash:: Insert (const item & _data) { i = Hash(_data); ………………. } b. Vẽ hình Hàng 0 : 5 Hàng 1 : 31 -> 16 Hàng 2 : 12 -> 217 -> 42 Hàng 3 : Hàng 4 : 9 Câu 4 : a. Theo chiều rộng : A , B , C , G , D , F b. Theo chiều sâu : A , B , G , D , F , C Câu 5 : Giống bài thi Toán rời rạc vừa thi Chúc mọi người thi tốt