兰州文理学院2021年招生

《数字媒体技术》考试大纲

(审判)

一、考试的目的

综合评估高职院校应届毕业生数字媒体技术专业核心课程是否达到教学大纲规定的目标。数字媒体技术专业的核心课程主要包括:数据结构和操作系统。甘肃省大学生数字媒体技术专业考试重点考核数据结构与操作系统课程的学习是否达到了教学大纲规定的目标。

二、考试范围

主要涵盖学院教学大纲中规定的数据结构和操作系统，是指本科数字媒体技术专业一、二年级的教学内容。重点考核学生对数字媒体技术基础知识的掌握程度和应用能力。考试不追求题型古怪，而是以基础知识为核心内容。为了保证试卷的可靠性，除了随笔题主观性强外，其他试题主要以客观性的形式出现。

三、考试内容

考试内容主要是指定教材，题型有单项选择题、多项选择题、真假题、简答题、随笔题五种。

教科书:

1.《实用数据结构基础》(第三版)，陈元春，中国铁道出版社；

2.《计算机操作系统》，唐，西安电子科技大学出版社，第四版。

第四，试题的难度

30%左右比较好问

大约60%中等难度的问题

难度增加10%左右

动词 （verb的缩写）解释

试卷满分200分，两门课成绩分别是:数据结构和操作系统各考100分。考试时间180分钟。

(a)数据结构(100分)

一、考试的目的

综合评估专升本(含高职院校)应届毕业生的数据结构课程是否达到教学大纲规定的目标。数据结构部分主要考核对数据结构中基本概念和原理的掌握情况；要求考生具备抽象思维能力、逻辑推理能力、综合运用所学知识分析问题和解决问题的能力，以及基本的编程和编程能力。

二、考试范围

主要涵盖了陈元春主编辑《实用数据结构》(中铁出版社，2011年第三版)中的部分内容，重点介绍了数据结构中的线性表、栈、队列、树、图、搜索和排序的基本概念、原理和应用能力。考试不追求题型古怪，而是以基础知识为核心内容。所有试题均严格从教材内容中选取。

三、考试内容

考试内容包括掌握基础知识、线性表、栈、队列、字符串、多维数组、概化表、树、二叉树、图、搜索排序、掌握应用相关简单算法等七个部分。

靠前部分:基础知识，共5分。

本部分考察学生对数据结构的基本概念和术语、算法和算法分析的概念和描述方法的理解和掌握情况。

(1)了解数据、数据元素、数据对象、数据结构、数据类型等概念的定义。

(2)掌握数据的逻辑结构、存储结构和类型，以及算法的重要特点。

(3)理解时间复杂度和空之间复杂度的概念。

第二部分:线性表，共10分。

本部分考查学生对线性表的定义、逻辑结构、顺序存储结构、链式存储结构的理解和掌握，单向链表、循环链表、双向链表的概念和表示，一元多项式的表示和加法。

(1)了解线性表的定义和线性结构的特点。

(2)了解线性表的顺序存储和链式存储，了解它们的优缺点。

(3)掌握线性序列表中数据元素存储位置的计算。

(4)掌握顺序表、单向链表、循环链表、双向链表的插入和删除。

(5)将使用单链表来编写插入、删除等相关算法。

第三部分:栈和队列，共10分。

本部分考查学生对栈定义、表示与实现、队列定义、表示与实现、链队列、循环队列、栈应用的理解和掌握。

(1)了解栈和队列的定义。

(2)了解线性表、栈和队列的特点和区别，以及栈在实现递归过程中的作用。

(3)掌握序列栈和链栈的栈入口和栈出口操作，序列队列和链队列的队列入口和队列出口操作，循环队列的queue 空和queue full的判断条件。

(4)会写进出栈、入队、离队的算法。

(5)了解栈的相关应用，如数字转换、表达式求值、子程序调用、递归调用等算法。

第四部分:字符串、多维数组、广义表，共10分。

本部分考查学生对相关定义、逻辑结构、静态存储结构、动态存储结构、字符串的基本运算和应用、数组的定义和运算、顺序存储结构、特殊矩阵和稀疏矩阵的定义和压缩存储、广义表的定义和存储结构的理解和掌握。

(1)了解字符串的定义。

(2)了解字符串的逻辑结构、定长顺序存储结构、链接存储结构、堆分配存储结构。

(3)掌握传统的字符串模式匹配方法。

(4)了解多维数组、特殊矩阵和稀疏矩阵的定义，广义表和链表表示的概念。

(5)了解特殊矩阵压缩存储的概念。

(6)掌握矩阵压缩存储的计算方法。

(7)掌握广义表的首末存储方式。

第五部分:树和二叉树，共20分。

本部分考查学生对树结构定义和基本运算、二叉树定义、性质、存储结构、遍历二叉树和线索二叉树、树存储结构、森林和二叉树之间的转换、树遍历、标识符树、霍夫曼树及其编码等的理解和掌握。

(1)了解树和二叉树的定义。

(2)了解二叉树的性质和存储结构。

(3)掌握遍历二叉树的方法、线索二叉树的构造、森林与二叉树的转换、最优二叉树和霍夫曼编码方法。

(4)利用二叉树的首根、中根、后根遍历来解决与二叉树相关的应用问题，编译与二叉树相关的算法。

第六部分:图，共15分。

本部分考察学生对图的定义和术语、图的基本运算、邻接矩阵和邻接表、深度优先搜索和广度优先搜索、无向图的连通分量、生成树、最小生成树、拓扑排序和关键路径的理解和掌握情况。

(1)了解图、生成树、最小生成树的定义和术语。

(2)理解邻接矩阵中元素和邻接表中节点的含义。

(3)掌握深度优先搜索和广度优先搜索算法。

(4)将使用Prim算法和Kruskal算法构造最小生成树。

(5)可以求出图中顶点的拓扑序列，用floyd算法和DijKstra算法求出顶点间的最短路径。

第七部分:整理，共15分。

这一部分考察学生对直接插入排序、半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、合并排序、基数排序以及各种内部排序方法的比较的理解和掌握情况。

(1)了解直接插入排序、二进制插入排序、Hill排序、冒泡排序、快速排序、简单选择排序、堆排序、合并排序、基数排序算法的基本思想。

(2)掌握上述排序算法的稳定性和时间复杂度分析。

(3)将使用上述排序方法写出每次排序的结果，并将写出与直接插入排序和简单选择排序相关的算法。

第八部分:搜索，共15分。

本部分考查学生对顺序搜索、二分搜索法、二叉排序树、平衡二叉树、哈希搜索、哈希函数构造方法和冲突处理方法的理解和掌握。

(1)了解搜索、关键词、平均搜索长度等基本概念。

(2)掌握顺序搜索、二分搜索法、分块搜索、二叉排序树、平衡二叉树、哈希搜索等基本算法思想及其搜索效率。

(3)掌握哈希函数的构造方法和冲突的处理方法，平衡二叉树的搜索、插入和删除算法。

(2)操作系统(100分)

一、考试的目的

综合考核专升本(含高职院校)应届毕业生的“数据结构”和“操作系统”两门课程是否达到教学大纲规定的目标，“操作系统”部分主要考核学生对操作系统基本概念和理论的掌握情况。

二、考试范围

主要涵盖唐、梁主编辑《计算机操作系统》(第四版)的内容，重点考核学生对操作系统基本概念和原理的掌握情况，以基础知识为考试核心内容。除了测试学生对课程知识的综合应用的综合应用题，其他的题都是从教材内容中严格选取的。

三、考试内容

靠前章操作系统介绍，大概10分。

了解操作系统的定义和功能；掌握操作系统的开发流程；掌握操作系统的分类；重点记忆操作系统的基本特征和主要功能；了解OS的结构设计。

第二章过程描述与控制，约10分。

了解过程的定义和特征；掌握过程的基本状态和过渡(三态模型)；了解PCB和过程控制的概念；掌握并灵活运用信号量机制解决经典进程同步问题；理解线程的概念。

第三章处理器调度和死锁，大概20分。

了解处理器调度的三个层次；掌握常用的调度算法(先到先得，先短操作，先高响应比)；理解操作、过程和程序之间的区别和联系；理解和掌握死锁的概念、原因和必要条件；了解处理死锁的四种对策(预防、避免、检测和取消)；掌握并灵活运用银行家算法避免死锁；

第四章内存管理，大概15分。

了解连续分配的四种内存管理模式(单一连续、固定分区、动态分区和可重定位)；掌握两种基本的离散存储管理方法(基本分页和基本分段)；了解分页和分段的主要区别。

第五章虚拟内存，10分左右。

掌握虚拟内存的定义；理解并掌握各种页面替换算法(先进先出、LRU、LRU近似算法)。

第六章投入产出体系，15分左右。

了解设备管理的基本功能；掌握四种输入输出控制模式(程序查询模式、中断模式、DMA模式、通道模式)；了解I/O软件的层次结构(中断处理、设备驱动、设备无关、用户层软件)；掌握后台打印系统的组成；理解缓冲的概念；了解并掌握磁盘调度算法并进行分析(先到先得、最短寻道时间、扫描算法、循环扫描算法)。

第七章文档管理，大概10分。

了解文件系统的基本功能；了解文件的逻辑结构(记录文件、流文件)和物理结构(连续结构、串行结构、索引文件)；掌握文档的访问方法(顺序访问法、直接访问法、密钥访问法)；掌握简单的文件目录。

第八章磁盘存储管理，约5分。

了解几种常见的文件存储空管理方法(空空闲表法，空空闲链法，位图法)；了解廉价的冗余阵列。

第九章操作系统界面，大概5分。

了解两种类型的界面(用户界面和程序界面)；理解系统函数调用。

部分内容来源于网络转载、学生投稿，如有侵权或对本站有任何意见、建议或者投诉，请联系邮箱（1296178999@qq.com）反馈。 未经本站授权，不得转载、摘编、复制或者建立镜像， 如有违反，本站将追究法律责任！