选择填空模拟题大全

第一章概论二、填空题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.任何算法都必须用某种语言加以描述。根据描述算法的语言的不同，可将算法分为：运行终止的程序可执行部分、伪语言算法、非形式算法三类。22.数据结构课程着重评论算法的时空性能，又称为“算法分析”。23.通常从正确性能、易读性、健壮性、高效性等几方面评价算法的(包括程序)的质量。24.一个算法的时空性能是指该算法的时间性能（或时间效率）和空间性能（或空间效率），前者是算法包含的计算量，后者是算法需要的存储量。25.通常采用下述办法来估算求解某类问题的各个算法在给定输入下的计算量：①根据该类问题的特点合理地选择一种或几种操作作为“标准操作”；②确定每个算法在给定输入下共执行了多少次标准操作，并将此次数规定为该算法在给定输入下的计算量。26.通常，一个算法在不同输入下的计算量是不同的。则可用以下两种方式来确定一个算法的计算量：以算法在所有输入下的计算量的最大值作为算法的计算量，这种计算量称为算法的最坏情况时间复杂性或最坏情况时间复杂度。以算法在所有输入下的计算量的加权平均值作为算法的计算量，这种计算量称为算法的平均时间复杂性或平均时间复杂度。27.最坏情况时间复杂性和平均时间复杂性统称为时间复杂性或时间复杂度。28.在一般情况下，一个算法的时间复杂性是算法输入规模的函数。29.一个算法的输入规模或问题的规模是指作为该算法输入的数据所含数据元素的数目，或与此数目有关的其他参数。30.常见时间复杂性的量级有：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、平方阶O(n2)、和指数阶O(2n)。通常认为，具有指数阶量级的算法是实际不可计算，而量级低于平方阶的算法是高效的。31.数据结构的基本任务是数据结构的设计和实现。32.数据结构的课程的主要内容可以概括为：数据结构的定义、数据结构的实现、数据结构的评价和选择。33.数据的逻辑结构与数据元素本身的内容和形式无关。34.从逻辑关系上讲，数据结构主要分为两大类，它们是线性结构和非线性结构。35.程序段“for(i=l;i=n;i++){k++;for(j=1;j=n;j++)l+=k;}”的时间复杂度T(n)=O（n2）。36.程序段“i=1;while(i=n)i=i*2;”的时间复杂度T(n)=o(log2n)。三、单项选择题1.以下说法错误的是①用数字式计算机解决问题的实质是对数据的加工处理②程序设计的实质是数据处理③数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式④运算实现是完成运算功能的算法，或这些算法的设计⑤数据处理方式总是与数据某种相应的表示形式相联系，反之亦然2.根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式。以下解释错误的是()①集合中任何两个结点之间都有逻辑关系但组织形式松散②线性结构中结点按逻辑关系依次排列形成一条锁链③树形结构具有分支、层次特性，其形态有点像自然界中的树④图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接3.关于逻辑结构，以下说法错误的是()①逻辑结构与数据元素本身的形成、内容无关②逻辑结构与数据元素的相对位置有关③逻辑结构与所含结点个数无关④一些表面上很不相同的数据可以有相同的逻辑结构⑤逻辑结构是数据组织的某种本质性的东西4.根据操作的效果，可将运算分成加工型运算、引用型运算两种基本类型。对于表格处理中的五种功能以下解释错误的是()①查找引用型运算，功能是找出满足某种条件的结点在s(线形结构)中的位置②读取引用型运算功能是读出s(线形结构)中某指定位置结点的内容③插入引用型运算，功能是在s(线形结构)的某指定位置上增加一个新结点④删除加工型运算，功能是撤消s(线形结构)某指定位置上的结点⑤更新加工型运算，功能是修改s(线形结构)中某指定结点的内容5.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是()①存储结点每个存储结点可以存放一个或一个以上的数据元素②数据元素之间关联方式的表示也就是逻辑结构的机内表示③附加设施，如为便于运算实现而设置的“哑结点”等等6.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是①每个存储结点只能存放一个数据元素()②数据元素之间的关联方式可由存储结点之间的关联方式直接表达③一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级④语言级描述可经编译自动转换成机器级因此也可以看成是一种机内表示7.通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。以下解释错误的是()①正确性算法应能正确地实现预定的功能(即处理要求)②易读性算法应易于阅读和理解以便于调试修改和扩充③健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果④高效性即达到所需要的时间性能8.对于数据结构课程的主要内容，以下解释正确的是()①数据结构的定义，包括逻辑结构、存储结构和基本运算集②数据结构的实现，包括存储实现、运算实现和基本运算集③数据结构的评价和选择，包括逻辑结构的选择、基本运算集的选择和存储选择9，与数据元素本身的形式、内容、相对位置、个数无关的是数据的()①存储结构②存储实现③逻辑结构④运算实现10顺序存储结构()①仅适合于静态查找表的存储②仅适合于动态查找表的存储③既适合静态又适合动态查找表的存储④既不适合静态又不适合动态查找表的存储11.算法的时间复杂度，都要以通过算法中执行频度最高的语句的执行次数来确定这种观点()①正确②错误12以下说法正确的是()①所谓数据的逻辑结构指的是数据元素之间的逻辑关系。②逻辑结构与数据元素本身的内容和形式无关③顺序文件只适合于存放在磁带上，索引文件只能存放在磁盘上④基于某种逻辑结构之上的运算，其实现是惟一的13以下说法正确的是()①数据元素是数据的最小单位②数据项是数据的基本单位③数据结构是带有结构的各数据项的集合④数据结构是带有结构的数据元素的集合14以下说法错误的是()①所谓数据的逻辑结构指的是数据元素之间的逻辑关系的整体②数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的③数据结构、数据元素、数据项在计算机中的映象分别称为存储结构、结点、数据域④数据项是数据的基本单位15通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着()①数据元素具有同一特点②不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致③每个数据元素都一样④数据元素所包含的数据项的个数要相等第二章线性表二、填空题1.为了便于讨论，有时将含n(n=0)个结点的线性结构表示成(a1，a2,……an)，其中每个ai代表一个结点。a1称为起始结点，an称为终端结点，i称为ai在线性表中的序号或位置。对任意一对相邻结点ai、ai┼1(1=in),ai称为ai┼1的直接前趋ai┼1称为ai的直接后趋。2.为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。不含任何结点的线性结构记为（）或ф。3.线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接前趋外，其他结点有且仅有一个直接前趋;除终端结点没有直接后趋外，其它结点有且仅有一个直接后趋。4.所有结点按1对1的邻接关系构成的整体就是线性结构。5.线性表的逻辑结构是线性结构。其所含结点的个数称为线性表的长度，简称表长。6.表长为O的线性表称为空表。7.线性表典型的基本运算包括:初始化INITLATE（L）、求表长LENGTH（L）、读表长GET（L，i）、定位LOCATE（L，X）、插入INSERT（L，X，i）、删除DELETE（L，i）等六种。8.顺序表的特点是逻辑结构中相邻的结点在存储结构中仍相邻。9.顺序表的类型定义可经编译转换为机器级。假定每个datatype类型的变量占用k(k=1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点ai的存储地址为b+（i-1）xk。10.以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。Voidinsert_sqlist(sqlistL，datatypex，inti)/*将X插入到顺序表L的第i-1个位置*/{if(L.last==maxsize)error(“表满”)；if((i1)||(iL.last+1))error(“非法位置”);for(j=L.last;j=i;j--)L．data[j]=L．data[j-1];L.data[i-1]=x;L.last=L.last+1;}11.对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的最坏时间复杂性为n，量级是O(n)。插入算法的平均时间复杂性为n/2，平均时间复杂性量级是O(n)。12.以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。voiddelete_sqlist(sqlistL,inti)/*删除顺序表L中的第i-1个位置上的结点*/{if((i1)||(iL.last))error(“非法位置”)；for(j=i+1;j=L.last;j++)L.data[j-2]=l.data[j-1];L.last=L.last-1;}13.对于顺序表的删除算法delete_sqlist来说，若以结点移动为标准操作，最坏情况时间复杂性及其量级分别是n-1和O(n)，其平均时间复杂性及其量级分别为(n-1)/2和O(n)。14.以下为顺序表的定位运算，分析算法，请在________处填上正确的语句。intlocate_sqlist(sqlistL,d