大连东软 数据结构题库

1.6习题1.6.1知识点：数据结构的定义一、选择题1①数据结构通常是研究数据的（A）及它们之间的相互联系。A．存储和逻辑结构B．存储结构C．顺序结构D．链式存储结构2①数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（C）A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构3①线性结构是数据元素之间存在一种（D）。A．一对多关系B.多对多关系C多对一关系D一对一关系4①计算机内部数据处理的基本单位是（B）。A.数据B．数据元素C.数据项D．数据库5②从逻辑上可以把数据结构分为（C）两大类。【武汉交通科技1996】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构二、填空题1①数据结构按逻辑结构可分为四大类，它们分别是集合、线性、树、图。2①数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、散列、索引。三、判断题（F）1①数据元素是数据的最小单位。（T）2①记录是数据处理的最小单位。（F）3①数据的逻辑结构是指数据的各数据项之间的逻辑关系。（T）4①数据的物理结构是指数据在计算机内的实际存储形式。四、简答题1①简述什么是数据结构?2②数据结构与数据类型有什么区别?【哈尔滨工业2001】1.6.2知识点：算法的概念一、选择题1①计算机算法指的是（C）A．计算方法B．排序方法C．解决问题的有限运算序列D．调度方法2①算法分析的目的是（（1）C），算法分析的两个主要方面（（2）A）．（1）A．找出数据结构的合理性B．研究算法中的输入与输出的关系C．分析算法的效率以求改进D．分析算法的易查性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性3②设语句X++的时间是单位时间，则语句：for（i=1;i=n;i++）x++;时间复杂度为（C）。A．O（1）B．O（n）C．O（n2）D．O（n3）4②算法的计算量的大小称为计算的（B）。【北京邮电2000】A．效率B．复杂性C．现实性D．难度5②算法的时间复杂度取决于（C）【中科院计算所1998】A．问题的规模B．待处理数据的初态C．A和B6②下面关于算法说法错误的是（A）【南京理工2000】A．算法最终必须由计算机程序实现B．为解决某问题的算法同为该问题编写的程序含义是相同的C．算法的可行性是指指令不能有二义性D．以上几个都是错误的7②下面说法错误的是（D）【南京理工2000】（1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度O（2n）的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．（1）B．（1）,（2）C．（1）,（4）D．（3）8②程序段for（i=n-1;i=1;i++）for（j=1;j=i;j++）if（A[j]A[j+1]）A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（D）【南京理工1998】A．O（n）B．O（nlog2n）C．O（n3）D．O（n2）二、填空题1①以夹杂自然语言和程序语句的形式来描述解决问题的方法称为____伪码________。2①一个算法的效率可分为___时间______效率和__空间_______效率．3②有一个程序片断如下：for（i=0;in;i++）x=x+1;则其时间复杂度为：_O（n）________4②有一个程序片断如下：for（i=0;in;i++）for（j=i;jn;j++）for（k=j;kn;k++）m=1;则其时间复杂度为：O（n3）5②有一个程序片断如下：for（i=0;in;i++）{j=i;while（j=2）j=j/2;}则其时间复杂度为：O（nlog2n）三、判断题（T）1①算法的优劣与算法描述语言无关，但与所用计算机有关。（T）2①健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（F）3①程序一定是算法。四、简答题1①如何判断一个算法的好坏?2③调用下列C函数f（n）回答下列问题：（1）试指出f（n）值的大小，并写出f（n）值的推导过程；（2）假定n=5，试指出f（5）值的大小和执行f（5）时的输出结果。C函数：intf（intn）{inti,j，k,sum=0;for（i=l;in+1;i++）{for（j=n;ji-1;j--）for（k=1;kj+1;k++）sum++;printf（sum=%d\n,sum）;}return（sum）;}【华中理工2000】2.7习题2.7.1知识点：线性表的逻辑结构一、选择题1①线性表L=（a1,a2,…,an）,下列说法正确的是（D）。A．每个元素都有一个直接前驱和一个直接后继。B．线性表中至少要有一个元素。C．表中诸元素的排列顺序必须是由小到大或由大到小。D．除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。2①在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D）。A．插入B．删除C．排序D．定位3①线性表是具有n个（C）的有限序列（n0）。【清华1998】A．表元素B．字符C．数据元素D．数据项E．信息项二、判断题（T）1①线性表中的每个结点最多只有一个前驱和一个后继。（F）2①线性表中的每个结点都至少有一个前驱结点和后继结点。（F）3①线性表是N个数的有限序列。（F）4①同一线性表的数据元素可以具有不同的特性。（T）5①线性表的长度n就是表中数据元素的个数，当n=0时，称为空表。（T）6①线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短。（F）7①对线性表中的数据元素只能进行访问，不能进行插入和删除操作。2.7.2知识点：线性表的顺序存储结构一、选择题1①在一个长度为n的顺序表中，在第i个元素（1=i=n+1）之前插入一个新元素时需向后移动（B）个元素．A．n-1B．n-i+1C．n-i-1D．i2①若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（D）存储方式最节省时间。A．单链表B．双链表C．单向循环D．顺序表3②一个数组第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）A．110B．108C．100D．1204①下述哪一条是顺序存储结构的优点（A）。【北方交通2001】A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示5③若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C）（1=i=n+1）。【北京航空航天1999】A．O（0）B．O（1）C．O（n）D．O（n2）6③对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C）。【青岛2000】A．O（n）O（n）B．O（n）O（1）C．O（1）O（n）D．O（1）O（1）二、填空题1①线性表的顺序存储的缺点是在任意位置上___插入_____数据与____删除_____数据费时间。2①设一线性表的顺序存储，总存储容量为M，其元素存储位置的范围为__0~M-1__________。3①向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动____n-i______个元素。三、简答题1③已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：voidf30（SeqList*L）{inti，j;for（i=j=0;iL-length;i++）if（L-data[i]=0）{if（i!=j）L-data[j]=L-data[i];j++；}L-length=j;}（1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30（&L）后L状态；(21,19,0,34,30)（2）简述算法f30的功能。删除顺序表中小于0的元素四、编程题1④已知顺序表La中数据元素按非递减有序排列。试写一个算法，将x插入到La的合适位置上，保持该表的有序性。2.7.3知识点：线性表的链式存储结构一、选择题1①链表是一种采用（B）存储结构存储的线性表。A．顺序B．链式C．星式D．网状2①链接存储的存储结构所占存储空间（A）。A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。B．只有一部分，存放结点值。C．只有一部分，存储表示结点间关系的指针。D．分两部分，一部分存放结点值，另一部分存放结点所占单元数。3①线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以4①线性表Ｌ在（B）情况下适用于使用链式结构实现。A．需经常修改Ｌ中的结点值B．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点D．Ｌ中结点结构复杂5①对单链表表示法,以下说法错误的是（C）。A．数据域用于存储线性表的一个数据元素。B．指针域（或链域）用于存放一个指向本结点所含数据元素的直接后继所在结点的指针。C．所有数据通过指针的链接而组织成单链表。D．NULL称为空指针，它不指向任何结点只起标志作用。6①以下说法正确的是（D）。A．顺序存储方式的优点是存储密度大且插入、删除运算效率高B．链表的每个结点中都恰好包含一个指针C．线性表的顺序存储结构优于链式存储结构D．顺序存储结构属于静态结构而链式结构属于动态结构7①以下说法错误的是（D）。A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B．顺序存储的线性表可以随机存取C．由于顺序存储要求连续的存储区域,所以在存储管理上不够灵活D．线性表的链式存储结构优于顺序存储结构8①不带头结点的单链表head为空的判定条件是（A）。A．head==NULLB．head-next==NULLC．head-next==headD．head!=NULL9①带头结点的单链表head为空的判定条件是（B）。A．head==NULLB．head-next==NULLC．head-next==headD．head!=NULL10②在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是（A）。A．p-next==headB．p-next-next==headC．p-next==NULLD．p==head11②在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行语句（C）。A．s-next=p-next;p-next=s;B．p-next=s-next;s-next=p;C．q-next=s;s-next=p;D．p-next=s;s-next=q;12②在一个单链表中，若p所指结点不是最后结点，在p之后插入s结点，则应执行语句（B）。A．s-next=p:p-next=s;B．s-next=p-next;p-next=s;C．s-next=p-next;p=s;D．p-next=s;s-next=p;13②在一个单链表中，若删除p所指结点的后续结点，则应执行语句（A）。A．p-next=p-next-next;B．p=p-next;p-next=p-next-next;C．p-next=p-next;D．p=p-next-next;14②指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是（A）。A．p-next=r；q-next=r-next；r-next=q；B．p-next=r；r-next=q；q-next=r-next；C．r-next=q；q-next=r-next；p-next=r；D．r-next=q；p-next=r；q-next=r-next；15①链表不具有的特点是（B）【福州1998】A．插入、删除不需要移动元素B．