数据结构试题库

《数据结构》试题库1、第一章绪论试题2、第二章线性表试题3、第三章栈和队列试题4、第四章串试题5、第五章数组与广义表试题6、第六章树和二叉树试题7、第七章图试题8、第九章查找试题9、第十章内部排序试题1、第一章绪论试题1.1简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。1.2试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。1.3常用的存储表示方法有哪几种?1.4设三个函数f,g,h分别为f(n)=100n^3+n^2+1000,g(n)=25n^3+5000n^2,h(n)=n^1.5+5000nlgn请判断下列关系是否成立：(1)f(n)=O(g(n))(2)g(n)=O(f(n))(3)h(n)=O(n^1.5)(4)h(n)=O(nlgn)1.5设有两个算法在同一机器上运行，其执行时间分别为100n^2和2^n,要使前者快于后者，n至少要多大?1.6设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。(1)i=1;k=0while(in){k=k+10*i;i++;}◆T(n)=n-1∴T(n)=O(n)◇该函数是按线性阶递增的(2)i=0;k=0;do{k=k+10*i;i++;}while(in);◆T(n)=n∴T(n)=O(n)◇这也是线性阶递增的(3)i=1;j=0;while(i+j=n){if(ij)j++;elsei++;}◆T(n)=n/2∴T(n)=O(n)◇虽然时间函数是n/2,但其数量级仍是按线性阶递增的。(4)x=n;//n1while(x=(y+1)*(y+1))y++;◆T(n)=n1/2∴T(n)=O(n1/2)◇最坏的情况是y=0，那么循环的次数是n1/2次，这是一个按平方根阶递增的函数。(5)x=91;y=100;while(y0)if(x100){x=x-10;y--;}elsex++;◆T(n)=O(1)◇这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有?没。这段程序的运行是和n无关的，就算它再循环一万年，也不管他，只是一个常数阶的函数。1.7算法的时间复杂度仅与问题的规模相关吗?1.8按增长率由小至大的顺序排列下列各函数：2^100,(2/3)^n，(3/2)^n，n^n,,n!，2^n，lgn,n^lgn,n^(3/2)1.9有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大O记号表示。例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n),T2(n)=2.0nlgn-2n=2.0lgn+O(n),这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣?函数大O表示(1)T1(n)=5n^2-3n+60lgn5n^2+O(n)(2)T2(n)=3n^2+1000n+3lgn3n^2+O(n)(3)T3(n)=8n^2+3lgn8n^2+O(lgn)(4)T4(n)=1.5n^2+6000nlgn1.5n^2+O(nlgn)1.10试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别？1.11试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。1.12设n为正整数。试确定下列各程序段中前置以记号@语句的频度。（1）i=1;k=0;While(i=n-1){@k+=10*i;i++;}（2）i=1;k=0;Do{@k+=10*ki;i++;}while(i=n-1);（3）i=1;k=0;While(i=n-1){i++;@k+=10*i;}（4）k=0;For(i=1;i=n;i++){For(j=i;j=n;j++)@k++;}（5）i=1;j=0;While(i+j=n){If（ij）j++;Elsei++;}（6）x=91;y=100;While(y0){@if(x100){x-=10;y--;}Elsex++;}1.13按增长率由小到大的顺序排列下列各函数：2100,(3/2)n,(2/3)n,(4/3)n,nn,n3/2,n2/3,n,n!,n,log2n,n/log2n,log22n,log2(log2n),nlog2n,nlog2n1.14已知有实现同一功能的两个算法，其时间复杂度分别为O(2n)和O(n10)，假设现实计算机可持续运算的时间为107秒（100多天），又每秒可执行基本操作（根据这些操作来估算算法时间复杂度）105次。试问在此条件下，这两个算法可解问题的规模（即n值的范围）各为多少？哪个算法更适宜？请说明理由。1.15设有以下三个函数：f(n)=21n4+n2+1000,g(n)=15n4+500n3,h(n)=5000n3.5+nlogn请判断以下断言正确与否：(1)f(n)是O(g(n))(2)h(n)是O(f(n))(3)g(n)是O(h(n)(4)h(n)是O(n3.5)(5)h(n)是O(nlogn)1.16试设定若干n值，比较两函数n2和50nlog2n的增长趋势，并确定n在什么范围内，函数n2的值大于50nlog2n的值。1.17试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值。1.18已知K阶裴波那契序列的定义为f0=0,f10,…,fk-2=0,fk-1=1,fn=fn-1+fn-2+fn-3+fn-4+…+fn-k,n=k,k+1,…试编写求K阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。1.19假设有A，B，C，D，E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为项目名称性别校名成绩得分编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。1.20试编写算法，计算i!2i(i=0,1,…,n-1)的值并分别存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大值为MAXINT，则当narrsize或对某个k(10nk)使k!2kMAXINT时，应按出错处理。注意选择你认为较好的出错处理方法。1.21试编写算法求一元多项式Pn(x)=iniixa0的值Pn(x0)，注意选择你认为较好的输入和输出方法。本题的输入为ai(i=0,1,…,n),x0和n，输出为Pn(x0)。2、第二章线性表试题2.1试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。2.2何时选用顺序表、何时选用链表作为线性表的存储结构为宜?2.3为什么在单循环链表中设置尾指针比设置头指针更好?2.4在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?2.5下述算法的功能是什么?2.6试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,...an-1)就地逆置的操作，所谓就地指辅助空间应为O(1)。2.7设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。2.8设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。2.9写一算法在单链表上实现线性表的ListLength(L)运算。2.10设A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。2.11写一算法将顺序表（单链表）中值重复的结点删除，使所得的结果表中各结点值均不相同。2.12填空题（1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。（2）顺序表种逻辑上相邻的元素的屋里位置紧邻。单链表种逻辑上相邻的元素的物理位置紧邻。（3）在单链表种，除了首元结点外，任一结点的存储位置由指示。（4）在单链表种设置头结点的作用是。2.13已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.在P结点后插入S结点的语句序列是。b.在P结点前插入S结点的语句序列是。c.在表首插入S结点的语句序列是。d.在表尾插入S结点的语句序列是。（1）P-next=S;（2）P-next=P-next-next;（3）P-next=S-next;（4）S-next=P-next;（5）S-next=L;（6）S-next=NULL;（7）Q=P;（8）while(P-next!=Q)P=P-next;（9）while(P-next!=NULL)P=P-next;（10）P=Q;（11）P=L;（12）L=S;（13）L=P;2.14已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.删除P结点的直接后继结点的语句序列是。b.删除P结点的直接前驱结点的语句序列是。c.删除P结点的语句序列是。d.删除首元结点的语句序列是。e.删除尾元结点的语句序列是。(1)P=P-next;(2)P-next=P;(3)P-next=P-next-next;(4)P=P-next-next;(5)while(P!=NULL)P=P-next;(6)while(Q-next!=NULL){P＝Q；Q＝Q-next;}(7)while(P-next!=Q)P=P-next;(8)while(P-next-next!=Q)P=P-next;(9)while(P-next-next!=NULL)P=P-next;(10)Q=P;(11)Q=P-next;(12)P=L;(13)L=L-next;(14)free(Q);2.15设A=(a1,…,am)和B=(b1,…,bn)均为顺序表，A/和B/分别为A和B除去最大共同前缀后的子表。若A/＝B/＝空表，则A＝B；若A/＝空表，而B/空表，或者两者均不为空表，且A/的首元小于B/的首元，则AB；否则AB。试写出一个比较A,B大小的算法。（请注意：在算法中，不要破坏原表A和B，也不一定要先求得A/和B/才进行比较。）2.16试写出一算法在带头结点得单链表结构上实现线性表操作LOCATE（L，X）。2.17已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。2.18试写一算法，在无头结点的动态单链表上实现线性表操作INSERT（L,i,b），并和在带头结点的动态单链表上实现相同操作的算法进行比较。2.19试写一算法，在无头结点的单链表上实现线性表操作DELETE(L,i)。2.20已知线性表中的元素值以值递增有序排列，并以单链表作存储结构。试写高效的算法，删除表中所有值大于mink且小于maxk的元素，同时释放被删结点空间。2.21假设有两个元素依值递增有序排列的线性表A和B（表中可能存在值相同的元素），构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素也依值递增有序排列，并且各不相同，现要求利用A表空间存放表C。试编写求得表C的算法。2.22假设有两个元素依值递增有序排列的单链表A和B（表中可能存在值相同的元素），构成一个单链表C，其元素为A和B中元素的交集，且表C中的元素也依值递增有序排列，现要求利用A表空间存放表C，并释放A表中的无用结点空间。试编写求得表C的算法。2.23已知A，B和C为三个递增有序的线性表，现要求对A表作如下操作：删除那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复