2018年西安交通大学软件学院814计算机基础综合之数据结构考研仿真模拟五套题
● 摘要
目录
2018年西安交通大学软件学院814计算机基础综合之数据结构考研仿真模拟五套题（一） ... 2 2018年西安交通大学软件学院814计算机基础综合之数据结构考研仿真模拟五套题（二） . 11 2018年西安交通大学软件学院814计算机基础综合之数据结构考研仿真模拟五套题（三） . 21 2018年西安交通大学软件学院814计算机基础综合之数据结构考研仿真模拟五套题（四） . 33 2018年西安交通大学软件学院814计算机基础综合之数据结构考研仿真模拟五套题（五） . 43
一、单项选择题
1． 若某通信链路的数据传输速率为2400bps , 采用4相位调制, 则该链路的波特率是（ ）。
A.600波特
B.1200波特
C.4800波特
D.9600波特
【答案】B
【解析】注意无噪声下的码元速率极限值B 与信道带宽H 的关系:
特公式一无噪信道传输能力公式是
以得到波特率与数据传输速率的关系, 即, 而奈奎斯, N 为—个码元所取的离散值个数。从而可, 在本题中数据传输速率C=2400, N=4, 因此波特率是1200, 答案是B 。
2． 用哈希(散列) 方法处理冲突(碰撞) 时可能出现堆积(聚集) 现象, 下列选项中, 会受堆积现象直接影响的是（ ）
A. 存储效率
B. 数列函数
C. 装填(装载) 因子
D. 平均查找长度
【答案】D
【解析】哈希方法冲突会使在查找冲突的关键字时, 还要根据冲突处理办法多次比较关键字, 则直接影响了平均查找长度。
3． 下列关于银行家算法的叙述中, 正确的是（ ）
A. 银行家算法可以预防死锁
B. 当系统处于安全状态时, 系统中一定无死锁进程
C. 当系统处于不安全状态时, 系统中一定会出现死锁进程
D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件
【答案】B
【解析】银行家算法是避免死锁的方法。利用银行家算法, 系统处于安全状态时没有死锁进程, 故答案选B 。
4． 在双向链表指针P 的结点前插入一个指针q 的结点操作是（ ）。
A.p ﹣＞llink ＝q ；q ﹣＞Rlink ＝p ；p ﹣＞Llink ﹣＞Rlink ＝q ；q ﹣＞Llink ＝q ；
B.p ﹣＞llink ＝q ；p ﹣＞Llink ﹣＞Rlink ＝q ；q ﹣＞Rlink ＝p ；q ﹣＞Llink ＝p ﹣＞Llink ；
C.q ﹣＞Rlink ＝p ；q ﹣＞Llink ＝p ﹣＞L1ink ；p ﹣＞L1ink ﹣＞Rlink ＝q ；p ﹣＞Llink ＝q ；
D.q ﹣＞llink ＝p ﹣>llink；q ﹣＞Rlink ＝q ；p ﹣＞llink ＝q ；p ﹣＞llink ＝q ；
【答案】C
5． 图的BFS 生成树的树高比DFS 生成树的树高（ ）。
A. 小或相等
B. 小
C. 大或相等
D. 大
【答案】A
【解析】BFS 称作广度优先搜索，DFS 称作深度优先搜索。广度优先搜索类似与二叉树的层序遍历算法，深度优先搜索类似于树的先序遍历。因为深度优先搜索算法遵循的策略是尽可能的“深”地搜索一个图。所以图的BFS 生成树的树髙比DFS 生成树的树高小或者相等。
6． 某计算机采用微程序控制器, 共有32条指令, 公共的取指令微程序包含2条微程序, 各指令对应的微程序平均由4条微指令组成, 采用断定法(下址字段法) 确定下条微指令的地址, 则微指令中下址字段的位数至少是:（ ）
A.5
B.6
C.8
D.9
【答案】C 【解析】, ,
所以至少需要8位才能表示完130个地址。
7． 在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）
A.O(2n)
B.O(n)
C.O(n2)
D.O(log2n )
【答案】C
2【解析】两个循环嵌套，那么语句x :＝x+l:则被执行了n 次。
8． 主机甲和主机乙之间已建立了一个TCP 连接，TCP 最大段长度为1000字节，若主机甲的当前拥塞窗口为4000字节，在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的对第一个段的确认段，确认段中通告的接收窗口大小为2000字节，则此时主机甲还可以向主机乙发送的最大字节数是（ ）.
A.1000
B.2000
C.3000
D.4000
【答案】A
【解析】发送方的发送窗口的上限值应该取接收方窗口和拥塞窗口这两个值中较小的一个，于是此时发送方的发送窗口为min{4000，2000) ＝2000字节，由于发送方还没有收到第二个最大段的确认，所以此时主机甲还可以向主机乙发送的最大字节数为2000－1000＝1000字节，正确选项为A.
9． 设X 是树T 中的一个非根结点，B 是T 所对应的二叉树。在B 中，X 是其双亲的右孩子，下列结论正确的是（ ）。
A. 在树T 中，X 是其双亲的第一个孩子
B. 在树T 中，X 一定无右兄弟
C. 在树T 中，X 一定是叶结点
D. 在树T 中，X 一定有左兄弟
【答案】D
【解析】由树和二叉树的转换关系可知，X 一定有左兄弟，X 是其双亲的第二个孩子，不能确定在树T 中，X 是否有右兄弟，是否是叶结点。
10．哈希函数有一个共同的性质，即函数值应当以（ ）取其值域中的每个值。
A. 最大概率
B. 最小概率
C. 平均概率
D. 同等概率
【答案】D
二、填空题
11．一个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列