升研教育考研频道为23考研、24考研的同学们整理了“安徽师范大学2021年考研真题:896计算机理论基础”的相关信息,希望对正在备考的你有所帮助。考研复习效率不高怎么办?自己备考抓不住重点?想报考985/211等热门院校,但是没把握?升研教育推出考研集训营,全日制封闭式面授,10余年授课经验的老师,浓厚的学习氛围助你冲击目标、一战上研!
安徽师范大学2021年考研真题:896计算机理论基础
考试科目:896计算机理论基础
适用专业:081200计算机科学与技术
第一部分数据结构(80分)
一、简答题(每小题5分,共20分)
1.简述线性结构中数据元素间关系的特点,并列举常用的线性结构(3种以上)。
2.简述头结点和头指针的概念,并说明链表中加入头结点的作用。
3.对于一个栈,如果输入序列为A、B、C,给出全部可能的输出序列。
4.简述稀疏矩阵压缩存储的方法。
二、应用题(每小题8分,共40分)
1.一棵二叉树的后序遍历序列为CEFDBKJIHGA,中序遍历序列为CBEDFAHJKIG,给出相应的二叉树以及先序遍历序列。.
2.已知图G的邻接矩阵如下图所示,顶点集V={ V0, V1,V2,V3,V4,V5}。
(1)画出图G;
(2) 基于上述邻接矩阵,给出从顶点Vo出发的深度优先遍历序列。
3.已知权值集合为{16,5, 9, 3,30,1}, 构造出哈夫曼树(要求:左孩子结点权重为最小值,右孩子结点权重为次小值),并计算其带权路径长度。
4.设哈希表HT表长m为13,哈希函数为H(k)=k MOD m,给定的关键字值序列为{19,14,23,10,68,20,84,27,55,11}。采用线性探测再散列解决冲突构造该散列表,并给出在等概率条件下查找成功时的平均查找长度。
5.设待排序序列为{10,18,4,3,6,12,1,9,18,8}, 请写出直接插入排序前四趟以及第一趟快速排序的结果。
三、算法设计题(每小题10分,共20分)
1.设计一个空间复杂度为0(1)且时间上尽可能高效的算法,在带头结点的单链表L中删除所有值为x的结点。
2.有向图G采用邻接矩阵存储,设计算法求图G中顶点度的最大值。图的邻接矩阵存储定义如下:
第二部分操作系统 (70分)
一、简答题(每小题5分,共30分)
1.多道程序设计技术的主要优点是什么?
2.什么是临界资源、临界区?
3.同步机制应遵循哪些准则?
4.按序分配是预防死锁的一种策略。试说明什么是按序分配?
5.在采用首次适应算法回收内存时,可能出现哪几种情况?
6.简述文件逻辑结构的类型。
二、应用题(每小题10分,共40分)
1.设一系统中有四类资源R1、R2、 R3、 R4, 且每类资源总数分别为6、3、4、2。在某时刻,系统状态如下表所示,问:若进程B请求(0,0,1,0),可否立即分配?请分析说明。
2.在分页、分段、段页式存储管理中,当访问一 条指令或数据时,各需要访问内存几次?假设一个分页存储系统中有快表,多数活动页表项都可以存在其中。若页表在内存中,内存访问时间为1μs,检索快表时间是0. 2μs,若快表的命中率是85%,则存取时间是多少?
3.设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址。若某进程最多需要6页数据存储空间,页的大小为1KB,操作系统采用固定分配局部置换策略为此进程分配4个物理块。在时刻260前,该进程的访问情况见下表(访问位即使用位)。
当该进程执行到时刻260时,要访问逻辑地址为17CAH的数据。请回答下列问题:
(1)该逻辑地址对应的页号是多少?
(2)若采用先进先出(FIF0) 置换算法,该逻辑地址对应的物理地址是多少,要求给出计算过程。
4.多个生产者进程和多个消费者进程共享-一个能存放500件产品的环形缓冲区(初始为空)。当缓冲区未满时,生产者进程可以放入其生产的一-件产品,否则等待;当缓冲区未空时,消费者进程可以从缓冲区取走一件产品,否则等待。要求一个生产者进程连续向缓冲区放5件产品后,其他生产者进程才可以放产品。请使用P、V操作实现进程间的互斥与同步,要求写出完整的过程,并说明所用信号量的含义和初值。
免责声明:本站所提供的内容部分来源于网络搜集整理,由本站编辑上传,仅供个人研究、交流学习使用,不涉及商业盈利目的。如涉及版权问题,请联系本站管理员予以更改或删除。
距2024考研还剩天
三师服务丨全程规划丨大咖领学
三师服务丨全程规划丨大咖领学
三师服务丨全程规划丨大咖领学