The carrier of information is a collection of numbers, characters and all symbols that can be recognized and processed by computers that describe the attributes of objective things.

The basic unit of data, consisting of data items, the smallest indivisible unit

A collection of data elements with the same properties, a subset of data

A collection of values ​​and a set of operations defined on the collection.

1. Definition: A mathematical model and a set of operations defined on the model

2. Characteristics: The definition only depends on its set of logical characteristics and has nothing to do with how it is represented and implemented inside the computer.

3. Representation: (data objects, data relationships, basic operation sets)

1. Structure: the relationship between data elements

2. Definition: A collection of data elements that have one or more specific relationships with each other.

3. Content: Logical structure, storage structure, data operations

1. Definition: The logical relationship between data elements, which has nothing to do with storage and is independent of the computer.

2. Classification

1. Definition: Representation of data structure in computer (also called image/physical structure)

2. Including: representation of data elements and representation of relationships

3. Classification

1. Definition of operation: Point out the function of operation according to the logical structure

2. Implementation of operation: Point out the specific operation steps of the operation according to the storage structure.

1. Belongs to a logical structure

2. A circular queue is a queue represented by a sequence table. It is a data structure, not an abstract data structure.

3. The storage spaces of different nodes can be discontinuous, but the storage spaces within the nodes must be continuous.

4. Two different data structures, the logical structure and the physical structure can be exactly the same, but the data operations are different.

1. Finiteness

2.Certainty

3. Feasibility

4.Input

5.Output

1. Correctness

2. Readability

3. Robustness

4. Efficiency and low storage requirements

Definition: Measures how quickly the execution time of an algorithm increases as the size of the problem increases.

1. Definition: Measures how quickly the space required by the algorithm increases as the size of the problem increases.

2. The algorithm works in place: the auxiliary space required by the algorithm is constant, that is, O(1)

1. Merge two ascending linked lists of length m, n into a descending linked list of m n (take the smaller element, head interpolation method)

2. Time complexity calculation

3. For the same algorithm, the higher the level of the implemented language, the lower the execution efficiency.

The starting position of the storage space

Maximum storage space of sequence table

The current length of the sequence table

C language: L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);

C: L.data=new ElemType[InitSize];

1. The linear table must be a finite sequence

2. Insert a number into the i-th position of the sequence table. The legal value of i is: 1≤i≤n 1

1. Reverse all elements of the sequence list

1.1 In the array A[m n], there are two sequence tables with lengths m and n, and the positions are interchanged.

2. Sequential list (non-ordered) deletes all data elements with value x

2.1 Sequential list (non-ordered) deletes all elements with values ​​between s and t

3. The ordered sequence list deletes all elements between the given values ​​s and t

4. Remove all elements with duplicate values ​​from the ordered list

4.1 Change ordered list to unordered list

5. Merge two ordered lists into one ordered list, and return the result by the function

6. An ascending sequence S of length L, the median is ┍L/2┑ Find the median of two equal-length ascending sequences A and B

7. If the number of elements with value x > n/2, it is called the main element. Find the main element of A.

8. Find the smallest positive integer that does not appear in the array, less time

1. Regardless of whether there is a head node or not, the head pointer always points to the first node of the linked list.

2. The head node is the first node in the linked list with the head node and usually does not store information.

1. The operation at the first position of the linked list is consistent with the operation at other positions.

2. Regardless of whether the linked list is empty or not, the head pointer points to the non-null pointer of the head node, and empty lists and non-empty lists are treated the same

Forward insertion operation: Find the previous node first, the time complexity is O(n)

Extension: Convert the forward insert operation into a backward insert operation, and then exchange the data of the two nodes. The time complexity is O(1)

Find the predecessor node first, then delete the node, O(n)

Extension: first exchange data with the successor node, and then delete the successor node, O(1)

Count the number of data nodes

1. Null condition: Whether the pointer of the head node points to the head pointer

2. When operating on the head and tail of a singly linked list: do not set the head pointer and only set the tail pointer, which is more efficient.

3. You can traverse the entire linked list starting from any node

Null condition: The prior field and next field of the head node both point to the head pointer.

1. Like the sequence table, a continuous memory space must be allocated in advance

2. Insertion and deletion only require modifying the pointer and do not require moving elements.

3. Very clever in high-level languages ​​(Basic) that do not support pointers

The sequence list can be accessed sequentially or randomly. The linked list can only be accessed sequentially from the head.

1. Search by value

2. Search by serial number

1. Storage considerations

2. Considerations based on operations

3. Environmental considerations

1. The chain storage structure is more convenient to represent various logical structures than the sequential storage structure.

2. Sequential storage can not only be used to store linear structures, but also the structures of graphs and trees (full binary trees)

3. Static linked lists need to allocate a large continuous space, and insertion and deletion do not require moving elements.

4. If a singly linked list is used to represent the queue, a circular linked list with a tail pointer should be used.

5. Given a one-dimensional array, the minimum time to build an ordered singly linked list is O(nlog₂n)

6. Commonly used operations on linked lists are inserting after the last element and deleting the first element. The most time-saving operation is

1. Stack top pointer: S.top Stack top element: S.data[S.top]

2. Push to the stack: The pointer is first incremented by 1, and then the value is sent to the top element of the stack.

3. Pop the stack: first take the value of the element on top of the stack, and then decrement the pointer on the top of the stack by 1

4. Conditions for empty judgment and full judgment: vary due to different actual conditions.

1. Definition: Set the bottoms of the two stacks at both ends of the shared space, and the tops of the two stacks extend toward the middle.

2. Blank judgment: top0=-1 top1=MaxSize

3. Full sentence: top1-top0=1

4. Push into the stack: top0 first adds 1 and then assigns a value, top1 first decrements 1 and then assigns a value, and the opposite is true when popping out of the stack.

1. Top element of stack

2. The next element of the top element on the stack

3. The judgment conditions for stack empty and stack full will also change.

For increasing sequences

f(2)=2, f(3)=5, f(4)=14

1. The stack and queue have the same logical structure, not a storage structure

2. The linked list does not have a head node and all operations are performed at the head of the list. It is the most unsuitable link stack.

3. Insert an x ​​node into a chain stack (without the head node) whose top pointer is top

4. The push sequence is 1,2,...,n, and the pop sequence is P1, P2,...,Pn. If P2=3, the number of possible values ​​of P3 is n-1.

5. When rewriting a recursive program in a non-recursive way, the stack may not be applicable

6. The definitions of the pointers at the top of the stack, the head of the queue, and the tail of the queue are not unique. Be sure to review the question carefully.

1. Determine whether a linked list is centrally symmetrical

1. Two pointers: front points to the head element of the queue, and rear points to the next position of the tail element of the queue.

2. Initial state (team empty): Q.front==Q.rear==0

3. Enter the queue: first send the value to the last element of the queue, and then add 1 to the last pointer of the queue.

4. Dequeue: First take the value of the head element, and then add 1 to the head pointer

5. False overflow exists

6.Type description

1. Initial state (team empty): Q.front==Q.rear==0

2. Advance the front pointer: Q.front=(Q.front 1)%MaxSize

3. Advance the queue tail pointer: Q.rear=(Q.rear 1)%MaxSize

4. Queue length: (Q.rear MaxSize-Q.front)%MaxSize

5. Distinguish between empty and full teams

1.Type description

2. Single linked list with head node: unified insertion and deletion operations

3. Suitable for situations where data elements change greatly. There is no queue overflow or unreasonable storage allocation in multiple queues.

1. When using a chained storage queue to perform a deletion operation, both the head and tail pointers may be modified.

2. In the chain queue, when the element pointed to by x enters the queue, perform the operation

1. Determine the initial and full status of the circular queue

2. Determine the sequence that cannot be obtained by the input/output restricted double-ended queue

1. Set up an empty stack and read parentheses sequentially

2. If it is ), it will be popped out of the stack if paired with the top of the stack (or it is illegal.

3. If it is ( , push it onto the stack as a new more urgent expectation

4. The algorithm ends and the stack is empty, otherwise the bracket sequence does not match

1. Add parentheses to all operators and their operands according to operator precedence (no need to add parentheses if they exist originally)

2. Move the operator after the corresponding parentheses

3. Remove the brackets

Note: The prefix expression puts the operator in front of the parentheses, and the others are the same.

1. Numbers: directly added to the suffix expression

2. If it is (: push to stack

3. If it is ): Add the operators in the stack to the postfix expression in sequence until ( and delete the ( in the stack

4.If - */

5. The traversal is completed. If the stack is not empty, pop up all elements in sequence.

1. Scan each term of the expression sequentially

2. Operand: Push onto the stack

3. Operator <op>: Continuously exit two operands x and y from the stack to form an operation instruction x<op>y, and push the calculation result back onto the stack

1. Recursive expression (recursive body)

2. Boundary conditions (recursive exit)

1. Set up a print data buffer, pause output when full, do other things, and wait for the printer to send a request

1. Arrange each request in a queue according to the time order, and allocate the CPU to the first user in the queue each time.

1. Symmetric matrix

2.Triangular matrix

3. Tridiagonal matrix

The number of child nodes of a node

The maximum degree of a node in a tree

Starting from the root node and accumulating layer by layer from top to bottom.

Starting from leaf nodes and accumulating layer by layer from bottom to top.

The maximum number of levels of nodes in the tree

The sequence of nodes passing between two nodes

The number of edges passed on the path

The branches in the tree are directed (parents point to children), the path is from top to bottom, and there is no path between two children.

Sum of geometric series

1. Subtrees can be divided into left and right, and the order cannot be reversed arbitrarily.

2. The difference between a binary tree and an ordered tree of degree 2

1. Full binary tree

2. Complete binary tree

3. Binary sorting tree

4.Binary balanced tree

1.n0=n₂ 1

2. The nth layer has at most 2^(n-1) nodes

3. A binary tree with height h has at most 2^h-1 nodes.

4. For complete binary trees

5.The height of a complete binary tree with n nodes is ㏒₂n (taken off the bound) 1

1. Suitable for complete binary trees and full binary trees

2. Generally, some empty nodes that do not exist are added to the binary tree.

3. Note: Only by starting storage from array subscript 1 can the above properties be satisfied.

4. Distinguish between the sequential storage of trees and binary trees

1. Binary linked list has three fields: data, lchild, rchild

2. A binary linked list with n nodes has n 1 empty link fields (the root node does not use a pointer) to form a clue linked list.

1. Thoughts

2. Algorithm implementation

3. The execution efficiency of non-recursive algorithms is higher than that of recursive algorithms

1. Thoughts

2. Algorithm implementation

1. Pre-order and mid-order

2. Post-order and mid-order

3. First order and last order are not allowed

1.Purpose: To speed up the search for node predecessors and successors

2. Regulations

3.Clue: Pointers to predecessors and successors

4. Threading: The process of traversing a binary tree in a certain order to turn it into a threaded binary tree.

1. The essence of clueing

2. Implementation of threaded in-order traversal

3. Sometimes a head node is also added to the clue linked list to form a two-way clue linked list.

1. A non-recursive algorithm for binary tree traversal can be implemented using clue binary trees.

2. Algorithm implementation

1. Definition: Continuous space storage, each node adds a pseudo pointer to indicate the position of the parents in the array, the root node subscript is 0, and its pseudo pointer is -1

2. Features: Parents can be obtained quickly, but the child must traverse the entire structure.

1. Definition: Connect the children of each node into a linear structure using a single linked list

2. Features: It is convenient to ask for children, but inconvenient to ask for parents.

1. Definition: The left pointer points to the first child, the right pointer points to the first brother, and the binary linked list is used as a storage structure

2. Advantages: Convenient to convert tree into binary tree, easy to find children

3. Disadvantages: It is troublesome to find parents. It will be convenient if you add parent to point to parents.

The left pointer points to the first child, the right pointer points to the first brother, the root has no brothers, and the binary tree has no right subtree.

The root of each binary tree serves as the right subtree of the previous binary tree.

1. The root and left subtree of the binary tree are used as the binary tree form of the first tree, and then converted into a tree (the right child becomes a brother)

2. The right subtree of the root and its left child serve as the second tree, and the right child serves as the third tree, and so on.

Visit the root first, and then traverse each subtree from left to right, which is the same as the root-first traversal of the corresponding binary tree.

Traverse each subtree from left to right and then visit the root, which is the same as the middle root traversal of the corresponding binary tree.

Same as root-first traversal of a binary tree

Same as root traversal in binary tree

1.Union(S,Root1,Root2): Merge two sub-collections and connect root Root2 to root Root1

2.Find(S,x): Find the root of the tree containing x until a negative number is found

3.Inital(s): Each element in the set S is initialized as a sub-set with only a single element (all elements are assigned a value of -1)

1. The keys of all nodes on the left subtree are less than the root node

2. The keywords of all nodes on the right subtree are greater than the root node

3. The left and right subtrees are each a binary sorting tree.

Inorder traversal can obtain increasing ordered sequence

1. Non-recursive implementation, recursion is simple but inefficient

1. The new node inserted must be a leaf node (it will only be inserted when the tree is empty)

1. Even if the inserted elements are the same but in different orders, the constructed BST will be different.

1. Leaf node: delete directly

2.i has only one left/right subtree: let i's subtree become the subtree of i's parent node, replacing i's position

3.i has two subtrees on the left and right: replace i with the direct successor/predecessor of i, then delete the direct successor/predecessor, and convert to case 1,2

1. Average search length ASL = (number of each layer * number of corresponding layers) / total number

2. Worst case: similar to ordered singly linked list O(n)

3. Best case: balanced binary tree O(㏒₂n)

4. Search process: Similar to binary search, but the decision tree of binary search is unique

1. Balanced binary tree: The absolute value of the height difference between the left and right subtrees of any node does not exceed 1

2. Balance factor: The height difference between the left and right subtrees of the node -1,0,1

1. The object of each adjustment is the minimum unbalanced subtree

2.LL balanced rotation (right single rotation)

3.RR balanced rotation (left single rotation)

4.LR balanced rotation (double rotation first left and then right)

5.RL balanced rotation (right and then left double rotation)

1. The maximum depth of a balanced binary tree containing n nodes is O(㏒₂n), and the balanced search length is O(㏒₂n)

1. The weighted path length (WPL) of the node

2. Weighted path length of the tree

3. Huffman tree (optimal binary tree)

1.Construction process

2.Features

1. Fixed length encoding

2. Variable length encoding

3. Prefix encoding

4.Huffman coding process

<v,w>: arc from v to w (v is adjacent to w/w is adjacent to v) v: arc tail w: arc head

(v,w)=(w,v)

There are no duplicate edges, and there are no edges from the vertex to itself.

There are duplicate edges and there are edges from the vertex to itself.

1. Undirected complete graph: There are n(n-1)/2 edges between any two vertices.

2. Directed complete graph: any two vertices have two arcs in opposite directions, n(n-1)

Generate subgraph: subgraph with the same vertex set

1. Maximally connected subgraph (connected component): A connected subgraph contains all edges, not necessarily all vertices (not necessarily a connected graph)

2. Minimally connected subgraph: a subgraph that maintains graph connectivity while minimizing the number of edges (can be a single vertex)

Minimum, maximum relative to the side

1. Spanning tree of a connected graph; a minimal connected subgraph containing all vertices (n vertices have n-1 edges)

2. In a non-connected graph, the spanning tree of connected components constitutes the spanning forest of the non-connected graph.

1. Degree of a vertex: the number of edges with the vertex as an endpoint

2. In an undirected graph: the sum of degrees of all vertices = number of edges * 2

3. In a directed graph: the degree of a vertex = in-degree and out-degree, the sum of in-degrees of all vertices = the sum of out-degrees = the number of edges

1. Weighted picture (net): a picture with weights on the side

1. Loop/Loop: The path where the first vertex and the last vertex are the same

1. Simple path: a path in which vertices do not appear repeatedly

2. Simple loop: Except for the first vertex and the last vertex, the other vertices do not appear repeatedly.

1. If the shortest path from v to w exists, it is a distance. If it does not exist, it is recorded as infinity.

1. A directed graph in which the in-degree of one vertex is 0 and the in-degree of the other vertices is 1.

1. A one-dimensional array stores vertex information, and a two-dimensional array stores edge information.

1. Undirected graph/directed graph: The number of non-zero elements in the i-th row is the degree/out-degree of the i-th vertex

2. It is easy to determine whether there are edges, but it is difficult to determine how many edges there are.

3. Dense graphs are suitable for using adjacency matrices

4.Aⁿ[i][j]: The number of paths of length n from vertex i to vertex j

1. Combine sequential and linked storage to create a singly linked list for each vertex i

2. Vertex table: Vertex field (data) pointer to the first adjacency list (firstarc)

3. Edge table: Adjacency point field (adjvex) Pointer field pointing to the next adjacency list (nextarc)

1. Undirected graph: storage space O(|V| 2|E|) directed graph: O(|V| |E|)

2. Use adjacency list method to save space in sparse graphs

1. ArcNode: 5 domains

2. Vertex pointer (VNode): 3 fields

3. Note: Vertex nodes are stored sequentially

1. It is easy to find the arc with vi as the tail and the arc with vi as the head. It is easy to find the out-degree/in-degree of the vertex.

2. It means it is not unique, but it determines a graph.

1. Each edge is represented by a node

2. The vertex is represented by a node

1. Edges attached to the same vertex are connected in the same linked list, and each edge node is linked in two linked lists at the same time.

2. Each edge has only one node

A hierarchical traversal algorithm similar to a binary tree, giving priority to the earliest discovered node.

1. First visit the starting vertex v

2. Visit all unvisited adjacent vertices of v in sequence

3. Then start from these vertices and visit all their unvisited nodes.

1. Hierarchical search, which visits a batch of nodes forward, unlike depth-first where there is a backwards situation, and it is not recursive.

2. Use the queue auxiliary mark array (whether the vertex is visited)

3. Algorithm implementation

1. Space complexity: O(|V|)

2. Time complexity

1. Definition: A traversal tree obtained during breadth traversal

2. Features: Unique in adjacency matrix, not unique in adjacency list

Similar to pre-order traversal of a tree, the last discovered node is given priority.

1. First visit the starting vertex v

2. Visit any unvisited adjacent vertex w of v

3. Then visit any unvisited adjacent vertex w2 of w

4. Repeat until you can no longer access downwards and return to the most recently visited vertices in turn.

1. Starting from a vertex, using recursive form

2. Algorithm implementation

1. Space complexity: O(|V|)

2. Time complexity

1. Connected: visit all vertices in one traversal

2. Non-connected: visit all vertices of connected components in one traversal

1. If there is a path from the initial vertex to each vertex, all vertices can be accessed, otherwise it cannot

The first for loop initializes the vertices to FLASE

The spanning tree with the smallest sum of edge weights

1. The tree shape is not unique, the sum of the edge weights is unique

2. Number of edges = number of vertices - 1

When T does not form a spanning tree, find a minimum cost edge and no loop will be generated after adding T

1.Prim algorithm (Prim)

2.Kruskal algorithm (Kruskal)

1. Auxiliary variables

2. Thoughts

3.Features

1. Thoughts

2.Features

There are no cycles in directed graphs

The DAG graph represents a project, the vertices represent activities, and the directed edges <vi, vj> represent that activity i must precede activity j

1.Definition

2. Implementation method

3.Features

4.Attention

1.Definition

2. Two properties

1. Start vertex (source point): There is only one vertex with in-degree 0, the beginning of the entire project

2. End vertex (sink): There is only one vertex with an out-degree of 0, which is the end of the entire project.

3. Critical path: The path with the maximum path length

4. Critical Activities: Activities on the critical path

5. Minimum time: length of critical path

1. The earliest occurrence time Ve(k) of event vk

2. The latest occurrence time Vl(k) of event vk

3. The earliest occurrence time e(i) of activity ai

4. The latest occurrence time l(i) of activity ai

5. The difference in activities d(i)=l(i)-e(i)

The activities with the difference d()=0 among all activities constitute the critical path

1. Algorithm characteristics

2. Advantages and Disadvantages

3.Performance

1. Decision tree: circular nodes are existence nodes, rectangular nodes are failure nodes (interval), n successes must have n 1 failure nodes

2. The search length to reach the failed node = the number of layers of a circular node above it

3. Only ASL failure is different = (1 2 ... n n)/n 1

1. Loop condition: low≤high ensures that they all point to the same value in the end, otherwise there will be one less number to search for.

2.mid=(low high)/2 is equivalent to removing the bounds

1. Time complexity: O(log₂n)

2.ASL: Number of layers per layer * number of nodes per layer / number of summary points, n layer has 2ⁿ﹣¹ nodes

1. Absorb the respective advantages of sequential search and binary search, have a dynamic structure, and are suitable for fast search.

1. Divided into several sub-blocks, the blocks can be unordered and the blocks can be ordered.

2. The largest keyword in the first block < all records in the second block, and so on

3. Create an index table, containing the largest keyword of each block and the address of the first element of each block, arranged in order by keyword

1. Determine the block in the index table and search sequentially/in half

2. Search sequentially within the block

ASL=index table ASL intra-block ASL

1. The speed of half search is now generally faster. In special cases, sequential search may be faster.

2. Time performance of binary search and binary sorting tree

3. When searching by half, the middle value is bounded

1. The height of the binary decision tree: ┎log₂(n 1)┒ or ┕log₂n┙ 1

2. The optimal block length of the index sequence table of n records:

3. Sequential search ASL=(n 1)/2, index search ASL=index table ASL intra-block ASL

1. Determine whether a tree is a binary search decision tree

2. Use an idea similar to block search directly in the ordered list: W252

1.k-point search method: The time complexity of success and failure is O(logk(n))

2. When the search probabilities are different, the most effective way is to use sequential search

0.B-tree (a multi-path balanced search tree with a balance factor of 0 for all nodes), the maximum number of child nodes is the order of the B-tree (m)

1. Each node has at most m subtrees (at most m-1 keywords)

2. If the root node is not a terminal node, there are at least two subtrees and 1 keyword

3. All non-leaf nodes except the root node have at least ┎m/2┒ subtrees and at least ┎m/2┒-1 keywords.

4. All non-leaf node structures

5. All leaf nodes are at the same level, without information (external nodes/failure nodes)

1. Minimum height

2. Maximum height

Similar to a binary search tree

1. Positioning: must be inserted into a non-leaf node at the lowest level

2.Insert

1. At the terminal node

2. Not at the terminal node

1. Each branch node has at most m subtrees (child nodes)

2. The non-leaf root node has at least two subtrees, and all non-leaf nodes except the root node have at least ┎m/2┒ subtrees

3. The number of subtrees of a node = the number of keywords

4. All leaf nodes contain all keywords (arranged in order) and pointers to corresponding records, and adjacent leaf nodes are linked to each other according to size.

5. All branch nodes (indexes that can be regarded as indexes) only contain the maximum value of the keywords in each of its child nodes and pointers to the child nodes.

1. Two head pointers: one points to the root node, and the other points to the leaf node with the smallest keyword

2. Two search operations: search from the minimum keyword order/multi-way search from the root node

3. Note: When searching, the search does not end when the non-leaf node is equal to the given value. The search continues downward until the leaf node. Regardless of whether the search is successful or not, it is a path from the root node to the leaf node.

1. When the number of keywords in a node ≠ the number of subtrees, it must not be a B tree

2. All non-leaf nodes except the root node have at least ┎m/2┒ subtrees and at least ┎m/2┒-1 keywords.

3. When the B-tree is split after insertion, as long as the root node does not split, the height will not be 1

1. Minimum height: h≥logm(n 1)

2. Maximum height: n 1≥2┎m/2┒^(h-1)

1. For a third-order B-tree: when the number of nodes is the smallest, it is similar to a full binary tree; when the number of nodes is the largest, it is similar to a full ternary tree.

2.B tree is used for file index/database index

The function that maps keywords to corresponding addresses is recorded as Hash(key)=addr (can be array subscript/index/memory address)

Two or more different keywords map to the same address

Collision of different keywords

A data structure that is accessed directly based on keywords, ideally O(1)

1. The definition domain must contain all keywords, and the value range depends on the size/address range of the hash table

2. Addresses should be equally likely and evenly distributed.

3. Make the function as simple as possible and calculate it in a short time

1. Function: H(key)=a*key b

2. Features: No conflict, suitable for basically continuous distribution of keywords

1. Function: H(key)=key%p

2. Selection of P: The prime number p that is no larger than m (hash table length) but closest to or equal to m

1. Select a number of bits with a relatively even digital distribution as the hash address

2. Features: Suitable for collections of known keywords

1. The middle digits of the square value are used as the hash address

2. Applicable to situations where the values ​​of each bit are not uniform enough/are less than the number of bits required for the hash address.

1. Divide the keyword into several parts with the same number of digits, and take the superposition sum as the hash address.

2. Suitable for a large number of digits and the digits on each bit are roughly evenly distributed.

0.Definition

1. Linear detection method

2. Square detection method (secondary detection method)

3.Rehashing method (double hashing method)

4. Pseudo-random sequence method

5.Attention

1. Definition: All synonyms are stored in a linear linked list, uniquely identified by a hash address

2. Suitable for frequent insertion and deletion situations, and can be directly physically deleted

0.Initialization: Addr=Hash(key)

1. Check whether there is a record on Addr

2. Calculate the "next hash address" using the given conflict handling method, set Addr to this address, and transfer to 1

1. Depends on: hash function, method of handling collisions, loading factor

2. Filling factor (α): defines how full a table is

3. The average search length depends on α and does not directly depend on n or m.

1. K synonyms are filled into the hash table using linear detection, which requires K (K 1)/2 times of detection.

2. The probability of conflict is proportional to the size of the loading factor

3. The hash function cannot be constructed using a random number function, and normal searches cannot be performed.

1. Causes of accumulation

2. Average number of detections = average search length

1.ASL success

2.ASL failed

1. Similar to linear table sequential storage, allocate fixed-length arrays

2. Truncation: String values ​​exceeding the predefined length will be discarded.

1. Use malloc() and free() to dynamically allocate and delete

1. Linked storage similar to a linear list, each node can hold one or more characters

1.String assignment: StrAssigh

2.String comparison: StrCompare

3. String connection: Concat

4. Find the string length: StrLength

5. Find substring: SubString

1. Starting from the pos character of the main string, compare it with the first character of the pattern string

2. If they are equal, continue to compare the subsequent characters one by one.

3. If not equal, start the comparison again from the next character of the main string.

Worst time complexity: O(mn)

1. Prefix: All header substrings except the last character (can only start from the first position)

2. Suffix: All tail substrings except the first character (can only start from the last position)

3. Partial matching value: The longest prefix and suffix lengths are equal

1. Time complexity: O(m n)

1.next array value = longest same prefix and suffix length 1

2. The string itself cannot be used as a prefix or suffix.

3. Usually next[1]=0 (depends on the specific question, if it is -1, still use 0 for calculation, and finally all numbers are -1)

4. When the i-th element in next[i] does not match, the string length is i-1, excluding the i-th element.

5. When the string is long, you can only count the first few to get the answer.

1.The biggest advantage of KMP algorithm

1. A quick way to solve next[], assuming that next[n] is currently being solved, next[n-1]=m

2.KMP matching process

1. During the exam, you must distinguish whether the next[] value starts from 0 or 1

1. The sorting algorithm implemented on the sequence list may not be implemented on the linked list.

2. If you use different sorting methods to sort the same linear table, the sorting results obtained may be different.

1. The minimum number of comparisons for sorting any n keywords is ┍log₂(n!)┑

1. Assume that the first element has been sorted

2. Starting from the second element, compare it with the previous one in sequence. If immediate exchange is not satisfied, sort in place and repeatedly move the already arranged items backward.

1. Copy A[0] as a sentinel to avoid out-of-bounds subscripts, facilitate assignment, and eliminate the need to apply for temporary variables.

2. Compare and move at the same time

1. Time efficiency

2. Applicability

1. First fold in half to find the position where the element is to be inserted.

2. Move all elements after the position to be inserted uniformly

1. Only the number of comparison elements is reduced, the number of moves has not changed

2. The number of comparisons has nothing to do with the initial state, only n

1. Time complexity: O(n²)

2. Stable

1. First take the step size as n/2, divide it into several groups, and use direct insertion sorting in each group.

2. Reduce the step size by half and continue until the step size is 1

1. The best incremental sequence has not yet been found, and the time complexity cannot be calculated.

1. Time efficiency

2. Unstable

1. The time complexity of half insertion sort is O(n²)

1. Starting from the last element, compare the two adjacent elements. If they are in reverse order, exchange them.

2. A bubbling operation will result in swapping the smallest element to the first position.

3. In the next round of bubbling, the smallest element determined in the previous round will no longer participate, and the column to be sorted will be reduced by one element.

4. The result of each bubble is that the smallest element in the sequence is placed at the final position, and up to n-1 is completed.

1. The ordered subsequence generated by bubble sorting must be globally ordered, which is different from direct insertion sorting.

1. Time efficiency

1. Each time, the first element in the current table is taken as the base pivot (pivot value) to divide the table.

2.i points to the first element (base), j points to the last element

3. Start with j, and find the first element smaller than the baseline from back to front. j points to the position of this element, and replace the element pointed to by i with this element.

4. Starting from i, find the first element larger than the baseline from front to back. i points to the position of this element, and replace the element pointed to by j with this element.

5. Start from j again and repeat until the contact between i and j stops. Place the reference value at the contact position and divide the sequence into two parts. The front is smaller than the reference value and the latter is greater than the reference value.

6. Take the first element of the two subsequences as the reference value and repeat the operation

1. No ordered subsequence is generated, but an element will be placed at the final position after each sorting pass

2. The more ordered the algorithm is, the lower the efficiency is, and the more disordered the algorithm is, the higher the efficiency is.

1. Space efficiency

2. Time efficiency

4. Unstable

1. When the subsequence obtained by recursive division is small, recursion is no longer required and direct insertion sorting is used for subsequent work.

2. Try to choose a benchmark that can divide the data.

1. The fastest situation when a group of numbers is sorted using quick sort

2. When looking for possible sequences, both orders must be considered (from large to small, small to large)

1. Quick sort is most suitable for sequential storage.

1. Algorithm to move all odd numbers in front of all even numbers (least time/space)

2. Dutch flag problem: a sequence of blocks consisting only of red, white, and blue, so that the blocks are arranged in the order of red, white, and blue, and the time is O(n)

3. Find the kth smallest element in the array L[1...n]

4. n numbers constitute a set A, which is divided into two disjoint subsets A1 and A2. The numbers are n1 and n2, and the sum of the elements is s1 and s2. Satisfy |n1-n2| minimum and |s1-s2| maximum

1. Find the smallest element in the first pass and exchange this element with the first element

1. Find the smallest element in the second pass, exchange this element with the second element, and repeat n-1 times

1. Each sorting pass can determine the final position of an element.

1. Time complexity is always O(n²)

2. Unstable

1. Definition of heap

1.1 Heap operations

2. Construct the initial heap (large root heap)

3. Output the top element (maximum value) of the heap, put the last element into the top of the heap, and adjust the top of the heap downward to become a large top heap.

4. Repeat the operation until there is only one element left in the heap

1. The time complexity is always O(n㏒₂n)

2. Unstable

3. Space complexity: O(1)

1. Each element has two data items k1 and k2. Sort: look at k1 first, with the smaller one first; k1 has the same value, then look at k2, with the smaller one first.

1. Number of comparisons when inserting/deleting elements from the heap

2. Just want to get the partial sorted sequence before the kth (k≥5) smallest element

3. Determine whether a data sequence is a small root heap

1. First divide into n sub-tables with length 1, and merge them in pairs.

2. Obtain the sublists with length 2 and merge them two by two again, and repeat

1. Space complexity: O(n)

2. Time complexity: O(n㏒₂n)

1. Least Significant First (LSD)

2. Most significant bit first (MSD)

1. Not based on comparison, adopt the idea of ​​multi-keyword sorting

1. Space complexity: O(r)

2. Time complexity: O(d(n r))

3. Stable

1. What method should be used to sort 10TB data files?

1. Merge two ordered lists with n elements each into one ordered list

1. How many sorting code comparisons are performed in radix sorting?

1.n is smaller

1.1 Medium scale (n<1000)

2. n is very large (choose the one with less time)

3.n is very large, the number of keywords is small and can be decomposed

4. The sequence is basically in order

5.The result after several sortings

6. Several of the most

7.0 Algorithm time is independent of the initial sequence

7.1 The number of sorting passes has nothing to do with the initial sequence

7.2 The number of moves has nothing to do with the initial sequence

Radix sort has nothing to do with the initial sequence

8. Find the least efficient data structure

9. If sequential storage is replaced by chain storage, time efficiency will be reduced.

Combined with direct insertion sorting: first use direct insertion to obtain longer ordered subsequences, and then merge them in pairs, still stable

The comparison decision process can be described by a binary tree, so it takes at least O(n㏒₂n) time

Using linked lists as storage structures can avoid spending a lot of time moving records

Increase the number of merging paths/reduce the number of merging segments

loser tree

permutation-selection sort

best merge tree

1. Get the merged segment/serial string

2. Merge the merged segments one by one, so that the merged segments increase from small to large until they are completed.

n-the number of initial merging segments m-the number of merging paths ┌┐-round up

1. Offsets the benefits gained from reducing the number of external memory accesses due to increasing m.

2. Ordinary internal merge sort cannot be used

1. Leaf node

2. Internal nodes

3. Root node

As m increases, the input buffer increases, its capacity decreases, and the number of data exchanges between internal and external memory increases.

1. First take the smallest number a in the work area

2. Then take the smallest number among the numbers greater than a and put it into this merging section, and the number smaller than a is put into the next merging section.

1. Leaf node

2. Weight of leaf node

3. Path length from leaf node to root node

4.Non-leaf nodes

5. Weighted path length of merge tree

Let the merge segments with fewer records be merged first, and those with more records be merged last.

1. If the last missing item is not enough to form a strict m-ary tree, add a "virtual segment" with a length of 0 and merge it first.

2. Number of empty merge segments = m-u-1

1. There are n records in total, the workspace can accommodate a records, and m-way balanced merging is performed.

2.5 initial merge segments, each with 20 records, using 5-way balanced merge, Number of comparisons without loser tree and with loser tree

3. Do m-way balanced merging, the number of input and output buffers

4. The total number of input/output files available at the same time does not exceed 15