Đề thi môn cấu trúc dữ liệu và giải thuật

Bản quyền tài liệu thuộc về diễn đàn ĐỀ THI 1 MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Thời gian: 120 phút Câu 1. Cho danh sách sinh viên. Mỗi sinh viên được mô tả bởi các thuộc tính họ tên, tuổi, giới tính. 1. Hãy cài đặt danh sách sinh viên bởi danh sách liên kết. 2. Hãy viết thủ tục loại khỏi danh sách tất cả các sinh viên nữ. Câu 2. Cho danh sách các số nguyên được sắp xếp theo thứ tự không giảm với danh sách được cài đặt bởi mảng: 1. Hãy khai báo CTDL biểu diễn dánh sách đó. 2. Hãy viết thủ tục xem vào sanh sách một số nguyên mới n sao cho danh sách nhận được vẫn còn được sắp theo thứ tự không giảm. Câu 3. Một mảng rỗng gồm 11 ô được đánh số từ 0 đên 10 dùng để lưu trữ các số nguyên. Các số nguyên k được đưa vào mảng bởi hàm băm: h(k) = (k – 3*i)%11 (i = 0,1,…) Hãy đưa các dãy số nguyên 15, 20, 6, 9, 17 vào mảng. Giải thích tại sao chúng lại được đưa vào những vị trí đó trong mảng. Câu 4. Cho đồ thị định hướng sau: Đi qua đồ thị xuất phát từ đỉnh 1. 1. Hãy đưa ra rừng các cây tạo thành khi đi qua đồ thị theo bề rộng và danh sách các đỉnh theo thứ tự đã đi qua. 2. Hãy đưa ra rừng các cây tạo thành khi đi qua đồ thị theo bề sâu và danh sách các đỉnh theo thứ tự đã đi qua. 2 3 4 5 6 7 1 Bản quyền tài liệu thuộc về diễn đàn ĐỀ THI 2 MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Thời gian: 120 phút Câu 1. (2 điểm) Khoa Công nghệ được biểu diễn bởi danh sách các lớp. Mỗi lớp được biểu diễn bởi tên lớp và danh sách sinh viên của lớp. Mỗi sinh viên được biểu diễn bởi tên, năm sinh, giới tính. Danh sách các lớp được cài đặt bởi danh sách liên kết. Hãy khai báo CTDL biểu diễn Khoa Công nghệ, Cho biểu diễn hình học CTDL này. Câu 2. ( 2,5 điểm) Cho 2 danh sách các số nguyên được cài đặt bởi danh sách liên kết. Ta cần kết hợp 2 danh sách thành một danh sách bằng cách nôi đuôi danh sách thứ nhất tới đầu danh sách thw hai. Ví dụ, từ 2 danh sách L1 và L 2, sau khi nối ta được L như sau: a) Khai báo CTDL biểu diễn danh sách liên kết b) Từ 2 danh sách liên kết ( có thể rỗng), hãy viết hàm kết nối 2 danh sách thành một danh sách. Câu 3. (2,5 điểm) Các giá trị khóa của cây tìm kiếm nhị phân là số nguyên. Cho dãy các số nguyên: 5, 1, 6, 8, 4, 9, 7 a) Áp dụng thủ tục xen vào cây bắt đầu từ cây rỗng, hãy xây dựng cây tìm kiếm nhị phân, bằng cách xem vào các đỉnh mới có khóa lần lượt là 5, 1, 6, 8, 4, 9, 7 b) Từ cây đã xây dựng, hãy dưa ra dãy các khóa theo các thứ tự: trước, trung và sau. Câu 4. (2 điểm) Mỗi người có giá trị ưu tiên là số nguyên. Mỗi người được biểu diễn bởi tên, và giả trị ưu tiên. Hàng ưu tiên được lưu trong mảng theo thứ tự giảm dần của giá trị ưu tiên. Chẳng hạn, An có GTƯT là 5, Ba và Lan có GTƯT là 2 và 4 được lưu trong mảng sau: 0 1 2 Max-1 a) Khai báo CTDL cài đaẹt hàng ưu tiên bởi mảng như trên b) Viết hàm loại người có giá trị ưu tiên nhỏ nhất. Câu 5. (1 điểm) Áp dụng thuật toán sắp xếp nổi bọt cho mảng sau Yêu cầu: Đưa ra kết quả của từng bước 7 5 9 4 3 7 5 9 4 3 L1 L2 L An Lan Ba 5 4 2 9 4 7 1 3 Bản quyền tài liệu thuộc về diễn đàn ĐỀ THI 3 MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Thời gian: 120 phút Câu 1. Cho danh sách tên của mỗi lớp. Mỗi sinh viên được biểu diễn bởi 2 trường: ten, diem. Danh sách được cài đặt bởi danh sách liên kết. 1. Hãy khai báo CTDL cài đặt danh sách đó. 2. Viết thủ tục tính điểm trung bình của lớp đó. 3. Viết thủ tục loại khỏi danh sách tất cả sinh viên có điểm bằng p cho trước. Câu 2. Cho một cây, mỗi đỉnh có tối đa K đỉnh con. Thông tin chứa trong mỗi đỉnh là số thực. Cây được cài đặt cách chỉ ra danh sách các con của mỗi đỉnh và sử dụng con trỏ. 1. Khai báo CTDL cài đặt cây bằng cách trên. 2. Viết thủ tục đi qua cây theo độ sâu ( đệ quy hoặc không đệ quy) để tính tổng các số thực lưu trong các đỉnh của cây. Câu 3. Cho bảng băm đóng gồm 11 thành phần. Các giá trị khóa là các số nguyên và được đưa vào bảng bởi hàm băm: h(x) = x%11. Va chạm được giải quyết bằng cách băm lại bình phương. Từ bảng băm rỗng, sử dụng tồi đa 3 lần bă lại, hãy đưa ra bảng băm kết quả khi thực hiện các hành động sau: 1. Xen vào 5099, 23,, 213, ,36, 300, 19, 283. 2. Loại 300, 36 rồi xen vào 146, 360, 480. Yêu cầu: cần giải thích tại sao nhận được kết quả như thế. Câu 4. Trình bày tư tưởng của thuật toán PRIM tìm cây bao trùm ngắn nhất của đồ thị vô hướng liên thông có trọng số. Mô tả thuật toán này. Áp dung thuật toán để tìm cây bao trùm ngắn nhất củ đồ thị sau Yêu cầu: Cần phải tìm ra kết quả của mỗi bước và giải thích. A DC EF B 7 2 2 9 3 6 4 4 6 1 Bản quyền tài liệu thuộc về diễn đàn ĐỀ THI 4 CTDL VÀ GIẢI THUẬT Cho K46CA, CB,CC (Thời gian: 120 phút) Câu 1. (3 điểm) Kiểu dữ liệu trừu tượng được xác định như sau: • Các đối tượng DL là các danh sách số nguyên được sắp xếp theo thứ tự không giảm. • Các phép toán gồm: 1. Tìm xem danh sách có chứa số nguyên cho trước không? 2. Xen một số nguyên mới vào danh sách sao cho sau khi xen, danh sách vẫn còn được sắp 3. Kết hợp 2 danh sách được sắp thành một danh sách được sắp. Danh sách được cài đặt bằng danh sách liên kết. a) Hãy viết file đầu chứa mô tả CTDL và các prototype của các hàm thực hiện các phép toán trên (Với mỗi hàm cần viết ra các điều kiện trước và điều kiện sau) b) Hãy cài đặt hàm xen vào. Câu 2. (2 điểm) Giả sử các đối tượng khác nhau có giá trị ưu tiên khác nhau và hàng ưu tiên được cài đặt bởi cây tìm kiếm nhị phân với khóa tìm kiếm là giá trị ưu tiên. a) Hãy mô tả CTDL biểu diễn hangf ưu tiên trong cáhc cài đặt trên b) Hãy viết hàm loại đối tựong có giái trị ưu tiên nhỏ nhất khỏi hàng ưu tiên. Câu 3. (2,5 điểm) a) Hãy mô tả CTDL biểu diễn bảng băm dây chuyền và viết hàm xem vào bảng băm này theo hàm băm đã cho. b) Giả sử cớ của bảng là 5, các giá trị khóa là các số nguyên không âm. Và hàm băm là hàm chua lấy phần sư. Áp dụng hàm xen vào, từ bẳng băm day chuyền rỗng, hãy đâ vào các dẽ liệu với khóa 9,12,31,217,5.42,16. Cho biểu diễn hình học bảng băm kết quả. Câu 4. (1,5 điểm) a) Hãy trình bày tư tưởng cảu thuật toán đi qua đồ thị theo bề rộng và theo độ sâu. b) Cho đồ thị định hướng trong hình vẽ sau: c) Hãy đưa ra thứ tự các đỉnh được thưm theo bề rộng và độ sâu khi xuất phát từ đỉnh A. Câu 5. (1 điểm) Giả sử các xâu được tạo thành từ 2 lý tự A vàB. Sử dụng ccs phép toán ngăn xếp, hãy viết hàm cho biết một xâu có dạng AnBn (n>=0) hay không? A C E B D H G F Bản quyền tài liệu thuộc về diễn đàn Đề 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 // // Bản quyền tài liệu thuộc về diễn đà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) Bản quyền tài liệu thuộc về diễn đàn { 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 Bản quyền tài liệu thuộc về diễn đàn { 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(); Bản quyền tài liệu thuộc về diễn đàn // 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 Bản quyền tài liệu thuộc về diễn đàn // 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) Bản quyền tài liệu thuộc về diễn đàn { 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