练习题2
1．单项选择题
（1）线性表是（ ）。
A．一个有限序列，可以为空
B．一个有限序列，不可以为空
C．一个无限序列，可以为空
D．一个无限序列，不可以为空
（2）顺序表具有随机存取特性，指的是（ ）。
A．查找值为x的元素的时间与顺序表中元素个数n无关
B．查找值为x的元素的时间与顺序表中元素个数n有关
C．查找序号为i的元素的时间与顺序表中元素个数n无关
D．查找序号为i的元素的时间与顺序表中元素个数n有关
（3）在n个元素的顺序表中，算法的时间复杂度是O（1）的操作是（ ）。
A．访问第i个元素（2≤i≤n）及其前驱元素
B．在第i（1≤i≤n）个元素后插入一个新元素
C．删除第i个元素（1≤i≤n）
D．将n个元素从小到大排序
（4）在含有127个元素的顺序表中插入一个新元素，平均移动元素的次数是（ ）。
A．8
B．63.5
C．63
D．7
（5）将两个分别含有m、n个元素的有序顺序表归并成一个有序顺序表，对应算法的时间复杂度是（ ）。这里MIN表示取最小值。
A．O（n）
B．O（m）
C．O（m+n）
D．O（MIN（m，n））
（6）线性表采用链表存储结构时，其存放各个元素的单元地址（ ）。
A．必须是连续的
B．一定是不连续的
C．部分地址必须是连续的
D．连续与否均可以
（7）线性表的链式存储结构和顺序存储结构相比，其优点是（ ）。
A．所有的操作算法实现简单
B．便于随机存取C.便于插入和删除元素
D．节省存储空间
（8）关于线性表的顺序存储结构和链式存储结构的描述中，正确的是（ ）。
Ⅰ．线性表的顺序存储结构优于链式存储结构
Ⅱ．顺序存储结构比链式存储结构的存储密度高
Ⅲ．如需要频繁插入和删除元素，最好采用顺序存储结构
Ⅳ．如需要频繁插入和删除元素，最好采用链式存储结构
A．Ⅰ、Ⅱ、Ⅲ
B．Ⅱ、Ⅳ
C．Ⅱ、Ⅲ
D．Ⅲ、Ⅳ
（9）设线性表中有n个元素，以下运算中，（ ）在单链表上实现要比在顺序表上实现效率更高。
A．删除指定位置元素的后一个元素
B．在尾元素的后面插入一个新元素
C．顺序输出前k（k＜n）个元素
D．交换第i个元素和第n—i+1个元素的值
（10）以下关于单链表的叙述中，不正确的是（ ）。
A．结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
B．逻辑上相邻的元素物理上不必相邻
C．可以通过头结点直接计算第i个结点的存储地址
D．插入、删除运算操作方便，不必移动结点
（11）通过含有n（n≥1）个元素的数组a，采用头插法建立一个单链表L，则L中结点值的次序（ ）。
A．与数组a的元素次序相同
B．与数组a的元素次序相反
C．与数组a的元素次序无关
D．以上都不对
（12）在含有n（n≥1）个结点的单链表中，实现（ ）运算的时间复杂度为O（n）。
A．遍历单链表来求第i个结点值
B．在地址为p的结点之后插入一个新结点
C．删除链表的首结点
D．删除地址为p的结点的后继结点
（13）已知两个长度分别为m和n的升序单链表，若将它们合并为一个长度为m+n的升序单链表，则最好情况下的时间复杂度是（ ）。
A．O（n）
B．O（m×n）
C．O（MIN（m，n））
D．O（MAX（m，n））
（14）与非循环单链表相比，循环单链表的主要优点是（ ）。
A．不再需要头指针
B．已知某个结点的位置后，能够容易地找到它的前驱结点
C．在进行插入、删除操作时，能更好地保证链表不断开
D．从表中任意结点出发都能扫描到整个链表
（15）与单链表相比，双链表的优点之一是（ ）。
A．插入、删除操作更简单
B．可以进行随机访问
C．可以省略表头指针或表尾指针
D．访问前后相邻结点更方便
（16）在长度为n（n≥1）的双链表中插入一个结点（非尾结点）要修改（ ）个指针域。
A．1
B．2
C．3
D．4
（17）在长度为n（n≥1）的双链表L中，在p所指结点之前插入一个新结点的时间复杂度为（ ）。
A．O（1）
B．O（n）
C．O（n2）
D．O（nlog2n）
（18）非空的循环单链表L的尾结点（由p所指向）满足（ ）。
A．p—>next==NULL
B．p==NULL
C．p—>next==L
D．p==L
（19）在长度为n（n≥1）的循环双链表L中，删除尾结点的时间复杂度为（ ）。
A．O（1）
B．O（n）
C．O（n2）
D．O（nlog2n）
（20）某线性表最常用的操作是在尾元素之后插入一个元素和删除尾元素，则采用以下（ ）存储方式最节省运算时间。
A．单链表
B．循环单链表
C．双链表
D．循环双链表
2．填空题
（1）为了设置一个空的顺序表L，采用的操作是（ ）。
（2）在长度为n的顺序表L中查找第i个元素，其时间复杂度为（ ）。
（3）在长度为n的顺序表L中查找值为x的元素，其时间复杂度为（ ）。
（4）在一个长度为n（n≥1）的顺序表中删除第i个元素（1≤i≤n）时，需向前移动（ ）个元素。
（5）在线性表的顺序存储结构中，元素之间的逻辑关系是通过元素的（ ① ）表示的；在线性表的链式存储结构中，元素之间的逻辑关系是通过结点的（ ② ）表示的。
（6）在含有n（n＞1）个结点的单链表中，要删除某一指定的结点，必须找到该结点的（ ① ）结点，其时间复杂度为（ ② ）。
（7）删除单链表L中p结点（非尾结点）的后继结点并释放其空间，对应的语句是（ ）。
（8）在单链表L中p结点之后插入s结点，对应的语句是（ ）。
（9）在含有n个结点的双链表中，要删除p所指结点（非首结点）的前驱结点，其时间复杂度为（ ）。
（10）带头结点的循环单链表L为空的条件是（ ）。
3．简答题
（1）比较线性表的顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？
（2）对于表长为n的顺序表，在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需要移动的元素的平均次数为多少？删除一个元素所需要移动的平均次数为多少？
（3）在链表中设置头结点的作用是什么？
（4）对于双链表和单链表，在两个结点之间插入一个新结点时需修改的指针各为多少个？
（5）某含有n（n＞1）结点的线性表中，最常用的操作是在尾元素之后插入一个元素和删除第一个元素，则采用以下哪种存储方式最节省运算时间？
①单链表；
②仅有头指针不带头结点的循环单链表；
③双链表；
④仅有尾指针的循环单链表。
4．算法设计题
（1）设计一个算法，判断顺序表L中所有元素是否是递增有序的。
（2）设计一个算法，将顺序表L的所有元素逆置，要求算法空间复杂度为O（1）。
（3）有一个非空整数顺序表L，其中元素值可能重复出现，设计一个算法，在最后一个最大值元素之后插入一个值为x的元素。
（4）设计一个算法，通过相邻两个元素交换的方法将非空顺序表L中最大元素移到最后面（假设最大元素唯一）。
（5）设计一个算法删除单链表L中第一个值为x的结点。
（6）设计一个算法判定单链表L的所有结点值是否是递增的。
（7）有一个整数单链表A，设计一个算法，将其拆分成两个单链表A和B，使得A单链表中含有所有的偶数结点，B单链表中含有所有的奇数结点，且保持原来的相对次序。
（8）有一个递增有序单链表L，设计一个算法向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。
（9）有一个带头结点的非空单链表L，设计一个算法由L复制产生另外一个结点值及其顺序完全相同的带头结点单链表L1。
（10）设计一个算法，将一个带头结点的非空循环单链表L中最后一个最小值结点移到表头。
（11）对于有n（n≥1）个数据结点的循环单链表L，设计一个算法将所有结点逆置。
（12）有一个双链表L，设计一个算法查找第一个元素值为x的结点，将其与前驱结点进行交换。
（13）设有一个含两个以上结点的双链表L，设计一个算法将最后两个结点进行交换。设L中数据结点个数为n，分析你所设计算法的时间复杂度。
（14）有一个非空循环双链表L，设计一个算法删除所有值为x的结点。
（15）设有一个含两个以上结点的循环双链表L，设计一个算法将最后两个结点进行交换。设L中数据结点个数为n，分析你所设计算法的时间复杂度。