Tổng quan Cấu trúc dữ liệu và giải thuật

1. Cấu trúc dữ liệu là gì?

Cấu trúc dữ liệu là cách thức dữ liệu được tổ chức và thao tác. Nó giúp cho chúng ta tìm ra cách để truy cập dữ liệu hiệu quả hơn. Khi làm việc với cấu trúc dữ liệu, chúng ta không chỉ chú trọng đến một phần dữ liệu mà có thể là một tập các dữ liệu khác nhau và cách chúng có thể liên hệ với nhau một cách có tổ chức

2. Phân biệt giữa cấu trúc tệp và cấu trúc lưu trữ.

Điểm khác biệt chính giữa hai kiểu cấu trúc này là phạm vi vùng nhớ mà chúng ta có thể tiếp cận đến dữ liệu. Khi xử lý cấu trúc chứa bộ nhớ chính của hệ thống máy tính, đây được gọi là cấu trúc lưu trữ. Khi xử lý một cấu trúc phụ trợ, nó là cấu trúc tệp.

3. Binary search được áp dụng tốt nhất trong trường hợp nào?

Bineary Search hay gọi là tìm kiếm nhị phân là một thuật toán được áp dụng tốt nhất để tìm kiếm một thành phần nào đó trong danh sách khi danh sách đó đã được sắp xếp. Danh sách được tìm kiếm sẽ bắt đầu tại vị trí ở giữa của dữ liệu

Nếu ngay tại phần tử chính giữa đó chính là giá trị cần tìm kiếm thì việc tìm kiếm hoàn tất. Ngược lại, nó sẽ kiểm tra xem giá trị cần tìm kiếm lớn hơn hay nhỏ hơn giá trị phần tử ở giữa đó.

Nếu giá trị cần tìm kiếm lớn hơn thì phía bên trái so với giá trị chính giữa sẽ bị loại bỏ, lúc này ta chỉ xét các giá trị bên phải. Và tương tự như trên ta tiếp tục lấy vị trí chính giữa để so sanh với giá trị cần tìm kiếm. Cứ so sánh như vậy cho đến khi tìm kiếm được phần tử cần tìm hoặc đến khi vòng lặp kết thúc mà không tìm ra được phần tử nào thì nó trả về kết quả không tìm thấy.

Ngược lại, nếu giá trị cần tìm nhỏ hơn giá trị trung tâm, toàn bộ phần tử bên phải so với giá trị chính giữa sẽ bị loại bỏ, tương tư như trên ta lại xét giá trị chính giữa để đi so sánh với giá trị cần tìm kiếm và xét xem nên chọn phía bên nào để tìm kiếm tiếp theo.

4. Danh sách liên kết đơn là gì?

Danh sách liên kết là một chuỗi các nút trong đó mỗi node được kết nối với node theo sau nó. Điều này tạo thành một liên kết giống như chuỗi để lưu trữ dữ liệu.

5. Làm như thế nào để có thể tham chiếu tất cả các phần tử trong mảng một chiều?

Để tham chiếu đến tất cả các phần tử trong mảng một chiều, chúng ta cần sử dụng vòng lặp được đánh chỉ số index. Từ đó, khi lặp theo bắt đầu từ vị trí 0 đến phần tử cuối cùng (độ dài mảng trừ 1), ta sẽ lấy phần tử đó ra bằng cách gọi vị trí của nó trong mảng chứa nó.

6. Cấu trúc dữ liệu được ứng dụng trong những lĩnh vực nào?

Cấu trúc dữ liệu rất cần thiết và được áp dụng hầu hết mọi khía cách nơi mà dữ liệu cần được xử lý. Nói chung, các thuật toán liên quan đến cấu trúc dữ liệu hiệu quả được áp dụng trong các lĩnh vực sau: phân tích số, hệ điều hành, phát triển phần mềm, A.I.,thiết kế trình biên dịch, quản lý cơ sở dữ liệu, xử lý đồ họa, phân tích thống kê...

7. LIFO là gì?

LIFO là tên viết tắt của Last In First Out ( cuối vào đầu ra ), cũng được biết đến là cấu trúc Ngăn xếp (Stack). Sử dụng lược đồ này, dữ liệu được lưu trữ cuối cùng phải là dữ liệu được trích xuất đầu tiên. Điều này cũng có nghĩa là để có được quyền truy cập vào dữ liệu đầu tiên, tất cả các dữ liệu khác đã được lưu trữ sau dữ liệu đầu tiên này cần phải được trích xuất.

8. Hàng chờ là gì ?

Hàng chờ (Queue) là một cấu trúc mô phỏng một danh sách hoặc một tập hợp các dữ liệu. Trong cấu trúc này, phần tử mới sẽ được đẩy vào phía sau cùng, khi xóa phần tử thì phần tử ở phía đầu sẽ bị xóa đi.

9. Cây nhị phân là gì?

Cây nhị phân là loại cấu trúc dữ liệu có 2 nút, một bên trái và một bên phải. Trong lập trình, cây nhị phân là phần mở rộng của danh sách liên kết.

10. Cấu trúc dữ liệu nào được áp dụng khi xử lý với hàm đệ quy?

Đệ quy là một hàm tự gọi lại chính nó với điều kiện kết thúc, thường được sử dụng trong cấu trúc ngăn xếp.

Khi sử dụng LIFO, một lệnh gọi đến một hàm đệ quy lưu địa chỉ trả về để nó biết cách quay lại hàm đang gọi sau khi cuộc gọi kết thúc.

11. Ngăn xếp là gì?

Ngăn xếp là một cấu trúc dữ liệu trong đó chỉ phần tử trên cùng mới có thể được truy cập. Khi dữ liệu được lưu trữ trong ngăn xếp, mỗi dữ liệu được đẩy xuống dưới, để lại dữ liệu được thêm gần đây nhất ở trên cùng.

12. Giải thích về Binary Search Tree (BST)

Cây tìm kiếm nhị phân lưu trữ dữ liệu theo cách mà chúng có thể được truy xuất rất hiệu quả. Cây con bên trái chứa các node có giá trị nhỏ hơn giá trị khóa của node cha, trong khi cây con bên phải chứa các node có giá trị lớn hơn hoặc bằng giá trị khóa của node cha. Hơn nữa, cả hai cây con cũng là cây tìm kiếm nhị phân, nghĩa là mỗi cây con cũng có thể có 2 node con sau nó.

13. Mảng đa chiều là gì?

Mảng đa chiều tận dụng nhiều index để lưu trữ dữ liệu. Nó hữu ích khi lưu trữ dữ liệu không thể được biểu diễn bằng cách sử dụng index cho mảng một chiều, chẳng hạn như biểu diễn dữ liệu trong bảng trò chơi, các bảng có dữ liệu được lưu trữ trong nhiều cột.

14. Danh sách liên kết được coi là cấu trúc dữ liệu tuyến tính hay phi tuyến tính?

Nó phụ thuộc vào nơi bạn định áp dụng danh sách liên kết. Nếu dựa trên bộ nhớ, một danh sách được liên kết được coi là phi tuyến tính. Mặt khác, nếu dựa trên các chiến lược truy cập, thì danh sách liên kết được coi là tuyến tính.

15.Việc cấp phát vùng nhớ động giúp quản lý dữ liệu như thế nào?

Ngoài khả năng lưu trữ các kiểu dữ liệu có cấu trúc đơn giản, việc cấp phát bộ nhớ động có thể kết hợp các khối có cấu trúc được phân bổ riêng biệt để tạo thành cấu trúc hỗn hợp có thể mở rộng số phần hoặc co lại khi cần.

16. FIFO là gì?

FIFO được viết tắt của First in, First out nghĩa là đi vào trước thì ra trước và được sử dụng để thể hiện cách dữ liệu được truy cập trong hàng chờ. Dữ liệu đã được chèn vào danh sách hàng đợi lâu nhất là dữ liệu bị loại bỏ đầu tiên.

17. Thế nào là một danh sách có thứ tự?

Danh sách có thứ tự là danh sách trong đó vị trí của mỗi nút trong danh sách được xác định bởi giá trị của thành phần chính của nó, để các giá trị khóa tạo thành một chuỗi tăng dần khi danh sách được duyệt qua.

18. Merge sort là gì?

Merge sort, là một cách tiếp cận chia để trị để sắp xếp dữ liệu. Trong một chuỗi dữ liệu, những dữ liệu liền kề được hợp nhất và sắp xếp để tạo danh sách được sắp xếp lớn hơn. Các danh sách đã sắp xếp này sau đó được hợp nhất lại để tạo thành một danh sách được sắp xếp lớn hơn, tiếp tục cho đến khi bạn có một danh sách được sắp xếp duy nhất.

19. Ưu điểm của danh sách liên kết là gì?

Danh sách liên kết là một cấu trúc dữ liệu lý tưởng vì nó có thể được sửa đổi dễ dàng. Điều này có nghĩa là chỉnh sửa danh sách liên kết hoạt động bất kể có bao nhiêu phần tử trong danh sách.

20. Sự khác biệt giữa PUSH và POP là gì?

push và pop áp dụng cho cách dữ liệu được lưu trữ và truy xuất trong một ngăn xếp. push biểu thị dữ liệu được thêm vào nó, có nghĩa là dữ liệu đang được “đẩy” vào ngăn xếp. Mặt khác, pop biểu thị truy xuất dữ liệu và đặc biệt, đề cập đến dữ liệu cao nhất đang được truy cập.

Nói tóm lại, push được dùng để thêm phần tử vào phía sau cùng của danh sách, pop để lấy phần tử sau cùng ra khỏi danh sách

21. Linear search là gì?

Linear search hay còn gọi là tìm kiếm tuyến tính đề cập đến cách một khóa đích được tìm kiếm trong cấu trúc dữ liệu tuần tự. Trong phương pháp này, mỗi phần tử trong danh sách được kiểm tra và so sánh với khóa đích. Quá trình được lặp lại cho đến khi tìm thấy hoặc nếu đã đến cuối tệp.

22. Việc khai báo biến ảnh hưởng đến việc cấp phát vùng nhớ như thế nào?

Lượng bộ nhớ được cấp phát hoặc dự trữ sẽ phụ thuộc vào kiểu dữ liệu của biến được khai báo. Ví dụ, nếu một biến được khai báo là kiểu int, thì 32 bit bộ nhớ lưu trữ sẽ được dành cho biến đó.

23. Lợi thế của heap so với stack là gì?

Heap thì linh hoạt hơn stack là vì vùng nhớ cho heap có thể cấp phát vùng nhớ động và hủy cấp phát khi cần thiết. Tuy nhiên, bộ nhớ của heap đôi khi có thể chậm hơn khi so sánh với stack.

24. Biểu thức hậu tố là gì?

Biểu thức hậu tố là một biểu thức trong đó mỗi toán tử tuân theo các toán hạng của nó. Ưu điểm của dạng này là không cần nhóm các biểu thức con trong dấu ngoặc đơn hoặc phải xem xét mức độ ưu tiên của toán tử.

25. Trừu tượng hóa dữ liệu là gì?

Trừu tượng hóa dữ liệu là một công cụ mạnh mẽ để chia nhỏ các vấn đề dữ liệu phức tạp thành các phần có thể quản lý được. Điều này được áp dụng bằng cách chỉ định ban đầu các đối tượng dữ liệu có liên quan và các hoạt động sẽ được thực hiện trên các đối tượng dữ liệu này mà không quá quan tâm đến cách các đối tượng dữ liệu sẽ được biểu diễn và lưu trữ trong bộ nhớ.

26. Làm như thế nào để chèn phần tử mới vào BST?

Giả sử rằng dữ liệu được chèn vào là một giá trị duy nhất (nghĩa là, không phải là mục nhập hiện có trong cây), trước tiên hãy kiểm tra xem cây có trống không. Nếu nó trống, chỉ cần chèn mục mới vào nút gốc. Nếu nó không trống, ta bắt đầu xét các nhánh con của root. Nếu nó nhỏ hơn giá trị của gốc, hãy chèn nó vào cây con bên trái của gốc, nếu không, hãy chèn nó vào cây con bên phải của root.

27. selection sort hoạt động như thế nào đối với một mảng?

Selection sort hay gọi là sắp xếp lựa chọn là một thuật toán sắp xếp khá trực quan, mặc dù không nhất thiết phải hiệu quả. Trong quá trình này, phần tử nhỏ nhất được chỉ định vị đầu tiên và đổi vị trí với phần tử ở chỉ số 0, do đó đặt phần tử nhỏ nhất ở vị trí đầu tiên.

Phần tử nhỏ nhất còn lại trong mảng con sau đó được đặt bên cạnh các chỉ số con từ 1 đến n-1 và được chuyển đổi với phần tử ở chỉ số con 1, do đó đặt phần tử nhỏ nhất thứ hai ở vị trí thứ hai. Các bước được lặp lại theo cùng một cách cho đến phần tử cuối cùng.

28. Các số có dấu và không dấu ảnh hưởng đến bộ nhớ như thế nào?

Trong trường hợp các số có dấu, bit đầu tiên được sử dụng để biểu thị là dương hay âm, điều này khiến bạn thiếu một chút. Với số không dấu, bạn có tất cả các bit có sẵn cho số đó. Ví dụ rõ nhất là trong phạm vi số (số 8 bit không dấu có phạm vi 0-255, trong khi số có dấu 8 bit có phạm vi -128 đến +127.

29. Số nút tối thiểu mà cây nhị phân có thể có là bao nhiêu?

Một cây nhị phân có thể có tối thiểu là 0 nút, điều này xảy ra khi các nút có giá trị NULL. Hơn nữa, một cây nhị phân cũng có thể có 1 hoặc 2 nút.

30. Cấu trúc dữ liệu động là gì?

Cấu trúc dữ liệu động là cấu trúc mở rộng và co lại khi chương trình chạy. Nó cung cấp một phương tiện linh hoạt để thao tác dữ liệu vì nó có thể điều chỉnh theo kích thước của dữ liệu.

31. Con trỏ được áp dụng trong cấu trúc dữ liệu nào?

Con trỏ được sử dụng trong danh sách liên kết có các ứng dụng khác nhau trong cấu trúc dữ liệu. Cấu trúc dữ liệu sử dụng khái niệm này bao gồm Ngăn xếp, Hàng đợi, Danh sách được Liên kết và Cây nhị phân.

32. Có phải tất cả các câu lệnh khai báo đều dẫn đến một vùng lưu trữ cố định trong bộ nhớ không?

Hầu hết các khai báo đều có, ngoại trừ con trỏ. Khai báo con trỏ không cấp phát bộ nhớ cho dữ liệu, nhưng cho địa chỉ của biến con trỏ. Việc phân bổ bộ nhớ thực tế cho dữ liệu đến trong thời gian chạy.

33. Mảng là gì?

Khi xử lý mảng, dữ liệu được lưu trữ và truy xuất bằng cách sử dụng chỉ mục đề cập đến số phần tử trong chuỗi dữ liệu. Điều này có nghĩa là dữ liệu có thể được truy cập theo bất kỳ thứ tự nào. Trong lập trình, một mảng được khai báo là một biến có một số phần tử được lập chỉ mục.

34. Số lượng hàng đợi tối thiểu cần thiết khi triển khai một hàng đợi ưu tiên là bao nhiêu?

Số hàng đợi tối thiểu cần thiết trong trường hợp này là hai. Một hàng đợi được dùng để sắp xếp các mức độ ưu tiên trong khi hàng đợi còn lại được sử dụng để lưu trữ dữ liệu thực tế.

35. Thuật toán sắp xếp nào được coi là nhanh nhất?

Có nhiều loại thuật toán sắp xếp: quick sort, bubble sort, balloon sort, radix sort, merge sort, v.v. Không thể coi một thuật toán nào là nhanh nhất vì mỗi thuật toán được thiết kế cho một cấu trúc dữ liệu và tập dữ liệu cụ thể. Nó sẽ phụ thuộc vào tập dữ liệu mà bạn muốn sắp xếp.

36. Sự khác biệt giữa ngăn xếp và mảng

Ngăn xếp theo mẫu LIFO. Nó có nghĩa là truy cập dữ liệu tuân theo một trình tự trong đó dữ liệu cuối cùng được lưu trữ khi dữ liệu đầu tiên được trích xuất. Mặt khác, mảng không tuân theo một thứ tự cụ thể và thay vào đó, có thể được truy cập bằng cách tham chiếu đến phần tử được lập chỉ mục trong mảng.

37. Đưa ra một thuật toán cơ bản để tìm kiếm cây tìm kiếm nhị phân.

1. nếu cây trống, thì mục tiêu không có trong cây, nên kết thúc tìm kiếm
2. nếu cây không trống, mục tiêu nằm trong cây
3. kiểm tra xem mục tiêu có nằm trong mục root không
4. nếu mục tiêu không có trong root, kiểm tra xem mục tiêu có nhỏ hơn giá trị của mục root hay không
5. nếu mục tiêu nhỏ hơn giá trị của gốc, tìm kiếm cây con bên trái, ngược lại tìm kiếm cây con bên phải
6. Nếu tìm thấy trong các mục tiêu trong nhánh con, kết thúc vòng lặp và trả về giá trị. Nếu đi qua các nhánh con không tìm được, trả về null.

38. Dequeue là gì?

Một hàng đợi là một hàng đợi hai đầu. Đây là một cấu trúc trong đó các phần tử có thể được chèn hoặc loại bỏ từ một trong hai đầu.

39. Bubble sort là gì và thực hiện nó như thế nào?

Bubble sort là một kỹ thuật sắp xếp có thể được áp dụng cho các cấu trúc dữ liệu chẳng hạn như một mảng. Nó hoạt động bằng cách so sánh các phần tử liền kề và trao đổi giá trị của chúng nếu chúng không theo thứ tự. Phương pháp này cho phép các giá trị nhỏ hơn "nổi bong bóng" lên đầu danh sách, trong khi giá trị lớn hơn chìm xuống dưới cùng.

40. Những thành phần có trong danh sách liên kết có gì?

Một danh sách được liên kết thường có hai phần: head và tail. Giữa đầu và đuôi là các node chứa value và next. Tất cả các node này được liên kết tuần tự.

42. selection sort hoạt động như thế nào?

selection sort hoạt động bằng cách chọn số nhỏ nhất từ ​​danh sách và đặt nó ở phía trước. Quá trình này được lặp lại cho vị trí thứ hai về cuối danh sách. Nó là một thuật toán sắp xếp đơn giản nhất.

43. Graph là gì?

Biểu đồ hay gọi là graph là một kiểu cấu trúc dữ liệu có chứa một tập hợp các cặp có thứ tự. Các cặp có thứ tự này còn được gọi là các cạnh hoặc cung và được sử dụng để kết nối các nút nơi dữ liệu có thể được lưu trữ và truy xuất.

44. Phân biệt cấu trúc dữ liệu tuyến tính với cấu trúc dữ liệu phi tuyến.

Cấu trúc dữ liệu tuyến tính là cấu trúc trong đó các phần tử dữ liệu nằm kề nhau. Ví dụ về cấu trúc dữ liệu tuyến tính bao gồm mảng, danh sách liên kết, ngăn xếp và hàng đợi. Mặt khác, cấu trúc dữ liệu phi tuyến tính là cấu trúc trong đó mỗi phần tử dữ liệu có thể kết nối với nhiều hơn hai phần tử dữ liệu liền kề. Ví dụ về cấu trúc dữ liệu phi tuyến bao gồm cây và đồ thị.

45. AVL tree là gì?

Cây AVL là một loại cây tìm kiếm nhị phân luôn ở trạng thái cân bằng một phần. Số dư được đo bằng sự khác biệt giữa chiều cao của các cây con từ gốc. Cây tự cân bằng này được biết đến là cấu trúc dữ liệu đầu tiên được thiết kế như vậy.

46. Danh sách liên kết đôi là gì?

Danh sách được liên kết đôi là một loại danh sách được liên kết đặc biệt, trong đó việc truyền qua các phần tử dữ liệu có thể được thực hiện theo cả hai hướng. Điều này có thể thực hiện được bằng cách có hai liên kết trong mỗi nút, một liên kết với nút tiếp theo và một liên kết khác kết nối với nút trước đó.

47. Thuật toán Huffman là gì?

Thuật toán của Huffman được sử dụng để tạo cây nhị phân mở rộng có độ dài đường dẫn có trọng số tối thiểu từ các trọng số đã cho. Nó sử dụng một bảng chứa tần suất xuất hiện cho mỗi phần tử dữ liệu.

48. Giải thích ngắn gọn thuật toán đệ quy.

Thuật toán đệ quy nhắm mục tiêu một vấn đề bằng cách chia nó thành các vấn đề con nhỏ hơn, có thể quản lý được. Đầu ra của một lần đệ quy sau khi xử lý một bài toán con sẽ trở thành đầu vào cho quá trình đệ quy tiếp theo.

49. Làm cách nào để bạn tìm kiếm khóa đích trong danh sách được liên kết?

Để tìm khóa đích trong danh sách được liên kết, bạn phải áp dụng tìm kiếm tuần tự. Mỗi nút được duyệt và so sánh với khóa đích, và nếu nó khác, thì nó đi theo liên kết đến nút tiếp theo. Quá trình truyền tải này tiếp tục cho đến khi tìm thấy khóa đích hoặc nếu đạt đến nút cuối cùng.