最新中南大学数据结构与算法-绪论课后作业答案

1、仅供学习与交流第一章绪论习题练习答案1.1简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构' 存储结构、线性结构、非线性结构.数据：指能够被计算机识别、存储和加工处理的信息载体。数据元索：就是数据的基本单位，在某些情况下，数据元索也称为元索、结点、顶点.记录。数据元索 有时可以由若干数据项组成。数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计 语言中已实现的数据结构。数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结 构、存储结构和数据的运算。逻辑结构：指数据元素之间的逻辑关系。存储结构：数据元

2、索及其关系在计算机存储器内的表示，称为数据的存储结构.线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一 个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构C 栈、队列、串等都是线性结构。非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。 数组、广义表、树和图等数据结构都是非线性结构。1.2试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。答：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体垂等各项体检信息。这张登记表中， 每个学生的各项体检信息

3、排在一行上。这个表就是一个数据结构。每个记录（有姓名，学号，身高和体垂等 字段）就是一个结点，对于整个表来说，只有一个开始结点（它的前面无记录）和一个终端结点（它的后面无 记录），其他的结点则各有一个也只有一个直接前趋和直接后继（它的前面和后面均有且只有一个记录）。这 几个关系就确定了这个表的逻辑结构是线性结构。这个表中的数据如何存储到计算机里，并且如何表示数据元索之间的关系呢？即用一片连续的内存单 元来存放这些记录（如用数组表示）还是随机存放各结点数据再用扌旨针进行链接呢？这就是存储结构的问 题。在这个表的杲种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作C对这个表 可以进

4、行哪些操作以及如何实现这些操作就是数据的运算问题了。1.3常用的存储表示方法有哪几种？答：常用的存储表示方法有四种：顺序存储方法：它是把逻辑上相邻的结点存储在物理位這相邻的存储单元里，结点间的逻辑关系由存 储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。链接存储方法：它不要求逻辑上相邻的结点在物理位這上亦相邻，结点间的逻辑关系是由附加的指针 字段表示。由此得到的存储表示称为链式存储结构通帛借助于程序语言的指针类型描述。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引 项由结点的关键字和地址组成。若每个结点在索引表中

5、都有一个索引项，则该索引表称之为稠密索引(Dense Index) o若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。散列存储方法：就是根据结点的关键字直接计算岀该结点的存储地址。1.4 设三个函数 f.g.h 分别为 f(n)h00!?+M000 g (n) =25n3+5000n2 , h (n) =n'6+5000n I gn 请判断下列 关系是否成立：(1) f(n)=0(g(n)(2) g(n)=0(f(n) h(n)=0(n，5) h (n) =0 (n I gn)分析：数学符号“0“的严格的数学定义：若T (n)和f (n)是定义在正整数集合上的两个函数，则

6、T (n) =0 (f (n)表示存在正的常数C和n0, 使得当nMnO时都满足OWT (n) WCf (n) o通俗地说，就是当时，f(n)的函数值增长速度与T (n)的增长速度同阶。一般，一个函数的增长 速度与该函数的最高次阶同阶。即：0(f(n)=n30(g (n)=n30(h(n)=n5所以答案为: 收集于网络，如有侵权请联系管理员删除仅供学习与交流答： (1)成立。 (2)成立。 (3)成立。 (4)不成立。1.5设有两个算法在同一机器上运行，其执行时间分别为100(和2：要使前者快于后者，n至少要多大? 分析：要使前者快于后者，即前者的时间消耗低于后者，即：100n2<2n求

7、解上式，可得答：n=151.6设n为正整数，利用大"(T记号，将下列程序段的执行时间表示为n的函数。(1) i=1； k=0;wh i I e (i <n) k=k+10*i;i+：分析：k=0; /1while(i<n) /n k=k+10*i: /n-1/n-1由以上列岀的各语句的频度，可得该程序段的时间消耗:T(n) =1+1+n+(n-1) + (n-1)=3n可表示为T(n) =0(n)(2) i=0; k=0;do(k=k+10*i: i+;whiIe (i <n):分析：i=0; /1k=0; /1do /nk=k+10*i: /n收集于网络，如有侵权

8、请联系管理员删除仅供学习与交流i*; /n)wh iIe (i <n);/n由以上列岀的各语句的频度，可得该程序段的时间消耗：T(n)=1+1+n+n+n+n=4n+2可表示为T(n) =0(n) i=1； j=0;v/hi le(i+j<=n)if (i>j) j*+；else i+：分析：通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i*j的值加Io该程序段的主要时间消耗是While循环，而while循环共做了 n次，所以该程序段的执行时间为：T(n)=O(n)while (x>=(y+1)* (y+1)y+;分析：由x=n且x的值在程

9、序中不变，又while的循环条件(x>=(y+1)*(y+D)可知：当(y+1)*(y+1)刚超过n的值时退出循环。由(y+1)*(y+1)<n 得：y<n'O. 5-1所以，该程序段的执行时间为：向下取整(rT05T)(5) x=91; y=100;while(y>0)if(x>100)(x=x-10:y一；else x*+;分析：x=91; /1y=100; /1whi le(y>0) /1101收集于网络，如有侵权请联系管理员删除仅供学习与交流if(x>100) /1100x=x-10： /100y： /100elsex+: /1000以

10、上程序段右侧列出了执行次数。该程序段的执行时间为：T(n)=0(1)1.7算法的时间复杂度仅与问题的规模相关吗？答：算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其 时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复 杂度为准的。1.8按増长率由小至大的颇序排列下列各函数：2100. (3/2) (2/3)n, nr ,n05 . n! , 2n , lgn f J n,a?2)答：常见的时间复杂度按数屋级递増排列依次为:常数阶0(1)、对数阶0(log；n)x线性阶0(n)、线性对数阶0 Slogan)、平方阶

11、0 ()、立方阶OS3)、k次方阶0 (nk).指数阶0(2%先将题中的函数分成如下几类:常数阶：2100对数阶:IgnK次方阶:n叭严指数阶(按指数由小到大排)：十、(3/2) 2 nL nn注意：(2/3)"由于底数小于1,所以是一个递减函数，其数屋级应小于常数阶。根据以上分析按增长率由小至大的顺序可排列如下：(2/3)n < 21W < Ign < n05 < noz2> < n，in < (3/2)n < 2ft < n! < nn1.9有时为了比较两个同数级算法的优劣.须突出主项的常数因子.而将低次项用大”0“记号

12、表示.例 如.设 L (n) =1.39n I gn+100n+256=1. 39n I gn+O (n) r T, (n) =2. On I gn-2n=2 OlgrrH)(n),这两个式子表示.当 n足够大时T,(n)优于TNn),因为前者的常数因子小于后者.谓用此方法表示下列函数，并指出当n足够 大时，哪一个较优，哪一个较劣？函数(1) Ti (n) =5n2-3n+601 gn(2) T2(n)=3n2+1000n+3lgn T3(n)=8n2+3lgn(4) T4 (n) =1 5n2+6000n I gn大“0”表示优劣5rA0 (n)较差3十0 (n)其次8n*+0(lgn)最差

13、1.5n*+0(nlgn)最优浅谈中小企业人力资源管理与开发的重要性前言随着我国经济的发展中小企业也在市场竞争中蓬勃发展，在我国经济发展中的地位和作用越來越明显。它为我国劳动者提供了大址的就业岗位.缓解了严峻的就业趋势促进了劳动力市场的发展.创造了大址 的社会财富.取得了良好的社会利益C中小企业自身持征互补了大企业集团不能够解决的问题.在市场经 济条件下.灵活的优势使其具有较大的竞争力，近几年來.发展速度飞快。爪在发展过程中，凸显了一系 列的问题.尤其是在人力资源管理与开发方面。人才是21世纪企业最宝贵的资源，中小企业想在同行中间站稳脚跟并不断前进就处耍重视企业的人力资源 管理与开发与管理因此

14、如何有效的开发和科学的管理人力资源成为中小企业走向成功的关键.也成为企 业提商效率、保证自身竞争优魁的强有力的武器。木文从中小企业人力资源管理与开发的重要性出发，分 析了中小企业人力资源管理与开发的现状及存在问趣并提出相应对策。一、中小企业人力资源管理与开发的重要性X今知识经济时代.人力资源的管埋与开发已然变成企业管埋匸作的重要组成部分.是企业获得长足、稳 定发展具有决定性影响的因素。通过有效的人力资源管理与开发.将促进员匸积极参与企业经营，并把它 与员工个人目标结合起來.达到企业与员工“共赢"状态，使得企业蓬勃发展。（一）人力资源管理与开发可以有效促进企业的竞争能力提升现在社会发展

15、尤为迅速，企业面对的不仅仅是來自市场外激烈的竞争.还存在有内部的竞争。人力资源管 理与开发可有效协调和改善企业内部人员和匚作管理，从而获得更女的资源优势以及増加可竞争的资本。 伏I此.人力资源管理与开发可以有效提升企业的竞争力。（二）人力资源管理与开发可促进企业重要职能的充分发挥人力资源管理与开发不仅可以有效提升企业的竞争能力，还可以促进企业中重婆职能的充分发挥C人力资 源管理与开发可以有效培养和开发出更女人的聪明才智，将其潜能充分发掘出來.从而有效优化配宜人力 资源.发挥和做好各项职能工作，有力的保障了企业中各项职能的充分发挥。因此，人力资源管理与开发 是有效促进企业中重要职能的充分发挥的重要保障。（三）人力资源管理与开发可以促进企业人力资源管理进一步发展人力资源管理与开发为企业提供更女人才优势，创适更弱价值，閃此对人力资源进行管理开发是企业更好 为社会公益服务、为国民经济发展提供r前进的动力。对企业人力资源的合理有效开发.可以让其在企业 中充分发挥自身优魁.提商讯位内部管理质址以及人才的平均专业素质。因此，人力资源的合理有效开发. 可以促进企业人力资源管理的进一步发展。二、企业人力资源管理与开发存在的问題（-）人力资源的战略规划存在的问題中小企业在制定发展战略时.往往忽视人力资源规划，也不考虑木企业的人力资源状况及木企业的人力资 源体系能否有效的