北京理工大学2013级数据结构B试题(A卷)_答案
一、选择题
1、从逻辑结构上可以把数据结构分为【 C 】。
A、动态结构和静态结构
B、紧凑结构和非紧凑结构
C、线性结构和非线性结构
D、内部结构和外部结构
2、在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元
素时，需要从后向前依次后移【 B 】个元素。
A、n-i
B、n-i+1
C、n-i-1
D、i
3、链表结构不具有下列【 B 】特点。
A、插入和删除无需移动元素
B、可随机访问链表中的任意元素
C、无需实现分配存储空间
D、所需空间与结点个数成正比。
4、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，
则执行【C】。
A、s->next = p->next; p->next = s;
B、p->next = s->next; s->next = p;
C、q->next = s; s->next = p;
D、p->next = s; s->next = q;
5、一个栈的入栈序列是1，2，3，4，5，则栈不可能输出的序列是【 C 】。
A、54321
B、45321
C、43512
D、12345
6、判断一个队列Q（元素最多为M个）为空的条件是【 C 】。
A、Q->rear – Q->front = M
B、Q->rear – Q->front -1 ==M
C、Q->rear == Q->front
D、Q->rear + 1 == Q->front
7、在一个链队列中，假设f和r分别指向队首和队尾，则插入s所指结点的运算是【 A 】。
A、r->next = s; r=s;
B、f->next = s; f=s;
C、s->next = r; r=s;
D、s->next = f; f=s;
8、深度为5的二叉树至多有【 A 】个结点。
A、31
B、32
C、16
D、10
9、在一非空二叉树的中序遍历序列中，根结点的右边【 A 】。
A、只有右子树上的所有结点
B、只有右子树上的部分结点
C、只有左子树上的所有结点B、只有左子树上的部分结点
10、如果一棵完全二叉树有1001个结点，则其叶子结点个数为【 D 】。
A、250
B、500
C、502
D、490
11、在一个图中，所有顶点的度数之和是所有边数的【 C 】倍。
A、1/2
B、1
C、2
D、4
12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的【 A 】。
A、先序遍历
B、中序遍历
C、后序遍历
D、按层遍历
13、一个有n个顶点的无向图最多有【 D 】条边。
A、n
B、n(n-1)
C、2n
D、n(n-1)/2
14、静态查找表与动态查找表的根本区别在于【 B 】。
A、它们的逻辑结构不同
B、施加在其上的操作不同
C、所包含的数据元素类型不同
D、存储实现不一样
15、顺序查找适用于存储结构为【 C 】的线性表。
A、哈希存储
B、压缩存储
C、顺序存储或链式存储
D、索引存储
16、若一颗二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足【 B 】。
A、所有结点均无孩子
B、所有结点均无右孩子
C、只有一个叶子结点
D、是一颗满二叉树
17、二叉排序树是【 B 】。
A、每一分支结点的度均为2的二叉树
B、中序遍历得到一升序序列的二叉树
C、按从左到右顺序编号的二叉树
D、每一分支结点的值均小于左子树上所有结点的值，又大于右子树上所有结点的值
18、具有12个记录的序列，采用冒泡排序最少的比较次数是【 C 】。
A、1
B、144
C、11
D、66
19、堆的形状是一棵【 C 】。
A、二叉排序树
B、满二叉树
C、完全二叉树
D、平衡二叉树
20、在一个包含n个顶点e条边的无向图的邻接矩阵中，零元素的个数为【D 】。
A、e
B、2e
C、n2-e
D、n2-2e
二、判断对错
【x】1、具有n个顶点的连通图至少有n条边。
【x】2、链表的单个结点内部的存储空间可以是不连续的。
【√】3、栈和队列的共同点是只允许在端点处插入和删除元素。
【√】4、使用循环队列可以解决队列顺序存储时的假溢出问题。
【x】5、要想通过遍历序列还原为惟一二叉树，应当知道其先序序列和后序序列。
【√】6、若一个结点是某二叉树子树的中序遍历序列的第一个结点，则它也必是该子树的后序遍历序列的第一个结点。
【x】7、完全二叉树可采用顺序存储结构存储，非完全二叉树则不能。
【√】8、对于一棵含有n个结点的完全二叉树，将其结点按从上到下且从左至右按1至n进行编号，则对其任意一个编号为i的结点，如果它有左孩子，则其左孩
子结点的编号为2i。
【√】9、哈夫曼树的所有子树也都是哈夫曼树。
【x 】10、当图的边较少而结点较多时，求其最小生成树用Prim算法比用Kruskal算法效率更高。
三、填空题
1、向量的第一个元素的存储地址是200，每个元素的长度是3，那么第6个元素的存储地址是。
答案：215
2、在一个带头结点的单链表中，p所指结点既不是首元结点，也不是尾元结点，删除p 结点的语句序列是、、。
答案: q=p，p=p->next，free(q)
3、设堆栈有足够的存储空间，那么向堆栈中插入一个数据元素，即入栈的操作过程是、。
答案: 存入数据元素，栈顶指针加1
4、一般情况下，向循环队列中插入数据元素时，需要判满队列是否已经满了，判断条件是：。
答案: (rear+1)%MaxSize == front
6、已知循环队列用数组data[1…n]存储元素值，front和rear分别表示队头和队尾指针，则当前队列中元素的个数为。
答案: (n+rear-frone)%n或(n+rear-frone) mod n
7、深度为k的二叉树最多有个结点，深度为k的完全二叉树最少有个结点（k≥1）。
答案: 2k-1，2k-1
8、如以{2,3,6,7,9}作为叶子结点的权值构造哈夫曼树，则其最短带权路径长度为
。
答案: 55
10、已知某二叉树的中序序列和前序序列分别为42758136、12457836，则它的后序序列为。
答案: 47852631
12、在有n个顶点的有向图中，每个顶点的度最大可达到。
答案: 2(n-1)
13、在有序表A[1…18]中，采用折半查找算法查找元素值等于A[7]的元素，所比较过的元素的下标依次为。
答案: 9 4 6 7
14、一组记录的输入顺序为(25,38,65,90,72,14)，则利用堆排序方法建立的初始“小顶堆”为。
答案: 14,38,25,90,72,65
四、简答题
1、设有一段正文是由字符集{a, b, c, d, e, f, g, h}组成，正文长度为100个字符，其中每个字符在正文中出现的次数分别为17, 12, 14, 4, 10, 9, 20, 3。若采用哈夫曼树对这段文字
进行压缩存储，请完成如下工作：
（1）构造哈夫曼树（规定权值较小的结点为左子树）；
（2）求出每个字符的哈夫曼编码；
（3）若其中一段正文的二进制编码序列为“10111100011000101”，请按（2）的哈夫曼编码将其译码成原始正文。
答案：
（1）树的结构为：
（2）编码为a=111，b=101，c=110，d=0001，e=100，f=001，g=01，h=0000
（3）上述编码序列的对应原文为：badegg
2、一棵有11个结点的二叉树的存储情况如下图所示（其中“∧”表示空指针），left[i]和right[i]分别表示结点i的左、右孩子，根结点是序号为3的结点，要求：
（1）画出该二叉树；
（2）分别写出该二叉树的前序和中序遍历序列。
第2题图
答案：
（1）二叉树的结构如图所示：
（2）前序序列ALKRSECFMBD
中序序列RKSLEAFCBDM
3、设数据集合D={2, 24, 12, 15, 32, 9, 10, 35, 7, 5}，要求：
（1）依次读取D中的各个数据，构造一棵二叉排序树Bt；
（2）如何根据此二叉树Bt求得数据集合D的一个有序序列？并写出该有序序列；（3）画出在上述二叉树中删除结点“12”后得到的二叉树结构。
答案：
（1）构造的二叉排序树如下：
（2）上述二叉树Bt的中序遍历序列即是数据集合D的一个有序序列：2，5，7，9，10，12，15，24，32，35
（3）删除结点12后的二叉树结构为下面任意一种结构：
或者
4、用深度优先和广度优先遍历算法对下图G进行遍历（要求从顶点A出发），请给出深度优先和广度优先遍历序列。
第4 题图
答案：深度优先序列：ABFDEGHC
广度优先序列：ABCFDEHG
5、对于如下所示的加权无向图，写出用Prim算法构造最小生成树的过程，并画出最后得到的最小生成树。
第5题图答案：最小生成树的构造过程如下图所示：
北京理工大学汇编语言实验六磁盘文件存取实验报告
第六章磁盘文件存取实验（设计性实验） 一、实验要求和目的 1．理解文件、目录的概念； 2．了解FCB(文件控制块)方式文件管理方法； 3．掌握文件代号式文件存取方式； 4．学习使用文件指针读取文件 二、软硬件环境 1．硬件环境：计算机系统windows； 2．软件环境：装有MASM、DEBUG、LINK、等应用程序。 三、实验涉及的主要知识单元 DOS功能调用中断（INT 21H）提供了两类磁盘文件管理功能，一类是FCB(文件控制块)方式，另一类是文件代号式存取方式。 对于文件的管理，实际上是对文件的读写管理，DOS 设计了四种存取文件 方式：顺序存取方式、随机存取方式、随机分块存取方式和代号法存取方式。文件的处理步骤 A）写之前必须先建立文件、读之前必须先打开文件。 B）写文件之后一定要关闭文件。通过关闭文件，使操作系统确认此 文件放在磁盘哪一部分，写后不关闭会导致写入文件不完整。 1、文件代号式存取方式： 当用户需要打开或建立一个文件时，必须提供文件标识符。文件标识符用ASCII Z 字符串表示。ASCII Z 字符串是指文件标识符的ASCII 字符串后面再加1 个“0”字符。文件标识符的字符串包括驱动器名、路径名和文件名。其格式为 [d:][path]filename[.exe] 其中d 为驱动器名，path 为路径名，.exe 为文件名后缀。 中断 21H 提供了许多有关目录和文件操作的功能，其中文件代号式存取方式常用的功能如下： 2、操作目录的常用功能 39H——创建目录 3BH——设置当前目录 3AH——删除目录 47H——读取当前目录 有关中断功能的详细描述和调用参数在此从略，需要查阅者可参阅相关资料 之目录控制功能。 3、用文件句柄操作文件的常用功能 3CH——创建文件 4EH——查找到第一个文件 3DH——打开文件 4FH——查找下一个文件 3EH——关闭文件 56H——文件换名 3FH——读文件或设备 57H——读取/设置文件的日期和时间 40H——写文件或设备 5AH——创建临时文件 41H——删除文件 5BH——创建新文件
北京理工大学《数据结构与算法设计》实验报告实验四
《数据结构与算法设计》 实验报告 ——实验四 学院： 班级： 学号： 姓名：
一、实验目的 1. 通过实验实践、巩固线性表的相关操作； 2. 熟悉VC 环境，加强编程、调试的练习； 3. 用C 语言实现线性表的抽象数据类型，实现线性表构造、插入、取数据等基本操作； 4. 理论知识与实际问题相结合，利用上述基本操作实现三种排序并输出。 二、实验内容 从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。 三、程序设计 1、概要设计 为了实现排序的功能，需要将输入的数字放入线性表中，进行进一步的排序操作。 (1)抽象数据类型： ADT SqList{ 数据对象：D={|,1,2,,,0}i i a a ElemSet i n n ∈=≥ 数据关系：R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作： InPut(SqList &L) 操作结果：构造一个线性表L 。 OutPut(SqList L) 初始条件：线性表L 已存在。 操作结果：按顺序在屏幕上输出L 的数据元素。 InsertSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行插入排序。 QuickSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行快速排序。 SelectSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行选择排序。 }ADT SqList ⑵主程序流程 由主程序首先调用InPut(L)函数创建顺序表，调用InsertSort(L)函数进行插入排序， 调用OutPut(L)函数显示排序结果。调用QuickSort(L)函数进行交换排序，调用OutPut(L) 函数显示排序结果。调用SelectSort(L)函数进行选择排序，调用OutPut(L)函数显示排序 结果。 ⑶模块调用关系 由主函数模块调用创建顺序表模块，排序模块与显示输出模块。
北京理工大学汇编实验五
一、实验目的 1、掌握子程序有关基本知识，学会子程序设计方法； 2、掌握主程序与子程序之间的调用关系及调用方法； 3、掌握汇编语言字符串处理方法； 4、掌握字符串的输入输出程序设计方法； 5、掌握数制转换程序实现方法。 二、实验软硬件环境 1、硬件环境：惠普64 位一体化计算机及局域网； 2、软件环境：windows 8，红蜘蛛管理系统，MASM for Windows。 三、实验相关知识 把功能相对独立的程序段单独编写和调试，作为一个相对独立的模块供程序使用，就性成子程序。子程序可以实现源程序的模块化，可简化源程序结构，可以提高编程效率。 1) 子程序的定义语句格式 汇编语言子程序以proc 语句行开始，以endp 语句行结束。如： 过程名PROC near[或far] 过程体 .......................... 过程名ENDP 在主程序中用CALL 过程名调用。主程序和子程序之间传递参数通常通过栈来进行，当然也可以用某些缺省的寄存器或内存来传递。但以通过栈来传递参数程序的通用性最强。 2) 子程序调用说明 子程序从PROC 语句开始，以ENDP 语句结束，程序中至少应当包含一条RET 语句用以返回主程序。在定义子程序时，应当注意其距离属性：当子程序和调用程序在同一代码段中时，用NEAR 属性；当子程序及其调用程序不在同一个代码段中时，应当定义为FAR 属性。当由DOS 系统进入子程序时，子程序应当定义为FAR 属性。为执行子程序后返回操作系统，在子程序的前几条指令中设置返回信息。 3) 子程序使用中的问题 A、主程序调用子程序是通过CALL 指令来实现的。子程序执行后，通过RET 指令， 返回主程序调用指令CALL 的下一条指令，继续执行主程序。一个子程序可以由 主程序在不同时刻多次调用。如果在子程序中又调用了其他的子程序，则称为子程 序的嵌套。特别是当子程序又能调用子程序本身时，这种调用称为递归。 B、调用子程序时寄存器及所用存储单元内容的保护。如果子程序中要用到某些寄存器 或存储单元时，为了不破坏原有的信息，要将寄存器或存储单元的原有内容压栈保 护，或存入子程序不用的寄存器或存储单元中。 C、用于中断服务的子程序则一定要把保护指令安排在子程序中，这是因为中断是随机 出现的，因此无法在主程序中安排保护指令。 D、调用程序在调用子程序时需要传送一些参数给子程序，这些参数是子程序运算中所 需要的原始数据。子程序运行后要将处理结果返回调用程序。原始数据和处理结果 的传递可以是数据，也可以是地址，统称为参数传递。 E、参数传递必须事先约定，子程序根据约定从寄存器或存储单元取原始数据（称入口 参数）；进行处理后将处理结果（称出口参数）送到约定的寄存器或存储单元，返回到调用程序。参数传递一般有下面三种方法：用寄存器传递：适用于参数传递较少、
北京理工大学数据结构编程练习答案
1.一元多项式相加(10分) 成绩: 10 / 折扣: 0.8 题目说明： 编写一元多项式加法运算程序。要求用线性链表存储一元多项式（参照 课本）。该程序有以下几个功能： 1. 多项式求和 输入：输入三个多项式，建立三个多项式链表Pa、Pb、Pc （提示：调用CreatePolyn(polynomial &P,int m)。 输出：显示三个输入多项式Pa、Pb、Pc、和多项式Pa+Pb、多项式Pa+Pb+Pc （提示：调用AddPolyn(polynomial &Pa, polynomial Pb), 调用 PrintPolyn(polynomial P))。 0. 退出 输入： 根据所选功能的不同，输入格式要求如下所示（第一个数据是功能选择编号，参见测试 用例）： ? 1 多项式A包含的项数，以指数递增的顺序输入多项式A各项的系数（整数）、指数（整数） 多项式B包含的项数，以指数递增的顺序输入多项式B各项的系数（整数）、指数（整数） 多项式C包含的项数，以指数递增的顺序输入多项式C各项的系数（整数）、指数（整数） ?0 －－－操作终止，退出。 输出： 对应一组输入，输出一次操作的结果（参见测试用例）。 ? 1 多项式输出格式：以指数递增的顺序输出: <系数,指数>,<系数,指数>,<系数,指数>,参见测试用例。零多项式的输出格式为<0,0> ?0 无输出 1.
#include 1 北京理工大学2012-2013学年第一学期 工科数学分析期末试题(A 卷) 一. 填空题（每小题2分, 共10分） 1. 设?????<≥++=01arctan 01)(x x x x a x f 是连续函数，则=a ___________. 2. 曲线θρe 2=上0=θ的点处的切线方程为_______________________________. 3. 已知),(cos 4422x o bx ax e x x ++=- 则_,__________=a .______________=b 4. 微分方程1cos 2=+y dx dy x 的通解为=y __________________________________. 5. 质量为m 的质点从液面由静止开始在液体中下降, 假定液体的阻力与速度v 成正比, 则质点下降的速度)(t v v =所满足的微分方程为_______________________________. 二. (9分) 求极限 21 0)sin (cos lim x x x x x +→. 三. (9分) 求不定积分?+dx e x x x x )1arctan (12. 四. (9分) 求322)2()(x x x f -=在区间]3,1[-上的最大值和最小值. 五. (8分) 判断2 12arcsin arctan )(x x x x f ++= )1(≥x 是否恒为常数. 六. (9分) 设)ln(21arctan 22y x x y +=确定函数)(x y y =, 求22,dx y d dx dy . 七. (10分) 求下列反常积分. (1);)1(1 22?--∞+x x dx (2) .1)2(1 0?--x x dx 八. (8分) 一垂直立于水中的等腰梯形闸门, 其上底为3m, 下底为2m, 高为2m, 梯形的上底与水面齐平, 求此闸门所受 到的水压力. (要求画出带有坐标系的图形) 九. (10分) 求微分方程x e x y y y 3)1(96+=+'-''的通解. 十. (10分) 设)(x f 可导, 且满足方程a dt t f x x x f x a +=+?)())((2 ()0(>a , 求)(x f 的表达式. 又若曲线 )(x f y =与直线0,1,0===y x x 所围成的图形绕x 轴旋转一周所得旋转体的体积为,6 7π 求a 的值. 十一. (8分) 设)(x f 在]2,0[上可导, 且,0)2()0(==f f ,1sin )(1 21 =?xdx x f 证明在)2,0(内存在ξ 使 .1)(='ξf 偏微分方程数值解大作业 目录 第一题 (3) 第二题 (7) 第三题 (16) 第四题 (20) 第五题 (26) 第六题（附加题1） (39) 第七题（附加题2） (45) 第八题（附加题3） (51) 第一题 习题1 3. （1）解曲线图 图1 （2）误差曲线图 图2 （3）表格 表1 部分点处精确解和取不同步长时所得的数值解 表2 取不同步长时部分结点处数值解的误差的绝对值和数值解的最大误差 （4）MATLAB源代码 M=64; a=0; b=pi/2; h=(b-a)/M; x=[a+h:h:b-h]; u=zeros(M-1,M-1); u(1,1)=(2/h^2)+(x(1)-1/2)^2; u(1,2)=-(1/h^2); u(M-1,M-1)=(2/h^2)+(x(M-1)-1/2)^2; u(M-1,M-2)=-(1/h^2); for i=2:M-2 u(i,i-1)=-(1/h^2); u(i,i)=(2/h^2)+(x(i)-1/2)^2; u(i,i+1)=-(1/h^2); end f=zeros(M-1,1) f(1)=(x(1).*x(1)-x(1)+5/4).*sin(x(1)); f(M-1)=(x(M-1).*x(M-1)-x(M-1)+5/4).*sin(x(M-1))+1/h^2; for j=2:M-2 f(j)=(x(j).*x(j)-x(j)+5/4).*sin(x(j)); end y=inv(u)*f; true=sin(x); plot(x,y'-true) 实验五子程序设计实验（设计性实验） 一、实验要求和目的 1．熟悉汇编语言程序设计结构； 2．熟悉汇编语言子程序设计方法； 3．熟悉利用汇编语言子程序参数传递方法； 4．熟悉汇编语言字符串处理基本指令的使用方法； 5．掌握利用汇编语言实现字符串的输入输出程序设计方法； 6．掌握数制转换程序实现方法。 二、软硬件环境 1、硬件环境：计算机系统windows； 2、软件环境：装有MASM、DEBUG、LINK、等应用程序。 三、实验涉及的主要知识 A）子程序知识要点： 1、掌握子程序的定义语句； 过程名 PROC [near/far] 过程体 RET 过程名 ENDP 2.子程序结构形式 一个完整的子程序一般应包含下列内容: 1. ）子程序的说明部分 在设计了程序时,要建立子程序的文档说明,使用户能清楚此子程序的功能和调用方法. 说明时,应含如下内容: .子程序名:命名时要名中见意. .子程序的功能:说明子程序完成的任务; .子程序入口参数:说明子程序运行所需参数及存放位置; .子程序出口参数:说明子程序运行结果的参数及存放位置; .子程序所占用的寄存器和工作单元； .子程序调用示例； 2、）掌握子程序的调用与返回 在汇编语言中，子程序的调用用CALL，返回用RET 指令来完成。 .段内调用与返回：调用子程序指令与子程序同在一个段内。因此只修改IP； .段间调用与返回：调用子程序与子程序分别在不同的段，因此在返回时，需同时修改CS：IP。 3．）子程序的现场保护与恢复 保护现场：在子程序设计时，CPU 内部寄存器内容的保护和恢复。 一般利用堆栈实现现场保护和恢复的格式： 过程名PROC [NEAR/FAR] 889数据结构 考试内容： 数据结构主要考查考生以下几个方面： 1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3.能够选择合适的数据结构和方法进行问题求解。 应掌握的具体内容为： 一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的概念 （二）二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 （三）树、森林 1.书的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 （四）树的应用 1.等价类问题 2.哈夫曼（Huffman）树和哈夫曼编码 四、图 （一）图的概念 （二）图的存储及基本操作 1.邻接矩阵法 2.邻接表法 （三）图的遍历 1.深度优先搜索 2.广度优先搜索 （四）图的基本应用及其复杂度分析 1.最小（代价）生成树 2.最短路径 3.拓扑排序 4.关键路径 五、查找 （一）查找的基本概念 （二）顺序查找法 （三）折半查找法 （四）B-树 （五）散列（Hash）表及其查找 （六）查找算法的分析及应用 六、内部排序 （一）排序的基本概念 （二）插入排序 1.直接插入排序 2.折半插入排序 （三）起泡排序（bubble sort） （四）简单选择排序 （五）希尔排序（shell sort） （六）快速排序 （七）堆排序 （八）二路归并排序（merge sort） （九）基数排序 （十）各种内部排序算法的比较 （十一）内部排序算法的应用 题型和分值 填空题20分、选择题30分、问答题70分、算法题30分 参考书目 数据结构（C语言版）严蔚敏吴伟民清华大学出版社 课程编号：H0172103 北京理工大学2017-2018学年第一学期 工科数学分析（上）期末试题(A 卷) 座号 _______ 班级_____________ 学号_____________ 姓名_____________ (试卷共6页,十个大题. 解答题必须有过程. 试卷后面空白纸撕下做草稿纸. 试卷不得拆散.) 1．若 e x x kx x 1 )2( lim =-∞ → ，则=k . 2．已知,arctan 2111ln 41x x x y --+= 则=dx dy . 3. =-+?dx xe x e x x 1 02 ) 1() 1( . 4 . =?xdx x sin 2 . 5. 设x y y cos =+'，则=y . 二、计算题（每小题5分，共20分） 1.求极限 ).2 sin 211(sin lim 3n n n n -∞→ 2. 设 x x y x 2sin sin +=，求dy . 3. 计算 dx x x x x ? -++1 1 2 211cos 2-. 4.求)cos(y x dx dy +=的通解. 三、（8分）已知0)-1(lim 2 =-+-+∞ →b ax x x x ，试确定常数a 和b 的值. 四、（6分）已知,...).2,1)((21,0,011=+= >>+n b b b b b b n n n 证明: 数列{}n b 极限存在；并求此极限. 五、（8分）求函数2) 1(42 -+= x x y 的单调区间和极值，凹凸区间和拐点，渐近线. 六、（8分）设曲线2x y =，x y =围成一平面图形D . (1) 求平面图形D 的面积； (2) 求平面图形D 绕y 轴旋转所得旋转体的体积. 七、（8分）设一长为l 的均匀细杆，线密度为μ,在杆的一端的延长线上有一质量为m 的质点，质点与该端的距离为a . （1）求细杆与质点间的引力； （2）分别求如果将质点由距离杆端a 处移到b 处(b a >)与无穷远处时克服引力所 做的功. 八、（8分）设)(x f 在]1,1[-上具有三阶连续导数，且,0)0(,1)1(,0)1('===-f f f 证明在开区间)1,1(-内至少存在一点ξ，使3)()3(=ξf . 九、（8分）设?-+ =x x dt t f t x xe x f 0)()()(, 其中)(x f 连续，求)(x f 的表达式. 十、（6分）已知)(x f 在闭区间[]6,1上连续，在开区间)6,1(内可导，且 ，5)1(=f ，1)5(=f .12)6(=f 证明：存在)6,1(∈ξ，使 22)()(=-+'ξξξf f 成立. 北京理工大学2017-2018学年第一学期《工科数学分析》（上）期末试题(A 卷) 标准答案及评分标准 2018年1月12日 一、填空（每小题4分，共20分） 1． 21 2．42 1x x - 3. )(，不收敛+∞∞ 4 . C x x x x x +++-cos 2sin 2cos 2 5. x ce x x y -++= )cos (sin 2 1 二、计算题（每小题5分，共20分） 1. 解：)2 sin 211(sin lim 3x x x x -∞→ 3 12sin 211sin lim x x x x -=∞→ x t 1=令 30) 2sin(21 sin lim t t t t -=→ …………. 2分 2 0cos 1sin lim t t t t t -?=→21= …………. 4分 2 1 )2sin 211(sin lim 3=-∴∞→n n n n …………. 5分 一. (10分) 用三角分解（LU 分解）求解下方程组,要求写出L,U 矩阵： 1232644145361182x x x -?????? ? ? ? -= ? ? ? ? ? ?-???? ??. 二. (10分) 已知矩阵6 37398785A -?? ? =- ? ?--?? ,求1cond()A 和cond()A ∞,要求计算过程保留三位 有效数字,并简要分析所得结果. 三. (10分) 设矩阵1001005a A b b a ?? ? = ? ??? ,且0det()A ≠,试求用,a b 表示的求解线性方程组 Ax d =的Jacobi 及Gauss-Seidel 迭代法收敛的充分必要条件. 四. (10分) 试确定下求积公式中的待定参数,使求积公式的代数精确度尽量高,并指明所确定的求积公式具有的代数精确度 []20 002 '' ()()()()()h h f x dx f f h h f f h α??≈ ++-??? . 五. (10分) 已知非线性方程240x x +-=在014.x =附近有根，试构造一种收敛的迭代格式,并说明理由. 六. (10分) 求形如e (,)bx y a a b =为常数的经验公式,使它能和下表给出的数据相拟合 x １ ２ ３ ４ ５ ６ ７ ８ y 15.3 20.5 27.4 36.6 49.1 65.6 87.8 117.6 七. (10分) 分别用Euler 法和改进Euler 法求解下问题的数值解,取01.h =,计算过程保留四位小数. 00201',., (). y x y x y =+≤≤?? =? 八. (15分) 用下数据表构造不超过3次的插值多项式,建立导数型插值误差公式,并证明. 一、数制转换，以下数为带符号数，表达成字节或字的形式：(10分) （-327）10 = （）2 （70b6）16=（）10 （11010001）2 =（）10 （0101010101011001）2=（）10 （ 2572）10 =（）16 二、指出划线部分的寻址方式，并计算其物理地址：(10分) 已知: (CS)=2100H, (DS)=2400H, (ES)=2800H, (SS)=2600H, (BX)=0600H, (DI)=0200H, (SI)= 0300H, (BP)=0400H, BUF=1000H 1、MOV CL ES:[1500H] ；寻址方式：物理地址： 2、CMP SI, [DI] ；寻址方式：物理地址： 3、ADD AX, BUF [BP] [SI] ；寻址方式：物理地址： 4、CALL WORD PTR CS:[SI] ；寻址方式：物理地址： 5、LEA DX, [BX+SI] ；寻址方式：物理地址： 三、已知一程序数据段如下，请在右边表格中填写该数据段数据存储的形式。（12 分，未初始化的单元填写“xx”） DATA SEGMENT Array C=50H BUFFER DB 'B',0BH, B_BYTE LABEL BYTE DATA1 DW 0FFAAH ORG $+1 DATA2 DW B_BYTE DATA3 DW C DATA4 DB 3 DUP(20H),0FFH DATA ENDS 四、写出下列程序段的运行结果，并逐条注释每条指令。 1. 该程序段执行后，BX＝ .，为什么？(用图表示)（9分）ADDR DW PROC0，PROC1，PROC2，PROC3，PROC4，PROC5，PROC6 DW PROC7，PROC8，PROC9 LEA SI，ADDR ADD SI，2 MOV BX，[SI] INC SI INC SI PUSH BX MOV AX，[SI] INC SI INC SI PUSH AX PUSH BP MOV BP，SP MOV DX，[BP+2] CALL [SI] … PROC1 PROC MOV BX，1 RET PROC1 ENDP PROC2 PROC MOV BX，2 RET PROC2 ENDP PROC3 PROC MOV BX，3 RET PROC3 ENDP 余此类推… （9分）2. 下面这段程序的功能是。 一、选择题 1、从逻辑结构上可以把数据结构分为【 C 】。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从后向前依次后移【 B 】个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3、链表结构不具有下列【 B 】特点。 A、插入和删除无需移动元素 B、可随机访问链表中的任意元素 C、无需实现分配存储空间 D、所需空间与结点个数成正比。 4、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行【 C 】。 A、s->next = p->next; p->next = s; B、p->next = s->next; s->next = p; C、q->next = s; s->next = p; D、p->next = s; s->next = q; 5、一个栈的入栈序列是1，2，3，4，5，则栈不可能输出的序列是【C 】。 A、54321 B、45321 C、43512 D、12345 6、判断一个队列Q（元素最多为M个）为空的条件是【 C 】。 A、Q->rear – Q->front = M B、Q->rear – Q->front -1 ==M C、Q->rear == Q->front D、Q->rear + 1 == Q->front 7、在一个链队列中，假设f和r分别指向队首和队尾，则插入s所指结点的运算是【A 】。 A、r->next = s; r=s; B、f->next = s; f=s; C、s->next = r; r=s; D、s->next = f; f=s; 8、深度为5的二叉树至多有【 A 】个结点。 A、31 B、32 C、16 D、10 9、在一非空二叉树的中序遍历序列中，根结点的右边【A 】。 课程编号：MTH07034 北京理工大学2015-2016学年第二学期 2015级离散数学期末试题（A卷） 班级学号姓名成绩 1.选择题（共10题, 每题1分） 1)设p：我有时间，q：我去旅游，下面哪个命题可以符号化为p→q？( ) A. 除非我有时间，我才去旅游. B. 除非我去旅游，否则我没时间. C. 只有我有时间，我才去旅游. D. 我去旅游仅当我有时间. 2)设C(x)表示x是运动员，G(x)表示x是强壮的，则命题“没有运动员不是 强壮的”符号化为哪个公式？( ) A. ??x(C(x)∧?G(x)) B.??x(C(x)→?G(x)) C. ??x(C(x)∧?G(x)) D.??x(C(x)→?G(x)) 3)设F(x)表示x是火车，G(y)表示y是汽车，H(x,y)表示x比y快，则命题“有 的汽车比所有的火车快”符号化为下面哪个公式？( ) A. ?y(G(y)→?x(F(x)∧H(x,y))) B. ?y(G(y)∧?x(F(x)→H(y,x))) C. ?x?y(G(y)→(F(x)∧H(x,y))) D. ?y(G(y)→?x(F(x)→H(x,y))) 4)下列推理哪个是不正确的？( ) A. 前提：?p∨ (q→r), ?s∨p, q结论：s→r B. 前提：(p∨q)→ (r∧s), (s∨t)→u结论：p→u C. 前提：(p∧q) →r, r→s, ?s∧p结论：q D. 前提：p→ (q→r), p , q结论：r∨s 5)下面哪个命题公式是永真式？( ) A. (p∨q) →?r B. (q→p)∧q→p C. ?(?p∨q)∧q 课程编号：12000044 北京理工大学2009-2010学年第二学期 2008级计算机学院《数值分析》期末试卷A 卷 班级 学号 姓名 成绩 注意：① 答题方式为闭卷。 ② 可以使用计算器。 请将填空题和选择题的答案直接填在试卷上，计算题答在答题纸上。 一、 填空题（每空2分，共30分） 1. 设函数f (x )区间[a ，b]内有二阶连续导数，且f (a )f (b )<0, 当 时，用双点 弦截法产生的解序列收敛到方程f (x )=0的根。 2. n 个求积节点的插值型求积公式的代数精确度至少为______次，n 个求积节点的高斯 求积公式的代数精度为 。 3. 已知a =3.201，b =0.57是经过四舍五入后得到的近似值，则a ?b 有 位有 效数字，a +b 有 位有效数字。 4. 当x =1，-1，2时，对应的函数值分别为f (-1)=0，f (0)=2，f (4)=10，则f (x )的拉格朗 日插值多项式是 。 5. 设有矩阵?? ????-=4032A ，则‖A ‖1＝_______。 6. 要使...472135.420=的近似值的相对误差小于0.2%，至少要取 位有效数字。 7. 对任意初始向量0()X 和常数项N ，有迭代公式1()()k k x Mx N +=+产生的向量序列 {}() k X 收敛的充分必要条件是 。 8. 已知n=3时的牛顿-科特斯系数,8 3,81)3(1) 3(0 ==C C 则=) 4(2C ，=) 3(3C 。 9. 三次样条函数是在各个子区间上的 次多项式。 10. 用松弛法 (9.0=ω)解方程组??? ??=+-=++--=++3 1032202412 25322 321321x x x x x x x x x 的迭代公式是 。 北京理工大学汇编实验二报告 本科实验报告实验名称：算术运算类操作实验 一、实验要求和目的 1、了解汇编语言中的二进制、十六进制、十进制、BCD 码的表示形式； 2、掌握各类运算类指令对各状态标志位的影响及测试方法； 3、熟悉汇编语言二进制多字节加减法基本指令的使用方法； 4、熟悉无符号数和有符号数乘法和除法指令的使用； 5、掌握符号位扩展指令的使用。 6、掌握 BCD 码调整指令的使用方法 二、软硬件环境 1、硬件环境：计算机系统 windows； 2、软件环境：装有 MASM、DEBUG、LINK、等应用程序。 三、实验涉及的主要知识 1、加减法处理指令 主要有加法指令 ADD，带进位加法 ADC，减法指令 SUB，带进位减法指令 SBB。 2．乘除法指令和符号位扩展指令 主要有无符号数乘法指令MUL,带符号数乘 法指令IMUL,无符号数除法指令DIV,带符号数除法指令 IDIV,以及符号位从字节扩展到字的指令 CBW 和从字扩展到双字的指令 CWD。 3．BCD 码的调整指令 主要有非压缩的BCD 码加法调整指令DAA，压缩的 BCD 码减法调整指令 DAS，非压缩的 BCD 码加法调整指令 AAA，非压缩的 BCD 码减法调整指令 AAS，乘法的非压缩 BCD码调整指令 AAM，除法的非压缩 BCD 码调整指令 AAD。 8088/8086 指令系统提供了实现加、减、乘、除运算的上述基本指令，可对表 1 所示的数据类型进行数据运算。 表 1-2-1 数据类型数据运算表 四、实验内容与步骤 1、对于两组无符号数，087H 和 034H,0C2H 和5FH，试编程求这两组数的和差积商，并考虑计算结果对标志寄存器中状态标志位的影响：（1）实验流程 将一组 操作数 分别用 ADD,SUB,MUL,DIV 运算 （2）实验代码： DATAS SEGMENT BUF1 DB 087H BUF2 DB 034H BUF3 DB 4 DUP(?);此处输入数据段代码 DATAS ENDS 2019年北京理工大学889《数据结构》考试大纲 考试内容： 数据结构主要考查考生以下几个方面： 1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3.能够选择合适的数据结构和方法进行问题求解。 应掌握的具体内容为： 一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的概念 （二）二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 （三）树、森林 1.书的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 （四）树的应用 1.等价类问题 2.哈夫曼（Huffman）树和哈夫曼编码 四、图 （一）图的概念 （二）图的存储及基本操作 1.邻接矩阵法 2.邻接表法 （三）图的遍历 1.深度优先搜索 2.广度优先搜索 （四）图的基本应用及其复杂度分析 1.最小（代价）生成树 2.最短路径 3.拓扑排序 4.关键路径 五、查找 （一）查找的基本概念 （二）顺序查找法 （三）折半查找法 （四）B-树 （五）散列（Hash）表及其查找 （六）查找算法的分析及应用 六、内部排序 （一）排序的基本概念 （二）插入排序 1.直接插入排序 2.折半插入排序 （三）起泡排序（bubble sort） （四）简单选择排序 （五）希尔排序（shell sort） （六）快速排序 （七）堆排序 （八）二路归并排序（merge sort） （九）基数排序 （十）各种内部排序算法的比较 （十一）内部排序算法的应用 题型和分值 填空题20分、选择题30分、问答题70分、算法题30分 参考书目 数据结构（C语言版）严蔚敏吴伟民清华大学出版社 本科实验报告实验名称：子程序设计实验 实验五子程序设计实验（设计性实验） 一、实验要求和目的 1．熟悉汇编语言程序设计结构； 2．熟悉汇编语言子程序设计方法； 3．熟悉利用汇编语言子程序参数传递方法； 4．熟悉汇编语言字符串处理基本指令的使用方法； 5．掌握利用汇编语言实现字符串的输入输出程序设计方法； 6．掌握数制转换程序实现方法。 二、软硬件环境 1、硬件环境：计算机系统windows； 2、软件环境：装有MASM、DEBUG、LINK、等应用程序。 三、实验涉及的主要知识 A）子程序知识要点： 1、掌握子程序的定义语句；过 程名PROC [near/far] 过程 体 RET 过程名ENDP 2.子程序结构形式一个完整的子程序一般应包含下列内容: 1. ）子程序的说明部分 在设计了程序时,要建立子程序的文档说明,使用户能清楚此子程序的功能和调用方法. 说明时,应含如下内容: .子程序名:命名时要名中见意. .子程序的功能:说明子程序完成的任务; .子程序入口参数:说明子程序运行所需参数及存放位置; .子程序出口参数:说明子程序运行结果的参数及存放位置; .子程序所占用的寄存器和工作单元； .子程序调用示例； 2、）掌握子程序的调用与返回在汇编语言中，子程序的调用用CALL，返回用RET指令 来完成。 .段内调用与返回：调用子程序指令与子程序同在一个段内。因此只修改IP； .段间调用与返回：调用子程序与子程序分别在不同的段，因此在返回时，需同时修改CS：IP。 3．）子程序的现场保护与恢复保护现场：在子程序设计时，CPU内部寄存器内容的 保护和恢复。 一般利用堆栈实现现场保护和恢复的格式：过程名PROC [NEAR/FAR] PUSH AX PUSH BX . . PUSH DX . . . POP DX . . . POP AX RET 过程名ENDP 4.子程序的参数传递方法 1．寄存器传递参数这种方式是最基本的参数传递方式。 2．存储器单元传（变量）递参数 这种方法是在主程序调用子程序前，将入口参数存放到约定的存储单元中；子程序运行时到约定存储位置读取参数；子程序执行结束后将结果也放在约定存储单元中。 3．用堆栈传递参数 利用共享堆栈区，来传递参数是重要的的方法之一。 B）字符、字符串输入输出知识要点： 在实际应用中，经常需要从键盘输入数据并将结果等内容显示到屏幕上，方便程序控制及查看结果。汇编语言的数据输入和输出分成两类，一是单个字符数据的输入输出，一是字符串数据的输入输出。都可以通过DOS功能调用来实现，下面就分别介绍下用来实现数据输入输出的功能调用的使用方法。 1、单个字符输入 单个字符输入可以利用DOS的1号功能调用来完成，使用方法为： MOV AH,1 INT 21H 这两条语句执行后，光标会在屏幕上闪烁，等待输入数据，输入的数据以ASCII 码形式存储在AL寄存器中。 2、单个字符输出 单个字符输出可利用DOS2号功能调用来完成，使用方法为： MOV DL,’?’ MOV AH,2 课程编号：12000044 北京理工大学2010-2011学年第一学期 2009级计算机学院《数值分析》期末试卷A 卷 班级 学号 姓名 成绩 注意：① 答题方式为闭卷。 ② 可以使用计算器。 请将填空题和选择题的答案直接填在试卷上，计算题答在答题纸上。 一、 填空题 （2 0×2′） 1. 设x =0.231是精确值x *=0.229的近似值，则x 有 位有效数字。 2. 设 ?? ????-=? ?????-=32,1223X A ，‖A ‖∞＝___ ____，‖X ‖∞＝__ _____， ‖AX ‖∞≤____ ___ (注意：不计算‖AX ‖∞的值) 。 3. 非线性方程f (x )=0的迭代函数x =?(x )在有解区间满足 ，则使用该迭代函 数的迭代解法一定是局部收敛的。 4. 若f (x )=x 7－x 3＋1，则f [20,21,22,23,24,25,26,27]= ， f [20,21,22,23,24,25,26,27,28]= 。 5. 区间[a ,b ]上的三次样条插值函数S (x )在[a ,b ]上具有直到 阶的连续导数。 6. 当插值节点为等距分布时，若所求节点靠近首节点，应该选用等距节点下牛顿差商 公式的 （填写前插公式、后插公式或中心差分公式），若 所求节点靠近尾节点，应该选用等距节点下牛顿差商公式的 （填写前插公式、后插公式或中心差分公式）；如果要估计结果的舍入误差，应该选用插值公式中的 。 7. 拉格朗日插值公式中f (x i )的系数a i (x )的特点是：=∑=n i i x a 0)( ；所以当 系数a i (x )满足 ，计算时不会放大f (x i )的误差。 8. 要使 20的近似值的相对误差小于0.1%，至少要取 位有效数字。 9. 对任意初始向量X (0)及任意向量g ，线性方程组的迭代公式x (k +1)=Bx (k )+g (k =0,1,…)收 敛于方程组的精确解x *的充分必要条件是 。 10. 由下列数据所确定的插值多项式的次数最高是 。 《数据结构与算法统计》 实验报告 ——实验四 学院： 班级： 学号： 姓名： 一、实验目的 1、熟悉VC 环境，学会使用C 语言利用顺序表解决实际问题。 2、通过上机、编程调试，加强对线性表的理解和运用的能力。 3、锻炼动手编程，独立思考的能力。 二、实验内容 从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。 三、程序设计 1、概要设计 为了实现排序的功能，需要将输入的数字放入线性表中，进行进一步的排序操作。 (1)抽象数据类型： ADT SqList{ 数据对象：D={|,1,2,,,0}i i a a Elem Set i n n ∈=≥ 数据关系：R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作： InPut(SqList &L) 操作结果：构造一个线性表L 。 OutPut(SqList L) 初始条件：线性表L 已存在。 操作结果：按顺序在屏幕上输出L 的数据元素。 InsertSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行插入排序。 QuickSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行快速排序。 SelectSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行选择排序。 }ADT SqList ⑵主程序流程 由主程序首先调用InPut(L)函数创建顺序表，调用InsertSort(L)函数进行插入排序，调用OutPut(L)函数显示排序结果。 再由主程序首先调用InPut(L)函数创建顺序表，调用QuickSort(L)函数进行交换排序，调用OutPut(L)函数显示排序结果。 再由主程序首先调用InPut(L)函数创建顺序表，调用SelectSort(L)函数进行选择排序，调用OutPut(L)函数显示排序结果。 ⑶模块调用关系北京理工大学2012-2013学年第一学期工科数学分析期末试题(A卷)试题2012-2(A)
孙志忠北京理工大学偏微分方程数值解上机作业
北京理工大学汇编语言实验报告实验五 子程序设计实验
北理工889数据结构考纲
北京理工大学2017-2018学年工数上期末试题A及标准答案
北京理工大学数学专业数值计算方法Ⅰ期末试题2010级B卷(MTH17170)
北京理工大学汇编试题
北京理工大学2013级数据结构B试题(A卷)-答案
北京理工大学 离散数学I 期末测试
北京理工大学2008级数值分析试题及答案
北京理工大学汇编实验二报告
2019 北京理工大学 889《数据结构》 考试大纲
北京理工大学汇编实验五实验报告概要
北京理工大学 级数值分析试题及答案
北京理工大学数据结构实验报告4
- 北京理工大学2013级数据结构B试题(A卷)_答案
- 北京理工大学数据结构实验一报告
- 北理工数据结构作业2
- 北京理工大学数据结构查找课件
- 北京理工大学数据结构编程练习答案
- 北理工18秋学期《实用数据结构与算法》在线作业
- 北理工数据结构作业2
- 北京理工大学数据结构图课件
- 北京理工大学数据结构课程设计堆栈简易运算器
- 北京理工大学 数据结构 实验报告 实验二 简易计算器
- 2019 北京理工大学 889《数据结构》 考试大纲
- 2017年北京理工大学数据结构889模拟试题
- 数据结构考试题库(含参考答案)
- 数据结构考试题库(含参考答案)
- 北京理工大学2014-2015学年数据结构期末考试卷
- 北京理工大学《数据结构与算法设计》实验报告实验四
- 17秋北理工《数据结构与算法》在线作业满分答案
- 北京理工大学数据结构作业(全)
- 北京理工大学2004年_数据结构与程序设计_真题
- 19春北理工《数据结构与算法》在线作业答案