Xác định thời gian thực hiện của chương trình là:

C. Xác định độ phức tạp của giải thuật.

A. Xác định các bước thực hiện của giải thuật

B. Xác định sai sót trong kết quả của giải thuật

Khi nói đến độ phức tạp của giải thuật là ta muốn nói đến

Hiệu quả của thời gian thực hiện của chương trình

Kết quả thu được sau khi thực hiện của chương trình

Các bước tính toán trong quá trình thực hiện chương trình

Đối với các chương trình gọi chương trình con, thì tính độ phức tạp theo nguyên tắc:

Tùy thuộc vào độ phức tạp mà lựa chọn cách tính

Đối với các chương trình không gọi chương trình con, thì dùng cách nào để phân tích, tính độ phức tạp:

Phương pháp truy hồi hoặc phương pháp đoán nghiệm.

Trong giải thuật, Ta nói rằng hàm không âm T(n) có tỷ suất tăng (growth rate) f(n) nếu tồn tại các hằng số C và N 0 sao cho :

T(n) ≤ Cf(n) với mọi n ≥ N 0

T(n) ≥ Cf(n) với mọi n ≥ N 0

T(n) ≤ Cf(n) với mọi n ≤ N 0

T(n) ≥ Cf(n) với mọi n ≥ N 0

Giả sử ta có hai giải thuật P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n 2 (với tỷ suất tăng là n 2 ) và T2(n) = 5n 3 (với tỷ suất tăng là n 3 ) . Với n > 20 , giải thuật nào sẽ thực hiện nhanh hơn?

Giải thuật P1 có thời gian thực hiện nhanh hơn giải thuật P2 (T1)

Hai giải thuật P1 và P2 có thời gian thực hiện bằng nhau tương ứng (T2 = T1)

Giải thuật P2 có thời gian thực hiện nhanh hơn giải thuật P1 (T2)

Câu trả lời phụ thuộc vào kích thước dữ liệu vào

Giả sử ta có hai giải thuật P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n 2 (với tỷ suất tăng là n 2 ) và T2(n) = 5n 3 (với tỷ suất tăng là n 3 ) . Với n < 20 , giải thuật nào sẽ thực hiện nhanh hơn?

Giải thuật P2 có thời gian thực hiện nhanh hơn giải thuật P1 (T2)

Hai giải thuật P1 và P2 có thời gian thực hiện bằng nhau tương ứng (T2 = T1)

Giải thuật P1 có thời gian thực hiện nhanh hơn giải thuật P2 (T1)

Câu trả lời phụ thuộc vào kích thước dữ liệu vào

Chọn phát biểu đúng trong các phát biểu dưới đây: bằng cách chạy thử 1 thuật toán với 1 bộ dữ liệu, ta có thể:

Khẳng định thuật toán sai nếu cho kết quả sai

Khẳng định thuật toán đúng nếu nó cho kết quả đúng

Khẳng định thuật toán tốt nếu cho kết quả nhanh

Khẳng định thuật toán hiệu quả nếu cho kết quả đúng

Mục đích của việc sắp xếp là:

Sử dụng khả năng truy nhập ngẫu nhiên của bộ nhớ để truy nhập được thực hiện nhanh

Tổ chức lại các mẩu tin sao cho các khóa của chúng được sắp thứ tự tương ứng với quy luật sắp xếp

Tìm kiếm một đối tượng trong một danh sách các đối tượng bằng giải thuật tìm kiếm nhị phân nhanh chóng

Nhân tố nào là nhân tố chính ảnh hưởng đến thời gian thực hiện của một giải thuật?

Kích thước của dữ liệu đầu vào

Kiểu lệnh được sử dụng

Để lựa chọn một giải thuật tốt, ta sẽ căn cứ vào tiêu

Giải thuật thực hiện nhanh.

Để kiểm tra tính đúng đắn của giải thuật chúng ta có thể

Cài đặt giải thuật đó và cho thực hiện trên máy với một số bộ dữ liệu mẫu rồi lấy kết quả thu được so sánh với kết quả đã biết

Cài đặt giải thuật đó và cho thực hiện trên máy với một số bộ dữ liệu mẫu

Đo lường thời gian thực hiện của hoạt động trên một máy tính xác định hợp được chọn lọc các dữ liệu vào.

Xác định bởi số các lệnh được thực hiện trong một máy tính lý tưởng

Thời gian thực hiện chương trình là

Một hàm của kích thước dữ liệu vào, ký hiệu T(n) trong đó n là kích thước (độ lớn) của dữ liệu vào.

Một hàm của độ dài dữ liệu vào, ký hiệu N(x) trong đó x là độ dài của dữ liệu vào.

Thời gian ngắn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n.

Thời gian thực hiện chương trình trong trường hợp nhanh nhất trên dữ liệu vào có kích thước n

Ðơn vị đo thời gian thực hiện là:

Đơn vị đo thời gian bình thường giờ, phút ,giây...

Không phải là đơn vị đo thời gian bình thường như giờ, phút, giây....

Được xác định bởi thời gian được thực hiện trong một máy tính lý tưởng

Thường ta coi T(n) là thời gian thực hiện chương trình trong trường hợp xấu nhất trên dữ liệu vào có kích thước n, tức T(n) là:

Thời gian lớn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n.

Thời gian nhỏ nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước T

Thời gian nhỏ nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n

Thời gian lớn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước T

Trong bài toàn sắp xếp, sắp xếp ngoài là:

Là sự sắp xếp được sử dụng khi số lượng đối tượng cần sắp xếp lớn không thể lưu trữ trong bộ nhớ trong mà phải lưu trữ trên bộ nhớ ngoài

Sự sắp xếp dữ liệu được tổ chức trong bộ nhớ trong của máy tính

Là sự sắp xếp dữ liệu được tổ chức sắp xếp dữ liệu được lưu trữ trong các tập tin

Trong bài toàn sắp xếp, sắp xếp trong là:

Sự sắp xếp dữ liệu được tổ chức trong bộ nhớ trong của máy tính

Là sự sắp xếp được sử dụng khi số lượng đối tượng cần sắp xếp lớn không thể lưu trữ trong bộ nhớ trong mà phải lưu trữ trên bộ nhớ ngoài

Là sự sắp xếp dữ liệu được tổ chức sắp xếp dữ liệu được lưu trữ trong các tập tin

Trong giải thuật QuickSort, các bước để tiến hành sắp xếp mảng a[i]..a[j] là:

1. Xác định chốt 2. Phân hoạch mảng đã cho thành các mảng con a[i]..a[k-1] , a[k] và a[k+1]..a[j] sao cho a[i], .., a[k-1] < a[k] và a[k+1], .., a[j] >a[k] . 3. Sắp xếp mảng a[i]..a[k-1] ( Đệ quy ) 4. Sắp xếp mảng a[k+1]..a[j] (Ðệ quy)

1. Phân hoạch mảng đã cho thành hai mảng con a[i]..a[k-1] và a[k]..a[j]. 2. Xác định chốt 3. Sắp xếp mảng a[i]..a[k-1] ( Đệ quy ) 4. Sắp xếp mảng a[k]..a[j] (Ðệ quy)

1. Phân hoạch mảng đã cho thành hai mảng con 2. Sắp xếp mảng a[i]..a[k-1] ( Đệ quy ) 3. Sắp xếp mảng a[k]..a[j] (Ðệ quy) 4. Xác định chốt

Chọn phát biểu sai trong các phát biểu sau:

Thuật toán tìm kiếm nhị phân chỉ áp dụng được trên dãy tăng.

Thuật toán tìm kiếm nhị phân áp dụng được trên dãy sắp xếp.

Thuật toán tìm kiếm nhị phân áp dụng được trên dãy sắp xếp tăng.

Thuật toán tìm kiếm nhị phân áp dụng được trên dãy sắp xếp giảm.

. Cho đoạn mã chương trình sau: for i := 1 to n - 1 do begin i . m := i; ii . for j := i + 1 to n do if K[j] < K[m] then m := j; iii . if m <> i then Begin X := K[i]; K[i] := K[m]; K[m] := X; End; end;

Sắp xếp dãy khóa theo thứ tự tăng dần bằng phương pháp lựa chọn.

Sắp xếp dãy khóa theo thứ tự giảm dần bằng phương pháp lựa chọn.

Sắp xếp dãy khóa theo thứ tự tăng dần bằng phương pháp thêm dần.

Sắp xếp dãy khóa theo thứ tự giảm dần bằng phương pháp thêm dần.

Cho đoạn chương trình sau void main() { int a[50], n, i, k; k = a[0]; for(i=0;i<n;i++) if(a[i]>k) k=a[i]; } Chọn phát biểu đúng trong các phát biểu sau:

k mang giá trị lớn nhất trong mảng

a[k] mang giá trị lớn nhất trong mảng

a[k] mang giá trị nhỏ nhất trong mảng

k mang giá trị nhỏ nhất trong mảng

Đoạn mã giả dưới đây mô tả thuật toán gì? 1. k[0] := - ¥; 2. for i := 2 to n do begin X := k[i]; j := i-1; while x < k[j] do begin k[j+1] := k[j]; j := j-1; end; k[j+1] := X; end; 3. return

Sắp xếp dãy khóa theo thứ tự tăng dần bằng phương pháp thêm dần

Sắp xếp dãy khóa theo thứ tự giảm dần bằng phương pháp lựa chọn.

Sắp xếp dãy khóa theo thứ tự tăng dần bằng phương pháp lựa chọn

Sắp xếp dãy khóa theo thứ tự giảm dần bằng phương pháp thêm dần.

Đoạn mã giả dưới đây mô tả thuật toán gì? 1. i:=1; K[n +1] := X; 2. while K[i] <> X do i := i+1; 3. if i = n +1 then return (0) else return (i);

Tìm kiếm tuyến tính phần tử có giá trị X

Tìm kiếm nhị phân phần tử có giá trị X

Tìm phần tử nhỏ nhất của mảng

Tìm phần tử lớn nhất của mảng

Giải thuật sắp xếp kiểu nổi bọt Procedure Bubble_sort(k, n) {1} for i := 1 to n-1 do {2} for j := n downto i+1 do {3} if k[j] < k[j-1] then sw (k[j], k[j-1]); Thủ tục sw thực hiện nhiệm vụ gì?

Không có phương án nào đúng.

Trong giải thuật sắp xếp Quicksort, phần tử chốt tốt nhất là:

Phần tử trung vị của dãy.

Phần tử đầu tiên trong dãy.

Phần tử cuối cùng trong dãy.

Đoạn mã giả dưới đây mô tả thuật toán gì? 1. l :=1;r :=n; 2. while l r do begin m:=[(l+r)/2]; if X < K[m] then r := m - 1 else if X > K[m] then l := m+1 else return (m); end; 3.return (0);

Tìm kiếm nhị phân phần tử có giá trị X

Tìm phần tử nhỏ nhất của mảng

Tìm kiếm tuyến tính phần tử có giá trị X

Tìm phần tử lớn nhất của mảng

Phép “hòa nhập hai đường” chỉ có thể áp dụng cho 2 dãy con thỏa mãn tính chất:

Hai dãy đã được sắp xếp

Cấu trúc dữ liệu nào tương ứng với LIFO (Last In First Out)

Hai dãy đã được sắp xếp

Thao tác nào dưới đây thực hiện trên hàng đợi (Queue):

Thêm phần tử vào lối sau

Loại bỏ phần tử ở lối sau

Thêm phần tử vào lối trước

Thêm và loại bỏ phần tử tại vị trí bất kỳ

Thao tác nào dưới đây thực hiện trên ngăn xếp (Stack):

Phép thêm, bớt phần tử chỉ thực hiện ở một đầu.

Loại bỏ phần tử ở lối sau, thêm phần tử ở lối trước

Thêm phần tử vào lối sau, loại phần tử ở lối trước

Thêm và loại bỏ phần tử tại vị trí bất kỳ

Chọn định nghĩa đúng nhất về hàng đợi (Queue):

Hàng đợi là một danh sách mà trong đó thao tác thêm 1 phần tử vào trong danh sách được thực hiện 1 đầu này và lấy 1 phần tử trong danh sách lại thực hiện bởi đầu kia.

Hàng đợi còn được gọi là danh sách FILO và cấu trúc dữ liệu này còn được gọi cấu trúc FILO (First In Last Out)

Hàng đợi là một danh sách mà trong đó thao tác thêm 1 phần tử hay hủy một phần tử trong danh sách được thực hiện 1 đầu.

Hàng đợi phải là một danh sách liên kết đơn.

Định nghĩa cấu trúc dữ liệu của danh sách liên kết đơn được mô tả như sau: struct Node { int Key; Node * NextNode; } OneNode; Trong đó, khai báo Node * NextNode; dùng để mô tả

Vùng liên kết quản lý địa chỉ phần tử kế tiếp

Con trỏ trỏ tới phần dữ liệu

Con trỏ trỏ tới phần dữ liệu cuối của danh sách

Vùng liên kết quản lý địa chỉ phần tử kế tiếp của phần tử cuối

Định nghĩa nào là đúng với danh sách liên kết

Danh sách liên kết là tập hợp các phần tử mà giữa chúng có một sự nối kết với nhau thông qua vùng liên kết của chúng.

Danh sách liên kết là cấu trúc dữ liệu dạng cây.

Danh sách liên kết là cấu trúc dữ liệu tự định nghĩa.

Danh sách liên kết là tập hợp các phần tử mà đặt kề cận với nhau trong vùng nhớ.

Lựa chọn câu đúng nhất về danh sách liên kết đôi (Doubly Linked List)

Vùng liên kết của một phần tử trong danh sách liên đôi có 02 mối liên kết với 02 trước và sau nó trong danh sách.

Vùng liên kết của một phần tử trong danh sách liên đôi có 02 mối liên kết với 01 phần tử khác trong danh sách.

Vùng liên kết của một phần tử trong danh sách liên đôi có 01 mối liên kết với 02 phần tử khác trong danh sách.

Vùng liên kết của một phần tử trong danh sách liên đôi có 02 mối liên kết với phần tử đầu và cuối của danh sách.

Chọn định nghĩa đúng nhất đối với cây nhị phân tìm kiếm

Cây nhị phân tìm kiếm là cây nhị phân có thành phần khóa của mọi nút lớn hơn thành phần khóa của tất cả các nút trong cây con trái của nó và nhỏ hơn thành phần khóa của tất cả các nút trong cây con phải của nó.

Cây nhị phân tìm kiếm là cây nhị phân có thành phần khóa của mọi nút nhỏ hơn thành phần khóa của tất cả các nút trong cây con trái của nó và nhỏ hơn thành phần khóa của tất cả các nút trong cây con phải của nó.

Cây nhị phân tìm kiếm là cây nhị phân có thành phần khóa của mọi nút lớn hơn thành phần khóa của tất cả các nút trong cây con trái của nó và lớn hơn thành phần khóa của tất cả các nút trong cây con phải của nó.

Cây nhị phân tìm kiếm chính là cây nhị phân

Bài kiểm tra số 2

Quiz

•

Computers

•

University

•

Practice Problem

•

Easy

Trần Trang

Used 9+ times

FREE Resource

65 questions

Show all answers

1.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

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:

Cấu trúc dữ liệu + Giải thuật = Chương trình

Cấu trúc dữ liệu + Chương trình = Giải thuật

Chương trình + Giải thuật = Cấu trúc dữ liệu

Cấu trúc dữ liệu = Chương trình

2.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Để đánh giá một cấu trúc dữ liệu ta thường dựa vào một số tiêu chí

Cấu trúc dữ liệu phải tiết kiệm tài nguyên (bộ nhớ trong),

Cấu trúc dữ liệu phải phản ảnh đúng thực tế của bài toán,

Cấu trúc dữ liệu phải dễ dàng trong việc thao tác dữ liệu.

Cả a, b, c đều đúng

3.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Để đánh giá giải thuật ta sử dụng khái niệm:

Quy tắc cộng, quy tắc nhân và quy tắc chung

Phương trình đệ quy, nghiệm của phương trình đệ quy

Độ phức tạp và ký hiệu ô lớn

4.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng:

Qui tắc cộng

Qui tắc trừ

Qui tắc nhân

Tất cả đều đúng

5.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Trong qui tắc tổng quát, thời gian thực hiện của mỗi lệnh gán, scanf, printf là:

C(0)

C(1)

O(0)

O(1)

6.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Theo qui tắc cộng, nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1 và P2; và T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện của đoạn hai chương trình đó nối tiếp nhau là:

T(n) = O(min(f(n),g(n)))

T(n) = O(max(f(n),g(n)))

T(n) = O(f(n).g(n))

T(n) = max(O(f(n)), O(g(n)))

7.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Có thể tính độ phức tạp của một giải thuật theo nguyên tắc:

Qui tắc cộng

Qui tắc nhân

Qui tắc tổng quát để phân tích một chương trình

Tất cả đều đúng

Create a free account and access millions of resources

Create resources

Host any resource

Get auto-graded reports

Continue with Google

Continue with Email

Continue with Classlink

Continue with Clever

or continue with

Microsoft

Apple

Others

Already have an account?

Similar Resources on Wayground

65 questions

Câu hỏi về giao tiếp qua mạng

Quiz

•

12th Grade - University

64 questions

Câu hỏi về CSS và HTML

Quiz

•

University

66 questions

ÔN TẬP GK2 TIN 10

Quiz

•

University

69 questions

Unit 18 and Unit N02

Quiz

•

University

64 questions

Kiến thức về hệ thống thông tin

Quiz

•

University

63 questions

TRIẾT HỌC MÁC CHƯƠNG !

Quiz

•

University

69 questions

Câu hỏi về mã độc và phân tích

Quiz

•

University

60 questions

Chương 2_Mạng máy tính và Internet

Quiz

•

University

Popular Resources on Wayground

25 questions

Multiplication Facts

Quiz

•

5th Grade

15 questions

4:3 Model Multiplication of Decimals by Whole Numbers

Quiz

•

5th Grade

10 questions

The Best Christmas Pageant Ever Chapters 1 & 2

Quiz

•

4th Grade

12 questions

Unit 4 Review Day

Quiz

•

3rd Grade

20 questions

Christmas Trivia

Quiz

•

6th - 8th Grade

18 questions

Kids Christmas Trivia

Quiz

•

KG - 5th Grade

14 questions

Christmas Trivia

Quiz

•

5th Grade

15 questions

Solving Equations with Variables on Both Sides Review

Quiz

•

8th Grade

Discover more resources for Computers

26 questions

Christmas Movie Trivia

Lesson

•

8th Grade - Professio...

7 questions

Different Types of Energy

Interactive video

•

4th Grade - University

7 questions

Transition Words and Phrases

Interactive video

•

4th Grade - University

7 questions

Force and Motion

Interactive video

•

4th Grade - University

7 questions

Biomolecules (Updated)

Interactive video

•

11th Grade - University

34 questions

Unit 5 Review - The Middle Ages in Europe-B

Quiz

•

9th Grade - University

26 questions

Day2 classwork: Permutation and combination

Quiz

•

2nd Grade - University

5 questions

Using Context Clues

Interactive video

•

4th Grade - University

Bài kiểm tra số 2

65 questions

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:

Để đánh giá một cấu trúc dữ liệu ta thường dựa vào một số tiêu chí

Để đánh giá giải thuật ta sử dụng khái niệm:

Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng:

Trong qui tắc tổng quát, thời gian thực hiện của mỗi lệnh gán, scanf, printf là:

Theo qui tắc cộng, nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1 và P2; và T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện của đoạn hai chương trình đó nối tiếp nhau là:

Có thể tính độ phức tạp của một giải thuật theo nguyên tắc:

Xác định thời gian thực hiện của chương trình là:

Khi nói đến độ phức tạp của giải thuật là ta muốn nói đến

Khi nói đến độ phức tạp của giải thuật là ta muốn nói đếnHàm thể hiện độ phức tạp có dạng thường gặp là:

Create a free account and access millions of resources

Similar Resources on Wayground

Popular Resources on Wayground

Discover more resources for Computers

Khi nói đến độ phức tạp của giải thuật là ta muốn nói đến
Hàm thể hiện độ phức tạp có dạng thường gặp là: