下载文档原格式
《数据结构》第二版严蔚敏课后习题作业参考答案(1-7章)【第一章绪论】1. 数据结构是计算机科学中的重要基础知识，它研究的是如何组织和存储数据，以及如何通过高效的算法进行数据的操作和处理。
本章主要介绍了数据结构的基本概念和发展历程。
【第二章线性表】1. 线性表是由一组数据元素组成的数据结构，它的特点是元素之间存在着一对一的线性关系。
本章主要介绍了线性表的顺序存储结构和链式存储结构，以及它们的操作和应用。
【第三章栈与队列】1. 栈是一种特殊的线性表，它的特点是只能在表的一端进行插入和删除操作。
本章主要介绍了栈的顺序存储结构和链式存储结构，以及栈的应用场景。
2. 队列也是一种特殊的线性表，它的特点是只能在表的一端进行插入操作，而在另一端进行删除操作。
本章主要介绍了队列的顺序存储结构和链式存储结构，以及队列的应用场景。
【第四章串】1. 串是由零个或多个字符组成的有限序列，它是一种线性表的特例。
本章主要介绍了串的存储结构和基本操作，以及串的模式匹配算法。
【第五章数组与广义表】1. 数组是一种线性表的顺序存储结构，它的特点是所有元素都具有相同数据类型。
本章主要介绍了一维数组和多维数组的存储结构和基本操作，以及广义表的概念和表示方法。
【第六章树与二叉树】1. 树是一种非线性的数据结构，它的特点是一个节点可以有多个子节点。
本章主要介绍了树的基本概念和属性，以及树的存储结构和遍历算法。
2. 二叉树是一种特殊的树，它的每个节点最多只有两个子节点。
本章主要介绍了二叉树的存储结构和遍历算法，以及一些特殊的二叉树。
【第七章图】1. 图是一种非线性的数据结构，它由顶点集合和边集合组成。
本章主要介绍了图的基本概念和属性，以及图的存储结构和遍历算法。
【总结】1. 数据结构是计算机科学中非常重要的一门基础课程，它关注的是如何高效地组织和存储数据，以及如何通过算法进行数据的操作和处理。
本文对《数据结构》第二版严蔚敏的课后习题作业提供了参考答案，涵盖了第1-7章的内容。
《数据结构》作业习题班级：学号：姓名：习题一绪论1、数据结构主要研究的三个内容为、以及定义在该结构上的。
2、数据结构从逻辑结构上可分为线性结构与非线性结构，其中树、图属于。
3、数据结构被形式地定义为（D，R），其中D是的有限集，R是D上的有限集。
4、程序作用是利用swap函数，实现main函数中变量a与b的值的交换。
填写空缺使代码完整。
void swap( ) { int temp;;;; } int main( ){ int a=7,b=11;printf("a=%d,b=%d\n",a,b);swap( );printf("a=%d,b=%d\n",a,b); }5、函数triangleArea的作用是：根据三角形的三条边a、b、c，求三角形的面积。
求三角形面积的公式为)cs)(bs)(as(s---，其中s=(a+b+c)/2。
要求函数返回值类型定义为状态类型（Status 类型），当给定的三条边不能构成三角形时，函数返回ERROR；否则函数返回OK，并利用引用类型参数返回三角形的面积。
填写空缺使代码完整。
triangleArea( double a, double b, double c, area) { double s;if(a+b<=c||a+c<=b||b+c<=a) return ;else{ s=(a+b+c)/2;=sqrt(s*(s-a)*(s-b)*(s-c));return ;}6、设有定义如下：typedef struct stuInfo{int num;char name[20];char sex;struct stuInfo *next;} stuType;（1）利用指针变量stus,实现一个能容纳40个stuType类型元素动态数组。
实现该功能正确的代码为：stuType *stus;stus=( )malloc( );（2）从内存中分配两个stuType类型的结点空间，其指针分别为p、q。
数据结构练习题1、在数据结构中，从逻辑上可以把数据结构分成A、动态结构和静态结构B、紧凑结构和非紧凑结构B、线性结构和非线性结构D、内部结构和外部结构2、线性表的顺序存储结构是一种_____的结构，线性表的链式存储结构是一种____的存储结构A、随机存取B、顺序存取C、索引存储D、散列存取3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址____A、必须是连续的B、部分地址必须是连续的B、一定是不连续的D、连续或不连续都可以4、在下列叙述中，正确的是____A、线性表的顺序存储结构优于链表存储结构B、二维数组是其数据元素为线性表的线性表C、栈的操作方式是先进先出D、队列的操作方式是先进后出5、一个顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是___A、110B、108C、100D、1206、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是____A、edcbaB、decbaC、dceabD、abcde7、一个栈的入队序列是1，2，3，4，则队列的输出序列是____A、4，3，2，1B、1，2，3，4C、1，4，3，2D、3，2，4，18、判定一个栈ST空的(最多元素为m0)为空的条件是_____A、ST->top!=0B、ST->top= =0C、S T->top!=m0D、ST->top= =m09、判定一个栈(最多元素为m0)为满的条件是_____A、ST->top!=0B、ST->top= =0D、ST->top!=m0 D、ST->top= =m010、判定一个队列QU(最多元素为m0)为空的条件是_____A、QU->rear-QU->front= =m0B、Q U->rear-QU->front-1= =m0C、Q U->front= =QU->rearD、QU->front= =QU->rear+111、判定一个队列QU(最多元素为m0)为空的条件是_____A、QU->rear-QU->front= =m0B、QU->rear-QU->front-1= =m0C、QU->front= =QU->rearD、QU->front= =QU->rear+112、判定一个循环队列QU(最多元素为m0)为空的条件是_____A、QU->rear-QU->front= =m0B、QU->rear-QU->front-1= =m0C、QU->front= =（QU->rear+1）%m0D、QU->front! =（QU->rear+1）%m013、判定一个循环队列QU(最多元素为m0)为满的条件是_____A 、QU->rear -QU->front= =m0B 、QU->rear -QU->front -1= =m0C 、QU->front= =（QU->rear+1）%m0D 、QU->front! =（QU->rear+1）%m014、循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是front 和rear ，则当前队列中的元素个数是_____A 、（rear -front+m ）%mB 、rear -front+1C 、rear -front-1E 、 rear -front15、如下图所示的4棵二叉树中，____不是完全二叉树。
大工15秋《数据结构》在线作业1满分答案大工15秋《数据结构》在线作业1一单选题1.广义表((e))的表头是（）。
A. eB. (e)C. ()D. (())正确答案：B2.在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（）个指针域的值。
A. 1B. 2C. 3D. 4正确答案：B3.在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）。
A. (n+1)/2B. n/2C. nD. n+1正确答案：C4.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）。
A. head==NULLB. head→next==NULLC. head→next==headD. head!=NULL正确答案：B5.一个顺序栈S，元素a，b，c，d，e依次进栈，如果5个元素的出栈顺序为b，e，d，c，a，则顺序栈的容量至少应为（）。
A. 2B. 3C. 4D. 5正确答案：C6.在表长为n的顺序表中,若在每个位置插入数据元素的概率相等，插入一个数据元素平均需要移动（）个数据元素。
A. (n-1)/2B. n/2C. n-1D. n正确答案：B7.广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（）。
A. cB. b，cC.（b，c）D.（（b，c））正确答案：D8.表达式a*(b+c)-d的后缀表达式是（）。
A. abcd*+-B. abc+*d-C. abc*+d-D. -+*abcd精确谜底：B9.在一个单链表中，删除*p结点之后的一个结点的操作是（）。
A. p->next=p;B. p->next->next=p->next;C. p->next->next=p;D. p->next=p->next->next;精确谜底：D10.最大容量为n的轮回行列，队尾指针是rear，队头是front，则队空的条件是（）。
数据结构作业题及答案第一章绪论1、简述下列概念：数据、数据元素、数据结构、逻辑结构、存储结构、线性结构、非线性结构。
数据：指能够被计算机识别、存储和加工处理的信息载体。
数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。
数据元素有时可以由若干数据项组成。
数据结构：指的是数据之间的相互关系，即数据的组织形式。
一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。
逻辑结构：指各数据元素之间的逻辑关系。
存储结构：就是数据的逻辑结构用计算机语言的实现。
线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
线性表就是一个典型的线性结构。
非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。
2、常用的存储表示方法有哪几种?顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。
由此得到的存储表示称为顺序存储结构。
链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。
由此得到的存储表示称为链式存储结构。
索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。
3、求解下列算法的时间复杂度(1)i=1;k=0 while(i<n){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(i<n);T(n)=n∴T(n)=O(n)这也是线性阶递增的(3)i=1;j=0;while(i+j<=n) {if(i<j)j++; else i++;}T(n)=n/2∴T(n)=O(n)虽然时间函数是n/2,但其数量级仍是按线性阶递增的。
数据结构第一次作业一、单选题 (共100.00分)1. 已知栈S为空，数据1、2、3、4依次逐个进入栈S，则栈顶数据为（）A. 1B. 2C. 3D. 4正确答案：D2. 栈的最大特点是（）A. 先进先出B. 后进先出C. 无限递归D. 有限递归正确答案：B3. 队列的最大特点是（）A. 先进先出B. 后进先出C. 无限递归D. 有限递归正确答案：A4. 已知栈包含10元素，其中存放在栈底是第1号元素，则第10号元素可以通过（）进行访问A. 栈底B. 栈中C. 栈尾D. 栈顶正确答案：D5. 以下结构中，哪一个是属于物理结构（）A. 栈B. 队列C. 链队列D. 线性表正确答案：C6. 使用长度为10的数组实现循环队列，则该队列最多存储数据个数为（）A. 1B. 9C. 11.D.5正确答案：B7. 已知顺序表包含1000个数据，现在第88号位置插入新的数据，需要移动的数据个数为（）A. 88B. 87C. 912D. 913正确答案：D8. 若线性表最常用的操作是存取第i个元素及其后继的值,则最节省操作时间的存储结构是（）A. 单链表B. 双链表C. 单循环链表D. 顺序表正确答案：D9. 以下结构中，哪一个是属于物理结构（）A. 线性表B. 栈C. 单链表D. 队列正确答案：C10. 已知顺序表包含100个数据，现在要删除第99号位置的数据，需要移动的数据个数为（）A. 99B. 100C. 1D. 2正确答案：C已知指针p指向单链表L的某个结点，判断p指向的结点是尾结点的条件是（）A. if (p->next>p)B. if (p->next==NULL)D. if (p->data==0)正确答案：B12. 以下描述哪个是正确的（）A. 线性表的数据元素的存储位置一定是连续的B. 顺序表的数据元素的存储位置一定是连续的C. 链表的数据元素的存储位置一定不是连续的D. 线性表的数据元素的存储位置一定不是连续的正确答案：B已知顺序表包含100个数据，先在第15号位置插入1个新数据，接着删除第3号位置的数据，需要移动的数据总个数为（）A. 18B. 84C. 184D. 188正确答案：C在数据结构概念中，数据的基本单位是（）A. 数据段B. 数据项C. 数据表D. 数据元素D在数据结构概念中，结构是描述（）A. 数据项的类型B. 数据元素之间的关系C. 数据成员的先后顺序D. 数据对象的取值范围正确答案：B在算法设计中，要求算法便于理解和修改是属于算法要求的（）A. 正确性B. 可读性C. 健壮性D. 效率高正确答案：B以下关于算法的描述，哪个是正确的（）A. 算法可以没有输入B. 算法可以包含无限个执行步骤C. 算法可以没有输出D. 算法的每个步骤允许带有歧义的正确答案：抽象数据类型ADT通过三方面描述，包括数据关系、数据操作和（）A. 数据对象B. 数据来源C. 数据范围D. 数据判断正确答案：A设n为问题规模，以下程序的时间复杂度为（）for (i=1; i<=10000; i++) for (j=1; j<=n; j++) a = a + 1;A. O(1)B. O(n)C. O(10000n)D. O(n2)正确答案：B20.设n为问题规模，以下程序的时间复杂度为（） for (i=1; i< POW（2, n）; i++) //POW(x, y)函数表示x的y次幂a = a+100;A. O(n)B. O(2n)C. O(n!)D. O(2n)正确答案：D。
数据结构习题答案一评论:0 条查看:40 次zjw313014322发表于2009-04-21 16:25一、选择题1. 下面说法错误的是 C 。
（1）算法原地工作的含义是指不需要任何额外的辅助空间。
（2）在相同的规模n下，复杂度O（n）的撒在时间上总是优于复杂度O(2n)的算法。
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。
（4）同一个算法，实现语言的级别越高，执行效率越低。
A、（1）B、（1）（2）C、（1）（4）D、（3）2. 一个递归算法必须包括 B 。
A、递归部分B、终止条件和递归部分C、迭代部分D、终止条件和迭代部分3. 数据的 C 包括查找、插入、删除、更新、排序等操作类型。
A、存储结构B、逻辑结构C、基本运算D、算法描述4. 在数据结构中，从逻辑上可以把数据结构分成 C 。
A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构5. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的 C 。
A、存储结构B、存储实现C、逻辑结构D、运算实现6. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 B 。
A、数据具有同一特点B、不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C、每个数据元素都一样D、数据元素所包含的数据项的个数要相等7. 以下说法正确的是 D 。
A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、一些表面上很不相同的数据可以有相同的逻辑结构8. 以下说法错误的是 A 。
A、程序设计的实质是数据处理B、数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式C、运算实现是完成运算功能的算法或这些算法的设计D、数据处理方式总是与数据的某种相应表示形式相联系，反之亦然9. 下列程序段的时间复杂度为 B 。
x=n;y=0;while (x>=(y+1)*(y+1))y=y+1;A、O(n)B、O(n1/2)C、O(1)D、O(n2)10. 下列叙述中有关好的编程风格的正确描述是 C 。
数据结构练习题1⼀、单项选择题1.若⽤⼀个⼤⼩为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除⼀个元素，再加⼊两个元素后，rear和front的值分别为多少？( )A. 1和 5B. 2和4C. 4和2D. 5和1⼤⼩为6的数组：下标从0-5;从前⾯出队，从后⾯⼊队front(前⾯)=3rear(后⾯)=0当出队列中删除⼀个元素，也就是出队，即front+1:=4再插⼊两个元素，即rear+2= 2【注】循环队列中，由于⼊队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。
因此，⽆法通过条件front==rear来判别队列是"空"还是"满"。
2.循环队列A[0..m-1]存放其元素值，⽤front和rear分别表⽰队头和队尾，则当前队列中的元素数是( )。
A. (rear-front+m)%mB. rear-front+1C. rear-front-1D. rear-front3.for（i=0；ifor（j=0；jA［i］［j］=i*j；上⾯算法的时间复杂度为( )A.O(m2)B.O(n2)C.O(m×n)D.O(m+n）4.设h是指向⾮空带表头结点的循环链表的头指针，p是辅助指针。
执⾏程序段p=h;while (p->next->next!=h)p=p->next;p->next=h;后（其中，p->next为p指向结点的指针域），则( )A. p->next指针指向链尾结点B. h指向链尾结点C. 删除链尾前⾯的结点D. 删除链尾结点5.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（）A.head= =NULLB.head–>next= =NULLC.head!=NULLD.head–>next= =head6. 设顺序表有19个元素，第⼀个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( )A.236B.239C.242D.2457. 若⼀棵⼆叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A ．9B ．11C ．15D ．不确定8. n 个结点的线索⼆叉树上含有的线索数为（）A ．2nB ．n －lC ．n ＋lD ．n9. 设有⼀个栈，按A 、B 、C 、D 的顺序进栈，则可能为出栈序列的是( )A.DCBAB.CDABC.DBACD.DCAB10. 归并排序中，归并的趟数是( )。
第一次作业------------线性表题目1、下列图1单链表执行R->data=P->next->data语句后，P->next->data值为A. 5B. 7C. 2D. 3题目2、在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。
A. 向量大小B. 基地址和结点大小C. 结点大小D. 基地址题目3、非空的循环单链表head的尾节点（由r所指向）满足( )A. r->next=NULLB. r->next=headC. r=NULLD. r=head题目4、设线性表（a1,a2,a3···an）按顺序存储,且每个元素占有m个存储单元，则元素ai 的地址为A. LOC(a1) + i×m ，其中LOC(a1)表示元素a1的地址B. 元素ai的地址无法计算C. LOC(a1) + (i-1)×m，D. LOC(a1) + (i－2)×m题目5、在（）运算中，使用顺序表比链表好。
A. 根据元素值查找B. 插入C. 根据序号查找D. 删除题目6、在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点A. P→next=S;S→next=PB. S→next=P→next; P=SC. S→next=P→next;P→next=SD. S→next=P;P→next=S题目7、在双向循环链表的*p结点之后插入*s结点的操作是A. s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;B. s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;C. p->next=s; s->prior=p; p->next->prior=s; s->next=p->nextD. p->next=s; p->next->prior=s; s->prior=p; s->next=p->next题目8、单链表表示的整数数列如下图，值P->next->next->data为:A. 47B. 93C. 19D. 64题目9、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。
