下载文档原格式
2012年计算机专业考研真题——OS一、试题23. 下列选项中，不可能在用户态发生的事件是（）。
A. 系统调用B. 外部中断C. 进程切换D. 缺页24. 中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（）。
A. 程序计数器B. 程序状态字寄存器C. 通用数据寄存器D. 通用地址寄存器25. 下列关于虚拟存储的叙述中，正确的是（）。
A. 虚拟存储只能基于连续分配技术B. 虚拟存储只能基于非连续分配技术C. 虚拟存储容量只受外存容量的限制D. 虚拟存储容量只受内存容量的限制26. 操作系统的I/O子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。
其合理的层次组织排列顺序是（）。
A. 用户级I/O软件、设备无关软件、设备驱动程序、中断处理程序B. 用户级I/O软件、设备无关软件、中断处理程序、设备驱动程序C. 用户级I/O软件、设备驱动程序、设备无关软件、中断处理程序D. 用户级I/O软件、中断处理程序、设备无关软件、设备驱动程序27. 假设5个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3，这些资源总数分别为18、6、。
A. P0, P1, P2, P3, P4B. P1, P0, P3, P4, P2C. P2, P1, P0, P3, P4D. P3, P4, P2, P1, P028. 若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（）。
Ⅰ. 若该文件的数据不在内存，则该进程进入睡眠等待状态Ⅱ. 请求read系统调用会导致CPU从用户态切换到核心态Ⅲ. read系统调用的参数应包含文件的名称A. 仅Ⅰ、ⅡB. 仅ⅡC. 仅ⅢD. Ⅰ、Ⅱ和Ⅲ29. 一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms到达。
它们的计算和I/O 操作顺序如下：P1：计算60ms，I/O80ms，计算20msP2：计算120ms，I/O40ms，计算40ms若不考虑调度和切换时间，则完成两个作业需要的时间最少是（）。
样卷一、选择（每题1分，共20分）1、文件系统为用户提供了（）功能，使得用户能透明地存储访问文件。
A、按名存取B、密码存取C、路径存取D、命令调用2、位示图方法可用于 ( )A、磁盘空间的管理B、磁盘的驱动调度C、文件目录的查找D、页式存贮管理的页面调度3、在一个可变式分区管理中，最坏适应分配算法宜将空闲区表中的空闲区按（）的次序排列A、地址递增B、地址递减C、长度递增D、长度递减4、进程从运行状态到等待状态可能是由于（）A、进程调度程序的调度B、现运行进程时间片用完C、现运行进程执行了 P操作D、现运行进程执行了 V操作5、资源的静态分配算法在解决死锁问题中是用于（）A、预防死锁B、避免死锁C、检测死锁D、解除死锁6、进程控制块是描述进程状态和特性的数据结构，一个进程（）A、可以有多个进程控制块B、可以和其他进程共用一个进程控制块C、可以没有进程控制块D、只能有惟一的进程控制块7、在 UNIX 系统中，设备作为（）存在，除占据相应的节点位置外，并不占据实际的物理存储块，设备可采用文件的读写和保护方法。
A、记录文件B、普通文件C、设备文件D、系统文件8、由字符序列组成，文件内的信息不再划分结构，这是指（）。
A、流式文件B、记录式文件C、顺序文件D、有序文件9、对于给定的信号量 s ，等待操作 wait （ s ）（又称 P 操作）定义为： if s>0 then ( ) eles 挂起调用的进程。
A、s:=0B、s:=s+1C、s:=s-1D、s:=110、户程序通过系统调用 create来创建一新文件时，在执行create()的过程中，处理机程运行在（）下。
A、系统态B、用户态C、系统态或用户态D、目态11、设有12个同类资源可供四个进程共享，资源分配情况如表：进程已占用资源数最大需求P1 2 4P2 3 6P3 4 7P4 1 4目前剩余资源数为2。
当进程P1，P2，P3，P4又都相继提出申请要求，为使系统不致死锁，应满足( )的要求。
警综平台执法办案题1. 在“案事件管理?审批/监督?执法审批”页面中，系统默认显示的是一段时间内未审批的案件（文书），描述正确的是：()A. 系统默认显示的是一天内未审批的案件（文书）B. 系统默认显示的是三天内未审批的案件（文书）C. 系统默认显示的是七天内未审批的案件（文书）D. 系统默认显示的是8小时内未审批的案件（文书）未选择！正确答案为：D。
2. 在系统中,关于刑事案件中指派侦查员的描述，正确的是：()A. 主办侦查员只能有一个，协办侦查员可以有多个B. 主办侦查员可以有多个，协办侦查员可以有多个C. 主办侦查员和协办侦查员，均只能指派一个D. 以上说法都不正确未选择！正确答案为：A。
3. 在系统中，关于刑事案件和行政案件的转换，下面描述不正确的是：（）A. 行政案件受理后，可以转为刑事案件B. 行政案件办理期间，可以转为刑事案件C. 刑事案件在立案前，可以直接转行政案件D. 刑事案件在立案后，不能转行政案件未选择！正确答案为：D。
4. 关于系统的简表查询，下面说法正确的是：（）A. 选择“模糊匹配”查询时，可以查出包含关键字的记录B. 查询结果只能以时间字段排序显示C. 查询结果只能以固定的字段显示D. 查询结果只能查看，不能下载未选择！正确答案为：A。
5. 在系统中,关于行政案件中的嫌疑人描述，错误的是：(）A. 行政案件中，可以关联已有的嫌疑人，也可以直接新增嫌疑人B. 行政案件中，可以对犯罪嫌疑人进行刑事拘留C. 行政案件中，可以添加失踪人口信息D. 嫌疑人信息页面中的“身高”字段只允许输入长度为3位的整数未选择！正确答案为：D。
6. 对于已处于受理状态的行政案件，有关涉案单位的操作，以下说法错误的是：(）A. 只有“单位涉案类型”为“嫌疑单位”时，才可以对其呈请处理文书B. 对所有涉案单位都可以呈请处理文书C. 如果案件中有报案单位和报案人，则系统生成的受案登记表会自动调用报案单位和报案人信息D. 新增涉案单位时，可以关联已有的涉案单位，也可以直接新增未选择！正确答案为：B。
第3章存储管理-习题集一、选择题1.把作业空间中使用的逻辑地址变为内存中物理地址称为（）。
【＊，★，联考】A. 加载B. 重定位C. 物理化D. 逻辑化2.为了保证一个程序在主存中改变了存放位置之后仍能正确执行，则对主存空间应采用（）技术。
【＊，★，联考】A. 静态重定位B. 动态重定位C. 动态分配D. 静态分配3.分区分配内存管理方式的主要保护措施是（）。
（注：分区包括“固定分区”和“可变分区”）【＊＊，09考研】A. 界地址保护B. 程序代码保护C. 数据保护D. 栈保护4.分区管理要求对每一个作业都分配（）的内存单元。
【＊，★，联考】A. 地址连续B. 若干地址不连续C. 若干连续的块D. 若干不连续的块5.在固定分区分配中，每个分区的大小是（）。
【＊，联考】A. 相同B. 随作业长度变化C. 可以不同但预先固定D. 可以不同但根据作业长度固定6.在可变式分区存储管理中的拼接技术可以（）。
（注：拼接是指通过移动将多个分散的小分区合并成一个大分区。
）【＊，★，联考】A. 集中空闲分区B. 增加内存容量C. 缩短访问周期D. 加速地址转换7.可变式分区存储管理中，采用拼接技术的目的是（）。
【＊，联考】A. 合并空闲分区B. 合并分配区C. 增加主存容量D. 便于地址转换8.某基于动态分区存储管理的计算机，其主存容量为55MB（初始为空），采用最佳适配算法，分配和释放的顺序为：分配15MB，分配30MB，释放15MB，分配8MB，分配6MB，此时主存中最大空闲分区的大小是（）。
【＊＊，★，10考研】A. 7MBB. 9MBC. 10MBD. 15MB9.在分页存储管理中，主存的分配是（）。
【＊，联考】A. 以块为单位进行B. 以作业的大小分配C. 以物理段进行分配D. 以逻辑记录大小进行分配10.首次适应算法的空闲分区是（）。
【＊＊，★，联考】A. 按大小递减顺序连在一起B. 按大小递增顺序连在一起C. 按地址由小到大排列D. 按地址由大到小排列11.最佳适应算法的空闲分区是（）。
《计算机应用基础》第2章习题答案一、选择题1、下列操作中，________不能打开资源管理器。
A、单击“开始”按纽，从系统菜单选择“程序”子菜单中的“Windows资料管理器”B、右击“开始”按钮，从快捷菜单选择“资源管理器”C、双击“我的电脑”，从窗口中选择“资源管理器”D、右击“我的电脑”，从快捷菜单中选择“资源管理器”2、Windows中，若将鼠标指针“I”移动到一个窗口的边缘时，便会变为一个双向的箭头，表明________。
A、可以改变窗口的大小形状B、可以移动窗口的位置C、既可以改变窗口的大小，又可以移动窗口的位置D、既不可以改变窗口的大小，又不可以移动窗口的位置3、在Windows中，当一个应用程序窗口被最小化后，该应用程序将_______。
A、继续在前台执行B、被暂停C、被转入后台执行D、被终止执行4、在Windows中，屏幕上可以同时打开多个窗口，它们的排列方式是______ __。
A、既可以平铺也可以层铺B、只能平铺，不能层叠C、只能层叠，不能平铺D、只能由系统决定，用户无法更改5、Windows中的“桌面”指的是_________。
A、活动窗口B、全部窗口C、某个窗口D、整个桌面6、在Windows中不能打开“我的电脑”的操作是________。
A、双击“我的电脑”图标B、单击“开始”按纽，然后在系统菜单中选取C、右击“开始”按纽，然后在“资源管理器”中选取D、右击“我的电脑”图标，然后在快捷菜单中选择“打开”7、当一个应用程序窗口被最小化了后，该应用程序的状态为________。
A、保持最小化前的状态B、继续在前台运行C、被转入后台运行D、被终止运行8、Windows系统是一个________操作系统。
A、单用户单系统B、单用户多任务C、多用户单任务D、多用户多任务9、下列操作中，能进行格式化软盘的操作为________。
A、在“资源管理器”窗口中能够进行格式化软盘的操作B、在“我的电脑”窗口中能够进行格式化软盘的操作C、在Word的“打开”文件窗口中，可以进行软盘格式化操作D、在“控制面板”窗口中能够进行软盘的格式化操作10、在Windows中，若想改变屏幕上窗口的排列方式（改变平铺或层铺的方式），操作方法为_______。
一、单选题1．哪个不是Windows Server 2003 家族版本（ B ）A．Windows Server 2003 标准版 B．Windows Server 2003 专业版C．Windows Server 2003 企业版 D．Windows Server 2003 数据中心版2．在域内进行层次划分的最小单位是（ D ）A．对象 B．容器 C．用户 D．OU3．活动目录种的域之间的信任关系是（ D ）A．单向不可传递 B．双向不可传递C．单向可传递 D．双向可传递4．一个域中的AD 存放在（ A ）A．域控制器 B．独立服务器 C．域成员服务器 D．全局编录服务器5．下列关于域模式描述错误的是（ C ）A．账户和安全性都是由域中的DC 集中管理和维护B．用户在域中只需要一个唯一的账户即可访问整个域中的资源C．域模式只适用于规模小的网络环境，扩张性差D．集中性管理，安全性高6．下列不属于网络操作系统的是（ A ）A．MS/DOC B．NetWare C．Windows NT D．Linux7．在 Windows 中，为计算机上安装的各种硬件设备更新驱动程序的管理工具是（ C ）A．MMC B．系统属性 C．设备管理器 D．显示属性8．你公司的办公网络是Windows 2003 域环境。
你想使员工无论使用哪台计算机都能获得他在前一次登录使用的桌面环境，该员工可以修改并保存桌面环境。
你使用（ B ）能实现。
A．本地配置文件 B．漫游配置文件C．强制配置文件 D．临时配置文件9．你想将一台工作组中的windows 2003 服务器升级成域控制器，可以使用下列方法（ D ）。
A．组件服务 B．Windows 组件向导C．设备管理器 D．命令dcpromo10．公司新购买了一台服务器准备作为公司的文件服务器，管理员正在对该服务器的硬盘进行规划。
如果用户希望读写速度最快，他应将硬盘规划为（ C ），如果用户希望对系统分区进行容错，他应将硬盘规划为（ D ），如果用户希望对数据进行容错，并保证较高的磁盘利用率，他应将硬盘规划为（ E ）。
2012年PLC培训复习题2012年PLC培训复习题⼀、填空题1、PLC系统的组成：机架、CPU模块、信号模块、功能模块、接⼝模块、通讯处理器、电源模块和编程设备2、S7-300 是模块式中⼩型PLC，最多可以扩展 32 个模块，最多可以扩展为4个机架，但CPU312FM和CPU313却不具有扩展功能。
3、PLC停电的顺序是：系统断电时先断PLC主机电源，后断 ET200远程站电源；PLC主机断电时先断控制电源，后断负载电源；ET200远程站断电时先断控制电源，后断负载电源。
4、PLC送电的顺序是：系统送电时先送 ET200远程站电源，后送 PLC主机电源；PLC主机送电时先送负载电源，后送控制电源；ET200远程站送电时先送负载电源，后送控制电源。
5、电源模板PS307（10A）输⼊电压为AC220V ，输出电压为DC24V 。
6、我们常⽤的定时器有 5 类，分别为：脉冲定时器，扩展脉冲定时器，接通延时定时器，带保持的接通延时定时器，断开延时定时器。
7、2个累加器CPU的16位整数相加，加法指令将累加器1、2低字中的内容相加，其结果保存在累加器 1低字中，覆盖累加器 1 低字中的内容，⽽累加器 2 以及累加器 1 ⾼字中的内容保持不变。
8、S7-300 的模拟量模块起始地址从 256 开始，同类模块的地址按顺序连续排列。
9、图形编程语⾔属于可选软件包，它是⽤状态图来描述异步、⾮顺序过程的编程语⾔。
10、在西门⼦PLC中，⽤于循环处理的组织块是OB1。
11、对于S7项⽬，路径的⽬录名不能超过 8 个字符。
否则，在归档或使⽤“⽤于M7 的C”(Borland 编译器)时会出错。
12、在西门⼦PLC中，操作系统循环调⽤OB1并⽤这个调⽤启动⽤户程序循环执⾏。
13、在西门⼦PLC中，CPU并不直接访问I/O模板的输⼊（I）和输出（Q）地址区域，⽽是访问⼀个CPU内部的存储区域，该区域中包含输⼊和输出的映象。
操作系统（本科）模拟试题二 一、 选择题（每题2分，共30分） 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、方便用户与计算机的交互 D、需要中断机构及时钟系统的支持 8、进程是程序的执行过程，可以处于不同的状态，各自向前推进的速度是不可预知的，这种性质称作进程的（ ） A、动态性 B、并发性 C、异步性 D、调度性 9、操作系统中利用信号量和P、V操作，（ ） A、只能实现进程的互斥 B、只能实现进程的同步 C、可实现进程的互斥和同步 D、可完成进程调度 10、在操作系统中，作业处于（ ）状态时，已处于进程的管理之下。 A、后备 B、执行 C、提交 D、完成 11、进程和程序的本质区别是（ ） A、存储在内存和外存 B、顺序和非顺序执行机器指令 C、分时使用和独占使用计算机资源 D、动态和静态特征 12、下列的进程状态转换中，不可能发生的转换的是（ ） A、执行——>就绪 B、执行——>等待 C、等待——>执行 D、等待——>就绪 13、对于两个并发进程，设互斥信号量为mutex，若mutex=0则（ ） A、表示没有进程进入临界区 B、表示有一个进程进入临界区 C、表示有一个进程进入临界区，另一个进程等待进入 D、表示有两个进程进入临界区 14、银行家算法是一种（ ）算法。 A、死锁解除 B、死锁避免 C、死锁预防 D、死锁检测 15、UNIX/Linux属于（ ）操作系统 A、单用户单任务 B、单用户多任务 C、多用户单任务 D、多用户多任务
习题1、2 n+1=O(2n)成立吗？2 2n=O(2n)成立吗？2、证明O(f)+O(g)=O(max(f,g))3、证明：n!=o(n n)4、下面的算法段用于确定n的初始值。
试分析该算法段所需计算时间的上界和下界。
While(n>1)If (odd(n))n=3*n+1elsen=n/2;解：平均复杂度：log(2,n)+log(2,3^k)=log(2,n)+k*log(2,3*n)最小复杂度：log(2,n),当n=2^m,只执行第2句，最大复杂度：k*log(2,3*n);n约等于[log(2,n*3^k)]5、画出T(n)=T(n/3)+T(2n/3)+3的递归树。
T(n)= T(n/3)+ T(2n/3)+n的地归树如下：Mathematical Induction 数学归纳法使用数学归纳法，这个大家基本都清楚，就是假设一个在n的时候结论成立，证明在n+1的时候结论也成立，当然，在我们这里，稍微有点变化。
举个例子。
T(n) = T(n/2) + T(n/4) + T(n/8) + n现在我们要就上面表达式T(n)，现在我们就先guess T(n) = Theta(n)。
当然我们知道要证明T(n) = Theta(n)，我们需要分别证明T(n) = O(n)和T(n) = Omega(n)。
很显然，这里T(n) = Omega(n)的，因为T(n) = T(n/2) + T(n/4) + T(n/8) + n > n，显然，T(n) = Omega(n).下面用数学归纳法证明T(n) = O(n)假设T(n) <= cn，所以其中c是一个常数。
所以T(n) <= c*n/2 + c*n/4 + c*n/8 + n = (7c/8+1)n我们只需让(7c/8+1)n <= cn，显然我们可以找到一个正常数c使该式成立。
所以T(n) = O(n)。
综上，T(n) = Theta(n)。
上面的证明是没有问题了，但是可能有朋友要问，凭什么你一开始就guess T(n) = Theta(n) 呢？没错，make a good guess 是这种方法的关键，下面就简单的说一下make this guess 的intuition。
首先，我们可以简单的画出下面这棵树。
6、求⎣⎦n n T n T ++=)172/(2)(的上界。
【见文档】我们推测T(n)=O(n log n)，即推测存在正的常数C 和自然数n 0，使得当n≥n 0时有：T (n )≤Cn logn (6.2)事实上，取n 0=22=4，并取那么，当n 0≤n ≤2n 0时，(6.2)成立。
今归纳假设当2k -1n 0≤n ≤2k n 0 ，k ≥1时，(1.1.16)成立。
那么，当2k n 0≤n ≤2k +1n 0时，我们有：即(6.2)仍然成立，于是对所有n ≥n 0，(6.2)成立。
可见我们的推测是正确的。
因而得出结论：递归方程(6.1)的解的渐近阶为O (n log n )。
当n 充分大时与相差无几。
因此可以推测(6.3)与(6.1)有类似的上界T (n )=O (n log n )。
进一步，数学归纳将证明此推测是正确的。
7、确定n n T n T +=)3/(9)(的渐近界。
【见文档】解：T (n )=aT (n /b )+f (n ) (6.17)1. 对照(6.17)，我们有a =9，b =3， f (n )=n ，，取，便有，有相关定理知根据f (n )，有T (n )的渐近估计式第一类情况的公式，即：若对于某常数ε>0，有，则即T (n )=θ(n 2)。
8、设dd x a x a a x p +++=...)(10是一个d 次多项式。
假设已有一个算法能在O(i)时间内计算一个i 次多项式与一个一次多项式的乘积，以及一个算法能在)log (i i O 时间内计算两个i 次多项式的乘积。
对于任意给定的d 个整数d n n n ,...,,21，用分治法设计一个有效算法，计算出满足)(...)()(21d n p n p n P ===且最高次项系数为1的d 次多项式P(x),并分析算法的效率。
9、设计一个O(n 2)的时间算法，找出由n 个数组成的序列的最长单调递增子序列。
10、设计一个在O （n ）时间内计算nd x a x a a x p +++=...)(10的算法。
11、数组A[1..n]中存放正整数和负整数，设计一个在O(n)时间内将所有负整数放置所有正整数之前的算法。
12、掌握用动态规划解0-1背包问题。
【见文档】13、掌握用贪心算法（prim 算法）无向连通图的最小生成树。
14、掌握回溯法解0-1背包问题的解空间树[见文档] 15、掌握单纯形算法解线性规划问题[见文档8章] 16、掌握顶点覆盖问题的近似算法【9.4.2 】无向图G=(V,E)的顶点覆盖是它的顶点集V 的一个子集V ’ V ，使得若(u,v)是G 的一条边，则v ∈V ’或u ∈V ’。
顶点覆盖V ’的大小是它所包含的顶点个数|V ’|。
【 Cset 用来存储顶点覆盖中的各顶点。
初始为空，不断从边集e1中选取一边(u,v)，将边的端点加入cset 中，并将e1中已被u 和v 覆盖的边删去，直至cset 已覆盖所有边。
即e1为空。
】VertexSet approxVertexCover ( Graph g ) { cset=空集； e1=g.e ；while (e1 != 空集) {从e1中任取一条边(u,v)； cset=cset ∪{u,v}；从e1中删去与u 和v 相关联的所有边； }return c }算法approxVertexCover的性能比为2图(a)～(e)说明了算法的运行过程及结果。
(e)表示算法产生的近似最优顶点覆盖cset，它由顶点b,c,d,e,f,g所组成。
(f)是图G的一个最小顶点覆盖，它只含有3个顶点：b,d和e。
性能分析：若用A,B分别来计算算法循环中选取的边的集合和点的集合，由算法的构造克制A中任何两条边没有公共断点且B中的点也互不关联，因为算法选了一条边，并在将其断点加入顶点覆盖集C后，就将E1中与该边关联的所有边从E1中删去，对于每次选择的点也是同样处理，故算法终止时有|C|=2A+B，而图G的最小顶点覆盖C’，则|C’|≥|A|+|B 由此可得，|C|≥2|C'|-|B ,与原算法的|C|≥2|C'|,相比，当|B远远大于|A|时，此算法比原算法显示了更大的优越性。
17、什么是P类和NP类问题P问题：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。
我们常见到的一些信息奥赛的题目都是P问题。
NP类问题：首先NP问题不是非P类问题。
NP问题是指可以在多项式的时间里验证一个解的问题，即可以在多项式的时间里猜出一个解的问题，像Hamilton回路问题。
所有的P 问题都是NP问题，即能用多项式解决一个问题，必然能用多项式验证一个问题的解。
递归方程解的渐近阶的求法1.代入法这个方法的基本步骤是先推测递归方程的显式解，然后用数学归纳法证明这一推测的正确性。
那么，显式解的渐近阶即为所求。
2.迭代法这个方法的基本步骤是通过反复迭代，将递归方程的右端变换成一个级数，然后求级数的和，再估计和的渐近阶；或者，不求级数的和而直接估计级数的渐近阶，从而达到对递归方程解的渐近阶的估计。
3.套用公式法这个方法针对形如：T (n)=aT (n / b)+f (n) 的递归方程，给出三种情况下方程解的渐近阶的三个相应估计公式供套用。
4.差分方程法有些递归方程可以看成一个差分方程，因而可以用解差分方程(初值问题)的方法来解递归方程。
然后对得到的解作渐近阶的估计。
母函数法这是一个有广泛适用性的方法。
它不仅可以用来求解线性常系数高阶齐次和非齐次的递归方程，而且可以用来求解线性变系数高阶齐次和非齐次的递归方程，甚至可以用来求解非线性递归方程。
方法的基本思想是设定递归方程解的母函数，例如，我们要估计T(n)的上界，T(n)满足递归方程：其中是地板(floors)函数的记号，表示不大于n的最大整数。
我们推测T(n)=O(n log n)，即推测存在正的常数C和自然数n0，使得当n≥n0时有：T(n)≤Cn log n (6.2)事实上，取n0=22=4，并取那么，当n0≤n≤2n0时，(6.2)成立。
今归纳假设当2k-1n0≤n≤2k n0，k≥1时，(1.1.16)成立。
那么，当2k n0≤n≤2k+1n0时，我们有：即(6.2)仍然成立，于是对所有n≥n0，(6.2)成立。
可见我们的推测是正确的。
因而得出结论：递归方程(6.1)的解的渐近阶为O(n log n)。
这个方法的局限性在于它只适合容易推测出答案的递归方程或善于进行推测的高手。
推测递归方程的正确解，没有一般的方法，得靠经验的积累和洞察力。
我们在这里提三点建议：(1) 如果一个递归方程类似于你从前见过的已知其解的方程，那么推测它有类似的解是合理的。
作为例子，考虑递归方程：右边项的变元中加了一个数17，使得方程看起来难于推测。
但是它在形式上与(6.1)很类似。
实际上，当n充分大时与相差无几。
因此可以推测(6.3)与(6.1)有类似的上界T(n)=O(n log n)。
进一步，数学归纳将证明此推测是正确的。
(2)从较宽松的界开始推测，逐步逼近精确界。
比如对于递归方程(6.1)，要估计其解的渐近下界。
由于明显地有T(n)≥n，我们可以从推测T(n)=Ω(n)开始，发现太松后，把推测的阶往上提，就可以得到T(n)=Ω(n log n)的精确估计。
(3)作变元的替换有时会使一个末知其解的递归方程变成类似于你曾见过的已知其解的方程，从而使得只要将变换后的方程的正确解的变元作逆变换，便可得到所需要的解。
例如考虑递归方程：看起来很复杂，因为右端变元中带根号。
但是，如果作变元替换m=log n，即令n=2m，将其代入(6.4)，则(6.4)变成：把m限制在正偶数集上，则(6.5)又可改写为：T(2m)=2T(2m/2)+m若令S(m)=T(2m)，则S(m)满足的递归方程：S(m)=2S(m/2)+m，与(6.1)类似，因而有：S(m)=O(m1og m)，进而得到T(n)=T(2m)=S(m)=O(m1og m)=O(log n loglog n) (6.6)上面的论证只能表明：当(充分大的)n是2的正偶次幂或换句话说是4的正整数次幂时(6.6)才成立。
进一步的分析表明(6.6)对所有充分大的正整数n都成立，从而，递归方程(6.4)解的渐近阶得到估计。
