(完整版)数据结构查找习题及答案.doc资源-CSDN文库

84 浏览量 2022-12-16 01:22:30 上传评论收藏 437KB DOC 举报

资源推荐

资源详情

资源评论

(完整版)数据结构查找习题及答案

第 9 章查找

一、单选题

1. 对一棵二叉搜索树按()遍历，可得到结点值从小到大的排列序列.

A。先序　 B。中序 C. 后序 D。层次

2. 从具有 n 个结点的二叉搜索树中查找一个元素时，在平均情况下的时间复杂度大致为（）。

A. O（n) B。 O（1） C。 O（logn） D. O(n

2

)

3. 从具有 n 个结点的二叉搜索树中查找一个元素时,在最坏情况下的时间复杂度为（）。

A。 O（n） B。 O（1) C. O(logn) D。 O（n

2

)

4. 在二叉搜索树中插入一个结点的时间复杂度为（）.

A。 O（1) B。 O(n) C。 O(logn) D。 O(n

2

）

5. 分别以下列序列构造二叉搜索树，与用其它三个序列所构造的结果不同的是(）。

A．（100,80， 90， 60， 120，110,130）

B。（100，120,110，130，80, 60， 90)

C.（100，60， 80， 90， 120，110,130）

D.（100，80， 60， 90， 120，130，110)

6. 在一棵 AVL 树中,每个结点的平衡因子的取值范围是().

A. —1~1 B。 -2~2 C. 1~2 D. 0～1

7. 根据一组关键字(56，42,50,64，48）依次插入结点生成一棵 AVL 树，当插入到值为（)的结点时需要进

行旋转调整。

A. 42 B. 50 C。 64 D. 48

8. 深度为 4 的 AVL 树至少有（）个结点.

A．9 B. 8 C。 7 D。 6

9. 一棵深度为 k 的 AVL 树，其每个分支结点的平衡因子均为 0,则该平衡二叉树共有（）个结点。

A。2

k—1

-1 B.2

k—1

+1 C.2

k

—1 D。2

k

10. 在 AVL 树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A，并已知 A 的左孩子的平衡因子为

0，右孩子的平衡因子为 1，则应作（）型调整以使其平衡。

A. LL B. LR C。 RL D. RR

二、判断题

1. 二叉搜索树的任意一棵子树中,关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。

2. 二叉搜索树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右

非空子树（若存在的话）所有结点的关键字值。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余8页未读，立即下载

内容反馈

matlab大师

粉丝: 2438
资源: 9万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip