数据结构复习自测题第2章线性表答案

第2章自测卷答 级—二三四五六七一、填空（113分在表中的位置有关。线性表中结点的集合是有 一对 的向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n- 个元素向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n- 个元素在顺序表中任意一结点的时间复杂度均为 ，因此，顺序表也称为随机存取的数据结构在单链表中，除了首元结点外，任一结点的位置由其直接前驱结点的链域的值指示O（n（（）1.（×）3.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向（）4.（）5.（×）6.顺序方式的优点是密度大，且插入、删除运算效率高在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。（×）7.线性表在物理空间中也一定是连续的错，线性表有两种方式，顺序和链式。后者不要求连续存放（×）8.线性表在顺序时，逻辑上相邻的元素未必在的物理位置次序上相邻错误。线性表有两种方式，在顺序时，逻辑上相邻的元素在的物理位置次序上也相邻（×）9.顺序方式只能用于线性结构错误。顺序方式不仅能用于线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳方式是顺序方式（后一节介绍）（×）10.线性表的逻辑顺序与顺序总是一致的错，理由同7。链式就无需一致（ （A）结 （C）顺序结 （ （A）3.在nO（1）（A）第i个结点（1≤i≤n）和求第i个结点的直接前驱i个结点n（ ）4.127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 （A）5.的结构所占空间（ ）6.链表是一种采 结构的线性表（A）顺 （ ）7.线性表若采用链式结构时，要求内存中可用单元的地址 （ ）8．线性表Ｌ （Ｃ）Ｌ中的结 （ ）9．单链表的密（Ａ）1（Ｂ）1；（Ｃ）1（Ｄ）（ ）10．设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式结构称043 043

（Ｂ）单链表（Ｃ）双向循环链 答：①顺序时，相邻数据元素的存放地址也相邻（逻辑与物理统一要求内存中可用单元的地址必须是连续的。（<1，2.描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点。在单链表中设置头结点的答首结指链中线表中一个据元素1的结点为操作便常在表首元点之附设一个结点称头结，该点的据域不线表的元素，作是为对链进行作时可对空、非空循链表适用是否置头点是不的构表示一辑结的问。

首元素结点是指链表中线性表中第一个数据元素a1的结点2个字节）UXVYZ 答 StatusStatusDeleteK(SqList&a,inti,int 结构的线性表a中删除第i个元素起的k个元素if(i<1||k<0||i+k>a.length)returnINFEASIBLE; for(count=1;count<k;count++)for(j=a.length;j>=i+1; j--)a.elem[j-1]=a.elem[j];a.length--;}return}//Elem//空间基//#defineLISTINITSIZE100#defineLISTINITSIZE100#defineLISTINCREMENT10typedefstruct10，若从第一位置（i=1）10个元素（k=10）,要求合理但会被判为。ifi<1||k<0||i+k>a.lengthreturn(（0<i≤a.length）^()第二个FOR语句中，元素前移的次序错误。应将for(j=a.length; j--)a.elem[j-1]=forj>=i+1;ja.length;ja.elem[j-1]intn;ET{intETintn;ET{intETfor(k=1;k<=n/2;{t=a[k-1];a[k-1]=a[n-k];a[n-k]=t;}}n的线性表数组A(1:n)。C语言描述如下（其中ET为数据元素的类型 (11)(10)(4)S->next=P->next;P指向该链表的第一个结点解：C程序如下(已上机通过)：typedefstructliuyu{intdata;structliuyu*link;}test;liuyu*p,*q,*r,*head;int main {int p=head;i=0;while(i!=-{printf("/ninputaninteger[stopby'-9999']:"); /*inputdata issaved p=p-} p=head;i=0; while(p->link!=NULL)}printf("\nnodenumber=%d\n",i- }请编写26个字母按特定字母值插入或删除的完整程序，可自行选用顺序或链表结#include<stdioh> #include<stdlibh>typedefstructliuyu{chardata;structliuyu*link;}test;liuyu*p,*q,*r,*head;int intvoidbuild(); /**/voiddisy();intinsert_char(char,char); /*插入一个字母，在第字母Y之前，若无字母则加到末尾*/intdelet_char(char); /*删除元素X，注意保存X的前趋元素指针！*/ void {int {p->data=i+'a'-1; /*'a'也可用其ASCII码97来表示 p=p->link;p-} voiddis while(p-{printf("%c",p->data);p=p->link;}} intinsert_char(charX,char { else{while((p->data!=Y)&&(p->link!=NULL)){q=p;p=p->link;}if(p->data==Y){q->link=r;r->link=p;}} intdelet_char(char /*删除元素XX{ else{while((p->data!=X)&&(p->link!=NULL)){q->link=p->link; }} void {disprintf("insertreturnvalue=%d\n",insert_char('L','W'));printf("deletereturnvalue=%d\n",delet_char('z'))