文档介绍：...wd...
...wd...
顺序表的第i〔1≤i≤n+1〕个元素之前插入一个元素，需向后移动
n-i+1 个元素，删除第i〔1≤i≤n〕个元素时，需向前移动n-i个元素。
3. 在单循环链表中，由rear指向表尾，在表尾插入一个结点s的操作顺序是s->next =rear->next; rear->next =s; rear =s;；删除开场结点的操作顺序为q=rear->next->next; rear->next->next=q->next; delete q;。
二. 选择题
，称之为： C
A存储构造 B逻辑构造 C顺序存储构造 D链式存储构造
2. 在n个结点的顺序表中，算法的时间复杂度是O〔1〕的操作是： A
A 访问第i个结点〔1≤i≤n〕和求第i个结点的直接前驱〔2≤i≤n〕
B 在第i个结点后插入一个新结点〔1≤i≤n〕
C 删除第i个结点〔1≤i≤n〕 D 将n个结点从小到大排序
3. 线性表L在B情况下适用于使用链式构造实现。
A需经常修改L中的结点值 B需不断对L进展删除插入
CL中含有大量的结点 D L中结点构造复杂
4. 单链表的存储密度C
A大于1 B等于1 C小于1 D不能确定
三. 判断题
1. 线性表的逻辑顺序和存储顺序总是一致的。F
2. 线性表的顺序存储构造优于链接存储构造。F
3. 设p，q是指针，假设p=q，则*p=*q。F
4. 线性构造的根本特征是：每个元素有且仅有一个直接前驱和一个直接后继。F
四. 简答题
1. 分析以下情况下，采用何种存储构造更好些。
(1)假设线性表的总长度根本稳定，且很少进展插入和删除操作，但要求以最快的速度存取线性表中的元素。
(2)如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。
(3)描述一个城市的设计和规划。
⑴ 应选用顺序存储构造。很少进展插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储构造。
⑵ 应选用链式存储构造。链表容易实现表容量的扩大，适合表的长度动态发生变化。
⑶ 应选用链式存储构造。因为一个城市的设计和规划涉及活动很多，需要经常修改、扩大和删除各种信息，才能适应不断开展的需要。而顺序表的插入、删除的效率低，故不适宜。
...wd...
...wd...
...wd...
五. 算法设计
1. 数组A[n]中的元素为整型，设计算法将其调整为左右两局部，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O(n)。
2. 线性表存放在整型数组A[arrsize]的前elenum 个单元中，且递增有序。编写算法，将元素x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。
int insert (datatype A[],int *elenum,datatype x)    /*设elenum为表的最大下标*/
{if (*elenum==arrsize-1)  return 0;     /*表已满，无法插入*/
else {i=*elenum;
         while (i>=0 && A[i]>x)      /*边找位置边移动*/
{A[i+1]=A[i];
i--;
}
         A[i+1]=x;         /*找到的位置是插入位的下一位*/
         (*elenum)++;
return 1;         /*插入成功*/
}
}
O〔n〕
...wd...
...wd...