为您推荐:
精华内容
最热下载
问答
  • 5星
    55KB m0_52957036 2019-12-14 11:25:27
  • 6.93MB qaq123666 2018-12-19 10:18:32
  • 4星
    7.96MB yuqitao242 2017-03-18 21:45:06
  • 925KB u012552432 2013-11-26 12:16:57
  • 623KB u013405266 2014-01-07 10:40:22
  • 834KB new_new_zero 2018-09-02 14:19:25
  • 922KB zzyywr 2011-03-15 22:47:18
  • 2.47MB m0_52957036 2020-09-01 08:32:07
  • 21KB yuansaijie0604 2017-03-13 20:55:50
  • 4星
    869KB s_999999 2019-01-05 22:27:38
  • 876KB u014355480 2014-12-18 17:52:25
  • 900KB dfsethtdfd 2019-01-26 18:35:09
  • 4.58MB mistletoe_ww 2018-06-13 23:10:36
  • 15.79MB m0_37774173 2019-02-03 08:08:07
  • 1.25MB qq_43648927 2019-06-29 15:29:19
  • 严蔚敏数据结构C语言版)参考答案第十章第十章 内部排序10.23void Insert_Sort1(SqList &L)//监视哨设在高下标端的插入排序算法{??k=L.length;??for(i=k-1;i;--i) //从后向前逐个插入排序????if(L.r[i].key>...

    严蔚敏版数据结构C语言版)参考答案第十章

    第十章 内部排序

    10.23

    void Insert_Sort1(SqList &L)//监视哨设在高下标端的插入排序算法{??k=L.length;??for(i=k-1;i;--i) //从后向前逐个插入排序????if(L.r[i].key>L.r[i+1].key)????{??????L.r[k+1].key=L.r[i].key; //监视哨??????for(j=i+1;L.r[j].key>L.r[i].key;++j)????????L.r[j-1].key=L.r[j].key; //前移??????L.r[j-1].key=L.r[k+1].key; //插入????}}//Insert_Sort1

    10.24

    void BiInsert_Sort(SqList &L)//二路插入排序的算法{??int d[MAXSIZE]; //辅助存储??x=L.r.key;d=x;??first=1;final=1;??for(i=2;i<=L.length;i++)??{????if(L.r[i].key>=x) //插入前部????{??????for(j=final;d[j]>L.r[i].key;j--)????????d[j+1]=d[j];??????d[j+1]=L.r[i].key;??????final++;????}????else //插入后部????{??????for(j=first;d[j]

    10.25

    void SLInsert_Sort(SLList &L)//静态链表的插入排序算法{??L.r[0].key=0;L.r[0].next=1;??L.r[1].next=0; //建初始循环链表??for(i=2;i<=L.length;i++) //逐个插入??{????p=0;x=L.r[i].key;????while(L.r[L.r[p].next].keyL.r[i];??????L.r[i].next=p;????}????p=q;??}//for}//SLInsert_Sort

    10.26

    void Bubble_Sort1(int a[ ],int n)//对包含n个元素的数组a进行改进的冒泡排序{??change=n-1; //change指示上一趟冒泡中最后发生交换的元素??while(change)??{????for(c=0,i=0;ia[i+1])??????{????????a[i]a[i+1];????????c=i+1; //c指示这一趟冒泡中发生交换的元素??????}????change=c;??}//while}//Bubble_Sort1

    10.27

    void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法{??low=0;high=n-1; //冒泡的上下界??change=1;??while(lowa[i+1])??????{????????a[i]a[i+1];????????change=1;??????}????high--; //修改上界????for(i=high;i>low;

    展开全文
    weixin_39975366 2021-05-19 14:42:04
  • 1.01MB kksmission 2014-03-23 18:56:24
  • 5星
    1.14MB qq_47436772 2021-03-16 16:43:32
  • 1.自学编程,难免思路阻塞,收集更新了严蔚敏,吴伟民版《数据结构-C语言版》各章节的课本源码和配套习题集答案解析,目的是为了整理数据结构中的知识点,并与网友交流意见,集思广益,共同进步。这里是所有的源码和...

    数据结构c语言版第二版课后答案+源码

    1.自学编程,难免思路阻塞,收集更新了严蔚敏,吴伟民版《数据结构-C语言版》各章节的课本源码和配套习题集答案解析,目的是为了整理数据结构中的知识点,并与网友交流意见,集思广益,共同进步。这里是所有的源码和课后习题实现目录:
    数据结构c语言版严蔚敏课后答案
    02.本源码与解析涵盖了《数据结构》课本和习题集两部分,课本和习题集分别以下图书籍为参照(我有左边的纸质版和右边的电子版,貌似内容没区别):
    03.所有源码实现均使用C语言,遵循C99标准,使用C-Free 5(C-Free置gcc编译器,编译时,需要在菜单栏,定位到构建–>构建选项–>类别–>C Language,勾选第三个:“ISO C99 plus GNU extensions [-std=gnu99]”,即编译选项用-std=gnu99,而不是-std=c89或者-std=c99)测试通过(不要在CFree里创建工程,如果确实想在工程里运行,那文件互相引用的方式需要改写)。(是的,初学C语言,郑重推荐CFree这个小巧的IDE(win7),简洁、易用、强大!出于兼容性原因,win10上更推荐CLion。注意事项参见第6条)
    附下载链接:CFree5
    04.为了便于引用、查阅,各章内容在计算机中分文件夹存放,其中,《▲课本算法实现》中存放对课本中算法的实现,《▼配套习题解析》存放对题集中习题的解答,各源文件按章、节组织,组织方式见附录二。
    ★★★05.注意各文档引用.h文件或.c文件时的相对路径。为保证源码中对各.h或.c文档的引用有效,请保持各文档的相对位置固定。
    ★★★06.对于主文档(含有main函数的文档),#include自定义源码时引入的是.c文件而不是.h文件,其原因是测试用的gcc编译器支持不创建工程的情况下直接编译。如果是在Visual Studio等微软的编译器下做测试,则必须先创建工程,并引入.h文件,而且,对全局变量的定义等可能需要作出修改,变为带有extren的形式。对于使用VC6或Visual Studio,还有其他编译器产生的各种编译问题,请自行百度解决。
    ★★★07.部分类型定义名称、宏名、函数名和算法步骤与《数据结构》原书略有区别,但算法思想与原书一致,这样“改写”主要是为了易于区分各名称并简化操作。部分文件的测试数据设置为单独的文档而不从控制台录入,目的是为了测试时方便,避免重复录入数据。
    ★★08.如果你使用的编译器不是CFree,请注意文件编码格式(当然,如果是你自己从头敲代码的话,忽略这一条!)
    09.各算法并非100%完善,未考虑所有意外,未做过多输入与输出验证。
    10.有的数据结构在创建之前需要初始化,有的创建和初始化合为一体。
    11.大多数组0号单元弃用,或用作计数器。
    12.留意全局变量和类型定义、宏定义。
    13.算法的测试文档中有些看似“多余”的缩进是为了区分不同功能模块,便于浏览。
    ★★★14.在习题集解析中,不同人可能会对同一个题的理解有差别,所以这里只是表达我个人的想法,不代表其他任何人的看法。
    15.所有教材源码已上传到Github,仅供参考,望大家勿抄作业。
    ★★★16.若对代码有疑问,或者发现有错误,再或者有好的建议、思路,都可以联系博主。
    17.绪论中的Scanf.c文件包含一个Scanf函数,用来从文件中读取西文字符。设计这个函数的原因是减少测试工作,避免每次测试时在控制台手动输入数据……
    18.关于IDE,前面说过,学习C语言,从我个人审美角度,在win7上,新手只推荐CFree,配合mingw这个编译工具集,简洁强大又好看。除此之外,还推荐CLion(在win10上同样好用)CLion和CFree使用的编译环境一样,不同的是,这个软件更“智能”,颜值也很高,操作体验也不错,而且开发C++也毫无压力,不过对电脑配置可能要求高一点点。如果你偏爱微软,也可以去使用他们家的VS除了体积庞大操作复杂外,也是个非常强悍的IDE,开发大型项目必备,但是初学者就算了吧,不太建议…当然,现在微软有了轻量级的编辑器VS Code,但这个工具不带编译功能,需要自己配置工具链,同样不推荐初学者使用…
    19.关于C/C++的编译器,粗略分为微软和GNU吧,微软的一般集成在自己的IDE里,GNU的有gcc(C语言)和g++(C++)等,这里的CFree里使用的mingw就是gcc和g++等的一个集合,如果想使用最新版,可以自行去下载配置。数据结构c语言版课后答案
    20.★★★★如果没有认真学过一门编程语言,请不要尝试这门课程,或者说,即使想学,也不要从这本书开始。这本书的定位应该是假设你已经熟悉某一种语言,不限于C语言,也可以是C++、Java、Python等。当然,懂得C/C++最好了,数据结构c语言版严蔚敏第二版课后答案因为这本书的示例代码就是C/C++的混编么(绝大部分是C)。数据结构c语言版严蔚敏第二版课后答案

    展开全文
    bookanddream 2020-04-06 21:38:29
  • 822KB qq_40802825 2018-12-16 11:08:19
  • 清华数据结构习题集答案 (C 语言版严蔚敏 )第 1 章 绪论简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。解:数据 是对客观事物的符号表示。在计算机科学中是指所有能输入到...

    清华数据结构习题集答案 (C 语言版严蔚敏 )

    第 1 章 绪论

    简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

    解:数据 是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符

    号的总称。

    数据元素 是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。

    数据对象 是性质相同的数据元素的集合,是数据的一个子集。

    数据结构 是相互之间存在一种或多种特定关系的数据元素的集合。

    存储结构 是数据结构在计算机中的表示。

    数据类型 是一个值的集合和定义在这个值集上的一组操作的总称。

    抽象数据类型 是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。

    试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

    解: 抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由

    具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据类型

    通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数

    据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实

    现,这样抽象层次更高,更能为其他用户提供良好的使用接口。

    设有数据结构 (D,R) ,其中

    D d 1,d 2,d 3,d 4 , R r , r d 1,d 2 , d 2,d 3 , d 3,d 4

    试按图论中图的画法惯例画出其逻辑结构图。

    解:

    试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义 (有理数是其分子、 分母均为自

    然数且分母不为零的分数) 。

    解:

    ADT Complex{

    数据对象: D={r,i|r,i 为实数 }

    数据关系: R={}

    基本操作:

    InitComplex(&C,re,im)

    操作结果:构造一个复数 C,其实部和虚部分别为 re 和 im

    DestroyCmoplex(&C)

    操作结果:销毁复数 C

    Get(C,k,&e)

    操作结果:用 e 返回复数 C 的第 k 元的值

    Put(&C,k,e)

    操作结果:改变复数 C 的第 k 元的值为 e

    IsAscending(C)

    操作结果:如果复数 C 的两个元素按升序排列,则返回 1,否则返回 0

    IsDescending(C)

    操作结果:如果复数 C 的两个元素按降序排列,则返回 1,否则返回 0

    Max(C,&e)

    操作结果:用 e 返回复数 C 的两个元素中值较大的一个

    Min(C,&e)

    操作结果:用 e 返回复数 C 的两个元素中值较小的一个

    }ADT Complex

    ADT RationalNumber{

    数据对象: D={s,m|s,m 为自然数,且 m不为 0}

    数据关系: R={}

    基本操作:

    InitRationalNumber(&R,s,m)

    操作结果:构造一个有理数 R,其分子和分母分别为 s 和 m

    展开全文
    weixin_39879881 2021-05-26 02:33:21
  • 4.49MB bendan233 2019-01-25 13:22:22
  • 921KB weixin_44143552 2021-03-12 20:29:09
  • 4星
    5.42MB blue0bird 2018-09-01 11:08:09
  • 数据结构(C语言版 第2版)课后习题答案 严蔚敏 等 编著,仅供参考,还是自己认真做了再看 第1章 绪论   5.选择题 (1)在数据结构中,从逻辑上可以把数据结构分成( C )。 A.动态结构和静态结构 B....

     

    转自 https://blog.csdn.net/Bamboo_shui/article/details/72433523    (原文没第八章答案)

    数据结构(C语言版 第2版)课后习题答案 严蔚敏 等 编著,仅供参考,还是自己认真做了再看

    第1章  绪论

     

    5.选择题

    (1)在数据结构中,从逻辑上可以把数据结构分成(  C )。

    A.动态结构和静态结构     B.紧凑结构和非紧凑结构

    C.线性结构和非线性结构   D.内部结构和外部结构

    (2)与数据元素本身的形式、内容、相对位置、个数无关的是数据的(  C )。

    A.存储结构               B.存储实现

    C.逻辑结构               D.运算实现

    (3)通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着(  B )。

       A.数据具有同一特点

    B.不仅数据元素所包含的数据项的个数要相同,而且对应数据项的类型要一致

    C.每个数据元素都一样

    D.数据元素所包含的数据项的个数要相等

    (4)以下说法正确的是( D  )。

    A.数据元素是数据的最小单位

    B.数据项是数据的基本单位

    C.数据结构是带有结构的各数据项的集合

    D.一些表面上很不相同的数据可以有相同的逻辑结构

    解释:数据元素是数据的基本单位,数据项是数据的最小单位,数据结构是带有结构的各数据元素的集合。

    (5)算法的时间复杂度取决于(  D  )。

    A.问题的规模 B.待处理数据的初态

    C.计算机的配置 D.A和B

    解释:算法的时间复杂度不仅与问题的规模有关,还与问题的其他因素有关。如某些排序的算法,其执行时间与待排序记录的初始状态有关。为此,有时会对算法有最好、最坏以及平均时间复杂度的评价。

    (6)以下数据结构中,( A )是非线性数据结构

    A.树        B.字符串       C.队列           D.栈

     

    6.试分析下面各程序段的时间复杂度。

    (1)x=90; y=100; 

    while(y>0)

    if(x>100)

     {x=x-10;y--;}

    else x++;

    答案:O(1)

    解释:程序的执行次数为常数阶。

    (2)for (i=0; i<n; i++)

    for (j=0; j<m; j++)

    a[i][j]=0;

    答案:O(m*n)

    解释:语句a[i][j]=0;的执行次数为m*n。

    (3)s=0;

         for i=0; i<n; i++)

    for(j=0; j<n; j++)

             s+=B[i][j];

    sum=s;

    答案:O(n2)

    解释:语句s+=B[i][j];的执行次数为n2。

    (4)i=1;

         while(i<=n)

            i=i*3;

    答案:O(log3n

    解释:语句i=i*3;的执行次数为 ëlog3nû。

    (5)x=0;

    for(i=1; i<n; i++)

       for (j=1; j<=n-i; j++)

    x++;

    答案:O(n2)

    解释:语句x++;的执行次数为n-1+n-2+……+1= n(n-1)/2。

     

     

    第2章  线性表

    1.选择题

    (1)顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是(  B  )。

    A.110            B.108         C.100          D.120

    解释:因为顺序表是连续存储的,所以第5个元素的地址为:100+2*( 5 - 1)=108。

    (2)在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是(  A )。

    A.访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)

    B.在第i个结点后插入一个新结点(1≤i≤n)

    C.删除第i个结点(1≤i≤n)

    D.将n个结点从小到大排序

    解释:在顺序表中插入、删除一个结点,平均约移动表中一半元素,时间复杂度为O(n);顺序表是一种随机存取结构,按位置访问元素可通过数组下标直接定位,时间复杂度是O(1);(排序的时间复杂度为O(n2)或O(nlog2n)?)。

    (3) 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动  的元素个数为( B  )。

    A.8      B.63.5        C.63      D.7

    解释:平均移动元素个数为n/2

    (4)链接存储的存储结构所占存储空间( A  )。

    A.分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针

    B.只有一部分,存放结点值

    C.只有一部分,存储表示结点间关系的指针

    D.分两部分,一部分存放结点值,另一部分存放结点所占单元数

    (5)线性表若采用链式存储结构时,要求内存中可用存储单元的地址( D  )。

    A.必须是连续的        B.部分地址必须是连续的

    C.一定是不连续的      D.连续或不连续都可以

    (6)线性表L在(  B )情况下适用于使用链式结构实现。

    A.需经常修改L中的结点值      B.需不断对L进行删除插入

    C.L中含有大量的结点          D.L中结点结构复杂

    解释:链表插入/删除数据只需修改指针不需要移动表中数据,链表适用长度变化大、频繁进行插入/删除操作。

    (7)单链表的存储密度( C  )。

    A.大于1        B.等于1      C.小于1    D.不能确定

    解释:存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比,假设单链表一个结点本身所占的空间为D,指针域所占的空间为N,则存储密度为D/(D+N),即一定小于1。

    (8)将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是(   )。

    A.n            B.2n-1        C.2n        D.n-1

    答案:A

    解释:当第一个有序表中所有的元素都小于(或大于)第二个表中的元素,只需要用第二个表中的第一个元素依次与第一个表的元素比较,总计比较n次,最多比较2n-1次。

    (9)在一个长度为n的顺序表中,在第i个元素(1≤i≤n+1)之前插入一个新元素时须向后移动( B  )个元素。

    A.n-i           B.n-i+1       C.n-i-1      D.I

    (10) 线性表L=(a1,a2,……an),下列说法正确的是(D  )。

    A.每个元素都有一个直接前驱和一个直接后继

    B.线性表中至少有一个元素

    C.表中诸元素的排列必须是由小到大或由大到小

    D.除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。

    (11) 创建一个包括n个结点的有序单链表的时间复杂度是(    )。

    A.O(1)          B.O(n)            C.O(n2)          D.O(nlog2n)

    答案:C

    解释:创建单链表的时间复杂度是O(n),而要建立一个有序的单链表,则每生成一个新结点时需要和已有的结点进行比较 以确定合适的插入位置,所以时间复杂度是O(n2)。

    (12) 以下说法错误的是(   )。

    A.求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低

    B.顺序存储的线性表可以随机存取

    C.由于顺序存储要求连续的存储区域,所以在存储管理上不够灵活

    D.线性表的链式存储结构优于顺序存储结构

    答案:D

    解释:链式存储结构和顺序存储结构各有优缺点,有不同的适用场合。

    (13) 在单链表中,要将s所指结点插入到p所指结点之后,其语句应为(   )。

    A.s->next=p+1; p->next=s;

    B.(*p).next=s; (*s).next=(*p).next;

    C.s->next=p->next; p->next=s->next;

    D.s->next=p->next; p->next=s;  

    答案:D

     (14) 在双向链表存储结构中,删除p所指的结点时须修改指针(   )。

    A.p->next->prior=p->prior; p->prior->next=p->next;

    B.p->next=p->next->next; p->next->prior=p;

    C.p->prior->next=p; p->prior=p->prior->prior;

    D.p->prior=p->next->next; p->next=p->prior->prior;

    答案:A

    (15) 在双向循环链表中,在p指针所指的结点后插入q所指向的新结点,其修改指针的操作是(   )。

    A.p->next=q; q->prior=p; p->next->prior=q; q->next=q;

    B.p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;

    C.q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;

    D.q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

    答案:C

    2.算法设计题

    (1)将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。

    [题目分析]

    (合并后的新表用一个新的Lc指针。新建一个Lc头指针,pa和pb分别是链表La和Lb的工作指针且初始化为相应链表的第一个结点。从第一个结点开始进行比较,当两个链表La和Lb均未到达表尾结点时,则依次摘取较小元素重新链接在Lc表的后面。其中,如果两个表中的元素相等,只摘取La表中的元素,删除Lb表中的元素(注意释放删除的元素的空间),这样确保合并后表中无重复的元素。当一个表到达表尾结点,为空时,将非空表的剩余元素直接链接在Lc表的最后面。

    [算法描述]

     

     
    1. void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)

    2. {//合并链表La和Lb,合并后的新表使用头指针Lc指向

    3. pa=La->next; pb=Lb->next;

    4. //pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点

    5. Lc=pc=La; //用La的头结点作为Lc的头结点

    6. while(pa && pb)

    7. {

    8. if(pa->data<pb->data){

    9. pc->next=pa;

    10. pc=pa;

    11. pa=pa->next;

    12. }

    13. //取较小者La中的元素,将pa链接在pc的后面,pa指针后移

    14. else if(pa->data>pb->data){

    15. pc->next=pb;

    16. pc=pb;

    17. pb=pb->next;

    18. }

    19. //取较小者Lb中的元素,将pb链接在pc的后面,pb指针后移

    20. else //相等时取La中的元素,删除Lb中的元素

    21. {

    22. pc->next=pa;

    23. pc=pa;

    24. pa=pa->next;

    25. q=pb->next;delete pb ;pb =q;(删除记得要释放空间)

    26. //q=pb;pb=q->next;delete q;

    27. }

    28. }

    29. pc->next=pa?pa:pb; //插入剩余段

    30. delete Lb; //释放Lb的头结点(La的头结点已赋给了Lc,不需释放)

    31. }



    (2)将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。

     

    [题目分析]

    合并后的新表使用头指针Lc指向,pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点,从第一个结点开始进行比较,当两个链表La和Lb均为到达表尾结点时,依次摘取其中较者重新链接在Lc表的表头结点之后,如果两个表中的元素相等,只摘取La表中的元素,保留Lb表中的元素。当一个表到达表尾结点,为空时,将非空表的剩余元素依次摘取,链接在Lc表的表头结点之后(前插法)

    [算法描述]

     

     
    1. void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, )

    2. {//合并链表La和Lb,合并后的新表使用头指针Lc指向

    3. pa=La->next; pb=Lb->next;

    4. //pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点

    5. Lc=pc=La; //用La的头结点作为Lc的头结点

    6. Lc->next=NULL;

    7. while(pa||pb)

    8. {//只要存在一个非空表,用q指向待摘取的元素

    9. if(!pa) {q=pb; pb=pb->next;}

    10. //La表为空,用q指向pb,pb指针后移

    11. else if(!pb) {q=pa; pa=pa->next;}

    12. //Lb表为空,用q指向pa,pa指针后移

    13. else if(pa->data<=pb->data) {q=pa; pa=pa->next;}

    14. //取较小者(包括相等)La中的元素,用q指向pa,pa指针后移

    15. else {q=pb; pb=pb->next;}

    16. //取较小者Lb中的元素,用q指向pb,pb指针后移

    17. q->next = Lc->next; Lc->next = q;

    18. //将q指向的结点插在Lc 表的表头结点之后

    19. }

    20. delete Lb; //释放Lb的头结点

    21. }

     

    (3)已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出A与B的交集,并存放于A链表中。

    [题目分析]

    只有同时出现在两集合中的元素才出现在结果表中,合并后的新表使用头指针Lc指向。pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点,从第一个结点开始进行比较,当两个链表La和Lb均为到达表尾结点时,如果两个表中相等的元素时,摘取La表中的元素,删除Lb表中的元素;如果其中一个表中的元素较小时,删除此表中较小的元素,此表的工作指针后移。当链表La和Lb有一个到达表尾结点,为空时,依次删除另一个非空表中的所有元素。

    [算法描述]

     

     
    1. void Mix(LinkList& La, LinkList& Lb, LinkList& Lc)

    2. { pa=La->next;pb=Lb->next;

    3. pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点

    4. Lc=pc=La; //用La的头结点作为Lc的头结点

    5. while(pa&&pb)

    6. { if(pa->data==pb->data)∥交集并入结果表中。

    7. { pc->next=pa;pc=pa;pa=pa->next;

    8. u=pb;pb=pb->next; delete u;}

    9. else if(pa->data<pb->data) {u=pa;pa=pa->next; delete u;}

    10. else {u=pb; pb=pb->next; delete u;}

    11. }

    12. while(pa) {u=pa; pa=pa->next; delete u;}∥ 释放结点空间

    13. while(pb) {u=pb; pb=pb->next; delete u;}∥释放结点空间

    14. pc->next=null;∥置链表尾标记。

    15. delete Lb; //释放Lb的头结点

    16. }

     

    (4)已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出两个集合A和B 的差集(即仅由在A中出现而不在B中出现的元素所构成的集合),并以同样的形式存储,同时返回该集合的元素个数。

    [题目分析]

    求两个集合A和B的差集是指在A中删除A和B中共有的元素,即删除链表中的相应结点,所以要保存待删除结点的前驱,使用指针pre指向前驱结点。pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点,从第一个结点开始进行比较,当两个链表La和Lb均为到达表尾结点时,如果La表中的元素小于Lb表中的元素,pre置为La表的工作指针pa删除Lb表中的元素;如果其中一个表中的元素较小时,删除此表中较小的元素,此表的工作指针后移。当链表La和Lb有一个为空时,依次删除另一个非空表中的所有元素。

    [算法描述]

     

     
    1. void Difference(LinkList& La, LinkList& Lb,int *n)

    2. {∥差集的结果存储于单链表La中,*n是结果集合中元素个数,调用时为0

    3. pa=La->next; pb=Lb->next;

    4. ∥pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点

    5. pre=La; ∥pre为La中pa所指结点的前驱结点的指针

    6. while(pa&&pb)

    7. {if(pa->data<q->data){pre=pa;pa=pa->next;*n++;}

    8. ∥ A链表中当前结点指针后移

    9. else if(pa->data>q->data)q=q->next; ∥B链表中当前结点指针后移

    10. else {pre->next=pa->next; ∥处理A,B中元素值相同的结点,应删除

    11. u=pa; pa=pa->next; delete u;} ∥删除结点

    12. }

    13. }

     

    (5)设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B表的结点为A表中值小于零的结点,而C表的结点为A表中值大于零的结点(链表A中的元素为非零整数,要求B、C表利用A表的结点)。

    [题目分析]

    B表的头结点使用原来A表的头结点,为C表新申请一个头结点。从A表的第一个结点开始,依次取其每个结点p,判断结点p的值是否小于0,利用前插法,将小于0的结点插入B表,大于等于0的结点插入C表。

    [算法描述]

     

     
    1. void DisCompose(LinkedList A)

    2. { B=A;

    3. B->next= NULL; ∥B表初始化

    4. C=new LNode;∥为C申请结点空间

    5. C->next=NULL; ∥C初始化为空表

    6. p=A->next; ∥p为工作指针

    7. while(p!= NULL)

    8. { r=p->next; ∥暂存p的后继

    9. if(p->data<0)

    10. {p->next=B->next; B->next=p; }∥将小于0的结点链入B表,前插法

    11. else {p->next=C->next; C->next=p; }∥将大于等于0的结点链入C表,前插法

    12. p=r;∥p指向新的待处理结点。

    13. }

     

     

    第3章  栈和队列

    1.选择题

    (1)若让元素1,2,3,4,5依次进栈,则出栈次序不可能出现在(  )种情况。

    A.5,4,3,2,1   B.2,1,5,4,3    C.4,3,1,2,5   D.2,3,5,4,1

    答案:C

    解释:栈是后进先出的线性表,不难发现C选项中元素1比元素2先出栈,违背了栈的后进先出原则,所以不可能出现C选项所示的情况。

    (2)若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为(  )。

    A.i               B.n-i               C.n-i+1            D.不确定

    答案:C

    解释:栈是后进先出的线性表,一个栈的入栈序列是1,2,3,…,n,而输出序列的第一个元素为n,说明1,2,3,…,n一次性全部进栈,再进行输出,所以p1=n,p2=n-1,…,pi=n-i+1。

    (3)数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素个数的公式为(  )。

    A.r-f             B.(n+f-r)%n       C.n+r-f           D.(n+r-f)%n

    答案:D

    解释:对于非循环队列,尾指针和头指针的差值便是队列的长度,而对于循环队列,差值可能为负数,所以需要将差值加上MAXSIZE(本题为n),然后与MAXSIZE(本题为n)求余,即(n+r-f)%n。

    (4)链式栈结点为:(data,link),top指向栈顶.若想摘除栈顶结点,并将删除结点的值保存到x中,则应执行操作(  )。

    A.x=top->data;top=top->link;      B.top=top->link;x=top->link;    

    C.x=top;top=top->link;       D.x=top->link;

    答案:A

    解释:x=top->data将结点的值保存到x中,top=top->link栈顶指针指向栈顶下一结点,即摘除栈顶结点。

    (5)设有一个递归算法如下

            int fact(int n) {  //n大于等于0

                 if(n<=0) return 1;

                 else return n*fact(n-1);        }

    则计算fact(n)需要调用该函数的次数为(  )。 

    A. n+1              B. n-1              C. n                  D. n+2

    答案:A

    解释:特殊值法。设n=0,易知仅调用一次fact(n)函数,故选A。

    (6)栈在 (  )中有所应用。

    A.递归调用       B.函数调用      C.表达式求值        D.前三个选项都有

    答案:D

    解释:递归调用、函数调用、表达式求值均用到了栈的后进先出性质。

    (7)为解决计算机主机与打印机间速度不匹配问题,通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是(  )。

    A.队列           B.栈            C. 线性表           D.有序表

    答案:A

    解释:解决缓冲区问题应利用一种先进先出的线性表,而队列正是一种先进先出的线性表。

    (8)设栈S和队列Q的初始状态为空,元素e1、e2、e3、e4、e5和e6依次进入栈S,一个元素出栈后即进入Q,若6个元素出队的序列是e2、e4、e3、e6、e5和e1,则栈S的容量至少应该是( )。

    A.2              B.3              C.4                D. 6

    答案:B

    解释:元素出队的序列是e2、e4、e3、e6、e5和e1,可知元素入队的序列是e2、e4、e3、e6、e5和e1,即元素出栈的序列也是e2、e4、e3、e6、e5和e1,而元素e1、e2、e3、e4、e5和e6依次进入栈,易知栈S中最多同时存在3个元素,故栈S的容量至少为3。

    (9)若一个栈以向量V[1..n]存储,初始栈顶指针top设为n+1,则元素x进栈的正确操作是(    )。

    A.top++; V[top]=x; B.V[top]=x; top++;

    C.top--; V[top]=x; D.V[top]=x; top--;

    答案:C

    解释:初始栈顶指针top为n+1,说明元素从数组向量的高端地址进栈,又因为元素存储在向量空间V[1..n]中,所以进栈时top指针先下移变为n,之后将元素x存储在V[n]。

    (10)设计一个判别表达式中左,右括号是否配对出现的算法,采用( )数据结构最佳。

    A.线性表的顺序存储结构              B.队列     

    C. 线性表的链式存储结构              D. 栈

    答案:D

    解释:利用栈的后进先出原则。

    (11)用链接方式存储的队列,在进行删除运算时( )。

    A. 仅修改头指针                      B. 仅修改尾指针

    C. 头、尾指针都要修改                D. 头、尾指针可能都要修改

    答案:D

    解释:一般情况下只修改头指针,但是,当删除的是队列中最后一个元素时,队尾指针也丢失了,因此需对队尾指针重新赋值。

    (12)循环队列存储在数组A[0..m]中,则入队时的操作为( )。

    A. rear=rear+1                       B. rear=(rear+1)%(m-1)

      C. rear=(rear+1)%m                   D. rear=(rear+1)%(m+1) 

    答案:D

    解释:数组A[0..m]中共含有m+1个元素,故在求模运算时应除以m+1。

    (13)最大容量为n的循环队列,队尾指针是rear,队头是front,则队空的条件是( )。

      A. (rear+1)%n==front                  B. rear==front                                                          

    C.rear+1==front                      D. (rear-l)%n==front

    答案:B

    解释:最大容量为n的循环队列,队满条件是(rear+1)%n==front,队空条件是rear==front。

    (14)栈和队列的共同点是( )。

    A. 都是先进先出                       B. 都是先进后出   

    C. 只允许在端点处插入和删除元素       D. 没有共同点

    答案:C

    解释:栈只允许在栈顶处进行插入和删除元素,队列只允许在队尾插入元素和在队头删除元素。

    (15)一个递归算法必须包括( )。

    A. 递归部分                           B. 终止条件和递归部分

    C. 迭代部分                           D. 终止条件和迭代部分

    答案:B

     

     

     

    第5章  树和二叉树

    1.选择题

    (1)把一棵树转换为二叉树后,这棵二叉树的形态是(   )。              

    A.唯一的                          B.有多种

    C.有多种,但根结点都没有左孩子    D.有多种,但根结点都没有右孩子

    答案:A

    解释:因为二叉树有左孩子、右孩子之分,故一棵树转换为二叉树后,这棵二叉树的形态是唯一的。

    (2)由3个结点可以构造出多少种不同的二叉树?(    )

    A.2          B.3             C.4          D.5   

    答案:D

    (3)一棵完全二叉树上有1001个结点,其中叶子结点的个数是(  )。

    A.250         B. 500          C.254        D.501   

    答案:D

    解释:设度为0结点(叶子结点)个数为A,度为1的结点个数为B,度为2的结点个数为C,有A=C+1,A+B+C=1001,可得2C+B=1000,由完全二叉树的性质可得B=0或1,又因为C为整数,所以B=0,C=500,A=501,即有501个叶子结点。

    (4)一个具有1025个结点的二叉树的高h为(  )。

    A.11          B.10             C.11至1025之间       D.10至1024之间

    答案:C

    解释:若每层仅有一个结点,则树高h为1025;且其最小树高为 ëlog21025û + 1=11,即h在11至1025之间。

    (5)深度为h的满m叉树的第k层有(  )个结点。(1=<k=<h)

    A.mk-1          B.mk-1            C.mh-1        D.mh-1

    答案:A

    解释:深度为h的满m叉树共有mh-1个结点,第k层有mk-1个结点。

    (6)利用二叉链表存储树,则根结点的右指针是(  )。

    A.指向最左孩子        B.指向最右孩子         C.空        D.非空

    答案:C

    解释:利用二叉链表存储树时,右指针指向兄弟结点,因为根节点没有兄弟结点,故根节点的右指针指向空。

    (7)对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左、右孩子的编号,同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,可采用(  )遍历实现编号。

    A.先序         B. 中序           C. 后序       D. 从根开始按层次遍历

    答案:C

    解释:根据题意可知按照先左孩子、再右孩子、最后双亲结点的顺序遍历二叉树,即后序遍历二叉树。

    (8)若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置,利用(  )遍历方法最合适。

    A.前序         B.中序            C.后序      D.按层次

    答案:C

    解释:后续遍历和层次遍历均可实现左右子树的交换,不过层次遍历的实现消耗比后续大,后序遍历方法最合适。

    (9)在下列存储形式中,(  )不是树的存储形式?

    A.双亲表示法   B.孩子链表表示法   C.孩子兄弟表示法   D.顺序存储表示法

    答案:D

    解释:树的存储结构有三种:双亲表示法、孩子表示法、孩子兄弟表示法,其中孩子兄弟表示法是常用的表示法,任意一棵树都能通过孩子兄弟表示法转换为二叉树进行存储。

    (10)一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足(  )。

    A.所有的结点均无左孩子        B.所有的结点均无右孩子

    C.只有一个叶子结点            D.是任意一棵二叉树

    答案:C

    解释:因为先序遍历结果是“中左右”,后序遍历结果是“左右中”,当没有左子树时,就是“中右”和“右中”;当没有右子树时,就是“中左”和“左中”。则所有的结点均无左孩子或所有的结点均无右孩子均可,所以A、B不能选,又所有的结点均无左孩子与所有的结点均无右孩子时,均只有一个叶子结点,故选C。

    (11)设哈夫曼树中有199个结点,则该哈夫曼树中有(    )个叶子结点。

    A.99 B.100

    C.101 D.102

    答案:B

    解释:在哈夫曼树中没有度为1的结点,只有度为0(叶子结点)和度为2的结点。设叶子结点的个数为n0,度为2的结点的个数为n2,由二叉树的性质n0=n2+1,则总结点数n= n0+n2=2*n0-1,得到n0=100。

    (12)若X是二叉中序线索树中一个有左孩子的结点,且X不为根,则X的前驱为(  )。

    A.X的双亲                      B.X的右子树中最左的结点 

    C.X的左子树中最右结点          D.X的左子树中最右叶结点

    答案:C

    (13)引入二叉线索树的目的是(  )。

    A.加快查找结点的前驱或后继的速度    B.为了能在二叉树中方便的进行插入与删除

    C.为了能方便的找到双亲              D.使二叉树的遍历结果唯一

    答案:A

    (14)设F是一个森林,B是由F变换得的二叉树。若F中有n个非终端结点,则B中右指针域为空的结点有(   )个。

    A.n−1 B.n C.n + 1 D.n + 2

    答案:C

    (15)n(n≥2)个权值均不相同的字符构成哈夫曼树,关于该树的叙述中,错误的是( )。

    A.该树一定是一棵完全二叉树

    B.树中一定没有度为1的结点

    C.树中两个权值最小的结点一定是兄弟结点

    D.树中任一非叶结点的权值一定不小于下一层任一结点的权值

    答案:A

    解释:哈夫曼树的构造过程是每次都选取权值最小的树作为左右子树构造一棵新的二叉树,所以树中一定没有度为1的结点、两个权值最小的结点一定是兄弟结点、任一非叶结点的权值一定不小于下一层任一结点的权值。

    2.应用题

    (1)试找出满足下列条件的二叉树

    ① 先序序列与后序序列相同    ②中序序列与后序序列相同

    ③ 先序序列与中序序列相同    ④中序序列与层次遍历序列相同

    答案:先序遍历二叉树的顺序是“根—左子树—右子树”,中序遍历“左子树—根—右子树”,后序遍历顺序是:“左子树—右子树―根",根据以上原则有

    ① 或为空树,或为只有根结点的二叉树

    ②  或为空树,或为任一结点至多只有左子树的二叉树.

    ③  或为空树,或为任一结点至多只有右子树的二叉树.

    ④ 或为空树,或为任一结点至多只有右子树的二叉树

     

    (2)设一棵二叉树的先序序列: A B D F C E G H ,中序序列: B F D A G E H C

    ①画出这棵二叉树。

    ②画出这棵二叉树的后序线索树。

    ③将这棵二叉树转换成对应的树(或森林)。

    答案:

    第六章

     

    1.选择题

    1-4:CBBB

     

     

    (5)G是一个非连通无向图,共有28条边,则该图至少有(   )个顶点。

    A.7              B.8             C.9             D.10 

    答案:C

    解释:8个顶点的无向图最多有8*7/2=28条边,再添加一个点即构成非连通无向图,故至少有9个顶点。

    6-12:BABAADC

    13-15:CDB

     

    2.应用题

    (1)

    第七章

    (1)C (2)D (3)C (4)A (5)B (6)C (7)C (8)C (9)C (10)C (11)B (12)C (13)A  (14)D (15)A 

     

    第八章

    1.选择题

    1-5:CDBDC          6-10:BCDBC      

    11-15:BCCCA

     

    展开全文
    qq_42777804 2018-09-11 17:09:52
  • Clown_pan 2019-05-11 22:44:34

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,047
精华内容 1,218
关键字:

数据结构严蔚敏答案

数据结构 订阅