lOMoAR cPSD| 45469857
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Phần 1. Cấu trúc dữ liệu cơ bản và cấu trúc dữ liệu trừu tượng (STACK, QUEUE) Câu
1. Các thuộc tính của một kiểu dữ liệu a. Tên kiểu dữ liệu b. Miền giá trị
c. Kích thước lưu trữ, Tập các toán tử tác động lên kiểu dữ liệu
d. Tất cả các thuộc tính đưa ra
Câu 2. Miền giá trị của Kiểu số nguyên là: a. -32767 .. 32768 b. 0..32768 c. -32768 .. 32767 d. 0..32767
Câu 3. Kích thước lưu trữ kiểu số nguyên là a. 2 byte b. 4 byte c. 1 byte d. 6 byte
Câu 4. Tập các toán tử kiểu số nguyên là
a. + , -, *, /, %, các phép so sánh
b. + , -, *, /, %, các phép so sánh, div ,mod c. + , -, *, /, % d. + , -, *, /, % ,true,false
Câu 5. Tên kiểu nguyên trong hệ kiểu pascal là: a. Integer b. Byte c. Real lOMoAR cPSD| 45469857 d. Boolean Câu 6. Khi khai báo: type T = min..max
Trong đó min và max là cận dưới và cận trên của khoảng T là kiểu gì? a. Kiểu đoạn con b. Kiểu liệt kê c. Kiểu integer d. Không có kiểu này
Câu 7. Khi khai báo trong hệ kiểu pascal
type T = (obj1, obj2,..., objn)
obj1, obj2,..., objn là các đối tượng nào đó T là kiểu gì? a. Kiểu liệt kê b. Kiểu đoạn con c. Kiểu integer d. Kiểu liệt kê e. Không có kiểu này
Câu 8. Đâu là kiểu dữ liệu có cấu trúc trong hệ kiểu pascal a. Kiểu array (mảng) b. Kiểu record (bản ghi) c. Kiểu con trỏ
d. Tất cả các kiểu đưa ra
Câu 9. Dấu hiệu nào dưới đây cho biết danh sách liên kết đơn L là rỗng:
A. (L->left == NULL) B. (L->ìnfor == NULL) C. (L->next == NULL) D. (L == NULL)
Câu 10. Để truy nhập vào từng phần tử trong danh sách móc nối đơn ta phải bắt đầu từ: a.
Phần tử đầu tiên của danh sách
b. Truy nhập trực tiếp vào phần tử đó giống mảng 1 chiều
c. Thực hiện tìm kiếm nhị phân trên danh sách móc nối đơn lOMoAR cPSD| 45469857
d. Thực hiện tìm kiếm tuần tự từ phần tử cuối dãy
Câu 11. Để tiện cho việc quản lý một danh sách móc nối đơn, ta cần phải quản lý
a. Địa chỉ phần tử đầu danh sách
b. Địa chỉ phần tử cuối danh sách
c. Thành phần thông tin của nút đầu danh sách. d. Cả a và b
Câu 12. Trong danh sách móc nối đơn, để tìm kiếm một phần tử có khoá X, ta phải thực hiện tìm kiếm: a. Tìm kiếm tuyến tính b. Tìm kiếm nhị phân
c. Tìm kiếm trên cây nhị phân
d. Có thể bắt đầu tìm trên một thành phần bất kỳ.
Câu 13. Giả sử pHead và pTail là hai con trỏ để trỏ đến phần tử đầu và cuối trong danh
sách móc nối đơn. Ban đầu danh sách rỗng. Để tạo danh sách móc nối đơn ta có thể sử
dụng cách nào trong các cách sau:
a. Chèn liên tiếp phần từ mới vào sau phần tử đang trỏ bởi pTail (chèn liên tiếp vào cuối danh sách)
b. Chèn liên tiếp phần tử mới vào đầu danh sách sau nút đang trỏ bởi pHead
c. Chèn liên tiếp phần tử mới vào giữa danh sách
d. Chèn liên tiếp phần tử mới vào trước nút trỏ bởi bởi pTail
Câu14. Với cấu trúc dữ liệu của danh sách liên kết đơn lưu trữ thông tin về phòng máy typedef struct PM { int maPM; int tongsoMay; } PHONGMAY; typedef struct Node { PHONGMAY Info; Node * PNext; } OneNode; typedef OneNode * SLLPointer;
Để quản lý danh sách liên kết đơn bằng phần tử đầu và phần tử cuối, cần định nghĩa kiểu dữ liệu: a. SLLPointer DanhSach; b. typedef struct SSLLIST { SLLPointer Phead; SLLPointer Ptail; } LIST; c. typedef struct SSLLIST lOMoAR cPSD| 45469857 { SLLPointer Phead; SLLPointer Ptail; int total; } LIST; d.typedef struct SSLLIST { SLLPointer Phead; int total; } LIST; Câu 15. Trong khai báo sau: Typedef struct SinhVien { char Ten[30]; int MaSV; } ; Typedef struct SinhVienNODE { Sinhvien Info; SinhvienNODE *PNext; }SV;
Thành phần con trỏ dùng để trỏ lưu địa chỉ của phần tử kế tiếp trong danh sách móc nối đơn là: a. PNext b. Ten c. MaSV d. Cả Ten, MaSV và Next. Câu 16. Trong khai báo Typedef struct NODE { int INFO; struct NODE *Next; } NODE p; Thì biến p là:
a. Con trỏ dùng để trỏ đến địa chỉ của biến động mà mỗi biến động này gồm 2 thành phần:
Thành phần INFO có giá trị nguyên và thành phần con trỏ Next b. Là địa chỉ của 1 nút
(phần tử) trong danh sách móc nối
c. Một nút (phần tử) trong danh sách móc nối
d. Một biến thuộc kiểu cấu trúc không được cấp phát vùng. lOMoAR cPSD| 45469857
Câu 17. Giải thuật Chèn phần tử có trường thông tin là X vào đầu danh sách thì thứ tự các thao tác sẽ là: Ở đây:
Getnode(P) là thủ tục xin cấp phát một biến động và cho con trỏ P trở tới
Info: Thành phần thông tin (trường thông tin hay dữ liệu) của nút một nút trong danh
sách pnext: Thành phần con trỏ dùng để móc nối đến biến động đứng sau trong danh sách l: danh sách
a. p= Getnode(X); p->pnext = l.Head→pnext; l.Head = p;
b. l.Head→pnext=p; p→pnext=l.head→pnext; p=Getnode(X);
c. p = Getnode(X); p→pnext=l.head→pnext; l.head→pnext=p;
d. p→pnext =l.head→pnext; l.head→pnext=p; p=getnode(X);
Câu 18. Giải thuật Chèn phần tử có trường thông tin là X vào Cuối danh sách thì thứ tự các thao tác sẽ là:
Ở đây: Thủ tục cấp phát một biến động và cho con trỏ p trỏ tới: Getnode(x)
pnext: Thành phần con trỏ dùng để móc nối đến biến động đứng sau trong danh sách l: danh sách
a. p=Getnode(X); l.PTail->pnext = new_ele; l.Tail = new_ele ;
b. l.PTail->pnext = new_ele; l.Tail = new_ele ; p=Getnode(X);
c. l.Tail = new_ele; l.PTail->pnext = new_ele ; p=Getnode(X);
d. l.PTail->pnext = new_ele ; p=Getnode(X); l.Tail = new_ele; Câu 19.
Thao tác nào dưới đây thực hiện trên ngăn xếp (stack): lOMoAR cPSD| 45469857
A. Thêm và loại bỏ phần tử luôn B. Thêm và loại bỏ phần tử có thể thực hiện tại
vị trí đỉnh (top) thực hiện tại vị trí bất kỳ
C. Thêm phần tử vào vị trí bất kỳ D. Loại bỏ phần tử tại vị trí bất kỳ Câu 20.
Thao tác nào dưới đây thực hiện trên hàng đợi (queue):
A. Thê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ỳ
Câu 21. Kiểu cấu trúc dữ liệu Queue hoạt động theo cơ chế nào a.FIFO. b.LIFO. c.LOFI. d.FOFI.
Câu 22. Cấu trúc dữ liệu nào tương ứng với LIFO a.Queue b.Linked List c.Tree d. Stack
Phần 2. Thuật toán và đánh giá độ phức tạp của thuật toán (15 câu)
Câu1. Chọn câu trả lời đúng nhất về thuật toán
a. Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán hoặc
hành động cần thực hiện để giải quyết vấn đề đặt ra
b. Thuật toán cần có một hoặc nhiều dữ liệu ra (output) ,dữ liệu vào (input).
c. Thuật toán là một dãy hữu hạn các bước, tất cả các phép toán có mặt trong các bước
của thuật toán phải đủ đơn giản.
d. Thuật toán là nòng cốt của chương trình
Câu 2. Đặc trưng của thuật toán:
a. Mỗi thuật toán có bộ dữ liệu vào ,ra tương ứng
b. Mỗi bước của thuật toán cần phải được mô tả một các chính xác
c. Tất cả các phép toán có mặt trong các bước của thuật toán phải đủ đơn giản d. Tất cả ý nêu ra
e. thuật toán phải dừng lại sau một số hữu hạn các bước cần thực hiện
Câu 3.Đặc trưng nào của thuật toán thể hiện: Tất cả các phép toán có mặt trong các bước
của thuật toán phải đủ đơn giản a. Tính xác định b. Tính dừng lOMoAR cPSD| 45469857 c. Tính khả thi d. Tính đúng đắn
Câu 4. sắp xếp theo thứ tự tăng dần của cấp thời gian thực hiện chương trình
a. O(1),O(log2n),O(n),O(nlog2n)
b. O(nlog2n),O(n),O(log2n),O(1)
c. O(log2n),O(n),O(nlog2n),O(1)
d. O(n),O(nlog2n),O(1),O(log2n)
Câu 5. Qui tắc tổng xác định độ phức tạp tính toán Giả sử T
(n) là thời gian thực hiện của hai giai đoạn chương trình P 1(n) và T2 1 và P2 mà T
(n) = O(g(n)) thì thời gian thực hiện đoạn P 1(n) = O(f(n)); T2
1 rồi P2 tiếp theo sẽ là a. T1(n)
+ T2( n) = O(max(f(n),g (n))).
b. T1(n) + T2( n) = O(Min(f(n),g (n))).
c. T1(n) + T2( n) = O((f(n)+g (n))).
d. T1(n) + T2( n) = O((f(n) or g (n))).
Câu 6. Trong một chương trình có 3 bước thực hiện mà thời gian thực hiện tưng bước lần
lượt là O(n2), O(n3) và O(nlog n). thời gian thực hiện chương trình sẽ là 2 a. O(n3) b. O(n2)+ O(n3) + O(nlog2n) c. O(n2) d. O(nlog2n)
Câu 7. Xác định độ phức tạp tính toán Nếu tương ứng với P
(n) = O(g(n)) thì thời gian thực hiện P
1 và P2 là T1(n) = O(f(n)), T2 1 và P2 lồng nhau sẽ là a. T1(n)T2( n) = O(f(n)g(n ))
b. T1(n)T2( n) = O(f(n)+g(n ))
c. T1(n)T2( n) = O(f(n)and g(n ))
d. T1(n)T2( n) = O(f(n)/g(n ))
Câu 8. Thời gian thực hiện các lệnh đơn : gán, đọc, viết là a. O(1) lOMoAR cPSD| 45469857 b. O(2) c. O(log2(n)) d. O(n)
Câu 9. Thời gian thực hiện lệnh hợp thành(Begin.. end) được xác định bởi a. quy tắc tổng b. Quy tắc nhân c. O(log2(n) d. Hằng số
Câu 10. Nếu S1 và S2 là các câu lệnh và E là biểu thức logic thì if E then S1 else S2
Giả sử thời gian thực hiện các lệnh S1, S2 là O(f(n)) và O(g(n)) tương ứng. Khi đó thời gian thực hiện lệnh if là a. O(max (f()n), g(n))) b. O(Min (f()n), g(n))) c. O(or( (f()n), g(n))) d. O(And (f()n), g(n)))
Câu 11. Nếu S là câu lệnh và E là biểu thức logic thì while E do S
Giả sử thời gian thực hiện lệnh S (thân của while) là O(f(n)) . Giả sử g(n) là số tối đa các
lần thực hiện lệnh while . Khi đó thời gian thực hiện lệnh while a. O(f(n)g(n)). b. O(max (f()n), g(n))) c. O(And (f()n), g(n))) d. Quy tắc tổng
Câu 12. Tính thời gian thực hiện của Hàm sau:
function Euclid (m, n : integer) :integer; var r : integer ; begin r := m mod n; (1)
while r<> 0 do (2) begin m := n; (3) n :=r; (4) r := m mod n; (5) end; Euclid := n; (6) lOMoAR cPSD| 45469857 end; a. O(log2n) b. 2log2n + 1 c. O(1) d. O(n) Câu 13. Cho Hàm sau:
function Euclid (m, n : integer) :integer; var r : integer ; begin r := m mod n; (1)
while r<> 0 do (2) begin m := n; (3) n :=r; (4) r := m mod n; (5) end; Euclid := n; (6) end;
lệnh (1) có thời gian thực hiện là a. O(1) b. O(n) c. O(2) d. O(m) Câu 14. Cho Hàm sau:
function Euclid (m, n : integer) :integer; var r : integer ; begin r := m mod n; (1)
while r<> 0 do (2) begin m := n; (3) n :=r; (4) r := m mod n; (5) end; Euclid := n; (6) end;
lệnh (6) có thời gian thực hiện là e. O(1) lOMoAR cPSD| 45469857 f. O(n) g. O(2) h. O(m)
Câu 15. Thời gian thực hiện lệnh đơn được xác định bởi a. Hằng số e. Quy tắc nhân f. O(log2(n) g. Quy tắc tổng
Phần 3. Giải thuật đệ quy, giải thuật sắp xếp và tìm kiếm (55 câu) Câu
1. Câu nào đúng nhất trong các câu sau:
a. Thuật toán tìm kiếm tuyến tính là thuật toán tiến hành so sánh phần tử cần tìm(x) lần
lượt với phần tử thứ nhất, thứ hai…..đến phần tử cuối cùng của mảng cho đến khi gặp
được phần tử có khoá cần tìm hoặc đến hết mảng mà không thấy x.
b. Thuật toán tìm kiếm tuyến tính là thuật toán rất đơn giản và cổ điển.
c. Thuật toán tìm kiếm tuyến tính là thuật toán tiến hành so sánh phần tử cần tìm(x) với
các phần tử của mảng cho đến khi gặp phần tử có khoá cần tìm hoặc đến hết mảng mà không thấy x.
Câu 2. Nhận xét sau đây, nhận xét nào đúng: a.
Giải thuật tìm kiếm tuyến tính không phụ thuộc vào thứ tự các phần tử của mảng,
do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một dãy số bất kỳ. b.
Thuật toán tìm kiếm tuyến tính dựa vào quan hệ của các phần tử mảng để định
hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được cho những dãy đã có thứ tự. c.
Giải thuật tìm kiếm tuyến tính phụ thuộc vào thứ tự các phần tử của mảng, do vậy
đây là phương pháp tìm kiếm tổng quát nhất.
Câu 3. Giả sử cho dãy số như sau: 4 6 6 7 3 8 7 2 8 7
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] Phần tử cần tìm x=7
Kết thúc giải thuật, phần tử X tìm thấy nằm ở vị trí a. Vị trí 4 lOMoAR cPSD| 45469857 b. Ví trí 7 c. Ví trí 12 d. Vị trí 4, 7, và 12
Câu 4. Xét mảng các số nguyên có nội dung sau: -9 -9 -9 -9 0 3 7 7 10 15
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
Cần tìm phần tử X= -9 bằng giải thuật tìm kiếm nhị phân. Phần tử -9 ở vị trí thứ mấy được
tìm thấy (vị trí 1, 2 3 hay 4): a. Vị trí 2 b. Vị trí 1 c. Vị trí 3 d. Vị trí 4 Câu 5.
Cho hàm tìm kiếm tuyến tính như sau int
TimKiem (int M[], int N, int X) { int k = 0; M[N] = X; while (M[k] != X) k++; if (k < N) return (k); return (-1); } Chọn câu đúng nhất:
a. Hàm sẽ trả về 0 nếu không tìm thấy phần tử có giá trị là X
b. Hàm sẽ trả về 1 nếu tìm thấy phần tử có giá trị lả X
c. Hàm sẽ trả về -1 nếu không tìm thấy phần tử có giá trị là X
d. Hàm sẽ trả về 1 nếu không tìm thấy phần tử có giá trị lả X
Câu 6. Xét thủ tục sau: int TimKiemNP (int M[], int First, int Last, int X) { if (First > Last) return (- 1);
int Mid = (First + Last)/2; if (X == M[Mid]) lOMoAR cPSD| 45469857 return (Mid); if (X < M[Mid])
return(TimKiemNP (M, First, Mid – 1, X)); else
return(TimKiemNP (M, Mid + 1, Last, X)); }
Lựa chọn câu đúng nhất để mô tả thủ tục trên
a. Thủ tục hỗ trợ tìm kiếm phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ First đến chỉ số Last
b. Thủ tục hỗ trợ tìm kiếm đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ số
từ First đến chỉ số Last
c. Thủ tục hỗ trợ tìm kiếm đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ số
từ Last đến chỉ số First
d. Thủ tục hỗ trợ tìm kiếm không đệ quy phần tử có giá trị là X trên mảng các phần tử từ
chỉ số từ Last đến chỉ số First
Câu 7: A và B chơi trò chơi đoán số, thể lệ như sau:
A nghĩ trong đầu 1 số nguyên dương X nằm trong khoảng từ 0 đến 100.
B phải đoán xem A đang nghĩ số bao nhiêu bằng cách đặt câu hỏi bạn cho A
A phải trả lời trung thực bằng 1 trong các đáp án: Lớn hơn, nhỏ hơn, bằng
Hỏi B phải hỏi ít nhất là mấy lần và dùng phương pháp tìm kiếm gì mà B có thể đoán đúng số A đang nghĩ:
a. 7 lần hỏi và dùng tìm kiếm nhị phân
b. X lần hỏi và dùng phương pháp tìm kiếm tuần tự
c. Không thể đoán được A đang nghĩ trong đầu số gì d. Mất 100 lần hỏi. Câu 8
Cho đoạn chương trình sau:
Int timkiem(int a[], int N, int x) { Int i=0;
While ((iIf (i= =N) return -1; Else return i; }
Với mảng a= {5,10,20,40,68, 86}; N=6; x=20. Đoạn chương trình trên cho lại giá trị là: a. -1 b. 1 c. 3 d. 6 Câu 9.
Cho đoạn chương trình sau:
Int timkiemtuantu(int a[], int N, int x) { lOMoAR cPSD| 45469857 Int i=0; a[N]=x; while (a[i]!=x) i++; if (i= = N ) return - 1; else return i ; }
Với tham số thực như sau a={4,4,6,7,8,9}; N=6; x= 4. Chương trình trên sẽ cho lại giá trị là: a. -1 b. 1 c. 4 d. 2 Câu 10.
Cho đoạn chương trình như sau:
Int timkiem_NP(int a[], int N, int x) { Int left=0, right=N-1, mid; Do { mid = (eft+right)/2; if(x=a[mid]) return mid; else if(xelse left= mid+1; } while (left<=right); Return -1 }
Với tham số thực truyền vào hàm trên như sau: a={20,85, 90, 68, 78, 90}; x= 90 đoạn
chương trình trên sẽ trả lại giá trị mid bằng bao nhiêu? a. -1 b. 2 c. 5 d. 6 Câu 11.
Kết quả nào đúng khi thực hiện giải thuật sau với a[]= {-3, -3, 15, -3}; n= 4; x= -3:
int FindX(int a[], int n, int x) A. 1 {int i; B. 2
for (i= n; i>= 1; i--) if (a[i]==x) return C. 3 (i); D. 4 return (-1); }
Câu 12. Tư tưởng chính của giải thuật chọn trực tiếp là: a.
Ở lượt thứ i ta sẽ chọn trong dãy a[i], a[i+1], …, a[n] phần tử nhỏ nhất và đổi
chỗ nó với a[i]. Như vậy sau j đợt, j khoá nhỏ hơn đã lần lượt ở các vị trí thứ nhất, thứ 2,
…, thứ j theo đúng thứ tự sắp xếp. lOMoAR cPSD| 45469857 b.
Giả sử có dãy A[1], A[2],…, A[n], trong đó i phần tử đầu A[1], …, A[i-1] đã
được sắp xếp. Tìm vị trí để đưa phần tử A[i] vào vị trí thích hợp của đoạn đã được sắp
xếp để được dãy A[1], A[2],…, A[i] có thứ tự. c.
Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kề cận để đưa phần tử nhỏ hơn
trong cặp phần tử đó về vị trí đúng đầu dãy hiện hành, sau đó không xét đến nó ở bước
tiếp theo. Do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i (phần tử ở vị trí i ở đúng vị trí). d.
Tại bước thứ i, xét phần tử thứ a[i].Với mỗi phần tử a[i], xét các phần tử a[j]
nằm sau nó (j=i+1…n). Nếu a[i]>a[j] thì đổi chỗ a[i] cho a[j]
Câu 13. Tư tưởng của 1 giải thuật sắp xếp như sau:
Giả sử có dãy A[1], A[2],…, A[n], trong đó i phần tử đầu A[1], …, A[i-1] đã được sắp
xếp. Tìm vị trí để đưa phần tử A[i] vào vị trí thích hợp của đoạn đã được sắp xếp để được
dãy A[1], A[2],…, A[i] có thứ tự. Hỏi giải thuật trên có tên gọi là gì: a. Chèn trực tiếp (Insertion Sort)
b. Chọn trực tiếp (Selection Sort) c. Nổi bọt (Bubble Sort)
d. Sắp xếp nhanh (Quick Sort)
Câu 14. Đối với thuật toán sắp xếp chọn trực tiếp cho dãy các phần tử sau (10 pt) 16 60 2 25 15 45 5 30 33 20
Cần thực hiện ..................... chọn lựa phần tử nhỏ nhất để sắp xếp mảng M có thứ tự tăng dần. a. 7 lần b. 8 lần c. 9 lần d. 10 lần
Câu 15. Giả sử cần sắp xếp mảng M có N phần tử sau theo phương pháp sắp xếp chèn trực tiếp 11 16 12 75 51 54 5 73 36 52 98
Cần thực hiện ..................... chèn các phần tử vào dãy con đã có thứ tự tăng đứng đầu dãy
M để sắp xếp mảng M có thứ tự tăng dần. a. 9 lần b. 10 lần c. 8 lần d. 7 lần
Câu 16. 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ử: a.
Đi từ cuối mảng về đầu mảng, trong quá trình đi nếu phần tử ở dưới (đứng phía
sau) nhỏ hơn phần tử đứng ngay trên (trước) nó thì hai phần tử này sẽ được đổi chỗ cho
nhau. Sau mỗi lần đi chúng ta đưa được một phần tử trồi lên đúng chỗ. Sau N–1 lần đi thì
tất cả các phần tử trong mảng M sẽ có thứ tự tăng. b.
Đi từ đầu mảng về cuối mảng, trong quá trình đi nếu phần tử ở dưới (đứng phía
sau) nhỏ hơn phần tử đứng ngay trên (trước) nó thì hai phần tử này sẽ được đổi chỗ cho lOMoAR cPSD| 45469857
nhau. Sau mỗi lần đi chúng ta đưa được một phần tử trồi lên đúng chỗ. Sau N lần đi thì tất
cả các phần tử trong mảng M sẽ có thứ tự tăng. c.
Đi từ cuối mảng về đầu mảng, trong quá trình đi nếu phần tử ở dưới (đứng phía
sau) nhỏ hơn phần tử đứng ngay trên (trước) nó thì hai phần tử này sẽ được đổi chỗ cho
nhau. Sau mỗi lần đi chúng ta đưa được một phần tử trồi lên đúng chỗ. Sau N lần đi thì tất
cả các phần tử trong mảng M sẽ có thứ tự tăng. d. Cả a, b, c đều sai
Câu 17. Hàm mô tả sắp xếp nổi bọt (Bubble Sort) trên mảng M có N phần tử
void BubbleSort(int M[], int N) [1] { [2] int Temp; [3]
for (int I = 0; I < N-1; I++) [4]
………………………………….. [5] if (M[J] < M[J-1]) [6] { [7] Temp = M[J]; [8] M[J] = M[J-1]; [9] M[J-1] = Temp; [10] } [11] return; [12] } [13]
Lệnh nào sau đây sẽ được đưa vào dòng lệnh thứ [5] của thủ tục a.
for (int J = N-1; J > I; J++) b.
for (int J = N; J < I; J--) c.
for (int J = N-1; J > I; J--) d.
Không có dòng lệnh nào phù hợp, không cần thêm vào thuật toán vẫn chạy đúng Câu
18. Cho 1 dãy gồm các phần tử như sau: 9 6 8 2 5 3 4 7 1 10
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
Sử dụng giải thuật Quick sort để sắp xếp dãy số trên. Giả sử chọn phần tử ở giữa làm khoá
(phần tử chốt) a[5] thì sau khi phân hoạch thành 2 dãy con, ta được dãy nào sau đây?
a. 1, 4, 3, 2, 5, 8, 6, 7, 9, 10
b. 9, 6, 8, 2, 5, 3, 4, 7, 1, 10
c. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
d. 1, 6, 8, 2, 5, 3, 4, 7, 9, 10
Câu 19. Cho 1 dãy gồm các phần tử như sau: lOMoAR cPSD| 45469857 6 8 2 7 5 3 4 1 10 14
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
Sử dụng giải thuật Quick sort để sắp xếp dãy số trên. Giả sử chọn phần tử ở giữa làm khoá
(phần tử chốt) a[5] thì ở lần đổi chỗ đầu tiên ta phải đổi chỗ như thế nào? a. Đổi chỗ A[1] cho A[8]
b. Đổi chỗ A[1] cho A[10] c. Đổi chỗ A[4] và A[6] d. Đổi chỗ A[2] cho A[7]
Câu 20. Hiệu quả của giải thuật sắp xếp Quick sort phụ thuộc vào việc chọn phần tử mốc
(khoá). Trường hợp tốt nhất xảy ra nếu mỗi lần phân hoạch đều chọn được phần tử
Median (phần tử trung vị làm khoá). Phần tử Meadian là phần tử:
a. Phần tử lớn hơn (hay bằng) một nửa số phần tử và nhỏ hơn (hay bằng) nửa số phần tử còn lại
b. Phần tử nằm ở giữa dãy
c. Phần tử nằm ở đầu dãy
d. Phần tử nằm ở cuối dãy
Câu 21. Trong các giải thuật sau, thì nhóm các giải thuật nào có cùng độ phức tạp tính toán trung bình là O(n2)
a. Quick Sort, Heap Sort và Merge Sort
b. Quick Sort, Heap Sort và Bubble Sort
c. Selection Sort, Heap Sort và Merge Sort
d. Insertion Sort, Bubble Sort và Selection Sort
Câu 22. ý tưởng phương pháp sắp xếp chọn tăng dần (select sort)
a. Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy.
b. Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần
tử nào bé hơn được cho lên vị trí trên.
c. Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn hơn,
cho đến khi thu được dãy ban đầu đã được sắp xếp.
d. Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất với
phần tử thứ nhất; Tương tự đối với phần tử nhỏ thứ hai,ba...
Câu 23. ý tưởng phương pháp sắp xếp nổi bọt (bubble sort) là: a.
Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy bằng
cách đẩy các phần tử lớn hơn xuống. b.
Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất
với phần tử thứ nhấ; Tương tự đối với phần tử nhỏ thứ hai,ba... lOMoAR cPSD| 45469857 c.
Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu
phần tử nào nhỏ hơn được đứng vị trí trên. d.
Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn
hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.
Câu 24. Ý tưởng phương pháp sắp xếp chèn (insertion sort) là: a.
Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu
phần tử nào nhỏ hơn được đứng vị trí trên. b.
Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất
với phần tử thứ nhấ; Tương tự đối với phần tử nhỏ thứ hai,ba... c.
Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy bằng
cách đẩy các phần tử lớn hơn xuống. d.
Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn
hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.
Câu 25. ý tưởng phương pháp sắp xếp nhanh (Quick sort) là: a.
Lần lượt chia dãy phần tử thành hai dãy con bởi một phần tử khoá (dãy con trước
khoá gồm các phần tử nhỏ hơn khoá và dãy còn lại gồm các phần tử lớn hơn khoá). b.
Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu
phần tử nào nhỏ hơn được đứng vị trí trên. c.
Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất
với phần tử thứ nhấ; Tương tự đối với phần tử nhỏ thứ hai,ba... d.
Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn
hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.
Câu 26. Phương pháp sắp xếp nhanh (Quick sort) chính là phương pháp: a. Phân đoạn b. Trộn c. Chèn d. Vun đống
Câu 27. ý tưởng phương pháp sắp xếp Trộn (Merge sort) là: a.
Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn
hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp. b.
Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu
phần tử nào nhỏ hơn được đứng vị trí trên. lOMoAR cPSD| 45469857 c.
Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất
với phần tử thứ nhất; Tương tự đối với phần tử nhỏ thứ hai,ba... d.
Lần lượt chia dãy phần tử thành hai dãy con bởi một phần tử khoá (dãy con trước
khoá gồm các phần tử nhỏ hơn khoá và dãy còn lại gồm các phần tử lớn hơn khoá).
Câu 28. ý tưởng phương pháp sắp xếp vun đống (Heap sort) là:
a. Lần lượt tạo đống cho cây nhị phân (phần tử gốc có giá trị lớn nhất) và loại phần tử
gốc ra khỏi cây đưa vào dãy sắp xếp.
b. Tạo đống cho cây nhị phân (cây nhị phân đã được sắp xếp giảm dần).
c. Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần
tử nào nhỏ hơn được đứng vị trí trên.
d. Lần lượt chia dãy phần tử thành hai dãy con bởi một phần tử khoá (dãy con trước khoá
gồm các phần tử nhỏ hơn khoá và dãy còn lại gồm các phần tử lớn hơn
Câu 29. Cây nhị phân tìm kiếm là:
a. Cây nhị phân mà mỗi nút trong cây đều thoả tính chất: giá trị của nút cha nhỏ hơn mọi
nút trên cây con trái và lớn hơn mọi nút trên cây con phảI của nó.
b. Cây nhị phân mà mỗi nút trong cây đều thoả tính chất: giá trị của nút cha lớn hơn giá trị của hai nút con.
c. Cây nhị phân thoả tính chất heap
d. Là cây nhị phân đầy đủ.
Câu 30. Trong các giải thuật sắp xếp, giải thuật nào áp dụng phương pháp Chia để trị? a. Quick sort, Merge sort b. Quick sort, Heap sort c. Quick sort, Bubble sort d. Qucick sort, Insert sort
Câu 31.Thủ tục sau áp dụng giải thuật sắp xếp nào? Procedure F Begin For i:=1 to (n-1) do For j:=n downto (i+1) do if a[j] < a[j-1] then begin tg:=a[j]; a[j]:=a[j- 1]; a[j-1]:=tg; end; End; lOMoAR cPSD| 45469857 a. Bubble sort b. Select sort c. insert sort d. Merge sort
Câu 32. Thủ tục sau áp dụng giải thuật sắp xếp nào? Procedure F Begin a[0]:=- ∞;
for i:=2 to n do begin x:=a[i]; j:=i-
1; while xa[j+1]:=a[j]; j:=j-1; end; a[j+1]:=x; end; End; a. Insert sort b. Select sort c. Bubble sort d. Merge sort
Câu 33. Thủ tục sau áp dụng giải thuật sắp xếp nào? Procedure F(X,b,m,n,Z)
Begin i:=k; i:=b; j:=m+1; while i<=m and j<=n do if
x[i] <=x[j] then begin z[k]:=x[i]; i:=i+1; end
else begin z[k]:=x[j]; j:=j+1; end; k:=k+1; if i>m then (z ,…,z ,…,x k n):= (xj n) else (z ,…,z ,…,x k n):= (xi n) End; a. Merge sort b. Select sort c. Bubble sort d. Insert sort
Câu34. Thủ tục sau áp dụng giải thuật sắp xếp nào? Procedure F(a, t, s); Begin B:= true;
if tdo begin i:=i+1; while a[i]<=key do i:=i+1;
j:=j -1; while a[j]>=key do j:=j-1; if i lOMoAR cPSD| 45469857
begin tg:=a[i]; a[i]:=a[j]; a[j]:=tg; end else b:=false; end;
tg:=a[t]; a[t]:=a[j]; a[j]:=tg; call F(a, t,j-1); cal F(a, j+1,s); end; End; a. Quick sort b. Merge sort c. Bubble sort d. Insert sort
Câu 35. Cho dãy số {6 1 3 0 5 7 9 2 8 4}. áp dụng phương pháp sắp xếp lựa chọn
(Select sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 1 3 6 5 7 9 2 8 4}.
Dãy số thu được sau lần lặp thứ hai là: a. {0 1 2 6 5 7 9 3 8 4} b. {0 1 2 6 5 7 9 3 4 8} c. {0 1 2 3 4 5 6 7 8 9} d. {0 1 3 6 5 7 9 2 8 4}
Câu 36. Cho dãy số {6 1 3 0 5 7 9 2 8 4}. áp dụng phương pháp sắp xếp lựa chọn
(Select sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 1 3 6 5 7 9 2 8 4}.
Dãy số thu được sau lần lặp thứ ba là: a. {0 1 2 3 6 5 7 9 8 4} b. {0 1 2 6 5 7 9 3 4 8} c. {0 1 2 3 4 5 6 7 8 9} d. {0 1 2 6 5 7 9 3 8 4}
Câu 37. Cho dãy số {6 1 3 0 5 7 9 2 8 4}. áp dụng phương pháp sắp xếp lựa chọn
(Select sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 1 3 6 5 7 9 2 8 4}.
Dãy số thu được sau lần lặp thứ tư là: a. {0 1 2 3 5 7 9 6 8 4} b. {0 1 2 3 6 5 7 9 8 4} c. {0 1 2 3 5 7 9 4 8 6} d. {0 1 2 3 4 5 6 7 8 9}