(13电子本)数据结构_选择填空.docxVIP

PAGE PAGE # 第一章概论 一、填空题 计算机专业人员必须完成的两项基本任务是：数据表示和数据处理。 数据在计算机存储器中的存在形式称为机内表示。 3?概括地说，数据结构课程的主要内容包括：数据的逻辑结构、定义在逻辑结构上的基本运算、数据的存储结构和运算的实现。此外，该课程还要考虑各种结构和实现方法的评价和选择。 由一种逻辑性_结构和一组—基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立、选择和实现是数据结构的核心问题。 存储结构是逻辑结构的存储实现。 数据表示任务是逐步完成的，即数据表示形式的变化过程是机外表示-〉逻辑结构-存储结构。 数据处理任务也是逐步完成的，即转化过程是处理要求-基本运算和运算-算法。 从数据结构的观点看，通常所说的〃数据〃应分成三个不同的层次，即—数据、数据元素和数据项。 9?根据需要，数据元素又被称为元素、结点、顶点或记录。 在有些场合下，数据项又称为字段或域，它是数据的不可分割的最小标识单位。 从某种意义上说，数据、数据元素和数据项实际反映了数据组织的三个层次，数据可由若干个数据元素构成，数据元素可由若干个数据项构成。 根据数据元素之间关系的不同特性，通常有集合、线性结构、树形结构、图状结构四类基本逻辑结构，它们反映了四类基本的数据组织形式。 根据操作的效果，可将运算分成以下两种基本类型： 加工型运算，其操作改变了原逻辑结构的“值”,如结点个数、某些结点的内容等； 引用型运算，其操作不改变原逻辑结构，只从中提取某些信息作为运算的结果。 将以某种逻辑结构S为操作对象的运算称为“定义在S上的运算”,简称“_S上运算”。 一般地，可能存在同一逻辑结构S上的两个运算A和B，A的实现需要或可以利用B，而B的实现不需要利用A。在这种情况下，称A可以“归纳”为B。 存储实现的基本目标是建立数据的机内表示。 —般地，一个存储结构包括存储结点、数据兀素之间关联方式的表示7.附加设施三个主要部分。 通常，存储结点之间可以有顺序存储方式、链式存储方式、索引存储方式、散列存储方式四种关联方式，称为四种基本存储方式。 可用任何一种存储方式所规定的存储结点之间的关联方式来间接表达给定逻辑 结构S中数据元素之间的逻辑关系。由此得到的存储结构，称为给定逻辑结构S的存储实现—或—存储映象。 —个运算的实现是指一个完成该运算功能的墮序。运算实现的核心是处理步骤的规定，即算法设计。 21?任何算法都必须用某种语言加以描述。根据描述算法的语言的不同，可将算法分为：运行终止的程序可执行部分、伪语言算法、非形式算法三类。 数据结构课程着重评论算法的时空性能，又称为“算法分析”。 通常从正确性能、易读性、健壮性、高效性等几方面评价算法的（包括程序）的质量。 一个算法的时空性能是指该算法的时间性能和空间性能，前者是算法包含的计算量后者是算法需要的存储量。 通常采用下述办法来估算求解某类问题的各个算法在给定输入下的计算量： 根据该类问题的特点合理地选择一种或几种操作作为“标准操作”; 确定每个算法在给定输入下共执行了多少次—标准操作，并将此次数规定为该算法在给定输入下的计算量。 通常，一个算法在不同输入下的计算量是不同的。则可用以下两种方式来确定一个算法的计算量： 以算法在所有输入下的计算量的最大值作为算法的计算量，这种计算量称为算法的 最坏情况时间复杂性或—最坏情况时间复杂度。 以算法在所有输入下的计算量的加权平均值作为算法的计算量，这种计算量称为算法的—平均时间复杂性或平均时间复杂度。 最坏情况时间复杂性和平均时间复杂性统称为时间复杂性或时间复杂度。 在一般情况下，一个算法的时间复杂性是算法输入规模的函数。 一个算法的输入规模或问题的规模是指—作为该算法输入的数据所含数据元素的数目，或与此数目有关的其他参数。 常见时间复杂性的量级有：常数阶0(1)、对数阶0(log2n)、线性阶0(_n_)、平方阶o(_n_)、和指数阶0(2n)o通常认为，具有指数阶量级的算法是实际不可计算,而量级低于平方阶的算法是高效的。 数据结构的基本任务是数据结构的—设计_和_实现_。 数据结构的课程的主要内容可以概括为：数据结构的定义、数据结构的实现数据结构的评价和选择-。 数据的逻辑结构与数据元素本身的内容和形式无关。 从逻辑关系上讲，数据结构主要分为两大类，它们是线性结构和非线性结构。 程序段“for(i=l;i〈二n;i++){k++;for(j=1;j〈二n;j++)l+=k;}”的时间复杂度T(n)=0(n2)。 程序段“i=1;while(i〈二n)i=i*2;”的时间复杂度T(n)=o(lo%n)。 二、单项选择题 以下说法错误的是2_ 用数字式计算机解决问题的实质是对数据的加工处理 程序设计的实质是数据处理 数据的逻辑