《2018年武汉体育学院体育工程与信息技术学院615C语言程序设计及数据结构之数据结构考研仿真模拟五套题.doc》由会员分享,可在线阅读,更多相关《2018年武汉体育学院体育工程与信息技术学院615C语言程序设计及数据结构之数据结构考研仿真模拟五套题.doc(4页珍藏版)》请在金锄头文库上搜索。
1、2018年武汉体育学院体育工程与信息技术学院615C语言程序设计及数据结构之数据结构考研仿真模拟五套题-一、填空题1 设有N 个结点的完全二叉树顺序存放在向量【答案】 中,其下标值最大的分支结点为_。【解析】最大的分支结点是最后一个叶子结点的父结点。 2 在循环队列中,队列长度为n ,存储位置从0到,n 1编号,以rear 指示实际的队尾元素,现要在此队列中插入一个新元素,新元素的位置是_。【答案】 3 数据结构中评价算法的两个重要指标是_。【答案】算法的时间复杂度和空间复杂度 4 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中,则对这样的二叉排序树检索时,平均比较次数为_。【答案】
2、 【解析】如果关键码是排好序的,构建二叉排序树就会形成一个单支树,它的查找效率和顺序查找效率一样为。 5 应用prim 算法求解连通网络的最小生成树问题。(1)针对如图所示的连通网络,试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号,终顶点号,权值) (2)下面是Prim 算法的实现,中间有5个地方缺失,请阅读程序后将它们补上。的值在图的顶点数,应由用户定义 中 用二维数组作为邻接矩阵表示生成树的边结点边的起点与终点边上的权值 最小生成树定义 从顶点rt 出发构造图G 的最小生成树T , rt 成为树的根结点 初始化最小生成树T 依次求MST 的候选边 遍历当前候选边集合选具
3、有最小权值的候选边 图不连通,出错处理 修改候选边集合 【答案】(1)(2)【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设是N 上最小生成树边的集合。算法从属于的边为止。 6 二叉树的前序序列和中序序列相同的条件是_。【答案】空树或任何结点至多只有右子树的二叉树【解析】前序遍历的顺序为根左右,中序遍历的顺序为左根右,因此若中序遍历和前序遍历序列相同,则任何结点都没有左子树。 ,属于E 中找一条代价最小的边加入集合是连通图,v ,直到开始,重复执行下述操作:在所有u 属于,同时将并入7 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接,请填空完善之。 h
4、 为附加头结点指针 (_)_; 【答案】(1)p!NULL /链表未到尾就一直进行 (2)q /将当前结点作为头结点后的第一元素结点插入 8 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中,则非零元素中的存储位置k _。(注:矩阵元素下标从1开始)【答案】93【解析】对于上三角矩阵,k (il)(2ni 2)/2(ji) l 。将i j 9,n 15代入得93。9 设数组的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存储,则元素a45,68的存储地址为_;若以列序为主序顺序存储,则元素a45,68的存储地址为_。【答案】9174;8788【解析】设一个元素的
5、行标为i ,列标为j 。若以行序为主存储顺序,则它的存储地址为2000(il)*80j 1) 2。若以列序为主存储顺序,则它的存储地址为2000(jl)*50i l)*2。 10已知二维数组中每个元素占4个单元,在按行优先方式将其存储到起始地址为1000的连续存储区域时,A5,9的地址是: _。【答案】1196【解析】设元素的行标为i ,列标为j 。则它的存储位置为:l000(il)*l0(j0)*411从用户的观点看,文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构,称为_文件; 另一种是诸如用各种文字处理软件编辑成的文本文件,称为_文件。从文件在存储器上的存放方式来看,文件的物理结构往往可区分为三类,即_, _和_。B+树适用于组织_的索引结构,m 阶B+树毎个结点至多有_个儿子,除根结点外每个结点至少有_个儿子,根结点至少有_个儿子,有k 个儿子的结点必有_个关键码。【答案】数据库;文本;顺序组织;随机组织;链组织;随机组织;m ;12一个字符串中_称为该串的子串。【答案】任意个连续的字符组成的子序列 在B;2;k-一、填空题-考研试题-