20 trang 2 lượt tải

Đề Cương Ôn Tập Môn Cấu trúc dữ liệu và giải thuật | Trường Cao đẳng Kinh tế Công nghiệp Hà Nội

4

Đề Cương Ôn Tập Môn Cấu trúc dữ liệu và giải thuật. Tài liệu được sưu tầm gồm 20 trang, giúp bạn ôn tập tốt hơn. Mời các bạn đón xem. 

Môn: Cấu trúc dữ liệu và giải thuật (CĐ) 2 tài liệu

Trường: Trường Cao đẳng Kinh tế Công nghiệp Hà Nội 83 tài liệu

Tác giả:

Profile

Linh Giang

22 giờ trước
Danh sách Quiz
/20
lOMoARcPSD| 58675420
TRỌNG TÂM ÔN TẬP MÔN:
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
STT
Nội dung
1.
Giải thuật là gì?
A. Giải thuật là một cách để giải bài toán nào đó bằng phương pháp lưu đồ.
B. Giải thuật là một cách để giải bài toán nào đó chỉ bằng ngôn ngữ.
C. Giải thuật là một cách để giải bài toán nào đó.Cũng có thể chỉ đúng cho một vài
trường hợp đặc biệt.
D. Giải thuật là một cách để giải bài toán nào đó, nhưng nó phải áp dụng được cho mọi
bài toán cùng loại.
2.
Mối quan hệ giữa cấu trúc dữ liệu và giải thuật được mô tả:
A. Cấu trúc dữ liệu + Giải thuật = Chương trình
B. Cấu trúc dữ liệu + Chương trình = Giải thuật
C. Chương trình + Giải thuật = Cấu trúc dữ liệu
D. Cấu trúc dữ liệu = Chương trình
3.
Thế nào là ngôn ngữ giả?
A. Ngôn ngữ giả là cấu trúc của môt chuương trình chỉ viết bằng ngôn ngữ Pascal mà
tuỳ thuộc vào nguười lập trình.
B. Ngôn ngữ giả là sự kết hợp của ngôn ngữ tự nhiên và các cấu trúc của một ngôn
ngữ lập trình nào đó.
C. Ngôn ngữ giả là ngôn ngữ lập trình pascal, C, hay một ngôn ngữ bậc cao khác.
D. Ngôn ngữ giả là ngôn ngữ do ngưuoi lập trình định nghĩa.
4.
Hãy sắp xếp thứ tự 3 giai đoạn để giải quyết bài toán?
(a) Chọn một cách cài đặt một kiểu dữ liệu trừu tượng và thay ngôn ngữ giả bằng các
mã lệnh của 1 ngôn ngữ lập trình . Kết quả là ta được 1 chương trình hoàn chỉnh có thể
giải quyết được vấn đề đặt ra.
(b) Xây dựng mô hình toán thích hợp cho bài toán và tìm một giải thuật giải quyết bài
toán trên mô hình đó.
(c) Giải thuật được trình bày bằng ngôn ngữ giả dựa trên các kiểu dữ liệu trừu tượng.
A. a,b,c
lOMoARcPSD| 58675420
B. b, c, a
C. b, a, c
D. c, a, b
5.
Thời gian chạy chương trình phụ thuộc vào các yếu tố nào? A.
Dữ liệu đầu vào.
B. Độ phức tạp tính toán của giải thuật.
C. Tốc độ của máy được dùng.
D. Tất cả các yếu tố nêu ra
6.
Khi nói đến độ phức tạp của giải thuật là ta muốn nói đến:
A. Kết quả thu được sau khi thực hiện của chương trình
B. Hiệu quả của thời gian thực hiện của chương trình
C. Các bước tính toán trong quá trình thực hiện chương trình
D. Tất cả đều đúng
7.
Ta có thể tính độ phức tạp của một giải thuật bất kỳ theo nguyên tắc:
A. Quy tắc cộng
B. Quy tắc nhân
C. Quy tắc tổng quát để phân tích một chương trình
D. Tất cả đều đúng
8.
Để lựa chọn một giải thuật tốt, ta sẽ căn cứ vào tiêu chuẩn: A.
Giải thuật đúng đắn.
B. Giải thuật đơn giản.
C. Giải thuật thực hiện nhanh.
D. Tất cả đều đúng
9.
Nếu T1(n) và T2(n) là thời gian chạy của 2 đoạn chương trình P1 ,P2. Thời gian chạy của
hai chuơng trình P1, P2 nối nhau là:
A. T=T1+T2
B. T=T1/T2
C. T=T1-T2
D. T = T1 T2
lOMoARcPSD| 58675420
10.
Nếu T1(n) và T2(n) là thời gian chạy của 2 đoạn chương trình P1,P2.Thời gian chạy của hai
chuơng trình P1, P2 lồng nhau là:
A. T=T1-T2
B. T=T1+T2
C. T=T1*T2
D. T=T1/T2
11.
Thời gian chạy của các lệnh gán, câu lệnh nhập, hiển thị là:
A. O(n)
B. O(2)
C. O(3)
D. O(1)
12.
Thời gian chạy của một chuỗi tuần tự áp dụng quy tắc?
A. Quy tắc Trừ
B. Quy tắc Nhân
C. Quy tắc Cộng
D. Quy tắc Nhân đôi
13.
Nếu S1 và S2 là các câu lệnh và E là biểu thức logic thì
If (E) 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(And (f()n), g(n)))
D. O(or( (f()n), g(n)))
14.
Nếu S là câu lệnh và E là biểu thức logic thì
while (E)
{
S
lOMoARcPSD| 58675420
}
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 là:
A. O(max (f()n), g(n)))
B. O(And (f()n), g(n)))
C. O(f(n)g(n)).
D. O(Or(f(n),g(n))
15.
Miền giá trị của Kiểu số nguyên là:
A. 0..32767
B. 0..32768
C. -32767 .. 32768
D. -32768 .. 32767
16.
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 là nòng cốt của chương trình
C.Thuật toán cần có một hoặc nhiều dữ liệu ra (output),dữ liệu vào (input).
D. 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.
17.
Đặc điểm nào của giải thuật viết bằng đệ quy là sai trong các đặc điểm sau:
A. Sau mỗi lần có lời gọi đệ quy thì kích thước của bài toán được thu nhỏ hơn trước.
B. Sau một số lần gọi đệ quy bài toán có giá trị bằng 0
C. Trong thủ tục đệ quy có lời gọi đến chính thủ tục đó
D. Tất cả đều sai
18.
Một giải thuật đệ quy xảy ra trường hợp suy biến khi nào? A.
Sau một số lần có lời gọi đệ quy.
B. Khi không thể giải quyết được giải thuật.
C. Khi kết quả của giảI thuật bằng giá trị 0
lOMoARcPSD| 58675420
D. Sau một số lần có lời gọi đệ quy bài toán còn lại sẽ được giải quyết theo một cách khác
19.
Khi dùng giải thuật đệ quy để thực hiện bài toán tháp Hà Nội, nếu tháp có 5 vòng thì ta phải
thực hiện bao nhiêu thao tác:
A. 64
B. 15
C. 70
D. 31
20.
Giải thuật đệ quy là:
A. Trong giải thuật của nó có lời gọi tới chính nó nhưng với phạm vi lớn hơn.
B. Trong giải thuật của nó có lời gọi tới một giải thuật khác đã biết kết quả.
C. Trong giải thuật của nó có lời gọi tới chính nó nhưng với phạm vi nhỏ hơn.
D. Trong giải thuật của nó có lời gọi tới chính nó.
21.
Cho hàm đệ quy
sau: int factorial(int
n) { if (n == 1)
return 1; else
return (n * factorial(n - 1)); }
Sau mỗi lần gọi đệ quy thì giá trị của n là:
A. Giảm đi 1
B. Tăng lên 1
C. N=0
D. N=1
22.
Có Hàm đệ quy
sau:
intfactorial(intn) {
if(n == 1)
return1; else
return(n * factorial(n - 1));
} if(n ==
1)return1;
A. Lặp vô hạn
B. Điều kiện dừng đệ quy
lOMoARcPSD| 58675420
C. Điều kiện không thực hiện đệ quy
D. Lặp 1 lần
23.
Có Hàm đệ quy sau giải bài toán gì?:
intfactorial(intn)
{ if(n ==
1)
return1;
else
return(n * factorial(n - 1)); }
A. Tính số cặp thỏ sau n tháng
B. Tính n^n (n mũ n).
C. Tính giai thừa n
D. Tính tích: 1*2*3*…*n
24.
Có Hàm đệ quy
sau: int factorial(int
n) { if (n == 1)
return 1; else
return (n * factorial(n - 1)); }
Kết quả bằng bao nhiêu khi n=3
A. 8
B. 2
C. 9
D. 6
25.
Dãy số Fibonacci bắt nguồn từ bài toán cổ về việc sinh sản của các cặp thỏ. Bài toán được
đặt ra như sau: Các con thỏ không bao giờ chết. Hai tháng sau khi ra đời một cặp thỏ mới
sẽ sinh ra một cặp thỏ con. Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh
được mộtcặp con mới. Giả sử bắt đầu từ một cặp thỏ mới ra đời thì đến tháng thứ 5 sẽ có
bao nhiêu cặp?
A. 5 cặp
B. 10 cặp
C. 9 cặp
D. 12 cặp
lOMoARcPSD| 58675420
26.
Cho giải thuật đệ quy sau:
function fibonacci(n)
{
if (n <= 2) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Dòng lệnh if (n <= 2) return n;đóng vai trò:
A. Lặp 1 lần
B. Điều kiện dừng đệ quy
C. Điều kiện không thực hiện đệ quy
D. Lặp vô hạn
27.
Đặc điểm của giải thuật đệ quy:
A. Trong thủ tục đệ quy có lời gọi đến chính thủ tục đó
B. Có một trường hợp đặc biệt, trường hợp suy biến khi trường hợp này xảy ra thì bài
toán còn lại sẽ được giải quyết theo một cách khác
C. Sau mỗi lần có lời gọi đệ quy thì kích thước của bài toán được thu nhỏ hơn trước.
D. Tất cả đều đúng
28.
Giải thuật đệ quy của bài toán "Tháp Hà Nội" như sau:
void Tower(int n , char a, char b, char c ){
if(n==1){
cout<<"\t"<<a<<"-------"<<c<<endl;
return;
}
Tower(n-1,a,c,b);
Tower(1,a,b,c);
Tower(n-1,b,a,c);
}
Khi n=3 có bao nhiêu bước chuyển?
A. 8 bước
B. 14 bước
C. 15 bước
D. 16 bước
29.
Cho giải thuật đệ quy:
1.F(0,a)=F(a,0)=a
lOMoARcPSD| 58675420
2. F(m,n)=F(m-n,n) nếu m>=n
3. F(m,n)=F(m,n-m) nếu m<n
Nếu m=30, n = 75 thì sau khi thực hiện giải thuật ta được giá trị nào?
A. 30
B. 10
C. 15
D. 45
30.
Cho giải thuật đệ quy:
1. F(0, a) = F(a, 0) = a
2. F(m, n) = F(m - n, n) nếu m >= n
3. F(m, n) = F(m, n - m) nếu m < n
Nếu m=72, n = 48 thì sau khi thực hiện giải thuật ta được giá trị nào? A.
4
B. 10
C. 20
D. 24
31.
Cho giải thuật đệ quy:
1. F(1)=F(2)=1
2. F(k)=F(k-1)+F(k-2) nếu K>2 Hãy tính F(6)?
A. 10
B. 9
C. 8
D. 7
32.
Cho giải thuật đệ quy:
1.F(1)=1, F(2)=2, F(3)=3
2.F(k)=F(K-1) + 2F(K-3) , K>3 Hãy
tính F(6)?
A. 16
B. 15
C. 14
D. 13
lOMoARcPSD| 58675420
33.
Có thể cài đặt danh sách bằng:
A. Con trỏ
B. Mảng
C. Mảng và con trỏ.
D. Tất cả đều sai
34.
Tính chất quan trọng của danh sách là?
A. Các phần tử của danh sách không theo thứ tự
B. Các phần tử của danh sách có thể truy nhập ngẫu nhiên.
C. Các phần tử của danh sách có thứ tự tuyến tính theo vị trí xuất hiện của chúng(position)
D. Tất cả đều sai
35.
Trong các cấu trúc dữ liệu sau đâu là dữ liệu trừu tượng?
A. Cấu trúc dữ liệu dạng ngăn xếp (Stack)
B. Cấu trúc dữ liệu kiểu hàng đợi(Queue)
C. Cấu trúc dữ liệu dạng danh sách(List)
D. Tất cả cấu trúc đã nêu
36.
Danh sách tuyến tính là:
A. Danh sách dạng được lưu dưới dạng mảng.
B. Danh sách mà quan hệ lân cận giữa các phần tử được xác định.
C. Danh sách tuyến tính là một danh sách có dạng (a1, a2, ..., an).
D. Danh sách tuyến tính là một danh sách rỗng.
37.
Ưu điểm của việc cài đặt danh sách bằng mảng:
A. Có thể thay đổi số lượng phần tử theo ý muốn của người dùng.
B. Có thể bổ sung hoặc xóa một phần tử bất kỳ trong mảng. C. Việc truy nhập vào
phần tử của mảng được thực hiện trực tiếp dựa vào địa chỉ tính được (chỉ số), nên tốc độ
nhanh và đồng đều đối với mọi phần tử. D. Tất cả các ý trên đều đúng.
38.
Để 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
lOMoARcPSD| 58675420
C. Thực hiện tìm kiếm nhị phân trên danh sách móc nối đơn
D. Thực hiện tìm kiếm tuần tự từ phần tử cuối dãy
39.
Để 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
40.
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ỳ.
41.
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
42.
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;
lOMoARcPSD| 58675420
SLLPointer Ptail;
} LIST;
C. typedef struct SSLLIST
{ SLLPointer Phead;
SLLPointer Ptail;
int total;
} LIST;
D.typedef struct SSLLIST
{ SLLPointer Phead;
int total;
} LIST;
lOMoARcPSD| 58675420
43.
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.
44.
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.
lOMoARcPSD| 58675420
45.
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);
46.
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;
47.
Thao tác nào dưới đây thực hiện trên ngăn xếp (stack)?
A. Thêm và loại bỏ phần tử luôn thực hiện tại vị trí đỉnh (top)
B. Thêm và loại bỏ phần tử có thể thực hiện tại vị trí bất kỳ C. Thêm
phần tử vào vị trí bất kỳ
lOMoARcPSD| 58675420
D. Loại bỏ phần tử tại vị trí bất kỳ
48.
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ỳ
49.
Cấu trúc dữ liệu nào tương ứng với LIFO?
A.Queue
B.Linked List
C.Tree
D. Stack
50.
Để cài đặt Stack ta có thể dùng phương pháp nào sau đây:
A. Bằng mảng
B. Bằng con trỏ
C. Bằng con trỏ và bằng mảng
D. Tất cả đều không đúng
51.
Danh sách tuyến tính dạng ngăn xếp là:
A. Là một danh sách tuyến tính trong đó phép bổ sung sung một phần tử vào ngăn xếp
được thực hiện ở một đầu, Và phép loại bỏ không thực hiện được.
B. Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp và
phép loại bỏ một phần tử khỏi ngăn xếp luôn luôn thực hiện ở một đầu gọi là đỉnh .
C. Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp và
phép loại bỏ một phần tử khỏi ngăn xếp luôn luôn thực hiện ở tại một vị trí bất kì trong danh
sách.
D. Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp được
thực hiện ở một đầu, và phép loại bỏ được thực hiện ở đầu kia.
52.
Danh sách tuyến tính dạng ngăn xếp làm việc theo nguyên tắc?
A. FIFO( first in first out)
B. LIFO(last in first out)
C. FOLO( fisrt out last out)
D. LILO(last in last out)
lOMoARcPSD| 58675420
53.
Khi đổi một số nguyên từ hệ thập phân sang hệ nhị phân thì người ta dùng phép chia liên
tiếp cho 2 và lấy các số dư (là các chữ số nhị phân) theo chiều ngược lại.
Cơ chế sắp xếp này chính là cơ chế hoạt động của cấu trúc dữ liệu:
A. Mảng (array)
B. Hàng đợi(Queue)
C. Bản ghi (Record)
D. Ngăn xếp (stack)
54.
Định nghĩa danh sách tuyến tính Hàng đợi (Queue)?
A. Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử được thực
hiện ở một đầu, gọi là lối sau (rear) hay lối trước (front). Phép loại bỏ không thực hiện được.
B. Là một danh sách tuyến tính trong đó phép bổ sung một phần tử và phép loại bỏ một
phần tử được thực hiện ở tại một vị trí bất kì trong danh sách.
C. Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung phần tử ở một đầu, gọi
là lối sau (rear) và phép loại bỏ phần tử được thực hiện ở đầu kia, gọi là lối trước (front).
D. Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử hay loại
bỏ được thực hiện ở một đầu danh sách gọi là đỉnh (Top)
55.
Hàng đợi còn được gọi là danh sách kiểu?
A. FIFO
B. LIFO
C. LOLO
D. FILO
56.
Để thêm một đối tượng x bất kỳ vào Stack, thao tác thường dùng là: A.
EMPTY(x).
B. TOP(x).
C. POP(x).
D. PUSH(x).
57.
Để lấy loại bỏ một đối tượng ra khỏi Stack, thao tác thường dùng là:
A. FULL(x)
B. POP(x)
C. PUSH(x)
lOMoARcPSD| 58675420
D. EMPTY(x)
58.
Để biểu diễn Stack, ta thường sử dụng kiểu dữ liệu nào sau đây?
A. Mảng dữ liệu
B. Kiểu bản ghi
C. Danh sách móc nối
D. Danh sách móc nối và mảng dữ liệu
59.
Thao tác POP(x) dùng trong Stack là để:
A. Lấy một phần tử cuối cùng ra khỏi đỉnh Stack
B. Lấy phần tử đầu tiên ra khỏi Stack
C. Xóa bỏ một phần tử bất kì khỏi Stack
D. Xóa bỏ một dãy các phần tử ra khỏi Stack
60.
Thao tác Push(x) dùng trong Stack là để:
A. Bổ sung một phần tử vào đầu Stack
B. Bổ sung một phần tử bất kì vào Stack
C. Bổ sung một phần tử vào đỉnh Stack
D. Bổ sung một dãy các phần tử vào đỉnh Stack.
61.
Bậc của một nút là:
A. Số cây con của nút đó
B. Là tổng số nút lá của cây đó
C. Là tổng số tất cả các nút thuộc cây nhận nút đó làm gốc
D. Không có đáp án đúng
62.
Cây nhị phân là:
A. Cây mà mỗi nút có tối đa 2 cây con
B. Cây mà tổng số nút của nó là bội của 2
C. Mỗi nút không phải nút lá có đúng 2 con
D. Bậc của mọi nút bằng 2.
63.
Cho cây nhị phân như hình vẽ
Kết quả duyệt các phép duyệt trước, duyệt giữa, duyệt sau là:
lOMoARcPSD| 58675420
lOMoARcPSD| 58675420
Duyệt trước: A, B, K, E, C
Duyệt giữa: K, B, E, A, C
Khi đó kết quả phép duyệt sau sẽ là:
A. Không thể xác định được
B. K, B, E, C, A
C. A, B, C, K, E
D. K, E, B, C, A.
69.
Cho kết quả của phép phép duyệt sau và duyệt giữa như sau:
Duyệt sau: D, E, B, C, A
Duyệt giữa: D, B, E, A, C
Khi đó kết quả phép duyệt trước sẽ là:
A. A, B, D, E, C
B. Không thể xác định được
C. D, E, B, C, A
D. D, B, E, C, A
70.
Để huỷ toàn bộ cây nhị phân tìm kiếm ta có thể thực hiện thông qua thao tác duyệt cây theo
thứ tự sau, nghĩa là:
A. Huỷ cây con trái, cây con phải rồi mới huỷ gốc
B. Huỷ cây con phải, cây con trái rồi mới huỷ gốc
C. Huỷ mọi cây con trái rồi mới huỷ gốc
D. Chỉ cần huỷ nút gốc vì cây mất gốc thì không thể tồn tại được.
71.
Cho cây nhị phân như sau:
lOMoARcPSD| 58675420
Với cách duyệt Inorder (Left – Root – Right) cho ra kết quả là dãy nào? Tìm lựa chọn đúng
nhất
A. 13 2 169 20 11 40 55 22 90 50 34
B. 13 2 55 40
169 11
20 34
90 22
C. 34 55 2 13
D. Cả a, b, c đều sai.
40 11
169 20
90 22
72.
Độ cao của cây là gì?
A. Cấp lớn nhất của nút
B. Mức lớn nhất của cây
C. Số cây con của cây
D. Số lượng nút của cây
73.
Cho dãy khoá 42, 23, 74, 11, 65, 58, 94, 36.Lần lượt đưa dãy khoá trên vào cây nhị phân
tìm kiếm. Nếu ta tìm kiếm trên cây nhị phân này thì trong trường hợp xấu nhất phải làm
bao nhiêu phép so sánh?
A. 3
B. 4
C. 5
D. 6
lOMoARcPSD| 58675420
74.
Cho dãy khoá 42, 23, 74, 11, 65, 58, 94, 36. Lần lượt đưa dãy khoá trên vào cây nhị phân
tìm kiếm. Bây giờ ta muốn tìm kiếm xem trong dãy khoá trên có khoá 105 không thì phải
làm bao nhiêu phép so sánh?
A. 3
B. 4
C. 5
D. 8
75.
Cho dãy khoá 42, 23, 74, 11, 65, 58, 94, 36. Lần lượt đưa dãy khoá trên vào cây nhị phân
tìm kiếm. Bây giờ ta muốn tìm kiếm xem trong dãy khoá trên có khoá 60 không thì phải làm
bao nhiêu phép so sánh?
A. 3
B. 4
C. 5
D. 7

Tài liệu khác của Trường Cao đẳng Kinh tế Công nghiệp Hà Nội

Preview text:

lOMoAR cPSD| 58675420
TRỌNG TÂM ÔN TẬP MÔN:
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT STT Nội dung 1. Giải thuật là gì? A.
Giải thuật là một cách để giải bài toán nào đó bằng phương pháp lưu đồ. B.
Giải thuật là một cách để giải bài toán nào đó chỉ bằng ngôn ngữ. C.
Giải thuật là một cách để giải bài toán nào đó.Cũng có thể chỉ đúng cho một vài
trường hợp đặc biệt. D.
Giải thuật là một cách để giải bài toán nào đó, nhưng nó phải áp dụng được cho mọi bài toán cùng loại. 2.
Mối quan hệ giữa cấu trúc dữ liệu và giải thuật được mô tả:
A. Cấu trúc dữ liệu + Giải thuật = Chương trình
B. Cấu trúc dữ liệu + Chương trình = Giải thuật
C. Chương trình + Giải thuật = Cấu trúc dữ liệu
D. Cấu trúc dữ liệu = Chương trình 3.
Thế nào là ngôn ngữ giả? A.
Ngôn ngữ giả là cấu trúc của môt chuương trình chỉ viết bằng ngôn ngữ Pascal mà
tuỳ thuộc vào nguười lập trình. B.
Ngôn ngữ giả là sự kết hợp của ngôn ngữ tự nhiên và các cấu trúc của một ngôn ngữ lập trình nào đó. C.
Ngôn ngữ giả là ngôn ngữ lập trình pascal, C, hay một ngôn ngữ bậc cao khác. D.
Ngôn ngữ giả là ngôn ngữ do ngưuoi lập trình định nghĩa. 4.
Hãy sắp xếp thứ tự 3 giai đoạn để giải quyết bài toán? (a)
Chọn một cách cài đặt một kiểu dữ liệu trừu tượng và thay ngôn ngữ giả bằng các
mã lệnh của 1 ngôn ngữ lập trình . Kết quả là ta được 1 chương trình hoàn chỉnh có thể
giải quyết được vấn đề đặt ra. (b)
Xây dựng mô hình toán thích hợp cho bài toán và tìm một giải thuật giải quyết bài toán trên mô hình đó. (c)
Giải thuật được trình bày bằng ngôn ngữ giả dựa trên các kiểu dữ liệu trừu tượng. A. a,b,c lOMoAR cPSD| 58675420 B. b, c, a C. b, a, c D. c, a, b 5.
Thời gian chạy chương trình phụ thuộc vào các yếu tố nào? A. Dữ liệu đầu vào.
B. Độ phức tạp tính toán của giải thuật.
C. Tốc độ của máy được dùng.
D. Tất cả các yếu tố nêu ra 6.
Khi nói đến độ phức tạp của giải thuật là ta muốn nói đến:
A. Kết quả thu được sau khi thực hiện của chương trình
B. Hiệu quả của thời gian thực hiện của chương trình
C. Các bước tính toán trong quá trình thực hiện chương trình D. Tất cả đều đúng 7.
Ta có thể tính độ phức tạp của một giải thuật bất kỳ theo nguyên tắc: A. Quy tắc cộng B. Quy tắc nhân
C. Quy tắc tổng quát để phân tích một chương trình D. Tất cả đều đúng 8.
Để lựa chọn một giải thuật tốt, ta sẽ căn cứ vào tiêu chuẩn: A. Giải thuật đúng đắn.
B. Giải thuật đơn giản.
C. Giải thuật thực hiện nhanh. D. Tất cả đều đúng 9.
Nếu T1(n) và T2(n) là thời gian chạy của 2 đoạn chương trình P1 ,P2. Thời gian chạy của
hai chuơng trình P1, P2 nối nhau là: A. T=T1+T2 B. T=T1/T2 C. T=T1-T2 D. T = T1 T2 lOMoAR cPSD| 58675420 10.
Nếu T1(n) và T2(n) là thời gian chạy của 2 đoạn chương trình P1,P2.Thời gian chạy của hai
chuơng trình P1, P2 lồng nhau là: A. T=T1-T2 B. T=T1+T2 C. T=T1*T2 D. T=T1/T2 11.
Thời gian chạy của các lệnh gán, câu lệnh nhập, hiển thị là: A. O(n) B. O(2) C. O(3) D. O(1) 12.
Thời gian chạy của một chuỗi tuần tự áp dụng quy tắc? A. Quy tắc Trừ B. Quy tắc Nhân C. Quy tắc Cộng D. Quy tắc Nhân đôi 13.
Nếu S1 và S2 là các câu lệnh và E là biểu thức logic thì If (E) 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(And (f()n), g(n))) D. O(or( (f()n), g(n))) 14.
Nếu S là câu lệnh và E là biểu thức logic thì while (E) { S lOMoAR cPSD| 58675420 }
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 là: A. O(max (f()n), g(n))) B. O(And (f()n), g(n))) C. O(f(n)g(n)). D. O(Or(f(n),g(n)) 15.
Miền giá trị của Kiểu số nguyên là: A. 0..32767 B. 0..32768 C. -32767 .. 32768 D. -32768 .. 32767 16.
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 là nòng cốt của chương trình
C.Thuật toán cần có một hoặc nhiều dữ liệu ra (output),dữ liệu vào (input).
D. 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. 17.
Đặc điểm nào của giải thuật viết bằng đệ quy là sai trong các đặc điểm sau:
A. Sau mỗi lần có lời gọi đệ quy thì kích thước của bài toán được thu nhỏ hơn trước.
B. Sau một số lần gọi đệ quy bài toán có giá trị bằng 0
C. Trong thủ tục đệ quy có lời gọi đến chính thủ tục đó D. Tất cả đều sai 18.
Một giải thuật đệ quy xảy ra trường hợp suy biến khi nào? A.
Sau một số lần có lời gọi đệ quy.
B. Khi không thể giải quyết được giải thuật.
C. Khi kết quả của giảI thuật bằng giá trị 0 lOMoAR cPSD| 58675420
D. Sau một số lần có lời gọi đệ quy bài toán còn lại sẽ được giải quyết theo một cách khác 19.
Khi dùng giải thuật đệ quy để thực hiện bài toán tháp Hà Nội, nếu tháp có 5 vòng thì ta phải
thực hiện bao nhiêu thao tác: A. 64 B. 15 C. 70 D. 31 20. Giải thuật đệ quy là:
A. Trong giải thuật của nó có lời gọi tới chính nó nhưng với phạm vi lớn hơn.
B. Trong giải thuật của nó có lời gọi tới một giải thuật khác đã biết kết quả.
C. Trong giải thuật của nó có lời gọi tới chính nó nhưng với phạm vi nhỏ hơn.
D. Trong giải thuật của nó có lời gọi tới chính nó. 21. Cho hàm đệ quy sau: int factorial(int n) { if (n == 1) return 1; else
return (n * factorial(n - 1)); }
Sau mỗi lần gọi đệ quy thì giá trị của n là: A. Giảm đi 1 B. Tăng lên 1 C. N=0 D. N=1 22. Có Hàm đệ quy sau: intfactorial(intn) { if(n == 1) return1; else
return(n * factorial(n - 1)); } if(n == 1)return1; A. Lặp vô hạn
B. Điều kiện dừng đệ quy lOMoAR cPSD| 58675420
C. Điều kiện không thực hiện đệ quy D. Lặp 1 lần 23.
Có Hàm đệ quy sau giải bài toán gì?: intfactorial(intn) { if(n == 1) return1; else
return(n * factorial(n - 1)); }
A. Tính số cặp thỏ sau n tháng B. Tính n^n (n mũ n). C. Tính giai thừa n D. Tính tích: 1*2*3*…*n 24. Có Hàm đệ quy sau: int factorial(int n) { if (n == 1) return 1; else
return (n * factorial(n - 1)); }
Kết quả bằng bao nhiêu khi n=3 A. 8 B. 2 C. 9 D. 6 25.
Dãy số Fibonacci bắt nguồn từ bài toán cổ về việc sinh sản của các cặp thỏ. Bài toán được
đặt ra như sau: Các con thỏ không bao giờ chết. Hai tháng sau khi ra đời một cặp thỏ mới
sẽ sinh ra một cặp thỏ con. Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh
được mộtcặp con mới. Giả sử bắt đầu từ một cặp thỏ mới ra đời thì đến tháng thứ 5 sẽ có bao nhiêu cặp? A. 5 cặp B. 10 cặp C. 9 cặp D. 12 cặp lOMoAR cPSD| 58675420 26.
Cho giải thuật đệ quy sau: function fibonacci(n) { if (n <= 2) return n;
return fibonacci(n - 1) + fibonacci(n - 2); }
Dòng lệnh if (n <= 2) return n;đóng vai trò: A. Lặp 1 lần
B. Điều kiện dừng đệ quy
C. Điều kiện không thực hiện đệ quy D. Lặp vô hạn 27.
Đặc điểm của giải thuật đệ quy: A.
Trong thủ tục đệ quy có lời gọi đến chính thủ tục đó B.
Có một trường hợp đặc biệt, trường hợp suy biến khi trường hợp này xảy ra thì bài
toán còn lại sẽ được giải quyết theo một cách khác C.
Sau mỗi lần có lời gọi đệ quy thì kích thước của bài toán được thu nhỏ hơn trước. D. Tất cả đều đúng 28.
Giải thuật đệ quy của bài toán "Tháp Hà Nội" như sau:
void Tower(int n , char a, char b, char c ){ if(n==1){ cout<<"\t"<return; } Tower(n-1,a,c,b); Tower(1,a,b,c); Tower(n-1,b,a,c); }
Khi n=3 có bao nhiêu bước chuyển? A. 8 bước B. 14 bước C. 15 bước D. 16 bước 29. Cho giải thuật đệ quy: 1.F(0,a)=F(a,0)=a lOMoAR cPSD| 58675420 2. F(m,n)=F(m-n,n) nếu m>=n 3.
F(m,n)=F(m,n-m) nếu mNếu m=30, n = 75 thì sau khi thực hiện giải thuật ta được giá trị nào? A. 30 B. 10 C. 15 D. 45 30. Cho giải thuật đệ quy: 1. F(0, a) = F(a, 0) = a
2. F(m, n) = F(m - n, n) nếu m >= n
3. F(m, n) = F(m, n - m) nếu m < n
Nếu m=72, n = 48 thì sau khi thực hiện giải thuật ta được giá trị nào? A. 4 B. 10 C. 20 D. 24 31. Cho giải thuật đệ quy: 1. F(1)=F(2)=1 2.
F(k)=F(k-1)+F(k-2) nếu K>2 Hãy tính F(6)? A. 10 B. 9 C. 8 D. 7 32. Cho giải thuật đệ quy: 1.F(1)=1, F(2)=2, F(3)=3
2.F(k)=F(K-1) + 2F(K-3) , K>3 Hãy tính F(6)? A. 16 B. 15 C. 14 D. 13 lOMoAR cPSD| 58675420 33.
Có thể cài đặt danh sách bằng: A. Con trỏ B. Mảng C. Mảng và con trỏ. D. Tất cả đều sai 34.
Tính chất quan trọng của danh sách là?
A. Các phần tử của danh sách không theo thứ tự
B. Các phần tử của danh sách có thể truy nhập ngẫu nhiên.
C. Các phần tử của danh sách có thứ tự tuyến tính theo vị trí xuất hiện của chúng(position) D. Tất cả đều sai 35.
Trong các cấu trúc dữ liệu sau đâu là dữ liệu trừu tượng?
A. Cấu trúc dữ liệu dạng ngăn xếp (Stack)
B. Cấu trúc dữ liệu kiểu hàng đợi(Queue)
C. Cấu trúc dữ liệu dạng danh sách(List)
D. Tất cả cấu trúc đã nêu 36. Danh sách tuyến tính là:
A. Danh sách dạng được lưu dưới dạng mảng.
B. Danh sách mà quan hệ lân cận giữa các phần tử được xác định.
C. Danh sách tuyến tính là một danh sách có dạng (a1, a2, ..., an).
D. Danh sách tuyến tính là một danh sách rỗng. 37.
Ưu điểm của việc cài đặt danh sách bằng mảng: A.
Có thể thay đổi số lượng phần tử theo ý muốn của người dùng. B.
Có thể bổ sung hoặc xóa một phần tử bất kỳ trong mảng. C. Việc truy nhập vào
phần tử của mảng được thực hiện trực tiếp dựa vào địa chỉ tính được (chỉ số), nên tốc độ
nhanh và đồng đều đối với mọi phần tử. D. Tất cả các ý trên đều đúng. 38.
Để 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 lOMoAR cPSD| 58675420
C. Thực hiện tìm kiếm nhị phân trên danh sách móc nối đơn
D. Thực hiện tìm kiếm tuần tự từ phần tử cuối dãy 39.
Để 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 40.
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ỳ. 41.
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 42.
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; lOMoAR cPSD| 58675420 SLLPointer Ptail; } LIST; C. typedef struct SSLLIST { SLLPointer Phead; SLLPointer Ptail; int total; } LIST; D.typedef struct SSLLIST { SLLPointer Phead; int total; } LIST; lOMoAR cPSD| 58675420 43. 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. 44. 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| 58675420 45.
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); 46.
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; 47.
Thao tác nào dưới đây thực hiện trên ngăn xếp (stack)? A.
Thêm và loại bỏ phần tử luôn thực hiện tại vị trí đỉnh (top) B.
Thêm và loại bỏ phần tử có thể thực hiện tại vị trí bất kỳ C. Thêm
phần tử vào vị trí bất kỳ lOMoAR cPSD| 58675420
D. Loại bỏ phần tử tại vị trí bất kỳ 48.
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ỳ 49.
Cấu trúc dữ liệu nào tương ứng với LIFO? A.Queue B.Linked List C.Tree D. Stack 50.
Để cài đặt Stack ta có thể dùng phương pháp nào sau đây: A. Bằng mảng B. Bằng con trỏ
C. Bằng con trỏ và bằng mảng
D. Tất cả đều không đúng 51.
Danh sách tuyến tính dạng ngăn xếp là: A.
Là một danh sách tuyến tính trong đó phép bổ sung sung một phần tử vào ngăn xếp
được thực hiện ở một đầu, Và phép loại bỏ không thực hiện được. B.
Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp và
phép loại bỏ một phần tử khỏi ngăn xếp luôn luôn thực hiện ở một đầu gọi là đỉnh . C.
Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp và
phép loại bỏ một phần tử khỏi ngăn xếp luôn luôn thực hiện ở tại một vị trí bất kì trong danh sách. D.
Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp được
thực hiện ở một đầu, và phép loại bỏ được thực hiện ở đầu kia. 52.
Danh sách tuyến tính dạng ngăn xếp làm việc theo nguyên tắc? A. FIFO( first in first out) B. LIFO(last in first out) C. FOLO( fisrt out last out) D. LILO(last in last out) lOMoAR cPSD| 58675420 53.
Khi đổi một số nguyên từ hệ thập phân sang hệ nhị phân thì người ta dùng phép chia liên
tiếp cho 2 và lấy các số dư (là các chữ số nhị phân) theo chiều ngược lại.
Cơ chế sắp xếp này chính là cơ chế hoạt động của cấu trúc dữ liệu: A. Mảng (array) B. Hàng đợi(Queue) C. Bản ghi (Record) D. Ngăn xếp (stack) 54.
Định nghĩa danh sách tuyến tính Hàng đợi (Queue)? A.
Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử được thực
hiện ở một đầu, gọi là lối sau (rear) hay lối trước (front). Phép loại bỏ không thực hiện được. B.
Là một danh sách tuyến tính trong đó phép bổ sung một phần tử và phép loại bỏ một
phần tử được thực hiện ở tại một vị trí bất kì trong danh sách. C.
Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung phần tử ở một đầu, gọi
là lối sau (rear) và phép loại bỏ phần tử được thực hiện ở đầu kia, gọi là lối trước (front). D.
Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử hay loại
bỏ được thực hiện ở một đầu danh sách gọi là đỉnh (Top) 55.
Hàng đợi còn được gọi là danh sách kiểu? A. FIFO B. LIFO C. LOLO D. FILO 56.
Để thêm một đối tượng x bất kỳ vào Stack, thao tác thường dùng là: A. EMPTY(x). B. TOP(x). C. POP(x). D. PUSH(x). 57.
Để lấy loại bỏ một đối tượng ra khỏi Stack, thao tác thường dùng là: A. FULL(x) B. POP(x) C. PUSH(x) lOMoAR cPSD| 58675420 D. EMPTY(x) 58.
Để biểu diễn Stack, ta thường sử dụng kiểu dữ liệu nào sau đây? A. Mảng dữ liệu B. Kiểu bản ghi C. Danh sách móc nối
D. Danh sách móc nối và mảng dữ liệu 59.
Thao tác POP(x) dùng trong Stack là để:
A. Lấy một phần tử cuối cùng ra khỏi đỉnh Stack
B. Lấy phần tử đầu tiên ra khỏi Stack
C. Xóa bỏ một phần tử bất kì khỏi Stack
D. Xóa bỏ một dãy các phần tử ra khỏi Stack 60.
Thao tác Push(x) dùng trong Stack là để:
A. Bổ sung một phần tử vào đầu Stack
B. Bổ sung một phần tử bất kì vào Stack
C. Bổ sung một phần tử vào đỉnh Stack
D. Bổ sung một dãy các phần tử vào đỉnh Stack. 61. Bậc của một nút là:
A. Số cây con của nút đó
B. Là tổng số nút lá của cây đó
C. Là tổng số tất cả các nút thuộc cây nhận nút đó làm gốc
D. Không có đáp án đúng 62. Cây nhị phân là:
A. Cây mà mỗi nút có tối đa 2 cây con
B. Cây mà tổng số nút của nó là bội của 2
C. Mỗi nút không phải nút lá có đúng 2 con
D. Bậc của mọi nút bằng 2. 63.
Cho cây nhị phân như hình vẽ
Kết quả duyệt các phép duyệt trước, duyệt giữa, duyệt sau là: lOMoAR cPSD| 58675420 lOMoAR cPSD| 58675420
Duyệt trước: A, B, K, E, C
Duyệt giữa: K, B, E, A, C
Khi đó kết quả phép duyệt sau sẽ là:
A. Không thể xác định được B. K, B, E, C, A C. A, B, C, K, E D. K, E, B, C, A. 69.
Cho kết quả của phép phép duyệt sau và duyệt giữa như sau: Duyệt sau: D, E, B, C, A
Duyệt giữa: D, B, E, A, C
Khi đó kết quả phép duyệt trước sẽ là: A. A, B, D, E, C
B. Không thể xác định được C. D, E, B, C, A D. D, B, E, C, A 70.
Để huỷ toàn bộ cây nhị phân tìm kiếm ta có thể thực hiện thông qua thao tác duyệt cây theo thứ tự sau, nghĩa là:
A. Huỷ cây con trái, cây con phải rồi mới huỷ gốc
B. Huỷ cây con phải, cây con trái rồi mới huỷ gốc
C. Huỷ mọi cây con trái rồi mới huỷ gốc
D. Chỉ cần huỷ nút gốc vì cây mất gốc thì không thể tồn tại được. 71.
Cho cây nhị phân như sau: lOMoAR cPSD| 58675420
Với cách duyệt Inorder (Left – Root – Right) cho ra kết quả là dãy nào? Tìm lựa chọn đúng nhất A. 13 2 169 20 11 40 55 22 90 50 34 B. 13 2 55 40 169 11 20 34 50 90 22 C. 34 55 2 13 40 11 169 20 50 90 22 D. Cả a, b, c đều sai. 72. Độ cao của cây là gì?
A. Cấp lớn nhất của nút
B. Mức lớn nhất của cây C. Số cây con của cây
D. Số lượng nút của cây 73.
Cho dãy khoá 42, 23, 74, 11, 65, 58, 94, 36.Lần lượt đưa dãy khoá trên vào cây nhị phân
tìm kiếm. Nếu ta tìm kiếm trên cây nhị phân này thì trong trường hợp xấu nhất phải làm bao nhiêu phép so sánh? A. 3 B. 4 C. 5 D. 6 lOMoAR cPSD| 58675420 74.
Cho dãy khoá 42, 23, 74, 11, 65, 58, 94, 36. Lần lượt đưa dãy khoá trên vào cây nhị phân
tìm kiếm. Bây giờ ta muốn tìm kiếm xem trong dãy khoá trên có khoá 105 không thì phải
làm bao nhiêu phép so sánh? A. 3 B. 4 C. 5 D. 8 75.
Cho dãy khoá 42, 23, 74, 11, 65, 58, 94, 36. Lần lượt đưa dãy khoá trên vào cây nhị phân
tìm kiếm. Bây giờ ta muốn tìm kiếm xem trong dãy khoá trên có khoá 60 không thì phải làm bao nhiêu phép so sánh? A. 3 B. 4 C. 5 D. 7

Tài liệu liên quan: