《2017年军事医学科学院国家生物医学分析中心836计算机应用之数据结构考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年军事医学科学院国家生物医学分析中心836计算机应用之数据结构考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年军事医学科学院国家生物医学分析中心836计算机应用之数据结构考研强化模拟题一、填空题1 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_，_和_。B+树适用于组织_的索引结构，m阶个关键码。【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；2 在二叉树中，指针p 所指结点为叶结点的条件是_。【答案】 【解析】叶子节点的左右孩子都不存在。3 栈是_的线性表，其运算遵循_的原则。；后进
2、先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作） 4 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_。（注：矩阵元素下标从1开始）【答案】93【解析】对于上三角矩阵，将代入得93。 5 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 【答案】（1）（2）链表未到尾就一直进行将当前结点作为头结点后的第一元素结点插入在B树每个结点至多有_个儿子，除根结点外每个结点至少有_个儿子，根结点至少有_个儿子，有k 个儿子的结点必有_ 6 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_和记录的_，【答
3、案】比较；移动 7 当两个栈共享一存储区时，栈利用一维数组当栈1空时，【答案】为_，栈2空时， 表示，两栈顶指针为则为_，栈满时为_。【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。8 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_次探测。【答案】 【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为 9 以下是用类C 语言写山的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的
4、Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针，试填充算法中的空格，使算法完整。void leafchain（BiTree Abt）p=BiTree）malloc （sizeof （BiTNode ）; If （!p ）print（“OVERFLOWn”; exit （1）; head=p; top=0; if （bt ）top+; stacktop=bt; while （top ）t=stacktop; top-;if （it-Lchild & !t-Rchild） （1）
5、 ; （2） ; （3） ; else if（ （4） ）top+; stacktop= （5） ; if （ （6） ）top+; stacktop= （5） ; （8） ; （9） ; 【答案】p-Rchild=t:t-Lchild=p:p=t: p-Rchild=head:head-Lchild=p 10【答案】5t-Rchild!=null:t-Rchild:t-Lchild!=null:t-Lchild:=_11N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_个非零元素。【答案】2（N-1）【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边
6、就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。12对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_，在给定值为x 的结点后插入一个新结点的时间复杂度为_。【答案】 【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。 13数据结构中评价算法的两个重要指标是_。【答案】算法的时间复杂度和空间复杂度14应用prim 算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。始顶点号，终顶点号，权值） （2）下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。 的值在limits ?h中 /图的顶点数，应由用户定义/用二维数组作为邻接矩阵表示/生成树的边结点/边的起点与终点 /边上的权值 /最小生成树定义 /从顶点rt 出发构造图G 的最小生成树T ，rt 成为树的根结点 /初始化最小生成树T 一、填空题考研试题
