在二叉排序树中进行查找的效率与（）有关

A．二叉排序树的深度

B．二叉排序树的结点的个数

C．被查找结点的度

D．二叉排序树的存储结构

A．平衡二叉树

B．二叉查找树

C．没有左子树的二叉排序树

D．没有右子树的二叉排序树

A、二叉排序树是动态的，在查找不成功时，会引起树的重新分裂和组合。

B、对二叉排序树进行层次遍历可以得到有序序列。

C、在二叉排序树中，新结点总是作为叶子结点插入的。

D、二叉排序树的查找效率和二叉排序树的高度有关。

E、若用一个有序序列来构造一棵二叉排序树，其高度最大。

F、在含有 n 个结点的二叉排序树中进行查找，关键字的比较次数不超过n/2

G、在一棵二叉排序树中删除关键字为 k 的结点，然后再插入关键字为 k 的结点，这样的二叉排序树前后没有变化。

A、查找时间效率

B、存储效率

C、查找时间效率和存储效率

D、插入和删除数据效率

A、二叉排序树的结点数

B、二叉树的高度

C、后序线索树

D、多有线索树

I在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小。

Ⅱ每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二叉排序树。

Ⅲ在二叉排序树中，新插入的关键字总是处于最底层。

Ⅳ在二叉排序树中，新结点总是作为叶子结点来插入的。

V二叉排序树的查找效率和二叉排序树的高度有关。

A． I、Ⅱ、Ⅳ、V

B．Ⅱ、Ⅲ、Ⅳ

C． I、Ⅲ、V

D． I、Ⅳ、V

[说明]

下面程序用来将打乱的单词还原为原来的次序，比如将rty还原为try。单词的原来次序存储于wordlist.txt文件中，原则上可用穷举法(rty对应的穷举为：rty、ryt、try、tyr、ytr、yrt)，但考虑到破译速度，采用如下方法。

注意到单词列表中不存在组成字符完全相同的单词(如Hack12与Hack21包含完全相同的字符)，因此将单词中的字符进行重组再进行比较，例如，try单词重组为rty(按ASCⅡ码顺序)，这样不管打乱的单词是什么顺序，只要是由r、t、y三个字母组成的均破译为try，大大提高破译速度。程序中借助二叉排序树以进一步提高查找效率，二叉排序树左子树(如果有)上的节点对应的值均小于根节点的值，右子树(如果有)上的节点对应的值均大于根节点的值。

函数中使用的符号定义如下：

#define NumberofWords 1275//单词总数

#define MaxLength 10//最长单词所含字符数

char WordList[NumberofWords][MaxLength]；//存储单词列表

int cmp(Node *q，Node *p)；//q与p比较。p小，返回负值；P大返回正值：相等，返回0

typedef struct Node(//二叉树节点

char *eleLetters；//重组后的字符串

int index；//对应单词表中的下标

struct Node *lChiId，*rChiid；//左右子节点

}Node；

[C代码]

void reCompose(Node *p，char *temp)

//重纰，亦即将temp字符串中的字符升序排序，存储于p节点中

//采用直接插入排序法

{

char c；

strcpy(p-＞eleLetters，temp)；//

int len=strlen(temp)；

int i，j，k；

for(i=0；i＜len－1；i++){

k=i；

for(j=i+1；j＜lan；j++){

if(p-＞eleLetters[j]＜P-＞eleLetters[k])k=J；

}

if( (1) ){

C=P-＞eleLetters[i]；

P-＞eleLetters[i]=P-＞eleLetters[k]；

P-＞eleLetters[k]=c；

}//if

}//for

}；

int find(Node &root，char *temp)

//在二叉排序树root中查找与temp匹配的单词。

//若匹配返回相应单词在WordList中下标；若查找失败，返回-1

{

Node *P，*q；

int flag；

P=(2)；//临时存储

reCompose(p，temp)；//将temp重组

q=&root；

while((flag=(3))＆＆q !=NULL){

if(flag＜0){//搜索左子树

q=q-＞lChiid；

}else(//搜索右子树

q=q-＞rChild；

}

}//while

if(flag==0){//找到匹配的，保存下标

return (4)；

}

}

if( (5) ){//查找失败

printf("cant unscramble the following word：%s"，temp)；；

return -1；

}

}；

(1)

A、高度

B、结点的多少

C、树型

D、结点的位置

A、（1）高度 ；（2）结点太多

B、（1）结点的多少 ；（2）完全二叉树

C、（1） 树型 ；（2）呈单枝树

D、（1） 结点的位置 ；（2）结点太复杂

A、结点太多

B、完全二叉树

C、呈单枝树

D、结点太复杂