1. 简答题 设一组有序的关键字序列为（13，18，24，35，47，50，62，83，90），查找方法采用折半查找，要求：（1）画出折半查找的二叉判定树；（2）给出查找关键字62时需要和哪些关键字进行比较；（3）计算出查找成功时的平均查找长度。

1. (1) 折半查找的二叉判定树如下所示：

              47
            /    \
          18      83
         /  \    /  \
       13   24  62  90
             \      
             35     
             /
            50

(2) 查找关键字62时需要和47、83、62进行比较。

(3) 平均查找长度ASL = (log2n + 1)/2 = (log210 + 1)/2 ≈ 1.5。其中n为关键字的数量。因此，查找成功时的平均查找长度为1.5。

相关问题

简答题 设散列表的地址范围为0～17，散列函数为：H（K）＝K MOD 13，K为关键字。用线性探测法(di=1,2,3,4,...)处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），完成以下问题： （1）试画出构造的散列表

根据散列函数 H（K）＝K MOD 13，计算出上述关键字的散列地址如下：

10 -> 10
24 -> 11
32 -> 6
17 -> 4
31 -> 5
30 -> 4 （冲突）
46 -> 7
47 -> 8
40 -> 1
63 -> 11 （冲突）
49 -> 10 （冲突）

因为 30 的散列地址 4 已经被 17 占用了，所以按照线性探测法，依次尝试散列地址 5、6、7 等，直到找到空闲的散列地址为止。同理，对于 63 和 49，也需要依次尝试散列地址 0、1、2、3 等，直到找到空闲的散列地址。

最终得到的散列表如下图所示：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|----|----|----|----|----|----|----|----|
| | 40| | | 17| 31| 32| 46| 47| | 10| 24| | | | | | |
| | | | | 30| | | | | | 49| 63| | | | | | |

其中，每个格子存储一个关键字，空格表示该格子为空。

1. 简答题 读取一张图片，实现图像的色彩空间转换

读取一张图片并进行色彩空间转换通常涉及以下几个步骤：

1. **导入库**：首先，你需要导入相关的图像处理库，如Python的PIL（Pillow）或者OpenCV。

2. **加载图片**：使用`Image.open()`（PIL）或`cv2.imread()`（OpenCV）函数从文件系统中加载图片。

   from PIL import Image
   img = Image.open('image.jpg')
   # 或者
   import cv2
   img = cv2.imread('image.jpg', cv2.IMREAD_COLOR)

3. **选择色彩空间**：确定你想要将图片转换到哪种色彩空间，比如RGB、HSV、灰度等。PIL库可以直接操作色彩空间，而OpenCV则需要先将其转换。

4. **转换色彩空间**：对于PIL，可以使用`.convert()`方法；对于OpenCV，你可以使用`cv2.cvtColor()`函数。

   # 转换为HSV色彩空间（如果目标是HSV）
   hsv_img = img.convert('HSV')

   # 或者
   hsv_img = cv2.cvtColor(img, cv2.COLOR_BGR2HSV)

5. **保存新图像**：完成转换后，用新的图像数据再次保存它。

   hsv_img.save('hsv_image.jpg')
   # 或者
   cv2.imwrite('hsv_image.jpg', hsv_img)