数据结构(C++版)课后作业1-6章带答案.docx

《数据结构(C++版)课后作业1-6章带答案.docx》由会员分享，可在线阅读，更多相关《数据结构(C++版)课后作业1-6章带答案.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章绪论课后习题讲解1 .填空（1）从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）o（2）数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（） 和（）。（3）算法在发生非法操作时可以作出处理的特性称为（）。2 .选择题顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关 系是由（）表示的。 A线性结构B非线性结构C存储位置D指针假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或者母亲的遗产；子女间 不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。A树B图C线性表D集 合3 ,判

2、断题（1）每种数据结构都具备三个基本操作：插入、删除和查找。第2章线性表课后习题讲解1 .填空 顺序表中第一个元素的存储地址是100,每一个元素的长度为2,则第5个元素的存储地址是（）。第5 个元素的存储地址=第1个元素的存储地址+ （5 - 1）x2=108设单链表中指针p指向结点A,若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）o【解答】p-next=（p-next）-next 非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。p-next=head（6）在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的

3、操作 序歹4为（）o o 【解答】 s-next =rear-next; rear-next =s; rear =s; q=rear-next-next;rear-next-next=q-next; delete q;2 .选择题线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。A随 机存取B顺序存取C索引存取D散列存取【解答】A， B【分析】参见 线性表采用链接存储时，其地址（）。A必须是连续的B部份地址必须是连续的C一定是不连续 的D连续与否均可以【解答】D【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据 元素，这组存储单元可以连续，也可以不

4、连续，甚至可以零散分布在内存中任意位置。单循环链表的主要优点是（）。A再也不需要头指针了 B从表中任一结点出发都能扫描到整个链表; C已知某个结点的位置后，能够容易找到它的直接前趋；D在进行插入、删除操作时，能更好地保证链 表不断开。【解答】B（4）链表不具有的特点是（）。A可随机访问任一元素B插入、删除不需要挪移元素C不必事先估计 存储空间D所需空间与线性表长度成正比.【解答】A若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋，则采用（）存储方法最节省时间0 A 顺序表B单链表C双链表D单循环链表 【解答】A【分析】线性表中最常用的操作是取第i个元素， 所以，应选择随机存取结构即顺

5、序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链 表既不能实现随机存取，查找第卜个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能 实现随机存取。（10）使用双链表存储线性表，其优点是可以（）。A提高查找速度B更方便数据的插入和删除C节约 存储空间D很快回收存储空间 【解答】B【分析】在链表中普通只能进行顺序查找，所以，双链表并 不能提高查找速度，因为双链表中有两个指针域，显然不能节约存储空间，对于动态存储分配，回收存储 空间的速度是一样的。由于双链表具有对称性，所以，其插入和删除操作更加方便。（11）在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在

6、q和p之间插入s所指结点，则执行（） 操作。 A s-next=p-next; p-next=s; B q-next=s; s-next=p; C p-next=s-next; s-next=p; D p-next=s; s-next=q;【解答】B,本题答案不是非常合理，应该换顺序更好！考试可以修改说：已知q所指结点,在q后面插入一个节点。（12）在循环双链表的p所指结点后插入s所指结点的操作是（）。A p-next=s; s-prior=p;p-next-prior=s; s-next=p-next; B p-next=s; p-next-prior=s; s-prior=p; s-nex

7、t=p-next; C s-prior=p; s-next=p-next; p-next=s; p-next-prior=s; D s-prior=p; s-next=p-next;p-next-prior=s; p-next=s 【解答】 D3 .判断题线性表的逻辑顺序和存储顺序总是一致的。【解答】错。顺序表的逻辑顺序和存储顺序一致，链表的逻辑顺序和存储顺序不一定一致。线性表的顺序存储结构优于链接存储结构。（4）线性结构的基本特征是：每一个元素有且仅有一个直接前驱和一个直接后继。【解答】错。每一个元素最多惟独一个直接前驱和一个直接后继，第一个元素没有前驱，最后一个元素没 有后继。 在单链表中

8、，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。 【解答】错。要找到该结点的地址，必须从头指针开始查找，所以单链表是顺序存取结构。4 .请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。若线性表的 总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。 如果n个线 性表同时并存，并且在处理过程中各表的长度会动态发生变化。描述一个城市的设计和规划。【解答】顺序表的优点： 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速地 存取表中任一位置的元素（即随机存取）。顺序表的缺点： 插入和删除操作需挪移大量元

9、素； 表的 容量难以确定；造成存储空间的碎片单链表的优点：不必事先知道线性表的长度；插入和 删除元素时只需修改指针，不用挪移元素。单链表的缺点：指针的结构性开消；存取表中任意元素 不方便，只能进行顺序存取。 应选用顺序存储结构因为顺序表是随机存取结构，单链表是顺序存取 结构。本题很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。（2） 应选用链接存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。应选用链接存储结构。因为一个城市的设计和规划涉及活动不少，需要时常修改、扩充和删除各种信息， 才干适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。

10、5 .算法设计（1）假设在长度大于1的循环链表中，即无头结点也无头指针，s为指向链表中某个结点的指针，试编写算 法删除结点S的前趋结点。第3章特殊线性表栈、队列和串课后习题讲解1.填空 设有一个空栈，栈顶指针为1000H,现有输入序列为1、2、3、4、5,经过push, push, pop, push,pop, push, push后，输出序列是（），栈顶指针为（）。【解答】23, 1003H栈通常采用的两种存储结构是（）；其判定栈空的条件分别是（）,判定栈满的条件分别是（）o【解答】顺序存储结构和链接存储结构（或者顺序栈和链栈），栈顶指针top=-1和top=NULL,栈顶指针 top等于数

11、组的长度和内存无可用空间（）可作为实现递归函数调用的一种数据结构。（栈或者队列选一个）【解答】栈 【分析】递归函数的调用和返回正好符合后进先出性。 栈和队列是两种特殊的线性表，栈的操作特性是（），队列的操作特性是（），栈和队列的主要区别在于（）。 【解答】后进先出，先进先出，对插入和删除操作限定的位置不同（6）循环队列的引入是为了克服（）。【解答】假溢出数组Qn用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中 元素个数的公式为（）。（rear-front+n） % n2 .选择题 若一个栈的输入序列是1，2, 3, . , n,输出序列的第一个元素是

12、n,则第i个输出元素是（）。A不 确定Bn-i C n-i-1 D n-i+1【解答】D【分析】此时，输出序列一定是输入序列的逆序。 设栈S和队列Q的初始状态为空，元素el、e2、e3、e4、e5、e6挨次通过栈S, 一个元素出栈后即进入 队列Q,若6个元素从队列输出的元素的顺序是e2、e4、e3、e6、e5、el,则栈S的容量至少应该是（）。A6 B4 C3 D 2【解答】C【分析】由于队列具有先进先出性，所以，此题中队列形同虚设，即出栈的顺序也是e2、学、 e3 e6、 e5 el。3 3） 一个栈的入栈序列是1, 2, 3, 4, 5,则栈的不可能的输出序列是（）。A 54321 B 4

13、5321 C 43512 D 12345【解答】C【分析】此题有一个技巧：在输出序列中任意元素后面不能浮现比该元素小并且是升序（指的是元素的序号）的两个元素。（4）设计一个判别表达式中摆布括号是否配对的算法，采用（）数据结构最佳A顺序表B栈C队列D链 表【解答】B【分析】每一个右括号与它前面的最后一个没有匹配的左括号配对，因此具有后进先出性。在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（） 结构。A栈B队列C数组D线性表【解答】B【分析】先进入打印缓冲区的文件先被打印，因此具有先进先出性。（6） 一个队列的入队顺序是1, 2, 3, 4,则队列的输出顺

14、序是（）。 A 4321 B 1234 C 1432 D 3241 【解答】B【分析】队列的入队顺序和出队顺序总是一致的。栈和队列的主要区别在于（）。A它们的逻辑结构不一样B它们的存储结构不一样C所包含的运算不一样D插入、删除运算的限定不一样【解答】D（9）设有两个串p和q,求q在p中首次浮现的位置的运算称作（）。A连接B模式匹配C求子串D求 串长3.判断题栈可以作为实现过程调用的一种数据结构。在循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，则队满的条件是front=ear。【解答】错。这是队空的判定条件，在循环队列中要将队空和队满的判定条件区别开。空串与空格串是

15、相同的。1.在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针， 当出栈时，top的变化为（）。 A 不变 B top=0; C top=top-l; D top=top+l;【解答】C3 .从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行（）。A x=top; top=top-next; B x=top-data; C top=top-next; x=top-data; D x=top-data; top=top-next; 【解 答】D5 .设S=匚am_a_teacther”，其长度为（）。【解答】156 .对于栈和队列，

16、无论它们采用顺序存储结构还是链接存储结构，进行插入和删除操作的时间复杂度都是 （）。 【解答】0 （1）8.简述队列和栈这两种数据结构的相同点和不同点。第5章树和二叉树课后习题讲解1 .填空题一棵二叉树的第i （巨1）层最多有（）个结点；一棵有n （n0）个结点的满二叉树共有（）个叶子结 点和（）个非终端结点。【解答】2i-i, （n+l）/2 , （n-l）/2【分析】设满二叉树中叶子结点的个数为nO,度为2的结点个数为n2,由 于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+l,得n0=（n+l）/2, n2=（n-l）/2o（4）设高度为h的二叉树上惟独度为

17、0和度为2的结点，该二叉树的结点数可能达到的最大值是（）,最小 值是（）。【解答】2h-l, 2h-l【分析】最小结点个数的情况是第1层有1个结点，其他层上都惟独2个结点。（6）具有100个结点的彻底二叉树的叶子结点数为（）。【解答】50【分析】100个结点的彻底二叉树中最后一个结点的编号为100,其双亲即最后一个分支结点 的编号为50,也就是说，从编号51开始均为叶子。已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有（）个叶子 结点。（8）某二叉树的前序遍历序列是ABCDEFG,中序遍历序歹U是CBDAFGE,则其后序遍历序列是（）。【解答】CDBGFEA

18、【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。（10）在有n个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）。【解答】n, n-1【分析】nl个分支结点是经过n-1次合并后得到的。2 .选择题如果结点A有3个兄弟，B是A的双亲，则结点B的度是（）。A 1 B2C3 D4 【解答】D二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A空或者惟独一个结点B 高度等于其结点数C任一结点无左孩子D任一结点无右孩子【解答】B【分析】此题注意是序列正好相反，则左斜树和右斜树均满足条件。（4）线索二叉树中某结点R没有左孩子的充要条件是（）。 A R.lchild=NUL

19、L B R.ltag=O C R.ltag=l D R.rchild=NULL【解答】C【分析】线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左 标志是否为1。（6） 一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（）成立。An=h+m Bh+m=2nC m=h-l D n=2m-l【解答】D【分析】满二叉树中没有度为1的结点，所以有m个叶子结点，则度为2的结点个数为m-1（比如 叶子为8,则挨次往上是4,2,1个节点，等比数列个数为m-L） o 设森林中有4棵树，树中结点的个数挨次为nl、n2、n3、n4,则把森林转换成二叉树后，其根结点的右 子树上有

20、（）个结点，根结点的左子树上有（）个结点。A nl-1 B nl C nl+n2+n3 D n2+n3+n4 （10）讨论树、森林和二叉树的关系，目的是为了（）。 A借助二叉树上的运算方法去实现对树的一些 运算B将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题C将树、森林转 换成二叉树D体现一种技巧，没有什么实际意义3.判断题在线索二叉树中，任一结点均有指向其前趋和后继的线索。【解答】错。某结点是否有前驱或者后继的线索，取决于该结点的标志域是否为1。 在二叉树的前序遍历序列中，任意一个结点均处在其子女的前面。 二叉树是度为2的树。【解答】错。二叉树和树是两种不同的树结构，

21、例如，左斜树（4）由树转换成二叉树，其根结点的右子树总是空的。【解答】对。因为根结点无兄弟结点。用一维数组存储二叉树时，总是以前序遍历存储结点。【解答】错。二叉树的顺序存储结构是按层序 存储的，普通适合存储彻底二叉树。4.证明：对任一满二叉树，其分枝数B=2（n0-l） o （其中，nO为终端结点数）已知二叉树的中序和后序序列分别为CBEDAFIGH和CEDBIFHGA,试构造该二叉树。8 .对给定的一组权值W= （5, 2, 9, 11, 8, 3, 7）,试构造相应的哈夫曼树，并计算它的带权路径长 度。带权路径长度为：WPL=2x4+3x4+5x3+7x3+8x3+9x2+llx2 =12

22、09 .已知某字符串S中共有8种字符，各种字符分别浮现2次、1次、4次、5次、7次、3次、4次和9次，对该 字符串用0, 1进行前缀编码，问该字符串的编码至少有多少位。【解答】以各字符浮现的次数作为叶子结点的权值构造的哈夫曼编码树如图514所示。其带权路径长度 =2x5+1x5+3x4+5x3+9x2+4x3+4x3+7x2=98,所以，该字符串的编码长度至少为98位。10 .算法设计以二叉链表为存储结构，编写算法求二叉树中结点x的双亲。（6）以二叉链表为存储结构，在二叉树中删除以值X为根结点的子树。公司印章管理制度一、目的公司印章是公司对内对外行使权力的标志，也是公司名称的法律体现，因 此，

23、必须对印章进行规范化、合理化的严格管理，以保证公司各项业务的正常运 作，由公司指定专人负责管理。二、印章的种类1、公章，是按照政府规定，由主管部门批准刻制的代表公司权力的印章。2、专用章，为方便工作专门刻制的用于某种特定用途的印章，如：合同 专用章、财务专用章、业务专用章、仓库签收章等。3、手章（签名章），是以公司法人代表名字刻制的用于公务的印章。三、印章的管理规定1、印章指定专人负责保管和使用，保管印章的地方（桌、柜等）要坚固加 锁，印章使用后要及时收存。2、财务专用章由财务部负责保管，向银行备案的印章，应由财务部会计、 总经办分别保管。3、印章要注意保养，防止碰撞，还要及时清洗，以保持印迹

24、清晰。4、普通情况下不得将印章携出公司外使用，如确实因工作所需，则应由 印章管理员携带印章到场盖章或者监印。5、印章管理人员离职或者调任时，须履行印章交接手续。四、公章刻制印章需本公司法人代表批准，并由印章管理专责人负责办理刻制并启用并 交由专人进行保管。五、印章的使用1、使用任何的印章，需由相应负责人审核签字。为方便工 作，总经理可授权印章管理专责人审核普通性事务用印。2、用印前印章管理人员须认真审核，明确了解用印的内容和目的，确 认符合用印的手续后，在用印登记簿上逐项登记，方可盖章。3、对需要留存的材料，盖印后应留存一份立卷归档。4、不得在空白凭证、便笺上盖章。5、上报有关部门的文件资料，未经部门经理、总经理审签，不得盖章。6、以公司名义行文，未经总经理签发，不得盖章。7、按照合同会签制度的规定，所有合同和协议在会签手续齐全后方可盖五.早。8、各印章管理人员如出差，应把印章移交有关人员，并办理有关交接手续。六、印章管理人员的责任1、印章管理人员要与公司签订印章管理责任书，并在“印章管理制度”上签名。2、印章管理人员不得擅自使用印章，对于非法使用印章者，造成经济损失的除 赔偿损失外，还要追究其行政责任或者法律责任。用章申请事由：部门负责人核准时间副经理核准时间总经理核准时间