2018年安徽农业大学信息与计算机学院829数据结构考研核心题库
● 摘要
一、单项选择题
1． 若某文件系统索引结点(inode)中有直接地址项和间接地址项, 则下列选项中, 与单个文件长度无关的因素是（ ）
A. 索引结点的总数
B. 间接地址索引的级数
C. 地址项的个数
D. 文件块大小
【答案】A
【解析】根据文件长度与索引结构的关系可知, 只有选项A 是与单个文件长度无关的。
2． 数据序列(8，9，10，4，5，6，20，1，2) 只能是下列排序算法中的（ ）的两趟排序后的结果。
A. 选择排序
B. 起泡排序
C. 插入排序
D. 堆排序
【答案】C
【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大值或者最小值。
3． 有n(n＞0) 个分支结点的满二叉树的深度是（ ）。
A.n 2﹣l
B.log 2(n＋1) ＋1
C.log 2(n＋1)
D.log 2(n—1)
【答案】C
【解析】满二叉树的结点总数＝分支的结点总数＋非分支的结点总数。由于此树为满二叉树，
所以非分支的结点总数为1，所以满二叉树共有n ＋1个结点，所以满二叉树的深度为log 2 (n＋1) 。
4． 若一个栈以向量 存储，初始栈顶指针top 为n+1，则下面X 入栈的正确操作是（ ）。
A.top :＝top ＋l ；V[top]:＝x
B.V[top]:＝x ；top :＝top ＋l
C.top :＝top ﹣l ；V[top]:＝x
D.V[top]:＝x ；top :＝top ﹣l
【答案】C
【解析】题中初始栈顶指针top 为n ＋1，而栈顶指针又位于最大下标以上，此时入栈应进行先减一操作。
5． 若某单处理器多进程系统中有多个就绪态进程, 则下列关于处理机调度的叙述中, 错误的是（ ）。
A. 在进程结束时能进行处理机调度
B. 创建新进程后能进行处理机调度
C. 在进程处于临界区时不能进行处理机调度
D. 在系统调用完成并返回用户态时能进行处理机调度
【答案】C 。
【解析】对于A 、B 、D 显然是可以进行处理机调度的, 对于C , 当进程处于临界区时, 只要不破坏临界资源的使用规则, 是不会影响处理机调度的, 比如, 通常访问临界资源可能是慢速的外设(如打印机) , 如果在进程访问打印机时, 不能处理机调度, 那么系统的性能将是非常低的。几种不进行处理机调度的情况如下:
①在处理机中断的过程中;
②进程在操作系统内核程序临界区中;
③其他需要完全屏蔽中断的原子操作过程中。
6． 数组通常具有的两种基本操作是（ ）。
A. 查找和修改
B. 查找和索引
C. 索引和修改
D. 建立和删除
【答案】A
【解析】数组中的元素是顺序存放的，通过下标可以很好地查找数组元素，同时通过对应的指针可以修改数组元素的值，因此数组通常具有的两种基本操作是查找和修改。根据数组的性质，数组通常具有的两种基本运算是排序和查找。
7． 下列关于虚拟存储的叙述中, 正确的是（ ）。
A. 虚拟存储只能基于连续分配技术
B. 虚拟存储只能基于非连续分配技术
C. 虚拟存储容量只受外存容量的限制
D. 虚拟存储容量只受内存容量的限制
【答案】D 。
【解析】所谓虚拟存储, 是指运行的进程不必全部装入内存, 只需要部分装入便可以开始运行的一种技术, 在运行过程中, 当所需要的代码部分不在内存时, 通过一种技术(例如缺页中断技术) , 将所需要的页面调入内存, 从而继续运行。虚拟存储可以在较少的内存中运行较大的程序。但是需要有较大的外存以及相应的软、硬件机制配合才能实现。虚拟存储器可以连续分配也可以非连续分配, 虚拟存储器和外存大小没有关系, 所以选项中的A , B , C 都是错误的, 所以答案是D 项。
8． 在一棵度为4的树T 中, 若有20个度为4的结点, 10个度为3的结点, 1个度为2的结点, 10个度为1的结点, 则树T 的叶结点个数是（ ）。
A.41
B.82
C.113
D.122
【答案】B
【解析】根据二叉树的性质3的推广公式:
式, 即
。
树T 的叶子结点的个数是82。
9．
将一个的三对角矩阵，
按行优先存入一维数组
A 6665(即该元素下标i ＝66，j ＝65) ，在B 数组中的位置K 为（ ）。
A.198
B.195
C.197
【答案】B
【解析】将对角矩阵a[i][j]存入b[k]，三对角矩阵压缩地址计算公式如下:k ＝2i ＋j ﹣2。
10．某计算机的Cache 共有16块，采用2路组相联映射方式(即每组2块). 每个主存块大小为32字节，按字节编址. 主存129号单元所在主存块应装入到的Cache 组号是（ ）.
A.0
B.2
C.4
D.6
【答案】C
【解析】首先根据主存地址计算所在的主存块号，然后根据组相联映射的映射关系K ＝ImodQ(K代表Cache 的组号，I 代表主存的块号，Q 代表Cache 的组数) 来计算Cache 的组号. 由于每个主存块大小为32字节，按字节编址，那么主存129号单元所在的主存块号是4，Cache 共有16块，采用2路组相联映射方式(即每组2块) ，故Cache 有8组，按照上面的公式可以计算得到Cache 的组号＝4mod8＝4.
可直接在将数据带入公中，A 中元素