《2017年辽宁工程技术大学项目管理(专业学位)935数据结构考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年辽宁工程技术大学项目管理(专业学位)935数据结构考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年辽宁工程技术大学项目管理(专业学位)935数据结构考研强化模拟题一、填空题1 设数组数组中任一元素均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么（1）存放该数组至少需要的单元数是_；（2）存放数组的第8列的所有元素至少需要的单元数_； （3）数组按列存储时，元素【答案】270; 27; 2204 【解析】数组的元素个数为需要第8列有9个元素，共占因为每个元素占内存48个二进制位，即6个字节。故总个单元数。个字节，因此至少需要个单元数。由题知，每个元素占3个字节，因为主内存字长为16位，即2个字节，所以至少需要的起始地址是_。个单元。按列存储时
2、，的起始地址为 2 n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。注：（1）图的顶点号从0开始计；（2）indegree 是有n 个分量的一维数组，放顶点的入度， （3）函数crein 用于记算顶点入度；（4）有三个函数push （data ）, pop（ ）, check（ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1, 否则0）。 ） . 【答案】0; j; i; 0; indegreei=0; vexi; k=l; indegreei=0【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程： ；（“图有回
3、路”）首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。 3 外排序的基本操作过程是_和_。；归并 【答案】生成有序归并段（顺串） 4 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_算法，最费时间的是_算法。【答案】起泡；快速，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为（n ） 而快速排序算法需要比较的次数达到最大，时间复杂度为 5 以下是用类C 语言写山的算法，该算法将以二叉链表存储的二叉树中的叶结点按
4、从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的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; wh
5、ile （top ）t=stacktop; top-;if （it-Lchild & !t-Rchild） （1） ; （2） ; （3） ; else if（ （4） ）top+; stacktop= （5） ; if （ （6） ）top+; stacktop= （5） ; （8） ; （9） ; 【答案】p-Rchild=t:t-Lchild=p:p=t: t-Rchild!=null:t-Rchild: t-Lchild!=null: p-Rchild=head:head-Lchild=p6 文件可按其记录的类型不同而分成两类，即_和_文件。【答案】操作系统文件；数据库t-Lchild
6、:7 顺序存储结构是通过_表示元素之间的关系的；链式存储结构是通过_表示元素之间的关系的。【答案】物理上相邻；指针【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。 8 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个顶点用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。（1）若是边，则的值等于_，若不是边，则的值是一个比任何边的权，矩阵的对角线元素全为0。（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若【答案】（1） 已包括进生成树，就把矩阵元素A （i
7、 ，j ）置成。 边上的权值；都大的数；（2）1; 负值；（3）为负；边（3）算法结束时，相邻矩阵中的元素指出最小生成树的 9 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f （m , n ）为这种表示方式的 数目。例f （5, 3）=5，有5种表示方式：32, 311，221，2111, 11111。以下是该函数的程序段，请将未完成的部分填入，使之完整。 执行程序，f （6，4）=_。 【答案】1; 1; f （m ，n 1）; n 9 10求图的最小生成树有两种算法，_算法适合于求稀疏图的最小生成树e【答案】克鲁斯卡尔【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。 二、算法设计题一、填空题考研试题
