2.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点。
第 21 页 共 30 页
参考答案
一、单项选择题(每小题2分，共30分) BADBA CDDDD CDBBA
二、填空题(每题2分，共24分) 1.树形
2.s->next===p->next; 3.hs===hs一>next; 4.f===f一>next; 5.42 6.行号列号 7.13 8.图状 9.树形 10.abdefCg 11.尾头 12.假上溢
三、综合应用题(每小题10分，共30分)
第 22 页 共 30 页
四、程序填空题(每空2分，共16分) 1.(l)n-l (2)n (3)k==j (4)a[i]==a[k] (5)a[k]==temp 2.(1)Inorder(BT->left) (2)printf(\，BT->data)
(3)Inorder(B1-\
第 23 页 共 30 页
一、单项选择题（每小题 2 分，共 30 分）
1.数据元素是数据的3基本单位，它( A. 只能有一个数据项组成
)。
B. 至少有二个数据项组成 D. 至少有一个数据项为指针类型
C. 可以是一个数据项也可以由若干个数据项组成 2. 绒性表的顺序结构中，(
)。
A 逻辑上相邻的元素在物理位置上不一定相邻 C. 逻辑上相邻的元素在物理位置上也相邻 3. 以下表中可以随机访问的是( A.单向链表
)。
B.数据元素是不能随机访问的 D.进行数据元素的插入、删除效率较高
B.双向链表 D. 顺序表
C. 单向循环链表
4 .设顺序存储的钱性表长度为 n，对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为(
A.(n+1)/2 C.2n
)。
B. n D.n-i
5. 设top 是一个链栈的栈顶指针，栈中每个结点由一个数据域 data 和指针域 next 组成，设用 x 接收楼顶元素，则出栈操作为(
)。
B. top=top->next；x=top->data； D. top->next=top；x=top->data；
A. x=top->data；top=top->next； C. x=top->next；top=top->data； 6. 以于说法正确的是( A. 队列是后进先出
)。
B. 栈的特点是后进后出
D．队列的删除和捶入操作都只能在队头
C．栈的删除和插入操作都只能在栈顶进行 进行
7. 串函数StrCmp(\，\的值为( A. 1 C. \
)。
B.0 D. -1
8. 设有一个 12 阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主存储如一维数组b中〈矩阵A的第一个元素为al,l ，数组 b 的下标从1开始)，则矩阵A中第4行的元素在数组b中的下标i一定有(
)。
第 24 页 共 30 页
9. 已知一个图的边数为 m. 则该图的所有顶点的度数之和为( A. 2m C. 2m+1
)。
B. m D. m/2
)。
10. 以下说法不正确的是( A.连通图 G一定存在生成树
B.连通圈 G 的生成树中一定包含 G 的所有顶点 C.连通图 G 的生成制中不一定包含 G 的所有边 D. 连通图G的生成树可以是不连同的 11.散列查找的原理是(
)。
A. 在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系 B．按待查记录的关键字有序的顺序方式存储 C.按关键字值的比较进行查找 D. 基于二分查找的方法
12. 排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到全部排好序为止，该排序算法是( )。
A．直接插入排序 C.冒泡排序
B. 快速排序f D. 选择排序
13. 采用顺序查找法对长度为 n 的线性表进行查找〈不采用表尾设监视哨的方法) ，最坏的情况下要进行(
)次元素间的比较。
B. n D. n/2
)。
A. n+2 C. n-l
14. 如图若从顶点a出发按广度优先搜索法进行遍历，则可能得到的顶点序列为(
A. acebdfgh C. aedfbcgh
B. aebcghdf D. abecdfgh
15. 一棵哈夫曼树总共有23个结点，该树共有( )个叶结点(终端结点〉。
第 25 页 共 30 页