2017年武汉科技大学信息科学与工程学院856数据结构(C语言版)考研仿真模拟题
● 摘要
一、选择题
1． 求整数
阶乘的算法如下，其时间复杂度是（ ）。
A.
B. C. D.
【答案】B 。
【解析】设fact （n ）的运行时间函数是T （n ）。
该函数中语句①的运行时间是0（1）, 语句②的运行时间是法运算的时间。
因此，
当
时
，
当
时
，
则
，
其中O （1）为乘
即fact （n ）的时间复杂度为
2． 若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则X 的前驱为（ ）。
A.X 的双亲
B.X 的右子树中最左的结点 C.X 的左子树中最右的结点 D.X 的左子树中最右的叶结点 【答案】C
【解析】中序线索，只有把其左子树最右结点遍历完后，才会遍历自己，所以X 的前驱为X 的左子树中最右的结点。
3． 设文件索引节点中有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。
4． 若某文件系统索引结点（inode ）中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是（ ）
A. 索引结点的总数 B. 间接地址索引的级数 C. 地址项的个数 D. 文件块大小 【答案】A
【解析】根据文件长度与索引结构的关系可知，只有选项A 是与单个文件长度无关的。 5． 有个分支结点的满二叉树的深度是（ ）。
A.
B.
C.
D. 【答案】C
【解析】满二叉树的结点总数=分支的结点总数+非分支的结点总数。由于此树为满二叉树， 所以非分支的结点总数为1，所以满二叉树共有个结点，所以满二叉树的深度为
6． 如果本地域名服务无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为（ ）。
A.1条，1条 B.1条，多条 C. 多条，1条 D. 多条，多条 【答案】A
【解析】所谓递归查询方式就是：如果主机所询问的本地域名服务器不知道被查询域名的IP
地址，那么本地域名服务器就以DNS 客户的身份向其他服务器继续发出查询请求报文，而不是让该主机自行下一步的查询。所以主机只需向本地域名服务器发送一条域名请求，采用递归查询方法，本地域名服务器也只需向上一级的根域名服务器发送一条域名请求，然后依次递归。正确选项为A 。
7． 下列排序算法中，其中（ ）是稳定的。
A. 堆排序，起泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，起泡排序 【答案】D
8． 循环队列元素数是（ ）。
【答案】A
【解析】对于循环队列，需要深刻理解队头在队尾进行进队操作。
和队尾
的概念，在队头进行出队操作，
如果为负则元
可能为正也可能为负，为正时元素个数=
存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的
素的个数=所以统一的公式就是
9． 主机甲和主机乙间已建立一个TCP 连接，主机甲向主机乙发送了两个连续的TCP 段，分别包含300字节和500字节的有效载荷，第一个段的序列号为200, 主机乙正确接收到两个段后，发送给主机甲的确认序列号是（ ）。
A.500 B.700 C.800 D.1000
【答案】D
【解析】TCP 使用滑动窗口流控协议，窗口大小的单位是字节，本题中分别包含300字节和500字节的有效载荷，第一个段的序列号为200, 那么确认序列号为200+300+500=1000。
10．下列网络设备中，能够抑制广播风暴的是（ ）。
中继器
集线器
网桥
路由器 A.
仅
和 B.
仅
相关内容
相关标签