2015年硕士研究生入学考试业务课试题811数据结构.doc

第 1 页 共 3 页河南财经政法大学2015年硕士研究生入学考试业务课试题专业名称：计算机应用技术考试科目：数据结构（共 150 分）一、选择题（本题共 10 个小题，每小题 3 分，共计 30分）1数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（ ） 。（A）存储结构 （B）逻辑结构（C）顺序存储结构 （D）链式存储结构2. 一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是（ ） 。（A）110 （B）108 （C）100 （D ）120 3. 设有一个长度为 n 的顺序表，要在第 i 个元素之前（也就是插入元素作为新表的第 i 个元素） ，则移动元素个数为（ ） 。An-i+1 Bn-i Cn-i-1 Di4. 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。（A）8 （B）63.5 （C）63 （D ）7 5 判定一个队列 QU（最多元素为 m0）为满队列的条件是（ ） 。（A）QU-rear QU-front = = m0（B） QU-rear QU-front 1= = m0（C） QU-front = = QU-rear（D）QU-front = = QU-rear+1 6. 链表是一种采用（ ）存储结构存储的线性表。（A）顺序 （B）链式 （C）星式 （D ）网状 7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）（A）必须是连续的 （B）部分地址必须是连续的（C）一定是不连续的 （D）连续或不连续都可以 8 线性表在（ ）情况下适用于使用链式结构实现。（A）需经常修改中的结点值 （B）需不断对进行删除插入 （C）中含有大量的结点 （D）中结点结构复杂 9. 若已知一个栈的入栈序列是 1，2，3，n，其输出序列为第 2 页 共 3 页p1，p2，p3，pn，若 p1=n，则 pi 为（ ） 。（A）i （B）n=i （C）n-i+1 （D ）不确定10.设某无向图中有 n 个顶点 e 条边，则该无向图中所有顶点的度之和为（ ） 。(A) n (B) e (C) 2e (D) 7二、填空题（本题共 10 个小题，每小题 3 分，共计 30分）1.设有一个顺序共享栈 S0：n-1，其中第一个栈项指针 top1 的初值为-1，第二个栈顶指针 top2 的初值为 n，则判断共享栈满的条件是_。2.在图的邻接表中用顺序存储结构存储表头结点的优点是_。3.设有一个 n 阶的下三角矩阵 A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在 n(n+1)个连续的存储单元中，则 Aij与 A00之间有_个数据元素。4.设一棵完全二叉树的顺序存储结构中存储数据元素为 ABCDEF，则该二叉树的后序遍历序列为_。5.设一组初始记录关键字序列(k 1，k 2，k n)是堆，则对i=1，2，n/2 而言满足的条件为_。6.设关键字序列为(K l，K 2，K n)，则用筛选法建初始堆必须从第_个元素开始进行筛选。7.设有一组初始关键字序列为(24，35，12，27，18，26)，则第 3趟直接插入排序结束后的结果的是_。8.设有一组初始关键字序列为(24，35，12，27，18，26)，则第 3趟简单选择排序结束后的结果的是_。9.设一棵二叉树的前序序列为 ABC，则有_种不同的二叉树可以得到这种序列。10.设输入序列为 1、2、3，则经过栈的作用后可以得到_种不同的输出序列。三、判断题（本题共 10 个小题，每小题 3 分，共计 30分）（请在小题括号内打或） ( )1调用一次深度优先遍历可以访问到图中的所有顶点。( )2分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。第 3 页 共 3 页( )3冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。( )4满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。( )5设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。( )6层次遍历初始堆可以得到一个有序的序列。( )7设一棵树 T 可以转化成二叉树 BT，则二叉树 BT 中一定没有右子树。( )8线性表的顺序存储结构比链式存储结构更好。( )9中序遍历二叉排序树可以得到一个有序的序列。( )10.快速排序是排序算法中平均性能最好的一种排序。四、简答题（本题共 2 个小题，每小题 15 分，共计 30分）1设无向图 G（如图 1 所示） ，给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。图 12从空树起，依次插入关键字37，50，42，18，48，12，56，30，23，构造一棵二叉排序树。（1）画出该二叉排序树；（2）画出从（1）所得树中删除关键字为 37 的结点之后的二叉排序树。五、算法设计题（本题共 2 个小题，每小题 15 分，共计30 分）1. 设计在链式存储结构上建立一棵二叉树的算法。2设计在单链表中删除值相同的多余结点的算法。