Free Printable CTDL

Worksheets

CTDL_3

Total questions: 51

Worksheet time: 51mins

Name

Class

Date

Đối với một giải thuật, ta thường sử dụng những quy tắc nào để đánh giá độ phức tạp của giải thuật?

Quy tắc nhân.

Quy tắc tỏng và quy tắc nhân.

Quy tắc tỏng.

Không dùng quy tắc nào.

Cho biết dộ phức tạp của giải thuật sau:

sum=0;

for(i=0;i<n;i++){

sum=sum+i*i; }

O(n²)

O(n³)

O(n)

O(log₂n)

Cho biết độ phức tạp của giải thuật tính tổng các nghịch đảo của n số tự nhiên đầu tiên.

O(n²)

O(n3)

O(log₂n)

O(n)

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 nào dưới đây?

Giải thuật=Chương trình.

CTDL+Chương trình=Giải thuật.

CTDL+Giải thuật=Chương trình.

CTDL=Giải thuật+Chương trình.

Với a được khai báo là số nguyên và giá trị khởi tạo là 1, cho biết kết quả của câu lệnh: printf("%d",a==2? 5:2);

Để đánh giá một CTDL chúng ta thường dựa vào những tiêu chí nào?

CTDL phải phản ánh đúng thực tế của bài toán.

CTDL phải dễ dàng trong việc thao tác dữ liệu.

CTDL phải tiết kiệm tài nguyên (bộ nhớ trong).

Cả 3 tiêu chí trên.

Cho chương trình sau:

#include <stdio.h>

float Tinh(float n){ if(n==1) return 0.5;

return Tinh(n-1) + 1/(2*n);}

int main(){ printf("\nkq= %3.2f", Tinh(4); }

Cho biết kết quả hiển thị ra màn hình khi chạy chương trình trên.

1.041667

1.04

3.2

1.041

Cho biết phân cơ sở của giải thuật sau:

int Tinh(int n){ if(n==1) return 1;

return Tinh(n-1) + n;}

if(n==1) return 1;

int Tinh(int n){

return

$Cho\ S\left(n\right)=\frac{1}{2}+\frac{3}{4}+\frac{5}{6}+\cdot\cdot\cdot+\frac{\left(2n+1\right)}{\left(2n+2\right)}$ , n là số nguyên không âm. viết công thức truy hồi cho S(n)

$S(n)=\frac{\left(2n+1\right)}{\left(2n+2\right)}$

$S(n)=S\left(n-1\right)+\frac{\left(2n+1\right)}{\left(2n+2\right)}$

$S(n)=\frac{1}{2}$

$S(n)=0$

10.

Khi viết giải thuật tính xⁿ với x là số thực, n là số nguyên, ta phải xét những trường hợp nào của n?

n>0

n=0

Cả 3 phương án

n<0

11.

Khi viết chương trình đệ quy tính Fibonacci thứ n, điều kiện nào của n là điều kiện cơ sở, biết F(0)=F(1), F(n)= F(n-1)+F(n-2).

n<2

n=2

n=4

n=3

12.

Khi nào không nên dùng đệ quy?

Mọi trường hợp.

Không trường hợp nào.

Khi chương trình có thể viết dưới dạng lặp hoặc cấu trúc lệnh khác.

Khi chương trình có thể viết dưới dạng cấu trúc điều kiên.

13.

Để nhập một dãy gồm n số nguyên ta dùng lệnh nào dưới đay?

Lệch switch và scanf.

Lệnh printf.

Lệnh if và scanf.

Kết hợp giữa lệnh lặp và lệnh scanf.

14.

Cho danh sách đặc L có kiểu dữ liệu là cấu trúc List, Count là biến số nguyên lưu trữ số phần tử hiện tại của L, Lệnh nào trong các lệnh sau đay được sử dụng trong hàm kiểm tra danh sách rỗng?

return (L.Count==0);

return (L.Count==1);

return (L.Count=0);

return (L.Count=1);

15.

Cho khai báo CTDL cho danh sách đặc như sau:

typedef struct list{ int a[100]; int Last;} List;

List L;

Khi xóa một phần tử ra khỏi L thì giá trị của biến Last thay đổi ntn?

Last++

Last =0

Last--

Last=1

16.

Với khai báo, danh sách L kiểu List có tối đa bao nhiêu phần tử?

typedef struct list{ int a[100]; int Last;}List;

Không giới hạn phần tử

100 phần tử.

200 phần tử

10 phần tử

17.

Điền phần còn thiếu vào chỗ chống trong phát biểu sau: "Hàng đợi (queue) là một cấu trúc dữ liệu dùng để chứa các đối tượng làm việc theo cơ chế ............."

FIFO

FILO

ILOL

LIFO

18.

Điền phần còn thiếu vào chỗ chống trong phát biểu sau: "Ngăn xếp (Stack) là một cấu trúc dữ liệu dùng để chứa các đối tượng làm việc theo cơ chế ............."

ILOL

FIFO

LIFO

IFLO

19.

10 * 25 40 + 60/30-

10*25+40-60 30/

-* 10 * 25 40 / 60 30

10 25 40+ * 60 30 / -

20.

120

1200

100

1300

21.

655

650

648

600

22.

Phát biểu nà sau đây đúng với nút gốc của một cây nhị phân?

Nút gốc của cây nhị phân luôn con và có cha.

Nút gốc của cây nhị phân chỉ có con mà không có cha.

Nút gốc của cây nhị phân không có con mà chỉ có cha.

Nút gốc của cây nhị phân không có con và không có cha.

23.

10, 25, 40, 60

20, 50.

30, 20, 50.

30, 20, 50, 10, 25, 40, 60.

24.

25.

Phát biểu nào sau đây đúng với tính chất của cây VUN ĐỐNG?

Bút con trái có khóa lớn hơn khóa của nút con phải.

Nút con trái có khóa lớn hơn nút cha

Khó của nút cha bao giờ cũng lớn hơn khóa của nút con.

Khóa của các nút lớn hơn khóa của nút cha.

26.

Nhược điểm điểm lớn nhất của giải thuật tìm kiếm nhị phân là gì?

Luôn duyệt hết dãy.

Số phép so sánh nhiều.

Số lần lặp ( hoặc gọi đệ quy ) nhiều.

Dãy cần tìm phải được sắp xếp theo thứ tự nhất định.

27.

Phương pháp sắp xếp nào phải chọn khóa "chốt"?

Phương pháp sắp xếp kiểu chèn trục tiếp.

Phương pháp sắp xếp phân đoạn( sắp xếp nhanh ).

Phương pháp sắp xếp kiểu đổi chỗ.

Phương pháp sắp xếp trộn.

28.

Tư tưởng: "Tách mảng M thành các mảng con theo các đường chạy (run) rồi sau đó tiến hành nhập các mảng này lại the từng cặp dường chạy để tạo thành các đường chạy mới có chiều dài lớn hơn đường chạy cũ. Sau một số lần tách/nhập thì cuối cùng mảng M chỉ còn lại 1 đường chạy, lúc đó thì các phần tử trên mảng M sẽ trở nên có thứ tự."

Tư tưởng trên thược phương pháp sắp xếp nào?

Săp xếp trộn ( hòa nhập )

Sắp xếp nhanh ( phân đoạn )

Sắp xếp vun đống

Sắp xếp nổi bọt

29.

Phương pháp sắp xếp ngoại dữ liệu cần sắp xếp được lưu trữ ở đâu?

Thanh ghi

ROM

Bộ nhớ ngoài

RAM

30.

Phương án nào sau đây cho phép hóa vị hai phần tử kề nhau trong mảng A?

tg = A[j];

{ tg = A[j-1], A[j-1]=A[j]; A[j] = tg; }

tg = A[j-1];

A[j] = tg;

31.

Cho độ phức tạp của đoạn trương trình sau:

for(i=0;i<n;i++){ s=1;

for(j=0;j<n;j++){

s/=(j+1); }

n³

n²

nlog₂n

32.

Cho biết hàm sau thực hiện chứa năng gì?

int Cop(int M[], int Len, int CM[]){

for(int i=0; i<Len;i++) CM[i]=M[i];

return (Len);}

Hàm thực hiện việc sao chép nội dung mảng M có chiều dài Len-1 về mảng CM có cùng chiều dài. Hàm trả về chiều dài của mảng CM sau khi sao chép.

Hàm thực hiện việc sao chép nội dung mảng CM có chiều dài Len-1 về mảng M có cùng chiều dài. Hàm trả về chiều dài của mảng M sau khi sao chép.

Hàm thực hiện việc sao chép nội dung mảng CM có chiều dài Len về mảng CM có cùng chiều dài. Hàm trả về chiều dài của mảng M sau khi sao chép.

Hàm thực hiện việc sao chép nội dung mảng M có chiều dài Len về mảng CM có cùng chiều dài. Hàm trả về chiều dài của mảng CM sau khi sao chép.

33.

CTDL khai báo kiểu dữ liệu sinh viên như sau:

typedef struct tagSV{ char MSSV[8]; char Ten[30];

char ngaysinh[11]; float DTB;} SV;

SV sv1, *sv2;

Lựa chọn đúng nhất để nhập mã sinh viên của hai biến sv1, sv2?

gets(sv1->MSSV); gets(sv2->MSSV);

gets(sv1.MSSV); gets(sv2->MSSV);

gets(sv1.MSSV); gets(sv2.MSSV);

gets(sv1->MSSV); gets(sv2.MSSV);

34.

Cho hàm sau đây, đâu là phần cơ sở của hàm kt(n)?

int kt(int n) { if(n==0) return 1;

if(n%2==1) return 0;

if(n%2==0) return kt(n/10);}

if(n==0) return 1; if(n%2==1) return 0;

if(n==0) return 1;

if(n%2==1) return 0;

if(n%2==0) return kt(n/10);

35.

Phương án nào không phải là nhược điểm của giải thuạt đệ quy?

Việc chuyển giao điều khiển từ các thủ tục cũng cần được lưu trữ các thông số dùng cho việc trả lại điều khiển cho thủ tực ban đầu.

Giải thuật đệ quy ngắn ngọn, dễ viết chương trình.

Việc sử dụng đệ quy đôi khi tạo ra các tính toán thừa, không cần thiết cho tính tự động gọi thực hiện thủ tục khi chưa gặp điều kiện dừng đệ quy.

Khi một thủ tục đệ quy gọi chính nó, tập các đối tượng được sử dụng trong thủ tục này như biến, hằng, ... sẽ được tạo ra.

36.

Viết\ công\ thức\ giảm\ kích\ thước\ cho\ bài\ toán\ a^n.\ a^n=\left\{1\ nếu\ n=0,\ \left(a^{\left(\frac{n}{2}\right)}\right)^2\ nếu\ n\ chẵn,\ a\times\left(a^{\left(\frac{n}{2}\right)}\right)^2\ nếu\ n\ lẻ\right\}

chưa bt

a*a

$a\times\left(a^{\left(\frac{n}{2}\right)}\right)^2$

37.

Cho khai báo: typedef struct tagNode{

int Data;

struct tagNode *next; }OneNode;

typedef Node *List;

Lệnh nào dưới đây thể hiện q là con rỏ kế tiếp của p?

q->next=p;

q=p;

p=q;

p->next=q;

38.

Cho khai báo sau:

typedef struct Node{ int Data; struct Node *Left;

struct Node *Right; }DNode;

DNode *p;

Trong ngôn ngữ lập trình C, lệnh nào dùng để xin giải phóng bộ nhớ cho con troe p?

p=NULL;

free(p);

p=NIL;

p=(DNode *) malloc (sizeof(DNode));

39.

Tổ chức CTDL cho danh sách liên kết đơn:

typedef struct ds{ int Data; struct ds *next; }Node;

Node *p, *q;

Để nố nút kế sau p vào sau nút q, ta dùng lệnh nào?

p=q->next;

q->next=p->next;

q=p->next;

p->next=q;

40.

Khi tìm một phần tử có giái trị x trên cây Root khác rỗng, phải so sách giá trị x với nội dung nào trên cây đầu tiên?

So sánh với nội dung của nút nhỏ nhất ở cây con trái của nút gốc.

So sánh x với nội dung của nút gốc.

So sánh với nội dung của nút trái của gốc.

So sánh với nội dung của nút phải của gốc.

41.

Giá trị lớn nhất trên cây nhị phân tìm kiếm khác rỗng nằm ở vị trí nào?

Nút phải nhất

Nút trái nhất

Nút gốc

Nút bất kì

42.

Cây kết quả khong có nút có giá trị 60.

Cây rỗng.

Cây cho kết quả giống cây bên đầu.

Cây kết quả có 2 nút có giá trị bằng 60.

43.

Số lượng nút tối đa các nút trên một cây nhị phân có chiều cao h là:

2^h-1 +1(h>0)

2^h-1 (h>0)

2^h + 1 (h>0)

2^h-1 -1(h>0)

44.

Trong các thuật toán sắp xếp, phép toán nào được sử dụng nhiều nhất?

Phép gán.

Phép tăng các giá trị.

Phép so sánh.

Phép cộng.

45.

Khi thêm một phần tử có nội dung x vào tại vị trí k (0<k<Last+2) của danh sách đặc L, Last là độ dài hiện tại của danh sách, giải thuật được thực hiện:

+Độ dài danh sách tăng 1.

+Dời các phần tử từ vị trí p đến cuối danh sách ra sau ( bên phải ) 1 vị trí.

+Đưa phần tử mới vào vị trí p.

+Dời các phần tử từ vị trí p đến cuối danh sách ra sau ( bên phải ) 1 vị trí.

+Độ dài danh sách tăng 1.

+Đưa phần tử mới vào vị trí p.

+Độ dài danh sách tăng 1.

+Dời các phần tử từ vị trí p đến cuối danh sách ra sau ( bên phải ) 1 vị trí.

+Độ dài danh sách tăng 1.

+Đưa phần tử mới vào vị trí p.

+Dời các phần tử từ vị trí p đến cuối danh sách ra sau ( bên phải ) 1 vị trí.

46.

Cho ý tưởng: "Dựa vào tư tương chia để trị, chia dãy đầu k₁,...,k_n thành 2 dãy con k₁,...,k_i và dãy con k_i+1 sao cho khóa k_j, i=[1...m]; j=[m+1...n]. sau đó lần lượt sắp xếp 2 dãy con cũng vớ phương pháp trên ta thu được dãy ban đầu đã sắp xếp."

Ý tưởng trên thuộc phương pháp sắp xếp nào?

Phương pháp sắp xếp đổi chỗ trực tiếp.

Phương pháp sắp xếp nhanh ( phân đoạn).

Phương pháp sắp xếp trộn ( hòa nhập ).

Phương pháp sắp xếp chèn.

47.

Giải thuạt trộn 2 dãy k₁,.....,k_i và k_i+1,.....,k_n đã sắp xếp thành một dãy mới cũng được sắp xếp, ta phải sử dụng mấy để trộn hai dãy trên được thuật lợi, đó là những chỉ số nào?

Không cần chỉ số nào.

hai chỉ số dùng cho hai dãy k₁,.....,k_i và k_i+1,.....,k_n

Ba chỉ số dùng cho hai dãy cần trộn và dãy kết quả.

Một chỉ số dùng cho dãy kết quả.

48.

Trong phương pháp sắp xếp chọn trực tiếp một mảng các số nguyên, lệnh nào thường dùng trong vòng lặp thứ hai của giải thuật dùng biến đếm j để ghi nhận vị trí của phần tử nhỏ nhất trong đoạn đang sắp xếp cho biến min.

min =1

min = j

min = j + 1

min = n

49.

Phát biểu nào sau đây đúng với khử đệ quy ?

Khủ đệ quy là biến một thủ tục đệ quy thành một thủ không chứa vòng lặp và không ảnh hưởng gì đến các yếu tố khác

Khử đệ quy là biến một thủ tục đệ quy thành một thủ tục chỉ chứa câu lệnh điều kiện mà không ảnh hưởng gì đến các yếu tố khác.

Khử đệ quy là biến một thủ tục đệ quy thành một thủ tục chỉ chứa vòng lặp mà không ảnh hưởng gì đến các yếu tố khác.

Khử đệ quy là biến một thủ tục đệ quy thành một thủ tục Không chứa các vòng lặp và ảnh hưởng đến các yếu tố khác.

50.

Trong giải thuật tìm giá trị lớn nhất trong một mảng số nguyên bất kì, độ phức tạp của giải thuật trong th tốt nhất và th xấu nhất là bao nhiêu?

Tốt nhất: O(n)-Tồi nhất: O(n).

Tốt nhất: O(n)-Tồi nhất: O(n²).

Tốt nhất: O(1)-Tồi nhất: O(1).

Tốt nhất: O(log₂n)-Tồi nhất: O(n).

51.

Đứa nào lười nhất và khôn nhất trong nhóm?

Hiệp

Đại mõm chứ ai.

con ăn ko ở đợ

Reset

CTDL_3

Total questions: 51

Worksheet time: 51mins

Similar Resources on Wayground