2023年天津理工大学计算机技术考研初试考试大纲

考研考试大纲一般是由各个院校自行发布，内容包含考试科目的考试范围、试卷结构、考试形式和主要参考资料等等。考试大纲对考生来说至关重要，以下是希赛网小编为大家整理的2023年天津理工大学计算机技术（085404）考研初试808数据结构与操作系统和818数据结构与C++程序设计(听障)的考试大纲，仅供大家参考。

相关推荐：2021-2022年分数线 | 研究方向一览表 | 考试科目 | 学费汇总 | 招生人数 | 历年真题

（注：以下信息来自学院官网，仅供参考，具体内容以院校发布为准）

808数据结构与操作系统一初试考试大纲

一、考试方式

考试采用笔试形式，考试时间为180分钟，试卷满分为150分。

二、 试卷结构与分数比重

数据结构占80分，题型及分配比例：选择题(25%)、综合应用题(75%)。

操作系统占70分，题型及分配比例：填空题(20%)、选择题(20%)、简述题(20%)、算法实现与综合分析习题(40%)。

三、考查的知识范围

《数据结构与操作系统》入学考试总分150分，包括两部分内容：其中数据结构考试主要涉及线性结构、树、图、查找和排序中的典型数据结构和算法，要能够针对具体问题进行分析，选择正确的逻辑结构、设计合理的存储结构、提出解决问题的方法或算法，并能对所选方法和算法的正确性、复杂性进行分析，占80分;操作系统考试主要涉及基本概念、原理和功能，理解操作系统的整体运行过程， 掌握操作系统进程、内存、文件和I/O管理的策略、算法、机制以及相互关系，能够运用所学的操作系统原理、方法与技术分析问题和解决问题，并能利用C语言描述相关算法，占70分。

数据结构部分

一、绪论

1. 数据结构相关基本概念

2. 逻辑结构和物理结构

3. 算法效率的度量(O-表示法)

二、线性表、栈和队列(以下各点要求掌握算法的程序实现)

1. 顺序表的表示和基本操作的实现算法

2. 单链表、循环链表、双向链表的表示和基本操作的实现算法

3. 栈的表示和基本操作的实现算法

4. 循环队列、链队列的表示和基本操作的实现算法

三、数组、递归

1. 数组的存储方式

2. 特殊矩阵的压缩存储

3. 递归思想的特点

4. 递归算法和递归函数

四、树和二叉树

1. 树的定义和基本术语

2. 二叉树的定义、性质，二叉链表存储结构

3. 完全二叉树的性质

4. 二叉树的深度优先(先序、中序、后序)和广度优先(层序)遍历算法和程序实现

5. 树的存储结构

6. 树、森林与二叉树的转换

7. 哈夫曼树的定义、性质、构造方法、哈夫曼树的应用

五、图

1. 图的定义和术语

2. 图的邻接矩阵、邻接表存储结构

3. 图的深度优先搜索、广度优先搜索及其算法实现

4. 生成树的定义，图的最小生成树定义与构造方法(不要求算法实现)

5. 拓扑排序

6. 单源最短路径问题的求解

六、查找

1. 平均搜索长度(ASL)的定义

2. 顺序表的查找算法、程序实现和ASL分析

3. 二分查找法的算法描述、程序实现和ASL分析

4. 索引顺序表的查找(分块查找)方法和和ASL分析

5. 二叉排序树的定义、插入、删除操作

6. 平衡二叉树的定义、构造(掌握4种旋转方法)，计算等概率下查找成功的ASL和查找不成功的ASL

7. B-树的定义、插入与删除操作

8. 散列表的概念，几种常用散列函数的构造方法

9. 散列表处理冲突的方法(线性探查法、二次探查法、再散列法、链地址法)，计算等概率下查找成功的ASL和查找不成功的ASL

10.散列表负载因子(装填因子)α的定义

七、排序(以下每种排序算法要求掌握排序过程和程序实现)

1. 直接插入排序、希尔排序

2. 冒泡排序、快速排序

3. 简单选择排序、堆排序

4. 归并排序

5. 基数排序(箱排序)

6. 以上各种排序算法的时间复杂度分析，各自的特征及其比较

操作系统部分

一、操作系统概述

1.操作系统的概念、特征、功能和作用

2.操作系统的发展与分类

3.操作系统体系结构

二、进程管理

1.进程与线程

(1)进程概念

(2)进程的状态与转换

(3)进程控制

(4)进程同步

(5)进程通信

共享存储系统;消息传递系统;管道通信。

(6)线程概念与线程实现方式

2.处理机调度

(1)调度的基本概念

(2)调度时机、切换与过程

(3)调度的基本准则

(4)调度方式

(5)典型调度算法

先来先服务调度算法;短作业(短进程、短线程)优先调度算法;时间片轮转调度算法;优先级调度算法;高响应比优先调度算法;多级反馈队列调度算法。

3.同步与互斥

(1)进程同步的基本概念

(2)实现临界区互斥的基本方法

软件实现方法;硬件实现方法。

(3)信号量机制

(4)管程机制

(5)经典同步问题

生产者-消费者问题;读者-写者问题;哲学家进餐问题;睡眠理发师问题。

4.死锁

(1)死锁的概念

(2)死锁处理策略

(3)死锁预防

(4)死锁避免

系统安全状态;银行家算法。

(5)死锁检测和解除

三、存储器管理

1.存储器管理概念

(1)存储器的层次结构

(2)程序的装入和链接

绝对装入方式;可重定位装入方式;动态运行时装入方式。

静态链接方式;装入时动态链接方式;运行时动态链接方式。

(3)交换技术

(4)连续分配存储管理方式

单一连续分配;固定分区分配;动态分区分配(基于顺序搜索的动态分区分配算法、基于索引的动态分区分配算法);动态可重定位分区分配。

(5)非连续分配管理方式

分页管理方式;分段管理方式;段页式管理方式。

2.虚拟内存管理

(1)虚拟存储器基本概念

(2)请求分页存储管理方式

(3)页面置换算法

最佳置换算法OPT;先进先出置换算法FIFO;最近最久未使用置换算法LRU;最少使用置换算法LFU;时钟置换算法CLOCK;页面缓冲算法PBA。

(4)页面分配策略

(5)抖动与工作集

(6)请求分段存储管理方式

四、输入输出(I/O)管理

1.I/O管理概述

(1)I/O系统的功能

(2)I/O软件层次结构

(3)I/O系统接口

(4)I/O控制方式

(5)设备控制器

(6)设备驱动程序

(7)设备无关性

2.I/O核心子系统

(1)缓冲区管理

(2)设备分配与回收

(3)假脱机技术(SPOOLing)

3.磁盘存储器的性能和调度

(1)磁盘性能与结构

(2)磁盘调度算法

先来先付服务FCFSl;最短寻道时间优先DDTF;扫描算法SCAN (电梯调度算法);循环扫描算法CSCAN;NStepSCAN和FSCAN调度算法。

五、文件管理

1.文件系统基础

(1)文件概念

(2)文件的逻辑结构(顺序文件、索引文件、索引顺序文件)

(3)文件目录

文件控制块和索引节点;单级目录结构和两级目录结构;树形目录结构。

(4)文件共享

(5)文件保护

2.磁盘存储器的管理

(1)外存组织方式

连续组织方式;链接组织方式(FAT技术、NTFS技术);索引组织方式。

(2)文件存储空间的管理

空闲表法;空闲链表法;位示图法;成组链接法。

(3)提高磁盘I/O速度的方法

(4)磁盘可靠性技术

(5)数据一致性控制

四、参考书目

《数据结构》 机械工业出版社 2008年 戴敏

《计算机操作系统》(第四版)，汤小丹等编著, 西安电子科技大学出版社。

818数据结构与C++程序设计(听障)一初试考试大纲

一、考试方式

考试采用笔试形式，考试时间为180分钟，试卷满分为150分。

二、 试卷结构与分数比重

题型包括填空题(20%)、选择题(20%)、算法或数据结构的设计与分析题(30%)、程序分析题(15%)与编程题(15%)等。

三、考查的知识范围

《数据结构与C++程序设计》入学考试包括两部分内容：其中数据结构考试主要涉及线性结构、树、图、查找表和排序，占75分;C++程序设计考试主要涉及支持面向对象程序设计的内容，同时兼顾C++支持结构化程序设计的特征，占75分。本试卷总共150分，具体考试内容主要包括：

数据结构部分

一、数据结构基础(5%)

1. 数据结构相关基本概念

2. 逻辑结构和物理结构

3. 算法效率的度量(O-表示法)

二、线性表、栈和队列(20%)(以下各点要求掌握算法的程序实现)

1. 顺序表的表示和基本操作的实现算法

2. 单链表、循环链表、双向链表的表示和和基本操作的实现算法

3. 栈的表示和和基本操作的实现算法

4. 循环队列、链队列的表示和和基本操作的实现算法

三、数组、递归(5%)

1. 数组的存储方式

2. 特殊矩阵的压缩存储

3. 递归思想的特点

4. 递归算法和递归函数

四、树和二叉树(20%)

1. 树的定义和基本术语

2. 二叉树的定义、性质，二叉链表存储结构

3. 完全二叉树的性质

4. 二叉树的深度优先(先序、中序、后序)和广度优先(层序)遍历算法和程序实现

5. 树的存储结构

6. 树、森林与二叉树的转换

7. 霍夫曼树的定义、性质、构造方法

五、图(15%)

1. 图的定义和术语

2. 图的邻接矩阵、邻接表存储结构

3. 图的深度优先搜索、广度优先搜索及其算法实现

4. 生成树的定义，图的最小生成树定义与构造方法(不要求算法实现)

5. 拓扑排序

6. 单源最短路径问题的求解

六、查找(25%)

1. 顺序表的查找算法、程序实现

2. 二分查找法的算法描述、程序实现

3. 索引顺序表的查找(分块查找)方法

4. 二叉排序树的定义、插入、删除操作

5. 平衡二叉树的定义、构造(掌握4种旋转方法)

6. B-树的定义、插入与删除操作

七、排序(10%)(以下每种排序算法要求掌握排序过程和程序实现)

1. 直接插入排序、希尔排序

2. 冒泡排序、快速排序

3. 简单选择排序、堆排序

4. 归并排序

5. 基数排序(箱排序)

6. 以上各种排序算法的时间复杂度分析，各自的特征及其比较

C++程序设计部分

一、C++基础语法(15%)

1. C++的字符集与词法规则

2. 常见的数据类型

3. 变量与常量

4. 运算符的优先级和结合性

5. 表达式的类型与计算顺序

6. 语句：包括操作运算语句和流程控制语句

7. C++中的编译预处理

二、函数、指针、结构与联合(15%)

1. 函数定义/说明的格式

2. 函数的参数和返回值

3. 函数的调用机制

4. 函数的参数传递方式

5. 重载函数以及函数重载的原则

6. 标识符的作用域与变量的存储类别

7. 指针、引用与数组的概念和应用

三、类的封装性(20%)

1. 类的定义

2. 构造函数与析构函数

3. 隐含的this指针

4. 类的静态成员

5. 类的友元

6. 指向类成员的指针

7. 复杂对象与成分对象

8. 类的常量成员

四、类的继承性(15%)

1. 基类与派生类

单继承与多继承

继承方式：public protected private

2. 访问特征

派生类成员函数对基类成员的访问

派生类对象对基类成员的访问

派生类的派生类对基类成员的访问

3. 虚拟继承(共享继承)

多继承时的二义性

虚基类：在派生类对象中只有一份拷贝

4. 构造函数和析构函数的调用顺序

Con：虚基类-非虚基类-成员对象类-派生类

Des：以构造函数相反的顺序

五、多态性(15%)

1. 多态性的概念

2. 多态性的分类

编译时的多态性：采用静态联编

运行时的多态性：采用动态联编

3. 静态联编：概念与常见形式

4. 运算符重载：“四不变”原则， 另外只能重载已有的运算符，而不能创造新的运算符;即将c++已有的运算符扩展到用户自定义类的类型上。

① 两种形式：成员函数与友元函数形式

② ++ --的重载，分前缀和后缀两种形式

5. 动态联编

虚函数的概念与应用

六、模板与I/O流类(20%)：

1. 模板引入的必要性

函数模板

类模板

2. C++ I/O流类库

标准I/O

文件I/O

字符串I/O

四、参考书目

《数据结构及其C语言实现》(第1版) 李少辉 北京邮电大学出版社 2015.1

《C++程序设计》(第3版) 谭浩强 清华大学出版社 2015.8

资料来源：天津理工大学2023考研初试自命题科目考试大纲