当前位置：问答库＞考研试题

二 O 一二年招收硕士研究生入学考试试题 考试科目及代码： 适用专业： 计算机软件技术基础 控制科学与工程 827 答题内容写在答题纸上，写在试卷或草稿纸上一律无效考完后试题随答题纸交回。 考试时间 3 小时，总分值 150 分。 一、选择题（下列四个选项只有一项正确，错选或多选不得分，每小题 2 分，共 44 分） 1. 下列选项不属于微机系统总线的是： （ ） A. 指令总线 B. 数据总线 C. 地址总线 D. 控制总线 2. 计算机软件分为系统软件和应用软件，下列选项不属于系统软件的是： （ ） A. 操作系统 B. 网络通信管理程序 C. 图形图像处理软件 D. 数据库管理软件 3. 下列关于算法的说法错误的是： （ ） A. 算法必须在有限步骤内正常结束。 B. 算法中的每一个步骤必须有确定含义。 C. 算法可以没有输入。 D. 算法可以没有输出。 4. 下列关于线性链表的叙述正确的是： （ ） A. 线性链表的长度是固定不变的。 B. 线性链表不需要一组连续的存储单元。 C. 线性链表所有元素的存储空间必须预先分配好。 D. 线性链表的元素物理结构是顺序存放的。 5. 一个栈的输入序列是 ABCDE，则栈的不可能的输出序列是： （ ） A. EDCBA B. ECDBA C. DECBA D. ABCDE 6. 将 nxn 的下三角矩阵 A[1, …, n][1, …, n]按“行序优先”存储在一维数组 C[1,…]中，则元 素 A[i][j]对应于数组 C 中的 （ ） A. j(j‐1)/2+i‐1 B. j(j‐1)/2+i C. i(i‐1)/2+j‐1 D. i(i‐1)/2+j 7. 下图所示的二叉树，如果采用中序遍历，则下列选项正确的是： （ ） 准考证号码： 姓名： 报考学科、专业： 密 封 线 内 不 要 写 题 第 1 页 共 5 页

A. ABCDEFGHIJ B. ABCDFEGHIJ C. DCFBEAHIGJ D. DFCEBIHJGA 8. 下图所示的一个有向图 G 的拓扑排序序列正确的是： （ ） A. ABCDEFG B. ACFBDGE C. GEDFBCA D. ACBFDEG 9. 如果哈希表的表长为 25，用除留余数法，即哈希函数为 H(Key) = Key Mod p，此时 p 的值应为： （ ） A. 23 B. 27 C. 15 D. 24 10. 堆排序算法在最坏的情况下，其算法复杂度为： （ ） 2 A. O(n) B. O(n ) C. O( ) B. O( ) 11. 下列软件中最接近计算机硬件的软件是： （ ） A. 应用软件 B. 编译软件 C. 系统实用软件 D. 操作系统软件 12. 实存储管理的特点是当用户作业要求调入内存时，若存储空间不够，一般采用覆盖 或（ ）作为内存扩充的手段。 （ ） A. 地址转换技术 B. 交换技术 C. 重定位技术 D. 虚拟内存技术 13. 在页长为 128 字长的分页系统中，以下 C 程序段产生的缺页中断次数为： （ ） int A[128][128]; for( j = 0; j < 128; j ++) for( i = 0; i < 128; i ++) A[i][j]=0; A. 128 B. 256 C. 8192 D. 16384 14. 下列选项不是进程间产生死锁的必要条件的是： （ ） A. 所涉及的资源是共享的； B. 进程在等待新资源时，继续占用已分配的资源； C. 一个进程占有的资源不能被别的进程强行抢占； D. 一个进程获得的资源同时被另一个进程所请求，从而形成一个进程的循环链。 第 2 页 共 5 页

15. Unix 操作系统中，创建子进程的 shell 命令是： （ A. wait B. exec C. fork D. creat 16. 对于数据模型，下面说法不正确的是 （ A. 概念模型是信息世界的建模工具 B. 关系模型是一种概念模型 C. 概念模型不涉及计算机的处理细节 D. ER 模型是一种概念模型 17. 下面关于数据库的视图（VIEW）说法正确的是： （ A. 视图是一种真实存在的关系 B. 视图只能从一个关系中建立 C. 视图以文件形式存放在外存中 D. 视图可以和其他关系一样进行操作 18. 规范化理论是为了解决关系数据库中的( )问题而引入的。 （ A. 插入异常、删除异常和数据冗余 B. 减少数据操作的复杂性 C. 提高查询速度 D. 保证数据的安全性和完整性 19. 下列选项用于碰撞检测的方法是： （ A. 令牌控制技术 B. CSMA/CD C. HDLC D. CDMA/CD 20. 下列协议属于 TCP/IP 网络结构中的传输层的是： （ A. HTTP B. SMTP C. TCP D. IP 21. 因特网中按组织机构划分的顶层域名表示商业组织的是： （ A. EDU B. ORG C. NET D. COM 22. 下面关于 OSI 参考模型的叙述错误的是： （ A. OSI 参考模型中的下四层是面向通信的。 B. OSI 参考模型会话层以上各层是面向应用的。 C. OSI 的物理层是指连接计算机的具体物理设备或传输介质。 D. OSI 各层协议实际上是各个对等层之间传输数据的各项规定。 二、填空题（每空 2 分，共 24 分） 1. 通常评价一个算法的优劣的标准为【1】和【2】 。 ） ） ） ） ） ） ） ） 2. 如果按行优先的方式存储一个 m×n 的二维数组 A，则 Aij 的地址 Loc(Aij)为【3】 。 3. 设一 AOE 网如图所示： 。 请写出该 AOE 网的关键路径： 【4】 第 3 页 共 5 页

4. 5. 6. 7. 8. 9. 目前计算机存储器一般分为高速缓冲存储器， 【5】和外部存储器三级。 操作系统的处理器管理又称为处理器调度，一般分为作业调度和【6】 。 数据库模型一般分为层次模型，网状模型和【7】 。 关系数据库中，具有唯一标识关系中元组的属性或最小属性组，称为该关系的【8】 。 常用的网络拓扑结构有【9】 ， 【10】 ，环形，网状及层次形几种。 OSI 网络参考模型从下到上依次划分为物理层、 【11】 、网络层、 【12】 、会话层、表示 层和应用层。 三、判断题（每小题 2 分，共 20 分） 1. 深度为 h 的二叉树中之多含有 个结点。 （ ） 2. 将一个元素插入到长度为 n 的顺序存储的线性表的第 i 个位置， 需要移动的元素个数 为 n‐i+1。 （ ） 3. 一个有向图 G 的弧的数量等于所有结点的度除以 2。 （ ） 4. 快速排序算法是一种稳定的排序算法。 （ ） 5. 相对于程序而言，进程是动态的、暂时的。 （ ） 6. 原语是机器指令的延伸，由若干条机器指令构成的程序段，在原语执行期间允许被 中断。 （ ） 7. 如果关系 R 上的两个属性集 X，Y 是 m‐m 关系，则 X，Y 间不存在函数 依赖关系。 （ ） 8. SQL 语言是结构化查询语言。 （ ） 9. 路由器工作在 OSI 参考模型的第 2 层——数据链路层。 （ ） 10. IP 地址 192.168.10.1 属于 B 类地址。 （ ） 四、 综合题（共 62 分） 1. 请分别为顺序存储线性表和线性链表设计相应的冒泡排序算法（升序） 。(12 分) 2. 给定一组权值 W={8, 13, 5, 6, 31, 11, 9, 10, 7},画出由此生成的哈夫曼树。 （10 分） 3. 设有 n 件体积分别为 的物品和一个能装载总体积为 T 的背包，要求从 n ， 件物品中挑选若干件物品，其体积之和恰好装满背包，即 其中 为入选物品的序号。设计算法求解。 （8 分） 4. 设有两个进程 A、B，它们各自的 P‐V 操作流程如下： （4 + 6 = 10 分） 进程 A 进程 B … … P(S1) P(S2) P(S2) P(S1) … … V(S2) V(S1) V(S1) V(S2) … … 第 4 页 共 5 页

1> 试分析 A，B 进程运行中是否会出现死锁？ 2> 若会产生死锁，在什么情况会出现死锁，如何改进？ 5. 有一用户程序共分为 6 页， 操作系统分配给该程序的页数为 4， 其执行时页面走向为 （5,2,1,4,6,5,4,3,6,1,5,2,4） 。试计算采用先进先出的页面更新算法时的缺页中断率， 并按顺序写出程序结束前内存中的页面队列存储的页面的页号。 （6 分） 6. 设有三个基本表,表的结构如下所示,请用 SQL 语句完成下列查询:（4+4+8 = 16 分） student: 学号 1 3 5 8 course: 课程号 1 2 3 score: 学号 1 3 5 5 8 1 8 3 课程号 1 1 2 1 2 2 1 2 成绩 90 85 78 89 70 84 67 80 课程名 C 语言 数据结构 数据库 教材 C 语言程序设计 数据结构——C 语言描述 数据库系统概论 姓名 王华 李彬 刘英 马奇 性别 女 男 女 男 民族 汉族 回族 回族 满族 班号 07001 07001 07002 07002 1> 查询 07001 班所有“回族”同学的学号，姓名，性别。 2> 将 “C 语言”这门课程的教材修改为“C 语言程序设计教程” 。 3> 查询 07002 班所有人的学号，姓名和“数据结构”课程的成绩，并按学号升序排 列。 第 5 页 共 5 页