您的位置: 主页 > 产品中心 >

咨询热线

400-690-123455
  • 数据结构(C语言版 第2版)课后习题答案 严蔚敏
数据结构(C语言版 第2版)课后习题答案 严蔚敏

授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累! 授予每

全国热线

400-690-123455

  • 产品详情

  授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!

  授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。

  求 FIRST集,FOLLOW集,FIRSTVT 集和 LASTVT 集

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  合并后的新表使用头指针Lc指向,pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点,从第一个结点开始进行比较,当两个链表La和Lb均为到达表尾结点时,依次摘取其中较

  者重新链接在Lc表的表头结点之后,如果两个表中的元素相等,只摘取La表中的元素,保留Lb表中的元素。当一个表到达表尾结点,为空时,将非空表的剩余元素依次摘取,链接在Lc表的表头结点之后

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

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

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

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

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

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

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

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

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

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

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

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

  解释:解决缓冲区问题应利用一种先进先出的线性表,而队列正是一种先进先出的线)设栈S和队列Q的初始状态为空,元素e1、e2、e3、e4、e5和e6依次进入栈S,一个元素出栈后即进入Q,若6个元素出队的序列是e2、e4、e3、e6、e5和e1,则栈S的容量至少应该是()。

  解释:元素出队的序列是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进栈的正确操作是(    )。

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

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

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

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

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

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

  C.有多种,但根结点都没有左孩子    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个叶子结点。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  点击上方“Python大本营”,选择“置顶公众号”Python大本营 IT人的职业提升平台最近有很多程序员在

  当HR压你价,说你只值7K时,你可以流畅地回答,记住,是流畅,不能犹豫。礼貌地说:“7K是吗?了解了。嗯~其实我对贵司的面试官印象很好。只不过,现在我的手头上已经有一份11K的offer。来面试,主要也是自己对贵司挺有兴趣的,所以过来看看……”(未完)这段话主要是陪HR互诈的同时,从公司兴趣,公司职员印象上,都给予对方正面的肯定,既能提升HR的好感度,又能让谈判气氛融洽,为后面的发挥留足空间。......

  1.选择题(1)串是一种特殊的线性表,其特殊性体现在(B) 。A.可以顺序存储 B.数据元素是单个字符

  )串下面关于串的的叙述中,(B)是不正确的。A.串是字符的有限序列B.空串是由空格构成的串

  .模式匹配是串的一种重要运算D .串既可以采用顺序存储,也可以采用链式存储

  的学习当然要从线性表学起,而线性表里首先需要学习单链表,这里从单链表最简单的顺序存储结构(本质就是可变数组存储)开始。解析    单链表强调元素在逻辑上紧密相邻,所以首先想到用数组存储。但是普通数组有着无法克服的容量限制,在不知道输入有多少的情况下,很难确定出一个合适的容量。对此,一个较好的解......

  原题描述问题描述 设停车场是一个可停放n辆汽车的狭长通道,且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第一辆车停放在车场的最北端),若车场内已停满n辆汽车,则后来的汽车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时,在它之后开入的车辆必须先退出车场为它让路,待该辆车开出大门外,其它车...