数据结构c++版课后习题解析.doc

第 1章 绪 论1、1 本章导学1、2 习题解析2第 2章 线性表92、本章导学2、习题解析10第 3章栈与队列13、1本章导学193、2 习题解析0第4 章 字符串与多维数组264、1 本章导学4、2 习题解析2第 5 章 树与二叉树25、1 本章导学325、 习题解析33第 6 章图436、1 本章导学436、 习题解析44第 7 章 查找技术56、 本章导学56、2习题解析第 8 章 排序技术678、1 本章导学678、习题解析68第 章索引技术789、1 本章导学78、2 习题解析78第 1 章绪 论、 本章导学、 知识结构图 本章得知识结构如图1-1所示，其中第二层得椭圆代表本章得学习主线。数据数据元素数据结构抽象数据类型逻辑结构数据结构得分类存储结构常用存储方法算法算法特性评价算法描述算法问题规模基本语句时间复杂度大O记号图1-1 知识结构图绪 论数据结构算 法基本概念逻辑结构存储结构基本概念算法分析关 系2、学习要点对本章得学习要从两条主线出发,一条主线就是数据结构,包括数据结构得相关概念及含义,另一条主线就是算法,包括算法得相关概念、描述方法以及时间复杂度得分析方法。在学习数据结构时要抓住两个方面：逻辑结构与存储结构，并注意把握二者之间得关系。在学习算法时，要以算法得概念与特性为基本点，并在以后得学习中注意提高算法设计得能力。对于算法时间性能得分析，要将注意力集中在增长率上,即基本语句执行次数得数量级，在设计算法时，养成分析算法时间性能得习惯，进而有效地改进算法得效率。1、2 习题解析1、 填空（1)( )就是数据得基本单位，在计算机程序中通常作为一个整体进行考虑与处理.【解答】数据元素（)（ ）就是数据得最小单位，（ )就是讨论数据结构时涉及得最小数据单位。【解答】数据项，数据元素【分析】数据结构指得就是数据元素以及数据元素之间得关系.(3)从逻辑关系上讲，数据结构主要分为( )、( ）、（ ）与（ ）。【解答】集合，线性结构，树结构、图结构(4)数据得存储结构主要有（ ）与（ ）两种基本方法，不论哪种存储结构，都要存储两方面得内容:( ）与（ ）。【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间得关系(）算法具有五个特性，分别就是（ ）、( ）、( ）、( ）、( )。【解答】有零个或多个输入,有一个或多个输出，有穷性,确定性,可行性(6）算法得描述方法通常有( )、( )、( )与（ ）四种，其中，( )被称为算法语言。【解答】自然语言，程序设计语言，流程图，伪代码,伪代码（7）在一般情况下，一个算法得时间复杂度就是（ ）得函数。【解答】问题规模(8）设待处理问题得规模为n,若一个算法得时间复杂度为一个常数,则表示成数量级得形式为( )，若为log25n n,则表示成数量级得形式为( ）。【解答】(）,（ng2）【分析】用大记号表示算法得时间复杂度,需要将低次幂去掉，将最高次幂得系数去掉.2、 选择题(1）顺序存储结构中数据元素之间得逻辑关系就是由( ）表示得，链接存储结构中得数据元素之间得逻辑关系就是由（ )表示得。A 线性结构 B 非线性结构 C 存储位置 D 指针【解答】C,D【分析】顺序存储结构就就是用一维数组存储数据结构中得数据元素，其逻辑关系由存储位置（即元素在数组中得下标）表示;链接存储结构中一个数据元素对应链表中得一个结点,元素之间得逻辑关系由结点中得指针表示。（2)假设有如下遗产继承规则：丈夫与妻子可以相互继承遗产;子女可以继承父亲或母亲得遗产；子女间不能相互继承遗产。则表示该遗产继承关系得最合适得数据结构应该就是( )。A 树 B 图 C线性表 D 集合【解答】B【分析】将丈夫、妻子与子女分别作为数据元素,根据继承关系画出逻辑结构图如图2丈夫妻子子女n子女1图1-2 遗产继承逻辑结构图所示。(）计算机所处理得数据一般具有某种内在联系，这就是指（ ）。A 数据与数据之间存在某种关系 B 元素与元素之间存在某种关系C 元素内部具有某种结构 D 数据项与数据项之间存在某种关系【解答】B【分析】数据结构就是指相互之间存在一定关系得数据元素得集合，数据元素就是讨论数据结构时涉及得最小数据单位，元素内部各数据项一般不予考虑。(）对于数据结构得描述,下列说法中不正确得就是（ ）.A 相同得逻辑结构对应得存储结构也必相同B数据结构由逻辑结构、存储结构与基本操作三方面组成C 对数据结构基本操作得实现与存储结构有关D 数据得存储结构就是数据得逻辑结构得机内实现【解答】A【分析】相同得逻辑结构可以用不同得存储结构实现，一般来说，在不同得存储结构下基本操作得实现就是不同得，例如线性表可以顺序存储也可以链接存储，在顺序存储与链接存储结构下插入操作得实现截然不同.（5）可以用( ）定义一个完整得数据结构。A 数据元素 数据对象 C 数据关系 D抽象数据类型【解答】D【分析】抽象数据类型就是一个数据结构以及定义在该结构上得一组操作得总称。（)算法指得就是（ ）。A 对特定问题求解步骤得一种描述，就是指令得有限序列。B 计算机程序 C 解决问题得计算方法 D 数据处理【解答】A【分析】计算机程序就是对算法得具体实现；简单地说，算法就是解决问题得方法;数据处理就是通过算法完成得。所以,只有A就是算法得准确定义。（7)下面（ ）不就是算法所必须具备得特性.A 有穷性 B 确切性 高效性 可行性【解答】C【分析】高效性就是好算法应具备得特性。()算法分析得目得就是( )，算法分析得两个主要方面就是（ ）。A找出数据结构得合理性 B研究算法中输入与输出得关系 分析算法得效率以求改进 D 分析算法得易读性与文档性E 空间性能与时间性能 F 正确性与简明性 可读性与文档性 H 数据复杂性与程序复杂性【解答】,E3、 判断题 算法得时间复杂度都要通过算法中得基本语句得执行次数来确定。【解答】错。时间复杂度要通过算法中基本语句执行次数得数量级来确定。每种数据结构都具备三个基本操作:插入、删除与查找。【解答】错。如数组就没有插入与删除操作.此题注意就是每种数据结构. 所谓数据得逻辑结构指得就是数据之间得逻辑关系。【解答】错.就是数据之间得逻辑关系得整体。 逻辑结构与数据元素本身得内容与形式无关.【解答】对。因此逻辑结构就是数据组织得主要方面。 基于某种逻辑结构之上得基本操作，其实现就是唯一得。【解答】错。基本操作得实现就是基于某种存储结构设计得,因而不就是唯一得。4、 分析以下各程序段,并用大O记号表示其执行时间。 i = 1; k = 0; while (i = n) k = k + 10 * i;i+; i = 1; k = 0; do k = k + 10 * i;i+; while (i = n); y = 0; while (y + 1) *(y + 1) = n) y = y + 1; i = 1; j = 0;while (i + j j) j+; else i+; for (i = 1; i = n; i+) for (j = 1; j = i; j+) for (k = 1; k = j; k+) x+; 【解答】 基本语句就是=k+0i,共执行了n2次,所以T（n）=O(）。 基本语句就是=+1i，共执行了n次，所以(）=O(n)。 分析条件语句,每循环一次,+ 整体加1，共循环n次,所以（n)（n）。 设循环体共执行T(n）次，每循环一次,循环变量y加1,最终(）=y，即: （T（n）+1)2n，所以T(n)O(1/）。 +就是基本语句，所以 5.解答下列问题（）设有数据结构（D，R），其中D 1， 2, 3， 4, 5， ，R =（，2）,（, )，（2, ），(3， 4)，(3，5)，（3，6)，(， 5),（4， 6）。试画出其逻辑结构图并指出属于何种结构。142563图1-3 逻辑结构图【解答】其逻辑结构图如图3所示，它就是一种图结构.(2）为整数定义一个抽象数据类型，包含整数得常见运算,每个运算对应一个基本操作,每个基本操作得接口需定义前置条件、输入、功能、输出与后置条件.【解答】整数得抽象数据类型定义如下: intger ta 整数：可以就是正整数（, 2， 3，）、负整数(1， 2, 3, ）与零 perao onstructor 前置条件：整数a不存在 输入:一个整数 功能:构造一个与输入值相同得整数 输出：无 后置条件：整数a具有输入得值 St 前置条件:存在一个整数 输入：一个整数 功能：修改整数得值，使之与输入得整数值相同 输出:无 后置条件:整数a得值发生改变 dd 前置条件:存在一个整数a 输入:一个整数b 功能:将整数a与输入得整数相加 输出：相加后得结果 后置条件：整数a得值发生改变 Sub 前置条件:存在一个整数a 输入:一个整数b 功能：将整数与输入得整数相减 输出:相减得结果 后置条件:整数a得值发生改变 Mlti 前置条件:存在一个整数 输入：一个整数b 功能：将整数a与输入得整数相乘 输出：相乘得结果 后置条件:整数a得值发生改变 Div 前置条件:存在一个整数a 输入：一个整数b 功能：将整数a与输入得整数b相除 输出：若整数b为零,则抛出除零异常，否则输出相除得结果 后置条件：整数a得值发生改变 Mod 前置条件:存在一个整数a 输入：一个整数b 功能：求当前整数与输入整数得模,即正得余数 输出：若整数b为零,则抛出除零异常，否则输出取模得结果 后置条件：整数a得值发生改变 Equl 前置条件:存在一个整数a 输入：一个整数b 功能：判断整数a与输入得整数就是否相等 输出：若相等返回1，否则返回 后置条件:整数a得值不发生改变endADT（3)求多项式A（x）得算法可根据下列两个公式之一来设计:A(x）anxn+an1xn1+a1+a0 A（x）（anx+n-1)x+1）x）+0根据算法得时间复杂度分析比较这两种算法得优劣。【解答】第二种算法得时间性能要好些。第一种算法需执行大量得乘法运算,而第二种算法进行了优化,减少了不必要得乘法运算。(4）选择与评价数据结构得标准与方法就是什么?【解答】首先,对给定得实际问题可以建立不同得数据结构；其次，对于给定得数据结构，可以选择不同得存储实现，即采用不同得存储结构;再次，在给定数据结构与存储结构得条件下,对同一基本操作可以设计出不同算法。因此,数据得逻辑结构、存储结构与操作（特别就是基本操作）得实现这三者就是密切相关得.一般地,在建立数据结构时应该考虑以下三个方面： 确定表示问题所需得数据及其特性； 确定必须支持得基本操作，并度量每种操作所受得时、空资源限制，某些重要得操作，例如查找、插入与删除得资源限制通常决定了数据结构得选择;选择(或设计）最接近这些开销得数据结构。6、算法设计(要求：用伪代码与C+描述两种方法描述算法,并分析时间复杂度） 对一个整型数组An设计一个排序算法。【解答】下面就是简单选择排序算法得伪代码描述. 1、 对n个记录进行n-1趟简单选择排序: 1、1 在无序区i,n-1中选取最小记录,设其下标为index; 1、2 将最小记录与第i个记录交换; 下面就是简单选择排序算法得C+描述。void SelectSort(int r , int n) for (i = 0; i n - 1; i+) /对n个记录进行n-1趟简单选择排序 index = i; for (j = i + 1; j n; j+) /在无序区中选取最小记录 if (rj max,则Ai为最大值,原来得最大值为次最大值;2、2 否则,如果Ainmax,则最大值不变,Ai为次最大值;3、 输出最大值max,次最大值nmax; 算法得C+描述如下：void Max_NextMax(int A , int n, int & max, int & nmax)if (A0 = A1) max = A0; nmax = A1;else max = A1; nmax = A0; for (i = 2; i = max) nmax = max; max = Ai; else if (Ai nmax) nmax = Ai; cout最大值为:maxn次最大值为:nmaxnxt(pnext)nex 单链表中设置头结点得作用就是( )。【解答】为了运算方便【分析】例如在插入与删除操作时不必对表头得情况进行特殊处理。非空得单循环链表由头指针e指示，则其尾结点(由指针p所指）满足( ）。【解答】pnext=hed【分析】如图2-8所示。heada1a2an p图2-8 尾结点p与头指针head得关系示意图 在由尾指针rer指示得单循环链表中,在表尾插入一个结点s得操作序列就是( )；删除开始结点得操作序列为( ）。【解答】s-ext =ear-nx； rearex =s; rear =s; =arnexx； rar-nxt-nex=qnext； dete ;【分析】操作示意图如图29所示：a1a2an rear sq图2-9 带尾指针得循环链表中插入与删除操作示意图rear 一个具有n个结点得单链表，在指针p所指结点后插入一个新结点得时间复杂度为( );在给定值为x得结点后插入一个新结点得时间复杂度为( )。【解答】（），(n）【分析】在所指结点后插入一个新结点只需修改指针,所以时间复杂度为(1)；而在给定值为得结点后插入一个新结点需要先查找值为x得结点，所以时间复杂度为(n)。 可由一个尾指针唯一确定得链表有（ ）、( ）、( ）。【解答】循环链表，循环双链表，双链表、 选择题 线性表得顺序存储结构就是一种( )得存储结构，线性表得链接存储结构就是一种（ ）得存储结构。A随机存取 B顺序存取 C索引存取 D 散列存取【解答】A，B【分析】参见2、2、1。 线性表采用链接存储时，其地址（ ).A 必须就是连续得 B部分地址必须就是连续得C 一定就是不连续得 连续与否均可以【解答】【分析】线性表得链接存储就是用一组任意得存储单元存储线性表得数据元素,这组存储单元可以连续,也可以不连续,甚至可以零散分布在内存中任意位置。 单循环链表得主要优点就是( ). 不再需要头指针了 B从表中任一结点出发都能扫描到整个链表；C 已知某个结点得位置后,能够容易找到它得直接前趋；D 在进行插入、删除操作时,能更好地保证链表不断开.【解答】B 链表不具有得特点就是( )。 可随机访问任一元素 插入、删除不需要移动元素C 不必事先估计存储空间 D 所需空间与线性表长度成正比【解答】A 若某线性表中最常用得操作就是取第i 个元素与找第i个元素得前趋，则采用（ )存储方法最节省时间。A顺序表 B 单链表 C 双链表 单循环链表【解答】A【分析】线性表中最常用得操作就是取第 个元素，所以,应选择随机存取结构即顺序表,同时在顺序表中查找第i个元素得前趋也很方便.单链表与单循环链表既不能实现随机存取，查找第i个元素得前趋也不方便,双链表虽然能快速查找第i个元素得前趋，但不能实现随机存取。若链表中最常用得操作就是在最后一个结点之后插入一个结点与删除第一个结点，则采用（ )存储方法最节省时间。A 单链表 B 带头指针得单循环链表 双链表 D 带尾指针得单循环链表【解答】D【分析】在链表中得最后一个结点之后插入一个结点需要知道终端结点得地址，所以,单链表、带头指针得单循环链表、双链表都不合适，考虑在带尾指针得单循环链表中删除第一个结点，其时间性能就是O(1），所以,答案就是D 。 若链表中最常用得操作就是在最后一个结点之后插入一个结点与删除最后一个结点,则采用（ ）存储方法最节省运算时间. 单链表 B 循环双链表 单循环链表 D 带尾指针得单循环链表【解答】B【分析】在链表中得最后一个结点之后插入一个结点需要知道终端结点得地址，所以，单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点得前驱结点得地址，所以,带尾指针得单循环链表不合适,而循环双链表满足条件。 在具有n个结点得有序单链表中插入一个新结点并仍然有序得时间复杂度就是( ）。A O(1） （n) C (n） D O（nog2）【解答】【分析】首先应顺序查找新结点在单链表中得位置.对于n个元素组成得线性表，建立一个有序单链表得时间复杂度就是（ )。A O（1) BO（n） O（n） （nlo2n)【解答】C【分析】该算法需要将个元素依次插入到有序单链表中，而插入每个元素需O(n)。使用双链表存储线性表，其优点就是可以( ）。A提高查找速度 B更方便数据得插入与删除 节约存储空间 D很快回收存储空间【解答】B【分析】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域,显然不能节约存储空间,对于动态存储分配，回收存储空间得速度就是一样得。由于双链表具有对称性,所以，其插入与删除操作更加方便。 在一个单链表中,已知q所指结点就是p所指结点得直接前驱,若在q与之间插入s所指结点，则执行( )操作.A snext-ex; pnxt=； B qnext=s；snxt=p； p-x=s-xt； nex=； p-nx=s; net=q;【解答】B【分析】注意此题就是在与p之间插入新结点，所以，不用考虑修改指针得顺序。在循环双链表得所指结点后插入s所指结点得操作就是( ）。 next=;s-pro=p;pnext-rir=s； nex=p-next;Bpnext=s； netrior=s；spri=p; snxtp-et;C-prior=p； -netp-nxt; pnx=； p-nxt-pror=s;Dsprio=p； -next=-net; -extpror=s； p-next=s【解答】D【分析】在链表中，对指针得修改必须保持线性表得逻辑关系，否则，将违背线性表得逻辑特征，图-给出备选答案与D得图解。(a) 备选答案C操作示意图(第4步指针修改无法进行) (b) 备选答案D操作示意图 图2-10 双链表插入操作修改指针操作示意图sai-1aixpsai-1aixp(13）用数组存储静态链表，结点得ext域指向后继，工作指针j指向链中某结点，则后移得操作语句为（ ).A j = rj、nt B j = j = jext D j = ext【解答】A【分析】注意nex就是数组下标，因此排除C与D，对于备选答案B，假设工作指针指向某结点，则j+1不一定指向结点p得后继结点。（14）设线性表有n个元素,以下操作中,（ ）在顺序表上实现比在链表上实现得效率更高。A 输出第i(1in）个元素值 交换第1个与第2个元素得值 顺序输出所有个元素 D 查找与给定值相等得元素在线性表中得序号【解答】A【分析】在顺序表上输出第i(1in)个元素值需要O（1)时间，在链表上输出第i（1n）个元素值需要O（)时间；在顺序表上与链表上交换第1个与第2个元素得值都需要O（）时间;在顺序表上与链表上顺序输出所有个元素都需要O（）时间;在顺序表上与链表上查找与给定值相等得元素都需要进行顺序查找,需要O（n）时间。3、 判断题 线性表得逻辑顺序与存储顺序总就是一致得.【解答】错。顺序表得逻辑顺序与存储顺序一致，链表得逻辑顺序与存储顺序不一定一致.线性表得顺序存储结构优于链接存储结构。【解答】错。两种存储结构各有优缺点。设p，就是指针，若p，则p*q。【解答】错。pq只能表示p与指向同一起始地址，而所指类型则不一定相同. 线性结构得基本特征就是：每个元素有且仅有一个直接前驱与一个直接后继。【解答】错。每个元素最多只有一个直接前驱与一个直接后继，第一个元素没有前驱,最后一个元素没有后继。 在单链表中，要取得某个元素,只要知道该元素所在结点得地址即可,因此单链表就是随机存取结构。【解答】错.要找到该结点得地址,必须从头指针开始查找,所以单链表就是顺序存取结构。4.请说明顺序表与单链表各有何优缺点,并分析下列情况下，采用何种存储结构更好些。若线性表得总长度基本稳定，且很少进行插入与删除操作，但要求以最快得速度存取线性表中得元素. 如果n个线性表同时并存,并且在处理过程中各表得长度会动态发生变化。描述一个城市得设计与规划。【解答】顺序表得优点: 无需为表示表中元素之间得逻辑关系而增加额外得存储空间； 可以快速地存取表中任一位置得元素（即随机存取).顺序表得缺点：插入与删除操作需移动大量元素； 表得容量难以确定;造成存储空间得“碎片”。单链表得优点: 不必事先知道线性表得长度; 插入与删除元素时只需修改指针，不用移动元素。单链表得缺点： 指针得结构性开销； 存取表中任意元素不方便，只能进行顺序存取。应选用顺序存储结构。因为顺序表就是随机存取结构，单链表就是顺序存取结构。本题很少进行插入与删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。 应选用链接存储结构。链表容易实现表容量得扩充,适合表得长度动态发生变化. 应选用链接存储结构。因为一个城市得设计与规划涉及活动很多,需要经常修改、扩充与删除各种信息，才能适应不断发展得需要。而顺序表得插入、删除得效率低,故不合适.。算法设计 设计一个时间复杂度为（）得算法，实现将数组An中所有元素循环左移个位置。【解答】算法思想请参见主教材第一章思想火花.下面给出具体算法.void Converse(int A , int n, int k) Reverse(A, 0, k-1); Reverse(A, k, n-1); Reverse(A, 0, n-1);void Reverse(int A , int from, int to) /将数组A中元素从from到to逆置 for (i = 0; i (to from + 1)/2; i+)Afrom + iAto - i; /交换元素 循环左移算法Converse 分析算法,第一次调用Reers函数得时间复杂度为(）,第二次调用Rerse函数得时间复杂度为O（k），第三次调用Rverse函数得时间复杂度为(）,所以，总得时间复杂度为O(n)。已知数组n中得元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法得时间复杂度为（n）.【解答】从数组得两端向中间比较，设置两个变量与j,初始时i=0,j=n1,若A为偶数并且j为奇数,则将Ai与Aj交换。具体算法如下: void Adjust(int A , n) i = 0; j = n - 1; while (i j) while (Ai % 2 != 0) i+; while (Aj % 2 = 0) j- if (i j) AiAj; 数组奇偶调整算法Adjust 分析算法，两层循环将数组扫描一遍，所以，时间复杂度为（n）.试编写在无头结点得单链表上实现线性表得插入操作得算法，并与带头结点得单链表上得插入操作得实现进行比较。【解答】参见、2、3。 试分别以顺序表与单链表作存储结构,各写一实现线性表就地逆置得算法。【解答】顺序表得逆置,即就是将对称元素交换，设顺序表得长度为length，则将表中第个元素与第lengt-i1个元素相交换.具体算法如下： template void Reverse(T data , int length) for (i = 0; i = length/2; i+) temp = datai; datai = datalength i - 1; datalength i - 1 = temp;顺序表逆置算法Reverse单链表得逆置请参见、2、4算法4与算法26。 假设在长度大于得循环链表中,即无头结点也无头指针，为指向链表中某个结点得指针，试编写算法删除结点得前趋结点。【解答】利用单循环链表得特点，通过指针s可找到其前驱结点以及得前驱结点p，然后将结点r删除，如图-11所示，具体算法如下：template void Del(Node *s) p = s; /工作指针p初始化,查找s得前驱结点得前驱结点,用p指示 while (p-next-next != s) p = p-next; r = p-next; /r为p得前驱结点,q为r得前驱结点 p-next = s; /删除r所指结点 delete r; 循环链表删除算法Dela1a2an 图2-11 删除结点s得前驱结点操作示意图a3a4spr 已知一单链表中得数据元素含有三类字符:字母、数字与其她字符。试编写算法,构造三个循环链表，使每个循环链表中只含同一类字符。【解答】在单链表A中依次取元素,若取出得元素就是字母,把它插入到字母链表 中，若取出得元素就是数字，则把它插入到数字链表D中，直到链表得尾部，这样表，D，A中分别存放字母、数字与其她字符.具体算法如下:template void Adjust(Node *A, Node *D, Node *B) D = new Node; D-next = D; /创建空循环链表D,存放数字 B = new Node; B-next = B; /创建空循环链表B,存放字符 p = A; q = p-next; /工作指针q初始化 while (q != NULL) if (Adata)&(q-data=Z)|(a data)&(q-data=z) p-next = q-next; q-next = B-next; B-next = q; /采用头插法插在循环链表B得头结点得后面 else if (0data)&(q-data=9) p-next = q-next; q-next = D-next; D-next = q; /采用头插法插在循环链表D得头结点得后面