数据结构代码课程类别必

专业班级学学生签试卷编号 数据结 课 课程类别：题—二三四五六七八九十总题题—二三四五六七八九十总题得考生注意事项：1、本试卷共7页，总分 分，考试时间120分钟一、选择题2，共30 假设某算法语句总的执行次数为T(n)=6n4+n³+n2,那么该算法的时间复杂性量级为(C 线性表采用顺序结构时，其地址 必须是连续 B)部分地址必须是连续C)一定是不连续 D)连续与否均可从物理结构上可以把数据结构分为（B B．顺序结构、链式结构 在顺序线性表（a1,a2,···,a29,a30）中，在a20之前插入一个新的结点，需 B) C) D)结点的单循环链表为空的条件是 栈S最多能容纳4个元素。现在6个元素按A、B、C、D、E、F的顺序进 B) B)A、F、E、D、C、C)C、B、E、D、A、 D)C、D、B、F、E、深度为K的二叉树最多有( )个结点 2K 2Kn个顶点的无向完全图的弧数为 )n(n- n(n-1)在一个图中，图的边数等于所有顶点的度数之和的 )倍 图的广度优先遍历类似于二叉树的（ 先序遍 B)中序遍 C)层次遍 D)后序遍在有n个叶子结点的哈夫曼树中，其结点总数为 不确 D)2n-100个结点的完全二叉树从根这一层开始，每一层从左到右依次对136B) D)利用逐点插入法建立序列(50，72，43，85，5，20，35，5，65，3)对应的二叉排序树以后，查找元素35要进行（A ）元素间的比较。4 5 7 10在顺序表(3,6,8,10,12,15,16,18,21,25,30)中，用折半法查找关键码值 链表适用于（ 顺 二分 顺序，也能二分 D)随二、填空题（每空1分,20分通常是以算法执行所耗费的时 和所占用的空间来判断一个算法的优劣队列中允许进行删除的一端 队 n个顶点的连通图的生成树 n- 条边后缀算式 2 +-6 /*的值为_ _。中缀算式（8--4*Y/7对应的后缀算式为8XY*-4 若要求一个稀疏图G的最小生成树，最好用克鲁斯卡尔个点若进栈序列为a,b,c，则通过入出栈操作可能得到的a,个点1这棵树的根结点是（9）A1这棵树的叶子结点 结点A3的度 （11）这棵树的度 这棵树的深度 结点A3的 （14）结点A3的父结点 （15）叶678个结点，则共有叶假定一棵二叉树的结点数为18，则它的最小深度为 ，最大深度为 若要求一个稠密图G的最小生成树，最好 普里 算法来求解n个顶点e条边的图，若采用邻接矩阵，则空间复杂度 三、构造题(每 分，共34分DS（5分DS=(D, D={a,b,c,d,e,f R={TT={<a,b>,<c,b>,<d,c>,<d,f>,<e,d>,<f,a>,<f,e>（5分）（10分（10012345001234505726图 图给定网G3G的最小生成树，画出其逻辑结构图（4分四、编程题（共16分1、写一算法，从顺序表中插入自第i个元素开始的k（已知给定抽象数据类型及算法参数，ka中，请补充完成下面算法typedefStruct{int