2017年华东交通大学信息工程学院829数据结构考研导师圈点必考题汇编一、填空题1 起始地址为480，大小为8的块，其伙伴块的起始地址是_；若块大小为32，则其伙伴块的起始地址为_。【答案】 【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下： 根据上述公式起始地址就为488。2 一个有2001个结点的完全二叉树的高度是_。【答案】11【解析】完全二叉树的高度 3 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_检索。也可以按_检索；按_检索又可以有_检索和_检索。【答案】关键字；记录号；记录号；顺序；直接 4 求图的最小生成树有两种算法，_算法适合于求稀疏图的最小生成树e【答案】克鲁斯卡尔【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。 5 设数组的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素为_。【答案】9174；8788【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，则它的存储地址为若以列序为主存储顺序，则它的存储地址为 6 求最短路径的Dijkstra 算法的时间复杂度为_。【答案】 的存储地址为_；若以列序为主序顺序存储，则元素的存储地址7 设数组数组中任一元素均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么（1）存放该数组至少需要的单元数是_；（2）存放数组的第8列的所有元素至少需要的单元数_； （3）数组按列存储时，元素【答案】270; 27; 2204 【解析】数组的元素个数为需要第8列有9个元素，共占因为每个元素占内存48个二进制位，即6个字节。故总个单元数。个字节，因此至少需要个单元数。由题知，每个元素占3个字节，因为主内存字长为16位，即2个字节，所以至少需要的起始地址是_。个单元。按列存储时，的起始地址为8 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_算法，最费时间的是_算法。【答案】起泡；快速，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为（n ） 而快速排序算法需要比较的次数达到最大，时间复杂度为 9 设广义表 则是_tail（L ）是_；L 的长度是_；深度是_。；2；2 【答案】（ ）（ ）【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。 10当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_存储结构。【答案】顺序【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。 二、选择题11内部异常（内中断）可分为故障（fault ）、陷讲（trap ）和终止（abort ）三类。下列有关内部异常的叙述中，错误的（ ）。A. 内部异常的产生与当前执行指令相关 B. 内部异常的检测由CPU 内部逻辑实现 C. 内部异常的响应发生在指令执行过程中D. 内部异常处理后返回到发生异常的指令继续执行【答案】D【解析】内中断分为：由软中断指令启动的中断；在一定条件下由CPU 自身启动的中断。D 项错误，如突然掉电引发的内中断经处理后不会继续执行。12求整数阶乘的算法如下，其时间复杂度是（ ）。 A.B. C. D. 【答案】B 。【解析】设fact （n ）的运行时间函数是T （n ）。 该函数中语句的运行时间是0（1）, 语句的运行时间是法运算的时间。因此，当时， 当时，则，其中O （1）为乘 即fact （n ）的时间复杂度为 13稀疏矩阵一般的压缩存储方法有两种，即（ ）。A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表 【答案】C【解析】稀疏矩阵一般的压缩方法为三元组表和十字链表。三元组表就是将非零元素及其对应的行和列构成一个三元组（行标，列标，值）。十字链表相比三元组表而言，主要是对每个结点增加了两个链域。如果数组经常运算时，会产生大量数据元素的移动，此时，采用链表存储结构更为恰当。 14用海明码对长度为8位的数据进行检/纠错时，若能纠正一位错，则校验位数至少为（ ）A.2 B.3 C.4一、填空题考研试题