Knowledge of data structures and algorithms?
For most programmers, when learning techniques such as data analysis need to first understand the knowledge points about data structures as well as algorithms, below we will give you a brief introduction to what is a data structure? What are algorithms?
Most data structures and algorithms textbooks give a clear definition of these two concepts at the beginning. However, these definitions are very abstract and do not substantially help in understanding these two concepts, but instead will let you fall into the misunderstanding of sticking to the definitions. After all, we are studying now, not for the exam, so it is of little use to memorize the concepts as well as not being able to use them.
While we say that there is no need to dig deep into strict definitions, this is not the same as not needing to understand the concepts. Below I’ll help you understand the concepts of data structures and algorithms at both the broad and narrow levels.
In a broad sense, a data structure is a set of structures for storing data. An algorithm is a set of methods for manipulating data.
Surely you’ve seen libraries storing books, right? In order to make it easier to find, librarians usually “store” books in different categories. The books are numbered according to a certain pattern, which is the storage structure of this “data”.
How do we find a book? There are many ways, of course, you can find one by one, you can also be based on the number of the book category, is the humanities, or science, computers, to locate the bookshelf, and then in turn to find. In general terms, all of these finding methods are algorithms.
From the narrow sense, that is, our column to talk about, refers to certain well-known data structures and algorithms, such as queues, stacks, heaps, binary lookups, dynamic programming and so on. These are the crystallization of the wisdom of previous generations, and we can use them directly. These data structures and algorithms we are going to talk about are abstracted from many practical operational scenarios by previous generations, and after very much seeking and testing, they can efficiently help us to solve a lot of practical development problems.
What is the relationship between data structures and algorithms? Why do most books put them together?
This is because data structures and algorithms go hand in hand. Data structures serve algorithms, and algorithms work on top of specific data structures. Therefore, we can’t talk about algorithms in isolation from data structures, and we can’t talk about data structures in isolation from algorithms.
For example, because the array has the characteristics of random access, the commonly used binary search algorithm needs to use the array to store data. But if IT training chooses a data structure like a chained table, the binary lookup algorithm won’t work because chained tables don’t support random access.
The data structure is static; it is just a way of organizing data. A data structure that exists in isolation is useless if you don’t manipulate and build algorithms on top of it.
Selected MSOffice Exams for March 2018 Computer Level 2 Exam: Data Structures and Algorithms
Selected MSOffice Exams for March 2018 Computer Level 2 Exam: Data Structures and Algorithms
Data Structures and Algorithms
1. Basic Concept of Algorithms
(1) Concepts : An algorithm is a clear set of instructions for solving a problem.
(2) 4 basic characteristics: feasibility, certainty, infinity, and having enough intelligence.
(3) Two basic elements: operations and manipulations on data objects, and the control structure of the algorithm (the order of operations and manipulations).
(4) The basic methods of design: enumeration, induction, recursion, recursion, halving recursion techniques and backtracking.
2. Complexity of Algorithms
(1) Time complexity of an algorithm: the amount of computational effort required to execute the algorithm.
(2) Space complexity of an algorithm: the memory space required to execute the algorithm.
1.2 Basic Concepts of Data Structures
A data structure refers to a collection of interrelated data elements, i.e., the organization of data. The logical structure reflects the logical relationship between the data elements; the storage structure for the logical structure of the data in the computer storage space in the form of storage, sequential storage, chained storage, indexed storage and hash storage in four ways.
Data structure according to the complexity of the relationship between the elements before and after the pieces can be divided into:
(1) linear structure: there is only one root node, and each node has at most one direct predecessor and one direct successor of the non-empty data structure.
(2) Nonlinear structure: a data structure that does not satisfy the linear structure.
1.3 Linear Tables and Their Sequential Storage Structures
1. Basic Concepts of Linear Tables
Linear structures are also known as linear tables, and linear tables are one of the simplest and most commonly used data structures.
2. Sequential Storage Structure of Linear Tables
– The storage space occupied by the elements must be consecutive.
-Elements are stored in logical order in the storage space.
3. Insertion Operations in Linear Tables
The steps to insert a new element before the ith element are as follows:
Step 1: Move the original nth node to the ith node back by one element position in order.
Step 2: Place the new node at the ith position.
Step 3: Fix the number of nodes in the linear table.
In the worst case, where the inserted element is at the first position, all elements in the linear table need to be moved.
4. Deletion operations on linear tables
The steps to delete the element at the ith position are as follows:
Step 1: Move the n-i elements after the ith element, excluding the ith element, forward by one position in order;
Step 2: Correct the number of nodes in the linear table.
1.4 Stacks and Queues
1. Stacks and their basic operations
(1) Basic concepts: Stacks are a special kind of linear table, whose insertion and deletion operations are carried out only at one end of the linear table, which is also known as “first-in-first-out” or ” last-in-first-out” table. LIFO” table.
– Top of stack: the end that allows insertions and deletions.
– Bottom: the other end of the top of the stack.
– Empty stack: a stack with no elements in it.
-The top element of the stack is the last to be inserted and the earliest to be deleted.
-The bottom element of the stack is the element that was first inserted and last deleted.
– The stack has memory.
– In a sequential storage structure, stack insertion and deletion operations do not move other data elements in the table.
-Top-of-stack pointer top dynamically reflects changes in the elements of the stack
(3) Sequential storage and operations: entry operation, exit operation and read top-of-stack operation.
2. Queue and its basic operations
(1) Basic concepts: Queue is a linear table that allows insertion at one end and deletion at the other, also known as “first-in-first-out” linear table.
-Tail: The end of the queue where insertions are allowed, with the tail pointer pointing to the last element of the queue.
– Head: The end that allows deletions, with the head pointer pointing to the previous position of the head element.
(2) Circular queues and their operations.
The so-called circular queue is the last position of the queue storage space around to the first position, forming a logical circular space.
The entry operation is the addition of a new element to the end of the circular queue.
When the circular queue is not empty (s = 1) and the pointer to the end of the queue is equal to the pointer to the head of the queue, the circular queue is full, and the queuing operation can not be carried out, which is called “overflow”.
Unqueueing refers to exiting an element at the head of a circular queue and assigning it to a specified variable. The head pointer is first rounded up to one, and then the element pointed to by the head pointer is assigned to the specified variable. When the circular queue is empty (s=0), you can’t back out of the queue, which is called “underflow”.
1.5 Linear Chained Tables
A chained table is said to be single or linear if it contains only one pointer field for the address of the next element.
In chained storage, each node is required to consist of two parts: one part is used to store the data element values, called the data domain; the other part is used to store pointers, called the pointer domain. Where pointers are used to point to the previous or next node of that node (i.e., antecedent or consequent).
1.6 Tree and Binary Tree
1. Basic Concepts of Tree
A tree is a simple nonlinear structure, where there is one and only one node with no predecessor, called the root, and the rest of the nodes are grouped into m finite sets of disjoint sets T1, T2, …. T}mm, each of which is a tree, and T1, T2, …, T}mm are subtrees of the root node.
– Parent node: each node has only one antecedent, and there is only one node without antecedent, called the root node of the tree (referred to as the root of the tree).
– Child nodes: each ~ node can be followed by more than one antecedent, nodes without antecedents are called leaf nodes.
– Tree degree: the maximum degree of all nodes.
– Tree depth: the maximum level of the tree.
2. Definition of a binary tree and its basic properties
(1) Definition of a binary tree: a binary tree is a nonlinear structure, is a finite set of nodes, the set is empty (the empty binary tree) or consists of a root node and two non-intersecting left and right binary subtrees. They can be categorized as full binary trees and complete binary trees, where a full binary tree must be a complete binary tree, but a complete binary tree is not necessarily a full binary tree. A binary tree has the following two characteristics:
– A binary tree can be empty, an empty binary tree has no nodes, and a non-empty binary tree has one and only one root node;
– Each node can have up to two subtrees, called the left subtree and the right subtree.
What is the knowledge related to data structure algorithms?
Input: an algorithm has zero or more outputs. In order to portray the initial situation of the object of the operation, the term zero inputs means that the algorithm itself sets out the initial conditions. The latter phrase translates to mean that an algorithm can have no outputs if the algorithm itself gives the initial conditions. For example, print the sentence: NSLog. output: the algorithm has at least one output. That is, the algorithm must have an output. The output can be in the form of a printout, or it can return a value or multiple values, etc. It can also display some kind of hint. It can also display some hints. Infinity: the execution steps of the algorithm are finite, and the execution time of the algorithm is also finite. Deterministic: each step of the algorithm has a definite meaning and there is no dichotomy. Feasibility: the algorithm is usable, that is, it is able to solve the problem at hand. The design of an algorithm depends on the (logical) structure of the data, while the implementation of the algorithm depends on the storage structure employed. The storage structure of data is essentially the realization of its logical structure in computer memory. In order to fully reflect the logical structure of a piece of data, its image in memory consists of two aspects, i.e., the information between data elements and the relationships between data elements. Different data structures have their corresponding several operations. The operations of data are algorithms of operations defined on the logical structure of data, such as retrieval, insertion, deletion, updating and sorting. The operations on data are an important aspect of data structures, and no discussion of any data structure can be separated from a discussion of the operations on that structure and the algorithms that implement them. A data structure is different from a data type and from a data object in that it not only describes the data object of the data type, but also describes the interrelationships between the elements of the data object.
A data type is a general term for a set of values and a set of operations defined on that set of values. Data types can be divided into two categories: atomic types, and structural types. In a programming language, every piece of data belongs to a certain data type. The type specifies, either explicitly or implicitly, the range of values the data can take, how it can be stored, and the operations it is allowed to perform. Data types can be thought of as data structures that have been implemented in program design. When some new data structure needs to be introduced during the programming process, the storage structure of the data is always described with the help of the data type provided by the programming language. BASE-BAND SIGNAL: A raw electrical signal that is not modulated (subjected to spectral shifts and transformations). Baseband communication (also known as baseband transmission): refers to the transmission of baseband signals. The system that performs baseband transmission is called a baseband transmission system. The entire channel of the transmission medium is occupied by a baseband signal. Baseband transmission does not require a modem, small equipment costs, has the advantages of high rate and low bit error rate, etc.,. Suitable for short-distance data transmission, transmission distance of 100 meters, in the audio city phone, computer network communications are widely used.
Basic Concepts of Data Structures and Evaluation of Algorithms and Algorithms
1. Basic Concepts and Terminology
Data: data is the carrier of information, a collection of numbers, characters, and all the symbols that can be entered into a computer and recognized and processed by a computer program that describes the attributes of an objective
Data Elements: a data element is a basic unit of data. It is usually considered and processed as a whole
Data Object: a data object is a collection of data elements with the same properties, a subset of data
Data Type: a data type is a general term for a collection of values and a set of operations defined on this collection
Atomic Type: A data type whose values are not subdividable
Structural type: a data type whose values can be subdivided into a number of components (parts)
Abstract data type: an abstract organization of data and the operations associated with it
Data structure: a data structure is a collection of data elements that have one or more specific relationships with each other
Data structure Includes three aspects: logical structure, storage structure, operation of data
2. Three elements of data structure
Logical structure of data: logical structure refers to the logical relationship between data elements, that is, describing the data in terms of logical relationships has nothing to do with the storage of the data, which is independent of computers
Linear structure: linear table , stacks, queues, arrays
Nonlinear structures: sets, trees, graphs
Storage structure of data: storage structure is the representation (also known as image) of the data structure in the computer, also known as the physical structure. Representation of data elements and representation of relationships. A storage structure is a logical structure implemented in a computer language, which depends on the computer language
Categories: sequential storage, chained storage, indexed storage, hash storage
Operations on data: operations imposed on data include the definition and implementation of operations. The definition of an operation is specific to the logical structure and indicates the function of the operation. The implementation of an operation is specific to the storage structure and indicates the specific steps of the operation.
3. Basic Concepts of Algorithms
An algorithm is a description of the steps involved in the solution of a particular problem; it is a finite sequence of instructions, each of which represents one or more operations
Important Characteristics: Infinity, Determinism, Feasibility, Inputs, and Outputs
Criteria of a Good Algorithm Criteria: correctness, readability, robustness, efficiency and low storage requirements
4. Metrics of algorithmic efficiency
Measures of algorithmic efficiency are described by time complexity and space complexity
Time complexity: the frequency of a statement is the number of times the statement is repeatedly executed in an algorithm
Space complexity: the space complexity of an algorithm, S(n), is defined as the amount of storage space consumed by the algorithm, which is a function of the problem size, n
A program, when executed, requires storage space for the instructions, constants, variables, and input data used in its own execution, as well as units of work to manipulate the data and auxiliary units for storing the information needed to implement the computation.
Algorithms work in situ in the sense that the amount of auxiliary space required by the algorithm is constant, i.e., O(1)
Algorithms for Database Technical Knowledge Data Structures
Algorithms for Database Technical Knowledge Data Structures
For candidates who are going to take the computer level exam, the computer level exam knowledge tutorials are very important review materials. Here is my collection of algorithms for database technical knowledge data structures, I hope you read it carefully!
1, data: the basic unit of data is the data element. Data elements can consist of one or more data items. The data item is the smallest indivisible unit of data
2, data structure: the logical structure of the data, the storage structure of the data, the operation of the data
3, the main ways of storing data: sequential storage structure (logical and physical adjacent, storage density) and chained storage structure
Sequential storage structure:
Sequential storage formula Li = L0 + (i-1) × K sequential structure can be random access; insertion, deletion operations will cause a large number of corresponding nodes to move
Chained storage structure: a, the pointer field can be more than one, you can point to the empty, than than the sequential storage structure of the storage density of the small
b, logically adjacent nodes physically may not necessarily adjacent. c, insertion, deletion, etc., does not require a large number of moving nodes
4, the nodes are adjacent, and the node is not required to move the node.
4, sequential table: in general, if the length of n sequential table, the probability of insertion or deletion at any location is equal, the average number of times an element moves is n/2 (insertion) and (n-1)/2 (deletion).
5, chained tables: linear chained tables (single and bidirectional chained tables, etc.) and non-linear chained tables
Linear chained tables, also known as single chained tables, each of its one node contains only a pointer field, double chained tables, each node is set up with two pointer fields. (Note the insertion and deletion operations of the nodes)
6, stack: “last in first out” (LIFO) table. Application: expression solving, binary tree symmetric order tour, fast sorting algorithm, recursive process implementation
7, queue: “first-in-first-out” linear table. Applications: hierarchical traversal of trees
8, string: a finite sequence of zero or more characters.
9, multi-dimensional arrays of sequential storage:
10, sparse matrix storage: lower triangular matrix sequential storage
Other common storage methods are ternary and cross-chained table method
11, generalized table: a finite sequence consisting of zero or more single elements or sub-tables. The elements of a generalized table can be sub-tables, and the elements of a sub-table can also be sub-tables
12, tree structure: non-linear structure. Commonly used tree structures are trees and binary trees.
Difference between a binary tree and a tree: binary tree is not a special case of a tree, the main difference between a tree and a binary tree is that: the subtree of the node of the binary tree to distinguish between the left subtree and the right subtree, even if the node has only one subtree, it should also be clearly stated that the subtree is a left subtree or a right subtree.
13, tree (forest) and binary tree conversion between (to be able to convert)
14, binary tree and tree circumambulation (traversal)
binary tree circumambulation there are mainly the following three ways: the method of the preorder (NLR), symmetric order method (LNR), the method of the posterior (LRN)
circumambulation of the tree and the forest: depth-first and according to breadth-first two ways Conduct. Depth-first way can be subdivided into periphyton order and periphyton order periphyton
Correspondence between periphyton and binary tree periphyton: periphyton order periphyton tree is exactly equivalent to the binary tree corresponding to periphyton tree according to the preorder method, and periphyton order periphyton tree is exactly equivalent to `binary tree according to symmetric order method periphyton
By breadth-first way is hierarchical order periphyton
15, Binary tree storage and clues
Binary tree storage structure: binary tree llink-rlink storage representation
Clue binary tree: in the binary tree with n nodes and llink-rlink storage representation, there must be n + 1 null pointer field
16, Huffman tree: a class of trees with weighted paths of the shortest length. The weighted path length of the tree is the sum of the weighted path lengths of all the leaf nodes in the tree WPL.
(1) sequential find: the average length of the find is (n+1)/2 times, time complexity of O (n)
(2) bisection find: the linear table nodes must be sorted by the value of the key code, and the linear table is stored in sequential memory. . Finding success comparison times log2n, finding failure comparison times log2n+1
(3) chunked lookup: first inter-block lookup, then intra-block lookup.
(4) hash table (hash table hash) storage and lookup: methods to deal with conflicts: open address method (linear probing method), zipper method, etc.
Load factor (loading factor) = the number of nodes actually stored in the table / the maximum number of nodes that can be stored in the table (i.e., the length of the table)
Bifurcated sorted tree: the value of all the key codes of the left subtree of each node is less than that of the All keycode values in the left subtree of each node are less than the node’s keycode value, and all keycode values in the right subtree of each node are greater than the node’s keycode value. Symmetric perimeter binary tree to get an ordered sequence, time complexity O(log2n)
B-tree and B+-tree: M-order tree, each node has at most M-1 keycodes, and at least M/2 (taking the upper bound)-1 keycodes. b-tree is suitable for random search, not for sequential search. b+-tree is suitable for sequential search.
Direct insertion sort, Hill sort, direct selection sort, heap sort, bubble sort, quick sort and other sorting algorithms to understand.
Direct Choice Sort, Hill Sort, Quick Sort and Heap Sort are unstable sorts and other sorts are stable sorts