搜索
Ch2线性表一．填空：1．按顺序存储方法存储的线性表称为顺序表，按链式存储方法存储的线表称为链表。2．线性表是n个数据元素的有限序列。3．在个n结点的顺序表中插入一个结点需平均移动n/2个结点，在第i个之前插入一个元素时，需向后移动n-i+1个元素。123…i-1ii+1…n4．在个n结点的顺序表中删除一个结点需平均移动(n-1)/2个结点，删除第i个元素时，需向前移动n-i个元素。5．一个顺序表的第一个元素的存储地址是1000，每个元素的长度是2，则向量的第五个元素的地址是1008。Loc(ai)=Loc(a1)+(i-1)*L6．带头结点的单链表head为空的判定条件是head-next=NULL，不带头结点的单链表head为空的判定条件是head=NULL。7．在一个单链表中，已知p所指结点不是最后结点，若删除p的后继结点，则执行p-next=p-next-next。8．用单链表方式存储的线性表，存储每个结点需要两个域，一个是数据域，另一个是指针域。9．在一个单链表中，已知p所指结点是q所指结点的前驱结点，若在q之前插入结点s，要执行的操作为p-next=s;s-next=q。10．线性表的顺序存储结构是用一组地址连续的存储单元依次存储各元素。11．在双向链表中，每个结点有两个指针域，一个指向前驱，另一个指向后继。12．在一个单链表中的p所指结点之后插入一个s所指结点时，执行的操作为s-next=p-next；p-next=s。13．在一个单链表中的p所指结点之前插入一个s所指结点时，执行的操作为s-next=p-next；p-next=s；t=p-data；p-data=s-data；s-data=t。(交换)14．在一个单链中删除p所指结点时，应执行的操作是p-data=p-next-data；p-next=p-next-next。15．对于一个具有n个结点的单链表，在已知p所指结点之后插入一个新结点的时间复杂度为O(1)；在给定值为x的结点后插入一个新结点的时间复杂度为O(n)。16．线性表的顺序存储中，元素之间的逻辑关系是通过相对位置决定的；线性表的链接存储中，元素之间的逻辑关系是通过指针决定的。17．在单链表中，每个结点有1个指针域，最后一个结点的指针域为空。18．对于一个线性表经常进行的是存取操作，很少进行插入和删除操作时，则采用顺序存储结构为宜；相反，当经常进行的是插入和删除操作时，则采用链式存储结构为宜。29．顺序表相对于链表的优点有容易实现和随机存取。链表相对于顺序表的优点有不需要预分配存储空间和插入、删除操作方便。二．选择：1．下面关于线性表的叙述错误的是D。A．若用数组表示，表中诸元素的存储位置是连在一起的B．若用链表表示，便于插入和删除操作C．若用链表表示，不需要占用一片相邻的存储空间D．表的插入和删除操作仅允许在表的一端运行2．用带表头结点的链表表示线性表的主要好处是B。A．可以加快对表的遍历B．使空表和非空表的处理统一C．节省存储空间D．可以提高存取元素的速度3．线性表的顺序存储结构是一种A的存储结构。A．随机存取B．顺序存取C．索引存取D．HASH存取4．在线性表的第i个元素之前入一个元素时，需将第n至第i个元素C位置。A．向前移动一个B．向前移动i个C．向后移动一个D．向后移动i个5．在下面关于线性表的叙述中，选出正确的一项DA．线性表的每个元素都有一个直接前驱和直接后继B．线性表至少要有一个元素C．线性表中的元素必须按递增或递减的顺序排列D．除第一个元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继6．对于一个线性表若既要求能够进行较快的插入和删除，又要求存储结构能反映数据元素间的逻辑关系，应该BA．以顺序方式存储B．以链接方式存储C．以散列方式存储D.以索引方式存储7．下列描述线性表叙述错误的是AA．线性表的顺序存储的元素是从小到大顺序排列的B．线性表的链接存储，便于插入删除操作C．除第一个元素和最后一个元素外，其余每个元素有且仅有一个直接前驱和直接后继D．线性表可以为空8．线性表的逻辑顺序与存储顺序总是一致的，这种说法BA．正确B．不正确9．与数据元素本身的形式、内容、相对位置、个数无关的是数据的C？A．存储结构B．存储实现C．逻辑结构D．运算实现10．顺序存储结构AA．仅适合于静态查找表的存储B．仅适合于动态查找表的存储C．既适合静态又适合于动态查找表的存储D．既不适合静态又不适合于动态查找表的存储11．若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用A存储方式最节省时间。A．顺序表B．单链表C．双链表D．单循环链表12．对于有个元素的顺序表，任意删除一个元素后，平均移动次数约为CA．nB．lognC．n/2D．113．单链表的结点结构为{data,next}，下面算法要找出不带头节点的单链表中第i个元素的位置。此算法是BA．正确B．错误LinklistGet(LinklistV,inti){p=V;if(p==NULL)return(NULL);for(j=1;j=i;j++)//循环停止时，*P=?--ji{p=p-next;if(p==NULL)return(NULL);}returnp;}三.综合1．已知一个单链表如图所示，编写一个函数将该单链表复制一个拷贝。解：本题的算法思想是依次查找该单链表（其头指针为head1）中的每个节点，对每个节点复制一个新节点并链接到新的单链表（其头指针为head2）中。实现本题功能的函数如下：voidcopy(LinkListhead1,LinkListhead2){LinkListp,q,new;head2=(LinkList)malloc(sizeof(Node));/*建立一个头节点*/p=head1;q=head2;while(p!=NULL){new=LinkList)malloc(sizeof(Node));/*复制一个新节点new*/new-Data=p-Data;q-Next=new;/*将new链接到q之后*/q=new;p=p-Next;}q-Next=NULL;/*将最后一个节点的Next域置为NULL*/p=head2;/*删除头节点*/head2-head2-Next;free(p);}2．编写一个函数交换单链表中p所指向的位置和其后续位置上的两个节点，head指向该单链表的表头，p指向该单链表中的某一节点。解：本题的算法思想是：如果p存在后续节点，看它是否是头节点，如果是，则交换后要改变该链表的head，若不是头节点，则直接交换。实现本题功能的函数如下：LinkListswap(LinkListhead,LinkListp){LinkListq,back;q=p-next;if(q!=NULL)/*若p存在后续节点，则进行相应处理*/{if(p==head)/*若p指向头节点，则将该链表的前两个节点交换位置*/{p-next=q-next;q-next=p;head=q;}else/*若p指向第二个之后的节点*/{back=head;/*查找p的前驱节点*/while(back-next!=p)back=back-next;back-next=q;/*交换p和q的位置*/p-next=q-next;q-next=p;}return(head);}elsereturn(NULL);/*若p不存在后续，则返回NULL*/}3．有两个具有相同节点个数的单链表heada和headb如图所示，编写一个函数将其合并成如图所示的单链表headc。a1a2an∧heada…headb……headc……解：本题的算法思想是:遍历两个单链表heada,headb,依次将两链表中的节点复制headc中，直到链表遍历完为止。实现本题功能的函数如下：LinkListsum(LinkListheada,LinkListheadb){b1b2bn∧a1b1a2b2anbn∧LinkListheadc;headc=(LinkList)malloc(sizeof(LNode));pa=heada;pb=headb;pc=headc;while(pa!=NULL){newnode=(LinkList)malloc(sizeof(Node));/*复制一个与heada链表中节点相同的节点，把它链接到headc中*/newnode-data=pa-data;pc-next=newnode;pa=pa-next;pc=newnode;/*pc始终指向headc链表的最后一个节点*/new=(LinkList)malloc(sizeof(LNode));/*复制一个与headb链表中节点相同的节点，把它链接到headc中*/newnode-data=pb-data;pc-next=newnode;pb=pb-next;pc=newnode;/*pc始终指向headc链表的最后一个节点*/}pc-next=NULL;newnode=headc;headc=headc-next;/*删除headc链表的头节点*/free(newnode);}4．有一单链表，其结点的元素值以非递减有序排列。试编写删除该单链表中多余的元素值相同的结点的算法。解：本题采用的算法是：从头到尾扫描该单链表，并作这样的操作：若当前元素节点的元素值与后续节点的元素值不相等，则指针后移，否则删除该后续节点，直到扫描所有的节点。实现本题功能的函数如下：voiddelete(LinkListhead){//head为不带头结点的单链表LinkListp,q;p=head;if(head!=NULL){while(p-next!=NULL)if(p-data!=p-next-data)p=p-next;else{q=p-next;p-next=q-next;free(q);}}}5．有一单链表，head为单链表的头指针，试编写一算法查找数据域为x的结点，并返回链指针。解：本题是遍历该链表的每一个节点，每遇到一个数据域为x的节点，节点个数加1，节点个数存储在变量n中。实现本题功能的函数如下：intcount(LinkListhead,intx){LinkListp;intn=0;p=head;while(p!=NULL){if(p-data==x)n++;p=p-next;}returnn;}11．名词解释：线性表单链表解：线性表是n(n≥0)个数据元素的有限序列，除第一个结点没有前驱外，其余每个结点都只有一个前驱结点，除最后一个结点没有后继外，其余每个结点都只有一个后继结点。单链表是线性表的链式存储结构，用一组任意的存储单元存储线性表的元素，每个数据元素对应的结点包括一个存储数据信息的数据域和一个存储后继结点存储地址的指针域，所有结点链接成一个单链表。12．什么是头结点？说明链表中头结点的作用。解：给链表附加表头结点的目的是简化插入删除操作.由于开始结点的位置被存放在头结点的指针域中，所以对链表第一个位置的操作同其他位置一样，无须特殊处理。无论链表是否为空，其头指针是指向头结点的非空指针，因此对空表与非空表的处理也就统一了，简化了链表操作的实现。下午13：00—17：00度。全体员工都必须自觉遵守工作时间，实行不定时工作制的员工不必打卡。3.1.2.2打卡次数：一日两次，即早上上班打卡一次，下午下班打卡一次。3.1.2.3打卡时间：打卡时间为上班到岗时间和下班离岗时间；3.1.2.4因公外出不能打卡：因公外出不能打卡应填写《外勤登记表》,注明外出日期、事由、外勤起止时间。因公外出需事先申请，如因特殊情况不能事先申请，应在事毕到岗当日完成申请、审批手续，否则按旷工处理。因停电、卡钟（工卡）故障未打卡的员工，上班前、下班后要及时到部门考勤员处填写《未打卡补签申请表》，由直接主管签字证明当日的出勤状况，报部门经理、人力资源部