1 绪论一、选择题：1、下列算法的时间复杂度是（ ） for(i=0;in;i+ +) ci=i； AO（1） BO（n） CO（log2n） DO（nlog2n）2、数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（ ） A索引存储方法 B顺序存储方法 C链式存储方法 D散列存储方法 解析： 数据结构在计算机中的表示（映像）称为数据的物理（存储）结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链式存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成线性结构和非线性结构。线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。3、以下哪一个术语与数据的存储结构无关？（ ）。A.顺序表 B.链表C.散列表 D.队列4、算法在发生非法操作时可以做出处理的特性称为（ ）。A正确性B易读性C健壮性D高效性5、逻辑结构是指数据元素的（ ）。A关联方式 B存储方式C结构D数据项6、研究数据结构就是研究（ ）。A数据的逻辑结构B数据的存储结构C数据的逻辑结构和存储结构D数据的逻辑结构、存储结构及其数据的运算7、从逻辑上可以把数据结构分为（ ）。A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构8、以下有关数据的叙述中错误的是（ ）。A计算机能够处理的数据包括整数、实数、字符、声音、图像等B数据的逻辑结构是从逻辑关系上描述数据，它取决于数据的存储方式C数据存储结构的实现依赖于计算机语言D数据的运算是定义在数据的逻辑结构上的9、数据的基本单位是（ ）。A.数据结构 B.数据元素C.数据项 D.文件10、下列算法的时间复杂度是（ ） for(i=0;im;i+ +) for(j=0;jn;j+ +) aij=i*j； AO（m2） BO（n2） CO（mn） DO（m+n）11、算法分析的两个主要方面是（ ）。A正确性和简明性 B数据复杂性和程序复杂性C可读性和可维护性D时间复杂性和空间复杂性二、填空题：1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、（ ）和（ ）。2、数据的逻辑结构是从逻辑关系上描述数据，它与数据的（）无关，是独立于计算机的。3、( )结构与数据元素本身的内容和形式无关。 4、程序段“for(i=1;i=n;i+) k+; for(j=1;j=n;j+) x=x+k;”的时间复杂度为( )。5、数据的存储结构（物理结构）可以用（ ）、（ ）、（ ）及散列存储等四种存储方法表示。三、 判断题：1、顺序存储方式优点是存储密度大，且插入和删除运算效率高。 （ ）2、顺序存储结构属于静态存储结构，链式存储结构属于动态存储结构。 （ ）3、线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。 （ ）4、数据的机内表示称为数据的存储结构。 （ ）5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（ ）6、数据元素是数据的最小单位。 （ ）7、基于某种逻辑结构之上的运算，其实现是惟一的。 （ ）参考答案（绪论）一、选择题1234567891011BDDCADCBACD二、填空题1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、（存储结构）和（运算）。2、数据的逻辑结构是从逻辑关系上描述数据，它与数据的（）无关，是独立于计算机的。3、(逻辑)结构与数据元素本身的内容和形式无关。 4、程序段“for(i=1;i=n;i+) k+; for(j=1;jnext=P-next;P-next=S BP-next=S-next;S-next=P； CP-next=P;P-next=S； DP-next=S;S-next=P；3、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（ ） A（1） B（log2n） CO（n） DO（n2） 解析：单就插入运算而言，算法时间复杂度为（1），但要将指针定位到链表末尾，指针移动的时间复杂度为O（n）；4、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（ ） A顺序表 B用头指针表示的单循环链表 C用尾指针表示的单循环链表 D单链表 解析：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。5、线性表是（ ） A一个有限序列，可以为空 B一个有限序列，不能为空 C一个无限序列，可以为空 D一个无限序列，不能为空6、在n个结点的双链表的某个结点前插入一个结点的时间复杂度是（ ） AO（n） BO（1） CO（log2n） DO（n2）7、线性表采用链式存储时，结点的地址（ ） A必须是连续的 B必须是不连续的 C连续与否均可 D必须有相等的间隔8、在单链表中，增加头结点的目的是（ ） A使单链表至少有一结点 B标志表中首结点位置 C方便运算的实现 D说明单链表是线性表的链式存储实现9、带头结点的单链表head为空的判定条件是（ ） Ahead = NULL； Bhead - next = NULL； Chead - next = head； Dhead ! = NULL；10、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为（ ） A（1） B（n） C（n2） D（log2n）11、下列有关线性表的叙述中，正确的是（ ） A线性表中的元素之间是线性关系 B线性表中至少有一个元素 C线性表中任何一个元素有且仅有一个直接前趋 D线性表中任何一个元素有且仅有一个直接后继12、在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的（ ） A直接前趋 B直接后继 C开始结点 D终端结点13、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。An B.2n-1 C.2n D.n-114、链表不具有的特点是（ ）。A随机访问 B不必事先估计存储空间C插入删除时不需移动元素 D所需的空间与线性表成正比15、在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入s结点，则执行的操作是（ ）。 As-next=p-next;p-next=s; Bq-next=s;s-next=p;Cp-next=s-next;s-next=p; Dp-next=s;s-next=q;16