《2017年南京理工大学计算机科学与工程学院825计算机专业基础B之数据结构考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年南京理工大学计算机科学与工程学院825计算机专业基础B之数据结构考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年南京理工大学计算机科学与工程学院825计算机专业基础B之数据结构考研强化模拟题一、填空题1 一个有2001个结点的完全二叉树的高度是_。【答案】11【解析】完全二叉树的高度2 数组的存储结构采用_存储方式。【答案】顺序存储结构【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。3 在哈希函数中，P 值最好取_。【答案】小于等于表长的最大素数或不包含小于20的质因子的合数【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。 4 起始地址为480，大小为8的块，其伙伴块的起始地址是_；若块
2、大小为32，则其伙伴块的起始地址为_。【答案】 【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下： 根据上述公式起始地址就为488。5 阅读下列程序说明和裎序，填充程序中的_。【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：（1）把根结点放入堆栈。（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。 存放还没有转换过的结点，它的栈顶指针为。 （1） （2）If （ （3） ） 【答案】 【解析】本题主要使用堆栈完成
3、了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。6 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。Prior （node , x ） if（nod
4、e !=null）If （ （1） ） *x=node-right；else * x-node-left;next （bt , node, x ）/*bt是二叉树的树根*/ （2） ; if （node-rflag）（3）; else do t=*x；;while （*x=node ）; *x=t; 【答案】nodc-rflag=O; *x=ht; *x=nodc-right; prior （t , X ） 7 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_和_；若只设尾指针，则出队和入队的时间复杂度分别是_和_。【答案】 【解析】队列的出队操作即删除队头的元素
5、，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。 8 建立索引文件的目的是_。【答案】提高查找速度 9 从平均时间性能而言，_排序最佳。【答案】快速【解析】快速算法的平均时间复杂度为nlogn 。10在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_、_、_、_。【答案】 11克鲁斯卡尔算法的时间复杂度为_，它对_图较为适合
6、。【答案】O （eloge ）; 边稀疏 12在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_。【答案】要加“虚结点”。设编号为和的结点在顺序存储中的下标为和。 ，则结点和在同一层上的条件是 【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，二、选择题13某计算机的指令流水线由4个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间）分别为90ns 、80ns 、70ns 和60ns , 则该计算机的CPU 时钟周期至少是（ ）。A.90ns B.80ns C.70ns D.60ns 【答案】A【解析】对于各功能段执行时间不同的指令流水线，计算机的CPU 时钟周期应当以最长的功能段执行时间为准。14若串其子串的数目是（ ）。A.8 B.37 C.36 D.9【答案】B一、填空题考研试题
