2016年西南民族大学工程硕士(计算机技术)计算机导论之数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 在一个文件被用户进程首次打开的过程中，操作系统需做的是（ ）
A. 将文件内容读到内存中 B. 将文件控制块读到内存中 C. 修改文件控制块中的读写权限
D. 将文件的数据缓冲区首指针返回给用户进程 答:B
【解析】概念
2． 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
答:C
【解析】二叉排序树：左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。
3． 已知广义表用
答:C 【解析】
操作就是得到广义表中第一个的原子。
得
到得到e 。
4． 已知一棵有2011个结点的树，其叶结点个数为116, 该树对应的二叉树中无右孩子的结点个数是（ ）。
A.115 B.116 C.1895 D.1896 答:D
【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点（因为一个非终端结点，另外，树根结点转至少有一个孩子结点，其最右边的孩子结点转换成二叉树后一定没有右孩子）
换成二叉树后也没有右孩子。题目中树的总结点数是2011，叶结点个数是116, 则非终端结点个数
第 2 页，共 44 页
和数取出LS 中原子e 的运算是（ ）。
操作就是得到除第一个原子外剩下元得
到
得
到
素构成的表
。
是2011-116=1895, 则该树对应的二叉树中 无右孩子的结点个数是1895+1=1896。
5． 设被排序的结点序列共有N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为（ ）。
答:C
【解析】因为该序列中的结点已经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为的时间复杂度为
对于采用归并法，它是一种稳定的排序方法，它
对于一般的快速排序法，序列越接近有序，所需要的比较次数越多，
此时的时间复杂度为
6． 若路由器R 因为拥塞丢弃IP 分组，则此时R 可向发出该IP 分组的源主机发送的ICMP 报文件类型是（ ）。
A. 路由重定向 B. 目的不可达 C. 源抑制 D. 超时 答:C
【解析】当路由器或主机由于拥塞而丢弃数据报时，就向源点发送源点抑制报文，使源点知道把数据报的发送速率放慢，正确选项为C 。
7． 设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块的大小均为256字节，则可表示的单个文件最大长度是（ ）。
A.33KB B.519KB C.1057KB D.16513KB 答:C
【解析】4个地址项为直接地址索引，其指向的数据块大小4×256B=lKB，一级间接地址索引可以索引256/4=64个直接地址索引，故2个一级间接地址索引指向的数据块大小为2×64×256B=32KB，二级间接地址索引为256/4×256/4=4096个直接地址索引，故1个二级间接地址索引指向的数据块大小为4096×256B=1024KB, 共计1KB+32KB+1024KB=1057KB。
8． 用数组r 存储静态链表，结点的next 域指向后继，工作指针j 指向链中结点，使j 沿链移动的操作为（ ）。
答:A
第 3 页，共 44 页
【解析】因为是用数组存储，这里所说的工作指针j 相当于数组的下标，结点是存储一个值域和next 域，next 域就是存放下一个结点的下表，所以只要将next 域中的值赋给j 就可以实现j 沿链移动。
9． 下列介质访问控制方法中，可能发生冲突的是（ ）
A.CDMA B.CSMA C.TDM AC D.FDMA 答:B
【解析】介质访向控制协议中能够发生冲突的是CSMA 协议，答案为B 。
10．现有容量为10GB 的磁盘分区，磁盘空间以簇（cluster ）为单位进行分配，簇的大小为4KB , 若采用位图法管理该分区的空闲空间，即用一位（bit ）标识一个簇是否被分配，则存放该位图所需簇的个数为（ ）
A.80 B.320 C.80K D.320K 答:A
【解析】磁盘的簇的个数为：
而一个簇的位示图能管理的簇的个数为：所以需要簇的个数为
个
二、填空题
11．以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
答:（1）（2）
链表未到尾就一直进行
将当前结点作为头结点后的第一元素结点插入
12．空格串是指_____，其长度等于_____。
答:由空格字符（
值32）所组成的字符串；空格个数
13．无用单元是指_____，例_____
答:用户不再使用而系统没有回收的结构和变量；
第 4 页，共 44 页