真题
安 徽 大 学
2017年招收攻读硕士研究生入学考试试题
计算机专业
（注：所有答案必须写在答题纸上，写在试题或草稿纸上一律无效）
一、选择题
1、（）是非线性结构。
A.队列
B.栈
C.二叉树
D.线性表
2、出队序列式（）[入队为1234]。
A.4321
B.1234
C.1432
D.3241
3、a*b*（c+d）的前缀（）。
A.abcd+**
B ab*cd+*
C *+*abcd
D **ab+cd
4、非空循环单链表head的尾结点*p满足（）。
A p->next==null
B p==null
C p->next=head
D p==head
5、高为h的二叉树只有度为0和2的结点，此二叉树的结点数至少为（）。
A 2h
B 2h+1
C 2h-1
D h+1
6、6个顶点的无向图至少有（）条边能确保为连通图。
A 5
B 6
C 7
D 8
7、排序算法平均时间不是O（nlogn)的是（）。
A快排
B堆排
C基排
D归排
8、硬件用I/O设备时通常采用（）。
A 物理设备名
B 逻辑设备名
C 虚拟设备名
D 设备牌号
9、抖动指（）。
背定义
10、（）是防止文件被破坏。
A 文件保护
B 文件加密
C 文件保存
D 文件保密
11、I/O设备与存储设备的数据交换不经过CPU来完成，方式是（）。
A 程序查询
B 中断
C DMA方式
D 无条件存储方式
12、快表的目的（）。
A 提高地址查找的命中率
B 提高地址变换速度
C 淘汰不用的页
D 增加页表的容量
13、硬件采用了中断和通道技术，使得（）。
A cpu与外设能并行工作
B cpu与外设能紧密结合
C cpu速度提高
D 外设速度提高
14、死锁避免策略是（）。
A银行家算法
B检测
C资源有序分配
D资源分配图简化
15、虚拟存储技术是（）。
A补充内存物理空间的技术
B补充相对地址空间的技术
C扩充外存空间的技术
D扩充输入输出缓冲区的技术
二、填空题
1、____和____称为非线性结构。
2、双链表中，每个结点有2个指针域，1个指向____，1个指向____。
3、深度为k、结点数为n的完全二叉树，所有结点度数总和是____，n的值为____。
4、不带头结点的单链表head为空的条件是____。
5、长为n的单链表中，在表头插一个结点的时间复杂度是____，在表尾插得时间复杂度是____。
6、5个结点7个边的有向图和无向图，邻接表中边结点数分别为____和____。
7、操作系统的基本特征有____ ____ ____ ____。
8、多道程序环境下，处于同一个系统中各进程间的制约关系主要有____ ____。
9、时间片用完而被暂停，该进程状态转为____；因为发生某事件而不被继续运行，进程状态转变为____；就绪状态的进程被调度，转为____。
三、简答题
1、在单链表的第一个结点前插入新结点的算法。
2、 深度遍历，广度遍历。
3、ABCDEF权值分别为（5，22，27，15，17，13），构造哈夫曼树，要求左孩子结点值大于右孩子结点值。
4、分页虚拟存储管理，引用顺序：7，1，2，0，3，0，4，2，3，0，3，2，7，0，1。4个主存块，FIFO，LRU各产生多少次缺页中断。
5、磁盘文件空间有200块，字长32位（标号从1开始）问：
（1）位示图需带上字
（2）第2个字地2位对应的块号
（3）110号块的位示图位置。
四、应用题
1、迪杰斯特拉求最短路径，该图的邻接矩阵省略（把资料书上的题目做熟，这题的难度不大）。
2、分别用普里姆和克鲁斯卡构造最小生成树。
3、（287，110，083，789，324，505，008）用链式基数排序。
4、PA,PB,PC信号量（具体的忘记了）。
5、银行家算法。
6、磁盘调度算法：FCFS，SSTF，Scan的调度顺序和磁头移动的总距离。（86，147，9，177，94，150，102，175，130），磁头从140移到143，并完成了读写。
备注：安大专业课试卷为A4纸正反印刷
答题纸为A3纸3张
安小研
千千万万的公众号中
能被你识别都是缘分
微信号：FL-anxiaoyan
联系客服
