Đề thi trắc nghiệm môn Cấu trúc dữ liệu và thuật toán
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
Cấu trúc dữ liệu và giải thuật (CK1)
Đề thi trắc nghiệm điền kết quả
Các bạn sinh viên điền kết quả thi trắc nghiệm điền kết quả vào phần văn bản (công thức toán,
số) hoặc một lựa chọn đúng nhất với câu trắc nghiệm lựa chọn.
6
Cho biết trong các công thức độ phức tạp tính toán sau, công thức nào là
không hợp lệ ?
(1 Điểm)
7
Hãy sắp xếp các hàm độ phức tạp tính toán tiệm cận theo thứ tự không giảm
của tốc độ tăng
(1 Điểm)
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
8
Cho hàm đệ quy được định nghĩa như sau
Bước cơ sở : F(0) = 1
Bước đệ quy : F(n) chia thành hai tình huống với n>0
Tình huống n chẵn : F(n) = F(n/2)*F(n/2)
Tình huống n lẻ : F(n)= 3*F((n-1)/2)*F((n-1)/2)
Hãy cho biết giá trị hàm F(6) là bao nhiêu ?
(1 Điểm)
729
9
Cho đoạn mã nguồn ngôn ngữ lập trình C của f() như sau
int f(unsigned int n)
{
int i,j,S=0;
for(i=0;i<n;i++)
for(j=i;j<n;j++)
S+=i;// Câu lệnh cần đếm
return S;
}
Hãy cho biết câu lệnh S+=i được thực hiện bao nhiêu lần khi gọi f(10) ?
(1 Điểm)
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
55
10
Cho biết chi phí thuật toán đệ quy có công thức truy hồi như sau
(1 Điểm)
11
Cho biểu thức hậutố Balan như sau
a b - c / d c - b/ +
Hãy tính giá trị biểu thức trên sử dụng ngăn xếp biết a = 25, b =5, c = 4 và d =
19
(1 Điểm)
Giá trị phải là một số
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
12
Cho cây mã Huffman có bảng chữ cái in hoa có tần suất xuất hiện tuân theo
dãy số Fibonnaci.
A:1 B:1 C:2 D:3 ...
Hãy cho biết ký tự H trong bảng chữ cái Tiếng Anh có tần suất là bao nhiêu ?
(1 Điểm)
Giá trị phải là một số
13
Cho cây mã Huffman có bảng chữ cái thường có tần suất xuất hiện tuân theo
dãy số Fibonnaci.
a:1 b:1 c:2 d:3 ...
Hãy cho biết cây mã Huffman của tất cả bảng chữ cái trên trong Tiếng Anh có
chiều cao là bao nhiêu ?
(1 Điểm)
Giá trị phải là một số
14
Độ phức tạp về thời gian trong trường hợp tồi nhất O của thuật toán tìm kiếm
tuần tự trên danh sách liên kết đơn là
(1 Điểm)
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
15
Độ phức tạp về thời gian trong trường hợp tồi nhất O của thuật toán tìm kiếm
nhị phân là
(1 Điểm)
16
Trong các thuật toán sắp xếp trên mảng sau, thuật toán nào có cận thời gian
trong trường hợp tồi nhất không ổn định
(1 Điểm)
Thuật toán sắp xếp chèn - Insertion Sort
Thuật toán sắp xếp lựa chọn - Selection Sort
Thuật toán sắp xếp vun đống - Heap Sort
Thuật toán sắp xếp trộn - Merge Sort
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
Thuật toán sắp xếp nhanh - Quick Sort
17
Số lượng nút tối đa trên một cây nhị phân tìm kiếm có chiều cao h=13 là bao
nhiêu ?
(1 Điểm)
Giá trị phải là một số
18
Có bao nhiêu cây nhị phân khác nhau có thể tạo từ n=4 nút ?
(1 Điểm)
Giá trị phải là một số
19
Cho cây nhị phân hoàn chỉnh có số nút n=2021 hãy cho biết chiều cao cây trên
là bao nhiêu ?
(1 Điểm)
Giá trị phải là một số
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
20
Cho cây nhị phân hoàn chỉnh có số nút n=2020 hãy cho biết số nút lá thuộc
mức đáy của cây trên là bao nhiêu ?
(1 Điểm)
Nhập câu trả lời của bạn
21
Trong các cấu trúc dữ liệu sau, cấu trúc nào hỗ trợ thao tác lưu trữ và tìm kiếm
dữ liệu với thời gian trung bình nhanh nhất
(1 Điểm)
Cây tìm kiếm nhị phân
Hàng đợi
Ngăn xếp
Danh sách liên kết
Bảng băm
Đống
22
Cho biểu thức dạng trung tố sau A+B*C/D-G*H, biểu thức dạng hậu tố tương
ứng là ?
(1 Điểm)
ABC*/D+GH-*
ABC*/D+-GH*
ABC*D/+GH*-
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
ABC*D/GH-*+
ABC*D/GH*-+
ABC*D/+-GH*
23
Nếu duyệt cây nhị phân theo thứ tự trước -preOrder và thứ tự sau postOrder
mà cùng cho ra một kết quả giống nhau thì cây đó có tối đa mấy nút ?
(1 Điểm)
Giá trị phải là một số
24
Cho hàm được định nghĩa bởi đoạn mã nguồn ngôn ngữ lập trình C như sau
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return f(n-1) + 2*f(n-2);
else return 2*f(n-1) + f(n-2);
}
Hãy cho biết giá trị hàm f(5) là bao nhiêu ?
(1 Điểm)
Giá trị phải là một số
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
25
Kết quả của chương trình là bao nhiêu ?
#include <stdio.h>
int f(int* a, int n){
if(n == 1) return 0;
return a[n-1] + f(a,n-1);
}
int main(){
int a[5] = {1,2,3,4,5};
printf("%d",f(a,5));
}
(1 Điểm)
Giá trị phải là một số
26
Cho hàm được định nghĩa bởi đoạn mã nguồn ngôn ngữ lập trình C như sau
int f(int n){
if(n == 0) return 1;
else return f(n-1) + f(n-1);
}
Hãy cho biết giá trị hàm f(9) là bao nhiêu ?
(1 Điểm)
Giá trị phải là một số
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
27
Cho hàm được định nghĩa bởi đoạn mã nguồn ngôn ngữ lập trình C như sau
int f(int n){
if(n == 0) return 1;
else return 2*f(n-1);
}
Hãy cho biết số phép toán * được thực hiện khi gọi hàm f(11) ?
(1 Điểm)
Giá trị phải là một số
28
Cho thủ tục được định nghĩa bởi đoạn mã nguồn ngôn ngữ lập trình C như sau
void f(int n){
if(n>0) f(--n);
printf("%d",n);
}
Hãy cho biết kết quả hiện ra màn hình khi gọi thủ tục f(4) ?
(1 Điểm)
Giá trị phải là một số
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
29
Cho thủ tục được định nghĩa bởi đoạn mã nguồn ngôn ngữ lập trình C như sau
void f(int n, int b){
if(n==0) return;
else{
f(n/b,b);
printf("%d",n%b);
}
}
Hãy cho biết kết quả hiện ra màn hình khi gọi thủ tục f(2020,8) ?
(1 Điểm)
Giá trị phải là một số
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
30
Cho nút của danh sách liên kết có cấu trúc sau.
typedef struct Node{
int value;
struct Node* next;
}Node;
Hỏi đoạn chương trình sau đây thực hiện công việc gì ?
Node* proc(Node* h, int v){
if(h== NULL) return NULL;
if(h->value == v){
Node* p =h->next;
free(h);
return proc(p,v);
}else{
h->next =proc(h->next,v);
return h;
}
}
(1 Điểm)
Loại bỏ phần tử v cuối cùng khỏi danh sách
Đảo ngược thứ tự các phần tử giá trị v trong danh sách
Thêm nhiều phần tử có giá trị v vào danh sách
Loại bỏ tất cả các phần tử có giá trị v khỏi danh sách
Thêm một phần tử có giá trị v vào danh sách
Loại bỏ phần tử v đầu tiên khỏi danh sách
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
31
Mỗi nút của danh sách liên kết có cấu trúc sau
typedef struct Node{
int value;
struct Node* next;
}Node;
Hỏi đoạn chương trình sau đây thực hiện công việc gì ?
Node* proc(Node* h){
if(h == NULL)
return NULL;
Node* cur = h; Node* p = NULL; Node* np = NULL;
while(cur != NULL){
np = cur->next;
cur->next = p;
p = cur;
cur = np;
}
return p;
}
(1 Điểm)
Loại bỏ phần tử cuối cùng có giá trị v khỏi danh sách
Loại bỏ tất cả các phần tử có giá trị v khỏi danh sách
Thêm nhiều phần tử có giá trị v vào danh sách
Đảo ngược thứ tự các phần tử trong danh sách
Loại bỏ phần tử đầu tiên có giá trị v khỏi danh sách
Thêm một phần tử có giá trị v vào danh sách
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
32
Kết luận nào sau đây không đúng với danh sách liên kết đơn
(1 Điểm)
Sử dụng một con trỏ trỏ (tham chiếu) đến phần tử đầu tiên trong danh sách
Có thể truy nhập ngẫu nhiên đến một phần tử bất kỳ của danh sách thông qua chỉ số của
nó với độ phức tạp là hằng số
Để chèn phần tử vào vị trí cuối cùng trong danh sách cần chi phí tuyến tính với chiều dài
danh sách
Các phần tử thường không được cấp phát liên tiếp nhau trong bộ nhớ
Mỗi phần tử có một trường con trỏ (tham chiếu) đến phần tử tiếp theo trong danh sách
Việc tìm kiếm một phần tử luôn phải thực hiện từ đầu danh sách
33
Cho ngăn xếp hình bên, hãy cho biết khi lấy hai phần tử khỏi ngăn xếp thì giá
trị của nó là bao nhiêu ?
(1 Điểm)
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
Giá trị phải là một số
34
Cho hàng đợi cho dưới đây, hãy cho biết khi lấy ba phần tử khỏi hàng đợi thì
giá trị của nó là bao nhiêu ?
(1 Điểm)
Giá trị phải là một số
35
Cho cây nhị phân có các nhãn được minh họa như hình bên, hay cho biết giá trị
thứ năm được duyệt theo thứ tự giữa là ?
(1 Điểm)
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
Giá trị phải là một số
36
Cho định nghĩa ô dữ liệu cây nhị phân sau
typedef struct Node{
int id;
struct Node* left;// con trỏ đến con trái
struct Node* right; // con trỏ đến con phải
}Node;
Hàm sau đây (nhận h là con trỏ đến gốc của 1 cây nhị phân) thực hiện công
việc gì ?
int proc(Node* h){
if(h == NULL) return 0;
if(h->left == NULL &&h->right == NULL) return 1;
return proc(h->left) +proc(h->right);
}
(1 Điểm)
Trả về tổng số nút trên cây
Trả về tổng số nút lá trên cây
Trả về tổng số nút trong (nút có ít nhất 1 nút con) trên cây
Trả về tổng số nút có đúng 2 nút con trên cây
Trả về tổng số lá có con khác rỗng trên cây
Trả về tổng số nút có đủ hai nút con
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
37
Thuật toán sắp xếp có mã nguồn ngôn ngữ C như sau
void sort(int A[], int N) {
int swapped, i;
do{
swapped = 0;
for(i=0; i<N-1; i++){
if(A[i] > A[i+1]){
int tmp = A[i];
A[i] = A[i+1];
A[i+1] = tmp;
swapped = 1;
}
}
}while(swapped);
}
Hãy nhận diện đúng xem nó là giải thuật sắp xếp nào ?
(1 Điểm)
Sắp xếp lựa chọn
Sắp xếp nhanh
Sắp xếp trộn
Sắp xếp chèn
Sắp xếp nổi bọt
Sắp xếp vun đống
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
38
Cho mảng khóa A[]={30, 19, 24, 28, 41, 34, 15, 43, 20, 12, 36} cần sắp xếp dùng
giải thuật sắp xếp nhanh Quik-Sort. Hãy thực hiện thao tác phân đoạn
partition(A) theo chốt là khóa ngoài cùng bên trái. Hãy cho biết cấu trạng của
mảng A[] sau khi phân đoạn là lựa chọn nào sau đây ?
(1 Điểm)
A[]={30, 19, 24, 28, 41, 34, 15, 43, 20, 12, 36}
A[]={15, 19, 24, 28, 20, 12, 30, 43, 34, 36, 41}
A[]={15, 24, 19, 28, 12, 20, 30, 43, 41, 34, 36}
A[]={15, 19, 24, 28, 20, 12, 30, 43, 34, 41, 36}
A[]={15, 24, 19, 28, 12, 20, 30, 43, 34, 41, 36}
A[]={15, 19, 24, 28, 12, 20, 30, 43, 34, 41, 36}
39
Cho mảng A[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7 } cần sắp xếp dùng giải thuật sắp
xếp vun đống. Trước tiên ta dùng thao tác Build-Max-Heap(A) để vun lại đống.
Hãy cho biết vòng lặp thứ 3 của thao tác thì cấu trạng mảng A[] là như thế nào
theo lựa chọn sau ?
(1 Điểm)
A[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7 }
A[] = {4, 16, 10, 14, 9, 7, 3, 2, 8, 1 }
A[] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1 }
A[] = {4, 16, 10, 14, 7, 9, 3, 2, 8, 1 }
A[] = {4, 1, 3, 14, 16, 9, 10, 2, 8, 7 }
A[] = {4, 1, 10, 14, 16, 9, 3, 2, 8, 7 }
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
40
N phần tử được lưu trữ trên cây nhị phân tìm kiếm (BST). Độ phức tạp trong
tình huống tốt nhất của thuật toán tìm kiếm trên BST là bao nhiêu ?
(1 Điểm)
41
Cho cây nhị phân tìm kiếm như hình bên, hãy thực hiện xóa khóa 2 và sau đó
duyệt cây theo thứ tự sau. Hãy cho biết giá trị khóa thứ ba là bao nhiêu ?
(1 Điểm)
27/8/2021
Cấu trúc dữ liệu và giải thuật (CK1) (Trang 2 trên 2)
Giá trị phải là một số
42
Chiều cao của cây tìm kiếm nhị phân cân bằng AVL có số nút n=2020 trong
trường hợp tồi nhất là
(1 Điểm)
Giá trị phải là một số
43
Cho biết trong bốn cây nhị phân dưới đây đâu là cây nhị phân tìm kiếm cân
bằng ?
(1 Điểm)
a)
b)
c)
d)
Tải về để xem bản đầy đủ
22 trang
26/04/2022
10240
Bạn đang xem 20 trang mẫu của tài liệu "Đề thi trắc nghiệm môn Cấu trúc dữ liệu và thuật toán", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- de_thi_trac_nghiem_mon_cau_truc_du_lieu_va_thuat_toan.pdf
