1 概述一、选择题：1、下列算法的时间复杂度是（）for(i=0;i<n;i+ +)c[i]=i；A．O（1）B．O（n）C．O（log2n）D．O（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;i<m;i+ +)for(j=0;j<n;j+ +)a[i][j]=i*j；A．O（m2）B．O（n2）C．O（m×n）D．O（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、数据元素是数据的最小单位。
（）8、基于某种逻辑结构之上的运算，其实现是惟一的。
（）2 线性表一、选择题：1、在表长为n的顺序表上做插入运算，平均要移动的结点数为（）。
A．n B．n/2 C．n/3 D．n/42、在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，则执行（）A．S->next=P->next;P->next=SB．P->next=S->next;S->next=P；C．P->next=P;P->next=S；D．P->next=S;S->next=P；3、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（）A．Ｏ（1）B．Ｏ（log2n）C．O（n）D．O（n2）4、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）A．顺序表B．用头指针表示的单循环链表C．用尾指针表示的单循环链表D．单链表5、线性表是（）1A．一个有限序列，可以为空B．一个有限序列，不能为空C．一个无限序列，可以为空D．一个无限序列，不能为空6、在n个结点的双链表的某个结点前插入一个结点的时间复杂度是（）A．O（n）B．O（1）C．O（log2n）D．O（n2）7、线性表采用链式存储时，结点的地址（）A．必须是连续的B．必须是不连续的C．连续与否均可D．必须有相等的间隔8、在单链表中，增加头结点的目的是（）A．使单链表至少有一结点B．标志表中首结点位置C．方便运算的实现D．说明单链表是线性表的链式存储实现9、带头结点的单链表head为空的判定条件是（）A．head = NULL；B．head - > next = NULL；C．head - > next = head；D．head ! = NULL；10、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为（）A．Ｏ（1）B．Ｏ（n）C．Ｏ（n2）D．Ｏ（log2n）11、下列有关线性表的叙述中，正确的是（）A．线性表中的元素之间是线性关系B．线性表中至少有一个元素C．线性表中任何一个元素有且仅有一个直接前趋D．线性表中任何一个元素有且仅有一个直接后继12、在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的（）A．直接前趋B．直接后继C．开始结点D．终端结点13、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A．n B.2n-1 C.2n D.n-114、链表不具有的特点是（）。
A．随机访问B．不必事先估计存储空间C．插入删除时不需移动元素D．所需的空间与线性表成正比15、在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入s 结点，则执行的操作是（）。
A．s->next=p->next;p->next=s; B．q->next=s;s->next=p;C．p->next=s->next;s->next=p; D．p->next=s;s->next=q;16、链表具有的特点是（）。
A．可随机访问任一元素B．插入、删除需要移动元素C．不必事先估计存储空间D．存储空间是静态分配的17、一个顺序表一旦说明，其中可用空间大小（）A．已固定B．可以改变C．不能固定D．动态变化18、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）2存储方式最节省时间。
A．顺序表B．单链表C．双向链表D．单循环链表19、两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素的前驱的条件是（）。
A．P->next==Q B．Q->next==PC．P==Q D．P->next==Q->next20、链表不具有的特点是（）。
A．可随机访问任一元素B．插入、删除不需要移动元素C．不必事先估计存储空间D．所需空间与线性表长度成正比21、下面关于线性表的叙述中，错误的是（）。
A．线性表采用顺序存储，必须占用一片连续的存储单元B．线性表采用顺序存储，便于进行插入和删除操作C．线性表采用链接存储，不必占用一片连续的存储单元D．线性表采用链接存储，便于进行插入和删除操作22、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前趋（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序23、在一个单链表中，若删除p指向结点的后继结点，则执行的操作为（）。
A．q=p->next;p->next=p->next->next;free(q);B．p=p->next;q=p->next;p=q->next;free(q);C．q=p->next->next;p=p->next;free(q);D．p=p->next->next;q=p->next;free(q);二、填空题：1、在双链表中要删除已知结点*p，其时间复杂度为（）。
2、在仅有尾指针R指示的单循环链表R中，在表尾插入一个结点S的语句序列是（）。
3、在带头结点的双链表Ｌ中，指针Ｐ所指结点是开始结点的条件是（）。
4、在具有n个结点的双链表中做插入、删除运算，平均时间复杂度为（）。
5、在一个长度为n的顺序表中第i个元素（1 ≤ i≤n）之前插入一个元素时，需向后移动（）个元素。
6、在双循环链表中，若要在指针p所指结点之前插入指针s所指的结点，则需执行下列语句：s->prior=p->prior;p->prior->next=s;( )和p->prior=s;。
7、已知指针p指向双向链表中的一个结点（非首结点、非尾结点），则将结点s插入在p 结点的直接后继位置的语句是（）s->prior=p；s->next->prior=s；p->next=s;8、已知带表头结点的单链表L，指针p指向L链表中的一个结点（非首结点、非尾结点），则删除结点p的直接后继结点的语句是（）；删除首结点的语句是（）。
3三、判断题：1、在有序的顺序表和有序的链表上，均可以使用折半查找法来提高查找速度。
（）2、顺序存储的线性表可以随机存取。
（）3、线性表采用顺序存储，必须占用一片连续的存储单元。
（）4、线性表的顺序存储结构优于链式存储结构。
（）四、程序设计题：1、已知带头结点的单链表head中的结点是按整数值递增排序的，写一算法将值为x的结点插入到表head中，使head仍然有序。
2、用尾插入法建立带头结点的单链表。
3、写出将整数i插入到无头结点的链栈中的算法。
4、对给定的单链表L，编写一个删除L中值为x的结点的直接前趋结点算法。
]3栈和队列一、选择题：1、循环队列是空队列的条件是（）A．Q - > rear = = Q - > front B．（Q - > rear + 1）%maxsize = = Q - > frontC．Q - > rear = = 0 D．Q - > front = = 02、链栈与顺序栈相比，比较明显的优点是（）A．插入操作更加方便B．删除操作更加方便C．不会出现下溢的情况D．不会出现上溢的情况3、若一个栈的输入序列是１，２，３，……，n，输出序列的第一个元素是ｎ，则第ｉ个输出元素是（）A．n - i B．n – i + 1 C．i D．不确定4、栈与一般线性表的区别主要在（）A．元素个数B．元素类型C．逻辑结构D．插入、删除元素的位置5、一个链栈的栈顶指针是top，则执行出栈操作时（栈非空），用x保存被删除结点，则执行（）A．x = top;top = top - > next；B．x = top - > data；C．top = top - > next;x = top - > data；D．x = top - > data;top = top - > next；6、对于一个栈，给定输入序列为1，2，3，则下列不可能为输出序列的是（）A．1，2，3 B．3，2，1 C．3，1，2 D．2，1，37、在链接队列执行入队操作（）4A．需判别队是否空B．需判别队是否满C．限制在链表头p进行D．限制在链表尾p进行8、以下不属于栈的基本运算是（）。