一、单项选择题。
1、在顺序表中查找第i个元素的时间效率最高的算法的时间的复杂度是 a 。
a. o(1) b. o() c. o(log2n) d. o(n)
2、最好的情况下，在顺序表中按值查找一个元素算法时间的复杂度是 d 。
a. o(n) b. o() c. o(log2n) d. o(1)
3、在查找顺序表各结点概率相等的情况下，顺序按值查找某个元素的算法的时间的复杂度是 b 。
a. o(1) b. o(n) c. o() d. o(log2n)
4、在带有头结点的单链中插入一个新结点时不可能修改 a 。
a. 头指针 b. 头结点指针域 c. 开始结点指针域 d. 其它结点指针域。
5、在带头结点的单链中删除由某个指针变量指向的结点的直接后继算法时间复杂度是 b 。
a. o() b. o(1) c. o(n) d. o(log2n)
6、在带头结点的单链中，若被删除结点位置概率相等，那么，删除第i个结点算法的时间复杂度是 d 。
a. o(1) b. o(log2n) c. o() d. o(n)
二、填空题。
1、顺序表的存储密度是 1 ，而链式存储结构的存储密度值一定是 < 1。
2、头指针的值或为null，或为单链表第1 个结点的地址。
3、在顺序表中按值查找一个元素的时间耗费不仅与表长有关，还与被查找元素在顺序表中的位置有关。
4、在不带头结点的单链表的结点类型为。
typedef strut node{
int data;
struct node * next;
tnode;
若sizeof(int)=2,sizeof(struct node *)4,则该单链表的存储密度值为 1/3 。
5、在单链表中查找第i个结点算法的时间复杂度是 o(n) 。
三、基础知识。
1、 试描述头指针、头结点、开始结点的区别，并说明头指针和头结点的作用。
头指针是一个指针变量。若相应的链表有表头结点，则头指针指向该头结点；否则，头指针的值或者为null或者为开始结点的地址。
头结点是在开始结点之前的一个附加的结点，它不存储线性表中的元素信息。它的引入，使得空表和非空表处理一致；还使得对链表在不同位置上的处理（插入、删除）一致。
开始结点是存放线性表第一个元素值的结点，它没有直接前驱。
2、 何时选用顺序表、何时选用链表作为线性表的存储结构为宜？
顺序表：若线性表大小事先知道，且插入、删除运算不多，而按序号查找运算较多时；
链表：若线性表中元素事先不知道有多少，或者插入、删除运算很多时。
3、 在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？
插入：n/2，插入位置、表中元素个数。
删除：(n-1)/2，删除结点位置、表中元素个数。
4、 为什么在单循环链表中设置尾指针比设置头指针好？
单循环链表的操作经常是对其开始结点和最后（终端）结点进行。用尾指针很容易表示开始结点（不带头结点：rear->next或带头结点：
rear->next->next）和终端结点（rear）。
5、 在单链表、双链表、单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去？若可以，其时间复杂度是多少？
单链表：无法。
双链表：可以；其时间复杂度是o(1)。
单循环链表：可以；其时间复杂度是o(n)。
6、 下述算法的功能是什么？
linklist demo (linklist l){/l是无头结点的单链表。
listnode * q, *p;
if (l &&l->next){
q=l; l=l->next; p=l;
while (p->next) p=p->next;
p->next=q; q->next=null;
return l;
//demo
若l指向的单链表至少有两个结点，则l指向第2个结点，把第1个结点移到最后一个结点之后，返回l值；否则直接返回l值。
四、算法设计题。
1、 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
status insert_sqlist(sqlist &va,int x)//把x插入递增有序表va中。
if(> return error;
for(i=>x&&i>=0;i--)
return ok;
//insert_sqlist
2、 试写一算法在带头结点的单链表结构上实现线性表操作locate（l，x）。
lnode* locate(linklist l,int x)//链表上的元素查找，返回指针。
for(p=l->next;p&&p->data!=x;p=p->next);
return p;
//locate
3、 试写一算法在带头结点的单链表结构上实现线性表操作length（l）。
int length(linklist l)//求链表的长度。
for(k=0,p=l;p->next;p=p->next,k++)
return k;
//length
4、 试写一算法实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1, a2, …an）逆置为（an, an-1, …a1）。
void reverse(sqlist &a)//顺序表的就地逆置。
for(i=0,j=
//reverse
5、 试写一算法，对单链表实现就地逆置。
void linklist_reverse(linklist &l)//链表的就地逆置；为简化算法，假设表长大于2
p=l->next;q=p->next;s=q->next;p->next=null;
while(s->next)
q->next=p;p=q;
q=s;s=s->next; /把l的元素逐个插入新表表头。
q->next=p;s->next=q;l->next=s;
//linklist_reverse
分析：本算法的思想是，逐个地把l的当前元素q插入新的链表头部，p为新表表头。
6、 设线性表a =（a1， a2， …an），b=（b1, b2, …bn），试写一个按下列规则合并a，b为线性表c的算法，即使得。
c=（a1, b1, …am ,bm ,bm+1, …bn） 当m<=n时；
或者c=（a1, b1, …an ,bn ,an+1, …am） 当m.>n时；
线性表a，b和c均以单链表作存储结构，且c表利用a表和b表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。
void merge1(linklist &a,linklist &b,linklist &c)//把链表a和b合并为c,a和b的元素间隔排列，且使用原存储空间。
p=a->next;q=b->next;c=a;
while(p&&q)
s=p->next;p->next=q; /将b的元素插入。
if(s)t=q->next;q->next=s; /如a非空，将a的元素插入。
p=s;q=t;
//while
//merge1
第二章线性表作业
一 判断题。1.线性表的逻辑顺序与物理顺序总是一致的。2.线性表的顺序存储表示优于链式存储表示。3.线性表若采用链式存储表示。时所有存储单元的地址可连续可不连续。4.每种数据结构都应具备三种基本运算 插入 删除和搜索。5.线性表的特点是每个元素都有一个前驱和一个后继。6.顺序存储方式插入和删除时效率...
第二章作业解答
一 填空。1 劳动耗费是指在生产过程中消耗的活劳动和物化劳动 2.活劳动包括活劳动消耗和活劳动占用 3 商品产值是指企业在计划期内生产的，可供外销的产品 半成品以及工业性作业的价值。4 总产值由已消耗的生产资料的转移价值 劳动者为自己创造的价值和为社会创造的价值三部分组成。5 净产值的特点是不受转移...
第二章作业解答
2.1 已知某一区域中给定瞬间的电流密度，其中c是大于零的常量，求 在此瞬间，点 1，1，2 处电荷密度的时间变化率 解 由电流连续性方程 p26 2.2 8 所以电荷密度的时间变化率为 在点 1，1，2 处的电荷密度的时间变化率为 18c 2.2 设在某静电场域中任意点的电场强度均平行于x轴。证明...