Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Author's homepage: Knowing that a lonely cloud has emerged from a mountain

1. Multiple Choice: Examine basic concepts and basic operations
2. Fill in the Blanks: Strengthen the understanding of core concepts and details
3. Short Answer Questions：To examine the mastery of theoretical knowledge
4. Programming Questions: Test actual programming skills and data structure application
5. 

Data Structure Simulation Volume

I. Multiple choice questions (2 points each, 20 points in total)

1. The time complexity of inserting an element into an array is ().
   A. O(1)
   B. O(n)
   C. O(log n)
   D. O(n^2)

2. In heap sort, the time complexity of building a maximum heap is ().
   A. O(n)
   B. O(n log n)
   C. O(log n)
   D. O(n^2)

3. A red-black tree is a ().
   A. Complete binary tree
   B. Balanced Binary Tree
   C. Minimum Heap
   D. Max Heap

4. The following statement about hash table is wrong ().
   A. The search time complexity of a hash table is O(1)
   B. The insertion time complexity of the hash table is O(1)
   C. Hash tables can resolve conflicts
   D. The search time complexity of a hash table must be O(1)

5. In graph traversal, the time complexity of depth-first search (DFS) and breadth-first search (BFS) are ().
   A. O(V + E) and O(V)
   B. O(V^2) and O(V)
   C. O(V + E) and O(V + E)
   D. O(V) and O(V^2)

6. The time complexity of reversing a singly linked list is ().
   A. O(1)
   B. O(n)
   C. O(log n)
   D. O(n^2)

7. In a binary search tree, the worst time complexity of deleting a node is ().
   A. O(1)
   B. O(n)
   C. O(log n)
   D. O(n log n)

8. Which of the following sorting algorithms has an average time complexity of O(n log n) ().
   A. Bubble sort
   B. Quick sort
   C. Insertion sort
   D. Selection sort

9. In a binary tree, the degree of a node is ().
   A. The number of child nodes of this node
   B. The depth of the node
   C. The height of the node
   D. The node's level

10. The main difference between B-tree and B+tree is ().
    A. All nodes of the B-tree store data, while only leaf nodes of the B+ tree store data
    B. B-tree is more balanced than B+ tree
    C. B-tree insertion and deletion operations are simpler
    D. B+ tree search efficiency is lower

II. Fill in the blanks (3 points each, 15 points in total)

1. The height of a complete binary tree containing n nodes is ______.
2. The average time complexity of quick sort is ______.
3. In a linked list, the time complexity of searching for the kth element is ______.
4. The space complexity of the adjacency matrix representation of a graph is ______.
5. In the Huffman tree, the formula for calculating the weighted path length is ______.

3. Short answer questions (10 points each, 30 points in total)

1. Please briefly describe the properties of red-black trees and explain how red-black trees remain balanced.
2. Explain the difference between dynamic arrays and linked lists, and discuss their advantages and disadvantages and application scenarios.
3. Describe how hash tables work and explain how collisions are handled.

IV. Programming questions (15 points each, 35 points in total)

1. Please implement a function to determine whether a linked list is a palindrome linked list.

   def is_palindrome(head):
       # 请在这里编写代码
   1
   2

2. Please write code to implement the insertion operation of the binary search tree.

   class TreeNode:
       def __init__(self, key):
           self.left = None
           self.right = None
           self.val = key
   
   def insert(root, key):
       # 请在这里编写代码
   1
   2
   3
   4
   5
   6
   7
   8

3. Given a graph, represented by an adjacency matrix, implement a breadth-first search (BFS).

   def bfs(graph, start):
       # 请在这里编写代码
   1
   2

Answer

I. Multiple choice questions

1. B
2. A
3. B
4. D
5. C
6. B
7. B
8. B
9. A
10. A

2. Fill in the blanks

1. log(n+1) rounded down
2. O(n log n)
3. O(n)
4. O(V^2)
5. The sum of the weighted path lengths of all leaf nodes

3. Short answer questions

1. Properties of Red-Black Trees：

   • Property 1: Every node is either red or black.
   • Property 2: The root node is black.
   • Property 3: Every leaf node (NIL node) is black.
   • Property 4: If a node is red, then both of its child nodes are black (i.e. there cannot be two consecutive red nodes on all paths from each leaf to the root).
   • Property 5: All simple paths from any node to each of its leaves contain the same number of black nodes.

   How red-black trees maintain balance：

   • After insertion and deletion operations, the properties of the red-black tree are maintained by rotation and recoloring, ensuring that the height of the tree always remains within the O(log n) range.

2. The difference between dynamic arrays and linked lists：

   • Dynamic arrays (such as lists in Python): The memory is continuous, elements can be quickly accessed by index, and insertion and deletion operations require moving elements, with a time complexity of O(n).
   • Linked list: The memory is not continuous, connected by pointers (references), the time complexity of insertion and deletion operations is O(1), but the time complexity of searching for elements is O(n).
   • Pros and Cons：
     • Dynamic array: The advantage is fast random access, the disadvantage is slow insertion and deletion, and may need to be expanded.
     • Linked list: The advantage is fast insertion and deletion, the disadvantage is slow random access and takes up more memory (because pointers need to be stored).
   • Application Scenario：
     • Dynamic arrays are suitable for scenarios where elements need to be accessed frequently and the size is infrequently modified, such as caching.
     • Linked lists are suitable for scenarios where elements need to be frequently inserted and deleted, such as implementing queues and stacks.

3. The principle of hash table：

   • A hash table uses a hash function to map keywords to array index positions, thereby enabling fast search, insertion, and deletion operations.
   • Ways to deal with conflict：
     • Open address method: When a conflict occurs, use linear probing, quadratic probing and other methods to find the next free location.
     • Chain address method: When there is a conflict, elements with the same hash value are stored in a linked list.

4. Programming Questions

1. Determine whether the linked list is a palindrome linked list:

   class ListNode:
       def __init__(self, x):
           self.val = x
           self.next = None
   
   def is_palindrome(head):
       # 使用快慢指针找到链表中点
       slow = fast = head
       while fast and fast.next:
           slow = slow.next
           fast = fast.next.next
       
       # 反转后半部分链表
       prev = None
       while slow:
           temp = slow.next
           slow.next = prev
           prev = slow
           slow = temp
       
       # 比较前半部分和后半部分
       left, right = head, prev
       while right:
           if left.val != right.val:
               return False
           left = left.next
           right = right.next
       return True
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28

2. Insertion operation of binary search tree:

   class TreeNode:
       def __init__(self, key):
           self.left = None
           self.right = None
           self.val = key
   
   def insert(root, key):
       if root is None:
           return TreeNode(key)
       if key < root.val:
           root.left = insert(root.left, key)
       else:
           root.right = insert(root.right, key)
       return root
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14

3. Breadth First Search (BFS):

   from collections import deque
   
   def bfs(graph, start):
       visited = [False] * len(graph)
       queue = deque([start])
       visited[start] = True
       result = []
   
       while queue:
   
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10