<4D F736F F F696E74202D20CAFDBEDDBDE1B9B9B8C5C2DBA3ADB5DA38D5C2B2E9D5D22D E BBCE6C8DDC4A3CABD5D>
|
|
|
- 壁瑕 汤
- 7 years ago
- Views:
Transcription
1 数据结构概论 第 8 章查找 董黎刚浙江工商大学信电学院
2 1. 查找的基本概念
3 8.1.1 背景 第 2-7 章以数据结构为主线介绍, 第 8-9 章将以算 法为主线来介绍 现实生活中, 查找 ( 与 搜索 是同一个英文单 词 Search) 几乎无处不在, 特别是现在的网络时代, 查找占据了我们上网的大部分时间 比如要确认一下某个新词的拼写对不对, 不妨问问 baidu/google, 哪个拼写搜到的记录多就选哪个 8.1 查找的基本概念
4 8.1.1 背景 查找的第一个层次是字符 单词 语句的文本匹 配 具体说, 用于搜索的关键字与被查找的目标数 据之间文本要一致 我们之前其实已经学过一些查找方法, 比如串 的模式匹配 我们这里介绍的是这种查找 查找的第二个层次是字符 单词 语句的语意匹 配 这其实是数据挖掘 要挖掘出文本背后的含义 8.1 查找的基本概念
5 8.1.1 背景 大数据 数据挖掘的一个重要分支, 特点是基 于分布式环境, 处理海量数据, 具有实时性 典型 处理系统是基于 MapReduce 的 Hadoop 大数据查找理念上的三大转变 : 要全体不要抽样 要效率不要绝对精确 要相关不要因果要因果 8.1 查找的基本概念
6 8.1.1 背景 机器学习 使计算机具备自主学习能力, 是大数 据分析的一个主要技术 ( 这是基于人工智能, 其他还 有基于统计学等 ) 深度学习 机器学 习领域的一个重要分支, 可以完成具有高度抽象 特征的人工智能任务 8.1 查找的基本概念
7 8.1.2 基本概念 列表 : 由相同性质的数据元素 ( 或称记录 ) 组成的 集合 ( 但是不明确是什么数据结构 ) 显然, 列表就是数据对象 关键字 : 可以标识列表中的一个或一组记录的某个 数据项 如果一个关键字可以唯一标识列表中的一个记录, 则称其为主关键字, 否则就是次关键字 8.1 查找的基本概念
8 8.1.2 基本概念 8.1 查找的基本概念
9 8.1.2 基本概念 查找 (search): 在特定的列表中找到与给定关 键字值相同的记录 查找算法中要用到三类参量 : 1 查找对象 K( 找什么 ) 2 查找范围 L( 在哪找 ) 3 查找的结果 (K 在 L 中的位置 ) 其中 1 2 为输入参量, 在函数中不可缺少 3 为输出参量, 可用函数返回值表示 8.1 查找的基本概念
10 8.1.2 基本概念 对列表进行查找, 该列表就称为查找表 静态查找表 对查找表只进行查找或检索操作 检索是指找某个特定的记录的各种属性 动态查找表 在查找过程中查找表元素集合可能 动态改变 8.1 查找的基本概念
11 8.1.2 基本概念 平均查找长度 (Average Search Length,ASL): 在查找时, 给定关键字值需要比较次数的期望值 对于长度为 n 的列表, 查找成功的 ASL 为 : n ASL = i= 1 p c i i 其中 p i 为查找列表中第 i 个记录的概率,c i 为找到列表 中第 i 个记录时, 需要的关键字比较次数 对于查找不成功的 ASL, 需要具体情况具体分析 8.1 查找的基本概念
12 8.1.3 查找算法的分类 比较式查找法 ( 待查记录与列表中记录进行比较 ) 基于线性表的查找, 包括顺序查找 分块查找找和折半查找 基于树的查找 计算式查找法 ( 根据待查记录, 计算其在列表中 位置 ) 就是指哈希查找 8.1 查找的基本概念
13 2. 基于线性表的查找法 顺序查找和分块查找找
14 8.2.1 背景 基于线性表的查找 一般线性结构上的查找, 用顺序查找法 ( 或称 线性查找 ) 索引结构上的查找, 用分块查找法 有序顺序表上的查找, 用折半查找法 8.2 基于线性表的查找法 顺序查找和分块查找
15 8.2.1 背景 比如你要在一个小学里找一个学生个学生, 可以从一年 级 1 班开始, 然后 2 班,, 然后二年级 1 班,2 班, 这就是顺序查找 效率可以提高! 我们发现不同年级的学生的出生年月有严格限制, 即当年 9 月 1 日到第二年 8 月 31 日, 因此你只要按照 待查学生的年龄到某个年级进行顺序查找 这就是 分块查找 而这个按年龄划分年级的结构就是索引 结构 8.2 基于线性表的查找法 顺序查找和分块查找
16 8.2.2 顺序查找法 顺序查找法 (Sequential Search) 思想 : 用所 给关键字与线性表中各元素的关键字逐个比较, 直 到成功或失败 比如, 在下面列表中查找关键字 22 可以适用于顺序表或者链表 8.2 基于线性表的查找法 顺序查找和分块查找
17 8.2.2 顺序查找法 C 语言定义 ( 用顺序表 ) #define LIST_SIZE 20 // 记录数目 typedef int KeyType; typedef struct { KeyType key; OtherType other data; }RecordType; typedef struct { RecordType r[list_size+1]; int length; }RecordList; 8.2 基于线性表的查找法 顺序查找和分块查找
18 8.2.2 顺序查找法 顺序查找法 ( 有监视哨 ) 的动画 8.2 基于线性表的查找法 顺序查找和分块查找
19 8.2.2 顺序查找法 算法 : 顺序表上的顺序查找法 ( 有监视哨 ) int SeqSearch(RecordList l, KeyType k)/* 在顺序表 l 中顺序查找其关键字等于 k 的元素, 若找到, 则函数值为该元素在表中的位置, 否则为 0*/ { l.r[0].key=k; i=l.length; length; Sentinel) while(l.r[i].key!=k) i--; 哨 return(i); } l.r[0] 为监视哨 ( 或称哨兵, Sentinel), 可以起到防止越界的作用 有了监视哨, 在循环中就能省去判定下标越界的条件 i 1, 从而节省比较的时间 8.2 基于线性表的查找法 顺序查找和分块查找
20 8.2.2 顺序查找法 算法 : 顺序表上的顺序查找法 ( 无监视哨 ) int SeqSearch(RecordList l,keytype k)/* 不用监视哨法, 在顺序表中查找关键字等于 k 的元素 */ { l.r[0].key=k; i=l.length; while(i>=1&&l.r[i].key!=k) i--; if(i>=1) return(i); else } return(0); 8.2 基于线性表的查找法 顺序查找和分块查找
21 8.2.2 顺序查找法 n=11 顺序查找法的平均查找长度 假设列表长度为 n, 那么查找第 i 个记录时需进行 n-i+1 次比较 ( 比如查找 第 1 个元素需要比较 n 次, 查找第 n 个元素需要比较 1 次 ), 即 c i =n-i+1 又假设查找每个记录的概率相等, 即 p i =1/n, 则查找成功的平均查找长度为 : ASL n i= 1 = p c i i = 1 n n +1 = ( n i+ 1) = n = 2 1 n c i n i = 基于线性表的查找法 顺序查找和分块查找 i 1
22 8.2.2 顺序查找法 顺序查找的优点是算法简单, 且对表的结构无任 何要求, 缺点是查找效率低, 因此, 当 n 较大时不 宜采用顺序查找 如何提高查找效率? 方法 1: 将表中结点按查找概率由小到大存放, 以便提高顺序查找的效率 方法 2: 每当查找成功, 就将找到的结点和其后继 ( 若存在 ) 结点交换 8.2 基于线性表的查找法 顺序查找和分块查找
23 8.2.3 分块查找法 分块查找法 (Blocking Search) 又称索引顺序 查找, 是基于索引结构的查找 索引结构 ( 块内无序, 块间有序 ) 第 1 块 第 2 块 第 3 块 8.2 基于线性表的查找法 顺序查找和分块查找
24 8.2.3 分块查找法 分块查找法的动画 8.2 基于线性表的查找法 顺序查找和分块查找
25 8.2.3 分块查找法 平均查找长度 :ASL bs =L B +L W 其中, 查找索引表时的平均查找长度为找长度为 L B B, 在相应 块内进行顺序查找的平均查找长度 L W 8.2 基于线性表的查找法 顺序查找和分块查找
26 8.2.3 分块查找法 假定将长度为 n 的列表分成 b 块, 且每块含 s 个元 素, 则 b=n/s n=13 b=3 s=5 索引表内 L B b s 1 b s + 1 = j = 块内 LW = j = b j = 1 2 s i = 1 2 b+ s 1 n + = + 1 = ( + s) s AST = L + L 1 bs B W 8.2 基于线性表的查找法 顺序查找和分块查找
27 8.2.3 分块查找法 与顺序查找相比的优点? 分块查找不仅查找效率提高找效率提高, 而且表中插入或删除记录也比较方便 ( 因为只需要移动块内的记 录 ) 分块查找的主要代价是增加一个索引表的存储 空间和将初始表分块排序的运算 因为索引表本身有序, 当其长度较大时还可以对索引表进行折半查找以进一步提高查找效率 8.2 基于线性表的查找法 顺序查找和分块查找
28 3. 基于线性表的查找法 折半查找
29 8.3.1 背景 顺序查找指采用逐个比较查找 效率较低, 适合于 在小规模且存放无规律的线性表 在部分有序 ( 所谓 分块有序 ) 的列表中, 通过 建立索引表而使用分块查找 对于有序顺序表 ( 有序和顺序表两个条件必不可少 ) 采用折半查找法 ( 又称为二分查找法,Binary Search) 速度最快 比如, 列表中有 1 万条记录, 顺序查找平均需做 5000 次比较 ; 如果分成 100 块, 每块中含 100 条记录, 分块查找平均需要做 100 次比较 ; 而折半查找最多需 14 次比较 (2 14 =16384) 8.3 基于线性表的查找法 折半查找
30 8.3.2 折半查找法思想 将表中间位置记录的关键字与查找关键字比较, 如果两者相等, 则查找成功 ; 否则将表分成前 后两个子表, 如果中间位置记 录的关键字大于查找关键字, 则进一步查找前一子 表, 否则进一步查找后一子表 重复以上过程, 直到找到满足条件的记录, 或查 找不成功 8.3 基于线性表的查找法 折半查找
31 8.3.3 折半查找法实例 用折半查找法查找 12 的过程 ( 查找成功的例子 ) low=1 low=2 mid=(low+high)/2=6 high=5 high=2 mid=(low+high)/2=3 high=mid-1=5 mid=(low+high)/2=1 mid=(low+high)/2=2, h)/2 2 找到 12 high= 基于线性表的查找法 折半查找
32 8.3.3 折半查找法实例 用折半查找法查找 50 的过程 ( 查找不成功的例子 ) low=1 mid=6 high=9<low, low=7 找不到 high=11 mid=9 low=10 mid=10 查找不成功的终止判定条件? 8.3 基于线性表的查找法 折半查找
33 8.3.3 折半查找法实例 折半查找法的动画 8.3 基于线性表的查找法 折半查找
34 8.3.4 折半查找对应的判定树 对表中每个记录的查找过程, 可用一个特殊的二 叉树 ( 称为折半查找判定树 ) 来描述 特点 : 该二叉树中的每个结点的值就是折半查 找中的 mid 值 提出判定树的目的是为了进行平均查找长度计算 8.3 基于线性表的查找法 折半查找
35 8.3.4 折半查找对应的判定树 对这个列表, 按照折半查找算法可以产生右边的判定树 ( 与记录内容无关 ) 结点中的值就是 mid 的计算值 8.3 基于线性表的查找法 折半查找
36 8.3.5 平均查找长度 查找成功的平均查找长度为 ( 以满二叉树情况估计 ) ASL n h 1 = j 1 p c 第 j 层上有 2 = j 2 j-1 个结点, n 这些结点比较次数是 j j= 1 1 n n (( 1)2 h = h + 1) i 1 n ( q 1) 根据 iq = nq n i= 1 ( q 1) 1 ((log n+ 1 = 2 1)(n + 1) + 1) n n + 1 这是大致计算公式, 对于 log n+ 1 = 2 1 具体情况有更精确的计算 n bs i i i= 基于线性表的查找法 折半查找
37 8.3.6 平均查找长度实例 对于前述 11 个记录的列表, 查找成功的平均查找长 度为 :ASL=( )/11=33/11 / 在折半查找判定树中, 查找不成功时的比较次数相当于查找下图中虚线结点的平均比较次数 假设查找各虚线结点的概 率相等, 那么查找失败时 的平均查找长度为 : ASL=( )/12 =44/ 基于线性表的查找法 折半查找
38 8.3.6 平均查找长度实例 定理 : 若折半查找判定树有 N 个元素, 则查找不成功时有 N+1 种可能 证明 : 考虑表长为 N 的有序表, 若查找不成功, 最终位置可能有三种情况 : 第一个元素之前 两个元素之间 最后一个元素之后, 因此共有 N+1 种可能情况 8.3 基于线性表的查找法 折半查找
39 4. 基于树的查找法 二叉排序树
40 8.4.1 背景 基于线性表的查找中, 顺序查找法效率低, 而折 半查找只适用顺序有序的存储结构 折半查找特别找特别 适用于那种一经建立就很少改动 而又经常需要查 找的线性表 ( 即静态查找表 ) 而对于动态查找表, 较适合用基于树的查找法 二叉排序树和平衡 ( 二叉 ) 排序树 B 树, B+ 树,B B* 树和键树等 对于采用二叉树或树作为组织形式的列表, 被统 称为树表 8.4 基于树的查找法 二叉排序树
41 8.4.2 二叉排序树的概念 二叉排序树 (Binary Sort Tree) 特点 : 左子树 根 右子树 例子 : 折半查找的判定树 GAO 排序树 名称的来源 : 中序遍历一个二叉排序 树时可以得到一个递增有序序列 CHEN LI CAO DONG HAN ZENG KE 8.4 基于树的查找法 二叉排序树
42 8.4.2 二叉排序树的概念 二叉排序树又称为二叉查找树 (Binary Search Tree, BST), 为什么? 一般情况下, 构造二叉排序树的目的并非为了 排序, 而是用它来加速查找, 这是因为在一个有 序的集合上查找通常比在无序集合上查找更快 8.4 基于树的查找法 二叉排序树
43 8.4.3 二叉排序树的插入 算法思想 : 如是空树, 则 Key 成为根, 否则如果 key 小于根, 则将 key 插入左子树, 如果 key 大于根, 则将 key 插入右子树 实例, 关键字的输入顺序为 :45,24,53,12, 53 28, 基于树的查找法 二叉排序树
44 8.4.3 二叉排序树的插入 12 插入 45 插入 如果输入顺序为 :12,24,28,45,53,90, 产生的 二叉排序树为 8.4 基于树的查找法 二叉排序树 插入
45 8.4.3 二叉排序树的插入 二叉排序树插入的动画 8.4 基于树的查找法 二叉排序树
46 8.4.4 二叉排序树的删除 删除比插入难度大, 因为从二叉排序树中删除一 个结点时, 必须保证删除后所得的二叉树仍然满足 二叉排序树的性质不变 算法思想 : 首先确定被删除的结点是否在二叉排 序树中 若不在, 则不做任何操作 ; 否则, 分三种 情况 8.4 基于树的查找法 二叉排序树
47 8.4.4 二叉排序树的删除 假设要删除的结点为 p, 并假设结点 p 是其双亲结点 f 的左孩子 ( 右孩子的情况类似 ) 情况一 : 若 p 为叶结点, 则可直接将其删除 : 8.4 基于树的查找法 二叉排序树
48 8.4.4 二叉排序树的删除 情况二 : 若 p 结点只有左子树, 或只有右子树 : 8.4 基于树的查找法 二叉排序树
49 8.4.4 二叉排序树的删除 情况三 : 若 p 既有左 子树, 又有右子树, 则处理的方法有多种 : s 是 p 的中序 前继 8.4 基于树的查找法 二叉排序树
50 8.4.4 二叉排序树的删除 二叉排序树删除的动画 8.4 基于树的查找法 二叉排序树
51 8.4.5 二叉排序树的查找 思路与插入类似, 下面是递归算法 BSTree SearchBST(BSTree bst, KeyType yyp key) { if(!bst) return NULL; else if(bst >key==key) return bst;/* 查找成功 */ else if(key < bst >key) } 递归转换成非递归的方法? 方法 1. 递归的从顶向下改成 一般循环的自底向上 方法 2. 用户自定义栈 return SearchBST(bst >lchild, key);// 在左子树继续找 else return SearchBST(bst >rchild, key);// 在右子树继续找 8.4 基于树的查找法 二叉排序树
52 8.4.5 二叉排序树的查找 BSTree SearchBST(BSTreebst, KeyType key) { BSTree q=bst; while(q) { if(q >key==k) k) return q;/* 查找成功 */ if(key< q >data.key) q=q >lchild;/* 在左子树中查找 */ else q=q >rchild; /* 在右子树中查找 */ } return NULL;/* 查找失败 */ } 8.4 基于树的查找法 二叉排序树 这是非递归算法, 为什么这次从递归 到非递归转化这么简单? 因为这里不需要从底层到顶层的回溯
53 8.4.6 二叉排序树的评价 查找算法的性能与折半查找类似, 与关键字比较的次数不超过树的深度 12 可以证明, 平均查找长度是 O(log 2 n) 二叉排序树的具体查找长度与二叉排 序树的形态有关, 二叉排序树的各分 支越均衡越好, 树的深度浅, 其平均 查找长度越小 基于树的查找法 二叉排序树
54 5. 基于树的查找法 平衡二叉树
55 8.5.1 背景 AVL 树是最先发明的平衡二叉查找 树 (1962 年 ) AVL 树得名于它的发明者 前苏 联的 GM G.M. Adelson-Velsky (1922 ) 和 E.M. Landis AVL 查找 插入和删除在平均和最 坏情况下都是 O(log 2 n) 红黑树 (red-black trees) 也是一种平衡二叉查 找树 它是在 1972 年由德国的 R. Bayer 发明的 8.5 基于树的查找法 平衡二叉树
56 8.5.2 平衡二叉排序树概念 缺省情况下, 平衡 ( 二叉 ) 查找树就是指 AVL 树 ( 或称为 AV 树 ) 平衡 ( 二叉 ) 查找树 (Balanced Binary Search Tree) 又称为平衡二叉排序树 AV 树的特征 : 左子树与右子树高度之差的绝对值 小于等于 基于树的查找法 平衡二叉树
57 8.5.2 平衡二叉排序树概念 结点的平衡因子 : 结点的左子树深度与右子树深度 之差 8.5 基于树的查找法 平衡二叉树
58 8.5.3 平衡二叉树失衡调整 插入新结点 S 后失衡, 怎么办? 调整 调整原则 : 调整前后的中序遍历结果相同 8.5 基于树的查找法 平衡二叉树
59 8.5.3 平衡二叉树失衡调整 插入新结点 S 后的失衡情况以及相应的调整方法 (1)LL 型 ( 以 B 为轴, 对 A 做了一次顺时针旋转 ) 说明 : LL 的取名是考虑新结点 S 的位置 ( 下同 ) 8.5 基于树的查找法 平衡二叉树
60 8.5.3 平衡二叉树失衡调整 (2)LR 型 ( 对 B 做一次逆时针旋转, 对 A 做一次顺 时针旋转 ) 8.5 基于树的查找法 平衡二叉树
61 8.5.3 平衡二叉树失衡调整 (3)RR 型 ( 以 B 为轴, 对 A 做了一次逆时针旋转 ) 8.5 基于树的查找法 平衡二叉树
62 8.5.3 平衡二叉树失衡调整 (4)RL 型 ( 对 B 做了一次顺时针旋转, 对 A 做了一 次逆时针旋转 ) 8.5 基于树的查找法 平衡二叉树
63 6. 基于树的查找法 B 树
64 8.6.1 背景 二叉查找树, 平衡二叉树, 红黑树都是二叉查找树 结构, 其查找时间复杂度是 O(log 2 n) 但是大规模 数据存储导致二叉查找树结构由于树的深度过大而 造成查询效率低下 如何减少树的深度? 一个基本的想法就是 : 采用多 叉树结构 m 叉排序树是二叉排序树概念的扩展, 即变成三叉 四叉..., 而 B 树是平衡二叉树概念的扩 展 8.6 基于树的查找法 B 树
65 8.6.1 背景 B 树是德国计算机专家 R. Bayer (1939 ) 和 E. M. McCreight 在 1970 年首次提出的 R. Bayer 是 B 树和红黑树的发明 人 注意,B 树有时也被写成 B- 树, 这是对 B-tree 翻译不慎造成的 8.6 基于树的查找法 B 树
66 8.6.2 m 路查找树的定义 m 路查找树又称为 m 叉 /m 阶排序树 其特点是 : 结点最多有 m 棵子树,m 1 个关键字, 其结构如 m-1 P 0 K 1 P 1 K 2 P 2 K m-1 P m-1 P i 为指向子树根结点的 指针,K i 为关键字 子树 P i 中的所有关键字 均大于 K i 小于 K i+1 子树 P i 也是 m 路查找树 右图是 3 路查找树 ( 省略了 "m" 字段 ) 8.6 基于树的查找法 B 树
67 8.6.3 B 树的定义 B 树 (Balanced Search Tree, 平衡的 m 路查找树 ) 是一种特殊的 m 路查找树, 特殊在于 : 若根结点不是叶子结点, 则至少有 2 棵子树 ; 根结点之外的所有非叶结点至少有 m/2 棵子树 ; 所有叶结点出现在同一层上 4 路 B 树 m 路 B 树中的最 + 1 大高度是 log n ceil m ( ) 基于树的查找法 B 树
68 8.6.4 B 树的插入 基本思想 : 首先, 总是把新元素插到最低层 其次, 如果最低层结点超过阶数, 则进行分裂, 把中 间的元素上移 最后, 如果中间层结点超过阶数, 则依次进行上移操 作 8.6 基于树的查找法 B 树
69 8.6.4 B 树的插入 3 阶 B 树 插入 基于树的查找法 B 树
70 8.6.4 B 树的插入 3 阶 B 树 插入 基于树的查找法 B 树
71 8.6.4 B 树的插入 3 阶 B 树 插入 基于树的查找法 B 树
72 8.6.5 B 树的生成 从空树开始, 逐个插入关键字 {37,70,12,45,90,3,24,61,53},,,,,,, 来生成 3 阶 B 树 插入 37 和 70 插入 12 插入 基于树的查找法 B 树
73 8.6.5 B 树的生成 插入 90 插入 3 插入 基于树的查找法 B 树
74 8.6.5 B 树的生成 插入 61 插入 基于树的查找法 B 树
75 8.6.5 B 树的生成 4 阶 B 树生成的动画 8.6 基于树的查找法 B 树
76 8.6.6 B 树的删除 删除底层元素 ( 即叶子结点中的元素 ) 基本思想 : 首 先, 把新元素删掉, 其次, 如果导致所在结点空了, 就把上层的元素降下来插入到非空的叶子结点 上层 的元素降下来可能会有两个后果 : 如果叶子结点超过阶数, 那么采取分裂策略 如果上层结点中元素数少于 m/2, 那么就继续 把更上层的元素降下来, 并和上层结点的兄弟结点 合在一起 如果发生超过阶数的情况, 那么采取插 入时的策略 8.6 基于树的查找法 B 树
77 8.6.6 B 树的删除 开始状态的 4 阶 B 树 删除 基于树的查找法 B 树
78 8.6.6 B 树的删除 删除 39 删除 基于树的查找法 B 树
79 8.6.6 B 树的删除 删除 基于树的查找法 B 树
80 8.6.6 B 树的删除 删除非底层元素 ( 即分支结点中的元素 ) 基本思想 : 首先, 把新元素删掉, 其次, 把该元素在中序遍历中 的前一个或后一个元素升一个上来以填补空白 这样 依次填补, 直到最底层结点 如果导致最底层结点空 了, 那么采用前述删除底层元素时的策略 8.6 基于树的查找法 B 树
81 8.6.6 B 树的删除 初始状态 删除 基于树的查找法 B 树
82 8.6.6 B 树的删除 删除 基于树的查找法 B 树
83 8.6.7 算法性能分析 以 B 树上的查找为例, 有两个基本步骤 : 在 B 树中查找结点, 每查找 1 个结点就读一次磁盘获得该结点内信息, 读磁盘次数不超过树高 h, 故 log n+1 ceil( ) 2 其时间是 O(h), 即 O( m ) ( 结点内信息读入内存后 ) 在结点内查找, 每个 结点内的关键字数目不超过 m(m 是 B 树的阶数 ), 故 其计算时间为 O(m), 总的时间是 O(mh)= 1 O(m log n + m ceil( )) 2 结点内查找所需时间远远小于读磁盘时间 8.6 基于树的查找法 B 树
84 8.6.7 算法性能分析 比较 B 树和二叉排序树的时间复杂度 查找结点 总的时间 二叉排序树 O(log 2 n) O(log 2 n) B 树 O( m ) O(m m ) 评价 B 树更好 1 log n+ log n + 1 ceil( ) ceil( ) 2 2 因此, 如果全部记录都已经存在内存中, 用二叉排序树, 否则用 B 树 8.6 基于树的查找法 B 树
85 7. 基于树的查找法 B+ 树等
86 8.7.1 背景 针对文件索引系统, 出现了 B+ 树和 B* 树 针对查找单词, 出现了键树 8.7 基于树的查找法 B+ 树等
87 8.7.2 B+ 树 三个特征 有 n 棵子树的结点中含有 n 个关键字 ;( 而 B 树是 n 棵 子树有 n-1 个关键字 ) 所有的分支结点是索引表 ( 其中含有其子树根结点 中最大 ( 或最小 ) 关键字 ), 所有元素都在叶子结 点上 ;( 而 B 树的分支结点和叶子结点都包含元素 ) 叶子结点本身依关键字的大小顺序链接 ( 而 B 树的叶子结点并没有相互链接在一起 ) 8.7 基于树的查找法 B+ 树等
88 8.7.2 B+ 树 8.7 基于树的查找法 B+ 树等
89 8.7.3 B* 树 二个特征 B* 树的分支结点具有指向兄弟结点的指针 ;( 而 B+ 树的分支结点没有兄弟结点的指针 ) B+ 树的分裂只影响原结点和父结点, 而 B* 树中 兄弟结点之间可以直接迁移数据, 从而各结点的 数据分配比较均衡, 为此 B* 树分裂产生新结点的 概率比 B+ 树要低, 空间使用率更高 B* 树的分支结点中关键字个数至少为 2m/3 ( 而 B+ 树分支结点中关键字个数至少为 m/2) 8.7 基于树的查找法 B+ 树等
90 8.7.3 B* 树 8.7 基于树的查找法 B+ 树等
91 8.7.4 键树 键树 ( keyword tree) 又称为数字查找树 (digital Search Tree) Trie 树 (trie 为 retrieve 中 间 4 个字符 ) 前缀树或字典树 是一种有序树 键树是一种特殊的查找树, 它的某个结点不是包含 一个或多个关键字, 而是只包含组成关键字的一部 分 ( 字符或数字 ) 键树特别适用于查找单词的场合 8.7 基于树的查找法 B+ 树等
92 8.7.4 键树 一个保存了 8 个键的键 树,"A", "to", "tea", "ted", "ten", "i", "in", and "inn" 8.7 基于树的查找法 B+ 树等
93 8. 计算式查找法 散列表原理 (1)
94 8.8.1 背景 散列是一种非常独特的技术 : 不以关键字的比较为 查找的基本操作, 采用直接寻址技术 查找的时间 复杂度为 O(1) 散列的应用主要是两方面 : 把关键字值转换成存储地址, 目的是为了快速 查找 本书要介绍的内容 把任意长度的输入 ( 称为原文 ) 转换成固定长度的输出 ( 称为摘要,digest), 目的是检测原文 在传输中是否出错, 以及防止对原文的篡改 8.8 计算式查找法 散列表原理 (1)
95 8.8.2 散列法和散列表的概念 散列译自 hash, 音译是 哈希 散列的意 思就是把记录分散到 n 个位置中去 散列法又称哈希法 杂凑法以及关键字地址计算法 散列法的基本思想 : 以记录的关键字为自变量, 设 计一个函数 ( 此为散列函数 ), 该函数对关键字进 行转换后, 其结果为记录的存放地址 散列表 (Hash Table) 就是按照散列法存放记录形成的结构 8.8 计算式查找法 散列表原理 (1)
96 8.8.2 散列法和散列表的概念 8.8 计算式查找法 散列表原理 (1)
97 8.8.2 散列法和散列表的概念 散列函数和散列表实散列表实 例 以工号为关键字构 造散列函数 由于工号的独一性和连 续性, 比较容易构造散列 函数 而身份证号码有独一性, 但是缺少连续性 8.8 计算式查找法 散列表原理 (1)
98 8.8.3 散列函数的构造 构造的主要原则 计算出来的地址分布均匀, 即对任一关键字 k,f(k) 对应不同地址的概率相等, 目的是尽可能减少冲突 所谓冲突 (Collision), 就是不同的关键字值通 过散列函数计算出相同的函数值, 比如上图中的 k 3 和 k 5 发生冲突的两个关键字称为该散列函数的同 义词 (Synonym) 8.8 计算式查找法 散列表原理 (1)
99 8.8.3 散列函数的构造 冲突情况与散列函数和装填因子有关 散列表的装填因子 (Load Factor)α 的定义如下 : α= 散列表中元素个数 / 散列表的长度 α 可描述散列表的装满程度 显然,α 越小, 发生 冲突的可能性越小, 而 α 越大, 发生冲突的可能性也 越大 8.8 计算式查找法 散列表原理 (1)
100 8.8.3 散列函数的构造 散列函数构造策略之一 数字分析法 : 如果事 先知道关键字集合, 可以从关键字中选出分布较均 匀的若干位, 构成散列地址 例如, 前面以工号为关键字构造散列函数 再例如, 有学生的生日数据如下 : , , , , , ,... 经分析, 第一位, 第二位, 第三位重复的可能性大, 取这三位造成冲突的机会增加, 所以尽量不取前三位, 取后三位来构造散列函数比较好 8.8 计算式查找法 散列表原理 (1)
101 8.8.3 散列函数的构造 散列函数构造策略之二 平方取中法 : 当无法 确定关键字中哪几位分布较均匀时, 可以先求出关 键字的平方值, 然后按需要取平方值的中间几位作 为散列地址 例如, 将一组关键字 (0100,0110,1010,1001, 0111) 平方后得 ( , , , , ), ) 若取表长为 1000, 则可取中间的三位数作为散列地址集 : (100,121,201, 020,123) 8.8 计算式查找法 散列表原理 (1)
102 8.8.3 散列函数的构造 散列函数构造策略之三 分段叠加法 : 这种方 法是按散列表地址位数将关键字分成位数相等的几 部分 ( 最后一部分可以较短 ), 然后将这几部分相 加, 舍弃最高进位后的结果就是散列地址 例如 : 每一本书都有编号, 比如 , ) 04 +) 移位法 H(key)=0088 折叠法 H(key)= 计算式查找法 散列表原理 (1)
103 8.8.3 散列函数的构造 散列函数构造策略之四 除留余数法 : 假设散 列表长为 m,p 为小于等于 m 的最大素数, 则散列函 数为 :H(k)=k%p, 其中 % 为模 p 取余运算 例如, 设关键字为 :15, 14, 28, 26, 56, 23 H(15)=15 MOD 7=1 H(15)=15 MOD 13=2 H(14)=14 MOD 7=0 H(28)=28 MOD 7=0 H(14)=14 MOD 13=1 H(28)=28 MOD 13=2 H(26)=26 MOD 7=5 H(56)=56 MOD 7=0 H(26)=26 MOD 13=0 H(56)=56 MOD 13=4 H(23)=23 MOD 7=2 H(23)=23 MOD 13= 计算式查找法 散列表原理 (1)
104 8.8.3 散列函数的构造 H(k)=k%p, 其中 p 要用素数, 为什么? 如果 k 是随机分布的整数, 那么 k 只要取到足够大, 在概率上来说,p 取素数或合数都是一样的 但是在一些应用中, 不取素数有风险 比如,p 取合数为 a*x, 如果 k 正好跟这个约数 x 存在关系, 最坏情况假设都为 x 的倍数 ( 即 b*x), 那么可以想象 hash 的结果为 :0,1,2,,(a 12 (a-1) 1), 而不是 0~p 计算式查找法 散列表原理 (1)
105 8.8.3 散列函数的构造 散列函数构造策略之五 伪随机数法 : 采用一 个伪随机函数做散列函数, 即 h(key)=random(key) 通常在关键字长度不等时采用此法 伪随机函数中用同一种子值 ( 即这里的 key), 产 生的第一个随机值总是确定的 这就是被称为 伪 的原因 8.8 计算式查找法 散列表原理 (1)
106 8.8.3 散列函数的构造 其他常用的散列函数, 比如,BKDRHash, APHash,MurmurHash 等都是比较优秀的散列函数 unsigned int APHash(char *str) { } unsigned int hash = 0; for(int i=0; *str; i++) { if((i & 1) == 0) hash ^=((hash << 7) ^(*str++) ^(hash >> 3)); else hash ^=(~((hash << 11) ^(*str++) ^(hash >> 5))); } return(hash & 0x7FFFFFFF); 8.8 计算式查找法 散列表原理 (1)
107 9. 计算式查找法 散列表原理 (2)
108 8.9.1 散列表中处理冲突的方法 冲突解决办法 (Collision Resolution) 开放定址法 再散列法 链地址法 ( 又称为拉链法 ) 建立公共溢出区 8.9 计算式查找法 散列表原理 (2)
109 8.9.2 处理冲突 开放定址法 开放定址法基本思想 : 当关键字 key 的散列地址 p= h(key) 出现冲突时, 以 p 为基础, 产生别的散列地 址, 直到找出一个不冲突的散列地址 p i p i =(h(key)+d i )%m 开放定址法种类 线性探测, d i =1,2,3,,m 1 二次探测, d i =1 2, 1 2,2 2, 2 2,,k 2, k 2 伪随机探测, d i = 伪随机数序列 8.9 计算式查找法 散列表原理 (2)
110 8.9.2 处理冲突 开放定址法 开放定址法的实例 比如, 在长度为 11 的散列表中已填有关键字分别为 17,60,29 的记录, 现有第四个记录, 其关键字为 38, 由散列函数 ( 除留余数法 ) 得到地址为 5, 但是在 5 的 位置上已经有记录 ( 见下图 ), 发生了冲突 计算式查找法 散列表原理 (2)
111 8.9.2 处理冲突 开放定址法 开放定址法 线性探测的思想 : 按照偏移量 1,2,3, 逐个尝试下个, 下下个,, 直到找到空位 比如, 插到位置 8( 见下图 ) 计算式查找法 散列表原理 (2)
112 8.9.2 处理冲突 开放定址法 开放定址法 线性探测的动画 8.9 计算式查找法 散列表原理 (2)
113 8.9.2 处理冲突 开放定址法 开放定址法 二次探测的思想 : 按照偏移量 1 2,- 1 2,2 2,-2 2, 逐个尝试 比如, 插到位置 4( 见下图 ) 计算式查找法 散列表原理 (2)
114 8.9.2 处理冲突 开放定址法 开放定址法 伪随机探测的思想 : 假如用伪随机 数 d=9,5,3,8,1... 作为偏移量逐个尝试 比如按照 (5+d)% 11 计算出 3, 因此就插到位置 3( 见下图 ) 计算式查找法 散列表原理 (2)
115 8.9.3 处理冲突 再散列法 再散列法基本思想 : 这种方法是同时构造多个不同的 散列函数 :h i =h 1 (key), i=1,2,,k 当散列地址 h i =h 1 (key) 发生冲突时, 再计算 h i =h 2 (key), 直到冲突不再产生 8.9 计算式查找法 散列表原理 (2)
116 8.9.4 处理冲突 链地址法 链地址法基本思想 : 将所有散列地址为 i 的元素构 成一个称为同义词链的单链表 比如, 散列函数 h(key) 为 :Key% 计算式查找法 散列表原理 (2)
117 8.9.4 处理冲突 链地址法 链地址法的动画 8.9 计算式查找法 散列表原理 (2)
118 8.9.4 处理冲突 链地址法 与开放定址法相比, 链地址法有如下优点 : 链地址法处理冲突简单, 平均查找长度较短 ; 由于链地址法中各链表上的结点空间是动态申请的, 故它更适合于造表前无法确定表长的情况 ; 计算式查找法 散列表原理 (2)
119 8.9.4 处理冲突 链地址法 与开放定址法相比, 链地址法有如下优点 ( 续 ): 开放定址法为减少冲突, 要求装填因子 α 较小, 故当结点规模较大时会浪费很多空间 而链地址法中可取 α 1, 且结点较大时, 链地址法中增加的指针域可忽略不计, 因此节省空间 ( 反之, 用开放定址法比较节省空间 ); α= 散列表中元素个数 / 散列表的长度 8.9 计算式查找法 散列表原理 (2)
120 8.9.4 处理冲突 链地址法 与开放定址法相比, 链地址法有如下优点 ( 续 ): 用链地址法时, 删除结点的操作易于实现 只要简单地删去链表上相应的结点即可 而用开放定址法, 只能在被删结点上做删除标记, 而不能真正删除结点 否则会影响同义词的查找, 因为空地址单元意味着查找失败 计算式查找法 散列表原理 (2)
121 8.9.5 处理冲突 建立公共溢出区 建立公共溢出区基本思想 : 将散列表分为基本表和 溢出表两部分, 凡是和基本表发生冲突的元素, 一 律填入溢出表 假设散列函数的值域为 [0,m-1], 则设数组 HashTable[0..m-1] 为基本表, 另外设立存储空间 数组 OverTable[0..v] 用以存储发生冲突的记录 8.9 计算式查找法 散列表原理 (2)
122 10. 计算式查找法 散列表运算
123 背景 在前面介绍散列表原理 ( 散列表的概念 散列表的 构造方法 冲突的解决方法 ) 的基础上, 本学习点 介绍散列表的插入 建表 查找 删除等操作的实 现 8.10 计算式查找法 散列表运算
124 散列表的插入算法 算法思想 : 首先调用查找算法, 若在表中找到待插入的关键字或表已满, 则插入失败 ; 否则, 将待插入的结点插入其中, 即插入成功 8.10 计算式查找法 散列表运算
125 散列表的建表算法 算法思想 : 首先要将表中各结点的关键字清空 ; 然 后调用插入算法将给定的关键字序列依次插入表中 构造散列表实例 : 已知一组关键字为 (26,36,41, 38,44,15,68,12,06,51), 12 51) 用除留余数法构 造散列函数, 用线性探查 ( 探测 ) 法解决冲突 为了减少冲突, 通常令装填因子 α<l 这里关键字个 数 n=10, 不妨取 m=13, 此时 α 0.77, 散列表为 T[0..12], 散列函数为 :h(key)=key% 计算式查找法 散列表运算
126 散列表的建表算法 散列函数为 :h(key)=key%13 从而得到关键字 (26,36,41,38,44,15,68,12,06,51) 的地址为 (0,10,2,12,5,2,3,12,6,12) 前 5 个关键字插入时没有冲突, 结果为 序号 探查次数 计算式查找法 散列表运算
127 散列表的建表算法 采用链地址法解决冲突, 结果如下 ( 可头插或尾 插 ) 8.10 计算式查找法 散列表运算
128 散列表的查找算法 算法思想 : 当查找关键字为 K 的元素时, 首先计算 p 0 = h(k) 如果单元 p 0 为空, 则所查元素不存在 ; 如果单元 p 0 中元素的关键字为 K, 则找到所查元素 ; 否则重复下述解决冲突的过程 : 按解决冲突的方法, 找出下一个散列地址 p i, 如果单元 p i 为空, 则所查元 素不存在 ; 如果单元 p i 中元素的关键字为 K, 则找到 所查元素 8.10 计算式查找法 散列表运算
129 散列表的查找算法 查找实例 查找成功的 ASL: 序号 探查次数 线性探查法 ASL=( )/10= 计算式查找法 散列表运算
130 散列表的查找算法 查找实例 查找成功的 ASL: 链地址法 ASL=( )/10= 计算式查找法 散列表运算
131 散列表的查找算法 查找实例 查找成功的 ASL: 序号 顺序查找 ASL=(10+1)/2= 计算式查找法 散列表运算
132 散列表的查找算法 查找实例 查找成功的 ASL: 二分查找 ASL=( )/10= 计算式查找法 散列表运算
133 散列表的查找算法 查找实例 查找不成功的 ASL: 序号 探查次数 线性探查法 ASL unsucc =( )/ )/13 =59/ 计算式查找法 散列表运算
134 散列表的查找算法 查找实例 查找不成功的 ASL: 链地址法 ASL unsucc =( )/13=23/ 计算式查找法 散列表运算
135 散列表的查找算法 查找实例 查找不成功的 ASL: 序号 顺序查找 ASL unsucc = 计算式查找法 散列表运算
136 散列表的查找算法 查找实例 查找不成功的 ASL: 二分查找 ASL unsucc =( )/11= 计算式查找法 散列表运算
137 散列表的删除算法 算法思想 : 基于开放定址法的散列表不宜执行散列 表的删除操作 若必须在散列表中删除结点, 则不 能将被删结点的关键字清空, 而应该将其置为特定 的标记 DELETED 在查找操作时, 碰到 DELETED 可以继续探查下去 在插入操作时, 碰到 DELETED 则可以插入 这样做无疑增加了时间开销 因此, 当必须对散列表做删除结点的操作时, 一般是用链地址法来解决 冲突 8.10 计算式查找法 散列表运算
138 总结
139 8.4.3 二叉排序树的 C 语言定义 typedef dfint KeyType; typedef struct node { KeyType key; /* 关键字的值 */ struct node *lchild,*rchild;/* * 左右指针 */ }BSTnode,*BSTree; 8.4 基于树的查找法 二叉排序树
140 8.8.3 散列函数的构造 构造时考虑的因素 计算散列函数所需时间 关键字的长度 散列表大小 关键字分布情况 记录查找频率 8.8 计算式查找法 散列表原理
141 8.6.3 B 树的定义 m 路 B 树 ( 也可称为 m 阶 B 树或 m 度 B 树 ) 的 C 语言定义 #define m l000 // 阶数 typedef intboolean; typedef int KeyType; typedef struct MBTNode { struct MBTNode *parent; intkeynum; KeyType key[m+1]; // 关键字数组 其中 key[0] 不用 struct MBTNode *ptr[m+1];// 子树指针数组 }MBTNode, *MBTree; 在实用应用中, 与每个关键字存储在一起的还有一个指向该关键字所代表的记录 ( 在磁盘中 ) 的指针 8.6 基于树的查找法 B 树
142 8.3.4 折半查找对应的判定树 在折半查找判定树中, 某结点所在的层数即是查 找该结点的比较次数 根据二叉树性质 2( 深度为 h 二叉树至多有 2 h - 1 个结点 ), 对于满二叉树, 如果结点数是 n, 那么 n=2 h 1-1,h= log n+ 2 而对于判定树, 1 h= log n+ 2 ( 表示向上取整 ) 或者根据性质 4 得出 log 2 n +1, 两者一致 8.3 基于线性表的查找法 折半查找
143 散列法性能分析 散列法中影响关键字比较次数的因素 散列函数 处理冲突的方法 散列表的装填因子 8.10 计算式查找法 散列表运算
数据结构
9 查找 董洪伟 http://hwdong.com 主要内容 查找的概念 线性查找表 线性查找 折半查找 索引查找 ( 分块查找 ) 二叉查找树 ( 平衡二叉树 ) 二叉查找树 平衡二叉树 哈希查找 ( 散列查找 ) 查找的概念 查找 : 在数据集合中寻找满足某种条件的数据元素 关键字 相当于排序中的排序码 数据元素中某个数据项的值 可以标识一个数据元素 关键字可以相同, 即不一定唯一标识这个元素
2018 年天津城建大学攻读硕士学位研究生入学考试试题 (A) 卷 考试科目代码 :825 考试科目名称工程信息技术 招生专业 : 建筑与土木工程
一 单项选择题 ( 本题共 20 小题, 每题 2 分, 共 40 分 ) 1. 计算机所处理的数据一般具有某种内在联系, 这是指 ( ) A. 数据和数据之间存在某种联系 B. 数据项和数据项之间存在某种联系 C. 元素内部具有某种结构 D. 元素和元素之间存在某种联系 2. 在计算机中表示数据时, 数据的物理地址和逻辑地址相同并且连续, 称其为 ( ) A. 链式存储结构 B. 顺序存储结构 C.
第九章
第八章 查找 本章教学知识点与学习要求 :( 课内教学时数 6 学时, 实践教学时数 2 学时 ) (1) 熟练掌握顺序表和有序表的查找方法 ; (2) 熟悉静态查找树的构造方法和查找算法, 理解静态查找树和折半查找的关系 ; (3) 熟练掌握二叉排序树的构造方法和查找方法 ; (4) 掌握二叉平衡树的维护平衡方法 ; (5) 理解 B- 树 B+ 树和键树的特点以及他们的建树过程 ; (6) 熟练掌握哈希表的构造方法,
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.
四 读算法 ( 每题 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. 有向无回路
幻灯片 1
1.3 查找与排序 一 查找 查找, 也称为检索, 就是在一组同类型的数据元素中找出满足条件的元素 这种操作可能成功 ( 找到 ), 也可能失败 ( 未找到 ) 通常把待查找的数据元素集合称为查找表 下面介绍的查找是按关键字进行的 关键字 (key) 是数据元素中能唯一标识一个数据元素 ( 或记录 ) 中某个 ( 些 ) 数据项 要衡量一种查找算法的优劣, 主要是看要找的值与关键字的比较次数 为此,
PowerPoint Presentation
数据结构与算法 ( 六 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五 国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 6 章树 C 树的定义和基本术语 树的链式存储结构 子结点表 表示方法 静态 左孩子 / 右兄弟 表示法 动态表示法 动态 左孩子 / 右兄弟 表示法 父指针表示法及其在并查集中的应用
Microsoft PowerPoint - ds-9.ppt [兼容模式]
![Microsoft PowerPoint - ds-9.ppt [兼容模式]](/thumbs/39/20198929.jpg "Microsoft PowerPoint - ds-9.ppt [兼容模式]")
第 九 章 静 态 表 动 态 表 哈 希 表 9.1 基 本 概 念 (Page 214) 2 表 : 是 由 同 一 类 型 元 素 成 的 集 合 静 态 表 : 只 做 询 或 检 索 操 作 动 态 表 : 询 检 索 插 入 删 除 关 键 字 : 是 元 素 中 某 个 相 的 值, 用 它 可 以 标 识 一 个 元 素 主 关 键 字 次 关 键 字 : 根 给 定 值, 在 表
试卷代号 : 座位号 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. 针对线性表, 在存储后如果最常用的操作是取第
<4D F736F F D B8BDBCFE4220D7A8D2B5BBF9B4A1D3EBBACBD0C4BFCEB3CCC3E8CAF62E646F6378>
B212CC: 数据结构与算法 课程描述 0 课程基本信息 课程编号 : B212CC 课程名称 : 数据结构与算法英文名称 : Data Structures and Algorithms 英文简称 : DSA 预备课程 : 计算系统基础 离散数学授课时间 : 二年级第一学期时间分配 : 课堂教学 (48 课时 )+ 实验安排 (48 课时 )+ 课后作业与阅读 (48 课时 ) 学分数 : 3
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)
试卷代号 : 座位号 中央广播电视大学 学年度第二学期 " 开放本科 " 期末考试 数据结构试题 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=
试卷代号 : 座位号 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. 一种抽象数据类型包括数据和
PowerPoint 演示文稿
The BitCoin Scripting Language 交易实例 交易结构 "result": { "txid": "921a dd24", "hash": "921a dd24", "version": 1, "size": 226, "locktime": 0, "vin": [ ], "vout": [ ], "blockhash": "0000000000000000002c510d
幻灯片 1
二叉树 汪小林改写 基于张铭 王腾蛟原稿 北京大学信息学院 主要内容 1. 二叉树的概念 2. 二叉树的抽象数据类型 3. 二叉树的存储结构 4. 二叉搜索树 5. 堆与优先队列 6. Huffman 树及其应用 7. 二叉树知识点总结 1 二叉树的概念 二叉树的定义及基本术语 满二叉树 完全二叉树 扩充二叉树 二叉树的主要性质 二叉树的定义 二叉树 (binary tree) 由结点的有限集合构成,
生成word文档
希赛网, 专注于软考 PMP 通信考试的专业 IT 知识库和在线教育平台 希赛网在线题库, 提供历年考试真题 模拟试题 章节练习 知识点练习 错题本练习等在线做题服务, 更有能力评估报告, 让你告别盲目做题, 针对性地攻破自己的薄弱点, 更高效的备考 希赛网官网 :http://www.educity.cn/ 希赛网软件水平考试网 :http://www.educity.cn/rk/ 希赛网在线题库
Microsoft Word - 专升本练习2：线性表.doc
第二章 线性表 一 选择题 1. 线性表是 ( ) A. 一个有限序列, 可以为空 B. 一个有限序列, 不能为空 C. 一个有限序列, 可以为空 D. 一个无序序列, 不能为空 2. 对顺序存储的线性表, 设其长度为 n, 在任何位置上插入或删除操作都是等概率 插入一个元素 时大约要移动表中的 ( ) 个元素, 删除一个元素时大约要移动表中的 ( ) 个元素 A. n/2 B. (n+1)/2 C.
试卷代号 : 座位号 中央广播电视大学 学年度第一学期 " 开放本科 " 期末考试 数据结构试题 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
数据结构习题
数据结构 习题集 第一章序论 思考题 : 1.1 简述下列术语 : 数据 数据元素 数据对象 数据结构 存储结构 数据类型 抽象数据类型 作业题 : 1.2 设有数据结构 (D,R), 其中 D={d1, d2, d3, d4 R={r1, r2 r1={ , , , , , r2={ (d1, d2),
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) 的结点
各章例题 Contents 1 第 1 章例题 2 第 4 章例题 3 第 4-1 章例题 4 第 4-2 章例题 5 第 5 章例题 6 第 7 章例题 7 第 8 章例题 8 第 9 章例题 第 1 章例题 选择题 在数据结构中, 从逻辑上可以把数据结构分成 :( ) A 动态结构和静态结构 B 紧凑结构和非紧凑结构 C 线性结构和非线性结构 D 内部结构和外部结构 答案 C 第 1 章例题 判断题
<4D F736F F D20BBAAC4CFC0EDB9A4B4F3D1A72020CAFDBEDDBDE1B9B9B8B4CFB0B1CABCC7D5FBC0ED2E646F63>
数据结构复习笔记整理第二部分复习提纲 ( 不分题型, 弄清原理, 不要死记硬背 ). 简单复杂性的判断 : ()i=n; while(i>=) i=i/2; 其中 i=n,n/2,n/2 2,,n/2 k, 需 n/2 k >=, 即 2 k
帝国CMS下在PHP文件中调用数据库类执行SQL语句实例
帝国 CMS 下在 PHP 文件中调用数据库类执行 SQL 语句实例 这篇文章主要介绍了帝国 CMS 下在 PHP 文件中调用数据库类执行 SQL 语句实例, 本文还详细介绍了帝国 CMS 数据库类中的一些常用方法, 需要的朋友可以参考下 例 1: 连接 MYSQL 数据库例子 (a.php)
PowerPoint Presentation
第十章文件 外部排序 与搜索 赵建华 南京大学计算机系 文件 什么是文件 文件是存储在外存上的数据结构 文件分操作系统文件和数据库文件 操作系统中的文件是流式文件 : 是没有结构的字符流 数据库文件是具有结构的数据集合 数据结构中讨论的是数据库文件 操作系统对文件是按物理记录读写的, 在数据库中文件按页块存储和读写 文件的组成 文件由记录组成 ; 记录由若干数据项组 成 记录 : 文件存取的基本单位
树的非递归中序和层次遍历实现
相信大家对树的各种递归的遍历很了解, 利用递归使得代码变得简单而且比较好理解, 但是利用递归是需要代价的, 特别是当递归层次比较深的时候, 可能会导致递归栈溢出 而且递归一般运行速度比较慢, 那么这种情况下, 我们就可以采用非递归来实现, 非递归相对递归来说, 代码相对比较难理解, 而且代码量也一般比较多, 可是它的执行效率却是很不错的 在树的中序非递归遍历中需要用到栈, 在层次遍历中需要用到队列,
<4D F736F F F696E74202D20CAFDBEDDBDE1B9B9B8B4CFB0CCE22E707074>
数据结构与算法 58-1 计算机的算法指的是 (1), 它必须具备 (2) * A.(1) 计算方法,(2) 可执行性, 可移植性, 可扩充性 B.(1) 解决问题的步骤序列,(2) 可执行性, 确定性, 有穷性 C.(1) 排序方法,(2) 确定性, 有穷性, 稳定性 D.(1) 调度方法,(2) 易读性, 稳定性, 安全性 评价一个算法好坏的标准主要是 A 执行时间 B 辅助空间 C 算法本身的复杂度
东北大学1996年考研题.doc
1996 年考研题 一 ( 25 分 ) 每小题 5 分 1. 根据下图完成 : (1) 画出该图的十字链表存储结构图 (2) 写出其拓扑排序的输出序列 (3) 写出图的强连通分量 ( 支 ) ( 4 ) 写出到的所有路径及简单路径 2. 给定 8 个权值集合 (2,5,3,10,4,7,9,18) 画出含有 8 个叶子结点的最佳三叉归并树, 并计算出 3. 已知含有 8 个结点的一棵二叉树, 按先序
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. 注意 "," 后面有一个空格,"." 结束,
Microsoft PowerPoint - Slides09_第五章 集合 [兼容模式]
![Microsoft PowerPoint - Slides09_第五章 集合 [兼容模式]](/thumbs/84/90139818.jpg "Microsoft PowerPoint - Slides09_第五章 集合 [兼容模式]")
第五章集合 集合的基本概念 并查集 散列表 集合 集合是成员 ( 元素 ) 的一个无序群集 集合中的成员可以是原子 ( 单元素 ), 也可以是集合 集合的成员必须互不相同, 即同一成员不能在集合中多次出现 集合的有序链表类的定义 // 集合的结点类定义 template struct SetNode { T data; SetNode *link; // 每个成员的数据 //
湖北工业大学二 八年招收硕士学位研究生试卷 则从顶点 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 以下术语与数据的存储结构无关的是(
重 庆 邮 电 大 学
机密 启用前 重庆邮电大学 2019 年攻读硕士学位研究生入学考试试题 科目名称 : 数据结构 (A) 科目代码 : 802 考生注意事项 1 答题前, 考生必须在答题纸指定位置上填写考生姓名 报考单位和考生编号 2 所有答案必须写在答题纸上, 写在其他地方无效 3 填 ( 书 ) 写必须使用 0.5mm 黑色签字笔 4 考试结束, 将答题纸和试题一并装入试卷袋中交回 5 本试题满分 150 分,
PowerPoint 演示文稿
第 6 章树和二叉树 6.1 树的概念与定义 6.2 二叉树 6.3 二叉树的遍历与线索化 6.4 树 森林和二叉树的关系 6.5 哈夫曼树及其应用 定义 : 树 (tree) 是 n(n 0) 个结点的有限集 其中 : 在任意一个非空树中 :1) 有且仅有一个特定的称为根 (root) 的结点 ; 2) 当 n>1 时, 其余结点可分为 m(m>0) 个互不相交的有限集 T 1,T 2,,T m,
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" 一些
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
2009
数据结构 考研真题及解答 目 录 2009 年试题... 1 填空题... 1 解答题... 2 2010 年试题... 2 填空题... 2 解答题... 4 2011 年试题... 4 填空题... 4 解答题... 5 2012 年试题... 6 填空题... 6 解答题... 7 2013 年试题... 8 填空题... 8 解答题... 9 2014 年试题... 10 填空题... 10
求出所有的正整数 n 使得 20n + 2 能整除 2003n n 20n n n 20n n 求所有的正整数对 (x, y), 满足 x y = y x y (x, y) x y = y x y. (x, y) x y =
求出所有的正整数 n 使得 20n + 2 能整除 2003n + 2002 n 20n + 2 2003n + 2002 n 20n + 2 2003n + 2002 求所有的正整数对 (x, y), 满足 x y = y x y (x, y) x y = y x y. (x, y) x y = y x y 对于任意正整数 n, 记 n 的所有正约数组成的集合为 S n 证明 : S n 中至多有一半元素的个位数为
2.3 链表
数据结构与算法 ( 二 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五 国家级规划教材 ) https://pkumooc.coursera.org/bdsalgo-001/ 第二章线性表 2.1 线性表 2.2 顺序表 tail head a 0 a 1 a n-1 2.4 顺序表和链表的比较 2 链表 (linked list) 通过指针把它的一串存储结点链接成一个链
【此处填写课程中文名称】
数据结构 Data Structures 一 基本信息 课程代码 : 2050161 课程学分 : 4 面向专业 : 计算机科学与技术 课程性质 : 院级必修课 开课院系 : 信息技术学院计算机科学与技术系 使用教材 : 教材 数据结构 ( 第 2 版 ), 陈越等, 高等教育出版社,2016 年 6 月 参考书目 数据结构 (C 语言版 ), 李云清等, 人民邮电出版社,2009 年第二版 数据结构学习与实验指导,
Microsoft PowerPoint - 6-.pptx
基本概念 树的存储结构 树的线性表示 树的遍历 二叉树 二叉树的存储表示 二叉树的各种遍历 线索化二叉树 堆 计算二叉树的数目 二叉树的应用 : 霍夫曼树和霍夫曼编码 本章小结 6.1 基本概念 树是由一个或多个结点组成的有限集 T, 它满足下面两个条件 : 有一个特定的结点, 称之为根结点 ; 其余的结点分成 m (m 0) 个互不相交的有限集 T 0, T 1,, T m-1 其中每个集合又都是一棵树,
A.39 B.52 C.111 D.119 解析 C 根据完全二叉树的定义, 此树的前 6 层应该是满二叉树, 共有 = 63 个结点 第 6 层有 8 个叶子结点, 说明另外 32-8=24 个结点不是叶子结点, 最多各有 2 个孩子结点 而该树不可能有第 8 层存在, 所以结点总数最
09 年真题 1 为解决计算机与打印机之间速度不匹配的问题, 通常设置一个打印数据缓冲区, 主机将要输出的数据依次写入该缓冲区, 而打印机则依次从该缓冲区中取出数据 该缓冲区的逻辑结构应该是 ( ) A. 栈 B. 队列 C. 树 D. 图 解析 B 打印机取出数据的顺序与数据被写入缓冲区的顺序相同, 为先进先出结构, 即队列 2 设栈 S 和队列 Q 的初始状态均为空, 元素 a,b,c,d,e,f,g
华侨大学2011年硕士研究生入学考试专业课试卷
华侨大学 2016 年硕士研究生入学考试专业课试卷 ( 答案必须写在答题纸上 ) 招生专业计算机技术 ( 专业学位 ) 科目名称数据结构与 C++ 科目代码 850 第一部分数据结构 ( 总分 75 分 ) 一. 单项选择题 ( 每题 1.5 分, 共 12 分 ) 1. 下列关于顺序存储结构的叙述哪一个是错误的?( ) A. 存储密度大 B. 插入操作不方便 C. 不可随机访问任意结点 D. 存储单元的地址是连续的
6.1 树的定义和基本术语 6.2 二叉树 ( 定义 性质 存储结构 ) 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用
第六章树与二叉树 树型结构是一类非常重要的非线性结构 直观地, 树型结构是以分支关系定义的层次结构 树在计算机领域中也有着广泛的应用, 例如在编译程序中, 用树来表示源程序的语法结构 ; 在数据库系统中, 可用树来组织信息 ; 在分析算法的行为时, 可用树来描述其执行过程等等 6.1 树的定义和基本术语 6.2 二叉树 ( 定义 性质 存储结构 ) 6.3 遍历二叉树和线索二叉树 6.4 树和森林
PowerPoint 演示文稿
Slide: 5-1 李希然 哈尔滨工业大学计算机学院 213 年 8 月 Slide: 5-2 第五章 查找 Slide: 5-3 本章目录 1. 线性查找 2. 折半查找 3. 分块查找 4. 二叉查找树 5.AVL 树 6.B- 树与 B + 树 7.Trie 树 * 8. 散列法 8.1. 内散列表 8.2. 散列函数 8.3. 冲突的处理 8.4. 外散列表 Slide: 5-4 查找的概念对给定的值与数据集合中各记录的关键字进行比较,
<4D F736F F D20D6A3D6DDB4F3D1A7CAFDBEDDBDE1B9B9B1CABCC72E646F63>
郑州大学 硕士研究生入学考试 计算机应用与技术专业基础课 数据结构 课程辅导笔记 (2005 年版 ) 1. 设 A=(a 1 a n ), 问利用顺序存储结构 : 1 在等概率的前提下, 插入一个元素平均移动多少个元素? n( n 1) n ( n 1) 1 0 解 : = 2 n = n 1 n 1 2 n i 2 若元素插入在 a i 与 a i 1 (0 i n-1) 的概率为, 则平均插入一个元素所需
一元多项式实验要求
实验一一元多项式实验要求 (12 课时 ) 一基本要求 : 1. 编写程序 polyn.c( 或 polyn.cpp) 实现 ADT Polynomial, 可以使用下列结构实现 : typedef struct{ float p; // 系数 int e; // 指数 }ElemType; 实现基本操作 : CreatePolyn(&p,m), 创建一元多项式, 可从终端接受 m 组 (p,e)
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)
C++ 程序设计 告别 OJ2 - 参考答案 MASTER 2019 年 5 月 3 日 1
C++ 程序设计 告别 OJ2 - 参考答案 MASTER 2019 年 5 月 3 日 1 1 TEMPLATE 1 Template 描述 使用模板函数求最大值 使用如下 main 函数对程序进行测试 int main() { double a, b; cin >> a >> b; cout c >> d; cout
《C语言程序设计》第2版教材习题参考答案
教材 C 语言程序设计 ( 第 2 版 ) 清华大学出版社, 黄保和, 江弋编著 2011 年 10 月第二版 ISBN:978-7-302-26972-4 售价 :35 元 答案版本 本习题答案为 2012 年 2 月修订版本 一 选择题 1. 设已定义 int a, * p, 下列赋值表达式中正确的是 :C)p = &a A. *p = *a B. p = *a C.p = &a D. *p =
PowerPoint Presentation
数据结构与算法 ( 六 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五 国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg A 第 6 章树 B C 树的定义和基本术语 树的链式存储结构 子结点表 表示方法 静态 左孩子 / 右兄弟 表示法 动态表示法 动态 左孩子 / 右兄弟 表示法 父指针表示法及其在并查集中的应用
中国科学院研究生院
中国科学院大学 2013 年招收攻读硕士学位研究生入学统一考试试题 考生须知 : 1. 本试卷满分为 150 分, 全部考试时间总计 180 分钟 2. 所有答案必须写在答题纸上, 写在试题纸上或草稿纸上一律无效 一 单选题 ( 每小题 2 分, 共 80 分 ) 1. 操作系统负责管理和控制计算机系统的 A. 软件资源 B. 硬件资源和软件资源 C. 对用户有用的资源 D. 硬件资源 2. UNIX
三种方法实现Hadoop(MapReduce)全局排序(2)
三种方法实现 Hadoop(MapReduce) 全局排序 (2) 我在前面的文章介绍了 MapReduce 中两种全排序的方法及其实现 但是上面的两种方法都是有很大的局限性 : 方法一在数据量很大的时候会出现 OOM 问题 ; 方法二虽然能够将数据分散到多个 Reduce 中, 但是问题也很明显 : 我们必须手动地找到各个 Reduce 的分界点, 尽量使得分散到每个 Reduce 的数据量均衡
算法分析与问题的计算复杂度
算法分析与问题的计算复杂度 王子辰 2016.5.20 概要 第一部分检索 算法的评价指标 平凡下界 决策树与时间复杂度 第二部分排序 冒泡排序 堆排序等排序算法 排序算法的复杂度下界 第三部分选择 选择问题的时间复杂度分析 问题之间的归约性 概要 第一部分检索 算法的评价指标 平凡下界 决策树与时间复杂度 第二部分排序 冒泡排序 堆排序等排序算法 排序算法的复杂度下界 第三部分选择 选择问题的时间复杂度分析
PowerPoint 演示文稿
数据结构与算法 ( 十 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五 国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 10.1 线性表的检索 第十章 检索 10.1 线性表的检索 10.2 集合的检索 10.3 散列表的检索 总结 2 散列检索 10.3.0 散列中的基本问题 10.3.1
数据结构
第六讲 二叉树 孙猛 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 课程内容 二叉树及其抽象数据类型
数学分析（Ｉ）短课程 [Part 2] 4mm 自然数、整数和有理数
![数学分析（Ｉ）短课程 [Part 2] 4mm 自然数、整数和有理数](/thumbs/51/27870416.jpg "数学分析（Ｉ）短课程 [Part 2] 4mm 自然数、整数和有理数")
.. 数学分析 (I) 短课程 [Part 2] 自然数 整数和有理数 孙伟 华东师范大学数学系算子代数中心 Week 2 to 18. Fall 2014 孙伟 ( 数学系算子代数中心 ) 数学分析 (I) 短课程 Week 2 to 18. Fall 2014 1 / 78 3. 自然数理论初步 孙伟 ( 数学系算子代数中心 ) 数学分析 (I) 短课程 Week 2 to 18. Fall 2014
6 tree
6 树和二叉树 董洪伟 http://hwdong.com 1 树和二叉树 主要内容一 树的类型定义二 二叉树的类型定义三 二叉树的存储结构四 二叉树的操作五 线索二叉树六 树和森林七 赫夫曼树八 树的计数 2 树的类型定义 树是一个层次结构的抽象模型 树是由具有父子关系的结点构成的 应用示例 : - 组织结构 - 文件系统 Computers R Us Sales Manufacturing R&D
什么是函数式编程?
函数式编程 FUNCTIONAL PROGRAMMING byvoid@byvoid.com 什么是函数式编程? 真相是 从停机问题开始 Bug 假设有停机判定算法 function halting(func, input) { } return if_func_will_halt_on_input; 充分利用停机判定 function ni_ma(func) { if (halting(func,
高等数学A
高等数学 A March 3, 2019 () 高等数学 A March 3, 2019 1 / 55 目录 1 函数 三要素 图像 2 导数 导数的定义 基本导数表 求导公式 Taylor 展开 3 积分 Newton-Leibniz 公式 () 高等数学 A March 3, 2019 2 / 55 函数 y = f(x) 函数三要素 1 定义域 2 值域 3 对应关系 () 高等数学 A March
PowerPoint 演示文稿
友乾营 报表的 SQL 植入风险 规避风险 : 让你的报表变的安全起来 SQL 植入的概念 恶意的 SQL 归根结底 : 执行了不该允许执行的 SQL 命令, 达到非法的目的 常见案例 骗过登录验证非法获取账号信息篡改 删除数据 为什么存在 SQL 植入 植入原理 如何攻击 特殊的输入参数 未处理特殊字符 -- # 数据库配置不合理 植入原理 : 案例 1, 特殊输入参数 union or 猜表名
没有幻灯片标题
指针作为函数参数 : 原因 : 1 需要修改一个或多个值,( 用 return 语句不能解决问题 ) 2 执行效率的角度 使用方法 : 在函数原型以及函数首部中需要声明能够接受指针值的形参, 具体的写法为 : 数据类型 * 形参名 如果有多个指针型形参, 则用逗号分隔, 例如 : void swap(int *p1, int *p2) 它说明了形参 p1 p2 是指向整型变量的指针 在函数调用时,
Microsoft PowerPoint - 概率统计Ch02.ppt [Compatibility Mode]
![Microsoft PowerPoint - 概率统计Ch02.ppt [Compatibility Mode]](/thumbs/104/161694025.jpg "Microsoft PowerPoint - 概率统计Ch02.ppt [Compatibility Mode]")
66 随机变量的函数.5 随机变量的函数的分布 设 是一随机变量, 是 的函数, g(, 则 也是一个随机变量. 本节的任务 : 当 取值 x 时, 取值 y g 67 ( 一 离散型随机变量的函数 设 是离散型随机变量, 其分布律为 或 P { x } p (,, x x, P p p, x p 已知随机变量 的分布, 并且已知 g 要求随机变量 的分布. (, 是 的函数 : g(, 则 也是离散型随机变
《C语言程序设计》教材习题参考答案
教材名称 : C 语言程序设计 ( 第 1 版 ) 黄保和 江弋编著清华大学出版社 ISBN:978-7-302-13599-9, 红色封面 答案制作时间 :2011 年 2 月 -5 月 一 选择题 1. 设已定义 int a, * p, 下列赋值表达式中正确的是 :C)p=&a 2. 设已定义 int x,*p=&x;, 则下列表达式中错误的是 :B)&*x 3. 若已定义 int a=1,*b=&a;,
立 志 于 打 造 最 贴 近 考 生 实 际 的 辅 导 书 计 算 机 考 研 之 数 据 结 构 高 分 笔 记 率 辉 编 著 周 伟 张 浩 审 核 讨 论 群 :15945769
立 志 于 打 造 最 贴 近 考 生 实 际 的 辅 导 书 计 算 机 考 研 之 数 据 结 构 高 分 笔 记 率 辉 编 著 周 伟 张 浩 审 核 讨 论 群 :15945769 前 言 在 计 算 机 统 考 的 四 门 专 业 课 中, 最 难 拿 高 分 的 就 是 数 据 结 构 但 是 这 门 课 本 身 的 难 度 并 不 是 考 生 最 大 的 障 碍, 真 正 的 障 碍
第四章 １０２ 图 ４唱１６ 基于图像渲染的理论基础 三张拍摄图像以及它们投影到球面上生成的球面图像 拼图的圆心是相同的 而拼图是由球面图像上的弧线图像组成的 因此我 们称之为同心球拼图 如图 ４唱１８ 所示 这些拼图中半径最大的是圆 Ｃｋ 最小的是圆 Ｃ０ 设圆 Ｃｋ 的半径为 ｒ 虚拟相机水平视域为 θ 有 ｒ Ｒ ｓｉｎ θ ２ ４畅１１ 由此可见 构造同心球拼图的过程实际上就是对投影图像中的弧线图像
运用伸展树解决数列维护问题
运用伸展树解决数列维护问题 By Crash 1 关键词 数列维护问题 伸展树 摘要 对于数列维护问题, 我们常用的一种手段是线段树 但使用线段树有一定的局限性, 本文介绍运用伸展树解决这类问题, 并且可以实现更多的功能 目录 (1) 伸展树的伸展操作 (2) 在伸展树中对区间进行操作 (3) 实例分析 NOI 2005 维护数列 (Sequence) (4) 和线段树的比较 1 Blog 地址 :http://hi.baidu.com/oimaster
第一章三角函数 1.3 三角函数的诱导公式 A 组 ( ) 一 选择题 : 共 6 小题 1 ( 易诱导公式 ) 若 A B C 分别为 ABC 的内角, 则下列关系中正确的是 A. sin( A B) sin C C. tan( A B) tan C 2 ( 中诱导公式 ) ( ) B. cos(
第一章三角函数 1. 三角函数的诱导公式 A 组 一 选择题 : 共 6 小题 1 ( 易诱导公式 ) 若 A B C 分别为 ABC 的内角 则下列关系中正确的是 A. sin( A B) sin C C. tan( A B) tan C ( 中诱导公式 ) B. cos( B C) cos A D. sin( B C) sin A sin60 cos( ) sin( 0 )cos( 70 ) 的值等于
一、单项选择题, 共十五小题，每小题2分，全题总分为30分
810 华南理工大学 2010 年攻读硕士学位研究生入学考试试卷 ( 请在答题纸上做答, 试卷上做答无效, 试后本卷必须与答题纸一同交回 ) 科目名称 : 物流信息基础 ( 含数据库 数据结构 ) 适用专业 : 物流工程与管理, 物流工程共 6 页说明 : 本卷分为数据库和数据结构共两部分内容, 全卷满分 150 分, 其中数据库部分满分 75 分, 数据结构满分 75 分 一. 数据库部分一. 单项选择题,
14
孙猛 http://www.math.pku.edu.cn/teachers/sunm 2017 年 11 月 27 日 1 字典的散列列表示 2 动机 : 如果关键码是存储字典元素的数组下标, 则可以直接找到字典元素! 关键码未必总是整数! Windows 序列列号 关键码即使是整数, 也未必适合做数组下标! 北北 大学 生学号 10 位数字, 取值范围 100 亿 如何建 立从关键码集合到适当整数集合的映射,
PowerPoint Presentation
USTC Chapter 3 Data Structures 王子磊 (Zilei Wang) Email: zlwang@ustc.edu.cn http://vim.ustc.edu.cn/ 学习要点 基本数据结构 栈 队列 链表 有根树 图 堆与堆排序 散列表 Hash Table 二叉搜索树 红黑树 基本数据结构 栈 栈实现的是一种后进先出 (LIFO) 策略的动态集合 用一个数组 S[1:n]
第六章 树
第六章树和二叉树 本章教学知识点与学习要求 :( 课内教学时数 8 学时, 实践教学时数 2 学时 ) (1) 理解树型结构的基本概念和术语 ; (2) 熟练掌握二叉树的定义 性质及相应的证明方法 ; (3) 熟悉二叉树的各种存储结构的特点及适用范围 ; (4) 熟练掌握二叉树的三种遍历算法, 且能灵活运用遍历算法实现二叉树的其他操作 ; (5) 熟练掌握线索化二叉树的过程, 以及在中序线索化树上找给定结点的前驱和后继
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 标识符逗号分隔,
第 33 届宁波市中小学生信息学能力水平展示活动第一轮试题 第 33 届宁波市中小学生信息学能力水平展示小学组第一轮 pascal 试题 ( 说明 : 答案请填在答题卷上 考试时间 120 分钟, 满分 100 分 ) 一. 选择题 ( 每题 1.5 分, 共 30 分 每小题只有一个正确答案, 多
第 33 届宁波市中小学生信息学能力水平展示小学组第一轮 pascal 试题 ( 说明 : 答案请填在答题卷上 考试时间 120 分钟, 满分 100 分 ) 一. 选择题 ( 每题 1.5 分, 共 30 分 每小题只有一个正确答案, 多选错选均不给分 ) 1 以下不属于计算机硬件的是( ) A. 显示器 B. 内存 C. 操作系统 D. 光盘驱动器 2 以下列扩展名结尾的文件, 是视频文件的是
<4D F736F F D20B5DAC8FDCBC4D5C2D7F7D2B5B4F0B0B82E646F63>
第三章 Q3 1 1. 省略了 I/O 操作的复杂逻辑, 易实现, 耗费低 ; 2. 可以利用丰富的内存寻址模式实现灵活的 I/O 操作 Q3 2 假设存储单元 ds1 处寄存器地址为 0x2000, 代码如下 #define ds1 0x2000 while ( *ds1 == 0 ) ; Q3 3 假设设备 (dev1) 中有两个寄存器 ds1 和 dd1,dev1 的地址为 0x1000,ds1
章名 （第1章）
第 1 章数据结构与算法 1.1 算法的复杂度... 1 1.2 数据结构... 1 1.2.1 逻辑结构和存储结构... 1 1.2.2 线性结构和非线性结构... 3 1.3 栈... 3 1.4 队列... 4 1.5 链表... 5 1.6 二叉树... 5 1.6.1 二叉树概念及其基本性质... 5 1.6.2 二叉树的遍历... 8 1.7 查找... 8 1.7.1 顺序查找...
Microsoft Word A.doc
一 单项选择题 :1~40 小题, 每小题 2 分, 共 80 分 在每小题给出的四个选项中, 请选出一项最符合题目要求的 1. 在下面的 C 语言程序段中, 加法操作的时间复杂度为 ( ) int i, j, k, sum = 0; for( i=0; i < n; ++i) for( j=0; j < i*i; ++j) sum++; A.Ο(2n 2 ) B.Ο(2n 3 ) C.Ο(n 3
<4D F736F F D E3131CAFDBEDDBDE1B9B9C6DAD6D0BFBCCAD4A3A8BAACB2CEBFBCB4F0B0B8A3A92E646F63>
一 选择题 ( 每小题 2 分, 共 30 分, 奇 偶 ) 1. 从逻辑上可以把数据结构分为 ( ) 两大类. 动态结构 静态结构. 顺序结构 链式结构. 线性结构 非线性结构 D. 初等结构 构造型结构 2. 下面关于线性表的叙述中, 错误的是哪一个?( ). 线性表采用顺序存储, 必须占用一片连续的存储单元. 线性表采用顺序存储, 便于进行插入和删除操作. 线性表采用链接存储, 不必占用一片连续的存储单元
PowerPoint Presentation
数 据 结 构 与 算 法 ( 六 ) 张 铭 主 讲 采 用 教 材 : 张 铭, 王 腾 蛟, 赵 海 燕 编 写 高 等 教 育 出 版 社,2008. 6 ( 十 一 五 国 家 级 规 划 教 材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg A 第 6 章 树 B 树 的 定 义 和 基 本 术 语 树 的 链 式 存 储 结 构 J H
Microsoft Word - 第3章.doc
第 3 章数据结构与算法 数据结构是指数据元素的集合及元素间的相互关系和构造方法, 结构就是元素之间的关系 在数据结构中, 元素之间的相互关系是数据的逻辑结构 按照逻辑关系的不同将数据结构分为线性结构和非线性结构, 其中, 线性结构包括线性表 栈 队列 串, 非线性结构主要包括树和图 数据元素及元素之间关系的存储形式称为存储结构, 可分为顺序存储和链接存储两种基本方式 算法与数据结构密切相关, 数据结构是算法设计的基础,
Microsoft Word A3.doc
一 单项选择题 :1~40 小题, 每小题 2 分, 共 80 分 在每小题给出的 选项中, 请选出一项最符合题目要求的 1. 下列排序算法中, 平均时间复杂度最小的是 ( ) A. 归并排序 B. 起泡排序 C. 简单选择排序 D. 直接插入排序 2. 关于线性表的描述正确的是 ( ) A. 采用顺序存储时, 其存储地址必须是连续的 B. 采用链式存储时, 其存储地址必须是连续的 C. 采用顺序存储时,
7
孙猛 http://www.math.pku.edu.cn/teachers/sunm 2017 年 10 月 19 日 1 堆与优先队列列 哈夫曼树 2 介绍 一种特殊的完全 二叉树 这种 二叉树的顺序存储表示 堆 优先队列列的概念及使 用堆的实现 方法 3 每个结点的值都 小于 ( 或者都 大于 ) 它的左右 子树的根结点的值 这种 二叉树的 广度优先周游序列列顺序表示中, 用于存放结点的顺序表具有如下性质
<4D F736F F F696E74202D20536C FB5DACBC4D5C220CAF7D3EBB6FEB2E6CAF7205BBCE6C8DDC4A3CABD5D>
第四章树 二叉树 森林 树的基本概念 二叉树 定义 主要特征 存储结构 : 顺序 链式 遍历 线索二叉树 : 基本概念 构造 树 森林 存储结构 : 树 森林与二叉树的转换 遍历 : 树 森林 应用 二叉排序树 Huffman 树和哈夫曼编码 树和有根树 两种树 : 自由树 有根树 树 (Tree) 和森林的概念 自由树无回路的连通图 : 一棵自由树 T f 可定义为一个二元组 T f = (V,
试卷格式
复 旦 大 学 计 算 机 科 学 技 术 学 院 数 据 结 构 期 末 考 试 试 卷 ( 参 考 答 案 与 评 分 标 准 ) A 卷 共 8 页 课 程 代 码 :COMP130004.01-03 考 试 形 式 : 开 卷 闭 卷 2012 年 1 月 ( 本 试 卷 答 卷 时 间 为 120 分 钟, 答 案 必 须 写 在 试 卷 上, 做 在 草 稿 纸 上 无 效 ) 专 业
浙江师范大学
软件与通信工程学院 数据结构与算法 实验指导书 江西财经大学软件与通信工程学院通信工程系 2016 年 9 月 - 1 - 目录 写在上机实验之前... - 3 - 数据结构与算法( 电子 ) 课程实验教学大纲... - 4 - 实验一线性表链式表示和实现... - 7 - 实验二栈的应用之表达式求值... - 8 - 实验三二叉树的遍历操作... - 10 - 实验四图的遍历操作... - 13
Computer Engineering and Applications 计算机工程与应用 07,53(9) 63 一种新型有序数据结构 : 容量平衡三叉查找树 徐懿彬, 徐学荣 XU Yibin, XU Xuerong. 福建省福州第八中学, 福州 350004. 福建农林大学, 福州 35000.Fuzhou No.8 Secondary School, Fuzhou 350004,China.Fujian
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 分, 共计
Microsoft PowerPoint - 5. 指针Pointers.ppt [兼容模式]
![Microsoft PowerPoint - 5. 指针Pointers.ppt [兼容模式]](/thumbs/86/93544395.jpg "Microsoft PowerPoint - 5. 指针Pointers.ppt [兼容模式]")
指针 Pointers 变量指针与指针变量 Pointer of a variable 变量与内存 (Variables and Memory) 当你声明一个变量时, 计算机将给该变量一个内存, 可以存储变量的值 当你使用变量时, 计算机将做两步操作 : - 根据变量名查找其对应的地址 ; - 通过地址对该地址的变量内容进行读 (retrieve) 或写 (set) 变量的地址称为变量的指针! C++
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 算法 算法 : 是指解题方案的准确而完整的描述 算法不等于程序, 也不等计算机方法, 程序的编制不可能优于算法的设计 算法的基本特征 : 是一组严谨地定义运算顺序的规则, 每一个规则都是有效的, 是明确的, 此顺序将在 有限的次数下终止 特征包括
¹
复仇母题与中外叙事文学 杨经建 彭在钦 复仇是一种特殊的历史文化现象 也是以超常态的 极端性方式为特征的人类自然法则的体现 而在中外叙事文学中以 复仇 为取向的创作大致有三种母题形态 血亲复仇 痴心女子负心汉式复仇 第三类复仇 本文在对这三类复仇叙事模式进行艺术解析的前提下 发掘并阐释了蕴涵其中的不同民族的文化精神和价值指向 复仇母题 叙事文学 创作模式 文化蕴涵 ¹ º » ¼ ½ ¹
18
孙猛 http://www.math.pku.edu.cn/teachers/sunm 2017 年 12 月 14 日 1 2 排序的基本概念 插 入排序 3 假设给定 一个有待排序的 文件, 它由 N 个记录的集合构成 :{R 1,R 2,, R N } 每个记录 R i 有 一个排序码 ( 不不 一定是关键码 ), 记为 K i 在排序码上确定 一个全序关系
清华大学1995年考研试题.doc
清华大学 1995 年考研试题 一 已知三个带头结的线性链表 A B 和 C 中的结点均已元素值自小至大非递减排列可能存在两个值相同的结点 ), 编写算法对 A 表进行如下操作 : 使操作后的链表 A 中仅留下三个表中均包含的数据元素的结点, 且没有值相同的结点, 并释放所有结点 限定算法的时间复杂度为 O(m+n+p), 其中 m n 和 p 分别为三个表的长度 ( 15 分 ) 二 画出下列广义表的存储结构图,
Fig1 Theforceappliedtothetrainwhenrunning :w = w j +w q (3) :w = w = w 0 +w j (4) w i 121 基本阻力 w r = 600 R ( N/kN) (8) :R : [2] w s [3] w s =0
![Fig1 Theforceappliedtothetrainwhenrunning :w = w j +w q (3) :w = w = w 0 +w j (4) w i 121 基本阻力 w r = 600 R ( N/kN) (8) :R : [2] w s [3] w s =0](/thumbs/88/114838964.jpg "Fig1 Theforceappliedtothetrainwhenrunning :w = w j +w q (3) :w = w = w 0 +w j (4) w i 121 基本阻力 w r = 600 R ( N/kN) (8) :R : [2] w s [3] w s =0")
31 4 2012 8 JournalofLanzhouJiaotongUniversity Vol31No4 Aug2012 :1001-4373(2012)04-0097-07 * 张友兵 张 波 ( 100073) : 分析了列车运行过程中的受力情况 给出了制动过程中减速度的计算方法 并采用正向 反向两种迭代方式计算列车制动曲线 两种方式计算出的制动曲线一致 证明了计算制动曲线的方法是正确的
Microsoft PowerPoint - 2线性表.ppt [兼容模式]
![Microsoft PowerPoint - 2线性表.ppt [兼容模式]](/thumbs/80/82184163.jpg "Microsoft PowerPoint - 2线性表.ppt [兼容模式]")
2 线性表 董洪伟 http://hwdong.com 1 主要内容 线性表的类型定义 即抽象数据类型 顺序实现 即用一连续的存储空间来表示 链式实现 即用链表实现 一元稀疏多项式 链表实现 2 线性表的类型定义 线性表 n 个元素的有限序列 数据项 元素 ( 记录 ) 姓名 学号 性别 年龄 班级 健康状况 王小林 790631 男 18 计 91 健康 陈红 790632 女 20 计 91 一般
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:
吉林大学学报 工学版 ２４４ 第 ４ 卷 复杂 鉴于本文篇幅所限 具体公式可详见参考文 献 ７ 每帧的动力学方程建立及其解算方法如图 ３ 所示 图４ 滚转角速度与输入量 η 随时间的变化波形 Ｆｉｇ ４ Ｗａｖｅｆｏｒｍ ｏｆ ｒｏｌｌ ｒａｔｅ ａｎｄ ｉｎｐｕｔ η ｗｉｔｈ ｔｉｍｅ ｃｈａｎｇｉｎｇ 图５ Ｆｉｇ ５ 滚转角随时间的变化波形 Ｗａｖｅｆｏｒｍ ｏｆ ｒｏｌｌ ａｎｇｌｅ ｗｉｔｈ
Microsoft PowerPoint - 01_Introduction.ppt
Hello, World C 程序设计语言 第 1 章章观其大略 孙志岗 sun@hit.edu.cn http://sunner.cn prf("hello,, world\n"); 超级无敌考考你 : 如何把 hello 和 world 分别打印在两行? 2004-12-19 A Tutorial Introduction 2 hello.c 打印华氏温度与摄氏温度对照表 计算公式 : C=(5/9)(
PowerPoint 演示文稿
数据结构与算法 ( 十一 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五 国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 索引 基本概念 11.1 线性索引 11.2 静态索引 11.3 倒排索引 11.4 动态索引 11.5 位索引技术 11.6 红黑树 第十一章索引 2 索引 输入顺序文件
华侨大学 2014 年硕士研究生入学考试专业课试卷 B ( 答案必须写在答题纸上 ) 招生专业 计算机技术 科目名称 数据结构与 C++ 科目代码 850 第一部分 C++ ( 总分 75 分 ) 一 单项选择题 (18 分, 每小题 2 分 ) 1. 若有定义 :int a[3][4];, 则表达
![华侨大学 2014 年硕士研究生入学考试专业课试卷 B ( 答案必须写在答题纸上 ) 招生专业 计算机技术 科目名称 数据结构与 C++ 科目代码 850 第一部分 C++ ( 总分 75 分 ) 一 单项选择题 (18 分, 每小题 2 分 ) 1. 若有定义 :int a[3][4];, 则表达](/thumbs/96/128100622.jpg "华侨大学 2014 年硕士研究生入学考试专业课试卷 B ( 答案必须写在答题纸上 ) 招生专业 计算机技术 科目名称 数据结构与 C++ 科目代码 850 第一部分 C++ ( 总分 75 分 ) 一 单项选择题 (18 分, 每小题 2 分 ) 1. 若有定义 :int a[3][4];, 则表达")
华侨大学 2014 年硕士研究生入学考试专业课试卷 B ( 答案必须写在答题纸上 ) 招生专业 计算机技术 科目名称 数据结构与 C++ 科目代码 850 第一部分 C++ ( 总分 75 分 ) 一 单项选择题 (18 分, 每小题 2 分 ) 1. 若有定义 :int a[3][4];, 则表达式 sizeof(a)/sizeof(int[4]) 的值为 ( ) A) 3 B) 4 C) 5 D)
Microsoft Word - 作业.doc
董洪伟罗海驰李婷第 1 章绪论要点 1. 数据结构的逻辑结构和物理结构, 即数据结构从逻辑上分为 : 集合 一对一的线性结构 一对多的树型结构和多对多的图型结构 例如一维数组或链表都是线性结构, 称为线性表, 而多维数组则是图型结构 也有分为 : 线性结构和非线性结构 ( 集合 树 图 ) 一个实际问题的数据结构模型可能是混合型的结构, 既有线性结构的表也有其他非线性结构的树或图等 根据数据结构元素之间的逻辑关系在计算机内部表示
谷 德军 等 对 流边 界层 中 公 路 线 源 扩 散的 期 扩 散 的模 拟 式 大 气扩 散 的 方 法 是 把 污 染物 在 大 气 中 的 扩 散 看 成 标 记 粒 子 在 平 均 风 场 约束 下 的 随机 运 动 假 定 粒 子 的运 动 是 相 互独 立 的 向上 的 坐 标 为
谷 德军 等 对 流边 界层 中 公 路 线 源 扩 散的 期 扩 散 的模 拟 式 大 气扩 散 的 方 法 是 把 污 染物 在 大 气 中 的 扩 散 看 成 标 记 粒 子 在 平 均 风 场 约束 下 的 随机 运 动 假 定 粒 子 的运 动 是 相 互独 立 的 向上 的 坐 标 为 时间 步长 的 脉 动速 度 可 以 用 小 匡 每 个 粒 子 的运 动 为 小 分别 代表粒子 在