数据结构C++版课后作业章带答案.pdf

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

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

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

3、的单循环链表中，在表尾插入一个结点 s 的操作序列是（）；删除开始结点的操作 序列为（）。【解答】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【分析】参见 2.2.1。线性表采用链接存储时，其地址（）。A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续 的 D 连续与否均可以【解答】D【分析】线性表

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

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

6、的速度是一样的。由于双链表具有对称性，所以，其插入和删除操作更加方便。（11）在一个单链表中，已知 q 所指结点是 p 所指结点的直接前驱，若在 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

7、;p-next-prior=s;s-next=p-next;B p-next=s;p-next-prior=s;s-prior=p;s-next=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【解答】D 3.判断题 线性表的逻辑顺序和存储顺序总是一致的。【解答】错。顺序表的逻辑顺序和存储顺序一致，链表的逻辑顺序和存储顺序不一定一致。线性表的顺序存储结构优于链接存储结构。线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后

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

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

10、需要经常修改、扩充和删除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。5算法设计(1)假设在长度大于 1 的循环链表中，即无头结点也无头指针，s 为指向链表中某个结点的指针，试编写算 法删除结点 S 的前趋结点。第 3 章特殊线性表 栈、队列和串 课后习题讲解 1.填空 设有一个空栈，栈顶指针为 1000H，现有输入序列为 1、2、3、4、5，经过 push，push，pop，push，pop，push，push 后，输出序列是()，栈顶指针为()。【解答】23，1003H 栈通常采用的两种存储结构是()；其判定栈空的条件分别是()，判定栈满的条件分别是()。【解答

11、】顺序存储结构和链接存储结构(或顺序栈和链栈)，栈顶指针 top=-1 和 top=NULL，栈顶指针 top 等于数组的长度和内存无可用空间 3()可作为实现递归函数调用的一种数据结构。(栈或者队列选一个)【解答】栈【分析】递归函数的调用和返回正好符合后进先出性。栈和队列是两种特殊的线性表，栈的操作特性是()，队列的操作特性是()，栈和队列的主要区别 在于()。【解答】后进先出，先进先出，对插入和删除操作限定的位置不同 循环队列的引入是为了克服()。【解答】假溢出 数组 Qn 用来表示一个循环队列，front 为队头元素的前一个位置，rear 为队尾元素的位置，计算队列中 元素个数的公式为(

12、)。(rear-front+n)%n 2.选择题 若一个栈的输入序列是 1,2，3，n，输出序列的第一个元素是 n，则第 i 个输出元素是()。A 不 确定 B n-i C n-i-1 D n-i+1【解答】D【分析】此时，输出序列一定是输入序列的逆序。设栈 S 和队列 Q 的初始状态为空，元素 e1、e2、e3、e4、e5、e6 依次通过栈 S,个元素出栈后即进入 队列 Q,若 6 个元素从 队列输出的元素 的顺序是 e2、e4、e3、e6、e5、e1,则栈 S 的容量至少应该是()。A 6 B 4 C 3 D 2【解答】C【分析】由于队列具有先进先出性，所以，此题中队列形同虚设，即出栈的顺

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

14、C 数组 D 线性表【解答】B【分析】先进入打印缓冲区的文件先被打印，因此具有先进先出性。一个队列的入队顺序是 1，2，3，4，则队列的输出顺序是（）。A 4321 B 1234 C 1432 D 3241【解答】B【分析】队列的入队顺序和出队顺序总是一致的。栈和队列的主要区别在于（）。A 它们的逻辑结构不一样 B 它们的存储结构不一样 C 所包含的运 算不一样 D 插入、删除运算的限定不一样【解答】D 设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作（）。A 连接 B 模式匹配 C 求子串 D 求 串长 3.判断题 栈可以作为实现过程调用的一种数据结构。在循环队列中，fro

15、nt 指向队头元素的前一个位置，rear 指向队尾元素的位置，则队满的条件是 front=re ar。【解答】错。这是队空的判定条件，在循环队列中要将队空和队满的判定条件区别开。空串与空格串是相同的。1.在一个具有 n 个单元的顺序栈中，假定以地址低端（即下标为 0 的单元）作为栈底，以 top 作为栈顶指针，当出栈时，top 的变化为（）。A 不变 B top=0;C top=top-1;D top=top+1;【解答】C 3.从栈顶指针为 top 的链栈中删除一个结点，用 x 保存被删除结点的值，则执行（）。A x=top;top=top-next;B x=top-data;C top=t

16、op-next;x=top-data;D x=top-data;top=top-next;【解 答】D 5.设 S=l_ am_ a_ teacther，其长度为（）。【解答】15 6对于栈和队列，无论它们采用顺序存储结构还是链接存储结构，进行插入和删除操作的时间复杂度都是（）。【解答】0 8简述 队列和栈这两种数据结构的相同点和不同点。第 5 章 树和二叉树 课后习题讲解 1.填空题一棵二叉树的第 i（i 1层最多有（）个结点；一棵有 n（n0）个结点的满二叉树共有（）个叶子结 点和（）个非终端结点。【解答】2i-1,（n+1）/2，（n-1）/2【分析】设满二叉树中叶子结点的个数为 n0，

17、度为 2 的结点个数为 n2，由 于满二叉树中不存在度为 1 的结点，所以 n=n0+n2;由二叉树的性质 n0=n2+1，得 n0=（n+1）/2,n2=（n-1）/2。设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，该二叉树的结点数可能达到的最大值是（），最小 值是（）。【解答】2h-1，2h-1【分析】最小结点个数的情况是第 1 层有 1 个结点，其他层上都只有 2 个 结点。具有 100 个结点的完全二叉树的叶子结点数为（）。【解答】50【分析】100 个结点的完全二叉树中最后一个结点的编号为 100，其双亲即最后一个分支结点 的编号为 50，也就是说，从编号 51 开始均为

18、叶子。已知一棵度为 3 的树有 2 个度为 1 的结点，3 个度为 2 的结点，4 个度为 3 的结点。则该树中有（）个叶子 结点。某二叉树的前序遍历序列是 ABCDEFG,中序遍历序列是 CBDAFGE,则其后序遍历序列是（）。【解答】CDBGFEA【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。（10）在有 n 个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）。【解答】n，n-1【分析】n-1 个分支结点是经过 n-1 次合并后得到的。2.选择题 如果结点 A 有 3 个兄弟，B 是 A 的双亲，则结点 B 的度是（）。A 1 B 2 C 3 D 4【解答】D 二叉树的

19、前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A 空或只有一个结点 B 高 度等于其结点数 C 任一结点无左孩子 D 任一结点无右孩子【解答】B【分析】此题注意是序列正好相反，则左斜树和右斜树均满足条件。线索二叉树中某结点 R 没有左孩子的充要条件是（）。A R.lchild=NULL B R.ltag=0 C R.ltag=1 D R.rchild=NULL【解答】C【分析】线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左 标志是否为 1。一个高度为 h 的满二叉树共有 n 个结点，其中有 m 个叶子结点，则有（）成立。A n=h+m B h+m=2n

20、C m=h-1 D n=2m-1【解答】D【分析】满二叉树中没有度为 1 的结点，所以有 m 个叶子结点，则度为 2 的结点个数为 m-1（比如 叶子为 8,则依次往上是 4,2,1 个节点,等比数列个数为 m-1.）。设森林中有 4 棵树，树中结点的个数依次为 n1、n2、n3、n4，则把森林转换成二叉树后，其根结点的右 子树上有（）个结点，根结点的左子树上有（）个结点。A n1-1 B n1 C n1+n2+n3 D n2+n3+n4 10）讨论树、森林和二叉树的关系，目的是为了（）。A 借助二叉树上的运算方法去实现对树的一些 以二叉链表为存储结构，在二叉树中删除以值 x 为根结点的子树。

21、运算 B 将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题 C 将树、森林转 换成二叉树 D 体现一种技巧，没有什么实际意义 3.判断题 在线索二叉树 中，任一结点均有指向其前趋和后继的线索。【解答】错。某结点是否有前驱或后继的 线索，取决于该结点的标志域是否为 1。在二叉树的前序遍历序列中，任意一个结点均处在其子女的前面。二叉树是度为 2 的树。【解答】错。二叉树和树是两种不同的树结构，例如，左斜树 由树转换成二叉树，其根结点的右子树总是空的。【解答】对。因为根结点无兄弟结点。用一维数组存储二叉树时，总是以前序遍历存储结点。【解答】错。二叉树的顺序存储结构是按层序 存储

22、的，一般适合存储完全二叉树。4.证明：对任一满二叉树，其分枝数 B=2(n0-1)。(其中，nO 为终端结点数)已知二叉树的中序和后序序列分别为 CBEDAFIGH 和 CEDBIFHGA，试构造该二叉树。8.对给定的一组权值 W=(5,2,9,11,8,3,7)，试构造相应的哈夫曼树，并计算它的带权路径长 度。带权路径长度为：WPL=2X 4+3 X4+5 X3+7 X3+8 X3+9 X2+11 X2=120 9.已知某字符串 S 中共有 8 种字符，各种字符分别出现 2 次、1 次、4 次、5 次、7 次、3 次、4 次和 9 次，对该 字符串用 0,1 进行前缀编码,问该字符串的编码至少有多少位。【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图 5-14 所示。其带权路径长度=2X5+1 X5+3X4+5X3+9X2+4X3+4X3+7X2=98，所以，该字符串的编码长度至少为 98 位。10 算法设计 以二叉链表为存储结构，编写算法求二叉树中结点 x 的双亲。