数据结构c语言版试题大全(含答案).pdf

资源描述

8、表不具备的特点是 o可随机访问任一结点I插入删除不需要移动元素I不必事先估计存储空间I所需空间与其长度成正比34、线性表的静态存储结构与顺序存储结构相比优点是 o所有的操作算法实现简单|便于随机存取|便于插入和删除|便于利用零散的存储器空间-3-35、设线性表有n个元素，以下操作中，在顺序表上实现比在链表上实现效率更高。输出第i(l=i=n)个元素值|交换第1个元素与第2个元素的值|顺序输出这n个元素的值|输出与给定值x 相等的元素在线性表中的序号36、对于一个线性表，既要求能够较快地进行插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应采用存储结构。顺序I链式I散列I索引37

16、alse3、False4、False5、False6、True7、False8、False9、True10 False11 False12、False13 False14 False15、False16、False19 True-6-数据结构复习题：绪论算法分析题1、求两个n阶矩形的乘法C=A*B,其算法如下：#define MAX 100void maxtrixmult(int,float aMAXMAX,bMAXMAX,float cMAXMAX)int ij,k；float x;for(i=l;i=n;i+)for(j=l；j=n;j+)(x=0;for(k=l;k=n;k+)x+=ai

17、k*bkj;cij=x;/)计算各语句的频度，并分析该算法的时间复杂度。2、设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。m=0;for(i=l;i=n;i+)for(j=2*l;j=n;j+)m+;3、阅读下列算法：void suan_fa(int n)(int i,j,k,s,x;for(s=0J=0;in;i+)for(j=i;jn;j+)s+;i=l;j=n;x=0;while(ij)(i+；j；x+=2;)pirntf(s=%d,x=%d,s,x);)分析算法中语句“s+;”的执行次数；分析算法中语句“x+=2;“的执行次数；-7-分析该算法的时间复杂度；假定n

18、=5,试指出执行该算法的输出结果。6、设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。int m=O,ij;for(i=l;i=n;i+)for(j=2*i;j=n;j+)m+;数据结构复习题答案：绪论算法分析题1、答：语句频度for(i=l;i=n;i+).n+1 for(j=l；j=n;j+).n(n+l)x=0;.n2for(k=l;k=n;k+).n2(n+l)x+=aik*bkj;n3cij=x;/.n2所以：f(n)n+l+n(n+l)+n2+n2(n+l)+n3+n2=2n3+4n2+2n+l=O(n3)2、答：m+n(n-l)0(n2)3分析算法中语句 s

19、+;”的执行次数:n+(n-1)+(n-2)+-+l=n(n+l)/2分析算法中语句 x+=2;的执行次数:n/2分析该算法的时间复杂度：0(n2)假定n=5,试指出执行该算法的输出结果:s=15,x=46、数据结构复习题：绪论填空题1、一个数据结构在计算机中称为存储结构。2、数据逻辑结构包括,和三种类型，树形结构和图形结构合称为。3、在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点：最后一个结点后续结点，其余每个结点有且只有个后续结点。4、在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结点:叶子结点没有结点，其余每个结点后的后续结点可以5、在图形结

20、构中，每个结点的前驱结点数和后续结点数可以。6、线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系O7、算法的5个重要特性是、输入和输出。8、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实现上就是程序 To这个断言是。9、数据结构、数据元素和数据项在计算机中的映射(或表示)分别称为存储结构、结点和数据域。这个断言-8-是 o10、下面程序段的时间复杂度是 0for(i=0;in;i+)for(j=0;jm;j+)Aij=0;IK下面程序段的时间复杂度是。i=s=0;while(sn)(i+；s+=i;)12、下面程序段的

21、时间复杂度是 os=0;for(i=0;in;i+)for(j=O;jn;j+)s+=Bij;sum=s;13、下面程序段的时间复杂度是 oi=l；while(i=n)i=i*3;14、有如下递归函数fact(n),分析其时间复杂度。int fact(int n)(if(n=l)return 1;elsereturn(n*fact(n-l);)15、指出下列各算法的时间复杂度(1)prime(int n)(int i=2;while(n%i!=0&isqrt(n)printf”是一素数”；elseprintf”不是一素数”；)suml(int n)-9-int p=l,sum=OJ;for(i

22、=l;i=n;i+)P*=i；sum+=p;)returm(sum);)sum2(int n)(int sum=0,ij;for(i=l;i=n;i+)(P=l；for(j=l；j=i；j+)P*=j；sum+=p;)return(sum);16、数据的逻辑结构是指.17、一个数据结构在计算机中的称为存储结构.18、顺序存储方法是把逻辑上存储在物理位置上_里;链式存储方法中结点间的逻辑关系是由_的，19、数据结构是指研究数据的和以及它们之间的相互关系，并对这种结构定义相应的，设计出相应的，从而确保经过这些运算后所得到的新结构是原来的结构类型.20、一个算法具有5个特性:、输入和输出。2

23、1、算法的执行时间是的函数。22、数据的逻辑结构是从逻辑上描述数据，它与数据的无关,是独立于计算机的.23、数据的逻辑结构被分为、和 4种。24、数据的存储结构被分为、和 4种。25、在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着、的联系。26、一种抽象数据类型包括和两个部分。27、从一维数组an中顺序查找出一个最大值元素的时间复杂度为,输出一个二维数组bm n中所有元素值的时间复杂度为28、在下面程序段中，s=s+p语句的执行次数为,p*可语句的执行次数为,该程序段的时间复杂度为。int i=0,s=0;while(+i=n)int p=l;for(int j=l;

24、jlink=f即可。8、在双向链表存储结构中，删除p所指的结点时需修改指针 o9、在双向链表存储结构中，删除p所指的结点的前趋结点(若存在)时需修改指针-10、根据线性表的链式存储结构，每个结点所含指针的个数，链表分为单链表和 o11、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上 o12、链表不具备的特点是 o13、不带头结点的单链表head为空的判定条件是 o14、带头结点的单链表的head为空的判定条件是 o15、带头结点的双循环表L为空表的条件是 o16、非空的循环单链表head的尾结点(由p所指向)满足。17、在循环双链表的p所指结点之前插入s所指结点的操作是。18、若某表最

25、常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用存储方式最节省运算时间。19、某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用存储方式最节省运算时间。20、需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 o21、如果最常用的操作是取第i个结点及其前驱，则采用存储方式最节省时间。22、在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 o23、在一个长度为n(n1)的单链表上，设有头和尾两个指针，执行操作与链表的长度有关。24、设线性表有n个元素，以下算法中，在顺序表上实现比在链表上实现效率更高。2

26、5、设线性表中有2n个元素，算法,在单链表上实现要比在顺序表上实现效率更高。26、与单链表相比，双链表的优点之一是 o27、如果对线性表的运算只有4种，即删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后一个元素的后面插入新元素，则最后使用 o28、如果对线性表的运算只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用 29、设有两个长度为n的单链表，结点类型相同。若以hl为表头指针的链表是非循环的，以h2为表头指针的链表是循环的，则 o30、在长度为n的上，删除第一个结点，其算法的时间复度为O(n)。31、将两个各有n个元素的有序顺序表归并成一个有序顺

27、序表，其最少的比较次数是 o32、带头结点的单链表L为空的判定条件是。-14-33、在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 o34、在一个长度为n(nl)的带头结点的单链表h上,，另设有尾指针r(指向尾结点)，执行操作与链表的长度有关。35、在一个双链表中，在*p结点之后插入结点*q的操作是 036、在一个双链表中，在*p结点之前插入*q结点的操作是 o37、在一个双链表达式，删除*p结点的操作是 o38、在一个双链表中，删除*p结点之后的一个结点的操作是 039、非空的循环单链表L的尾结点(由p所指向)满足 o40、带头结点的双循环链表L为空表的条件是

28、o41、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用存储方式最节省运算时间。42、如果对含有n(nl)个元素的线性表的运算只有4种:删除第一个元素；删除最后一个元素；在第一个元素前面插入新元素；在最后一个元素的后面插入新元素，则最好使用 o43、某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，则采用存储方式最节省运算时间。44、设有两个长度为n的单链表，结点类型相同，若以hl为头结点的链表是非循环的，以h2为头结点指针的链表是循环的，则。45、在长度麟n(nl)的上，删除第一个元素，其算法的时间复杂度为O(n)。46、元素A、B、

29、C、D依次进顺序栈后，栈顶元素是，栈底元素是 o47、经过以下栈运算后，X的值是 olnitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x);48、经过以下的栈运算后，StackEmpty(s)的值是。lnitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)49、设一个栈的输入序列为A、B、C、D,则借助一个栈所得到的输出序列不可能是 o50、若线性表最常用的运算是存取第i个元素及其前驱的值，则采用存储方式节省时间.51、链表不具备的特点是.52、在一个长度为n的顺序存储的线性表中，向第i个元素(1

31、-link;|f=nil;B-15-8、(p-rlink)-rlink)-link=p;p-rlink=(p-rlink)-rlink;|(p-llink)-rlink=p-rlink;(p-rlink)-llink=p-llink;|p-llink=(p-llink)-llink;(p-llink)-llink)-rlink=p;|(p-llink)-llink)-rlink=p;p-llink=(p-llink)-llink;B9、(p-llink)-llink)-rlink=p;p-llink=(p-llink)-llink;|(p-rlink)-rlink)-llink=p;p-rli

35、n)B34、删除单链表中的第一个元素|删除单链表中的最后一个元素|在单链表第一个元素前插入一个新元素|在单链表最后一个元素后插入一个新元素 B-16-35、q-prior=p;p-next=q;p-next-prior=q;q-next=p-next;|q-next=p-next;p-next-prior=q;p-next=q;q-prior=p;|p-next=q;q-prior=p;q-next=p-next;p-next-prior=q;|p-next-prior=q;q-next=p-next;q-prior=p;p-next=q;B36、p-prior=q;q-next=p;p-p

36、rior-next=q;q-prior=p-prior;|q-prior=p-prior;p-prior-next=q;q-next=p;p-prior=q-next;|q-next=p;p-next=q;q-prior-next=q;q-next=p;|p-prior-next=q;q-next=p;q-prior=p-prior;p-prior=q;D37、p-prior-nexxt=p-next;p-next-prior=p-prior;|p-prior=p-prior-prior;p-prior-prior=p;|p-next-prior=p;p-next=p-next-next;|p

39、结点指针r的带头结点h的循环单链表|只有头结点h的循环单链表 A46、A|B|C|D D|A47 a|b|l|0 A48 a|b|l|0 C49、A、B、C、D|D、C、B、A|A、C、D、B|D、A、B、C D50、单链表|双链表|单循环链表|顺序表 D51、可随机访问任一结点|插入删除不需要移动元素|不必事先估计存储空间|所需空间与其长度成正比A52、n-i|n-i+l|n-i-l|l B53、n-l|n-i+l|n-i-l|l A54、n|n/2|(n+l)/2|(n-l)/2 C57 p=q-next;p-next=q-next;|p=q-next;q-next=p;|p=q-next

40、;q-next=p-next;|q-next=q-next-next;q-next=q;C数据结构复习题：线性表判断题1、顺序存储的线性表可以随机存取。-17-2、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此，是属于同一数据对象。3、在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素。4、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。5、链表的每个结点中，都恰好包含一个指针。6、线性表中每个元素都有一个直接前驱和直接后继。7、线性表中所有元素的排列顺序必须由小到大或由大到小。8、静态

41、链表的存储空间在运算中可以改变大小。9、静态链表既有顺序存储结构的优点，又有动态链表的优点。所以，它存取表中的第i个元素的时间与i 无关。10、静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加。1K静态链表与动态链表的插入、删除操作类似，不需做元素的移动。12、线性表的顺序存储结构优于链式存储结构。15、在双链表中，可以从任一结点开始沿同一方向查找任何其他结点。数据结构复习题答案：线性表判断题1 True2、True3、False4、False5、False6、False7、False8、False9、False10 True11、True12、False15、False数据结构

42、复习题：线性表算法分析题1、己知一个顺序表L,其中的元素按值非递减有序排列,设计一个算法插入一个元素x后保持该顺序表仍按递减有序排列。要求算法的空间复杂度为0(1)。2、设计一个算法从顺序表L中删除所有值为X的元素。要求算法的空间复杂度为0(1)。3、从顺序表L中删除重复的元素，并使剩余元素间的相应次序保持不变.要求本算法的空间复杂记度为0(1)。4、有一个单链表(不同结点的数据域值可能相同)，其头指针为head,设计一个算法计算数据域为x的结点个数。5、己知线性表元素递增有序,并以带头结点的单链表作存储结构，设计一个高效算法，删除表中所有值大于 mink且小于maxk的元素(若表中存在这

43、样的元素)。并分析所写算法的时间复杂度。-18-6、设计一个在带头结点的单链表中删除一个最小值结点的高效算法。7、有一个不带头结点的单链表L(至少有1人结点)，其头指针为head,设计一个算法将L逆置,即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。8、用单链表表示集合，设计一个算法求两个集合的差。要求不破坏原有的结点。9、用单链表表示集合，设计一个算法求两个集合的并。要求不破坏原有的结点。10、设计一个算法，将一个头结点指针为a的单链表A分解成两个单链表A和B,其头结点指针分别为a和b,使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为倒数

44、的元素，且保持原来的相对顺序。1K有一个单链表，其结点的元素值以递增有序排列，设计一个算法删除该单链表中多余的元素值相同的结点。12、己知两个存放整数的有序单链表(己按整数从小至大的顺序排序)，指针L1和L2分别指向这两个单链表的头结点。设计一个算法，将L1和L2合并成一个单链表,且新的链表仍按整数由小到大的顺序排列，新的单链表的结点由L1和L2的结点构成。要求合并后的单链表利用原来单链表的存储空间。13、设计一个算法，将线性表1b连接到la之后,要求其时间复杂度为0(1),占用的辅助空间尽量小。描述所用的结构。14、设指针p指向双链表中的结点X,指针f指向将要插入的新结点Y,Y要插入

45、在结点X之后,写出指针需要修改的有关步骤。15有一个循环双链表,每个结点由两个指针(prior和next)以及关键字(data)构成,p指向其中某一结点，设计一个算法从该循环双链表中删除p所指的结点。16、设有一个循环双链表，其中有一结点的指针为p,设计一个算法将p与其后续结点进行交换。19、设A和B是两个单链表(带头结点)，其表中元素递增有序。设计一个算法将A和B归并成一个按元素值递增有序的单链表C,要求辅助空晨为0(1),并分析算法的时间复杂度。数据结构复习题答案：线性表算法分析题1、答：void insert(sqlist&L,ElemType x)(int i=0J;while(

46、iL.Length&L.datai=i;j-)L.dataj+l=L.dataj;L.datai=x;L.Length+;)2、void delnode(SqList&A,ElemType item)(int k=0,i=0;while(inext-data=x)n+;p=p-.next;)return n;)5、void Delnodes(LinkList*&L,日emType mink,日emType maxk)(LinkList*p=head-next;While(p!=null&p-datanext;q=p；求值域刚好minwhile(q!=null&q-datamaxk)求值域刚好

47、next;r-next=q-next;while(r!=q)(r=p-next;free(p);P=r；)free(q);)6、void Dels(LinkList*&head)-20-p=head,q=head-next;while(q-next!=null)if(p-next-dataq-next-data)p=q;q=q-next;p-next=p-next-next;)7、void Reverse(LinkList*&head)(p=head;q=p-next;if(q=null)return(p);p-next=null;if(q-next=null)q指向p的后继结点，仅为当前结点

48、仅有一个结点原链表的首结点位新链表的尾结点仅有两个结点q-next=p;return(q);)r=q-next;while(r-next!=null)q=r;r=r-next;(q-next=p;p=q;实现逆置)q-next=p;return(r);)8、Typedef Elemtype int;Typedef struct Lnode(Elemtype data;Struct LNode*next;Lnode,*LinkList;#include LinkList creatlist()-21-建立单链表LinkList head,r,s;ElemType x;head=(LinkList

49、)malloc(sizeof(LNode);建立单链表头结点r=head;printf(输入系列整数，。标志结束n”)；scanf(&d,&x);while(x)/x=0则退出while循环s=(LinkList)mslloc(sizeof(LNode);s-data=x;r-next=s;r=s;scanf(%d,&x);)/whiler-next=NULL;s=head;删除头结点head=head-next;free(s);return(head);)status ListFind(LinkList L,Elemtype e)查找元素eLinkList p;P=L;while(p&p-d

50、ata!=e)p=p-next;lf(p)return FALSE;else return TRUE;)void Lis9、Typedef 日emtype int;Typedef struct Lnode(Elemtype data;Struct LNode*next;Lnode,*LinkList;void MergeList(LinkList Ha,LinkList Hb,LinkList&Hc)(LinkList p,q,r,s;Hc=(LinkList)malloc(sizeof(Lnode);-22-r=Hc;p=Ha;q=Hb;while(p&q)(s=(LinkList)mall

展开阅读全文