2017年杭州师范大学杭州国际服务工程学院826计算机基础之数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 设无向图的顶点个数为m 则该图最多有（ ）条边。
A.n-1
B.n （n-l ）/2
C.n （n+l）/2 D.0 E.n2
【答案】B
【解析】在数据结构中仅讨论简单图，在计算无向图的最多边时，不考虑顶点与顶点的边。因此边数最多时，构成的是无向完全图。此时的边数为n （n-l ）/2。
2． 在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps , 电缆中的信号传播速度是200000km/s。若最小数据帧长度减少800bit ，则最远的两个站点之间的距离至少需要（ ）。
A. 增加160m B. 增加80m C. 减少160m D. 减少80m 【答案】D
【解析】以太网采用CSMA/CD访问协议，在发送的同时要进行冲突检测，这就要求在能检测出冲突的最大时间内数据包不能够发送完毕，否则冲突检测不能有效地工作。所以，当发送的数据包太短时必须进行填充。最小帧长度=碰撞窗口大小x 报文发送速率，本题最小数据帧长度减少800b ，那么碰撞的窗口也要减少，因此距离也要减少，从而（800×2×
）/（l ×
）=160m，
由于时间延时存在两倍的关系，因此减少的距离为80m 。
3． —
组记录的关键码为则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。
【答案】C
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：46比84小，不交换；
第二次比较：40比46小，交换，此时为第三次比较：46比79小，交换，此时为第四次比较：38比46小，交换，此时为第五次比较：56比46大，交换，此时为
一次划分结束。
4． 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。
【答案】A
【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语句
，则有设其执行时间为T （n ）
5． 折半查找的时间复杂性为（ ）。
【答案】D
【解析】顺序查找的事件复杂度为度为
6． 以太网交换机进行转发决策时使用的PDU 地址是（ ）。
A. 目的物理地址 B. 目的IP 地址 C. 源物理地址 D. 源IP 地址 【答案】A
【解析】交换机会监测发送到每个端口的数据帧，通过数据帧中的有关信息（源结点的MAC 地址、目的结点的MAC 地址）, 就会得到与每个端口所连接结点的MAC 地址, 并在交换机的内部建立一个“端口-MAC 地址”映射表。建立映射表后，当某个端口接收到数据帧后，交换机会读取出该帧中的目的结点的MAC 地址，并通过“端口-MAC 地址”的对应关系，迅速将数据帧转发到相应的端口，注意这里的交换机工作在数据链路层，因此关于IP 地址的选项是不对的，因此答案为A 。
7． 以下与数据的存储结构无关的术语是（ ）。
A. 循环队列
因为折半查找是查找效率最高的算法，它的事件复杂
B. 链表 C. 哈希表 D. 栈 【答案】D
【解析】循环队列体现线性表是以顺序存储。用散列法存储的线性表称散列表。链表说明线性表是以链式结构存储的。栈不能体现出是顺序还是链式存储结构。
8． 设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块的大小均为256字节，则可表示的单个文件最大长度是（ ）。
A.33KB B.519KB C.1057KB D.16513KB 【答案】C
【解析】4个地址项为直接地址索引，其指向的数据块大小4×256B=lKB，一级间接地址索引可以索引256/4=64个直接地址索引，故2个一级间接地址索引指向的数据块大小为2×64×256B=32KB，二级间接地址索引为256/4×256/4=4096个直接地址索引，故1个二级间接地址索引指向的数据块大小为4096×256B=1024KB, 共计1KB+32KB+1024KB=1057KB。
9． 假定主存地址为32位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（WriteBack ）方式，则能存放4K 字数据的Cache 的总容量的位数至少是（ ）。
A.146k B.147K C.148K D.158K 【答案】B
【解析】Cache 和主存直接映射方式的规则为：主存储器分为若干区，每个区与缓存容量相同；每个区分为若干数据块，每个块和缓存块容量相同；主存中某块只能映象到Cache 的一个特定的块中。本题中，Cache 总共存放4K 字数据，块大小为4个字，因此cache 被分为4K/4 = 1K 个块，由10位表示。块内共16字节，所以由4位表示，于是标记位为32-10-14= 18位。所以，Cache 的每一行需要包含所存的数据4个字，每个字32位，18位标记位和一个有效位，因此总容=147K。 量为：
10．假定下列指令已装入指令寄存器。则执行时不可能导致CPU 从用户态变为内核态（系统态）的是（ ）。
A. B. 产生软中断