Time: August 2006-65438+June Reading: 447

Data Structure and Operating System —— Outline of 2007 Postgraduate Entrance Examination of Fudan University

Fudan University enrolled graduate students in 2007.

Examination outline of data structure and operating system specialty course

The first part data structure

Test questions: short answer questions, programming questions

Bibliography: Data Structure (described by object-oriented method C++) Yin Renkun, Tsinghua University Publishing House.

Total score: 100

The basic requirements of the exam

Candidates are required to systematically understand the basic concepts and theories of data structures, master the characteristics and basic methods of various data structures, and emphasize that candidates should have the ability to comprehensively apply what they have learned to analyze and solve problems.

Requirements for programming languages

All algorithms in data structure testing are required to be described in C or C++ language.

I. Array

Examination content

Data; Sequence table; String matching.

Examination requirements

1. Understand the storage structure of array, and master the corresponding relationship between array elements and storage units under the condition of sequential storage.

2. Understand the structure and characteristics of sequence table, and master the implementation algorithm of basic operations on sequence table.

3. Master the basic algorithms of string comparison (including KMP algorithm).

4. Have the ability to solve practical problems with array structure.

Second, the linked list

Examination content

Single linked list; Bidirectional linked list; Circular linked list; Sparse matrix.

Examination requirements

1. Understand the storage structure and characteristics of single linked list, double linked list and circular linked list, and master the implementation algorithm of their basic operations.

2. Understand the storage structure and characteristics of sparse matrix, and master the implementation algorithm of basic operations of sparse matrix.

3. Have the ability to solve practical problems (such as polynomial operation realized by linked list) with linked list structure.

Third, stacks and queues

Examination content

Stack; Line up.

Examination requirements

1. Understand the definition and structural characteristics of stack, and master its storage mode (sequential storage and linked storage) and the implementation algorithm of basic operations.

2. Understand the structure and characteristics of queues, and master their storage methods (sequential storage and linked storage) and the implementation algorithm of basic operations.

3. Ability to solve practical problems (such as expression calculation and priority queue) with queue and stack structure.

Fourth, recursion

Examination content

Recursion.

Examination requirements

1. Understand the basic concept and implementation principle of recursion, and master the method of describing problems and writing algorithms with recursion.

2. Master the recursive solution of the problems such as the Tower of Hanoi and the maze.

3. Use the stack to master the non-recursive solution of recursive problems.

Verb (abbreviation for verb) trees and forests

Examination content

Trees, binary trees, forests, piles.

Examination requirements

1. Understand the structure of the tree and master the main concepts of the tree.

2. Understand the structure of various binary trees, master their characteristics, and have the ability to use binary trees to solve practical problems.

3. Master the principles and properties of three traversal methods of binary tree, apply the traversal method of binary tree to solve the problems of leaf node number and counting of binary tree, and master the non-recursive implementation method of traversal.

4. Master the structure and basic operation of clue binary tree.

5. Understand the principle of heap and master the implementation method of basic operation.

6. Understand the definition and storage structure of trees and forests, and master the implementation of methods such as traversal of trees and forests.

7. Understand the basic principle of huffman encoding and master the method of generating huffman encoding based on Huffman tree.

Collection and search of intransitive verbs

Examination content

Assembly; Equivalence class; Static search structure; Binary search tree; Best binary search tree; AVL tree.

Examination requirements

1. Understand the basic concepts of collections and master various storage methods of collections.

2. Master the generation algorithm of equivalence classes.

3. Master the search methods such as folding search and Fibonacci of ordered table.

4. Understand the definition and characteristics of AVL tree, and master the realization principle of AVL tree adjustment operation.

5. Master the construction principle and related algorithms of the optimal binary tree.

Seven. figure

Examination content

Figure; Connected component; Minimum graph; Shortest path; An active network.

Examination requirements

1. Understand various basic concepts related to graphics and master various storage methods of graphics.

2. Master two searching methods of graphs and the generation method of connected components.

3. Master two methods of generating minimum spanning tree.

4. Master all kinds of methods to find the shortest path.

5. Master the characteristics of two network structures, namely, using vertices to represent activities and using edges to represent activities, and the implementation algorithms of related operations.

Eight, sorting

Examination content

Insert sort; Exchange sorting; Select sorting; Merge and sort; Cardinal sorting; External sorting.

Examination requirements

Understand the realization of various sorting methods, master the time complexity and characteristics of various sorting algorithms, and be able to compare horizontally.

Nine. Index structure and hash

Examination content

Static index structure; Dynamic index structure; Hash.

Examination requirements

1. Understand the structure and characteristics of linear index structure, inverted list and static search tree.

2. Understand the structure of B-tree and master the implementation algorithms of various operations.

3. Understand the implementation principle of hash and master the implementation algorithms of various operations.

The second part of the operating system

The examination content includes the design principle and implementation method of four basic components: process, storage management, input and output and file system. The content also involves the basic knowledge of distributed operating system, cluster system and operating system security.

Candidates are required to systematically understand and master the basic concepts, main functions, main components and different implementation methods of each main component of the operating system; Master the basic idea of operating system design from the perspective of resource management and the interface between application programs and hardware systems, and master the management technology of various soft and hard resources in modern computer systems. Candidates are required to have the ability to comprehensively apply what they have learned to analyze and solve problems.

Test questions: fill in the blanks and multiple-choice questions, solve problems and calculate problems.

Bibliography: William Stalling S. Operating System: Internal and Design Principles. Fourth edition, Prentice Hall.200 1.

Total score: 50 points

Details of examination contents and requirements

I. Overview of Operating System

Examination content

1. Basic structure of computer, internal structure of processor, cache; Memory;

2. The concept, evolution, characteristics, classification, operating environment and functions of the operating system.

3. The hierarchical structure of memory

Examination requirements

1. Review the basic principles of computers and understand the software and hardware resources under the jurisdiction of the operating system;

2. Understand the key concepts of the operating system and grasp the characteristics and functions of the operating system as a whole;

3. Make a case study on the hierarchical structure of memory.

4. Establish the functional concepts of resource management and application program interface of operating system.

Second, the process

Examination content

Process, Process Description and Process State Transition

Examination requirements

Grasping the essential characteristics of the process, clarifying the dynamic characteristics of the process, and being familiar with the reasons for the transition between process states, and establishing the process are the basic concepts of resource allocation units and operating entities.

Threads, symmetric multiprocessing SMP and microkernel

Examination content

The concept of 1. thread defines the necessity and possibility of thread;

2. Functional characteristics and implementation of threads;

3. Symmetric multiprocessing SMP architecture:

4. The architecture of operating system (microkernel and monolithic kernel) and its performance analysis.

Examination requirements

1. Understand the necessity and possibility of introducing threads as basic running entities;

2. Master the various implementation methods and characteristics of threads;

3. Familiar with SMP architecture and operating system architecture (microkernel and monolithic kernel).

Fourth, concurrency.

Examination content

1. Concurrency and related concepts, such as critical section, mutex, semaphore and pipeline.

2. Various algorithms of process mutual exclusion, synchronization and communication;

3. The concept, causes and conditions of deadlock.

4. Deadlock prevention, avoidance and detection algorithm.

Examination requirements

1. You can use semaphore, pipeline and other technologies to solve the problem of mutually exclusive contract steps;

2. Understand the concept of deadlock and the necessary and sufficient conditions of deadlock;

3. Master deadlock prevention, avoidance and detection algorithms;

4. Understand how to avoid starvation when dealing with deadlocks.

Verb (abbreviation for verb) memory management

Examination content

1. Partition storage management, coverage and exchange;

2. Page management and segment management;

3. The management method and implementation technology of segment and page storage;

4. The principle of virtual memory and related algorithms and data structures.

Examination requirements

1. Understand the function of storage management and its support for multiprogramming;

2. Master the management method and implementation technology of segment and page storage;

3. Focus on mastering the principle of virtual memory and related algorithms and data structures.

Six, single processor scheduling

Examination content

Three scheduling types of 1. processor;

2. Various algorithms of process scheduling and their characteristics.

Examination requirements

1. Understand three scheduling types: remote, medium and short;

2. Focus on mastering various algorithms of process scheduling and their applicable environments.

Seven, multiprocessor scheduling and real-time scheduling

Examination content

1. Influence of Multiprocessors on Process Scheduling

2. Process and thread scheduling algorithm in multiprocessor environment:

3. Characteristics of real-time process;

4. Deadline scheduling and monotonic rate scheduling methods.

Examination requirements

1. Understand the concept of scheduling granularity;

2. Familiar with the process and thread scheduling algorithm in multiprocessor environment;

3. Understand the essence of real-time process and master the methods of deadline scheduling and monotonic rate scheduling.

Eight, equipment management and disk scheduling

Examination content

1. Organization of input and output functions in the operating system;

2. Interrupt processing;

3. Device driver, device-independent software interface and spooling technology;

4. Buffering strategy;

5. Disk scheduling algorithm;

6. Disk array.

Examination requirements

1. Understand the organization of input and output functions in input and output devices and operating systems;

2. Master interrupt handling, device driver, device independent software interface and spooling technology;

3. Focus on mastering various buffering strategies and disk scheduling algorithms for improving performance;

4. Understand various disk array configurations that can improve performance and reliability.

Nine, the file system

Examination content

1. File system characteristics and file organization;

2. The data structure of the file system;

3. The basic nature of the directory and its implementation method;

4. Management of disk space.

Examination requirements

1. Understand the file system characteristics and file organization;

2. Master the basic data structure of the file system;

3. Understand the basic properties of files and directories and their implementation methods;

4. Focus on the management of disk space, the performance and reliability of file system, the security and protection mechanism of file system.

X. distributed computer system

Examination content

1. Characteristics and types of distributed processing;

2. Multilayer architecture and middleware technology;

3. Cluster system;

4. Operating system design issues related to distributed process management.

Examination requirements

1. Understand the characteristics and types of distributed processing;

2. Master the basic concepts and characteristics of multi-tier architecture, middleware technology and cluster system;

3. Focus on process migration, recognition of distributed global state, distributed mutual exclusion and deadlock prevention.

XI。 Trusted computer system

Examination content

1. The security problems faced by computer systems and their coping mechanisms;

2. The basic concept of trusted system.

Examination requirements

1. Understand the security problems faced by computer systems and their coping mechanisms;

2. Master a comprehensive method of computer security design-trusted system.

How's it going? It is worthy of reference.