《数据结构》模拟卷.doc

课程: 数据结构 班级学号： 姓名: 题 号 一 二 三 四 五 六 合计 题 分 一．选择题（每小题2分，共20分） 1．如果以链表作为栈的存储结构，做退栈操作时( ) A.必须判别栈是否满 B.必须判别栈是否空 C.判别栈元素的类型 D.对栈不做任何操作 2.线性结构中的一个结点代表一个（ ） A. 数据元素 B. 数据项 C. 数据 D. 数据结构 3.线性表L=(a1,a2,...,ai,...,an),下列说法正确的是( ) A.每个元素都有一个直接前驱和直接后继 B.线性表中至少要有一个元素 C.表中诸元素的排列顺序必须是由小到大或由大到小的 D.除第一个元素和最后一个元素外其余每个元素都有一个数且仅有一个直接前驱和直接后继 4.单链表的一个存储结点包含（ ） A.数据域或域 B.指针域或链域 C.指针域和链域 D.数据域和指针域 5．将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双结点编号为 ( ) 42 B.40 C.21 D.20 6.已知某二叉树的后序遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（ ） A.acbed B.deabc C.cedba D.decab 7.当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（ ） A.n-1 B.log2n C. 2log2n D.n2 8．对采用二分查找法进行查找运算的查找表，要求按（ ）方式进行存储。 A.顺序存储 B 链式存储 C.顺序存储且结点按关键字有序 D.链式存储且结点按关键字有序 9．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ） A．插入 B．删除 C．排序 D．定位 10．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ ） A．不一定相同 B．都相同 C．都不相同 D．互为逆序 二．填空题（每题2分，共20分） 1.二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值________于其左孩子（及其子孙）的键值且________于其右孩子（及其子孙）的键值。 2.平衡二叉排序树上任一结点的平衡因子只可能是________、________或________。 3.在无向图中，如果从顶点v到顶点v’有路径，则称v和v’是_______的。如果对于图中的任意两个顶点vi,vj∈V，且vi和vj都是连通的，则称G为________。 4.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。 5.直接插入排序是稳定的，它的时间复杂性为________，空间复杂度为________。 6.一个具有n个顶点的完全无向图的边数为________。一个具有n个顶点的完全有向图的弧度数为________。 7．队列称为___________线性表。 8.常见时间复杂性的量级有：常数阶O(___________)、对数阶O(________)线性阶O(___________)、平方阶O(___________)、和指数阶O(___________)。 9.深度为k(k=1)的二叉树至多有______个结点。 10．有m个叶子结点的哈夫曼树，其结点总数为________。 三．名词解释题（每小题3分,共15分） 1.排序 2. ..查找长度 3..无向完全图 4 满二叉树 5.链表 四．简答题（每小题5分,共15分） 什么是二叉排序树? 什么叫稀疏矩阵? 静态查找表与动态查找表的区别是什么? 五．解答题（每小题5分,共10分） 1.对长度为20的有序表进行二分查找，请画出它的一棵判定树，并求等概率情况下的平均查找长度。 2.求出下面带权图的最小生成树 六．算法设计题（每小题10分,共20分） 1.找出数组A[1..n]中元素的最大