数据结构各章节试题

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

1、第一章一、填空题1.........数据元素.......是数据的基本单位，....数据项...是具有独立含义的最小标识单位。3数据之间的关系（逻辑结构）有四种.....集合.....、.............线性结构..........、............树形结构...........、...........网状结构............，可分为.........顺序映像........、.......非顺序映像............两大类。4数据的存储结构包括.........顺序存储结构........

2、......、..........链式存储结构.................。.二、问答题1.什么是数据结构?什么是数据类型?数据结构是相互之间存在一种或多种特定关系的数据元素的集合，数据类型是一个值的集合和定义，在这个值集上的一组操作的总称。2.叙述算法的定义与特性。算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。特性：有穷性，确定性，可行性，输入，输出。3.        叙述算法的时间复杂度。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算法

3、的时间量度记作：T（n）=0（f（n）），它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。三、判断题（在各题后填写“√”或“×”）1.        线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（  错）2．下列几种数量级从小到大的排列顺序为：O(1)、O(logn)、O(n)、O(nlogn)、O(n2)、O(n3)、O(2n)。（对）四、算法分析1．计算机执行下面的语句时，语句s的执行频度（重复执行的次数）为n（n+1）/2-3FOR

4、(i=l；i=i;j--)s;2．有下列运行时间函数：（1）T1(n)=1000;（2）T2(n)=n2+1000n;（3）T3(n)=3n3+100n2+n+1;分别写出相应的大O表示的运算时间。（1）0（1）.（2）0（n二次方），（3）0（n三次方）3．设n为正整数，利用大O记号，将该程序段的执行时间表示为n的函数，则下列程序段的时间复杂度可表示为（1）0（n）（2）0（n二次方）1)floatsum1(intn){   /*计算1！+2！+…+n!*/   p=1;sum1=

5、0;   for(i=1;i<=n;++i){      p=p*i;sum1=sum1+p      }}/*sum1*/ (2)floatsum2(intn){    /*计算1！+2！+…+n!*/sum2=0;   for(i=1;i<=n;++i){     p=1;     for(j=1;j<=i;++j)p=p*j;     sum2=sum2+p;     }  }/*sum2*/3.n是描述问题规模的非负整数规模，下面程序片段的时间复杂度是0。(2011)i=2；WHILE（i

6、i=i*2;第二章一、判断1.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（错）2.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（错）二、填空1．在单链表中，指针p所指结点为最后一个结点的条件是P→next==null。2．在单链的循环链表中，指针p所指结点为最后一个结点的条件是P→next==head。三、选择1.、在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（B）A．O(n)B．O(1)C．O(n2)D．O(log2n)2.线性链表不具有的特点是（C）。A．随机访问

7、B．不必事先估计所需存储空间大小C．插入与删除时不必移动元素D．所需空间与线性表长度成正比3.线性表采用链式存储时，其地址（D）。A必须是连续的B一定是不连续的C部分地址必须是连续的D连续与否均可以.4、下列哪一个程序片段是在链表中间插入一个结点。（假设新结点为NEW，欲插入在Pointer结点之后）(B).ANEW->next=PointerBNEW->next=Pointer->nextPointer=NEWPointer->next=NEWCPointer->next=NEW->nextD以上皆非NEW->next

8、=Pointer5.在单链表中,增加头结点的目的是（C）A.使单链表至少有一结点B.标志表中首结点位置C.方便运算的实现D.说明单链表是线性表的链式存储实现6．线性表Ｌ在情况下适用于使用链式结构实现。（B）（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂7、向一个