北京大学数据结构基础-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

二叉树

wim

wen

yum

xul

wul

xal

wan zol

wil yo

xem

zi

yon

?删除wan ?

删除zol

zom zoo

二叉树

5.4 二叉搜索树

BST 删除(值替换)

void BinarySearchTree:::removehelp(BinaryTreeNode *& rt, const T val) {

if (rt==NULL) cout<

else if (val < rt->value()) removehelp(rt->leftchild(), val);

else if (val > rt->value()) removehelp(rt->rightchild(), val);else { // 真正的删除

BinaryTreeNode * temp = rt;

if (rt->leftchild() == NULL) rt = rt->rightchild(); else if (rt->rightchild() == NULL) rt = rt->leftchild(); else {

temp = deletemin(rt->rightchild()); A

B G D J F H

C K E I

找rt右子树中最小结点，并删除template

BinaryTreeNode* BST::deletemin(BinaryTreeNode *& rt) { if(rt->leftchild() != NULL)

return deletemin(rt->leftchild());

else{ // 找到右子树中最小，删除

BinaryTreeNode *temp = rt;

rt= rt->rightchild();

return temp;

}

}A

B G

D

J

F H

C

K E

I

二叉搜索树总结

?组织内存索引

?二叉搜索树是适用于内存储器的一种重要的树形索引?常用红黑树、伸展树等，以维持平衡

?外存常用B/B+树

?保持性质vs 保持性能

?插入新结点或删除已有结点，要保证操作结束后仍符合二叉搜索树的定义

思考

?怎样防止BST退化为线性结构？

7

32

37

40

思考

?允许重复关键码吗？

?插入、检索、删除

120

32

132

42

7

42

2

37

24

40

二叉树

?二叉树的概念

?二叉树的抽象数据类型?深度优先搜索

?宽度优先搜索?二叉树的存储结构?二叉搜索树

?堆与优先队列?Huffman树及其应用

H

G

E

A

B C

D

F

I

第五章二叉树

堆的定义及其实现

?

最小堆：最小堆是一个关键码序列{ K 0，K 1，…K n-1}，它具有如下特性：

?K i ≤K 2i+1(i=0，1，…，?n/2?-1)?K i ≤K 2i 十2

?类似可以定义最大堆

41628

5931440

1

23

45

堆的性质

?完全二叉树的层次序列，可以用数组表示?堆中储存的数是局部有序的，堆不唯一?结点的值与其孩子的值之间存在限制

?任何一个结点与其兄弟之间都没有直接的限制?从逻辑角度看，堆实际上是一种树形结构

4

1628

59 3144

12

345

堆的类定义template

class MinHeap{ // 最小堆ADT定义

private:

T* heapArray; // 存放堆数据的数组

int CurrentSize; // 当前堆中元素数目

int MaxSize; // 堆所能容纳的最大元素数目

void BuildHeap(); // 建堆

public:

MinHeap(const int n)；// 构造函数,n为最大元素数目

virtual~MinHeap(){delete[]heapArray;}; // 析构函数

bool isLeaf(int pos) const; // 如果是叶结点，返回TRUE

int leftchild(int pos) const; // 返回左孩子位置

int rightchild(int pos) const; // 返回右孩子位置

int parent(int pos) const; // 返回父结点位置

bool Remove(int pos, T& node); // 删除给定下标的元素

bool Insert(const T& newNode)；// 向堆中插入新元素newNode

T& RemoveMin()；// 从堆顶删除最小值

void SiftUp(int position); // 从position向上开始调整，使序列成为堆void SiftDown(int left)；// 筛选法函数，参数left表示开始处理的数组下标｝

对最小堆用筛选法SiftDown调整template

void MinHeap::SiftDown(int position) {

int i= position; // 标识父结点

int j = 2*i+1; // 标识关键值较小的子结点

Ttemp= heapArray[i]; // 保存父结点

72

2305

689471

16

while(j < CurrentSize) {

if((j < CurrentSize-1)&&

(heapArray[j] > heapArray[j+1])) j++; // j指向数值较小的子结点if(temp > heapArray[j]) {

heapArray[i] = heapArray[j];

i= j;

j = 2*j + 1; // 向下继续

}

else break;

}

heapArray[i]=temp;

}

72

2305

16 6894

对最小堆用筛选法SiftDown调整

71

对最小堆用筛选法SiftUp向上调整template

void MinHeap::SiftUp(int position) {

// 从position向上开始调整，使序列成为堆

int temppos=position;

// 不是父子结点直接swap

T temp=heapArray[temppos];

while((temppos>0) && (heapArray[parent(temppos)] > temp)) { heapArray[temppos]=heapArray[parent(temppos)];

temppos=parent(temppos);

}

heapArray[temppos]=temp;// 找到最终位置

}

二叉树 5.5 堆与优先队列

建最小堆过程

?首先，将n 个关键码放到一维数组中?整体不是最小堆

?所有叶结点子树本身是堆

?当i≥?n/2?时，

以关键码K

i

为根的子树已经是堆?从倒数第二层，i= ?n/2?-1 开始

从右至左依次调整

?直到整个过程到达树根

?整棵完全二叉树就成为一个堆

4

1628

59

31440

12 345

分析化学课后习题答案 北大版(第4章+思考题)

4.1 已知铜氨络合物各级不稳定常数为 K 不稳1=7.8×10-3 K 不稳2=1.4×10-3 K 不稳3=3.3×10-4 K 不稳4=7.4×10-5 （1）计算各级稳定常数K 1~K 4和各级累积常数β1~β4； （2）若铜氨络合物水溶液中Cu(NH 3)2+4的浓度为Cu(NH 3)2+ 3的10倍，问溶液中[NH 3]是多少？ （3）若铜氨络合物溶液中c (NH 3)=1.0×10-2mol 〃L -1，c (Cu 2+)=1.0×10-4 mol 〃L -1（忽略Cu 2+ ，NH 3的副反应）， 计算Cu 2+ 与各级铜氨络合物的浓度。此时溶液中Cu(Ⅱ)的主要存在型体是什么？ 答案： （1）K 不1 K 不2 K 不3 K 不4 7.8×10-3 1.4×10-3 3.3×10-3 7.4×10-5 14 1 K K = 不 23 1 K K = 不 32 1 K K = 不 41 1K K = 不 1.4×104 3.0×103 7.1×102 1.3×102 11K β= 212K K β= 3213K K K β= 43214K K K K β= 1.4×104 4.2×107 3.0×1010 3.9×1012 （2） ()[]()[] []10NH NH Cu NH Cu 3 4 23 3243==++ K []12 4 3 L mol 10 7.710NH --??==K （3） ()()14123L mol 100.1Cu L mol 100.1NH ----??=??=c c ()() []4 4 333 322 31302][NH ]NH [NH ]NH [1Cu Cu ]Cu [βββ βc x c ++++= ?=+ 12810674424 109.3100.1100.3100.1102.4100.1104.1100.11100.1???+???+???+???+?= -----194 4L mol 104.110 3.7100.1---??=??= ()[]()[]174 4 13 1 23 L mol 109.110 0.110 3.7 NH Cu NH Cu ---+ ??=???=?=βx c ()[]()[]1644 22 32 223L mol 108.5100.1103.7NH Cu NH Cu ---+??=???=?=βx c ()[]()[]1544 33 33 23 3L mol 101.4100.1103.7NH Cu NH Cu ---+??=???=?=βx c ()[]()[]1544 44 34 24 3L mol 103.5100.1103.7NH Cu NH Cu ---+ ??=???=?=βx c

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

北京大学信息学院2007年秋季学期《数据结构与算法A(实验班)》课程作业 张铭编写并发布 mzhang@https://www.docsj.com/doc/6b3974162.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 树

北京大学操作系统期末试题有答案

操作系统原理试题 一. 名词解释题 1. 中断—— 2. 进程控制块(PCB)――它是进程实体的一部分，是操作系统最重要的记录型数据结构, 是进程存在的唯一标识 3. 虚时钟 4. 段式管理 5. 文件控制块(FCB) 6. 对换(SWAPPING) 7. 系统调用 8. 绝对路径名 9. 特别文件 10.虚设备技术 11.管道 12.中断接收 13.恢复现场 14.页式管理 15.作业步 16.字符流文件 17.通道 18.页面淘汰 19.多道程序设计 20.死锁 21.当前目录 22.快表 23.作业调度 24.原语 25.中断屏蔽 26.地址映射 27.文件目录 28.死锁避免 29.原语 31. CPU 状态 32.虚存

二 . 填空题 1. 分时系统追求的目标是 __及时响应 ___. 2. 用户进程从目态 （常态）转换为管态 （特态）的唯一途径是 ___ 中断 ________ . 3. 从静态的观点看 , 操作系统中的进程是由程序段、数据和 __ 作业控制块 PCB__ 三 部分组成 . 4. 在系统内核中必须包括的处理模块有进程调度、原语管理和 __中断处理 __. 5. 批处理操作系统中 , 作业存在的唯一标志是 _作业控制块 PCB ___. 6. 操作系统中的一种同步机制 , 由共享资源的数据及其在该数据上的一组操作组成 , 该同步机制称为 _管程 ______________ . 7. 在可变分区存储管理中 , 为实现地址映射 , 一般由硬件提供两个寄存器 , 一个是基 址寄存器 , 另一个是 _限长寄存器 ___. 8. 联想寄存器 （相联存储器 ） 的最重要、最独到的特点是 _按内容并行查找 ___. 9. 在虚拟段式存储管理中 , 若逻辑地址的段内地址大于段表中该段的段长 , 则发生 __ 地址越界 __中断 . 10. 文件系统中若文件的物理结构采用顺序结构 , 则文件控制快 FCB 中关于文件的物 理位置应包括 ___ 首块地址和文件长度 _. 11. 在操作系统设计时确定资源分配算法 , 以消除发生死锁的任何可能性 , 这种解决死 锁的方法是 __死锁预防 __. 12. 选择对资源需求不同的作业进行合理搭配 , 并投入运行是由 _作业调度算法 ___来完 成的. 13. 实时系统应具有两个基本特征 : 及时性和 ___可靠性 ___. 14. 磁带上的文件只能采用 _顺序 ______ 存取方式 . 15. 不让死锁发生的策略可以分成静态和动态的两种 , 死锁避免属于 __动态的 ___. 16. 在 UNIX 系统中 , 文件分成三类 , 即普通文件 , 目录文件和 ___特殊文件 __. 17. 在磁盘调度策略中有可能使 I/O 请求无限期等待的调度算法是 __最短寻道时间优先 18. 进程获得了除CPU 外的所有资源,一旦获得CPU 即可执行,这时进程处于—就绪 _ 状态 . 19. ______________________________________________________ 为实现CPU 与外部设备的并行工作，系统必须引入一通道 ____________________________________ 硬件基础. 20. 操作系统为保证不经文件拥有者授权 , 任何其它用户不能使用该文件所提出的解决 措施是 ___文件保密 __. 21. 两个或两个以上程序在计算机系统中同处于开始和结束之间的状态 , 这就称为 __ 并发 ___. 33. 磁盘调度 34. 缓冲技术 36. 进程调度 37. 虚设备 39. 死锁预防 40. 临界资源 — 42. 交换技术 43. 互斥区 段时间内只允许一个进程访问的资源，也称为独立资源

数据结构考试题8

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。 一、单项选择题（选择最准确的一项，共15小题，每小题2分，共计30分） 1. 数据结构是指。 A. 一种数据类型 B. 数据的存储结构 C. 一组性质相同的数据元素的集合 D. 相互之间存在一种或多种特定关系的数据元素的集合 2. 以下算法的时间复杂度为。 void fun(int n) { int i=1,s=0; while (i<=n) { s+=i+100; i++; } } A. O(n) B. O(n) C. O(nlog2n) D. O(log2n) 3. 在一个长度为n的有序顺序表中删除其中第一个元素值为x的元素时，在查找元素x时采用二分查找方法，此时删除算法的时间复杂度为。 A. O(n) B. O(nlog2n) C. O(n2) D. O(n) 4. 若一个栈采用数组s[0..n-1]存放其元素，初始时栈顶指针为n，则以下元素x进栈的正确操作是。 A.top++;s[top]=x; B.s[top]=x;top++; C.top--;s[top]=x; B.s[top]=x;top--; 5. 设环形队列中数组的下标为0～N-1，其队头、队尾指针分别为front和rear（front 指向队列中队头元素的前一个位置，rear指向队尾元素的位置），则其元素个数为。 A. rear-front B. rear-front-1 C. (rear-front)％N+1 D. (rear-front+N)％N 6. 若用一个大小为6的数组来实现环形队列，队头指针front指向队列中队头元素的

北京大学医学继续教育学院 无机化学 答案P02A作业4-2

1、用H3PO4（pKa1= 2.16，pKa2= 7.21，pKa3= 12.32）和NaOH所配成的pH = 7.35的缓冲溶液中，抗碱成分是（）（4 分）A．H3PO4 B．H2PO4- C．HPO42- D．PO43- 我的答案：B 得分：4分 2、对于一个化学反应，下列说法中正确的是（）（4 分）

A．越负，反应速率越大 B．越负，反应速率越大 C．活化能越大，反应速率越大 D．活化能越小，反应速率越大 我的答案：D 得分：4分 3、蛋白质发生盐析的主要原因是（）（4 分）A．电解质离子强烈的水化作用使大分子去水化 B．蛋白质所带的电荷发生了变化

C．由于电解质的加入，使大分子溶液处于等电点 D．蛋白质上基团的解离情况发生了变化我的答案：A 得分：4分 4、已知某蛋白的pI = 5.6，欲使该蛋白移向正极，则电泳液的pH应（）（4 分）A．＜5.6 B．=5.6 C．＞5.6 D．无法确定

我的答案：C 得分：4分 5、聚沉As2S3负溶胶，下列电解质中聚沉能力最强的是（）（4 分） A．Ca(NO3)2 B．K2SO4 C．Na3PO4 D．AlCl3 我的答案：D 得分：4分

6、溶胶在一定时间内能稳定存在而不聚沉，主要原因是（）（4 分） A．溶胶的分散相粒子很小 B．溶胶的分散相粒子很大，扩散速度慢C．溶胶的胶粒呈均匀分布，是均相系统D．胶粒带电，相互排斥；胶粒带有水化膜保护，阻止彼此碰撞时聚结沉淀 我的答案：D 得分：4分 7、溶胶的丁铎尔（Tyndall）现象的本质是胶粒对光的（）（4 分） A．透射作用

【适用于2019年软微最新专业】2018年北京大学867计算机基础综合考研真题及答案解析 如何备考

大家好，我是姜老师。 今日有话说： 现在已经是九月份了，很多考生比较担心自己的学习进度，甚至去花什么时间去证实自己的进度慢还是快，虽然每个学生的情况不一样，包括报考的学校难度也不一样，但是因为回答了很多学生的问题，所以给一个大概的进度情况： 9月份之前专业课所有参考书应该至少完成一遍并做好笔记； 9-11月份文科类的专业必须背诵3-4轮，理工类的专业课做题至少2遍。 11-12月必须刷题，真题是必须要做的，而且要发动你的所有能力去搞到真题答案。 这些，我们都有! 所以今天也是给大家整理的最重要的真题！ 关于：这个真题有啥用 北大软微有了很大的变化，2019年最新的招生目录也出来了，昨天给大家把所 有的专业变动以及如何备考都整理出来了，今天给大家整理的是2018年的软微计算机基础真题，去年适用专业是计算机技术数一方向（包括软件工程、金融大数据、大数据云安全等等），今年虽然代码改为了867计算机基础综合，但内容相信不会有太大的变化，所以此真题仍适用于软件工程以及计算机技术数一方向，招生目录给大家在下方列出来。

2018年北京大学软微822计算机基础综合考研真题 选择题（30*2’） 有点多，很多实在记不太清了，欢迎大家一起补充。自己印象比较深的： 单缓冲，求大量数据条件下单个时间为多少，那道题的BD选项一样。 最后一道单选题问浏览器和邮件服务器建立的什么连接，两个邮件服务器之间传送用的什么连接。 RIP、OSPF、BGP的传递协议分别是什么。 大题 第一题，给出一个前序序列、中序序列，要求画出二叉树，并且画出后序遍历的线索树。 第二题，给出一个边的集合，要求写出邻接矩阵，写出邻接表，写出Prim和Kruscal算法的生成树； 第三题，给出一个顶点集及相应的权值，要求画出哈夫曼树，并计算WPL； 第四题，有四个作业，给出分别到达的时间、作业时间，使用多级反馈队列进行调度，共4个队列，Q1～Q4优先级递减，时间片分别是24816，每个队列内使用FCFS算法，要求给出整个调度的过程； 第五题，叙述屏蔽中断和嵌套中断的原理；叙述中断发生的过程； 第六题，1）文件目录的顺序结构有什么优点？2）文件目录的哈希结构有什么优点？有什么局限性？ 第七题，A向B发送了三个帧，第一个帧序号300，第二个帧序号500，第三个帧序号580； 1）第一个帧发送了多少字节 2）B接收到第一个帧后，发回的确认号多少 3）第二个帧发送了多少字节 4）如果第一个帧丢失，第二第三个帧到达，B发回的确认号多少 第八题， 1）为什么有些协议（BGP、STMP等）要用TCP，而有些协议（RIP、DNS等）要用UDP？ 2）路由选择协议中，为什么BGP和RIP是在应用层，而OSPF是在网络层？

北京大学1997硕士入学数据结构试题

北京大学1997硕士入学数据结构试题 1 （16分） 填空 ① 设只包含要根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数 为，最小结点数为。 ② 某二叉树结点的对称序序列为A，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E，则该二叉树结点的前序序列为，该二叉树对应的树林包括棵树。 ③ 求具有最小带权外部路径长度的扩充二叉树的算法称为算法，对于给出的一组权W={10，12，16，21，30}，通过该算法求出的扩充二叉树的带权外部路径长度为。 ④ 设有关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是；若采用以第一个元素为分界元素的快速排序法，则一趟扫描的结果是。 2 （10分） 请简要回答下列问题 ① 什么是抽象数据类型？试举一例说明之。 ② 什么是广义表？请简述广义表与线性表的主要区别。 3 （6分） 给定关键码序列（26，25，20，33，21，24，45，204，42，38，29，31），要用散列法进行存储，规定负载因子a=0.6。 ① 请给出除余法的散列函数。 ② 用开地址线性探查法解决碰撞，请画出插入所有的关键码后得到的散列表，并指出发生碰撞的次数。 4 （6分） 本题要求在检索各结点的概率不相等的条件下构造最佳二叉排序树。给出关键码集合 { B, E, H} key1 key2 key3

以及权的序列 ( 9 4 5 8 6 1 3) p1 p2 p3 q0 q1 q2 q3 请构造最佳二叉排序树。 5 （12分） ① 请画出往图1的5阶B-树中插入一个关键码390后得到的B-树，以及再删除关键码150后得到的B-树。 ② 包括n个关键码的m阶B-树在一次检索中最多涉及多少个结点？（要求写出推导过程） 图1 题5图 6 （10分） 如图2所示是一棵正在进行插入运算的AVL树，关键码70的插入使它失去了平衡，按照AVL树的插入方法，需要对它的结构进行调整以恢复平衡。 ①请画出调整后的AVL树。 ②假设AVL树用llink-rlink法存储，T是指向根结点的指针、请用PASCAL（或C）语句表示出这个高速的过程。 （说明：不必写出完整的程序，只需用几个语句表示出在本题所给的具体情况下调整过程中指针的变化。在调整过程中还有两个指针变量p和q可以使用）。

分析化学课后习题答案 北大版(第3章)

3.1 从手册中查出下列各酸的酸度常数p K a ，分别计算它们的K a 及与其相应的共轭碱的K b 值。 34224+43+ 3.2 （1）计算pH=5.0时，H 3PO 4的摩尔分数3210。（2）假定H 3PO 4各种形式总浓度是0.050 mol 〃L -1 ， 问此时H 3PO 4、H 2PO 4-、HPO 42-、PO 43-的浓度各为多少？ 答案：（1）123 112122 a a a 03 2 a a a a a a [H ][H ][H ]K K K x K K K K K K +++ = +++ 10 69.2137.1416.1200.1531.1221.716.2100.31010101010--------?=+++= 3 16 .1200 .15337.1416.1216.1223 16 .1237 .141104.110 10 )994.0(0.1)1010(10102.610 10 ---------?===+= ?==x x x （2）c =0.050mol 〃L -1 1 53431 24 2141241 11034L mol 102.7]PO H [L mol )0497.0(050.0]PO H [L mol 101.3]HPO [L mol 105.1]PO [---- ------??=?=?=?=??=?=??=?=x c x c x c x c 3.3 某溶液中含有HAc 、NaAc 和Na 2C 2O 4，其浓度分别为0.80、0.29和1.0×10-4 mol 〃L -1 。计算此溶液 中C 2O 42-的平衡浓度。 答案：溶液的酸度由HAc-Ac -所决定 ()() 4.76 4.32a HAc 0.80 [H ]10100.29 Ac c K c +---= = ?= 22 a 224 0a 4 4.2951 4.32 4.29 [C O ][H ]1.01010 5.210mol L 1010cK cx K -+------== +??==??+ 写出下列物质水溶液的质子条件： （1）NH 3；（2）NH 4Cl ；（3）Na 2CO 3；（4）KH 2PO 4；（5）NaAc+H 3BO 3。 答案：（1）NH 3 [NH 4+]+[H +]=[OH -] （2）NH 4Cl [H +]=[NH 3]+[OH -] （3）Na 2CO 3 [H +]+[HCO -3]+2[H 2CO 3]=[OH -]

北大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

北京中医药大学无机化学考试辅导试题及答案

北京中医药大学《无机化学》考试辅导试题及答案 用离子-电子法配平并完成下列反应 答：+ + 2I－= 2Fe2+ + I2 －+ 3SO32－+H2O = 2MnO2 + 3SO42－+ 2OH— + + Zn = Cu+ Zn2+ －＋3S2－＋14H+ =2Cr3＋＋3S +7 H2O －+ 5SO32－+ 6H+= 2Mn2+ + 5SO42－+3 H2O — + SO32－+ 2OH—= 2MnO42—+ SO42－+ H2O 简答题 1. 一种钠盐A,在A的水溶液中加入稀盐酸产生刺激性气体B。A的水溶液在酸性中能使KMnO4溶液腿色，得到无色溶液C。若在A的水溶液中通入Cl2得溶液D,在D中加入AgNO3溶液产生白色沉淀E,若在E中加入NH3水，震荡后得到无色溶液F。指出A、B、C、D、E、F各为何物。 答：A、Na2SO3B、SO2C、Mn2+ D、Cl- E、AgCl F、[Ag(NH)2]+ 2.根据配合物的价键理论，指出下列配离子中，中心离子和配体的配位情况（即画出中心离子杂化后价电子排布、指出杂化轨道类型及空间构型）。 （1）[FeF6]3－μ= . （2）[Fe(CN)6]3－μ= . 答：（1）Fe3+ 3d53d轨道有5个单电子sp3d2杂化八面体 （2）Fe3+ 3d53d轨道有1个单电子d2sp3杂化八面体 3.有四种试剂：Na2SO4、Na2SO3、Na2S2O3、Na2S，它们的标签已脱落，请设计只加一种试剂的简便方法鉴别它们,并写出有关配平的离子反应方程式。 答：加稀HCl （略） 4.根据配合物的价键理论，确定下列配离子是内轨型还是外轨型，说明理由。 (1) [Fe(H2O)6]3－（Fe3+3d 5）μ= . (2) [Mn(CN)6] 4－（Mn2+3d 5）μ= . 答：（1）μ= 则n=5 Fe3+ 3d53d轨道有5个单电子sp3d2杂化八面体 （2）μ= 则n=1 Fe3+ 3d53d轨道有1个单电子d2sp3杂化八面体 5.现有一种含结晶水的淡绿色晶体A，将其配成溶液，若加入BaCl2溶液，则产生不溶于酸的白色沉淀B，若加入NaOH溶液，则生成白色胶状沉淀C并很快变成红棕色沉淀D，再加入盐酸，此红棕色沉淀又溶解，滴入硫氰化钾溶液显深红色溶液E。指出A、B、C、D、E各为何物。 答：A、Na2SO3B、SO2C、Mn2+ D、Cl- E、AgCl F、[Ag(NH)2]+

计算机网络设计试题及答案

一、选择题 1.网格体系结构的五层沙漏结构的基本思想是以（）为中心。 A.协议 B.应用 C . 用户 D.服务 2.需求管理包括需求跟踪、（）、需求评估等工作。 A.需求变更 B.需求分析 C .需求优先级 D.需求说明 3.网络工程师在大部分情况下可以通过（）来获取用户需求。 A.分析 B.统计 C .调查 D.用户 4.电信网的主干链路，一般采用（）和DWDM 技术。 A.ATM B.ISDN C . Ethernet D.SDH 5.（）是实现网络安全最基本、最经济、最有效的措施之一。 A.防火墙 B.杀毒软件 C . IDS D.IPS 6.在环型网络拓扑结构中，N 个节点完全互联需要（）条传输线路。 A.N B.N-1 C . N+1 D.N/2 7.网络冗余设计主要是通过重复设置（）和网络设备，以提高网络的可用性。 A.光纤 B.双绞线 C . 网络服务 D.网络链路 8.蜂窝拓扑结构使用频率（）的方法，使有限的带宽容纳大量的用户。 A.分割 B.复用 C .调制 D.解调 9.（）是基于增加带宽的需要，可以将几条链路捆绑在一起，以增加链路带宽。 A.VLAN B.STP C . 汇聚 D.堆叠 10.QoS 的目标是有效提供（）的服务质量控制或保证。 A.点对点 B.端到端 C . 用户 D.因特网服务商 11.在分层网络设计中，如果汇聚层链路带宽低于接入层链路带宽的总和，我们称为（） 式设计。 A.汇聚 B.聚合 C .阻塞 D.非阻塞 12.基于分组交换的网络中，目前还没有统一的流量模型，而基于电路交换的电话网络已 经建立了很成熟的（）话务量模型。 A.爱尔兰 B.英格兰 C . 耐奎斯特 D.香农 13.以太网交换机的每一个端口相当于一个（）。 A.网卡 B.Hub C . 中继器 D.网桥 14.在中低端路由器中，（）负责交换路由信息、路由表查找以及转发数据包。 A.数据库 B.路由算法 C . CPU D.NVROM 15.路由器在轻载条件下，丢包率一般小于（）％。 A.0.1 B.1 C . 2 D.5 16.计算机网络是计算机技术和（）技术相结合的产物。 A．通信B．网络 C．Inernet D．Ethernet 17.城域网往往由多个园区网以及（）、传输网等组成。 A．校园网 B．以太网 C．电信网 D．接入网 18.（）标准化组织主要由计算机和电子工程学等专业人士组成。 A．ITU B．IEEE C．ISO D．RFC 19.根据统计，个人用户使用因特网的时间上大部分集中在晚上8．00～12．00之间，在 晚上（）点达到流量高峰。 A．8 B．10 C．11 D．12 20.拓扑学把实体抽象成与实体大小、形状无关的点，将连接实体的通道抽象成线，进而

北大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

北京大学中级无机化学答案

无机化学习题参考答案(II) 第一章 1.4．解： （1）H 2O 2 2C （2）S 2O 32 3v C （3）N 2O (N N O 方式) v C ∞ （4）Hg 2Cl 2 h D ∞ （5）H 2C=C=CH 2 2d D （6）UOF 4 C 5v （7）BF 4 d T （8）SClF 5 4v C （9）反-Pt(NH 3)2Cl 2 2h D （10）PtCl 3(C 2H 4) 2v C 1．B(CH 3)3和BCl 3相比，哪一个的Lewis 酸性强，为什么？ 一般来说，CH 3为推电子基团，Cl 为吸电子基团，因此的Lewis 酸性强。 （BCl 3易水解；B(CH 3)3不溶于水，在空气中易燃） 2．BH 3和BF 3都可和(CH 3)2NPF 2生成加合物，在一种加合物中，B 原子和N 相连，另一种则和P 相连，绘出两种结构式，并说明形成两种结构的原因。 P F F H 3C CH 3 N P F F H 3C CH 3 N B B H 3F 3 (该题可参考史启桢等翻译的"无机化学",作者Shriver 等,由高教社出版, 其中关于热力学酸度参数的部分，p.190-191; 或者该书的英文原版第5章的相关内容) 3. 无水AlCl 3可作为傅-克烷基化反应的催化剂, 而吸水后则失效, 原因何在? 配位饱和（6配位），失去Lewis 酸性 4. 吸水后失效 的AlCl 3有什么方法可以脱水? 因为Al 3+是典型的硬酸，与氧的亲合力很强，因此实验室不能在HCl ，NH 4Cl ，SOCl 2等气氛下加热脱水。（只能加强热生成 Al 2O 3后，用高温下用加C 和Cl 2用还原氯化法制备，这就不是脱水方法了）。 第二章

计算机网络基础标准答案及解析北京大学

1. （6.5节）具有隔离广播信息能力的网络互连设备是 A. 中继器 B. 网桥 C. 交换机 D. 路由器 2. （2.5节）曼彻斯特编码中，比特中间电平由低到高表示的二进制数是 A. 1 B. 0 C. -1 D. 2 3. （6.5节）RIP路由协议的最大跳数（hop）是 A. 15 B. 16 C. 32 D. 不限制 4. （4.8节）最高传输速率为54Mbps，室外300m的无线局域网标准是 A. IEEE802.11 B. IEEE802.11a

C. IEEE802.11b D. IEEE802.11g 5. （7.4节）在TCP中，建立连接需要进过几次握手，终止连接又需要经过几次握手。 A. 三次，两次 B. 两次，四次 C. 三次，四次 D. 四次，两次 6. （2.9节）以下哪项不是物理层的特性 A. 机械特性 B. 电气特性 C. 接口特性 D. 规程特性 7. （3.1节）为了保证数据通信的准确，错误发生的几率尽可能低，在OSI模型中的哪一层提供差错控制来实现此功能。 A. 物理层 B. 数据链路层 C. 网络层 D. 传输层 8. （2.4节）数据在多条信道上同时传输的通信方式是

A. 串行 B. 并行 C. 异步串行 D. 同步串行 9. （1.3节）完成路径选择和数据转发两个基本功能的OSI参考模型的层次是 A. 物理层 B. 数据链路层 C. 网络层 D. 传输层 10. （2.4节）收发双方可以同时发送信息的传输形式成为 A. 单工 B. 半双工 C. 全双工 D. 多工 11. （6.2节）IP数据包传送过程中有可能被分片，分片后通常由什么设备进行重组。 A. 源主机 B. 目的主机 C. 转发路由器

北京大学定量分析化学简明教程习题-5

北京大学定量分析化学简明教程习题 第四章 络合滴定法 1．已知铜氨络合物各级不稳定常数为： K 不稳1＝7.8?10-3 K 不稳2＝1.4?10-3 K 不稳3＝3.3?10-4 K 不稳4＝7.4?10-5 (1) 计算各级稳定常数K1－K4和各积累常数β1-β4； (2) 若铜氨络合物水溶液中Cu(NH 3)42+的浓度为Cu(NH 3)32+的10倍，问溶液中[NH 3]是多少？ (3) 若铜氨络合物溶液的C NH3=1.010-2M ，C Cu2+=1.0?10-4M,（忽略Cu 2+，NH 3的副反应）。计算Cu 2+与各级铜氨络合物的浓度。此时溶液中以那种形体为最主要？ 解：(1) 稳定常数 K 1＝45-4 101.4104.711 ??＝＝不稳K K 2=34-3 103.0103.311 ??＝＝不稳K K 3=23-2 107.1101.411 ??＝＝不稳K K 4＝＝＝ 不稳3-1107.811 ?K 1.3?102 各级累积常数 β1＝K 1=1.4?104 β2＝K 1K 2＝1.4?3.0?107＝4.2?107 β3＝K 1K 2K 3＝1.4?3.0?7.1?109=3.0?1010 β4＝K 1K 2K 3K 4=1.4?3.0?7.1?1.3?1011＝3.9?1012 (2) β3=332233]][[])([NH Cu NH Cu ++,β4=432243]][[])([NH Cu NH Cu +-

] )([]][[]][[])([2333 3243224334++++=NH Cu NH Cu NH Cu NH Cu ββ =][1])([])([3233243NH NH Cu NH Cu ? ++ [NH 3]=4 3233243])([])([ββ?++NH Cu NH Cu =10?1210 10 9.3100.3?? =0.077(ml/l) (3) Φ0=4 3433323231][][][][11NH NH NH NH ββββ++++ ＝812610472410 9.3100.3102.4104.111----?+?+?+?+ ＝4 43109.3100.3102.41?+?+? ＝ 4103.71? ＝1.4?10-5 Φ1＝4 343332323131][][][][1][NH NH NH NH NH βββββ++++ ＝ 3104.74102.1 ＝1.910-3 Φ2＝43433323231232] [][][][1][NH NH NH NH NH βββββ++++ ＝43 10 3.7102.4?? ＝0.058 Φ3＝434333232313 33] [][][][1][NH NH NH NH NH βββββ++++

北京大学各院系课程设置一览

北京大学各院系课程设置一览 前言 很多同学希望了解在北京大学各院系的某个年级要学习哪些课程，但又不容易查到课程表。本日志充当搬运工作用，将各院系开设课程列于下方，以备查询。 查询前必读 注释： ※在课程名称后标注含义如下： 标注（必）表示此课程为专业必修课，是获得学士学位必须通过的课程； 标注（限）表示此课程为专业任选课（原称专业限选课），各院系规定需在所有专业任选课中选修足够的学分（通常为30~40）以获取学士学位； 标注（通）表示此课程为通选课，非本院系本科生可选修此类课程，并计入通选课所需总学分；通选课无年级限制； 标注（公）表示此课程为全校任选课（原称公共任选课），此类课程不与学位挂钩，公选课无年级限制。 标注（体）表示此课程为体育课，每名学生必须且仅能选修4.0学分体育课；男生必须选修“太极拳”，女生必须选修“健美操”。 ※实际上，多数专业必修课及专业选修课也没有年级限制。对应的年级是“培养方案”推荐的修该门课程的适当年级。 ※不开设任何专业必修课的院系为研究生院或其他不招收本科生的部门，如马克思主义学院、武装部等。 ※由于在某些院系下有不同专业方向，标注为必修课的课程可能并不对于所有学生均为必修（如外国语学院的各个语种分支）。相关信息请咨询相应院系教务。 ※多数课程可以跨院系选修，但可能需缴纳额外学费。 ※院系编号为学号中表示院系字段的数字，因院系调整原因，编号并不连续。“系”可能为院级单位，具体以相应主页标示为准。 ※课程名称后标注数字表示学分。一般情况下，对于非实验课及非习题课，每学分表示平均每周有一节50分钟时长课程，16-18周。 ※院系设置的课程不一定由本院系开设。 ※医学部课程仅包含在本部的课程内容。 ※本一览表不包括政治课、军事理论课、英语课、文科计算机基础、辅修及双学位课程。※本一览表不提供上课地点及主讲教师信息，请与相应院系教务联系。 001 数学科学学院 https://www.docsj.com/doc/6b3974162.html,/ 一年级秋季学期 数学分析（I）（必）5.0 数学分析（I）习题（必）0.0 高等代数（I）（必）5.0 高等代数（I）习题（必）0.0 几何学（必）5.0 几何学习题（必）0.0 一年级春季学期 数学分析（II）（必）5.0

北京大学定量研究分析化学简明教程习题-

北京大学定量分析化学简明教程习题-

————————————————————————————————作者：————————————————————————————————日期： 2

北京大学定量分析化学简明教程习题 第四章 络合滴定法 1．已知铜氨络合物各级不稳定常数为： K 不稳1＝7.8?10-3 K 不稳2＝1.4?10-3 K 不稳3＝3.3?10-4 K 不稳4＝7.4?10-5 (1) 计算各级稳定常数K1－K4和各积累常数β1-β4； (2) 若铜氨络合物水溶液中Cu(NH 3)42+的浓度为Cu(NH 3)32+的10倍，问溶液中[NH 3]是多少？ (3) 若铜氨络合物溶液的C NH3=1.010-2M ，C Cu2+=1.0?10-4M,（忽略Cu 2+，NH 3的副反应）。计算Cu 2+与各级铜氨络合物的浓度。此时溶液中以那种形体为最主要？ 解：(1) 稳定常数 K 1＝45-4 101.4104.711 ??＝＝不稳K K 2=34-3 103.0103.311 ??＝＝不稳K K 3=23-2 107.1101.411 ??＝＝不稳K K 4＝＝＝ 不稳3-1107.811 ?K 1.3?102 各级累积常数 β1＝K 1=1.4?104 β2＝K 1K 2＝1.4?3.0?107＝4.2?107 β3＝K 1K 2K 3＝1.4?3.0?7.1?109=3.0?1010 β4＝K 1K 2K 3K 4=1.4?3.0?7.1?1.3?1011＝3.9?1012 (2) β3=332233]][[])([NH Cu NH Cu ++,β4=432243]][[])([NH Cu NH Cu +- ]][[])([3 22++NH Cu NH Cu β

北京大学数据结构与算法信科数算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个字节是数据字段。记录已经排序，顺序地存储