2016年沈阳师范大学教师专业发展学院数据结构(同等学力加试)考研复试题库
● 摘要
一、选择题
1． 下列关于无向连通图特性的叙述中，正确的是（ ）。
I. 所有的顶点的度之和为偶数
II. 边数大于顶点个数减1
III. 至少有一个顶点的度为1
A. 只有I
B. 只有II
C.I 和II
D.I 和III
答:A
【解析】在图中，顶点的度TD
点数，
e 为总边数），因此，I 项正确。对于II 、III 项中的特性不是一般无向连通图的特性，可以轻松地举出反例。“至少有一个顶点的度为1”的反例如下图（1）所示，“边数大于顶点个数减1”的反例如下图（2）所示。
之和与边的数目满足关系式：（n 为图的总结
图
2． 下列存储器中，在工作期间需要周期性刷新的是（ ）。
A.SRAM
B.SDRAM
C.ROM
D.FLASH
答:B
【解析】动态随机存储器（DRAM ）是利用存储元电路中栅极电容上的电荷来存储信息的，电容上的电荷一般只能维持
间必须刷新。
因此即使电源不掉电，信息也会自动消失。为此，每隔一定时
3． 若X 是后序线索二叉树中的叶结点， 且X 存在左兄弟结点Y ，则X 的右线索指向的是（ ）
A.X 的父结点
B. 以Y 为根的子树的最左下结点
C.X 的左兄弟结点Y
D. 以Y 为根的子树的最右下结点
答:A
【解析】根据后续线索二叉树的定义，X 结点为叶子结点且有左兄弟，那么这个结点为右孩子结点，利用后续遍历的方式可知X 结点的后继是其父结点，即其右线索指向的是父结点。
4． 在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps , 电缆中的信号传播速度是200000km/s。若最小数据帧长度减少800bit ，则最远的两个站点之间的距离至少需要（ ）。
A. 增加160m
B. 增加80m
C. 减少160m
D. 减少80m
答:D
【解析】以太网采用CSMA/CD访问协议，在发送的同时要进行冲突检测，这就要求在能检测出冲突的最大时间内数据包不能够发送完毕，否则冲突检测不能有效地工作。所以，当发送的数据包太短时必须进行填充。最小帧长度=碰撞窗口大小x 报文发送速率，本题最小数据帧长度减少800b ，那么碰撞的窗口也要减少，因此距离也要减少，从而（800×2×）/（l ×）=160m，由于时间延时存在两倍的关系，因此减少的距离为80m 。
5． 对n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ）。
A. 每次分区后，先处理较短的部分
B. 每次分区后，先处理较长的部分
C. 与算法每次分区后的处理顺序无关
D. 以上三者都不对
答:A
【解析】令递归函数为f ，第一次进行递归函数认为递归深度为1，以后从深度为n 的递归函数f 中再调用递归函数f ，此时深度为整个f 的最大深度为递归深度。
6．
循环两列放在一维数组中，endl 指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（ ）
A. 队空：队满：
相关内容
相关标签