2017年延安大学数学与计算机科学学院812数据结构与程序设计考研强化模拟题
● 摘要
一、选择题
1． 使用浏览器访问某大学Web 网站主页时，不可能使用的协议是（ ）
A.PPP B.ARP C.UDP D.SMTP 【答案】D 【解析】SMTP 是简单邮件传输协议，访问主页时并不涉及邮件相关协议。
2． 以下数据结构中，（ ）是非线性数据结构。
A. 树 B. 字符串 C. 队 D. 栈 【答案】A
【解析】非线性结构是指存在一对多或者多对一的关系。常见的非线性结构有树结构和图结构。
3． 某计算机处理器主频为50MHz ，采用定时查询方式控制设备A 的I/0, 查询程序运行一次所用的时钟 周期数至少为500。在设备A 工作期间，为保证数据不丢失，每秒需对其查询至少200次，则CPU 用于设备A 的I/0的时间占整个CPU 时间的百分比至少是（ ）。
A.0.02% B.0.05% C.0.20% D.0.50% 【答案】C
【解析】对于设备A ，每秒中查询至少200次，每次查询至少500个时钟周期，总的时钟周期数为100000, 又因为处理器主频为50MHz 。所以CPU 用于设备A 的I/0的时间占整个CPU 时间的百分比至少为100000/50=0.20%。
4． 将一个的三对角矩阵，按行优先存入一维数组（即该元素下标
A.198 B.195 C.197
在B 数组中的位置K 为（ ）。
中，A 中元素
【解析】将对角矩阵
存入
三对角矩阵压缩地址计算公式如下：
5． 浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位（均含2位符号位）
。若有两个数
则用浮点加法计算X+Y的最终结果是（ ）。
A.001111100010
B.001110100010 C.010000010001 D. 发生溢出 【答案】D
【解析】浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤，难点在对阶、规格化、判溢出这三步。X 和Y 的阶码不同，所以应该先对阶，对阶原则为：小阶向大阶看齐。因此将Y 对阶后得到：Y=
然后将尾数相加，得到尾数之和为：34/32。因为这
是两个同号数相加，尾数大于1，则需要右规，阶码加1。由于阶码的位数为5位，且含两位符号位，即阶码的表示范围在-8〜+7之间。而阶码本身等于7, 再加1就等于8。因此，最终结果发生溢出。
6． 要连通具有n 个顶点的有向图，至少需要（ ）条边。
A.n-1 B.n C.n+1 D.2n
【答案】B
【解析】对于有向图来说，两个顶点之间的边是具有方向的。如果是构成连通的无向图，需要n-1条边，而对于有向图来说，只需要再加上第一个顶点和最后一个顶点加上一条边，让其构成环状的图即可，因此最少需要n 条边。
7． 在系统总线的数据线上，不可能传输的是（ ）。
A. 指令 B. 操作数
C. 握手（应答）信号 D. 中断类型号型号 【答案】C
【解析】握手（应答）信号属于通信联络控制信号应该在通信总线上传输，不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。
8． 从堆中删除一个元素的时间复杂度为（ ）。
【解析】堆中删除一个元素，需要重新调整堆，其时间复杂度为
9． 某CPU 主频为1.03GHz , 采用4级指令流水线，每个段的执行需要1个时钟周期。假定CPU
执行了100条指令，在其执行过程中没有发生任何流水线阻塞，此时流水线的吞吐率为（ ）
A. B. C. D. 【答案】C
【解析】采用4级流水线执行100条指令，在执行过程中共用
条指令/秒，故答案为C 。
10．将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。
A.4 B.5 C.6 D.7
【答案】C
【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个全二叉树的高度为
或
的TCP 段，期望与主机乙建立TCP 连接，
叉树的高度为
或
11．主机甲向主机乙发送一个
结点的完
由完全二叉树类推到完全三叉树可知，n 个结点的完全三
个时钟周期。
CPU 的主频是1.03GHz , 也就是说每秒钟有1.03G 个时钟周期。流水线的吞吐率
为
条指令/秒
条指令/秒
条指令/秒
条指令/秒
若主机乙接受该连接请求，则主机乙向主机甲发送的正确的TCP 段可能是（ ）。
A. （SYN=0, ACK=0, seq=11221, ack=11221） B. （SYN=1, ACK=1, seq=11220, ack=11220） C. （SYN=1，ACK=1, seq= 11221，ack= 11221） D. （SYN=0, ACK=0, seq= 11220, ack= 11220） 【答案】C
【解析】TCP 是面向连接的，所谓面向连接，就是当计算机双方通信时必需先建立连接，然后数据传送，最后拆除三个过程，也就是客户主动打开TCP 传输，服务器被动打开。第一次握手：客户发送SYN=1，seq=x 给服务器，即客户的TCP 向服务器发出连接请求报文段，其首部中的同步位SYN=1，并选择序号seq=x，表明传送数据时的第一个数据字节的序号是X 。第二次握手：服务器发送SYN=1, ACK=1, Seq=y, ack=X+l给客户，即服务器的TCP 收到连接请求报文段后，如同意则发回确认。服务器在确认报文段中应使SYN=1，使 ACK=1，其确认号ack=x+l, 自己选
相关内容
相关标签