《数据结构-王红梅-课后答案.pdf》由会员分享，可在线阅读，更多相关《数据结构-王红梅-课后答案.pdf（64页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、目 录第 1 章 绪 论.2第 2 章线性表.8第 3 章特殊线性表栈、队列和串.16第 4 章广义线性表多维数组和广义表.23第 5 章树和二叉树.27第 6 章 图.37第 7 章查找技术.45第 8 章排序技术.53第 9 章索引技术.61第1章 绪 论课后习题讲解1.填空（1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。【解答】集合，线性结构，树结构，图
2、结构（4）数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）,【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系算法具有五个特性，分 别 是（）、（）、（）、（）、（）。【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性（6）算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。【解答】自然语言，程序设计语言，流程图，伪代码，伪代码在一般情况下，一个算法的时间复杂度是（）的函数。【解答】问题规模设待处理问题的规模为n,若一个算法的时间复杂度为一个常数，则表示成数量级的形式 为（），若为n*log25n
3、,则表示成数量级的形式为（）。【解答】0（1）,O（nlog2n）【分析】用大0记号表示算法的时间复杂度，需要将低次第去掉，将最高次嘉的系数去掉。2.选择题（1）顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系 是 由（）表示的。A线性结构B非线性结构C存储位置D指针【解答】C,D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中 个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产
4、；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。A树B图C线 性 表D集合【解答】B【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。算 法 指 的 是（）。A对特定问题求解步骤的一种描述，是指令的有限序列。B计算机程序C解决问题的计算方法D数据处理【解答】A【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。（4）下 面（）不是算法所必须具备的特性。A有 穷 性B确 切 性C高 效 性D可行性【解答】C【分析】高效性是好算法应具备的特性。算法分析的目的是（）,算法分析的两个主要
5、方面是（）。A找出数据结构的合理性B研究算法中输入和输出的关系C分析算法的效率以求改进D分析算法的易读性和文档性E空间性能和时间性能F正确性和简明性G可读性和文档性H数据复杂性和程序复杂性【解答】C,E3.判断题算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。【解答】错。时间复杂度要通过算法中基本语句执行次数的数量级来确定。每种数据结构都具备三个基本操作：插入、删除和查找。【解答】错。如数组就没有插入和删除操作。此题注意是每种数据结构。所谓数据的逻辑结构指的是数据之间的逻辑关系。【解答】错。是数据之间的逻辑关系的整体。(4)逻辑结构与数据元素本身的内容和形式无关。【解答】对。因此逻辑
6、结构是数据组织的主要方面。基于某种逻辑结构之上的基本操作，其实现是唯一的。【解答】错。基本操作的实现是基于某种存储结构设计的，因而不是唯一-的。4.分析以下各程序段，并用大0记号表示其执行时间。【解答】基本语句是k=基本*i,共执行了 n-2次，所以T(n)=O(n).基本语句是k=k+10*i,共执行了 n次，所以T(n)=O(n)。分析条件语句，每循环一次，i+j整体加1,共循环n次，所以T(n)=O(n)。(4)设循环体共执行T(n)次，每循环一次，循环变量y加1,最终T(n)=v，即：(T(n)+l)2W n,所以 T(n)=O(n 1/2)。x+是基本语句，所以5.设有数据结构(D,
7、R),其中 D=1,2,3,4,5,6,R=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)。试画出其逻辑结构图并指出属于何种结构。【解答】其逻辑结构图如图1-3所示，它是一种图结构。6.为整数定义个抽象数据类型，包含整数的常见运算，每个运算对应个基本操作，每个基本操作的接口需定义前置条件、输入、功能、输出和后置条件。【解答】整数的抽象数据类型定义如下：ADT integerData整数a：可以是正整数(1,2,3,)、负整数(口 23)和零OperationConstructor前置条件：整数a不存在输入：一个整数b功能：构造一个与输入值相同的整
8、数输出：无后置条件：整数a具有输入的值Set前置条件：存在一个整数a输入：一个整数b功能：修改整数a 的值，使之与输入的整数值相同输出：无后置条件：整数a 的值发生改变Add前置条件：存在一个整数a输入：一个整数b功能：将整数a 与输入的整数b 相加输出：相加后的结果后置条件：整数a 的值发生改变Sub前置条件：存在一个整数a输入：一个整数b功能：将整数a 与输入的整数b 相减输出：相减的结果后置条件：整数a 的值发生改变Multi前置条件：存在一个整数a输入：一个整数b功能：将整数a 与输入的整数b 相乘输出：相乘的结果后置条件：整数a 的值发生改变Div前置条件：存在一个整数a输入：一个整
9、数b功能：将整数a 与输入的整数b 相除输出：若整数b 为零，则抛出除零异常，否则输出相除的结果后置条件：整数a 的值发生改变Mod前置条件：存在一个整数a输入：一个整数b功能：求当前整数与输入整数的模，即正的余数输出：若整数b 为零，则抛出除零异常，否则输出取模的结果后置条件：整数a 的值发生改变Equal前置条件：存在一个整数a输入：一个整数b功能：判断整数a 与输入的整数b 是否相等输出：若相等返回1,否则返回0后置条件：整数a 的值不发生改变endADT7.求多项式A(x)的算法可根据下列两个公式之一来设计：A(x)=anxn+an-lxn-l+-+alx+aO(2)A(x)=(anx
10、+an-l)x+al)x)+aO根据算法的时间复杂度分析比较这两种算法的优劣。【解答】第二种算法的时间性能要好些。第种算法需执行大量的乘法运算，而第二种算法进行了优化，减少了不必要的乘法运算。8.算法设计(要求：算法用伪代码和C+描述，并分析最坏情况下的时间复杂度)对一个整型数组AnJ设计一个排序算法。【解答】卜面是简单选择排序算法的伪代码描述。下面是简单选择排序算法的C+描述。分析算法，有两层嵌套的fo r循环，所以，。找出整型数组An中元素的最大值和次最大值。【解答】算法的伪代码描述如下：算法的C+描述如下:分析算法，只有一层循环，共执行n-2次，所以，T(n)=O(n)学习自测及答案1.
11、顺序存储结构的特点是(),链接存储结构的特点是()。【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，用指示元素存储地址的指针表示数据元素之间的逻辑关系。2.算法在发生非法操作时可以作出处理的特性称为()。【解答】健壮性3.常见的算法时间复杂度用大0记号表示为：常数阶()、对数阶()、线 性 阶()、平方阶()和指数阶()。【解答】0(1),O(log2n),0(n),0(n2),0(2n)4.将下列函数按它们在n时的无穷大阶数，从小到大排列。n,n-n3+7n5,nlogn,2n/2,n3,Iog2n,nl/2+log2n,(3/2)n,n!,n2+log2n【解答】Iog2n
12、,nl/2+log2n,n,nlog2n,n2+log2n,n3,n-n3+7n5,2n/2,(3/2)n,n!5.试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。【解答】数据结构是指相互之间存在一定关系的数据元素的集合。而抽象数据类型是指一个数据结构以及定义在该结构上的一组操作。程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的总称。抽象数据类型可以看成是对数据类型的一种抽象。6.对下列用二元组表示的数据结构，试分别画出对应的逻辑结构图，并指出属于何种结构。(1)A=(D,R),其中 D=al,a2,a3,a4,R=B=(D,R),其中 D=a,b,c,
13、d,e,f,R=C=(D,R),其中 D=a,b,c,d,e,f,R=,(4)D=(D,R),其中 D=1,2,3,4,5,6,R=(1,2),(1,4),(2,3),(2,4),(3,4),(3,5),(3,6),(4,6)【解答】属于集合，其逻辑结构图如图l-4(a)所示；属于线性结构，其逻辑结构图如图l-4(b)所示；属于树结构，其逻辑结构图如图L4(c)所示；(4)属于图结构，其逻辑结构图如图l-4(d)所示。7.求下列算法的时间复杂度。count=0;x=l;while(x x*=2;count+;)return count;【解答】O(log2n)第2章线性表课后习题讲解1.填空（
14、1）在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。【解答】表长的一半，表长，该元素在表中的位置顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的存储地址是（）。【解答】108【分析】第5个元素的存储地如:=第1个元素的存储地址+（5-1）X2=108设单链表中指针p指向结点A,若要删除A的后继结点（假 设A存在后继结点），则需修改指针的操作 为（）【龟 帛答】p-next=（p-next）-next（4）单链表中设置头结点的作用是（）。【解答】为了运算方便【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。非
15、空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满 足（）。【解答】p-next=head【分析】如图2-8所示。在由尾指针rear指示的单循环链表中，在表尾插入个结点s的操作序列是（）；删除开始结点的操作序列为（）。【解答】s-next=rear-next;rear-next=s;rear=s;q=rear-next-next;rear-next-next=q-next;delete q;【分析】操作示意图如图2-9所示：一 个 具 有n个结点的单链表,在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为X的结点后插入个新结点的时间复杂度为（）。【解答】0（1）,0（
16、n）【分析】在 P 所指结点后插入一个新结点只需修改指针，所以时间复杂度为。口）：而在给定值为x 的结点后插入一个新结点需要先查找值为x 的结点，所以时间复杂度为0（n）。（8）可由一个尾指针唯一确定的链表有（）、（）、（）。【解答】循环链表，循环双链表，双链表2.选择题线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。A 随机存取B 顺序存取C 索引存取D 散列存取【解答】A,B【分析】参见2 2 1。线性表采用链接存储时，其 地 址（）。A 必须是连续的B 部分地址必须是连续的C 定是不连续的D 连续与否均可以【解答】D【分析】线性表的链接存储是用一组任意
17、的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。单循环链表的主要优点是（）。A 不再需要头指针了B 从表中任一结点出发都能扫描到整个链表；C 已知某个结点的位置后，能够容易找到它的直接前趋；D 在进行插入、删除操作时，能更好地保证链表不断开。【解答】B（4）链表不具有的特点是（）。A 可随机访问任一元素B 插入、删除不需要移动元素C 不必事先估计存储空间D 所需空间与线性表长度成正比【解答】A若某线性表中最常用的操作是取第i 个元素和找第i 个元素的前趋，则 采 用（）存储方法最节省时间。A 顺 序 表 B 单 链 表 C 双 链 表 D
18、单循环链表【解答】A【分析】线性表中最常用的操作是取第i 个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。（6）若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（）存储方法最节省时间。A单 链 表B带头指针的单循环链表C双 链 表D带尾指针的单循环链表【解答】D【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链
19、表中删除第一个结点，其时间性能是0（1）,所以，答案是D。若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方法最节省运算时间。A单 链 表B循环双链表C单循环链表D带尾指针的单循环链表【解答】B【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点的前驱结点的地址，所以，带尾指针的单循环链表不合适，而循环双链表满足条件。（8）在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。A 0 B 0（n）C 0（n2）D O（nlog2n）【解答】B【分析】首先应
20、顺序查找新结点在单链表中的位置。（9）对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（A。B 0（n）C 0（n2）D O（nlog2n）【解答】C【分析】该算法需要将n个元素依次插入到有序单链表中，而插入每个元素需0（n）。（1 0）使用双链表存储线性表，其优点是可以（）。A提高查找速度B更方便数据的插入和删除C节约存储空间D很快回收存储空间【解答】B【分析】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节约存储空间，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，所以，其插入和删除操作更加方便。(11)在一个
21、单链表中，已知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 和 p 之间插入新结点，所以，不用考虑修改指针的顺序。在循环双链表的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
22、;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【分析】在链表中，对指针的修改必须保持线性表的逻辑关系，否则，将违背线性表的逻辑特征，图 2-10给出备选答案C 和 D 的图解。3.判断题线性表的逻辑顺序和存储顺序总是一致的。【解答】错。顺序表的逻辑顺序和存储顺序一致，链表的逻辑顺序和存储顺序不一定一致。线性表的顺序存储结构优于链接存储结构。【解答】错。两种存储结构各有优缺点。设 p,q 是 指 针,若 p
23、=q,则*p=*q。【解答】错。p=q只能表示p 和 q 指向同一起始地址，而所指类型则不一定相同。(4)线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。【解答】错。每个元素最多只有一个直接前驱和一个直接后继，第一个元素没有前驱，最后一个元素没有后继。在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。【解答】错。要找到该结点的地址，必须从头指针开始查找，所以单链表是顺序存取结构。4.请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中
24、的元素。如 果 n 个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。描述一个城市的设计和规划。【解答】顺序表的优点：无需为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速地存取表中任一位置的元素(即随机存取)。顺序表的缺点：插入和删除操作需移动大量元素；表的容量难以确定；造成存储空间的“碎片”。单链表的优点：不必事先知道线性表的长度；插入和删除元素时只需修改指针，不用移动元素。单链表的缺点：指针的结构性开销；存取表中任意元素不方便，只能进行顺序存取。应选用顺序存储结构。因为顺序表是随机存取结构，单链表是顺序存取结构。本题很少进行插入和删除操作，所以空间变化不大，且需要快速存
25、取，所以应选用顺序存储结构。应选用链接存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。应选用链接存储结构。因为一个城市的设计和规划涉及活动很多，需要经常修改、扩充和删除各种信息,才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。5.算法设计设计一个时间复杂度为0(n)的算法，实现将数组An中所有元素循环右移k 个位置。【解答】算法思想请参见主教材第一章思想火花。下面给出具体算法。分析算法，第一次调用Reverse函数的时间复杂度为0(k),第二次调用Reverse函数的时间复杂度为O(n-k),第三次调用Reverse函数的时间复杂度为0(n),所以，总的时间复杂度
26、为0(n)。已知数组An中的元素为整型，设计算法将其调整为左右两部分,左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为0(n)。【解答】从数组的两端向中间比较，设置两个变量i 和 j,初始时i=0,j=n-L 若 Ai为偶数并且Aj为奇数，则将Ai与 Aj交换。具体算法如卜：分析算法，两层循环将数组扫描遍，所以，时间复杂度为0(n)。试编写在无头结点的单链表上实现线性表的插入操作的算法，并和带头结点的单链表上的插入操作的实现进行比较。【解答】参见2.2.3。(4)试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。【解答】顺序表的逆置，即是将对称元素交换，设顺序表
27、的长度为le n g th,则将表中第i个元素与第length-i-1个元素相交换。具体算法如下：单链表的逆置请参见2 2 4算法2-4和算法2-6。假设在长度大于1的循环链表中，即无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前趋结点。【解答】利用单循环链表的特点，通过指针s可找到其前驱结点r以及r的前驱结点p,然后将结点r删除，如图2-11所示，具体算法如下：(6)已知一单链及中的数据元素含有三类字符：字母、数字和其他字符。试编写算法，构造三个循环链表，使每个循环链表中只含同一类字符。【解答】在单链表A中依次取元素，若取出的元素是字母，把它插入到字母链表B中，若取
28、出的元素是数字，则把它插入到数字链表D中，直到链表的尾部，这样表B,D,A中分别存放字母、数字和其他字符。具体算法如下：设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。【解答】从头到尾扫描单链表，若当前结点的元素值与后继结点的元素值不相等，则指针后移；否则删除该后继结点。具体算法如下:（8）判断带头结点的双循环链表是否对称。【解答】设工作指针p 和 q 分别指向循环双链表的开始结点和终端结点，若结点p 和结点q的数据域相等，则工作指针p 后移，工作指针q 前移，直到指针p 和指针q 指向同一结点（循环双链表中结点个数为奇数），或结点q 成为结点P 的 前 驱（循环双链表中
29、结点个数为偶数）。如图2-12所示。学习自测及答案1.已知一维数组A 采用顺序存储结构，每个元素占用4 个存储单元，第 9 个元素的地址为1 4 4,则第一个元素的地址是（）。A 108 B 180 C 176 D 112【解答】D2.在长度为n 的线性表中查找值为x 的数据元素的时间复杂度为：（）。AO（0）BO（l）CO（n）DO（n2）【解答】C3.在一个长度为n 的顺序表的第i（l W n+l）个元素之前插入一个元素，需向后移动（）个元素，删除第 i（lW iW n）个元素时，需向前移动（）个元素。【解答】n-i+1,n-i4.在单链表中，除了头结点以外，任一结点的存储位置由（）指示。
30、【解答】其前趋结点的指针域5.当线性表采用顺序存储结构时，其主要特点是（）。【解答】逻辑结构中相邻的结点在存储结构中仍相邻6.在双链表中，每个结点设置了两个指针域，其 中 个 指 向（）结点，另一个指向（）结点。【解答】前驱，后继7.设 A 是一个线性表（a l,a 2,an）,采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在a i与 ai+1之 间（lnext;B x=top-data;C top=top-next;x=top-data;D x=top-data;top=top-next;【解答】D4.设元素1,2,3,P,A 依次经过一个栈，进栈
31、次序为123PA,在栈的输出序列中，有哪些序列可作为C+程序设计语言的变量名。【解答】PA321,P3A21,P32A1,P321A,AP3215.设 S=l_am_a_teacther,其长度为（）。【解答】156.对于栈和队列，无论它们采用顺序存储结构还是链接存储结构，进行插入和删除操作的时间复杂度都是()。【解答】。7.如果进栈序列为A、B、C、D,则可能的出栈序列是什么？答：共 14 种，分另I 是：ABCD,ABDC,ACBD,ACDB,ADCB,BACD,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA8.简述队列和栈这两种数据结构的相同点和不同点。【
32、解答】相同点：它们都是插入和删除操作的位置受限制的线性表。不同点：栈是限定仅在表尾进行插入和删除的线性表，是后进先出的线性表，而队列是限定在表的一端进行插入，在另一端进行删除的线性表，是先进先出的线性表。9.利用两个栈S 1和S 2模拟一个队列，如何利用栈的运算实现队列的插入和删除操作，请简述算法思想。【解答】利用两个栈S1和S 2模拟一个队列，当需要向队列中插入一个元素时，用S 1来存放已输入的元素，即通过向栈S1执行入栈操作来实现；当需要从队列中删除元素时，则将S 1中元素全部送入到S 2中,再从S 2中删除栈顶元素，最后再将S 2中元素全部送入到S 1中；判断队空的条件是：栈S1和S 2
33、同时为空。10.设计算法把一个十进制整数转换为二至九进制之间的任一进制数输出。【解答】算法基于原理：N=(N div d)Xd+N mod d(d iv为整除运算，m od为求余运算)。11.假设一个算术表达式中可以包含三种括号：圆括号“(”和“)”，方 括 号 和以及花括号“和“，且这三种括号可按任意的次序嵌套使用。编写算法判断给定表达式中所含括号是否配对出现。【解答】假设表达式已存入字符数组An中，具体算法如下：第4章广义线性表多维数组和广义表课后习题讲解1.填空(1)数组通常只有两种运算：()和()，这决定了数组通常采用()结构来实现存储。【解答】存取，修改，顺序存储【分析】数组是一个具
34、有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。二维数组A 中行下标从10到 2 0,列下标从5 到 1 0,按行优先存储，每个元素占4 个存储单元，A10的存储地址是1000，则元素A1510的存储地址是()。【解答】1140【分析】数组A 中每行共有6 个元素，元素A1510的前面共存储了(15-10)X6+5个元素,每个元素占4个存储单元，所以，其存储地址是1000+140=1140。设 有 一 个 10阶的对称矩阵A 采用压缩存储，A为第一个元素，其存储地址为d,每个元素占1 个存储单元，则元素A8的存储地址
35、为()。【解答】d+41【分析】元素A的前面共存储了(1+2+8)+5=41个元素。(4)稀疏矩阵一般压缩存储方法有两种，分 别 是()和()。【解答】三元组顺序表，十字链表广义表(a),(b),c),(d)的长度是(),深 度 是()，表 头 是(),表 尾 是()。【解答】3,4,(a),(b),c),(d)(6)已知广义表LS=(a,(b,c,d),e),用 Head和 Tail函数取出LS中原子b 的运算是()。【解答】Head(Head(Tail(LS)2.选择题 二维数组A 的每个元素是由6 个字符组成的串，行下标的范围从08,列下标的范围是从 09,则存放 A 至少需要()个字节
36、，A 的第8 列和第5 行共占()个字节，若 A 按行优先方式存储，元素A的起始地址与当A 按列优先方式存储时的()元素的起始地址一致。A90 B 180 C 240 D 540 E 108 F 114 G 54H A85 I A310 J A58 K A49【解答】D,E,K【分析】数组A为9行10歹 共 有9 0个元素，所以，存放A至少需要90X6=540个存储单元，第8列和第5行共有18个元素(注意行列有一个交叉元素)，所以，共占108个字节，元素A按行优先存储的起始地址为d+8X10+5=d+85,设 元 素 按 列 优 先 存 储 的 起 始 地 址 与 之 相 同，则d+jX9+i
37、=d+85,解此方程，得i=4,j=9。将数组称为随机存取结构是因为()A数组元素是随机的B对数组任一元素的存取时间是相等的C随时可以对数组进行访问D数组的存储结构是不定【解答】B下面的说法中，不正确的是()A数组是一种线性结构B数组是一种定长的线性结构C除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等D数组的基本操作有存取、修改、检索和排序等，没有插入与删除操【解答】C【分析】数组属于广义线性表，数组被创建以后，其维数和每维中的元素个数是确定的，所以，数组通常没有插入和删除操作。对特殊矩阵采用压缩存储的目的主要是为了()A表达变得简单B对矩阵元素的存取变得简单C去掉矩阵中的多
38、余元素D减少不必要的存储空间【解答】D【分析】在特殊矩阵中，有很多值相同的元素并且他们的分布有规律，没有必要为值相同的元素重复存储。下 面()不属于特殊矩阵。A对角矩阵B三角 矩 阵C稀疏矩阵D对称矩阵【解答】C(6)若广义表A满 足Head(A)=Tail(A),则 人 为()A()B()C(),()D(),(),()【解答】B下面的说法中，不正确的是()A广义表是一种多层次的结构B广义表是一种非线性结构C广义表是一种共享结构D广义表是一种递归【解答】B【分析】从各层元素各自具有的线性关系讲，广义表属于线性结构。(8)下面的说法中，不正确的是()A对称矩阵只须存放包括主对角线元素在内的下(或
39、上)三角的元素即可。B对角矩阵只须存放非零元素即可。C稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。D稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储【解答】D【分析】稀疏矩阵中大量值为零的元素分布没有规律，因此采用三元组表存储。如果零元素的分布有规律，就没有必要存储非零元素的行号和列号，而需要按其压缩规律找出相应的映象函数。3.判断题数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。【解答】错。例如二维数组可以看成是数据元素为线性表的线性表。使用三元组表存储稀疏矩阵的元素，有时并不能节省存储空间。【解答】对。因为三元组表除了存储非零元素值外
40、，还需要存储其行号和列号。稀疏矩阵压缩存储后，必会失去随机存取功能。【解答】对。因为压缩存储后，非零元素的存储位置和行号、列号之间失去了确定的关系。线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。【解答】对。若一个广义表的表头为空表，则此广义表亦为空表。【解答】错。如广义表L=(),(a,b)的表头为空表，但L不是空表。4.一个稀疏矩阵如图4-4所示，写出对应的三元组顺序表和十字链表存储表示。【解答】对应的三元组顺序表如图4-5所示，卜字链表如图4-6所示。5.已知A为稀疏矩阵，试从空间和时间角度比较采用二维数组和三元组顺序表两种不同的存储结构完成求运算的
41、优缺点。【解答】设稀疏矩阵为m行n歹I，如果采用二维数组存储，其空间复杂度为O(m Xn)；因为要将所有的矩阵元素累加起来，所以，需要用一个两层的嵌套循环，其时间复杂度亦为O(m Xn)。如果采用三元组顺序表进行压缩存储，假设矩阵中有t个非零元素，其空间复杂度为O(t),将所有的矩阵元素累加起来只需将三元组顺序表扫描一遍，其时间复杂度亦为O(t)。当t m X n时，采用三元组顺序表存储可获得较好的时、空性能。6.设某单位职工工资表ST由“工资”、“扣除”和“实发金额”三项组成，其中工资项包括“基本工资”、“津贴”和“奖金”，扣除项包括“水”、电”和“煤气”。请用广义表形式表示所描述的工资表S
42、 T,并用表头和表尾求表中的“奖金”项；画出该工资表ST的存储结构。【解答】ST=(基本工资，津贴，奖金)，(水，电，煤气)，实发金额)Head(Tail(Tail(Head(ST)=奖金 工资表ST的头尾表示法如图4-7所示。7.若在矩阵A中存在一个元素ai,j(0 W i 0）个（）的集合，每个集合都是根结点的子树。【解答】有且仅有一个，互不相交树中某结点的子树的个数称为该结点的（），子树的根结点称为该结点的（）,该结点称为其子树根结 点 的（）o【解答】度，孩子，双亲 一 棵二叉树的第i（i 2 l）层最多有（）个结点；一棵有n（n0）个结点的满二叉树共有（）个叶子结 点 和（）个非终端
43、结点。【解答】2i-l,（n+l）/2,（n-l）/2【分析】设满二叉树中叶子结点的个数为n O,度为2的结点个数为n 2,由于满二叉树中不存在度为1的结点,所以 n=nO+n2；由二叉树的性质 nO=n2+l,得 nO=（n+l）/2,n2=（n-l）/2（4）设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值 是（），最小 值 是（）。【解答】2h-l,2h-l【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。深 度 为k的二叉树中，所含叶子的个数最多为（）。【解答】2k-l【分析】在满二叉树中叶子结点的个数达到最多。（6）具 有100个结点
44、的完全二叉树的叶子结点数为（）。【解答】50【分析】100个结点的完全二叉树中最后一个结点的编号为1 0 0,其双亲即最后一个分支结点的编号为50,也就是说，从编号51开始均为叶子。已知一棵度为3 的树有2 个度为1 的结点，3 个度为2 的结点，4 个度为3 的结点。则该树 中 有（）个叶子结点。【解答】12【分析】根据二叉树性质3 的证明过程，有 n0=n2+2n3+l（n0、n2、n 3 分别为叶子结点、度为2 的结点和度为3 的结点的个数）。（8）某二叉树的前序遍历序列是ABCDEFG,中序遍历序列是CBDAFGE,则其后序遍历序列是（）。【解答】CDBGFEA 分析根据前序遍历序列和
45、后序遍历序列将该二叉树构造出来。（9）在具有n 个结点的二叉链表中，共 有（）个指针域，其 中（）个指针域用于指向其左右孩子，剩下的（）个指针域则是空的。【解答】2n,n-1,n+1（10）在有n 个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）【解答】n,n-1【分析】n-1个分支结点是经过n-1次合并后得到的。2.选择题 如 果 结 点 A 有 3 个兄弟，B 是 A 的双亲，则结点B 的 度 是（）。A 1 B 2 C 3 D 4【解答】D 设二叉树有n 个结点，则其深度为（）。A n-1 B n C+1 D 不能确定【解答】D【分析】此题并没有指明是完全二叉树，则其深度最多是
46、n,最 少 是+1。二叉树的前序序列和后序序列正好相反，则该二叉树一 定 是（）的二叉树。A空或只有一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子【解答】B【分析】此题注意是序列正好相反，则左斜树和右斜树均满足条件。（4）线索二叉树中某结点R没有左孩子的充要条件是（）。A R.lchild=NULL B R.ltag=O C R.ltag=l D R.rchild=NULL【解答】C【分析】线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左标志是否为1。深 度 为k的完全二叉树至少有（）个结点，至 多 有（）个结点，具 有n个结点的完全二叉树按层序从1开
47、始编号，则编号最小的叶子的序号是（）。A 2k-2+l B 2k-l C2k-1 D 2 k-l-1E 2k+l F 2k+l-1 G 2k-1+1 H 2k【解答】B,C,A【分析】深度为k的完全二叉树最少结点数的情况应是第k层上只有1个结点，最多的情况是满二叉树，编号最小的叶子应该是在结点数最少的情况下，叶子结点的编号。（6）一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则 有（）成立。A n=h+m B h+m=2n C m=h-l D n=2m-l【解答】D【分析】满二叉树中没有度为1的结点，所以有m个叶子结点,则度为2的结点个数为m-lo任何一棵二叉树的叶子结点在前序、中序
48、、后序遍历序列中的相对次序（）。A肯定不发生改变B肯定发生改变C不能确定D有时发生变化【解答】A【分析】三种遍历次序均是先左子树后右子树。（8）如果 是由有序树T转换而来的二叉树，那么T中结点的前序序列就是T中结点的（）序列，T中结点的后序序列就是T 中结点的（）序列。A前 序B中 序C后 序D层序【解答】A,B（9）设森林中有4棵树，树中结点的个数依次为n l、n2、n3、n 4,则把森林转换成二叉树后，其根结点的右子树匕有（）个结点，根结点的左子树上有（）个结点。A nl-1 B nl C nl+n2+n3 D n2+n3+n4【解答】D,A【分析】由森林转换的二叉树中，根结点即为第一棵树
49、的根结点，根结点的左子树是由第一棵树中除了根结点以外其余结点组成的，根结点的右子树是由森林中除第一棵树外其他树转换来的。（10）讨论树、森林和二叉树的关系，目的是为了（）。A借助二叉树上的运算方法去实现对树的些运算B将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题C将树、森林转换成二叉树D体 现 种 技 巧，没有什么实际意义【解答】B3.判断题在线索二叉树中，任一结点均有指向其前趋和后继的线索。【解答】错。某结点是否有前驱或后继的线索，取决于该结点的标志域是否为1。在二叉树的前序遍历序列中，任意一个结点均处在其子女的前面。【解答】对。由前序遍历的操作定义可知。二叉树是度为
50、2的树。【解答】错。二叉树和树是两种不同的树结构，例如，左斜树是一棵二叉树，但它的度为1。由树转换成二叉树，其根结点的右子树总是空的。【解答】对。因为根结点无兄弟结点。用一维数组存储二叉树时，总是以前序遍历存储结点。【解答】错。二叉树的顺序存储结构是按层序存储的，一般适合存储完全二叉树。4.证明：对任一满二叉树，其分枝数B=2（n0-l）。（其中，n0为终端结点数）【解答】因为在满二叉树中没有度为1的结点，所以有:n=nO+n2设B为树中分枝数，则n=B+1所以B=nO+n2-l再由二叉树性质：n0=n2+l代入上式有：B=nO+nO-l-l=2(nO_l)5.证明：已知一棵二叉树的前序序列和