中南大学09级线性代数试卷A[1]
![中南大学09级线性代数试卷A[1]](https://img.wendangku.net/img13/0lhiishz6qphz8k38gy-31.webp)
![中南大学09级线性代数试卷A[1]](https://img.wendangku.net/img13/0lhiishz6qphz8k38gy-e2.webp)
中南大学考试试卷
2009——2010学年第二学期（2010.5）
时间：100分钟
《线性代数》
课程32学时2学分
考试形式：闭卷
专业年级：2009级
总分：100分
一、填空题（本题15分，每小题3分）
1、已知A 为三阶方阵，且3
1
||=
A ，则=?|)3(|1A 。
2、已知向量T T T T )0,0,0,1(,)0,0,1,1(,)0,1,1,1(,)1,1,1,1(4321====αααα,
则向量T )1,0,2,0(?=β用4321αααα，，，线性表示为
。
3、已知向量组()()()，
，，，，，，，，，，，T
T
T
243102131312321?=?=?=ααα()，，，，T 11344?=α则()=
4321,,,ααααR 。
4、若n 阶方阵A 满足O E A A =+?22，其中E 为n 阶单位矩阵，
则
A 必有特征值
。
5、设三阶方阵A 的特征值为101，，?，则与方阵E A A B 23+?=相似的对角矩阵
为
。
二、选择题（本题15分，每题3分）
1、设B A ,是三阶方阵，已知,2||,1||?==B A 则六阶行列式
B
A O
A ?2=（
）。
（A ）4
?（B ）4
（C ）16
?（D ）16
2、下列命题中正确的是（）
（A ）在线性相关的向量组中，去掉若干向量后所得向量组仍然线性相关；（B ）在线性无关的向量组中，去掉每个向量的最后若干分量后仍然线性无关；
（C ）任何k n +个n 维向量)1(≥k 必然线性相关；
（D ）若只有m k k k ,,,21?全为零时，等式ο
ββαα=+++++m m m m k k k k ??1111才成立，且m ααα,,,21?线性无关，则m βββ,,,21?线性无关。
3、已知非齐次线性方程组B AX =的3个解向量为321,,ηηη，若321)(ηηηk ?+是其导出组O AX =的解向量，则=k （
）。
（A ）3
（B ）2
（C ）1
（D ）0
4、设三阶矩阵A 的三个特征值为1,1,2,且321,,ααα分别为对应的特征向量，则（
）。
（A ）321,,ααα必为矩阵A E ?2的特征向量；（B ）21αα?必为矩阵A E ?2的特征向量；（C ）31αα?必为矩阵A E ?2的特征向量；
（D ）21,αα必为矩阵A E ?2的特征向量，3α不是矩阵A E ?2的特征向量。
5、设n 阶方阵A 与B 相似，则必有（
）。
（A ）A 与B 同时可逆或不可逆；
（B ）A 与B 有相同的特征向量；
（C ）A 和B 均与同一个对角矩阵相似；（D ）矩阵A E ?λ与B E ?λ相等。
三、计算行列式（本题10分）
n
n a a a a 0
00100000
0001000121
???????????，其中n i a i ,,2,1,0?=≠。四、（本题15分）讨论b a ,取何值时，线性方程组
???
???=+?=?+?=+?.
106,132,
2321
321321bx x x x x x a x x x 无解，有惟一解或有无穷多个解？并在有无穷多个解时，写出通解。
五、证明题（本题10分）
设r ααα,,,21?)2(≥r 是数域P 上的线性空间V 中线性无关的向量组，任取P k k k r ∈?121,,?，求证：
,111r k ααβ+=,222r k ααβ+=,?r r r r r r k αβααβ=+=???,111线性无关。
六、（本题10分）设???
?
???????=100010001A ，三阶方阵B 满足E BA BA A 92?=?，其中?A 为A
的伴随矩阵，E 为单位矩阵。求矩阵B 。
七、（本题15分）设三阶实对称矩阵A 的特征值为，，，211?矩阵A 对应的特征向量依次为
T T T )1,0,1(,)1,0,1(,)0,1,0(321?===ααα。
（1）求矩阵A ；（2）求2009A ；
（3）判断A 所对应的二次型是否为正定二次型。
八、（本题10分）设A 为三阶实对称矩阵，二次型AX X f T =经正交变换PY =X 得标准形
2
322214y y y f ?+=，其中),,(321ααα=P ,且T )1,1,1(3
13=
α，试求所作的正交变换。
中南大学2014算法试卷及答案分析
中南大学考试试卷 2013 -- 2014学年下学期时间100分钟 2014 年6 月6日 算法分析与设计课程 48 学时 3 学分考试形式：闭卷 专业年级：12级计算机、信安、物联本科生，总分100分，占总评成绩70 % 注：此页不作答题纸，请将答案写在答题纸上 一、简答题（本题30分，每小题5分） 1、陈述算法在最坏情况下的时间复杂度和平均时间复杂度；这两种评估算法复杂性的方 法各自有什么实际意义？ 1最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。意义：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长2平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。意义：在输入不同的情况下算法的运行时间复杂度可能会发生变化。平均时间复杂度给出了算法的期望运行时间，有助于算法好坏的评价以及在不同算法之间比较时有一个统一标准 2、简单描述分治法的基本思想。 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。 3、何谓最优子结构性质？ 如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。 4、何谓P、NP、NPC问题 P(Polynomial问题)：也即是多项式复杂程度的问题。 NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。 NPC(NP Complete)问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。 5、试比较回溯法与分支限界法。 1、引言 1.1回溯法 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。这种以深度优先方式系统搜索问题解的算法称为回溯法。
中南大学线性代数试卷
考试试卷1 闭卷考试时间：100分钟 一、填空题（本题15分，每小题3分） 1、设()4321,,,A A A A A =为四阶方阵，其中)4,3,2,1(=i A i 为A 的第i 个列向量, 令()14433221,,,A A A A A A A A B ----=，则=B 。 2、设A 为三阶方阵，*A 为A 的伴随矩阵，且3||=A ，则=-*|)(|1A 。 3、设??? ? ? ??-----=2531312311 112t t A ，且2)(=A R ，则=t 。 4、若n 阶方阵A 有特征值λ，则E a A a A a A A f k k k 011 1)(++++=-- 必有 特征值 。 5、若二次型yz xz axy z y x f 2223222+++++=经正交变换化为2 2214y y f +=， 则=a 。 二、选择题（本题15分，每题3分） 1、设A 是n 阶方阵，则0||=A 的必要条件是（ ）。 （A ）A 中两行（列）元素对应成比例； （B ）A 中有一行元素全为零； （C ）任一行元素为其余行的线性组合； （D ）必有一行元素为其余行的线性组合。 2、设A 是n 阶对称阵，B 是n 阶反对称阵，则下列矩阵中反对称矩阵是（ ） （A ）BAB ； （B ）ABA ； （C ）ABAB ； （D ）BABA 。 3、设向量组()()()，，，，，，，，，T T T t 31321111321===ααα当=t （ ）时，向量组3 21ααα，，线性相关。 （A ）5 （B ）4 （C ）3 （D ）2 4、设A 为34?矩阵，321,,ηηη是非齐次线性方程组b Ax =的3个线性无关的解向量， 21,k k 为任意常数，则非齐次线性方程组b Ax =的通解为（ ）。 （A ） )(21213 2ηηηη-++k ； （B ） )(21213 2ηηηη-+-k ； （C ）)()(213212132ηηηηηη-+-++k k ； （D ）)()(2 1321213 2ηηηηηη-+-+-k k 。
2014年12月中南大学网络教育课程考试：算法分析与设计作业参考答案
《算法分析与设计》作业参考答案 作业一 一、名词解释： 1.递归算法：直接或间接地调用自身的算法称为递归算法。 2.程序：程序是算法用某种程序设计语言的具体实现。 二、简答题： 1.算法需要满足哪些性质？简述之。 答：算法是若干指令的有穷序列，满足性质： （1）输入：有零个或多个外部量作为算法的输入。（2）输出：算法产生至少一个量作为输出。 （3）确定性：组成算法的每条指令清晰、无歧义。 （4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 2.简要分析分治法能解决的问题具有的特征。 答：分析分治法能解决的问题主要具有如下特征： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 答：将递归算法转化为非递归算法的方法主要有： （1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归， 只不过人工做了本来由编译器做的事情，优化效果不明显。（2）用递推来实现递归函数。 （3）通过Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。 三、算法编写及算法应用分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 do for j ←1 to n-i do if a[j] 中南大学考试试卷 2012 -- 2013学年上学期时间120分钟2013 年1 月4日 算法分析与设计课程48 学时3 学分考试形式：闭卷 专业年级：10级计算机、信安、物联本科生，总分100分，占总评成绩70 % 注：此页不作答题纸，请将答案写在答题纸上 1. (15分)本期学了很多类算法，请针对以下几类设计策略，举出相应的例子，详细描述算法细节，以说明它们为什么是属于相应的设计策略？ （1）分治法 （2）动态规划 （3）贪心策略 2. （30分）请判断下列陈述是否正确。 （1）根据Master定理，可得到递归式T(n)=4T(n/2)+n2的解为T(n)=O(n2logn). （2）归并排序在最好情况下的时间复杂度为O(nlogn). （3）具有n个结点的二叉排序树的树高均为O(logn)。 （4）如果一个问题是NP完全问题，它肯定也是NP问题。 （5）给定n个数，可以在O（n）的时间内找到10个最大数与10个最小数之间的中间数。（6）Kruskal算法利用了动态规划思想寻找给定图中的最小生成树。 （7）n!=O(2n)。 （8）回溯法借鉴了广度优先的策略得到问题的最优解。 （9）对于一个有n个顶点m条边的无向图G，有两个不同的顶点s( t，则在O(m+n)的时间内可以找到s与t之间的最短路径。 （10）在最坏情况下，快速排序耗费O(N2)。 （11）如果图中包含负权值的边，则Dijkstra算法不可适用。 （12）分治法是属于自底向上的算法策略；动态规划是属于自顶向下的算法策略。 （13）有一个算法，将n个整数a1,...,an作为输入，算法的时间复杂度是O(a1+a2+......+an)。它是一个多项式时间算法。 （14）有一个图G=(V,E) ，每条边e∈E的权We>0, 如果一棵生成树T 最小化Σe∈TWe ，那么T 也最小化Σe∈TWe2 ，反之也成立（即图中边的权值都平方后，生成树T仍是这个图的最小生成树）。 （15）给定两个判定性问题Q1、Q2，如果Q1可以在多项式时间内规约到Q2，则Q1和Q2具有同等难度。 3. （20分）算法设计（选做两题） （10分）设计一个算法判断一个多边形是否是凸多边形，并分析你的算法的时间性能(注：（1） 输入是沿着多边形逆时针的顶点系列)。 （2）（10分）给定图G=(V, E)，利用深度优先算法统计图G中连通块的个数。给出统计算法. （3）(10分)给定边加权图G=(V, E)，图G中的最大生成树为图G中所有生成树中权值最大的生成树。设计构造最大生成树的算法 4. （10分）求解下列递归式。T(1)=1. （1）T(n)=2T(n-1)+1 （2）T(n)=T(n/2)+T(n/4)+n2 5. （25分）对于0/1背包问题，给定n个物品，每个物品都具有一定的权重和价值，寻找物品的一个子集，使得当把这些物品放到背包中时，物品的总重量不会超过背包的容量M。 第一章绪论习题练习答案 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 ? 数据：指能够被计算机识别、存储和加工处理的信息载体。 ? 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素 有时可以由若干数据项组成。 ? 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。 ? 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容 :数据的逻辑结构、存储结构和数据的运算。 ? 逻辑结构：指数据元素之间的逻辑关系 ? 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构 ? 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。 栈、队列、串等都是线性结构。 ? 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 答： 例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录（有姓名，学号，身高和体重等 字段）就是一个结点，对于整个表来说，只有一个开始结点（它的前面无记录）和一个终端结点（它的后面无记录），其他的结点则各有一个也只有一个直接前趋和直接后继（它的前面和后面均有且只有一个记录）。这几 个关系就确定了这个表的逻辑结构是线性结构。 这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢即用一片连续的内存单元来存放这些记录（如用数组表示）还是随机存放各结点数据再用指针进行链接呢这就是存储结构的问题。 在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。 常用的存储表示方法有哪几种 答： 常用的存储表示方法有四种 : ? 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。 ? 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构,通常借助于程序语言的指针类型描述。 ? 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引 项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。 ? 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。 设三个函数 f,g,h 分别为 f(n)=100n 3+n2+1000 , g(n)=25n3+5000n2 , h(n)=+5000nlgn 请判断下列关系是否成立： 计算机体系结构课程设计 学院：信息科学与工程学院 专业班级： 指导老师： 学号： 姓名： 目录 实验1 对指令操作码进行霍夫曼编码 (3) 一、实验目的 (3) 二、实验内容 (3) 三、设计思路 (4) 四、关键代码 (4) 五、实验截图 (5) 六、源代码 (5) 实验2 使用LRU 方法更新Cache (8) 一、实验目的 (8) 二、实验内容 (8) 三、设计思路 (9) 四、程序截图 (9) 五、实验代码 (9) 实验总结 (16) 参考文献 (16) 实验1 对指令操作码进行霍夫曼编码一、实验目的 了解和掌握指令编码的基本要求和基本原理 二、实验内容 1. 使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果以及对指令码的长度进行评价。与扩展操作码和等长编码进行比较。 2. 问题描述以及问题分析 举例说明此问题，例如： 下表所示： 对此组指令进行 HUFFMAN 编码正如下图所示： 最后得到的HUFFMAN 编码如下表所示： 最短编码长度为： H=0.45*1+0.30*2+0.15*3+0.05*4+0.03*5+0.01*6+0.01*6=-1.95. 要对指令的操作码进行 HUFFMAN 编码，只要根据指令的各类操作码的出现概率构造HUFFMAN 树再进行 HUFFAM 编码。此过程的难点构造 HUFFMAN 树，进行 HUFFAM 编 码只要对你所生成的 HUFFMAN 树进行中序遍历即可完成编码工作。 三、设计思路 观察上图，不难看出构造 HUFFMAN 树所要做的工作：1、先对各指令操作码的出现概率进行排序，构造一个有序链表。2、再取出两个最小的概率节点相加，生成一个生的节点加入到链表中，同时从两表中删除此两个节点。3、在对链表进行排序，链表是否只有一个节点，是则 HUFFAN 树构造完毕，否则继续做 2 的操作。为此设计一个工作链表（链表的元素时类，此类的功能相当结构。）、HUFFMAN 树节点、HUFFMAN 编码表节点。 四、关键代码 哈夫曼树重点在于如何排列权值大小不同的结点的顺序 private int leafNum; //叶子结点个数 private HaffmanNode[] hnodes; //哈夫曼树的结点数组 public HaffManCode(double[] weight) //构造指定权值集合的哈夫曼树 { int n = weight.length; //n个叶子结点 this.leafNum = n; this.hnodes = new HaffmanNode[2*n-1]; //n个叶子结点的哈夫曼树共有2n-1个结点 for(int i=0; i 应用化学专业本科培养方案 一、专业简介 应用化学学科为湖南省重点学科，是由中国科学院学部委员、原中南矿冶学院院长陈新民教授和配位化学家张祥麟教授倡导和创办的。本学科自成立以来，立足于解决资源、能源、医药和生命科学领域等关系到国民经济发展、国防建设等涉及化学基础及其应用技术等重大问题，开展了以有色金属为研究对象的功能材料化学、能源化学与工艺、有色金属资源化学；以提高人民健康水平为目的的中草药现代化、生物技术等方面的前沿探索及应用技术研究；以及在构建和谐社会的实践中培养和造就高层次的创新型人才。经过近30年的发展，已取得了引人注目的成就，形成了鲜明的学科特色和人才培养模式；已凝炼出功能材料设计与化学组装、化学计量学与中药现代化、选冶药剂分子设计及分离新技术、生物传感及表面分析、储能与应用电化学等五个主要研究方向。 二、培养目标 培养适应我国社会及经济发展需要，具有扎实的化学理论理论知识、良好的科学素养与身心素质、较强的科研能力与实践技能和创新意识，能从事科学研究与工程技术开发的复合型高级人才。毕业后能在高等院校、科研院所、企业和其他单位胜任化学化工、冶金、新能源、资源高效利用、精细化工、食品、环保和军工等领域的工作。 三、培养要求 学生通过对本专业的系统学习，应掌握化学的基本理论和知识，受到应用化学领域实验技能、分析测试技能、计算机应用、科学研究等方面的基本训练，具有开发设计新工艺和研制新产品的基本能力，能胜任相关部门的科学研究、分析检验、生产工艺和组织管理等工作。毕业生应获得以下几方面的知识和能力： 1．掌握本专业必需的数学、物理学的基本知识原理，系统扎实地掌握化学基础理论知识和基本实验技能。 2．掌握必要的工程技术知识及系统分析能力，受到良好的科学思维和科学实验的基础训练，具有较强的综合思维能力，独立分析问题和解决问题的能力。 3．掌握化学工艺、分析化学、生物化学、材料化学等学科的基本理论与知识，具有较强的分析和解决实际问题的能力。能够从事化学化工新理论和新技术的探索、创新与开发，掌握分析检验的基本技能，具有研究、开发新产品和新的分析方法的初步能力。 4．了解化学工业现状及相关产业政策，了解化学学科理论前沿、最新动态及发展方向。具有创新意识，熟悉应用化学领域新理论、新技术、新设备和新型分析仪器、新的分析方法的发展动态。 5．掌握一门外国语，能顺利地阅读和翻译本专业外文技术资料，有较强的听、说、读、写能力。 6．了解计算机基本原理，掌握一种以上计算机语言，能够熟练应用计算机技术。 7．掌握文献检索、资料查询的基本方法，适应现代信息社会的需求。具有一定的科学研究能力。 算法设计与分析基础 ——实验报告 姓名：周建权 学号：0909122820 班级：信安1202 实验一分治 —最近点对 一．问题 Problem Have you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded. In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring. Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0. Input The input consists of several test cases. For each case, the first line contains an integer N (2 <= N <= 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0. Output For each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 decimal places. 二．分析思路 题目是给n个点的坐标，求距离最近的一对点之间距离的一半。第一行是一个数n表示有n个点，接下来n行是n个点的x坐标和y坐标。 首先，假设点是n个，编号为1到n。找一个中间的编号mid，先求出1到mid点的最近距离设为d1，还有mid+1到n的最近距离设为d2。如果说最近点对中的两点都在1-mid 集合中，或者mid+1到n集合中，则d就是最小距离了。但是还有可能的是最近点对中的两点分属这两个集合，若存在，则把这个最近点对的距离记录下来，去更新d。这样就得到最小的距离d了。 三．源代码 #include 中南大学考试试卷答案（补考） 2008 -- 2009学年 2学期时间110分钟算法分析与设计课程 48学时 3学分考试形式：闭卷 专业年级：信安0601-0602 总分100分，占总评成绩70 % 注：此页不作答题纸，请将答案写在答题纸上 一、基本概念题（本大题40分） 1、（6分） 1）顺序结构将运算步骤的时间累计，简单运算只需要1个单位时间。（1分）2）选择结构：计算复杂的情况复杂度。（2分） 3）循环结构：复杂度计量=循环着次数*循环体的时间（2分） 4）函数调用：计算函数的执行时间（1分） 2、设T(n)=n，根据T(n)= O(f（n）)的定义，下列等式是否成立？（4分） 1）T(n)= O(n2) （√） 2）O(n2) = T(n) （×） 3）T(n)= O(log n)+ O(n) （√） 4）T(n) = O(n) *O(log n) （√） 3、与顺序查找算法相比，折半查找算法的时间复杂性有多大程度的降低？ 它是如何提高算法的效率的？（6分） 顺序查找的时间是O(n) ，折半查找O(log n) 降低了一个数量级（2分）采用分治策略，每一次比较可以排除一半的数据。（4分） 4、简述归并排序算法和快速排序算法的分治方法。（6分） 1）归并排序的分治是将数组从中间分开，分别对前后来那个部分进行排序，将排序后的两个数组合并成整个数组的排序。这样分治为递归过程， 直到一个元素时返回。 2）快速排序的分治是选取分割元素，以分割元素为界，将数组分成两部分，一部分小于分割元素，一部分大于分割元素，分别对两部分排序。 5、一般背包问题的贪心算法可以获得最优解吗？物品的选择策略是什么？（6分） 按照p[i]/w[i]≥p[i+1]/w[i+1]排序，选择当前利润/重量比最大的物品，可以获得最优解， 6、Prim算法和Dijkstra算法选择下一个节点的标准分别是什么？对于有负边的 无向图，Prim算法和Dijkstra算法还能保证获得最优解吗？（6 一、判断题 （1）极大似然估计是无偏估计且在所有的无偏估计中方差最小，所以极大似然估计的风险最小。 （2）回归函数A和B，如果A比B更简单，则A几乎一定会比B在测试集上表现更好。 （3）全局线性回归需要利用全部样本点来预测新输入的对应输出值，而局部线性回归只需利用查询点附近的样本来预测输出值。所以全局线性回归比局部线性回归计算代价更高。 （4）Boosting的一个优点是不会过拟合。 （5）在回归分析中，最佳子集选择可以做特征选择，当特征数目较多时计算量大；岭回归和Lasso模型计算量小，且Lasso也可以实现特征选择。 （6）梯度下降有时会陷于局部极小值，但EM算法不会。 （7）支持向量机是判别模型。T （8）ICA方法对于高斯分布的数据也有效。F （9）回归问题属于非监督学习的一种方法。F （10）聚类算法中不需要给出标签y。T 二、考虑一个二分类器问题（Y为1或0），每个训练样本X有两个特征X1、X2（0或1）。给出P（Y=0）=P（Y=1）=0.5，条件概率如下表： 分类器预测的结果错误的概率为期望错误率，Y是样本类别的实际值，Y'（X1，X2）为样本类别的预测值，那么期望错误率为： （2）计算给定特征（X1，X2）预测Y的期望错误率，假设贝叶斯分类器从无限的训练样本中学习所得。 （3）下面哪个有更小的期望错误率？ a、仅仅给出X1，采用贝叶斯分类器预测Y。 b、仅仅给出X2，采用贝叶斯分类器预测Y。 （4）给出一个新的特征X3，X3的与X2保持完全相同，现在计算给定（X1，X2，X3）采用贝叶斯分类器预测Y的期望错误率，假设分类器从无限的训练数据中学习所得。 （5）使用贝叶斯分类器会产生什么问题，为什么？ 机械设计制造及其自动化专业本科培养方 一、专业简介 本专业依托中南大学“机械工程”国家一级重点学科和“高性能复杂制造” 国家重点实验室，2001 年被确定为省重点专业，并在省“十五” 重点学科建设验收中被评为优秀，2009 年被评为国家特色专业。本专业下设“机械电子工程” 、“机械制造及其自动化” 、“机械设计”、“现代装备设计与控制” 、“模具设计与制造” 、“材料成型及控制” 6 个专业方向，具有博士、硕士学位授予权与博士后流动站，拥有以中国工程院院士、973 首席科学家、长江 学者为代表的强大的师资队伍，和以山河智能为代表的一批学科性公司，在复杂装备与极端制造领域拥有学科特色与行业优势。 二、培养目标贯彻“宽口径、厚基础、强实践、重创新”的培养方针，以社会需求为导向，以实际工程为背景，以工程技术为主线，结合机电工程学院在复杂装备与极端制造工程学科上的优势和特色，着力培养具有良好的思想品质与职业道德，掌握坚实的基础理论、系统的专业知识及丰富的生产实践，了解本学科前沿发展动态和方向，并具备较强的工程实践能力、自我获取知识能力、创新思维及设计能力、组织管理能力、团队协作能力和国际视野的机械工程领域高素质人才。 本专业毕业的学生，主要在现代制造及相关领域从事机电产品设计与制造、机电系统研究与开发、设备运行与维护、生产技术管理、企业市场运营等工作，也可在高等院校、科研院所从事相关教学与科研工作。 三、培养要求 按本方案培养的学生应具备的知识、能力和素质为：1．德、智、体、美全面发展，具有良好的沟通能力、协调组织能力和较强的团队合作精神。 2．具有较扎实的自然科学基础，较好的人文、艺术、社会科学基础和良好的心理素质。 3．较系统地掌握本专业领域的技术理论基础知识，主要包括力学、机械学、电工与电子技术、计算机应用、机械设计理论与制造学、自动控制理论与技术、市场经济及企业管理等基础知识。 4．具有本专业必须的设计、制造、运行及管理等方面的综合能力。5．具有本专业领域某个专业方向必须的专业知识，并了解其科学前沿和发展趋势。6．具有初步的科学研究、科技开发及组织管理能力。 7．具有较强的创新意识和获取新知识的能力。 8．能熟练使用一门外语。 四、主干课程和特色课程 主干课程：工程图学、理论力学、材料力学、机械原理、机械设计、电工技术、模拟电子技术、数字电子技术、互换性与测量技术、机械制造工艺学 特色课程：机电传动控制、现代制造装备及其自动化、现代设计方法、金属成形与模具 设计、金属凝固理论与铸造装备、电液比例控制技术 中南大学考试试卷 2008 -- 2009学年 2学期时间110分钟算法分析与设计课程 48学时 3学分考试形式：闭卷 专业年级：信安0601-0602 总分100分，占总评成绩70 % 注：此页不作答题纸，请将答案写在答题纸上 一、基本概念题（本大题40分） 1、一般情况下，如何计算执行顺序、选择、循环、子过程调用结构的运算时间？ （6分）2、设T(n)=n，根据T(n)= O(f（n）)的定义，下列等式是否成立？（4分） 1）T(n)= O(n2) 2）O(n2) = T(n) 3）T(n)= O(log n)+ O(n) 4）T(n) = O(n) *O(log n) 3、与顺序查找算法相比，折半查找算法的时间复杂性有多大程度的降低？ 它是如何提高算法的效率的？（6分） 4、简述归并排序算法和快速排序算法的分治方法。（6分） 5、一般背包问题的贪心算法可以获得最优解吗？物品的选择策略是什么？（6分） 6、Prim算法和Dijkstra算法选择下一个节点的标准分别是什么？对于有负边的无 向图，Prim算法和Dijkstra算法还能保证获得最优解吗？（6分）7、比较回溯法和分支限界法的搜索方式，哪种方法更适合找最优解问题？（6分） 二、分析算法的时间复杂性，需要写出分析过程（本大题20分） 1、用分割元素v将有n个元素的数组分割成元素大于v和小于v的两部分，需要 花多少时间（要讲出道理）。（5分）2、如果修改归并排序算法，将数组分成1/3和2/3大小不等的两部分，分别排序 后再归并，算法的最坏时间复杂度有什么变化？（5分）3、设函数f1、f2和f3的处理时间分别为O(n)、O(n2) 和O(1)，分析下列流程 的时间复杂性： 1)基本结构 procedure A1(int n，b) （4分） if b < 3 then f1 else f2 第9章查找习题练习答案 1.对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较? 答： 设变量max和min用于存放最大元和最小元(的位置)，第一次取两个元素进行比较，大的放入max，小的放入min。从第2次开始，每次取一个元素先和max比较，如果大于max 则以它替换max，并结束本次比较；若小于max则再与min相比较，在最好的情况下，一路比较下去都不用和min相比较，所以这种情况下，至少要进行n-1次比较就能找到最大元和最小元。 2.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度： (1)查找不成功，即表中无关键字等于给定值K的记录； (2)查找成功，即表中有关键字等于给定值K的记录。 答： 查找不成功时，需进行n+1次比较才能确定查找失败。因此平均查找长度为n+1，这时有序表和无序表是一样的。 查找成功时，平均查找长度为(n+1)/2,有序表和无序表也是一样的。因为顺序查找与表的初始序列状态无关。 3.画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。 答： 等概率情况下，查找成功的平均查找长度为： ASL=(1+2*2+3*4+4*8+5*3)/18=3.556 查找失败时，最多的关键字比较次树不超过判定树的深度，此处为5. 4.为什么有序的单链表不能进行折半查找? 答： 因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。 5.设有序表为(a,b,c,e,f,g,i,j,k,p,q),请分别画出对给定值b,g和n进行折半查找的过程。 解： (1)查找b的过程如下(其中方括号表示当前查找区间，圆括号表示当前比较的关键字) 下标： 1 2 3 4 5 6 7 8 9 10 11 12 13 第一次比较：[a b c d e f (g) h i j k p q] 第二次比较：[a b (c) d e f] g h i j k p q 第三次比较：[a (b)]c d e f g h i j k p q 经过三次比较，查找成功。 (2)g的查找过程如下： 机械设计制造及其自动化专业本科培养方 案 一、专业简介 本专业依托中南大学“机械工程”国家一级重点学科和“高性能复杂制造”国家重点实验室，2001年被确定为湖南省重点专业，并在湖南省“十五”重点学科建设验收中被评为优秀，2009年被评为国家特色专业。本专业下设“机械电子工程”、“机械制造及其自动化”、“机械设计”、“现代装备设计与控制”、“模具设计与制造”、“材料成型及控制”6个专业方向，具有博士、硕士学位授予权与博士后流动站，拥有以中国工程院院士、973首席科学家、长江学者为代表的强大的师资队伍，和以山河智能为代表的一批学科性公司，在复杂装备与极端制造领域拥有学科特色与行业优势。 二、培养目标 贯彻“宽口径、厚基础、强实践、重创新”的培养方针，以社会需求为导向，以实际工程为背景，以工程技术为主线，结合机电工程学院在复杂装备与极端制造工程学科上的优势和特色，着力培养具有良好的思想品质与职业道德，掌握坚实的基础理论、系统的专业知识及丰富的生产实践，了解本学科前沿发展动态和方向，并具备较强的工程实践能力、自我获取知识能力、创新思维及设计能力、组织管理能力、团队协作能力和国际视野的机械工程领域高素质人才。 本专业毕业的学生，主要在现代制造及相关领域内从事机电产品设计与制造、机电系统研究与开发、设备运行与维护、生产技术管理、企业市场运营等工作，也可在高等院校、科研院所从事相关教学与科研工作。 三、培养要求 按本方案培养的学生应具备的知识、能力和素质为： 1．德、智、体、美全面发展，具有良好的沟通能力、协调组织能力和较强的团队合作精神。 2．具有较扎实的自然科学基础，较好的人文、艺术、社会科学基础和良好的心理素质。 3．较系统地掌握本专业领域的技术理论基础知识，主要包括力学、机械学、电工与电子技术、计算机应用、机械设计理论与制造学、自动控制理论与技术、市场经济及企业管理等基础知识。 4．具有本专业必须的设计、制造、运行及管理等方面的综合能力。 5．具有本专业领域某个专业方向必须的专业知识，并了解其科学前沿和发展趋势。 6．具有初步的科学研究、科技开发及组织管理能力。 7．具有较强的创新意识和获取新知识的能力。 线性代数习题册答案 第一章行列式 练习一 班级 学号 1．按自然数从小到大为标准次序，求下列各排列的逆序数： （1）τ(3421)= 5 ; （2）τ(135642)= 6 ; （3）τ(13…(2n-1)(2n)…42) = 2+4+6+…+（2 n-2）= n（n-1）. 2．由数字1到9组成的排列1274i56j9为偶排列，则i=8 、j= 3 . 3．在四阶行列式中，项 12233441 a a a a的符号为负. 4．003 042 215 =－24 . 5．计算下列行列式： （1） 122 212 221 - -- -- = －1＋（－8）＋（－8）－（－4）－（－4）―（－4）= －5 或 （2） 11 11 11 λ λ λ - - - = －3λ＋1＋1－（－λ）－（－λ）―（－λ） = －3λ＋3λ+2=2 (2)(1) λλ -+ 练习 二 班级 学号 1．已知3阶行列式det()ij a =1，则行列式det()ij a -= －1 . 3 (1)11-?=- 2． 11 1 2 3 44916 = 2 . 3．已知D= 1 01211031 110 1254 --,则41424344A A A A +++= —1 . 用1，1，1，1替换第4行 4． 计算下列行列式： (1) 111a b c a b c a b c +++ = 13233110 1 10 011 ,01 101 11111r r r r c c a b c b c a b c a b c -----+-= =++++++ (2) x y x y y x y x x y x y +++ 第10章内部排序习题练习答案 1.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。 (1) 直接插入排序(2)希尔排序(3)冒泡排序(4)快速排序 (5) 直接选择排序(6) 堆排序(7) 归并排序(8)基数排序 上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。 答： (1)直接插入排序:(方括号表示无序区) 初始态: 265[301 751 129 937 863 742 694 076 438] 第一趟：265 301[751 129 937 863 742 694 076 438] 第二趟：265 301 751[129 937 863 742 694 076 438] 第三趟：129 265 301 751[937 863 742 694 076 438] 第四趟：129 265 301 751 937[863 742 694 076 438] 第五趟：129 265 301 751 863 937[742 694 076 438] 第六趟：129 265 301 742 751 863 937[694 076 438] 第七趟：129 265 301 694 742 751 863 937[076 438] 第八趟：076 129 265 301 694 742 751 863 937[438] 第九趟：076 129 265 301 438 694 742 751 863 937 (2)希尔排序(增量为5，3，1) 初始态: 265 301 751 129 937 863 742 694 076 438 第一趟：265 301 694 076 438 863 742 751 129 937 第二趟：076 301 129 265 438 694 742 751 863 937 第三趟：076 129 265 301 438 694 742 751 863 937 (3)冒泡排序(方括号为无序区) 初始态[265 301 751 129 937 863 742 694 076 438] 第一趟：076 [265 301 751 129 937 863 742 694 438] 第二趟：076 129 [265 301 751 438 937 863 742 694] 第三趟：076 129 265 [301 438 694 751 937 863 742] 第四趟：076 129 265 301 [438 694 742 751 937 863] 第五趟：076 129 265 301 438 [694 742 751 863 937] 第六趟：076 129 265 301 438 694 742 751 863 937 (4)快速排序：（方括号表示无序区，层表示对应的递归树的层数） 无机非金属材料工程专业本科培养方案 一、专业简介 无机非金属材料工程专业于1995年正式招生，所属一级学科为材料科学与工程，国家A++级专业，湖南省重点专业和湖南省特色专业。专业具有优良的教学、科研条件，拥有1000余平方米的功能实验区和国家级实验教学中心，拥有原子力显微镜、X射线粉末衍射仪、显微图像仪、比表面孔径测试仪、综合力学性能测试仪等结构和性能表征设备，先后在中国建材南方公司、海螺公司、广西渔峰水泥公司、旗滨公司、新华联、湖南航天磁材、湘福建材、兖矿北海高岭土公司等公司建立了实习基地，拥有教职员工16人，15人拥有博士学位，其中两院院士2人，教授5人，副教授5人，讲师3人。立足行业领域，坚持学科交叉，为矿物材料、建筑材料、资源高效利用和功能材料领域培养高级专门人才。 二、培养目标 培养适应社会主义建设需要，德、智、体、美全面发展，具有较强的知识获取能力、实践能力和创新创业能力，具备无机非金属材料工程的基础理论、基本知识、工程技术和研究技能，能从事无机非金属材料生产、质量控制和性能改进、非金属矿物深加工、新型无机材料的开发与设计等无机非金属材料工程及其相关领域的工艺和工程设计、技术开发和改造、科学研究和教学、生产和管理等方面工作的创新型高级工程技术人才。 三、培养要求 主要强化无机非金属材料工程的基础理论、基本知识和基本技能的学习，掌握无机非金属材料的专业知识和专业技术(结构性能、生产工艺和设备、实验研究、设计方法)，应用开发技术、经济管理、相关的机电及计算机知识等，接受科学思维、科学实验以及工程实践能力方面的基本训练，具有运用其基础理论、基本知识和实验技能进行高新无机非金属材料研究创新和技术开发的能力。毕业生应获得以下几方面的知识和能力： (1)系统地掌握数学、物理、化学等自然科学基础知识，了解一定的人文社会科学和管理科学基础知识； (2)掌握本专业所需的工程制图、电工及电子技术、信息及网络技术、计算机应用等方面的基本知识和技能； (3)熟练掌握一门外语，具有听、说、写、译、阅读基本能力； (4)全面系统地掌握无机非金属材料专业的基础理论、生产工艺和无机非金属材料工厂设计的基本知识和基本技能，主要包括：无机非金属材料基础知识、无机非金属材料制备与加工专业知识、无机非金属材料结构性能表征和分析以及控制方法、无机非金属材料工厂设计及设备选型配置能力、无机非金属材料科学的研究方法和测试技术； (5)具备本专业所需的设计、计算、测试、调研、文献查阅、科学研究和实验操作等基本技能，初步掌握科学研究的能力； (6)掌握无机非金属材料生产工厂工程设计方法，并具有进行工厂工艺设计的能力；中南大学算法试卷
中南大学数据结构与算法
中南大学 计算机体系结构实验报告
中南大学应用化学专业本科培养方案
中南大学算法实验报告
算法分析与设计试卷
机器学习试卷——中南大学
中南大学_机械设计制造和自动化专业本科培养方案12
中南大学算法考试试卷及答案
中南大学数据结构与算法第9章查找课后作业答案..
中南大学——机械设计制造及其自动化专业本科培养方案
线性代数习题册(答案)
中南大学数据结构与算法第10章内部排序课后作业答案要点
中南大学无机非金属材料工程专业本科培养方案