2018年北京交通大学计算机与信息技术学院926软件工程理论与技术之数据结构考研核心题库
● 摘要
一、判断题
1． 深度为k 的二叉树中结点总数小于等于2k ﹣l 。（ ）
【答案】 √
【解析】深度为K 的二叉树，当结点数最多时为满二叉树，此时结点数为2k ﹣l 。
2． 两个长度不相同的串有可能相等。（ ）
【答案】 ×
【解析】两个字符串相等，只有当两个字符串的长度相等，并且各个对应位置的字符相等才相等。
3． 数组不适合作为任何二叉树的存储结构。（ ）
【答案】 ×
【解析】对于完全二叉树，因为其n 个结点的位置已经固定，所以用一维数组作为存储结构是高效率的(存储密度大) 。
4． 用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。（ ）
【答案】×
【解析】单链表不能使用折半查找方法。折半查找主要用于数据元素有序且存储方式为顺序存储的表。
5． 树形结构中元素之间存在一对多的关系。（ ）
【答案】√
【解析】树形结构是非线性结构，存在一对多的关系。
6． 在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）
【答案】√
【解析】堆排序:基本思想先将原始序列构造成一个堆(初始堆) ，使其n 个元素的最大(小) 值处于序列的第 —个位置；然后交换序列第一个元素与最后一个元素的位置。
二、单项选择题
7． 设置当前工作目录的主要目的是（ ）.
A. 节省外存空间
B. 节省内存空间
C. 加快文件的检索速度
D. 加快文件的读/写速度
【答案】C
【解析】工作目录只是指出了当前操作的默认目录，使得在每次访问的时候不需要由根目录一层一层地解析，在文件路径比较长时，可以节省许多解析的时间，从而加快了文件的检索速度.
8． 下列关于最小生成树的叙述中, 正确的是（ ）。
Ⅰ. 最小生成树的代价唯一
Ⅱ. 所有权值最小的边一定会出现在所有的最小生成树中
Ⅲ. 使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同
IV. 使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树总不相同
A. 仅Ⅰ
B. 仅Ⅱ
C. 仅Ⅰ、Ⅲ
D. 仅Ⅱ、Ⅳ
【答案】A 。
【解析】当图中存在相同权值的边时, 其最小生成树可能是不唯一的, 但最小生成树的代价一定是相同的, 所以说法Ⅰ正确。从n 个顶点的连通图中选取n-1条权值最小的边可能构成回路, 所以说法Ⅱ错误。
当某个顶点有权值相同的边, 使用普里姆(Prim)算法从不同顶点开始得到的最小生成树并不一定相同, 所以说法Ⅲ错误。当最小生成树不唯一时, 使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树可能相同, 也可能不同, 所以说法Ⅳ错误。由此可得出正确答案。
9． 若一个用户进程通过read 系统调用读取一个磁盘文件中的数据, 则下列关于此过程的叙述中, 正确的是（ ）。
Ⅰ. 若该文件的数据不在内存, 则该进程进入睡眠等待状态;
Ⅱ. 请求read 系统调用会导致CPU 从用户态切换到核心态;
Ⅲ.read 系统调用的参数应包含文件的名称
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
【答案】A
【解析】对于Ⅰ, 当所读文件的数据不再内存时, 产生中断(缺页中断、缺段中断) , 原进程进入睡眠等待状态(阻塞状态) , 直到所需数据从外村调入内存后, 将该进程唤醒, 使其变为就绪状态。对于Ⅱ, read 系统调用cpu 将从用户态切换到核心态, 从而获取操作系统提供的服务。对于Ⅲ, 在操作
Open 系统调用的参数需要包含文件的系统中, 要读一个文件首先要open 系统调用将该文件打开。
路径名与文件名, 而read 系统调用只需使用open 返回的文件描述符, 并不使用文件名作为参数。Read 系统调用要求用户提供三个输入参数:
①文件描述符; ②buf 缓冲区首址; ③传送的字节数n 。
read 系统调用的功能是试图从fd 所指示的文件中读入n 个字节的数据, 并将它们送至由指针buf 所指示的缓冲区中。
10．下列哪一种图的邻接矩阵是对称矩阵？（ ）
A. 有向图
B. 无向图
C.AOV 网
D.AOE 网
【答案】B
【解析】邻接矩阵存储，就是用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间关系的二维数组称为邻接矩阵。因为无向图中边是没有方向的，
所以
，所以无向图的邻接矩阵是对称矩阵。
11．用户在删除某文件的过程中, 操作系统不可能执行是（ ）
A. 删除此文件所在的目录
B. 删除与此文件关联的目录项
C. 删除与此文件对应的控制块
D. 释放与此文件关联的内存级冲区
【答案】A
【解析】删除文件不需要删除文件所在的目录, 而文件的关联目录项和文件控制块需要随着文件一同删除, 同时释放文件的关联缓冲区。
12．对线性表进行折半查找时，要求线性表必须（ ）。
A. 以顺序方式存储
B. 以顺序方式存储，且数据元素有序
C. 以链接方式存储
D. 以链接方式存储，且数据元素有序
【答案】B
【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是
相关内容
相关标签