《2017年南京师范大学计算机科学与技术学院889计算机技术综合[专业硕士]之数据结构考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年南京师范大学计算机科学与技术学院889计算机技术综合[专业硕士]之数据结构考研导师圈点必考题汇编.doc（5页珍藏版）》请在金锄头文库上搜索。
1、2017年南京师范大学计算机科学与技术学院889计算机技术综合专业硕士之数据结构考研导师圈点必考题汇编一、选择题1 以太网的MAC 协议提供的是（ ）。A. 无连接不可靠服务B. 无连接可靠服务C. 有连接不可靠服务D. 有连接可靠服务【答案】A 。【解析】考查以太网MAC 协议，考虑到局域网信道质量好，以太网采取了两项重要的措施以使通信更简洁：采用无连接的工作方式；不对发送的数据帧进行编号，也不要求对方发回确认。因此，以太网提供的服务是不可靠的服务，即尽最大努力交付，差错的纠正由高层完成。 2 下列排序算法中，占用辅助空间最多的是（ ）。A. 归并排序B. 快速排序C. 希尔排序D. 堆排序
2、【答案】A【解析】归并排序的辅助空间为用的辅助空间为 3 已知一算术表达式的中缀表达式为【答案】D【解析】后缀表达式：在程序语言中，运算符位于两个操作数后面的表达式。 4 假定主存地址为32位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（WriteBack ）方式，则能存放4K 字数据的Cache 的总容量的位数至少是（ ）。A.146kB.147KC.148KD.158K【答案】B快速排序所占用的辅助空间为堆排序所占其后缀形式为（ ）。 【解析】Cache 和主存直接映射方式的规则为：主存储器分为若干区，每个区与缓存容量相同；每个区分为若干数
3、据块，每个块和缓存块容量相同；主存中某块只能映象到Cache 的一个特定的块中。本题中，Cache 总共存放4K 字数据，块大小为4个字，因此cache 被分为4K/4 = 1K 个块，由10位表示。块内共16字节，所以由4位表示，于是标记位为32-10-14= 18位。所以，Cache 的每一行需要包含所存的数据4个字，每个字32位，18位标记位和一个有效位，因此总容=147K。 量为： 5 设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块的大小均为256字节，则可表示的单
4、个文件最大长度是（ ）。A.33KBB.519KBC.1057KBD.16513KB【答案】C【解析】4个地址项为直接地址索引，其指向的数据块大小4256B=lKB，一级间接地址索引可以索引256/4=64个直接地址索引，故2个一级间接地址索引指向的数据块大小为264256B=32KB，二级间接地址索引为256/4256/4=4096个直接地址索引，故1个二级间接地址索引指向的数据块大小为4096256B=1024KB, 共计1KB+32KB+1024KB=1057KB。 6 棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有（ ）个结点。A.2hB.C.D.【答案】B【解析】此
5、树满足哈夫曼树，除根节点外每层有两个节点。 7 一个TCP 连接总是以1KB 的最大段发送TCP 段，发送方有足够多的数据要发送。当拥塞窗口为16KB 时发生了超时，如果接下来的4个RTT （往返时间）时间内的TCP 段的传输都是成功的，那么当第4个RTT 时间内发送的所有TCP 段都得到肯定应答时，拥塞窗口大小是（ ）。A.7KBB.8KBC.9KBD.16KB【答案】C【解析】回顾TCP 流量控制和拥塞控制（慢启动）的知识点，从第一个MSS 开始，每次发送成功，拥塞窗口值翻倍，四次以后，应该为16, 但是由于拥塞阈值变为16/2=8, 故三次成功后为8, 以后为线性增长，故为8+1=9,
6、答案为C 。 8 如果本地域名服务无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为（ ）。A.1条，1条B.1条，多条C. 多条，1条D. 多条，多条【答案】A【解析】所谓递归查询方式就是：如果主机所询问的本地域名服务器不知道被查询域名的IP 地址，那么本地域名服务器就以DNS 客户的身份向其他服务器继续发出查询请求报文，而不是让该主机自行下一步的查询。所以主机只需向本地域名服务器发送一条域名请求，采用递归查询方法，本地域名服务器也只需向上一级的根域名服务器发送一条域名请求，然后依次递归。正确选项为A 。 9 一棵哈夫曼树共有215个结点，对其
7、进行哈夫曼编码，共能得到（ ）个不同的码字。A.107B.108C.214D.215【答案】B【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有以 10最大容量为n 的循环队列，队尾指针是rear ，队头：front , 则队空的条件是（ ）。A.B.C.D.【答案】B【解析】循环队列队空的条件是：rear=front。循环队列队满的条件，通常采用来判定队满，其中表示队列的长度。 所也就是说若对其进行哈夫曼编码，共能得到108个码字。二、判断题11如果完全二叉树从根结点开始按层次遍历的输序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树。（ ）【答案】【解析】不是，2，3作为1的左右孩子，由于左节点2比1大，所以不具有二叉排序树的性质。 一、选择题考研试题
