考试科目名称算法设计与分析A卷-南京大学计算机科学与技术系

计算机科学与技术同等学力申硕学科综合考试五选三全文共四篇示例，供读者参考第一篇示例：计算机科学与技术同等学力申硕学科综合考试是一种重要的选拔方式，对于有志于深造计算机科学与技术的学生来说，通过这个考试能够进入理想的研究生院校，深造自己的专业知识。

这个考试对于考生的综合能力要求较高，需要掌握广泛的知识，包括计算机基础理论、常见算法、编程能力等方面的知识。

下面我们来讨论一下这个考试的五选三部分。

第一部分是计算机基础理论。

计算机基础理论是计算机科学与技术领域的基础知识，包括计算机组成原理、操作系统、计算机网络、数据库系统等内容。

考生需要掌握这些基础知识，才能够在后续的学习和研究中有所突破。

在这个部分的考试中，常见的题目包括计算机组成原理中的CPU、内存、I/O等概念的解释，操作系统中的进程管理、内存管理、文件系统等知识的运用，计算机网络中的TCP/IP协议、网络层次模型等知识的理解，以及数据库系统中的SQL语言、关系数据库设计等内容。

第二部分是常见算法。

算法是计算机科学与技术领域的重要概念，它是解决问题的一种方法论，是计算机程序的核心。

在这个部分的考试中，考生需要掌握常见的排序算法、查找算法、动态规划算法等内容。

常见的题目包括对算法的理解、算法的时间复杂度和空间复杂度分析、算法的实现等方面的问题。

第三部分是编程能力。

编程是计算机科学与技术领域的核心技能，它是将问题转化为计算机程序的过程，是对计算机语言、数据结构、算法等知识的综合运用。

在这个部分的考试中，考生需要掌握至少一种编程语言，如C++、Java、Python等，并能够熟练地运用该语言解决实际问题。

常见的题目包括编程题、算法实现、数据结构的应用等内容。

计算机科学与技术同等学力申硕学科综合考试的五选三部分是考生综合能力的体现，需要考生具备扎实的计算机基础理论知识、熟练的算法分析能力和编程实践经验。

希望广大考生能够充分准备，取得优异的成绩，进入心仪的研究生院校，开启自己的科研之路。

2022年南京航空航天大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。

A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next2、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入B.选择C.希尔D.二路归并3、链表不具有的特点是（）。

A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s5、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V76、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

考试科目名称计算机组织与系统结构（A卷）2010——2011学年第1学期教师袁春风/杨若瑜考试方式：闭卷系（专业）计算机科学与技术年级2009班级学号姓名成绩题号一二三四五分数得分一、选择题（每小题2分，共36分）1.-1022的32位补码用十六进制表示为（ D ）。

A. 0000 03FEHB. 0000 FC02HC. FFFF 03FEHD. FFFF FC02H2.假定变量f的数据类型为float，f=-4.093e3，则变量f的机器数表示为（ B ）。

A. 457FD000HB. C57F D000HC. C5FF D000HD. C67FE800H3.某8位计算机中，假定带符号整数变量x和y的机器数用补码表示，[x]补=F5H，[y]补=7EH，则x–y的值及其相应的溢出标志OF分别是（ D ）。

A. 115、0B. 119、0C. 115、1D. 119、14.考虑以下C语言代码：short si= –8196;int i=si;执行上述程序段后，i的机器数表示为（D）。

A. 0000 9FFCHB. 0000DFFCHC.FFFF 9FFCHD. FFFF DFFCH5.以下几种存储结构中，采用相联存取方式访问信息的是（ C ）。

A.堆栈B.直接映射cacheC.分支历史记录表D.主存页表6.假定用若干个16K×8位的存储器芯片组成一个64K×8位的存储器，按字节编址，芯片内各单元交叉编址，则地址BFFFH所在的芯片的最小地址为（D）。

A. 0000HB. 0001HC. 0002HD. 0003H7.假定主存地址位数为32位，按字节编址，主存和cache之间采用全相联映射方式，主存块大小为一个字，每字32位，采用回写（Write Back）方式和随机替换策略，则能存放32K字数据的cache的总容量至少应有多少位？（ D）A. 1536KB. 1568KC. 2016KD. 2048K8.某计算机按字节编址，采用小端方式存储信息。

南京大学计算机科学与技术系操作系统期末试卷（2003年12月28）一、简答题1、列出I/O控制方式。

2、列出文件的共享方式。

3、列出几种实时调度算法。

4、列举系统发生死锁的必要条件。

5、虚拟存储器的容量与什么有关？6列出可变分区搜索分配算法。

7、列出影响缺页中断率的主要因素。

8、列出管程的主要特性。

二、问答题1、假设有一个操作系统采用层次结构组成，它运行在裸机上，并有以下层次组成：作业管理、设备管理、内存管理、命令管理、文件管理、进程调度及内核支撑功能，试给出一种由底向上的正确层次。

2、试从资源管理的观点，叙.述操作系统的功能和任务。

3、叙述操作系统中引入”进程”和”线程”的主要目的。

4、叙述进程通信及其分类。

5、叙述SPOOLING系统的技术特点、组成和数据结构。

6叙述内存映射文件的基本原理和优点。

7、解释微内核与单内核操作系统，说明微内核结构设计的主要优点。

8、来自处理器和主存内部的中断称“异常”，列举它的分类及主要区别？三、计算题1、如果一个操作系统采用LFU页面置换算法的一个变种：每个页框对应一个计数器，用来计数曾经装入过一个页框的页面个数，当有多个候选淘汰页面所在的页框计数器具有相同的最小值时，按FIFO进行。

现在有一个进程分到了4个页框，则对如下页面走向求出缺页中断次数及淘汰的页号。

1 , 2,3 ,4,5 ,3,4, 1,6,7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 7, 22、假定在某移动臂磁盘上，刚刚处理了访问38号柱面的请求，目前正在40号柱面读信息，并且有下述请求序列等待访问磁盘。

试分别使用电梯调度算法和最短寻找时间优先算法列出实际处3、某多道程序设计系统供用户使用的主存为100K，磁带机2台，打印机1台。

采用可变分区内存管理，采用静态方式分配外围设备，忽略用户作业I/O时间。

现有作业序列如下：作业号进入输入井时间运行时间主存需求量磁带需求打印机需求18:0025分钟15K1128:2010分钟30K0138:2020分钟60K1048:3020分钟20K1058:3515分钟10K11作业调度采用FCFS策略，优先分配主存低地址区且不准移动已在主存的作业，在主存中的各作业平分CPU 时间。

《计算机算法设计与分析》试卷 考试时间120分钟2002年-2003年第二学期学号 姓名 成绩一、阐述题1． 请说明算法的五个基本特性，并进行简要的分析(5分) 答：算法的五个基本特性如下：① 确定性 算法的每一种运算必须要有确切的定义，即每一种运算应该执行何种动作必须是相当清楚的、无二义性的。

② 能行性 一个算法是能行的是指算法中有待实现的运算都是基本的运算，每种运算至少在原理上能由人用纸和笔在有限时间内完成。

③ 输入 一个算法有0个或多个输人，这些输人是在算法开始之前给出的量，它取自特定的对象集合。

④ 输出 一个算法产生一个或多个输出，这些输出是同输人有某种特定关系的量。

⑤ 有穷性 一个算法总是在执行了有穷步的运算之后能够终止，且每一步都可在有穷时间内完成。

这里的有穷的概念不是纯数学的，而是在实际上是合理的，可以接受的。

凡是算法，都必须满足以上五条特性。

只满足前四条特性的一组规则不能称为算法，只能叫做计算过程。

2． 若森林非空，请按照森林和树相互递归的定义，阐述森林的两种遍历的方法。

(10分) 答：森林是由m(m ≥0)棵互不相交的树构成的集合。

对树中的每一个结点而言，其子树的集合即为森林。

所以，森林和树是可以相互递归定义的。

对于一个非空的森林F=(T 1，T 2，…，T m )，因为至少存在一棵树，不妨假设为T 1，则森林F 可以分解成T 1和由T 2，…，T m 构成的森林。

于是，可得到森林的两种遍历算法。

① 先序遍历森林若森林非空，则可按下述规则遍历这个森林： （1） 访问树中第一棵树的根结点；（2） 先序遍历第一棵中根结点的所有子树构成的森林； （3） 先序遍历除去第一棵树外剩下的树构成的森林。

② 中序遍历森林若森林非空，则可按下述规则遍历这个森林：（1） 中序遍历第一棵中根结点的所有子树构成的森林； （2） 访问树中第一棵树的根结点；（3） 中序遍历除去第一棵树外剩下的树构成的森林。

它的工作流程如下：首先在未排序序列（初始时为整个序列）中选择其中最大的元素max ，然后将该元素同未排序序列中的最后一个元素交换。

这时，max 元素就包含在由每次的最大元素组成的已排序序列之中了，也就说这时的max 已经不在未排序序列之中了。

重复上述过程直到完成整个序(a) 写出Maxsort 算法。

其中待排序序列为E ，含有n 个元素，脚标为范围为0,,1n-。

void Maxsort(Element[] E) {int maxID = 0;for (int i=E.length; i>1; i--) {for (int j=0; j<i; j++) {if (E[j] > E[maxID]) maxID = k;}E[i] <--> E[maxID];}}最坏情况同平均情况是相同的都是11(1)()2n i n n C n i -=-==∑。

该算法通过连续几遍浏览序列实现。

排序策略是顺序比较相邻元素，如果这两个元素未排序则交换这两个元素的位置。

也就说，首先比较第一个元素和第二个元素，如果第一个元素大于第二个元素，这交换这两个元素的位置；然后比较第二个元素与第三个元素，按照需要交换两个元素的位置；起泡排序的最坏情况为逆序输入，比较次数为11(1)()2n i n n C n i -=-==∑。

(b) 最好情况为已排序，需要(n-1)次比较。

4.3：(a)归纳法：当n=1时显然成立，当n=2时经过一次起泡后，也显然最大元素位于末尾；现假设当n=k-1是，命题也成立，则当n=k时，对前k-1个元素经过一次起泡后，根据假设显然第k-1个元素是前k-1个元素中最大的，现在根据起泡定义它要同第k个元素进行比较，当k元素大于k-1元素时，它为k个元素中最大的，命题成立；当k元素小于k-1元素时，它要同k-1交换，这时处于队列末尾的显然时队列中最大的元素。

综上所述，当n=k时命题成立。

《算法分析与设计》期末试题及参考答案一、简要回答下列问题：1.算法重要特性是什么？1.确定性、可行性、输入、输出、有穷性2.2.算法分析的目的是什么？2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。

3.3.算法的时间复杂性与问题的什么因素相关？3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。

4.算法的渐进时间复杂性的含义？4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。

时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。

5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。

最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max{ T(n，I) } , I∈Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n) =∑P(I)T(n，I) I∈Dn6.简述二分检索（折半查找）算法的基本过程。

6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]<x，则A[i：(i+j)/2-1]找x，否则在A[ (i+j)/2+1：j] 找x。

上述过程被反复递归调用。

7.背包问题的目标函数和贪心算法最优化量度相同吗？7. 不相同。

目标函数：获得最大利润。

最优量度：最大利润/重量比。

8.采用回溯法求解的问题，其解如何表示？有什么规定？8. 问题的解可以表示为n元组：（x1,x2,……x n），x i∈S i, S i为有穷集合，x i∈S i, （x1,x2,……x n）具备完备性，即（x1,x2,……x n）是合理的，则（x1,x2,……x i）(i<n)一定合理。

一、填空题（20分）1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。

2.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。

3.某一问题可用动态规划算法求解的显著特征是____________________________________。

4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。

5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。

6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。

7.以深度优先方式系统搜索问题解的算法称为_____________。

8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。

9.动态规划算法的两个基本要素是___________和___________。

10.二分搜索算法是利用_______________实现的算法。

二、综合题（50分）1.写出设计动态规划算法的主要步骤。

2.流水作业调度问题的johnson算法的思想。

3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。

4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。

南京师范大学的计算机科学与技术是工学大类下，此专业设置在计算机科学与技术学院下，主要的研究方向为计算机学习与智能软件、网络与信息安全、数据智能处理与挖掘三大研究方向。

在备考之前首先要知道院校的考察范围，对于南京师范大学来说，计算机科学与技术主要包括政治（思想政治理论）、英语一、数学一，专业科目为计算机学科专业综合。

下面说下各个科目的复习建议：数学首先，大家要明白数学在考验中的地位。

这是一门十分重要的的科目，也是考验拉分的重点科目，大家会发现，数学考研，高分很多，但是低分也是比比皆是，高分低分之间差个50、60分都是很正常的，对于考研想考计算专业的同学来说，你的竞争对手，大多数都是数学比较好的同学，因此千万不要在数学上被竞争对手差太多，否则是没有竞争力的。

在这里，我想说的一点是，千万不要盲目自信，我记得我在本科时候，自我感觉数学不错，有些时候，因为这样或者那样的原因，翘了很多节的数学课，总想着自己能够自己看书补回来，虽然看书的时候没有太大的障碍，但是在真正考试做题的时候，效果并不如我想的理想。

后来我想了想，其实老师上课，在讲解基础知识的同事，辅以题目练习，都是一些重点题目，这些题目大都包含了本章节的核心思想，同时老师对于知识的讲解，是基于多年的授课和备考经验来的，因此十分有针对性而且利于我们理解，因此在这里奉劝大家，千万不要自作聪明，认认真真跟随老师授课的脚步。

在复习时候，我建议，如果你对自己的数学基础知识没太有信心的话，千万不要直接进入做题训练环节。

我的做法是，先抽出时间过一下书，高数、线代等核心的基础知识、定理、公式等要先整理一下，最重要的是要形成自己的知识体系，千万不要在做题时遇到不会的知识点，去查书都找不到在哪里，这样非常的浪费时间，复习没有效率。

在对于基础的知识进行扫盲以后，下面就要对重点的知识点进行专项复习，这里可以做下《李永乐复习全书》，这本书对于想对数学分数有较高要求额同学可以仔细做做，还是很有收获的。

《计算机算法设计与分析》习题及答案一．选择题1、二分搜索算法是利用（ A ）实现的算法。

A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（ A ）。

A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（ A ）的一搜索方式。

A、分支界限法B、动态规划法C、贪心法D、回溯法4. 回溯法解旅行售货员问题时的解空间树是（ A ）。

A、子集树B、排列树C、深度优先生成树D、广度优先生成树5．下列算法中通常以自底向上的方式求解最优解的是（ B ）。

A、备忘录法B、动态规划法C、贪心法D、回溯法6、衡量一个算法好坏的标准是（ C ）。

A 运行速度快B 占用空间少C 时间复杂度低D 代码短7、以下不可以使用分治法求解的是（ D ）。

A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题8. 实现循环赛日程表利用的算法是（ A ）。

A、分治策略B、动态规划法C、贪心法D、回溯法9．下面不是分支界限法搜索方式的是（ D ）。

A、广度优先B、最小耗费优先C、最大效益优先D、深度优先10．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。

A、备忘录法B、动态规划法C、贪心法D、回溯法11.备忘录方法是那种算法的变形。

（ B ）A、分治法B、动态规划法C、贪心法D、回溯法12．哈夫曼编码的贪心算法所需的计算时间为（ B ）。

A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）13．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。

A、最小堆B、最大堆C、栈D、数组14．最长公共子序列算法利用的算法是（ B ）。

A、分支界限法B、动态规划法C、贪心法D、回溯法15．实现棋盘覆盖算法利用的算法是（ A ）。

A、分治法B、动态规划法C、贪心法D、回溯法16.下面是贪心算法的基本要素的是（ C ）。

A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解17.回溯法的效率不依赖于下列哪些因素（ D ）A.满足显约束的值的个数B. 计算约束函数的时间C.计算限界函数的时间D. 确定解空间的时间18.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ）A．递归函数 B.剪枝函数 C。

习 题 解 析第1章1. 解析：算法主要是指求解问题的方法。

计算机中的算法是求解问题的方法在计算机上的实现。

2. 解析：算法的五大特征是确定性、有穷性、输入、输出和可行性。

3. 解析：计算n ⎢⎥⎣⎦的算法，其中n 是正整数。

可以取循环变量i 的值从1开始，算i 的平方，取平方值最接近且小于或者等于n 的i 即可。

4. 解析：可以使用反证法，设i=gcd(m, n)=gcd(n, m mod n)，则设m=a*i ，n=b*i ，且a 与b 互质，这时m mod n=（a-x*b ）*i ，只需要证明b 和a-x*b 互质，假设二者不互质，可以推出a 与b 不互质，因此可以得到证明。

5. 解析：自然语言描述：十进制整数转换为二进制整数采用“除2取余，逆序排列”法。

具体做法是：用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为0时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。

流程图：如图*.1开始输入n长度len=(logn/log2)len>=0Y输出(n>>len)&1)len=len-1N结束图*.1 十进制整数转换成二进制整数流程图6. 解析：a.如果线性表是数组，则可以进行随机查找。

由于有序，因此可以进行折半查找，这样可以在最少的比较次数下完成查找。

b.如果线性表是链表，虽然有序，则只能进行顺序查找，从链表头部开始进行比较，当发现当前节点的值大于待查找元素值，则查找失败。

7. 解析：本题主要是举例让大家了解算法的精确性。

过程中不能有含糊不清或者二义性的步骤。

大家根据可行的方式总结一下阅读一本书的过程即可。

8. 解析：数据结构中介绍的字典是一种抽象数据结构，由一组键值对组成，各个键值对的键各不相同，程序可以将新的键值对添加到字典中，或者基于键进行查找、更新或删除等操作。

《算法设计与分析》试卷1一、多项选择题（每空2分, 共20分）:1.以下关于算法设计问题的叙述中正确的是__________。

A.计算机与数值问题的求解——方程式求根、插值问题、数值积分、函数逼近等有关B.利用计算机无法解决非数值问题C.计算机在解决分类、语言翻译、图形识别、解决高等代数和组合分析等方面的数学问题、定理证明、公式推导乃至日常生活中各种过程的模拟等问题中, 主要进行的是判断、比较, 而不是算术运算D、算法设计与分析主要研究对象是非数值问题, 当然也包含某些数值问题2.算法的特征包括_________。

A.有穷性B、确定性C.输入和输出D.能行性或可行性3、以下描述是有关算法设计的基本步骤:①问题的陈述②算法分析③模型的拟制④算法的实现⑤算法的详细设计⑥文档的编制, 应与其它环节交织在一起其中正确的顺序是__________。

A.①②③④⑤⑥B.①③⑤②④⑥C.②④①③⑤⑥D.⑥①③⑤②④4.以下说法正确的是__________。

A.数学归纳法可以证明算法终止性B.良序原则是证明算法的正确性的有力工具C. x = 小于或等于x的最大整数（x的低限）D. x = 小于或等于x的最大整数（x的高限）5、汉诺塔（Hanoi）问题中令h（n）为从A移动n个金片到C上所用的次数, 则递归方程为__________, 其初始条件为__________, 将n个金片从A柱移到C柱上的移动次数是__________；设菲波那契（Fibonacci）数列中Fn为第n个月时兔子的对数, 则有递归方程为__________, 其中F1=F2=__________。

A.Fn=Fn-1+Fn-2 B、h（n）= 2h（n-1）+1C.1 D、h（1）= 1E、h（n）=2n-1F、06.在一个有向连通图中（如下图所示）, 找出点A到点B的一条最短路为____ ______。

A.最短路: 1→3→5→8→10, 耗费: 20B、最短路：1→4→6→9→10, 耗费：16C.最短路: 1→4→6→9, 耗费: 12D.最短路: 4→6→9→10, 耗费: 13二、填空（每空2分, 共20分）:1.快速排序法的基本思想是重新排列关键字, 把一个文件分成两个文件, 使得第一个文件中所有元素均小于第二个文件中的元素；然后再对两个子文件进行同样的处理。

《算法设计与分析》课程笔试样题一（90分钟，开卷笔试，100分）学年学期班一、设n为正整数，利用大“O(·)”记号，将下列程序段的执行时间表示为n的函数，分析下列程序段的时间复杂度（每小题7.5分，共15分）1．程序段1i=1; k=0;while(i<n) {k=k+10*i;i++;}2．程序段2y=0; n=100;while ((y+1)*(y+1)<n) y++;二、简答题（每小题7.5, 共15分）1. 什么是算法, 算法具有的特性是什么？2. 什么是分枝限界法?三、设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。

试画出对其进行折半搜索时的二叉搜索树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度（20分）四、下面是利用贪心算法求解单源点最短路径问题的伪代码，请你阅读代码并在空白处填上适当的代码（20分）Procedure SHORTEST_PATHS(v, COST, DIST, n)// G是一个n个结点的有向图，它由成本邻接矩阵COST(n, n)表示，DIST(j)表示结点v到结点j的最短路径长度，这里1≤ j ≤n，DIST(v)置成0。

boolean S(1:n);real COST(1:n, 1:n), DIST(1:n);integer u, v, n, i, w;for i=1 to n doS(i)=0;①;repeatS(v)=1; DIST(v)=0; u=v;for i=2 to n dofor所有S(w)=0的结点w do找DIST(u)+COST(u, w)最小的节点w;repeatDIST(w)=min(DIST(w), ②) ;S(w)=1;③;repeatend SHORTEST_PATHS五、下列代码为求多段图问题的伪C语言代码：ForwardShortestPath(float c[][n], int k, int n){ float C[n]; int d[n], p[k]; C[0:n-2]=MAX; C[n-1]=0;for(i=n-2; i>=0; i--)for(j=i+1; j<=n-1; j++)if((c[i][j]>0)&&(c[i][j]+C[j]<C[i])){ C[i]=c[i][j]+C[j];①;}for(p[0]=0, p[k-1]=n-1, i=1; i<k-1; k++) ②;}其中，n为图的节点数，k为段数，c[][]为成本邻接矩阵，C[]为各节点到汇点的最短路径长度，d[]为各节点到汇点的最短路径上的后向邻接节点，p[]存储最短路径上的节点序列。

2019南京大学软件工程考研初试科目及参考书目
南京大学（Nanjing University）简称“南大”，是中华人民共和国教育部直属、中央直管副部级建制的全国重点大学，是历史悠久、声誉卓著的百年名校，位列首批国家“双一流A类、211工程、985工程”。

考试科目：
101政治、201英语一、301数学一、842数据结构、软件工程、操作系统和计算机网络
参考书目：
《数据结构与算法分析：Java语言描述》（英文版），第2版，机械工业出版社；
《软件工程：实践者的研究方法》（第五版）梅宏译，机械工业出版社；《操作系统教程》（第四版），费翔林、骆斌编著,，高等教育出版社，2008年；
《思科网络技术学院教程CCNA（1、2，3学期）》，人民邮电出版社；《需求工程-软件建模与分析》骆斌主编、丁二玉编著，高等教育出版社；《设计模式：可复用面向对象软件的基础》李英军等译，机械工业出版社；《Java核心技术》卷1（原书第8版）(美)Cay S.Horstmann GaryCornell，机械工业出版社。