第2章-线性表习题及参考答案

第二章线性表习题

一判断题

1．线性表的逻辑顺序与存储顺序总是一致的。

2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二单选题 (请从下列A，B，C，D选项中选择一项)

1．线性表是( ) 。

(A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空；

(C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。

(A) n/2 (B) n+1/2 (C) n -1/2 (D) n

3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的；(B) 部分地址必须是连续的；

(C) 一定是不连续的；(D) 连续与否均可以。

4．用链表表示线性表的优点是（）。

(A)便于随机存取 (B)花费的存储空间较顺序存储少

(C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同

5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。

(A)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表

6．循环链表的主要优点是( )。

(A)不再需要头指针了

(B)已知某个结点的位置后，能够容易找到他的直接前趋

(C)在进行插入、删除运算时，能更好的保证链表不断开

(D)从表中的任意结点出发都能扫描到整个链表

7．下面关于线性表的叙述错误的是( )。

(A)线性表采用顺序存储，必须占用一片地址连续的单元；

(B)线性表采用顺序存储，便于进行插入和删除操作；

(C)线性表采用链式存储，不必占用一片地址连续的单元；

(D)线性表采用链式存储，不便于进行插入和删除操作；

8．单链表中，增加一个头结点的目的是为了（）。

(A) 使单链表至少有一个结点(B)标识表结点中首结点的位置

（C）方便运算的实现(D) 说明单链表是线性表的链式存储

9．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

(A) 单链表(B) 仅有头指针的单循环链表

(C) 双链表(D) 仅有尾指针的单循环链表

10．若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省运算时间（）。

(A) 单链表(B) 顺序表(C) 双链表(D) 单循环链表

三填空题

1．带头结点的单链表H为空的条件是__________________。

1．非空单循环链表L中*p是尾结点的条件是__________________。

3．在一个单链表中p所指结点之后插入一个由指针s所指结点，应执行s->next=________;和p->next=_____________的操作。

4．在一个单链表中p所指结点之前插入一个由指针s所指结点，可执行以下操作：s->next=________;

p->next=s;

t=p->data;

p->data=___________;

s->data=___________;

5．在顺序表中做插入操作时首先检查_________________。

四算法设计题

1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。2．已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同的元素。

3．线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表

（a1, a2, … , a m, b1, b2, … , b n）改变为：

（b1, b2, … , b n , a1, a2, … , a m）。

4．已知带头结点的单链表L中的结点是按整数值递增排列的，试写一算法，将值为x 的结点插入到表L中，使得L仍然有序。并且分析算法的时间复杂度。

5．假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针，编写一个函数删除该结点的前趋结点。

五上机实习题目

1．Josephu 问题

Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）

的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的

单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。2．一元多项式的相加

提示：

（1）一元多项式的表示问题：对于任意一元多项式：

P n(x)= P0+ P1X1+ P2X2+ … + P i X i+ … + P n X n

可以抽象为一个由“系数-指数”对构成的线性表，且线性表中各元素的指数项是递增的：

P=( ( P0,0), ( P1,1), ( P2,2), … , ( P n,n) )

(2 ) 用一个单链表表示上述线性表，结点结构为：

typedef sturct node Array { float coef; /*系数域*/

int exp; /*指数域*/

struct node *next; /*指针域*/

} Ploy Node;

约瑟夫环问题

约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，

每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m 值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。

源程序代码：（在Tubro C 2.0测试通过）

#include

#include

struct node

{

int number; /* 人的序号*/

int cipher; /* 密码*/

struct node *next; /* 指向下一个节点的指针*/

};

struct node *CreatList(int num) /* 建立循环链表*/

{

int i;

struct node *ptr1,*head;

if((ptr1=(struct node *)malloc(sizeof(struct node)))==NULL)

{

perror("malloc");

return ptr1;

}

head=ptr1;

ptr1->next=head;

for(i=1;i

{

if((ptr1->next=(struct node *)malloc(sizeof(struct node)))==NULL)

{

perror("malloc");

ptr1->next=head;

return head;

}

ptr1=ptr1->next;

ptr1->next=head;

}

return head;

}

main()

{

int i,n=30,m; /* 人数n为30个*/

struct node *head,*ptr;

randomize();

head=CreatList(n);

for(i=1;i<=30;i++)

{

head->number=i;

head->cipher=rand();

head=head->next;

}

m=rand(); /* m取随机数*/

i=0; /* 因为我没办法删除head指向的节点，只会删除head的下一节点，所以只能从0数起。*/

while(head->next!=head) /* 当剩下最后一个人时，退出循环*/

{

if(i==m)

{

ptr=head->next; /* ptr记录数到m的那个人的位置*/

printf("number:%d\n",ptr->number);

printf("cipher:%d\n",ptr->cipher);

m=ptr->cipher; /* 让m等于数到m的人的密码*/

head->next=ptr->next; /* 让ptr从链表中脱节，将前后两个节点连接起来*/

head=hea/d->next; /* head移向后一个节点*/

free(ptr); /* 释放ptr指向的内存*/

i=0; /* 将i重新置为0，从0再开始数*/

}

else

{

head=head->next;

i++;

}

}

printf("number:%d\n",head->number);

printf("cipher:%d\n",head->cipher);

free(head); /* 让最后一个人也出列*/

}

第二章线性表习题（参考答案）

一判断题

二单选题

三填空题

1、H->next == NULL

2、p->next == L

3、p->next s

4、p->next s->data t

5、表是否满了

四算法设计题（答案仅供参考）

1、Status OrderInsert(ElemType A[], int &elenum, ElemType x)

{

if (elenum>= arrsize) return ERROR; //如果溢出

for(i=0; i

for(j=elenum-1; j>=i; j--)

A[j+1] = A[j]; //将数据元素后移

A[i] = x;

elenum++;

return OK;

}

时间复杂度：O(elenum)

2、void ReElemDelete(SqList &A)

{

if (A.length<=1) return; //少于一个元素不处理

i=2; //从第2个以后的元素开始处理

j=1; //删除重复值后的表的最后一个元素的位置，初始的位置为1

while (i

if (A.elem[j-1] == A.elem[i-1]) i++;//若待处理的元素和删除重复值后的表的最后一个元素相同，不插入，继续处理下一个元素

else {

A.elem[j] == A.elem[i-1];//插入无重复值得表

j++; //指向无重复值得表的最后一个元素

i++; //继续处理下一个元素

}

A.length = j; //修改表长度

}

3、算法思想：利用逆置的思想处理

首先将表（a1, a2, … , a m, b1, b2, … , b n）逆置为（b n,… , b2, b1 ,a m, … , a2, a1），然后将前n个（b n,… , b2, b1）和后m个（a m, … , a2, a1）分别逆置后即可得到（b1, b2, … , b n , a1, a2, … , a m）。（请同学们自己设计算法）

void InverseListSeq(SeqList &L,int iStart,int iEnd)

{

ElemType *p, *q, temp ;

for (p = L.elem+iStart-1, q = L.elem + iEnd - 1; p < q; p ++,q --){

temp = *p ;

*p = *q ;

*q = temp ;

}

}

Status Inverse(SeqList &L,int m)

{

n=L.length-1;

InverseListSeq(L,1,m+n);

InverseListSeq(L,1,m );

InverseListSeq(L,m+1,m+n);

Return Ok;

}

4、

void OrderInsert(LinkList L, ElemType x)

{

pre = L; // 指向待插入位置的前驱

p = L->next; // 指向待插入位置

while ( p && p->data < x) //查找插入位置

{

pre = p;

p = p->next;

}

s = (LNode *)malloc(sizeof(LNode)); //分配内存

if (!s) return; //失败返回

s->data = x; //给结点赋值

s->next = p;

pre->next = s; //插入结点

}

4、

void PreNodeDelete(LinkList p, ElemType &e) {

pre = p; //指向q的前驱

q = pre->next; //指向要找的p的前驱

while (q->next != p) //查找前驱

{

pre = q; q = q->next;

}

pre->next = p; //删除前驱

e = q->data;

free(q);

}

数据结构习题二线性表

一．选择题 1. 已知在单链表中指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？（ B ） A、s->next = p； p->next = s； B、s->next = p->next； p->next = s； C、s->next = p->next； p = s； D、p->next = s； s->next = p； 2. 非空的循环单链表first的尾结点（由p所指向）满足：（ C ） A、 p->next == NULL； B、 p == NULL； C、 p->next == first； D、 p == first； 3. 在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）插入一个新元素时，需要从后向前依次后移___C___个元素。 A、n-i B、n-i-1 C、n-i+1 D、i 4. 线性表是具有n个__C____的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 5. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较___B___个结点。 A、 n B、n/2 C、(n-1)/2 D、(n+1)/2 6. 若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用___A___存储方式最节省运算时间。 A、单链表 B、双链表 C、单循环链表 D、带头结点的双循环链表 7. 已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a.在P结点后插入S结点的语句序列是：＿＿。 b.在P结点前插入S结点的语句序列是：。 c.在表首插入S结点的语句序列是：。 d.在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S;（2）P->next=P->next->next; （3）P->next=S->next;（4）S->next=P->next; （5）S->next=L;（6）S->next=NULL;（7）Q=P; （8）while(P->next!=Q)P=P->next; （9）while(P->next!=NULL)P=P->next; （10）P=Q;（11）P=L;（12）L=S;（13）L=P; 二．填空题 1．在顺序表中插入或删除一个元素，需要平均移动________元素，具体移动的元素个数与_______有关。 2．在顺序表中，逻辑上相邻的元素，其物理位置________相邻。在单链表中，逻辑上相邻的元素，其物理位置__________相邻。 3．在带头结点的非空单链表中，头结点的存储位置由___________指示，首元素结点的存储位置由_________指示，除首元素结点外，其它任一元素结点的存储位置由_______指示。4.当对一个基本线性表进行的插入和删除操作较频繁时，基本线性表应采用存储结构；当对基本线性表的操作不会引起它的变化时，基本线性表应采用存储结构。 5.设某有一双链表，若要在指针q所指结点（中间结点）的后面插入一个新结点s，则需要执行下述语句段： s->prior=q；s->next=q->next；；q->next=s;

线性代数第二章答案

第二章 矩阵及其运算 1 已知线性变换 ?????++=++=++=3 213321232113235322y y y x y y y x y y y x 求从变量x 1 x 2 x 3到变量y 1 y 2 y 3的线性变换 解 由已知 ? ??? ?????? ? ?=???? ??221321323513122y y y x x x 故 ???? ?????? ? ?=???? ??-3211 221323513122x x x y y y ? ??? ?????? ??----=321423736 947y y y ?????-+=-+=+--=3 21332123 211423736947x x x y x x x y x x x y 2 已知两个线性变换 ?????++=++-=+=321332123 11542322y y y x y y y x y y x ?????+-=+=+-=3 233122 11323z z y z z y z z y 求从z 1 z 2 z 3到x 1 x 2 x 3的线性变换 解 由已知 ???? ?????? ? ?-=???? ??221321514232102y y y x x x ??? ? ?????? ??--???? ??-=32131 010 2013514232102z z z ??? ? ?????? ??----=321161109412316z z z

所以有?????+--=+-=++-=3 21332123 2111610941236z z z x z z z x z z z x 3 设???? ??--=111111111A ??? ? ??--=150421321B 求3AB 2A 及A T B 解 ??? ? ??---???? ??--???? ??--=-1111111112150421321111111111323A AB ???? ??----=???? ??---???? ??-=2294201722213211111111120926508503 ??? ? ??-=???? ??--???? ??--=092650850150421321111111111B A T 4 计算下列乘积 (1)??? ? ?????? ??-127075321134 解 ???? ?????? ??-127075321134???? ???+?+??+?-+??+?+?=102775132)2(71112374??? ? ??=49635 (2)???? ??123)321( 解 ??? ? ??123)321((132231)(10)

线性规划经典例题及详细解析

一、 已知线性约束条件,探求线性目标关系最值问题 1. 设变量x 、y 满足约束条件?? ???≥+-≥-≤-1122y x y x y x ,则y x z 32+=的最大值为 。 二、 已知线性约束条件,探求非线性目标关系最值问题 2. 已知1,10,220x x y x y ≥??-+≤??--≤? 则22x y +的最小值就是 。 3. 已知变量x,y 满足约束条件+201-70x y x x y -≤??≥??+≤? ,则 y x 的取值范围就是( )、 A 、 [95,6] B 、(－∞,95 ]∪[6,＋∞) C 、(－∞,3]∪[6,＋∞) D 、 [3,6] 三、 研究线性规划中的整点最优解问题 4. 某公司招收男职员x 名,女职员y 名,x 与y 须满足约束条件?? ???≤≥+-≥-.112,932,22115x y x y x 则1010z x y =+的最大值 就是 。 四、 已知最优解成立条件,探求目标函数参数范围问题 5. 已知变量x ,y 满足约束条件1422x y x y ≤+≤??-≤-≤? 。若目标函数z ax y =+(其中0a >)仅在点(3,1)处取得最大值,则a 的取值范围为 。 6. 已知x 、y 满足以下约束条件5503x y x y x +≥??-+≤??≤? ,使z=x+a y (a >0) 取得最小值的最优解有无数个,则a 的值为( ) A. －3 B 、 3 C 、 －1 D 、 1 五、 求可行域的面积 7. 不等式组260302x y x y y +-≥??+-≤??≤? 表示的平面区域的面积为 ( ) A. 4 B 、 1 C 、 5 D 、 无穷大

第二章线性表答案

第2章线性表 一选择题 1．下述哪一条是顺序存储结构的优点？（ A ） A．存储密度大 B．插入运算方便 C．删除运算方 便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（ B ）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元 素 D．数据项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 AHA12GAGGAGAGGAFFFFAFAF

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链 表 C．双链表D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 AHA12GAGGAGAGGAFFFFAFAF

A．单链表 B．双链表 C．单循环链 表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（ BC ）. A．内存地址 B．数组下标 C．下一元素地址D．左、右孩子地址 9. 链表不具有的特点是（ C ） A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（ BC ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 AHA12GAGGAGAGGAFFFFAFAF

线性代数第二章矩阵试题及答案

第二章矩阵 一、知识点复习 1、矩阵的定义 由m n个数排列成的一个m行n列的表格，两边界以圆括号或方括号，就成为一个m n型矩阵。例如 2 -1 0 1 1 1 1 1 0 2 2 5 4 -2 9 3 3 3 -1 8 是一个45矩阵. 一个矩阵中的数称为它的元素,位于第i行第j列的数称为(i,j)位元素。 元素全为0的矩阵称为零矩阵,通常就记作0。 两个矩阵A和B相等(记作A=B)，是指它的行数相等，列数也相等(即它们的类型相同)，并且对应的元素都相等。 2、 n阶矩阵与几个特殊矩阵 行数和列数相等的矩阵称为方阵，行列数都为n的矩阵也常常叫做n阶矩阵。 n阶矩阵的从左上角到右下角的对角线称为主对角线。 下面列出几类常用的n阶矩阵,它们都是考试大纲中要求掌握的. 对角矩阵: 对角线外的的元素都为0的n阶矩阵. 单位矩阵: 对角线上的的元素都为1的对角矩阵,记作E(或I). 数量矩阵: 对角线上的的元素都等于一个常数c的对角矩阵,它就是c E. 上三角矩阵: 对角线下的的元素都为0的n阶矩阵. 下三角矩阵: 对角线上的的元素都为0的n阶矩阵. 对称矩阵: 满足A T=A矩阵，也就是对任何i,j,(i,j)位的元素和(j,i)位的元素总是相等的n阶矩阵. 反对称矩阵:满足A T=-A矩阵.也就是对任何i,j,(i,j)位的元素和(j ,i)位的元素之和总等于0的n阶矩阵.反对称矩阵对角线上的元素一定都是0.) 正交矩阵：若AA T=A T A=E，则称矩阵A是正交矩阵。 （1）A是正交矩阵?A T=A-1 （2）A是正交矩阵?2 A=1 阶梯形矩阵:一个矩阵称为阶梯形矩阵，如果满足: ①如果它有零行，则都出现在下面。 ②如果它有非零行，则每个非零行的第一个非0元素所在的列号自上而下严 格单调递增。 把阶梯形矩阵的每个非零行的第一个非0元素所在的位置称为台角。 每个矩阵都可以用初等行变换化为阶梯形矩阵，这种运算是在线性代数的各类 计算题中频繁运用的基本运算，必须十分熟练。 请注意：一个矩阵用初等行变换化得的阶梯形矩阵并不是唯一的，但是其非零 行数和台角位置是确定的。 3、矩阵的线形运算 （1）加(减)法:两个m n的矩阵A和B可以相加(减),得到的和(差)仍是m n 矩阵,记作A+B (A-B),运算法则为对应元素相加(减). （2）数乘: 一个m n的矩阵A与一个数c可以相乘,乘积仍为m n的矩阵, 记作c A,运算法则为A的每个元素乘c. 这两种运算统称为线性运算,它们满足以下规律: ①加法交换律:A+B=B+A. 2加法结合律:(A+B)+C=A+(B+C). ③加乘分配律:c(A+B)=c A+c B.(c+d)A=c A+d A. ④数乘结合律: c(d)A=(cd)A. ⑤ c A=0 c=0 或A=0. 4、矩阵乘法的定义和性质 （1）当矩阵A的列数和B的行数相等时,则A和B可以相乘,乘积记作AB. AB的行数和A相等,列数和B相等. AB的(i,j)位元素等于A的第i个行向量 和B的第j个列向量(维数相同)对应分量乘积之和.

六种经典线性规划例题

线性规划常见题型及解法 求线性目标函数的取值范围 2 2 2 x y A D y 2 O x x=2 求可行域的面积 y y M 5 2 x y 2 y x y 2 x y 2 x y x (3,5] y =2 ( 13 例1 x+2y 时 6 的点 C 、 x ， 个 y 6 y 3 2 x + y —3 = 0 C 、 5 A 、 4 B 、 1 D 、无穷大 () 0,将 有 最小值 故选A .B A --- 作出可行域如右图 点个数为13个，选D x + y =2 则z=x+2y 的取值范围是 () 旦y =2 0 0表示的平面区域的面积为 三、求可行域中整点个数 解：|x| + |y| <2等价于 解：如图，作出可行域，作直线I : I 向右上方平移，过点A ( 2,0 ) 2,过点B ( 2,2 )时，有最大值 [2,6] B 、[2 ,5] C 、[3,6] 解：如图，作出可行域，△ ABC 的面积即为所求，由梯形OMBC 的面积减去梯形OMAC 的 面积即可，选B 例 3、满足 |x| + |y| <2 A 、9 个 B 、10 个 由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性 目标函数的最优解是最常见的题型，除此之外，还有以下六类常见题型。 (x 0,y 0) (x 0,y p 0) (xp 0,y 0) (xp 0,y p 0) 是正方形内部(包括边界)，容易得到整 y)中整点(横纵坐标都是整数)有() D 、 14 个 2x 例2、不等式组x x 若x 、y 满足约束条件 y O C V —? x 2x + y —6= 0

第2章线性表习题解答

第2章线性表习题解答

第2章习题 (2) 第2章习题 2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？ 【解】 //用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType; typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList; //初始化 void initialList(seqList &S)

{ https://www.wendangku.net/doc/8015554161.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.wendangku.net/doc/8015554161.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.wendangku.net/doc/8015554161.html,st+1) //i为元素编号，有效范围在https://www.wendangku.net/doc/8015554161.html,st+1之间 return false; else { x=S.data[i-1];

return true; } } //查找元素x，成功：返回元素编号；失败：返回0 int listLocate(seqList S,elementType x) { int i; for(i=0;i<=https://www.wendangku.net/doc/8015554161.html,st;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出 } return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i)

第2章线性表习题解析(答)

第二章线性表练习题 一、选择题 1.线性表是具有n个的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 E、信息项 2.线性表的静态链表存储结构与顺序存储结构相比优点是。 A、所有的操作算法实现简单 B、便于随机存储 C、便于插入和删除 D、便于利用零散的存储器空间 3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为。 A、O(log2n) B、O(1) C、O(n) D、O(n2) 4.（1）静态链表既有顺序存储的特点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关； （2）静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加；（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是。 A、（1）、（2） B、（1） C、（1）、（2）、（3） D、（2） 6.在双向链表存储结构中，删除p所指的结点时须修改指针。 A、p－＞next－＞prior=p－＞prior; p－＞prior－＞next=p－＞next; B、p－＞next=p－＞next－＞next;p－＞next－＞prior=p; C、p－＞prior－＞next=p;p－＞prior=p－＞prior－＞prior; D、p－＞prior=p－＞next－＞next;p－＞next=p－＞prior－＞prior;

7.在双向循环链表中，在P指针所指的结点后插入q所指向的新结点，其修改指针的操作是。 A、p－＞next=q; q－＞prior=p;p－＞next－＞prior=q;q－＞next=q; B、p－＞next=q;p－＞next－＞prior=q;q－＞prior=p;q－＞next=p－＞next; C、q－＞prior=p; q－＞next=p－＞next; p－＞next－＞prior=q; p－＞next=q; D、q－＞next=p－＞next;q－＞prior=p;p－＞next=q;p－＞next=q; 8.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。 A、 n b、2n－1 c、2n d、n－1 9.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动个元素。 A、n－i B、n－i+1 C、n－i－1 D、i 10.线性表L=(a1，a2,……an)，下列说法正确的是。 A、每个元素有有一个直接前驱和一个直接后继 B、线性表中至少有一个元素 C、表中诸元素的排列必须是由小到大或由大到小。 D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 11.对单链表表示法，以下说法错误的是。 A、数据域用于存储线性表的一个数据元素 B、指针域(或链域)用于存放一指向本结点所含数据元素的直接后继所在结点的指针 C、所有数据通过指针的链接而组织成单链表 D、NULL称为空指针，它不指向任何结点只起标志作用

线性代数课后习题答案(陈维新)

第一章 行列式 习题1.1 1. 证明：（1）首先证明)3(Q 是数域。 因为)3(Q Q ?，所以)3(Q 中至少含有两个复数。 任给两个复数)3(3,32211Q b a b a ∈++，我们有 3 )()3()3)(3(3)()()3()3(3)()()3()3(2121212122112121221121212211b a a b b b a a b a b a b b a a b a b a b b a a b a b a +++=++-+-=+-++++=+++。 因为Q 是数域，所以有理数的和、差、积仍然为有理数，所以 ) 3(3)()3()3)(3()3(3)()()3()3()3(3)()()3()3(2121212122112121221121212211Q b a a b b b a a b a b a Q b b a a b a b a Q b b a a b a b a ∈+++=++∈-+-=+-+∈+++=+++。 如果0322≠+b a ，则必有22,b a 不同时为零，从而0322≠-b a 。 又因为有理数的和、差、积、商仍为有理数，所以 )3(33) (3)3() 3)(3()3)(3(3 32 2 22212122222121222222112211Q b a b a a b b a b b a a b a b a b a b a b a b a ∈--+--= -+-+= ++。 综上所述，我们有)3(Q 是数域。 （2）类似可证明)(p Q 是数域，这儿p 是一个素数。 （3）下面证明：若q p ,为互异素数，则)()(q Q p Q ?。 （反证法）如果)()(q Q p Q ?，则q b a p Q b a +=? ∈?,，从而有 q ab qb a p p 2)()(222++==。 由于上式左端是有理数，而q 是无理数，所以必有02=q ab 。 所以有0=a 或0=b 。 如果0=a ，则2 qb p =，这与q p ,是互异素数矛盾。 如果0=b ，则有 a p =，从而有“有理数=无理数”成立，此为矛盾。 所以假设不成立，从而有)()(q Q p Q ?。

八种 经典线性规划例题(超实用)

线性规划常见题型及解法 由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型，除此之外，还有以下六类常见题型。 一、求线性目标函数的取值范围 例1、若x、y满足约束条件 2 2 2 x y x y ≤ ? ? ≤ ? ?+≥ ? ，则z=x+2y的取值范围是（） A、[2,6] B、[2,5] C、[3,6] D、（3,5] 解：如图，作出可行域，作直线l：x+2y＝0，将l向右上方平移，过点A（2,0）时，有最小值2，过点B（2,2）时，有最大值6，故选 A 二、求可行域的面积 例2、不等式组 260 30 2 x y x y y +-≥ ? ? +-≤ ? ?≤ ? 表示的平面区域的面积为（） A、4 B、1 C、5 D、无穷大 解：如图，作出可行域，△ABC的面积即为所求，由梯形OMBC 的面积减去梯形OMAC的面积即可，选 B 三、求可行域中整点个数 例3、满足|x|＋|y|≤2的点（x，y）中整点（横纵坐标都是整数）有（） A、9个 B、10个 C、13个 D、14个 解：|x|＋|y|≤2等价于 2(0,0) 2(0,0) 2(0,0) 2(0,0) x y x y x y x y x y x y x y x y +≤≥≥ ? ?-≤≥ ? ? -+≤≥? ?--≤ ? 作出可行域如右图，是正方形内部（包括边界），容易得到整点个数为13个，选 D

四、求线性目标函数中参数的取值范围 例4、已知x、y满足以下约束条件 5 50 3 x y x y x +≥ ? ? -+≤ ? ?≤ ? ，使z=x+ay(a>0) 取得最小值的最优解有无数个，则a的值为（） A、－3 B、3 C、－1 D、1 解：如图，作出可行域，作直线l：x+ay＝0，要使目标函数z=x+ay(a>0)取得最小值的最优解有无数个，则将l向右上方平移后与直线x+y＝5重合，故a=1，选 D 五、求非线性目标函数的最值 例5、已知x、y满足以下约束条件 220 240 330 x y x y x y +-≥ ? ? -+≥ ? ?--≤ ? ，则z=x2+y2的最大值和最小值分别是（） A、13，1 B、13，2 C、13，4 5 D 、 解：如图，作出可行域,x2+y2是点（x，y）到原点的距离的平方，故最大值为点A（2,3）到原点的距离的平方，即|AO|2=13，最小值为原点到直线2x＋y－2=0的距离的平方， 即为4 5 ，选 C 六、求约束条件中参数的取值范围 例6、已知|2x－y＋m|＜3表示的平面区域包含点（0,0）和（－1,1），则m的取值范围是（） A、（-3,6） B、（0,6） C、（0,3） D、（-3,3） 解：|2x－y＋m|＜3等价于 230 230 x y m x y m -++>? ? -+- ? ? -< ? ,故0＜m＜3，选 C

(完整版)数据结构第二章线性表1答案

（A ）需经常修改L 中的结点值 （E ）需不断对L 进行删除插入 第二部分线性表 、选择题 1 ?关于顺序存储的叙述中，哪一条是不正确的 （B ） A. 存储密度大 B. 逻辑上相邻的结点物理上不必邻接 C. 可以通过计算直接确定第 i 个结点的位置 D. 插入、删除操作不方便 2.长度为n 的单链表连接在长度为 m 的单链表后的算法的时间复杂度为 （C ） A 0（ n ） B 0（1） C 0（m ） D 0（m+n ） 3 .在n 个结点的顺序表中，算法的时间复杂度是 0（1）的操作是：（A ） A 访问第i 个结点（1<=i<=n ）和求第i 个结点的直接前趋（2<=i<=n ) B 在第i 个结点（1<=i<=n ）后插入一个新结点 C 删除第i 个结点（1<=i<=n ) D 将n 个结点从小到大排序 4.一个向量第一个兀素的存储地址是 100 ,每个兀素的长度为 2 ,则第5 个兀素的地址是 (B ) ( A ) 110 ( B ) 108 (C ) 100 ( D ) 120 5 .已知一个顺序存储的线性表， 设每个结点需要占 m 个存储单元，若第一个结点的地址为 da , 则第i 个结点的地址为：（A ） 7 .链表是一种采用（ B ）存储结构存储的线性表。 （A ）顺序 （B ）链式 （C ）星式 （D ）网状 8 .线性表若采用链式存储结构时，要求内存中可用存储单兀的地址： （D ） （A ）必须是连续的 （B ）部分地址必须是连续的 （C ）一定是不连续的 （D ）连续或不连续都可以 9 .线性表L 在_ （ B ）情况下适用于使用链式结构实现。 A ） da+（i-1）*m B ） da+i*m 6.在具有n 个结点的单链表中，实现（ A ）遍历链表和求链表的第 i 个结点 C ）删除开始结点 C ） da-i*m D ） da+（i+1）*m A ）的操作，其算法的时间复杂度为 0（n ）。 B ）在地址为p 的结点之后插入一个结点 D ） 删除地址为p 的结点的后继结点

线性表练习题(答案)

第2章线性表 一选择题 下列程序段的时间复杂度为（ C ）。 for( int i=1;i<=n;i++) for( int j=1;j<= m; j++) A[i][j] = i*j ; A. O(m2) B. O(n2) C. O(m*n) D. (m+n) 下面关于线性表的叙述中，错误的是哪一个？（B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素B．字符C．数据元素D．数据项 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表 C．双链表D．仅有尾指针的单循环链表 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 A．单链表B．双链表C．单循环链表D．带头结点的双循环链表 链表不具有的特点是（ B ） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 下面的叙述不正确的是（B,C ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ）A．O（i）B．O（1）C．O（n）D．O（i-1） 循环链表H的尾结点P的特点是（A ）。 A．P->next=H B．P->next= H->next C．P=H D．P=H->next 完成在双循环链表结点p之后插入s的操作是（D ）；

高中数学线性规划经典题型

高考线性规划归类解析 一、平面区域和约束条件对应关系。 例1、已知双曲线224x y -=的两条渐近线与直线3x =围成一个三角形区域,表示该区域的不等式组是（） (A)0003x y x y x -≥??+≥??≤≤? (B)0003x y x y x -≥?? +≤??≤≤? (C) 003x y x y x -≤?? +≤??≤≤? (D) 0003x y x y x -≤?? +≥??≤≤? 解析：双曲线224x y -=的两条渐近线方程为y x =±，与直线3x =围 成一个三角形区域（如图4所示）时有0 003x y x y x -≥?? +≥??≤≤? 。 点评：本题考查双曲线的渐近线方程以及线性规划问题。验证法或排除法是最效的方法。 例2：在平面直角坐标系中，不等式组20 200x y x y y +-≤??-+≥??≥? 表示的平面区域的面积是（） (A)42 (B)4 (C) 22 (D)2 解析：如图６，作出可行域，易知不等式组20 200x y x y y +-≤??-+≥??≥? 表示的平面区域是一个三角形。容 易求三角形的三个顶点坐标为Ａ（０，２），B(2,0),C(-2,0).于是三角形的面积为： 11 ||||42 4.22 S BC AO =?=??=从而选Ｂ。 点评：有关平面区域的面积问题，首先作出可行域，探求平面区域图形的性质；其次利用面积公式整体或部分求解是关键。 二、已知线性约束条件，探求线性截距——加减的形式(非线性距离——平方的形式，斜率——商的形式)目标关系最值问题（重点） 例3、设变量x 、y 满足约束条件?? ? ??≥+-≥-≤-1122y x y x y x ，则 ①y x 32+的最大值为 。（截距） 解析：如图1，画出可行域，得在直线 2x-y=2与直线x-y=-1 的交点A(3,4)处，目标函数z 最大值为18 点评：本题主要考查线性规划问题,由线性约束条件画出可行域,然后求出目标函数的最大值.，是一道较为简单的送分题。数形结合是数学思想的重要手段之一。 ②则2 2 x y +的最小值是 . ③1y x =+的取值范围是 . 图1

第二章线性表习题及答案

第二章线性表习题及答案 一、基础知识题 2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 答：始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。 头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。 2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i 越接近n则所需移动的结点数越少。 2.4 为什么在单循环链表中设置尾指针比设置头指针更好? 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。 2.5 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少? 答：我们分别讨论三种链表的情况。 1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。 2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。 3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。 2.6 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是无头结点单链表 ListNode *Q,*P; if(L&&L->next){ Q=L;L=L->next;P=L;

线性表练习题答案

一、判断题 1．线性表的逻辑顺序与存储顺序总是一致的。(FALSE) 2．顺序存储的线性表可以按序号随机存取。(TRUE) 3．顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。（TRUE） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。（TRUE） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（FALSE） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（TRUE）7．线性表的链式存储结构优于顺序存储结构。（FALSE） 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。（TRUE） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（TRUE）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（FALSE） 二、单选题、(请从下列A，B，C，D选项中选择一项) 11．线性表是( ) 。 (A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。 答：A 12．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等 概率的。插入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) (n+1)/2 (C) (n –1)/2 (D) n 答：A 13．线性表采用链式存储时，其地址( D ) 。 (A) 必须是连续的；(B) 部分地址必须是连续的； (C) 一定是不连续的；(D) 连续与否均可以。 答：D 14．用链表表示线性表的优点是（）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 答：C 15. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。 (A)单链表 (B)双链表 (C)单循环链表

线性代数第二章答案

第二章 矩阵及其运算 1 已知线性变换 ?????++=++=++=3 21332123 2113235322y y y x y y y x y y y x , 求从变量x 1 x 2 x 3到变量y 1 y 2 y 3的线性变换 解 由已知 ? ??? ?????? ? ?=???? ??22 1321323513122y y y x x x 故 ???? ?????? ? ?=???? ??-3211 221323513122x x x y y y ? ??? ?????? ??----=321423736 947y y y ?????-+=-+=+--=3 21332123 211423736947x x x y x x x y x x x y 2 已知两个线性变换 ?????++=++-=+=3 2133 2123 11542322y y y x y y y x y y x ?????+-=+=+-=3 233122 11323z z y z z y z z y 求从z 1 z 2 z 3到x 1 x 2 x 3的线性变换 解 由已知 ???? ?????? ? ?-=???? ??221321514232102y y y x x x ??? ? ?????? ??--???? ??-=32131 010 2013514232102z z z ??? ? ?????? ??----=32 1161109412316z z z

所以有?????+--=+-=++-=3 2133 2123 2111610941236z z z x z z z x z z z x 3 设???? ??--=111111111A ??? ? ??--=150421321B 求3AB 2A 及A T B 解 ??? ? ??---???? ??--???? ??--=-1111111112150421321111111111323A AB ???? ??----=???? ??---???? ??-=2294201722213211111111120926508503 ??? ? ??-=???? ??--???? ??--=092650850150421321111111111B A T 4 计算下列乘积 (1)??? ? ?????? ??-127075321134 解 ???? ?????? ??-127075321134???? ???+?+??+?-+??+?+?=102775132)2(71112374?? ? ? ??=49635 (2)???? ??123)321( 解 ??? ? ??123)321((132231)(10)

线性规划经典例题及详细解析

1 / 6 一、 已知线性约束条件，探求线性目标关系最值问题 1. 设变量x 、y 满足约束条件?? ? ??≥+-≥-≤-1122y x y x y x ,则y x z 32+=的最大值为 。 二、 已知线性约束条件,探求非线性目标关系最值问题 2. 已知1,10,220x x y x y ≥??-+≤??--≤? 则22 x y +的最小值是 。 3. 已知变量x ，y 满足约束条件+201-70x y x x y -≤?? ≥??+≤? ,则 错误! 的取值范围是（ )。 A 。 ［错误!，6] B.（－∞，错误!］∪［6，＋∞） C.（－∞，3］∪［6，＋∞） D 。 ［3，6］ 三、 研究线性规划中的整点最优解问题 4. 某公司招收男职员x 名，女职员y 名，x 和y 须满足约束条件?? ? ??≤≥+-≥-.112,932,22115x y x y x 则1010z x y =+的最大 值是 。 四、 已知最优解成立条件，探求目标函数参数范围问题 5. 已知变量x ，y 满足约束条件14 22x y x y ≤+≤?? -≤-≤? 。若目标函数z ax y =+(其中0a >）仅在点(3,1)处 取得最大值，则a 的取值范围为 。 6. 已知x 、y 满足以下约束条件5503x y x y x +≥?? -+≤??≤? ,使z=x+a y (a >0) 取得最小值的最优解有无数个，则a 的 值为（ ） A. －3 B. 3 C 。 －1 D. 1 五、 求可行域的面积 7. 不等式组260302x y x y y +-≥?? +-≤??≤? 表示的平面区域的面积为 （ ） A. 4 B. 1 C. 5 D 。 无穷大

线性表例题

例1说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。 答：在线性表的链式存储结构中，头指针是指指向链表的指针，若链表有头指针则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一数据元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用作监视哨，等等），有了头结点后，对在第一数据元素结点前插入结点和删除第一结点，其操作与对其它结点的操作就统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一数据元素结点，它是头结点后边的第一个结点。 例2 为什么在单循环链表中设置尾指针比设置头指针更好？ 答：尾指针是指指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一个带头结点的单循环链表，其尾指针是rear，则开始结点和终端结点分别为指针rear所指结点的后继结点的后继结点和指针rear所指结点（利用C语言分别描述为rear->next->next和rear，利用标准Pascal语言分别描述为rear↑.next↑.next和rear），查找时间均为O(1)。若用头指针来表示该链表，则查找时间均为O(n)。 例3请分析含有n个结点的顺序表，在进行插入和删除操作时的时间复杂度，并对计算的结果进行分析，由此可得到线性表的适用范围的什么结论。 解：值得注意的是，插入操作是指在某个元素前面或后面插入，是针对位置的，因此可插入的位置为n+1个，而删除操作是删除线性表中某个位置上的元素，是针对元素的，因此可删除的元素为n个。 设p i为在第i个元素之前插入一个元素的概率，在等概率的条件下，其值为1/(n+1)。在第i个元素之前插入一个元素需要移动的元素的个数为：n-i+1。所以，在长度为n的线性表中插入一个元素所需要移动的元素次数的数学期望值（平均次数）为： E in=∑+ = + - 1 1 )1 ( n i i i n p=n/2 同理，设q i为删除第i个元素的概率，在等概率的条件下，其值为1/n。删除第i 个元素需要移动的元素的个数为：n-i。所以，在长度为n的线性表中删除一个元素所需要移动的元素次数的数学期望值（平均次数）为： E del=∑ =- n i i i n q 1 ) (=(n-1)/2 由于这两个操作的时间主要消耗在数据元素的移动上，所以插入算法和删除算法的时间复杂度均为：O(n)。 从上述分析可知，在顺序存储结构下，在线性表上插入或删除一个元素时需要平均移动线性表长度一半的元素个数，因此当n的值较大时，在顺序结构下，不宜对它频繁