苏州大学2009年872试题

数据结构

名词解释

循环队列

将队列想象成一个环状的空间, 即把存储队列元素的表从逻辑上看成一个环.
快速排序

基于分治的方法, 在待排序列中任取一个元素作为基准, 通过一趟排序将待排序序列分成独立的两个部分, 而
后分别递归的对两个子表重复上述过程, 直至每部分内只有一个元素或空为止, 即所有元素都放在其最终位置
上.
满二叉树** ** 一棵高度为 h,并且含有 2^(h-1) 个结点的二叉树称为满二叉树.
三元组顺序表

稀疏矩阵的一种存储方法, 用一个数组存储一个稀疏矩阵. 稀疏矩阵中非零元素的行、列和值作为一个元素存
储在数组中, 并且数组按照行从小到大、行相同列从小到大排序.
串的模式匹配

子串的定位操作。从主串的第 pos 个字符起和模式的第 1 个字符比较, 若相等, 则继续逐个比较后续字符;
否则从主串的下一个字符起再重新和模式的字比较. 以此类推, 直到模式中的每个字符依次和主串中的字符序
列相等, 则匹配成功, 否则不成功.

哈希表解决冲突

设哈希表函数为 H(k)=k mod 9, 关键字序列为: 23, 45, 14, 17, 9, 29, 37, 18, 25, 41, 33. 采用链地址法解
决冲突.

(1) 画出哈希表.

根据散列函数计算各关键字对应的 Hash 地址:

0	1	2	5	6	7	8
45	37	29	23	33	25	17
9			14
18			41

(2) 求出查找各个关键字的比较次数.

45, 37, 29, 23, 33, 25, 17 的比较次数为 1

9, 14 的比较此时为 2

18, 41 的比较此时为 3

(3) 计算在等概率情况下, 查找成功的平均查找长度.

查找成功: 指关键字在 Hash 表中, 最终能够查找出. 因此等概率指所有存在于 Hash 表中的关键字等概率.

查找失败: 指关键字不在 Hash 表中, 最终没有关键字比配. 因此等概率指对于每个 Hash 地址等概率.

查找成功的平均长度为 (1*7 + 2*2 + 3*2) / 11 = 17/11

[ 查找失败的平均查找长度: (0*2 + 1*5 + 3*2) / 9 = 11/9 ]

循环单链表交换前驱后继

def change_pre_post(node: ListNode):
    """
    已知node是循环单链表中的一个节点, 要求交换它的前驱和后继.

    先用一个指针循环单链表一遍, 直到指针指向前驱节点. 然后交换节点的前驱和后继.

    Args:
        node (ListNode): 需要更改前驱和后继的节点.
    """
    cur = node
    while cur and cur.next != node:
        cur = cur.next
    if cur and node.next:
        node.next, cur.next = cur, node.next.next

有向图邻接表的出度

class ArcNode(object):
    """
    顺序表的边节点类, 是一个链表结构的用于保存指向节点和权重的链表.
    实现了通过list初始化的功能.
    """

    def __init__(
        self, target: int = 0, weight: int = 0, next: Optional["ArcNode"] = None
    ) -> None:
        self.target = target
        self.weight = weight
        self.next = next

    @classmethod
    def init_by_list(cls, arr: List[Any]) -> Optional["ArcNode"]:
        head = ArcNode()
        cur = head
        for x in arr:
            node = ArcNode(target=x[0], weight=x[1], next=None)
            cur.next, cur = node, node
        return head.next


class VNode(object):
    """
    顺序表的节点类, 记录了当前节点的数据、出度、入度和边度单链表.
    """

    def __init__(
        self,
        data: int = 0,
        in_degree: int = 0,
        out_degree: int = 0,
        first_arc: Optional[ArcNode] = ArcNode(),
    ) -> None:
        self.data = data
        self.in_degree = in_degree
        self.out_degree = out_degree
        self.first_arc = first_arc


class ArcGraph(object):
    """
    顺序表类, 记录了边的数量和节点的数量, 以及一个节点的列表, 用于描述图的结构.
    """

    def __init__(
        self, graph: List[VNode] = [], vex: int = 0, arc: int = 0
    ) -> None:
        self.graph = graph
        self.vex_num = vex
        self.arc_num = arc


def get_in_and_out(g: ArcGraph):
    """
    根据顺序表的结构, 初始化每个节点的出度和入读.

    Args:
        g (ArcGraph): 顺序表.
    """
    for l in g.graph:
        p = l.first_arc
        while p:
            l.out_degree += 1
            g.graph[p.target - 1].in_degree += 1
            p = p.next

二叉树的繁茂度

def get_depth(t: Optional[TreeNode]) -> int:
    """
    由顶到下的递归操作, 每次取左子树和右子树中高度较大的一颗子树, 就能得到树的深度.

    Args:
        t (Optional[TreeNode]): 树

    Returns:
        int: 树的深度.
    """
    if not t:
        return 0
    if t.left or t.right:
        return max(
            0 if not t.left else 1 + get_depth(t.left),
            0 if not t.right else 1 + get_depth(t.right),
        )

    else:
        return 1


def get_width(t: Optional[TreeNode]) -> int:
    """
    遍历每一层, res取所有层宽度的最大值, 就能找到树的宽度.

    Args:
        t (Optional[TreeNode]): 树

    Returns:
        int: 树的宽度.
    """
    if not t:
        return 0
    lst = [t]
    res = 0
    while lst:
        new_lst = []
        res = max(res, len(lst))
        for node in lst:
            if node.left:
                new_lst.append(node.left)
            if node.right:
                new_lst.append(node.right)
        lst = new_lst
    return res


def get_luxuriant(t: Optional[TreeNode]) -> int:
    return get_depth(t) * get_width(t)