《数据结构》模拟试卷(B卷).doc

山东科技大学数据结构模拟试卷（B卷）班级 姓名 学号 题号一二三四五总得分评卷人审核人得分一、填空题（每空1分，共10分）1、L是一个带表头结点的单链表，P结点既不是首元结点，也不是尾元结点，在P结点后插入结点Q的语句序列是Q-next=P-next; (1) _ _.2、一个算法的时间复杂度为(3n+nlog2n+n2)，其数量级表示为(2) .3、从稳定性来讲，快速排序是一种(3)的排序方法。4、对于一棵二叉树，满足(4) 是满二叉树。5、后缀算式79 2 30 + - 4 2 / *的值为(5)。中缀算式(3+X*Y)-2Y/3对应的后缀算式为(6)。6、顺序存储的循环队列队满的判断条件是(7)。(Q.rear、Q.front和maxsize分别表示队列的队头指针、队尾指针和队列的存储单元个数) 7、*a是平衡二叉树中一个子树的根结点，其平衡因子为1，现在在*a的左子树根结点的左子树上插入一新的结点，使*a的平衡因子变为(8)，使以*a为根的子树失去平衡，则需进行(9)的旋转平衡处理。8、利用给出AOV_网中顶点的拓扑序列的方法可以检查(10)。二、单项选择题（每题2分，共20分）1、深度为k的二叉树的结点总数最多为（）。A2k-1 B2k+1 C2k-1 D2k-12、假设按低下标优先存储整数数组A635时，第一个元素的字节地址是100，每个整数占四个字节，则a312的存储地址是()A.280 B.308 C.412 D.1523、若顺序存储的循环队列的的MaxSize=n,则该队列最多可存储（）个元素。A.n B.n-1 C.n+1 D.不确定4、对n个记录进行堆排序，所需要的辅助存储空间为( )A.O(Log2n) B.O(n) C.O(1) D.O(n2)5、下列关于B_树的叙述中，错误的是（）A.一棵m阶的B_树中，每个结点至多有m棵子树；B.一棵m阶的B_树中，每个结点中至多有m个关键字；C.一棵m阶的B_树中，除根之外的所有非终端结点至少有棵子树；D.一棵m阶的B_树中，若根结点不是叶子结点则至少有2棵子树6、下列关于AOE网的叙述中错误的是（）A.从源点到汇点的路径长度最长的路径是关键路径；B.完成工程的最短时间是从源点到汇点的最长路径长度；C.提前完成某些关键活动可以加快工程的进度；D.提前完成某些非关键活动可以加快工程的进度7、下列关于二叉树遍历的叙述中，正确的是（）A.若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点；B.若一个结点是某二叉树的前序遍历的最后一个结点，则它必是该二叉树的中序遍历最后一个结点；C.若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点；D.若一个树叶是某二叉树的前序遍历的最后一个结点，则它必是该二叉树的中序遍历最后一个结点；8、非空的循环单链表first的尾结点（由p所指向）满足（）A.p-next=NULL B.p=NULL C.p-next=first C.p=first9、采用邻接表存储的图的深度优先遍历算法类似于树的（）A.先序遍历 B.中序遍历 C.后序遍历 D.层序遍历10、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有边链表中边结点的总数为（） A.e/2 B.e C.2e D.n+e三、应用题（每题10分，共40分）1、试为下列关键字建立一个装填因子不小于0.75的哈希表，并写出你所使用的哈希函数，以及解决冲突的方法，并计算你所构造的哈希表在等概率的情况下查找成功和不成功时的平均查找长度。（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG）2、输入序列为(53,31, 19,23,14,55,68,11,13)，请画出插入所有关键字后的平衡二叉树。3、已知某二叉树的每个结点，要么其左、右子树皆为空，要么其左、右树皆不空。又知该二叉树的前序序列为：JFDBACEHXIK；后序序列为：ACBEDXIHFKJ。画出相应的二叉树，给出该二叉树的中序序列，并将此二叉树转换为树或森林。4、某带权有向图及它的邻接表如下：1）试写出它的深度优先搜索序列。2）根据Prim算法，求它的最小生成树。ABCBCDEFGHDEFCFGEHGHGBCEAGDFH234512346523四