《2017年北方工业大学计算机学院861数据结构考研题库.doc》由会员分享，可在线阅读，更多相关《2017年北方工业大学计算机学院861数据结构考研题库.doc（5页珍藏版）》请在金锄头文库上搜索。
1、2017年北方工业大学计算机学院861数据结构考研题库一、填空题1 阅读下列程序说明和裎序，填充程序中的_。【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：（1）把根结点放入堆栈。（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。 存放还没有转换过的结点，它的栈顶指针为。 （1） （2）If （ （3） ） 【答案】 【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，
2、交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。 2 索引顺序文件既可以顺序存取，也可以_存取。【答案】随机 3 循环队列的引入，目的是为了克服_。【答案】假溢出时大量移动数据元素【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。 4 实现字符串拷贝的函数strcpy 为： 【答案】 5 在单链表中设置头结点的作用是_。【答案】方便运算 6 高度为4的3阶B-树中，最多有_个关键字。【答案】26【解析】第4层是叶结点，1层至
3、3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。 7 在有n 个顶点的有向图中，每个顶点的度最大可达。【答案】2（n-l ）【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。8 设数组数组中任一元素均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么（1）存放该数组至少需要的单元数是_；（2）存放数组的第8列的所有元素至少需要的单元数_； （3）数组按列存储时，元素【答案】270; 27; 2204 【解析】数组的元素个数为需要第8列有9个元素，共占因为每个元素占内存48个二进制位，即6个字节。故总个单元数。个字节，因此
4、至少需要个单元数。由题知，每个元素占3个字节，因为主内存字长为16位，即2个字节，所以至少需要的起始地址是_。个单元。按列存储时，的起始地址为 9 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_。【答案】要加“虚结点”。设编号为和的结点在顺序存储中的下标为和。 10从平均时间性能而言，_排序最佳。【答案】快速【解析】快速算法的平均时间复杂度为nlogn 。 【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，则结点和在同一层上的条件是二、判断题11倒排文件是对次关键字建立索引。（ ）【答案】，将所有具有相同【解析】倒排文件是对每一个次关键字项
5、建立次关键字索引（称为倒排表）次关键字的记录的物理记录号都填入倒排表为此次关键字的表中。 12哈希表的结点中只包含数据元素自身的信息，不包含任何指针。（ ）【答案】【解析】哈希表的结点中可以包括指针，指向其元素。如哈希链表。 13数据元素是数据的最小单位。（ ）【答案】 【解析】数据项是数据的不可分割的最小单位，而数据元素是数据的基本单位。 14若把堆看成是一棵完全二叉树，则该树一定是一棵二叉排序树。（ ）【答案】【解析】堆中某个节点的值总是不大于或不小于其父节点的值，这个并不是二叉排序树的性质。 15内排序要求数据一定要以顺序方式存储。（ ）【答案】【解析】由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：一类是内部排序；另一类是外部排序。因此，内部排序没有要求数据一定是以顺序方式存储。162，. ，n , 输出序列是栈的输入序列是1，【答案】 若则有： （ ）【解析】出栈序列不一定满足比如1进栈，然后出栈， 17顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ）【答案】 【解析】前者正确，后者错误。顺序存储方式在插入、删除元素时需要挪动大量的元素，执行效率较低。 18一般来说，若深度为k 的n 个结点的二叉树只有最小路径长度，那么从根结点到第的最多结点数为【答案】层具有余下的个结点在第k 层的任一位置上。（ ）一、填空题考研试题
