A.n-1 B.n C.n/2 D.n1 9． .数据元素及其关系在计算机存储器内的表示，称为数据的( ) A.逻辑结构 B.存储结构 C.线性结构 D.非线性结构 10． .导致栈上溢的操作是( ) A.栈满时执行的出栈 B.栈满时执行的入栈 C.栈空时执行的出栈 D.栈空时执行的入栈 11． 设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是( ) A.(rear-front)%m= =1 B.front= =rear C.(rear-front)%m= =m-1 D.front= =(rear+1)%m 12． 对于图所示的二叉树，按前序遍历所得到的结点序列为( )： A A A. G D B A C E F B. A B C D E F G B C C. A B D G C E F D. D G B A E C F D E F G 13． 以二叉链表作为二叉树的存储结构中，有n（n>0）个结点的二叉链表中空链的个数为（） A.2n-1 B. n-1 C. n+1 D. 2n+1 14． 下列排序算法中，( )算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。 A.堆排序 B.冒泡排序 C.快速排序 D.SHELL排序 15． 关键路径是事件结点网络中.（） A.从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长回路 D. 最短回路 16． 求最短路径的迪杰斯特拉算法的时间复杂度为( ) A. O(n) B. O(n+e) C. O(n2) D. O(n×e) 17． 队列操作的原则是( ) A.先进先出 B.后进先出 C.只能进行插入 D.只能进行删除 18． 对树而言，最不适合的遍历是（） A 先序 B 中序 C后序 D层次 第1页共4页 19． n条边的无向图的邻接表的存储中，边结点的个数有（） A .n B .2n C .n/2 D. n*n 20． 顺序查找适合于存储结构为（）的线性表 A. 哈希存储 B.压缩存储 C.顺序存储或链表存储 D.索引存储
二．判断题(本大题共10小题，每小题1分，共10分)
请在每小题的括号中填上正确答案。错填、不填均无分。
1. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。( ) 2. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就
完成了对该矩阵的转置运算( )
3. 插入排序是稳定的，希尔排序是不稳定的。( )
4. .二叉树中的叶子结点就是二叉树中没有左右子树的结点。( ) 5. 有向图的邻接表和逆邻接表中的结点数一定相同。( ) 6. 用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（） 7. 霍夫曼树一定是满二叉树。（） 8. 栈是一种线性结构。（）
9. 求最小生成树的Prim算法在边较少，节点较多时效率高。（）
10. 对二叉排序树进行中序遍历得到的序列是由小到大有序的。( ) 三、填空题(本大题共10小题，每小题2分，共20分)
请在每小题的空格中填上正确答案。错填、不填均无分。
1． 在一个单链表中p所指结点之后插入一个由指针f所指结点，应执行s->next=__
______;和p->next=s的操作。
2． 在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为_____。 3． 假设以行优先顺序存储三维数组A[5][6][7]，其中元素A[0][0][0]的地址为1100，且
每个元素占2个存储单元，则A[4][3][2]的地址是________。 4． 深度为k(k>0)的二叉树最多有___________个结点。 5． 串中所含字符个数称为该串的_____ ______。
6． n(n>0)个结点、(n-1)条边的连通无向图中，顶点度数最大值为____________。
7． 如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出栈序列
中第30个元素为______。
8． 二叉排序树中，最大值结点和最小值结点一定是结点。 9． 在有n个叶子结点的哈夫曼树中，总结点数是_______。 10． 在有n个结点的无向图中，其边数最多为_______。
四、解答题(本大题共4小题，每小题5分，共20分)
1. 现有如下图所示的二叉树，试给出其顺序存储结构示意图。
2. 给出如下有向图的邻接表和逆邻接表。
3. 构造一棵表达式(a+b*(c-d))-e/f的二叉树，并写出其波兰式（前缀式）和逆波兰式
（后缀式）
4. 构造下图深度优先生成树和广度优先生成树。
V1 V2 V3 V4 V5 V6 V7 V8 五、算法设计题(本题共20分，要求在语句后面加注释)
1.设计一个算法判别一个算术表达式的圆括号是否正确配对，并说明其圆括号配对正确与否的返回值。(10分)
2.以二叉链表为存储结构，写出求二叉树叶子总数的算法。(10分)
第2页共4页
2007 –2008 学年第 2学期期末考试 试题参考答案 一、选择题(每个选项1.5分，共30分) 1 A 11 D 2 C 12 C 3 C 13 C 4 D 14 C 5 C 15 A 6 C 16 C 7 D 17 A 8 B 18 B 9 B 19 B 10 B 20 C 2 V3 3 ∧ 2 0 V3 ∧ 3 V4 3 V4 0 ∧ 2 ∧ (a) 邻接表 (b) 逆邻接表 3.每式2.5分 答：波兰式（前缀式）-+a*b-cd/ef 逆波兰式（后缀式）abcd-*+ef/- 4.答：每个生成树2.5分 深度优先生成树 二、判断题，正确打√，错误打Х（每小题1分,共10分 ） 1 √ 2 × 3 √ 4 √ 5 √ 6 × 7 × 8 √ 9 × 10 √ 三、填空题(每空2分，共20分) 1 2 3 4 5 p->next O(n) 1291 2k-1 长度 6 7 8 9 10 n-1 69 叶子 2n-1 n(n-1)/2 V1V2V4 V3广度优先生成树 V1 V3 V5 V7V2 V5 V7 V8 V6 V4 V8 V6 四、解答题(本大题共4小题，每小题5分，共20分) 1 A B C D E F ∧ ∧ ∧ G ∧ ∧ H 五、算法设计题(本题共20分，要求在语句后面加注释) 1． 设计一个算法判别一个算术表达式的圆括号是否正确配对，并说明其圆括号配对正确与否的返回值。 int process(char *c) /*判断C中的括号是否匹配，如果匹配返回1,否则返回0 */ {SeqStack *s;/*定义堆栈指针*/ char s1,*x; 1分 x=&s1; s=Init_SeqStack(); /*初始化堆栈*/ 1分 while(*c!='\\0') 3分 {if(*c=='(') Push_SeqStack (s,'(' );2分 if(*c==')' ) 第3页共4页 （错一个扣一分，最多扣5分） 2. 每个表2.5分 V1 2 1 ∧ 3 ∧ V1 0 ∧ 1 V2 1 V2 0 ∧
{if(!Empty_SeqStack(s))
Pop_SeqStack(s, x); 2分 else
return 0; }
c++; 1分 }
return (Empty_SeqStack(s));/*如果匹配，则栈空 返回1,否则返回0 */ }
2． 以二叉链表为存储结构，写出求二叉树叶子总数的算法。
int CountLeafs(BinTree *root) {
int num1,num2; 2 if(root==Null) return(0);
else if(root->lchild==Null&&root->rchild==Null) 3 return(1); else {
num1=CountLeafs(root->lchild);
num2=CountLeafs(root->rchild); 5return(num1+num2);
} } 3．
分 分 分 第4页共4页
因篇幅问题不能全部显示，请点此查看更多更全内容