《2017年北华大学计算机科学技术学院841数据结构考研仿真模拟题.doc》由会员分享，可在线阅读，更多相关《2017年北华大学计算机科学技术学院841数据结构考研仿真模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年北华大学计算机科学技术学院841数据结构考研仿真模拟题一、填空题1 已知二维数组为1000的连续存储区域时，【答案】1196【解析】设元素的行标为i ，列标为j 。则它的存储位置为： 2 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_次探测。【答案】 【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为 3 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。 【答案】（1）（2）（3）（4）（5）置空链表，然后将原链表结点逐
2、个插入到有序表中当链表尚未到尾，p 为工作指针查P 结点在链表中的插入位置，这时q 是工作指针将P 结点链入链表中是q 的前驱，u 是下个待插入结点的指针中每个元素占4个单元，在按行优先方式将其存储到起始地址的地址是：_。 4 一个有2001个结点的完全二叉树的高度是_。【答案】11【解析】完全二叉树的高度 5 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个顶点用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。（1）若是边，则的值等于_，若不是边，则的值是一个比任何边的权，矩阵的对角线元素全为0。（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把
3、相邻矩阵的对角线元素A （i , i ）置成若【答案】（1）6 设数组 已包括进生成树，就把矩阵元素A （i ，j ）置成。 边上的权值；都大的数；（2）1; 负值；（3）为负；边 数组中任一元素均占内存48个二进制位，从首地址2000开始（3）算法结束时，相邻矩阵中的元素指出最小生成树的连续存放在主内存里，主内存字长为16位，那么（1）存放该数组至少需要的单元数是_；（2）存放数组的第8列的所有元素至少需要的单元数_； （3）数组按列存储时，元素【答案】270; 27; 2204 【解析】数组的元素个数为需要第8列有9个元素，共占个单元。按列存储时， 7 设数组储，则元素为_。【答案】917
4、4；8788【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，则它的存储地址为若以列序为主存储顺序，则它的存储地址为 8 起始地址为480，大小为8的块，其伙伴块的起始地址是_；若块大小为32，则其伙伴块的起始地址为_。【答案】 【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下： 根据上述公式起始地址就为488。因为每个元素占内存48个二进制位，即6个字节。故总个单元数。个字节，因此至少需要的起始地址为个单元数。由题知，每个元素占3 个字节，因为主内存字长为16位，即2个字节，所以至少需要的起始地址是_。的基地址为2000，每个元素占2个存储单元，若以行序
5、为主序顺序存的存储地址的存储地址为_；若以列序为主序顺序存储，则元素9 属于不稳定排序的有_。【答案】希尔排序、简单选择排序、快速排序、堆排序等 10顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_次；当使用监视哨时，若查找失败，则比较关键字的次数为_。【答案】 【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。 11G 是一个非连通无向图，共有28条边，则该图至少有_个顶点。【答案】9【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。12下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空： 【答案】 【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。 二、选择题13折半查找的时间复杂性为（ ）。 【答案】D【解析】顺序查找的事件复杂度为因为折半查找是查找效率最高的算法，它的事件复杂度为 14希尔排序的组内排序采用的是（ ）。A. 直接插入排序 B. 折半插入排序一、填空题考研试题
