数据结构与算法（Python）-00/引子
|
|
|
- 侃悲 支
- 5 years ago
- Views:
Transcription
1 物理 结构 逻辑 结构 运算 -06/ 树及算法 刘云淮 北京大学大数据科学研究中心
2 目录 本章目标 树的例子 实现树 二叉堆实现的优先队列 二叉树应用 树遍历 二叉搜索树
3 本章目标 理解树数据结构及其应用 树用于实现 ADT Map 用列表来实现树 用类和引用来实现树 以递归方式实现树 用堆来实现优先队列
4 树的例子 在学习了栈 队列等线性数据结构, 以及递归算法之后 ; 本章我们来讨论一种基本的 非线性 数据结构 树 ; 树在计算机科学的各个领域中被广泛应用 操作系统 图形学 数据库管理系统 计算机网络 跟自然界中的树一样, 数据结构树也分为 : 根 枝和叶等三个部分 但一般数据结构的图示把根放在上方 叶放在下方
5 树
6 树
7 树的例子 : 生物学物种分类体系 首先我们看到分类体系是层次化的 树是一种分层结构越接近顶部的层越普遍越接近底部的层越独特界 门 纲 目 科 属 种 分类树的用法 : 辨认物种从顶端开始, 沿着箭头方向向下 门 : 脊索动物还是节肢动物? 纲 : 哺乳动物么? 目 : 食肉动物? 科 : 猫科? 属 : 猫属? 种 : 家猫!
8 树的例子 : 生物学物种分类体系 分类树的第二个特征 : 一个节点的子节点与另一个节点的子节点相互之间是隔离 独立的 猫属 Felis 和蝇属 Musca 下面都有 Domestica 的同名节点 但相互之间并无任何关联, 可以修改其中一个 Domestica 而不影响另一个 分类树的第三个特征 : 每一个叶节点都具有唯一性 可以用从根开始到达每个种的完全路径来唯一标识每个物种动物界 -> 脊索门 -> 哺乳纲 -> 食肉目 -> 猫科 -> 猫属 -> 家猫种 Animalia->Chordate->Mammal->Carnivora->Felidae->Felis->Domestica
9 树的例子 : 文件系统 :Linux
10 树的例子 : 文件系统 :Windows Windows\ Program Files\ C:\ Python27\ System32\ Fonts\ Temp\ Drivers\ Lib\ Doc\ Tools\ etc\ hosts
11 树的例子 :HTML 文档 ( 嵌套标记
12 树的例子 : 域名体系 ICANN.com.cn.name... google apple facebook edu chenbin www mail pku tsinghua ruc www www its mail
13 术语与定义 节点 Node: 组成树的基本部分每个节点具有名称, 或 键值, 节点还可以保存额外数据项, 数据项根据不同的应用而变 边 Edge: 边是组成树的另一个基本部分每条边恰好连接两个节点, 表示节点之间具有关联, 边具有出入方向 ; 每个节点 ( 除根节点 恰有一条来自另一节点的入边 ; 每个节点可以有多条连到其它节点的出边 根 Root: 树中唯一一个没有入边的节点 路径 Path: 由边依次连接在一起的节点的有序列表如 : 哺乳纲 -> 食肉目 -> 猫科 -> 猫属, 是一条路径
14 术语与定义 子节点 Children: 入边均来自于同一个节点的若干节点, 称为这个节点的子节点 父节点 Parent: 一个节点是其所有出边所连接节点的父节点 兄弟节点 Sibling: 具有同一个父节点的节点之间称为兄弟节点 子树 Subtree: 一个节点和其所有子孙节点, 以及相关边的集合 0 根 1 B 2 D E C F
15 术语与定义 叶节点 Leaf Node: 没有子节点的节点称为叶节点 层级 Level: 从根节点开始到达一个节点的路径, 所包含的边的数量, 称为这个节点的层级 如 D 的层级为 2, 根节点的层级为 0 高度 Height: 树中所有节点的最大层级称为树的高度 如右图树的高度为 2 0 根 1 B 2 D E C F
16 术语与定义 : 树的定义 1 树由若干节点, 以及两两连接节点的边组成, 并具有如下性质 : 其中一个节点被设定为根 ; 每个节点 n( 除根节点, 都恰连接一条来自 节点 p 的边,p 是 n 的父节点 ; 每个节点从根开始的路径是唯一的 如果每个节点最多有两个子节点, 这样的 树称为 二叉树 binary tree
17 术语与定义 : 树的定义 2( 递归定义 树是 : 空集 ; 或者由根节点及 0 或多个子树构成 ( 其中子 树也是树, 每个子树的根到根节点具有 边相连
18 实现树 : 嵌套列表法 首先我们尝试用 Python List 来实现二叉树树数据结构 ; 递归的嵌套列表实现二叉树, 由具有 3 个元素的列表实现 : 第 1 个元素为根节点的值 ; 第 2 个元素是左子树 ( 所以第 2 个元素是一个列表 ; 第 3 个元素是右子树 ( 所以第 3 个元素也是一个列表 以右图的示例, 一个 6 节点的二叉树 根是 mytree[0], 左子树 mytree[1], 右子树 mytree[1] 嵌套列表法的优点 子树的结构与树相同, 是一种递归数据结构 可以很容易扩展到多叉树, 仅需要增加列表元素即可
19 实现树 : 嵌套列表法 我们通过定义一系列函数来辅助操作嵌套列表 BinaryTree 创建仅有根节点的二叉树 insertleft/insertright 将新节点插入 树中作为其直接的左 / 右子节点 get/setrootval 则取得或返回根节点 getleft/rightchild 返回左 / 右子树
20 实现树 : 嵌套列表法 请画出 r 的图示 请通过图示讲解操作
21 实现树 : 节点链接法 同样可以用类似链表的节点链接法来实现树 每个节点保存根节点的数据项, 以及指向 左右子树的链接 定义一个 BinaryTree 类 成员 key 保存根节点数据项成员 left/rightchild 则保存指向左 / 右子树的引用 ( 同样是 BinaryTree 对象
22 实现树 : 节点链接法 insertleft/right 方法 过程与线性表的节点插入相似 请画出 r 的图示
23 树的应用 : 解析树 Parse Tree( 语法树 将树用于表示语言中句子, 可以分析句子的各种语法成分, 对句子的各种成分进行处理 语法分析树 主谓宾, 定状补 程序设计语言的编译 词法 语法检查 从语法树生成目标代码 自然语言处理 机器翻译 语义理解
24 树的应用 : 解析树 Parse Tree( 表达式树 我们还可以将表达式表示为树结构 叶节点保存操作数, 内部节点保存操作符 全括号表达式 ((7+3*(5-2 由于括号的存在, 需要计算 * 的话, 就必须先计算 7+3 和 5-2 表达式树的层次帮助我们了解表达式计算的优先级 越底层的表达式, 优先级越高 树中每个子树都表示一个子表达式 将子树替换为子表达式值的节点, 即可实现求值
25 树的应用 : 表达式树 下面, 我们用树结构来做如下尝试从全括号表达式构建表达式解析树 利用表达式解析树对表达式求值 从表达式解析树恢复原表达式的字符串形式 首先, 全括号表达式要分解为单词 Token 列表其单词分为括号 ( 操作符 +-*/ 和操作数 0~9 这几类 左括号就是表达式的开始, 而右括号是表达式的结束
26 树的应用 : 表达式树 从左到右扫描全括号表达式的每个单词, 依据规则建立解析树如果当前单词是 "(": 为当前节点添加一个新节点作为其左子节点, 当前节点下降, 设为这个新节点 如果当前单词是操作符 ['+','-','/','*']: 将当前节点的值设为此符号, 为当前节点添加一个新节点作为其右子节点, 当前节点下降, 设为这个新节点 如果当前单词是操作数 : 将当前节点的值设为此数, 当前节点上升返回到父节点 如果当前单词是 "": 则当前节点上升返回到父节点
27 从全括号表达式建立表达式解析树 : 图示 全括号表达式 :(3+(4*5 分解为单词表 ['(', '3', '+', '(', '4', '*', '5','',''] 创建表达式解析树过程 创建空树, 当前节点为根节点 读入 '(', 创建了左子节点, 当前节点下降 读入 '3', 当前节点设置为 3, 上升到父节 点 读入 '+', 当前节点设置为 +, 创建右子节 点, 当前节点下降
28 从全括号表达式建立表达式解析树 : 图示 创建表达式解析树过程 读入 '(', 创建左子节点, 当前节点下降 读入 '4', 当前节点设置为 4, 上升到父节点 读入 '*', 当前节点设置为 *, 创建右子节点, 当前节点下降 读入 '5', 当前节点设置为 5, 上升到父节点 读入 '', 上升到父节点
29 从全括号表达式建立表达式解析树 : 思路 从图示过程中我们看到, 创建树过程中关键的是对当前节点的跟踪 当前节点创建左右子树, 可以调用 BinaryTree.insertLeft/Right 当前节点设置值, 可以调用 BinaryTree.setRootVal 当前节点下降到左右子树, 可以调用 BinaryTree.getLeft/RightChild 但是, 当前节点上升到父节点, 这个没有方法支持! 我们可以用一个栈来记录跟踪父节点 当前节点下降时, 将下降前的节点 push 入栈 当前节点需要上升到父节点时, 上升到 pop 出栈的节点即可!
30 从全括号表达式建立表达式解析树 : 代码 分解单词空树表达式开始操作数 入栈下降 入栈下降 操作符 出栈上升 表达式结束 出栈上升
31 利用表达式解析树求值 : 思路 创建了表达式解析树之后, 我们可以用来进行表达式求值 由于 BinaryTree 是一个递归数据结构, 自然地, 可以用递归算法来处理 BinaryTree, 包括求值函数 evaluate 由前述对子表达式的描述, 可以从树的底层子树开始, 逐步向上层求值, 最终得到整个表达 式的值 求值函数 evaluate 的递归三要素 : 基本结束条件 : 叶节点是最简单的子树, 没有左右子节点, 其根节点的数据项即为子表达式 树的值 缩小规模 : 将表达式树分为左子树 右子树, 即为缩小规模 调用自身 : 分别调用 evaluate 计算左子树和右子树的值, 其基本操作是将左右子树的值依 根节点的操作符进行计算, 从而得到表达式的值
32 利用表达式解析树求值 : 思路 一个增加程序可读性的技巧 : 函数引用 import operator op= operator.add
33 利用表达式解析树求值 : 代码 缩小规模 递归调用 基本结束条件
34 树的遍历 Tree Traversals 线性数据结构中, 对其所有数据项的访问比较简单直接, 对树中所有节点进行访问的操作称为 遍历 Traversal 树的非线性特点, 使得遍历操作较为复杂, 我们按照对节点访问次序的不同来区分 3 种遍历 前序遍历 (preorder: 先访问根节点, 再递归地前序访问左子树 最后前序访问右子树 ; 中序遍历 (inorder: 先递归地中序访问左子树, 再访问根节点, 最后中序访问右子树 ; 后序遍历 (postorder: 先递归地后序访问左子树, 再后序访问右子树, 最后访问根节点
35 前序遍历的例子 : 一本书的章节阅读 Book-> Ch1-> S1.1-> S1.2-> S1.2.1-> S1.2.2-> Ch2-> S2.1-> S2.2-> S2.2.1-> S2.2.2
36 树的遍历 : 递归算法代码 树遍历的代码非常简洁! 也可以在 BinaryTree 类中实现前序遍历的方法 : 需要加入子树是否为空的判断 后序遍历和中序遍历的代码仅需要调整语句顺序 :
37 后序遍历 : 表达式求值 回顾前述的表达式解析树求值, 实际上也是一个后序遍历的过程, 只是代码没有明显表现出遍历的次序 采用后序遍历法重写表达式求值代码 : 左子树右子树 根节点
38 中序遍历 : 生成全括号中缀表达式 采用中序遍历递归算法来生成全括号中缀表达式 下列代码中对每个数字也加了括号, 请自行修改代码去除 ( 课后练习
39 优先队列 Priority Queue 在第 3 章我们学习了一种 FIFO 数据结构队列 queue 队列有一种变体称为 优先队列 银行窗口取号,VIP 客户优先级高, 可以插 到队首 操作系统中执行关键任务的进程或用户特 别指定进程在调度队列中靠前
40 优先队列 Priority Queue 优先队列的出队 dequeue 操作跟队列一样, 都是从队首出队 ; 但在优先队列内部, 数据项的次序却是由 优先级 来确定 : 高优先级的数据项排在队首, 而低优先级的数据项则排在后面 这样, 优先队列的入队操作就比较复杂, 需要将数据项根据其优先级尽量挤到队列前方 思考 : 有什么方案可以用来实现优先队列? 出队和入队的复杂度大概是多少?
41 二叉堆 Binary Heap 实现优先队列 实现优先队列的经典方案是采用二叉堆数据结构二叉堆能够将优先队列的入队和出队复杂度都保持在 O(log n 二叉堆的有趣之处在于, 其逻辑结构上象二叉树, 却是用非嵌套的列表来实现的! 最小 key 排在队首的称为 最小堆 min heap 反之, 最大 key 排在队首的是 最大堆 max heap ADT BinaryHeap 的操作定义如下 : BinaryHeap(: 创建一个空二叉堆对象 ; insert(k: 将新 key 加入到堆中 ; findmin(: 返回堆中的最小项, 最小项仍保留在堆中 ; delmin(: 返回堆中的最小项, 同时从堆中删除 ; isempty(: 返回堆是否为空 ; size(: 返回堆中 key 的个数 ; buildheap(list: 从一个 key 列表创建新堆
42 ADT BinaryHeap 的操作示例
43 用非嵌套列表实现二叉堆 为了使堆操作能保持在对数水平上, 就必须采用二叉树结构 ; 同样, 如果要使操作始终保持在对数数量级上, 就必须始终保持二叉树的 平衡 树根左右子树拥有相同数量的节点 我们采用 完全二叉树 的结构来近似实现 平衡 完全二叉树, 指每个内部节点都有两个子节点, 最多可有 1 个节点例外
44 完全二叉树的列表实现及性质 完全二叉树由于其特殊性, 可以用非嵌套列表, 以简单的方式实现, 并具有很好的性质 : 如果节点在列表中的下标为 p, 那么其左子节点下标为 2p, 右子节点为 2p+1 如果节点在列表中下标为 n, 那么其父节点下标为 n//
45 堆次序 Heap Order 所谓 堆 的特性, 是指堆中任何一个节点 x, 其父节点 p 中的 key 均小于等于 x 中的 key 这样, 符合 堆 性质的二叉树, 其中任何一条路径, 均是一个已排序数列 符合 堆 性质的二叉树, 其树根节点中的 key 最小
46 二叉堆操作的实现 二叉堆初始化 采用一个列表来保存堆数据, 其中表首下标为 0 的项无用, 但为了后面代码可以用到简单的 整数乘除法, 仍保留它 insert(key 方法 首先, 为了保持 完全二叉树 的性质, 新 key 应该添加到列表末尾 问题?
47 二叉堆操作的实现 insert(key 方法 但是, 新 key 简单地加在列表末尾, 显然无法保持 堆 次序 虽然对其它路径的次序没有影响, 但对于其到根的路径可能破坏次序 于是需要将新 key 沿着路径来 上浮 到其正确位置 注意 : 新 key 的 上浮 不会影响其它路径节点的 堆 次序
48 二叉堆操作的实现 :insert 代码 与父节点交换 沿路径向上 添加到末尾 新 key 上浮
49 二叉堆操作的实现 delmin( 方法 首先, 移走整个堆中最小的 key 位于堆首位的根节点 heaplist[1] 为了保持 完全二叉树 的性质, 用最后一个节点来代替根节点 问题?
50 二叉堆操作的实现 delmin( 方法 同样, 这么简单的替换, 还是破坏了 堆 次序 解决方法 : 将新的根节点沿着一条路径 下沉, 直到比两个子节点都小 下沉 路径的选择 : 如果比子节点大, 那么选择较小的子节点交换下沉
51 二叉堆操作的实现 :delmin 代码 交换下沉 沿路径向下 唯一子节点 返回较小的 移走堆顶 新顶下沉
52 二叉堆操作的实现 buildheap(lst 方法 : 从无序表生成 堆 我们最自然的想法是 : 用 insert(key 方法, 将无序表中的数据项逐个 insert 到堆中, 但 这么做的总代价是 O(nlog n 其实, 用 下沉 法, 能够将总代价控制在 O(n 从最后节点的父节点开始因叶节点无需下沉
53 二叉堆操作的实现 思考 : 利用二叉堆来进行排序? 堆排序 算法 :O(nlog n
54 二叉搜索树 Binary Search Tree 在 ADT Map 的实现方案中, 可以采用不同的数据结构和搜索算法来保存和查找 Key, 前面已经实现了两个方案有序表数据结构 + 二分搜索算法 散列表数据结构 + 散列及冲突解决算法 下面我们来试试用二叉搜索树保存 key, 实现 key 的快速搜索
55 二叉搜索树 Binary Search Tree:ADT Map 复习一下 ADT Map 的操作 : Map(: 创建一个空映射 put(key, val: 将 key-val 关联对加入映射中, 如果 key 已经存在, 则将 val 替换原来的旧关联值 ; get(key: 给定 key, 返回关联的数据值, 如不存在, 则返回 None; del: 通过 del map[key] 的语句形式删除 key-val 关联 ; len(: 返回映射中 key-val 关联的数目 ; in: 通过 key in map 的语句形式, 返回 key 是否存在于关联中, 布尔值
56 二叉搜索树 BST 的性质 比父节点小的 key 都出现在左子树, 比父节点大的 key 都出现在右子树 右图是一个简单的 BST, 按照 70,31,93,94,14,23,73 的顺序插入 首先插入的 70 成为树根 31 比 70 小, 放到左子节点 93 比 70 大, 放到右子节点 94 比 93 大, 放到右子节点 14 比 31 小, 放到左子节点 23 比 14 大, 放到其右 73 比 93 小, 放到其左 注意 : 插入顺序不同, 生成的 BST 也不同!
57 二叉搜索树的实现 : 节点和链接结构 需要用到 BST 和 Node 两个类,BST 的 root 成员引用根节点 Node class BinarySearchTree root 引用 TreeNode 对象 size 表示节点总个数 iter ( 以后再说
58 二叉搜索树的实现 :TreeNode 类 class TreeNode key 为键值 payload 是 value left/rightchild 另外加了个 parent 引用
59 二叉搜索树的实现 :TreeNode 类
60 二叉搜索树的实现 :BST.put 方法 put(key, val 方法 : 插入 key 构造 BST 首先看 BST 是否为空, 如果一个节点都没有, 那么 key 成为根节点 root 否则, 就调用一个递归函数 _put(key, val, root 来放置 key _put(key, val, currentnode 的算法流程 如果 key 比 currentnode.key 小, 那么 _put 到 currentnode 左子树 但如果没有左子树, 那么 key 就成为左子节点如果 key 比 currentnode.key 大, 那么 _put 到 currentnode 右子树 但如果没有右子树, 那么 key 就成为右子节点
61 二叉搜索树的实现 :_put 辅助方法 注意! 这个代码没有处理插入重复 key 的情况 其实也就是把 val 替换一下的事 递归左子树 递归右子树 随手把 setitem 做了 : 可以 myziptree['pku'] =
62 二叉搜索树的实现 : BST.put 图示 插入 key=19,currentnode 的变化过程 ( 灰色 :
63 二叉搜索树的实现 : BST.get 方法 一旦 BST 构建起来, 下一个方法就是从树中按照 key 来取 val, 即在树中找到 key 所在的节点 从 root 开始, 递归向下, 直到找到, 或者下到最底层的叶节点也未找到 get 方法 查看 root 是否存在? 调用递归函数 _get _get 方法 空引用返回 None 匹配当前节点, 成功 否则递归进入左 / 右子树
64 二叉搜索树的实现 :BST.get 方法 getitem 特殊方法 实现 val= myziptree['pku'] contains 特殊方法 实现 'PKU' in myziptree 的集合判断运算符 in
65 二叉搜索树的实现 : BST.delete 方法 有增就有减, 最复杂的 delete 方法 : 首先, 看树中有多少节点, 超过 1 个的话, 就先用 _get 找到要删除的节点, 然后调用 remove 来删除, 找不到则提示错误 ; 如果仅有 1 个节点 ( 就是只有根节点了, 那就看是否匹配根 key, 能匹配的话就删除根节 点, 匹配不了则报错 delitem 特殊方法 实现 del myziptree['pku'] 这样的语句操作 复杂在 remove 方法!
66 二叉搜索树的实现 : BST.remove 方法 从 BST 中 remove 一个节点, 还仍然保持 BST 的性质, 分以下 3 种情形 节点没有子节点 节点有 1 个子节点 节点有 2 个子节点 没有子节点的情况好办, 直接删除
67 二叉搜索树的实现 : BST.remove 方法 第 2 种情形稍复杂 : 被删节点有 1 个子节点 解决 : 将这个唯一的子节点上移, 替换掉被删节点的位置 但替换操作需要区分几种情况 : 被删节点的子节点是左? 还是右子节点? 被删节点本身是其父节点的左? 还是右子节点? 被删节点本身就是根节点?
68 BST.remove 方法 左子节点删除 右子节点删除 根节点删除 左子节点删除 右子节点删除 根节点删除
69 二叉搜索树的实现 : BST.remove 方法 第 3 种情形最为复杂 : 被删节点有 2 个子节点 这时无法简单地将某个子节点上移替换被删节点 但可以找到另一个合适的节点来替换被删节点, 这个合适节点就是被删节点的下一个 key 值 节点, 即被删节点右子树中最小的那个, 称为 后继 可以肯定这个后继节点最多只有 1 个子节点 ( 本身是叶节点, 或仅有右子树 将这个后继节点摘出来 ( 也就是删除了, 替换掉被删节点
70 二叉搜索树的实现 : BST.remove 方法 BinarySearchTree 类 :remove 方法 ( 情形 3
71 二叉搜索树的实现 : BST.remove 方法 TreeNode 类 : 寻找后继节点 findsuccessor( 调用找到最小节点 findmin( 目前不会遇到 到左下角
72 二叉搜索树的实现 : BST.remove 方法 TreeNode 类 : 摘出节点 spliceout( 摘出叶节点 目前不会遇到 摘出带右子节点的节点
73 二叉搜索树的实现 : 迭代器 作为 Python 字典, 我们可以用 for i in dict: 这样的方法枚举字典中的所有 key,adt Map 也应该实现这样的迭代器功能 BinarySearchTree 类中的 iter 方法直接调用了 TreeNode 中的同名特殊方法
74 二叉搜索树的实现 : 迭代器 TreeNode 类中的 iter 迭代器 实际上是一个递归函数, 想到上节 BinaryTree 中的 str 递归方法么? yield 是对每次迭代的返回值
75 二叉搜索树 : 算法分析 ( 以 put 方法为例 其性能决定因素在于二叉搜索树的高度 ( 最大层次, 而其高度又受数据项 key 插入顺序的影响 如果 key 的列表是随机分布的话, 那么大于和小于根节点 key 的键值大致相等, 那么 BST 的高度就是 log 2 n(n 是节点的个数, 而且, 这样的树就是平衡树, put 方法最差性能为 O(log 2 n 但 key 列表分布极端情况就完全不同 按照从小到大顺序插入的话, 如右图 这时候 put 方法的性能为 O(n 其它方法也是类似情况 如何改进? 不受 key 插入顺序的影响?
76 平衡二叉搜索树 :AVL 树的定义 我们来看看能够在 key 插入时一直保持平衡的二叉搜索树 :AVL 树 AVL 是发明者的名字缩写 :G.M. Adelson-Velskii and E.M. Landis 利用 AVL 树实现 ADT Map, 基本上与 BST 的实现相同, 不同之处仅在于二叉树的生成与维护过程 AVL 树的实现中, 需要对每个节点跟踪 平衡因子 balance factor 参数, 平衡因子是根据节点的左右子树的高度来定义的, 确切地说, 是左右子树高度差 : balancefactor = height(leftsubtree height(rightsubtree 如果平衡因子大于 0, 称为 左重 left-heavy, 小于零称为 右重 right-heavy 平衡因子等于 0, 则称作平衡
77 平衡二叉搜索树 : 平衡因子 如果一个二叉搜索树中每个节点的平衡因子都在 -1,0,1 之间 则把这个二叉搜索树称为平衡树
78 平衡二叉搜索树 :AVL 树的定义 一旦在平衡树操作过程中, 有节点的平衡因子超出此范围, 则需要一个重新平衡的过程 要保持 BST 的性质! 左子树所有节点都小于根, 右子树都大于根 如右图是一个 右重 的不平衡树 思考 : 如果重新平衡, 应该变成什么样?
79 AVL 树的性能 实现 AVL 树之前, 来看看 AVL 树是否确实能够达到一个很好的性能 我们来分析 AVL 树最差情形下的性能 : 即平衡因子为 1 或者 -1 下图列出平衡因子为 1 的 左重 AVL 树, 树的高度从 1 开始, 来看看问题规模 ( 总节点数 N 和比对次数 ( 树的高度 h 之间的关系如何?
80 AVL 树性能分析 观察上图 h= 时, 总节点数 N 的变化 : h= 1, N= 1 h= 2, N= 2= 1+ 1 h= 3, N= 4= h= 4, N= 7= 观察这个通式, 很接近斐波那契数列! 定义斐波那契数列 Fi 利用 Fi 重写 Nh 斐波那契数列的性质 :Fi/Fi-1 趋向于黄金分割 Φ 可以写出 Fi 的通式
81 AVL 树性能分析 将 Fi 通式代入到 Nh 中, 得到 Nh 的通式 上述通式只有 N 和 h 了, 我们解出 h 可见, 在最差情况下,AVL 树在总节点数为 N 的搜索中, 最多需要 1.44 log(nh 的搜索次数 可以说 AVL 树的搜索时间复杂度为 O(log n
82 AVL 树的实现 既然 AVL 平衡树确实能够改进 BST 树的性能, 避免退化情形, 我们来看看向 AVL 树插入一个新 key, 如何才能保持 AVL 树的平衡性质 首先, 新 key 必定以叶节点形式插入到 AVL 树中 叶节点的平衡因子是 0, 其本身无需重新平衡 但会影响其父节点的平衡因子 : 如果作为左子节点插入, 则父节点平衡因子会增加 1; 如果作为右子节点插入, 则父节点平衡因子会减少 1 这种影响可能随着其父节点到根节点的路径一直传递上去, 直到 : 传递到根节点为止 ; 或者某个父节点平衡因子被调整到 0, 不再影响上层节点的平衡因子为止 ( 无论从 -1 或者 1 调整到 0, 都不会改变子树高度 将 AVL 树作为 BST 树子类实现,TreeNode 中增加 balancefactor
83 AVL 树的实现 :put 方法 重新定义 _put 方法即可 调整因子 调整因子
84 AVL 树的实现 :UpdateBalance 方法 重新平衡 调整父节点因子
85 AVL 树的实现 :rebalance 重新平衡 主要手段 : 将不平衡的子树进行旋转 rotation 视 左重 或者 右重 进行不同方向的旋转, 同时更新相关父节点引用 更新旋转后被影响节点的平衡因子 如图, 是一个 右重 子树 A 的左旋转 ( 并保持 BST 性质 将右子节点 B 提升为子树的根 将旧根节点 A 作为新根节点 B 的左子节点 如果新根节点 B 原来有左子节点, 则将此节点设置为 A 的右子节点 (A 的右子节点一定有空 ( 为什么?
86 AVL 树的实现 :rebalance 重新平衡 更复杂一些的情况 : 如图的 左重 子树右旋转 旋转后, 新根节点将旧根节点作为右子节点, 但是新根节点原来已有右子节点, 需要将原有 的右子节点重新定位! 原有的右子节点 D 改到旧根节点 E 的左子节点 同样,E 的左子节点在旋转后一定有空
87 AVL 树的实现 :rotateleft 代码 综合两种右重情形 仅有两个节点需要调整因子
88 AVL 树的实现 : 如何调整平衡因子 看看左旋转对平衡因子的影响 保持了次序 ABCDE ACE 的平衡因子不变 ha/hc/he 不变主要看 BD 新旧关系
89 AVL 树的实现 : 如何调整平衡因子 我们来看看 B 的变化 新 B= ha- hc 旧 B= ha- 旧 hd 而 : 旧 hd= 1+ max(hc, he, 所以旧 B= ha- (1+ max(hc, he 新 B- 旧 B= 1+ max(hc, he- hc 新 B= 旧 B+ 1+ max(hc, he- hc; 把 hc 移进 max 函数里就有 新 B= 旧 B+ 1+ max(0, - 旧 D <==> 新 B= 旧 B+ 1- min(0, 旧 D
90 AVL 树的实现 : 更复杂的情形 下图的 右重 子树, 单纯的左旋转无法实现平衡 左旋转后变成 左重 了 左重 再右旋转, 还回到 右重 所以, 在左旋转之前检查右子节点的因子 如果右子节点 左重 的话, 先对它进行右旋转 再实施原来的左旋转 同样, 在右旋转之前检查左子节点的因子 如果左子节点 右重 的话, 先对它进行左旋转 再实施原来的右旋转
91 AVL 树的实现 :rebalance 代码 右重需要左旋 右子节点左重先右旋 左重需要右旋 左子节点右重先左旋
92 AVL 树的实现 : 操练一下 如图所示的 右重 子树如何平衡? 请图示旋转过程
93 AVL 树的实现 : 结语 经过复杂的 put 方法,AVL 树始终维持平衡性质, 这样 get 方法也始终保持 O(log n 的高性能 不过,put 方法的代价有多大? 将 AVL 树的 put 方法分为两个部分 : 需要插入的新节点是叶节点, 更新其所有父节点和祖先节点的代价最多为 O(log n 如果插入的新节点引发了不平衡, 重新平衡最多需要 2 次旋转, 但旋转的代价与问题规模无 关, 是常数 O(1 所以整个 put 方法的时间复杂度还是 O(log n 课后练习 : 从 AVL 树删除一个节点, 如何保持平衡?
94 ADT Map 的实现方法小结 我们采用了多种数据结构和算法来实现 ADT Map, 其时间复杂度数量级如下表所示 : operation Sorted List Hash Table Binary Search Tree AVL Tree put O(n O(1 -> O(n O(log 2 n -> O(n O(log 2 n get O(log 2 n O(1 -> O(n O(log 2 n -> O(n O(log 2 n in O(log 2 n O(1 -> O(n O(log 2 n -> O(n O(log 2 n del O(n O(1 -> O(n O(log 2 n -> O(n O(log 2 n
95 本章总结 本章介绍了 树 数据结构, 我们讨论了如下算法 用于表达式解析和求值的二叉树 用于实现 ADT Map 的二叉搜索树 BST 树 改进了性能, 用于实现 ADT Map 的平衡二叉搜索树 AVL 树 实现了 最小堆 的完全二叉树 : 二叉堆
PowerPoint Presentation
数据结构与算法 ( 六 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五 国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 6 章树 C 树的定义和基本术语 树的链式存储结构 子结点表 表示方法 静态 左孩子 / 右兄弟 表示法 动态表示法 动态 左孩子 / 右兄弟 表示法 父指针表示法及其在并查集中的应用
Microsoft PowerPoint - Lecture9.ppt
Chap 10. Index 1 Indexing Goals: Store large files Support multiple search keys Support efficient insert, delete, and range queries 2 Terms(1) Entry sequenced file: Order records by time of insertion.
树的非递归中序和层次遍历实现
相信大家对树的各种递归的遍历很了解, 利用递归使得代码变得简单而且比较好理解, 但是利用递归是需要代价的, 特别是当递归层次比较深的时候, 可能会导致递归栈溢出 而且递归一般运行速度比较慢, 那么这种情况下, 我们就可以采用非递归来实现, 非递归相对递归来说, 代码相对比较难理解, 而且代码量也一般比较多, 可是它的执行效率却是很不错的 在树的中序非递归遍历中需要用到栈, 在层次遍历中需要用到队列,
PowerPoint 演示文稿
数据结构与算法 ( 五 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五 国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第五章 的概念 的抽象数据类型 深度优先搜索 宽度优先搜索 的存储结构 D B A E G C H F I 二叉搜索树 堆与优先队列 Huffman 树及其应用 2 5.2
幻灯片 1
二叉树 汪小林改写 基于张铭 王腾蛟原稿 北京大学信息学院 主要内容 1. 二叉树的概念 2. 二叉树的抽象数据类型 3. 二叉树的存储结构 4. 二叉搜索树 5. 堆与优先队列 6. Huffman 树及其应用 7. 二叉树知识点总结 1 二叉树的概念 二叉树的定义及基本术语 满二叉树 完全二叉树 扩充二叉树 二叉树的主要性质 二叉树的定义 二叉树 (binary tree) 由结点的有限集合构成,
204 */ InitiateStack s ; /* s */ i = n; t = p = new node; /* */ p->data = postorder[i]; while i > q = new node; if parent[i - ] == postorder[i] S,T S
![204 */ InitiateStack s ; /* s */ i = n; t = p = new node; /* */ p->data = postorder[i]; while i > q = new node; if parent[i - ] == postorder[i] S,T S](/thumbs/51/27926443.jpg "204 */ InitiateStack s ; /* s */ i = n; t = p = new node; /* */ p->data = postorder[i]; while i > q = new node; if parent[i - ] == postorder[i] S,T S")
28 4 Vol.28 No.4 4 204 2 JOURNAL OF NANTONG VOCATIONAL UNIVERSITY Dec. 204!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! doi:0.3969/j.issn.008-5327.204.04.024 唐自立 ( 苏州大学计算机科学与技术学院, 江苏苏州 25006)
<4D F736F F D B8BDBCFE4220D7A8D2B5BBF9B4A1D3EBBACBD0C4BFCEB3CCC3E8CAF62E646F6378>
B212CC: 数据结构与算法 课程描述 0 课程基本信息 课程编号 : B212CC 课程名称 : 数据结构与算法英文名称 : Data Structures and Algorithms 英文简称 : DSA 预备课程 : 计算系统基础 离散数学授课时间 : 二年级第一学期时间分配 : 课堂教学 (48 课时 )+ 实验安排 (48 课时 )+ 课后作业与阅读 (48 课时 ) 学分数 : 3
大侠素材铺
编译原理与技术 语法制导翻译 Ⅱ 计算机科学与技术学院 李诚 22/10/2018 Announcement Tutorial on Thursday (25/10/2018) 3B201, Class time Assignment review Q & A Cheng @ Compiler Fall 2018, USTC 2 主要内容 源程序 词法分析器 token 语法分析器 分析树 语义分析
什么是函数式编程?
函数式编程 FUNCTIONAL PROGRAMMING byvoid@byvoid.com 什么是函数式编程? 真相是 从停机问题开始 Bug 假设有停机判定算法 function halting(func, input) { } return if_func_will_halt_on_input; 充分利用停机判定 function ni_ma(func) { if (halting(func,
Two Mergeable Data Structures
Two Mergeable Data Structures Disjoint-Set 并查集 & Leftist-Tree 左偏树 1 Disjoint-Set(Union-Find Set) 并查集 N distinct elements into a collection of disjoint sets. Op1: Find which set a given element belong in
试卷代号 : 座位号 中央广播电视大学 学年度第一学期 " 开放本科 " 期末考试 数据结构试题 2011 年 1 月 题号一四五总分一一 分数 得分 评卷人 一 单项选择题, 在括号内填写所选择的标号 ( 每小题 2 分, 共 1 8 分 ) 1. 执行下
试卷代号 : 1 0 1 0 座位号 中央广播电视大学 2 0 1 0 2011 学年度第一学期 " 开放本科 " 期末考试 数据结构试题 2011 年 1 月 题号一四五总分一一 分数 一 单项选择题, 在括号内填写所选择的标号 ( 每小题 2 分, 共 1 8 分 ) 1. 执行下面程序段时, s 语句的执行次数为 ( ) forcint i= 1; i
试卷代号 : 座位号 CD 中央广播电视大学 学年度第二学期 " 开放本科 " 期末考试 数据结构 ( 本 ) 试题 I 题号 - - I 二 l 三 l 四 l 总 分 分数 I I I I I I 2009 年 7 月 得分 评卷人 I I I 一
试卷代号 : 1 2 5 2 座位号 CD 中央广播电视大学 2 0 0 8-2 0 0 9 学年度第二学期 " 开放本科 " 期末考试 数据结构 ( 本 ) 试题 I 题号 - - I 二 l 三 l 四 l 总 分 分数 I I I I I I 2009 年 7 月 得分 评卷人 I I I 一 单项选择题 ( 每小题 2 分如 崎盯扫, 共 3t 3ω O 1. 针对线性表, 在存储后如果最常用的操作是取第
试卷代号 : 座位号 I II 中央广播电视大学 学年度第二学期 " 开放本科 " 期末考试 数据结构试题 2011 年 7 月! 题号 I - I 二 三 四! 五! 六 总分 分数 I I I 1 1- I ---1 I 得分 评卷人 一 单项选择
试卷代号 : 1 0 1 0 座位号 I II 中央广播电视大学 2 0 1 0-2 0 1 1 学年度第二学期 " 开放本科 " 期末考试 数据结构试题 2011 年 7 月! 题号 I - I 二 三 四! 五! 六 总分 分数 I I I 1 1- I ---1 I 得分 评卷人 一 单项选择题 ( 在括号内填写所选择的标号 每小题 2 分, 共 1 8 分 ) 1. 一种抽象数据类型包括数据和
演算法導入、ソート、データ構造、ハッシュ
培訓 - 1 演算法導入 ソート データ構造 ハッシュ 演算法導入 ソート データ構造 ハッシュ momohuang c2251393 chiangyo September 23, 2013 1 Schedule of the Year 1.1 Major Competition 9 12 11 10 12 10 TOI 的最 3 TOI 3 TOI 100 20 4 TOI 30 12 5 TOI
数据结构
第六讲 二叉树 孙猛 http://www.math.pku.edu.cn/teachers/sunm sunmeng@math.pku.edu.cn 2015 年 10 月 22 日 被猜价格 第一次 第二次 第三次 第四次 第五次 第六次 第七次 39 50 25 37 43 40 38 39 82 50 75 88 82 99 50 75 88 94 97 99 2 课程内容 二叉树及其抽象数据类型
SDK 概要 使用 Maven 的用户可以从 Maven 库中搜索 "odps-sdk" 获取不同版本的 Java SDK: 包名 odps-sdk-core odps-sdk-commons odps-sdk-udf odps-sdk-mapred odps-sdk-graph 描述 ODPS 基
开放数据处理服务 ODPS SDK SDK 概要 使用 Maven 的用户可以从 Maven 库中搜索 "odps-sdk" 获取不同版本的 Java SDK: 包名 odps-sdk-core odps-sdk-commons odps-sdk-udf odps-sdk-mapred odps-sdk-graph 描述 ODPS 基础功能的主体接口, 搜索关键词 "odpssdk-core" 一些
8
孙猛 http://www.math.pku.edu.cn/teachers/sunm 2017 年 10 月 26 日 1 树及其抽象数据类型 树的实现 树林林 2 树的 几种不不同表现形式 3 4 html head body meta title h1 ul h2 li li a 5 树是 n(n 0) 个结点的有限集 T,T 非空时满 足 : 有且仅有 一个特殊的称为根 (root) 的结点
运用伸展树解决数列维护问题
运用伸展树解决数列维护问题 By Crash 1 关键词 数列维护问题 伸展树 摘要 对于数列维护问题, 我们常用的一种手段是线段树 但使用线段树有一定的局限性, 本文介绍运用伸展树解决这类问题, 并且可以实现更多的功能 目录 (1) 伸展树的伸展操作 (2) 在伸展树中对区间进行操作 (3) 实例分析 NOI 2005 维护数列 (Sequence) (4) 和线段树的比较 1 Blog 地址 :http://hi.baidu.com/oimaster
2007 CS Part 05: (ONO, Kouichi)
2007 CS Part 05: (ONO, Kouichi) onono@computer.org , (expression, formula) (arithmetic expression) (logical expression, logic formula) CS (operator) ( ) (0 ) ( ) CS ( ) (arity) (unary operator) (!) (binary
第三章 栈和队列
第 3 章栈 3.1 ADT 栈 3.2 ADT 栈的实现 3.3 ADT 栈的应用 2008-3-31 福州大学数学与计算机科学学院吴英杰 1 1 栈的定义和特点 3.1 ADT 栈 (stack) 定义 : 限定仅在表首进行插入或删除操作的线性表, 表首 栈顶, 表尾 栈底, 不含元素的空表称空栈 特点 : 先进后出 (FILO) 或后进先出 (LIFO) 进栈栈顶... an... 出栈 栈
OOP with Java 通知 Project 4: 4 月 18 日晚 9 点 关于抄袭 没有分数
OOP with Java Yuanbin Wu cs@ecnu OOP with Java 通知 Project 4: 4 月 18 日晚 9 点 关于抄袭 没有分数 复习 类的复用 组合 (composition): has-a 关系 class MyType { public int i; public double d; public char c; public void set(double
<4D F736F F F696E74202D20536C FB5DACBC4D5C220CAF7D3EBB6FEB2E6CAF7205BBCE6C8DDC4A3CABD5D>
第四章树 二叉树 森林 树的基本概念 二叉树 定义 主要特征 存储结构 : 顺序 链式 遍历 线索二叉树 : 基本概念 构造 树 森林 存储结构 : 树 森林与二叉树的转换 遍历 : 树 森林 应用 二叉排序树 Huffman 树和哈夫曼编码 树和有根树 两种树 : 自由树 有根树 树 (Tree) 和森林的概念 自由树无回路的连通图 : 一棵自由树 T f 可定义为一个二元组 T f = (V,
树的基本概念 离散数学 树 南京大学计算机科学与技术系 内容提要 树的定义 树的性质 根树 有序根树的遍历 树的定义 定义 : 不包含简单回路的连通无向图称为树 森林 连通分支为树 ) 树叶 / 分支点 度为 1?) 互不同构的 6 个顶点的树 树中的通路 设 是树, 则 u,v V, 中存在唯一的 uv- 简单通路 证明 : 是连通图, u,v V, 中存在 uv- 简单通路 假设 中有两条不同的
Microsoft PowerPoint - Application of Classical Trees.pptx
Yonghui Wu ACM-ICPC Asia Council Member & ICPC Asia Programming Contest 1st Training Committee Chair yhwu@fudan.edu.cn Binary Search Trees which are used to improve efficiency for search; Binary Heaps
C++ 程序设计 告别 OJ1 - 参考答案 MASTER 2019 年 5 月 3 日 1
C++ 程序设计 告别 OJ1 - 参考答案 MASTER 2019 年 月 3 日 1 1 INPUTOUTPUT 1 InputOutput 题目描述 用 cin 输入你的姓名 ( 没有空格 ) 和年龄 ( 整数 ), 并用 cout 输出 输入输出符合以下范例 输入 master 999 输出 I am master, 999 years old. 注意 "," 后面有一个空格,"." 结束,
给定一个长度为 n 包含 100 个变量的布尔公式 F, 判断 F 是否可满足是 NP-complete, 假设 P NP. 2. Multiple Choices Select One (15 problems, 2 points each) 单选题 (15 题, 每题 2 分 ) Each qu
上海科技大学 2018 年攻读硕士学位研究生 招生考试试题 科目代码 :991 考生须知 : 1. 本试卷满分为 150 分, 全部考试时间总计 180 分钟 2. 所有答案必须写在答题纸上, 写在试题纸上或草稿纸上一律无效 3. 每道题的中文部分均已翻译为英文, 考生可在中英文中任选一种语言作答 1. True or False (5 problems, 2 points each) 判断题 (5
python内存管理
Python 级内存管理 - xiaorui.cc Object-specific allocators [ int ] [ dict ] [ list ]... [ string ] Python core +3 [ Python's object allocator ]
6 tree
6 树和二叉树 董洪伟 http://hwdong.com 1 树和二叉树 主要内容一 树的类型定义二 二叉树的类型定义三 二叉树的存储结构四 二叉树的操作五 线索二叉树六 树和森林七 赫夫曼树八 树的计数 2 树的类型定义 树是一个层次结构的抽象模型 树是由具有父子关系的结点构成的 应用示例 : - 组织结构 - 文件系统 Computers R Us Sales Manufacturing R&D
PowerPoint 演示文稿
算法基础 主讲人 : 庄连生 Email: { lszhuag@ustc.edu.c } Sprig 2010,USTC 第六讲排序 内容提要 : 排序问题 堆排序算法 快速排序算法 线性时间排序 排序算法比较 2010-4-14 2 第六讲排序 内容提要 : 排序问题 堆排序算法 快速排序算法 线性时间排序 排序算法比较 2010-4-14 3 排序问题 问题描述 : 输入 : 个数的序列 a 1,
OOP with Java 通知 Project 4: 4 月 19 日晚 9 点
OOP with Java Yuanbin Wu cs@ecnu OOP with Java 通知 Project 4: 4 月 19 日晚 9 点 复习 类的复用 组合 (composition): has-a 关系 class MyType { public int i; public double d; public char c; public void set(double x) { d
7
孙猛 http://www.math.pku.edu.cn/teachers/sunm 2017 年 10 月 19 日 1 堆与优先队列列 哈夫曼树 2 介绍 一种特殊的完全 二叉树 这种 二叉树的顺序存储表示 堆 优先队列列的概念及使 用堆的实现 方法 3 每个结点的值都 小于 ( 或者都 大于 ) 它的左右 子树的根结点的值 这种 二叉树的 广度优先周游序列列顺序表示中, 用于存放结点的顺序表具有如下性质
大侠素材铺
编译原理与技术 词法分析 Ⅱ 计算机科学与技术学院李诚 13/09/2018 主要内容 记号 (token) 源程序 词法分析器 getnexttoken 语法分析器 符号表 词法分析器的自动生成 正则表达式 NFA DFA 化简的 DFA 词法分析器的生成器 Lex: flex jflex Fst lexicl nlyzer genertor 2/51 Regulr Expr to NFA 正则表达式
水晶分析师
大数据时代的挑战 产品定位 体系架构 功能特点 大数据处理平台 行业大数据应用 IT 基础设施 数据源 Hadoop Yarn 终端 统一管理和监控中心(Deploy,Configure,monitor,Manage) Master Servers TRS CRYSTAL MPP Flat Files Applications&DBs ETL&DI Products 技术指标 1 TRS
PowerPoint 演示文稿
数据结构与算法 ( 五 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五 国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg A 的概念 第五章 B C 的抽象数据类型 深度优先搜索 宽度优先搜索 的存储结构 D E G H F I 二叉搜索树 堆与优先队列 Huffman 树及其应用 2 5.1
【附件：社群─申請表】（社群層級） 【四-四-五-1】
附 件 : 社 群 申 請 表 ( 社 群 層 級 ) 四 - 四 - 五 -1 高 雄 市 辦 理 十 二 年 國 民 基 本 教 育 精 進 國 中 小 教 學 品 質 計 畫 湖 內 區 明 宗 國 小 辦 理 103 年 度 教 師 專 業 學 習 社 群 ---- 環 境 教 育 議 題 社 群 名 稱 環 境 教 育 議 題 -- 風 華 再 現 的 二 仁 溪 召 集 人 或 聯 絡
樹
HW3 今天出爐. 加油! 樹 2 Michael Tsai 2012/3/27 HW2 星期四 due. 下周放假. 下下周上課. 嚇嚇嚇周期中考! 2 期中考 (4/17)!! 我的想法 : 關書 A4 大小一張, 雙面, 抄到你開心為止 ( 期末考沿用 ) 禁止使用放大鏡 顯微鏡 ( 供過小字體辨識用 ) XD 題目可能有 是非題 ( 並解釋原因 ) 填空題 問答題 ( 寫 algorithm,
2018 年天津城建大学攻读硕士学位研究生入学考试试题 (A) 卷 考试科目代码 :825 考试科目名称工程信息技术 招生专业 : 建筑与土木工程
一 单项选择题 ( 本题共 20 小题, 每题 2 分, 共 40 分 ) 1. 计算机所处理的数据一般具有某种内在联系, 这是指 ( ) A. 数据和数据之间存在某种联系 B. 数据项和数据项之间存在某种联系 C. 元素内部具有某种结构 D. 元素和元素之间存在某种联系 2. 在计算机中表示数据时, 数据的物理地址和逻辑地址相同并且连续, 称其为 ( ) A. 链式存储结构 B. 顺序存储结构 C.
Microsoft Word - 097119012001.htm
097 年 度 11901 電 腦 軟 體 設 計 (JAVA) 乙 級 技 術 士 技 能 檢 定 學 科 測 試 試 題 本 試 卷 有 選 擇 題 80 題, 每 題 1.25 分, 皆 為 單 選 選 擇 題, 測 試 時 間 為 100 分 鐘, 請 在 答 案 卡 上 作 答, 答 錯 不 倒 扣 ; 未 作 答 者, 不 予 計 分 准 考 證 號 碼 : 姓 名 : 單 選 題 :
OOP with Java 通知 Project 3: 3 月 29 日晚 9 点 4 月 1 日上课
OOP with Java Yuanbin Wu cs@ecnu OOP with Java 通知 Project 3: 3 月 29 日晚 9 点 4 月 1 日上课 复习 Java 包 创建包 : package 语句, 包结构与目录结构一致 使用包 : import restaurant/ - people/ - Cook.class - Waiter.class - tools/ - Fork.class
离散数学
The number of spanning trees longhuan@sjtu.edu.cn 树的刻画 树 (Tree): 连通无环图 树的例子 : TT 1 TT 2 TT 3 3 叶子 (leaf) 叶子 (leaf): 图 GG 中度数为 1 的顶点被称为叶子或终点 (end-vertex) 引理 : 对任意树 TT, 如果 TT 2, 则 TT 必含有至少两个终点 证明 : 取 TT
Microsoft PowerPoint - 6-.pptx
基本概念 树的存储结构 树的线性表示 树的遍历 二叉树 二叉树的存储表示 二叉树的各种遍历 线索化二叉树 堆 计算二叉树的数目 二叉树的应用 : 霍夫曼树和霍夫曼编码 本章小结 6.1 基本概念 树是由一个或多个结点组成的有限集 T, 它满足下面两个条件 : 有一个特定的结点, 称之为根结点 ; 其余的结点分成 m (m 0) 个互不相交的有限集 T 0, T 1,, T m-1 其中每个集合又都是一棵树,
数据结构
9 查找 董洪伟 http://hwdong.com 主要内容 查找的概念 线性查找表 线性查找 折半查找 索引查找 ( 分块查找 ) 二叉查找树 ( 平衡二叉树 ) 二叉查找树 平衡二叉树 哈希查找 ( 散列查找 ) 查找的概念 查找 : 在数据集合中寻找满足某种条件的数据元素 关键字 相当于排序中的排序码 数据元素中某个数据项的值 可以标识一个数据元素 关键字可以相同, 即不一定唯一标识这个元素
重 庆 邮 电 大 学
机密 启用前 重庆邮电大学 2019 年攻读硕士学位研究生入学考试试题 科目名称 : 数据结构 (A) 科目代码 : 802 考生注意事项 1 答题前, 考生必须在答题纸指定位置上填写考生姓名 报考单位和考生编号 2 所有答案必须写在答题纸上, 写在其他地方无效 3 填 ( 书 ) 写必须使用 0.5mm 黑色签字笔 4 考试结束, 将答题纸和试题一并装入试卷袋中交回 5 本试题满分 150 分,
Microsoft PowerPoint - 06.ppt
第 6 章树和二叉树 6.1 树的基本概念 6.2 二叉树概念和性质 6.3 二叉树存储结构 6.4 二叉树的遍历 6.5 二叉树的基本操作及其实现 6.6 二叉树的构造 6.7 哈夫曼树 本章小结 6.1 树的基本概念 6.1.1 树的定义形式化定义 : 树 :T={D,R} D 是包含 n 个结点的有穷集合 (n 0) 当 n=0 时为空树, 否则关系 R 满足以下条件 : 有且仅有一个结点 d
Computer Engineering and Applications 计算机工程与应用 07,53(9) 63 一种新型有序数据结构 : 容量平衡三叉查找树 徐懿彬, 徐学荣 XU Yibin, XU Xuerong. 福建省福州第八中学, 福州 350004. 福建农林大学, 福州 35000.Fuzhou No.8 Secondary School, Fuzhou 350004,China.Fujian
2009
数据结构 考研真题及解答 目 录 2009 年试题... 1 填空题... 1 解答题... 2 2010 年试题... 2 填空题... 2 解答题... 4 2011 年试题... 4 填空题... 4 解答题... 5 2012 年试题... 6 填空题... 6 解答题... 7 2013 年试题... 8 填空题... 8 解答题... 9 2014 年试题... 10 填空题... 10
四 读算法 ( 每题 7 分, 共 14 分 ) 1. (1) 查询链表的尾结点 (2) 将第一个结点链接到链表的尾部, 作为新的尾结点 (3) 返回的线性表为 (a 2,a 3,,a n,a 1 ) 2. 递归地后序遍历链式存储的二叉树 五 法填空 ( 每空 2 分, 共 8 分 ) true B
数据结构试卷 ( 一 ) 参考答案 一 选择题 ( 每题 2 分, 共 20 分 ) 1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 二 填空题 ( 每空 1 分, 共 26 分 ) 1. 正确性 易读性 强壮性 高效率 2. O(n) 3. 9 3 3 4. -1 3 4 X * + 2 Y * 3 / - 5. 2n n-1 n+1 6. e 2e 7. 有向无回路
湖北工业大学二 八年招收硕士学位研究生试卷 则从顶点 A 出发进行深度优先遍历可以得到的序列是 : A.ACEDBFG B.ACDGFBE C.AECDBGF D.ABDGFEC 9 在对 n 个元素的序列进行排序时, 堆排序所需要的附加存储空间是 ( ) A. O(log 2 n) B. O(1)
二 八年招收硕士学位研究生试卷 试卷代号 917 试卷名称数据结构 1 试题内容不得超过画线范围, 试题必须打印, 图表清晰, 标注准确 2 考生请注意 : 答案一律做在答题纸上, 做在试卷上一律无效 一 单项选择题 ( 在每小题列出四个供选择的答案 A B C D 中, 选一个正确的答案, 将其代号填在答卷纸相应题号后的下横线上, 每小题 2 分, 共 20 分 ) 1 以下术语与数据的存储结构无关的是(
1 1 大概思路 创建 WebAPI 创建 CrossMainController 并编写 Nuget 安装 microsoft.aspnet.webapi.cors 跨域设置路由 编写 Jquery EasyUI 界面 运行效果 2 创建 WebAPI 创建 WebAPI, 新建 -> 项目 ->
目录 1 大概思路... 1 2 创建 WebAPI... 1 3 创建 CrossMainController 并编写... 1 4 Nuget 安装 microsoft.aspnet.webapi.cors... 4 5 跨域设置路由... 4 6 编写 Jquery EasyUI 界面... 5 7 运行效果... 7 8 总结... 7 1 1 大概思路 创建 WebAPI 创建 CrossMainController
<4D F736F F F696E74202D20CAFDBEDDBDE1B9B9B8B4CFB0CCE22E707074>
数据结构与算法 58-1 计算机的算法指的是 (1), 它必须具备 (2) * A.(1) 计算方法,(2) 可执行性, 可移植性, 可扩充性 B.(1) 解决问题的步骤序列,(2) 可执行性, 确定性, 有穷性 C.(1) 排序方法,(2) 确定性, 有穷性, 稳定性 D.(1) 调度方法,(2) 易读性, 稳定性, 安全性 评价一个算法好坏的标准主要是 A 执行时间 B 辅助空间 C 算法本身的复杂度
<5B BECBB0EDB8AEC1F25D312D34B0AD5FC3E2BCAEBCF6BEF7C0DAB7E F31702E504446>
: 2 = 3 4? 0 an ordered set of unambiguous, executable steps that produces a result and terminates in a finite time (computational theory) ( ) 5 6 (C-) int min, max; float degree, b; char ch, token; /,,,
PowerPoint Presentation
数据结构与算法 ( 七 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五 国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 7 章图 7.1 图的定义和术语 7.2 图的抽象数据类型 7.3 图的存储结构 7.5 最短路径 7.6 最小生成树 2 图的遍历 (graph traversal)
樹
樹 2 Michael Tsai 2013/3/26 2 期中考 (4/16)!! 我的想法 : 關書 A4 大小一張, 雙面, 抄到你開心為止 ( 期末考沿用 ) 禁止使用放大鏡 顯微鏡 ( 供過小字體辨識用 ) XD 題目可能有 是非題 ( 並解釋原因 ) 填空題 問答題 ( 寫 algorithm, 證明題, 問 complexity) 請把答案寫清楚, 部分正確就有部分給分 作弊的直接砍頭
帝国CMS下在PHP文件中调用数据库类执行SQL语句实例
帝国 CMS 下在 PHP 文件中调用数据库类执行 SQL 语句实例 这篇文章主要介绍了帝国 CMS 下在 PHP 文件中调用数据库类执行 SQL 语句实例, 本文还详细介绍了帝国 CMS 数据库类中的一些常用方法, 需要的朋友可以参考下 例 1: 连接 MYSQL 数据库例子 (a.php)
Kubenetes 系列列公开课 2 每周四晚 8 点档 1. Kubernetes 初探 2. 上 手 Kubernetes 3. Kubernetes 的资源调度 4. Kubernetes 的运 行行时 5. Kubernetes 的 网络管理理 6. Kubernetes 的存储管理理 7.
Kubernetes 包管理理 工具 Helm 蔺礼强 Kubenetes 系列列公开课 2 每周四晚 8 点档 1. Kubernetes 初探 2. 上 手 Kubernetes 3. Kubernetes 的资源调度 4. Kubernetes 的运 行行时 5. Kubernetes 的 网络管理理 6. Kubernetes 的存储管理理 7. Kubernetes
Microsoft Word - 专升本练习5：图.doc
第五章 图 一 选择题 1. 关键路径是事件结点网络中的 ( ) A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路 2. 一个具有 n 个顶点和 e 条边的无向图, 采用邻接表表示, 表向量的大小为 ( 1 ), 所有顶点 邻接表的结点总数为 ( 2 ) 1A. n B. n+1 C. n-1 D. n+e 2A. e/2 B. e C. 2e D. n+e
一、单项选择题, 共十五小题，每小题2分，全题总分为30分
810 华南理工大学 2010 年攻读硕士学位研究生入学考试试卷 ( 请在答题纸上做答, 试卷上做答无效, 试后本卷必须与答题纸一同交回 ) 科目名称 : 物流信息基础 ( 含数据库 数据结构 ) 适用专业 : 物流工程与管理, 物流工程共 6 页说明 : 本卷分为数据库和数据结构共两部分内容, 全卷满分 150 分, 其中数据库部分满分 75 分, 数据结构满分 75 分 一. 数据库部分一. 单项选择题,
试卷代号 : 座位号 中央广播电视大学 学年度第二学期 " 开放本科 " 期末考试 数据结构试题 2012 年 7 月 题号一四五总分一一 分数 得分 评卷人 - 单项选择题, 在括号内填写所选择的标号 { 每小题 2 分, 共 1 8 分 ) 1. 下面算法
试卷代号 : 1 0 1 0 座位号 中央广播电视大学 2 0 11 2012 学年度第二学期 " 开放本科 " 期末考试 数据结构试题 2012 年 7 月 题号一四五总分一一 分数 得分 评卷人 - 单项选择题, 在括号内填写所选择的标号 { 每小题 2 分, 共 1 8 分 ) 1. 下面算法的时间复杂度为 ( ) int f( unsigned int n) { if(n= =0 II n=
PowerPoint 演示文稿
The BitCoin Scripting Language 交易实例 交易结构 "result": { "txid": "921a dd24", "hash": "921a dd24", "version": 1, "size": 226, "locktime": 0, "vin": [ ], "vout": [ ], "blockhash": "0000000000000000002c510d
6.1 树的定义和基本术语 6.2 二叉树 ( 定义 性质 存储结构 ) 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用
第六章树与二叉树 树型结构是一类非常重要的非线性结构 直观地, 树型结构是以分支关系定义的层次结构 树在计算机领域中也有着广泛的应用, 例如在编译程序中, 用树来表示源程序的语法结构 ; 在数据库系统中, 可用树来组织信息 ; 在分析算法的行为时, 可用树来描述其执行过程等等 6.1 树的定义和基本术语 6.2 二叉树 ( 定义 性质 存储结构 ) 6.3 遍历二叉树和线索二叉树 6.4 树和森林
Microsoft Word - 981192001.htm
098 年 度 11901 電 腦 軟 體 設 計 (JAVA) 乙 級 技 術 士 技 能 檢 定 學 科 測 試 試 題 本 試 卷 有 選 擇 題 80 題, 每 題 1.25 分, 皆 為 單 選 選 擇 題, 測 試 時 間 為 100 分 鐘, 請 在 答 案 卡 上 作 答, 答 錯 不 倒 扣 ; 未 作 答 者, 不 予 計 分 准 考 證 號 碼 : 姓 名 : 單 選 題 :
英美特殊关系 文化基础与历史演变
国别与地区 冯 梁 英美两国有着大致相同的文化背景 但自近代以来 英美两国的关系既不友好也不特殊 甚至还是对手 英美 特殊关系 的形成 与两国在世界 上的地位发生深刻变化有着密切联系 并在很大程度上是英国政治家刻意追求 的产物 英美 特殊关系 得以延续 主要是基于双方共同的战略利益而非单纯的文化因素 英国从 特殊关系 中得益匪浅 特别在欧洲事务上获得了仅次于 美苏的影响 但在世界其他地区 两国关系并无特殊可言
Microsoft PowerPoint - string_kruse [兼容模式]
![Microsoft PowerPoint - string_kruse [兼容模式]](/thumbs/72/67832504.jpg "Microsoft PowerPoint - string_kruse [兼容模式]")
Strings Strings in C not encapsulated Every C-string has type char *. Hence, a C-string references an address in memory, the first of a contiguous set of bytes that store the characters making up the string.
作业参考答案
本章的知识点了解 SQL 语言发展史掌握关系数据库体系结构 三层结构在关系数据库体现 ) 掌握基本表定义 包括修改 删除定义 ) 掌握视图的概念与定义 删除定义理解索引的概念与定义 删除定义总结 SQL 数据定义的特点总结用户数据查询的基本结构掌握 SELECT 子句重复元组的处理掌握 FROM 子句掌握 WHERE 子句理解更名 属性 列 ) 运算理解字符串操作理解元组显示顺序理解分组掌握聚集函数掌握空值处理理解嵌套子查询的概念
C++ 程序设计 OJ9 - 参考答案 MASTER 2019 年 6 月 7 日 1
C++ 程序设计 OJ9 - 参考答案 MASTER 2019 年 6 月 7 日 1 1 CARDGAME 1 CardGame 题目描述 桌上有一叠牌, 从第一张牌 ( 即位于顶面的牌 ) 开始从上往下依次编号为 1~n 当至少还剩两张牌时进行以下操作 : 把第一张牌扔掉, 然后把新的第一张放到整叠牌的最后 请模拟这个过程, 依次输出每次扔掉的牌以及最后剩下的牌的编号 输入 输入正整数 n(n
余鲲鹏等 旅游电子商务消费者购买意愿的影响因素研究 ｍ ｍ ｗ Ｋ ｗ ｍｍ ｍ ｗ ｍ ｗ 态下的消费者购买行为和网站经营管理理应得到 一 引言 重视 因此 本文将在对过去相关研究的回顾之 上 探寻在网络旅游信息搜寻中 网站特征对消费 在新的发展时期 旅游业作为环境友好的 低 者信任的影响 同时分
管理学 重庆理工大学学报社会科学 年第 卷第 期 Ｊ Ｃ Ｕ Ｔ Ｓ Ｓ Ｖ Ｎ ｊ 旅游电子商务消费者购买意愿的 影响因素研究 余鲲鹏郭东强 泉州师范学院 工商信息学院福建 泉州 华侨大学 工商管理学院福建 泉州 摘要 信息时代 旅游电子商务网站已成为旅游从业者与消费者信息交互的重要平台 通过信 息科技的优化强化网站的功能与内容 可提高消费者的在线浏览满意度 激发其购买意愿 以 旅游电子商务网站为研究主体
7. 下图中所使用的数据结构是 ( ) 压入 A 压入 B B 弹出 B 压入 C C A A A A A. 哈希表 B. 栈 C. 队列 D. 二叉树 8. 在 Windows 资源管理器中, 用鼠标右键单击一个文件时, 会出现一个名为 复制 的 操作选项, 它的意思是 ( ) A. 用剪切板中的
第十九届全国青少年信息学奥林匹克联赛初赛 普及组 C++ 语言试题 竞赛时间 :2013 年 10 月 13 日 14:30~16:30 选手注意 : 试题纸共有 9 页, 答题纸共有 2 页, 满分 100 分 请在答题纸上作答, 写在试题纸上的一律无效 不得使用任何电子设备 ( 如计算器 手机 电子词典等 ) 或查阅任何书籍资料 一 单项选择题 ( 共 20 题, 每题 1.5 分, 共计 30
7. 下图中所使用的数据结构是 ( ) 压入 A 压入 B B 弹出 B 压入 C C A A A A A. 哈希表 B. 栈 C. 队列 D. 二叉树 8. 在 Windows 资源管理器中, 用鼠标右键单击一个文件时, 会出现一个名为 复制 的 操作选项, 它的意思是 ( ) A. 用剪切板中的
第十九届全国青少年信息学奥林匹克联赛初赛 普及组 Pascal 语言试题 竞赛时间 :2013 年 10 月 13 日 14:30~16:30 选手注意 : 试题纸共有 9 页, 答题纸共有 2 页, 满分 100 分 请在答题纸上作答, 写在试题纸上的一律无效 不得使用任何电子设备 ( 如计算器 手机 电子词典等 ) 或查阅任何书籍资料 一 单项选择题 ( 共 20 题, 每题 1.5 分, 共计
第一章 前言
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 1 2 3 110 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 111 1 2 3 112 113 114 115 116 117 118 119 120 121 122 123 () () 124 125 126
1-5,6
作业讲解 UD 第 6 章问题 12 14 15 18 UD 第 17 章问题 11 13 14 16 18 19 ES 第 24 节练习 4 6 8 UD 第 27 章项目 3 DH 第 2 章练习 1 2 3 4 5 6 7 8 UD 第 6 章问题 12 Let S be the set of nonzero real numbers. Define a new addition on this
【此处填写课程中文名称】
数据结构 Data Structures 一 基本信息 课程代码 : 2050161 课程学分 : 4 面向专业 : 计算机科学与技术 课程性质 : 院级必修课 开课院系 : 信息技术学院计算机科学与技术系 使用教材 : 教材 数据结构 ( 第 2 版 ), 陈越等, 高等教育出版社,2016 年 6 月 参考书目 数据结构 (C 语言版 ), 李云清等, 人民邮电出版社,2009 年第二版 数据结构学习与实验指导,
数据结构与算法（Python）-00/引子
物理 结构 逻辑 结构 运算 -03/ 基本结构 刘云淮 Yunhuai.liu@pku.edu.cn http://www.yunhuai.net/dsa2018/dsa2018 北京大学大数据科学研究中心 目录 本章目标 什么是线性结构 栈 Stack 队列 Queue 双端队列 Deque 列表 List 本章目标 了解抽象数据类型 : 栈 stack 队列 queue 双端队列 deque
我 的 小 確 幸 四 : 在 第 二 份 打 工 時, 遇 到 一 位 對 我 非 常 好 的 同 事, 她 是 帶 我 的 人, 她 對 我 非 常 有 耐 性 的 教 導, 一 次 又 一 次 的 細 心 帶 領 在 這 次 的 期 中 考 前, 我 沒 上 班, 因 說 要 準 備 考 試,
我 的 小 確 幸 餐 旅 系 1021408157 林 欣 誼 這 些 小 確 幸 看 似 平 凡 無 奇, 但 在 心 中 卻 是 無 法 形 容 的 幸 福 窩 心 與 感 激 的 我 的 小 確 幸 一 : 與 家 人 一 起 在 家 就 是 一 種 小 確 幸, 從 國 小 到 高 中, 因 為 上 課 的 關 係, 不 能 在 白 天 時 與 家 人 在 一 起, 晚 上 回 家 後,
chap07.key
#include void two(); void three(); int main() printf("i'm in main.\n"); two(); return 0; void two() printf("i'm in two.\n"); three(); void three() printf("i'm in three.\n"); void, int 标识符逗号分隔,
第四章 １０２ 图 ４唱１６ 基于图像渲染的理论基础 三张拍摄图像以及它们投影到球面上生成的球面图像 拼图的圆心是相同的 而拼图是由球面图像上的弧线图像组成的 因此我 们称之为同心球拼图 如图 ４唱１８ 所示 这些拼图中半径最大的是圆 Ｃｋ 最小的是圆 Ｃ０ 设圆 Ｃｋ 的半径为 ｒ 虚拟相机水平视域为 θ 有 ｒ Ｒ ｓｉｎ θ ２ ４畅１１ 由此可见 构造同心球拼图的过程实际上就是对投影图像中的弧线图像
器之 间 向一致时为正 相反时则为负 ③大量电荷的定向移动形成电 流 单个电荷的定向移动同样形成电流 ３ 电势与电势差 １ 陈述概念 电场中某点处 电荷的电势能 Ｅ ｐ 与电荷量 ｑ Ｅｐ 的比值叫做该点处的电势 表达式为 Ｖ 电场中两点之间的 ｑ 电势之差叫做电势差 表达式为 ＵＡＢ Ｖ Ａ ＶＢ ２ 理解概念 电势差是电场中任意两点之间的电势之差 与参考点的选择无关 电势是反映电场能的性质的物理量
编译原理与技术
编译原理与技术 -- 文法和分析 2015/9/17 编译原理与技术 讲义 1 文法和分析 形式语言中若干基本概念 语言 文法 ( 上下文无关文法 ) 分析树与二义性 形式语言分类 乔姆斯基分类 2015/9/17 编译原理与技术 讲义 2 语言 语言 L={ s s 是 上任一字符串 }, s 称为语言 L 的一个句子 字母表 - 符号 / 字符的非空有限集合 e.g. 二进制数的 ={0,1},
¼ ½ ¾ ¼ ½ ¾
回归传统 历史学视野中的资本主义 刘光临 虽然明清资本主义萌芽研究和西方现代史学都使用了资本主义一词 但双方并无相同的理论背景 资本主义作为一个成熟的学科概念是由 世纪末 世纪初的历史学家和强调历史面向的政治经济学家 可简称为 德国历史学派 一起创造出来的 强调从历史而不是从抽象的理论中寻求社会变化的原因 资本主义萌芽这一概念的启用 实际上是对欧洲近代历史的严重误读 有鉴于此 在今后的中国历史研究中应该用资本主义来取代资本主义萌芽
目录 一 题目的内容及要求... 1 二 需求分析... 1 三 概要设计... 1 四 详细设计... 2 五 源代码... 7 六 运行结果及分析 七 收获及体会
程序设计实训报告 表达式求值问题 完成者 : 何炜班级 : 计科 1501 学号 :2015014278 完成日期 :2016 年 7 月 14 日星期四 1 目录 一 题目的内容及要求... 1 二 需求分析... 1 三 概要设计... 1 四 详细设计... 2 五 源代码... 7 六 运行结果及分析... 16 七 收获及体会... 17 2 一 题目的内容及要求 求解形如 (a+b)*((c+d)*e+f*h*g)
Microsoft Word - 97高二上複習考
97 學 年 度 第 一 學 期 高 二 國 文 複 習 考 - 作 答 注 意 事 項 - 考 試 時 間 :70 分 鐘 作 答 方 式 : 選 擇 題 用 2B 鉛 筆 在 答 案 卡 上 作 答, 修 正 時 應 以 橡 皮 擦 拭, 切 勿 使 用 修 正 液 非 選 擇 題 用 黑 色 或 藍 色 筆 在 答 案 卷 上 作 答 第 一 部 分 : 選 擇 題 ( 60 分 ) 壹 單
19
孙猛 http://www.math.pku.edu.cn/teachers/sunm 2017 年 12 月 21 日 1 选择排序 交换排序 2 基本思想 : 维护最 小的 i 个记录的已排序序列列 ; 每次从剩余未排序的记录中选取关键码最 小的记录, 排在已排序序列列之后, 作为序列列的第 i +1 个记录 ; 直接选择排序 堆排序 3 以空排序序列列开始 ; 每次从未排序记录中选排序码最 小的记录,
通过Hive将数据写入到ElasticSearch
我在 使用 Hive 读取 ElasticSearch 中的数据 文章中介绍了如何使用 Hive 读取 ElasticSearch 中的数据, 本文将接着上文继续介绍如何使用 Hive 将数据写入到 ElasticSearch 中 在使用前同样需要加入 elasticsearch-hadoop-2.3.4.jar 依赖, 具体请参见前文介绍 我们先在 Hive 里面建个名为 iteblog 的表,
数理逻辑 I Mathematical Logic I
前情提要 前情提要 一阶逻辑公理系统的元定理承自命题逻辑的元定理 : 演绎定理重言规则逆否命题反证法 前情提要 一阶逻辑公理系统的元定理承自命题逻辑的元定理 : 演绎定理重言规则逆否命题反证法 前情提要 一阶逻辑公理系统的元定理承自命题逻辑的元定理 : 演绎定理重言规则逆否命题反证法 前情提要 一阶逻辑公理系统的元定理承自命题逻辑的元定理 : 演绎定理重言规则逆否命题反证法 前情提要 一阶逻辑公理系统的元定理一阶逻辑特色的元定理
获取 Access Token access_token 是接口的全局唯一票据, 接入方调用各接口时都需使用 access_token 开发者需要进行妥善保存 access_token 的存储至少要保留 512 个字符空间 access_token 的有效期目前为 2 个小时, 需定时刷新, 重复
获取 Access Token access_token 是接口的全局唯一票据, 接入方调用各接口时都需使用 access_token 开发者需要进行妥善保存 access_token 的存储至少要保留 512 个字符空间 access_token 的有效期目前为 2 个小时, 需定时刷新, 重复 获取将导致上次获取的 access_token 失效 接入方可以使用 AppID 和 AppSecret
Applications: Haffman Tree 叶结点权值集合为 W={1,3,5,7} 的哈夫曼树的构造过程 可以计算出其带权路径长度为 29, 由此可见, 对于同一组给定叶结点所构造的哈夫曼树, 树的形状可能不同, 但带权路径长度值是相同的, 一定是最小的 第一步 第二步
Data Structure & Algorithm Analysis Trees & Binary Trees Zibin Zheng( 郑子彬 ) School of Data and Computer Science, SYSU http://www.inpluslab.com 课程主页 :http://inpluslab.sysu.edu.cn/dsa2016/ 1 Applications:
2. 2. 2. 3. 3. 4 6. 6. 10. 20 01 37 02 38 03 39 04 39 05 40 06 42 42.. 43.. 43 45 45 47 48 1
2. 2. 2. 3. 3. 4 6. 6. 10. 20 01 37 02 38 03 39 04 39 05 40 06 42 42.. 43.. 43 45 45 47 48 1 2 5 3 2 4 1 1 1 2 2 2 3 3 3 4 4 1 2 3 4 5 2 1 1 1 2 2 3 4 3 2 2 5 6 7 4 1. 2. 3. 4. 5 6 尙 3 尙 3 2 7 1 5 8 尙
エスポラージュ株式会社 住所 : 東京都江東区大島 東急ドエルアルス大島 HP: ******************* * 关于 Java 测试试题 ******
******************* * 关于 Java 测试试题 ******************* 問 1 运行下面的程序, 选出一个正确的运行结果 public class Sample { public static void main(string[] args) { int[] test = { 1, 2, 3, 4, 5 ; for(int i = 1 ; i System.out.print(test[i]);
Microsoft PowerPoint
书面作业讲解 TC 第 10.1 节练习 4 5 6 TC 第 10.2 节练习 1 2 3 6 TC 第 10.3 节练习 4 5 TC 第 10.4 节练习 2 3 4 TC 第 10 章问题 3 1 TC 第 10.11 节练习 4 Rewrite ENQUEUE to detect overflow. if (Q[Q.tail]!= null) 对不对? if (Q.tail == Q.head)
NethersoleJO89(8).indd
2 3 4 5 6 7 8 9 10 雅風四十六期 二零零八年九月 婆婆的愛心感動了我 陳姑娘在災區認識了白婆婆 她的家人全都在外地工 作 婆婆表示地震當日 她急忙地救了兩戶鄰舍的兩名小 孩 拖著六歲的男孩和揹著四個月大的嬰孩從災區步行兩 日後到達救援區 獲救的男孩每天都前往帳篷探望婆婆 因此她面上常帶笑容 每當白婆婆看見義工隊到災區時 都會送上暖暖的問候 更將獲配給的涼水贈予義工們 她 那真誠和熱切的關懷深深感動了義工隊
编程辑略 sosohu Blog: sosohu.github.io
编程辑略 sosohu Email: ustc.sosohu@gmail.com Blog: sosohu.github.io 前言 背景 说到程序员面试中的算法题面试, 我们不得不去做很多准备, 最简单粗暴的做法就是去刷题, 本书也就是作者在知名刷题网站 leetcode 刷题过程中针对各个算法题的解法总结以及一些基本知识的补充, 由于作者水平有限, 著作此书仅为交流, 不具备任何权威性, 有什么不正确的地方敬请指教.
******股票型证券投资基金
易 方 达 中 债 3-5 年 期 国 债 指 数 证 券 投 资 基 金 托 管 协 议 基 金 管 理 人 : 易 方 达 基 金 管 理 有 限 公 司 基 金 托 管 人 : 浙 商 银 行 股 份 有 限 公 司 目 录 一 基 金 托 管 协 议 当 事 人... 1 二 基 金 托 管 协 议 的 依 据 目 的 和 原 则... 3 三 基 金 托 管 人 对 基 金 管 理 人 的
Microsoft Word - ~7334973.doc
诺 安 中 证 创 业 成 长 指 数 分 级 证 券 投 资 基 金 托 管 协 议 基 金 管 理 人 : 诺 安 基 金 管 理 有 限 公 司 基 金 托 管 人 : 中 国 银 行 股 份 有 限 公 司 鉴 于 诺 安 基 金 管 理 有 限 公 司 是 一 家 依 照 中 国 法 律 合 法 成 立 并 有 效 存 续 的 有 限 责 任 公 司, 按 照 相 关 法 律 法 规 的
untitled
2005 1 2005 2 2005 312,507,269.15 3 2005 4 2005 99 2005 2004-6,605,310.43 1,021,528.18-0.0145 0.0010-14,245,850.97 877,258.83-0.0456 0.0010 5 2005 316,344,917.50 862,679,098.35 1.0123 1.0016-1.48% 0.10%
<4D F736F F D20B9A4D2F8B3C9B3A B0EBC4EAB1A82DC8ABCEC42E646F63>
2009 6 30 1 2 ... 2... 2... 3... 5... 5... 5... 5... 6... 6... 6... 6... 7... 8... 8... 10... 10... 11... 11... 11... 12... 12... 12... 12... 12... 13... 13... 14... 15... 16... 30... 30... 30... 31...
Microsoft Word - 教学大纲.doc
Python 快速编程入门 课程教学大纲 ( 课程英文名称 ) 课程编号 :201700810011 学 分 :5 学分 学时 :59 学时 ( 其中 : 讲课学时 41 上机学时 :18) 后续课程 :Python 高级教程适用专业 : 信息技术及其计算机相关专业开课部门 : 计算机系 一 课程的性质与目标 Python 快速编程入门 是面向计算机相关专业的一门专业基础课, 涉及 Python 语法
06-statement
PHP 基本语法 条件 循环 函数杨亮 程序的基本结构 程序 输 入 运算 (+ - x / &! ) 逻辑 ( 条件 循环 递归 ) 输出 辅助 ( 变量 数组 函数 ) 小测验 用你熟悉的程序找出 1~1000 中的所有质数 我们直接看代码好了 if else elseif 1
生成word文档
希赛网, 专注于软考 PMP 通信考试的专业 IT 知识库和在线教育平台 希赛网在线题库, 提供历年考试真题 模拟试题 章节练习 知识点练习 错题本练习等在线做题服务, 更有能力评估报告, 让你告别盲目做题, 针对性地攻破自己的薄弱点, 更高效的备考 希赛网官网 :http://www.educity.cn/ 希赛网软件水平考试网 :http://www.educity.cn/rk/ 希赛网在线题库
2005 3
Text 2009.4 hongqn@douban.com 2005 3 2.8M 1/4 20M / 500~600/sec 23 PC (1U*15/2U*8) 12 38G memcached 1U (frodo) AMD Athlon 64 1.8GHz 1G 160G SATA*2 Gentoo Linux MySQL 5 Quixote (a Python web framework)