数据结构复习题：线性表 单选题
1、在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动_____个元素。 2、从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较__(n+1)/2___个结点。
3、在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点， 则执行_____。 4、线性表是_____ 。
5、对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的， 删除一个元素时大约要移动表中的_____个元素。
6、线性表采用链式存储时，其地址_____。
7、设单链表中指针p指着结点m，指针f指着将要插入的新结点x，当x插在链表中最后一个结点m之后时，只要先修改_____后修改p->link=f即可。
8、在双向链表存储结构中，删除p所指的结点时需修改指针_____。
9、在双向链表存储结构中，删除p所指的结点的前趋结点（若存在）时需修改指针_____。 10、根据线性表的链式存储结构，每个结点所含指针的个数，链表分为单链表和_____。 11、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上_____。 12、链表不具备的特点是_______。
13、不带头结点的单链表head为空的判定条件是______。 14、带头结点的单链表的head为空的判定条件是______。 15、带头结点的双循环表L为空表的条件是__L->next==L____。 16、非空的循环单链表head的尾结点(由p所指向)满足_______。
17、在循环双链表的p所指结点之前插入s所指结点的操作是_______。
18、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用___带头结点的双循环链表___存储方式最节省运算时间。
19、某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用___仅有尾指针的单循环链表__存储方式最节省运算时间。
20、需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是_______。
21、如果最常用的操作是取第i个结点及其前驱，则采用___顺序表___存储方式最节省时间。
22、在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是______。
23、在一个长度为n(n>1)的单链表上，设有头和尾两个指针，执行____删除单链表中的最后一个元素____操作与链表的长度有关。
24、设线性表有n个元素，以下算法中，_______在顺序表上实现比在链表上实现效率更高。
25、设线性表中有2n个元素，算法___删除所有值为x的元素____，在单链表上实现要比在顺序表上实现效率更高。
26、与单链表相比，双链表的优点之一是________。 27、如果对线性表的运算只有4种，即删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后一个元素的后面插入新元素，则最后使用___只有表头指针没有表尾指针的循环双链表_____。 28、如果对线性表的运算只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用_______。
29、设有两个长度为n的单链表，结点类型相同。若以h1为表头指针的链表是非循环的，以h2为表头指针的链表是循环的，则_______。
30、在长度为n的______上，删除第一个结点，其算法的时间复度为O(n)。
31、将两个各有n个元素的有序顺序表归并成一个有序顺序表，其最少的比较次数是__n___。
- 11 -
32、带头结点的单链表L为空的判定条件是______。
33、在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_______。 34、在一个长度为n(n>1)的带头结点的单链表h上，，另设有尾指针r(指向尾结点)，执行_______操作与链表的长度有关。
35、在一个双链表中，在*p结点之后插入结点*q的操作是______。 36、在一个双链表中，在*p结点之前插入*q结点的操作是______。 37、在一个双链表达式，删除*p结点的操作是_______。
38、在一个双链表中，删除*p结点之后的一个结点的操作是________。 39、非空的循环单链表L的尾结点(由p所指向)满足______。 40、带头结点的双循环链表L为空表的条件是______。
41、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用_____带头结点的循环双链表____存储方式最节省运算时间。
42、如果对含有n(n>1)个元素的线性表的运算只有4种:删除第一个元素；删除最后一个元素；在第一个元素前面插入新元素；在最后一个元素的后面插入新元素，则最好使用____只有头结点指针没有尾结点指针的循环双链表____。 43、某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，则采用____仅有尾结点指针的单循环链表___存储方式最节省运算时间。
44、设有两个长度为n的单链表，结点类型相同，若以h1为头结点的链表是非循环的，以h2为头结点指针的链表是循环的，则________。
45、在长度驎n(n>1)的___只有首结点指针h的不带头结点的循环单链表___上，删除第一个元素，其算法的时间复杂度为O(n)。
46、元素A、B、C、D依次进顺序栈后，栈顶元素是_______，栈底元素是______。 47、经过以下栈运算后，X的值是______。
InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x);
48、经过以下的栈运算后，StackEmpty(s)的值是______。 InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)
49、设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的输出序列不可能是______。 50、若线性表最常用的运算是存取第i个元素及其前驱的值,则采用______存储方式节省时间. 51、链表不具备的特点是______.
52、在一个长度为n的顺序存储的线性表中，向第i个元素(1<=i<=n+1)位置插入一个新元素时，需要从后向前依次后移_________个元素． 53、在一个长度为n的顺序存储的线性表中，删除第i个元素(1<=i<=n)时，需要从前向后依次前移____n-i_____个元素．
54、在一个长度为n的线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x同元素的平均比较次数，查找每个元素的概率都相等）为（ ）．
57、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行_________。
数据结构复习题：线性表 判断题
1、顺序存储的线性表可以随机存取。
2、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性， 因此，是属于同一数据对象。T
3、在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素。
- 12 -
4、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 5、链表的每个结点中，都恰好包含一个指针。
6、线性表中每个元素都有一个直接前驱和直接后继。
7、线性表中所有元素的排列顺序必须由小到大或由大到小。 8、静态链表的存储空间在运算中可以改变大小。
9、静态链表既有顺序存储结构的优点，又有动态链表的优点。所以，它存取表中的第i个元素的时间与i无关。
10、静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加。 11、静态链表与动态链表的插入、删除操作类似，不需做元素的移动。 12、线性表的顺序存储结构优于链式存储结构。
15、在双链表中，可以从任一结点开始沿同一方向查找任何其他结点。F
数据结构复习题：线性表 算法分析题
1、己知一个顺序表L,其中的元素按值非递减有序排列,设计一个算法插入一个元素x后保持该顺序表仍按递减有序排列。要求算法的空间复杂度为O(1)。
2、设计一个算法从顺序表L中删除所有值为X的元素。要求算法的空间复杂度为O(1)。
3、从顺序表L中删除重复的元素,并使剩余元素间的相应次序保持不变.要求本算法的空间复杂记度为O(1)。 4、有一个单链表(不同结点的数据域值可能相同),其头指针为head,设计一个算法计算数据域为x的结点个数。 5、己知线性表元素递增有序,并以带头结点的单链表作存储结构,设计一个高效算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素)。并分析所写算法的时间复杂度。 6、设计一个在带头结点的单链表中删除一个最小值结点的高效算法。
7、有一个不带头结点的单链表L(至少有1人结点),其头指针为head,设计一个算法将L逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点,如此等等。
8、用单链表表示集合,设计一个算法求两个集合的差。要求不破坏原有的结点。 9、用单链表表示集合,设计一个算法求两个集合的并。要求不破坏原有的结点。
10、设计一个算法,将一个头结点指针为a的单链表A分解成两个单链表A和B,其头结点指针分别为a和b,使得A链表中含有原链表A中序号为奇数的元素,而B链表中含有原链表A中序号为倒数的元素,且保持原来的相对顺序。 11、有一个单链表,其结点的元素值以递增有序排列,设计一个算法删除该单链表中多余的元素值相同的结点。 12、己知两个存放整数的有序单链表(己按整数从小至大的顺序排序),指针L1和L2分别指向这两个单链表的头结点。设计一个算法,将L1和L2合并成一个单链表,且新的链表仍按整数由小到大的顺序排列,新的单链表的结点由L1和L2的结点构成。要求合并后的单链表利用原来单链表的存储空间。
13、设计一个算法,将线性表lb连接到la之后,要求其时间复杂度为O(1),占用的辅助空间尽量小。描述所用的结构。
14、设指针p指向双链表中的结点X,指针f指向将要插入的新结点Y,Y要插入在结点X之后,写出指针需要修改的有关步骤。
15、有一个循环双链表,每个结点由两个指针(prior和next)以及关键字(data)构成,p指向其中某一结点,设计一个算法从该循环双链表中删除p所指的结点。
16、设有一个循环双链表,其中有一结点的指针为p,设计一个算法将p与其后续结点进行交换。
19、设A和B是两个单链表(带头结点)，其表中元素递增有序。设计一个算法将A和B归并成一个按元素值递增有序的单链表C，要求辅助空晨为O(1)，并分析算法的时间复杂度。
- 13 -
数据结构复习题：线性表 填空题
1、在线性结构中第一结点_____前驱结点，其余每个结点有且只有______个前驱结点；最后一个结点______后继结点。
2、对于顺序存储的线性表，当随机插入或删除一个元素时，约需平均移动表长______的元素。
3、对于长度为n的顺序表，插入或删除元素的时间复杂性为________；对于顺序栈或队列，插入或删除元素的时间复杂性为_________。
4、在线性表的顺序存储中，元素之间的逻辑关系是通过_____相邻位置_____决定的；在线性表的链接存储中，元素之间的逻辑关系是通过______连接指针______决定的。 5、一个单链表中删除*p结点时，应执行如下操作: (1)q=p->next;
(2)p->data=p->next->data; (3)p->next=__________; (4)free(q);
6、对于线性表的顺序存储，需要预先分配好存储空间，若分配太多则容易造成存储空间的__________，若分配太少又容易在算法中造成_____溢出_____，因此适应于数据量变化不大的情况；对于线性表的链接存储(假定采用动态结点)，不需要__________存储空间，存储器中的整个____动态存储区______都可供使用，分配和回收结点都非常方便，能够有效地利用存储空间，在算法中不必考虑_____溢出_____的发生，因此适应数据量变化较大的情况。
7、从顺序表中删除第i个元素时，首先把第i个元素赋给_____变参或函数名_____带回，接着从______连接指针_______开始向后的所有元素均___________一个位置，最后使线性表的长度_____________。
8、向一个长度为n的顺序表中的第i个元素(0<=i<=n-1)之前插入一个元素时，需向后移动______个元素。 9、在一个长度为n的顺序表删除第i个元素(0<=i<=n-1)时，需向前移动______个元素。 10、在单链表中设置头结点的作用是_____简化插入、删除算法______。 11、在单链表中，要删除某一指定的结点，必须找到该结点的_______结点。 12、访问单链表中的结点，必须沿着_____指针链___依次进行。
13、在双链表中，每个结点有两个指针域，一个指向________，另一个指向_________。 14、在___循环双___链表上，删除最后一个结点，其算法的时间复杂度为O(1)。 15、在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作。 (1)s->next=_________。 (2)p->next=s; (3)t=p->data;
(4)p->data=_________。 (5)s-.data=_________。
16、在一个单链表中删除p所指结点时，应执行以下操作： q=p->next;
p_data=p->next->data; p->next=______; free(q);
17、在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=_______和p->next=________的操作。
18、对于一个具有n个结点的单链表，在*p结点后插入一个新结点的时间复杂度是____O(1)____；在给定值
- 14 -
为x的结点后插入一后新结点的时间复杂度是________。
19、在线性表的顺序存储中，元素之间的逻辑关系是通过___物理存储位置___决定的；在线性表的链式存储中，元素之间的逻辑关系是通过___链域的指针值___决定的。
20、在一个长度为n的顺序表中删除第i个元素(1<=i<=n)时，需向前移动_______个元素。 21、为了设置一个空的顺序表L，采用的操作是___L->length=0___。 22、删除顺序表的______元素，不需要移动任何元素。
23、删除顺序表的___最后一个___元素，不需要移动的元素最多。 24、在顺序表_____元素后面插入一个元素，不需要移动任何元素。 25、插入顺序表的______元素，需要移动的元素最多。
26、在长度为n的顺序表L中查找指定元素值的元素，其时间复杂度为______。 27、求单链表长度的时间复杂度为_______。
28、删除单链表L中某结点*p之后的一个结点，其时间复杂度为______。 29、删除单链表L中某结点*p之前的一个结点，其时间复杂度为___O(n)___。
30、在一个单链表(己知每个结点含有数据域data和指针域next)中删除p所指结点时，应执行以下操作： (1)q=p->next;
(2)p->data=q->data; (3)p->next = _____; (4)free(q);
31、在一个单链表中的p所指结点之后插入*s结点时，应执行s->next=_____和p->next=______的操作。 32、对于一个具有n个结点的单链表，在*p结点后插入一个新结点的时间复杂度是_______;在给定值为x的结点后插入一个新结点的时间复杂度是_______。
33、删除双链表L中某结点*p之后的一个结点，其时间复杂度为_______。 34、删除双链表L中某结点*p之前的一个结点，其时间复杂度为_______。 35、在非循环的______链表中，可以用表尾指针代替表头指针。
36、对于双链表，在两个结点之间插入一个新结点需要修改的指针共______。 37、在一个双链表中，若要在*p结点之前插入结点*q，则执行的操作是______。 38、循环单链表L为空的条件是_____。 39、在单链表中,结点与结点之间的逻辑关系不是通过存储单元的顺序来表示的,而是通过___指向下一个结点的指针___来实现的.
40、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为____________，在表尾插入元素的时间复杂度为____________。
41、对于一个单链接存储的线性表，在表头插入结点的时间复杂度为____________，在表尾插入元素的时间复杂度为____________。
42、在线性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为____________，后继元素的下标为____________。
43、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为
_____p->next_______，若p为一个数组a中的下标，则其后继结点的下标的______a[p]->next______。 44、在循环单链表中，最后一个结点的指针域指向____________结点。
45、在双向链表中每个结点包含有两个指针域，一个指向其____________结点，另一个指向其____________结点。
46、在循环双向链表中表头结点的左指针域指向____________结点，最后一个结点的右指针域指向____________结点。
47、在以ＨＬ为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为____________和____________。
- 15 -