2003-2016年南京航空航天大学829计算机专业基础考研真题及答案解析 汇编

科目代码：829科目名称：计算机专业基础 第1页 共4页 南京航空航天大学2013年硕士研究生入学考试初试试题󰄏A卷󰄐科目代码829 科目名称计算机专业基础 满分150 分注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！（一、数据结构部分 50分） 1.(1)（2分）推导二叉树的性质3：度为2的结点数与度为0的结点数的关系。 (2)（3分）推导二叉树的性质4：求解N个结点完全二叉树的高度。 (3)（5分））将关键字序列（75，24， 8，10，28，64，16，35）存储在长度为10的哈希表中，使用哈希函数H(key) = Key % 10，并采用二次探测再散列法解决冲突，说明关键字存储位置的计算方法，画出哈希表示意图。 2.（10分）试用Dijkstra算法，求下图中从V1到其余各顶点的最短路径，写出算法过程中每一步的状态。 3.（10分）设稀疏矩阵用三元组顺序表存储，用下面例子说明快速转置算法的执行过程。 A5×6=((1,3,8),(1,5,68),(3,1,12),(3,4,52),(3,5,3),(4,1,45),(5,1,26)) 4．（10分）已知有两个带头结点的单链表A和B，元素值递增有序，编写函数，调整删减A链表，使A链表结点的元素值为A、B的交集，并成为一个递减有序的单链表。要求先给出算法思想，再写出相应代码。 5.（10分）编写函数，用非递归方法，求二叉链表表示的二叉树T的高度。要求先给出算法思想，再写出相应代码。 （二、操作系统部分 50分） 1.简答题（20分，每题5分） （1）为什么要引入线程，线程和进程有何区别？ V2V4 V5 V6 V1 V31231377516

科目代码：829科目名称：计算机专业基础 第2页 共4页 （2） 什么是通道，通道经常采用如图所示的交叉连接，为什么？ 通道1存储器控制器1控制器2通道2I/O设备1I/O设备2I/O设备3I/O设备4 （3）简述操作系统引入缓冲的原因？ （4）何谓文件的物理结构，可分为哪几类，有何优缺点？ 2．(10分)假设有个南北向的胡同很窄，仅能容同方向的人顺序走过，相对方向的两个人则无法通过。现在胡同南北入口都有过路人。现把每个过路人当成一个进程，用P,V操作实现管理。 3. (7分)设系统有五个进程{P0，P1，P2，P3，P4}和四类资源{A，B，C，D}各种资源的数量分别为2，1，0，0，在T0时刻资源分配情况如下表： 资源 进程 最大资源需求 A B C D 当前已分配到的资源 A B C D P0 0 0 1 2 0 0 1 2 P1 2 7 5 0 2 0 0 0 P2 6 6 5 6 0 0 3 4 P3 4 3 5 6 2 3 5 4 P4 0 6 5 2 0 3 3 2 （1）当前系统是否是安全的？为什么？ （2）假定此时P2发出请求向量为Request(0，1，0，0)，系统可否分配给它？为什么？4. (7分)进程某时刻的页表如下图所示： 页号 标志 主存块号 0 1 4 1 1 8 2 0 3 1 2 4 0 5 1 0 其中的数字为十进制，页号、块号都以0开始，页的大小为2K字节，标志为1是在内存，

科目名称：计算机专业基础 第1页 共5页 南京航空航天大学 2015年硕士研究生入学考试初试试题󰄏 A卷󰄐 科目代码: 829 科目名称: 计算机专业基础 满分: 150 分 注意: ①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！ 数据结构部分（50分） 1．（10分）已知带权图如下所示，用Prim算法从顶点2开始产生最小生成树，说明算法思想，并给出求解所需的数据结构和每一步执行过程的相关数据变化。 2．（10分）已知输入数据序列为 (68, 40, 25, 21, 33, 12, 58, 51, 16,36)，给出建立3阶B-树示意图，再给出删除51，16后的B-树。 3．（10分））解释希尔排序的算法思想。对以下的数据序列，给出希尔排序过程的示意图。(46,8,36,50,6,24,18,78,12,10) 4．（10分）设一个带头结点的单链表L，数据元素为整数，编写函数，通过调整该链表的结点指针，对该链表进行简单选择排序（元素值从小到大）。先给出算法思想，再写相应代码。 5.（10分）设二叉树T，用二叉链表结构存储。编写函数，输出最长一枝（根到叶子）上的所有结点值。要求先给出算法思想，再写出相应代码。 操作系统部分（50分） 1.（15分）文件系统是操作系统的主要功能之一，请设计一个文件系统，需给出以下信息：（1）给出描述文件的数据结构（即文件控制块）和目录结构；（2分） （2）以索引节点为文件系统的物理文件组织结构，图示索引节点结构，说明其优点；（3分） V4 V2V6V3V5 V1 2 15 4 5 8 3 6 6 4

科目代码：829科目名称：计算机专业基础 第1页 共6页 南京航空航天大学 2017年硕士研究生入学考试初试试题（ A卷 ） 科目代码: 829 满分: 150 分 科目名称: 计算机专业基础 注意: ①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！ 数据结构部分（50分） 1．（10分）为一个家谱管理程序设计一种数据结构，以一个四代人，11个家庭成员为例，（A有3个孩子A1、A2、A3；A1有2个孩子A11、A12；A2无子，A3有3个孩子A31、A32、A33；A11有1个孩子A111；A32有1个孩子A321；其余尚无子），画出家谱示意图，给出所设计的存储结构示意图，并给出在该存储结构上输出第k代所有人员的算法思想。 2．（10分）已知输入数据序列为 (58,68,42,10,88,32,70,52,55,46 )，给出建立3阶B-树示意图，再给出删除55，70后的B-树。 3．（10分）试用Dijkstra算法，求下图中从V1到其余各顶点的最短路径，给出实现算法所用的数据结构和求解过程中每一步的状态。 4．（10分）设A、B为递减有序（元素值为整型）的单链表，编写函数，利用原结点将它们合并成一个递增有序的单链表，相同元素值只保留一个结点。先给出算法思想，再写出相应代码。 5.（10分）设有n个学生成绩（0-100整数）的顺序结构线性表L，编写函数，将该线性表中调整为成绩及格（大于等于60）在不及格之前，要求T(n)=O(n), S(n)=O(1)。先给出算法思想，再写出相应代码。

软件评测师上午基础知识考试选择题专项强化真题试卷6 (题后含答案及解析)

题型有：1.

1． 根据ANSI/IEEE829标准，以下(37)属于《测试程序说明》中程序步骤的内容。 ①启动 ②目的 ③日志 ④设置

A．①、②、③

B．①、③、④

C．②、③

D．①、②、③、④

正确答案：B

解析：本题考查程序步骤的概念。 根据ANSI/IEEE829标准，《测试程序说明》中程序步骤包括的内容举例如下。 .日志：测试员按测试要求记录程序执行过程，所有必须填写的项都必须填写，包括问题的记录。 .设置：测试者必须安装Windows 98的干净副本，使用测试工具Tool-A和 Tool-B等。 .启动：启动Windows 98，单击“开始”按钮，选择程序→附件→计算器。 .程序：用键盘输入每个测试用例并比较结果。 .衡量标准：……。

2． (41)不是易用性测试包括的内容。

A．安装测试

B．界面测试

C．菜单测试

D．文档测试

正确答案：D

解析：本题考查易用性测试的概念。 易用性测试包括： .安装测试。 .功能易用性测试。 .界面测试。 .辅助系统测试。

3． 以下所示程序控制流程图中有(59)条线性无关的基本路径。

A．1

B．2

C．3

D．4

正确答案：C

解析：本题考查白盒测试中测试用例的设计方法——基本路径法。 线性无关的基本路径计算方法如下。 线性无关的基本路径即是控制流图中的圈复杂度，圈复杂度又称为环路复杂性 V(G)，其计算方法包括： .控制流程图中的区域数。 .条边数-结点数+2。 .判定数+1。

4． 假设A、B为布尔变量，对于逻辑表达式(A&&B)，至少需要(63)个测试用例才能完成MCDC覆盖。

A．4

B．3

C．2

D．1

正确答案：B

解析：本题考查白盒测试中测试用例的设计方法——修正条件判定覆盖法。