单项选择题

1.算法的空间复杂度表示的是( )

（A）算法的可读性

（B）算法的难易程度

（C）执行算法所耗费的时间

（D）执行算法所耗费的存储空间

【正确答案】D

【试题解析】 一个算法的空间复杂度定义为该算法所耗费的存储空间，它是对一个算法在运行过程中临时占用存储空间大小的度量。

2.对需要频繁插入和删除元素的线性表，适合的存储方式是( )

（A）顺序存储

（B）链式存储

（C）索引存储

（D）散列存储

【正确答案】B

【试题解析】 如果经常进行的运算是插入和删除运算，以链式存储结构为宜。因为顺序表做插入和删除操作需要移动大量结点，而链式结构只需要修改相应的指针。

3.线性表的两个元素，如果逻辑上相邻，则( )

（A）顺序存储和链式存储时都一定相邻

（B）顺序存储和链式存储时都一定不相邻

（C）顺序存储时一定相邻，链式存储时不一定相邻

（D）顺序存储时不一定相邻，链式存储时一定相邻

【正确答案】C

【试题解析】 顺序存储方法是把逻辑上相邻的结点存储在物理位置上也相邻的连续存储单元里，由此得到的存储结构称为顺序存储结构。链接存储方法是用一组不一定连续的存储单元存储逻辑上相邻的元素，元素间的逻辑关系是由附加的指针域表示的，由此得到的存储结构称为链式存储结构。

4.在头指针为head的单链表中，判 ……此处隐藏9322个字…… return －1； }

【正确答案】

46.在空白处补充适当内容，使函数功能完整。

【正确答案】R[mid]．key＞k

47.如果待查序列R为(4，5，6，16，25，34，55，89)，分别给出执行f33(R，9，8)和f33(R，34，8)的返回值。

【正确答案】－1和5

算法设计题

49.二叉树的二叉链表类型定义如下： typedef struct node{ int data； struct node * lchild，* rchild； }BinNode； typedef BinNode * BinTree： 编写函数f34(BinTree Bt)，返回二叉树Bt中数据元素的最大值。 函数的原型为：int f34(BinTree Bt)。

【正确答案】 #define Min－65525 int f34(BinTree BT) { int lvalue，rvalue，maxvalue； if(BT==NULL) return Min； if(BT!=NULL) { lvalue=f34(BT－＞lchild)； rvalue=f34(BT－＞rchild)； maxvatue=(lvalue＞rvalue)?lvalue：rvalue； maxvalue=(maxvalue＞BT－＞data)?maxvalue：BT－＞data； } return maxvalue； }