复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i
数据结构知识点概括 第一章概论 数据就就是指能够被计算机识别、存储与加工处理得信息得载体。 数据元素就是数据得基本单位,可以由若干个数据项组成。数据项就是具有独立含义得最小标识单位。 数据结构得定义: ·逻辑结构:从逻辑结构上描述数据，独立于计算机.·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：就是逻辑结构用计算机语言得实现。·顺序存储结构:如数组。 ·链式存储结构:如链表。 ·索引存储结构：·稠密索引:每个结点都有索引项。 ·稀疏索引：每组结点都有索引项. ·散列存储结构:如散列表。 ·数据运算。 ·对数据得操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用得有:检索、插入、删除、更新、排序。 数据类型:就是一个值得集合以及在这些值上定义得一组操作得总称. ·结构类型:由用户借助于描述机制定义,就是导出类型。 抽象数据类型ＡDＴ:·就是抽象数据得组织与与之得操作。相当于在概念层上描述问题. ·优点就是将数据与操作封装在一起实现了信息隐藏. 程序设计得实质就是对实际问题选择一种好得数据结构，设计一个好得算法.算法取决于数据结构。 算法就是一个良定义得计算过程，以一个或多个值输入,并以一个或多个值输出．评价算法得好坏得因素：·算法就是正确得; ·执行算法得时间; ·执行算法得存储空间(主要就是辅助存储空间); ·算法易于理解、编码、调试。 时间复杂度：就是某个算法得时间耗费，它就是该算法所求解问题规模ｎ得函数. 渐近时间复杂度:就是指当问题规模趋向无穷大时,该算法时间复杂度得数量级。 评价一个算法得时间性能时，主要标准就就是算法得渐近时间复杂度。 算法中语句得频度不仅与问题规模有关,还与输入实例中各元素得取值相关。 时间复杂度按数量级递增排列依次为:常数阶Ｏ（1)、对数阶O（lｏg2n）、线性阶O（n)、线性对数阶O(nｌog2n)、平方阶O(ｎ＾2)、立方阶Ｏ(n^3）、……ｋ次方阶O(ｎ＾k)、指数阶O(2^n)。 空间复杂度:就是某个算法得空间耗费，它就是该算法所求解问题规模n得函数。 算法得时间复杂度与空间复杂度合称算法复杂度。 第二章线性表 线性表就是由n≥0个数据元素组成得有限序列. ｎ=0就是空表；非空表,只能有一个开始结点，有且只能有一个终端结点。 线性表上定义得基本运算: ·构造空表:Initｌist(Ｌ) ·求表长：Ｌiｓtlengｔh(L) ·取结点:GｅtNodｅ(Ｌ，i) ·查找:LoｃａｔeNodｅ(L,ｘ) ·插入:IｎsertＬｉsｔ(L,x,i) ·删除:Ｄeｌｅte（L,i） 顺序表就是按线性表得逻辑结构次序依次存放在一组地址连续得存储单元中。在存储单元中得各元素得物理位置与 逻辑结构中各结点相邻关系就是一致得。地址计算：LOCa(i)=LOCa(1）+(i-1）*d；（首地址为1) 在顺序表中实现得基本运算： ·插入:平均移动结点次数为ｎ/2；平均时间复杂度均为O(n）。 ·删除：平均移动结点次数为(ｎ-1)／２;平均时间复杂度均为O(n)。 线性表得链式存储结构中结点得逻辑次序与物理次序不一定相同，为了能正确表示结点间得逻辑关系,在存储每个结点值得同时,还存储了其后继结点得地址信息(即指针或链）。这两部分信息组成链表中得结点结构。 一个单链表由头指针得名字来命名。 单链表运算: ·建立单链表·头插法：ｓ—〉next=head;heａd=s；生成得顺序与输入顺序相反。平均时间复杂度均为Ｏ(n）。 ·尾插法:heａd=ｒｅar=null;ｉf(head＝nulｌ)hｅaｄ=s;eｌse r—>ｎexｔ=s;ｒ=s; 平均时间复杂度均为O（n) ·加头结点得算法:对开始结点得操作无需特殊处理,统一了空表与非空表。 ·查找·按序号:与查找位置有关，平均时间复杂度均为Ｏ(n）. ·按值：与输入实例有关,平均时间复杂度均为O(ｎ)。 ·插入运算：ｐ=GetNodｅ(Ｌ，i-1);s—〉next=p—〉ｎext;p->ｎext=s；平均时间复杂度均为O(n)
第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（） A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换；
第一章- 飞机结构 摘要：飞机结构是第一章，主要讲述了飞机的机身，机翼，尾翼，起落架，和发动机这几个主要结构部分。 根据美国联邦法规全书(CFR)第14篇第一部分的定义和缩写，飞行器(Aircraft)是一种用于或者可用于飞行的设备。飞行员执照的飞行器分类包括飞机(Airplane)，直升机，气球类(lighter-than-air)，动力升力类(powered-lift)，以及滑翔机。还定义了飞机(Airplane)是由引擎驱动的，比空气重的固定翼飞行器，在飞行中由作用于机翼上的空气动态反作用力支持。本章简单介绍飞机和它的主要组成部分。主要组成部分 尽管飞机可以设计用于很多不同的目的，大多数还是有相同的主要结构。它的总体特性大部分由最初的设计目标确定。大部分飞机结构包含机身，机翼，尾翼，起落架和发动机。 机身
机身包含驾驶舱和/或客舱，其中有供乘客使用的坐位和飞机的控制装置。另外，机身可能也提供货舱和其他主要飞机部件的挂载点。一些飞行器使用开放的桁架结构。桁架型机身用钢或者铝质管子构造。通过把这些管子焊接成一系列三角形来获得强度和刚性，成为桁架结构。图1-2就是华伦桁架。 华伦桁架结构中有纵梁，斜管子和竖直的管子单元。为降低重量，小飞机一般使用铝合金管子，可能是用螺钉或者铆钉通过连接件铆成一个整体。 随着技术进步，飞行器设计人员开始把桁架单元弄成流线型的飞机以改进性能。在最初使用布料织物来实现的，最终让位于轻金属比如铝。在某些情况下，外壳可以支持所有或者一主要部分的飞行载荷。大多数现代飞机使用称为单体横造或者半单体构造的加强型外壳结构。单体横造设计使用加强的外壳来支持几乎全部的载荷。这种结构非常结识，但是表面不能有凹痕或者变形。这种特性可以很容易的通过一个铝的饮料罐来演示。你可以对饮料罐的两头施加相当的力量管子不受什么损坏。然而，如果罐壁上只有一点凹痕，那么这个罐子就很容易的被扭曲变形。实际的单体造型结构主要由外壳，隔框，防水壁组成。隔框和防水壁形成机身的外形。如图1－3 由于没有支柱，外壳必须足够的坚固以保持机身的刚性。这样，单体造型结构有一个重要的问题，在保持重量在允许的范围内同时要维持足够的力量。由于单体设计的限制，今天的大多数飞机使用半单体造型结构。 半单体造型结构使用飞机外壳可以贴上去的亚结构，亚结构由隔框和不同尺寸的防水隔壁以及桁条组成，通过来自机身的弯曲应力来加固加强的外壳。机身的主要部分也包括机翼挂载
第一章概论习题 一、选择题 1．数据结构是具有【B 】的数据元素的集合。 A．相同性质B．相互关系C．相同运算D．数据项2．在计算机的存储结构中，逻辑上相邻的结点存储在物理位置上也相邻的连续存储单元里，称之为【 B 】。 A．逻辑结构B．顺序存储结构C．链式存储结构D．散列存储结构3．语句for(i=1;i<=n;i++) x++;的时间复杂度为【B 】。 A．O(1) B．O(n) C．O(n2) D．O(n3) 4．下面不属于数据的存储结构的是【D 】。 A．散列存储B．链式存储C．索引存储D．压缩存储5．数据结构研究的是数据的【 A 】及它们之间的相互关系。 A．存储结构和逻辑结构B．存储和抽象C．理想与抽象D．理想与逻辑6．下面程序段的时间复杂度是【D 】。 for(i=0;i<2*n;i++) for(j=1;j<3*n;j++) A[i][j]=0; A．O(n) B．O(5n) C．O(6n2) D．O(n2) 7．数据的逻辑结构有两大类，分别是【 B 】。 A．顺序存储结构和链式存储结构B．线性结构和非线性结构 C．压缩结构和非压缩结构D．有序结构和无序结构 8．以下与数据的存储结构无关的术语是【D 】。 A．循环队列B．链表C．哈希表D．栈 9．算法分析的两个主要方面是【A 】。 A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 10．下面程序段的时间复杂度是【D 】。 S=0; for(i=0;i 第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 数据结构基础知识 标准化文件发布号：（9312-EUATWW-MWUB-WUNN-INNUL-DQQTY- 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 第一章概论 一、名词解释 1.数据表示 2.数据处理 3.数据 4.数据元素 5.逻辑关系 6.逻辑结构 7.结构 8.运算 9.基本运算 10.存储结构 11.顺序存储结构 12.链式存储结构 13.索引存储结构 14.散列存储结构 15.算法 16.运行终止的程序可执行部分 17.伪语言算法 18.非形式算法 19.时空性能 20.时间复杂性 21.数据结构 二、填空题 1.计算机专业人员必须完成的两项基本任务是：_数据表示__和__数据处理__。 2.数据在计算机存储器中的存在形式称为_机内表示_。 3.概括地说，数据结构课程的主要内容包括: 数据的_逻辑结构__、定义在_逻辑结构上的基本运算__、数据的_存储结构和运算__的实现。此外，该课程还要考虑各种结构和实现方法的_评价和选择_。 4.由一种_逻辑性_结构和一组_基本运算_构成的整体是实际问题的一种数学模型，这种数学模型的建立、选择和实现是数据结构的核心问题。 5.存储结构是逻辑结构的_存储_实现。 6.数据表示任务是逐步完成的，即数据表示形式的变化过程是_机外表示_->_逻辑结构_->_存储结构__。 7.数据处理任务也是逐步完成的，即转化过程是_处理要求_->_基本运算和运算_->_算法。 8.从数据结构的观点看，通常所说的"数据"应分成三个不同的层次，即_数据_、_数据元素_和_数据项_。 9.根据需要，数据元素又被称为_元素_、_结点_、_顶点_或_记录_。 10.在有些场合下，数据项又称为_字段_或_域_，它是数据的不可分割的最小标识单位。 11.从某种意义上说，数据、数据元素和数据项实际反映了数据组织的三个层次，数据 可由若干个_数据元素_构成，数据元素可由若干个_数据项_构成。 12.根据数据元素之间关系的不同特性，通常有_集合_、_线性结构_、_树形结构__、_图状结构_四类基本逻辑结构，它们反映了四类基本的数据组织形式。 13.根据操作的效果，可将运算分成以下两种基本类型： ①__加工_型运算，其操作改变了原逻辑结构的“值”，如结点个数、某些结点的内容等； ②__引用_型运算，其操作不改变原逻辑结构，只从中提取某些信息作为运算的结果。 14.将以某种逻辑结构S为操作对象的运算称为“_定义在S上的运算_”，简称“_S上运算_”。 15.一般地，可能存在同一逻辑结构S上的两个运算A和B，A的实现需要或可以利用B，而B 的实现不需要利用A。在这种情况下，称A可以“_归纳_”为B。 16.存储实现的基本目标是建立数据的_机内表示_。 17.一般地，一个存储结构包括_存储结点__、_数据元素之间关联方式的表示_、_附加设施_三个主要部分。 18.通常，存储结点之间可以有_顺序存储方式_、_链式存储方式_、_索引存储方式_、_散列存储方式_四种关联方式，称为四种基本存储方式。 19.可用任何一种存储方式所规定的存储结点之间的关联方式来间接表达给定逻辑 结构S中数据元素之间的逻辑关系。由此得到的存储结构，称为_给定逻辑结构S的存储实现__或_存储映象_。 20.一个运算的实现是指一个完成该运算功能的_程序_。运算实现的核心是处 理步骤的规定，即_算法设计_。 21.任何算法都必须用某种语言加以描述。根据描述算法的语言的不同，可将算法分 为：__运行终止的程序可执行部分_、_伪语言算法_、_非形式算法_三类。 第一章概论练习题 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是的有限集合，R是D上的有限集合。 3. 数据结构包括数据的、数据的和数据的这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是和。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6．在线性结构中，第一个结点前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结点；叶子结点没有结点，其余每个结点的后续结点数可以。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是。 10. 数据的运算最常用的有5种，它们分别是。 11. 一个算法的效率可分为效率和效率。 二、单项选择题 （）1. 非线性结构是数据元素之间存在一种： A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系 （）2. 数据结构中，与所使用的计算机无关的是数据的结构； A) 存储 B) 物理 C) 逻辑 D) 物理和存储 （）3. 算法分析的目的是： A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 （）4. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 （）5. 计算机算法指的是： A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法 （）6. 计算机算法必须具备输入、输出和等5个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 三、简答题 1.数据结构和数据类型两个概念之间有区别吗？ 2. 简述线性结构与非线性结构的不同点。 8576 顺序线性表的基本操作 时间限制:1000MS 内存限制:1000K 提交次数:1714 通过次数:300 题型: 编程题语言: 无限制 Description 编写算法，创建初始化容量为LIST_INIT_SIZE的顺序表T，并实现插入、删除、遍历操作。本题目给出部分代码，请补全内容。 #include for(_________________________) printf("%d ",_________________________); // 请填空 } printf("\n"); return OK; } intListInsert_Sq(SqList&L,inti,int e) { // 算法2.4，在顺序线性表L中第i个位置之前插入新的元素e // i的合法值为1≤i≤L.length +1 // 请补全代码 } intListDelete_Sq(SqList&L,inti, int&e) { // 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值 // i的合法值为1≤i≤L.length // 请补全代码 } int main() { SqList T; int a, i; ElemType e, x; if(_________________________) // 判断顺序表是否创建成功 { printf("A Sequence List Has Created.\n"); } while(1) { printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n"); scanf("%d",&a); switch(a) { case 1: scanf("%d%d",&i,&x); if(_________________________) printf("Insert Error!\n"); // 判断i值是否合法，请填空 elseprintf("The Element %d is Successfully Inserted!\n", x); 第一章绪论 1、简述下列术语：数据、数据元素、数据对象、数据结构、数据存储、存储结构、数据类型和抽象数据类型。 2、数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？ 3、什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。 4、什么叫算法的时间复杂度？怎样表示算法的时间复杂度？ 5、两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？ 6、试画出与下列程序段等价的框图 (1)product = 1; i = 1; while(i <= n){ product * = i ; i++; } (2)i = 0; do{ i++; }while ((i!=n)&&(a[i])!=x); 7、已知如下程序段 for(i=n;n>=1;n--) {语句1} { x++； {语句2} for(j=n;j<=i;j--)FOR j:=n {语句3} y++; {语句4} }； 求语句１到语句４的频度。 8、按增长率从小到大的顺序排列下列各组函数： 2100，（3/2）n，（2/3）n，（4/3）n，n，n3/2，n2/3，n!，n n，log2n，n/log2n，log2(log2n)，n log2n 9、试写一算法，自大至小依次顺序读入的三个整数X,Y,Z的值。 10、假设有A,B,C,D,E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每行的形式为： 项目名称性别校名成绩得分 编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。 11、设求解同一个问题有三种算法，三种算法各自的时间复杂度分别为O(n2)，O(2n)和O(nlg n)，哪种算法最可取？为什么？ 12、设n为已在算法前边定义的整数类型，并已知n为正整数，分析下列各算法中语句的执行次数，并给出各算法的时间复杂度T(n)。 (1) int i = 1, k = 0; while (i < n-1) { k = k + 10 * i; i = i + 1; } (2) int i = 1, k = 0; do { k = k + 10 * i; i = i + 1; }while (i != n); (3) int i = 1, j = 1; while (i <= n && j <= n) { i = i + 1; j = j + 1; } (4) int x = n; /* n > 1 */ int y = 0; while(x >= (y+1)*(y+1)) y++; 飞机结构与系统复习题 飞机结构 1、飞机结构适航性要求的主要指标： A、强度、刚度、稳定性与疲劳性能 B、动强度与疲劳性能 C、抵抗破坏与变形的能力 D、安全系数与剩余强度 2、下列飞机结构中属于重要结构的是： (1|2|3) A、机身和机翼 B、尾翼和操纵面 C、发动机和起落架 D、发动机整流罩、背鳍与腹鳍 3、飞机结构安全寿命设计建立的基础是： A、充分发挥结构的使用价值 B、尽量减少结构的重量 C、结构无裂纹 D、允许结构有裂纹 4、飞机结构损伤容限设计思想是： A、承认结构在使用前带有初始缺陷 B、在服役寿命期内设有可检裂纹 C、结构的剩余强度随使用时间保持不变 D、设计出多路传力结构和安全止裂结构 5、飞机结构耐久性设计的基本要求是： (2|3|4) A、结构具有抵抗疲劳开裂、腐蚀、磨损能力 B、结构经济寿命必须超过一个设计使用寿命 C、低于一个使用寿命期内不出现功能性损伤 D、飞机经济寿命必须通过分析和试验验证 6、飞机结构经济寿命： A、结构到修不好的使用时间 B、结构出现裂纹的工作时间 C、结构第一个大修周期的时间 D、执行耐久性试验计划结果的工作寿命 7、现代民用运输机结构采用何种设计思想： A、安全寿命设计 B、耐久性设计 C、损伤容限设计思想 D、破损安全设计 8、飞机结构的强度是： A、结构抵抗变形的能力 B、结构抗腐蚀的能力 C、结构抵抗破坏的能力 D、结构的稳定性 9、损伤容限结构的分类 A、裂纹缓慢扩展结构 B、破损安全结构 C、限制损伤结果 D、1、2正确 10、飞机结构的刚度是： A、结构抵抗变形的能力 B、结构抗腐蚀的能力 C、结构抵抗破坏的能力 D、结构的稳定性 11、现代运输机飞行中所受的外载荷有： A、集中载荷、分布载荷与动载荷 B、重力、升力、阻力和推力 C、升力、重力、推力、阻力和惯性力 D、座舱增压载荷与疲劳载荷 12、飞机飞行过载定义为： A、气动力比重力 B、升力比阻力 C、推力比阻力 D、升力比重力 13、操纵n过载飞机左转弯右发动机过载： A、等于飞机过载n B、等于n-Δn C、等于n+Δn D、等于n±Δn 14、飞机结构安全系数定义为： A、P设计/P使用 B、P破坏/P设计 C、P破坏/P使用 D、n使用/n设计 15、运输机水平转弯过载值取决于： A、转弯速度大小 B、转弯升力大小 C、转弯半径大小 D、转弯坡度大小 16、某运输机飞行过载为3表明： A、飞机垂直平面曲线飞行，升力是重力3倍 B、升力为正是重力的3倍 C、飞机水平转弯过载为3g D、飞机着陆下滑重力是升力的3倍 17、飞机速度－过载包线表示： A、飞行中ny≤n使用最大 B、飞行中q≤q最大最大 C、空速与各种过载的组合 D、1和2正确 18、操纵n过载飞机抬头时头部发动机过载： A、等于n+Δn B、等于n-Δn C、等于飞机过载n。 D、等于n±Δn 19、飞机过载n使用表明： A、飞行中的最大过载值 第一章概述习题 一、单选题 1、研究数据结构就是研究( D )。 A、数据的逻辑结构 B、数据的存储结构 C、数据的逻辑结构和存储结构 D、数据的逻辑结构、存储结构及其数据在运算上的实现 2、以下说法正确的是(C )。 A、数据元素是数据的最小单位 B、数据项是数据的基本单位 C、数据结构是带有结构的各数据项的集合 D、一些表面上很不相同的数据可以有相同的逻辑结构. 3、在数据结构中，数据的逻辑结构可以分成（C ）。 A. 内部结构和外部结构 B. 紧凑结构和非紧揍结构 C. 线性结构和非线性结构 D. 动态结构和静态结构 4、数据元素及其关系在计算机存储器内的表示，称为数据的（D ）。 A. 线性结构 B. 非线性结构 C. 逻辑结构 D. 存储结构 5、计算机算法必须具备输入、输出、（ B ）等5个特性。 A 可行性、可移植性和可扩展性 B 可行性、确定性和有穷性 C 确定性、有穷性和稳定性 D 易读性、安全性和稳定性 6、下面关于算法的叙述中错误的是（ A ）。 A. 一个算法应有一个或多个输入。 B. 算法最终必须由计算机程序实现 C. 为解决某问题的算法同为该问题编写的程序含义是相同的 D. 算法中的每条指令都必须有明确的含义 7、若一个算法的时间复杂度用T(n)表示，其中n的含义是（C ）。 A. 循环层数 B. 语句条数 C. 问题规模 D. 函数数量 8、下面说法正确的是（A）。 A. 健壮的算法不会因非法的数据输入而出现莫名其妙的状态 B. 程序一定是算法 C. 算法的时间复杂度只依赖于问题的规模 D. 算法的优劣与算法描述语言无关，但与所用计算机有关 9、下面程序段的时间复杂性的数量级为（C ） for (i=1;i<=n;i++) 1.1 程序设计的实质是数据表示和数据处理。 1.2数据要能被计算机加工处理，首先必须能够存储在机器中，成为能被机器直接操作的对象。数据在计算机存储器中的这种存在形式称为机内表示。将数据从机外表示转化为机内表示，这项任务称为数据表示。 1.3用适当的可执行语句编制程序，以便让计算机去执行对数据机内表示的各种操作，从而实现处理要求，即得到所需的结果，这项工作称为数据处理。 1.4 软件工程学认为：软件系统的生存期可分为软件计划、需求分析、软件设计、软件编码、软件测试和软件维护等六个阶段。程序设计包括前五个阶段（程序设计包括数据表示和数据处理两个方面）。 1.5数据结构课程集中讨论以设计阶段为核心、同时涉及编码阶段和分析阶段的一个小范围内的若干基本问题。概括的说，其主要内容包括：数据的逻辑结构、定义在逻辑结构上的基本运算、数据的存储结构和运算的实现。其中，数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式。由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立、选择和实现是数据结构的核心问题。 1.6 数据表示任务是逐步完成的，即数据表示形式的变化过程是：机外表示——》逻辑结构——》存储结构。 数据处理任务也是逐步完成的，即有转化过程：处理需求——》基本运算和运算——》算法。 数据表示与数据处理是密切相关的，数据处理方式总是与数据的相应的表示形式相联系，反之亦然。 2.1从数据结构的观点看，数据就分成三个不同的层次，即数据、数据元素和数据项。凡能被计算机存储、加工的对象通称为数据；数据元素是数据的基本单位，在程序中作为一个整体而加以考虑和处理，即数据元素被当作运算的基本单位，并且通常具有完整确定的实际意义，又被称为元素、结点、顶点或记录；数据元素又是数据项组成的，但数据项通常不具有完整确定的实际意义，或不当作一个整体对待，又称为字段或域，它是数据的不可分割的最小标识单位。 2.2从数据结构的观点看，重要的是数据元素之间的逻辑关系。所谓逻辑关系是指数据元素之间的关联方式或称“邻接关系”。数据元素之间逻辑关系的整体称为逻辑结构。数据的逻辑结构就是数据的组织形式。四类基本逻辑结构：集合、线性结构、树形结构和图状结构。1）逻辑结构与数据元素本身的形式、内容无关 2）逻辑结构与数据元素的相对的相对位置无关 3）逻辑结构与所含结点个数无关 2.3运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。这种加工以一个或多个逻辑结构及其他有关参数为对象，以经过修改的逻辑结构或从原逻辑结构中提取的有关信息为结果。根据操作的效果将运算分成两种基本类型： 1）加工型运算，其操作改变了原逻辑结构的“值” 2）引用型运算，其操作不改变原逻辑结构，只从中提取某些信息作为运算的结果 2.4假如A是S上的一些运算的集合，B是A的一个子集，使得A中每一运算都可以“归约”为B中一个或多个运算，而B中任一运算不可归约为别的运算，则称B中运算为（相对于A的）基本运算。 2.5对某些逻辑结构S和在S上的基本运算集B，由S和B构成的整体（S，B）往往在大量不同种类的实际问题的求解中反复出现，在此将这样的整体称为一个“数据结构”；线性表、队列、栈等都是数据结构，这三个数据结构有相同的逻辑结构但有不同的基本运算集。 3.1存储实现的基本目标是建立数据的机内表示，存储实现建立的机内表示应遵循选定的逻 第一章概论自测题答案 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 二、单项选择题 （B）1. 非线性结构是数据元素之间存在一种： A）一对多关系B）多对多关系C）多对一关系D）一对一关系 （ C ）2. 数据结构中，与所使用的计算机无关的是数据的结构； A) 存储B) 物理C) 逻辑D) 物理和存储 （C）3. 算法分析的目的是： A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性 （A）4. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性B) 正确性和简明性 C) 可读性和文档性D) 数据复杂性和程序复杂性 （ C ）5. 计算机算法指的是： A) 计算方法B) 排序方法C) 解决问题的有限运算序列D) 调度方法 （B）6. 计算机算法必须具备输入、输出和等5个特性。 A) 可行性、可移植性和可扩充性B) 可行性、确定性和有穷性 第1章习题解答 1.1什么是数据结构？一个数据结构结构的二元组定义形式是什么样的？举例解释其含义。 [解答] 概括地说，数据结构是互相有关联的数据元素的集合。也就是说，数据结构是由某个数据元素的集合和该集合中的数据元素之间的关系组成的，因此数据结构可以用一个二元组来表示。例如，B=（D，R），其中D是某一数据元素的集合，R是D上的关系的有限集。R所表示的是集合D的数据元素之间的逻辑关系，它表示的可能是数据元素之间客观存在的某种联系，也可能是为了处理问题的需要而人为组织的数据元素之间的某种关系，因此，称之为数据的逻辑结构。例如，一个农历节气表，就构成了一个数据结构，其数据元素是一年的农历二十四节气，数据元素之间的关系是节气的时间先后关系。又如，一个某年级学生的成绩排序表，也是一个数据结构，其数据元素是包含成绩项的该年级的学生记录，数据元素之间的关系是学生之间的成绩高低关系。为了在计算机中进行数据处理，必须把从实际问题中抽象出来的数据的逻辑结构映象到计算机的存储器中，即要把抽象出来的数据元素集合D 和数据元素之间的关系存储到计算机的存储器中，称之为数据的物理结构或存储结构，它是数据的逻辑结构在计算机中的表示。 1.2假设R是集合M上的一个关系，R的定义是什么？对实际问题而言，其含义是什么？ [解答] 如果R是对集合M自身的笛卡尔积所取的一个子集，那么我们就说“R是集合M上的一个关系”。对实际问题而言，它表示的是集合M中元素的某种相关性。例如，对于参加一个羽毛球比赛的运动员集合，可以用一个二元关系表示出各场比赛的胜负关系。对于一组课程的集合，可以用一个二元关系表示出各门课程之间的先修和后续关系等等。 1.3设有集合M={d1,d2,d3,d4,d5}上的一个关 R={(d1,d2),(d2,d4),(d4,d5),(d2,d5),(d1,d4),(d1,d5),(d3,d5),(d1,d3)}，试说明关系R具有什么样的性质。 [解答] 从二元关系的基本性质容易验证，该关系R是反自反的、反对称的、传递的关系。 因为关系R中没有(d i,d i)这样的元素，所以它是反自反的。 因为关系R中没有(元素d i,d j)和(d j,d i)同时存在的情况，所以它是反对称的。 关系R 的传递性表现在： 有元素(d1,d2),(d2,d4)，同时有元素(d1,d4), 有元素(d1,d2),(d2,d5)，同时有元素(d1,d5), 有元素(d1,d3),(d3,d5)，同时有元素(d1,d5)， 有元素(d1,d4),(d4,d5)，同时有元素(d1,d5)， 有元素(d2,d4),(d4,d5)，同时有元素(d2,d5)。 1.4什么是线性结构？什么是非线性结构？举例说明。 [解答] 第一章概论自测题答案姓名班级 一、填空题（每空1分，共33分） 1. 一个计算机系统包括硬件系统和软件系统两大部分。 2. 一台计算机中全部程序的集合，称为这台计算机的软件资源/（系统）。 3. 计算机软件可以分为系统软件和应用软件两大类。科学计算程序包属于应用软件，诊断程序属于系统软件（工具）。 4. 一种用助忆符号来表示机器指令的操作符和操作数的语言是汇编语言。 5. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 6. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 7. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 8. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 9. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 10．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 11. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 12. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 13．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 14. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 15. 一个算法的效率可分为时间效率和空间效率。 16.〖00年省统考〗任何一个C程序都由一个主函数和若干个被调用的其它函数组成。 17. 【00年省统考题】变量一经说明，就确定该变量的取值范围（即存储单元）及确定变量所允许的运算。 二、单项选择题（每小题1分，共15分） （B ） 1. 通常所说的主机是指∶ A) CPU B) CPU和内存C) CPU、内存与外存D) CPU、内存与硬盘 （C ）2.在计算机内部，一切信息的存取、处理和传送的形式是∶ A)ACSII码B) BCD码C)二进制D)十六进制 （D）3.软件与程序的区别是∶数据结构复习要点(整理版).docx
数据结构基础知识
数据结构练习题 第一章 概论
数据结构C语言版第1章练习题
数据结构第一章
数据结构第一章 概述习题↓
第一章飞机结构与系统复习题手工改进无答案[]
数据结构 第一章 概述习题
数据结构第一章
第1章数据结构概论自测题及答案
数据结构第1章习题解答..
《c语言数据结构》第一章概论 自测题答案
相关主题
文本预览