Bn quyn tài liu thuc v din àn http://sinhviennganhang.com
 THI 1
MÔN CU TRÚC D LIU VÀ GII THUT
Thi gian: 120 phút
Câu 1. Cho danh sách sinh viên. Mi sinh viên c mô t bi các thuc tính h tên, tui, gii
tính.
1. Hãy cài t danh sách sinh viên bi danh sách liên kt.
2. Hãy vit th tc loi khi danh sách tt c các sinh viên n.
Câu 2. Cho danh sách các s nguyên c sp xp theo th t không gim vi danh sách c
cài t bi mng:
1. Hãy khai báo CTDL biu din dánh sách ó.
2. Hãy vit th tc xem vào sanh sách mt s nguyên mi n sao cho danh sách nhn c
vn còn c sp theo th t không gim.
Câu 3. Mt mng rng gm 11 ô c ánh s t 0 ên 10 dùng  lu tr các s nguyên. Các s
nguyên k c a vào mng bi hàm bm:
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 mng.
Gii thích ti sao chúng li c a vào nhng v trí ó trong mng.
Câu 4. Cho  th nh hng sau:
i qua  th xut phát t !nh 1.
1. Hãy a ra rng các cây to thành khi i qua  th theo b" rng và danh sách các !nh
theo th t ã i qua.
2. Hãy a ra rng các cây to 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
Bn quyn tài liu thuc v din àn http://sinhviennganhang.com
 THI 2
MÔN CU TRÚC D LIU VÀ GII THUT
Thi gian: 120 phút
Câu 1. (2 im) Khoa Công ngh# c biu din bi danh sách các lp. Mi lp c biu din
bi tên lp và danh sách sinh viên ca lp. Mi sinh viên c biu din bi tên, nm sinh, gii
tính. Danh sách các lp c cài t bi danh sách liên kt.
Hãy khai báo CTDL biu din Khoa Công ngh#, Cho biu din hình hc CTDL này.
Câu 2. ( 2,5 im) Cho 2 danh sách các s nguyên c cài t bi danh sách liên kt. Ta c$n kt
hp 2 danh sách thành mt danh sách b%ng cách nôi uôi danh sách th nht ti $u danh sách
thw hai. Ví d, t 2 danh sách L1 và L 2, sau khi ni ta c L nh sau:
a) Khai báo CTDL biu din danh sách liên kt
b) T 2 danh sách liên kt ( có th rng), hãy vit hàm kt ni 2 danh sách thành mt danh sách.
Câu 3. (2,5 im) Các giá tr khóa ca cây tìm kim nh phân là s nguyên.
Cho dãy các s nguyên: 5, 1, 6, 8, 4, 9, 7
a) Áp dng th tc xen vào cây bt $u t cây rng, hãy xây dng cây tìm kim nh phân,
b%ng cách xem vào các !nh mi có khóa l$n lt là 5, 1, 6, 8, 4, 9, 7
b) T cây ã xây dng, hãy da ra dãy các khóa theo các th t: trc, trung và sau.
Câu 4. (2 im)
Mi ngi có giá tr u tiên là s nguyên. Mi ngi c biu din bi tên, và gi tr u
tiên. Hàng u tiên c lu trong mng theo th t gim d$n ca giá tr u tiên. Ch&ng hn, An
có GT'T là 5, Ba và Lan có GT'T là 2 và 4 c lu trong mng sau:
0 1 2 Max-1
a) Khai báo CTDL cài a(t hàng u tiên bi mng nh trên
b) Vit hàm loi ngi có giá tr u tiên nh nht.
Câu 5. (1 im)
Áp dng thut toán sp xp ni bt cho mng sau
Yêu c$u: a ra kt qu ca tng bc
7
5
9
4
3
7
5
9
4
3
L1
L2
An Lan Ba
5 4 2
9 4 7 1 3
Bn quyn tài liu thuc v din àn http://sinhviennganhang.com
 THI 3
MÔN CU TRÚC D LIU VÀ GII THUT
Thi gian: 120 phút
Câu 1. Cho danh sách tên ca mi lp. Mi sinh viên c biu din bi 2 trng: ten, diem.
Danh sách c cài t bi danh sách liên kt.
1. Hãy khai báo CTDL cài t danh sách ó.
2. Vit th tc tính im trung bình ca lp ó.
3. Vit th tc loi khi danh sách tt c sinh viên có im b%ng p cho trc.
Câu 2. Cho mt cây, mi !nh có ti a K !nh con. Thông tin cha trong mi !nh là s thc.
Cây c cài t cách ch! ra danh sách các con ca mi !nh và s) dng con tr.
1. Khai báo CTDL cài t cây b%ng cách trên.
2. Vit th tc i qua cây theo  sâu ( # quy hoc không # quy)  tính tng các s thc
lu trong các !nh ca cây.
Câu 3. Cho bng bm óng gm 11 thành ph$n. Các giá tr khóa là các s nguyên và c a
vào bng bi hàm bm: h(x) = x%11. Va chm c gii quyt b%ng cách bm li bình phơng.
T bng bm rng, s) dng ti a 3 l$n b li, hãy a ra bng bm kt qu khi thc hi#n các
hành ng sau:
1. Xen vào 5099, 23,, 213, ,36, 300, 19, 283.
2. Loi 300, 36 ri xen vào 146, 360, 480.
Yêu c$u: c$n gii thích ti sao nhn c kt qu nh th.
Câu 4. Trình bày t tng ca thut toán PRIM tìm cây bao trùm ngn nht ca  th vô hng
liên thông có trng s. Mô t thut toán này.
Áp dung thut toán  tìm cây bao trùm ngn nht c  th sau
Yêu c$u: C$n phi tìm ra kt qu ca mi bc và gii thích.
A
D
C
E
F
B
7
2
2
9
3
6
4
4
6
1
Bn quyn tài liu thuc v din àn http://sinhviennganhang.com
 THI 4
CTDL VÀ GII THUT
Cho K46CA, CB,CC
(Thi gian: 120 phút)
Câu 1. (3 im) Kiu d li#u tru tng c xác nh nh sau:
• Các i tng DL là các danh sách s nguyên c sp xp theo th t không
gim.
• Các phép toán gm:
1. Tìm xem danh sách có cha s nguyên cho trc không?
2. Xen mt s nguyên mi vào danh sách sao cho sau khi xen, danh sách vn còn c sp
3. Kt hp 2 danh sách c sp thành mt danh sách c sp.
Danh sách c cài t b%ng danh sách liên kt.
a) Hãy vit file $u cha mô t CTDL và các prototype ca các hàm thc hi#n các
phép toán trên (Vi mi hàm c$n vit 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 im) 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 bi cây tìm kim nh phân vi khóa tìm kim là giá tr u tiên.
a) Hãy mô t CTDL biu din hangf u tiên trong cáhc cài t trên
b) Hãy vit hàm loi i tong có giái tr u tiên nh nht khi hàng u tiên.
Câu 3. (2,5 im)
a) Hãy mô t CTDL biu din bng bm dây chuy"n và vit hàm xem vào
bng bm này theo hàm bm ã cho.
b) Gi s) c ca bng là 5, các giá tr khóa là các s nguyên không âm. Và
hàm bm là hàm chua ly ph$n s. Áp dng hàm xen vào, t b&ng bm
day chuy"n rng, hãy â vào các d+ li#u vi khóa 9,12,31,217,5.42,16.
Cho biu din hình hc bng bm kt qu.
Câu 4. (1,5 im)
a) Hãy trình bày t tng cu thut toán i qua  th theo b" rng 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 thm theo b" rng và  sâu khi xut phát t
!nh A.
Câu 5. (1 im) Gi s) các xâu c to thành t 2 lý t A vàB. S) dng ccs phép toán ngn
xp, hãy vit hàm cho bit mt xâu có dng A
n
B
n
(n>=0) hay không?
A
C
E
B
D
H
G
F
Bn quyn tài liu thuc v din àn http://sinhviennganhang.com
" 4 (K46)
Câu1 .
a.c t
//DL.h
// Gii thích v" lp
#ifndef _DL_H_
#define _DL_H_
#include <assert.h>
class node
{
int data;
node * next;
node(int x)
{
data = x; next = NULL;
};
}
class DL
{
public :
DL()
// Khi to danh sách rng
// Precondition
// Postcondition
{Head = NULL ; Tail = NULL; length = 0};
DL(const DL & _dl);
// Hàm kin to copy
//
//
~ DL();
// Hàm hy
//
//
DL& operator = (const DL & _dl);
// Toán t) gán
//
//