厦门大学---算法分析——6

1. 数据元素是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。

2 何谓算法?它与程序有何区别?算法是解决某一特定类型问题的有限运算序列。

程序＝数据结构＋算法3. 算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机运行时间的长短和占据空间的大小。

4. 何谓频度、时间复杂度、空间复杂度？说明其含义。

算法中语句的重复次数称为该语句的频度。

时间复杂度是算法执行所需要的时间，也就是算法中每一个语句的执行次数乘以每一次执行所需的时间的总和。

空间复杂度是算法对空间占用的量度。

（一般在考虑空间复杂度时，只估算算法所需增添的辅助空间，而对问题中原始数据所占的空间，由于与算法无关，不予考虑。

）5. 时间复杂度的计算：语句2的频度为n-l，语句4的额度为(n-1)(2n+1)＝2n2-n-l，因此时间复杂度T(n)＝O(n2)。

语句3的频度为n，语句7的频度为n2，因此时间复杂度为T(n)＝O(n2)。

【解】语句3的频度不仅与n有关，而且和x及数组A中各分量的值有关。

这时通常考虑最坏的情况，由于while循环的最大次数为n-1，因此时间复杂度为T(n)＝O(n)。

i=1;while(i<=n)i=i*5;【解】设语句“i=i*5;”的频度为x，则5x<=n，x<=log5n，O(log5n)i=0;s=0;while(s<n){i++; s+=i;}【解】i=1,s=1i=2,s=1+2i=3,s=1+2+3,s就是对等差数列求和，因此s=i(i+1)/2<n，其中i就是循环语句的频度，因此O(n)6. 在一个具有n个结点的有序单链表中插入一个新结点，使得链表仍然有序，该算法的时间复杂度是( )A.O(log2n)B.O(1)C.O(n2)D.O(n)(D)7. 如果某线性表中最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。

A.单链表B.双向链表C.单循环链表D.顺序表（D）8. 写出带头结点的双向循环链表L为空表的条件（假设结点包括data, next, prior三个域）：(L==L->Next) && (L==L->Prior)注：L->Next==L->Prior不行，因为表长为1时该条件也成立。

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

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

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

（3）给出上述算法的递归算法。

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

答案：（1）第一步：15 29 135 18 32 1 27 25 5第二步：29 135 18 32 27 25 15 1 5 【1分】第三步：135 32 29 18 27 25 15 5 1 【1分】第四步：135 32 29 27 25 18 15 5 1 【1分】（2）基本思想：首先将待搜索元素v与数组的中间元素进行比较，如果，则在前半部分元素中搜索v；若，则搜索成功；否则在后半部分数组中搜索v。

【2分】非递归算法：输入：递减数组A[left:right]，待搜索元素v。

【1分】输出：v在A中的位置pos，或者不在A中的消息（-1）。

【1分】步骤：【3分】int BinarySearch(int A[],int left,int right,int v){int mid;while (left<=right){mid=int((left+right)/2);if (v==A[mid]) return mid;else if (v>A[mid]) right=mid-1;else left=mid+1;}return -1;}（3）递归算法：输入：递减数组A[left:right]，待搜索元素v。

【1分】输出：v在A中的位置pos，或者不在A中的消息（-1）。

【1分】步骤：【3分】int BinarySearch(int A[],int left,int right,int v){int mid;if (left<=right){mid=int((left+right)/2);if (v==A[mid]) return mid;else if (v>A[mid]) return BinarySearch(A,left,mid-1,v);else return BinarySearch(A,mid+1,right,v);}elsereturn -1;}（4）搜索18：首先与27比较，18<27，在后半部分搜索；再次与18比较，搜索到，返回5。

一．填空题（每空3分，共24分）1．算法的时间复杂性指算法中的执行次数。

2．设D n 表示大小为n 的输入集合，t(I)表示输入为I 时算法的运算时间,p(I)表示输入I 出现的概率，则算法的平均情况下时间复杂性A(n)=。

3.f(n )=n 2+log 50n ，g(n)=2n ×log n ，则O(f(n ))+O(g(n ))=。

4．分治算法的时间复杂性常常满足如下形式的递归方程：⎩⎨⎧>+===00n n , g(n)af(n/c)f(n)n n , d )n (f 其中，g(n)表示。

5．对于下面的确定性快速排序算法，只要在步骤3前通过算法，就可得到一个随机化快速排序算法，获得很好的平均性能。

算法QUICKSORT输入：n 个元素的数组A[1..n]。

输出：按非降序排列的数组A 中的元素。

1.quicksort(1,n)//对A[low..high]中的元素按非降序排序。

2.if low<high then3.w=SPLIT(A,low,high)//算法SPLIT 以A[low]为主元将A[low..high]划分成两部//分，返回主元的新位置。

4.quicksort (A,low,w-1)5.quicksort (A,w+1,high)6．end ifend quicksort6.下面算法的基本运算是运算，该算法的时间复杂性阶为Θ()。

算法SPLIT输入：正整数n ，数组A[1..n]。

SPLIT ：i=1x=A[1]for j=2to nif A[j]<=x theni=i+1if i ≠j then A[i]↔A[j]end ifend forA[i]↔A[1]w =ireturn w,A厦门大学《算法分析》课程试卷软件学院软件工程系08级软件工程专业主考教师：刘昆宏试卷类型：（A 卷）//end SPLIT7.假设某算法的T(n)=5×2n，在某台机上实现并完成该算法的时间为t秒。

第6章课后作业结题报告第一题：给定n种物品和一个背包，物品i(1≤i≤n)的重量是wi，其价值为vi，背包的容量为C，对每种物品只有两种选择：装入背包或者不装入背包。

如何选择装入背包的物品，使得装入背包中物品的总价值最大？这是一道老生常谈的背包问题，属于入门dp（Dynamic Programming动态规划）, 首先给出状态转移方程，设dp[i][j]表示用大小为j的背包去装前i个所能获得的最大价值, w[i]表示第i个物品的体积，v[i]表示第i个物品的价值。

关于第i个物品的决策，就是间单的”取与不取”，我们很容易得到如下的状态转移方程:dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);这边dp[i-1][j]表示第i个物品不取，dp[i-1][j-w[i]]+v[i]表示第i个物品取因为每次推导只用的到i-1维，我们其实可以只用一维的滚动数组就可以来求解。

这时候要逆序求解，这边不多做介绍接下来是打印路径问题，这个需要逆序贪心打印。

第i个背包是否选取应该用dp[i][V]与dp[i-1][V]来比较，从而求解，dp[i][V]>dp[i-1][V]，V表示当前可存在的最大容量。

根据贪心，容量V越大价值同样装前i个一定更优，后面的推导的正解一定是基于dp[i][V]的，所以可以这么选标程如下：#include <stdio.h>#include <algorithm>using namespace std;int dp[110][1010];int n, c, ans[110];int w[110], v[110];void print(){int i, j, k;k=c;for(i=n; i>=1; i--){if(dp[i][k]!=dp[i-1][k]){ans[i]=1;k=k-w[i];}else{}}return;}int main(){int i, j, k;scanf("%d%d", &n, &c);for(i=1; i<=n; i++){scanf("%d%d", &w[i], &v[i]);}for(i=1; i<=n; i++){for(j=1; j<=c; j++){dp[i][j]=dp[i-1][j];if(j>=w[i]){dp[i][j]=max(dp[i-1][j-w[i]]+v[i], dp[i][j]);}}}printf("%d\n", dp[n][c]);print();for(i=1; i<=n; i++) {printf("%d\n", ans[i]);}return 0;}第二题：设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。

《C语言》：（一）、C程序的组成和书写规则1、主函数main()和其他函数2、程序的书写格式（二）、数据类型1、基本类型整型、实型（单精度和双精度）和字符型基本类型常量的表示方法2、导出类型数组（一维数组和二维数组的定义及应用）结构体（类型、变量和数组的定义及应用）枚举和共用体的概念指针类型（各种数据类型指针的定义和应用）3、各种类型变量的说明和初值（三）、编译预处理（四）、运算符和表达式1、运算符的优先级、结合性和副作用2、表达式的组成规则和求值顺序3、表达式运算中的隐式类型转换和强制类型转换（五）、语句1、基本语句（简单语句、复合语句、空语句、说明语句）2、选择结构语句（if, switch）3、循环结构语句（while, do-while, for）4、转向语句（break, continue, goto）（六）、函数定义和调用1、返回不同类型值（包括指针）的函数的定义方法2、函数的调用（包括自定义函数的库函数）3、函数的参数传递传值调用、传址（指针参数）调用（七）、变量的存储类别1、变量存储类别的概念（自动、寄存器、静态和外部）2、变量的生存期和有效期《数据结构》：（一）算法和算法分析1. 算法的概念2. 算法效率的度量：时-空复杂度分析（二）数组结构1. 稀疏矩阵的数组表示2. 字符串模式匹配（三）线性链表1. 单链表的表示与实现2. 循环链表3. 双向链表（四）栈与队列1. 栈与队列的数组表示2. 栈与队列的动态链接表示（五）树1. 树的定义与表示方法2. 二叉树的定义与基本性质3. 遍历二叉树和线索二叉树4. 二叉树和森林的转换（六）图1. 图的定义和术语2. 图的存储结构3. 深度优先、广度优先搜索4. 最小生成树5. 最短路径问题（七）内部排序1. 简单选择排序2. 堆排序3. 插入排序4. 快速排序5. 归并排序6. 基数排序（八）哈希表1. 哈希表的定义2. 哈希函数的构造3. 冲突处理参考书：1、《C程序设计》谭浩强编，清华大学出版社2、《数据结构 (C 语言版 ) 》严蔚敏、吴伟民编著，清华大学出版社。

2025考研|厦门大学计算机科学与技术综合考情分析：招生目录、录取情况、拟录名单、复试流程计算机科学与技术是一个计算机系统与网络兼顾的计算机学科宽口径专业，旨在培养具有良好的科学素养，具有自主学习意识和创新意识，科学型和工程型相结合的计算机专业高水平工程技术人才。

随着互联网的不断发展，计算机行业也变得越来越火热，计算机科学与技术专业成为了考研的热门专业。

对于准备报考计算机科学与技术专业研究生的学生来说，了解计算机科学与技术专业考研院校是十分必要的。

研晟考研将为大家整理了厦门大学计算机科学与技术专业考情分析，一起来看一下吧！01.院校综合情况计算机科学与技术系拥有完整的高端人才培养体系，包括博士后科研流动站、工学博士、工程博士、工学硕士及工学学士授予点，招收博士生、学术型、专业型硕士生及计算机技术工程硕士生、本科生等。

计算机系涵盖两个一级学科：计算机科学与技术，网络空间安全。

三个二级学科：计算机应用技术，计算机软件与理论，计算机体系结构。

计算机科学与技术为福建省重点一级学科,计算机软件与理论及软件工程为省重点二级学科，是国家“卓越工程师计划”人才培养单位，计算机科学与技术本科专业为国家一流本科专业。

曾先后获得国家“211工程”一期、二期和“985工程”一期、二期创新研究平台项目支持，其中视频与图像信息处理是立项支持的重点研究方向之一。

02.招生目录03.录取情况汇总04.拟录取名单05.复试流程各个高校考研复试流程大同小异，一般包括笔试、面试、机试，笔试和面试涉及到英语。

具体以各院校的复试通知而定。

复试时间一般为两天，不同高校的复试比重有所不同，通常考研复试成绩占40%-50%。

根据我国教育部发布的《全国硕士研究生招生工作管理规定》可知，每年我国国内高校考研复试工作通常在录取当年3-4月底前完成。

每年考研复试的时间预计不会有太大变化,考研的复试流程各大高校也大同小异，时间一般为两天左右。

具体复试步骤如下1、笔试环节：笔试部分包括英语和专业课的考查。