数据结构(C++)模拟试题技术总结.doc

模拟试题 3 1. 当初始序列已按健值有序时,用直接插入算法进行排序,需要比较的次数为( ) A. n-1 B. log 2n C. 2log 2n 2 冒泡排序 n 2 选择排序 n 2 插入排序 n 2 堆排序 nlog n 归并排序 nlog2n 快速排序 n 2 希尔排序 n 2 2. 以下时间复杂性不是 O(n 2) 的排序方法是() A. 直接插入排序 B. 二路归并排序 C. 冒泡排序 D. 直接选择排序 3. .对采用二分查找法进行查找运算的查找表,要求按( )方式进行存储。 A. 顺序存储 B 链式存储 C. 顺序存储且结点按关键字有序 D. 链式存储且结点按关键字有序 4. 设有序表的关键字序列为{1,4,6, 10, 18, 35, 42, 53, 67, 71, 78, 84, 92, 99} , 当用二分查找法查找健值为 84 的结点时,经( )次比较后查找成功。 D. 12 5. 静态查找表与动态查找表两者的根本差别在于() ……………………………………………. A. 逻辑结构不同 B. 存储实现不同 C. 施加的操作不同 D. 数据元素的类型不同 6 .用顺序查找法对具有 n 个结点的线性表查找的时间复杂性量级为 (n 2) B. O(nlog 2 n) (n) D. O(log 2 n) 7. 设有 6 个结点的无向图,该图至少应有( )条边能确保是一个连通图。 8. 在无向图中,所有顶点的度数之和是所有边数的( )倍。 .5 9. 深度为 6 的二叉树最多有() 个结点. A. 64 B. 63 C. 32 D. 31 10 .将含有 83 个结点的完全二叉树从根结点开始编号,根为 1 号,后面按从上到下、从左到右的顺序对结点编号,那么编号为 41 的双亲结点编号为() A. 42 B. 40 C. 21 D. 20 11. 已知某二叉树的后序遍历序列是 dabec, 中序遍历序列是 deabc, 它的前序遍历序列是( ) A. acbed B. deabc C. decab D. cedba 12. 设二叉树结点的先根序列、中根序列和后根序列中,所有叶子结点的先后顺序() A. 都不相同 B. 完全相同 C. 先序和中序相同,而与后序不同 D. 中序和后序相同,而与先序不同 13 .如果以链表作为栈的存储结构,做退栈操作时() A. 必须判别栈是否满 B. 必须判别栈是否空 C. 判别栈元素的类型 D. 对栈不做任何操作 14 .链栈与顺序栈相比,有一个比较明显的优点即( ) A. 插入操作更方便 B. 通常不会出现栈满的情况 C. 不会出现栈空的情况 D. 删除操作更方便 15. 线性结构中的一个结点代表一个( ) A. 数据元素 B. 数据项 C. 数据 D. 1. 若待排序的序列中存在多个记录具有相同的键值,经过排序,这些记录的相对次序仍然保持不变,则称这种排序方法是________ 的,否则称为________ 的。 2. 按照排序过程涉及的存储设备的不同,排序可分为________ 排序和________ 排序。 3. 直接插入排序是稳定的,它的时间复杂性为_______