《计算机网络》期末考试样题 一．单项选择题(共15分，每题1分) 1.（）下列关于ADSL描述哪个是错误的 A. 实现了全双工通信，在两个方向上的传输速率可以不同 B. 使用基带传输方案，不需要像MODEM那样对数据进行调制， 所以ADSL一般比MODEM提供更高的通信速率 C. ADSL通信与普通电话机的语音通信使用完全相同的传输介质 D. ADSL仅仅是一个物理层标准 2.（）在有传输误码的数据信道上传输数据，下列哪种方法不能正确地 实现链路层的成帧处理 A. 字符计数法 B. 字节填充法 C. 比特填充法D．物理层编码违例法 3.（）如果用户计算机通过电话网接入因特网，则用户端必须具有： A. NAT网关 B. 以太网交换机 C. 集线器 D. 调制解调器 4.（）链路层协议采用选择重传滑动窗口协议，其中数据帧编号采用8 比特，发送窗口的最大值是： A．256 B. 255 C. 128 D. 127 5.（）以下哪个是正确的以太网地址 A. B. e0-2b-37 C. 00-30-2c-45-bc-2d D. 8000::126:376e:89bc:5c2e 6.（）IP路由器属于哪一层的互连设备 A．物理层 B. 链路层 C. 网络层 D. 传输层 7.（）下列哪种指标不是用来衡量网络服务质量(QoS)的主要指标 A．分组延迟时间B．到达抖动时间 C．分组生存时间 D. 分组传输带宽 8.（）某同学在校园网访问因特网，从该同学打开计算机电源到使用 命令ftp 连通文件服务器的过程中，哪个协议没有使用到 A．IP B．ICMP C．ARP D. DHCP 9.（）某主机的IP地址为子网掩码为，当这台主机在子网内发送广播 数据报时，IP数据报中的源地址为 A. B. 10.C. D. （）某校分给数学教研室的IP地址块为，分配给 外语教研室的地址块为，分配给物理教研室的地址块为。这三个地址块经过聚合后的地址块为： 11.A. B. D. （）关于TCP/IP协议特点的描述中，错误的是 A. IP提供尽力而为的服务，无法保证数据可靠到达 B. TCP是面向连接的传输协议 C. UDP是可靠的传输协议 D. TCP/IP协议可以运行于多种操作系统 12.（）在TCP/IP网络中，转发路由器对IP数据报进行分片的目的是： A. 提高路由器的转发效率
OFDM频率偏移估计算法分析 摘要 作为一种特殊的多载波调制技术，正交频分复用（OFDM，Orthogonal Frequency Division Multiplexing）因其高频谱利用率、高数据传输速率以及良好的抗多径干扰性能，广泛地应用于数字音视频广播、无线局域网等高速数据传输系统中。OFDM通信系统具备所有这些优势的前提是收发两端子载波均要保持良好的正交性，然而，在实际应用中，晶振的非理想因素以及移动通信中多径信道产生的多普勒频移将会造成OFDM系统发射机与接收机载波中心频率的偏移（CFO，Carrier Frequency Offset），而这将严重破坏子载波之间的正交性，因此OFDM系统接收机必须对载波频偏加以估计并对接收信号进行相应补偿以保证解调数据的准确性。通常，将这一操作称为载波频率同步，也可简称为频偏估计。由于OFDM系统对CFO非常敏感，微小的CFO就能造成系统误码性能的大幅下降，因此，频率同步技术是OFDM 系统的关键技术之一。 本论文首先回顾了OFDM技术发展的历史，然后从基本的OFDM系统的原理出发，阐述了OFDM系统中的同步问题。接着详细阐述了定时同步偏差和载波频率偏差对系统性能的影响。最后，对现有的频率同步技术（即，盲同步算法和非盲同步算法）进行了介绍且重点介绍了三种具有代表性的载波频偏估计算法：子载波间干扰（ICI，Intercarrier interference）自消除方法，高阶子载波间干扰（ICI）自消除方法和频率偏移盲估计方法，并通过仿真比较分析了它们在加性高斯白噪声信道和频率选择性信道下的估计性能。 关键词：正交频分复用；载波频率偏移；子载波间干扰；盲载波频偏估计；自消除
作业参考答案 一、（带头结点）多项式乘法C= A×B： void PoｌyAdd ( list &C,liｓｔR) ／／R为单个结 点 { p=C; while(（!p-＞ｎeｘt) &＆(p->nexｔ-＞eｘp>Ｒ->eｘp)) p=p－>ｎｅｘt； ｉf (（p->next) ｜｜(ｐ->neｘt->ｅｘp<Ｒ-＞eｘp)) {R－＞nｅxt=ｐ->ｎeｘｔ;p->neｘｔ=Ｒ;} ｅlse { ｐ-＞nｅxt－＞inf +=R->inｆ;delｅte R; if （！p－>neｘｔ-＞iｎｆ) { R=ｐ-＞nｅxt；p－>next=R->ｎext;deleｔe R; ｝ } } ｖoｉｄPｏlｙMul （lｉst A, lｉst B，lｉst &C ） ｛ C=new sｔｒuct nｏｄe; Ｃ-＞neｘt=ＮUＬL；q=B->next; Wｈｉｌe (q ） { p＝A->neｘｔ; whiｌｅ（p ) { ｒ= new struct node；r->ｅxｐ= p->ｅxp ＋ｑ－>exp； r-＞ｉnf ＝ｐ-＞inf* q－>iｎf; PolyAｄd(C，r）； p=p-＞next; ｝ q=q－>ｎext; ｝ } 二、梵塔的移动次数: 已知移动次数迭代公式为：M ( ｎ)= 2M (n－1 ) + 1 初值为: Ｍ( 0 ) ＝0 则：M （n）＝ 2 （2M
（n-2 ) + 1) + 1 =4M( n-2 )+ 3 = 8Ｍ(n－3 )+ 7 =２i M ( n-i ) + 2i– 1 若n＝ｉ，则Ｍ（n-ｎ) ＝0,故：M ( n ) =2ｎM( ｎ-n）+2n–1 =2n– 1 所以,梵塔的移动次数为2ｎ– 1次。 三、简化的背包问题： ｖoid Pacｋ( int ｍ, int i, ｉnt t ）// 初始值为:１１t ｛ for (k=i; k<＝ｎ; k＋＋) { soｌutiｏｎ[m] = ｗeighｔ[k]; if( t == weigｈｔ[k]) ｛ for ( j=1; ｊ<=m；j+＋) cout<＜ｓolutｉon［j]；coｕt<
北京邮电大学2019—2020学年第二学期 《计算机算法与数学模型（下）》期末考试试题 班级：学号（学校统一10位）：姓名： 说明：1）本次考试采用开卷方式，答卷时间为2周（2020年06月04日-06月14日），请按时（2020年06月14日之前，逾时将作无效化处理）交卷；2）本课程的考试是一学期课程学习结束的一次综合复习，因此在答题时务必独立完成，除了查阅有关资料外，请避免同学间相互抄袭，如发现雷同答卷，一并作废！3）答卷统一要求以电子文档报告形式完成，建议采用word或wps等较为常用的编辑软件处理（当然，由于实验条件的局限，也可以手写拍照）。文档版式统一要求A4纸型，正文小4号字体、单倍行距。请在答卷卷首写清姓名、班级、学号（学校统一10位编号；特别，若采用推荐字处理工具，可以选择基于本试题文档跟题作答）等。4）凡涉及计算编程的题目，将程序打包、压缩、以“数学模型”+“本人学号”+“姓名”命名，如“数学模型2015212999丁一”，然后发到ftp://10.105.221.24 (用户名：homework,密码：homework) 5) 若由于印刷原因造成试题不清晰，请从http://10.105.221.24/sxjm下载试题的电子文档。 一．模型解释： 1.设G(V,E)为一n-阶（n≥2任意自然数）竞赛图，V={v j|j=1..n}为顶点集，E为边集，构造 ???????? |i=1..n}∪{v i v n+1 ????????????? |i= (n+2) -阶竞赛图G?(V?,E?)，其中V?=V∪{v0,v n+1}，E?=E∪{v0v i ?????????????? }(竞赛图及完全路径的概念请你查阅有关资料). 试着说明：1）若以A?表示 1..n}∪{v n+1v0 G?(V?,E?)的邻接矩阵，试着说明A?的模最大的特征值λ?为一正单根，且其关于特征值λ?特征向量的所有分量具有相同的正负号；2）这里不妨以d?表示A?关于特征值λ?的符合归一化条件的特征向量，试着说明以d?作为V(V?)的实力进行竞赛图排名的合理性及其优点。 2.一个合理的红绿灯调节方案应当使为每一车流分配的有效通行时间与它的实际流量相适应，简 言之，那些相对繁忙的车流应当有更为充足的通行时间，我们考虑一个具有六车流十字路口的红绿灯调节问题， 不妨设λi(i=1..6)表示六个车流在单位时间内的车流量，则得如下的线性规划模型： Maxλ1d1+λ2d1+λ3d2+λ4(d2+d3)+λ5(d3+d4)+λ6d4 s.t.d1+d2+d3+d4=60 d1,d2,d2+d3,d3+d4,d4≥10,d3≥0 其中d i(i=1..4)为决策变量，d1,d1,d2,d2+d3,d3+d4,d4表示a..f六个车流在一个红绿灯调节周期（60秒）内的各车流的有效通行时间。试着分析该（类）模型的主要缺陷，你能给出某种改进的建模方案吗？
OFDM 基本原理概述 设OFDM 信号的符号周期为T ，当N 个子载波的频率之间的最小间 N 表示子信道的个数，T 表示OFDM 符号宽度，i d (i =0,1,…,N-1)是分配给每个子信道的数据符号，0f 是第0个子载波载波频率，则从t=s t 开始的OFDM 符号可以表示为 100exp 2()(),()0,N i s s s i i d j f t t t t t T s t T π-=??? +-≤≤+???=????? ∑其它 它的等效基带信号是 1 ()exp 2(),N i s s s i i s t d j t t t t t T T π-=?? =-≤≤+????∑ 式中实部和虚部分别对应于OFDM 符号的同相和正交分量，是集中可以分别与相应子载波 的余弦分量和正弦分量相乘，构成最终的子信道信号和合成的OFDM 符号。
信号解调，接收第k 路子载波信号 k d 与第k 路解调载波exp[2()]s j t t T π--相乘，得到的结果在符号持续时间T 内进行积分，即可获得相应的发送信号k d 1^ 0101exp 2()exp 2()1exp 2()s s s s N t T k s i s t i N t T i s t i k k i d j t t d j t t dt T T T i k d j t t dt T T d πππ-+=-+=????=---???????? -??=-????=∑?∑? OFDM 复等效基带信号可以采用离散傅立叶逆变化(IFFT)方法来实现。令s t =0，t=/kT N (k=0,1,….,N-1)， 即对s(t)以 T/N 的速率进行抽样可以得到 1 2()(/)exp N i i ki s k s kT N d j N π-=?? == ???∑ 01k N ≤≤- 式中s(k)即为i d 的IDFT 运算。接收端为恢复出原始的数据符号i d ，可以对s(k)进行DFT 运算，得到1 2()exp N i i ki d s k j N π-=? ? = - ?? ? ∑ 01i N ≤≤- OFDM 文章,时间连续系统模型时，发射机发射的第K 个载波波形时,
北邮算法与数据结构习题参考答案
作业参考答案 一、（带头结点）多项式乘法 C = A×B： void PolyAdd ( list &C, list R) // R 为单个结点 { p=C; while ((！p->next) && (p->next->exp>R->exp)) p=p->next; if ((p->next) || (p->next->exp
大数据技术 1.什么是数据挖掘，什么是机器学习： 什么是机器学习 关注的问题：计算机程序如何随着经验积累自动提高性能； 研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能； 通过输入和输出，来训练一个模型。 2.大数据分析系统层次结构：应用层、算法层、系统软件层、基础设施层 3.传统的机器学习流程 预处理-》特征提取-》特征选择-》再到推理-》预测或者识别。 手工地选取特征是一件非常费力、启发式（需要专业知识）的方法，如果数据被很好的表达成了特征，通常线性模型就能达到满意的精度。 4.大数据分析的主要思想方法 4.1三个思维上的转变 关注全集（不是随机样本而是全体数据）：面临大规模数据时，依赖于采样分析；统计学习的目的——用尽可能少的数据来证实尽可能重大的发现；大数据是指不用随机分析这样的捷径，而是采用大部分或全体数据。 关注概率（不是精确性而是概率）：大数据的简单算法比小数据的复杂算法更有效 关注关系（不是因果关系而是相关关系）：建立在相关关系分析法基础上的预测是大数据的核心，相关关系的核心是量化两个数据值之间的数理关系，关联物是预测的关键。 4.2数据创新的思维方式 可量化是数据的核心特征（将所有可能与不可能的信息数据化）；挖掘数据潜在的价值是数据创新的核心；三类最有价值的信息：位置信息、信令信息以及网管和日志。 数据混搭为创造新应用提供了重要支持。 数据坟墓：提供数据服务，其他人都比我聪明！ 数据废气：是用户在线交互的副产品，包括了浏览的页面，停留了多久，鼠标光标停留的位置、输入的信息。 4.3大数据分析的要素 大数据“价值链”构成：数据、技术与需求（思维）；数据的价值在于正确的解读。
北京邮电大学 2015-2016学年第1学期实验报告 课程名称：数据仓库与数据挖掘 实验名称：文本的分类 实验完成人： 姓名：学号： 日期： 2015 年 12 月
实验一：文本的分类 1.实验目的 1. 了解一些数据挖掘的常用算法，掌握部分算法； 2. 掌握数据预处理的方法，对训练集数据进行预处理； 3. 利用学习的文本分类器，对未知文本进行分类判别； 4. 掌握评价分类器性能的评估方法。 2.实验分工 数据准备、预处理、LDA主题模型特征提取实现、SVM算法都由范树全独立完成。 3.实验环境 ●操作系统：win7 64bit 、Ubuntu-14.04-trusty ●开发环境：java IDE eclipse 、Python IDLE 4.主要设计思想 4.1实验工具介绍 1.Scrapy 0.25 所谓网络爬虫，就是一个抓取特定网站网页的HTML数据的程序。不过由于一个网站的网页很多，而我们又不可能事先知道所有网页的URL地址，所以，如何保证我们抓取到了网站的所有HTML页面就是一个有待考究的问题了。一般的方法是，定义一个入口页面，然后一般一个页面会有其他页面的URL，于是从当前页面获取到这些URL加入到爬虫的抓取队列中，然后进入到新页面后再递归的进行上述的操作，其实说来就跟深度遍历或广度遍历一样。 Scrapy是一个基于Twisted，纯Python实现的爬虫框架，用户只需要定制开发几个模块就可以轻松的实现一个爬虫，用来抓取网页内容以及各种图片，非常之方便。Scrapy 使用Twisted这个异步网络库来处理网络通讯，架构清晰，并且包含了各种中间件接口，可以灵活的完成各种需求。 2.JGibbLDA-v.1.0 jGibbLDA是java版本的LDA实现，它使用Gibbs采样来进行快速参数估计和推断。LDA 是一种由基于概率模型的聚类算法。该算法能够对训练数据中的关键项集之于类簇的概率参数拟合模型，进而利用该参数模型实施聚类和分类等操作。 3.ICTCLAS50 中科院计算技术研究所在多年研究基础上，耗时一年研制出了基于多层隐码模型的汉语词法分析系统ICTCLAS，该系统有中文分词，词性标注，未登录次识别等功能。 4.libSVM-3.20 libSVM是台湾大学林智仁教授等开发设计的一个简单、易用和快速有效的SVM模式识
作业参考答案 一、（带头结点）多项式乘法 C = A×B： void PolyAdd ( list &C, list R) // R 为单个结点 { p=C; while ((！p->next) && (p->next->exp>R->exp)) p=p->next; if ((p->next) || (p->next->exp
= 8M ( n-3 ) + 7 = 2i M ( n-i ) + 2i– 1 若n=i ,则M ( n-n ) = 0,故：M ( n ) = 2n M ( n-n ) + 2n– 1 = 2n– 1 所以，梵塔的移动次数为2n– 1次。 三、简化的背包问题： void Pack ( int m, int i, int t ) // 初始值为: 1 1 t { for ( k=i; k<=n; k++ ) { solution[m] = weight[k]; if ( t == weight[k] ) { for ( j=1; j<=m; j++ ) cout<
算法设计与分析第三章程序作业 源程序代码 1.最长公共子序列 #include
#define N 1000 int e[N][N],f[N][N]; void LCSLength(int m,int n,char *x,char *y,int c[][N],int b[][N])//构造数组b[i][j] { int i,j; for (i=1; i<=m;i++) c[i][0]=0; //初始化, Y[j]为空时 for (i=1;i<=n;i++) c[0][i]=0; //初始化，X[i]为空时 for (i=1;i<=m;i++) //两重循环，自下而上，// 计算子问题{X(i), Y(j)} for (j=1;j<=n;j++){ if(x[i]==y[j]) { //情况1 c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } else if(c[i-1][j]>=c[i][j-1])
{ //情况2 c[i][j]=c[i-1][j]; b[i][j]=2; } else //情况3 { c[i][j]=c[i][j-1]; b[i][j]=3; } } } void LCS(int i,int j,char *x,int b[][N]) { if (i==0||j==0) return; if (b[i][j]==1) { LCS(i-1,j-1,x,b); printf("%c",x[i]); /*第1种情况下，X(i)和Y(j)的最长公共子序列由X(i-1)和Y(j-1)的解LCS(i-1, j-1, x, b)，加上位于最后的X[i] 组成*/
一、多项选择题（共10道小题，共100.0分） 1. 关于银行家算法，下面的说法哪些是对的？ A. 银行家算法是用来检查系统中是否有死锁发生的算法 B. 银行家算法是系统用来分配资源的算法 C. 银行家算法可以预防死锁的发生 D. 银行家算法并不干预系统分配资源 2. 采用预先静态资源分配法，主要是打破了哪些死锁条件？ A. 互斥条件 B. 不可抢占条件 C. 部分分配条件 D. 循环等待条件 3. 一个作业的进程处于阻塞状态，这时该作业处于什么状态？ A. 提交状态 B. 后备状态 C. 运行状态 D. 完成状态
4. 在短期繁重负载下，应将哪个进程暂时挂起的问题是由（）调度程序负责 A. 长期 B. 中期 C. 短期 D. 都不是 5. 多处理器系统分类中，对称式多处理器系统符合哪些特征？ A. 紧密耦合 B. 共享内存 C. 在一台处理器上执行操作系统，其他处理器执行应用进程 D. 各个处理器的地位都完全相同 6. 现在的进程通信通常是采用间接通信方式。在这种方式中，端口代表什么 意义？ A. 计算机终端在网络中的位置 B. 计算机中的不同的网卡 C. 服务器 D. 进程
7. 信号量机制可以总结为三个要素，应该是哪些？ A. 一个整型变量 B. 原语 C. Wait操作 D. Signal操作 8. 在下列的互斥方法中，不能用于多处理器系统的的方法有： A. 软件互斥方法 B. 中断屏蔽方式 C. 硬件指令方式 D. 信号量机制 9. 一个信号量被定义为一个（） A. 字符 B. 整数 C. 任意型变量 D. 整型变量
10. “异步事件能按照要求的时序进行，以达到合作进程间协调一致的工作” 既是所谓（）。 A. 互斥 B. 并行性 C. 同步 D. 临界段 11.
北京邮电大学操作系统实验实验报告 班号：姓名：学号： 实验日期：2010年12月16日 实验名称：页面替换算法的实现 一、实验目的 （1）了解内存分页管理策略 （2）掌握一般常用的调度算法 二、实验内容 写个程序来实现本章中介绍的FIFO和LRU算法。首先，产生一个随机的页面引用序列，页面数从0到9。将这个序列应用到每个算法并记录发生的页错误次数。实现这个算法时，要将页帧的数量设为可变（从1到7）。假设使用请求调页 三、项目要求及分析 项目要求： （1）采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响。 （2）实现对FIFO，LRU算法的模拟 分析： 先进先出(FIFO)页面置换算法： 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。 LRU置换算法： 选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间access_time,，当须淘汰一个页面时，选择现有页面中其access_time值最大的，即最近最久未使用的页面予以淘汰。 四、具体实现 4.1数据结构定义 此次工程包含main.cpp,lru.h,fifo.h. 在lru.h（主要是void lru(int memorysize,int random_size,int
*random)函数，用来实现LRU算法）中： 1．struct memory{ int pagenumber; int access_time; }; typedef memory MEMORY; MEMORY *MEMORYTable; 以上均为全局变量 此结构表示内存的一个帧。Pagenumber指的是这个帧所对应的页号，如果此帧空闲（即没有任何页调入），则值为-1；此帧对应页access_time是指进入内存的时间。在LRU算法的时候，要用到此结构定义一个数组。数组的大小为帧的个数。 2．int page_fault_time：局部变量，记录缺页的次数，初始值为0； 3. int value:当前所有帧的对应页的access_time最大值。这个值越大，表明这个帧所对应的页最近越少被访问到 在fifo.h（主要有void FIFO(int page_size,int requestsize,int memorysize,int *random)函数，实现FIFO算法）中： 1.struct page{ int pagenumber; int memorynumber; int IsInmemory; }; typedef page PAGE; PAGE *PageTable; 以上均为全局变量。 此结构表示一个页。Pagenumber是页号，memorynumber是这个页所对应的帧号，初始的时候每个页的memorynumber都为-1，IsInmemory表示这个页是否在内存中，如果在，值为1；不在，值为0 2.int *memory：局部变量，模拟内存。数组大小为帧的个数 3.int PageFalseTime：局部变量，记录缺页的次数 4.int FirstIn：记录最先进入内存的页 5.int FullNumber //记录物理块（即帧）被占用的个数 6．int index = 0;//随机访问串数组的起始下标 在main.cpp中： 1.int size_random:局部变量，随机访问串的大小
《算法设计与分析》实验与复习题 第一章引论 习题1 写一个通用方法用于判定给定数组是否已排好序。 算法实例： Algorithm compare(a,n) Begin J=1; While (j
习题2-1 求下列函数的渐进表达式： 3n 2+10n ; n 2/10+2n ; 21+1/n ; log n 3; 10 log3n 。 解答： 3n 2+10n=O （n 2）， n 2/10+2n =O （2n ）， 21+1/n=O （1）， log n 3=O （log n ），10 log3n =O （n ）。 习题2-2 说明O (1)和 O (2)的区别。 习题2-3 照渐进阶从低到高的顺序排列以下表达式：!n ， 3/22,2,20,3,log ,4n n n n n 。 解答：照渐进阶从低到高的顺序为：!n 、 3n 、 24n 、23 n 、20n 、log n 、2 习题2-4 （1） 假设某算法在输入规模为n 时的计算时间为n n T 23)(?=。在某台计算机 上实现并完成该算法的时间为t 秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t 秒内能解输入规模为多大的问题？ （2） 若上述算法的计算时间改进为2)(n n T =，其余条件不变，则在新机器上用 t 秒时间能解输入规模多大的问题？ （3） 若上述算法的计算时间进一步改进为8)(=n T ,其余条件不变，那么在新机 器上用t 秒时间能解输入规模多大的问题？ 解答： （1） 设新机器用同一算法在t 秒内能解输入规模为1n 的问题。因此有 64/23231n n t ?=?=，解得61+=n n 。 （2） n n n n 8641221==>=。 （3） 由于=)(n T 常数，因此算法可解任意规模的问题。 习题2-5 XYZ 公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC 公司同类产品的100倍。对于计算复杂性分别为n ，2n ，3n 和!n 的各算法，
第三次算法作业（贪心算法） 姓名：吴迪 班级：08211312 学号：08211488 班内序号15 摘要：本文为完成作业problem1，problem3，problem4，problem5的四道贪心算法题。 备注：所有后缀为_ex的可执行文件为文件输入输出模式的程序，比如problem1_ex.exe （所有算法实现代码承诺为本人自己编写并且截图为实际有效截图，所有程序均通过Dev-C++编译器实际测试可以运行） problem 1 特殊的01背包（原算法分析题4-3） 问题描述：01背包是在N件物品取出若干件放在空间为C的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn，并取得最大价值。普通的01背包中物品的重量和价值没有明确的关系，这里定义一种特殊的01背包：向背包中放入的物品的价值和体积成反比，也就是价值越高，体积越小，注意这里物品价值和体积的乘积并不是固定值。例如：如下的物品满足这
个“特殊的01背包”,5件物品: 物品1,价值 v=6,体积w=20 物品2,价值 v=1,体积w=60 物品3,价值 v=20,体积w=3 物品4,价值 v=15,体积w=15 物品5,价值 v=99,体积w=1 假如我有一个容量为c的背包,c=20，那么选择物品3、4、5可以获得最大价值134。 输入：首先是一个整数t,代表测试数据的组数。每组测试数据首先是两个正整数n和c，n 代表物品的个数，c代表背包的最大容积。然后有n行整数，每行有两个整数，分别代表物品的价值v和体积w。t的范围是(1-100),n的范围是(1-100000),c、v、w的范围不超过四字节的int型。 输出：首先输出测试数据的组号，例如第一组的组号为“Case 1:”，占一行。然后是一个整数，代表可以取得的最大价值，占一行。 Sample Input: 5 5 20 6 20 1 60 20 3 15 15 99 1 1 1 100 100 5 10 92 17 101 10 93 18 109 3 87 26 10 22 96 13 96 18 89 17 106 1 71 40 86 27 83 31 78 31 106 7
北京邮电大学2019—2020学年第一学期 《计算机算法与数学模型<上>》期末考试试题 说明：1）本次考试采用开卷方式，答卷时间为一周（2019年12月19日-26日），请按时（2019年12月26日数学模型课课间，逾时不候）交卷；2）本课程的考试是一学期课程学习结束的一次综合复习，因此在答题时务必独立完成，除了查阅有关资料外，请避免同学间相互抄袭，如发现雷同答卷，一并作废！3）答题纸务必采用学校提供的标准答题纸，否则将被视为无效。请在答卷卷首写清姓名、班级、学号（学校统一10位编号）等。4）凡涉及计算编程的题目，将程序打包、压缩、以“数学模型”+“本人学号”+“姓名”命名 一、综合建模——电动汽车与能源战略 随着我国经济的快速发展，我们成为世界上的能源消耗与进口大国，比如原油，中国已经连续多年是世界上最大的净进口国。 如果就某种战略物资一国对另外一国形成严重依赖，就会在物资交易价格形成与国家安全方面给物资进口国造成忧患。当然针对某种物资的国际交易，进口国家与出口国家均是两个利益群体，任何两个不同的国家之间通常也是既有合作又有竞争的某种复杂关系。 同时，一种特定资源（原油）尽管重要，但其效用可能通过其它物资（煤炭、核与其它可再生能源）替代或者部分替代，这种可替代性物资一国的储备与进出口结构是有很大弹性从而具有动态调整的空间。 1）请查阅资料，获取中国、美国近四十年原油的生产量、消耗量、进出口量等年度数据；若有可能，尝试给出未来十年相应数据的预测量； 2）查阅资料，获取我国机动车数量与耗能的历史数据，建模分析我国发展电动车会对我国能源消耗的图谱（不同能源消耗的数量、比例构成）带来何种改变？ 3）考虑一种战略物资供需关系对交易价格的影响，建模分析我国电动汽车的设定占有率分别为10%、50%、90%的取值下，会为我国在原油进口方面带来多大程度的比较受益（进口成本节约）？ 二、模型解释 1. 我们对文章的观点不予置评，而对其引述的有关“贫困陷阱”的概念模型感兴趣——文章提供了两个不同的模型：
●(2分)为解决计算机和打印机速度不匹配问题, 通常设置一个打印数据缓冲区, 主机将 要输出的数据依次写入缓冲区, 而打印机依次从该缓冲区中取出数据. 该缓冲区的逻辑结构应该是? A. 栈 B. 队列 C. 树 D. 图 ●(2分)设栈S和队列Q 的初始状态均为空, 元素abcdefg 依次进入栈S. 若每个元素出 栈后立即进入队列Q. 且7个元素出对的顺序是bdcfeag, 则栈S 的容量至少是? A . 1 B: 2 C. 3 D, 4 ●(2分)已知完全二叉树的第六层(根节点视为第一次)有8个节点. 则此完全二叉树节点个 数最多为 A. 39 B. 52 C. 111 D. 119 ●将森林转换为对应的二叉树. 若在二叉树中节点u 是节点v 的父节点的父节点. 则在 原来的森林中, u与v 的可能关系为 甲) 父子关系. 乙)兄弟关系丙) u 的父节点与v 的父节点是兄弟关系 A. 只有甲 B. 甲和乙 C. 甲和丙 D 甲乙丙 ●下面关于无向连通图特性的叙述中, 正确的是: 甲) 所有定点度数之和为偶数. 乙) 边数大于顶点个数减1 丙) 至少有一个顶点的度为1. A. 只有甲 B.只有乙 C.甲和乙 D.甲和丙 参考答案: 1)B 2)C 3)D 4)B 5)C 6)B 7) A
●下面叙述中, 不符合m阶B树定义要求的是: A. 根节点最多有m棵子树 B.所有叶节点都在同一层上. C.各节点内关键字均升序或降序排列 D. 叶节点之间通过指针链接. ●已知关键字序列5, 8, 12, 19, 28, 20, 15, 22 为极小堆(小根堆, 最小堆). 添加关键字3 调整后得到的极小堆是: A. 3,5,12,8,28,20,15,22,19 B. 3,5,12,19,20,15,22,8,28 C. 3,8,12,5,20,15,22,28,19 D. 3,12,5,8,28,20,15,22,19 ●若数据元素序列11,12,13,7,8,9,23,4,5 是采用下列排序算法之一得到的第二趟排序后的 结果, 则该排序算法只能是: A. 冒泡排序 B. 插入排序 C.选择排序 D.二路归并排序 ●如元素abcdef 依次进栈, 允许进栈出栈操作交替进行, 但不允许连续三次退栈. 则不 可能得到的出栈序列为: A. dcebfa B. cbdaef C.bcaefd D. afedcb ●某队列允许在其两端进行入队操作, 但仅允许在一端进行出队操作. 若元素abcde 依 次入队后再进行出队操作, 则不可能的出队序列为 A. bacde B. dbace C.dbcae D. ecbad ● 参考答案: 1)D 2)A 3)B 4) D 5)C
课本第九章21题实验 ytinrete 1．实验目的： 学习页面置换算法 2．实验内容 Write a program that implements the FIFO and LRU page-replacementalgorithms presented in this chapter. First, generate a random pagereferencestring where page numbers range from 0..9. Apply the randompage-reference string to each algorithm and record the numberof page faults incurred by each algorithm. Implement the replacementalgorithms such that the number of page frames can vary from 1..7.Assume that demand paging is used. 写一个程序来实现本章中介绍的FIFO和LRU页置换算法。首先产生一个随机的页面引用序列，页面数从0~9。将这个序列应用到每个算法并记录发生的页错误的次数。实现这个算法时，要将页帧的数量设为可变（从1~7）。假设使用请求调页。 3．设计说明 FIFO算法： 每次请求先查找是否有空块，有则替换，并标记为最晚到达，若没有则从标记中寻找最新到达的块，替换，并更新标记表。标记数字越小，到达时间最早。 LRU算法： 每次请求先查找是否有空块，有则替换，并标记为最近使用时间最短者，若没有则从标记中寻找最近使用时间最长者，替换，并更新标记表。标记数字越小，最近使用频率越低。 4．实验环境 windows7 ultimate x64 with sp1 Dev-c++
信息与通信工程学院通信网理论基础实验报告 班级： 姓名： 学号： 序号：
实验四 Floyd 算法 一、实验目的 Floyd 算法通过图的权值矩阵求出任意两点间的最短距离矩阵和路由矩阵。优点是容易理解，可以算出任意两个节点之间最短距离的算法，且程序容易实现，缺点是复杂度达到 ，不适合计算大量数据。 本次实验要求利用MATLAB 实现Floyd 算法，可对输入的邻接距离矩阵计算图中任意两点间的最短距离矩阵和路由矩阵，且能查询任意两点间的最短距离和路由。 二、 实验原理 Floyd 算法可描述如下： 给定图G 及其边(,)i j 的权,(1,1)i j w i n j n ≤≤≤≤ F0：初始化距离矩阵(0)W 和路由矩阵(0)R 。其中： (0) 0ij ij ij ij w e E w e E i j ∈?? =∞???=? 若（有边） 若（无边） 若(对角线元素) (0)(0) w 0,ij ij j r ?≠∞=?? 若 其它 F1：已求得(-1)k W 和(-1)k R ，依据下面的迭代求() k W 和() k R ()(1)(1)(-1) ,,,,min(,) k k k k i j i j i k k j w w w w --=+ (1)()(1) ,,,() ,(1) ()(1) ,,,k k k i k i j i j k i j k k k i j i j i j r w w r r w w ----?，终止。
三、 实验内容 用MATLAB 仿真工具实现Floyd 算法：给定图G 及其边(,)i j 的权,(1,1)i j w i n j n ≤≤≤≤，求出其各个端点之间的最小距离以及路由。 1、分别用以下两个初始距离矩阵表示的图进行算法验证： (0) 0 100 100 1.2 9.2 100 0.5100 0 100 5 100 3.1 2100 100 0 100 100 4 1.51.2 5 100 0 6.7 100 1009.2 100 100 6.7 0 15.6 100100 3.1 4 100 15.6 0 1000.5 2 1.5 100 100 100 0]W ?? ?? ?? ?? ??=???? ?? ?? ?? ?? (0)0 0.5 2 1.5 100 100 1000.5 0 100 100 1.2 9.2 1002 100 0 100 5 100 3.11.5 100 100 0 100 100 4100 1.2 5 100 0 6.7 100100 9.2 100 100 6.7 0 15.6100 100 3.1 4 100 15.6 0W ????????? ?=?? ?????????? 分别求出(7)W 和(7) R 。 2、根据最短路由矩阵查询任意两点间的最短距离和路由 （1）最短距离可以从最短距离矩阵的()j i ,ω中直接得出； （2） 相应的路由则可以通过在路由矩阵中查找得出。由于该程序中使用的是前向矩阵，因此在查找的过程中，路由矩阵中r(i,j)对应的值为Vi 到Vj 路由上的下一个端点，这样再代入r(r(i,j),j)，可得到下下个端点，由此不断循环下去，即可找到最终的路由。 （3）对图1，分别以端点对V4和V6, V3和V4为例，求其最短距离和路由；对图2，分别以端点对V1和V7，V3和V5，V1和V6为例，求其最短距离和路由。 3、输入一邻接权值矩阵，求解最短距离和路由矩阵，及某些点间的最短路径。 4、扩展的实验内容（选作部分） （1）实现Floyd 算法的回溯路由矩阵； （2）探讨可降低算法复杂度的算法。