数据结构（第二版）课后习题答案.doc

第 1 章绪 论 课后习题讲解 1、填空 ( )就是数据得基本单位，在计算机程序中通常作为一个整体进行考虑与处理。 【解答】数据元素 （ )就是数据得最小单位，( )就是讨论数据结构时涉及得最小数据单位。【解答】数据项，数据元素 【分析】数据结构指得就是数据元素以及数据元素之间得关系。 从逻辑关系上讲,数据结构主要分为（ )、( ）、（)与（）。【解答】集合，线性结构,树结构,图结构 数据得存储结构主要有( )与( )两种基本方法,不论哪种存储结构，都要存储两方面得内容：()与( ）。【解答】顺序存储结构,链接存储结构，数据元素，数据元素之间得关系 算法具有五个特性，分别就是（）、（)、（）、（ ）、（ )。 【解答】有零个或多个输入,有一个或多个输出，有穷性，确定性，可行性 算法得描述方法通常有（）、( )、( ）与（ ）四种，其中,（ )被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码,伪代码 在一般情况下,一个算法得时间复杂度就是（)得函数。【解答】问题规模 设待处理问题得规模为n，若一个算法得时间复杂度为一个常数，则表示成数量级得形式为( ）,若为n*log5n，则表示成数量级得形式为( ）. 【解答】(1),(lo2） 【分析】用大记号表示算法得时间复杂度，需要将低次幂去掉，将最高次幂得系数去掉. 2、 选择题 顺序存储结构中数据元素之间得逻辑关系就是由( )表示得，链接存储结构中得数据元素之间得逻辑关系就是由（ ）表示得。 A 线性结构 B非线性结构 C存储位置 指针 【解答】C，【分析】顺序存储结构就就是用一维数组存储数据结构中得数据元素，其逻辑关系由存储位置(即元素在数组中得下标)表示；链接存储结构中一个数据元素对应链表中得一个结点，元素之间得逻辑关系由结点中得指针表示。 假设有如下遗产继承规则：丈夫与妻子可以相互继承遗产;子女可以继承父亲或母亲得遗产；子女间不能相互继承。则表示该遗产继承关系得最合适得数据结构应该就是（ )。 A树 图 线性表 集合 【解答】B【分析】将丈夫、妻子与子女分别作为数据元素,根据题意画出逻辑结构图。 算法指得就是( )。 A 对特定问题求解步骤得一种描述,就是指令得有限序列。 B 计算机程序C 解决问题得计算方法 D 数据处理 【解答】A 【分析】计算机程序就是对算法得具体实现;简单地说,算法就是解决问题得方法；数据处理就是通过算法完成得。所以,只有A就是算法得准确定义. 下面( )不就是算法所必须具备得特性.A 有穷性B确切性 C 高效性 D 可行性 【解答】C【分析】高效性就是好算法应具备得特性。 算法分析得目得就是(）,算法分析得两个主要方面就是（ )。 A找出数据结构得合理性 B研究算法中输入与输出得关系C 分析算法得效率以求改进 D 分析算法得易读性与文档性 空间性能与时间性能 正确性与简明性 G可读性与文档性 数据复杂性与程序复杂性 【解答】，E 3、判断题 算法得时间复杂度都要通过算法中得基本语句得执行次数来确定. 【解答】错。时间复杂度要通过算法中基本语句执行次数得数量级来确定。 每种数据结构都具备三个基本操作：插入、删除与查找。 【解答】错。如数组就没有插入与删除操作。此题注意就是每种数据结构。 所谓数据得逻辑结构指得就是数据之间得逻辑关系。 【解答】错。就是数据之间得逻辑关系得整体。 逻辑结构与数据元素本身得内容与形式无关. 【解答】对。因此逻辑结构就是数据组织得主要方面。 基于某种逻辑结构之上得基本操作，其实现就是唯一得。 【解答】错。基本操作得实现就是基于某种存储结构设计得，因而不就是唯一得。 4、 分析以下各程序段，并用大O记号表示其执行时间。 【解答】 基本语句就是k=k10*，共执行了次,所以（）(n)。 基本语句就是k=+10i,共执行了n次，所以T（n)O（）。 分析条件语句，每循环一次，i 整体加1，共循环次,所以（n)=（)。 设循环体共执行T(n）次，每循环一次，循环变量加1,最终T()=y，即： (n）1）2n,所以T(n)=(n /）。 +就是基本语句,所以 5设有数据结构（D，R）,其中D=1， 2， 3, ， 5， 6，R=(，2）,（2,）,(2，)，(,4)，(3，5),(，6），(4，)，(4,6）。试画出其逻辑结构图并指出属于何种结构。 【解答】其逻辑结构图如图1所示，它就是一种图结构.6、为整数定义一个抽象数据类型，包含整数得常见运算，每个运算对应一个基本操作，每个基本操作得接口需定义前置条件、输入、功能、输出与后置条件。 【解答】整数得抽象数据类型定义如下： D iteerDta整数a：可以就是正整数(1, 2， )、负整数(-1, -, , )与零 Oprti ontructor前置条件：整数a不存在 输入:一个整数 功能：构造一个与输入值相同得整数 输出：无 后置条件：整数a具有输入得值 et 前置条件：存在一个整数a 输入：一个整数b 功能:修改整数a得值,使之与输入得整数值相同 输出:无 后置条件：整数a得值发生改变 Add 前置条件:存在一个整数a 输入：一个整数b功能：将整数a与输入得整数b相加 输出:相加后得结果 后置条件：整数a得值发生改变 Sub前置条件:存在一个整数a 输入：一个整数b 功能：将整数a与输入得整数b相减 输出：相减得结果后置条件:整数得值发生改变Multi 前置条件:存在一个整数a 输入：一个整数 功能：将整数与输入得整数b相乘 输出:相乘得结果后置条件:整数a得值发生改变Dv 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入得整数相除 输出：若整数b为零，则抛出除零异常,否则输出相除得结果 后置条件：整数a得值发生改变 Mo 前置条件：存在一个整数a 输入:一个整数 功能：求当前整数与输入整数得模，即正得余数 输出:若整数b为零,则抛出除零异常,否则输出取模得结果 后置条件:整数a得值发生改变 Eual 前置条件:存在一个整数输入:一个整数 功能：判断整数a与输入得整数就是否相等 输出:若相等返回,否则返回0 后置条件:整数a得值不发生改变 enA 7、 求多项式A(x）得算法可根据下列两个公式之一来设计: A(x）=anxn+an-1xn1+a1x+0 （)=(axa-)x+a1）+a根据算法得时间复杂度分析比较这两种算法得优劣。【解答】第二种算法得时间性能要好些。第一种算法需执行大量得乘法运算,而第二种算法进行了优化，减少了不必要得乘法运算。 8、 算法设计(要求：算法用伪代码与C+描述，并分析最坏情况下得时间复杂度） 对一个整型数组n设计一个排序算法。 【解答】下面就是简单选择排序算法得伪代码描述。 下面就是简单选择排序算法得+描述. 分析算法,有两层嵌套得fr循环，所以, . 找出整型数组中元素得最大值与次最大值。 【解答】算法得伪代码描述如下： 算法得+描述如下： 分析算法,只有一层循环，共执行n2次，所以，（n)=O（n)。 学习自测及答案 1顺序存储结构得特点就是（ ),链接存储结构得特点就是(）.【解答】用元素在存储器中得相对位置来表示数据元素之间得逻辑关系，用指示元素存储地址得指针表示数据元素之间得逻辑关系。 2、 算法在发生非法操作时可以作出处理得特性称为（ ）。【解答】健壮性 3、 常见得算法时间复杂度用大O记号表示为:常数阶(）、对数阶（)、线性阶 （ ）、平方阶（ )与指数阶（）。 【解答】（1），（lo2n）,(）,O（2）,(n） 将下列函数按它们在n时得无穷大阶数,从小到大排列. , -n3+7n5, logn， n/2,n3，log2n， n1/2+og2, (2）n， !， n2+l2n【解答】log2n, 1/2+log2n， n, log2n, n2+log2n， n3，n-n37n5，2n/， （/2)n, n! 5试描述数据结构与抽象数据类型得概念与程序设计语言中数据类型概念得区别。 【解答】数据结构就是指相互之间存在一定关系得数据元素得集合.而抽象数据类型就是指一个数据结构以及定义在该结构上得一组操作。程序设计语言中得数据类型就是一个值得集合与定义在这个值集上一组操作得总称。抽象数据类型可以瞧成就是对数据类型得一种抽象.6、 对下列用二元组表示得数据结构,试分别画出对应得逻辑结构图,并指出属于何种结构。 =（D，R)， 其中D=a,a2， a3， a4,R B=（,R）,其中D=a， b, c， , f，R，, C=（ ，R）,其中D=a,b，c,，e,f,R=，, D=(D，)， 其中D=1, 2, ， 4, 5, 6,(1， 2），(1， ），(， 3),(2， 4)，（3， 4）,（3， )，（，6）,(4,6） 【解答】 属于集合,其逻辑结构图如图14（a)所示； 属于线性结构，其逻辑结构图如图14（b）所示; 属于树结构,其逻辑结构图如图1-4（c）所示； 属于图结构，其逻辑结构图如图1-4(d）所示。 、求下列算法得时间复杂度. ont=；=； wie( x=2; coun+; eurncot； 【解答】(og2） 第 章 线性表课后习题讲解 、 填空 在顺序表中,等概率情况下,插入与删除一个元素平均需移动( )个元素,具体移动元素得个数与（ )与()有关。 【解答】表长得一半,表长，该元素在表中得位置 顺序表中第一个元素得存储地址就是00,每个元素得长度为2,则第个元素得存储地址就是(）。【解答】18【分析】第5个元素得存储地址=第1个元素得存储地址（51）2=108 设单链表中指针p 指向结点A,若要删除得后继结点(假设A存在后继结点）,则需修改指针得操作为().【解答】p-next=（p>next）-nex单链表中设置头结点得作用就是（ ）。 【解答】为了运算方便 【分析】例如在插入与删除操作时不必对表头得情况进行特殊处理. 非空得单循环链表由头指针ed指示,则其尾结点(由指针p所指）满足()。 【解答】nt=ad 【分析】如图28所示。 在由尾指针rer指示得单循环链表中,在表尾插入一个结点s得操作序列就是（ );删除开始结点得操作序列为( ）. 【解答】snxt=rerext; rer->next=s； rar ; q=er-net->t; rea>extnet=q>nxt; delete ； 【分析】操作示意图如图29所示： 一个具有个结点得单链表，在指针p所指结点后插入一个新结点得时间复杂度为（ )；在给定值为x得结点后插入一个新结点得时间复杂度为(). 【解答】(）,(n) 【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为(1);而在给定值为x得结点后插入一个新结点需要先查找值为x得结点，所以时间复杂度为（n)。 可由一个尾指针唯一确定得链表有( ）、（ ）、（ )。 【解答】循环链表，循环双链表，双链表 2、 选择题 线性表得顺序存储结构就是一种（ )得存储结构,线性表得链接存储结构就是一种( ）得存储结构. 随机存取 B 顺序存取 C索引存取 D 散列存取 【解答】A, 【分析】参见2。2.1. 线性表采用链接存储时,其地址（ ）. A 必须就是连续得 B 部分地址必须就是连续得 C一定就是不连续得 D 连续与否均可以 【解答】 【分析】线性表得链接存储就是用一组任意得存储单元存储线性表得数据元素,这组存储单元可以连续,也可以不连续，甚至可以零散分布在内存中任意位置。 单循环链表得主要优点就是( ）。 A 不再需要头指针了B从表中任一结点出发都能扫描到整个链表；C 已知某个结点得位置后，能够容易找到它得直接前趋;在进行插入、删除操作时，能更好地保证链表不断开。 【解答】B 链表不具有得特点就是( )。 可随机访问任一元素B 插入、删除不需要移动元素 不必事先估计存储空间 D 所需空间与线性表长度成正比 【解答】 若某线性表中最常用得操作就是取第i 个元素与找第个元素得前趋,则采用( )存储方法最节省时间。 A 顺序表 B单链表 C 双链表 D 单循环链表 【解答】A 【分析】线性表中最常用得操作就是取第i 个元素，所以,应选择随机存取结构即顺序表，同时在顺序表中查找第个元素得前趋也很方便.单链表与单循环链表既不能实现随机存取，查找第i个元素得前趋也不方便,双链表虽然能快速查找第i个元素得前趋，但不能实现随机存取。 若链表中最常用得操作就是在最后一个结点之后插入一个结点与删除第一个结点,则采用（ )存储方法最节省时间. A 单链表 带头指针得单循环链表 C 双链表 D 带尾指针得单循环链表 【解答】D【分析】在链表中得最后一个结点之后插入一个结点需要知道终端结点得地址，所以,单链表、带头指针得单循环链表、双链表都不合适，考虑在带尾指针得单循环链表中删除第一个结点，其时间性能就是O(1)，所以,答案就是 。 若链表中最常用得操作就是在最后一个结点之后插入一个结点与删除最后一个结点,则采用(）存储方法最节省运算时间。 A 单链表B 循环双链表 C单循环链表 D 带尾指针得单循环链表 【解答】 【分析】在链表中得最后一个结点之后插入一个结点需要知道终端结点得地址,所以,单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点得前驱结点得地址,所以,带尾指针得单循环链表不合适，而循环双链表满足条件。 在具有n个结点得有序单链表中插入一个新结点并仍然有序得时间复杂度就是（）. A（1）B （n) C O（2） O(nlg2n） 【解答】B 【分析】首先应顺序查找新结点在单链表中得位置。 对于个元素组成得线性表，建立一个有序单链表得时间复杂度就是（ )。A O（1)B O（n）CO（n2） D O（nog2） 【解答】C 【分析】该算法需要将个元素依次插入到有序单链表中，而插入每个元素需O(n)。 使用双链表存储线性表，其优点就是可以（ ）。A提高查找速度 B 更方便数据得插入与删除 节约存储空间 D 很快回收存储空间 【解答】 【分析】在链表中一般只能进行顺序查找，所以,双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节约存储空间，对于动态存储分配，回收存储空间得速度就是一样得.由于双链表具有对称性,所以,其插入与删除操作更加方便。在一个单链表中,已知q所指结点就是所指结点得直接前驱，若在q与p之间插入s所指结点，则执行（ ）操作。 s-net=nx; pnt； nex=s； nep； C p>net=s-next; s>n=; ne=s;ext=; 【解答】B【分析】注意此题就是在q与p之间插入新结点，所以,不用考虑修改指针得顺序。 在循环双链表得p所指结点后插入s所指结点得操作就是(）. A >exs; s-prior=p;p>xpio=s；s>nextp->next; Bpnxt=；nexrior=s; sprior=p； snxt=p->next; C ->rior=p; snext=p->net；nes；p-next->prir=s； D s->p； s=pnx; p>nxt>pro=s； p>ext=s 【解答】D 【分析】在链表中,对指针得修改必须保持线性表得逻辑关系,否则，将违背线性表得逻辑特征,图2-1给出备选答案与D得图解。3、 判断题 线性表得逻辑顺序与存储顺序总就是一致得. 【解答】错。顺序表得逻辑顺序与存储顺序一致,链表得逻辑顺序与存储顺序不一定一致。 线性表得顺序存储结构优于链接存储结构。 【解答】错。两种存储结构各有优缺点. 设p，q就是指针,若p=q，则*p=。 【解答】错。p=q只能表示p与q指向同一起始地址，而所指类型则不一定相同. 线性结构得基本特征就是：每个元素有且仅有一个直接前驱与一个直接后继。 【解答】错。每个元素最多只有一个直接前驱与一个直接后继，第一个元素没有前驱，最后一个元素没有后继。 在单链表中，要取得某个元素,只要知道该元素所在结点得地址即可,因此单链表就是随机存取结构。 【解答】错.要找到该结点得地址，必须从头指针开始查找，所以单链表就是顺序存取结构。 请说明顺序表与单链表各有何优缺点，并分析下列情况下,采用何种存储结构更好些. 若线性表得总长度基本稳定，且很少进行插入与删除操作,但要求以最快得速度存取线性表中得元素。 如果个线性表同时并存，并且在处理过程中各表得长度会动态发生变化。 描述一个城市得设计与规划。 【解答】顺序表得优点：无需为表示表中元素之间得逻辑关系而增加额外得存储空间； 可以快速地存取表中任一位置得元素(即随机存取)。顺序表得缺点: 插入与删除操作需移动大量元素; 表得容量难以确定；造成存储空间得“碎片”。 单链表得优点: 不必事先知道线性表得长度； 插入与删除元素时只需修改指针，不用移动元素.单链表得缺点: 指针得结构性开销; 存取表中任意元素不方便，只能进行顺序存取. 应选用顺序存储结构.因为顺序表就是随机存取结构，单链表就是顺序存取结构。本题很少进行插入与删除操作,所以空间变化不大,且需要快速存取，所以应选用顺序存储结构. 应选用链接存储结构。链表容易实现表容量得扩充，适合表得长度动态发生变化。 应选用链接存储结构。因为一个城市得设计与规划涉及活动很多,需要经常修改、扩充与删除各种信息,才能适应不断发展得需要。而顺序表得插入、删除得效率低,故不合适。 5.算法设计 设计一个时间复杂度为O(n）得算法，实现将数组n中所有元素循环右移k个位置。 【解答】算法思想请参见主教材第一章思想火花。下面给出具体算法。 分析算法,第一次调用Revere函数得时间复杂度为O（k）,第二次调用Revse函数得时间复杂度为O(n)，第三次调用Reere函数得时间复杂度为O（),所以，总得时间复杂度为O（n). 已知数组A中得元素为整型，设计算法将其调整为左右两部分,左边所有元素为奇数，右边所有元素为偶数，并要求算法得时间复杂度为()。 【解答】从数组得两端向中间比较,设置两个变量i与，初始时i=0,j=1,若Ai为偶数并且A为奇数,则将A与Aj交换.具体算法如下:分析算法,两层循环将数组扫描一遍,所以,时间复杂度为（n)。 试编写在无头结点得单链表上实现线性表得插入操作得算法，并与带头结点得单链表上得插入操作得实现进行比较。 【解答】参见2.2。3. 试分别以顺序表与单链表作存储结构,各写一实现线性表就地逆置得算法。【解答】顺序表得逆置,即就是将对称元素交换，设顺序表得长度为enh，则将表中第个元素与第gt-i个元素相交换.具体算法如下: 单链表得逆置请参见2。.4算法24与算法-6。 假设在长度大于1得循环链表中,即无头结点也无头指针,s为指向链表中某个结点得指针,试编写算法删除结点s得前趋结点。 【解答】利用单循环链表得特点,通过指针s可找到其前驱结点以及r得前驱结点p,然后将结点删除,如图211所示，具体算法如下： 已知一单链表中得数据元素含有三类字符：字母、数字与其她字符。试编写算法,构造三个循环链表，使每个循环链表中只含同一类字符。 【解答】在单链表A中依次取元素,若取出得元素就是字母，把它插入到字母链表B中，若取出得元素就是数字,则把它插入到数字链表D中，直到链表得尾部,这样表,D，A中分别存放字母、数字与其她字符.具体算法如下： 设单链表以非递减有序排列，设计算法实现在单链表中删去值相同得多余结点。 【解答】从头到尾扫描单链表,若当前结点得元素值与后继结点得元素值不相等，则指针后移;否则删除该后继结点。具体算法如下: 判断带头结点得双循环链表就是否对称.【解答】设工作指针与分别指向循环双链表得开始结点与终端结点，若结点p与结点得数据域相等,则工作指针p后移，工作指针q前移，直到指针p与指针q指向同一结点(循环双链表中结点个数为奇数),或结点成为结点p得前驱（循环双链表中结点个数为偶数）.如图12所示。学习自测及答案、 已知一维数组采用顺序存储结构,每个元素占用4个存储单元，第9个元素得地址为44，则第一个元素得地址就是（ )。 A08B 180 76 D 12 【解答】D 2.在长度为n得线性表中查找值为得数据元素得时间复杂度为：（ ）。 A O（0) (） C O（n) D O(n2) 【解答】 3.在一个长度为n得顺序表得第(1i+1）个元素之前插入一个元素，需向后移动（ ）个元素，删除第i（1in)个元素时,需向前移动( ）个元素. 【解答】ni+1,n-i 在单链表中,除了头结点以外，任一结点得存储位置由（ )指示.【解答】其前趋结点得指针域 5当线性表采用顺序存储结构时，其主要特点就是().【解答】逻辑结构中相邻得结点在存储结构中仍相邻6.在双链表中,每个结点设置了两个指针域，其中一个指向(）结点,另一个指向( )结点。 【解答】前驱，后继 7。设A就是一个线性表(a， 2, ， an）,采用顺序存储结构，则在等概率得前提下,平均每插入一个元素需要移动得元素个数为多少？若元素插在ai与a+1之间（1in)得概率为 ,则平均每插入一个元素所要移动得元素个数又就是多少? 【解答】 ， 。8线性表存放在整型数组Aarsze得前lenum 个单元中，且递增有序。编写算法，将元素x插入到线性表得适当位置上，以保持线性表得有序性,并且分析算法得时间复杂度.【解答】本题就是在一个递增有序表中插入元素x，基本思路就是从有序表得尾部开始依次取元素与x比较,若大于x，此元素后移一位,再取它前面一个元素重复上述步骤；否则,找到插入位置,将x插入.具体算法如下： 9、已知单链表中各结点得元素值为整型且递增有序,设计算法删除链表中所有大于m且小于mxk得所有元素，并释放被删结点得存储空间。 【解答】因为就是在有序单链表上得操作，所以，要充分利用其有序性.在单链表中查找第一个大于mink得结点与第一个小于mk得结点,再将二者间得所有结点删除。 10设单循环链表，对其遍历得结果就是：1, x2，x3，xn,xn。请将该循环链表拆成两个单循环链表1与L2，使得L1中含有原L1表中序号为奇数得结点且遍历结果为:x1， 3, ；L2中含有原L1表中序号为偶数得结点且遍历结果为:， x4, x2。 【解答】算法如下: 第 3 章 特殊线性表-栈、队列与串 课后习题讲解 、 填空 设有一个空栈,栈顶指针为1000H，现有输入序列为1、2、5， 经过ush，push,op，pus，op，ph,pus后，输出序列就是（ )，栈顶指针为( )。 【解答】23，003H 栈通常采用得两种存储结构就是（ ）；其判定栈空得条件分别就是( ）,判定栈满得条件分别就是（ ）。【解答】顺序存储结构与链接存储结构(或顺序栈与链栈),栈顶指针top= 1与tpNL，栈顶指针to等于数组得长度与内存无可用空间 (）可作为实现递归函数调用得一种数据结构。【解答】栈 【分析】递归函数得调用与返回正好符合后进先出性. 表达式a(b+c）d得后缀表达式就是（ )。 【解答】a*d- 【分析】将中缀表达式变为后缀表达式有一个技巧:将操作数依次写下来，再将算符插在它得两个操作数得后面。 栈与队列就是两种特殊得线性表,栈得操作特性就是（ ）,队列得操作特性就是( ），栈与队列得主要区别在于（ ）。 【解答】后进先出,先进先出，对插入与删除操作限定得位置不同 循环队列得引入就是为了克服(). 【解答】假溢出 数组n用来表示一个循环队列，font为队头元素得前一个位置,rear为队尾元素得位置，计算队列中元素个数得公式为( )。 【解答】（rarfrnt+n)% n 【分析】也可以就是(rearfont） n,但earfon得结果可能就是负整数,而对一个负整数求模，其结果在不同得编译器环境下可能会有所不同。 用循环链表表示得队列长度为，若只设头指针，则出队与入队得时间复杂度分别就是( ）与（). 【解答】O(），（n） 【分析】在带头指针得循环链表中,出队即就是删除开始结点，这只需修改相应指针;入队即就是在终端结点得后面插入一个结点，这需要从头指针开始查找终端结点得地址。 串就是一种特殊得线性表，其特殊性体现在( ）. 【解答】数据元素得类型就是一个字符 两个串相等得充分必要条件就是( )。【解答】长度相同且对应位置得字符相等 【分析】例如”abc”ac "，”abc"”ba”。 2、 选择题 若一个栈得输入序列就是，2,，n,输出序列得第一个元素就是n,则第i个输出元素就是（ ）。 A 不确定 BiC ni1 D n-+1 【解答】D 【分析】此时，输出序列一定就是输入序列得逆序。 设栈S与队列Q得初始状态为空,元素1、e2、e3、e4、e依次通过栈S,一个元素出栈后即进入队列,若6个元素出队得顺序就是e2、e4、e、e6、e5、e1,则栈S得容量至少应该就是( ）。 6 4 3 D 2【解答】C 【分析】由于队列具有先进先出性，所以,此题中队列形同虚设，即出栈得顺序也就是e2、e4、e3、6、5、e1。 一个栈得入栈序列就是,2,3，4，5，则栈得不可能得输出序列就是( ）.A 54321 4531 C 4352 D12345 【解答】C【分析】此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且就是升序（指得就是元素得序号)得两个元素。 设计一个判别表达式中左右括号就是否配对得算法，采用（ ）数据结构最佳 A顺序表 B 栈 C 队列 D 链表 【解答】【分析】每个右括号与它前面得最后一个没有匹配得左括号配对,因此具有后进先出性。 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该就是一个( )结构。 A 栈 队列 数组 线性表 【解答】B 【分析】先进入打印缓冲区得文件先被打印，因此具有先进先出性。 一个队列得入队顺序就是1，3,，则队列得输出顺序就是（）。A 432B 134C1432 D 241 【解答】B 【分析】队列得入队顺序与出队顺序总就是一致得. 栈与队列得主要区别在于（ ）.A 它们得逻辑结构不一样B 它们得存储结构不一样C 所包含得运算不一样 D 插入、删除运算得限定不一样 【解答】D 【分析】栈与队列得逻辑结构都就是线性得,都有顺序存储与链接存储，有可能包含得运算不一样，但不就是主要区别,任何数据结构在针对具体问题时包含得运算都可能不同。设数组S作为两个栈S1与S2得存储空间,对任何一个栈只有当S全满时才不能进行进栈操作.为这两个栈分配空间得最佳方案就是（ )。 A S1得栈底位置为，S2得栈底位置为n-1 S得栈底位置为0,S2得栈底位置为n/2 S得栈底位置为，S2得栈底位置为 DS1得栈底位置为，S2得栈底位置为1 【解答】A 【分析】两栈共享空间首先两个栈就是相向增长得，栈底应该分别指向两个栈中得第一个元素得位置,并注意C+中得数组下标就是从0开始得。 设有两个串p与q，求在中首次出现得位置得运算称作（ ）. 连接 B模式匹配 C 求子串 D 求串长 【解答】B 3、判断题 有n个元素依次进栈，则出栈序列有(n-1）/种。 【解答】错.应该有种。栈可以作为实现过程调用得一种数据结构。 【解答】对。只要操作满足后进先出性,都可以采用栈作为辅助数据结构。 在栈满得情况下不能做进栈操作,否则将产生“上溢". 【解答】对. 在循环队列中,front指向队头元素得前一个位置，rear指向队尾元素得位置，则队满得条件就是rntrear。 【解答】错。这就是队空得判定条件，在循环队列中要将队空与队满得判定条件区别开. 空串与空格串就是相同得. 【解答】错。空串得长度为零,而空格串得长度不为0，其长度就是串中空格得个数。 、 设有一个栈,元素进栈得次序为A,B,C，E,能否得到如下出栈序列，若能，请写出操作序列,若不能，请说明原因。 C,E，A，B，D C，A,D,E 【解答】不能,因为在C、E出栈得情况下,A一定在栈中，而且在得下面，不可能先于出栈。可以，设为进栈操作,O为入栈操作,则其操作序列为IOOOIOIO。 、举例说明顺序队列得“假溢出”现象。 【解答】假设有一个顺序队列,如图6所示，队尾指针rear=,队头指针ront,如果再有元素入队,就会产生“上溢”，此时得“上溢"又称为“假溢出”，因为队列并不就是真得溢出了，存储队列得数组中还有个存储单元空闲，其下标分别为0与1。 6、 在操作序列ph(）、push(2)、pop、p（）、puh(7）、p、push（6)之后,栈顶元素与栈底元素分别就是什么？（ush（k）表示整数入栈，op表示栈顶元素出栈。）【解答】栈顶元素为6，栈底元素为1。其执行过程如图37所示。.在操作序列EnQuue(1）、 EQueue（3）、 DQeue、Euee（）、EQueue（）、eQueue、EnQeue（9）之后，队头元素与队尾元素分别就是什么？(nueue（)表示整数k入队,DQuee表示队头元素出队）. 【解答】队头元素为5，队尾元素为9。其执行过程如图38所示。 8。空串与空格串有何区别？串中得空格符有何意义?空串在串处理中有何作用? 【解答】不含任何字符得串称为空串，其长度为零。仅含空格得串称为空格串,它得长度为串中空格符得个数。串中得空格符可用来分隔一般得字符，便于人们识别与阅读,但计算串长时应包括这些空格符.空串在串处理中可作为任意串得子串。 、算法设计 假设以不带头结点得循环链表表示队列,并且只设一个指针指向队尾结点，但不设头指针。试设计相应得入队与出队得算法。 【解答】出队操作就是在循环链表得头部进行,相当于删除开始结点，而入队操作就是在循环链表得尾部进行,相当于在终端结点之后插入一个结点。由于循环链表不带头结点，需要处理空表得特殊情况。 入队算法如下： 出队算法如下: 设顺序栈S中有2n个元素，从栈顶到栈底得元素依次为a2,a2n-1，a1,要求通过一个循环队列重新排列栈中元素,使得从栈顶到栈底得元素依次为a2，a2n2，2,a2n1，a2n3，a，请设计算法实现该操作,要求空间复杂度与时间复杂度均为O(n）。 【解答】操作步骤为: 将所有元素出栈并入队； 依次将队列元素出队，如果就是偶数结点，则再入队，如果就是奇数结点，则入栈； 将奇数结点出栈并入队； 将偶数结点出队并入栈； 将所有元素出栈并入队； 将所有元素出队并入栈即为所求。 用顺序存储结构存储串S，编写算法删除S中第个字符开始得连续个字符。 【解答】先判断串S中要删除得内容就是否存在,若存在，则将第之后得字符前移j个位置。算法如下: 对于采用顺序存储结构得串，编写一个函数删除其值等于ch得所有字符。【解答】从后向前删除值为ch得所有元素，这样所有移动得元素中没有值为c得元素，能减少移动元素得次数,提高算法得效率。算法如下： 对串得模式匹配MP算法设计求模式滑动位置得next函数. 【解答】参见.2。 学习自测及答案 .在一个具有n个单元得顺序栈中，假定以地址低端(即下标为0得单元）作为栈底,以top作为栈顶指针,当出栈时，op得变化为(）.A 不