Đánh giá độ phức tạp của giải thuật là việc xác định ……và…… mà giải thuật cần để thưc hiện giải một bài toán

Khoảng thời gian, dung lượng bộ nhớ máy tính

Khoảng thời gian, độ khó

Khoảng thời gian, độ phức tạp

Độ khó, dung lượng bộ nhớ máy tính

Các kiểu dữ liệu cơ bản là……

Các kiểu dữ liệu mà người lập trình được cung cấp sẵn từ ngôn ngữ lập trình

Các kiểu dữ liệu mà người lập trình được cung cấp sẵn từ máy tính

Các kiểu dữ liệu mà người lập trình được cung cấp sẵn từ ngôn ngữ tự nhiên

Các kiểu dữ liệu mà người lập trìn được cung cấp sẵn từ ngôn ngữ này

Cài đặt danh sách bằng mảng có nghiã là

Dùng một mảng (array) để lưu trữ liên tiếp các phần tử của danh sách bắt đầu từ vị trí đầu tiên của mảng.

Dùng bản ghi có hai thành phần để lưu trữ các phần tử của danh sách

Dùng biến con trỏ lưu trữ các phần tử của danh sách.

Tư tưởng của giải thuật tìm kiếm nhị phân:

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 quyế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.

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.

Lần lượt chia dãy thành hai dãy con dựa vào phần tử khoá, sau đó thực hiện việc tìm kiếm trên hai đoạn đã chia.

Tìm kiếm dựa vào cây nhị tìm kiếm.

Tư tưởng của giải thuật tìm kiếm tuần tự

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.

Tìm kiếm dựa vào cây nhị tìm kiếm: Nếu giá trị cần tìm nhỏ hơn gốc thì thực hiện tìm kiếm trên cây con trái, ngược lại ta việc tìm kiếm được thực hiện trên cây con phải.

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 quyế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.

Lần lượt chia dãy thành hai dãy con dựa vào phần tử khoá, sau đó thực hiện việc tìm kiếm trên hai đoạn đã chia.

Danh sách Đặc là:

Một tập hợp có thứ tự gồm một số xác định n phần tử cùng kiểu dữ liệu liên tục trong bộ nhớ và có cùng một tên (với n được gọi là độ dài hay kích thước của mảng).

Một tập hợp mà không cần khai báo trước số lượng phần tử khi sử dụng

Một các phần từ được xác định trước, có cùng kiểu dữ liệu và nằm rài rác trong vùng nhớ

Một tập các hợp phần tử có cùng kiểu dữ liệu và được sắp xếp theo thứ tự tăng dần.

Ý tưởng phương pháp sắp xếp nổi bọt (bubble sort) là:

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.

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.

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ương tự đối với phần tử nhỏ thứ hai, ba...

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.

Ý tưởng phương pháp sắp xếp nhanh (Quick sort) là:

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á).

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, ba...

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ắ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.

Trong thuật toán sắp xếp nổi bọt kết thúc khi nào?

Khi các phần tử đã nằm đúng thứ tự mong muốn.

Không còn bất kì cặp liền kề trái thứ tự mong muốn

Không còn xảy ra đổi chỗ lần nào nữa

Định nghĩa đúng nhất về 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ó 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ế 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ừ liên tục trong vùng nhớ

Chọn câu nói đúng nhất về danh sách liên kết đôi

Vùng liên kết của 1 phần từ trong danh sách liên kết có 2 mối liên kết với 2 phần tử trước và sau nó trong danh sách

Vùng liên kết của 1 phần từ trong danh sách liên kết có 2 mối liên kết với 1 phần tử khác

Vùng liên kết của 1 phần từ trong danh sách liên kết có 1 mối liên kết với 2 phần tử khác

Vùng liên kết của 1 phần từ trong danh sách liên kết có 2 mối liên kết với 2 phần tử khác trong danh sách

Định nghĩa cấu trúc dữ liệu dạng danh sách(LIST)

danh sách là một tập hợp các phần tử có cùng một kiểu mà ta gọi là kiểu phần tử (ElementType).

danh sách là kiểu con trỏ

danh sách là tập hợp các phần tử khác kiểu

danh sách là kiểu dữ liệu mảng

Cho p trỏ vào nút giữa của một DSLK đôi trỏ bởi con trỏ đầu pHead và con trỏ cuối pTail, danh sách chỉ gồm 3 nút. Để tách p ra khỏi danh sách mà danh sách vẫn nối đúng. Thực thiện những câu lệnh nào sau đây.

pHead->Next=pTail; pTail->Pre=pHead;

p->Next->Pre=p->Next; p->Pre->Next=p->Pre.

p->Pre->Next=p->Pre; p->Next->Pre=p->Next

Để xóa con trỏ p đang trỏ vào một nút không phải là vị trí đầu trong danh sách liên kết đơn có nhiều hơn một nút. Ta cần xác định con trỏ q trỏ vào vị trí nào sau đây:

Trỏ vào nút bên trái của p và gần p nhất.

Trỏ vào vị trí đầu danh sách.

Trỏ vào vị trí cuối danh sách.

Trỏ vào nút bên phải của p và gần p nhất.

Để nối 1 node vào danh sách liên kết đơn thì các câu lệnh cần thực hiện là gì?

q = (listnode) malloc(sizeof(struct node)); q->item = x; q->next=*p;

q->next=*p; q = (listnode) malloc(sizeof(struct node)); q->item = x;

q = (listnode) malloc(sizeof(struct node)); q->next=*p; q->item = x;

Phát biểu nào sau đây là đúng

Mỗi nút trong DSLK đôi chứa hai thành phần kết nối và thành phần dữ liệu.

Mỗi nút trong DSLK đơn chứa thành phần kết nối và một số nguyên hoặc dữ liệu của nút đó

Thành phần kết nối của một nút trong DSLK đơn luôn chứa địa chỉ của nút kết tiếp.

Trong DSLK đơn nối vòng thành phần kết nối của mỗi nút luôn trỏ vào nó.

Định nghĩa cấu trúc dữ liệu Stack:

Stack là một danh sách đặc biệt mà phép thêm vào hoặc loại bỏ một phần tử chỉ thực hiện tại một đầu gọi là đỉnh (Top) của Stack.

Stack là danh sách kết nối.

Stack là một danh sách đặc biệt mà phép thêm vào được thực hiện ở một đầu, và phép loại bỏ được thực hiện ở phần kia của stack.

Stack là cấu trúc dữ liệu được cài đặt bằng con trỏ.

Trong việc xây dựng các hàm cho danh sách hạn chế hàm sau viết ra để làm gì bool FunctionEmpty(Queue pHead){return (pHead==NULL);}

Kiểm tra hàng đợi hoặc ngăn xếp rỗng.

Khởi tạo hàng đợi rỗng

Khởi tạo ngăn xếp rỗng

Kiểm tra ngăn xếp hoặc hàng đợi đầy

Để cài đặt Stack ta có thể dùng phương pháp nào sau đây:

Bằng con trỏ và bằng mảng

Các phương án khác đều sai

Tính chất của hàng đợi

Vào trước - ra trước" - FIFO: First In First Out.

Vào sau - ra trước" - LIFO: Last In Fist Out.

Vào trước - ra sau" - FILO: First In last Out.

Các phương án khác đều sai

Chọn định nghĩa đúng nhât về hàng đợi (Queue)

Hàng đợi là 1 danh sách, trong đó việc thêm và bớt phần tử được thực hiện ở 2 đầu khác nhau

Hàng đợi là 1 danh sách, trong đó việc thêm và bớt phần tử được thực hiện ở cùng 1 đầu

Hàng đợi là 1 danh sách liên kết đơn

Hàng đợi là 1 danh sách họat động theo cơ chế FILO(First In Last Out)

Một cây nhị phân được gọi là đúng nếu:

Node gốc và các node trung gian đều có 2 node con và các node lá đều có mức giống nhau

Node gốc và tất cả các node trung gian đều có 2 node con

Giá trị khóa của node gốc bao giờ cũng lớn hơn giá trị các khóa của nhánh cây con bên phải

Giá trị khóa của node gốc bao giờ cũng lớn hơn giá trị các khóa của nhánh cây con bên trái

Chọn định nghĩa đúng nhất về cây nhị phân tìm kiếm (BST: Binary Search Tree)

BST là cây mà với mọi nút không phải là Lá có giá trị lớn hơn mọi giá trị của các nút trên cây con trái và nhỏ hơn mọi giá trị của các nút trên cây con phải

BST là cây mà với mọi nút không phải là Lá có giá trị lớn hơn giá trị của nút trên cây con trái và nhỏ hơn giá trị của nút con phải

BST là cây mà với mọi nút không phải là Lá có giá trị lớn hơn mọi giá trị của các nút trên cây con phải và nhỏ hơn mọi giá trị của các nút trên cây con trái

BST là cây nhị phân mà giá trị các nút trên cây khác nhau từng đôi một

Một cây nhị phân được gọi là đúng nếu:

Node gốc và tất cả các node trung gian đều có tối đa 2 node con

Node gốc và các node trung gian đều có 2 node con và các node lá đều có mức giống nhau

Giá trị khóa của node gốc bao giờ cũng lớn hơn giá trị các khóa của nhánh cây con bên trái

Giá trị khóa của node gốc bao giờ cũng lớn hơn giá trị các khóa của nhánh cây con bên phải

Cây nhị phân đầy đủ là?

Là cây nhị phân mà nút gốc và tất cả các node trung gian có đúng hai node con.

Là cây nhị phân mà nút gốc và các nút con có tối đa hai cây con.

Là cây nhị phân mà nút gốc có đúng hai cây con.

Là cây nhị phân mà tất cả các nút trung gian có đúng hai node con.

Cây nhị phân tìm kiếm là:

Với mọi Node: Node có tối đa hai cây con. Nội dung node cha lớn hơn nội dung node con bên trái và nhỏ hơn nội dung node con bên phải.

Cây nhị phân cân bằng (AVL Tree) là:

Cây nhị phân có số node thuộc nhánh cây con trái và số node thuộc nhánh cây con phải chênh lệch nhau không quá 1.

Là cây nhị phân có số node thuộc nhánh cây con trái và số node thuộc nhánh cây con phải cân bằng nhau

Cây nhị phân có số node thuộc nhánh cây con trái và số node thuộc nhánh cây con phải không được chênh lệch nhau.

Là cây nhị phân mà nút gốc và tất cả các node trung gian có đúng hai node con

Cho cây bên dưới, cho biết kết quả duyệt cây theo thứ tự trước (NLR)

A. 40, 30, 25, 20, 28, 35, 32, 38, 60, 50, 70, 65, 90

B. 20, 25, 28, 30, 32, 35, 38, 40, 50, 60, 65, 70, 90

C. 20, 28, 25, 32, 38, 35, 30, 50, 65, 90, 70, 60, 40

D. 40, 30, 25, 20, 28, 35, 32, 38, 60, 90, 65, 70, 50

Câu hỏi về Giải thuật và Cấu trúc dữ liệu

Authored by jajajaja Jajaj

Instructional Technology

University

Used 4+ times

Câu hỏi về Giải thuật và Cấu trúc dữ liệu

AI Actions

Add similar questions

Adjust reading levels

Convert to real-world scenario

Translate activity

More...

Content View

Student View

54 questions

Show all answers

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

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 dữ liệu đầu vào

Máy tính

Thuật toán

Chương trình dịch

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Theo cách tiếp cận của lập trình có cấu trúc, NiklausWirth đưa ra công thức thể hiện được mối liên hệ giữa cấu trúc dữ liệu và giải thuật như sau:

Thuật toán + dữ liệu đầu vào = chương trình

Thuật toán + cấu trúc dữ liệu = chương trình

Kỹ thuật lập trình + cấu trúc dữ liệu = Kết quả đầu ra.

Tất cả đều đúng

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Giải thuật là … câu lênh chặt chẽ, rõ ràng và xác định các thao tác trên các đối tượng dữ liệu

Một

Hai

Nhiều

Dãy

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Kiểu dữ liệu trừu tượng là…...

Kiểu dữ liệu mà người lập trình phải tự xây dựng dựa trên các kiểu dữ liệu cơ bản được cung cấp từ ngôn ngữ này.

Kiểu dữ liệu mà người lập trình phải tự xây dựng dựa trên kiểu dữ liệu không cơ bản được cung cấp từ ngôn ngữ lập trình

Kiểu dữ liệu mà người lập trình phải tự xây dựng trên các kiểu dữ liệu cơ bản được cung cấp từ ngôn ngữ lập trình

Kiểu dữ liệu mà người lập trình tự xây dựng không dựa trên kiểu dữ liệu cơ bản được cung cấp từ ngôn ngữ lập trình

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Hàm đệ quy sau thực hiện công việc gì? int F(int n){if(n==0) return 1;return F(n-1) + F(n-1) + F(n-1);}

n^3

3^n

3n^2

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Cho hàm đê quy sau:int F(int n){if(n==0) return 1;return F(n-1) + F(n-1);}Vậy

F(5) = 32

F(5) = 10

F(5) = 25

F(5) = 5

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Chọn phát biểu đúng nhất

Một chương trình gọi là đệ quy nếu trong chương trình có lời gọi đến một chương trình đệ quy khác.

Một chương trình đệ quy là chương trình lặp đi lặp lại với số lần lặp không biết trước.

Một đối tượng được gọi là đệ quy nếu nó hoặc một phần của nó được định nghĩa thông qua khái

niệm về chính nó.

Một chương trình đề quy là chương trình có chưa hàm main.

Access all questions and much more by creating a free account

Create resources

Host any resource

Get auto-graded reports

Continue with Google

Continue with Email

Continue with Microsoft

or continue with

Facebook

Apple

Others

Already have an account?

Similar Resources on Wayground

58 questions

Công nghệ

Quiz

•

10th Grade - University

50 questions

KẾT CẤU VÀ TÍNH TOÁN Ô TÔ

Quiz

•

University

52 questions

PMQLKS

Quiz

•

University

50 questions

bài số 9

Quiz

•

University

Popular Resources on Wayground

5 questions

A Home on the Shore

Quiz

•

3rd Grade

28 questions

US History Regents Review

Quiz

•

11th Grade

6 questions

A Horse Tale

Quiz

•

3rd Grade

20 questions

Math Review

Quiz

•

3rd Grade

10 questions

Juneteenth History and Significance

Interactive video

•

5th - 8th Grade

20 questions

Dividing Fractions

Quiz

•

5th Grade

55 questions

A Long Walk to Water Final Review

Quiz

•

6th - 8th Grade

10 questions

Equation Word Problems

Quiz

•

7th Grade

Discover more resources for Instructional Technology

40 questions

Flags of the World

Quiz

•

KG - Professional Dev...

Câu hỏi về Giải thuật và Cấu trúc dữ liệu

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

Theo cách tiếp cận của lập trình có cấu trúc, NiklausWirth đưa ra công thức thể hiện được mối liên hệ giữa cấu trúc dữ liệu và giải thuật như sau:

Giải thuật là … câu lênh chặt chẽ, rõ ràng và xác định các thao tác trên các đối tượng dữ liệu

Kiểu dữ liệu trừu tượng là…...

Hàm đệ quy sau thực hiện công việc gì? int F(int n){if(n==0) return 1;return F(n-1) + F(n-1) + F(n-1);}

Cho hàm đê quy sau:int F(int n){if(n==0) return 1;return F(n-1) + F(n-1);}Vậy

Chọn phát biểu đúng nhất

Đánh giá độ phức tạp của giải thuật là việc xác định ……và…… mà giải thuật cần để thưc hiện giải một bài toán

Các kiểu dữ liệu cơ bản là……

Chỉ ra kiểu dữ liệu cơ bản:

Access all questions and much more by creating a free account

Similar Resources on Wayground

Popular Resources on Wayground

Discover more resources for Instructional Technology