解放军电子工程学院攻读硕士学位研究生入学考试样卷计算机基础-数据结构.docxVIP

解放军电子工程学院 ****年攻读硕士学位研究生入学考试试卷 考试科目：《数据结构》 （75分） 一、选择题：（每题2分，共20分） 组成数据的基本单位是（ ）。 (A) 数据项 (B) 数据类型 ( C) 数据元素 (D)数据变量 设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ B ）。 (A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1 (C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3 在二叉排序树中插入一个关键字值的平均时间复杂度为（ ）。 (A) O(n) (B) O(log2n) (C) O(nlog2n) (D) O(n2) 设某棵二叉树中只有度数为0和度数为2的结点，且度数为0的结点数为n，则这棵二叉中共有（ ）个结点。 (A) 2n (B) n+l (C) 2n-1 (D) 2n+l 在下列排序算法中稳定的排序算法为（ ）。 (A) 直接插入排序 (B) shell排序 (C) 堆排序 (D) 快速排序 设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。 (A) n，e (B) e，n (C) 2n，e (D) n，2e 若数组S[1..n]作为两个栈S1和S2的存储空间，对任何一个栈，只有当[1．．n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是( )。 (A) S1的栈底位置为0，S2的栈底位置为n+l (B) S1的栈底位置为0，S2的栈底位置为n/2 (C) S1的栈底位置为1，S2的栈底位置为n (D) S1的栈底位置为1，S2的栈底位置为l 下面关于线性表的叙述中，错误的是哪一个？（ ） (A)线性表采用顺序存储，必须占用一片连续的存储单元。 (B)线性表采用顺序存储，便于进行插入和删除操作。 (C)线性表采用链接存储，不必占用一片连续的存储单元。 (D)线性表采用链接存储，便于插入和删除操作。 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ ）。 (A) 808 (B) 818 (C) 1010 (D) 1020 对稀疏矩阵进行压缩存储目的是（ ）。 (A) 便于进行矩阵运算 (B) 便于输入和输出 (C) 节省存储空间 (D) 降低运算的时间复杂度 二、填空题：（每空1分，共10分） 1.对算法从两方面进行度量，分别称为 分析和 分析。 2. 线性表是n个元素的 。 3. 线性表的存储结构有 和 。当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 存储结构。 4. 队列已满，但队列空间未被充分利用，此现象称 。 5. 二叉树第i层上最多有 个结点。 6. 在AVL树中，由于在A结点的右孩子的右子树上插入结点，使A结点的平衡因子由-1变为-2，使其失去平衡，应采用 型平衡旋转。 7. 堆排序的时间复杂度为 。 三、简答题：（20分） 1．求下列程序段的时间复杂度：（4分） （1） i=s=0; while(sn) { i++; s+=i; } （2） fact(int n) { if(n=1) return 1; else return(n*fact(n-1)); } 2．在某程序中，栈1和栈2共享一个一维数组空间SPACE[N]。SPACE[0]、SPACE[N-1]分别是栈1和栈2的栈底，top1和top2分别为栈1和2的栈顶指针。（6分） （1）对栈1、栈2，试分别写出（元素x）入栈的主要语句和出栈的主要语句。 （2）对栈1、栈2，试分别写出栈满、栈空的条件。 3．将下列由三棵树组成的森林转换为二叉树。（5分） 4. 已知某二叉树按中序遍历次序是BDCEAFHG，按后序遍历次序是 DECBHGFA，试画出该二叉树的形状，并写出它的前序扫描序列。（5分） 四、综合应用题（共25分） 设计在链式存储结构上的合并排序算法。（8分） 2．已知一棵二叉树以二叉链表的形式存储，请编写一算法判断该二叉树是否为二叉排序