第二章 线性表 练习题

一、选择题

1．线性表的链接实现有利于( A )运算。

(A)插入 (B)读表元 (C)查找 (D)定位

2．设单链表中指针p指向结点A，若要删除A之后的结点(若存在)，则修改指针的

操作为( A)。

(A)P一＞next＝p一＞next一＞next (B)p＝P一＞next

(C)p＝P一＞next一＞next (D)p一＞next＝p

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

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

(c)一定是不连续的 (D)连续与否均可以

4．在一个具有n个结点的单链表中查找其值等于x的结点．在查找成功的情况下需平均比较( c)个元素结点。

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

5．在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是(B)。

(A) p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;

(B) s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;

(C) p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;

(D) s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;

6．已知一个有序表为(13，18，24，35，47，50，62，83，90，115，134)，当二分查找值为90的元素时，需( D )次比较可查找成功。

(A)1 (B)2 (C)3 (D)4

7．在顺序存储的线性表R[029]上进行顺序查找的平均查找长度为(①)，进行二分查找的平均查找长度为(②)，讲行分块查找（设分为5块)的平均查找长度为(③)

①(A)15 (B)15．5 (C)16 (D)20

②(A)4 (B)62／15 (C)64／15 (D)25／6

③(A)6 (B)11 (C)5 (D)6．5

8．若线性表最常用的操作是存取第i个元素及其前驱元素的值，则采用( B )存储方式最节省时间。

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

二、填空题

1．循环链表的主要优点是__表的处理方便________________。

2．在双向循环链表中，在指针p所指的结点之后插入指针f所指的结点，其操作为______ f->prior=p; f->next=p->next; p->next=f; p->next->prior=f__________ 3．双向循环链表的主要优点是____克服单链表的单向性__________。

4．在双向循环表中，在p所指的结点之后插入指针f所指的结点，其操作为_____f->prior_＝p;f一＞next＝p一＞next;_ p->next->prior＝f;p一＞next＝f。

5．若要在一个单链表的*p结点之前插入一个*s结点时，可执行下列操作

s->next=____p->next________； p->next=s；t=p->data；p->data=_ s->data _；s->data=____t _____。

6．假定对线性表R[059]进行分块查找，共分10块，每块长度等于6。若假定查找索引表和块均用顺序查找法，则查找每一个元素的平均查找时间为___________。

7．在一个长度为n的顺序表中插入一个元素，最少需要移动_0_个元素，最多需要移动____n____个元素。

8．如果某线性表的每一个元素都没有后继元素，则其长度最多是_1______________。

9．设单链表中指针p指着结点A，若要删除A之后的结点(假设存在), 则需要修改指针的操作为__p->next=p->next->next_____________。

三、判断题

1．具有线性序关系的集合中，若a，b是集合中的任意两个元素，则必有a

2．在单链表中任何两个元素的存储位置之间都有固定的联系，因此可以从首结点进行查找任何一个元素。(错 )

3．如果某数据结构的每一个元素都最多只有一个直接前驱，则必为线性表。（错）4．一个有序的单链表不能采用折半查找法进行查找。(错)

5．线性表的惟一存储形式就是链表。( 错 )

四、读程序填空

1．以下函数ins的功能是在顺序表a中找到第一个值为x的元素，然后在该元素之前插入一个值为y的元素。如果找不到值为x的元素，则新元素成为顺序表的最后一个元素。插入成功返回1，否则返回0。完成以下程序。(8分)

typedef struct {

int elem[100];

int length;

}SQ;

int ins(SQ *a, int x, int y)

{

int k,i;

if( _a=NULL_ )

return 0;

for(k=0; klength; k++)

if(a->elem[k]==x)

break;

if(k==a->length) k--;

else

for(i=a->length-1; i>k; i--) ____a->elem[i+1]=a->elem[i]__________ ;

____a->elem[k]__ =y;

return 1;

}

2．在单链表(表首指针为head)的元素中找出最后一个值为e的元素，返回其指针；如果找不到，返回NULL。完成以下程序。(6分)

Typedef struct LinkNode{

int data;

Struct LinkNode *next;

}Node;

Node *search_link(Node *head, int e)

{

Node *p, *q;

q=____head___ ;

for(p=head; __p->next!=NULL_ ; p=p->next)

if(p->data==e) ____q=p____________;

return q;

}

3．已知单链表的表首指针为head，下面的函数delete是从单链表中删除指针为p的结点，并返回新的表首指针。请完成如下程序。(4分)

typedef struct LinkNode{

int data;

struct LinkNode *next;

}Node;

Node *delete(Node *head, Node *p)

{

Node *pf;

if(head==p){

head=______head->next____________;

free(p);}

else{

for(pf=head; pf->next!=p; pf=pf->next);

_____p_ = p->next;

free(p);}

}

return head;

}

4．以下算法是将线性表L中所有负数元素删除，返回被删除的元素个数。完成以下算法。(7分)

typedef struct{

int elem[100];

int length;

}SQ;

int deln(SQ *L)

{

／* 算法思路是，对每个元素做以下循环，如果第i个元素大于等于0，且前面有c个小于0的元素，则将它前移c个位置*／

int i，c; ／* c将记录小于0的元素个数 *／

for(i=0,c=0; ilength; i++)

{

if(__SQ->elem[i]_<0) c++;

else if(c>0) x->e[i - ____c______]=x->e[i];

}

x->length=_x->length-c_____;

return c;

}

5．以下算法将元素递增排列的顺序存储线性表A和B的元素的交集存人线性表C中。在空格处填上合适的语句或表达式完成该算法。(每空2分)

void SqList_Intersect(SqList A, SqList B, SqList &C

{ int i=1,j=1,k=0; ／* 下标初始化，A、B、C的下标都从1开始 */

while(i<=A.num && j<=B.num) ／* A、B表均末到表尾 */

{if(A.elem[i]

if(_A.elem[i]>B.elem[j]_) j++;

if(A.elem[i]==B.elem[j]) ／* 当发现了一个在A和B中都存在的元素 *／

{C.elem[_k++_]=A.elem[i]; /* 添加到C中 */

i++; j++;

}

}/* while */

C.num=k; /* C表长度置位 */

} /* SqList_Intersect */

6．已知一个单链表的表首指针为h，每个结点含元素值data和下一结点的地址next。链表一共有5个结点，其元素值分别为100，200，300，400，500，经过下列语句后，输出什么结果?(3分)

for(p=h; p->data<300; p=p->next);

p->next=p->next->next;

printf("%d", p->data);

答案：300

五、简答题

1．排序

(1)写出线性表(26，45，12，z0，30，5，15，29，16，2，18)采用基数排序后，第一趟结束时的结果。(4分)

(2)线性表采用简单选择排序算法对线性表(26，15，12，16，5，30)进行排序，进行交换的第一对元素是哪两个元素，在什么情况下，第一趟不需要进行元素的交换?(6分) 2．线性表有顺序表和链表两种存储结构，简述各自的优缺点。（4分）

顺序存储结构的特点：以数据元素在计算机内“物理位置相邻”来表示顺序表中数据元素之间的逻辑关系，能随机存取顺序表中任一数据元素。但它也使得插入和删除操作需移动大量的数据元素。由于顺序表需要一组地址连续的存储单元，对于长度可变的线性表就需要预分配足够的空间，有可能使一部分存储空间长期闲置不能充分利用。也可能由于估计不足，当表长超过预分配的空间而造成溢出，在这种情况下，又难于扩充连续的存储空间。

线性表的链式存储结构的特点是用一组任意的存储单元来依次存放线性表的结点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。不可以随机存取表中的任一结点

六、编程题

1．设a＝(a1，a2，…a m)和b＝(b1,b2，…，b n)是两个循环链表写出将这两个表合并为循环链表c的算法。(15分)

(a1，b1，a2，b2，…a m，b m，b m+1，…，b n) m≤n

c=

(a1，b1，a2，b2，…a n，b n，a n+1，…，a m) m>n

2．已知一个单链表中每个结点存放一个整数，并且其结点数不少于2。试编出算法以判断该链表中从第二项起的每个元素值是否等于其序号的平方减去其前驱结点的值，若满足，返回True，否则返回False。(10分)

答案：

Bool LinkList_H(LinkList &H){

p=H->next;j=2;

q=p->next;p=p->next;

while(p->next!=NULL&&(p->next->data!=j*j-q->data){

q=p->next;

p=p->next;

j++;

}

If(p->next==NULL)

return False;

If(p->next->data==j*j-q->data)

return True

}

3．某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个单链表存于计算机中，链表的每个结点指出同样价格的若干台，现在又新到m台价格为n元的电视机入库，试编写仓库电视机链表增加电视机的算法。

答案：

LinkList LinkList_H(LinkList &H,int m,int n){

p=H->next;

while(p->next!=NULL){

if(p->price!=n)

p=p->next;

p->data+=m;

p=p->next;

}

return H;

}

4．有一个带头结点的单链表，编写在值为x的结点之后插入m个结点的算法。(10 分) 答案：

LinkList LinkList_H(LinkList &H,int m,elemtype x){

p=H->next;

while(p->next!=NULL)

if(p->data!=x){

p=p->next;

}

q=p;

for(int i=0;i

s=(LinkList*)malloc(sizeof(LinkList));

s->next=q->next;q->next=s;q=p->next;

}

free(q);

return H;

}

5．我们用链表来存储多项式

m m m xe C xe C xe C x P +++= 2211)(, 其中011≥>>>=-e e e n m m ,

)1,,,2,1(0!>==m m i C i ,试编写求)(x P m 微商的算法。

（注，1/)(-=k k kx dx x d ）

6．已知线性表的元素按递增顺序排列，并以带首结点的单链表作为存储结构。试编写

一个删除表中所有值大于min 且小于max 的元素的算法。

答案：

LinkList LinkList_H(LinkLinst &H,int min,int max){

p=H->next;

whlie(p->data

p=p->next;

q=p;

whlie(p->data

p=p->next;

q->next=p->next;p->next=q;

free(q);

return LinkList;

}

7．已知单链表结点数据结构如下，编写算法判断一个单链表中各结点的值是否由小到

大排列。如果是(包括空表)，返回1，不是则返回0。(7分)

Typedef struct LinkNode{

int data;

Struct LinkNode *next;

}Node;

答案：

Typedef struct LinkNode{

int data;

Struct LinkNode *next;

}Node;

int LinkNode_H(Node H){

p=H->next;

whlie(p->next!=NULL&& p->datanext->data){

p=p->next;

}

If(p->next==NULL)

return 1;

if(p->data>p->next->data)

return 0;

}

8．已知顺序表的数据结构如下，编写算法．删除顺序表前面的10个元素。如果顺序表中的元素少于10个，则删完为止。(7分)

typedef struct LinkNode {

int elem[100];

int length;

}SQ;

答案：

typedef struct LinkNode {

int elem[100];

int length;

}SQ;

LinkNode LinkNode_Delete(LinkNode &H){

p=q=H->next;

for(int i=0;i<=10&& p->next!=NULL;i++){

q=p->next->nxet;p=p->next;

}

return H;

}

9.已知单链表结点数据结构如下，编写算法，删除单链表的表首结点与表尾结点。 (7分)

typedef struct LinkNode{

int data;

struct LinkNode *next;

}Node;

答案：

typedef struct LinkNode{

int data;

struct LinkNode *next;

}Node;

LinkNode LinkNode_Delete(LinkNode &H){

P=H->next;

H->next=p->next;

P=H->next;

while(p->next!=NULL){

q=p;p=p->next;}

q->next=NULL;

return H;

}

课后习题：

选择题：

1、链表不具备的特点是①。

①可随机访问任一节点②插入删除不需要移动元素

③不必事先估计存储空间④所需空间与其长度成正比

2、带头结点的单链表为空的判定条件是②。

①head==NULL ②head->next==NULL

③head->next==head ④head!=NULL

3、如果最常用的操作是取第i个结点及其前驱，则采用②存储方式最节省时间。

①单链表②双向链表③单循环链表④顺序表

填空题:

1、向一个长度为n的顺序表中的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动n-i+1个元素。

2、在单链表中，要删除某一指定的结点，必须找到该结点的头结点。

3、访问单链表中的结点，必须沿着链域进行。

4、在一个单链表中p所指结点之后插入一个s所指结点时，应执行

_s->next=p->next和p->next=s的操作。

编程题：

1、建立带表头结点的单链表h；

2、输出单链表h中所有结点的数据域值；

3、输入x、y。在第1个数据域值为x的结点后插入y，若无这样的结点x，则在表尾插入结点y；

4、输入k。删除单链表中所有值为k的结点，并输出被删除结点个数。

1.解：

void CreateList_H(LinkList &H,int n){

H=( LinkList)malloc(sizeof(LNode));

H->next=NULL;

For(i=n;i>0;i++){

p=( LinkList)malloc(sizeof(LNode));

scanf(&p->data);

p->next=H->next;

H->next=p;}

} //CreaterList_H

2.解：

Status Listshuchu_H(LinkList &H){

p=H;

if(p->next==NULL)

printf(“线性表为空”);

return ERROR;

else

while(p){

printf(“%d”,p->data);

p=p->next;}

return OK;

}

3.解：

Status ListInsert_L(ListInsert &L,int x , ElemType y){ p=L;

if(p->next==NULL)

printf(“线性表为空”);

return ERROR;

else

while(p&&p->data!=x){p=p->next}

s=( LinkList)malloc(sizeof(LNode));

s->data=y;s->next=p->next;

}

4,解：

Status ListDelete_L(ListInsert &L,int k, ElemType &e){ p=L;m=0;

if(p->next==NULL)

printf(“线性表为空”);

return ERROR;

else if(p){

while(p&&p->data!=k){p=p->next;}

q=p->next;p->next=q->next;

if(p)m=m+1;

free(q);

}

e=m;

return OK;

}

第二章线性表答案

2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 Status OrderListInsert-sq(SqList va, ElemType x) { //将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法1) if (va.length==va.listsize){ newbase=(ElemType *)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); va.elem=newbase; va.listsize+=LISTINCREMENT; }//当前存储空间已满，增加分配空间 if (!va.length) {va.elem[0]=x; ++va.length; return OK;} q=&(va.elem[0]); while (*q<=x)&&(q<=&(va.elem[va.length-1])) ++q; //查找插入位置 for (p=&(va.elem[va.length-1]); p>=q; --p) *(p+1)=*p; *q=x; ++va.length; return OK; }//OrderListInsert-sq Status OrderListInsert-sq(SqList va, ElemType x) { //将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法2) if (va.length==va.listsize){ newbase=(ElemType *)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); va.elem=newbase; va.listsize+=LISTINCREMENT; }//当前存储空间已满，增加分配空间 if (!va.length) {va.elem[0]=x; ++va.length; return OK;} p=&(va.elem[va.length-1]); while (P>=&(va.elem[0])&&*p>x) {*(p+1)=*p; --p;} *(p+1)=x; ++va.length;

第二章 考研试题精选

第二章线性表作业 一、选择题 1．下述哪一条是顺序存储结构的优点？（） A．存储密度大B．插入运算方便 C．删除运算方便D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（）的有限序列（n>0）。 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. 下面的叙述不正确的是（）

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

第二章矩阵 一、知识点复习 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 是一个4?5矩阵. 一个矩阵中的数称为它的元素,位于第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是正交矩阵?2A=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章线性表 一选择题 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

第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、描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。 2、对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。(1)定位到第i 个结点a i ； (2)定位到第i 个结点的前驱a i-1； (3)定位到尾结点； (4)定位到尾结点的前驱。 3、已知L 是有表头结点的单链表，且P 结点既不是首元结点，也不是尾结点，试写出实现下列功能的语句序列。 (1)在P 结点后插入S 结点；(2)在P 结点前插入S 结点；(3)在表首插入S 结点；(4)在表尾插入S 结点 . p=head; p=head; j=0; while ( p && jnext; j++;} p=head; j=0; while ( p && jnext; j++;} p=head; while ( p ->next ) p=p->next; while ( p->next->next ) p=p->next; （1）s->next=p->next; p->next=s; （2）q =L ; whil e ( q ->next !=p ) q =q ->next;s->next=p 或 q ->next ; q ->next=s; (3 ) s->next=L ->next; L ->next=s; （4）q =L ; whil e ( q ->next !=NULL) q =q ->next;s->next= q ->next ; q ->next=s;

4、设计算法：在顺序表中删除值为e 的元素，删除成功，返回1；否则，返回0。 5、设计一个算法，将一个带头节点的数据域依次为a 1，a 2，…，a n （n ≥3）的单链表的所有节点逆置，即第一个节点的数据域变为a n ，…，最后一个节点的数据域为a 1。（注意：先用自然语言描述算法基本思想，然后用类C++语言描述） int Sqlist::DeleteElem( T e ) { for (i=1; i<=len g t h ; i ++) // 按值顺序查找 * i 可从0开始 if (elem[i-1]= =e) // 找到，进行删除操作 { for ( j=i; jnext; 4 LinkList* pri = NULL; //之前的节点 5 while(p){ 6 LinkList* q = new LinkList; 7 q->data = p->data; //把当前节点记录下来 8 q->next = pri; 9 pri = q; 10 head->next = q; 11 LinkList* t = p; //当前节点没用了删除掉 12 p=p->next; 13 delete(t); 14 } 15 }

数据结构第2章作业 线性表(答案)

第2章线性表 班级学号__________-姓名 一、判断正误 （×）1. 链表的每个结点中都恰好包含一个指针。 链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。 （×）2. 链表的物理存储结构具有同链表一样的顺序。 链表的存储结构特点是无序，而链表的示意图有序。 （×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 链表的结点不会移动，只是指针内容改变。 （×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。 （×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” （×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 （×）7. 线性表在物理存储空间中也一定是连续的。 线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 （×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。 （×）9. 顺序存储方式只能用于存储线性结构。 顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如 完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍） （×）10. 线性表的逻辑顺序与存储顺序总是一致的。 理由同7。链式存储就无需一致。 二、单项选择题 （C ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（ B ）2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120 （ A ）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： （A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n） （C）删除第i个结点（1≤i≤n） （D）将n个结点从小到大排序 （ B ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8 （B）63.5 （C）63 （D）7 （ A ）5. 链式存储的存储结构所占存储空间：

第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/dc1315497.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.wendangku.net/doc/dc1315497.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.wendangku.net/doc/dc1315497.html,st+1) //i为元素编号，有效范围在https://www.wendangku.net/doc/dc1315497.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/dc1315497.html,st;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出 } return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i)

第二章线性表测试题

第二章测试试题 班级：学号：姓名：成绩： 一、选择题（每小题5分） 1.线性表是( A )。 A一个有限序列，可以为空；B一个有限序列，不能为空； C一个无限序列，可以为空；D一个无序序列，不能为空。 2.用链表表示线性表的优点是（C）。 A便于随机存取 B花费的存储空间较顺序存储少 C便于插入和删除 D数据元素的物理顺序与逻辑顺序相同 3.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( D )存储方式最节省运算时间。 A单链表 B双链表 C单循环链表 D带头结点的双循环链表 4.带头结点的单链表head为空的判定条件是（B ）。 A.head==NULL; B.head->next==NULL; C.head->next==head; D.head!=NULL; 5.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（C ）。 A.s->next=p->next;p->next=s; B.p->next=s->next;s->next=p; C.q->next=s;s->next=p; D.p->next=s; s->next=q; 二、填空题（每小题5分） 1．给定有n个结点的向量，建立一个单链表的时间复杂度_______。建立一个有序单链表的时间复杂度_______。 2．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_____个结点。 3．在一个长度为n的线性表（采用顺序存储结构）中删除第i个元素(1≤i≤n)时，需向前移动____个元素。 4．当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_____存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。5．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的个元素。 三、算法设计题（每小题25分） 1．设有一个用向量表示的线性表L，要求写出一个将该表逆置的过程，允许在原表的存储空间外再增加一个附加的工作单元。 2．已知两个整数集合A和B，它们的元素分别依元素值递增有序存放在两个单链表HA 和HB中，编写一个函数求出这两个集合的并集C，并要求集合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章线性表(课堂作业)

第2章线性表 1．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2．线性表是具有n个（）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 3.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置 元素的时间复杂性为（） A．O（i） B．O（1） C．O（n） D．O（i-1） 4.若长度为n的线性表采用顺序存储结构，在其第i个位置插 入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 5. 对于顺序存储的线性表，访问结点和增加、删除结点的时间 复杂度为（）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 6．对于一个头指针为head的带头结点的单链表，判定该表为空 表的条件是（）

A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 7.链表不具有的特点是（） A．可随机访问任一元素 B．插入、删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 8.在双向链表指针p的结点前插入一个指针q的结点操作是（）。 >Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q； >Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink ; C. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q; >Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q ; 9.在单链表指针为p的结点之后插入指针为s的结点，正确的 操作是：（）。 A． s->next=p->next;p->next=s; B． p->next=s;s->next=p->next; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 10．对于一个头指针为head的带头结点的单链表，判定该表为

线性代数1-2章精选练习题

第一章 行列式 一、单项选择题 1．下列排列是5阶偶排列的是 ( ). (A) 24315 (B) 14325 (C) 41523 (D)24351 2．如果n 阶排列n j j j 21的逆序数是k , 则排列12j j j n 的逆序数是( ). (A)k (B)k n (C) k n 2 ! (D)k n n 2)1( 3. n 阶行列式的展开式中含1122a a 的项共有( )项. (A) 0 (B)2 n (C) )!2( n (D) )!1( n 4． 001001001001 000( ). (A) 0 (B)1 (C) 1 (D) 2 5. 0 001100000100100( ). (A) 0 (B)1 (C) 1 (D) 2 6．在函数10 3 23211112)(x x x x x f 中3x 项的系数是( ). (A) 0 (B)1 (C) 1 (D) 2 7. 若2 1 33 32 31 232221 131211 a a a a a a a a a D ，则 32 3133 31 2221232112 111311122222 2a a a a a a a a a a a a D ( ). (A) 4 (B) 4 (C) 2 (D) 2 8．若 a a a a a 22 2112 11，则 21 11 2212ka a ka a ( ).

(A)ka (B)ka (C)a k 2 (D)a k 2 9． 已知4阶行列式中第1行元依次是3,1,0,4 , 第3行元的余子式依次为 x ,1,5,2 , 则 x ( ). (A) 0 (B)3 (C) 3 (D) 2 10. 若5 7 3 4 111113263478 D ，则D 中第一行元的代数余子式的和为( ). (A)1 (B)2 (C)3 (D)0 11. 若2 23 5 1 011110403 D ，则D 中第四行元的余子式的和为( ). (A)1 (B)2 (C)3 (D)0 12. k 等于下列选项中哪个值时，齐次线性方程组 00321 321321x x kx x kx x kx x x 有非零解. ( ) (A)1 (B)2 (C)3 (D)0 二、填空题 1. n 2阶排列)12(13)2(24 n n 的逆序数是. 2．在六阶行列式中项261365415432a a a a a a 所带的符号是. 3．四阶行列式中包含4322a a 且带正号的项是 . 4．若一个n 阶行列式中至少有12 n n 个元素等于0, 则这个行列式的值等于 .

第二章线性表习题及答案

第二章线性表习题及答案 一、基础知识题 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.一个线性表第一个元素的存储地址是100,每个元素的长度为4,则第5个元素的地址是( ) A.110 B.116 C.100 D.120 2. 向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。 A.64 B.63 C.63.5 D.7 3．在循环双链表的p所指接点之前插入s所指接点的操作是 A.p-> prior =s;s-> next t=p;p-> prior t->left=s;s-> prior =p-> prior; B. p-> prior =s;p-> prior -> next =s;s-> next =p;s-> prior =p-> prior; C.s-> next =p;s-> prior =p-> prior;p-> prior =s;p-> prior -> next =s; D.s-> next =p;s-> prior =p-> prior;p-> prior -> next =s;p-> prior =s; 4．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点。 A.n B.n/2 C.(n-1)/2 D.(n+1)/2 5．线性表是具有n个（）的有限序列（n≠0） A.表元素 B.字符 C.数据元素 D.数据项 6．非空的循环单链表head的尾结点（由P指向）满足 A. p->next=NULL B. p=NULL C. p->next=head D.p=head 7．在一个单链表中已知q所指的结点是p所指结点的前驱结点，若在q和p之间插入s 结点，则执行( ) A. s->next=p->next;p->next=s; B.p->next=s->next;s->next=p; C. q->next=s;s->next=p; D.p->next=s;s->next=q; 8．已知一个顺序存储线性表，若第1个结点的地址d，第3个的地址是5d，则第n个结点的地址为( ) A．[2*(n-1)+1]*d B.2*(n-1)*d C.[2*(n-1)-1]*d D.(n+1)*d 9．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( ) A.O(1) B.O(n) C.O(n2) D.O(nlog2n) 10．如果最常用的操作是提取第i个结点及其前驱，则采用( )存储方式最节省时间。 A．单链表 B.顺序表 C.循环链表 D.双链表 11．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n)之前插入一个新元素时，需要从后向前依次后移( )个元素。 A.n-i B.n-i+1 C.n-i-1 D.i 12．在一个长度为n的顺序存储线性表中，删除第i个元素(0≤i≤n-1)时，需要从后向

第二章_线性表(参考答案)

第二章线性表 一、填空题 1、数据逻辑结构包括线性结构、树型结构、图型结构这三种类型，树形结构和图形结构合称为非线性结构。 2、在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有个前驱结点，最后一个结点没有后续结点，其余每个结点有且只有一个后续结点。 3、在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。 4、在顺序表中，逻辑上相邻的元素，其物理位置一定相邻。在单链表中，逻辑上相邻的元素，其物理位置不一定相邻。 5、在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位置由头结点的next域指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋结点的next域指示。 6、阅读下列算法，并补充所缺内容。 void purge_linkst( ListNode *& la ) { // 从头指针为 la 的有序链表中删除所有值相同的多余元素，并释放被删结点空间ListNode *p,*q; if(la==NULL) return; q=la; p = la->link; while (p) { if (p && ___(1)p->data!=q->data___) {q=p; p = p->link;} else { q->link= ___(2)p->link___; delete(p); p=___(3)q->link___; } }//while }// purge_linkst 二、选择题 1、在数据结构中，从逻辑上可以把数据结构分成 C。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、线性表的逻辑顺序与存储顺序总是一致的，这种说法 B。 A、正确 B、不正确 3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址D。 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以 4、在以下的述叙中，正确的是B。 A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作是先进先出 D、队列的操作方式是先进后出 三、综合题 1、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 A、在P结点后插入S结点的语句序列是（（4）、（1））； B、在P结点前插入S结点的语句序列是（（7）、（11）、（8）、（4）、（1））； C、在表首插入S结点的语句序列是（（5）、（12））；

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

一、选择题 1. D 2. B 3. B 4. B 5. B 6. B 7. D 8. B 9. C 10. B 11. C 12. C 13. B 14. D 15. A 16. B 17. B 18. C 19. A 20. C 21. D 22. A 23. A 24. A 二、填空题 1. 首元素其直接前驱结点的链域的值 2. HL→next =NULL； HL=HL→next 3. 有限、一对一 4. O(1) 随机存取 5. 表中一半表长和该元素在表中的位置 6. 必定不一定 7. O（1） O（n） 8. 前驱结点的地址 O（n） 9. n-i+1 n-i 10. s->left=p p->right 三、判断题 1. × 2. × 3. × 4. × 5. × 6. × 7. √ 8. × 9. × 10. × 11. × 四、简答题 1. 线性表为：（78，50，40，60，34，90） 2. (36, 12, 8, 50, 25, 5, 15) 3. 解答： 尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear, 查找时间都是O(1)。

若用头指针来表示该链表，则查找终端结点的时间为O(n)。 五、编程题 1. 解答：由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法如下： int ListLength ( LinkList L ) { int len=0 ; ListNode *p; p=L; //设该表有头结点 while ( p->next ) { p=p->next; len++; } return len; } 2. int searchmin(linklist l) { int min; int *p; p=l; min=p->data; p=p->next; while (p->next< >nil) { if (min>p->data) min=p->data; p=p->next; } return min; } 3. int searchmax(linklist l) { int max; int *p; p=l; max=p->data; p=p->next; while (p->next< >nil) { if (maxdata) max=p->data; p=p->next; } return max; } 4. 顺序表：要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。 算法如下： // 顺序表结构定义同上题 void ReverseList( Seqlist *L) { DataType temp ; //设置临时空间用于存放data int i; for (i=0;i<=L->length/2;i++)//L->length/2为整除运算 { temp = L->data[i]; //交换数据 L -> data[ i ] = L -> data[ L -> length-1-i]; L -> data[ L -> length - 1 - i ] = temp; }

第二章课后作业答案

第二章线性表习题(答案) 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。 若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置也相邻。在单链表中，逻辑上相邻的元素，其物理位置不一定相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位置由头结点的next域指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋的next域指示。 3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：（4）、（1）。 b. 在P结点前插入S结点的语句序列是：（7）、（11）、（8）、（4）、（1）。 c. 在表首插入S结点的语句序列是：（5）、（12）。 d. 在表尾插入S结点的语句序列是：（11）、（9）、（1）、（6）。 供选择的语句有： （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; 4.设线性表存于a[n]中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保 持线性表的有序性。 void insertData(int a[],int data) { int i,location=0; for(i=0;i=location;i--) /*把查入点及查入点之后的数据以次后移一位*/ { a[i+1]=a[i]; } a[location]=data; /*把查新数据*/ lenth++; } 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 int DeleteData(int a[],int i,int k) { int j; if(i<1||i>lenth||k<0||k>lenth-k+1)return 0; for(j=i-1;j