C和数据结构北京大学(精)

数据结构与算法数据结构与算法是北京大学于2018年02月26日首次在中国大学MOOC开设的慕课课程，是国家精品在线开放课程。

该课程授课教师为张铭、陈斌、卢宗青、刘云淮、赵海燕、宋国杰、黄骏、邹磊、王腾蛟。

据2021年2月中国大学MOOC官网显示，该课程已开课4次。

数据结构与算法课程内容包括数据结构与抽象数据类型、算法特性及分类、算法效率与度量、线性结构、顺序表、链表、栈与队列、栈与递归、递归转非递归、字符串的存储结构、字符串运算的算法实现、字符串的快速模式匹配、二叉树的抽象数据类型、二叉树的搜索、二叉树的存储结构、树与二叉树的等价转换、树的抽象数据类型及树的遍历、树的链式存储结构、树的父指针表示法、树的顺序存储和K叉树、图的概念和抽象数据类型、图的存储结构、图的遍历、内排序、检索等内容。

课程性质:课程背景计算机是现代社会中用于解决问题的重要工具，支撑这个工具高效运转的就是其后的各种系统程序、应用程序。

数据结构，是抽象的表示数据的方式；算法，则是计算的一系列有效、通用的步骤。

算法与数据结构是程序设计中相辅相成的两个方面，是计算机学科的重要基石。

课程定位数据结构与算法是介绍基本数据结构以及相关的经典算法，强调问题-数据-算法的抽象过程，关注数据结构与算法的时间空间效率，培养学生编写出高效程序从而解决实际问题的综合能力的一门课程。

适应对象数据结构与算法适合计算机以及相关理工专业的本科生学习。

对于具有C语言结构化程序设计基础的学生，该课程第0章补充了一些面向对象的基本内容。

课程简介:数据结构与算法围绕着“算法+数据结构=程序”的思路，以问题求解为导向进行学习，运用问题抽象、数据抽象、算法抽象来分析问题，应用适当的数据结构和算法来设计和实现相应的程序。

在求解实际问题方面，该课程会学习到通过权衡时空和其他资源开销，利用数据结构来组织数据、设计高效的算法、完成高质量的程序以满足错综复杂的实际应用需要。

课程所学到的内容会被利用到计算机科学后续的各个课程中，如操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等。

栈的应用递归到非递归的转换张 铭 北京大学信息学院1内容提要递归函数调用原理 机械的递归转换 优化后的非递归函数 非递归的二叉树周游2张铭 北京大学信息学院递归函数示例void exmp(int n, int& f) { int u1, u2; if (n<2) f = n+1; else { exmp((int)(n/2), u1); exmp((int)(n/4), u2); f = u1*u2; } } 张铭3北京大学信息学院数学公式fu (n) ={n +1当n < 2时fu ( ⎣n / 2 ⎦)* fu ( ⎣n / 4 ⎦)n ≥ 2时}4张铭 北京大学信息学院函数调用及返回的步骤调用– 保存调用信息（参数，返回地址） – 分配数据区（局部变量） – 控制转移给被调函数的入口返回– 保存返回信息 – 释放数据区 – 控制转移到上级函数（主调用函数）5张铭 北京大学信息学院函数执行过程图解二叉树图解 Exmp(7,&f) f=u1*u2=4u1=f=2 u2=f=2 Exmp(3,&f) Exmp(1,&f) f=u1*u2=2u1=f=2 Exmp(1,&f)张铭u2=f=1 Exmp(0,&f)6北京大学信息学院用栈模拟递归调用过程后调用，先返回(LIFO），所以用栈rd=1: n=1 f=1 u1=? u2=? f=2 rd=2: n=0 f=? u1=? u2=? f=? rd=2: n=1 f=? u1=2 u2=1 rd=1: n=3 f=? u1=? u2=? f=2 u1=? u2=? rd=3: n=7 f=? u1=? u2=? u1=2 u2=2张铭7北京大学信息学院递归过程的模拟假设 void recfunc(p1, p2, p3，…，pk, pk+1, …, pm) 是一个递归函数void是无返回值型的函数，如果有返回值， 我们可以把返回值转换为一个引用型参数 其中参数p1, p2, p3，…，pk是值传递，参 数pk+1, …, pm是引用传递。

2019年招生信息：育明教育徐老师备注解析：1.2019年软件工程计划招收人数全日制60人，接收推免人数12人。

2.2019年软件工程只有1个方向，考的内容政治、英语一、数学一、867计算机基础综合。

3.软件工程从名称来看就知道是偏向于技术的专业，毕业后很多学生都能去微软，亚马逊，腾讯，百度，阿里巴巴这种国外和国内一流的软件公司。

北大软微这个平台是很好的，技术类的校友资源也很丰富，北大的学位基本保证找工作时候不会因为学校不好被刷掉简历，有些地方可是只要北清复交的哦，剩下的就看个人素质了，有了平台，个人专业知识、表达能力过硬，再找些相关实习，考些证书，找个好工作是不成问题的。

总的来说呢，技术类的就业不输给任何大学的计算机学硕。

读博方面，因为软微大部分是专硕，不能直博，读博只能申请或者考博，但软微作为北大的学院给教授的印象好，申博士的时候会优先考虑。

学院也有一些出国交流的机会，对于出国读博的同学有利。

推荐使用参考书：软件工程官方指定参考书：《数据结构》（C语言版）严蔚敏清华大学出版社《计算机操作系统》汤子瀛西安电子科技大学出版社《计算机网络》谢希仁电子工业出版社历年招生复试分数线：2016年：50，45，80，80，2902017年：50，45，80，80，3002018年：50，45，80，80，300北京大学软件与微电子学院2018年硕士研究生招生复试通知根据北京大学研究生院的工作安排，并结合我院的具体情况，现将2018年硕士研究生复试阶段的工作安排说明如下：一、复试时间、地点：复试时间：3月12日-16日；（具体时间请查收邮件）复试地点：软件与微电子学院（大兴校区）（地址：北京市大兴工业开发区金苑路24号）。

（具体地点见复试通知书）乘车路线：1、北京站：地铁二号线宣武门站换乘地铁四号线高米店南站下车，C 口出站，在金星西路打车或者乘兴11路到福苑东区站下车，北行300米路东。

2、北京西站：地铁九号线国家图书馆站换乘地铁四号线高米店南站下车，C口出站，在金星西路打车或者乘兴11路到福苑东区站下车，北行300米路东。

解忧书店 JieYouBookshop第二章单元测试1、(1分)以下哪种结构是逻辑结构，而与存储和运算无关：Which of the following structure is a logical structure regardless of the storage or algorithm:（There is only one correct answer）A、队列(queue)B、双链表(doubly linked list)C、数组(array)D、顺序表(Sequential list)答案： A2、(1分)计算运行下列程序段后m的值：Calculate the value of m after running the following program segmentn = 9; m = 0;for (i=1;i<=n;i++)for (j = 2*i; j<=n; j++)m=m+1;求m的值答案： 203、(1分)下列说法正确的是：Which options may be correct?（there are more than one correct answers）A、如果函数f(n)是O(g(n))，g(n)是O(h(n))，那么f(n)是O(h(n))【 if f(n) is O(g(n))，g(n) is O(h(n))，then f(n) is O(h(n))】B、如果函数f(n)是O(g(n))，g(n)是O(h(n))，那么f(n)+g(n)是O(h(n))【if f(n) is O(g(n))，g(n) is O(h(n))，so f(n)+g(n) is O(h(n))】C、如果a>b>1,logan是O(logbn)，但logbn不一定是O(logan)【if a>b>1,logan is O(logbn)，logbn may not be O(logan)】D、函数f(n)是O(g(n))，当常数a足够大时，一定有函数g(n)是O(af(n))【if f(n)是O(g(n))，When constant a is big enough ，there must be g(n) is O(af(n))】答案： A,B4、(1分)由大到小写出以下时间复杂度的序列：答案直接写标号，如：(1)(2)(3)(4)(5) （提示：系统基于字符匹配来判定答案，所以您的答案中不要出现空格）Write the following time complexity in descending sequence:Write down the answer labels such as (1)(2)(3)(4)(5). （Hint：This problem is judged by string matching, Please make sure your answer don't contain any blanks. ）RUX4%GXZNDD{IAQWTCSEEJG.png答案： (5)(1)(2)(4)(3)5、(1分)已知一个数组a的长度为n，求问下面这段代码的时间复杂度:An array of a, its length is known as n. Please answer the time complexity of the following code.（There are more than one answers.）for (i=0,length=1;i<n-1;i++){for (j = i+1;j<n && a[j-1]<=a[j];j++)if(length<j-i+1)length=j-i+1;}Screen Shot 2017-09-05 at 23.31.19.pngA、如图，A选项B、如图，B选项C、如图，C选项D、如图，D选项答案： A,B第三章单元测试1、(1分)下面关于线性表的叙述中，正确的是哪些？Which of the followings about linear list are correct?（There are more than one answers.）Select the answer that matchesA、线性表采用顺序存储，必须占用一片连续的存储单元。

数据结构任课教员：张铭、赵海燕、冯梅萍、王腾蛟/mzhang/DS/北京大学信息科学与技术学院网络与信息系统研究所©版权所有，转载或翻印必究教学目的掌握常用的基本数据结构的ADT 及其应用学会合理地组织数据, 有效地表示数据, 有效地处理数据基本掌握算法的设计分析技术 提高程序设计的质量教学要求平时(考勤+作业)20％ 上机(+报告)30％期中20％期末30％诚信端正学习态度、调动学习兴趣提倡讨论，但严禁抄袭可以讨论思路，请同学看算法的逻辑问题和效率问题。

但要亲自动手实现。

发现抄袭，则抄袭者和被抄袭者本次作业或上机题计双倍倒扣分，即得-20分。

以后的作业题会得到重点检查。

严重的期评将给予不及格处理数据结构教学计划和要求按时提交作业，严禁抄袭所有书面作业和上机作业都必须在指定的期限内完成并提交一般周三交书面作业。

除非不可抗拒的客观原因，请严格按提交时间完成书面作业和上机作业。

例如，一个满分为10分的作业题，记分标准为：（1）准时提交，满分可达10分（个别加分）；（2）延迟3天之内提交，满分可达7分；（3）延迟7天之内提交，满分可达3分；（4）7天之后提交或不交，得分-5分。

（5）抄袭得–20分。

书面作业提交要求1) 写学号、名字2) 每次作业，都在作业本或电子稿的word文档中写上“我保证没有抄袭他人作业”的诚实保证。

否则，计零分或根据抄袭情况倒扣分。

3) 写算法分析、注释4) 算法中直接使用的函数、过程先写ADT，并说明函数功能、入口参数、出口参数5) 注意算法格式(层次嵌套、不同功能块之间留空)上机题提交要求上机作业提交时打一个zip包，学号+姓名+作业次数，如”00308096张宁1.zip”包中含有：1. readme.txt文件，把你的程序运行环境、编译运行步骤、程序功能等等简单说明一下。

2. 附加了诚实代码保证和足够注释的源程序以及相关的项目和资源文件。

例如，VC++中的.dsw, .dsp文件，rc目录中的图像资源文件；Jbuilder中的.jpr或.jpx文件，特殊的Java包等等。

北京大学数学科学学院考研参考书目汇总考试科目编号：01 数学分析 02 高等代数03 解析几何 04 实变函数05 复变函数 06 泛函分析07 常微分方程 08 偏微分方程09 微分几何 10 抽象代数11 拓扑学 12 概率论13 数理统计 14 数值分析15 数值代数 16 信号处理17 离散数学 18 数据结构与算法01 数学分析（ 150 分）考试参考书：1. 方企勤等，数学分析（一、二、三册）高教出版社。

2. 陈纪修、於崇华、金路，数学分析(上、下册)，高教出版社。

02 高等代数（ 100 分）考试参考书：1. 丘维声,高等代数(第二版) 上册、下册，高等教育出版社，2002年, 2003年。

高等代数学习指导书（上册），清华大学出版社，2005年。

高等代数学习指导书（下册），清华大学出版社，2009年。

2. 蓝以中，高等代数简明教程（上、下册），北京大学出版社，2003年（第一版第二次印刷）。

03 解析几何（ 50 分）考试参考书：1. 丘维声，解析几何（第二版），北京大学出版社，（其中第七章不考）。

2. 吴光磊，田畴，解析几何简明教程，高等教育出版社， 2003年。

04 实变函数（ 50 分）考试参考书：1. 周民强，实变函数论，北京大学出版社， 2001年。

05 复变函数（ 50 分）考试参考书：1. 方企勤，复变函数教程，北京大学出版社。

06 泛函分析（ 50 分）考试参考书：1. 张恭庆、林源渠，泛函分析讲义（上册），北京大学出版社。

07 常微分方程（ 50 分）考试参考书：1. 丁同仁、李承治，常微分方程教程，高等教育出版社。

2. 王高雄、周之铭、朱思铭、王寿松，常微分方程（第二版），高等教育出版社。

3. 叶彦谦，常微分方程讲义（第二版）人民教育出版社。

08 偏微分方程（ 50 分）考试参考书：1. 姜礼尚、陈亚浙，数学物理方程讲义（第二版），高等教育出版。

2. 周蜀林，偏微分方程，北京大学出版社。

第三章字符串任课教员：张铭、赵海燕、冯梅萍、王腾蛟/mzhang/DS/北京大学信息科学与技术学院©版权所有，转载或翻印必究主要内容3.1 字符串抽象数据类型3.2 字符串的存储结构和类定义 3.3 字符串运算的算法实现3.4 字符串的模式匹配3.1字符串抽象数据类型3.1.1 基本概念3.1.2 String抽象数据类型3.1.1 基本概念字符串，由0个或多个字符的顺序排列所组成的复合数据结构，简称“串”。

串的长度：一个字符串所包含的字符个数。

空串：长度为零的串，它不包含任何字符内容。

3.1.1.1字符串常数和变量字符串常数例如："\n"字符串变量3.1.1.2 字符字符(char) ：组成字符串的基本单位。

在C和C＋＋中单字节（8 bits）采用ASCII码对128个符号（字符集charset）进行编码3.1.1.3 字符的编码顺序为了字符串间比较和运算的便利，字符编码表一般遵循约定俗成的“偏序编码规则”。

字符偏序：根据字符的自然含义，某些字符间两两可以比较次序。

其实大多数情况下就是字典序中文字符串有些特例，例如“笔划”序3.1.1.4 C++标准string标准字符串：将C++的<string.h>函数库作为字符串数据类型的方案。

例如：char S[M];串的结束标记：'\0''\0'是ASCII码中8位BIT全0码，又称为NULL符。

3.1.1.4 C++标准string(续)1. 串长函数int strlen(char*s);2. 串复制char *strcpy(char*s1, char*s2);3．串拼接char *strcat(char*s1, char *s2);4．串比较int strcmp(char*s1, char *s2);3.1.1.4 C++标准string(续)5．输入和输出函数6．定位函数char *strchr(char*s, char c); 7．右定位函数char *strrchr(char*s, char c);3.1.1.4 C++标准string(续)3.1.2 String抽象数据类型字符串类（class String）： 不采用char S[M]的形式而采用一种动态变长的存储结构。