《数据结构(第二版)课后习题答案(王红梅主编).pdf》由会员分享，可在线阅读，更多相关《数据结构(第二版)课后习题答案(王红梅主编).pdf（97页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1章 绪 论课后习题讲解1、填空（）就是数据得基本单位，在计算机程序中通常作为一个整体进行考虑与处理。【解答】数据元素（）就是数据得最小单位，（）就是讨论数据结构时涉及得最小数据单位。【解答】数据项，数据元素【分析】数据结构指得就是数据元素以及数据元素之间得关系。从逻辑关系上讲，数据结构主要分为（）、（）、（）与（）。【解答】集合，线性结构，树结构，图结构（4）数据得存储结构主要有（）与（）两种基本方法，不论哪种存储结构，都要存储两方面得内容：（）与（）。【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间得关系（5）算法具有五个特性，分 别 就 是（）、（）、（）、（）、（）。【解答
2、】有零个或多个输入,有一个或多个输出，有穷性，确定性，可行性（6）算法得描述方法通常有（）、（）、（）与（）四种，其中，（）被称为算法语言。【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 在一般情况下，一个算法得时间复杂度就是（）得函数。【解答】问题规模设待处理问题得规模为n,若一个算法得时间复杂度为一个常数,则表示成数量级得形式为（），若为n*log2 5 n,则表示成数量级得形式为（）.【解答】0（1）,O（n lo g 2 n）【分析】用大0记号表示算法得时间复杂度，需要将低次塞去掉，将最高次募得系数去掉.2、选择题顺序存储结构中数据元素之间得逻辑关系就是由（）表示得，链接存储结
3、构中得数据元素之间得逻辑关系就是 由（）表示得。A线 性 结 构B非线性结构C存 储 位 置D指针【解答】C,D【分析】顺序存储结构就就是用一维数组存储数据结构中得数据元素，其逻辑关系由存储位置（即元素在数组中得下标）表示；链接存储结构中一个数据元素对应链表中得一个结点，元素之间得逻辑关系由结点中得指针表示。假设有如下遗产继承规则：丈夫与妻子可以相互继承遗产;子女可以继承父亲或母亲得遗产；子女间不能相互继承。则表示该遗产继承关系得最合适得数据结构应该就是（）。A树B图C线 性 表D集合【解答】B【分析】将丈夫、妻子与子女分别作为数据元素，根据题意画出逻辑结构图。算法指得就是（）。A对特定问题求
4、解步骤得一种描述,就是指令得有限序列。B计 算 机 程 序C解决问题得计算方法D数据处理【解答】A 分析1计算机程序就是对算法得具体实现；简单地说,算法就是解决问题得方法；数据处理就是通过算法完成得。所以，只有A就是算法得准确定义.（4）下面（）不就是算法所必须具备得特性.A有 穷 性B确 切 性C高 效 性D可行性【解答】C【分析】高效性就是好算法应具备得特性。算法分析得目得就是（），算法分析得两个主要方面就是（）。A找出数据结构得合理性B研究算法中输入与输出得关系C分析算法得效率以求改进D分析算法得易读性与文档性E空间性能与时间性能F正确性与简明性G可 读 性 与 文 档 性H数据复杂性与
5、程序复杂性【解答】c,E3、判断题算法得时间复杂度都要通过算法中得基本语句得执行次数来确定.【解答】错。时间复杂度要通过算法中基本语句执行次数得数量级来确定。每种数据结构都具备三个基本操作：插入、删除与查找。【解答】错。如数组就没有插入与删除操作。此题注意就是每种数据结构。所谓数据得逻辑结构指得就是数据之间得逻辑关系。【解答】错。就是数据之间得逻辑关系得整体。(4)逻辑结构与数据元素本身得内容与形式无关.【解答】对。因此逻辑结构就是数据组织得主要方面。基于某种逻辑结构之上得基本操作，其实现就是唯一得。【解答】错。基本操作得实现就是基于某种存储结构设计得，因而不就是唯一得。4、分析以下各程序段，
6、并用大。记号表示其执行时间。【解答】基本语句就是k=k+10*i,共执行了 n 2次，所以T(n)=O(n)。基本语句就是k=k+10*i,共执行了 n次，所 以T(n)=0(n)0 分析条件语句，每循环一次，i+j整 体 加1,共循环n次,所以 T(n)=O(n)o(4)设循环体共执行T(n)次，每循环一次，循环变量y 加 1,最终T(n )=y,即：(T (n)+1)2 W n,所以 T(n)=O (n 1/2 )o x+就是基本语句，所以5 .设有数据结构(D,R),其中 D=1,2,3,4,5,6 ,R=(1,2),(2,3 ),(2,4),(3,4),(3,5),(3 ,6),(4,
7、5),(4,6)。试画出其逻辑结构图并指出属于何种结构。【解答】其逻辑结构图如图1 3 所示，它就是一种图结构.6 、为整数定义一个抽象数据类型，包含整数得常见运算，每个运算对应一个基本操作，每个基本操作得接口需定义前置条件、输入、功能、输出与后置条件。【解答】整数得抽象数据类型定义如下：A D T i n t e g e rD a t a整数a：可以就是正整数(1,2,3,)、负整数(-1,-2,-3,)与零O p e r a t i o nC o n s t r u c t o r前置条件：整数a 不存在输入:一个整数b功能：构造一个与输入值相同得整数输出：无后置条件：整数a 具有输入得值
8、S et前置条件：存在一个整数a输入：一个整数b功能:修改整数a 得值，使之与输入得整数值相同输出:无后置条件：整数a 得值发生改变Add前置条件:存在一个整数a输入：一个整数b功能：将整数a 与输入得整数b 相加输出：相加后得结果后置条件：整数a 得值发生改变Sub前置条件:存在一个整数a输入：一个整数b功能：将整数a 与输入得整数b 相减输出：相减得结果后置条件:整数a 得值发生改变Multi前置条件:存在一个整数a输入：一个整数b功能：将整数a 与输入得整数b 相乘输出：相乘得结果后置条件:整数a 得值发生改变D i v前置条件：存在一个整数a输入：一个整数b功能：将整数a 与输入得整数
9、b 相除输出：若整数b 为零，则抛出除零异常,否则输出相除得结果后置条件：整数a 得值发生改变M o d前置条件：存在一个整数a输入:一个整数b功能：求当前整数与输入整数得模，即正得余数输出：若整数b 为零,则抛出除零异常,否则输出取模得结果后置条件:整数a 得值发生改变E q ual前置条件:存在一个整数a输入:一个整数b功能：判断整数a 与输入得整数b 就是否相等输出：若相等返回1,否则返回0后置条件:整数a 得值不发生改变en d A D T7、求多项式A(x)得算法可根据下列两个公式之一来设计:(1)A (x)=a n x n+a n-l x n-1+a l x+a 0(2)A (x
10、)=(a n x+a n-1 )x+a l)x )+a 0根据算法得时间复杂度分析比较这两种算法得优劣。【解答】第二种算法得时间性能要好些。第一种算法需执行大量得乘法运算,而第二种算法进行了优化，减少了不必要得乘法运算。8、算法设计(要求：算法用伪代码与C+描述，并分析最坏情况下得时间复杂度)对一个整型数组A n 设计一个排序算法。【解答】下面就是简单选择排序算法得伪代码描述。下面就是简单选择排序算法得C+描述.分析算法,有两层嵌套得f o r循环，所以，.找出整型数组A n 中元素得最大值与次最大值。【解答】算法得伪代码描述如下：算法得C+描述如下：分析算法，只有一层循环，共执行n 2次，所
11、以，T (n)=0 (n)o学习自测及答案1.顺序存储结构得特点就是()，链接存储结构得特点就是().【解答】用元素在存储器中得相对位置来表示数据元素之间得逻辑关系，用指示元素存储地址得指针表示数据元素之间得逻辑关系。2、算法在发生非法操作时可以作出处理得特性称为()o【解答】健壮性3、常见得算法时间复杂度用大。记 号 表 示 为:常 数 阶()、对数阶()、线 性 阶()、平 方 阶()与 指 数 阶()o【解答】0 (1),0 (l o g 2n),0 (n ),0 (n 2),0 (2n)4.将下列函数按它们在n时得无穷大阶数，从小到大排列.n ,n-n 3+7 n 5,n l o g
12、n,2 n/2,n 3,l o g 2n,n l/2+1 o g 2 n,(3/2)n,n !,n 2+l o g 2n【解答】l o g 2n,n l/2+l o g 2n,n,n l o g 2n,n 2+l o g 2n,n 3,n-n 3+7 n 5,2n/2,(3/2)n,n!5.试描述数据结构与抽象数据类型得概念与程序设计语言中数据类型概念得区别。【解答】数据结构就是指相互之间存在一定关系得数据元素得集合.而抽象数据类型就是指一个数据结构以及定义在该结构上得一组操作。程序设计语言中得数据类型就是一个值得集合与定义在这个值集上一组操作得总称。抽象数据类型可以瞧成就是对数据类型得一种抽
13、象.6、对下列用二元组表示得数据结构,试分别画出对应得逻辑结构图，并指出属于何种结构。A=(D,R),其中 D=al,a2,a3,a4,R=B=(D,R),其中 D=a,b,c,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)【解答】属于集合，其逻辑结构图如图14(a)所示；属于线性结构，其逻辑结构图如图14(b)所示；属于树结构，其逻辑结构图如图1-4(c)所示；属于图结构，其逻辑结构图如图1-4(d)
14、所示。7、求下列算法得时间复杂度.c o u n t=0 ；x =1；w h i l e (x x*=2;co u n t +;)r e t u r n co u n t；【解答】0 (1 o g 2 n )第2章线性表课后习题讲解1、填空 在顺序表中，等概率情况下，插入与删除一个元素平均需移动()个元素，具体移动元素得个数与()与()有关。【解答】表长得一半,表长，该元素在表中得位置 顺序表中第一个元素得存储地址就是10 0,每个元素得长度为2,则第5个元素得存储地址就是（）。【解答】1 0 8【分析】第5个元素得存储地址=第1个元素得存储地址+（5-1）X2=1 0 8 设单链表中指针p指
15、向结点A,若要删除A得后继结点（假 设A存在后继结点），则需修改指针得操作为（）.【解答】p-next=（p next）-nex t（4）单链表中设置头结点得作用就是（）。【解答】为了运算方便【分析】例如在插入与删除操作时不必对表头得情况进行特殊处理.非空得单循环链表由头指针h e a d指示,则其尾结点（由指针p所指）满足（）。【解答】P -）ne x t=h e a d【分析】如图2 8所示。（6）在由尾指针r e a r指示得单循环链表中，在表尾插入一个结点s得操作序列就是（）；删除开始结点得操作序列为（）.【解答】s-n e xt =r e a r-n ext;r e a r-next
16、 =s；r e a r一s ;q=r e a r-ne x t-n ext;r ea r n ext ne x t=qn e xt;delete q；【分析】操作示意图如图2 9 所示：一个具有n 个结点得单链表，在指针p 所指结点后插入一个新结点得时间复杂度为（）；在给定值为x 得结点后插入一个新结点得时间复杂度为（）.【解答】0（1）,0（n）【分析】在 P 所指结点后插入一个新结点只需修改指针，所以时间复杂度为。（1）；而在给定值为x 得结点后插入一个新结点需要先查找值为x 得结点，所以时间复杂度为0（n）o可由一个尾指针唯一确定得链表有（）、（）、（）。【解答】循环链表，循环双链表，双
17、链表2、选择题（1）线性表得顺序存储结构就是一种（）得存储结构，线性表得链接存储结构就是一种（）得存储结构.A 随机存取B 顺序存取C索引存取D 散列存取【解答】A,B【分析】参见2。2.1.线性表采用链接存储时,其地址（）.A 必须就是连续得B 部分地址必须就是连续得C 一定就是不连续得D 连续与否均可以【解答】D【分析】线性表得链接存储就是用一组任意得存储单元存储线性表得数据元素,这组存储单元可以连续,也可以不连续，甚至可以零散分布在内存中任意位置。单循环链表得主要优点就是（）oA不再需要头指针了B从表中任一结点出发都能扫描到整个链表；C已知某个结点得位置后，能够容易找到它得直接前趋；D在
18、进行插入、删除操作时，能更好地保证链表不断开。【解答】B（4）链表不具有得特点就是（）。A可随机访问任一元素B插入、删除不需要移动元素C不必事先估计存储空间D所需空间与线性表长度成正比【解答】A 若某线性表中最常用得操作就是取第i个元素与找第i个元素得前趋,则采用（）存储方法最节省时间。A顺 序 表B单 链 表C双 链 表D单循环链表【解答】A【分析】线性表中最常用得操作就是取第i个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素得前趋也很方便.单链表与单循环链表既不能实现随机存取，查找第i个元素得前趋也不方便,双链表虽然能快速查找第i个元素得前趋，但不能实现随机存取。(6
19、)若链表中最常用得操作就是在最后一个结点之后插入一个结点与删除第一个结点,则采用()存储方法最节省时间.A 单 链 表 B带头指针得单循环链表C 双 链 表 D 带尾指针得单循环链表【解答】D【分析】在链表中得最后一个结点之后插入一个结点需要知道终端结点得地址，所以，单链表、带头指针得单循环链表、双链表都不合适，考虑在带尾指针得单循环链表中删除第一个结点，其时间性能就是0(1),所以，答案就是D。若链表中最常用得操作就是在最后一个结点之后插入一个结点与删除最后一个结点,则采用()存储方法最节省运算时间。A 单 链 表 B 循环双链表C单循环链表D 带尾指针得单循环链表【解答】B【分析】在链表中
20、得最后一个结点之后插入一个结点需要知道终端结点得地址，所以，单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点得前驱结点得地址,所以,带尾指针得单循环链表不合适，而循环双链表满足条件。在 具 有 n 个结点得有序单链表中插入一个新结点并仍然有序得时间复杂度就是().A 0 (1)B 0 (n)C 0 (n 2)D O(n l o g 2 n)【解答】B【分析】首先应顺序查找新结点在单链表中得位置。(9)对于n个元素组成得线性表，建立一个有序单链表得时间复杂度就 是()。A 0 (1)B 0 (n)C 0 (n 2)D 0 (n 1 o g 2 n )【解答】C【分析】该算法需要将f
21、个元素依次插入到有序单链表中，而插入每个元素需0(n)。使用双链表存储线性表，其优点就是可以()。A提高查找速度B更方便数据得插入与删除C节约存储空间D很快回收存储空间【解答】B【分析】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节约存储空间，对于动态存储分配，回收存储空间得速度就是一样得.由于双链表具有对称性，所以,其插入与删除操作更加方便。(1 1)在一个单链表中，已知q所指结点就是P所指结点得直接前驱，若 在q与P之间插入S所指结点，则执行()操作。A s-n e x t=p n e x t;p n e x t=s ；B q -n e
22、x t=s；s 一n e x t =p；C p n e x t=s-n e x t;s 一 n e x t =p ;D p -n e x t =s;s n e x t=q ;【解答】B【分析】注意此题就是在q与 P之间插入新结点，所以,不用考虑修改指针得顺序。0 2)在循环双链表得p 所指结点后插入S 所指结点得操作就是().A p n e x t =s;s-)p r i o r=p;p nextp r i o r =s；s-n e x t=p n e x t;B p )n e x t=s ；p 一n e x t 一p r i o r=s;s p r i o r=p；s一n e x t=p-n
23、 e x t;C s -p r i o r=p;s-n e x t=p-n e x t；p n e x t =s；p-n e x t-p r i o r=s；D s-p r i o r =p ；s next=p n e x t;p n ex t p r i o r =s；p n e x t=s【解答】D【分析】在链表中,对指针得修改必须保持线性表得逻辑关系，否则，将违背线性表得逻辑特征，图2-1 0给出备选答案C与 D 得图解。3、判断题(1)线性表得逻辑顺序与存储顺序总就是一致得.【解答】错。顺序表得逻辑顺序与存储顺序一致，链表得逻辑顺序与存储顺序不一定一致。线性表得顺序存储结构优于链接存储
24、结构。【解答】错。两种存储结构各有优缺点.设P，q就是指针，若P=q,则*p=*q。【解答】错。P=q只能表示P与q指向同一起始地址，而所指类型则不一定相同.(4)线性结构得基本特征就是：每个元素有且仅有一个直接前驱与一个直接后继。【解答】错。每个元素最多只有一个直接前驱与一个直接后继，第一个元素没有前驱，最后一个元素没有后继。在单链表中，要取得某个元素，只要知道该元素所在结点得地址即可,因此单链表就是随机存取结构。【解答】错.要找到该结点得地址，必须从头指针开始查找，所以单链表就是顺序存取结构。4.请说明顺序表与单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些.若线性表得总长度基
25、本稳定，且很少进行插入与删除操作，但要求以最快得速度存取线性表中得元素。如果n个线性表同时并存，并且在处理过程中各表得长度会动态发生变化。描述一个城市得设计与规划。【解答】顺序表得优点：无需为表示表中元素之间得逻辑关系而增加额外得存储空间；可以快速地存取表中任一位置得元素(即随机存取)。顺序表得缺点:插入与删除操作需移动大量元素;表得容量难以确定；造 成 存 储 空 间 得“碎片二单链表得优点:不必事先知道线性表得长度；插入与删除元素时只需修改指针，不用移动元素.单链表得缺点:指针得结构性开销;存取表中任意元素不方便，只能进行顺序存取.应选用顺序存储结构.因为顺序表就是随机存取结构，单链表就是
26、顺序存取结构。本题很少进行插入与删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构.应选用链接存储结构。链表容易实现表容量得扩充，适合表得长度动态发生变化。应选用链接存储结构。因为一个城市得设计与规划涉及活动很多，需要经常修改、扩充与删除各种信息，才能适应不断发展得需要。而顺序表得插入、删除得效率低，故不合适。5.算法设计(1)设计一个时间复杂度为0(n)得算法，实现将数组A n 中所有元素循环右移k个位置。【解答】算法思想请参见主教材第一章思想火花。下面给出具体算法。分析算法,第一次调用Rever s e函数得时间复杂度为0(k),第二次调用Rev e r s e函数得时间复
27、杂度为0(n k),第三次调用Re v e r s e函数得时间复杂度为0(n),所以，总得时间复杂度为0(n).已 知 数 组A n 中得元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法得时间复杂度为0(n)。【解答】从数组得两端向中间比较，设 置 两 个 变 量i与j,初始时i=0,j=n l,若A i为偶数并且A j 为奇数，则将Ai 与A j 交换.具体算法如下：分析算法,两层循环将数组扫描一遍,所以,时间复杂度为0(n)。试编写在无头结点得单链表上实现线性表得插入操作得算法，并与带头结点得单链表上得插入操作得实现进行比较。【解答】参 见2.
28、2。3.(4)试分别以顺序表与单链表作存储结构,各写一实现线性表就地逆置得算法。【解答】顺序表得逆置，即就是将对称元素交换，设顺序表得长度为1 eng t h,则将表中第i个元素与第1 e n g th-i-1个元素相交换.具体算法如下：单链表得逆置请参见2。2.4 算 法 24 与算法2-6。假 设 在 长 度 大 于 1 得循环链表中，即无头结点也无头指针,s 为指向链表中某个结点得指针,试编写算法删除结点s 得前趋结点。【解答】利用单循环链表得特点,通过指针s 可找到其前驱结点r 以及 r 得前驱结点p,然后将结点r 删除，如图2 11所示，具体算法如下：(6)已知一单链表中得数据元素含
29、有三类字符：字母、数字与其她字符。试编写算法,构造三个循环链表，使每个循环链表中只含同一类字符。【解答】在单链表A 中依次取元素，若取出得元素就是字母，把它插入到字母链表B中，若取出得元素就是数字，则把它插入到数字链表D中，直到链表得尾部,这样表B,D,A 中分别存放字母、数字与其她字符.具体算法如下：设单链表以非递减有序排列，设计算法实现在单链表中删去值相同得多余结点。【解答】从头到尾扫描单链表,若当前结点得元素值与后继结点得元素值不相等，则指针后移;否则删除该后继结点。具体算法如下：判断带头结点得双循环链表就是否对称.【解答】设工作指针P 与 q 分别指向循环双链表得开始结点与终端结点，若
30、结点P与结点q得数据域相等，则工作指针P后移，工作指针q前移，直到指针P与指针q指向同一结点(循环双链表中结点个数为奇数)，或结点q成为结点P得前驱(循环双链表中结点个数为偶数).如图2 12所示。学习自测及答案1、已知一维数组A采用顺序存储结构,每个元素占用4个存储单元，第9个元素得地址为1 4 4,则第一个元素得地址就是()。A 1 08 B 180 C 1 76 D 1 12【解答】D2.在长度为n得线性表中查找值为x得数据元素得时间复杂度为：()oA 0(0)B 0(1)C 0(n)D 0(n2)【解答】C3.在一个长度为n得顺序表得第i(IW iW n+l)个元素之前插入一个元素，需
31、向后移动()个元素，删除第i(IW iW n)个元素时-，需向前移动()个元素.【解答】n-i+1,n-i4 .在单链表中，除了头结点以外，任一结点得存储位置由()指示.【解答】其前趋结点得指针域5.当线性表采用顺序存储结构时，其 主 要 特 点 就 是().解答】逻辑结构中相邻得结点在存储结构中仍相邻6.在双链表中，每个结点设置了两个指针域，其中一个指向（）结点,另一个指向（）结点。【解答】前驱，后继7。设A就是一个线性表（a l ,a 2,，a n）,采用顺序存储结构,则在等概率得前提下,平均每插入一个元素需要移动得元素个数为多少？若元素插在a i与a i +1之 间（I W i Wn）得
32、 概 率 为，则平均每插入一个元素所要移动得元素个数又就是多少？【解答】8.线性表存放在整型数组A a r r s i z e 得 前e l e n u m个单元中，且递增有序。编写算法，将元素x插入到线性表得适当位置上，以保持线性表得有序性，并且分析算法得时间复杂度.【解答】本题就是在一个递增有序表中插入元素x,基本思路就是从有序表得尾部开始依次取元素与x比较，若 大 于x,此元素后移一位，再取它前面一个元素重复上述步骤；否则，找到插入位置,将x插入.具体算法如下：9、已知单链表中各结点得元素值为整型且递增有序,设计算法删除链表中所有大于mink且小于m a x k得所有元素，并释放被删结点
33、得存储空间。【解答】因为就是在有序单链表上得操作，所以，要充分利用其有序性.在单链表中查找第一个大于m i n k得结点与第一个小于m a x k得结点,再将二者间得所有结点删除。10.设单循环链表L1,对其遍历得结果就是：x 1,x2,x3,xn-1,xno请将该循环链表拆成两个单循环链表L1与L 2,使 得L 1中含有原L 1表中序号为奇数得结点且遍历结果为:xl,x3,；L 2中含有原L 1表中序号为偶数得结点且遍历结果为：，x4,x2o【解答】算法如下：第3章 特殊线性表一栈、队列与串课后习题讲解1、填空 设有一个空栈,栈顶指针为1000H,现有输入序列为1、2、3、4、5,经过 pu
34、 s h,pu s h,po p,pu s h ,P o p,pu s h,pu s h后，输出序列就是（），栈顶指针为（）。【解答】23,1 003 H栈通常采用得两种存储结构就是（）;其判定栈空得条件分别就是（），判定栈满得条件分别就是（）。【解答】顺序存储结构与链接存储结构（或顺序栈与链栈），栈顶指针to p=-1与t o p=N U L L,栈顶指针to p等于数组得长度与内存无可用空间闭（）可作为实现递归函数调用得一种数据结构。【解答】栈【分析】递归函数得调用与返回正好符合后进先出性.（4）表达式a*（b+c）d得后缀表达式就是（）。【解答】a b c +*d-【分析】将中缀表达式变
35、为后缀表达式有一个技巧:将操作数依次写下来，再将算符插在它得两个操作数得后面。栈与队列就是两种特殊得线性表，栈得操作特性就是（），队列得操作特性就是（）,栈与队列得主要区别在 于（）o【解答】后进先出，先进先出，对插入与删除操作限定得位置不同（6）循环队列得引入就是为了克服（）.【解答】假溢出 数 组Q n 用来表示一个循环队列，f r o n t为队头元素得前一个位置,r e a r为队尾元素得位置，计算队列中元素个数得公式为（）。【解答】（r e a r -f r o n t+n）%n【分析】也可以就是（r e a r f r o n t）%n,但r e a r f r o n t得结果可
36、能就是负整数，而对一个负整数求模，其结果在不同得编译器环境下可能会有所不同。（8）用循环链表表示得队列长度为n,若只设头指针，则出队与入队得时间复杂度分别就是（）与（）.【解答】0（1）,0（n）【分析】在带头指针得循环链表中，出队即就是删除开始结点，这只需修改相应指针;入队即就是在终端结点得后面插入一个结点，这需要从头指针开始查找终端结点得地址。（9）串就是一种特殊得线性表，其特殊性体现在（）.【解答】数据元素得类型就是一个字符（1 0）两个串相等得充分必要条件就是（）。【解答】长度相同且对应位置得字符相等【分析】例如a b c /a b c a b c /b c a”。2、选择题若一个栈得
37、输入序列就是1 ,2,3,n,输出序列得第一个元素就是n,则 第 i 个输出元素就是（）A 不确定 B n -i C n i1 D n-i +1【解答】D【分析】此时，输出序列一定就是输入序列得逆序。设 栈 S与队列Q得初始状态为空，元 素 e 1、e2、e3、e4、e 5、e6依次通过栈S,一个元素出栈后即进入队列Q,若 6个元素出队得顺序就是e2、e4、e 3、e6、e5、el,则栈 S得容量至少应该就是（）。A 6 B 4 C 3 D 2【解答】c【分析】由于队列具有先进先出性，所以，此题中队列形同虚设，即出栈得顺序也就是e2、e4、e3、e 6、e5、el o 一个栈得入栈序列就是1,
38、2,3,4,5,则栈得不可能得输出序列就是（）.A 5 4 3 2 1 B 4 5 3 2 1 C 4 3 5 1 2 D 1 2 3 4 5【解答】C【分析】此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且就是升序（指得就是元素得序号）得两个元素。（4）设计一个判别表达式中左右括号就是否配对得算法，采 用（）数据结构最佳A顺 序 表B栈C队 列D链表【解答】B【分析】每个右括号与它前面得最后一个没有匹配得左括号配对，因此具有后进先出性。在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该就是一个（）结构。A栈B队 列C数 组D线性表【解答】B【分析】
39、先进入打印缓冲区得文件先被打印，因此具有先进先出性。(6)一个队列得入队顺序就是1,2,3,4,则队列得输出顺序就是()oA 432 1 B 1 2 34 C 1432 D 3 241【解答】B【分析】队列得入队顺序与出队顺序总就是一致得.栈与队列得主要区别在于().A它们得逻辑结构不一样B它们得存储结构不一样C所包含得运算不一样D插入、删除运算得限定不一样【解答】D【分析】栈与队列得逻辑结构都就是线性得，都有顺序存储与链接存储，有可能包含得运算不一样，但不就是主要区别，任何数据结构在针对具体问题时包含得运算都可能不同。设数组S n 作为两个栈S1与S2得存储空间,对任何一个栈只有当S n 全
40、满时才不能进行进栈操作.为这两个栈分配空间得最佳方案就是()。A S1得栈底位置为0,S2得栈底位置为n-1B S 1得栈底位置为0,S2得栈底位置为n/2C S 1得栈底位置为0,S2得栈底位置为nD S1得栈底位置为0,S2得栈底位置为1【解答】A【分析】两栈共享空间首先两个栈就是相向增长得，栈底应该分别指向两个栈中得第一个元素得位置,并注意C+中得数组下标就是从0开始得。设有两个串P与q,求q在P中首次出现得位置得运算称作().A连 接B模 式 匹 配C求 子 串D求串长【解答】B3、判断题 有n个元素依次进栈，则出栈序列有(n-l)/2种。【解答】错.应 该 有 种。栈可以作为实现过程
41、调用得一种数据结构。【解答】对。只要操作满足后进先出性，都可以采用栈作为辅助数据结构。在栈满得情况下不能做进栈操作，否则将产生“上溢【解答】对.(4)在循环队列中，fro n t指向队头元素得前一个位置，re a r指向队尾元素得位置，则队满得条件就是f r o nt=rear o【解答】错。这就是队空得判定条件，在循环队列中要将队空与队满得判定条件区别开.空串与空格串就是相同得.【解答】错。空串得长度为零,而空格串得长度不为0,其长度就是串中空格得个数。4、设有一个栈，元素进栈得次序为A,B,C,D,E,能否得到如下出栈序列，若能，请写出操作序列，若不能，请说明原因。C,E,A,B,D C,
42、B,A,D,E【解答】不能，因为在C、E出栈得情况下,A 一定在栈中，而且在B得下面，不可能先于B出栈。可 以，设I为进栈操作，0为入栈操作，则 其 操 作 序 列 为I I IOOOIOIOo5、举例说明顺序队列得“假溢出”现象。【解答】假设有一个顺序队列，如 图3 6所示，队尾指针r e a r=4,队头指针f r o n t=1 ,如果再有元素入队，就会产生“上溢”，此 时 得“上溢又称为“假溢出”，因为队列并不就是真得溢出了，存储队列得数组中还有2个存储单元空闲，其下标分别为0与1。6、在操作序列 p u s h (1 )p us h (2)、p o p pu sh(5)、p ush(
43、7)、p o p、p us h (6)之后，栈顶元素与栈底元素分别就是什么？(p us h (k)表示整数k入栈，p o p表示栈顶元素出栈。)【解答】栈顶元素为6,栈底元素为1。其执行过程如图3 7所示。7 .在操作序列 E n Q ue ue(l)、E n Q ue ue (3)、D e Q ue ue、E nQ ue ue (5)、E n Q ue ue (7 )、D e Q ue ue、E n Q u e ue (9)之后，队头元素与队尾元素分别就是什么？(E n Q ue ue (k)表示整数k入队,D e Q ue ue表示队头元素出队）.【解答】队头元素为5,队尾元素为9。其执行
44、过程如图3 8所示。8 o空串与空格串有何区别？串中得空格符有何意义?空串在串处理中有何作用？【解答】不含任何字符得串称为空串，其长度为零。仅含空格得串称为空格串，它得长度为串中空格符得个数。串中得空格符可用来分隔一般得字符，便于人们识别与阅读,但计算串长时应包括这些空格符.空串在串处理中可作为任意串得子串。9、算法设计假设以不带头结点得循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针。试设计相应得入队与出队得算法。【解答】出队操作就是在循环链表得头部进行,相当于删除开始结点,而入队操作就是在循环链表得尾部进行，相当于在终端结点之后插入一个结点。由于循环链表不带头结点，需要处理空表
45、得特殊情况。入队算法如下：出队算法如下：设 顺 序 栈S中 有2 n个元素，从栈顶到栈底得元素依次为a 2n ,a 2 n-l,，a l,要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底得元素依次为a 2 n,a 2 n-2,，a 2,a 2 n 1,a 2 n 3,，a 1 ,请设计算法实现该操作,要求空间复杂度与时间复杂度均为0(n)。【解答】操作步骤为：将所有元素出栈并入队；依次将队列元素出队，如果就是偶数结点，则再入队，如果就是奇数结点，则入栈；将奇数结点出栈并入队；将偶数结点出队并入栈；将所有元素出栈并入队；将所有元素出队并入栈即为所求。用顺序存储结构存储串S,编写算法删除S中
46、 第i个字符开始得连续j个字符。【解答】先判断串S中要删除得内容就是否存在，若存在，则将第i+j -1之后得字符前移j个位置。算法如下：(4)对于采用顺序存储结构得串S ,编写一个函数删除其值等于c h得所有字符。【解答】从后向前删除值为c h得所有元素，这样所有移动得元素中没有值为c h得元素，能减少移动元素得次数，提高算法得效率。算法如下：对串得模式匹配K M P算法设计求模式滑动位置得n ex t函数.【解答】参 见3.2。5学习自测及答案1.在一个具有n个单元得顺序栈中，假定以地址低端（即下标为0得单元）作为栈底，以t o p作为栈顶指针，当出栈时，t o p得变化为（）.A 不变 B
47、 t o p=0;C t o p=t o p 1 ;D t o p=t o p+l;【解答】C2。一个栈得入栈序列就是a,b,c,d,e,则栈得不可能得出栈序列就是（）.A e d c b a B c d eb a C d eb c a D a b ed e【解答】C3.从栈顶指针为t o p得链栈中删除一个结点，用x保存被删除结点得值，则执行（）。A x=t o p ；t o p =t o p -n ex t；B x=t o p一 d a t a;C t o p =t o p-n ex t ;x=t o p d a t a；D x=t o p-d a t a；t o p=t o p n e
48、x t；【解答】D4。设 元 素1,2,3,P,A依次经过一个栈，进栈次序为1 2 3PA,在栈得输出序列中，有哪些序列可作为C+程序设计语言得变量名。【解答】PA3 2 1,P3 A2 1,P 3 2 A1,P3 2 1 A,AP3 2 15、设 S=I _ a m _ a _ t e a c t h er”,其 长 度 为（【解答】1 56 .对于栈与队列，无论它们采用顺序存储结构还就是链接存储结构，进行插入与删除操作得时间复杂度都就是()。【解答】0 (1)7.如果进栈序列为A、B、C、D,则可能得出栈序列就是什么？答:共 1 4 种，分别就是:AB C D,AB D C,AC B D,
49、AC D B,AD C B,B AC D,B AD C,B C AD,B C D A,B D C A,C B AD,C B D A,C D B A,D C B A8 o简述队列与栈这两种数据结构得相同点与不同点.【解答】相同点:它们都就是插入与删除操作得位置受限制得线性表。不同点：栈就是限定仅在表尾进行插入与删除得线性表,就是后进先出得线性表,而队列就是限定在表得一端进行插入，在另一端进行删除得线性表，就是先进先出得线性表。9、利用两个栈S 1与S 2模拟一个队列，如何利用栈得运算实现队列得插入与删除操作,请简述算法思想。【解答】利用两个栈S1与S 2模拟一个队列，当需要向队列中插入一个元素时
50、，用S 1来存放已输入得元素，即通过向栈S 1执行入栈操作来实现；当需要从队列中删除元素时，则将S 1中元素全部送入到S 2中，再 从S 2中删除栈顶元素，最后再将S 2中元素全部送入到S1中；判断队空得条件就是：栈S 1与S 2同时为空。1 0、设计算法把一个十进制整数转换为二至九进制之间得任一进制数输出.【解答】算法基于原理：N=（N d iv d）X d+N m o d d（d iv为整除运算，m o d为求余运算）。1 1。假设一个算术表达式中可以包含三种括号：圆括号“（”与“）”，方 括 号T与 以 及 花 括 号“”与“”，且这三种括号可按任意得次序嵌套使用。编写算法判断给定表达式