《大学《数据结构》习题（附答案）.docx》由会员分享，可在线阅读，更多相关《大学《数据结构》习题（附答案）.docx（102页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1章绪论1.1选择题1 .算法的时间复杂度取决于(C )A )问题的规模 B )待处理数据的初态C ) A和B2 .计算机算法指的是解决问题的步骤序列，它必须具备(B )这三个特性。A)可执行性、可移植性、可扩充性B)可执行性、确定性、有穷性C)确定性、有穷性、稳定性 D)易读性、稳定性、安全性5 .从逻辑上可以把数据结构分为(C )两大类。A)动态结构、静态结构B)顺序结构、链式结构C)线性结构、非线性结构D)初等结构、构造型结构6 .在下面的程序段中，对x的赋值的语句频度为(C )for(i=0;in;i+)for(j=0;j=l;i)for(j=l;jAU+l)Aj与 Aj+1对换；A
2、. O (n )B ) O(nlog2n) C ) O(n3) D ) O(n2)1.2填空题2.对于给定的n个元素，可以构造出的逻辑结构有集合、线性结构、树形结构、图状结构或网状结构四种。4 .数据结构中评价算法的两个重要指标是：算法的时间复杂度和空间复杂度。5 .数据结构是研讨数据的逻辑结构和物理结构以及它们之间的相互关系,并对与这种结构定义相应的_操作(运算)_设计出相应的算法6 .一个算法具有5个特性：有穷性_、确定性、可行性，有零个或多个输入、有一个或多个输出。9.已知如下程序段for(i=n;i0;i)语句1 x=x+l;语句2for(j=n;j=i;j-)语句3y=y+1;语句4
3、1语句1执行的频度为_n+l_;语句2执行的频度为_n_;语句3执行的频度为_n(n+3)/2_；语句4执行的频度为i(n+l)/2_。10 .在下面的程序段中，对x的赋值语句的频度为(表示为n的函数) for(i=0;in;i+)for(j=0;ji;j+)for(k=0;kj;k+)x = x +delta;【答案】1+(1+2)+(1+2+3)+.+( l+2+.+n )=n(n+l)(n+2)/6, O(n3)11 .下面程序段中带下划线的语句的执行次数的数量级是。i=l; while(in) i=i*2;【答案】log2n12 .计算机执行下面的语句时，语句s的执行次数为。for(i
4、=l;i=i;j) s;【答案】(n+3)(n-2)/213 .下面程序段的时间复杂度为。(nl)sum=l;for (i=0;sumn;i+) sum+=l;答案O(n)第2章线性表2.1选择题1 .对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择(A )最节省时间A)顺序表B)带头结点的双循环链表 C)单链表D)带尾结点的单循环链表2 .若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为(C )(1iprior=q; q-next=p; p-prior-next=q; q-prior=p-prior;B ) q-prior=p-prior;
5、 p-prior-next=q; q-next=p; p-prior=q-next;C) q-next=p; p-next=q; p-prior-next=q; q-next=p;D) p-prior-next=q; q-next=p; q-prior=p-prior; p-prior=q;4 .在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是(C )A ) O(nlog2n ) B )0(1) C) O(n ) D) O(n2)5 .在一个以h为头指针的单循环链中，p指针指向链尾结点的条件是(B )A) p-next=NULLB ) p-next=h C ) p-n
6、ext-next=hD) p-data=-16.对于一个具有n个结点的线性表，建立其单链表的时间复杂度是（A ）A） O（n） B） 0（1）8.在双向链表存储结构中,C ） O（nlog2n） D ） O（n2）删除p所指的结点时须修改指针（A ）A) p-prior-next=p-nextp-next-prior=p-prior;B ) p-prior=p-prior-priorP-prior-next=p;C) p-next-prior=p prior=p-next-next;9.线性表采用链式存储时,p-next=p-next-nextD) p-next=p-prior-prior其元
7、素地址（D ）P-A）必须是连续的B）一定是不连续的C）部分地址是连续的续与否均可2.2填空题1.线性表 L= (aH a2,.an）用数组表示，假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是.2.在单链表中设置头结点的作用是.【答案】主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表头指针不变。3 .线性表的顺序存储是通过.来反应元素之间的逻辑关系，而链式存储结构是通过来反应元素之间的逻辑关系。【答案】（1）数据元素的前后顺序（2）元素中的指针4 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操
8、作时，则采用存储结构最节省时间，相反当经常进行插入和删除操作时，则采用存储结构最节省时间。【答案】（1）顺序（2）链式5 .对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为,在给定值为x的结点后插入一个新结点的时间复杂度为.【答案】(1 ) 0(1)( 2 ) O(n)7 .对于双向链表，在两个结点之间插入一个新结点需修改的指针共 4.个，单链表为8.个。循环单链表的最大优点是.。【答案】从任一结点出发都可访问到链表中每一个元素。9.若要在一个不带头结点的单链表的首结点*p结点之前插入一个*s结点时，可执行下列操作:s-next=p-next=s;t=p-data;
9、p-data=s-data=:答案1（1） p-next （2） s-data （3） t10 .某线性表采用顺序存储结构，每个元素占据4个存储单元，首地址为100,则下标为11的（第12个）元素的存储地址为14411 .带头结点的双循环链表L中只有一个元素结点的条件是。【答案】L-next-next=L12 3判断题1 .取线性表的第i个元素的时间同i的大小有关（）【答案】X2 .线性表的特点是每个元素都有一个前驱和一个后继（）【答案】x3 .顺序存储方式的优点是存储密度大，且插入、删除运算效率高（）【答案】x4 .线性表采用链表存储时，结点的存储空间可以是不连续的（）【答案】q5 .链表是
10、采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高（）【答案】Y6 .顺序存储方式只能用于存储线性结构（）【答案】x解析】线性结构、树型结构和图状结构均可用顺序存储表示。9 .顺序存储结构的主要缺点是不利于插入或删除操作（）【答案】410 .顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（）【答案】x11 4程序设计题1 .设顺序表va中的数据元素递增有序。试设计一个算法，将x插入到顺序表的适当位置上，以保持该表的有序性。void Insert_SqList（SqList va,int x）/*把 x 插入递增有序表 va 中*/int i;if（va
11、.length MAXSIZE） return;for（i=va.length-l ;va.elemix&i=0;i）va.elemi+ l=va.elemi;va.elemi-i-l=x;va.length+4-;/*Insert_SqList*/2 .设A=（ai，a2,，am）和B=（bi，b2,，bn）均为顺序表，试设计一个比较A, B大小的算法（请注意：在算法中，不要破坏原表A和B）。【算法分析】比较顺序表A和B,并用返回值表示结果，值为1,表示AB;值为表示AvB;值为0,表示A=Bo1)当两个顺序表可以互相比较时，若对应元素不等，则返回值为1或-1；2)当两个顺序表可以互相比较的
12、部分完全相同时，若表长也相同，则返回值为0;否则，哪个较长，哪个就较大【算法源代码】int ListComp(SqList A,SqList B)for(i=l;i=A.length&iB.elemi?l1;if(A.length=B.length) return 0;return A.lengthB .length?11;/*当两个顺序表可以互相比较的部分完全相同时，哪个较长，哪个就较大*/*ListComp */3.已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和no试设计一个算法将这两个链表连接在一起(即令其中一个表的首元结点连在另一个表的最后一个结点之后)
13、，假设指针he指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。【算法分析】1)单链表ha的头结点作为连接后的链表的头结点，即hc=ha;2)查找单链表ha的最后一个结点，由指针p指向，即pnext=NULL;3 )将单链表hb的首元结点(非头结点)连接在p之后，即p-next=hb-next;4)回收单链表hb的头结点空间【算法源代码】void ListConcat(LinkList ha,LinkList hb,LinkList *hc)/*把链表 hb接在 ha后面形成链表 he*/*hc=ha;p=ha;/*由指针p指向ha的尾元结点*/p=p-next;p-next=
14、hb-next;free(hb);/*ListConcat */4 .试设计一个算法，在无头结点的动态单链表上实现线性表操作INSERT (L, i, b),并和在带头结点的动态单链表上实现相同操作的算法进行比较。【算法分析】1)生成新结点存放元素b,由指针new指向；2)将new插入在单链表的第i个元素的位置上：若i=l, new插在链表首部；否则查找第i-1个结点，由指针p指向，然后将new插在p之后。【算法源代码】void Insert(LinkList *L,int i,int b) LinkList new;new=(LinkList*)malloc(sizeof(LNode);ne
15、w-data=b;if(i=l)/*插入在链表头部*/New-next=*L;*L=new;)else/*插入在第i个元素的位置*/p=*L;while(-il) p=p-next;new-next=p-next;p-next=new;/*Insert */5.已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试设计一个高效的算法，删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素)，同时释放被删结点空间(注意：mink和maxk是给定的两个参变量。它们的值可以和表中的元素相同，也可以不同)。【算法分析】1)查找最后一个不大于mink的元素结点，由指针p指向；2 )如
16、果还有比mink更大的元素，查找第一个不小于maxk的元素，由指针q指向；3 ) p-next=q即删除表中所有值大于mink且小于maxk的元素。【算法源代码】void Delete_Between(LinkList *L,int mink,int maxk)p=*L;while(p-next-datanext;/*p是最后一个不大于 mink 的元素*/if(p-next)/*如果还有比mink更大的元素*/(q=p-next;while(q-datanext;/*q 是第一个不小于 maxk 的元素*/p-next=q;/*Delete_Between */6.已知线性表中的元素以值递增
17、有序排列，并以单链表作存储结构。试设计一个高效的算法，删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)，同时释放被删结点空间。【算法分析】1)初始化指针p和q,分别指向链表中相邻的两个元素；2)当p-next不为空时，做如下处理：若相邻两元素不相等时，p和q都向后推一步；否则，当相邻元素相等时，删除多余元素。【算法源代码】void Delete_Equal(LinkList *L)(p=(*L)-next;q=p-next;/*p和q指向相邻的两个元素*/ while(p-next)(if(pdata!二qdata)/*若相邻两元素不相等时，p和q都向后推一步*/(p=
18、p-next;q=p-next;else(while(q-data=pdata)/*当相邻元素相等时删除多余元素*/(r=q；q=q-next;free(r);p-nex t=q ;p=q ;q=p-next;/*else*/*while*/*Delete_Equal */7 .试设计一个算法，对带头结点的单链表实现就地逆置。【算法分析】1)空表或长度为1的表，不做任何处理；2)表长大于2时，做如下处理：首先将整个链表一分为二，即从链表的第一元素结点处断开；逐个地把剩余链表的当前元素q插入到链表的头部。【算法源代码】void LinkList_reverse(LinkList L) if(!L
19、-nextll!L-next-next) return;p=L-next; q=p-next; s=q-next;p-next=NULL;/*从链表的第一元素结点处断开*/ while(s-next)q-next=p;p=q;q=s;s=s-next;/*把L的元素逐个插入新表表头*/q-next=p;s-next=q;L-next=s;/*LinkList_reverse*/8 .设线性表A=(aj, a2,，am)和B=(bi， b2，bn),试设计一个按下列规则合并A, B 为线性表C的算法，即使得C=(a，b,ai，bm , bm+1，bn )占 mgn 时；或者C=(a b,， bn
20、,3n+l ，., am)当 FHn 时 o线性表A, B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。【算法分析】1)初始化指针p指向链表A的当前元素，指针q指向链表B的当前元素；2)当链表A和B均为结束时，做如下处理：将B的元素插入若A非空，将A的元素插入指针p和q同时后移【算法源代码】void mergel(LinkList A,LinkList B,LinkList *C)p=A-next;q=B-next;*C=A;while(p&q) s=p-next;p-next=q;/*将 B 的元素插入*/ if(s) t=q-nex
21、t;q-next=s;/*若A非空，将A的元素插入*/p=s;q=t;/*指针p和q同时后移*/*while*/*mergel */9 .假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构，请设计一个算法将A表和B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C,并要求利用原表(即A表和B表)的结点空间构造C表。【算法分析】按从小到大的顺序依次把A和B的元素插入新表的头部pc处，最后处理A或B的剩余元素。【算法源代码】void reverse_merge(LinkList A,LinkList B,LinkList *C) LinkList
22、pa,pb,pre;pa=A-next;pb=B-next;/*pa和pb分别指向A和B的当前元素*/pre=NULL;while(pallpb) if(pa-datavpb-datall!pb)/*将 A 的元素插入新表*/ pc=pa;q=pa-next;pa-next=pre;pa=q;else /*将B的元素插入新表*/ pc=pb;q=pb-next;pb-next=pre;pb=q; pre=pc;)*C=A;A-next=pc;/*构造新表头*/*re verse_merge */10 .已知A, B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C
23、表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度(注意：题中没有特别指明同一表中的元素值各不相同)。【算法分析】先从B和C中找出共有元素，记为same,再在A中从当前位置开始，凡小于same 的元素均保留(存到新的位置)，等于same的就跳过，到大于same时就再找下一个same。【算法源代码】void SqList_Intersect_Delete(SqList *A,SqList B,SqList C)i=0;j=0;k=0;m=0;/*i指示A中元素原来的位置，m为移动后的位置*/while(i(*A).length&jB.length& kC.length)
24、 if(B.elemgC.elemkl) k+;elsesame=B.elemj;/*找到了相同元素 same*/while(B.elemj=same) j+;while(C.elemk=same) k+;/*j 和 k 后移到新的元素*/while(i(*A).length&(*A).elemisame)(*A).elemm+=(*A).elemi+;/*需保留的元素移动到新位置*/while(i(*A).length&(*A).elemi=same) i+;/*跳过相同的元素*/)/*while*/while(inext!=NULL)/*链表不为空表*/p=la-next-next;/*p
25、指向第一结点的后继*/la-next-next=NULL;/*直接插入原则认为第一元素有序，然后从第二元素起依次插入*/ while(p!=NULL)r=p-next;/*暂存 p 的后继*/ q=la;while(q-next!=NULL&q-next-datadata)q=q-next;/*查才弋*宙入位置*/ p-next=q-next;/*将p结点链入链表*/ q-next=p;p=r；12 .设有一个双向循环链表，每个结点中除有prior, data和next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次LOCATE
26、( L, X )的操作后，被访问的结点(元素值等于X的结点)中的频度域freq的值便增1,同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的LOCATE操作的算法。【算法分析】1 )在双向链表中查找数据值为x的结点，由指针p指向，若找不到，直接返回，否则执行第2步；2 )修改x结点的访问频度freq,并将结点从链表上摘下；3)顺结点的前驱链查找该结点的位置，即找到一个结点的访问频度大于x结点的访问频度，由指针q指向；若q和p不是相邻结点，调整位置，把p插在q之后。【算法源代码】DuLNode *Locate_Du
27、List(DuLinkList *L,int x) p=(*L)-next;while(p.data!=x&p!=(*L) p=p-next;if(p=(*L) return NULL;/*没找至1x 结点*/p-freq+;p-pre-next=p-next;p-next-pre=p-pre;/*将 x 结点从链表上摘下*/q=p-pre;while(q-freqfreq&p!=(*L) q=q-pre;/*查找插入位置*/if(q!=p-pre)/*将 x 结点插入*/q-next-pre=p;p-next=q-next;q-next=p;p-pre=q;/*调整位置*/return p;
28、/*Locate_DuList */13 .已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点)，编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为0(m+n+p ),其中m、n和p分别为三个表的长度。【算法分析】留下三个链表中公共数据，首先查找两表A和B中公共数据，再去C中找有无该数据。要消除重复元素，应记住前驱，要求时间复杂度O (m+n+p),在查找每个链表时，指针不能回溯。【算法源代码】LinkList Common(LinkList A,
29、 LinkList B, LinkList C)pa=A-next;pb=B-next; pc=C-next;/*pa, pb 和 pc 是工作指针*/pre=A;while(pa & pb & pc)/*当三表均不空时，查找共同元素*/ while(pa & pb)if(pa-datadata)/*处理 pa 结点，后移指针*/u=pa;pa=pa-next;free(u);else if(pa-data pb-data)pb=pb-next;else if (pa & pb)/*处理A和B表元素值相等的结点*/while(pc & pc-datadata)pc=pc-next;if(pc)
30、if(pcdatapadata)/*处理pa结点,后移指针*/u=pa;pa=pa-next;free(u); elseif(pre=A)/*结果表中第一个结点*/ pre-next=pa;pre=pa;pa=pa-nextelse if(pre-data=pa-data)/*重复结点不链入 A 表*/u=pa;pa=pa-next;free(u);elsepre-next=pa;pre=pa;pa=pa-next;A A 表*/pb=pb-next;pc=pc-next;/*链表的工作指针后移*/ elseif(pa=NULL)pre-next=NULL;/*若 A 表已结束，置 A 表表尾
31、*/ else/*处理原A表未到尾而B或C到尾的情况*/pre-next=NULL;/*置 A 表表尾标记*/ while(pa!=NULL)/*删除原A表剩余元素。*/u=pa;pa=pa-next;free(u);14 .设head为一单链表的头指针，单链表的每个结点由一个整数域data和指针域next组成，整数在单链表中是无序的。编一函数，将head链中结点分成一个奇数链和一个偶数链，分别由p, q指向，每个链中的数据按由小到大排列。程序中不得使用malloc申请空间.【算法分析】本题要求将一个链表分解成两个链表，两个链表都要有序，两链表建立过程中不得使用malloc申请空间，这就是要利
32、用原链表空间，随着原链表的分解，新建链表随之排序。【算法源代码】discreat(LinkList p, LinkList q, LinkList head) p=NULL; q=NULL;/*p和q链表初始化为空表*/ s=head;while(s!=NULL)r=s-next;/*暂存 s 的后继*/ if(s-data%2=0)/*处理偶数*/if (p=NULL)p=s;p-next=NULL;/*第一个偶数结点*/ else pre=p;if(pre-datas-data)s-next=pre;p=s;/*插入当前最小值结点*/ elsewhile (pre-next!=NULL)i
33、f (pre-next-datadata) pre=pre-next;/*查找月宙入位置*/ s-next=pre-next;/*链入结点*/pre-next=s;else/*处理奇数链if (q=NULL)q=s;q-next=NULL;/*第一奇数结点*/ elsepre=q;if (pre-datas-data)s-next=pre; q=s;/*修改头指针*/ elsewhile (pre-next!=NULL)/*查找插入位置*/ if (pre-next-datadata) pre=pre-next; s-next=pre-next;/*链入结点*/ pre-next=s;/*结束
34、奇数链结点*/ s=r;/*s指向新的待排序结点*/第3章栈和队列3.1 选择题1 .一个栈的输入序列为123.n,若输出序列的第一个元素是n,输出第i (1 i next=s;front=s;B ） s-next=rear;rear=s;C ） rear-next=s;rear=s;D ） s-next=front;front=s;【解析】队列是运算受限的线性表（FIFO）,插入元素只能插在队尾，所以需修改队尾指针。12 .判定一个栈S （元素个数最多为MAXSIZE）为空和满的条件分别为（B ）A） S-top!=-l S-top!=MAXSIZE-l B） S-top=-l S-top=
35、MAXSIZE-lC） S-top=-l S-top!=MAXSIZE-l D） S-top!=-l S-top=MAXSIZE-l13 .循环顺序队列中是否可以插入下一个元素（A ）A）与队头指针和队尾指针的值有关B）只与队尾指针的值有关，与队头指针的值无关C）只与数组大小有关，而与队头指针和队尾指针的值无关D）与曾经进行过多少次插入操作有关【解析】在循环队列中判断队满的条件为：（q.rear+l）%m=q.front是否为真，从中可以看出，与队头指针和队尾指针的值有关。14 .最不适合用作链队的链表是（A ）A）只带队头指针的非循环双链表B）只带队头指针的循环双链表C）只带队尾指针的非循环
36、双链表D）只带队尾指针的循环单链表【解析】链队是在链表的两端进行操作，而在A中查找链表最后一个结点的时间复杂度为O（n）。15 .下列哪中数据结构常用于系统程序的作业调度（B ）A ）栈B）队列C ）链表D ）数组【解析】作业调度采用先到先服务的方式，因此最适合的数据结构为队列。3.2 填空题1 .栈是的线性表，其运算遵循_的原则.答案】（1）操作受限（或限定仅在表尾进行插入和删除操作）（2）后进先出2 .设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为1,2,3,4,5,经过 PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_23_而栈顶指针值是
37、_100CH_设栈为顺序栈，每个元素占4个字节。【解析】PUSH为入栈操作，POP为出栈操作。根据栈的性质，经过PUSH,PUSH,POP运算之后，栈中存在元素1,输出数据为2,然后经过PUSH,POP,3入栈，3出栈，然后经过PUSH,PUSH之后4,5入栈，此时出栈序列为2,3,栈中元素为1,4,5；每个元素占4个字节，所以栈顶指针的值为1000H+3*4=100CH (十六进制数)3 .循环队列的引入，目的是为了克服.答案】假溢出时大量移动数据元素。4 .队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是。【答案】先进先出5 .已知链队列的头尾指针分别是f和r,则将值x入队的操作序列是。【答案1 s=(LinkList)malloc(sizeof(LNode);s-data=x;s-next=r-next;r-next=s;as;【解析】根据队列的性质，新插入的元素永远插在队尾。6 .区分循环队列的满与空，只有两种方法，它们是和【答案】(1)牺牲一个存储单元(2)设标记