《2017年中国民航大学计算机科学与技术学院833算法与数据结构考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年中国民航大学计算机科学与技术学院833算法与数据结构考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年中国民航大学计算机科学与技术学院833算法与数据结构考研强化模拟题一、填空题1 设数组储，则元素为_。【答案】9174；8788【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，则它的存储地址为若以列序为主存储顺序，则它的存储地址为 2 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_。【答案】【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。3 VSAM 系统是由_、_、_构成的。【答案】索引集；顺序集；数据集 4 G 是一个非连通无向图，共有28条边，则该图至少有_个顶点。【答案】9【解析】求该非连通无向图的最少顶点数，
2、则该图为一个孤立的顶点和一个完全连通图。 5 中缀式对应的前缀式为_，若则后缀式的运算结果为_。【答案】 【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。 6 串是一种特殊的线性表，其特殊性表现在_; 串的两种最基本的存储方式是_、_; 两个串相等的充分必要条件是_。【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等7 VSAM （虚拟存储存取方法）文件的优点是：动态地_，不需要文件进行_，并能较快地_进行查找。【答案】分配和释放存储空间；重组；对插入的记录第 2 页，共 57 页的基地址为2000，每个元素占2个存储单元，若以行
3、序为主序顺序存的存储地址为_；若以列序为主序顺序存储，则元素的存储地址 8 文件可按其记录的类型不同而分成两类，即_和_文件。【答案】操作系统文件；数据库 9 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_和_；若只设尾指针，则出队和入队的时间复杂度分别是_和_。【答案】 【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在
4、尾指针的后面插入新的结点，并更新尾结点即可。 10以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 【答案】（1）链表未到尾就一直进行（2）将当前结点作为头结点后的第一元素结点插入 11抽象数据类型的定义仅取决于它的一组_，而与_无关, 即不论其内部结构如何变化，只要它的_不变，都不影响其外部使用。【答案】逻辑特性；在计算机内部如何表示和实现；数学特性 12棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _。【答案】2【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。13外排序的基本操作过程是_和_。；归并 【答案】生成有序归并段（顺串） 14对单链
5、表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。 第 3 页，共 57 页【答案】（1）（2）（3）（4）（5） 置空链表，然后将原链表结点逐个插入到有序表中当链表尚未到尾，p 为工作指针查P 结点在链表中的插入位置，这时q 是工作指针将P 结点链入链表中是q 的前驱，u 是下个待插入结点的指针 15求图的最小生成树有两种算法，_算法适合于求稀疏图的最小生成树e【答案】克鲁斯卡尔【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。 二、选择题1
6、6下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。A. 直接插入排序 B. 起泡排序 C. 基数排序 D. 快速排序 【答案】C【解析】C 项，基数排序是采用分配和收集实现的，不需要进行关键字的比较。ABD 三项都依赖关键字的比较，不同的初始排列次序下元素移动的次数有很大变化，最好情况元素正序，则不用移动，最坏情况元素反序，则需要移动n （n-1） /2次（为元素个数）。 17假定有4个整数用8位补码分别表示为存放在一个8位寄存器中，则下列运算会发生溢出的是（ ）。A.r1r2 B.r2r3 C.r1r4 D.r2r4 【答案】B【解析】用补码表示时8位寄存器所能表示的整数范围为在4个选项中，只有第 4 页，共 57 页 若将运算结果现在4个整数都是负数，结果溢出，其余3个算式结果一、填空题考研试题
