2017年贵州大学计算机科学与技术学院831程序设计与数据结构考研冲刺密押题
● 摘要
一、选择题
1． 广义表
【答案】D
head 操作就是得到广义表中第一个的原子。【解析】
操作就是得到除第一个原子外剩下元
素构成的表。也就是toil 得到的元素需要在外层再加一个（ ）。
2． TCP/IP参考模型的网络层提供的是（ ）。
A. 无连接不可靠的数据报服务 B. 无连接可靠的数据报服务 C. 有连接不可靠的虚电路服务 D. 有连接可靠的虚电路服务 【答案】A
【解析】TCP/IP的网络层向上只提供简单灵活的、无链接的、尽最大努力交付的数据服务，因此答案是A 。
3． 设有一棵3阶B 树，如题图所示。删除关键字78得到一棵新B 树，其最右叶结点所含的关键字是（ ）。
则式子
的值为（ ）。
题图二叉树图
A.60
B.60, 62 C.62, 65 D.65
【答案】D 。
【解析】本题主要考查B 树删除操作。即被删关键字所在的结点中的关键字个数等于
而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于则需将其兄弟结点中最
小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字78得到一棵新B 树如下，其最右叶结点所含的关键字是65。
4． 假设某计算机按字编址，Cache 有4个行，Cache 和主存之间交换的块大小为1个字。若Cache 的内容初始为空，采用2路组相联映射方式和LRU 替换算法，当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4， 8时，命中Cache 的次数是（ ）。
A.1 B.2 C.3 D.4
【答案】C 。
【解析】Cache 有4个行，2路组相联，即Cache 被分成2组，每组2行。主存地址为0〜1、4〜5、8〜9 可映射到第0组Cache 中，主存地址为2〜3、6〜7可映射到第1组Cache 中。Cache 初始为空，采用LRU 替换算法，当访问主存的10个地址依次为0, 4，8, 2, 0, 6，8, 6, 4, 8时，命中Cache 的次数共有3次，分别发生在第7、8和10步时。
5． 对线性表进行折半查找时，要求线性表必须（ ）。
A. 以顺序方式存储B. 以顺序方式存储，且数据元素有序 C. 以链接方式存储D. 以链接方式存储，且数据元素有序 【答案】B
【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
6． 将一棵树t 转换为孩子兄弟链表表示的二叉树h ，则t 的后序遍历是h 的（ ）。
A. 前序遍历 B. 中序遍历 C. 后序遍历 【答案】B
【解析】树的后序遍历恰好对应于二叉树的中序遍历。
7． 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A ，并已知A 的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（ ）型调整以使其平衡
【答案】C
【解析】A 的平衡因子此时为-1，要使插入结点不平衡，必须插在右孩子的左子树上，A 平衡因子变成了-2，则需要进行两次旋转（先右旋后左旋）。
8． 若将关键字1，2, 3, 4, 5, 6, 7依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0的分支结点的个数是（ ）
A.0 B.1 C.2 D.3
【答案】D
【解析】将图中给定的关键字序列依次插入到平衡树中，构成的平衡树如下图所示，由图可知平衡因子为0的分支结点为3个叶子结点，故答案为D 。
9． 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A.257 B.258 C.384 D.385 【答案】C
【解析】由
：_
则
和
_
_可知
，
即
显然
384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个
性质：最后一个分支结点的序号为[768/2], 故非叶子结点数为384, 而叶子结点的个数为768-384=384。（[x]表示不大于x 的最大整数，比如[3.14] =3）。
10．进程P0和P1的共享变量定义及若进程P0和P1访问临界资源的类C 伪代码实现如下：
相关内容
相关标签