《2017年南昌航空大学信息工程学院817数据结构考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年南昌航空大学信息工程学院817数据结构考研导师圈点必考题汇编.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年南昌航空大学信息工程学院817数据结构考研导师圈点必考题汇编一、填空题1 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_次查找成功，查找47时_成功，查找100时，需_次才能确定不成功。【答案】2；4；3【解析】二分法查找元素次数列表 查找100是找到115就停止了。 2 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_。【答案】要加“虚结点”。设编号为和的结点在顺序存储中的下标为和。 3 克鲁斯卡尔算法的时间复杂度为_，它对_图较为适合。【答案】O （eloge ）; 边稀疏 4 空格串是指_，其长
2、度等于_。【答案】由空格字符（值32）所组成的字符串；空格个数 5 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_次探测。【答案】 【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为 6 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_个，单链表为_个。【答案】4; 2，则结点和在同一层上的条件是 【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，7 有向图G=（V ，E ）, 其中V （G ）=0, 1，2，3，4, 5, 用三元组表示弧及弧上的权d 。
3、 E （G ）为 E （G= , , ， ，则从源点0到顶点3的最短路径长度是_，经过的中间顶点是_。【答案】50; 48 设广义表则是_tail（L ）是_；L 的长度是_；深度是_。；2；2 【答案】（ ）（ ）【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。 9 若用n 表示图中顶点数目，则有_条边的无向图成为完全图。【答案】n （n-l ）/2【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2
4、。10二叉树由_，_，_三个基本单元组成。【答案】根结点；左子树；右子树二、选择题11循环两列放在一维数组中，endl 指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（ ）A. 队空：B. 队空：C. 队空：D. 队空：【答案】A【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等，则队满。而队空的条件还是首尾指针是否相等。 12下列关于无向连通图特性的叙述中，正确的是（ ）。I. 所有的顶点的度之和为偶数 II. 边
5、数大于顶点个数减1 III. 至少有一个顶点的度为1 A. 只有I B. 只有II队满：队满：队满：modM ; 队满： C.I 和II D.I 和III 【答案】A【解析】在图中，顶点的度TD 点数，e 为总边数），因此，I 项正确。对于II 、III 项中的特性不是一般无向连通图的特性，可以轻松地举出反例。“至少有一个顶点的度为1”的反例如下图（1）所示，“边数大于顶点个数减1”的反例如下图（2）所示。 之和与边的数目满足关系式：（n 为图的总结 图 13下列选项中，对正确接收到的数据帧进行确认的MAC 协议是（ ）。A.CSMA B.CDMA C.CSMA/CD D.CSMA/CA 【答
6、案】D【解析】可采用排除法。CDMA 是码分多址复用，是物理层的内容；CSMA/CD即带冲突检测的载波监听多 路访问，接收方并不需要确认；CSMA/CD是CSMA 的加强版，故CSMA 也无确定；CSMA/CD是802.11中的 协议，其利用ACK 信号来避免冲突的发生，也就是说，只有当 客户端收到网络上返回的ACK 信号后才确认送 出的数据已经正确到达目的地址，因此答案是D 。14在文件的索引节点中存放直接索引指针10个，一级二级索引指针各1个，磁盘块大小为1KB 。每个索引指针占4个字节。若某个文件的索引节点已在内存中，到把该文件的偏移量（按字节编址）为1234和307400 处所在的磁盘块读入内存。需访问的磁盘块个数分别是（ ）。A.1, 2 B.1, 3 C.2, 3 D.2, 4【答案】B【解析】文件的索引结点的直接索引指针有10个，因此直接索引的偏移量范围是级索引的偏移量范围是二级索引访问的偏移量范围是一偏移量1234可以通过直接索引得到在磁盘块的地址，因此需要一次访问，307400需要通过二级索引查找其在一、填空题考研试题
