升研教育考研频道为23考研、24考研的同学们整理了“安徽师范大学2020年考研真题：896计算机理论基础”的相关信息，希望对正在备考的你有所帮助。考研复习效率不高怎么办？自己备考抓不住重点？想报考985/211等热门院校，但是没把握？升研教育推出考研集训营，全日制封闭式面授，10余年授课经验的老师，浓厚的学习氛围助你冲击目标、一战上研！

安徽师范大学2020年考研真题：896计算机理论基础

考试科目：896计算机理论基础

适用专业：081200计算机科学与技术

第一部分数据结构(80分)

一、简答题(每小题4分，共20分)

1.简述数据结构的逻辑结构与存储结构的含义及其相互关系。

2.线性表有两种存储结构，在什么情况下选用顺序表比链表更好。

3.栈底元素是不能删除的元素，此说法是否正确?请给出理由。

4.任意一个具有n个结点的二叉树，已知它有m个叶子结点,试证明它有n-2m+1个度数为1的结点。

5.具有n个顶点的有向完全图中有多少条边?

二、应用题(每小题8分，共40分)

1.给出下列算法被调用后得到的输出结果。

注意: enqueue(q, 'h")是将 h入队，dequeue(q, x) 是出队，并将出队元素赋给x，queueempty (q)用于判断队列是否为空，为空时，其值为真。

2.设一棵二叉树的先序序列为ABDEGCF,中序序列为DBGEACF.请画出这棵二叉树，并给出其后序序列。

3.请采用Prim算法为下图构造最小生成树，并给出构造过程。

4.将关键字序列{13, 5, 20, 19, 15, 8}散列存储到一个散列表中,该散列表的地址范围为0-7,散列函数为: H(key)= key MOD 7，采用线性探测再散列法处理冲突。请构造该散列表，并给出每个关键字的探测次数。

5.设待排序的关键字序列为{15, 5, 16, 2, 25, 8, 20, 9, 18, 12},试给出采用快速排序算法对该序列进行升序排序时的每一趟排序结果。

三、算法设计题(每小题10分，共20分)

1.设计一个算法，用头插法创建包含n个数据元素的带头结点的单链表L。

2.假设二叉树采用二叉链表存储结构存储，设计算法输出其先序遍历序列中第k个结点的值，假设k不大于二叉树的总结点数(结点数据域类型为字符型)。

第二部分操作系统(70分)

一、简答题(每小题5分,共30分)

1.什么是操作系统?

2.说明进程的三种基本状态。

3.产生死锁的四个必要条件是什么?

4.某分页系统的逻辑地址为16位，其中高6位为页号,低10位为页内偏移量，则每页的字节数是多少?最多可有多少页?

5.按资源分配方式可将外部设备分为哪几类?

6.分析文件的外存分配中连续分配方式的优缺点。

二、应用题(每小题10分，共40分)

1.现有某类资源12个，供3个进程共享。假定进程A已占1个资源，其最大需求4个，进程B已占4个资源，其最大需求6个，进程C已占5个资源，其最大需求8个。当3个进程同时请求尚需的资源时，系统应按怎样的次序为它们分配资源以保证不发生死锁，并解释之。

2.在采用请求分页存储管理的计算机系统中，运行-一个共有8页的作业，且该作业在主存中分配到4块主存空间，作业执行时访问页面顺序为7,0,1,2,3,0,4,3,2,3,6,7,3,1,5,7,6,2,6,7。请问用LRU页面调度算法时的缺页率是多少?并给出分析过程。

3.在UNIX文件系统中，盘块的分配与释放是借助于成组链接法中的空闲盘块栈进行的。假定某时刻空闲盘块栈如右图所示，此时要为某文件分配3个盘块。请说明分配过程，并图示分配完毕后有关数据及表目的更改情况。

4.某博物馆最多可容纳500人同时参观，只有一个出入口，该出入口一次仅允许一个人通过。当博物馆内少于500人时，参观者可进入，否则需在入口外等待。若把一个参观者看作一个进程，用P、V操作管理这些并发进程时，请回答如下问题:

(1)定义信号量，写出信号量的初值及其含义。

(2)插入应执行的P、V操作以保证进程能够正确地并发执行。