《2017年厦门大学自动化系845数据结构考研冲刺密押题.doc》由会员分享，可在线阅读，更多相关《2017年厦门大学自动化系845数据结构考研冲刺密押题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年厦门大学自动化系845数据结构考研冲刺密押题一、填空题1 循环队列的引入，目的是为了克服_。【答案】假溢出时大量移动数据元素【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。 2 遍历图的过程实质上是_，广度优先遍历图的时间复杂度_; 深度优先遍历图的时间复杂度_, 两者不同之处在于_, 反映在数据结构上的差别是_。【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，
2、深度优先遍历图使用栈这种数据结构。3 外排序的基本操作过程是_和_。；归并 【答案】生成有序归并段（顺串）4 在哈希函数中，P 值最好取_。【答案】小于等于表长的最大素数或不包含小于20的质因子的合数【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。 5给定一组数据以它构造一棵哈夫曼树，则树高为_，带权路径长度的值为_。 【答案】5；96【解析】每次找两个最小的权值构建哈夫曼树： 6 棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_个结点。【答案】 【解析】每个非终端结点都是
3、0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉 树。故结点个数为 7 在下面的程序段中，对X 的赋值语句的时间复杂度为_（表示为n 的函数）。 【答案】1（12）（123）?（l 2. n ）=n（n 1）（n 2）/6，即 【解析】当i=l时，赋值语句就被执行了一次。当i=2时，赋值语句被执行了12次。当i=3时，赋值语句被执行了123次。可以推出赋值语句总共被执行了1（12）（123）（l 2. n ）=n（n 1）（n 2）/6次。8 在基于关键字比较且时间为O （nl g2n ）的排序中，若要求排序是稳定的，则可选用_，则可选用_排序。 排序；若要求就地排序（及辅助空间为0（1
4、）【答案】归并；堆 9 已知一循环队列的存储空间为环队列判满的条件是（ ）【答案】 ，）则的地址为_。若 10设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：【答案】33【解析】设存储的元素的行标为i ，列标为j 。若则的地址为 11设广义表将则代入得33。是_tail（L ）是_；L 的长度是_；深度是_。则的地址为其中队头和队尾指针分别为front 和rear , 则此循；2；2 【答案】（ ）（ ）【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。 12组成串的数据元素只能是_。【答案】
5、字符二、选择题13若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（ ）。A. 存在，且唯一 B. 存在，且不唯一不唯一 C. 存在，可能不唯一 D. 无法确定是否存在 【答案】C 。【解析】图的基本应用拓扑排序，用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，说明该图为有向无环图，所以其拓扑序列存在，但不一定唯一，如图的邻接矩阵为则存在两个拓扑序列。14若则下列表达式采用8位定点补码运算实现时，会发生溢出的是（ ）A.x+y B.-x+y C.x-y D.-x-y【答案】C【解析】8位定点补码能表示的数的范围为： A 结果为78, B结果为-128,
6、D结果为-78都在此范围内，只有C 结果128超过了8位定点补码能表示的数的范围，会发生溢出 15用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为趟排序采用的增量（间隔）可能是（ ）A.2 B.3 C.4 D.5【答案】B【解析】对于A , 增量为2, 那么9, 4, 7, 20, 15是一组，而它们是无序的，所以A 错误 对于C , 增量为4, 那么9, 7，15是一组，而它们是无序的，所以C 错误对于D , 增量为5, 那么9, 8是一组，降序，1，20是一组，而它们是升序，所以D 也错误。对于B ，分为3组：都是升序有序，所以B 正确 16对给定的关键字序列110, 119, 007, 911，114，120, 122进行基数排序，则第2趟分配收集后得到的关键字序列是（ ）A. B. C. D.【答案】C 则该一、填空题考研试题
