2017年中国农业科学院作物科学所808数据结构考研强化模拟题
● 摘要
一、选择题
1． 以下与数据的存储结构无关的术语是（ ）。
A. 循环队列
B. 链表
C. 哈希表
D. 栈
【答案】D
【解析】循环队列体现线性表是以顺序存储。用散列法存储的线性表称散列表。链表说明线性表是以链式结构存储的。栈不能体现出是顺序还是链式存储结构。
2． 在有向图G 的拓扑序列中，若顶点V i 在顶点V j 之前，则下列情形不可能出现的是（ ） 。
A.G 中有弧
C.G 中没有弧 【答案】D 【解析】若想实现图的一个拓扑排序，需要满足的一个条件为：若顶点A 在序列中排在顶点B 的前面，则在图中不存在从顶点B 到顶点A 的路径。又因为若G 中有一条从V j 到V i 的路径，则在拓扑序列中V i 不可能在V j 前。 3． 线性表是具有n 个（ ）的有限序列（n ＞0）。 A. 表元素 B. 字符 C. 数据元素 D. 数据项E. 信息项 【答案】C 【解析】一个线性表是n 个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同。 4． 在双向链表指针P 的结点前插入一个指针q 的结点操作是（ ）。 A. B. C. D. 【答案】C 5． 下列哪一种图的邻接矩阵是对称矩阵？（ ） A. 有向图 B. 无向图 C.AOV 网 D.AOE 网 【答案】B 【解析】邻接矩阵存储，就是用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间关系的二维数组称为邻接矩阵。因为无向图中边是没有方向的，所以所以无向图的邻接矩阵是对称矩阵。 6． 引入二叉线索树的目的是（ ）。 A. 加快查找结点的前驱或后继的速度 B. 为了能在二叉树中方便地进行插入与删除 C. 为了能方便地找到双亲 D. 使二叉树的遍历结果唯一 【答案】A 【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。 7． 图的BFS 生成树的树高比DFS 生成树的树高（ ）。 A. 小或相等 B. 小 C. 大或相等 D. 大 【答案】A 【解析】BFS 称作广度优先搜索，DFS 称作深度优先搜索。广度优先搜索类似与二叉树的层序遍历算法，深度优先搜索类似于树的先序遍历。因为深度优先搜索算法遵循的策略是尽可能的“深”地搜索一个图。所以图的BFS 生成树的树高比DFS 生成树的树高小或者相等。 8． 若用户1与用户2之间发送和接收电子邮件的过程如图所示，则图中①、②、③阶段分别使用的应用层协议可以是（ ）。 图 电子邮件发送接收示意图 A.SMTP 、SMTP 、SMTP B.POP3、SMTP 、POP3 C.POP3、SMTP 、SMTP D.SMTP 、SMTP 、POP3 【答案】D 。 【解析】题中电子邮件的工作过程如下： ①用户1调用用户代理来编辑要发送的邮件，用户代理用SMTP 将邮件传送给用户1的发送端邮件服务器。 ②发送端邮件服务器也就是用户1的邮件服务器将邮件放入邮件缓存队列中，等待发送。 ③运行在发送端邮件服务器的SMTP 客户进程，发现在邮件缓存中有待发送的邮件，就向运行在接收端邮件服务器也就是用户2的邮件服务器的SMTP 服务器进程发起TCP 连接建立。当TCP 连接建立后，SMTP 客户进程开始向远程的SMTP 服务器发送邮件。当所有的待发邮件发完了，SMTP 就关闭所建立的TCP 连接。 ④运行在接收端邮件服务器中的SMTP 服务器进程收到邮件后，将邮件放人收信人的用户邮箱中，等待收信人在他方便时进行读取。收信人在打算收信时，调用用户代理，使用POP 协议将自己的邮件从接收端邮件服务器的用户邮箱中取回（如果邮箱中有来信的话）。 因此题中1，2, 3阶段分别使用的应用层协议可以是SMTP ，SMTP , POP3, 因此答案是D 。SMTP 采用“推”的通信方式，用于用户代理向邮件服务器发送邮件、以及邮件服务器之间发送邮件。POP3采用“拉”的通信方式，用于用户从目的邮件服务器上读取邮件。 9． 一个TCP 连接总是以1KB 的最大段发送TCP 段，发送方有足够多的数据要发送。当拥塞窗口为16KB 时发生了超时，如果接下来的4个RTT （往返时间）时间内的TCP 段的传输都是成功的，那么当第4个RTT 时间内发送的所有TCP 段都得到肯定应答时，拥塞窗口大小是（ ）。 A.7KB B.8KB C.9KB D.16KB 【答案】C 【解析】回顾TCP 流量控制和拥塞控制（慢启动）的知识点，从第一个MSS 开始，每次发送成功，拥塞窗口值翻倍，四次以后，应该为16, 但是由于拥塞阈值变为16/2=8, 故三次成功后为8, 以后为线性增长，故为8+1=9, 答案为C 。 10．站点A 、B 、C 通过CDMA 共享链路，A 、B 、C 的码片序列（chipping sequence ）分别是 和 C 收到A 发送的数据是（ ） A.000 B.101 C.110 D.111 【答案】B 【解析】用A 的码片与信息做内积运算 若C 从链路上收到的序列是则 二、判断题 11．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ） 【答案】 【解析】算法的健壮性是指当输入数据非法时，算法能作适当的处理并作出反应，而不应死机或输出异常结果。
相关内容
相关标签