《2017年南京师范大学地理科学学院645C语言程序设计(含数据结构)考研题库.doc》由会员分享，可在线阅读，更多相关《2017年南京师范大学地理科学学院645C语言程序设计(含数据结构)考研题库.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年南京师范大学地理科学学院645C语言程序设计(含数据结构)考研题库一、选择题1 某计算机存储器按字节编址，主存地址空间大小为64MB ，现用4Mx8位的RAM 芯片组成32MB 的主 存储器，则存储器地址寄存器MAR 的位数至少是（ ）。A.22 位 B.23 位 C.25 位 D.26 位 【答案】D【解析】虽然实际的主存储器（RAM 区）只有32MB , 但不排除还有ROM 区，考虑到存储器扩展的需要， MAR 应保证能访问到整个主存地址空间。因为主存的地址空间大小为64MB , 所以MAR 的位数至少需要26位。 2 在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（
2、 ）。A. 机械特性 B. 功能特性 C. 过程特性 D. 电气特性 【答案】C 。【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性；机械特性：主要定义物理连接的边界点，即接插装置；电气特性：规定传输二进制位时，线路上信号的电压高低、阻抗匹配、传输速率和距离限制；功能特性：主要定义各条物理线路的功能；规程特性：主要定义各条物理线路的工作规程和时序关系。而从题干可以 分析描述事件先后顺序的就是规程，也就是过程特性，答案是C 。 3 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。A. 直接插入排序 B. 起泡排序 C. 简单选择排序 D. 快速排序 【答案】A【解
3、析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需趟排序，也即时间复杂度仍为而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即间复杂度为0（nlog2n ）n-1趟，比较的时间复杂度由 降至4 系统为某进程分配了4个页框，该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下
4、一页的页号为7，依据LRU 算法，应淘汰页的页号是（ ）。A.2 B.3 C.4 D.8【答案】B【解析】LRU 置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框，题中访问过程中页框的变化如下：序列：页框： 淘汰：3。 5 下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（ ）。A. 先来先服务 B. 高响应比优先 C. 时间片轮转D. 非抢占式短任务优先 【答案】B【解析】分析该题目可以看到，本题所提到的问题是涉及短任务调度也就是属于作业调度，因此首先排除时 间片轮转算法；因为作业调度算法中没有时间片轮转的算法。其次，因为问题提到短任务，则先来先服务的算法也可以排除了，它与
5、短任务无关。剩余高响应比优先算法和非抢占式短任务优先是哪一个? 我们可以通过分析得到，非抢占式短任务优先算法不能解决饥饿问题，因为当一个系统短任务源源不断到达是，长任务必然会得不到 调度，产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法，并以高响应比值优先调度。这样，无论短任务或长任务，均可以得到调度，而且，较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有尚响应比优先算法。 访问页号为7的页时，内存中存在的页的页号是：3、8、4和5，根据LRU 定义应淘汰的是6 有关二叉树下列说法正确的是（ ）。A_二叉树的度为2B. 棵二叉树的度可以小于2 C. 二叉树中至
6、少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2 【答案】B【解析】树的度=MAX（结点1的度，结点2的度，结点3的度，. ，结点n 的度）。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。 7 求整数阶乘的算法如下，其时间复杂度是（ ）。 A. B. C. D. 【答案】B 。【解析】设fact （n ）的运行时间函数是T （n ）。 该函数中语句的运行时间是0（1）, 语句的运行时间是法运算的时间。因此，当时， 当 即fact （n）的时间复杂度为 8 用邻接表存储图所用的空间大小（ ）。A. 与图的顶点数和边数都有关 B. 只与图的边数有关 C. 只与图的顶点数有关 D. 与边数的平方有关 【答案】A【解析】邻接表就是对图G 中的每个顶点Vi 建立一个单链表，第i 个单链表中的结点表示依附于顶点V i 的边，这个单链表就称为顶点Vi 的边表。因此邻接表既存储图的所有顶点，也存储顶点之间的边的信息。 时，则，其中O （1）为乘一、选择题考研试题
