数据结构习题集及答案

《数据结构习题集及答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一章一、填空题1数据元素是数据的基本单位,..数据项….…是具有独立含义的最小标识单位。3数据Z间的关系(逻辑结构)有四种集合、线性结构、树形结构、网状结构或图状结构，可分为两大类。4数据的存储结构包括..顺序存储结构..链式存储结构二、问答题1.什么是数据结构?什么是数据类型？答：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。2.叙述算法的定义与特性。答：算法是对待定问题求解步骤的一种描述，他是指令的有限序

2、列，其中每一条指令表示一个或多个操作。一个算法具有以下5个重要特性：1)、有穷性2)、确定性3)、可行性4)、输入5)、输出3.叙述算法的时间复杂度。答：算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的吋量度，记作T(n)=0(f(n))他表示随着问题规模n的增大，算法执行时间增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。三、判断题(在各题后填写“J”或“X”)1.线性结构只能用顺序结构來存放，非线性结构只能用非顺序结构來存放。(X)2.下列几种数量级从小到大的排列顺序为

3、：0(1)、O(logn)、0(n)、O(nlogn)、O(n2)、0(n3)、0(2n)。(V)四、1.计算机执行下面的语句时，语句s的执行频度(重复执行的次数)为。FOR(i=l；i=i;j—)s;2.有下列运行时间函数：(1)T,(n)=1000;(2)T2(n)=n2+1000n;(3)T3(n)=3n3+100n2+n+l;分别写出相应的大0表示的运算时间。(1)(2)(3)3.设n为正整数，利用大O记号，将该程序段的执行时间表示为n的函数，则下列程序段的时间复杂度可

4、表示为(1)(0(n.))(2)(0(n2))1)floatsuml(intn){/*计算1!+2!+…+n!*/p=l;suml=O;for(i=l;i<=n;++i){p二p*i;suml二suml+p}}/*suml*/(2)floatsum2(intn){/*计算1!+2!+・・・+n!*/sum2=0;for(i=l;iUn;++i){p=l；for(j=l;j〈=i;++j)p二p*j;sum2=sum2+p;}}/*sum2*/第二章—、判断1.线性表在顺序存储吋，逻辑上相邻的元素未必在存储的物理位置

5、次序上相邻。(X)1.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。(X)二、填空1.在单链表中，指针P所指结点为最后一个结点的条件是p->next二NULL。2.在单链的循环链表中，指针P所指结点为最后一个结点的条件是p->next二头指针。三、选择B・0(1)A.O(n)1.、在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为(B)C.0(n2)D.O(log2n)2.线性链表不具有的特点是(A)。A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素3.线性表采用链式存储

6、时，其地址AC4、D.所需空间与线性表长度成正比)。D一定是不连续的连续与否均可以.必须是连续的B部分地址必须是连续的D下列哪一个程序片段是在链表中间插入一个结点。(假设新结点为NEW,欲插入在Pointer结点之后)B)ANEW->ncxt=PointcrBNEW->ncxt=Pointcr->ncxtPointer=NEWCPointer->next=NEW->nextPointer->next=NEWD以上皆非NEW->next=Pointer5.在单链表中,增加头结点的目的是有一结点B.标志表中首结点位置A

7、.使单链表至少C.方便运算的实现D.说明单链表是线性表的链式存储实现6.线性表L在情况下适用于使用链式结构实现。(B)(A)需经常修改L中的结点值(B)需不断对L进行删除插入(C)L中含有大量的结点(D)L中结点结构复杂7、向一个有127个元素原顺序表中插入一个新元素并保存原來顺序不变，平均要移动(B)个元素。A、8B、63.5C、63D、7三、算法设计1设顺序表L中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。1.StatusInsert_SqList(SqList&va,in

8、tx)〃把x插入递增有序表va中{if(va.lcngth+l>va.listsizc)returnERROR;va」cngth++;fbr(i=va1;va.elem[i]>x&&i>=0;i—)va.elem[i+l]=va.elem[i];va.elem[i4l]=x;returnOK;}//Insert_SqList2分别写出算法将单链表和顺序表就地