顺序表、链表题库word版.doc

第三章 顺序表
一、填空
1． 若线性表最常用的操作是存取第 i 个元素及其前驱元素的值，则采用（ ）存储结构最节省运算时间。
2．顺序存储结构的线性表中所有元素的地址（ ）连续。
3．顺序存储结构的线性表其物理结构与逻辑结构是（ ）的。
4．在具有n个元素的顺序存储结构的线性表任意一个位置中插入一个元素，在等概率条件下，平均需要移动（ ）个元素。
5．在具有n个元素的顺序存储结构的线性表任意一个位置中删除一个元素，在等概率条件下，平均需要移动（ ）个元素。
6．在具有n个元素的顺序存储结构的线性表中查找某个元素，平均需要比较（ ）次。
7．当线性表的元素基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中第i个元素时，应采用( )存储结构。
8．顺序存储结构的线性表中，插入或删除某个元素时，元素移动的次数与其位置（ ）关。（填有或无）。
9．顺序存储结构的线性表中，访问第i个元素与其位置（ ）关。（填有或无）。
10．在具有n个元素的顺序存储结构的线性表中要访问第i个元素的时间复杂度是（ ）。
11．在顺序表L中的i个位置插入某个元素x，正常插入时，i位置以及i位置以后的元素需要后移，首先后移的是（ ）个元素。
12．要删除顺序表L中的i位置的元素x，正常删除时，i位置以后的元素需要前移，首先前移的是（ ）元素。
13．若顺序表中的元素是从1位置开始存放的，要在具有n个元素的顺序表中插入一个元素，合法的插入位置是（ ）。
14．若顺序表中的元素是从1位置开始存放的，要删除具有n个元素的顺序表中某个元素，合法的删除位置是（ ）。
15．在具有n个元素的顺序存储结构的线性表中删除某个元素的时间复杂度是（ ）。
16．在具有n个元素的顺序存储结构的线性表中插入某个元素的时间复杂度是（ ）。
17．在具有n个元素的顺序存储结构的线性表中要访问第i个元素的后继结点的时间复杂度是（ ）。
18．在具有n个元素的顺序存储结构的线性表中，若给定的是某个元素的关键字值，要访问该元素的其它信息的时间复杂度是（ ）。
19．在顺序表中查找某个元素时，需要将当前元素与要找的元素进行若干次的比较，算法经常用while循环来实现，while里面的条件是没找完且（ ）。
20．在顺序表中查找某个元素时，需要将当前元素与要找的元素进行若干次的比较，算法经常用while循环来实现，while里面的条件是（ ）且没找到。
21．如果要将两个升序排列的整型顺序表a中的元素合并到b中（b的空间足够大），合并后表中元素依然升序排列，可以通过多次调用查找函数查找插入位置，再调用（ ）函数来实现插入。
22．若要将一个整型的顺序表拆分为一个存放正数，另一个存放非正数的两个顺序表，存放正数的顺序表用原来的表，时间复杂度为（ ）。
23．顺序表中查找某个元素时，从前到后查找与从后到前查找的时间复杂度（ ）同。
二、简答题
，正常插入返回1，否则返回0或-1，请在空的下划线上填写合适的内容完成该算法。
//表中最多可以放置MAXLEN个元素
int seq_ins(SeqList *SeqL,int i, DataType x)
{ int j;
if ( ) /*表满*/
{ printf("the list is full\n");
return 0;
}
else if (i<1||i> SeqL->len+1) /*位置不对*/
{ printf("the position is invalid\n ");
return -1;
}
else /*正常插入*/
{ for (j=SeqL->len;j>=i;j--)
/*元素后移*/
/*插入元素*/
(SeqL->len)++; /*表长加1*/