a[i][j]=0;
（18）有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为T1=○（2n），A2的时间复杂度为T2=○（n2），仅就时间复杂度而言，请具体分析这两个算法哪一个好。
综合应用题
（19）设n是偶数，且有程序段：
for（i=1;i<=n;i++）
if（2*i<=n）
for（j=2*I;j<=n;j++）
y=y+i*j;
则语句y=y+i*j的执行次数是多少？
要求列出计算公式。
（20）斐波那契数列Fn定义如下：
F0=0，F1=1，…，Fn=Fn-1+Fn-2n=2，3，…
请就此斐波那契数列，回答下列问题。
①在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，…，F1，F0精确计算多少次？
2用大○表示法给出递归计算时递归函数的时间复杂度是多少？
（21）运算是数据结构的一个重要方面。
举例说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同，因而具有不同的特性，则这两个数据结构是不同的。
（22）针对给定的实际问题建立数据结构时，应从哪些方面考虑。
2
线性表的逻辑结构
选择题
（1）线性表是具有n个（）的有限序列。
A．数据B．字符C．数据元素D．数据项
（2）线性表是（）。
A．一个有限序列，可以为空B．一个有限序列，不能为空
C．一个无限序列，可以为空D．一个无限序列，不能为空
（3）关于线性表，下列说法中正确的是（）。
A．线性表中每个元素都有一个直接前驱和一个直接后继
B．线性表中的数据元素可以具有不同的数据类型
C．线性表中数据元素的类型是确定的
D．线性表中任意一对相邻的数据元素之间存在序偶关系
（4）（）是一个线性表。
A．由n个实数组成的集合B．由所有实数组成的集合
C．由所有整数组成的序列D．由n个字符组成的序列
3
顺序线性表
选择题
（1）已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（）。
A．108B．180C．176D．112
（2）在长度为n的线性表中查找值为x的数据元素的时间复杂度为（）。
A．○（0）B．○
（1）C．○（n）D．○（n2）
（3）在一个长度为n的线性表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动（）个元素，删除第i（1≤i≤n）个元素时，需向前移动（）个元素。
A．n-iB．n-i+1C．n-iD．n-i+1
（4）线性表的顺序存储结构是一种（）的存储结构。
A．随机存取B．顺序存取C．索引存取D．散列存取
（5）顺序存储结构的优点是（）。
A．存储密度大B．插入运算方便
C．删除运算方便D．可方便地用于各种逻辑结构的存储表示
（6）n个结点的线性表采用数组实现，算法的时间复杂度是○
（1）的操作是（）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B．在第i个结点后插入一个新结点（1≤i≤n）
C．删除第i个结点（1≤i≤n）
D．以上都不对
（7）对于顺序存储的线性表，访问某个元素和增加一个元素的时间复杂度为（）。
A．○（n）、○（n）B．○（n）、○
（1）C．○
（1）、○（n）D．○
（1）、○
（1）
（8）顺序表的插入算法中，当n个空间已满时，可再申请增加分配m个空间，若申请失败，则说明系统没有（）可分配的存储空间。
A．m个B．m个连续的C．n+m个D．n+m个连续的
应用题
（9）设A是一个线性表（a1，a2，…，an），采用顺序存储结构，则在等概论的前提下，平均每插入一个元素需要移动的元素个数为多少？
若元素插在ai与ai+1之间（1≤i≤n）的概率为（n-i）/（n（n-1）/2），则平均每插入一个元素所移动的元素个数是多少？
（10）设n表示线性表中的元素个数，E表示存储数据元素所需要的存储单元大小，D表示可以在数组中存储线性表的最大元素个数（D≥n），则使用顺序存储方式存储线性表需要多少存储空间？
（11）在什么情况下线性表使用顺序存储比较好？
算法设计题
（12）试以顺序表作存储结构，实现线性表就地逆置。
（13）设计算法判断给定字符串是否是回文。
所谓回文是正读和反读均相同的字符串，例如abcba或abba是回文，而abcda不是回文。
（14）设计一个时间复杂度为○（n）的算法，实现将数组A[n]中所有元素循环左移k个位置。
（15）已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为○（n）。
（16）假定数组中有多个零元素，设计算法将数组中所有非零元素移到数组的前端。
（17）顺序存储的线性表A，其数据元素为整型，设计算法将A拆成B和C两个表，使A中值大于0的元素存入表B，值小于0的元素存入表C，要求B和C不另外设置存储空间而利用A的空间。
（18）已知顺序表L中的元素递增有序排列，设计算法将元素x插入到表L中并保持表L仍递增有序。
（19）设计一个高效算法，在顺序表中删除所有元素值为x的元素，要求空间复杂度为○
（1）。
（20）设计算法实现从顺序表L中删除所有值在x和y之间的所有元素，要求时间性能复杂度为○（n），空间性能为○
（1）。
（21）设计算法删除顺序表中重复的元素，要求算法移动元素的次数较少并使剩余元素间的相对次序保持不变。
（22）给定n个记录的有序序列A[n]和m个记录的有序序列B[m]，将它们归并为一个有序序列，存放在C[n+m]中，试写出这一算法（假设A、B和C均为升序序列）。
4
线性链表
选择题
（1）线性表的链接存储结构是一种（）的存储结构。
A．随机存取B．顺序存取C．索引存取D．散列存取
（2）线性表采用链接存储时，其（）。
A．地址必须是连续的B．部分地址必须是连续的
C．地址一定是不连续的D．地址连续与否均可以
（3）链表不具有的特点是（）。
A．可随机访问任一元素B．插入、删除不需要移动元素
C．不必事先估计存储空间D．所需空间与线性表长度成正比
（4）在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。
A．○
（1）B．○（n）C．○（n2）D．○（nlog2n1）
（5）对于n个元素组成的线性表，建立一个单链表的时间复杂度是（）。
A．○
（1）B．○（n）C．○（n2）D．○（nlog2n1）
（6）对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（）。
A．○
（1）B．○（n）C．○（n2）D．○（nlog2n1）
（7）在单链表中删除指针p所指结点的后续结点，则执行（）。
A．p->next=p->next->nextB．p->next=p->next
C．p=p->next->nextD．p=p->next;p->next=p->next->next
（8）在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入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
（9）在一个长度为n（n>1）的带头结点的单链表h上，另设有尾指针r指向尾结点，执行（）操作与链表的长度有关。
A．删除单链表中的第一个元素
B．删除单链表中的最后一个元素
C．在单链表第一个元素前插入一个新元素
D．在单链表的最后一个元素后插入一个新元素
（10）在单链表中附加头结点的目的是为了（）。
A．保证单链表中至少有一个结点B．标识单链表中首结点的位置
C．方便运算的实现D．说明单链表是线性表的链式存储
（11）将长度为n个单链表链接在长度为m的单链表之后的算法，其时间复杂度是（）。
A．○
（1）B．○（n）C．○（m）D．○（n+m）
（12）循环单链表的主要优点是（）。
A．不再需要头指针了
B．从表中任一结点出发都能扫描到整个链表
C．已知某个结点的位置后，能够容易找到它的直接前驱
D．在进行插入、删除操作时，能更好地保证链表不断开
（13）将线性表（a1，a2，…，an）组织为一个带头结点的循环单链表，设H为链表的头指针，则链表中最后一个结点的指针域中存放的是（）。
A．变量H的地址B．变量H的值
C．元素a1的地址D．空指针
（14）非空的循环单链表L的尾结点p满足（）。
A．p=NULLB．p->next=NULLC．p->next=LD．p=L
（15）若要在○
（1）的时间内实现两个循环单链表的首尾相接，则两个循环单链表应各设一个指针，分别指向（）。
A．各自的头结点B．各自的尾结点
C．各自的第一个元素结点D．一个表的头结点，一个表的尾结点
（16）设线性表非空，（）可以在○
（1）的时间内在表尾插入一个新结点。
A．带头结点的单链表，有一个链表指针指向头结点
B．带头结点的循环单链表，有一个链表指针指向头结点
C．不带头结点的单链表，有一个链表指针指向表的第一个结点
D．不带头结点的循环单链表，有一个链表指针指向表中某个结点（除第一个结点外）
（17）设指针rear指向带头结点的循环单链表的尾指针，若要删除链表的第一个元素结点，正确的操作是（）。
A．s=rear;rear=rear->next;
B．rear=rear->next;
C．rear=rear->next->next;
D．s=rear->next->next;rear->next->next=s->next;
（18）设有两个长度为n个单链表，以h1为头指针的链表是非循环的，以h2为尾指针的链表是循环的，则（）。
A．在两个链表上删除第一个结点的操作，其时间复杂度均为○
（1）
B．在两个链表的表尾插入一个结点的操作，其时间复杂度均为○（n）
C．循环链表要比非循环链表占用更多的存储空间
D．循环链表要比非循环链表占用更少的存储空间
（19）使用双链表存储线性表，其优点是可以（）。
A．提高查找速度B．更方便数据的插入和删除
C．节约存储空间D．很快回收存储空间
（20）与单链表相比，双链表的优点之一是（）。
A．插入和删除操作更简单B．可以进行随机访问
C．可以省略表头指针或表尾指针D．访问其后相邻结点更灵活
（21）带头结点的循环双链表L为空表的条件是（）。
A．L->next->prior=NULLB．L->prior=L
C．L->next=LD．B和C都对
（22）在循环双链表的p所指结点后插入s所指结点的操作是（）。
A．p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;
B．p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;
C．s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;
D．s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;
（23）在双链表中指针pa所指结点后面插入pb所指结点，执行的语句序列是（）。
①pb->next=pa->next;②pb->prior=pa;
③pa->next=pb;④pa->next->prior=pb;
A．①②③④B．④③②①C．③④①②D．①④③②
（24）在一个双链表中，删除结点p的操作是（）。
A．p->prior->next=p->next;p->next->prior=p->prior;
B．p->prior=p->prior->prior;p->prior->prior=p;
C．p->next->prior=p;p->next=p->next->next;
D．p->next=p->prior->prior;p->prior=p->prior->prior;
应用题
（25）单链表设置头结点的作用是什么？
（26）线性表的顺序存储结构具有三个弱点：
其一，插入或删除操作需要移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。
试问，线性表的链接存储结构是否能够克服上述三个弱点？
（27）若频繁地对一个线性表进行插入和删除操作，该线性表采用什么存储结构比较好？
（28）设n表示线性表中的元素个数，P表示指针所需的存储单元大小，E表示存储数据元素所需的存储单元大小，则使用单链表存储方式存储该线性表需要多少存储空间（不考虑头结点）？
算法设计题
（29）设计算法依次打印单链表中每个结点的数据信息。
（30）求单链表的长度。
（31）设计算法将值为x的结点插入到不带头结点的单链表L中值为k的结点之前，若找不到值为k的结点，则将x插入到链表的末尾。
（32）判断非空单链表是否递增有序。
（33）已知非空线性链表由list指出，结点结构为（data，link）。
请编写算法，将链表中数据域最小的结点移到链表的最前面。
要求：
不得额外申请新的结点。
（34）给定一个带头结点的单链表，设head为头指针，设计算法按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：
不允许使用数组作辅助空间）。
（35）已知非空线性链表由list指出，设计算法交换p所指结点与其后续结点在链表中的位置（设p所指结点不是链表的最后一个结点）。
（36）设计算法实现将单链表就地逆置。
（37）头插法建立单链表。
（38）尾插法建立单链表
（39）复制一个单链表。
（40）设计算法实现将单链表就地逆置。
（41）在一个有序单链表（假设从小到大排列）中插入一个元素值为x的结点，使得插入后单链表仍然有序。
（42）设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。
（43）已知单链表中各结点的元素值为整型且递增有序，设计算法删除表中大于mink且小于maxk的所有元素，并释放被删结点的存储空间。
（44）有两个整数序列A=（a1，a2，…，am）和B=（b1，b2，…，bn）已经存入两个单链表中，设计算法判断序列B是否是序列A的子序列。
（45）设线性表C=（a1，b1，a2，b2，…，an，bn）采用带头结点的单链表存储，设计算法将表C拆分为两个线性表A和B，使得A=（a1，a2，…，an），B=（b1，b2，…，bn）。
（46）有两个递增有序的单链表la和lb，设计算法将这两个单链表合并为一个有序链表。
（47）有两个有序的单链表，一个表为升序，另一个表为降序，设计算法将这两个链表合并为一个有序链表。
（48）已知单链表A和B的数据（设为整型）递增有序，设计算法利用
升级会员 