ĐỀ CƯƠNG ÔN TẬP HỌC PHẦN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
A. Đề:
Câu 1
a) Ngăn xếp là gì? Trình bày cách tổ chức ngăn xếp bằng mảng, danh sách
liên kết đơn?
b) Viết phép toán đẩy một phần tử vào ngăn xếp (Push), lấy ra (Pop) cho một
ngăn xếp được tổ chức dạng mảng, danh sách liên kết đơn, cho ví dụ minh họa?
Câu 2
Cho các xâu ký tự có dạng w $ w’, trong đó w’ là đảo ngược của xâu w,
chẳng hạn nếu w = a c d b thì w’ = b d c a. Hãy thiết kế thuật toán để đoán
nhậncác xâu ký tự trên và cho ví dụ mô phỏng?
Câu 3
Trình bày ý tưởng cho thuật toán sắp xếp chọn trực tiếp (selection sort). Theo
thuật toán này, anh/chị hãy viết hàm sắp xếp n số nguyên theo chiều tăng dần, cho
ví dụ minh họa các bước thực hiện.
Câu 4
a) Danh sách liên kết đơn là gì? Trình bày cách tổ chức.
b) Viết các phép toán bổ sung một phần tử và lấy ra một phần tử trong một
danh sách liên kết đơn, cho ví dụ minh họa.
Câu 5
Cho dãy A gồm n phần tử nguyên a 1, a2, ..., an (các phần tử khác nhau). Hãy xây
dựng thuật toán tìm phần tử lớn thứ k trong dãy A theo các bước sau đây:
1. Biểu diễn cấu trúc dữ liệu;
2. Mô tả thuật toán;
3. Ví dụ mô phỏng.
Câu 6
a) Trình bày cấu trúc dữ liệu danh sách được tổ chức dưới dạng mảng.
b) Viết phép toán bổ sung một phần tử trong một danh sách được tổ chức dạng
mảng, cho ví dụ minh họa.

1

Ví dụ mô phỏng.

Câu 12
a) Trình bày cấu trúc dữ liệu danh sách liên kết vòng hai chiều.
b) Viết các phép toán bổ sung một phần tử trong một danh sách liên kết vòng
hai chiều, cho ví dụ minh họa.

2


Câu13
Xâu kí tự được gọi là xâu chuẩn nếu thứ tự xuất hiện của các dấu đóng/mở
ngoặc tuân thủ theo nguyên tắc đóng mở của biểu thức toán học.
Ví dụ:

(()()); ()((()())()) : là các xâu chuẩn.
()); (()()))(()

: là các xâu không chuẩn.

Hãy thiết kế thuật toán và viết hàm kiểm tra xem một xâu có phải ở dạng xâu
chuẩn hay không, cho ví dụ minh họa các bước thực hiện.
Câu 14
a) Trình bày cấu cấu trúc dữ liệu hàng đợi (Queue) được tổ chức dưới dạng
mảng, mảng vòng tròn, danh sách liên kết.
b) Hãy viết hàm bổ sung/loại bỏ một phần tử trong hàng đợi theo các cách tổ
chức trong câu a, cho ví dụ minh họa.
Câu 15
Thiết kế thuật toán đổi số ở hệ đếm 10 ra hệ đếm cơ số q (2,8,16) bằng cách sử
dụng một Stack theo các bước sau đây:

b) Hàm tìm kiếm (ngôn ngữ tuỳ chọn, nếu Q xuất hiện trong P thì trả về vị trí
xuất hiện đầu tiên, ngược lại trả về không);
c) Ví dụ mô phỏng.
Câu 21
Cho hai mảng nguyên X,Y các phần tử được sắp theo thứ tự tăng dần. Hãy lập
thuật toán xây dựng dãy Z từ hai dãy đã cho sao cho Z cũng có thứ tự tăng dần
theo các bước sau:
a) Biểu diễn cấu trúc dữ liệu;
b) Mô tả thuật toán;
c) Ví dụ mô phỏng.
Câu 22
a) Các phương pháp duyệt cây theo thứ tự preorder, inorder, posorder.
b) Viết hàm duyệt cây theo thứ tự tương ứng, cho ví dụ mô phỏng.
Câu 23
Cho danh sách liên kết (DSLK) đơn với con trỏ ngoài head trỏ tới đầu DSLK, và P
là con trỏ trỏ tới một thành phần của DSLK đó. Hãy viết ra các mẫu hàm (thuật
toán) thực hiện các nhiệm vụ sau:

1. Xen thành phần mới chứa dữ liệu d vào trước P;
2. Loại thành phần P;
3. Cho ví dụ minh họa.
Câu 24
Cho hai danh sách móc nối (danh sách liên kết đơn) L1 và L2, các phần tử thuộc
kiểu số nguyên được sắp theo thứ tự tăng dần. Hãy thiết kế thuật toán và viết hàm

4


để xây dựng danh sách L từ hai danh sách L1 và L2 sao cho danh sách L cũng có
thứ tự tăng dần. Cho ví dụ mô phỏng.



A

B
a

c

D

E

F

I

G

J

H

K

Hãy viết ra danh sách các đỉnh khi duyệt cây theo các thứ tự preorder,
inorder và postorder.
Câu 29

a) Trình bày ý tưởng và cho ví dụ minh họa thuật toán sắp xếp nhanh

Viết hàm chèn một nút mới có giá trị x vào đầu, cuối danh sách liên kết đơn
L. Cho ví dụ minh họa
Câu 31. Các chiến lược thiết kế thuật toán. Áp dụng cho các bài toán thực tế.
Câu 32. Các phương pháp đánh giá độ phức tạp của thuật toán. Bài tập áp
dụng.
Câu 33. Các thuật toán tìm kiếm tuần tự và tìm kiếm nhị phân (ý tưởng, thuật
toán, ví dụ mô phỏng).

6


Câu 34
a) Trình bày các phương pháp biểu diễn đồ thị (ma trận kề, danh sách, ma

trận trọng số), cho ví dụ minh họa.
b) Trình bày thuật toán tìm kiếm trên đồ thị theo chiều sâu, cho ví dụ mô

phỏng các bước thực hiện của thuật toán.
Câu 35: Có khai báo sau:
Typedef
{

struct Node
int

data;

// Data là kiểu đã định nghĩa trước

Node * link;


struct Node
int

data;

// Data là kiểu đã định nghĩa trước

Node * link;

//con trỏ chỉ đến cấu trúc NODE

struct List

// kiểu danh sách liên kết

};
typedef
{

NODE* first;

7


NODE* last;

} LIST;
Trình bày hàm cắt một nút ở cuối danh sách, chuyển nút đó về đầu danh sách
L.

Câu 40:

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ự: preoder, inorder và
postorder.
Câu 41: Có khai báo sau:
Typedef
{

struct Node
int

data;

// Data là kiểu đã định nghĩa trước

Node * link;

//con trỏ chỉ đến cấu trúc NODE

struct List

// kiểu danh sách liên kết

};
typedef
{



// kiểu danh sách liên kết

};
typedef
{

NODE* first;
NODE* last;

} LIST;
Trình bày hàm tạo một danh sách liên kết L có n phần tử được nhập từ bàn
phím theo nguyên tắc LIFO (Last In First Out).
Câu 44 : Cho danh sách các số nguyên được cài đặt bằng mảng, các phần tử được
sắp xếp theo thứ tự tăng dần.
a) Hãy khai báo CTDL biểu diễn dánh sách đó.
b) Hãy viết thủ tục xen 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ự tăng dần.
Câu 45: Có khai báo sau:
Typedef
{

struct Node
int

data;

// Data là kiểu đã định nghĩa trước

Node * link;

a) Hãy xây dựng cây nhị phân tìm kiếm từ dãy khóa trên.
b) Giải thích và vẽ cây kết quả sau khi tiến hành thực hiện liên tiếp các thao tác:
xóa nút có giá trị 10, bổ sung nút có khóa là 33 và xóa nút có khóa là 35.
Câu 49: Định nghĩa thuật toán đệ quy tuyến tính, cho ví dụ minh họa.
Câu 50: Viết thuật toán đệ quy tìm ước số lẻ lớn nhất của số nguyên dương n. Cho
ví dụ mô phỏng các bước thực hiện của thuật toán.
Câu 51:Thuật toán đệ quy sau có dừng hay không vì sao?
function S(n)
begin
If (n=0 or n =1) the S= 1
else
if (n mod 2 =0) S= S(n/2)
else S = S(3*n+1)
endif
endif
end
Câu 52 Viết thuật toán đệ quy tính tổng các chữ số của số nguyên dương n. Cho ví
dụ mô phỏng các bước thực hiện của thuật toán.

Câu 53:Viết thuật toán đệ quy tính tổng các chữ số của số nguyên dương n.
Chuyển thuật toán đệ quy sang dạng lặp tương ứng.
10


Câu 54:Viết thuật toán đệ quy tính Tính S(n) = 1 + 2 + 3 + ... + n - 1 + n. Chuyển thuật
toán đệ quy sang dạng lặp tương ứng. Cho ví dụ mô phỏng.
Câu 55: Áp dụng phương pháp quay lui để thiết kế thuật toán giải quyết bài toán
sau:
Tìm tất cả các hoán vị của {1,2,..,n}.
Câu 56: Áp dụng phương pháp quay lui để thiết kế thuật toán giải quyết bài toán


{
stack[0] = stack[0] + 1;
stack[stack[0]] = value;
}
Else
{
printf("Khong the them vao STACK\n");
getch();
}
}
Pop với Mảng
int pop(int stack[], int *value)
{
if(stack[0] > 0 )
{
*value = stack[stack[0]];
stack[0] = stack[0] - 1; return 1;
}
else return 0;
}
Push với DSLK đơn
void Push ( Stack &s, DataType x )
{
Node *p = new Node;
if ( p==NULL ) { coutnext = NULL;
if (s.top==NULL) // if (isEmpty(s))
s.top = p;

nhậncác xâu ký tự trên và cho ví dụ mô phỏng?
- sử dụng stack đưa xâu w vào và trả xâu ra một xâu, xâu đó chính là w’.
THUẬT TOÁN:
int main(int argc, char *argv[])
{
char s[100];

13


char *p;
char **a;
fflush(stdin);
gets(s);
int j,i=0;
p=strtok(s,' ');
while(p!=NULL)
{
a[i]=p;
i++;
p=strtok(NULL,' ');
}
VÍ DỤ:
#include <string.h>
#include <stdio.h>
int main()
{
char hoten[80];
printf("nhap ho ten: ");
gets(hoten);

}

Ý tưởng:
- Giải thuật “selection sort” sắp xếp một danh sách các giá trị bằng cách lặp lại việc
đặt một giá trị cụ thể vào đúng vị trí thích hợp cho nó trong dãy sắp xếp. (Nói cách
khác, với mỗi vị trí trong danh sách, giải thuật đi tìm giá trị phù hợp cho vị trí đó).
Hàm:
void SelectionSorting(int a[], int n)
{

int tmp;
for (int i=0;i

-

Ngược lại:

new_node->pNext = pHead;
pHead = new_node;

VÍ DỤ
Thêm một số nguyên vào đầu ds:
// Nhập dữ liệu cho X
int x;
coutx;
// Tạo nút mới
Node* new_node = getNode(x);
// Gắn nút vào đầu ds
if (new_node != NULL)
addHead(l, new_node);
2. Gắn vào cuối DSLKĐ:
-

Nếu DS rỗng thì: pHead = pTail = new_node;

-


Câu 5

17


Cho dãy A gồm n phần tử nguyên a 1, a2, ..., an (các phần tử khác nhau). Hãy xây
dựng thuật toán tìm phần tử lớn thứ k trong dãy A theo các bước sau đây:
1. Biểu diễn cấu trúc dữ liệu;
2. Mô tả thuật toán;
3. Ví dụ mô phỏng.
1. Biểu diễn: 1 mảng gồm n phần tử
2. Mô tả:
- Khai báo 1 mảng int, một biến MAX
- Gắn MAX=a[i]
- Cho vòng lặp for i=2;iMAX thì gắn MAX=a[i]
- In MAX ra
3. Ví dụ:
int MAX(int A[], int n)
{
Int SMAX;
SMAM=A[0];
for (int i=1;i
-

VÍ DỤ

void Insert_Middle(listnode *p, int position, int x){
int count=1, found=0;
listnode q, r;
r = *p;
while ((r != NULL)&&(found==0)){
if (count == position){
q = (listnode)malloc(sizeof(struct node));
q-> item = x;
q-> next = r-> next;
r-> next = q;
found = 1;
}
count ++;
r = r-> next;
}
if (found==0)
printf(“Khong tim thay vi tri can chen !”);
}

19


Câu 7
Cho file văn bản bất kỳ. Hãy xây dựng thuật toán tìm từ trong file xuất hiện
nhiều nhất theo các bước sau:
1. Biểu diễn cấu trúc dữ liệu;

Câu 8
c) Trình bày cấu trúc dữ liệu danh sách liên kết đôi.
- Danh sách liên kết đôi: Là danh sách mà mỗi phần tử trong danh sách có 2 liên kết
với một phần tử đứng trước (Prev) và một phần tử đứng sau nó (Next).
d) Viết các phép toán lấy ra một phần tử trong một danh sách liên kết đôi, cho
ví dụ minh họa.
- đầu bằng đầu trỏ tien. vd: đau=đau->tien
Có 5 vị trí lấy ra:
1. Đầu DSLK2
int removeHead (DList &l)
{
if ( l.pHead == NULL)

return 0;

DNode *p = l.pHead;
l.pHead = l.pHead->pNext;
l.pHead->pPrev = NULL;
delete p;
if (l.pHead == NULL)
else

l.pTail = NULL;

l.pHead->pPrev = NULL;

return 1;
}
2. Cuối DSLK2
int removeTail (DList &l)

return 1;
}
else return 0;
}
4. Trước q:
int removeBefore (DList &l, DNode *q)
{
if (q == NULL) return 0;
DNode *p = q ->pPrev;
if (p != NULL)
{
q->pPrev = p->pPrev;
if (p == l.pHead) l.pHead = q;
else

p->pPrev->pNext = q;

delete p;
return 1;
}

22


else return 0;
}
5. Có khóa k:
int removeNode (DList &l, int k)
{
DNode *p = l.pHead;

23


Câu 10
a) Trình bày cấu trúc dữ liệu danh sách liên kết vòng một chiều?
- Danh sách liên kết vòng: Là một danh sách liên kết đơn (hoặc đôi) mà phần
tử cuối danh sách, thay vì mang giá trị NULL, trỏ tới phần tử đầu danh sách.
b) Viết phép toán bổ sung một phần tử trong một danh sách liên kết vòng
một chiều, cho ví dụ minh họa?
vd: đau->next=p; p->next=đau
Có 3 vị trí bổ sung
1. Đầu DSLKV:
void addHead (List &l, Node *new_node)
{
if (l.pHead == NULL)
{
l.pHead = l.pTail = new_node;
l.pTail->pNext = l.pHead;
}
else
{

24


new_node->pNext = l.pHead;
l.pTail->pNext = new_node;
l.pHead = new_node;
}
}