北京大学信息学院2007年秋季学期《数据结构与算法A(实验班)》课程作业
张铭编写并发布 mzhang@https://www.doczj.com/doc/0f11372391.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 树
7年级英语第一学期测试卷参考答案 Chapter 1 Ⅰ. 1-5 BCABC 6-10 ACCCC 11-15 ABCBB 16-20 BACBC Ⅱ. 1. having 2. well 3. healthy 4. was 5. friends 6. heard 7. playing 8. playing 9. owner 10. length 11-15 CDBCC Ⅲ. 1-5 BAACB 6-10 ADCDD 11-15 DBDBA 16-20 CBDBB Ⅳ. 1-5 BDACB 6-10 ADABD Ⅴ. 1-5 BACCA 6-10 BCDDB 11-15 CDABB Ⅵ. 1. Where, live 2. How many 3. doesn’t come 4. Would, like 5. Because our school is near my home, I can walk to school. /Our school is near my home, so I can walk to school. 6. works as 7. How old 8. am interested in / am fond of 9. favourite subject 10. walk to Ⅶ. Dear Helen, Nice to meet you! My name is Wang Lin. I’m 12 years old now. I study in a middle school. I’m a little shy but I’m friendly to my classmates. I can speak Chinese and a little English. But I like English best. It is my favorite subject at school. I like playing basketball best. And my favorite color is red, because it looks good on me. Can you tell me something about you? Please write to me soon. Best wishes! Yours, Wang Lin Chapter 2 Ⅰ. 1-5 ACBAC 6-10 CCBCB 11-15 BACAC 16-20 BCCCA Ⅱ. 1. colorful 2. once 3. does 4. leaves 5. healthy 6. to look 7. not to talk 8. to finish, doing 9. Yours 10. drawing 11-15 BADCD Ⅲ. 1-5 BBCAC 6-10 ACCBC 11-15 ACBBD 16-20 CABDC Ⅳ. 1-5 BCDAB 6-10 ACDCB Ⅴ. 1-5 DCDBA 6-10 ACDBC 11-15 BABCA Ⅵ. 1. When, start 2. She wants to be a teacher in the future. 3. Where does 4. Dose Mary like apples or bananas? 5. I found a purse on my way to school. 6. Is Jane good at Math? 7. What, do 8. Where do 9. She never fails an exam. 10. good at Ⅶ. Dear Gina, How are you? I am quite busy these days. I get up at 6:15 every day. I dress myself quickly and have breakfast at half past six. After breakfast I go to school. I have four lessons in the morning and three in the afternoon. I study hard and always help my classmates with their lessons. I have lunch at school. At half past four, I usually have sports or
实验报告 课程名称:数据结构与算法 实验名称:树的应用 一、实验目的 ⑴、掌握二叉树的静态数组存放。 ⑵、掌握哈夫曼编码的基本概念。 ⑶、掌握哈夫曼编码树的构造方法。 ⑷、掌握哈夫曼编码的构造和使用。 ⑸、理解前缀编码的概念。 二、实验内容 ⑴、按照字符出现概率构造一个哈夫曼树。要求输入为一个文本文件（可以限 制文本仅仅包含字母），通过统计字符出现的次数计算概率，在此基础上构造哈夫曼树。 ⑵、打印出每一个字母对应的哈夫曼编码。 三、实验环境 硬件：Windows XP计算机、鼠标、键盘、显示器 开发环境：Microsoft Visual C++ 6.0 四、实验步骤 ①、点击开始菜单中的程序-Microsoft Visual C++ 6.0 点击菜单栏中的文件—新建—文件—C++ Source File ，在文件名(N)中写入5.cpp,再点击确定. ②、编写程序如下： #include
数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：
（1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满
《数据结构与算法》课后习题 答案 2.3 课后习题解答 2．3.2 判断题 1.线性表的逻辑顺序与存储顺序总是一致的。（×） 2．顺序存储的线性表可以按序号随机存取。（√） 3.顺序表的插入和删除操作不需要付出很大的时间代价,因为每次操作平均只有近一半的元素需要移动。（×） 4.线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√）...文档交流仅供参考... 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×) ６.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√) 7.线性表的链式存储结构优于顺序存储结构。（×) 8．在线性表的顺序存储结构中,插入和删除时移动元素的个数与该元素的位置有关。（√） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）
10．在单链表中，要取得某个元素,只要知道该元素的指针即可，因此,单链表是随机存取的存储结构。(×)１１.静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与ｉ无关。(×） 12.线性表的特点是每个元素都有一个前驱和一个后继。（×) 2．3．3 算法设计题 1．设线性表存放在向量A[arｒｓize]的前eleｎum个分量中，且递增有序。试写一算法,将x 插入到线性表的适当位置上,以保持线性表的有序性，并且分析算法的时间复杂度。...文档交流仅供参考... 【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻,不一定将向量和表示线性表长度的变量封装成一个结构体),因为是顺序存储，分配的存储空间是固定大小的,所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性,来确定插入元素的插入位置,后面的元素为它让出位置,（也可以从高下标端开始一边比较,一边移位)然后插入ｘ，最后修改表示表长的变量。...文档交流仅供参考... int iｎsert （datａtypｅＡ[］，iｎt *eｌｅnｕm，dataｔypｅ x)???/*设eｌenum为表的最大下标＊/...文档交流仅供参考...
第八章力 一、力弹力 知识点1 力是什么 1.物体对物体的称为力.在国际单位制中，力的单位是，简称，其符号是.只要有力的作用发生，就一定会涉及两个物体:一个是施加力的物体，叫;另一个是受到力的物体，叫. 2.用绳子拴住水桶，手拿绳子从井中提水，此时手受到向下的拉力作用，这个力的施力物体是( ) A.水 B.水和水桶 C.绳子 D.地球 3.下列关于力的说法中，正确的是( ) A.在产生力的作用时，施力物体和受力物体不一定同时存在 B.一个物体也能产生力 C.力是物体对物体的作用，彼此不直接接触的物体之间没有力的作用 D.施力物体和受力物体是成对出现的 知识点2 形变和弹力 4.(1)物体形状的改变，叫作;如果形变的物体在撤去外力后能，那么该物 体发生的形变叫作弹性形变. (2)使物体发生弹性形变的外力越大，物体的形变就越. (3)物体发生形变后，力图恢复原来的形状，而对另一个物体产生力，这个力叫作弹力， 拉力、压力(填“属于”或“不属于”)弹力. 5.关于弹力，下列说法正确的是( ) A.相互不接触的物体间也会产生弹力 B.拉力不属于弹力 C.物体在发生形变时产生的力叫弹力 D.压缩的弹簧能产生弹力 6.一本书放在水平桌面上，下列关于书和桌面受力情况的叙述中，正确的是( ) A.桌面受到向下的弹力是因为桌面发生了形变 B.桌面受到向下的弹力是因为书发生了形变 C.书受到向上的弹力是因为桌面发生了形变 D.书受到向上的弹力是因为书发生了形变 7.下列形变属于弹性形变的是( ) A.捏面人时面人发生的形变 B.打碎玻璃时玻璃发生的形变 C.人坐在沙发上时，沙发发生的形变 D.骆驼在沙漠中行走时，沙漠表面发生的形变 8.几位同学用同一个弹簧拉力器锻炼身体，每位同学都可以将弹簧拉力器拉开至两臂伸直.两臂伸直时，对弹簧拉力器的拉力最大的是( ) A.几位同学都一样大 B.手臂长的同学 C.体重大的同学 D.力气大的同学 9.如图所示，取一根钢尺，一端用左手手指按压在桌面上，右手的手指将露出桌面的一端下压至a、b两位置，手指感觉用力较大的是把钢尺弯至(填“a”或“b”)位置.这一实验现象可以说明物体的越大，产生的弹力就越大.
北京大学信息学院2007年秋季学期《数据结构与算法A(实验班)》课程作业 张铭编写并发布 mzhang@https://www.doczj.com/doc/0f11372391.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 树
学生学号Xxx实验课成绩 学生实验报告书 实验课程名称数据结构与算法综合实验 开课学院计算机科学与技术学院 指导教师姓名xxx 学生姓名xxx 学生专业班级xxxx 2015--2016学年第2学期
实验课程名称：数据结构与算法综合实验 实验项目名称二叉树与赫夫曼图片压缩报告成绩 实验者xx专业班级xxx组别 同组者完成日期2016年5月 2日第一部分：实验分析与设计（可加页） 一、实验目的和要求 1.目的 掌握树的存储结构 掌握二叉树的三种遍历方法 掌握 Huffman树、Huffman编码等知识和应用 使用 C++、文件操作和 Huffman算法实现“图片压缩程序”专题编程。 2.要求 针对一幅 BMP 格式的图片文件，统计 256 种不同字节的重复次数，以每种字 节重复次数作为权值，构造一颗有 256 个叶子节点的哈夫曼二叉树。 利用上述哈夫曼树产生的哈夫曼编码对图片文件进行压缩。 压缩后的文件与原图片文件同名，加上后缀.huf （保留原后缀），如 pic.bmp 压 缩后 pic.bmp.huf 二、分析与设计 依据上述的实验目的与要求，可导出实现的二叉树与赫夫曼图片压缩软件的流程为： ① 读取图片文件、统计权值 ②生成 Huffman树 ③生成 Huffman编码 ④ 压缩图片文件 ⑤ 保存压缩的文件 1.数据结构的设计 记录统计 256种不同字节的重复次数使用整型数组。 int weight[256] = { 0 }; 二叉树的存储结构。使用结构体存储节点，使用数组存储树的节点，使用静态二叉链表方 式存储二叉树。 Huffman编码存储结构 struct HTNode { int weight;//权值
《数据结构》课程设计任务书 学期：11-12-2 班级：网络10 一、设计目的 《数据结构》是一门实践性较强的专业基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 二、设计要求 1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 2、学生必须仔细研读《数据结构》课程设计(实习)要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。 3、本次课程设计按照教学要求需要在一周半时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时地向指导教师汇报。 4、编程语言任选。 三、设计选题 题一：线索二叉树（**） 任务： 1.建立中序线索二叉树，并且中序遍历； 2.求中序线索二叉树上已知结点中序的前驱和后继； 需求分析和概要设计： 建立中序线索二叉树，并且中序遍历。首先就是要建立树，再将树中序线索化。求中序线索二叉树上已知结点中序的前驱和后继时，即是将树在遍历一遍。也可以在遍历的过程中，将树的结点放在数组中，当然必须讲述先遍历一遍，这是用空间来换时间。 详细设计： 树的结构体的声明： typedef char TElemtype; typedef enum PointerTag{Link,Thread}; //设置标志：Link为指针，Thread为线索typedef struct BiThrNode{ //树结点结构体 TElemtype data; struct BiThrNode *lchild,*rchild; PointerTag LTag,RTag; }BiThrNode,*BiThrTree; 相关函数的声明：
《数据结构与算法》期末复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 二、液体的压强 知识点1 液体压强的存在 1.如图甲所示，在两端开口的玻璃管下端蒙上橡皮膜，向玻璃管内倒水，看到橡皮膜向下凸出，说明液体对有压强;如图乙所示，用手指触压装水的保鲜袋，手指感觉到水和袋子对手有压力，说明液体对有压强. 2. 如图所示实验中，把下端蒙有橡皮膜的空玻璃管插入水中，会看到橡皮膜向管内凹陷，说明了，并且空玻璃管越向下放，橡皮膜形变越大，说明. 知识点2 探究影响液体内部压强的因素 3. 在“探究影响液体内部压强的因素”实验中. (1)压强计是通过U形管来显示橡皮膜所受压强的大小. (2)小华实验时的情形如图所示，四幅图中烧杯内的液面相平.(不考虑实验结论的偶然性) ①比较图甲和图，可以初步得出结论:在同种液体中，液体内部压强随深度的 增加而增大. ②保持金属盒在水中的深度不变，改变它的方向，如图乙、丙所示，根据实验现象可以 初步得出结论: . ③比较图乙和图丁，能初步得出液体内部压强与液体密度有关的结论吗? ，理由 是. (3)根据已有的压强知识，你认为水内部压强的大小与距离水底的距离d之间(填 “没有关系”或“有关系”). 4.如图所示，小明将压强计的探头放入水中的某一深度处，记下U形管中两液面的高度差h，下列操作中能使高度差h增大的是( ) A.将探头向下移动一段距离 B.探头水平向左移动一段距离 C.将探头放在酒精中的同样深度处 D.将探头在原深度处向其他方向任意转动一个角度 知识点3 液体压强的特点 5.装满水的容器侧壁上开有三个孔，水从小孔中流出，图中描述正确的是( ) 6.如图所示，玻璃管两端开口处蒙的橡皮膜绷紧程度相同，将此装置置于水中，图中能反 映橡皮膜受到水的压强后的凹凸情况的是( ) 7.如图所示的试管内装一定质量的水，当试管竖直放置时，水对管底的压强为1p ;当试管倾斜放置时，水对管底的压强为2p 比较1p 、2p 的大小，则( ) A. 1p <2p B. 1p =2p C. 1p >2p D.条件不足，无法判断 8.如图所示，装有水的容器静止在斜面上，其底部a 、b 、c 三处受到水的压强分别为a p 、b p 、c p ，则以下判断正确的是( ) A. a p =b p =c p B. a p b p >c p D. a p >b p =c p 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 合肥学院 计算机科学与技术系 课程设计报告 2009 ～2010 学年第二学期 课程 数据结构与算法 课程设计 名称 二叉排序树运算学生姓名顾成方 学号0704011033 专业班级08计科(2) 指导教师王昆仑张贯虹 2010 年 5 月 题目：（二叉排序树运算问题）设计程序完成如下要求：对一组数据构造二叉排序树，并在二叉排序树中实现多种方式的查找。基本任务：⑴选择合适的储存结构构造二叉排序树；⑵对二叉排序树T作中序遍历，输出结果；⑶在二叉排序树中实现多种方式的查找，并给出二叉排序树中插入和删除的操作。 ⑷尽量给出“顺序和链式”两种不同结构下的操作，并比较。 一、问题分析和任务定义 本次程序需要完成如下要求：首先输入任一组数据，使之构造成二叉排序树，并对其作中序遍历，然后输出遍历后的数据序列；其次，该二叉排序树能实现对数据（即二叉排序树的结点）的查找、插入和删除等基本操作。 实现本程序需要解决以下几个问题： 1、如何构造二叉排序树。 2、如何通过中序遍历输出二叉排序树。 3、如何实现多种查找。 4、如何实现插入删除等操作。 二叉排序树的定义： ⑴其左子树非空，则左子树上所有结点的值均小于根结点的值。 ⑵若其右子树非空，则右子树上所有结点的值大于根结点的值。 ⑶其左右子树也分别为二叉排序树。 本问题的关键在于对于二叉排序树的构造。根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现：输入（插入）的第一个数据即为根结点；继续插入，当插入的新结点的关键值小于根结点的值时就作为左孩子，当插入的新结点的关键值大于根结点的值时就作为右孩子；在左右子树中插入方法与整个二叉排序树相同。当二叉排序树建立完成后，要插入新的数据时，要先判断已建立的二叉排序树序列中是否已有当前插入数据。因此，插入算法还要包括对数据的查找判断过程。 本问题的难点在于二叉排序树的删除算法的实现。删除前，首先要进行查找，判断给出的结点是否已存在于二叉排序树之中；在删除时，为了保证删除结点后的二叉树仍为二叉排序树，要考虑各种情况，选择正确 数据结构复习题 第一章概论 一、选择题 1、研究数据结构就是研究( D )。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是( A )。 A. 空间复杂度和时间复杂度 B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 fori0;im;i++ forj0;jn;j++ a[i][j]i*j; A. Om2 B. On2 C. Om*n D. Om+n 6、算法是( D )。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。 A. On B. Onlog2n C. On2 D. Olog2n 8、下面程序段的时间复杂度为( C )。 i1; whilein ii*3; A. On B. O3n C. Olog3n D. On3 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是( A )。 is0; whilesn i++;s+i; A. On B. On2 C. Olog2n D. On3 11、抽象数据类型的三个组成部分分别为( A )。 A. 数据对象、数据关系和基本操作 B. 数据元素、逻辑结构和存储结构 C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型 12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。 启东中学作业本答案英语 【篇一：辅导书】 新概念》阅读现代文中考专版、经典学法频道《轻巧夺冠》这本书 侧重于基础知识当然你必须先掌握基础知识才能深入?? 语文数学 备上一本上了初二物理化学也备上的！《经典学法频道》 数学：《点拨》《倍速学习法》《轻巧夺冠》《典中典》英语： 《剖析》《典中典》《启东中学作业本》（龙门书局）《轻巧夺冠》点拨.. 我也初中..我英语年纪第一哦..我就是用这个.. 我们班英语老师也用 这个.. 是配套的..有语法讲解课文分析习题练习等等... 很全面.. 我门班百分之七十的人都用这个..各个科目的都有.. 你去书 店买都应该有的.. 如果你要练的话最好就买典中典.. 高才生就买这个吧.. 很有挑战性..题量也很大.. 中等生的话可以考虑 轻巧夺冠..这个难度要稍微小些.. 政治：《轻巧夺冠》 历史：《中学生教材全解》完全解读，点拨，倍速学习法 物理：《题网》《题典》【题很多也很经典】还有《分类精选》也 相当好一定要买的各省中考题时刻做一做不是你学完了才能做 提前做有好处这个最好选【天利38】版本的去书店问问就知道的...《中华题王》《成功学习计划》化学：《成功学习计划》《典中典》地理：《海淀单元卷》《轻巧夺冠》生物《中华题王》95分以上 《学习高手》对于课堂知识、基础知识的讲解、训练比较全面，全 部理解透了，考90分不是问题（我就是用这个的）《完全解读》题目有些比较深，如果你生物学的很好，想扩展一下，就用这个 世纪金榜，我们中考时就用了这本，挺好的，积分吧《金榜学案》 完全解读例题挺多的，内容挺详细的绿卡图书知识点特别多看着 清晰 数学和语文就买万象思维的《成功学习计划》。 英语就买《魔法英语》。我也在用这本，里面包含了句型、语法、 小常识、英美的礼节、适量的题目等。但如果你的英语基础稍差一点，就买《同步新课堂》，里面都是基础题目。 第七章树 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 常用的大数据结构与算法 在学习了解这些数据结构和算法之前，引用一位前辈的话： “我们不需要你能不参考任何资料，实现红黑树；我们需要的是你能在实践当中，选择恰当的数据结构完成程序开发；在必要的时候，能在已有的数据结构基础上进行适当改进，满足工程需要。但要做到这一点，你需要掌握基础的算法和数据结构，你需要理解并应用一些高级数据结构和算法的思想。因此，在程序员这条道路上，你要想走得更远，你需要活用各种数据结构，你需要吸收知名算法的一些思想，而不是死记硬背算法本身。” 那么，工程实践当中，最常用的算法和数据结构有哪些？ 以下是Google工程师Arjun Nayini在Quora给出的答案，得到了绝大多数人的赞同。 最常用的算法 1.图搜索算法(BFS,DFS) 2.排序算法 3.通用的动态规划算法 4.匹配算法和网络流算法 5.正则表达式和字符串匹配算法 最常用的数据结构 1.图，尤其是树结构特别重要 2.Maps结构 3.Heap结构 4.Stacks/Queues结构 5.Tries树 其他一些相对比较常用的数据算法还有：贪心算法、Prim’s / Kruskal’s算法、Dijkstra’s 最短路径算法等等。 怎么样才能活用各种数据结构？ 你能很清楚的知道什么时候用hash表，什么时候用堆或者红黑色？在什么应用场景下，能用红黑色来代替hash表么？要做到这些，你需要理解红黑树、堆、hash表各有什么特性，彼此优缺点等，否则你不可能知道什么时候该用什么数据结构。 常言道： 程序=算法＋数据结构 程序≈数据结构 小编希望这些算法的掌握能够帮助大家拓宽握数据结构和算法的视野，提高算法设计和动手编程的能力。 大学 《数据结构与算法分析》课程 习题及参考答案 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( ) 个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左 孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有 双亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题 6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};八年级物理下册《液体的压强》练习题(含答案)
北大2015年秋季学期数据结构课程作业
二叉排序树运算-数据结构与算法课程设计报告_l
数据结构与算法复习题库含答案
启东中学作业本答案英语
北大PKU 慕课 EDX 数据结构与算法 第七章图 quiz答案与解析
常用的大数据结构与算法
数据结构与算法分析习题与参考答案
相关主题
文本预览