● school profile, Shandong University
Founded in 190 1, Shandong University is known as the earliest modern higher education university in China. Its medical discipline originated from 1864, which opened modern higher medical education in China. Since its birth, the school has experienced several historical development periods, such as Shandong University Hall, National Qingdao University, National Shandong University, Shandong University and the new Shandong University formed by the merger of former Shandong University, Shandong Medical University and Shandong Polytechnic University. Since 120, Shandong University has always adhered to the mission of "storing talents for the world and enriching Qiang Bing", deeply practiced the spirit of "endless learning and lofty aspirations", made unremitting efforts, passed down from generation to generation, accumulated and formed the school spirit of "advocating truth, seeking truth from facts and being innovative", trained more than 600,000 talents of all kinds, and made contributions to national and regional economic and social development.
● The nature, objectives and contents of the "832 Computer Comprehensive" exam.
Computer synthesis includes data structure and computer composition principle, each accounting for 1/2.
I. Data structure
First, the basic requirements of the exam
Candidates are required to systematically understand the basic concepts of various main data structures such as linear structure (linear table, array and matrix, stack, queue, skip table and hash table), tree structure (forest (tree), binary tree, priority queue, search tree) and graph structure, and master the definitions, implementation algorithms and applications of various data structures; Master basic algorithm design methods (recursion, greedy algorithm, divide and conquer, dynamic programming) and their applications; Master the method of program performance analysis. Candidates are required to have abstract thinking ability, logical reasoning ability, and the ability to comprehensively apply what they have learned to analyze and solve problems.
Second, the scope of the examination
(a) preparing knowledge
The basic grammatical structure of 1 and its application. C++
2. Recursive ideas and methods
(2) program performance analysis
Representation and calculation method of 1. complexity (time complexity and space complexity)
2. Insertion sorting method, selection sorting method, bubbling sorting method and sorting method.
3. Sequential search and semi-search methods
(3) Linear table
1. Array description and linked list description of linear table.
2. Implementation methods of basic operations such as inserting, deleting and merging linear tables.
3. Function, realization method and application of dynamometer.
4. Application of linear table structure: box sorting, cardinal sorting, union (online equivalence class), etc.
(4) Arrays and matrices
1. General matrix storage method and basic operation implementation
2. The characteristics, storage methods and basic operation realization of special matrix.
3. Storage method and basic operation realization of sparse matrix.
(5) Stacking
The basic concept, operation and implementation of 1. stack
2. Application of stack structure: bracket matching, train car rearrangement, maze mouse, offline equivalence class, etc.
(6) queuing
The basic concept, operation and implementation of 1. queue
2. Application of queue structure: train car rearrangement, circuit wiring, graphic element identification, etc.
(7) Skip table and hash
Basic concepts and representation structure of 1. dictionary structure
2. The basic concept, basic operation and implementation method of skip table.
3. The basic concept, basic operation and implementation method of hash table.
4.LZW compression idea
(8) Binary trees and other trees
The basic concepts, storage methods, common operations and characteristics of 1. tree (and forest) and binary tree.
2. The traversal method and application of preorder, middle order, postorder and hierarchy of binary tree.
3. Storage methods of trees (and forests)
4. Application of tree and binary tree structure: parallel search set (online equivalent class) based on tree storage, etc.
(9) Priority queue
Basic concept and representation structure of 1. priority queue
2. The basic concept of heap structure, and the implementation method of inserting, deleting and initializing heap.
3. Application of heap structure: heap sorting, Huffman tree and huffman encoding.
4. The basic concept of left high tree and the realization ideas of operations such as insertion, deletion, merger and initialization.
(10) search tree
The basic concept of 1. binary search tree (sorting tree) and the implementation methods of operations such as insertion, deletion and search.
2. The basic concept of binary balanced tree (AVL tree) and the implementation methods of operations such as inserting, deleting and searching.
3. The basic concepts of M-fork search tree and B-tree, and the implementation methods of inserting, deleting and searching.
(1 1) diagram
Basic concepts and characteristics of 1. graph
2. The storage methods of adjacency matrix and adjacency list of graphs, as well as various basic operations and implementation methods.
3. Depth-first search and width-first search algorithms of graphs.
4.DFS/BFS application: finding paths, connected graphs and connected components, spanning trees, etc.
(12) Greedy algorithm
The basic idea of 1. greedy algorithm
2.2 topological sorting algorithm. AOV network.
3. Single-source shortest path Dijkstra algorithm
4. The concept of minimum cost spanning tree, Prim algorithm and Kruskal algorithm.
5.5 critical path algorithm. AOE network
13) divide and conquer
1. The idea of divide and rule
2. Combined sorting and quick sorting methods
3. Choose the method to solve the problem
(14) dynamic programming
1. Dynamic programming idea
2. Shortest path algorithm between all vertex pairs
Three. refer to
(a) Data Structure, Algorithms and Applications-Described in c++ Language (2nd edition of the original book), by Sartaj Sani, translated by Liu Zhihong, published by Machinery Industry Press 20 15.
(2) Data Structure (second edition described by object-oriented method and C++ language) Yin Renkun Tsinghua University Publishing House.
principles of computer composition
I. Basic requirements of the course
(a) to understand the internal working principle, composition structure and interconnection mode of each component in a single processor computer system, and to have a complete concept of the whole computer system;
(2) Understand the concept of hierarchical structure of computer system, be familiar with the interface between hardware and software, and master the basic knowledge and implementation method of instruction set architecture;
(3) Be able to comprehensively use the basic principles and methods of computer composition, calculate and analyze theoretical and practical problems in computer hardware systems, simply design some basic components, and analyze related problems with high-level programming languages (such as C language).
Second, the scope of the examination
(a) Overview of computer systems
1. History of computer development
2. Computer system hierarchy
(1) Basic components of a computer system
(2) the basic composition of computer hardware
(3) the classification of computer software
(4) the working process of the computer
3. Computer performance indicators
(1)CPU clock cycle, main frequency, CPI, CPU execution time, MIPS, MFLOPS.
(2) Word length
(3) Capacity
(4) Bus width
(2) Representation and operation of data
1. Number and coding
(1) carry counting system and its mutual conversion
(2) Truth value and number of machines
(3)BCD code
(4) Characters and strings
(5) Check code
2. Representation and operation of fixed points
Representation of (1) fixed point
Representation and value domain of unsigned numbers; The representation of signed numbers and their mutual transformation.
(2) Fixed-point operation
Fixed-point shift operation; Addition/subtraction operation of complement fixed point; Fixed-point multiplication/Divison; Concept and discrimination method of overflow.
3. Representation and operation of floating-point numbers
Representation of (1) floating-point number
The representation range of floating-point numbers; Conversion between floating point number and true value.
(2) Addition/subtraction of floating-point numbers
4. Arithmetic logic unit
(1) parallel adder
(2) Function and structure of arithmetic unit.
(3) Design principle of fast carry chain
(3) Memory level
1. Classification of memory
2. The hierarchical structure of memory
3. Semiconductor random access memory
Working principle of (1)SRAM memory
(2) The working principle of 2)DRAM memory; Refresh mode.
(3) read-only memory and flash memory
(4) The basic composition of main memory, the attributes of storage units and the storage mode of data.
(5) Technical indicators of memory
4. The expansion mode of memory and the connection between memory and CPU.
5. Multi-body parallel storage system
6. Cache (cache)
The basic working principle of (1) cache
(2)2) The mapping mode between cache and main memory and its address conversion.
(3) 3) Replacement algorithm of main memory block in cache.
(4) Cache read-write strategy
(4) Teaching system
1. instruction format
Basic format of (1) instruction
(2) Fixed-length opcode instruction format
(3) The instruction format of operation code is expanded.
2. The addressing mode of instructions
The concept of (1) effective address
(2) data addressing and instruction addressing
(3) Common addressing methods
The basic concept of 3.3. CISC and RISC
(5) Central processing unit
1. Functions and basic structure of central processing unit
2. Instruction execution process
3. Function and basic structure of data path
Based on data path, instruction cycle flow and data flow of fetching, addressing, executing and interrupting cycle.
4. Function and working principle of the controller
Analysis of (1) micro-operation command
Micro-operation commands with instruction fetch period, address addressing period, execution period and interrupt period and their beat arrangement.
(2) Combinatorial logic (hard-wired) controller
Composition structure and design steps of combinational logic controller.
(3) Microprogramming controller
Basic concepts of microprogram, microinstruction, microinstruction, micromanipulation and control memory;
The design idea, structure and working principle of microprogrammed controller;
Coding mode of microinstruction;
The form of micro address.
5. Instruction pipeline
Basic concept of (1) instruction pipeline
(2) Basic implementation of instruction pipeline
Factors affecting the performance of instruction pipeline: structural correlation, data correlation and control correlation;
The main performance of pipeline: throughput, acceleration ratio and efficiency.
(3) Multi-production technology of assembly line
Basic concepts of superscalar processor, super pipeline processor and very long instruction word processor.
(6) Bus
1. bus overview
Basic concept of (1) bus
(2) Classification of buses
(3) Composition and performance indicators of passenger cars
2. Bus arbitration
(1) centralized arbitration mode
(2) Distributed arbitration mode
3. Bus operation and timing
(1) synchronous timing mode
(2) Asynchronous timing mode
4. Bus standard
(7) Input and output system
The basic concept of 1 Input-output system
2. Input/output interface (input/output controller)
The function and basic structure of (1)I/O interface
(2)I/O ports and their addressing.
3. Input-output mode
(1) program query mode
(2) program interrupt mode
The basic concept of interruption; Interrupt response process; Interrupt processing; The concepts of multiple interrupts and interrupt masking; Interrupt processing sequence.
(3)DMA mode
Composition of DMA controller; DMA transfer process.
(4) Channel mode
Four. philology
(1)—— Fei, Principles of Computer Organization (3rd edition), Higher Education Press, 2020. 10, the 12th Five-Year Textbook for General Higher Education.
(2) Bai Zhongying and Dai, Principles of Computer Organization (6th Edition), Science Press, 20 19.8, National Planning Textbook for General Higher Education in the 12th Five-Year Plan.
Is the postgraduate entrance examination policy unclear? Is Shen Shuo confused with the same academic level? Is it difficult to choose a college major? Click on official website below, and a professional teacher will answer your questions. 2 1 1/985 postgraduate master/doctor open network application name: /yjs2/