算法与数据结构线性表答案

算法与数据结构线性表答案第2章线性表一、判断题1线性关系的逻辑构造与存储构造总是一致的。解：错。单链表的逻辑构造与存储构造有可能是不一致的，有可能两个相邻结点的存储地址并不是相邻的。2每种数据构造都包括插入、删除和查找这三种根本运算。解：错。散列构造无插入与删除运算；栈没有查找，查找须配有另一个栈。3线性表中的每个结点最多只有一个前驱和一个后继。解：对。线性表的定义为：表中任意一个元素至多有一个前驱，至多有一后继。4线性的数据构造既可以顺序存储，也可以链接存储；非线性的数据构造那么只能链接存储。解：错。对于非线性的数据构造，假设对它的数据规定某种次序之后，也可以顺序存储。如，树的前、中、后序遍历之后的存储，一个前驱可能对应多个后继。5顺序存储方式只能用于存储线性构造。解：错。非线性构造也可采用顺序存储。6多维数组是向量的推广。解：对。多维向量的存储方式实际上与一维向量是一致的。7设串s的长度为n，那么s的子串个数最多为n(n+1)/2。解：错。s的长度为n，故它含有n个字符，它的子串应包括：1个字符的子串，2个字符的子串，…，n个字符的子串；这些子串的个数分别为8单链表从任何一个结点出发，都能访问到所有结点。解：错。单链表仅能从头结点出发去访问所有结点，不能访问前驱。9线性表的长度是线性表所占用的存储空间的大小。解：错。线性表所占用的存储空间大小为：每个结点所占用的存储字节数乘以线性表的长度。10双循环链表中，任意一结点的后继指针均指向其逻辑后继。解：错。任意结点的后继结点包含有两个指针llink和rlink，只有rlink指向其逻辑后继，而llink指向其逻辑前驱。11数据构造、数据元素、数据项在计算机中的映象(或表示)分别称为存储构造、结点、数据域。解：对。12线性表的顺序存储构造优于链式存储构造。解：错。各有优缺点。顺序存储构造的优点是：〔1〕存储效率高。〔2〕可随机访问任意结点，存取速度快。顺序存储构造的缺点是：〔1〕插入与删除操作费事。〔2〕顺序表的长度扩大费事。链式存储构造的优点是：〔1〕插入与删除方便。〔2〕顺序表的长度可任意〔动态分配内存〕。链式存储构造的缺点是：算法与数据结构线性表答案全文共9页，当前为第1页。〔1〕存储效率低。〔2〕对结点的访问不方便。算法与数据结构线性表答案全文共9页，当前为第1页。二、选择题1假设长度为n的线性表采用顺序存储构造，在其第i个位置插入一个新元素的算法的时间复杂度为C，元素的挪动次数为F(0≤i≤n)。(A)．O(0)(B)．O(1)(C)．O(n)(D)．O(n2)(E)．n-i+1(F)．n-i(G)．i(H)．i-1解：选C与E。因为，需要第i个位置至第n个位置的n-i+1个元素向后逐一挪动，因此，共做n-i+1次赋值运算，故T(n)=n-i+1，即T(n)=O(n)。2在长度为n的顺序存储的线性表中，删除第i个元素(0≤i≤n-1)时，需要从前向后依次前移C个元素。(A)．n-i(B)．n-i+1(C)．n-i-1(D)．i解：选C。因为前移元素的个数为n-i。3从解决问题的需要出发，为实现必要的功能所建立的数据构造，称为B。(A)．物理构造(B)．逻辑构造(C)．数据类型(D)．数据对象解：选B。4假设长度为n的线性表采用顺序存储构造，在其第i(0≤i≤n)个位置插入一个新元素的平均挪动元素挪动次数为C，在其第i(0≤i≤n-1)个位置删除一个元素的平均挪动元素挪动次数为D。(A)．n(B)．(n+1)/2(C)．n/2(D)．(n-1)/2解：选C。因为，在第0个位置插入新元素应挪动n个元素，而在第1个位置插入新元素应挪动n-1个元素，一般地，在第i(0≤i≤n)个位置插入一个新元素应挪动n-i个元素，而在某个位置上插入新元素的概率为1/〔n+1〕，故平均挪动的次数为n/(n+1)+(n-1)/(n+1)+…+(n-i)/(n+1)+…+1/(n+1)+0/(n+1)=n/2选D。因为，在第0个位置删除一个元素应挪动n-1个元素，而在第1个位置删除元素应挪动n-2个元素，一般地，在第i(0≤i≤n-1)个位置删除一个元素的应挪动n-i-1个元素，而在某个位置上删除元素的概率为1/n，故平均挪动的次数为(n-1)/n+(n-2)/n+…+(n-i-1)/n+…+1/n+0/n=(n-1)/25假设长度为n的无序线性表采用顺序存储构造，在其中查找某个元素的平均比较的次数为D。(A)．n(B)．(n-1)/2(C)．n/2(D)．(n+1)/2解：选D。n个元素的排列方式有n!种，而某个指定元素排在第i个位置的种数为(n-1)!，故某个指定元素恰好排在第i个位置的概率为(n-1)!/n!=1/n。这说明，待查找的元素恰好排在第1个位置、第2个位置、…和第n个位置的概率均为1/n。假设待查找的元素排在第i个位置，那么查找的次数为i次〔1≤i≤n〕，故平均查找次数为1/n+2/n+…+i/n+…+n/n=(n+1)/26对于只在首、尾两端进展插入操作的线性表，宜采用的存储构造为。(A)．顺序表(B)．带头指针的单链表(C)．带尾指针的单循环链表(D)．单链表解：选C。7在一个单链表中，假设要在指针q所指结点的后面插入一个由指针p所指向的结点，那么执行。(A)．q->link=p->link；p->link=q；(B)．p->link=q->link；q=p；算法与数据结构线性表答案全文共9页，当前为第2页。(C)．q->link=p->link；p=q；(D)．p->link=q->link；q->link=p算法与数据结构线性表答案全文共9页，当前为第2页。解：选D。8在一个单链表HL中，假设要向表头插入一个由指针p指向的结点，那么执行。(A)．HL=p;p->next=HL;(B)．p->link=HL;HL=p;(C)．p->link=HL;p=HL;(D)．p->link=HL->link;HL->link=p;解：假设单链表不带头结点，那么应选B。假设单链表带头结点，那么应选D。9在一个单链表HL中，假设要删除由指针q所指向结点的后继结点，那么执行。(A)．p=q->link;p->link=q->link;deletep;(B)．p=q->link;q->link=p;deletep;(C)．p=q->link;q->link=p->link;deletep;(D)．q->link=q->link->link;q->link=q;解：选C。假设选D，那么链表中没有了q的后继结点，但未删除。仅C选项可使q的后继结点被删除，并按原有结点顺序重新拉链。10设p为有头结点双向循环链表中某结点的指针，lLink为左链指针，rLink为右链指针，那么下述表达式中，不恒为真。(A)．p->rLink->lLink==p(B)．p->rLink->lLink==p->lLink->rLink(C)．p->lLink->rLink==p(D)．p->rLink->rLink==p->lLink->lLink解：选D。因为p->rLink->lLink==p==p->lLink->rLink，故只有D不一定为真。11假设某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，那么采用存储方式最节省时间。(A)．单链表(B)．双向链表(C)．带头结点的双循环链表(D)．单循环链表解：选C。12链表不具有的特点是。(A)．可随机访问任一元素(B)．插入删除不需要挪动元素(C)．不必事先估计存储空间(D)．所需空间与线性表长度成正比解：选A。13线性表采用链式存储时，其地址。(A)．连续的(B)．局部连续的(C)．一定是不连续的(D)．连续与否均可解：选D。14设有一8×8下三角矩阵A[8][8]，采用按行压缩存储的方式存放在一维数组B[]中，那么数组B[]的容量至少需要B个元素空间。(A)．32(B)．36(C)．16(D)．64解：选B。矩阵的第1行有8个非零元素，第2行有7个非零元素，…，第8行有1个非零元素，故需要存储的非零元素的个数为8+7+6+5+4+3+2+1=8*(1+8)/2=36三、填空题1对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为。解：在表头〔即第0个位置〕插入元素，需挪动的元素个数为n，然后再做1次赋值操作，故T(n)=n+1=O(n)。在表尾插入元素无需挪动表中已有元素，只需1次赋值操作，故T(n)=1=O(1)。算法与数据结构线性表答案全文共9页，当前为第3页。2在线性表的单链接存储中，假设一个元素所在结点的地址为p，那么其后继结点的地址为，假设假定p为一个数组a中的下标，那么其后继结点的下标为算法与数据结构线性表答案全文共9页，当前为第3页。解：应填入p->link，p+13在单循环链表中，最后一个结点的指针指向结点。解：表头结点。4在双向链表中每个结点包含有两个指针域，一个指向其结点，另一个指向其结点。解：应填入前驱，后继。5在双向循环链表中表头结点的左指针域指向结点，最后一个结点的右指针域指向结点。解：应填入表尾，表头。6在以HL为表头指针的带附加表头结点的单链表和单循环链表中，链表为空的条件分别为和。解：HL->link==NULL,HL->link==HL7在双循环链表L中，指针p所指结点为尾结点的条件为。解：p!=first&&p==first->link8在单链表中，假设要使指针p指向它所指结点的后继结点，其语句是。解：p=p->link9在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的、和三项。解：为了节省对矩阵的存储空间，稀疏矩阵采用仅存储非零元素的行下标、列以下与非零元素值的方式存储。10二维数组A[4][5]按行优先存储方法存储在内存中，假设每个元素占2个存储单元，且数组中第一个元素的存储地址为120，那么元素A[3][4]的存储地址为。假设其余条件不变，但是数组的存放方式变为列序优先，那么元素A[3][4]的存储地址变为。解：行优先方式存储：第0行、第1行、第2行的5个元素依次占据3*5*2=30个存储单元。而第3行的前4个元素占据4*2=8个存储单元，故A[3][4]的存储地址为120+30+8=158列优先方式存储：第0列、第1列、第2列、第3列的4个元素依次占据4*4*2=32个存储单元。而第4列的前3个元素占据3*2=6个存储单元，故A[3][4]的存储地址为120+32+6=158四、算法设计1编写算法将以数组表示方式的顺序表原地逆置。解：#include<iostream>usingnamespacestd;#defineN10voidDisplay(inta[],intn){for(inti=0;i<n;i++)cout<<a[i]<<"\t";cout<<endl;}//逆置函数1voidInvert1(inta[],intn){inttemp,i,j;算法与数据结构线性表答案全文共9页，当前为第4页。for(i=0,j=n-1;i<j;i++,j--)算法与数据结构线性表答案全文共9页，当前为第4页。 {temp=a[i];a[i]=a[j];a[j]=temp;}}//逆置函数2voidInvert2(inta[],intn){inttemp,i;for(i=0;i<n/2;i++){temp=a[i];a[i]=a[n-1-i];a[n-1-i]=temp;}}//主函数voidmain(){inti,a[N]={0,1,2,3,4,5,6,7,8,9};Display(a,N);Invert1(a,N);Display(a,N); Invert2(a,N);Display(a,N);}2对于带附加头结点的单链表，给出以下算法的代码。(1)假设单链表中结点的数据域中数据依升序排列，将名为newNode，数据域数据为x的结点插入到该单链表中。(2)从无序的单链表中查找出所有元素的最大值，该值由函数返回；假设单链表为空，那么显示出错信息并停顿运行。(3)统计出单链表中结点的值等于给定值x的结点数。解:#include<iostream>usingnamespacestd;//定义结点structNode{ intdata; structNode*next;};//插入函数voidInsert(Node*&head,intx){Node*p,*q,*r,*newnode;newnode=newNode;//创立新结点 newnode->data=x; newnode->next=NULL; if(head->next==NULL)//假设链表空 head->next=newnode;//头指针指向新结点 else//假设链表非空 { //获取链尾指针 p=head; while(p->next!=NULL) p=p->next; r=p;算法与数据结构线性表答案全文共9页，当前为第5页。算法与数据结构线性表答案全文共9页，当前为第5页。 if(newnode->data<head->data)//假设新结点数据小于头结点数据 { newnode->next=head; head=newnode;//新结点插入链头 } elseif(newnode->data>=r->data)//假设新结点数据大于或等于链尾结点数据 r->next=newnode;//新结点插入链尾else {//新结点插入链表中间 p=head; while(newnode->data>=p->data) {q=p;p=p->next;} newnode->next=q->next; q->next=newnode; } }}//求最大值函数voidMax(Node*&head,int&maxValue){Node*p=head->next;if(p==NULL)//空表{cout<<"链表为空，退出!"<<endl;return;}maxValue=p->data;while(p->next!=NULL){ p=p->next;if(p->data>maxValue) maxValue=p->data;}}//计算值为x的结点个数函数voidCount(Node*&head,intx,int&countNum){ countNum=0;Node*p=head->next;if(p==NULL)//空表 {cout<<"链表为空，退出!"<<endl;return;}do {if(p->data==x)countNum++;p=p->next; }while(p!=NULL);}//输出函数voidDisplay(Node*head){ Node*p=head->next;算法与数据结构线性表答案全文共9页，当前为第6页。算法与数据结构线性表答案全文共9页，当前为第6页。 {cout<<"链表空，退出!"<<endl;return;}while(p!=NULL) {cout<<"["<<p->data<<"]->"; p=p->next; } cout<<"NULL"<<endl;}//主函数voidmain(){ Node*head; head=newNode; head->next=NULL;//创立带附加头结点的局部指针 intx,maxValue,countNum; intn=5; cout<<"输入"<<n<<"个数,创立升序链表"<<endl; for(inti=1;i<=n;i++) { cin>>x; Insert(head,x);//调用插入法创立升序链表 }Display(head);//调入输出函数 Max(head,maxValue);//求结点值最大者 cout<<"最大值x="<<x<<endl; cout<<"输入需查找的结点值x=";cin>>x; Count(head,x,countNum);//调用计算结点值为x的结点个数 cout<<"值为"<<x<<"的结点个数为"<<countNum<<endl;}五、阅读算法并描绘其功能1intfun1(int&x){ inti=0;while(i<=last&&data[i]!=x)i++;if(i>=0&&i<=last) {last--;for(intj=i;j<=last;j++)data[j]=data[j+1];return1;}return0;}解：该函数的功能是，假设在全局数组data[0…last]中找到值为x的元素，将它删除并返回1；否那么返回0。2intfun2(intx)算法与数据结构线性表答案全文共9页，当前为第7页。算法与数据结构线性表答案全文共9页，当前为第7页。while(i<=last&&!found) if(data[i]!=x)i++; elsefound=1;returnfound;}解：该函数的功能是，假设在全局数组data[0…last]中，找到值为x的元素，那么返回1；否那么返回0。验证程序如下：#include<iostream>usingnamespacestd;intdata[10]={1,2,3,4,5,6,7,8,9,10};intlast=9;//函数1intfun1(intx){inti=0;while(i<=last&&data[i]!=x) i++;if(i>=0&&i<=last){ last--