《2016年昆明理工大学理学院J012数据结构与算法分析之数据结构(同等学力加试)复试笔试最后押题五套卷.doc》由会员分享，可在线阅读，更多相关《2016年昆明理工大学理学院J012数据结构与算法分析之数据结构(同等学力加试)复试笔试最后押题五套卷.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2016年昆明理工大学理学院J012数据结构与算法分析之数据结构(同等学力加试)复试笔试最后押题五套卷一、选择题1 对于循环队列（ ）。A. 无法判断队列是否为空B. 无法判断队列是否为满C. 队列不可能满D. 以上说法都不是答:D【解析】循环队列也会出现队列满的情况，并且循环队列也可以判断是否为空或满。至少可以通过两种方法进行判断：另设一个布尔变量来区别队列是空还是满；队满时，（rear+1）=font。 2 有六个元素6, 5, 4, 3, 2, 1顺序入栈，下列不是合法的出栈序列的是（ ）。A.543612B.453126C.346521D.234156答:C【解析】根据栈的后进先出的特
2、点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出找。 3 关键路径是AOE 网中（ ）。A. 从始点到终点的最短路径B. 从始点到终点的最长路径C. 从始点到终点的边数最多的路径D. 从始点到终点的边数最少的路径答:B【解析】在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度（这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目）。路径长度最长的路径称作关键路径（critical path）。 4 用不带头结点的单链
3、表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）。A. 仅修改队头指针B. 仅修改队尾指针C. 队头、队尾指针都可能要修改D. 队头、队尾指针都要修改答:C【解析】用不带头结点的单链表存储队列，一般删除操作仅修改队头指针，但当队列中只有一个结点时，进行删除操作要将队头、队尾指针都修改成NULL 。 5 下列选项中，不可能是快速排序第2趟排序结果的是（ ）A.2, 3, 5, 4, 6, 7, 9B.2, 7, 5, 6, 4, 3, 9C.3, 2, 5, 4, 7, 6, 9D.4, 2, 3, 5, 7, 6, 9答:C【解析】对于快速排序，每一趟都会使一
4、个元素位于有序时的位置，而有序序列为2, 3, 4, 5, 6, 7, 9, 与C 进行对比，只有9位于它有序的时候的位置，显然不是第二趟快速排序的结果 6 n 个顶点的无向图的邻接表最多有（ ）个表结点。A.IT B.n （n-l ） C.n （n+l） D.n （n-l ）/2答:B【解析】当n 个顶点构成的无向图是无向完全图时，则每一个结点都会和其余的n-1个结点连接，从而会产生n （n-l ）个表结点。 7 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。 答:B【解析】根据输入序列和输出序列可知，输入序列全部进栈，然后再出栈。从中可以看出，push 的数目始终大于等于p
5、op 的数目。 8 下面关于串的叙述中，不正确的是（ ）。A. 串是字符的有限序列B. 空串是由空格构成的串C. 模式匹配是串的一种重要运算D. 串既可以采用顺序存储，也可以采用链式存储答:B【解析】空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。 9 下列选项中，导致创建新进程的操作是（ ）。 用户登录成功 设备分配 启动程序执行A. 仅和B. 仅和C. 仅和D.答:C【解析】进程创建是需要填写PCB 表的，其中唯一不需要的是II 。考察一个进程创建的过程是这样的：当进程被创建，可以是用户创建，例如双击相关图标；也可以由父进程创建，例如lock （
6、 ）时，操作系统首先到PCB 表区搜索空闲的表格，若无则直接拒绝创建进程，若有则填，许多操写PCB 表创建进程。通常填写PCB 表的过程有一段时间（主要涉及资源分配需要协调），也有的操作系统不设这个中间状态。此时操作系作系统为此设立了一个中间状态称为“初始化”统填写进程ID 号、处理机参数、进程参数（状态、特权、优先级）、分配内存（若是虚拟存储就分配虚拟地址）、映射文件等，一切就绪，将控制权交给系统进行下一步调度。设备分配可能引起进程状态的改变，但不会创建新进程，用户登录成功和启动程序执行都会创建新的进程，所以本题答案为C 。 10串是一种特殊的线性表，其特殊性体现在（ ）。A. 数据元素是一个字符B. 可以顺序存储C. 数据元素可以是多个字符D. 可以链接存储答:A和 二、填空题11设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f （m , n ）为这种表示方式的数目。例f （5, 3）=5，有5种表示方式：32, 311，221，2111, 11111。以下是该函数的程序段，请将未完成的部分填入，使之完整。 一、选择题考研试题
