资源描述
数据结构之数据结构之线性结构习题课王建芳2011.04.06重点讲解学生为主以练促学以练促教填空1.1.数据的存储结构主要有（数据的存储结构主要有（）和（）和（）两种基本方法，不论哪）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（种存储结构，都要存储两方面的内容：（）和（）。）和（）。【解答解答】顺序存储结构，链接存储结构，数据元素，数据元素顺序存储结构，链接存储结构，数据元素，数据元素之间的关系之间的关系2.2.算法具有五个特性，分别是（算法具有五个特性，分别是（）、（）、（）、（）、（）、（）、（）、）、（）。）。【解答解答】有零个或多个输入，有一个或多个输出，有穷性，确有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性定性，可行性3.3.算法的描述方法通常有（算法的描述方法通常有（）、（）、（）、（）、（）和（）和（）四种，）四种，其中，（其中，（）被称为算法语言。）被称为算法语言。【解答解答】自然语言，程序设计语言，流程图，伪代码，伪代码自然语言，程序设计语言，流程图，伪代码，伪代码4.4.在顺序表中，等概率情况下，插入和删除一个元素平均需移在顺序表中，等概率情况下，插入和删除一个元素平均需移动（动（）个元素，具体移动元素的个数与（）个元素，具体移动元素的个数与（）和（）有关。）和（）有关。【解答解答】表长的一半，表长，该元素在表中的位置表长的一半，表长，该元素在表中的位置5.5.单链表中设置头结点的作用是（单链表中设置头结点的作用是（）。）。【解答解答】为了运算方便为了运算方便【分析分析】例如在插入和删除操作时不必对表头的情况进行特殊例如在插入和删除操作时不必对表头的情况进行特殊处理。处理。6.6.非空的单循环链表由头指针非空的单循环链表由头指针headhead指示，则其尾结点（由指针指示，则其尾结点（由指针p p所指）满足（所指）满足（）。）。【解答解答】p-next=headp-next=head【分析分析】如图所示。如图所示。7.7.在由尾指针在由尾指针rearrear指示的单循环链表中，在表尾插入一个结点指示的单循环链表中，在表尾插入一个结点s s的操作序列的操作序列是（是（）；删除开始结点的操作序列为（）；删除开始结点的操作序列为（）。）。【解答解答】s-next=rear-next;rear-next=s;rear=s;s-next=rear-next;rear-next=s;rear=s;q=rear-next-next;rear-next-next=q-next;delete q;q=rear-next-next;rear-next-next=q-next;delete q;【分析分析】操作示意图如图所示：操作示意图如图所示：8.8.一个具有一个具有n n个结点的单链表，在指针个结点的单链表，在指针p p所指结点后插入一个新所指结点后插入一个新结点的时间复杂度为（结点的时间复杂度为（）；在给定值为）；在给定值为x x的结点后的结点后插入一个新结点的时间复杂度为（插入一个新结点的时间复杂度为（）。）。【解答解答】(1)(1)，(n)n)【分析分析】在在p p所指结点后插入一个新结点只需修改指针，所以时所指结点后插入一个新结点只需修改指针，所以时间复杂度为间复杂度为(1)(1)；而在给定值为；而在给定值为x x的结点后插入一的结点后插入一个新结点需要先查找值为个新结点需要先查找值为x x的结点，所以时间复杂度为的结点，所以时间复杂度为(n(n)。9.9.可由一个尾指针唯一确定的链表有（可由一个尾指针唯一确定的链表有（）、（）、（）、（）、（）。）。【解答解答】循环链表，循环双链表，双链表循环链表，循环双链表，双链表10.10.设有一个空栈，栈顶指针为设有一个空栈，栈顶指针为1000H1000H，现有输入序列为，现有输入序列为1 1、2 2、3 3、4 4、5 5，经过经过pushpush，pushpush，poppop，pushpush，poppop，pushpush，pushpush后，后，输出序列是（输出序列是（），栈顶指针为（），栈顶指针为（）。）。【解答解答】2323，1003H1003H11.11.栈通常采用的两种存储结构是（栈通常采用的两种存储结构是（）；其判定栈空的条件分）；其判定栈空的条件分别是（别是（），判定栈满的条件分别是（），判定栈满的条件分别是（）。）。【解答解答】顺序存储结构和链接存储结构（或顺序栈和链栈），顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针栈顶指针top=-1top=-1和和top=NULLtop=NULL，栈顶指针，栈顶指针toptop等于数组的长度等于数组的长度和内存无可用空间和内存无可用空间12.12.栈和队列是两种特殊的线性表，栈的操作特性是（栈和队列是两种特殊的线性表，栈的操作特性是（），队），队列的操作特性是（列的操作特性是（），栈和队列的主要区别在于（）。），栈和队列的主要区别在于（）。【解答解答】后进先出，先进先出，对插入和删除操作限定的位置后进先出，先进先出，对插入和删除操作限定的位置不同不同13.13.循环队列的引入是为了克服（循环队列的引入是为了克服（）。）。【解答解答】假溢出假溢出14.14.数组数组QnQn 用来表示一个循环队列，用来表示一个循环队列，frontfront为队头元素的前一为队头元素的前一个位置，个位置，rearrear为队尾元素的位置，计算队列中元素个数的公为队尾元素的位置，计算队列中元素个数的公式为（式为（）。）。【解答解答】（rear-rear-front+nfront+n）%n%n【分析分析】也可以是（也可以是（rear-frontrear-front）%n%n，但，但rear-frontrear-front的结果可的结果可能是负整数，而对一个负整数求模，其结果在不同的编译器能是负整数，而对一个负整数求模，其结果在不同的编译器环境下可能会有所不同。环境下可能会有所不同。15.15.用循环链表表示的队列长度为用循环链表表示的队列长度为n n，若只设头指针，则出队和，若只设头指针，则出队和入队的时间复杂度分别是（入队的时间复杂度分别是（）和（）和（）。）。【解答解答】(1)(1)，(n)(n)【分析分析】在带头指针的循环链表中，出队即是删除开始结点，在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。插入一个结点，这需要从头指针开始查找终端结点的地址。16.16.串是一种特殊的线性表，其特殊性体现在（串是一种特殊的线性表，其特殊性体现在（）。）。【解答解答】数据元素的类型是一个字符数据元素的类型是一个字符17.17.两个串相等的充分必要条件是（两个串相等的充分必要条件是（）。）。【解答解答】长度相同且对应位置的字符相等长度相同且对应位置的字符相等【分析分析】例如例如 abcabcabcabc ，abcbcaabcbca 选择题1.1.算法指的是（算法指的是（）。）。A A 对特定问题求解步骤的一种描述，是指令的有限序列。对特定问题求解步骤的一种描述，是指令的有限序列。B B 计算机程序计算机程序 C C 解决问题的计算方法解决问题的计算方法 D D 数据处理数据处理【解答解答】A A【分析分析】计算机程序是对算法的具体实现；简单地说，算法是计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有解决问题的方法；数据处理是通过算法完成的。所以，只有A A是算法的准确定义。是算法的准确定义。2.2.下面（下面（）不是算法所必须具备的特性。）不是算法所必须具备的特性。A A 有穷性有穷性 B B 确切性确切性 C C 高效性高效性 D D 可行性可行性【解答解答】C C【分析分析】高效性是好算法应具备的特性。高效性是好算法应具备的特性。3.3.算法分析的目的是（算法分析的目的是（），算法分析的两个主要方面是（），算法分析的两个主要方面是（）。）。A A 找出数据结构的合理性找出数据结构的合理性 B B 研究算法中输入和输出的关系研究算法中输入和输出的关系C C 分析算法的效率以求改进分析算法的效率以求改进 D D 分析算法的易读性和文档性分析算法的易读性和文档性E E 空间性能和时间性能空间性能和时间性能 F F 正确性和简明性正确性和简明性G G 可读性和文档性可读性和文档性 H H 数据复杂性和程序复杂性数据复杂性和程序复杂性【解答解答】C C，E E4.4.线性表采用链接存储时，其地址（线性表采用链接存储时，其地址（）。）。A A 必须是连续的必须是连续的 B B 部分地址必须是连续的部分地址必须是连续的C C 一定是不连续的一定是不连续的 D D 连续与否均可以连续与否均可以【解答解答】D D【分析分析】线性表的链接存储是用一组任意的存储单元存储线性线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。连续，甚至可以零散分布在内存中任意位置。5.5.单循环链表的主要优点是（单循环链表的主要优点是（）。）。A A 不再需要头指针了不再需要头指针了B B 从表中任一结点出发都能扫描到整个链表；从表中任一结点出发都能扫描到整个链表；C C 已知某个结点的位置后，能够容易找到它的直接前趋；已知某个结点的位置后，能够容易找到它的直接前趋；D D 在进行插入、删除操作时，能更好地保证链表不断开。在进行插入、删除操作时，能更好地保证链表不断开。【解答解答】B B6.6.链表不具有的特点是（链表不具有的特点是（）。）。A A 可随机访问任一元素可随机访问任一元素 B B 插入、删除不需要移动元素插入、删除不需要移动元素C C 不必事先估计存储空间不必事先估计存储空间 D D 所需空间与线性表长度成正比所需空间与线性表长度成正比【解答解答】A A7.7.若某线性表中最常用的操作是取第若某线性表中最常用的操作是取第i i 个元素和找第个元素和找第i i个元素的个元素的前趋，则采用（前趋，则采用（）存储方法最节省时间。）存储方法最节省时间。A A 顺序表顺序表 B B 单链表单链表 C C 双链表双链表 D D 单循环链表单循环链表【解答解答】A A【分析分析】线性表中最常用的操作是取第线性表中最常用的操作是取第i i 个元素，所以，应选个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第择随机存取结构即顺序表，同时在顺序表中查找第i i个元素个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第查找第i i个元素的前趋也不方便，双链表虽然能快速查找第个元素的前趋也不方便，双链表虽然能快速查找第i i个元素的前趋，但不能实现随机存取。个元素的前趋，但不能实现随机存取。8.8.若链表中最常用的操作是在最后一个结点之后插入一个结点若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（和删除第一个结点，则采用（）存储方法最节省时间。）存储方法最节省时间。A A 单链表单链表 B B 带头指针的单循环链表带头指针的单循环链表 C C 双链表双链表 D D 带尾指针的单带尾指针的单循环链表循环链表【解答解答】D D【分析分析】在链表中的最后一个结点之后插入一个结点需要知道在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、带头指针的单循环链表、终端结点的地址，所以，单链表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第一双链表都不合适，考虑在带尾指针的单循环链表中删除第一个结点，其时间性能是个结点，其时间性能是O(1)O(1)，所以，答案是，所以，答案是D D9.9.若链表中最常用的操作是在最后一个结点之后插入一个结点若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（和删除最后一个结点，则采用（）存储方法最节省运算时）存储方法最节省运算时间。间。A A 单链表单链表 B B 循环双链表循环双链表 C C单循环链表单循环链表 D D 带尾指针的单循带尾指针的单循环链表环链表【解答解答】B B【分析分析】在链表中的最后一个结点之后插入一个结点需要知道在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、单循环链表都不合适，删终端结点的地址，所以，单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点的前驱结点的地址，所以，除最后一个结点需要知道终端结点的前驱结点的地址，所以，带尾指针的单循环链表不合适，而循环双链表满足条件。带尾指针的单循环链表不合适，而循环双链表满足条件。10.10.在具有在具有n n个结点的有序单链表中插入一个新结点并仍然有序个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（的时间复杂度是（）。）。A O(1)B O(n)C O(n2)D O(nlog2n)A O(1)B O(n)C O(n2)D O(nlog2n)【解答解答】B B【分析分析】首先应顺序查找新结点在单链表中的位置。首先应顺序查找新结点在单链表中的位置。11.11.对于对于n n个元素组成的线性表，建立一个有序单链表的时间复个元素组成的线性表，建立一个有序单链表的时间复杂度是（杂度是（）。）。A O(1)B O(n)C O(n2)D O(nlog2n)A O(1)B O(n)C O(n2)D O(nlog2n)【解答解答】C C【分析分析】该算法需要将该算法需要将n n个元素依次插入到有序单链表中，而插个元素依次插入到有序单链表中，而插入每个元素需入每个元素需O(nO(n)。12.12.使用双链表存储线性表，其优点是可以（使用双链表存储线性表，其优点是可以（）。）。A A 提高查找速度提高查找速度 B B 更方便数据的插入和删除更方便数据的插入和删除C C 节约存储空间节约存储空间 D D 很快回收存储空间很快回收存储空间【解答解答】B B【分析分析】在链表中一般只能进行顺序查找，所以，双链表并不在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节能提高查找速度，因为双链表中有两个指针域，显然不能节约存储空间，对于动态存储分配，回收存储空间的速度是一约存储空间，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，所以，其插入和删除操作更样的。由于双链表具有对称性，所以，其插入和删除操作更加方便。加方便。13.13.在一个单链表中，已知在一个单链表中，已知q q所指结点是所指结点是p p所指结点的直接前驱，所指结点的直接前驱，若在若在q q和和p p之间插入之间插入s s所指结点，则执行（所指结点，则执行（）操作。）操作。A s-next=p-next;p-next=s;B q-next=s;s-next=p;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;C p-next=s-next;s-next=p;D p-next=s;s-next=q;【解答解答】B B【分析分析】注意此题是在注意此题是在q q和和p p之间插入新结点，所以，不用考虑之间插入新结点，所以，不用考虑修改指针的顺序。修改指针的顺序。201004062010040614.14.在循环双链表的在循环双链表的p p所指结点后插入所指结点后插入s s所指结点的操作是（所指结点的操作是（）。）。A p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;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;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;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=sD s-prior=p;s-next=p-next;p-next-prior=s;p-next=s【解答解答】D D【分析分析】在链表中，对指针的修改必须保持线性表的逻辑关系，否则，将违在链表中，对指针的修改必须保持线性表的逻辑关系，否则，将违背线性表的逻辑特征。背线性表的逻辑特征。15.15.若一个栈的输入序列是若一个栈的输入序列是1 1，2 2，3 3，n n，输出序列的第一，输出序列的第一个元素是个元素是n n，则第，则第i i个输出元素是（个输出元素是（）。）。A A 不确定不确定 B n-i C n-i-1 D n-i+1B n-i C n-i-1 D n-i+1【解答解答】D D【分析分析】此时，输出序列一定是输入序列的逆序。此时，输出序列一定是输入序列的逆序。1616从栈顶指针为从栈顶指针为toptop的链栈中删除一个结点，用的链栈中删除一个结点，用x x保存被删除保存被删除结点的值，则执行（结点的值，则执行（）。）。A x=top;top=A x=top;top=toptop-next;B x=top-data;-next;B x=top-data;C top=C top=toptop-next;x=top-data;D x=top-data;top=-next;x=top-data;D x=top-data;top=toptop-next;next;【解答解答】D D17.17.设设S=I_ am_ a_ S=I_ am_ a_ teactherteacther，其长度为（，其长度为（）。）。【解答解答】151518.18.设栈设栈S S和队列和队列Q Q的初始状态为空，元素的初始状态为空，元素e1e1、e2e2、e3e3、e4e4、e5e5、e6e6依次通过依次通过栈栈S S，一个元素出栈后即进入队列，一个元素出栈后即进入队列Q Q，若，若6 6个元素出队的顺序是个元素出队的顺序是e2e2、e4e4、e3e3、e6e6、e5e5、e1e1，则栈，则栈S S的容量至少应该是（的容量至少应该是（）。）。A 6A 6 B 4B 4 C 3C 3 D 2D 2【解答解答】C C【分析分析】由于队列具有先进先出性，所以，此题中队列形同虚设，即出栈的由于队列具有先进先出性，所以，此题中队列形同虚设，即出栈的顺序也是顺序也是e2e2、e4e4、e3e3、e6e6、e5e5、e1e1。19.19.一个栈的入栈序列是一个栈的入栈序列是1 1，2 2，3 3，4 4，5 5，则栈的不可能的输出序列是（，则栈的不可能的输出序列是（）。）。A 54321 B 45321 C 43512 D 12345A 54321 B 45321 C 43512 D 12345【解答解答】C C【分析分析】此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序（指的是元素的序号）的两个元素。并且是升序（指的是元素的序号）的两个元素。20.20.设计一个判别表达式中左右括号是否配对的算法，采用（设计一个判别表达式中左右括号是否配对的算法，采用（）数据结构）数据结构最佳最佳A A 顺序表顺序表 B B 栈栈 C C 队列队列 D D 链表链表【解答解答】B B【分析分析】每个右括号与它前面的最后一个没有匹配的左括号配对，因此具有每个右括号与它前面的最后一个没有匹配的左括号配对，因此具有后进先出性。后进先出性。21.21.在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（冲区，该缓冲区应该是一个（）结构。）结构。A A 栈栈 B B队列队列 C C 数组数组 D D线性表线性表【解答解答】B B【分析分析】先进入打印缓冲区的文件先被打印，因此具有先进先出性。先进入打印缓冲区的文件先被打印，因此具有先进先出性。23.23.一个队列的入队顺序是一个队列的入队顺序是1 1，2 2，3 3，4 4，则队列的输出顺序是（，则队列的输出顺序是（）。）。A 4321 B 1234 C 1432 D 3241A 4321 B 1234 C 1432 D 3241【解答解答】B B【分析分析】队列的入队顺序和出队顺序总是一致的。队列的入队顺序和出队顺序总是一致的。24.24.栈和队列的主要区别在于（栈和队列的主要区别在于（）。）。A A 它们的逻辑结构不一样它们的逻辑结构不一样 B B 它们的存储结构不一样它们的存储结构不一样C C 所包含的运算不一样所包含的运算不一样 D D 插入、删除运算的限定不一样插入、删除运算的限定不一样【解答解答】D D【分析分析】栈和队列的逻辑结构都是线性的，都有顺序存储和链栈和队列的逻辑结构都是线性的，都有顺序存储和链接存储，有可能包含的运算不一样，但不是主要区别，任何接存储，有可能包含的运算不一样，但不是主要区别，任何数据结构在针对具体问题时包含的运算都可能不同。数据结构在针对具体问题时包含的运算都可能不同。25.25.设数组设数组SnSn 作为两个栈作为两个栈S1S1和和S2S2的存储空间，对任何一个栈只的存储空间，对任何一个栈只有当有当SnSn 全满时才不能进行进栈操作。为这两个栈分配空间全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（的最佳方案是（）。）。A S1A S1的栈底位置为的栈底位置为0 0，S2S2的栈底位置为的栈底位置为n-1n-1B S1B S1的栈底位置为的栈底位置为0 0，S2S2的栈底位置为的栈底位置为n/2n/2C S1C S1的栈底位置为的栈底位置为0 0，S2S2的栈底位置为的栈底位置为n nD S1D S1的栈底位置为的栈底位置为0 0，S2S2的栈底位置为的栈底位置为1 1【解答解答】A A【分析分析】两栈共享空间首先两个栈是相向增长的，栈底应该分两栈共享空间首先两个栈是相向增长的，栈底应该分别指向两个栈中的第一个元素的位置，并注意别指向两个栈中的第一个元素的位置，并注意C+C+中的数组中的数组下标是从下标是从0 0开始的。开始的。26.26.设有两个串设有两个串p p和和q q，求，求q q在在p p中首次出现的位置的运算称作（中首次出现的位置的运算称作（）。）。A A 连接连接 B B 模式匹配模式匹配 C C 求子串求子串 D D 求串长求串长【解答解答】B B判断题 算法的时间复杂度都要通过算法中的基本语句的执行次数来算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。确定。【解答解答】错。时间复杂度要通过算法中基本语句执行次数的数错。时间复杂度要通过算法中基本语句执行次数的数量级来确定。量级来确定。每种数据结构都具备三个基本操作：插入、删除和查找。每种数据结构都具备三个基本操作：插入、删除和查找。【解答解答】错。如数组就没有插入和删除操作。此题注意是每种错。如数组就没有插入和删除操作。此题注意是每种数据结构。数据结构。所谓数据的逻辑结构指的是数据之间的逻辑关系。所谓数据的逻辑结构指的是数据之间的逻辑关系。【解答解答】错。是数据之间的逻辑关系的整体。错。是数据之间的逻辑关系的整体。逻辑结构与数据元素本身的内容和形式无关。逻辑结构与数据元素本身的内容和形式无关。【解答解答】对。因此逻辑结构是数据组织的主要方面。对。因此逻辑结构是数据组织的主要方面。基于某种逻辑结构之上的基本操作，其实现是唯一的。基于某种逻辑结构之上的基本操作，其实现是唯一的。【解答解答】错。基本操作的实现是基于某种存储结构设计的，因错。基本操作的实现是基于某种存储结构设计的，因而不是唯一的。而不是唯一的。6.6.线性表的逻辑顺序和存储顺序总是一致的。线性表的逻辑顺序和存储顺序总是一致的。【解答解答】错。顺序表的逻辑顺序和存储顺序一致，链表的逻辑错。顺序表的逻辑顺序和存储顺序一致，链表的逻辑顺序和存储顺序不一定一致。顺序和存储顺序不一定一致。7.7.线性表的顺序存储结构优于链接存储结构。线性表的顺序存储结构优于链接存储结构。【解答解答】错。两种存储结构各有优缺点。错。两种存储结构各有优缺点。8.8.设设p p，q q是指针，若是指针，若p=qp=q，则，则*p=*qp=*q。【解答解答】错。错。p=qp=q只能表示只能表示p p和和q q指向同一起始地址，而所指类型指向同一起始地址，而所指类型则不一定相同。则不一定相同。9.9.线性结构的基本特征是：每个元素有且仅有一个直接前驱和线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。一个直接后继。【解答解答】错。每个元素最多只有一个直接前驱和一个直接后继，错。每个元素最多只有一个直接前驱和一个直接后继，第一个元素没有前驱，最后一个元素没有后继。第一个元素没有前驱，最后一个元素没有后继。10.10.在单链表中，要取得某个元素，只要知道该元素所在结点的在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。地址即可，因此单链表是随机存取结构。【解答解答】错。要找到该结点的地址，必须从头指针开始查找，错。要找到该结点的地址，必须从头指针开始查找，所以单链表是顺序存取结构。所以单链表是顺序存取结构。11.11.有有n n个元素依次进栈，则出栈序列有个元素依次进栈，则出栈序列有(n-1)/2(n-1)/2种。种。【解答解答】错。应该有错。应该有 种。种。12.12.栈可以作为实现过程调用的一种数据结构。栈可以作为实现过程调用的一种数据结构。【解答解答】对。只要操作满足后进先出性，都可以采用栈作为辅对。只要操作满足后进先出性，都可以采用栈作为辅助数据结构。助数据结构。13.13.在栈满的情况下不能做进栈操作，否则将产生在栈满的情况下不能做进栈操作，否则将产生“上溢上溢”。【解答解答】对。对。14.14.在循环队列中，在循环队列中，frontfront指向队头元素的前一个位置，指向队头元素的前一个位置，rearrear指指向队尾元素的位置，则队满的条件是向队尾元素的位置，则队满的条件是front=rearfront=rear。【解答解答】错。这是队空的判定条件，在循环队列中要将队空和错。这是队空的判定条件，在循环队列中要将队空和队满的判定条件区别开。队满的判定条件区别开。15.15.空串与空格串是相同的。空串与空格串是相同的。【解答解答】错。空串的长度为零，而空格串的长度不为错。空串的长度为零，而空格串的长度不为0 0，其长度，其长度是串中空格的个数。是串中空格的个数。分析题4 4请说明顺序表和单链表各有何优缺点，并分析下列情况下，请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。采用何种存储结构更好些。若线性表的总长度基本稳定，且很少进行插入和删除操作，若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。但要求以最快的速度存取线性表中的元素。如果如果n n个线性表同时并存，并且在处理过程中各表的长度会个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。动态发生变化。描述一个城市的设计和规划。描述一个城市的设计和规划。【解答解答】顺序表的优点：顺序表的优点：无需为表示表中元素之间的逻辑关系而增加额外的存储空无需为表示表中元素之间的逻辑关系而增加额外的存储空 可以快速地存取表中任一位置的元素（即随机存取）。可以快速地存取表中任一位置的元素（即随机存取）。顺序表的缺点：顺序表的缺点：插入和删除操作需移动大量元素；插入和删除操作需移动大量元素；表的容量难以确定；表的容量难以确定；造成存储空间的造成存储空间的“碎片碎片”。单链表的优点：单链表的优点：不必事先知道线性表的长度；不必事先知道线性表的长度；插入和删除元素时只需修改指针，不用移动元素。单链表的插入和删除元素时只需修改指针，不用移动元素。单链表的缺点：缺点：指针的结构性开销；指针的结构性开销；存取表中任意元素不方便，只能进行顺序存取。存取表中任意元素不方便，只能进行顺序存取。应选用顺序存储结构。因为顺序表是随机存取结构，单链表应选用顺序存储结构。因为顺序表是随机存取结构，单链表是顺序存取结构。本题很少进行插入和删除操作，所以空间是顺序存取结构。本题很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。变化不大，且需要快速存取，所以应选用顺序存储结构。应选用链接存储结构。链表容易实现表容量的扩充，适合表应选用链接存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。的长度动态发生变化。应选用链接存储结构。因为一个城市的设计和规划涉及活动应选用链接存储结构。因为一个城市的设计和规划涉及活动很多，需要经常修改、扩充和删除各种信息，才能适应不断很多，需要经常修改、扩充和删除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。发展的需要。而顺序表的插入、删除的效率低，故不合适。分析以下各程序段，并用大分析以下各程序段，并用大O O记号表示其执行时间。记号表示其执行时间。【解答解答】基本语句是基本语句是k=k+10*ik=k+10*i，共执行了，共执行了n-2n-2次，所以次，所以T(nT(n)=)=O(nO(n)。基本语句是基本语句是k=k+10*ik=k+10*i，共执行了，共执行了n n次，所以次，所以T(nT(n)=)=O(nO(n)。分析条件语句，每循环一次，分析条件语句，每循环一次，i+ji+j 整体加整体加1 1，共循环，共循环n n次，所次，所以以T(nT(n)=)=O(nO(n)。设循环体共执行设循环体共执行T(nT(n)次，每循环一次，循环变量次，每循环一次，循环变量y y加加1 1，最终，最终T(nT(n)=y)=y，即：，即：(T(n)+1)2n(T(n)+1)2n，所以，所以T(n)=O(n1/2)T(n)=O(n1/2)。x+x+是基本语句，所以是基本语句，所以设有一个栈，元素进栈的次序为设有一个栈，元素进栈的次序为A A，B B，C C，D D，E E，能否得到如下，能否得到如下出栈序列，若能，请写出操作序列，若不能，请说明原因。出栈序列，若能，请写出操作序列，若不能，请说明原因。C C，E E，A A，B B，D D C C，B B，A A，D D，E E【解答解答】不能，因为在不能，因为在C C、E E出栈的情况下，出栈的情况下，A A一定在栈中，而且在一定在栈中，而且在B B的的下面，不可能先于下面，不可能先于B B出栈。出栈。可以，设为进栈操作，为入栈操作，则其操作序列为可以，设为进栈操作，为入栈操作，则其操作序列为IIIOOOIOIOIIIOOOIOIO。在操作序列在操作序列push(1)push(1)、push(2)push(2)、poppop、push(5)push(5)、push(7)push(7)、poppop、push(6)push(6)之后，栈顶元素和栈底元素分别是什之后，栈顶元素和栈底元素分别是什么？（么？（push(kpush(k)表示整数表示整数k k入栈，入栈，poppop表示栈顶元素出栈。）表示栈顶元素出栈。）【解答解答】栈顶元素为栈顶元素为6 6，栈底元素为，栈底元素为1 1。其执行过程如图所示。其执行过程如图所示。空串和空格串有何区别？串中的空格符有何意义？空串在串处空串和空格串有何区别？串中的空格符有何意义？空串在串处理中有何作用？理中有何作用？【解答解答】不含任何字符的串称为空串，其长度为零。仅含空格的串称为不含任何字符的串称为空串，其长度为零。仅含空格的串称为空格串，它的长度为串中空格符的个数。串中的空格符可用空格串，它的长度为串中空格符的个数。串中的空格符可用来分隔一般的字符，便于人们识别和阅读，但计算串长时应来分隔一般的字符，便于人们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。包括这些空格符。空串在串处理中可作为任意串的子串。算法设计算法设计（要求：算法用伪代码和算法设计（要求：算法用伪代码和C+C+描述，并分析最坏情况下描述，并分析最坏情况下的时间复杂度）的时间复杂度）找出整型数组找出整型数组AnAn 中元素的最大值和次最大值。中元素的最大值和次最大值。【解答解答】算法的伪代码描述如下：算法的伪代码描述如下：算法的算法的C C描述如下：描述如下：分析算法，只有一层循环，共执行分析算法，只有一层循环，共执行n-2n-2次，所以，次，所以，T(nT(n)=)=O(nO(n)。已知数组已知数组AnAn 中的元素为整型，设计算法将其调整为左右两部中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为法的时间复杂度为(n)(n)。【解答解答】从数组的两端向中间比较，设置两个变量从数组的两端向中间比较，设置两个变量i i和和j j，初始时，初始时i=0i=0，j=n-1j=n-1，若，若AiAi 为偶数并且为偶数并且AjAj 为奇数，则将为奇数，则将AiAi 与与AjAj 交交换。具体算法如下：换。具体算法如下：假设以不带头结点的循环链表表示队列，并且只设一个指针指假设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针。试设计相应的入队和出队的算向队尾结点，但不设头指针。试设计相应的入队和出队的算法。法。【解答解答】出队操作是在循环链表的头部进行，相当于删除开始结点，而出队操作是在循环链表的头部进行，相当于删除开始结点，而入队操作是在循环链表的尾部进行，相当于在终端结点之后入队操作是在循环链表的尾部进行，相当于在终端结点之后插入一个结点。由于循环链表不带头结点，需要处理空表的插入一个结点。由于循环链表不带头结点，需要处理空表的特殊情况。特殊情况。设顺序栈设顺序栈S S中有中有2n2n个元素，从栈顶到栈底的元素依次为个元素，从栈顶到栈底的元素依次为a2na2n，a2n-1a2n-1，a1a1，要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素，要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为依次为a2na2n，a2n-2a2n-2，a2a2，a2n-1a2n-1，a2n-3a2n-3，a1a1，请设计算法实现，请设计算法实现该操作，要求空间复杂度和时间复杂度均为该操作，要求空间复杂度和时间复杂度均为O(nO(n)。【解答解答】操作步骤为：操作步骤为：将所有元素出栈并入队；将所有元素出栈并入队；依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，则入栈；则入栈；将奇数结点出栈并入队；将奇数结点出栈并入队；将偶数结点出队并入栈；将偶数结点出队并入栈；将所有元素出栈并入队；将所有元素出栈并入队；将所有元素出队并入栈即为所求。将所有元素出队并入栈即为所求。对串的模式匹配对串的模式匹配KMPKMP算法设计求模式滑动位置的算法设计求模式滑动位置的nextnext函数。函数。作业从栈顶指针为从栈顶指针为toptop的链栈中删除一个结点，用的链栈中删除一个结点，用x x保存被删除结点保存被删除结点的值，则执行（的值，则执行（）。）。A x=top;top=A x=top;top=toptop-next;B x=top-data;-next;B x=top-data;C top=C top=toptop-next;x=top-data;D x=top-data;top=-next;x=top-data;D x=top-data;top=toptop-next;next;8 8线性表存放在整型数组线性表存放在整型数组AarrsizeAarrsize 的前的前elenumelenum 个单元中，个单元中，且递增有序。编写算法，将元素且递增有序。编写算法，将元素x x插入到线性表的适当位置插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。上，以保持线性表的有序性，并且分析算法的时间复杂度。设单循环链表设单循环链表L1L1，对其遍历的结果是：，对其遍历的结果是：x1,x2,x3,xn-1,x1,x2,x3,xn-1,xnxn。请将该循环链表拆成两个单循环链表。请将该循环链表拆成两个单循环链表L1L1和和L2L2，使得，使得L1L1中含有原中含有原L1L1表中序号为奇数的结点且遍历结果为：表中序号为奇数的结点且遍历结果为：x1,x3,x1,x3,；L2L2中含有原中含有原L1L1表中序号为偶数的结点表中序号为偶数的结点且遍历结果为：且遍历结果为：,x4,x2,x4,x2。设计算法把一个十进制整数转换为二至九进制之间的任一进制设计算法把一个十进制整数转换为二至九进制之间的任一进制数输出。数输出。假设一个算术表达式中可以包含三种括号：圆括号假设一个算术表达式中可以包含三种括号：圆括号“（”和和“）”，方括号，方括号“”和和“”以及花括号以及花括号“”和和“”，且，且这三种括号可按任意的次序嵌套使用。编写算法判断给定表这三种括号可按任意的次序嵌套使用。编写算法判断给定表达式中所含括号是否配对出现。达式中所含括号是否配对出现。谢谢
展开阅读全文