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:


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

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 đó.
A
D
C
E
F
B
7

2

2

9

3

6

4

4


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 A
n
B
n
(n>=0) hay không? A
C
E


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ô

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 <= P->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;


template <class item>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
//

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 <class item> 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 <assert.h>
typedef int keyType;

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 <class item> void ChainHash:: Insert (const item & _data)
Bản quyền tài liệu thuộc về diễn đàn