年龄问题解法与算法公式

___四__年级 _奥数__学科教案

北大屈婉玲算法分析与设计 习题解答4

Exercise1 说明：对于算法设计的习题，解题要求如下：先用一段简短的文字说明算法的主要设计思想，其中所引入的符号要给出必要的说明，是否给出伪码根据题目要求确定. 可以调用书上的算法作为子过程，最后对所设计的算法需要给出时间复杂度的分析. 1. 对以下函数，按照他们的阶从高到低排列；如果f (n )与g (n )的阶相等，表示为f (n )=Θ(g (n )). n n n n n n n n n n n n n n n n n n n n n log ,2,,log ,log log ,,,2,)(log ,log , )2/3(,,2,!,1,log ),!log(log 3log log 2log log /12 2. 求解以下递推方程： (1) ?????=++=1 )1(,)4()2()(T c cn n T n T n T 为常数 (2) ???=+=1 )1()log ()2/(5)(2 T n n n T n T 3．设A 是含有n 个元素的数组，如果元素x 在A 出现的次数大于n /2，则称x 是A 的主元素. (1) 对于可排序的数组，设计一个测试算法. (2) 如果A 中元素只能进行“是否相等”的测试，但是不能排序，设计一个算法判断A 中是否存在主元素. 4．设X [0:n ?1]和Y [0:n ?1]为2个数组，每个数组含有n 个已排好序的数。试设计一个O (log n )时间的算法，找出X 和Y 的2n 个数的中位数. 5．设S 是含有n 个数的数组，k 是给定正整数，k i k ，那么就称(i j ,i k )是这个排列的一个逆序. 一个排列含有逆序的个数称为这个排列的逆序数. 例如排列263451含有8个逆序(2,1), (6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，它的逆序数就是8. 显然，由1,2,…,n 构成的所有n !个排列中，最小的逆序数是0，对应的排列就是12…n ；最大的逆序数是n (n ?1)/2，对应的排列就是n (n ?1)…21. 逆序数越大的排列与原始排列的差异度就越大. 利用二分归并排序算法设计一个计数给定排列逆序的分治算法，并对算法进行时间复杂度的分析.

数据结构与算法-北大 HW11 B_B+树

北京大学信息学院2007年秋季学期《数据结构与算法A(实验班)》课程作业 张铭编写并发布 mzhang@https://www.doczj.com/doc/a617489430.html, 第11次作业，12月17日（周一）课前提交，电子稿提交时间12月17日开课之前提交。 11.1 偶数阶的B 树插入上溢出时，中 位数有两个，需要注意采用统一的策略。例如，取第二个中位数， 即分裂后左(1)/2m ?????个关键码，右(1)/2m ?????； 或者取第一个中位数，分裂后左(1)/2m ????? 右(1)/2m ?????。请画出对右图的4阶B 树进行下来操作后的B 树。 (1) 分裂时采用第2个中位数为 分界码，请画出插入关键码113后的B 树；分析插入操作的访外次数。 (2) 分裂时采用第1个中位数为分界码，请画出插入关键码113后的B 树；分析插入操 作的访外次数。 (3) 在原树中删除关键码50；分析删除操作的访外次数（与1、2题无关，从根重新开 始操作）。 11.2 已知一组关键码为(20, 30, 50, 52, 60, 68, 70)，试依次插入关键码。 (1) 生成一棵3阶的B +树，画出插入所有关键码后B 树的结构。 (2) 画出删除50后的B + 状态，分析删除操作的访外次数。 11.3 假设一个数据文件每个记录对象需要占用128 字节（其中关键码占用4字节），且所 有记录均已按关键码有序地存储在主磁盘文件中。设磁盘页块大小为2048（= 2K ）字节，若主存中有12M 空间可以用来存储索引结构，索引项中每一个地址指针占8 字节。请简要回答以下问题（请写明你的计算过程）。 （1） 使用B 树索引，B 树的阶m 1最多可以为多少？4层m 1阶B 树，最多可以索引多 少字节的数据文件？ （2） 使用B +树索引，B +树的阶m 2最多可以为多少? （3） 假设B +树的叶层各结点链接成双链结构，B +树的叶结点阶m 2’可以跟内部结点不 一样，则阶m 2’为多少? （4） 在第(3)小题的基础上，计算4层B +树（内部结点为m 2阶，叶结点m 2’阶），最多 可以索引多少字节的数据文件？ （5） 假设尽量把B +树的头几层放入内存（本题规定不能超过12M ），那么给定关键码， 通过B +树查找到(4)小题中主数据文件的一个记录，最少几次访外？最多几次访 外？ 11.4 对于下面两种B +树，列表给出他们在1、2、3、4和5层（独根是一层树）的不同情 况下，能够存储的最大记录数和最小记录数。 (1) 对于教材定义那样的B +树，其内部结点阶为50，叶结点阶为50。 (2) 如讲义P89那样的混合型B +树，其内部结点阶为55，叶结点阶为25（叶结点除关 键码，还索引部分记录信息）。 4阶B 树

北大屈婉玲算法分析与设计习题解答5.pdf

Exercise2 要求：对变量给出说明，动态算法要给出优化函数的递推方程、标记函数等，并给出时间复杂度分析。是否需要写伪码，看题目要求。对于给定实例，求出这个实例的解。 1. 有n 个底面为长方形的货柜需要租用库房存放. 如果每个货柜都必须放在地面上，且所有货柜的底面宽度都等于库房的宽度，那么第i 个货柜占用库房面积大小只需要用它的底面长度l i 来表示，i =1, 2, …, n . 设库房总长度是L ，且L l n i i >∑=1. 设库房单位长度的租金是常数c ，如果要求库房出租的收益达到最大，如何选择放入库房的货柜？设计一个算法求解这个问题，给出算法的伪码描述. 2. 设有n 种不同面值的硬币，第i 种硬币的币值是v k (其中v 1=1)，重量是w i ，i =1,2,…,n 且现在购有某些总价值为y 的商品，需要用这些硬币付款，如果每种钱币使用的个数不限，问如何选择付款的方法使得付出钱币的总重量最轻？设计一个求解该问题的算法. 假设问题的输入实例是： v 1=1, v 2=4, v 3=6, v 4=8 w 1=1, w 2=2, w 3=4, w 4=6 y =12 给出算法在该实例上计算的备忘录表和标记函数表，并说明付线的方法. 3. 有n 项作业的集合J ={1,2,…,n }，每项作业i 有加工时间t (i )∈Z +，效益值v (i )，任务的结束时间D ∈Z +，其中Z +表示正整数集合. 一个可行调度是对J 的子集A 中任务的一个安排，对于i ∈A ，f (i )是开始时间，且满足下述条件： f (i )+t (i )≤f (j ) 或者f (j )+t (j )≤f (i ), j ≠ i i , j ∈A D k t A k ≤∑∈)( 设机器从0时刻开动，只要有作业就不闲置，求具有最大总效益的调度. 给出算法的伪码. 4. 把0-1背包问题加以推广. 设有n 种物品，第i 种物品的价值是v i , 重量是w i ，体积是c i ，且装入背包的重量限制是W ，体积是V . 问如何选择装入背包的物品使得其总重不超过W ，总体积不超过V 且价值达到最大？ 5. 有n 个分别排好序的整数数组A 0，A 1, …, A n －1，其中A i 含有x i 个整数，i = 0,1,…,n －1. 已知这些数组顺序存放在一个圆环上，现在要将这些数组合并成一个排好序的大数组，且每次只能把两个在圆环上处于相邻位置的数组合并. 问如何选择这n －1次合并的次序以使得合并时总的比较次数达到最少？

OpenJudge算法设计与分析习题解答

1、硬币面值组合 描述 使用1角、2角、5角硬币组成n 角钱。 设1角、2角、5角的硬币各用了a、b、c个，列出所有可能的a, b, c组合。 输出顺序为：先按c的值从小到大，若c相同则按b的值从小到大。 输入 一个整数n（1 <= n <= 100)，代表需要组成的钱的角数。 输出 输出有若干行，每行的形式为： i a b c 第1列i代表当前行数（行数从001开始，固定3个字符宽度，宽度不足3的用0填充），后面3列a, b, c分别代表1角、2角、5角硬币的个数（每个数字固定12个字符宽度，宽度不足的在左边填充空格）。

源代码： #include #include int main(){ int t=1; int i,j,k; int n; scanf("%d",&n); int A=n,B=n/2,C=n/5; for(i=0;i<=C;i++){ for(j=0;j<=B;j++){ for(k=0;k<=A;k++){ if(i*5+j*2+k*1==n){ printf("%03d%12d%12d%12d\n",t,k,j,i); t++; } } } } getchar(); return 0; } 2、比赛排名 描述 5名运动员参加100米赛跑，各自对比赛结果进行了预测：A说：E是第1名。 B说：我是第2名。 C说：A肯定垫底。 D说：C肯定拿不了第1名。

E说：D应该是第1名。 比赛结束后发现，只有获第1名和第2名的选手猜对了，E不是第2名和第3名，没有出现名次并列的情况。 请编程判断5位选手各是第几名。 输入 无 输出 输出要求：按ABCDE的顺序输出5行，其中第1行是A的名次，第2行是B的名次，第3行是C的名次，第4行是D的名次，第5行是E的名次。 样例输入 样例输出 源代码： #include int main() { printf("5\n"); printf("2\n"); printf("1\n"); printf("3\n"); printf("4\n"); return 0; } 3、鸡兔同笼 描述 一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。

北大2015年秋季学期数据结构课程作业

2015年秋季学期《数据结构》课程作业 一. 单选题，每空有一个正确选择，请将正确的选择填在题号前边。（每空1分，共30分） 1.鼓励独立完成作业，严惩抄袭！数据的逻辑结构被形式地定义为B=(K,R),其中K 是 ____C__的有限集合，R是K上的___H___的有限集合。（第一章） a 存储 b 数据操作c数据元素d操作 e逻辑结构 f 映象 g算法h关系 2.以下关于算法的说法不正确的是____B _________。（第一章） a 一个算法应包含有限个步骤 b算法越简单越好 c算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之 d算法中的每个步骤都能在有限时间内完成 3．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03， 07>，<03，08>，<03，09>}，则数据结构A是______B________。（第一章） a 线性结构 b 树型结构 c 物理结构 d 图型结构 4.下面程序段的时间复杂度为___C___（第一章） int sum=0; for(i=0; i

北大PKU 慕课 EDX 数据结构与算法 第七章图 quiz答案与解析

第七章树

PROBLEM 2 (1/1 分) 一个深度为h的满k叉树，最多有多少个结点？（独根树深度为0）There is a full k-ary tree, whose depth is h. How many nodes can it have at most? (The depth of a tree, which only has a root node, is 0.) k^(h-1) k^h (k^(h+1)-1)/(k-1) (k^(h+1)-1)/(k-1) - 正确 (k^h-1)/(k-1) Explanation 层数---节点数 number of levels---number of nodes 0---1 1---k 2---k^2 3---k^3 .... h---k^h 所以答案是： so, the answer is： 1+k+k^2+k^3+...+k^h = (k^(h+1)-1)/(k-1)

PROBLEM 3 (1/1 分) 2-3树是一种特殊的树，它满足两个条件： （1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同； 如果一棵2-3树有9个叶结点，那么它可能有_________个非叶结点。(多项) 2-3 tree is a special kind of tree, it satisfy: （1）Every internal node has 2 or 3 child nodes. (2)All the leaf nodes have the same length of the path to the root node. If a 2-3 tree has 9 leaf nodes, then it may have __________ non-leaf nodes.（There are more than one correct answers） 4, 7, - 正确 4 5 6 7 Explanation 倒数第二层若是3个结点，深度为2，加上根结点，一共4个非叶子结点。 倒数第二层若是4个结点，深度为3，倒数第三层（第二层）有2个结点，一共4+2+1=7个非叶子结点。 If the second level from the bottom has 3 nodes, the depth of tree will be 2, and the tree will has 4 non-leaf nodes, including the root node. If the second level from the bottom has 4 nodes, the depth of tree will be 3, the third level from the bottom will has 2 nodes, and the tree will has 4+2+1=7 non-leaf nodes

北京大学算法设计与分析课09年期末试题

内部资料，转载请注明出处，谢谢合作。 北京大学信息科学技术学院考试试卷 考试科目：算法设计与分析 姓名： 学号： 考试时间：2009年6月9日 任课教师: 以下为试题和答题纸，共 9 页。

一、填空题(选做5道，10分) 1．用矩阵幂的方法求斐波那契数，其运行时间为（）。2．对于一个可以用动态规划法求解的问题，要求问题既要满足（）的特性，又要具有大量的（）。3．对于一个可以用贪心法求解的问题，不仅要求问题满足 （）的特性，还应证明其贪心策略的（）。4．设有n个栈操作（PUSH、POP、MULTIPOP ）的序列，作用于初始为空的栈S。不区分三种操作，则每个操作的最坏运行时间为（），平摊运行时间为（）。 5．三种平摊分析的方法分别为（）、（）、（）。 6．四后问题的搜索空间为（）树；0-1背包问题的搜索空间为（）树；巡回售货员问题的搜索空间为（）树。 7．（）法的求解目标是找出解空间树中满足约束条件的所有解，而（）法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 8．回溯法一般以（）优先的方式搜索解空间树，而分支限界法则一般以（）优先或以最小耗费优先的方 式搜索解空间树。

二、单项选择题(10分) Array 1．下列关于排序算法的叙述，不正确的是？（） A) 堆排序的最差情形运行时间为Θ(n lg n) B) 快速排序平均情形运行时间为Θ(n lg n) C) 任何排序算法的最差情形运行时间都不可能比Ω(n lg n)更小 D) 插入排序在最好情形下的运行时间为Θ(n) 2．对于课堂讲解的线性时间内找第i小的元素的算法，（） 下列叙述中不正确的是？ A) 算法第一步中可以按每五个元素一组找中位数； B) 算法第一步中可以按每七个元素一组找中位数； B) 算法第一步中不能按每三个元素一组找中位数； D) 如果要求的n个元素的中位数，则中位数一定是第一步中找到的中 位数中的某一个。 3．主方法可以求解满足形如下式的递推方程，（） A) 对于系数a，必须满足a≥1 B) 对于系数b，必须满足b > 1 C) 若对于常数ε> 0，f(n)=O(n log b a-ε)，则T(n)=Θ(n log b a) D) 若f(n)=O(n log b a)，则T(n)=Θ(n log b a log n) 4．下列哪些问题不能用贪心法求解？（） A) 霍夫曼编码问题B) 单源最短路径问题 C) 0-1背包问题D) 最小生成树问题

北京大学数据结构与算法信科数算2007秋期末考试题

北京大学信息科学技术学院考试试卷 考试科目：数据结构与算法A 姓名： 学号： 考试时间： 2008年 1 月 9 日 教师: 张铭、赵海燕、王腾蛟、宋国杰 以下为试题和答题纸，共 4 页。 题号 一 二 三 四 五六 七 八 总分 分数 阅卷人

第 1 页 一、（共30分，每空3分）填空 1. 1．无向图G=(V , E)，其中：V={a, b, c, d, e, f}, E={(a, b), (a, e), (a, c), (b, e), (c, f), (f, d), (e, d)}，对该图进行深度优先遍历，得到的顶点序列正确的是____。 A ．a,b,e,c,d,f B ．a,c,f,e,b,d C ．a,e,b,c,f,d D ．a,e,d,f,c,b 2. 下图中的强连通分量的个数为________个。 3. 设有向图G 如下: 写出所有拓扑序列:___________________________________________ 添加一条弧________________________之后, 则仅有唯一的拓扑序列. 4. 请问下面哪些操作在已排序数据上实施比在无序的数据上快 ？ A ．找最小值 B. 计算算术平均值 C. 找中位数 D. 找出现次数最多的值 5. 序列{15，142，51，68，121，46，57，575，60，89，185 }按最低位优先法进 行基数排序，进行一次分配和收集后得到的序列 。 6. 设输入的关键码满足k 1>k 2>…>k n ，缓冲区大小为m ，用最小值堆进行置换-选择 排序方法可产生____个初始归并段。 7. 在包含n 个关键码的线性表中进行顺序检索，若检索第i 个关键码的概率为p i , 且 分布如下： n n n n p p p p 21,21,....,41,211121====?? 成功检索的平均检索长度是_______________。 8. 假设计算机系统有2048个字节的磁盘块，要存储的每一条记录中4个字节是关 键码，磁盘指针4个字节，64个字节是数据字段。记录已经排序，顺序地存储

北京大学屈婉玲算法设计与分析最新课件07

第7章NP完全性 主要内容 Turing机 计算复杂性理论 NP完全性理论的基本概念 用NP完全性理论分析问题 NP难度

Turing机的定义基本模型双向无限带的Turing机 = M= < Q, ∑, Γ, δ, q0, B, F >, 其中 Q有穷状态集 Γ有穷带字符集 ∑输入字符集∑?Γ B空白字符, B∈Γ－∑ q 0初始状态, q ∈Q F终结状态集, F?Q,q Y, q N∈F :(－L R} δ: (Q F)×Γ→Q×Γ×{L,R} 状态转移函数 B x1x2x3… x n B带 读写头 有限状态控制器FSC

瞬时描述-格局(ID)α1qα2表示此刻Turing机的FSC处于状态q, 读写头指在串α2的第一个字符. 的第个字符 例如g机的某时刻的状态转移函数是 Turing M δ(q, x i) = (p,Y,L) 带上的字符串为x x2... x i... x n, 读写头指向字符x, 则它的 1 2 i n i 瞬间描述是: x1x2 ... x i-1q x i ... x n?x1x2...x i-2 p x i-1Yx i+1 ... x n ?表示由左边的ID一步达到右边的ID * ?表示由左边的ID经有限步达到右边的ID

实例 设L={ 0n1n | n ≥1 }, 设计接受L 的Turing机如下: = M<> Q= { q0, q1, q2, q3, q Y, q N}, ∑= { 0, 1}, {01} Γ= { 0, 1, X, Y, B }, F= { q Y,q N} { 初始将字符串放在从1 到n 方格中, FSC处在状态q, 读写头 指向方格1. 将第一个0改写成X, 然后带头向右扫描. 遇到第,, 一个1, 将1改为Y, 然后带头向左扫描. 遇到第一个X 改为向右扫描. 这时进入下一个巡回. 每个巡回将一对0 和1 改为X ,到接受或拒斥停机 和Y, 直到接受或拒斥停机.

北京大学算法设计与分析课09年期末试题

北京大学算法设计与分析课09年期末试题

内部资料，转载请注明出处，谢谢合作。 北京大学信息科学技术学院考试试卷 考试科目：算法设计与分析姓名：学号： 考试时间：2009年6月9日任课教师: 题号一二三四五六七八总分 分数 阅卷人 考场纪律 1．请持学生证入场考试，并按指定座位 就座；除必要的文具和教师指定的用具 用书外，其他所有物品包括手机、呼机、 MP3、电子词典、书籍、笔记、纸张等 严禁带入座位，必须放在指定位置。凡 有试题印制问题请向监考教师提出，不 得向其他考生询问。

2．认真、诚实、独立并在规定时间内完 成答卷，严禁任何形式的违纪作弊行为；否则，本答卷成绩以0分记，并根 据《北京大学本科考试工作与学术规范 条例》给予纪律处分。 3．提前交卷的考生不要在考场逗留，不 要在门口、窗外大声喧哗。考试结束时 间到，请停止答卷，在座位等候监考教 师收卷并清点完毕，方可离开考场；考 题和试卷不得带出考场。 以下为试题和答题纸，共9 页。 一、填空题(选做5道，10分) 1．用矩阵幂的方法求斐波那契数，其运行时间为（）。2．对于一个可以用动态规划法求解的问题，要求问题既要满足 （）的特性，又要具有大量的（）。3．对于一个可以用贪心法求解的问题，不仅要求问题满足 （）的特性，还应证明其贪心策略的（）。

4．设有n个栈操作（PUSH、POP、MULTIPOP ）的序列，作用于初始为空的栈S。不区分三种操作，则每个操作的最坏运行时间为 （），平摊运行时间为（）。 5．三种平摊分析的方法分别为（）、（）、（）。 6．四后问题的搜索空间为（）树；0-1背包问题的搜索空间为（）树；巡回售货员问题的搜索空间为（）树。 7．（）法的求解目标是找出解空间树中满足约束条件的所有解，而（）法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。8．回溯法一般以（）优先的方式搜索解空间树，而分支限界法则一般以（）优先或以最小耗费优先的方式搜索解空间树。

北京大学数据结构基础-chap6

数据结构与算法(五) 张铭主讲 采用教材：张铭，王腾蛟，赵海燕编写 高等教育出版社，2008. 6 （“十一五”国家级规划教材） 张铭《数据结构与算法》

第五章 二叉树 ?二叉树的概念 ?二叉树的抽象数据类型?深度优先搜索 ?宽度优先搜索?二叉树的存储结构?二叉搜索树 ?堆与优先队列?Huffman树及其应用 H G E A B C D F I 第五章二叉树

第五章二叉树 5.4 二叉搜索树 二叉搜索树 ?Binary Search Tree （BST ） ?或者是一棵空树； ?或者是具有下列性质的二叉树： ?对于任何一个结点，设其值为K ?则该结点的左子树(若不空)的任意一个结点的值都小于K ；?该结点的右子树(若不空)的任意一个结点的值都大于K ；? 而且它的左右子树也分别为BST ?性质: 中序遍历是正序的（由小到大的排列） 15 1822 51 7 8921 3 488 60 93 35 17 65

BST 示意图 wim wen yum xul wul xal wan zol wil zom yo xem zi yon

检索19 1219 2251 7 8 9 2 1 3 4 88 60 93 35 16 6?只需检索二个子树之一 ?直到K被找到 ?或遇上树叶仍找不到，则不存在 5

二叉树 5.4 二叉搜索树 插入17 ?首先是检索，若找到则不允许插入?若失败，则在该位置插入一个新叶?保持BST性质和性能！ 1219 22 51 7 8 9 2 13 4 88 60 93 35 16 6 17 2’ 5

数据结构与算法小测

2014年秋季北大《数据结构与算法B》随堂摸底测试A 学号_______________ 姓名_______________ 教师/教室____________________ 1.下列说法正确的是（） A.空串就是内容空白的串 B.字符串可以采用顺序存储，也可以采用链式存储 C.字符串是一种数据和操作都特殊的线性表 D.在C++标准中，char S[N]最多能表示长度为N的字符串 2.下列关于堆（Heap）的说法正确的有（） A.最小堆（任何结点值都比其左右子树小）最底层最靠右的结点一定是权值最大的结点。 B.堆一定是满二叉树（满二叉树每个结点有0个或2个孩子）。 C.最小堆中，某个结点左子树中最大的结点可能比右子树中最小的结点小。 D.初始建堆时，要使用筛选法建堆要比将元素一个一个插入堆来建堆效率高。 3.下列关于二叉搜索树（Binary Search Tree）的说法正确的有（） A.二叉搜索树按照中序遍历将各结点打印出来，将得到按照由小到大的排列。 B.二叉搜索树一定是满二叉树。 C.当根结点没有左儿子时，根结点一定是二叉搜索树中值最小的结点。 D.如果结点x的左儿子有右子树，则说明存在某个结点的值介于结点x的值和x左儿子的值 之间，并且这个结点在x的左子树之中。 4.下列关于Huffman树和Huffman编码的说法正确的有（） A.Huffman树一定是扩充的二叉树（度为1的结点增加1个外部结点，度为0的增加2个）。 B.对于具有同样的一组权值的内容可以得到不同的Huffman编码方案。 C.Huffman树（具有最小外部路径权重和的二叉树）一定是完全二叉树（除离根最远的底层， 其他每层都铺满了结点；最底层的结点也尽可能排在左侧的二叉树）。 D.Huffman编码中所有编码都是等长的。 5.设栈S 和队列Q 的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素 出栈后即进队列Q，若6 个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是。 6.在一棵深度（独根树深度为0）为K的完全二叉树（只有最下层结点度数可以小于2，并 且最下面一层结点都在该层最左边的连续位置上）中，至少存在个结点。 7.已知一棵二叉树的中序遍历序列为DBGEACF，后序遍历序列为DGEBFCA，这棵树的前序遍历序 列为： 8.将1，2，3，………, n顺序入栈，其输出序列为p1, p2, p3,……,p n若p1=n, 则p i为： 9.对于3个结点A,B,C，有棵不同的二叉树（不是树型，是树）？ 10.在一棵非空二叉树中，若（出）度为0的结点的个数n，度为2的结点个数为m，则有n= 。 11.算法填空题(如果填空的思路跟自己不一致，可以自己写思路、完整的带注释算法框架)。 在下面算法中填写合适的语句（每个空缺可以填写0条或多条语句），使得算法功能完整。 一棵二叉树中所有叶结点的最大枝长和最小枝长分别定义如下：

北京大学屈婉玲算法设计与分析最新课件0r4

第4章贪心法 （Greedy Approach） 4.1 贪心法的设计思想 4.2贪心法的正确性证明 4.3对贪心法得不到最优解情况的处理 4.4贪心法的典型应用 44 4.4.1最优前缀码 4.4.2最小生成树 4.4.3单源最短路径

4.1贪心法的设计思想 活动选择问题={12i i 输入：S {1, 2, … , n }为n 项活动的集合，s i , f i 分别为活动i 的开始和结束时间，活动i 与j 相容?s i ≥f j 或s j ≥f i .求：最大的两两相容的活动集A 实例 i 12345678910s i 1325456882f i 4 5 6 7 9 9 10 11 12 13 策略1：排序使得s 1≤s 2≤…≤s n ，从前向后挑选排序使得从前向后挑选策略2：排序使得f 1－s 1≤f 2－s 2≤…≤f n －s n ，从前向后挑选策略3：排序使得f 1≤f 2≤…≤f n ，从前向后挑选以上策略中的挑选都要注意满足相容性条件

两个反例 =0, f1=20,s2=2, f2=5, s3=8, f3=15 策略1：S={1,2,3}，s 1 =0,f1=8,s2=7,f2=9,s3=8,f3=15 策略2：S={1,2,3}，s 1 23 1 0 2 5 8 10 15 20 2 1 3 0 2 5 8 10 15 20

贪心算法 算法Greedy Select =12输入：活动集S ，s i ，f i , i =1,2,…,n ，且f 1≤… ≤f n 输出：A ?S ，选中的活动子集1]//1. n ←length [S ] // 活动个数 2. A ←{1}31//已选入的最后一个活动的标号3. j ←1 //已选入的最后个活动的标号 4. for i ←2 to n do 5if 5. if s i ≥f j //判断相容性6. then A ←A ∪{i }77. j ←i 8. return A 最后完成时间t = max { f k : k ∈A }

北大数据结构课件,内部资料,精品

数据结构课程的知识体系和教学实践 张铭许卓群杨冬青唐世渭/文 一、数据结构知识体系 计算机科学已经深入应用到各个领域，不仅有效地解决了各种工程和科学计算中的数值计算问题，而且也有效地解决了许多文本处理、信息检索、数据库管理、图像识别、人工智能等非数值的数据处理问题。数据结构有助于程序员更有效地组织数据、设计高效的算法、完成高质量的程序以满足错综复杂的实际需要。 数据结构是计算机学科的重要分支研究领域。数据结构和算法在计算机学科中的地位十分重要，其他计算机科学领域及有关的应用软件都要使用到各种数据结构。数据结构是算法分析与设计、操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等专业基础课和专业课程的先行课程。语言编译要使用栈、散列表及语法树；操作系统中用队列、存储管理表及目录树等；数据库系统运用线性表，多链表及索引树等进行数据管理；而在人工智能领域，依求解问题性质的差异将涉及到各种不同的数据结构，如广义表，集合、搜索树及各种有向图等等。 美国IEEE和ACM的教学计划CC2001把《算法与数据结构》列入计算机以及信息技术相关学科专业的本科必修基础课程。在我国，《数据结构》已经作为理工科非计算机专业必修的信息技术基础课程之一。世界上许多科技人员对学习、研究数据结构都非常重视，对于从事计算机科学及其应用的科技工作者来说，数据结构更是必须透彻地掌握的重要基础。 1．数据的逻辑结构、存储结构和运算 从字面上来看，数据结构就是指数据间的相互关系。具体到计算机环境，谈到任何一种结构时，都自然地联系着作用在这种类型的数据上的运算（即函数），为了在计算机上执行这些运算，我们有必要把这些数据以某种方式存储在计算机中。因此，我们可以认为，所谓数据结构，就是由某种逻辑关系组织起来的一批数据，按一定的存储方法被存储于计算机中，并在这些数据上定义了一个运算的集合。也就是说，数据结构具有三个方面：数据的逻辑结构、数据的存储结构和数据的运算。 常见逻辑关系有：线性结构、树形结构、图结构和文件结构。其中，线性结构是最简单的数据结构，例如，程序设计语言中往往都会介绍的线性表（包括数组和链表）、栈、队列、向量、字符串等。其中，字符串就是每个结点都是单个字符的线性表。实际上多维数组和广义表也是线性结构的推广。另外，文件其本质也是线性结构，不过由于存储在外存中，对文件数据的访问速度非常慢，因此，仔细研究文件结构和基于文件的外排序也是很有必要的。二叉树和树是非常重要的数据结构，其应用十分灵活而广泛。二叉树可以看作是树的特例。例如，语言编译中要用到语法树，操作系统有目录树，数据库系统需要用索引树等进行数据管理，而在人工智能领域，需要用到搜索树等。许多真实世界的问题都可以图来抽象地定义。例如，一张交通图可以用数据结构的图来形象化地表示：用结点表示城市，用边表示连接城市的高速公路；Web网页的关系也可以表示为图：Web网页作为结点，网页之间的链接作为边。图是一种最通用的逻辑结构，实际上，图?树?二叉树?线性表。 常见的存储方法有：顺序方法、链接方法、索引方法、散列方法。其中，索引存储又分为线性和树形两种。文件结构的索引则往往用树形结构。 对于一种数据结构，往往需要定义一些运算。例如，建立数据结构、清除数据结构、

北京大学算法设计方案与分析课期末试题

北京大学信息科学技术学院考试试卷 考试科目：算法设计与分析姓名： 学号： 考试时间：2009年6月9日任课教师: 以下为试卷和答题纸，共 9页。

一、填空题(选做5道，10分> 1．用矩阵幂的方法求斐波那契数，其运行时间为<）。2．对于一个可以用动态规划法求解的问题，要求问题既要满足<）的特性，又要具有大量的< ）。 3．对于一个可以用贪心法求解的问题，不仅要求问题满足<）的特性，还应证明其贪心策略的< ）。 4．设有n个栈操作

8．回溯法一般以<）优先的方式搜索解空间树，而分支限界法则一般以<）优先或以最小耗费优先的方式搜索解空 间树。 二、单项选择题 (10分> Array 1．下列关于排序算法的叙述，不正确的是？<） A> 堆排序的最差情形运行时间为Θ(nlgn>B> 快速排 序平均情形运行时间为Θ(nlgn> C> 任何排序算法的最差情形运行时间都不可能比 Ω(nlgn>更小D> 插入排序在最好情形下的运行时间为 Θ(n> 2．对于课堂讲解的线性时间内找第i小的元素的算法，<）下列叙述中不正确的是？ A> 算法第一步中可以按每五个元素一组找中位数；B> 算法第一步中可以按每七个元素一组找中位数；B> 算 法第一步中不能按每三个元素一组找中位数；D> 如果 要求的n个元素的中位数，则中位数一定是第一步中找 到的中位数中的某一个。

北大 算法 习题解析 solution4

第4次作业 1． 最小重量机器设计问题. 某机器由n 个部件构成，每种部件可以从m 个不同的供应商购 买. 设w ij 是从供应商j 购买部件i 的重量， c ij 是从供应商j 购买部件i 的价格. 如下给出该问题的一个实例，求总价值不超过120，总重量最轻的解。 . 解：按照价格从小到大对零件排序. 设解向量为, 其中x i =j 表示第i 号零件由j 号供应商供货. 1≤x j ≤m . 结点表示已经选择了前k 号零件的供应商, 约束条件是选择了下一个零件后总价格不超过120. 代价函数为 ∑∑+===+ n k j jl m l k i x w w k 1,...2,11}{min 其中w jl 表示第l 个供应商j 号零件的重量. 其中前面的和为到目前为止已经选定零件的总重，后面的和为剩下零件的重量的下界（每种零件选最轻的计算）. 界为目前可行解的总重量. 树省略，解为<3,1,2,3>, 总重量为31，价值为119. 2．用回溯法求下列不等式的所有的整数解。要求给出伪码和解。 ???≤++为非负整数3 21321,,12243x x x x x x 伪码略. 可行解： <0,0,0>, <0,0,1>, <0,0,2>, <0,0,3>, <0,0,4>, <0,0,5>, <0,0,6>, <0,1,0>, <0,1,1>, <0,1,2>, <0,1,3>, <0,1,4>, <0,2,0>, <0,2,1>,<0,2,2>, <0,3,0>,<1,0,0>,<1,0,1>,<1,0,2>,<1,0,3>,<1,0,4>,<1,1,0>, <1,1,1>, <1,1,2>, <1,2,0>,<2,0,0>,<2,0,1>,<2,0,2>, <2,0,3>, <2,1,0>, <2,1,1>, <3,0,0>, <3,0,1>, <4,0,0> 3. 如图所示，一个4阶Latin 方是一个4×4的方格，在它的每个方格内填入1,2,3或者4，并使得每个数字在每行、每列都恰好出现一次。用回溯法求出所有第一行为1,2,3,4的4阶Latin 方。将每个解的第2-4行的数字从左到右写成一个序列。例如图中的Latin 方对应于解：3,4,1,2,4,3,2,1,2,1,4,3。 1 2 3 4 3 4 1 2 4 3 2 1 零件 编号 供应商1 供应商2 供应商3 价格 重量 价格 重量 价格 重量 1 10 5 8 6 1 2 4 2 20 8 21 10 30 5 3 40 5 42 4 30 10 4 30 20 60 10 4 5 15

数据结构与算法-北大 HW4 BST、堆、Huffman

第4次作业，10月15日9：00课间提交，电子稿提交时间10月15日8：00之前。 4.1 假设BST允许重复关键码，在插入关键码K时，找到同义词K’, 那么K插入在K’为根的右子树中，当作右子树中序周游的第一个结点。 编写一个递归函数printRange，传入一个BST的根，一个较小的值和一个较大的值，按照顺序打印出介于两个值之间的所有结点，并返回重复关键码数目。函数printRange应尽可能少地访问BST的结点。PrintRange的原型为： template int printRange(BinaryTreeNode *root, T min, T max); 注释：重复关键码数目作为函数值返回。1 1 1 2 2 2 3 5的重复关键码数目是6，打印“重复关键码1 1 1 2 2 2”。1 2 3 4 5返回0，打印“重复关键码集为空”。 4.2 除了查找、插入和删除操作以外，有的应用还需要合并和分裂操作，请实现下面三种操作： （1） C.ThreeWayJoin(A, x, B)： 构建C，C由原来在A和B中的元素以及元素x构成。假设A中元素的关键字小于x.key，B中元素的关键字大于x.key。最后将A和B设置为空。 （2） C.TwoWayJoin(A, B)： 构建C，C由原来在A和B中的元素构成。假设A中所有元素的关键字小于B中所有元素的关键字。最后将A和B设置为空。 （3） A.Split(i, B, x, C)： 分裂为三部分：B包含A中所有关键字小于i的元素；如果A含关键字为i的元素，则将该元素复制到x，并返回x的指针，否则返回0；C包含A中所有关键字大于i的元素。最后将A设置为空。 4.3定义：双堆是一棵完全二叉树。该树或者为空，或者满足下列性质： （1） 根结点不含元素。 （2） 左子树是最小堆。 （3） 右子树是最大堆。 （4） 若右子树不空，设i为左子树中的任意结点，j为右子树中的对应结点。若这样的j 不存在，则令j为右子树中对应i的父结点。结点i中的key小于或等于结点j中的key。 左下图是一个双堆。最小堆的根结点含5，最大堆的根结点含45。最小堆结点10与最大堆结点25对应。最小堆中结点9，在性质（4）中定义的结点j是最大堆中结点40。 根据双堆定义，在具有n个元素的双堆中（n > 1），最小元素在最小堆的根结点中，最大元素在最大堆的根结点中。若n = 1，则最小和最大元素相同，在最小堆的根结点中。 在左下图插入4，j指向双堆中的新结点，i为其最小堆中对应结点。为了满足性质（4），交换4和19，然后调整最小堆。

数据结构与算法

数据结构与算法 第十章索引技术 任课教员：张铭 https://www.doczj.com/doc/a617489430.html,/mzhang/DS/ mzhang@https://www.doczj.com/doc/a617489430.html, 北京大学信息科学与技术学院网络与信息系统研究所?版权所有，转载或翻印必究 北京大学信息学院 ?版权所有，转载或翻印必究 Page 2 主要内容 10.1 线性索引 10.2 静态索引 10.3 倒排索引 10.4 动态索引 10.5 动态、静态索引性能比较 北京大学信息学院?版权所有，转载或翻印必究Page 3基本概念 输入顺序文件 主码与辅码 索引与索引文件 稠密索引与稀疏索引 北京大学信息学院?版权所有，转载或翻印必究Page 4 输入顺序文件 输入顺序文件( entry-sequenced file )按照记录进入系统的顺序存储记录 一般说来,输入顺序文件的结构相当于一个磁盘中未排序的线性表 因此不支持高效率的检索 北京大学信息学院?版权所有，转载或翻印必究Page 5主码 主码( primary key )是数据库中的每条记录的唯一标识 例如，公司职员信息的记录的主码可以是职员的身份证号码 如果只有主码，不便于各种灵活检索 北京大学信息学院?版权所有，转载或翻印必究Page 6 辅码 辅码( secondary key )是数据库中可以出现重复值的码 辅码索引把一个辅码值与具有这个辅码值的每一条记录的主码值关联起来 大多数检索都是利用辅码索引来完成的

北京大学信息学院 ?版权所有，转载或翻印必究 Page 7 索引 索引( indexing )是把一个关键码与它对应的数据记录的位置相关联的过程 索引技术是组织大型数据库的一种重要技术 数据库组织存储在外存中的大量记录 高效率的检索 插入、更新、删除 北京大学信息学院 ?版权所有，转载或翻印必究 Page 8 索引文件 索引文件( index file )是用于记录这种联系（关键码与它对应的数据记录的位置）的文件组织结构。 索引文件的记录 （关键码，指针）对 指针指向主要数据库文件（也称为“主文件”）中的完整记录 北京大学信息学院?版权所有，转载或翻印必究Page 9索引文件 索引文件并不需要重新排列记录在磁盘中的顺序（不用重排主文件） 一个数据库可能有多个相关的索引文件 每个索引文件往往支持一个关键码字段 可以通过该索引文件高效访问记录中该关键码值 北京大学信息学院 ?版权所有，转载或翻印必究 Page 10 稠密索引 对每一个记录建立一个索引项，这样建立的索引被称为稠密索引( dense index ) 数据库文件中的记录不按照关键码的顺序排列时（比如按照加入的顺序排列） 北京大学信息学院?版权所有，转载或翻印必究 Page 11 稀疏索引 对一组记录建立一个索引项，这种索引称之为稀疏索引( spare index ) 当记录在磁盘中是按照关键码的顺序存放 可以把记录分成多个组（块） 稀疏索引索引项的指针指向的是这一组记录在磁盘中的起始位置 北京大学信息学院?版权所有，转载或翻印必究Page 12 10.1 线性索引 基本概念 线性索引的优点 线性索引的问题 二级线性索引