thumbnail

Tổng Hợp Đề Ôn Luyện Cấu Trúc Dữ Liệu và Giải Thuật - Miễn Phí, Có Đáp Án

Bộ đề ôn luyện Cấu Trúc Dữ Liệu và Giải Thuật (CTDL & GT) miễn phí, bao gồm các câu hỏi đa dạng kèm đáp án chi tiết. Phù hợp cho sinh viên ngành công nghệ thông tin muốn củng cố kiến thức về thuật toán, cấu trúc dữ liệu, và giải quyết bài toán lập trình. Công cụ hữu ích để ôn tập và chuẩn bị tốt nhất cho kỳ thi.

Từ khoá: cấu trúc dữ liệu giải thuật đề thi online ôn thi công nghệ thông tin học thuật toán luyện thi lập trình CTDL & GT đề thi có đáp án bài kiểm tra lập trình ôn tập thuật toán

Số câu hỏi: 279 câuSố mã đề: 7 đềThời gian: 1 giờ

31,117 lượt xem 2,390 lượt làm bài


Chọn mã đề:


Bạn chưa làm Mã đề 1!!!

 

Xem trước nội dung:

Câu 1: 0.25 điểm

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 2: 0.25 điểm
"Khi lưu trữ cây nhị phân dưới dạng mảng, nếu vị trí của nút cha trong mảng là i thì vị trí của nút con phải là gì trong các phương án sau?"
A.  
"i+1"
B.  
"i-1"
C.  
"2*i"
D.  
"2*i + 1"
Câu 3: 0.25 điểm
Một giá trị kiểu char chiếm bao nhiêu bộ nhớ
A.  
1byte
B.  
2byte
C.  
3byte
D.  
4byte
Câu 4: 0.25 điểm
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 6 5 7 9 3 8 4}
B.  
{0 1 2 3 6 5 7 9 8 4}
C.  
{0 1 2 6 5 7 9 3 4 8}
D.  
{0 1 2 3 4 5 6 7 8 9}
Câu 5: 0.25 điểm
"Khi lưu trữ cây nhị phân dưới dạng mảng, nếu vị trí của nút cha là i thì vị trí của nút con trái là gì trong các phương án sau?"
A.  
"i+1"
B.  
"i-1"
C.  
"2*i"
D.  
"2*i + 1"
Câu 6: 0.25 điểm
"Hãy cho biết ý tưởng nào sau đây nói về tưởng phương pháp sắp xếp Trộn (Merge sort)?"
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."
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 cho đến phần tử cuối cùng."
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 7: 0.25 điểm

Câu 120: Cho hàm đệ qui sau : Function A(n:integer):integer  Begin     if n<=2 then    A:=1                        else                                   A := A(n-2) + A(n-1);  End;
Khi n=8, giá trị của hàm trả về bằng bao nhiêu 

A.  
5
B.  
8
C.  
13
D.  
21
Câu 8: 0.25 điểm
Cho Stack gồm 5 phần tử {12, 5, 20, 23, 72}, trong đó 72 là phần tử ở đỉnh Stack. Để lấy ra phần tử thứ 4 trong Stack ta phải thực hiện theo phương án nào?
A.  
"POP(72), POP(23), POP(72)."
B.  
"POP(23), PUSH(23), POP(72)."
C.  
"POP(72), POP(23), PUSH(72).
D.  
"POP(23), PUSH(72), POP(72)."
Câu 9: 0.25 điểm
Giả sử S là ngăn xếp các phần tử của nó có kiểu Item và X là một phần tử có cùng kiểu với các phần tử của ngăn xếp Thủ tục sau làm nhiệm vụ gì?  procedure Initialize (var S : Stack);  begin    S.top := 0;  end;  
A.  
Khởi tạo stack rỗng
B.  
Khởi tạo stack có giá trị bằng 0
C.  
Kiểm tra stack có phần tử bằng 0 hay không?
D.  
Thêm phần tử vào danh sách
Câu 10: 0.25 điểm
Khi khai báo type T = (obj1, obj2,..., objn) .Trongđó 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.  
Không có kiểu này
Câu 11: 0.25 điểm
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(n^{2}), O(n3)O(n^{3}) và O(nlog2n)O(n \log_{2} n). thời gian thực hiệen chương trình sẽ là: Chú ý: log2n\log_{2} n = Log cô só 2 của n; n2n^{2} = n mũ 2
A.  
O(n3)O(n^{3})
B.  
O(n2)+O(n3)+O(nlog2n)O(n^{2}) + O(n^{3}) + O(n \log_{2} n)
C.  
O(n2)O(n^{2})
D.  
O(nlog2n)O(n \log_{2} n)
Câu 12: 0.25 điểm
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 13: 0.25 điểm
Thời gian thực hiện của giải thuật `Exp2`: Chú ý: log2n\log_{2} n = Log cô só 2 của n; n2n^{2} = n mũ 2.
A.  
O(n)O(n)
B.  
O(n2)O(n^{2})
C.  
O(n3)O(n^{3})
D.  
O(1)O(1)
Câu 14: 0.25 điểm

Câu 130: 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 15: 0.25 điểm
Cho dãy số {4 0 2 8 5 9 6 1 3 7}. áp dụng phương pháp sắp xếp chèn (Insert sort) sau lần lặp đầu tiên của giải thuật ta có kết quả:{0 4 2 8 5 9 6 1 3 7}. Dãy số thu được sau lần lặp thứ hai là:?
A.  
{0 2 4 8 5 9 6 1 3 7}
B.  
{0 4 2 8 5 9 6 1 3 7}
C.  
{0 1 2 8 5 9 6 4 3 7}
D.  
{0 1 4 8 5 9 6 1 3 7}
Câu 16: 0.25 điểm
Tư tưởng của giải thuật tìm kiếm tuần tự
A.  
So sánh X lần lượt với các phần tử thứ nhất, thứ hai,... của dãy cho đến khi gặp phần tử có khoá cần tìm
B.  
Tại mỗi bước tiến hành so sánh X với phần tử ở giữa của dãy,Dựa vào bước so sánh này quuyết định giới hạn dãy tìm kiếm nằm ở nửa trên, hay nửa dưới của dãy hiện hành
C.  
Dựa vào Tư tưởng chia để trị .
Câu 17: 0.25 điểm
"Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp chèn (insertion sort)?"
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; Tương tự đối với phần tử nhỏ thứ hai cho đến phần tử cuối cùng."
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.  
"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."
Câu 18: 0.25 điểm
"Hãy cho biết phương pháp nào sau đây để loại bỏ nút X trên cây nhị phân tìm kiếm, với X là một phần tử bất kỳ?"
A.  
"Tìm nút chứa khoá lớn nhất trong cây con phải, đưa giá trị chứa trong đó sang nút X , rồi xoá X."
B.  
"Tìm nút chứa khoá lớn nhất trong cây con trái, đưa giá trị chứa trong đó sang nút X , rồi xoá X."
C.  
"Chỉ việc xoá X, vì X không liên quan đến phần tử nào khác."
D.  
"Không thể xoá X ra khỏi cây nhị phân tìm kiếm."
Câu 19: 0.25 điểm
Ý nghĩa của đoạn mã sau là gì?  Const max= 100;Stack= Record element : Array[1..max] Of integer;  top: 0..max;End;Var S: Stack; 
A.  
Cài đặt ngăn xếp kiểu con trỏ
B.  
Cài đặt ngăn xếp kiểu mảng
C.  
Cài đặt ngăn xếp kiểu danh sách liên kết
D.  
Khởi tạo stack có 100 bản ghi
Câu 20: 0.25 điểm
Cho giải thuật đệ quy sau: Function F(n)  Begin    if n<=2 then    F:=1    else F(n) := F(n-2) + F(n-1); End;  Trường hợp suy biến xảy ra khi nào?  
A.  
F(1) = 1
B.  
F(2) = 1
C.  
F(1) = 1 và F(2) = 1
D.  
F(1) = 0 và F(2) = 1
Câu 21: 0.25 điểm
Khi bổ sung một phần tử mới vào hàng đợi cần kiểm tra
A.  
Hàng đợi có đầy không
B.  
Hàng đợi có rỗng không
C.  
Hàng đợi có bao nhiêu phần tử
D.  
Hàng đợi có bao nhiêu giá trị bằng 0
Câu 22: 0.25 điểm
Ta có thể tạo một cây nhị phân tìm kiếm bằng cách:
A.  
Lặp đi lặp lại quá trình thêm 1 phần tử vào một cây rỗng
B.  
Chọn 1 phần tử bất kỳ làm gốc. Các phần tử có giá trị nhỏ hơn gốc được đưa sang trái, các phần tử có giá trị lớn hơn gốc đưa sang cây con phải
C.  
Phải tạo cây nhị phân tìm kiếm tuỳ theo yêu cầu của bài toán
D.  
Không có đáp án đúng.
Câu 23: 0.25 điểm
"Chọn phương án cho biết đối tượng T là kiểu gì trong khai báo sau?Var T : array[1..10] of real;"
A.  
"Là kiểu mảng."
B.  
"Là kiểu đoạn con."
C.  
"Là kiểu real."
D.  
"Là kiểu liệt kê."
Câu 24: 0.25 điểm

Câu 92: Cho đoạn mã sau. Hàm IsEmpty bằng giá trị nào khi stack rỗng. 

 function IsEmpty( S : Stack) : Boolean;

 begin 

   IsEmpty:= (S.top = 0);

 end;   

A.  
False
B.  
True
C.  
0
D.  
1
Câu 25: 0.25 điểm
Giả sử S là ngăn xếp các phần tử của nó có kiểu Item và X là một phần tử có cùng kiểu với các phần tử của ngăn xếp Thủ tục sau làm nhiệm vụ gì  procedure B ( var S : Stack, X : Item);  begin    with S do        if Full(S) then writeln(' Stack is full now')        else begin            top := top + 1;            E[top] := X;        end;  end;  
A.  
Thêm một phần tử mới vào đỉnh ngăn xếp
B.  
Loại bỏ phần tử ở đỉnh của ngăn xếp
C.  
Xử lý với nhiều ngăn xếp.
D.  
Kiểm tra ngăn xếp có đầy không
Câu 26: 0.25 điểm
Cho dãy số: 4 7 0 9 2 5 3 1 8 6 và các bước sắp xếp sau:                      Bước 1: 0 4 7 1 9 2 5 3 6 8                      Bước 2: 0 1 4 7 2 9 3 5 6 8                      Bước 3: 0 1 2 4 7 3 9 5 6 8                      Bước 4: 0 1 2 3 4 7 5 9 6 8                      Bước 5: 0 1 2 3 4 5 6 7 8 9 Các bước trên dựa theo giải thuật sắp xếp nào?
A.  
Bubble sort
B.  
Insert sort
C.  
Quick sort
D.  
Select sort
Câu 27: 0.25 điểm

Câu 201: "Hãy chọn phương án đúng về độ phức tạp thời gian thực hiện câu lệnh (1)? 

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;"

A.  
"O(n)"
B.  
"O(2)"
C.  
"O(m)"
D.  
"O(1)"
Câu 28: 0.25 điểm
Cho dãy số {3 1 6 0 5 4 8 2 9 7}. áp dụng phương pháp sắp xếp nhanh (Quick sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {(0 1 2) 3 (5 4 8 6 9 7)}. Dãy số thu được sau lần lặp thứ hai là:?
A.  
{0 (1 2) 3 (5 4 8 6 9 7)}
B.  
{(0 1 2) 3 (5 4 8 6 9 7)}
C.  
{(3 1 6 0) 5 (4 8 2 9 7)}
D.  
{(0 1 2 3) 4 (5 6 7 8 9)}
Câu 29: 0.25 điểm
"Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp nổi bọt (bubble 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ằ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; Tương tự đối với phần tử nhỏ thứ hai cho đến phần tử cuối cùng."
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 30: 0.25 điểm
Cho dãy số {3 1 6 0 5 4 8 2 9 7}. áp dụng phương pháp sắp xếp nhanh (Quick sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {(0 1 2) 3 (5 4 8 6 9 7)}. Dãy số thu được sau lần lặp thứ bốn là:?
A.  
{0 1 2 3 (4) 5 (8 6 9 7)}
B.  
{0 1 (2) 3 (5 4) 8 (6 9 7)}
C.  
{(3) 1 (6 0) 5 (4 8) 2 (9 7)}
D.  
{(0) 1 (2 3) 4 (5 6) 7 (8 9)}
Câu 31: 0.25 điểm
Ba lệnh (3), (4) và (5) trong hàm `Euclid` có thời gian thực hiện là: Chú ý: log2n\log_{2} n = Log cô só 2 của n; n2n^{2} = n mũ 2.
A.  
O(1)O(1)
B.  
O(n)O(n)
C.  
O(m)O(m)
D.  
O(n2)O(n^{2})
Câu 32: 0.25 điểm
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âu 33: 0.25 điểm
"Trong biểu diễn dữ liệu dưới dạng cây, nút có cấp bằng 0 gọi là nút gì trong các phương án sau?"
A.  
"Là nút lá."
B.  
"Là nút gốc."
C.  
"Là phần tử cuối cùng trong cây."
D.  
"Là phần tử đầu cùng trong cây."
Câu 34: 0.25 điểm
Ngôn ngữ diễn đạt giải thuật là phương án nào sau đây:
A.  
Ngôn ngữ liệt kê từng bước.
B.  
Sơ đồ khối.
C.  
Ngôn ngữ lập trình.
D.  
Cả A, B, C đều đúng.
Câu 35: 0.25 điểm
"Để loại bỏ một đối tượng ra khỏi Stack, ta dùng hàm nào sau đây?"
A.  
"PUSH(x)"
B.  
"EMPTY(x)"
C.  
"FULL(x)"
D.  
"POP(x)"
Câu 36: 0.25 điểm
Cho giải thuật đệ quy của bài toán "Tháp Hà Nội",Procedure Chuyen(n, A, B, C)  Begin     if n=1 then chuyển đĩa từ A sang C     else begin         call Chuyen(n-1, A, C, B);         call Chuyen(1, A, B, C);         call Chuyen(n-1, B, A, C) ; end;End;
Khi n=5 thì số bước chuyển đĩa bằng bao nhiêu?
A.  
15
B.  
31
C.  
63
D.  
127
Câu 37: 0.25 điểm
Lệnh (1) trong hàm `Euclid` có thời gian thực hiện là:
A.  
O(1)O(1)
B.  
O(n)O(n)
C.  
O(2)O(2)
D.  
O(m)O(m)
Câu 38: 0.25 điểm
cho dãy a = (12,2,8,5,1,6,4,15) các bước sắp xếp như sau:  Bước 1: 1 2 8 5 12 6 4 15  Bước 2: 1 2 8 5 12 6 4 15  Bước 3: 1 2 4 5 12 6 8 15  Bước 4: 1 2 4 5 12 6 8 15  Bước 5: 1 2 4 5 6 12 8 15  Bước6: 1 2 4 5 6 8 12 15  Bước 7: 1 2 4 5 6 8 12 15  Các bước trêndựa theo phương pháp sắp xếp kiểu gì: 
A.  
Sắp xếp chọn(selection sort)
B.  
Sắp xếp chèn(insertion sorr)
C.  
Sắp xếp nổi bọt(bubble sort)
D.  
Sắp xếp nhanh(quick sort)
Câu 39: 0.25 điểm
giải thuật đệ quy của bài toán Tháp Hà Nội như sau: Procedure Chuyen(n, A, B, C)  Begin    if n=1 then chuyển đĩa từ A sang C    else begin        call Chuyen(n-1, a, C, B);        call Chuyen(1, A, B, C);    call Chuyen(n-1, B, A, C);    end;  End;     Trường hợp suy biến xảy ra khi nào?
A.  
N=1
B.  
N=2
C.  
N=0
D.  
N=3
Câu 40: 0.25 điểm

Câu 131: 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])

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

Đề thi tương tự

Tổng hợp đề ôn luyện THPTQG Hóa học có lời giải

20 mã đề 1000 câu hỏi 1 giờ

332,169 xem25,547 thi

Tổng hợp đề ôn luyện thi THPTQG Hóa học có lời giải chi tiết

20 mã đề 900 câu hỏi 1 giờ

354,704 xem27,280 thi

Tổng Hợp Đề Ôn Luyện Thi Môn Quản Lý Nhân Lực 2 Full EPU

5 mã đề 244 câu hỏi 1 giờ

13,343 xem1,037 thi