《数据结构试卷40118.doc》由会员分享，可在线阅读，更多相关《数据结构试卷40118.doc（8页珍藏版）》请在金锄头文库上搜索。
1、数据结构试卷40118在世界上我们只活一次，所以应该爱惜光阴。必须过真实的生活，过有价值的生活。巴甫洛夫巢湖电大04/05学年度第一学期开放教育计算机专科数据结构期中考试试卷年级_ 学号 姓名 成绩 _一、选择题（每小题2分） 1、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）A 存储结构 B 逻辑结构 C 算法 D 操作 2、链式栈与顺序栈相比，一个比较明显的优点是（） A 插入操作更加方便 B 通常不会出现栈满的情况 C 不会出现栈空的情况 D 删除操作更加方便3、线性表是一个具有n个（ ）的有限序列。A表元素 B字符 C数据元素 D数据项4、对某二叉树进行前序遍历的结果为A
2、BDEFC，中序遍历的结果为DBFEAC，则后序周游的结果为（ ）ADBFEAC BDFEBCA CBDFECA DBDEFAC 5、在一个顺序存储的循环队列中，队头指针指向队头元素的（ ） A 前一个位置 B 后一个位置 C 队头元素位置 D 队尾元素的前一位置 6、用链表表示线性表的优点是（） A 便于随机存取 B 花费的存储空间比顺序表少 C 便于插入与删除 D 数据元素的物理顺序与逻辑顺序相同7、.若某完全二叉树的深度为h，则该完全二叉树中至少有_个结点。 ( )A.2h B.2h-1 C.2h-1-1 D.2h-1+1 8、下列存储形式中，（）不是树的存储形式 A 双亲表示法 B 左
3、子女右兄弟表示法 C 广义表表示法 D 顺序表示法 9、在一棵具有5层的满二叉树中结点数为（） A 31 B 32 C 33 D 1610、若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有_个结点。 ( )A.15 B.16 C.17 D.18二、判断题（每小题1分）（ ）1、算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。 （ ）2、二维数组是数组元素为一维数组的线性表，因此它是线性结构。 （ ）3、顺序表用一维数组作为存储结构，因此顺序表是一维数组。 （ ）4、通常使用两个类来协同表示单链表，即链表的结点类和链表类。 （ ）5、栈
4、和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。（ ）6、线性链表中各个链结点之间的地址不一定要连续（ ）7、具有n个结点的完全二叉树的高度为log2n+1。 （ ）8、数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。 （ ）9、.算法一定要有输入和输出。 （ ）10、一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。三、阅读理解题（10分） void unknown(BinTreeNode *T,int a,int i)if(T!=NULL)ai=T-data;unknown(T-leftChild,a,2*I+1);unknown(T-rightC
5、hild,a,2*I+2); 主程序调用方式unknown(BT.root,a,0); / 将完全二叉树所有结点从要开始，自顶向下，同一层自左向右连续编号， /根结点的编号为0。四、简答题（共35分）1、 将关键码53，78，65，17，87，09，81，45，23依次插入到一棵初始为空的二叉搜索树中，画出每插入一个关键码后的二叉搜索树 2、某二叉树的结点数据采用顺序存储表示如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19EAFDHCGIB （1）试画出此二叉树的图形表示。（3分） （2）写出结点D的双亲结点及左、右子女。（3分） （3
6、）将此二叉树看作森林的二叉树表示，试将它还原为森林。（3分） 3、已知某二叉树的前序序列为EBADCFHGI，中序序列为ABCDEFGHI，请给出二叉树的后序序列4、已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。中序序列：c，b，d，e，a，g，I，h，j，f前序序列：a，b，c，d，e，f，g，h，I，j后序序列： 在世界上我们只活一次，所以应该爱惜光阴。必须过真实的生活，过有价值的生活。巴甫洛夫五、综合算法题（每题5分，共15分） 对于二维整数数组Amn，对下列三种情况，分别编写相应的函数。 （1）求数组所有边缘的和。（5分） int suml (int AMN , int m
7、 , int n) /M和N分别大于等于m和n （2）求从A00开始的互不相邻的所有元素的和（5分）注：一个元素的八个方向上的第一个元素均为相邻元素。int sum2 (int AMN , int m , int n)（3）假定m=n，请分别计算正、反两条对角线上的元素的和。（5分）int sum3(int AMN , int n)六、填空题（每题2分，共10分） 已知一棵完全二叉树存放于一个一维数组Tn中，Tn中存放的是各结点的值。下面的算法的功能是：从T0开始顺序读出各结点的值，建立该二叉树的二叉链表表示。 此算法有5处缺失，请根据算法的功能补充之。（10分） #include typed
8、ef struct node int data; stuct node leftChild,rightchild; BintreeNode; typedef BintreeNode * BinaryTree; void ConstrucTree (int T , int n , int I ,BintreeNode *& ptr); int main(void) Binarytree t;int n; Coutn; Int *A =new intn; For(int I=0;In;I+) ;从键盘输入结点值 For(int I=0;In;I+)coutAi; Cout=n) ;/置根指针为空elseptr=new BintreeNode;ptr-data=Ti;ConstrucTree(T,n,2*I+1, );ConstrucTree(T, n, ,ptr-rightchild);缺失语句为： 在世界上我们只活一次，所以应该爱惜光阴。必须过真实的生活，过有价值的生活。巴甫洛夫
