第一章概论 、名词解释 数据表示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为操作对象的运算称为“ ,简称“ 15.一般地,可能存在同一逻辑结构S上的两个运算A和B,A的实现需要或可以利用B,而 的实现不需要利用A。在这种情况下,称A可以“ 16.存储实现的基本目标是建立数据的 17.一般地,一个存储结构包括 三个主要部分。 18.通常,存储结点之间可以有 四种关联 方式,称为四种基本存储方式 19.可用任何一种存储方式所规定的存储结点之间的关联方式来间接表达给定逻辑 结构S中数据元素之间的逻辑关系。由此得到的存储结构,称为」 或 0.一个运算的实现是指一个完成该运算功能的 运算实现的核心是处 理步骤的规定,即 21.任何算法都必须用某种语言加以描述。根据描述算法的语言的不同,可将算法分 三类 22.数据结构课程着重评论算法的 ,又称为
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 为操作对象的运算称为“__________”，简称“__________”。 15.一般地，可能存在同一逻辑结构 S 上的两个运算 A 和 B，A 的实现需要或可以利用 B，而 B 的实现不需要利用 A。在这种情况下，称 A 可以“__________”为 B。 16.存储实现的基本目标是建立数据的__________。 17.一般地，一个存储结构包括__________、__________、__________三个主要部分。 18.通常，存储结点之间可以有__________、__________、__________、_________四种关联 方式，称为四种基本存储方式。 19.可用任何一种存储方式所规定的存储结点之间的关联方式来间接表达给定逻辑 结构 S 中数据元素之间的逻辑关系。由此得到的存储结构，称为____________________或 __________。 20.一个运算的实现是指一个完成该运算功能的__________。运算实现的核心是处 理步骤的规定，即___________。 21.任何算法都必须用某种语言加以描述。根据描述算法的语言的不同，可将算法分 为：___________、___________、___________三类。 22.数据结构课程着重评论算法的___________，又称为“___________
23.通常从 等几方面评价算法的(包 括程序)的质量, 4.一个算法的时空性能是指该算法的 前者是算法 包含的 后者是算法需要的 25.通常采用下述办法来估算求解某类问题的各个算法在给定输入下的计算量: ①根据该类问题的特点合理地选择一种或几种操作作为“ ②确定每个算法在给定输入下共执行了多少次 并将此次数规定为该算法在给 定输入下的 26.通常,一个算法在不同输入下的计算量是不同的。则可用以下两种方式来确定一个算法的 计算量: ①以算法在所有输入下的计算量的最大值作为算法的计算量,这种计算量称为算法的 以算法在所有输入下的计算量的加权平均值作为算法的计算量,这种计算量称为算法的 或 27.最坏情况时间复杂性和平均时间复杂性统称为 或 8.在一般情况下,一个算法的时间复杂性是 的函数。 29.一个算法的输入规模或问题的规模是指 30.常见时间复杂性的量级有:常数阶0( )、对数阶0( )、线性阶0 )、平方阶0( )、和指数阶0( )。通常认为,具有指数 阶量级的算法是 ,而量级低于平方阶的算法是 的 1.数据结构的基本任务是数据结构的 32.数据结构的课程的主要内容可以概括为 33.与数据元素本身的内容和形式无关。 34.从逻辑关系上讲,数据结构主要分为两大类,它们是 和 35.程序段“for(i=1;i<=n;i++){k++;for(j=1;j<=n;j+)1+=-k;}”的时间复杂度T(n) 36.程序段“i=1; while(i<=n)i=i*2;”的时间复杂度T(n) 、单项选择题 1.以下说法错误的是 ①用数字式计算机解决问题的实质是对数据的加工处理 ②程序设计的实质是数据处理 ③数据的逻辑结构是数据的组织形式,基本运算规定了数据的基本操作方式 ④运算实现是完成运算功能的算法,或这些算法的设计 ⑤数据处理方式总是与数据某种相应的表示形式相联系,反之亦然 2.根据数据元素之间关系的不同特性,以下四类基本的逻辑结构反映了四类基本的 数据组织形式。以下解释错误的是 集合中任何两个结点之间都有逻辑关系但组织形式松散 ②线性结构中结点按逻辑关系依次排列形成一条"锁链 ③树形结构具有分支、层次特性,其形态有点像自然界中的树 ④图状结构中的各个结点按逻辑关系互相缠绕,任何两个结点都可以邻接 3.关于逻辑结构,以下说法错误的是 ①逻辑结构与数据元素本身的形成、内容无关 ②逻辑结构与数据元素的相对位置有关
2 23.通常从___________、___________、___________、___________等几方面评价算法的(包 括程序)的质量。 24.一个算法的时空性能是指该算法的___________和______________________，前者是算法 包含的___________，后者是算法需要的___________。 25.通常采用下述办法来估算求解某类问题的各个算法在给定输入下的计算量： ① 根据该类问题的特点合理地选择一种或几种操作作为“___________”； ② 确定每个算法在给定输入下共执行了多少次___________，并将此次数规定为该算法在给 定输入下的___________。 26.通常，一个算法在不同输入下的计算量是不同的。则可用以下两种方式来确定一个算法的 计算量： ① 以算法在所有输入下的计算量的最大值作为算法的计算量，这种计算量称为算法的 ________或___________。 ② 以算法在所有输入下的计算量的加权平均值作为算法的计算量，这种计算量称为算法的 ___________或___________。 27.最坏情况时间复杂性和平均时间复杂性统称为___________或___________。 28.在一般情况下，一个算法的时间复杂性是___________的函数。 29.一个算法的输入规模或问题的规模是指___________。 30.常见时间复杂性的量级有：常数阶 O(___________)、对数阶 O(___________)、线性阶 O (___________)、平方阶 O(___________)、和指数阶 O(___________)。通常认为，具有指数 阶量级的算法是___________，而量级低于平方阶的算法是___________的。 31.数据结构的基本任务是数据结构的___________和___________。 32.数据结构的课程的主要内容可以概括为：___________、___________、___________和 ___________。 33.___________与数据元素本身的内容和形式无关。 34.从逻辑关系上讲，数据结构主要分为两大类，它们是___________和___________。 35.程序段“for(i=l;i<=n;i++){k++;for(j=1;j<=n;j++)l+=k;}”的 时间复杂度 T(n)= ___________。 36.程序段“i=1;while(i<=n)i=i*2;”的时间复杂度 T(n)= ___________。 三、单项选择题 1.以下说法错误的是 ①用数字式计算机解决问题的实质是对数据的加工处理 ②程序设计的实质是数据处理 ③数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式 ④运算实现是完成运算功能的算法，或这些算法的设计 ⑤数据处理方式总是与数据某种相应的表示形式相联系，反之亦然 2.根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的 数据组织形式。以下解释错误的是 ( ) ①集合中任何两个结点之间都有逻辑关系但组织形式松散 ②线性结构中结点按逻辑关系依次排列形成一条"锁链" ③树形结构具有分支、层次特性，其形态有点像自然界中的树 ④图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接 3.关于逻辑结构，以下说法错误的是 ( ) ①逻辑结构与数据元素本身的形成、内容无关 ②逻辑结构与数据元素的相对位置有关
③逻辑结构与所含结点个数无关 ④一些表面上很不相同的数据可以有相同的逻辑结构 ⑤逻辑结构是数据组织的某种"本质性"的东西 4.根据操作的效果,可将运算分成加工型运算、引用型运算两种基本类型。对于表格 处理中的五种功能以下解释错误的是 ①查找引用型运算,功能是找出满足某种条件的结点在s(线形结构)中的位置 ②读取引用型运算功能是读出s(线形结构)中某指定位置结点的内容 ③插入引用型运算,功能是在s(线形结构)的某指定位置上增加一个新结点 ④删除加工型运算,功能是撤消s(线形结构)某指定位置上的结点 ⑤更新加工型运算,功能是修改s(线形结构)中某指定结点的内容 5.一般地,一个存储结构包括以下三个主要部分。以下说法错误的是() ①存储结点每个存储结点可以存放一个或一个以上的数据元素 ②数据元素之间关联方式的表示也就是逻辑结构的机内表示 ③附加设施,如为便于运算实现而设置的“哑结点”等等 6.一般地,一个存储结构包括以下三个主要部分。以下说法错误的是 ①每个存储结点只能存放一个数据元素 ②数据元素之间的关联方式可由存储结点之间的关联方式直接表达 ③一种存储结构可以在两个级别上讨论。其一是机器级,其二是语言级 ④语言级描述可经编译自动转换成机器级因此也可以看成是一种机内表示 7.通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质 量。以下解释错误的是 ①正确性算法应能正确地实现预定的功能(即处理要求) ②易读性算法应易于阅读和理解以便于调试修改和扩充 ③健壮性当环境发生变化时,算法能适当地做出反应或进行处理,不会产生不需要的运 行结果 ④高效性即达到所需要的时间性能 8.对于数据结构课程的主要内容,以下解释正确的是 ①数据结构的定义,包括逻辑结构、存储结构和基本运算集 ②数据结构的实现,包括存储实现、运算实现和基本运算集 ③数据结构的评价和选择,包括逻辑结构的选择、基本运算集的选择和存储 选择 9,与数据元素本身的形式、内容、相对位置、个数无关的是数据的 ①存储结构②存储实现 ③逻辑结构 ④运算实现10顺序存储结构 ①仅适合于静态查找表的存储 ②仅适合于动态查找表的存储 ③既适合静态又适合动态查找表的存储 ④既不适合静态又不适合动态查找表的存储 算法的时间复杂度,都要以通过算法中执行频度最高的语句的执行次数来确定这种 观点 ①正确 ②错误 12以下说法正确的是 ①所谓数据的逻辑结构指的是数据元素之间的逻辑关系 ②逻辑结构与数据元素本身的内容和形式无关 3
3 ③逻辑结构与所含结点个数无关 ④一些表面上很不相同的数据可以有相同的逻辑结构 ⑤逻辑结构是数据组织的某种"本质性"的东西 4.根据操作的效果，可将运算分成加工型运算、引用型运算两种基本类型。对于表格 处理中的五种功能以下解释错误的是 ( ) ①查找引用型运算，功能是找出满足某种条件的结点在 s(线形结构)中的位置 ②读取引用型运算 功能是读出 s(线形结构)中某指定位置结点的内容 ③插入引用型运算，功能是在 s(线形结构)的某指定位置上增加一个新结点 ④删除加工型运算，功能是撤消 s(线形结构)某指定位置上的结点 ⑤更新加工型运算，功能是修改 s(线形结构)中某指定结点的内容 5.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是 ( ) ①存储结点每个存储结点可以存放一个或一个以上的数据元素 ②数据元素之间关联方式的表示 也就是逻辑结构的机内表示 ③附加设施，如为便于运算实现而设置的“哑结点”等等 6.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是 ①每个存储结点只能存放一个数据元素 ( ) ②数据元素之间的关联方式可由存储结点之间的关联方式直接表达 ③一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级 ④语言级描述可经编译自动转换成机器级 因此也可以看成是一种机内表示 7.通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质 量。以下解释错误的是 ( ) ①正确性 算法应能正确地实现预定的功能(即处理要求) ②易读性 算法应易于阅读和理解 以便于调试 修改和扩充 ③健壮性 当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运 行结果 ④高效性 即达到所需要的时间性能 8.对于数据结构课程的主要内容，以下解释正确的是 ( ) ①数据结构的定义，包括逻辑结构、存储结构和基本运算集 ②数据结构的实现，包括存储实现、运算实现和基本运算集 ③数据结构的评价和选择，包括逻辑结构的选择、基本运算集的选择和存储 选择 9，与数据元素本身的形式、内容、相对位置、个数无关的是数据的 ( ) ①存储结构 ②存储实现 ③逻辑结构 ④运算实现 10 顺序存储结构 ( ) ①仅适合于静态查找表的存储 ②仅适合于动态查找表的存储 ③既适合静态又适合动态查找表的存储 ④既不适合静态又不适合动态查找表的存储 11.算法的时间复杂度，都要以通过算法中执行频度最高的语句的执行次数来确定这种 观点 ( ) ①正确 ②错误 12 以下说法正确的是 ( ) ①所谓数据的逻辑结构指的是数据元素之间的逻辑关系。 ②逻辑结构与数据元素本身的内容和形式无关
③顺序文件只适合于存放在磁带上,索引文件只能存放在磁盘上 ④基于某种逻辑结构之上的运算,其实现是惟一的 13以下说法正确的是 数据元素是数据的最小单位 ②数据项是数据的基本单位 ③数据结构是带有结构的各数据项的集合 ④数据结构是带有结构的数据元素的集合 14以下说法错误的是 ①所谓数据的逻辑结构指的是数据元素之间的逻辑关系的整体 ②数据的逻辑结构是指各数据元素之间的逻辑关系,是用户按使用需要而建立的 ③数据结构、数据元素、数据项在计算机中的映象分别称为存储结构、结点、数据域 ④数据项是数据的基本单位 15通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着 ①数据元素具有同一特点 ②不仅数据元素所包含的数据项的个数要相同,而且对应数据项的类型要一致 ③每个数据元素都一样 ④数据元素所包含的数据项的个数要相等 四、简答及应用 1数据与数据元素有何区别? 2·为什么说数据元素之间的逻辑关系是数据内部组织的主要方面? 3·逻辑结构与存储结构是什么关系? 4·运算与运算的实现是什么关系?有哪些相同点和不同点? 5,类C语言与标准C语言的主要区别是什么? 五、算法设计 1、设计求解下列问题的类C语言算法,并分析其最坏情况时间复杂性及其量级。 (1)在数组A[1.n中查找值为K的元素,若找到则输出其位置i(1<=i<=n),否则输出 0作为标志 (2)找出数组A[1..n中元素的最大值和次最大值(本小题以数组元素的比较为标准 操作)
4 ③顺序文件只适合于存放在磁带上，索引文件只能存放在磁盘上 ④基于某种逻辑结构之上的运算，其实现是惟一的 13 以下说法正确的是 ( ) ①数据元素是数据的最小单位 ②数据项是数据的基本单位 ③数据结构是带有结构的各数据项的集合 ④数据结构是带有结构的数据元素的集合 14 以下说法错误的是 ( ) ①所谓数据的逻辑结构指的是数据元素之间的逻辑关系的整体 ②数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的 ③数据结构、数据元素、数据项在计算机中的映象分别称为存储结构、结点、数据域 ④数据项是数据的基本单位 15 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 ( ) ①数据元素具有同一特点 ②不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 ③每个数据元素都一样 ④数据元素所包含的数据项的个数要相等 四、简答及应用 1 数据与数据元素有何区别？ 2·为什么说数据元素之间的逻辑关系是数据内部组织的主要方面? 3·逻辑结构与存储结构是什么关系? 4·运算与运算的实现是什么关系?有哪些相同点和不同点？ 5，类 C 语言与标准 C 语言的主要区别是什么? 五、算法设计 1、 设计求解下列问题的类 C 语言算法，并分析其最坏情况时间复杂性及其量级。 （1） 在数组A[1..n]中查找值为K的元素,若找到则输出其位置i(1<=i<=n),否则输出 0 作为标志。 （2） 找出数组 A[1..n]中元素的最大值和次最大值（本小题以数组元素的比较为标准 操作）