数据结构试卷

所有的限制，几乎都是从自己的内心开始的。
巢湖电大04/05学年度第一学期
开放教育计算机专科《数据结构》期中考试试卷

年级____________ 学号 姓名 成绩 ___一、选择题（每小题2分）
1、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）
A 存储结构 B 逻辑结构 C 算法 D 操作
2、链式栈与顺序栈相比，一个比较明显的优点是（）
A 插入操作更加方便 B 通常不会出现栈满的情况 C 不会出现栈空的情况 D 删除操作更加方便
3、线性表是一个具有n个（ ）的有限序列。
A．表元素 B．字符 C．数据元素 D．数据项
4、对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序周游的结果为（ ）
A．DBFEAC B．DFEBCA C．BDFECA D．BDEFAC
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 左子女右兄弟表示法 C 广义表表示法 D 顺序表示法
9、在一棵具有5层的满二叉树中结点数为（）
A 31 B 32 C 33 D 16
10、若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有______个结点。 ( )
　A.15 B.16 C.17 D.18
二、判断题（每小题1分）
（ ）1、算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。
（ ）2、二维数组是数组元素为一维数组的线性表，因此它是线性结构。
（ ）3、顺序表用一维数组作为存储结构，因此顺序表是一维数组。
（ ）4、通常使用两个类来协同表示单链表，即链表的结点类和链表类。
（ ）5、栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。
（ ）6、线性链表中各个链结点之间的地址不一定要连续
（ ）7、具有n个结点的完全二叉树的高度为┖log2n┘+1。
（ ）8、数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。
（ ）9、.算法一定要有输入和输出。
（ ）10、一棵m阶B树中每个结点最多有m

个关键码，最少有2个关键码。

三、阅读理解题（10分）
void unknown(BinTreeNode *T,int a[],int i){
if(T!=NULL){
a[i]=T->data;
unknown(T->leftChild,a,2*I+1);
unknown(T->rightChild,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 19
E A F D H C G I B （1）试画出此二叉树的图形表示。（3分）
（2）写出结点D的双亲结点及左、右子女。（3分）
（3）将此二叉树看作森林的二叉树表示，试将它还原为森林。（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分）
对于二维整数数组A[m][n]，对下列三种情况，分别编写相应的函数。
（1）求数组所有边缘的和。（5分）
int suml (int A[M][N] , int m , int n) //M和N分别大于等于m和n
{








}

（2）求从A[0][0]开始的互不相邻的所有元素的和（5分）
注：一个元素的八个方向上的第一个元素均为相邻元素。
int sum2 (int A[M][N] , int m , int n)
{







}

（3）假定m=n，请分别计算正、反两条对角线上的元素的和。（5分）
int sum3(int A[M][N] , int n)
{







}

六、填空题（每题2分，共10分）
已知一棵完全二叉树存放于一个一维数组T[n]中，T[n]中存放的是各结点的值。下面的算法的功能是：从T[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示。
此算法有5处缺失，请根据算法的功能补充之。（10分）
#include
typedef struct node {
int data;
stuct node leftChild,rightchild;
}Bin

treeNode;
typedef BintreeNode * BinaryTree;
void ConstrucTree (int T[ ] , int n , int I ,BintreeNode *& ptr);
int main(void){
Binarytree t;int n;
Cout<<"please enter the number of node:\n";cin>>n;
Int *A =new int[n];
For(int I=0;IFor(int I=0;ICout<ConstructTree(A,n,0,t);
② ;//删除数组A
return 1 ;
}
void ConstrucTree(int T[ ] , int n , int I, BintreeNode *& ptr)
{
if (I>=n) ③ ;//置根指针为空
else
ptr=new BintreeNode;
ptr->data=T[i];
ConstrucTree(T,n,2*I+1, ④ );
ConstrucTree(T, n, ⑤ ,ptr->rightchild);
}
}
缺失语句为：
①
②
③
④
⑤

所有的限制，几乎都是从自己的内心开始的。