**选择题：**

1. Python 中用于将列表逆序的方法是：
   a) reverse()
   b) invert()
   c) flip()
   d) rev()



2. 下列哪个关键字用于定义 Python 函数：
   a) def
   b) function
   c) define
   d) func

3. 在 Python 中，用于处理异常的关键字是：
   a) try
   b) catch
   c) print
   d) handle

4. Python 中，以下哪个模块用于处理正则表达式：
   a) regex
   b) rexp
   c) regexpy
   d) re

5. 下列哪个选项是 Python 中的真值（True）：
   a) 0
   b) "" (空字符串)
   c) None
   d) "False"

**填空题：**

6. 完成下列代码，实现一个函数 `is_prime` 判断一个正整数是否为素数。
   ```python
   def is_prime(n):
       # 请在这里填写代码
   ```

7. 编写一个 Python 程序，使用列表推导式生成一个包含前 10 个自然数的平方的列表。

8. 补充下列代码，实现一个简单的类 `Circle`，包含初始化方法 `__init__` 和计算圆面积的方法 `area`。
   ```python
   class Circle:
       def __init__(self, radius):
           # 请在这里填写代码

       def area(self):
           # 请在这里填写代码
   ```

9. 在 Python 中，如何将一个字符串转换为小写字母？

10. 编写一个 Python 函数 `multiply_elements`，接受两个列表作为参数，返回一个新列表，其中包含对应位置元素的乘积。例如，输入 `[1, 2, 3]` 和 `[4, 5, 6]`，输出 `[4, 10, 18]`

参考答案
===
**选择题参考答案：**

1. a) reverse()
2. a) def
3. c) except
4. d) re
5. d) "False" 

**填空题参考答案：**

6. 完成下列代码，实现一个函数 `is_prime` 判断一个正整数是否为素数。
   ```python
   def is_prime(n):
       if n < 2:
           return False
       for i in range(2, int(n**0.5) + 1):
           if n % i == 0:
               return False
       return True
   ```

7. 编写一个 Python 程序，使用列表推导式生成一个包含前 10 个自然数的平方的列表。
   ```python
   squares = [x**2 for x in range(1, 11)]
   ```

8. 补充下列代码，实现一个简单的类 `Circle`，包含初始化方法 `__init__` 和计算圆面积的方法 `area`。
   ```python
   import math

   class Circle:
       def __init__(self, radius):
           self.radius = radius

       def area(self):
           return math.pi * self.radius**2
   ```

9. 在 Python 中，如何将一个字符串转换为小写字母？
   ```python
   lowercase_string = original_string.lower()
   ```

10. 编写一个 Python 函数 `multiply_elements`，接受两个列表作为参数，返回一个新列表，其中包含对应位置元素的乘积。例如，输入 `[1, 2, 3]` 和 `[4, 5, 6]`，输出 `[4, 10, 18]`。
    ```python
    def multiply_elements(list1, list2):
        return [x * y for x, y in zip(list1, list2)]
    ```

python期末试题

正向最大匹配算法是一种中文分词算法，它的基本思想是从前往后遍历待分词文本，每次选择最长的词汇进行匹配。该算法的实现步骤如下：



1. **初始化：** 将待分词的文本和词典传入算法。
2. **迭代处理：** 从文本的起始位置开始，每次选择长度最长的词汇在词典中匹配。
   - 如果找到匹配的词汇，将该词汇加入分词结果，并从文本中截取匹配的部分。
   - 如果没有找到匹配的词汇，将文本的第一个字符作为单字成词加入结果，并从文本中截取一个字符。
3. **返回结果：** 当文本处理完毕后，返回最终的分词结果。

这个算法的核心思想是始终选择匹配到的最长词汇，从而实现分词的目的。

### 1. 初始化

```go
func ForwardMaximumMatching(text string, dict []string) []string {
	var result []string
```

这里定义了一个函数 `ForwardMaximumMatching`，接收待分词的文本 `text` 和词典 `dict`。

### 2. 迭代处理

```go
for len(text) > 0 {
	word := text
	for _, term := range dict {
		if len(term) > len(word) {
			continue
		}
		if word[:len(term)] == term {
			word = word[len(term):]
			result = append(result, term)
			break
		}
	}

	if len(word) == len(text) {
		_, size := utf8.DecodeRuneInString(word)
		word = word[size:]
		result = append(result, text[:size])
	}

	text = word
}
```

在这个循环中，算法从文本的起始位置开始，尝试匹配词典中最长的词汇。对于每个词汇，如果匹配成功，将该词汇加入结果，并截取匹配的部分；如果匹配不成功，则将文本的第一个字符作为单字成词加入结果，并截取一个字符。循环直到文本处理完毕。

### 3. 返回结果

```go
return result
```

最终，返回分词结果。

### 示例

```go
text := "正向最大匹配是中文分词中的一种基本算法"
dictionary := []string{"正向", "最大", "匹配", "是", "中文", "分词", "中的", "一种", "基本", "算法"}

result := ForwardMaximumMatching(text, dictionary)
fmt.Println(result)
```

以上示例演示了如何使用正向最大匹配算法对给定文本进行分词。

完整代码
===
```go
package main

import (
	"fmt"
	"unicode/utf8"
)

// ForwardMaximumMatching 使用正向最大匹配算法进行中文分词

func ForwardMaximumMatching(text string, dict []string) []string {
	var result []string

	for len(text) > 0 {
		word := text
		for _, term := range dict {
			if len(term) > len(word) {
				continue
			}
			if word[:len(term)] == term {
				word = word[len(term):]
				result = append(result, term)
				break
			}
		}

		// 处理单字成词
		if len(word) == len(text) {
			_, size := utf8.DecodeRuneInString(word)
			word = word[size:]
			result = append(result, text[:size])
		}

		text = word
	}

	return result
}

func main() {
	text := "正向最大匹配是中文分词中的一种基本算法"
	dictionary := []string{"正向", "最大", "匹配", "是", "中文", "分词", "中的", "一种", "基本", "算法"}

	result := ForwardMaximumMatching(text, dictionary)
	fmt.Println(result)
}
```

正向最大匹配算法（分词算法）

pdqsort是基于std::sort的改进算法，当数据量小的时候用插入排序，递归深度大的时候用heapsort，其他情况用改良的quicksort
```go
// pdqsort 对数据 data[a:b] 进行排序。
// 该算法基于 pattern-defeating quicksort (pdqsort)，但没有 BlockQuicksort 中的优化。
// pdqsort 论文：https://arxiv.org/pdf/2106.05123.pdf
// C++ 实现：https://github.com/orlp/pdqsort
// Rust 实现：https://docs.rs/pdqsort/latest/pdqsort/
// limit 是在陷入堆排序之前允许的坏（非常不平衡）枢轴的数量。
func pdqsort(data Interface, a, b, limit int) {
	const maxInsertion = 12



	var (
		wasBalanced    = true // 上次分区是否相当平衡
		wasPartitioned = true // 切片是否已分区
	)

	for {
		length := b - a

		if length <= maxInsertion {
			insertionSort(data, a, b)
			return
		}

		// 如果坏选择太多，就退回到堆排序。
		if limit == 0 {
			heapSort(data, a, b)
			return
		}

		// 如果上次分区不平衡，我们需要打破模式。
		if !wasBalanced {
			breakPatterns(data, a, b)
			limit--
		}

		// 选择枢轴和提示。
		pivot, hint := choosePivot(data, a, b)
		if hint == decreasingHint {
			// 反转范围，以便处理递增顺序的情况。
			reverseRange(data, a, b)
			// 选择的枢轴在数组开始后的 pivot-a 个元素。
			// 反转后，它在数组末尾前的 pivot-a 个元素。
			// 这个想法来自于 Rust 的实现。
			pivot = (b - 1) - (pivot - a)
			hint = increasingHint
		}

		// 如果切片可能已经排序，则尝试进行局部插入排序。
		if wasBalanced && wasPartitioned && hint == increasingHint {
			if partialInsertionSort(data, a, b) {
				return
			}
		}

		// 可能切片包含许多重复元素，将切片分为等于和大于枢轴的元素。
		if a > 0 && !data.Less(a-1, pivot) {
			// 如果前一个元素大于等于枢轴，则进行相等分区。
			mid := partitionEqual(data, a, b, pivot)
			a = mid
			continue
		}

		// 进行普通分区。
		mid, alreadyPartitioned := partition(data, a, b, pivot)
		wasPartitioned = alreadyPartitioned

		leftLen, rightLen := mid-a, b-mid
		balanceThreshold := length / 8
		if leftLen < rightLen {
			wasBalanced = leftLen >= balanceThreshold
			pdqsort(data, a, mid, limit)
			a = mid + 1
		} else {
			wasBalanced = rightLen >= balanceThreshold
			pdqsort(data, mid+1, b, limit)
			b = mid
		}
	}
}
```

heapsort
```go
// siftDown implements the heap property on data[lo:hi].
// first is an offset into the array where the root of the heap lies.
func siftDown(data Interface, lo, hi, first int) {
	root := lo
	for {
		child := 2*root + 1
		if child >= hi {
			break
		}
		if child+1 < hi && data.Less(first+child, first+child+1) {
			child++
		}
		if !data.Less(first+root, first+child) {
			return
		}
		data.Swap(first+root, first+child)
		root = child
	}
}

func heapSort(data Interface, a, b int) {
	first := a
	lo := 0
	hi := b - a

	// Build heap with greatest element at top.
	for i := (hi - 1) / 2; i >= 0; i-- {
		siftDown(data, i, hi, first)
	}

	// Pop elements, largest first, into end of data.
	for i := hi - 1; i >= 0; i-- {
		data.Swap(first, first+i)
		siftDown(data, lo, i, first)
	}
}

```

insertionsort
```go
// insertionSort sorts data[a:b] using insertion sort.
func insertionSort(data Interface, a, b int) {
	for i := a + 1; i < b; i++ {
		for j := i; j > a && data.Less(j, j-1); j-- {
			data.Swap(j, j-1)
		}
	}
}
```
---
参考：
https://mp.weixin.qq.com/s/8qMvwQE9p1UkEYpIR4Dg8A

pdqsort排序算法

```go
//	// INVALID: a directly-declared header will not hold Data as a reference.
//	var hdr reflect.StringHeader
//	hdr.Data = uintptr(unsafe.Pointer(p))
//	hdr.Len = n
//	s := *(*string)(unsafe.Pointer(&hdr)) // p possibly already lost
type Pointer *ArbitraryType


type ArvitraryType int

// Sizeof takes an expression x of any type and returns the size in bytes
// of a hypothetical variable v as if v was declared via var v = x.
// The size does not include any memory pos
```

指针的本质

ring实现了一个环形链表
```go
// Package ring 实现了环形链表的操作。
package ring



// Ring 是环形链表的元素。
// 环形链表没有明确定义的开头或结尾；指向环形链表的任何元素的指针都可视为对整个环形链表的引用。
// 空环形链表表示为 nil Ring 指针。Ring 的零值是一个只包含一个 nil Value 的环。
type Ring struct {
	next, prev *Ring
	Value      any // 由客户端使用；本库不会修改该值
}

// init 方法：初始化环形链表，返回链表的第一个元素。
func (r *Ring) init() *Ring {
	r.next = r
	r.prev = r
	return r
}

// Next 返回下一个环形链表元素。r 不能为空。
func (r *Ring) Next() *Ring {
	if r.next == nil {
		return r.init()
	}
	return r.next
}

// Prev 返回前一个环形链表元素。r 不能为空。
func (r *Ring) Prev() *Ring {
	if r.next == nil {
		return r.init()
	}
	return r.prev
}

// Move 将 n % r.Len() 个元素向前（n < 0）或向后（n >= 0）移动，并返回移动后的环形链表元素。r 不能为空。
func (r *Ring) Move(n int) *Ring {
	if r.next == nil {
		return r.init()
	}
	switch {
	case n < 0:
		for ; n < 0; n++ {
			r = r.prev
		}
	case n > 0:
		for ; n > 0; n-- {
			r = r.next
		}
	}
	return r
}

// New 创建包含 n 个元素的新环形链表。
func New(n int) *Ring {
	if n <= 0 {
		return nil
	}
	r := new(Ring)
	p := r
	for i := 1; i < n; i++ {
		p.next = &Ring{prev: p}
		p = p.next
	}
	p.next = r
	r.prev = p
	return r
}

// Link 连接环形链表 r 和 s，使得 r.Next() 变为 s，并返回 r.Next() 的原始值。
// r 不能为空。
//
// 如果 r 和 s 指向同一个环形链表，则连接它们将从链表中移除 r 和 s 之间的元素。
// 被移除的元素形成一个子环，结果是对该子环的引用（如果没有移除元素，则结果仍为 r.Next() 的原始值，而不是 nil）。
//
// 如果 r 和 s 指向不同的环形链表，则连接它们将创建一个单一的环形链表，其中包含 s 的元素插入到 r 之后。
// 结果指向插入后 s 的最后一个元素的下一个元素。
func (r *Ring) Link(s *Ring) *Ring {
	n := r.Next()
	if s != nil {
		p := s.Prev()
		// 注意：不能使用多重赋值，因为 LHS 的评估顺序未指定。
		r.next = s
		s.prev = r
		n.prev = p
		p.next = n
	}
	return n
}

// Unlink 从环形链表 r 中移除 n % r.Len() 个元素，从 r.Next() 开始。如果 n % r.Len() == 0，则 r 保持不变。
// 返回被移除的子环。r 不能为空。
func (r *Ring) Unlink(n int) *Ring {
	if n <= 0 {
		return nil
	}
	return r.Link(r.Move(n + 1))
}

// Len 计算环形链表 r 中的元素数量。
// 执行时间与元素数量成正比。
func (r *Ring) Len() int {
	n := 0
	if r != nil {
		n = 1
		for p := r.Next(); p != r; p = p.next {
			n++
		}
	}
	return n
}

// Do 对环形链表中的每个元素调用函数 f，按照正向顺序。
// 如果 f 改变 *r，则 Do 的行为未定义。
func (r *Ring) Do(f func(any)) {
	if r != nil {
		f(r.Value)
		for p := r.Next(); p != r; p = p.next {
			f(p.Value)
		}
	}
}

```
使用示例
```go
package main

import (
	"container/ring"
	"fmt"
)

func main() {
	// 创建一个包含 3 个元素的环形链表
	r := ring.New(3)

	// 遍历环形链表并设置元素值
	for i := 1; i <= r.Len(); i++ {
		r.Value = i
		r = r.Next()
	}

	// 遍历环形链表并打印元素值
	r.Do(func(x interface{}) {
		fmt.Print(x, " ")
	})
	fmt.Println()

	// 移动环形链表的元素，使得下一个元素成为新的第一个元素
	r = r.Move(1)

	// Link 连接两个环形链表
	s := ring.New(2)
	s.Value = 4
	r.Link(s)

	// 遍历连接后的环形链表并打印元素值
	r.Do(func(x interface{}) {
		fmt.Print(x, " ")
	})
	fmt.Println()

	// Unlink 移除环形链表中的两个元素
	unlinked := r.Unlink(2)

	// 遍历被移除的子环形链表并打印元素值
	unlinked.Do(func(x interface{}) {
		fmt.Print(x, " ")
	})
	fmt.Println()
}

```