2016年中国刑事警察学院计算机软件综合之数据结构考研复试题库

目录

2016年中国刑事警察学院计算机软件综合之数据结构考研复试题库（一） ............................. 2 2016年中国刑事警察学院计算机软件综合之数据结构考研复试题库（二） ........................... 12 2016年中国刑事警察学院计算机软件综合之数据结构考研复试题库（三） ........................... 20 2016年中国刑事警察学院计算机软件综合之数据结构考研复试题库（四） ........................... 30 2016年中国刑事警察学院计算机软件综合之数据结构考研复试题库（五） ........................... 38

2016年中国刑事警察学院计算机软件综合之数据结构考研复试题库（一）

说明：①本资料为VIP包过学员内部使用资料。

——————————————————————————————————————————

一、选择题

1． 有向带权图如题图所示，若采用迪杰斯特拉（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是（ ）。

题图有向带权图

A.d,e,f

B.e,d,f C.f,d,e D.f,e,d 答:C。

【解析】本题主要考查Dijkstra算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。

执行Dijkstra算法过程中各步的状态表，故后续目标顶点依次为f，d,e。

2． 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（ ）。

答:A

【解析】因为是用数组存储，这里所说的工作指针j相当于数组的下标，结点是存储一个值域和next域，next域就是存放下一个结点的下表，所以只要将next域中的值赋给j就可以实现j沿链移动。

3． 有关二叉树下列说法正确的是（ ）。

A_二叉树的度为2

B.—棵二叉树的度可以小于2 C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2 答:B

【解析】树的度=MAX（结点1的度，结点2的度，结点3的度，...，结点n的度）。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。

4． 数组中含有元素的个数（ ）。

A.55 B.45 C.36 D.16 答:B

【解析】该数组为三维数组。其个数为

5． 若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是（ ）。

A.在进程结束时能进行处理机调度 B.创建新进程后能进行处理机调度 C.在进程处于临界区时不能进行处理机调度

D.在系统调用完成并返回用户态时能进行处理机调度 答:C。

【解析】对于A、B、D显然是可以进行处理机调度的，对于C,当进程处于临界区时，只要不破坏临界资源的使用规则，是不会影响处理机调度的，比如，通常访问临界资源可能是慢速的，如果在进程访问打印机时，不能处理机调度，那么系统的性能将是非常低的。外设（如打印机）

几种不进行处理机调度的情况如下：①在处理机中断的过程中；②进程在操作系统内核程序临界区中；③其他需要完全屏蔽中断的原子操作过程中。

6． 设二维数组（即m行n列）按行存储在数组

在一维数组B中的下标为（ ）。

答:A 【解析】

前

的元素个数为

所以二维数组元素

在一维数组B

中的下标为

需要注意数组B的下标是从0开始，还是从1开始。

中，

则二维数组元素

7． 某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同，

把一个磁盘块读人缓冲区的时间为传送到用户区的时间是

CPU对一块数据进行分析的时间为

构下，读人并分析完该文件的时间分别是（ ）。

A. B. C. D. 答:B

【解析】这是一个简单的缓冲区的问题。由于缓冲区的访问是互斥的，所以对单一缓冲区，从磁盘写入和读 出到用户区的操作必须串行执行，也就是要保证互斥操作。而CPU对数据的分析与从用户区读数据也是需要互斥操作，但是CPU分析与从磁盘写入缓冲区的操作可以并行。从本题看，由于分析所用的时间小于从磁盘写入 缓冲区的时间，因此，CPU会空闲。单缓冲区的总时间=（磁盘写入缓冲区时间+缓冲区读出时间

）

处理最后一块数据的时

间

当采用双缓冲区时，每块缓冲区的操作也必须满足互斥操作，但是，

对两块缓冲区的操作却可以并行，所以，当第一个缓冲区写满以后，磁盘紧接着写另一个缓冲区，同时，前一个已经满了的缓冲区被读出到用户区，并立即进行CPU的数据分析。读出操作和数据分析必须互斥进行，故从时间上看，当数据被读出并分析后，恰好另一个缓冲区也写满了，可以立即进行读出数据到用户区并 进行数据分析。两块缓冲区交替进行读写，直到数据分析完毕，因此，总时间=（磁盘写入缓冲区时间）

读出最后一块数据时间+CPU分析最后一块数据时间=

8． 计算机算法指的是解决问题的步骤序列，它必须具备（ ）三个特性。

A.可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性 答:B

【解析】计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述，也就是解决问题的步骤序列。一个算法通常需要具备五大特性：有穷性；确定性；可执行性；输入一个算法有零个或多个输入；输出一个算法有零个或者多个输出。

9． 可以用（ ）定义一个完整的数据结构。

A.数据元素 B.数据对象 C.数据关系

将缓冲区的数据

，在单缓冲区和双缓冲区结

D抽象数据类型 答:D

【解析】抽象数据类型可以定义一个完整的数据结构。包括数据元素，数据元素之间的关系，以及可以进行的操作。

10．设有向图G= （V，E），顶点集能得到的不同遍历序列个数是（ ）。

A.2 B.3 C.4 D.5 答:D

【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可

能得到的不同遍历序列分别是

：

V={V0, VI，V2, V3}，边

集

若从顶点V0开始对图进行深度优先遍历，则可

二、填空题

11．在下面的程序段中，对X的赋值语句的时间复杂度为_____（表示为n的函数）。

答:1＋（1＋2）＋（1＋2＋3）＋" ＋（l＋2＋...＋n）=n（n＋1）（n＋2）/6，即

【解析】当i=l时，赋值语句就被执行了一次。当i=2时，赋值语句被执行了1＋2次。当i=3时，赋值语句被执行了1＋2＋3次。可以推出赋值语句总共被执行了1＋（1＋2）＋（1＋2＋3）＋…＋（l＋2＋...＋n）=n（n＋1）（n＋2）/6次。

12．对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。

答:集合；线性结构；树形结构；图状结构（网状结构）

13．有五个数据依次入栈：1，2,3,4,5。在各种出栈的序列中，以3,4先出栈的序列有_____。（3在4之前出栈）

答:3个

【解析】以3,4先出栈的序列有34521、34215、34251共3个。