A．1208 B．1212 C．1368 D．1364 28. 对矩阵压缩存储是为了【 】。
A．方便运算 B．节省空间 C．方便存储 D．提高运算速度 29. 以下说法错误的是【 】。
A．树形结构的特点是一个结点可以有多个直接前驱 B．线性结构中的一个结点至多只有一个直接后继 C．二叉树与树是两种不同的数据结构
D．树(及一切树形结构)是一种“分支层次’结构 30. 以下说法错误的是【 】。
A．二叉树可以是空集
B．二叉树的任一结点都有两棵子树 C．二叉树与树具有相同的树形结构
D、二叉树中任一结点的两棵子树有次序之分
31. 一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用【 】遍历方式就可以得到这棵二叉树所有结点的递减序列。
A．前序 B．中序 C．后序 D．层次
32. 对含有【 】个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。 A．0 B．1 C．2 D．不存在这样的二叉树
33. 已知某二叉树的后序遍历序列是deacb，中序遍历序列是deabc，它的前序遍历序列是【 】。 A．acbed B．baedc C．dceab D．cedba
34. 某二叉树的前序遍历的结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是【 】。
A．bdgcefha B．gdbecfha C．bdgechfa D．gdbehfca 35. 在图6-2中的二叉树中，【 】不是完全二叉树。
36. 树最适合用来表示【 】。
A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据
37. 在计算递归函数时，如不使用递归过程，则一般情况下必须借助于【 】数据结构。 A．栈 B．树 C．双向队列 D．顺序表
38. 对于一个具有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是【 】。 A．N B．(N-1)*(N-1) C．N-1 D．N*N 39. 以下说法错误的是【 】。
A．用邻接矩阵法存储图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关
B．邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用 C．存储无向图的邻接矩阵是对称的，因此也可以只存储邻接矩阵的下(或上)三角部分 D．用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am的第i行第j列的元素是否为0即可
6
二、填空题
1. 通常，数据在计算机中的存储结构有_____存储结构、______存储结构、______存储结构和_____存储结构四种基本存储结构。
2. 设循环队列的容量为70（序号为1~70），现经过一系列的入队与退队运算后，有： ①. front = 14，rear = 21，循环队列中有______个元素 ②. front = 23，rear = 12，循环队列中有______个元素
3. 单链表表示法的基本思想是用______表示结点间的逻辑关系。 4. 栈的逻辑特点是______，队列的逻辑特点是______ 5. ______可以作为实现递归函数调用的一种数据结构。 6. 在队列中，新插入的结点只能添加到______。
7. 设用一维数组A[n]来表示一个栈，令A[0]为栈底。用整型变量t来指示当前栈顶的位置，A[t]为栈顶元素。往栈中压入一个新元素时，变量t的值______，从栈中弹出一个元素时，变量t的值______。设空栈时，输入序列a，b，c经过push，pop，push，push，pop操作后，从栈中弹出的元素是_____。
8. 树(及一切树形结构)是一种_____结构。在树中，______结点没有直接前驱。 9. 二叉树第i(i>0)层上至多有______个结点。 10. 深度为k(k>0)的二叉树至多有______个结点。
11. 二叉树通常有_______存储结构和_____存储结构两类存储结构。 12. 对二叉链表的访问只能从______指针开始。
13. 对无向图，其邻接矩阵是一个关于_______对称的矩阵。
14. 请填空完成线性表在顺序存储下的插入运算程序：在线性表v中第i个位置插入值为x的元素 struct sqlist
{ int elem[MAXSIZE]; int last;
};
void insert(sqlist v, int i, int x) { int k; if (i<1 || i>v.last+1) printf( ''插入位置不合适！\\n'' ); else if (v.last>= MAXSIZE -1) printf( ''线性表已满！\\n'' ); else { for( k = v.last; k >= i; k-- ) _______________________ v.elem[i] = x; v.last++; }
}
15. 请填空完成线性表在顺序存储下的删除运算程序：在线性表v中删除第i个位置的元素
struct sqlist { int elem[MAXSIZE]; int last;
};
7
void delete(sqlist v, int i) { int k; if (i<1 || i>v.last)
printf( ''删除位置不合适！\\n'' ); else { for( k = i+1; k <= v.last; k++ ) v.elem[k-1] = v.elem[k]; _______________________ } }
16. 请填空完成栈在顺序存储下的入栈运算程序：将值为x的元素入栈s struct stack
{ int sData[MAXSIZE];
int top; //栈顶指针，指向当前栈顶的位置 };
void push(struct stack s, int x) //入栈运算 { if (s.top == MAXSIZE-1) { printf(''栈满溢出 \\n''); } else { _______________________ s.sData[top]=x; } }
17. 请填空完成栈在顺序存储下的出栈运算程序：栈s出栈，并将出栈元素作为函数返回值返回struct stack
{ int sData[MAXSIZE];
int top; //栈顶指针，指向当前栈顶的位置 };
int pop(struct stack s) //退（出）栈运算 { int x; if (s.top == -1) { printf(''栈空溢出 \\n''); exit(1); } else { x=s.sData[top]; _______________________ } return x; }
8
三、判断题
1．顺序存储的线性表可以随机存取。
2．顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。
3．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。 4．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 5．在单链表中，可以从头结点开始查找任何一个元素。 6．线性表的链式存储结构优于顺序存储结构。
7．在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。
8．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
9．顺序存储方式只能用于存储线性结构。 10．循环队列中元素个数为rear-front。
11．一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2． 12．若以链表作为栈的存储结构，则入栈需要判断栈是否满． 13．数组是同类型值的集合。 14．数组是一组连续的内存单元。
15．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。
16．插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。 17．使用三元组表示稀疏矩阵的元素，有时并不能节省存储空间。 18．二叉树是树的特殊形式。
19．树和二叉树之间最主要的差别是：二叉树的结点的子树要区分为左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
20．用邻接矩阵法存储图时，所占用的存储空间大小仅与图中结点个数有关。 21．存储有向图的邻接矩阵一定是对称的。
四、简答应用题
1. 有三个元素的进栈序列是1，2，3，举出此三个元素可能的出栈序列，并写出相应的进栈和出栈操作序列 (假设以I和O表示进栈和出栈操作)。 2. 试将下列稀疏矩阵A用三元组（三列二维表格）形式来表示，并写出对应的辅助向量POS和NUM。
40A?0000300000006500 00
3. 试写出对下图所示的二叉树分别按前序、中序和后序遍历时得到的结点序列。
E DA
BC
9
4. 画出下图所示的树对应的二叉树。
A BECFD
5. 请写出下图对应的关联矩阵R及求值矩阵V，结点A,B,C,D,E分别用1,2,3,4,5编号
10A811 B13ED12C
6. 逻辑结构与存储结构是什么关系？
7. 描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。 8. 何时选用顺序表，何时选用链表作为线性表的存储结构为宜？
9. 如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构？为什么？
10. 若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？为什么？
11. 设计算法并写出程序，实现“计算带头结点的单链表的结点个数”。
12. 已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树，并写出其前序遍历序列。
10
