tải PDF
1) Giải thích thuật toán trong tin học là gì?
Thuật toán là một thủ tục tính toán được xác định rõ ràng, lấy một số giá trị làm đầu vào và tạo ra một số giá trị làm đầu ra. Nói một cách đơn giản, đó là một chuỗi các bước tính toán chuyển đầu vào thành đầu ra.
2) Giải thích thuật toán Sắp xếp nhanh là gì?
Thuật toán Quick Sort có khả năng sắp xếp danh sách hoặc các truy vấn một cách nhanh chóng. Nó dựa trên nguyên tắc sắp xếp trao đổi phân vùng hoặc Phân chia và chinh phục. Loại thuật toán này chiếm ít không gian hơn và nó tách danh sách thành ba phần chính
- Các phần tử nhỏ hơn phần tử Pivot
- Phần tử tổng hợp
- Các phần tử lớn hơn phần tử Pivot
3) Giải thích độ phức tạp thời gian của Thuật toán là gì?
Độ phức tạp thời gian của một thuật toán cho biết tổng thời gian chương trình cần để chạy đến khi hoàn thành. Nó thường được thể hiện bằng cách sử dụng ký hiệu O lớn.
4) Đề cập đến các loại Ký hiệu được sử dụng cho Độ phức tạp về thời gian là gì?
Các loại ký hiệu được sử dụng cho Độ phức tạp về thời gian bao gồm
- Big Oh: Nó cho biết số lần lặp lại "ít hơn hoặc bằng"
- Big Omega : Nó chỉ ra các lần lặp lại "nhiều hơn hoặc giống như"
- Big Theta: Nó chỉ ra các lần lặp lại "giống như"
- Little Oh: Nó chỉ ra "ít hơn"
lặp lại - Little Omega: Nó chỉ ra các lần lặp lại "nhiều hơn"
5) Giải thích cách hoạt động của tìm kiếm nhị phân?
Trong tìm kiếm nhị phân, chúng tôi so sánh khóa với mục ở vị trí giữa của mảng. Nếu khóa nhỏ hơn mục được tìm kiếm thì nó phải nằm ở nửa dưới của mảng, nếu khóa lớn hơn mục được tìm kiếm thì nó phải nằm ở nửa trên của mảng.
6) Giải thích liệu có thể sử dụng tìm kiếm nhị phân cho danh sách liên kết không?
Vì quyền truy cập ngẫu nhiên không được chấp nhận trong danh sách liên kết, nên không thể tiếp cận phần tử giữa của O (1) thời gian. Do đó, không thể tìm kiếm nhị phân cho danh sách liên kết.
7) Giải thích heap sort là gì?
Heap-sort có thể được định nghĩa là một thuật toán sắp xếp dựa trên so sánh. Nó chia đầu vào của nó thành vùng chưa được sắp xếp và đã sắp xếp, cho đến khi nó thu nhỏ vùng chưa được sắp xếp bằng cách loại bỏ phần tử nhỏ nhất và chuyển phần tử đó đến vùng đã sắp xếp.
8) Giải thích Skip list là gì?
Bỏ qua danh sách phương pháp cấu trúc dữ liệu, nơi nó cho phép thuật toán tìm kiếm, xóa và chèn các phần tử trong bảng ký hiệu hoặc từ điển. Trong danh sách bỏ qua, mỗi phần tử được đại diện bởi một nút. Hàm tìm kiếm trả về nội dung của giá trị liên quan đến khóa. Thao tác chèn liên kết một khóa được chỉ định với một giá trị mới, trong khi hàm xóa sẽ xóa khóa được chỉ định.
9) Giải thích độ phức tạp không gian của thuật toán sắp xếp chèn là gì?
Sắp xếp chèn là một thuật toán sắp xếp tại chỗ có nghĩa là nó không yêu cầu thêm hoặc ít. lưu trữ. Đối với sắp xếp chèn, nó chỉ yêu cầu các phần tử danh sách đơn lẻ được lưu trữ bên ngoài dữ liệu ban đầu, làm cho độ phức tạp của không gian là 0 (1).
10) Giải thích "Thuật toán băm" là gì và chúng được sử dụng để làm gì?
"Thuật toán băm" là một hàm băm nhận một chuỗi có độ dài bất kỳ và giảm nó thành một chuỗi có độ dài cố định duy nhất. Nó được sử dụng cho tính hợp lệ của mật khẩu, tính toàn vẹn của thông điệp & dữ liệu và cho nhiều hệ thống mật mã khác.
11) Giải thích cách tìm danh sách liên kết có vòng lặp hay không?
Để biết liệu danh sách liên kết có một vòng lặp hay không, chúng ta sẽ thực hiện hai cách tiếp cận con trỏ. Nếu chúng ta duy trì hai con trỏ và chúng ta tăng một con trỏ sau khi xử lý hai nút và con trỏ khác sau khi xử lý mọi nút, chúng ta có thể gặp phải tình huống trong đó cả hai con trỏ sẽ trỏ đến cùng một nút. Điều này sẽ chỉ xảy ra nếu danh sách liên kết có một vòng lặp.
12) Giải thích cách thức hoạt động của thuật toán mã hóa?
Mã hóa là quá trình chuyển đổi bản rõ thành một định dạng mã bí mật được gọi là "Bản mã". Để chuyển đổi văn bản, thuật toán sử dụng một chuỗi các bit được gọi là "khóa" để tính toán. Khóa càng lớn, số lượng mẫu tiềm năng để tạo văn bản mật mã càng lớn. Hầu hết các thuật toán mã hóa sử dụng mã các khối đầu vào cố định có độ dài khoảng 64 đến 128 bit, trong khi một số sử dụng phương pháp dòng.
13) Liệt kê một số thuật toán mật mã thường dùng?
Một số thuật toán mật mã thường được sử dụng là
- 3 chiều
- Blowfish
- CAST
- CMEA
- ĐIST
- DES và ba DES
- Ý TƯỞNG
- LOKI và như vậy
14) Giải thích sự khác biệt giữa trường hợp tốt nhất và trường hợp xấu nhất của một thuật toán là gì?
-
Tình huống tốt nhất : Kịch bản trường hợp tốt nhất cho một thuật toán được giải thích là sự sắp xếp dữ liệu mà thuật toán hoạt động tốt nhất. Ví dụ: chúng tôi thực hiện tìm kiếm nhị phân, trong đó trường hợp tốt nhất sẽ là nếu giá trị đích nằm ở chính giữa dữ liệu bạn đang tìm kiếm. Độ phức tạp thời gian của trường hợp tốt nhất sẽ là 0 (1)
- Trường hợp xấu nhất: Nó được coi là tập hợp đầu vào tồi tệ nhất cho một thuật toán nhất định. Ví dụ: quicksort, có thể hoạt động kém nhất nếu bạn chọn phần tử lớn nhất hoặc nhỏ nhất của danh sách con cho giá trị pivot. Nó sẽ làm cho quicksort thoái hóa thành O (n2).
15) Giải thích thuật toán Radix Sort là gì?
Sắp xếp theo cơ số sắp xếp phần tử theo thứ tự bằng cách so sánh các chữ số của các số. Nó là một trong những thuật toán sắp xếp tuyến tính cho các số nguyên.
16) Giải thích thuật toán đệ quy là gì?
Thuật toán đệ quy là một phương pháp giải quyết một vấn đề phức tạp bằng cách chia nhỏ một vấn đề thành các bài toán con nhỏ hơn và nhỏ hơn cho đến khi bạn nhận được bài toán đủ nhỏ để nó có thể được giải quyết một cách dễ dàng. Thông thường, nó liên quan đến một hàm gọi chính nó .
17) Đề cập ba luật của thuật toán đệ quy là gì?
Tất cả các thuật toán đệ quy phải tuân theo ba luật
- Nó phải có một trường hợp cơ sở
- Một thuật toán đệ quy phải gọi chính nó
- Một thuật toán đệ quy phải thay đổi trạng thái của nó và chuyển sang trường hợp cơ sở
18) Giải thích thuật toán sắp xếp bong bóng là gì?
Thuật toán sắp xếp bong bóng còn được gọi là sắp xếp chìm. Trong kiểu sắp xếp này, danh sách được sắp xếp sẽ so sánh các cặp mục liền kề. Nếu chúng được sắp xếp theo thứ tự sai, nó sẽ hoán đổi các giá trị và sắp xếp chúng theo đúng thứ tự.