数据结构课后题new

《数据结构课后题new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章一、填空题1_____是数据的基本单位，.........是具有独立含义的最小标识单位。3数据之间的关系（逻辑结构）有四种——、——、——、——。4数据的存储结构包括.......................、...........................二、问答题1.什么是数据结构?什么是数据类型?2.叙述算法的定义与特性。3.        叙述算法的时间复杂度。三、判断题（在各题后填写“√”或“×”）1.        线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（  ）2．下

2、列几种数量级从小到大的排列顺序为：O(1)、O(logn)、O(n)、O(nlogn)、O(n2)、O(n3)、O(2n)。（）四、设n为正整数，利用大O记号，将该程序段的执行时间表示为n的函数，则下列程序段的时间复杂度可表示为（1）(....)（2）(....)1)floatsum1(intn){   /*计算1！+2！+…+n!*/   p=1;sum1=0;   for(i=1;i<=n;++i){      p=p*i;sum1=sum1+p      }}/*sum1*/ (2)floatsum2(intn){

3、    /*计算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*/第二章一、判断1.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（）2.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（）二、填空1．在单链表中，指针p所指结点为最后一个结点的条件是。2．在单链的循环链表中，指针p所指结点为最后一个结点的条件是。三、选择1

4、.、在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（）A．O(n)B．O(1)C．O(n2)D．O(log2n)2.线性链表不具有的特点是（）。12A．随机访问B．不必事先估计所需存储空间大小C．插入与删除时不必移动元素D．所需空间与线性表长度成正比3.线性表采用链式存储时，其地址（）。A必须是连续的B一定是不连续的C部分地址必须是连续的D连续与否均可以.4、下列哪一个程序片段是在链表中间插入一个结点。（假设新结点为NEW，欲插入在Pointer结点之后）ANEW->next=PointerBNEW->ne

5、xt=Pointer->nextPointer=NEWPointer->next=NEWCPointer->next=NEW->nextD以上皆非NEW->next=Pointer5.在单链表中,增加头结点的目的是（）A.使单链表至少有一结点B.标志表中首结点位置C.方便运算的实现D.说明单链表是线性表的链式存储实现6．线性表Ｌ在情况下适用于使用链式结构实现。（）（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂7、向一个有127个元素原顺序表中插入一个新元素并保存原来

6、顺序不变，平均要移动（）个元素。A、8B、63.5C、63D、7三、算法设计1设顺序表L中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。2分别写出算法将单链表和顺序表就地逆置（用尽可能少的附加空间在原存储出空间内将将线性表a1,a2,a3,…an逆置为an…a3,a2,a1）。*3删除元素递增排列的链表L中所有值相同的元素。第三章1.        按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：   ⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？⑵

7、如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。2.        设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4步操作：（1）      输出队首元素；（2）      把队首元素值插入到队尾；（3）      删除队首元素；（4）      再次删除队首元素。直到队列成为空队列为止，得到输出序列：（1）      A、C、E、C、C              （2）A、C、E（3

8、） A、C、E、C、C、C          （4）A、C、E、C3.        给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？124.        按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：         A－B