还剩9页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
单元练习2一.判断题下列各题,正确的请在前面的括号内打;错误的打V X线性表的链式存储结构优于顺序存储x1链表的每一个结点都恰好包含一个指针域X2在线性表的链式存储结构中,逻辑上相邻的两个元素在物理位置上并不一定紧邻V3顺序存储方式的优点是存储密度大,插入、删除效率高X4线性链表的删除算法简单,因为当删除链中某个结点后,计算机会自动地将后续的各个单元向X5前挪移顺序表的每一个结点只能是一个简单类型,而链表的每一个结点可以是一个复杂类型X6线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素V7线性表采用顺序存储,必须占用一片连续的存储单元V8顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取X9插入和删除操作是数据结构中最基本的两种操作,所以这两种操作在数组中也时常使用X10二.填空题顺序表中逻辑上相邻的元素在物理位置上必须相连1线性表中结点的集合是有限的,结点间的关系是一对一关系2顺序表相对于链表的优点是节省存储和随机存取3链表相对于顺序表的优点是插入、删除方便4采用顺序存储结构的线性表叫顺序表56顺序表中访问任意一个结点的时间复杂度均为01o链表相对于顺序表的优点是插入、删除方便;缺点是存储密度小78在双链表中要删除已知结点*P,其时间复杂度为01o在单链表中要在已知结点之前插入一个新结点,需找到的直接前趋结点的地址,其查9*P*P找的时间复杂度为0no单链表中需知道头指针才干遍历整个链表10线性表中第一个结点没有直接前趋,称为开始结点11在一个长度为的顺序表中删除第个元素,要挪移个元素12n in-i在一个长度为的顺序表中,如果要在第个元素前插入一个元素,要后移个元素13n in-i4-1在无头结点的单链表中,第一个结点的地址存放在头指针中,而其它结点的存储地址存放在前趋14结点的指针域中当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快速度存取线性表中的元15素时,应采用顺序存储结构在线性表的链式存储中,元素之间的逻辑关系是通过指针决定的16在双向链表中,每一个结点都有两个指针域,它们一个指向其前趋结点,另一个指向其后继结点17对一个需要时常进行插入和删除操作的线性表,采用链式存储结构为宜18双链表中,设是指向其中待删除的结点,则需要执行的操作为卜〉19p p--pri next=p-next;p,next-prio=p-prior20在如图所示的链表中,若在指针P所在的结点之后插入数据域值为a和b的两个结点,则可用下列两个语句S-next-next=P~next和P-next=S来实现该操作三.选择题在具有个结点的单链表中,实现的操作,其算法的时间复杂度都是1n A0no—I I-I I1遍历链表或者求链表的第个结点在地址为的结点之后插入一个结点A.i B.P删除开始结点删除地址为的结点的后继结点
0.一|b|D.P⑵设、、为三个结点,、、分别代表它们的地址,则如下的存储结构称为a bc p1020BA.循环链表B.单链表C.双向循环链表D.双向链表单链表的存储密度3CoA.大于1B.等于1C.小于1D.不能确定已知一个顺序存储的线性表,设每一个结点占个存储单元,若第一个结点的地址为则第个结4m B,i点的地址为AA.B+i—l*m B.B+i*m C-B-i*m在有个结点的顺序表上做插入、删除结点运算的时间复杂度为5n BoA.01B.0n C.0n2D.0log n26设Llink、Rlink分别为循环双链表结点的左指针和右指针,则指针P所指的元素是双循环链表L的尾元素的条件是D oA.P二二L B.P—〉Llink=L C.P=NULL D.P—〉Rlink=L7两个指针P和Q,分别指向单链表的两个元素,P所指元素是Q所指元素前驱的条件是B oA.P-next=Q-next B.P-next二二Q C.Q-next==P D.P=二Q用链表存储的线性表,其优点是8C便于随机存取A,花费的存储空间比顺序表少B.便于插入和删除C.数据元素的物理顺序与逻辑顺序相同D.在单链表中,增加头结点的目的是9C使单链表至少有一个结点A.标志表中首结点的位置B.方便运算的实现C.说明该单链表是线性表的链式存储结构D,下面关于线性表的叙述中,错误的是10D关系顺序表必须占一片地址连续的存储单元顺序表可以随机存取任一元素A.B.链表不必占用一片地址连续的存储单元链表可以随机存取任一元素C.D.是线性表,已知的值是经运算后,的值是11L LengthList L5,DelList L,2LengthListLCoA.2B.3C.4D.512单链表的示意图如下L指向链表结点的前趋的指针是Q BA.L B.P C.Q D.R设为指向单循环链表上某结点的指针,则*的直接前驱13p pC oA.找不到B.查找时间复杂度为01C.查找时间复杂度为0n D.查找结点的次数约为n等概率情况下,在有个结点的顺序表上做插入结点运算,需平均挪移结点的数目为14n CoA.n B.n-l/2C.n/2D.n+l/2在下列链表中不能从当前结点出发访问到其余各结点的是15CoA.双向链表B.单循环链表C.单链表D.双向循环链表A.基地址B.结点大小C.向量大小D.基地址和结点大小在双链表中做插入运算的时间复杂度为17A oA.01B.0n C.002D.0log n216在顺序表中,只要知道D,就可以求出任一结点的存储地址链表不具备的特点是18A oA.随机访问B.不必事先估计存储空间C.插入删除时不需挪移元素D.所需空间与线性表成正比以下关于线性表的论述,不正确的为19Co线性表中的元素可以是数字、字符、记录等不同类型A.线性顺序表中包含的元素个数不是任意的B.线性表中的每一个结点都有且仅有一个直接前趋和一个直接后继C.存在这样的线性表,即表中没有任何结点D.在的运算中,使用顺序表比链表好20B插入根据序号查找删除.根据元素查找A.B,C.D12ListNode*Demol LinkListL,ListNode*pvoid Demo2ListNode*p,ListNode*q{//L是有头结点的单链表{//P,*q是链表中的两个结点ListNode*q=L-next;DataType temp;While qq-next!=p q=q-next;temp=p-data;p-data=q-data;if qreturn q;q-data=temp;else Error*p notin L;}解返回结点*的直接前趋结点地址1p交换结点*和结点*和的值不变2p qp q四.下述算法的功能是什么?五.程序填空
1.已知线性表中的元素是无序的,并以带表头结点的单链表作存储工试写一算法,删除表中所有大于小于的元素,试完成下列程序填空min,maxVoid deleteIklist head;datatype min,max{q=head-next;while p!=NULL{if p-data=min||p-data=max;{q=P P=p-next;}else{q-next=p-next;delete p;p=q-next;}}
2.在带头结点head的单链表的结点a之后插入新元素x,试完成下列程序填空struct node{elemtype data;node*next;;void Ikinsertnode*head,elemtype x{node*s,*p;s二new node;s-data=x;p=head-next;while p!=NULLp-data!=a D=D—〉nDxt:if p=NULLcout«不存在结点a!〃;else{s-next=p-nextp-next=s;六.程序设计题写一个对单循环链表进行遍历打印每一个结点的值的算法,已知链表中任意结点的地址为
1.PO对给定的带头结点的单链表编写一个删除中值为的结点的直接前趋结点的算法
2.L,L x将一个顺序表中从第个结点开始的个结点删除
3.i k已知一个单链表,编写一个函数从单链表中删除自第个结点起的个结点
4.i k有一个单链表不同结点的数据域值可能相同,其头指针为编写一个函数计算值域为的结点
5.head,x个数有两个循环单链表,链头指针分别为和编写一个函数将链表链接到链表
6.headl head2,headl链接后的链表仍是循环链表head2,
1.解void ShowListNode*P{ListNode*t=P;do{printf〃%c〃,t-data;t=t-rear;}while t!=P;
2.解void deleteListNode*L{ListNode*p=L,*q;if L-next-data==X{printf“值为x的结点是第一个结点,没有直接前趋结点可以删除”;return;for;p-next-data!=X;q=p;p=p-next;//删除指针p所指向的结点q-next=p-next;delete p;
3.解void DelSeqList*L,int i,int k{int j=iT+k;for j=0;jk;j++{L-dataEi-l+j]=L-data[i+k-2+j];if i+k-2+jL-lastbreak;void DelSeqList*L,int i,int k{int j=i-l+k;if jL-last{printf超出范围!”return;for j=0;jL-last-i;j++L-data[i-l+j]=L-data[i+k-2+j];
4.解:void Delnode*head,int i,int k{node*p,*q;int j;if i=lfor j=l;j=k;j++//删除前k个元素p=head;//P指向要删除的结点head=head-next;delete p;elsep二head;for j=l;j=i-2;j++//p指向要删除的结点的前一个结点p=p-next;for j=l;j=k;j++q=p-next;//q指向要删除的结点p-next=q-next;delete q;
5.解本题是遍历单链表的每一个结点,每遇到一个结点,结点个数加1,结点个数存储在变量n中实现本题功能的函数如下int counterheadnode*head;{node*p;int n=0;p=head;while p!=NULL{if p-data=xn++;p=p-next;return n;}
6.解本题的算法思想是先找到两链表的尾指针,将第一个链表的尾指针与第二个链表的头结点链接起来,使之成为循环的函数如下node*link node*headl,*head2{node*p,*q;p=headl;while p-next!=headlp=p-〉next;q=head2;while q-next!=head2q=q-next;p-next=head2;q-next=headl;return headl;摹拟考题
1.在顺序存储的线性表第i个位置插入新结点X,试完成下列程序填空typedef struct〃将data和last封装在一个结构体{datatype data[MAXLEN];//MAXLEN为线性表的最大长度int last;}SeqList;int InsListSeqList*L,int i,datatype x//插入结点函数{int j;if L-last==MAXLENT{cout〃顺序表已满!〃;return-1;if KI|I iL-last+2//检查插入位置的正确性{cout〈〃位置出错!〃;return0;for i=L-last;i=i-l;j一//结点挪移L—〉data「i+1〕二L—〉data「il:L-LataFi-11=x//新结点插入L-〉last++:或者+1return1;
2.一个带头指针的单链表,写出在值为x的结点之后插入m个结点的算法void insertmIklist head;int m{p=head-next;while p!二NULLp-data!=xp-p-next;ifp-data==x{q=p-next;fori=0;i ni:i++//找到x,在其后插入m个结点{s=new node;cin«a;//输入待插入的值s-data=a;p-next=s;P=s;}p-next=q;}
3.有两个循环单链表,头指针分别为headl和head2,下列函数是将链表headl链接到链表head2,链接后的链表仍然是循环链表,试完成下列程序填空提示先找到两链表的尾指针,再将第一个链表的尾指针与第二个链表的头结点链接起来node*linknode*headl,node*head2{node*p,*q;p=headl;while p-next!=headlp=p-next;q二head2;while q-next!=head2q=q-next;p-next=head2;q-next=headl;return headl;。