2017年江苏大学理学院851数据结构考研仿真模拟题
● 摘要
一、选择题
1． 已知一棵有2011个结点的树，其叶结点个数为116, 该树对应的二叉树中无右孩子的结点个数是（ ）。
A.115 B.116 C.1895 D.1896 【答案】D
【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点（因为一个非终端结点，另外，树根结点转至少有一个孩子结点，其最右边的孩子结点转换成二叉树后一定没有右孩子）
换成二叉树后也没有右孩子。题目中树的总结点数是2011，叶结点个数是116, 则非终端结点个数是2011-116=1895, 则该树对应的二叉树中 无右孩子的结点个数是1895+1=1896。
2． 某计算机的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，故Cache 有8组，按照上面的公式可以计算得到块，采用2路组相联映射方式（即每组2块）
Cache 的组号=4mod8=4。
3． 现在有一颗无重复关键字的平衡二叉树（A VL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）。
A. 根节点的度一定为2 B. 树中最小元素一定是叶节点 C. 最后插入的元素一定是叶节点 D. 树中最大元素一定是无左子树 【答案】D
【解析】二叉树的中序遍历定义是“若二叉树为空，则空操作；否则：①中序遍历左子树；②访问根节点；③中序遍历右子树”。A 项错误，当树中仅有一个或者两个结点时，根节点的度就可
能不为2；B 项错误，树中最小元素是中序遍历时最后访问的节点，当没有右子树时，最后访问的节点是根节点；C 项错误，当最后插入的元素破坏树的平衡后，树会进行调整，使其成为中间节点；D 项正确，由中序遍历的特点可知，左子树的值大于根节点，所以最大元素一定没有左子树。
4． float 型整数据常用IEEE754单精度浮点格式表示，假设两个float 型变量x 和y 分别在32为寄存器
和中，若
A. B. C. D.
且符号相同 且符号不同 且符号相同 且符号不同
则x 和y 之间的关系为：（ ）
【答案】A
【解析】两个数对应的IEEE754的标准形式为；
将IEEE754
单精度形式的二进制转化为浮点数公式为由于
的符号位都是1, 所以fl ，f2符号相同，而阶码上
值比f2大，而他们都是负数，所以所以选A
5． 二叉树在线索化后，仍不能有效求解的问题是（ ）。
A. 前序线索二叉树中求前序后继 B. 中序线索二叉树中求中序后继 C. 中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继 【答案】D
【解析】后序线索二叉树求后序后继要分3种情况，比较复杂，不是仅仅线索化后就能求解的，算法上还要要分情况讨论。
6． 已知循环队列存储在一维数组rear 的值分别是（ ）。
A.0, 0 B.0, n-1 C.n-1, 0 D.n-1, n-1
【答案】B
【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素，若初始时队列为空，
所以fl 的绝对
中，且队列非空时front 和rear 分别指向队头元素和
队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front 和
且要求第1 个进入队列的元素存储在A[0]处，则此时front 和rear 的值都为0。由于进队操作要执行（rear+1） % n，则初始 时front 的值为0、rear 的值为n-1。
7． 若线性表最常用的操作是存取第I 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（ ）。
A. 单链表 B. 双向链表 C. 单循环链表 D. 顺序表 【答案】D
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素。
8． 某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int 和short 型长度分别为32位和16位，并且数据按边界对齐存储。某C 语言程序段如下：
若record 变量的首地址为则地址中内容及record.c 的地址分别为（ ）。 A. B. C. D. 【答案】D 。
【解析】32位整数a 需要占4个字节，16位整数c 需要占2个字节，而字符数据b 占一个字节。a=273, 转换成十六进制是111H , 采用小端方式存放数据，地址0xC008中的内容为11H 。由于数据按边界对齐存储，地址
中存放a , 地址
中存放b , 地址
中空闲，
地址中存放c 。
9． 下列因素中，不会影响信道数据传输速率的是（ ）
A. 信噪比 B. 频率宽带 C. 调制速率 D. 信号传播速度 【答案】D
【解析】信道数据传输速率与信噪比、频率宽度、调制速率都有关。
相关内容
相关标签