山东科技大学算法复习题

//////////Problem D: 货币兑换Description给出人民币对美元、欧元、日元的当日汇率，求给定金额的人民币能兑换成外币的金额，求给定金额的外币能兑换成人民币的金额。

要计算的外币有三种：美元、欧元、日元。

Input输入有三行。

第一行依次为美元、欧元、日元外币汇率，用空格分开。

汇率用100外币为单位，精确到小数点后4位，如668.5200表示“100美元=668.5200人民币”。

汇率浮动范围为(0,10000)。

第二行为外币金额x，第三行为人民币金额y。

x,y均为整数，且0<x,y<10000。

Output输出为两行。

第一行为金额为x的美元、欧元、日元兑换成人民币的金额，用空格分开。

第二行为金额为y的人民币兑换成美元、欧元、日元的金额，用空格分开。

所有金额精确到小数点后两位。

Sample Input668.5200 908.0685 7.985215001500Sample Output10027.80 13621.03 119.78#include <stdio.h>int main(){double i,j,k,a,b,c,d,e,f;double x,y;scanf ("%lf %lf %lf",&i,&j,&k);scanf ("%lf%lf",&x,&y);a=x/100*i;b=y/100*j;c=x/100*k;d=y*100/i;e=y*100/j;f=y*100/k;printf ("%.2lf %.2lf %.2lf\n",a,b,c);printf ("%.2lf %.2lf %.2lf\n",d,e,f);}////Problem E: 求字符的值////Description从键盘输入3个字符（不含双字节字符），分别输出每个字符的十进制值（ASCII码）、八进制值和十六进制值。

2021年山东科技大学数据结构与操作系统--真题及参考答案数据结构与操作系统Z试卷《数据结构》部分（90分）一、简答题（20分，每题5分）1、请给出四种数据结构基本类型。

答：根据数据元素之间关系的不同特征，通常有下列4类的基本结构：（1）集合。

（2）线性结构。

（3）树形结构。

（4）图状结构或网状结构。

2、简述栈和队列的区别。

（P44;P58）区别和联系：从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。

栈只允许在表的一端进行插入或删除操作，队列只允许在表的一端进行插入操作、而在另一端进行删除操作。

因而，栈和队列也可以被称作为操作受限的线性表。

3、什么是关键路径？(P183)在AOE网中，有些活动可以并行地运行，最短完成时间应是从源点到汇点的最长路径长度（指路径上所有权值之和），称这样的路径为关键路径。

4、插入类排序有哪几种？其中，哪些是不稳定的排序算法？(P265)二、应用题（40分）1、如果进栈的序列是12345，请给出所有3、4先出栈的序列（3在4之前出栈）。

（5分）(P)【解答】34215 ，34251， 34521 (可以参考下面这个题：【￥】铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：1，2，3，4，5，6，那么是否能够得到435612， 325641， 154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出\进栈\或\出栈\的序列)。

【解答】输入序列为123456，不能得出435612和154623。

不能得到435612的理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。

不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。

得到325641的过程如下：1 2 3顺序入栈，32出栈，得到部分输出序列32；然后45入栈，5出栈，部分输出序列变为325；接着6入栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。

Problem A: Hello world! DescriptionXiao_ming有两个哥哥，大哥叫Da_min，二哥叫Er_min。

三兄弟放学回家，父母分别跟他们打招呼。

Input无Output请输出：Hello Da_min,Hello Er_min,Hello Xiao_ming!Sample InputSample OutputHello Da_min,Hello Er_min,Hello Xiao_ming!HINT请注意换行符#include <stdio.h>int main(){printf("Hello Da_min,\nHello Er_min,\nHello Xiao_ming!");}Problem A: 算术基本运算Description计算两整数x和y（0<x,y<1000）的和、差、积、商、余数、x的平方和y的三次方。

Input输入只有一行，格式见sample。

Output输出为多行，按顺序每行输出x,y的和、差、积、商、余数、x的平方和y的三次方，格式见sampleSample Inputx = 11, y = 3Sample Outputx + y : 14x - y : 8x * y : 33x / y quotient: 3, remainder: 2x ^ 2 : 121y ^ 3 : 27HINT注意输入输出格式。

了解C语言整数除法运算符的特点，并且没有求幂的运算符。

#include <stdio.h>int main(){int x,y;scanf ("x = %d, y = %d",&x,&y);printf ("x + y : %d\n",x+y);printf ("x - y : %d\n",x-y);printf ("x * y : %d\n",x*y);printf ("x / y quotient: %d, remainder: %d\n",x/y,x%y);printf("x ^ 2 : %d\n",x*x);printf ("y ^ 3 : %d\n",y*y*y);}Problem B: 求圆的面积和周长Description从键盘输入圆的半径，求圆的面积和周长，圆周率取3.14。

山东科技大学第二届ACM程序设计大赛试题册试题共14页，题目共计12道山东科技大学第二届ACM 程序设计大赛试题册Problem A 简单计算Description给出n 个十进制的数，找出这n 个数的二进制表示中1的个数最少的数。

Input输入的第一行为一个正整数T （1≤T ≤20）,代表测试数据组数。

对于每组测试数据，输入的第一行为一个正整数n （1≤n ≤10000），第二行为n个正整数A 1、A 2、…、A n （1≤A i ≤109），每个数之间以空格分隔。

Output每组数据输出一行，先输出数据组数，再输出二进制中含1最少的数，如果存在多个数符合条件，输出最小的那个。

具体输出格式见样例输出。

Sample Input Sample Output山东科技大学第二届ACM 程序设计大赛试题册Problem B 关键字搜索Description我们的新网站具有了全新的搜索功能，使用了2个通配符“*”和“？”，其中“*”表示0或者多个小写字母，“？”代表1个字母。

当我们输入一个关键字的时候，我们在不确定的地方就使用通配符。

我们在数据库里面有多条记录，每条记录都是由小写字母组成，现在给出一个关键字，你能告诉我数据库里面有多少条与关键字相匹配的记录吗？例如： 如果关键字是j*y*m*y?，那么jiyanmoyu ，jyanmoyu ，jymyu 都是相匹配的记录。

Input第一行输入一个T （T ≤20），表示有T 组测试数据。

对于每组测试数据，第一行是输入的关键字，接下是数据库里面的所有记录的条数n ，1≤n ≤10000,每条记录的长度不超过50个小写字母。

Output对于每组测试数据，输出与关键字相匹配的总记录条数，占一行。

Sample Input Sample Output山东科技大学第二届ACM 程序设计大赛试题册Problem C 正方形Description在二维坐标轴内给出四个点，这四个点能否构成一个正方形。

2022年山东科技大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入B.选择C.希尔D.二路归并2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-13、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。

A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、已知串S='aaab'，其next数组值为（）。

A.0123B.1123C.1231D.12116、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4507、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。

A．只有e B．有e、b C．有e、c D．无法确定8、一个具有1025个结点的二叉树的高h为（）。

A.11B.10C.11至1025之间D.10至1024之间9、有n（n>0）个分支结点的满二叉树的深度是（）。

A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。

A.(n-1)/2B.n/2C.(n+1)/2D.n二、填空题11、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。

c语言考试题及答案山东科技大学一、选择题（每题2分，共20分）1. 下列哪个选项是C语言中的关键字？A. voidB. intC. floatD. All of the above答案：D2. C语言中，用于定义一个字符常量的是什么？A. "A"B. 'A'C. AD. a答案：B3. 在C语言中，以下哪个函数用于计算并返回字符串的长度？A. strlen()B. strcat()C. strcpy()D. strcmp()答案：A4. 下列哪个选项不是C语言中的控制语句？A. ifB. whileC. switchD. continue答案：D5. C语言中，以下哪个选项是正确的二维数组定义？A. int array[3][4];B. int array[][];C. int array[3][];D. int array[3][4] = {{1,2},{3,4},{5,6}};答案：A6. 在C语言中，哪个运算符用于将一个值赋给变量？A. +B. -C. =D. %答案：C7. 下列哪个选项是C语言中的正确注释？A. // This is a single line commentB. /* This is a single line comment */C. // This is a multi-line commentD. /* This is a multi-line comment */答案：A8. 在C语言中，以下哪个选项是正确的函数定义？A. int function(int a) { return a; }B. int function(int a) { return a; }C. int function(int a) { return a; }D. int function(int a) { return a; }答案：A9. C语言中，以下哪个选项是正确的文件包含指令？A. #include <stdio.h>B. #include "stdio.h"C. #include <stdio.h>D. #include "stdio.h"答案：A10. 在C语言中，以下哪个选项是正确的宏定义？A. #define PI 3.14159B. #define PI "3.14159"C. #define PI 3.14159D. #define PI 3.14159答案：A二、填空题（每题2分，共20分）1. C语言中，用于声明一个整型变量的关键字是________。

《数据结构》部分一、简答题（10分，每题5分）1、数据元素之间的关系在计算机中的存储有几种表示方法？各有什么特点？（P6）解：数据元素之间的关系在计算机中有四种不同的表示方法：(1)顺序存储方法。

数据元素顺序存放，每个结点只含有一个元素。

存储位置反映数据元素间的逻辑关系。

存储密度大，但有些操作(如插入、删除)效率较差。

(2)链式存储方法。

每个结点除包含数据元素信息外还包含一组指针。

指针反映数据元素间的逻辑关系。

这种操作不要求存储空间连续，便于进行插入和删除等操作，但存储空间利用率较低。

另外，由于逻辑上相邻的数据元素在存储空间上不一定相邻，所以不能对其进行随机存取。

(3)索引存储方法。

除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表。

索引表中的索引指示结点的存储位置，兼有动态和静态特性。

(4)哈希(或散列)存储方法。

通过哈希函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将哈希函数的值作为该数据元素的存储地址。

其特点是存取速度快，只能按关键字随机存取，不能顺序存储，也不能折半存取。

2、对于堆排序法，快速排序法和归并排序法，若仅从节省存储空间考虑，则应该首先选取其中哪种方法？其次选取哪种方法？若仅考虑排序结果的稳定性，则应该选取其中哪种方法？若仅从平均情况下排序最快这一点考虑，则应该选取其中哪些方法？（P289）答：若只从存储空间考虑，则应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法；若只从排序结果的稳定性考虑，则应选取归并排序方法；若只从平均情况下最快考虑，则应选取快速排序方法；若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。

二、应用题（55分）1、证明：同一棵二叉树的所有叶子结点，在前序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同）。

（8分）（例如先序abc，后序bca，中序bac。

）(P128) 答：【答案】先序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。

数学11-1 C语言平时训练题1、算术基本运算Description计算两整数x和y（0<x,y<1000）的和、差、积、商、余数、x的平方和y的三次方。

Input输入只有一行。

Output输出为多行，按顺序每行输出x,y的和、差、积、商、余数、x的平方和y的三次方。

Sample Inputx = 11, y = 3Sample Outputx + y : 14x - y : 8x * y : 33x / y quotient: 3, remainder: 2x ^ 2 : 121y ^ 3 : 27Answer#include <stdio.h>int main(){int x,y,a,b,c,d,e,f,g;0<x<1000,0<y<1000;scanf("x = %d, y = %d",&x,&y);a=x+y;b=x-y;c=x*y;d=x/y;e=x%y;f=x*x;g=y*y*y;printf("x + y : %d\n",a);printf("x - y : %d\n",b);printf("x * y : %d\n",c);printf("x / y quotient: %d, remainder: %d\n",d,e);printf("x ^ 2 : %d\n",f);printf("y ^ 3 : %d\n",g);return 0;}2、求圆的面积和周长Description从键盘输入圆的半径，求圆的面积和周长，圆周率取3.14。

Input输入一个浮点型数据，有效数字不会超过十进制的6位。

Output输出为两行。

第一行为圆的面积，第二行为圆的周长，格式见sample。

Sample Input3Sample OutputArea: 28.260000Perimeter: 18.840000Answer#include<stdio.h>#define PI 3.14int main(){float r,s,c;scanf("%f",&r);s=PI*r*r;c=2*PI*r;printf("Area: %f\n",s);printf("Perimeter: %f\n",c);return 0;}3、平均值Description求3个数的平均值。

Problem A: Hello world! DescriptionXiao_ming有两个哥哥，大哥叫Da_min，二哥叫Er_min。

三兄弟放学回家，父母分别跟他们打招呼。

Input无Output请输出：Hello Da_min,Hello Er_min,Hello Xiao_ming!Sample InputSample OutputHello Da_min,Hello Er_min,Hello Xiao_ming!HINT请注意换行符#include <stdio.h>int main(){printf("Hello Da_min,\nHello Er_min,\nHello Xiao_ming!");}Problem A: 算术基本运算Description计算两整数x和y（0<x,y<1000）的和、差、积、商、余数、x的平方和y的三次方。

Input输入只有一行，格式见sample。

Output输出为多行，按顺序每行输出x,y的和、差、积、商、余数、x的平方和y的三次方，格式见sampleSample Inputx = 11, y = 3Sample Outputx + y : 14x - y : 8x * y : 33x / y quotient: 3, remainder: 2x ^ 2 : 121y ^ 3 : 27HINT注意输入输出格式。

了解C语言整数除法运算符的特点，并且没有求幂的运算符。

#include <stdio.h>int main(){int x,y;scanf ("x = %d, y = %d",&x,&y);printf ("x + y : %d\n",x+y);printf ("x - y : %d\n",x-y);printf ("x * y : %d\n",x*y);printf ("x / y quotient: %d, remainder: %d\n",x/y,x%y);printf("x ^ 2 : %d\n",x*x);printf ("y ^ 3 : %d\n",y*y*y);}Problem B: 求圆的面积和周长Description从键盘输入圆的半径，求圆的面积和周长，圆周率取3.14。

一、排序和查找是经常遇到的问题。

按照要求完成以下各题：（20分)（1） 对数组A=｛15,29，135，18，32,1，27，25，5｝，用快速排序方法将其排成递减序。

（2） 请描述递减数组进行二分搜索的基本思想，并给出非递归算法。

（3） 给出上述算法的递归算法.（4） 使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：18，31，135。

二、对于下图使用Dijkstra 算法求由顶点a 到顶点h 的最短路径。

（20分）.三、 假设有7个物品，它们的重量和价值如下表所示。

若这些物品均不能被分割，且背包容量M ＝150，使用回溯方法求解此背包问题.请写出状态空间搜索树(20分)。

四、已知1()*()i i k k ij r r A a +=，k =1，2,3,4,5,6，r 1=5，r 2=10,r 3=3，r 4=12，r 5=5，r 6=50，r 7=6，求矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序.（要求:给出计算步骤）（20分） 五、回答如下问题：（20分)（1） 什么是算法？算法的特征有哪些?（2） 什么是P 类问题？什么是NP 类问题？请描述集合覆盖问题的近似算法的基本思想。

一、排序和查找是常用的计算机算法.按照要求完成以下各题：（20分）（1） 对数组A=｛15，9，115，118，3,90，27，25，5}，使用合并排序方法将其排成递减序。

（2） 若改变二分搜索法为三分搜索法，即从一个递减序列A 中寻找元素Z,先与元素[]3nA 比较,若[]3n Z A >，则在前面[]3n 个元素中寻找Z ；否则与2[]3nA 比较，总之使余下的序列为[]3n 个元素。

给出该方法的伪代码描述。

（3） 使用上述算法对(1）所得到的结果搜索如下元素，并给出搜索过程:118，31，25。

二、假设有7个物品，它们的重量和价值如下表所示。

数据结构部分
一、选择题（每题2分，共20分）
1、将线性表La和Lb头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小，
应该使用哪种结构？()
A.单链表
B.单循环链表
C.带尾指针的单循环链表
D.带头结点的双循环链表
2、在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作
为（）。

A.front=front->next
B.s->next=rear;rear=s
C.rear->next=s;rear=s;
D.s->next=front;front=s;
3、设一个堆栈的入栈顺序是1、2、3、
4、5。

若第一个出栈的元素是4，则最后一个
出栈的元素必定是：()
A.1
B.3
C.5
D.1或者5
4、由分别带权为9、2、
5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长
度为：()
A.23
B.37
C.44
D.46
5、如果AVL树的深度为5（空树的深度定义为0），则此树最少有多少个结点？()
A.12
B.20
C.33
D.64。

第一章测试1.程序运行结果往往与输入相关，所以程序可以不满足确定性（）A:错B:对答案:A2.有关算法分析的事后统计法正确的是（）。

A:结果是面向机器，面向程序员，面向语言的B:测试的结果与程序的编译和运行环境有关C:结果与测试的样本数据有关D:从理论上讲，在各种软硬件环境下进行算法测试，得到的资源耗费都是一样的。

答案:ABC3.下面哪些内容是算法设计之前要完成的内容? ( )A:使用何种计算机语言设计程序B:是求精确解还是近似解C:确定合适的数据结构D:证明算法的正确性。

答案:BC4.函数10logn3+5logn2的渐近表达式为（）：A:O(nlogn)B:O(logn3)C:O(logn)D:O（logn2）答案:C5.下列函数根据渐近阶从低到高顺序是（）A:logn ＜ n1/2 ＜2n ＜n3 ＜3n ＜n!B:n1/2 ＜ logn ＜2n ＜n3 ＜ n! ＜ 3nC:n1/2 ＜ logn ＜2n ＜n3 ＜3n ＜n!D:logn ＜n1/2＜2n ＜n3 ＜ n! ＜ 3n答案:A6.研究NPC 问题的意义: 一旦某个NPC问题找到了多项式时间复杂性的算法，那么所有的NP问题都找到了多项式时间算法。

( )A:对B:错答案:A第二章测试1.直接或间接的调用自身的算法称为（）。

A:递归算法B:迭代算法D:动态规划算法答案:A2.Hanoi塔问题如下图所示。

现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。

移动圆盘时遵守Hanoi塔问题的移动规则。

由此设计出解Hanoi塔问题的递归算法正确的为：（）A:B:C:D:答案:A3.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题分别解决子问题最后将子问题的解组合起来形成原问题的解。

这要求原问题和子问题（）。

A:问题规模相同，问题性质不同B:问题规模不同，问题性质不同C:问题规模相同，问题性质相同D:问题规模不同，问题性质相同答案:D4.利用二分搜索，最坏情况下的计算时间复杂性为（）。

《数据结构》部分
一、简答题（20分，每题5分）
1、什么是最优二叉树（Huffman 树）？
2、什么是哈希表？
3、什么是稳定的排序方法？
4、什么是AOE网中的关键路径？
二、应用题（45分）
1、给出使用两个栈模拟一个队列最高效的算法思想（只需使用图和必要的文字描述）。

（15分）
2、已知一个无向图如下图所示，要求用Kruskal算法生成最小树，试画出构造过程。

（10分）
3.一组关键字集合为(25，10，8，27，32，68)，设哈希函数H(k)=k mod 7，分别用线性探测和链地址法作解决冲突的方法构造长度为8的哈希表，要求画出具体的哈希表并求查找成功且等概率情况下各自的平均查找长度。

（10分）
4、画出向小顶堆中加入数据4, 2, 5, 8, 3, 6, 10, 1时，每加入一个数据后堆的变化。

（10分）
三、算法设计题（25分)
答题要求：
①用自然语言说明所采用算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③用C语言写出对应的算法程序，并做必要的注释。

1、已知一个带有表头结点的单链表，结点结构为 data link ,假设该链表只给出了头指针list。

在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点。

若查找成功，算法输出该结点的data域值，并返回1；否则只返回0。

（15分）
2、设计一个算法，判断无向图G是否连通。

若连通则返回1；否则返回0。

（10分）。

数据结构试卷（一)1.栈和队列的共同特点是( ）。

A。

只允许在端点处插入和删除元素B。

都是先进后出C。

都是先进先出D。

没有共同点2.用链接方式存储的队列，在进行插入运算时（ ).A。

仅修改头指针 B。

头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构?( ）A. 队列B。

栈 C. 线性表D。

二叉树4.设有一个二维数组A[m］［n]，假设A[0］［0]存放位置在644（10），A［2］[2］存放位置在676（10)，每个元素占一个空间，问A[3][3］(10）存放在什么位置？脚注(10)表示用10进制表示.A．688 B．678 C．692 D．6965.树最适合用来表示（)。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( )。

A．2k—1 B。

2K+1 C.2K—1 D. 2k—17.若有18个元素的有序表存放在一维数组A[19］中，第一个元素放A［1］中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1,2，3 B。

9，5，2,3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A。

O（1） B. O(n） C. O(1og2n) D。

O（n2）9.对于线性表（7，34，55，25，64，46，20，10)进行散列存储时，若选用H（K）=K ％9作为散列函数,则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。

A.5B.6 C。

7 D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：_________、_________、_________和_________。

2.一个算法的时间复杂度为(n3+n2log2n+14n）/n2,其数量级表示为________。

一、简答题（1题4分，2题4分，3题6分，共14分）1.什么是算法？什么是程序？。

2.算法的特点是什么？3.给出算法复杂度计量符号O 和Ω的定义。

二、算法复杂度计算（10分）已知某算法耗时为T （n ），且满足如下递归方程(1)1()2(/2)()1O n T n T n O n n =⎧=⎨+⎩＞试计算该算法的时间复杂度T （n ）。

三、对于分治法，试解答：（1、2题各5分，3题8分,共18分）1.分治法的基本思想什么？2.试给出分治法的一般算法设计模式，用伪代码描述或详述解题步骤。

3.设n 个不同的整数排好序后存于T[0..n-1]中。

若存在一个下标i ，0≤i<n,使得T[i]=i ，设计一个有效算法找到这个下标。

要求算法在最坏情况下的计算时间为O (logn)。

四、对于动态规划算法，试解答：（1题4分，2题6分，3题10分，共20分）1.动态规划算法的两个基本要素，每个要素的含义是什么?2.写出动态规划算法解题的基本步骤。

3.0－1背包问题：给定n 个物品和一个背包。

物品i 的重量为wi ，价值为vi ，背包容量为c 。

问如何选择装入背包中的物品，使得装入背包的物品的价值最大？在装入背包时，每种物品i 只有两种选择，装入或者不装入，既不能装入多次，也不能只装入一部分。

其形式化描述为：问题的形式描述是：给定c ＞0，wi ＞0，vi ＞0，1≤i ≤n ，求n 元0-1向量(x1,x2,…,xn)，使得用动态规划方法可以求解0－1背包问题,请回答下列问题：(1)证明该问题具有最优子结构性质；(2)设m(i,j)为背包容量为j ，可选择物品为i,i+1,…,n 时0-1背包问题的最优解，给出计算m(i,j)的递归式。

五、对于贪心算法，试解答：（1题3分，2题10分，共13分）1.贪心选择性质是什么?2.程序存储问题:设有n 个程序{1,2,…,n }要存放在长度为L 的磁带上。

程序i 存放在磁带上的长度是Li ，1≤i≤n 。