A) Phần lý thuyết

1. Trình bày khái niệm dữ liệu và kiểu dữ liệu, các kiểu dữ liệu cơ bản. Phân biệt xâu tuyến tính (danh xác tuyến tính) và danh sách liên kết đơn.

a. Khái niệm dữ liệu:

Là tất cả thông tin đã được chọn lọc và chuẩn hóa <có khuôn dạng>

b. Khái niệm kiểu dữ liệu:

-Kiểu dữ liệu T được xác định bởi một bộ <V,O> , với :

V : tập các giá trị hợp lệ mà một đối tượng kiểu T có thể lưu trữ.

O : tập các thao tác xử lý có thể thi hành trên đối tượng kiểu T.

-Ví dụ: Giả sử có kiểu dữ liệu mẫu tự = <Vc ,Oc> với

Vc = { a-z,A-Z}

Oc = { lấy mã ASCII của ký tự, biến đổi ký tự thường thành ký tự hoa...}

Giả sử có kiểu dữ liệu số nguyên = <Vi ,Oi> với

Vi = { -32768..32767}

Oi = { +, -, *, /, %}

-Như vậy, muốn sử dụng một kiểu dữ liệu cần nắm vững cả nội dung dữ liệu được phép lưu trữ và các xử lý tác động trên đó.

-Các thuộc tính của 1 KDL bao gồm:

+ Tên KDL,

+ Miền giá trị,

+ Kích thước lưu trữ.

Tập các toán tử tác động lên KDL.

c. Các kiểu dữ liệu:

Tùy theo nhu cầu sử dụng, dữ liệu được chia thành các loại khác nhau, có các kiểu dữ liệu sau:

- Dữ liệu cơ sở (sơ cấp):

+ Bit......(0/1),

+ Byte....(8 bites),

+ Word....(2 bytes).

- Dữ liệu cơ bản:

+ Số nguyên (Integer),

+ Số thực.....(Real),

+ Logic.......(Boolean),

+ Kí tự........(Char).

- Dữ liệu cơ bản có cấu trúc:

+ Xâu (String),

+ Mảng (Array),

+ Bản ghi (Record),

+ Tập hợp (Set),

+ Tệp (File),

+ Con trỏ (Point).

- Dữ liệu trừu tượng:

+ Danh sách (List),

+ Cây (Tree),

+ Đồ thị (Graph).

d. Phân biệt danh sách tuyến tính (DSTT) và danh sách liên kết đơn (DSLKĐ):

Mặc dù cùng là cấu trúc dữ liệu bao gồm một tập các phần tử, trong đó mỗi phần tử là một bản ghi, nhưng giữa danh sách tuyến tính và danh sách liên kết đơn có một số điểm khác biệt sau:

- DSTT là cấu trúc dữ liệu dễ sử dụng, tốc độ truy cập cao hơn DSLKĐ vì DSTT có thể được truy cập ngẫu nhiên thông qua chỉ số, còn DSLKĐ chỉ có thể truy cập tuần tự. Trong DSLKĐ, muốn truy cập tới 1 phần từ phải bắt đầu từ đầu danh sách sau đó lần lượt qua các phần tử kế tiếp cho tới khi đến phần tử cần truy cập.

- Việc bố trí, sắp đặt lại các phần tử trong 1 DSLKĐ đơn giản hơn nhiều so với DSTT. Bới vì đối với DSLKĐ, để thay đổi vị trí của 1 phần tử, ta chỉ cần thay đổi các liên kết của một số phần tử có liên quan, còn trong DSTT, ta thường phải thay đổi vị trí của rất nhiều phần tử.

- Do bản chất động của DSLKĐ, kích thước của DSLKĐ có thể linh hoạt hơn nhiều so với DSTT. Kích thước của DSLKĐ không cần phải khai báo trước, bất kỳ lúc nào có thể tạo mới 1 phần tử và thêm vào vị trí bất kỳ trong danh sách. Nói cách khác, DSTT là 1 tập có số lượng cố định các phần tử dễ dẫn đến tình trạng thiếu hoặc thừa bộ nhớ, còn DSLKĐ là 1 tập có số lượng phần tử không cố định, rất linh hoạt.

2. Trình bày về DSTT cài đặt bởi mảng. Công thức tính địa chỉ của một phần tử trong mảng.

a. DSTT cài đặt bởi mảng một chiều:

- Khi cài đặt danh sách bằng mảng một chiều, thì có một biến nguyên n lưu số phần tử hiệncó trong danh sách. Nếu mảng được đánh số bắt đầu từ 1 thì các phần tử trong danh sáchđược cất giữ trong mảng bằng các phần tử được đánh số từ 1 tới n (hoặc từ 0 tới n-1).

- Ðặc điểm của danh sách:

+ Kích thước của danh sách sẽ được cấp phát theo khai báo.

+ Các phần tử của danh sách nằm liên tục nhau trong bộ nhớ, giữa các phần tử này không có khoảng trống.

- Nhận xét: Danh sách cài đặt như trên còn gọi là danh sách đặc dùng phương pháp truy xuất trực tiếp nên thời giantruy xuất nhanh, nhưng hiệu quả sử dụng bộ nhớ thấp. Danh sách đặc không phù hợp với phép thêm vào và loại bỏ vì mỗi lần thêm vào và loại bỏ thì chúng taphải đổi chỗ nhiều lần. Ðặc biệt trường hợp xấu nhất là khi thêm vào và loại bỏ

ở đầu danh sách

- Kết luận : Danh sách đặc nên sử dụng cho các danh sách ít bị biến động về sốlượng các phần tử. Còn đối với những danh sách thường bị biến động thì ngườita chọn cấu trúc là danh sách liên kết.

b. DSTT cài đặt bởi mảng hai chiều:(tham khảo thôi)

DSTT được cài đặt bằng cách sử dụng mảng hai chiều. Mỗi hàng trong mảng biểu diễn một nút và trường Next được cài đặt là một dãy các giá trị nguyên từ 0..N để biểu diễn chỉ số hàng của nút kế tiếp (giá trị 0 được sử dụng tương đương với Null). Do đó, danh sách liên kết sau sẽ được cài đặt bằng mảng trong hình dưới:

Con trỏ Head chứa giá trị 1, chỉ ra rằng nút đầu tiên trong danh sách được lưu ở hàng 1 của mảng hai chiều. Hàng 1 chứa giá trị 103 và trường Next là 5 để chỉ vị trí của nút thứ hai trong danh sách là ở hàng 4. Trường Next của nút cuối cùng trong danh sách có giá trị 0 để chỉ ra không còn nút nào trong danh sách. Giá trị 0 cũng tương tự như Null trong cài đặt bằng danh sách liên kết.

Để sử dụng phương pháp cài đặt này, ta cần phải có một cách để xác định một hàng ở trong mảng là trống và có thể sử dụng hàng đó bất kỳ lúc nào (ví dụ hàng 3, 5, 6 trong hình trên). Nếu không, chúng ta sẽ không có cách nào để biết hàng đó đã bị chiếm chố chưa khi thực hiện thao tác bổ sung một phần tử mới vào danh sách. Để biết được các hàng vẫn còn trống trong mảng ta sử dụng một danh sách chứa các nút chính là các hàng còn trống trong mảng. Head của danh sách này được đặt vào một con trỏ tên là Available trỏ tới hàng trống đầu tiên. Các hàng còn trống sẽ được liên kết với nhau thông qua trường Next của các nút. Như vậy, ta có hai danh sách đan xen nhau trên một mảng hai chiều - một danh sách các phần tử được trỏ bởi Head và một danh sách các hàng còn trống của mảng được trỏ bởi Available. Khi giá trị của biến Available bằng 0 thì có nghĩa là mảng đã đầy. Thông thường, danh sách các hàng trống trong mảng và cấu trúc mảng sẽ được khởi tạo đồng thời bởi thao tác Create (khởi tạo) khi danh sách được xây dựng.

c. Công thức tính địa chỉ của một phần tử trong mảng:

- Mảng một chiều: p<= i <=q, loc(ap)= l0, loc(ai)= l0 + (i-p)*c.

- Mảng hai chiều: p<= i <=q, r<= j <= s, loc(ap)= l0:

+ Ưu tiên hàng:

loc(aij)= l0 + [(i-p)*(s-r +1) + (j-r)]*c.

+ Ưu tiên cột:

loc(aij)= l0 + [(j-r)*(q-p +1) + (i-p)]*c.

3. Trình bày định nghĩa danh sách, các thao tác thường gặp trên danh sách. Thế nào là danh sách liên kết đơn, kép, vòng, đa liên kết. Các trường hợp đặc biệt của danh sách liên kết (Ngăn xếp, hàng đợi):

a. Định nghĩa danh sách:

Danh sách tuyến tính hay còn gọi là danh sách là một tập có thứ tự của 0,1, hoặc nhiều thành phần (gọi là các nút). Mỗi nút chứa trường thông tin (viết tắt là I hay Info) và có một cách nào đó để xác định nút kề ngay sau nó trong danh sách. Để biết được nút đầu tiên trong danh sách ta sử dụng một con trỏ trỏ đến phần tử đầu tiên trong danh sách và gọi đó là con trỏ đầu (head pointer).

b. Định nghĩa danh sách liên kết:

- Là tập hợp các phần tử cùng loại mà số phần tử của nó là một con số luôn luôn biến động, phép bổ sung hay loại bỏ một phần tử của danh sách là những phép toán tác động thường xuyên lên danh sách.

- Mỗi phần tử của danh sách là một bản ghi gồm ít nhất hai trường:

+ Một trường để lưu trữ dữ liệu của chính phần tử đó, kí hiệu là trường Info.

+ Một trường dùng để lưu trữ địa chỉ của phần tử tiếp theo trong danh sách, kí hiệu là trường: Link.

- Tại mỗi thời điểm, danh sách có phần tử đầu và phần tử cuối và có một phần tử mà hệ thống truy xuất vào gọi là phẩn tử hiện thời hay phần tử bận.

c. Các thao tác thường gặp trên danh sách:

Các thao tác bổ sung, xoá, lấy thông tin từ các phần tử được thực hiện ở bất kỳ chỗ nào trong danh sách - ở đầu, cuối hoặc giữa.

d. Các loại danh sách liên kết:

- Danh sách liên kết đơn (DSLKĐ - singly linked list) là danh sách liên kết mà mỗi phần tử có dúng một trường liên kết dùng để lưu trữ địa chỉ của phần tử đứng ngay sau nó.

- Danh sách liên kết kép (DSLKK - double linked list): là danh sách liên kết mà mỗi phần tử có đúng hai trường liên kết dùng để lưu trữ địa chỉ của các phần tử đứng trước và đứng sau nó.

- Danh sách đa liên kết ( DSĐLK - multy linked list): là danh sách liên kết mà mỗi phần tử có từ hai trường liên kết trở lên.

- Danh sách liên kết nối vòng (DSLKLV): là danh sách liên kết đơn được cải tiến để có thể duyệt danh sách theo 1 vòng tròn mà không phải theo một chiều, nhờ việc sử dụng trường liên kết của phần tử cuối cùng để chứa địa chỉ của phần tử đầu tiên và do đó có thể quay về được phần tử đầu tiên có con trỏ Head trỏ tới.

e. Ngăn xếp (Stack) :

- Ngăn xếp là một loại dữ liệu có cấu trúc trừu tượng. Giống như danh sách tuyến tính trong đó việc bổ sung và loại bỏ phần tử được thực hiện ở cùng một đầu.

- tại mỗi thời điểm khác nhau thì số phần tử của danh sách sẽ khác nhau. Có 3 khả năng:

+ Cạn (rỗng - empty),

+ Tràn (đầy - full),

+ Không cạn và không tràn.

- Dữ liệu được tổ chức theo kiểu ngăn xếp được gọi là:

+ Vào sau ra trước (Last In Fist Out - LIFO),

+ Vào trước ra sau (Fist In Last Out - FILO).

- Cài đặt ngăn xếp bằng danh sách liên kết - có số phần tử luôn luôn biến động dễ dàng, khắc phục được hạn chế khi cài bằng mảng - có số phần tử cố định.

- Ứng dụng của ngăn xếp:

+Trong bài toán đổi cơ số,

+ Định giá biểu thức số học: chuyển biểu thức trung tố sang hậu tố, tiền tố và tính giá trị của biểu thức.

- Với quy tắc vào sau ra trước người ta sử dụng ngăn xếp để cài đặt các giải thuật đệ quy,.

f. Hàng đợi (Queue) :

- Hàng đợi là một loại danh sách tuyến tính mà phép bổ sung phần tử được thực hiện ở đầu này còn phép loại bỏ phần tử được thực hiện ở đầu kia của danh sách.

- Dữ liệu được tổ chức theo kiểu hàng đợi được gọi là:

+ Vào trước ra trước (Fist In Fist Out - FIFO),

+ Vào sau ra sau (Last In Last Out - LILO).

4. Trình bày các định nghĩa và các khái niệm về cây. Cây nhị phân và các thao tác trên cây nhị phân, cách chuyển cây tổng quát về cây nhị phân tương đương.

a. Định nghĩa cây:

Cây là một tập hợp gồm hữu hạn các phần tử được gọi là các nút, trong đó có một nút đặc biệt gọi là nút gốc (Root). Giữa các nút có quan hệ phân cấp gọi là quan hệ cha con.

b. Các khái niệm về cây:

- Rừng: Tập hợp một số cây thì gọi là rừng.

- Cây con: Mỗi nút trừ nút gốc có thể là gốc của một cây nào đó gọi là cây con.

- Nút trong: Mọi nút không phải là nút gốc đều gọi là nút trong.

- Nút lá: Là nút không có con.

- Cấp: Cấp của một nút là số cây con của nút đó, cấp của cây là cấp cao nhất có thể của các nút trên cây đó.

- Mức: Mức gốc bằng một, nếu một nút có mức là n thì nút con có mức n+1.

- Chiều cao (chiều sâu) là số mức lớn nhất của các nút trên cây đó.

- Thứ tự: Một nút có thể có nhiều con, các con đó có thể được sắp thứ tự hoặc không, thông thường các con được sắp xếp từ trái sang phải, nút ở bên trái nhất là con trưởng (cả), nút ở bên phải nhất là con út.

c. Cây nhị phân:

- Cây nhị phân là cây mà mỗi nút không có quá 2 con.

- Các con của mỗi nút được đánh thứ tự 1, 2 hoặc trái phải.

d. Các thao tác trên cây nhị phân:

- Phép duyệt cây - thao tác phổ biến nhất trên cây, là phép thăm tất cả các nút trên cây, mỗi nút đúng một lần, có 3 phương án để duyệt cây nhị phân với việc đệ quy bắt đầu từ gốc:

+ Theo thứ tự trước:

- > Duyệt gốc.

- > Duyệt cây con trái theo thứ tự trước.

- > Duyệt cây con phải theo thứ tự trước.

+ Theo thứ tự giữa:

- > Duyệt cây con trái theo thứ tự giữa.

- > Duyệt gốc.

- > Duyệt cây con phải theo thứ tự giữa.

+ Theo thứ tự sau:

- > Duyệt cây con trái theo thứ tự sau.

- > Duyệt cây con phải theo thứ tự sau.

- > Duyệt gốc.

e. Cách chuyển cây tổng quát về cây nhị phân tương đương:

Đệ quy bắt đầu từ gốc:

- > Chọn con trưởng là con trái.

- > Chọn em kế tiếp là con phải.

5. Định nghĩa cây nhị phân tìm kiếm và các thao tác trên cây nhị phân tìm kiếm.

a. Định nghĩa cây nhị phân tìm kiếm:

Cho n khóa k1, k2,... kn là một cây nhị phân mà mỗi nút của nó đều được định danh bởi một trong các khóa đã cho và đối với mọi nút trên cây tính chất sau đây luôn được thỏa mãn:

+ Mọi khóa của cây con trái đều nhỏ hơn của khóa đang xét.

+ Mọi khóa của cây con phải đều lớn hơn khóa của nút đang xét.

b. Các thao tác trên cây nhị phân tìm kiếm:

- Dựng cây nhị phân tìm kiếm từ dãy khóa k1, k2,... kn , thưc hiện đệ quy từ nút gốc, so sánh khóa ki+1 với khóa với nút đang xét:

+ Nếu ki+1 nhỏ hơn thì chuyển sang cây con trái của nút đang xét.

+ Nếu ki+1 lớn hơn thì chuyển sang cây con phải của nút đang xét.

- Xóa một nút trên cây nhị phân tìm kiếm:

+ Nếu là nút lá thì xóa ngay.

+ Nếu là nút trong hay cành mà

* Nút đó có một con thì thì đưa cả nút con đó nên thay thế.

* Nút đó có đủ hai con thì hoặc đưa nút cận trái nhất của cây con phải lên thế chỗ hoặc đưa nút cận phải nhất của cây con trái lên thế chỗ.

6. Định nghĩa và các khái niệm liên quan đến đồ thị. Các bài toán liên quan đến đồ

thị:

a. Định nghĩa:

Một đồ thị G bao gồm một tập hữu hạn V (các nút hay các đỉnh) và E (các cung hay các cặp đỉnh. Kí hiệu G= (V,E).

b. Các khái niệm liên quan:

- Nếu các cung hay các cặp đỉnh không phân biệt thứ tự thì đồ thị tương ứng gọi là đồ thị không định hướng, ngược lại gọi là đồ thị định hướng hay có hướng. Trong đồ thị định hướng thì các cung phải có chiều mũi tên.

- Giả sử V1, V2 thuộc V. Ta nói V1 và V2 là lân cận của nhau nếu tồn tại cung nối V1 và V2. Tức là (V1, V2) thuộc E hay (V2, V1) thuộc E.

- Đường đi từ đỉnh V1 đến đỉnh V2 của đồ thị G là một dãy các cung có đỉnh đầu là V1 và đỉnh cuối là V2.

- Đồ thị có trọng số nếu trên các cung có gắn một giá trị nào đó có thể là số hoặc chữ.

- Đường đi đơn là đường đi mà mọi điểm trên đó trừ điểm đầu và điểm cuối, phải khác nhau.

- Nếu đường đi đơn có điểm đầu trùng điểm cuối thì được gọi là chu trình.

- Liên thông: một đồ thị được gọi là liên thông nếu mọi đỉnh của chúng đều liên thông. Hai đỉnh gọi là liên thông nếu tồn tại ít nhất một đường đi nối đỉnh này với đỉnh kia.

c. Các bài toán liên quan:

Phép duyệt đồ thị là phép đưa ra danh sách các nút sao cho mỗi nút xuất hiện đúng một lần:

- Duyệt đồ thị theo chiều sâu:

+ Thăm đỉnh V là đỉnh xuất phát.

+ Thăm đỉnh W là đỉnh chưa được thăm và là lân cận của V.

+ Nếu tất cả các đỉnh lân cận của V đã được thăm hết thì quay lại điểm

xuất phát tiếp tục thực hiện một phép duyệt cây theo chiều sâu.

- Duyệt cây theo chiều rộng:

+ Duyệt V là đỉnh xuất phát.

+ Duyệt lần lượt các đỉnh lân cận của V từ trái sang phải đến hết rồi áp dụng tiếp cho các đỉnh lân cận của V.