Câu hỏi trắc nghiệm ôn tập cấu trúc dữ liệu giải thuật | Đại học Kinh tế Kỹ thuật Công nghiệp

ĐỀ CƯƠNG CTDL GT - là một môn học cực kỳ hữu ích dành cho tất cả mọi người m
Trắc Nghiệm Cấu Trúc Dữ Liệu & Giải Thuật
1. Phát biểu nào sau đây đúng:
a. Trong cấu trúc if có thể có else hoặc không
b. Cấu trúc switch luôn coa case
c. Cấu trúc for chỉ áp dụng với khối lệnh lặp xác định
d. Cấu trúc whlie chỉ áp dụng với khối lệnh lặp không xác định
2. Phát biểu nào sau đây sai:
a. Đa số các bài toán có thời gian thực thi tiệm cận tới một trong các hàm N, NLogN, 2N
b. Đa số các bài toán có thời gian thực thi tiệm cận tới một trong các hàm N, N2 +2, LogN
c. Đa số các bài toán có thời gian thực thi tiệm cận tới một trong các hàm N, N3, LogN
d. Đa số các bài toán có thời gian thực thi tiệm cận tới một trong các hàm N, N2, 2N
3. Hai loại danh sách thường được sử dụng là
a. Danh sách đặc và Ngăn xếp
b. Danh sách đặc và Danh sách liên kết
c. Ngăn xếp và Danh sách liên kết
d. Hàng đợi và danh sách đặc
4. Để tạo danh sách rỗng ta viết hàm như sau: a. Void MakeNullList(List L) { Node new L; L-> Next = NULL; } b. Void MakeNullList(List *L) { L= new Node; L-> Next = NULL; }
c. Void MakeNullList(List &L) { L= new Node; L-> Next = NULL; }
d. Void MakeNullList(List &L) { Node new L; 1
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long L-> Next = NULL; }
5. Cho hàm xóa 1 phần tử khỏi hang đợi như sau:
ElementType DeQueue(Queue &Q) { if( !EmptyQueue(Q)) { Position T = Q.Front->Next; (1) return T->Element; (2) Q.Front= Q.Front->Next;(3) Delete T; (4) } }
Ta có thể bỏ câu lệnh nào mà hàm trên vẫn thực hiện được và đúng chức năng của nó : a. Câu lệnh (4) b. Câu lệnh (2) c. Câu lệnh (3) d. Câu lệnh (1)
6. Bậc của một cây là:
a. Số cây con của nút gốc b. Bậc của nút gốc
c. Bậc lớn nhất của các nút trong cây
d. Tổng bậc của các nút trong cây
7. Ta có thể biểu diễn cây bằng bao nhiêu cách: a. 5 cách b. 3 cách c. 4 cách d. 6 cách
8. Cây nhị phân tìm kiếm được viết tắt là: a. SBT b. TSB c. BTS d. BST
9. Cho hàm trên cây nhị phân tìm kiếm như sau: Void Func (BST_Type BST_Tree) { if(BST_Tree != NULL) { cout<Key<<’\t’; Func(BST_Tree -> Right; } 2
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long }
Hàm Func thực hiện chức năng gì?
a. Tìm nút nhỏ nhất trong cây
b. Tìm nút lớn nhất trong cây
c. In từ nút gốc đến nút lớn nhất trong cây
d. In từ nút gốc đến nút nhỏ nhất trong cây
10.Đặc điểm nào sau đây không phải của hàm có tính đệ qui:
a. Chương trình viết ngắn gọn
b. Việc gọi đi gọi hàm rất nhiều lần phụ thuộc vào độ lớn đầu vào
c. Chương trình dễ viết và dễ đọc nhưng có thể gây khó hiểu
d. Hàm đệ qui sử dụng vùng nhớ HEAP để lưu địa chỉ các lần gọi đệ qui
11.Phát biểu nào sau đây là sai?
a. Việc đánh giá vào độ phức tạp của một giải thuật thường là ước lượng thời gian thực hiện phép toán
b. Thời gian thực hiện một giải thuật phụ thuộc rất nhều vò các yếu tố
c. Các yếu tố ảnh hưởng đến thời gian thực hiện một thuật toán là cấu tạo của
máy tính, dữ liệu đầu vào và đầu ra
d. Để ước lượng thời gian thực hiện một thuật toán người ta ước lượng thời gian
thực hiện trung bình dựa vào thời gian thực hiện tốt nhất và xấu nhất
12.Sắp xếp các câu lệnh sau theo trật tự đúng cho quy trình them một phần tử
vào vị trí X vào sau vị trí P trong danh sách liên kết đơn (1) Position Temp = new Node; (2) P -> Next = Temp; (3) Temp -> Element = X;
(4)Temp -> Next = P -> Next; a. 1, 2, 3, 4 b. 2, 4, 3 ,1 c. 1, 3, 4, 2 d. 4, 3, 2, 1 13.Cho hàm như sau:
Void Func(ElementType X, List &L) { Position Temp = new Node; Temp -> Element = X;
Temp -> Next = L -> Next; L->Next = Temp; }
Hàm trên thực hiện chức năng gì?
a. Thêm phần tử X vào cuối danh sách L
b. Xóa phàn tử X ở đầu danh sách L 3
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long
c. Xóa phần tử X ở cuối danh sách L
d. Thêm phần tử X vào đàu danh sách L
14.Người ta đặt tên phép duyệt cây dựa vào đâu
a. Thứ tự duyệt của nút gốc
b. Thứ tự duyệt của nút lá
c. Thứ tự duyệt của cây con trái
d. Thứ tự duyệt của cây con phải
15.Cho hàm xóa phần tử khỏi ngăn xếp S như sau ElementType Pop(Stack &S) { Position Temp = S->Next; if( Temp != NULL) {
ElementType T = Temp-> Element; (1) S->Next = Temp Next;(2) Delete Temp;(3) return T;(4) } }
Phát biểu nào sau đây đúng?
a. Thứ tự các câu lệnh 1, 2, 3, 4 không thể thay đổi
b. Câu lệnh 2 có thể thực hiện trước câu lệnh 1
c. Câu lệnh 3 có thể thực hiện trước câu lệnh 1
d. Câu lệnh 2 có thể thực hiện trước câu lệnh 3
16.Hàm nào sau đây tạo hàng đợi rỗng?
a. MakeNullQueue (Queue &Q) { Position Header = new Node; Header -> Next = NULL; Q.Front = Header; Q.Rear = Header; }
17.Phát biểu nào sau đây sai?
a. Trong đồ thị vô hướng đầy sẽ không có khuyên
b. Trong đồ thị hữu hướng thưa có N đỉnh thì tối đa có N khuyên
c. Trong đồ thị hữu hướng thưa có số đỉnh treo bằng số cung treo
d. Trong đồ thị vô hướng đầy số đỉnh treo bằng số cạnh treo 4
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long
18.Prototype nào sau đây có thể thực hiện chức năng in các đỉnh có cung đến
đỉnh d trong đồ thị hữu hướng thưa
a. Void incungden(Graph g, int n,e, int d)
b. Void incungden(Graph g, int n, int e, d)
c. Void incungden(Graph g, int n, int e, int d)
d. Void incungden(Graph g, int n, e, d)
19.Phát biểu nào sau đây là sai?
a. Nếu có cung (x,y) trong đồ thị thì ta nói x là đỉnh gốc y là đỉnh ngọn
b. Nếu đinh là gốc của một cung duy nhất và không là ngọn của bất kỳ cung
nào thì đỉnh này được gọi là đỉnh treo
c. Nếu có cung (x,y) trong đồ thị thì ta nói x và y kề nhau
d. Nếu một cung có đỉnh gốc và đỉnh ngọn trùng nhau thì được gọi là khuyên
20. Prototype nào sau đây có thể thực hiện chức năng thêm 1 cạnh trong đồ thị vô hướng đầy
a. Void InsertEdge(Graph &g, int n, int &e, int d1, int d2)
b. Void InsertEdge(Graph g, int &n, int &e, int d1, int d2)
c. Void InsertEdge(Graph &g, int 7n, int &e, d1, d2)
d. Void InsertEdge(Graph g, int n, int e, int d1, int d2) 21.Cho hàm như sau:
int Func(Graph g, int n, int e, int d) { int i, dem = 0; for (i=1; i<=n; i++)
if( i != d && g[d][i] == 1) dem++; if(dem % 2 == 0) return 1; else return 0; }
Hàm Func trên thực hiện chức năng gì đối với đồ thị vô hướng đầy g?
a. Kiểm tra đỉnh bậc chẳn
b. Kiểm tra đỉnh bậc lẻ
c. Đếm số đỉnh bậc chẳn
d. Đếm số đỉnh bậc lẻ
22.Giả sử đồ thị (G) có ma trận kề A = {ai} với ai là số cung từ đỉnh i đến đỉnh j
Phát biểu nào sau đây là sai?
a. G đối xứng nếu và chỉ nếu ai = aj
b. G đối xứng nếu và chỉ nếu ai ≠ aj
c. G đối xứng nếu và chỉ nếu ai + aj <= 1
d. G đối xứng nếu và chỉ nếu ai + aj >= 1 5
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long
23.Hàm biến đổi khóa là hàm a. Nhiều – nhiều b. Nhiều – một c. Một – nhiều d. Một – một
24.Hãy chọn phát biểu đúng?
a. Ta không thể sử dụng danh sách đặc để giải quyết sự đụng độ trong bảng băm
b. Ta không thể sử dụng danh sách liên kết để giải quyết sự đụng độ trong bảng băm
c. Người ta thường sử dụng danh sách liên kết để giải quyết sự đụng độ trong bảng băm
d. Người ta thường sử dụng danh sách đặc để giải quyết sự đụng độ trong bảng băm
25.Giả sử bảng băm được biểu diễn bằng phương pháp thử tuyến tính. M = 11, hàm băm như sau: int HF(int K) { return K%M; }
Khi biểu diễn các khóa 13, 14, 26, 38 vào bảng thì các khóa này vị trí tương ứng là: a. 2, 9, 10, 4 b. 2, 4, 10, 9 c. 2, 3, 4, 5 d. 2, 5, 3, 4
26.Giả sử bảng băm được biểu diễn bằng phương pháp nối kết trực tiếp, hãy
chọn phát biểu sai?
a. Nếu bảng băm có số butket(M) càng lớn thì thực hiện các phép toán càng nhanh và ngược lại
b. Nếu muốn ít tốn dung lượng bộ nhớ thì ta chọn số butket (M) càng nhỏ và
khi đó tốc độ truy xuất các khóa càng chậm
c. Nếu ta cần biểu diễn N khóa vào bảng băm có M butket thì trung bình mỗi butket có N/M khóa
d. Nếu số butket (M) bằng với số khóa cần biểu diễn N thì tốc độ truy xuất các
khóa có bậc tương đương là O(N/M)
27.Để giải quyết sự đụng độ khi biểu các khóa vào bảng băm người ta thường sử
bao nhiêu phương pháp? a. 3 b. 2 6
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long c. 4s d. 1
28. Giả sử bảng băm được biểu diễn bằng phương pháp nối kết trực tiếp, các
khóa cần biểu diễn là 1, 3, 4, 5, 7, 10, 11, 17,19, 23. Chọn giá trị M cho bảng
băm bao nhiêu là hợp lý nhất: a. 5 b. 11 c. 3 d. 7
29.Nếu trong hàm có nhiều đối số hình thức thì chúng cách nhau bởi dấu gi? a. Chấm phẩy (;) b. Hai châm(:) c. Chấm (.) d. Phẩy(,)
30.Phát biểu nào sau đây là đúng?
a. Ngăn xếp và danh sách hạn chế việc thêm vào thực hiện ở một đầu và loại bỏ
thực hiện ở đầu còn lại
b. Ta chỉ có thể cài đặt ngăn xếp bằng con trỏ
c. Ngăn xếp có tính chất “vào trước ra sau”
d. Ngăn xếp có tính chất “vào trước ra trước”
31.Hàng đợi là danh sách hạn chế có tính chất? a. LIFO b. FIFO c. FOFO d. FILO
32.Phát biểu nào sao đây là sai?
a. Nút T được gọi là nút trước của nút S nếu cây con có gốc là T chứa cây con có gốc là S
b. Nút S được gọi là nút sau của nút T nếu cây con có gốc là T chứa cây con có gốc là S
c. Nếu nút T là nút trước của nút S, thì nút S là nút sau của nút T
d. Nếu nút T là nút trước của nút S, thì nút T là nút cha của nút S
33.Khi đưa các khóa vào bảng băm, có thể xảy ra trường hợp trước khi đưa vào
không bị đụng độ nhưng khi đưa vào lại xảy ra đụng độ
Phát biểu trên không đúng đối với bảng băm biểu diển bằng phương pháp nào? a. Nối kết trực tiếp b. Băm kép c. Nối kết hợp nhất d. Thử bậc 2 7
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long CHƯƠNG 1: TỔNG QUAN
1. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật có thể minh họa bằng đẳng thức:
a. Cấu trúc dữ liệu + Giải thuật = Chương trình
2. Nhân tố nào là nhân tố chính ảnh hưởng đến thời gian tính của một giải thuật
Kích thước của dữ liệu đầu vào của thuật toán
3. Các tiêu chuẩn đánh giá cấu trúc dữ liệu. Để đánh giá một cấu trúc dữ liệu
chúng ta thường dựa vào một số tiêu chí
a. Cấu trúc dữ liệu phải tiết kiệm tài nguyên (bộ nhớ trong)
b. Cấu trúc dữ liệu phải phản ảnh đúng thực tế của bài toán
c. Cấu trúc dữ liệu phải dễ dàng trong việc thao tác dữ liệu d. Cả a, b, c đều đúng
4. Chọn phát biểu đúng trong các phát biểu dưới đây: bằng cách chạy thử 1
thuật toán với 1 bộ dữ liệu, ta có thể:
Khẳng định thuật toán sai nếu cho kết quả sai
5. Lớp có hàm là hằng số:
Thời gian chạy của nó là hằng số 6. Lớp có hàm là LogN:
Thời gian chạy chậm khi N lớn dần 7. Lớp có hàm là N:
Thời gian chạy của CT là tuyết tính, N tăng gấp đôi thì thời gian chạy nhân gấp đôi
8. Lớp có hàm là NLogN:
Đa số sắp xếp 1 vòng lập, cơ số 2, tìm kiếm nhị phân: có thứ tự tăng/giảm dần
N tăng gắp đôi thì thời gian chạy nhân lên nhiều hơn gấp đôi 9. Lớp có hàm là N2: Sắp xếp 2 vòng lập
Khi N đươc nhân đôi thì thời gian tăng gấp 4 10.Lớp có hàm là N3: Sắp xếp 3 vòng lập
Khi N tăng gấp đôi thì thời gian tăng gấp 8
11.Lớp có hàm là 2N: 8
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long Lớp số mũ: N! giai thừa
Khi N tăng gấp đôi thì thời gian tăng lên lũy thừa 2 9
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long CHƯƠNG 2: DANH SÁCH
12. Lựa chọn định nghĩa về danh sách đúng nhất
a. Danh sách là tập hợp các phần tử có kiểu dữ liệu xác định và giữa chúng có một mối liên hệ nào đó.
b. Số phần tử của danh sách gọi là chiều dài của danh sách.
c. Một danh sách có chiều dài bằng 0 là một danh sách rỗng. d. Cả a, b, c đều đúng
13. Tính chất quan trọng của ds là:
Các phần tử có thứ tự tuyến tính theo vị trí (position)
14. Ds thường được phân thành mấy loại?
Có 2 loại: ds đặc (mảng), ds liên kết (con trỏ)
15. Hàm Endlist (L) trong danh sách là?
Hàm trả về vị trí sau phần tử cuối trong danh sách NULL 16. Khi danh sách rỗng?
Giá trị hàm EndList(L) và hàm FirstList(L ) luôn luôn bằng nhau
17. Chọn câu đúng nhất để mô tả thuật toán sắp xếp nổi bọt (Bubble Sort) trên
mảng M có N phần tử:
Đi từ đầu mảng về cuối mảng, trong quá trình đi nếu phần tử ngay sau nó nhỏ hơn
thì hai phần tử này sẽ được đổi chỗ cho nhau. Sau N–1 lần đi thì tất cả các phần tử tăng dần
18. Giả sử cần sắp xếp mảng M có N phần tử thì cần thực hiện bao nhiêu lần? N-1 lần
19. Khi thêm hoặc xóa phần tử vào danh sách liên kết thì? L luôn luôn thay đổi.
20. Khi in(xuất) danh sách liên kết thì? L
luôn luôn KHÔNG thay đổi.
21. Trong danh sách đặc, khi thêm phần tử vào vị trí P trong danh sách ta cần phải:
Có thể dịch chuyển các phần tử từ P đến L.Last ra sau một vị trí.
22.Trong số các phép toán sau đây, phép toán nào không được dùng đối với mảng: A. Tạo mảng 10
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long
B. Bổ xung một phần tử vào mảng C. Lưu trữ mảng D. Tìm kiếm trên mảng
23. Ý nghĩa của đoạn code? typedef int ElementType; typedef struct Node { ElementType Element; Node* Next; }; typedef Node* Position; typedef Node* List;
Khai báo cấu trúc dữ liệu
24. Ý nghĩa của đoạn code?
void MakeNullList(List &L) { L = new Node; L->Next = NULL; } Tạo ds rỗng
25. Ý nghĩa của đoạn code? int EmptyList(List &L) { return L->Next==NULL; } Kiểm tra ds rỗng 26.
void InsertList(ElementType X, Position P, List &L) { Position Temp; Temp = new Node; Temp -> Element = X; Temp->Next=P->Next; P->Next=Temp; } Thêm một phần tử 27. 11
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long Position First (List L) { Position P; P=L->Next; return P; }
Xác định phần tử đầu tiên
28. Position Last (List L) { Position P; P=L; while (P->Next!=NULL) P=P->Next; return P; }
Xác định phần tử cuối cùng
29. Position Next (Position P, List L) { return P->Next; }
Xác định phần tử ngay sau P
30. Position Previous (Position P, List L) { Position Temp; if (P==L) return NULL; else { Temp=L; while (Temp->Next!=P) Temp=Temp->Next; return Temp; } }
Xác định phần tử ngay trước P
31. void DeleteList(Position P, List &L) { Position Temp; if (P->Next!=NULL) 12
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long { Temp=P->Next; P->Next=Temp->Next; delete Temp; } } Xóa phần tử ngay sau P
32. void ReadList(List &L) { ElementType X; do { cin >> X; if (X!=0) InsertList (X, Last (L), L); } while (X!=0); } Hàm nhập ds
33. void PrintList(List L) { if (EmptyList(L) != 0)
cout << "Danh sach rong" << endl; else while (L -> Next!=NULL) {
cout << L -> Next -> Element << '\t'; L=L->Next; } } Hàm in ds
34. Hãy cho biết thao tác nào không ñược phép dùng trên cấu trúc ngăn xếp (stack)
a. Thêm một phần tử vào đỉnh ngăn xếp
b. Xóa một phần tử ở vị trí bất kì khỏi ngăn xếp
c. Thêm một phần tử vào vị trí bất kì trong ngăn xếp d. Cả b và c
35. Nguyên tắc làm việc của ngăn xếp là: 13
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long
a. FIFO (first in - first out) – hàng đợi QUEUE b. FILO ( … - last out)
c. LILO (last in – last out) – hàng đợi QUEUE
d. Câu a và c cùng đúng
36. Các phép toán cơ bản: 5 phép nguyên thủy
makenull_stack(&S), push(x, &S), top(S), pop(&S), empty_stack(S)
37. Ứng dụng của ngăn xếp?
Xóa bỏ đệ qui của CT
38. Nguyên tắc làm việc của hàng đợi là:
a. FIFO (first in - first out) – hàng đợi QUEUE b. FILO ( … - last out)
c. LILO (last in – last out) – hàng đợi QUEUE
d. Câu a và c cùng đúng
39. Sử dụng 2 con trỏ Front: đầu Rear: cuối
40. Các phép toán cơ bản: 4
Makenull_queue: khởi tạo rỗng
Enqueue: thêm vào cuối hàng Dequeu: xóa đầu hàng Empty_queue: kiểm ra rỗng
41. Thao tác nào dưới đây thực hiện trên hàngđợi (queue): A. T
hêm phần tử vào lối sau
B. Loại bỏ phần tử ở lối sau
C. Thêm phần tử vào lối trước
D. Thêm và loại bỏ phần tử tại vị trí bất kỳ
42. Dấu hiệu nào cho biết hàng đợi đã có thao tác thêm và loại bỏ phần tử là rỗng:
A. Lối trước có giá trị > giá trị của lối sau
B. Lối sau nhận giá trị = 0
C. Lối trước có giá trị< giá trị của lối sau
D. Lối trước nhận giá trị = 0 14
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long CHƯƠNG 3: CÂY 43. Định nghĩa:
Cây là 1 tập hợp các phần tử (nút) được tổ chức, rỗng và khác rỗng 44. Bậc của 1 nút:
Là số cây con của nút đó 45. Bậc của 1 Cây:
Là bậc lớn nhất của các nút trong cây 46. Nút gốc:
Là nút không có nút cha 47. Nút kết thúc:
Nút lá: có bậc (cây con) bằng 0 48. Nút trung gian:
Nút giữa: không phải nút gốc cũng không phải nút lá 49. Mức của 1 nút:
Nút gốc là mức 1, con của nút gốc là mức 2, con của nút 2 là mức 3, …
50.Chiều cao của cây tìm kiếm nhị phân?
Mức cao (lớn) nhất của cây: mức của nút lá
51. Độ dài đường đi từ gốc đến nút x:
Là số nút cần đi qua kể từ gốc đến x
, bằng mức của nút đó
52. Chiều dài đường đi của 1 cây:
Tổng các mức nhân số nút : 1x1 + 2x2 + 3x4 53. Rừng là gì?
Là tập hợp các cây, Một cây bị mất nút gốc
54. Có bao nhiêu cách biểu diễn cây? Có 5 cách: 1. đồ thị 2. giản đồ 3. thục đầu hàng 4. chỉ mục 5. dấu ()
55. Có bao nhiêu cách duyệt cây?
Có 3 cách: tiền – trung – hậu 15
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long 56. Cho cây nhị phân T.
Phép duyệt tiền tố cho kết quả là: 57.ADBCEFG A. AEDBCFG B. ABDECFG C. AEBDCGF
58.Cho cây nhị phân T.
Phép duyệt trung tố cho ta kết quả là: 1. DBEAFCG 2. BEDACFG 3. DEBAGFC 4. DBEACFG
59. Cho cây nhị phân T.
Phép duyệt hậu tố cho ta biết kết quả là: A. DEBFGCA B. EBFCGAD C. DBEFAGC D. DEBGCFA
60. Định nghĩa cây nhị phân tìm kiếm:
Khóa của nút này lớn hơn tất cả các nút bên trái và nhỏ hơn tất cả các nút bên phải
60.Cây nhị phân khác rỗng là cây:
A. Mỗi nút (trừnút lá) đều cóhai nútcon
B. Tất cảcác nútđềucónútcon
C. Mỗi nút có không quá 2 nút con
D. Tất cảcác nútđềucónútcha CHƯƠNG 4: BẢNG BĂM 1. Định nghĩa:
Hàm băm: Là phép biển đổi khóa thành địa chỉ trong bảng băm
2. Hàm Hash (hàm băm) là: Hàm Nhiều – Một 16
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long
3. Bảng băm được sd nhiều nhất là: Bảng băm
ADT (kiểu dữ liệu trừu tượng)
4. Gọi M là số phần tử được chứa trong bộ nhớ:
Các khóa được chứa trong đoạn nào?
[0 … M-1] – từ 0 đến M-1 5. Hàm băm HF(k): HF(k) = k % M, k là khóa 6. Các khóa là: 8 13 6 9
15, chọn M=5, địa chỉ các khóa là: 3 3 1 4 3
7. Ta thường chọn M là số gì?
Số nguyên tố: chia hết cho 1 và chính nó , vd: 1, 3, 5, 7, 1 1, 13, 17, …
8. Có mấy bước biến đổi khóa?
Có 2 bước: hàm băm HF(k), giải quyết sự đụng độ
9. Một hàm băm được gọi là tốt thì phải? A. Tính toán nhanh
B. Các khóa được phân bố đều trong bảng C. Ít xảy ra đụng độ D. Cả 3 ý trên
10. Nếu khóa không phải số nguyên thì sao?
B1: Tìm cách biến đổi khóa về số nguyên
B2: Sử dụng hàm băm chuẩn trên số nguyên
11. Duyệt bảng băm theo thứ tự nào?
Địa chỉ từ nhỏ đến lớn
12. Có bao nhiêu bảng băm thông dụng? Có 5 phương pháp:
Nối kết trực tiếp, nối kết hợp nhất
Thử tuyến tính, thử bậc 2, băm kép
13. Pp nối kết trực tiếp
Mỗi bucket trong bảng băm Hash là 1 ds liên kết N khóa vào M dslk Mỗi M bucket có N/M khóa
M càng lớn thì tốc độ nhanh nhưng tốn vùng nhớ
M=N/k ít tốn bộ nhớ hơn k lần, nhưng tốc độ chậm k lần 17
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long
14. Pp nối kết hợp nhất
Là ds đặc mà mỗi phần tử có 2 phần: key và next Key được gán là nullkey Next gán -1
15. Bảng băm được gọi là đầy khi? Pp địa chỉ mở
N=M-1: còn 1 vị trí trống là đầy 16. Pp tuyến tính 17. Pp bậc 2 18. Pp băm kép CHƯƠNG 5: ĐỒ THỊ
1. Độ dài của đường đi trên đồ th? là gì
Số lượng các cung trên đường đi
19.Đồ thị vô hướng liên thông là gì ?
Bất kì 2 đỉnh nào của đồ th? c?ng liên thông
2. Cho một đồ thị n đỉnh. Nếu biểu diễn đồ thị bằng ma trận kề thì ma trận kề đó:
Là ma trận có n hàng, n cột
20.Đồ thị G có n đỉnh và m cạnh với m khác n thì ma trận kề của G luôn có dạng:
A. là ma trận vuông cấp n B. là ma trận cấp nxm
C. là ma trận vuông cấp m D. là ma trận cấp mxn
21. Đồ thị vô hướng G có chu trình Euler khi và chỉ khi:
A. G liên thông và mọi đỉnh thuộc G có bậc chẵn
B. B. mọi đỉnh thuộc G có bậc chẵn C. C. G cóchu trìnhHamilton D. D. G là liên thông
22. Đồ thị G là liên thông khi và chỉ khi: 18
Trường Đại Học Sư Phạm Kỹ Thuật Vĩnh Long
A. G là đồ thị có hướng
B. G là đồ thị vô hướng
C. Có đường đi giữa hai đỉnh bất kỳ thuộc G D. G có đường đi Eule 19