资源描述：
《中国科学技术大学822计算机软件技术基础历年考研真题汇编》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、目录2014年屮国科学技术大学822计算机软件技术基础考研真题22013年中国科学技术大学822计算机软件技术基础考研真题52012年中国科学技术大学822计算机软件技术基础考研真题82009年中国科学技术大学822计算机软件技术基础考研真题及详解102008年中国科学技术大学822计算机软件技术基础考研真题及详解272014年中国科学技术大学822计算机软件技术基础考研真题2014年硕士学位研究生入学考试试题(计算机软件技术基础)所有试题答案写在答题纸上，答案写在试卷上无效□需使用计算器■不使用计舜器-、简
2、答题(每小题6分，共30分)1.己知A为稀疏矩阵，试从空间和时间的角度，比较分别釆用二维数组和三元组表两种存储结构來计算的优缺点。2・引入假脱机操作功能后，操作系统单位时间内处理的作业数是否可以增加？为什么？每个作业的周转时间是否会发生变化？为什么？3.请阐述文件系统与数拥库系统之间的区别和联系。4.OSI模型由低到高有哪几层，每层的主要作用是什么？5.什么是面向对纵方法，其具备哪些优点？二、应用题(每小题15分，共90分)1.假设以R和C分别表示入栈和出栈操作，可以使用一个栈操作序列來完成一系列元素的输入和
3、输出。(1)请给出判别栈操作序列是否合法的一般性规则。(2)对于相同的元素集合，两个不同的合法输入元素序列是否可以得到相同的输出元索序列？如能得到，请举例说明，并给出相应的栈操作序列。2.(1)请证明由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。(2)设一棵二叉树的前序序列为ABDGECFH,中序序列为DGBEAFIIC,请画出该二叉树。(3)如果给出了一个二叉树结点的前序序列和后序序列，能否构造出此二叉树?如果可以，请证明。如果不可以，请给出反例。1.给定一组关键字Jan,Feb,Mar,Apr,M
4、ay,Jun,Jul,Aug,Sep,Oct,Nov,Dec,设定哈希函数H(K)=[i/2],其中i为关键字K中第一个字母在字母表中的序号，[x]表示取小于等于x的最大整数，试用以下两种冲突处理方法构造哈希表，并分别求岀等槪率查找情况下查找成功的平均查找氏度。(I)线性探测再散列法(散列地址空间为0-16)(2)链地址法4・使用快速排序法对关键字为卜7这7个元素进行排序，请问:(1)在最好情况下需进行多少次比较？请说明理由。(2)请给出一个眾好悄况下的初始序列实例。(3)在城坏借况下需进行多少次比较？请说明
5、理由。(4)请给出一个最坏情况下的初始序列实例。5.某操作系统存储器采用分页管理，某作业代码长度为320字，其在存储器中的页表结构如下，每页长为32字：页号0123456789页架号6432000000状态1111000000现有三个八进制逻辑地址:101,204,576,请将它们分别转换为相应的物理地址，如能转换，请给出转换过程，如不能转换，请说明原因。(1)请说明E・R图表达的概念。(2)请将E・R图的实体联系模型转换为关系模型。(3)请说明各个关系的主键。三、算法题（每题15分，共30分）1.设L1与L
6、2分别为两个单链表的头结点地址指针，两个表中的数据结点存放的均为单字母。请设计一个算法，在L1中找到与L2数据相同的连续结点，并将这些节点的顺序进行倒置。（主要步骤需给出注释）2・有一个可以装D1和D2两种物品的仓库，D1和D2的最大容量均为N,要求仓库中D1和D2两种物品的数量满足如下关系：-MWD1数量一D2数量WN其中M和N均为正幣数。此外，还有一个进程消费D1和D2,每次取走1个D1和1个D2來组装成D3。请使用信号量和PV操作來描述DI、D2的入库过程和D3的生产过程。2013年中国科学技术大学82
7、2计算机软件技术基础考研真题屮国科席枝*丈哮2013年硕士学位研究生入学考试试题（计算机软件技术基础）所有试题答案写在答題纸上，答案写在试卷上无效□需使用计算器■不使用计算器一.简答题（每小题6分，共30分）1.在单向链表、单循环链衷和双向链农中，若仅知道指针p指向某结点，不知道头指针，能否将该结点从相应的链表中删去，如果可以，请给出时间复杂度，并简述理由。2.“系统调用和库函数都是操作系统与用户程序之间的接口”，此段描述是否正确，请简述理由。3•什么是E・R图，如何表示E・R图？1.请简述A.B、C三类IP
8、地址的结构，并给出三类地址理论上允许的最大网络数和最大网内主机数。2.软件丿I•发过程中设计测试方案的任务是什么，其中眾困难的问题是什么?二、应用题（每小题15分，共90分）10031.设对称矩阵人=:〔002002000550若将力中包括主对角线在内的下三角元素按照列优先的顺序压缩到数组S中，请画出数组S,并给出使用4中任一元素的行下标i和列下标；（!
