PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。
16. 当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为_______，栈2空时 ，top[2]为_______，栈满时为_______。 17．两个栈共享空间时栈满的条件_______。
18．在作进栈运算时应先判别栈是否 ;在作退栈运算时应先判别栈是否 ；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为 。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的 分别设在内存空间的两端，这样只有当 时才产生溢出。
19. 多个栈共存时，最好用_______作为存储结构。
20．表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是_______。
21. 循环队列的引入，目的是为了克服_______。 22. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。 23．区分循环队列的满与空，只有两种方法，它们是______和______。
24. 设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为_______，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_______。 25．表达式求值是_______应用的一个典型例子。
三、判断题
1.栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。 2.通常递归的算法简单、易懂、容易编写，但执行的效率不高。 3.在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。 4.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 5.用非递归方法实现递归算法时一定要使用递归工作栈。 6．队列只允许在表的一端进行插入，而在另一端删除元素。
四、应用题
1．设有一个顺序栈S，元素s1， s2， s3， s4， s5， s6依次进栈，如果6个元素的出栈顺序为s2， s3， s4， s6， s5， s1，则顺序栈的容量至少应为多少？ 2. 试推导出当总盘数为n的Hanoi塔的移动次数。
3. 用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。
16
4. 举例说明顺序队的“假溢出”现象，并给出解决方案。
五、算法设计题
1. 设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。 2. 设从键盘输入一整数的序列：a1, a2, a3，?，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。 3. 设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。) 4. 如果允许在循环队列的两端都可以进行插入和删除操作。要求： （1）写出循环队列的类型定义；
（2）写出“从队尾删除”和“从队头插入”的算法。
5．线性表中元素存放在向量A（1,?,n）中，元素是整型数。试写出递归算法求出A中的最大和最小元素。 6. 已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若n等于零，则返回m；第二步：若m小于n，则m与n相互交换；否则，保存m，然后将n送m，将保存的m除以n的余数送n。
（1）将上述过程用递归函数表达出来（设求x除以y的余数可以用x MOD y 形式表示）。 （2）写出求解该递归函数的非递归算法。
7．设计算法以求解从集合{1..n}中选取k（k<=n）个元素的所有组合。例如，从集合{1..4}中选取2个元素的所有组合的输出结果为：1 2，1 3，1 4，2 3， 2 4，3 4。 8．假设两个队列共享一个循环向量空间， 其类型Queue2定义如下： typedef struct{
DateType data[MaxSize]； int front,rear； }Queue2；
对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。
int EnQueue (Queue2*Q,int i,DateType x)
{//若第 i个队列不满，则元素x入队列，并返回1；否则返回0 if(i<0||i>1)return 0；
17
if(Q－>rear[i]==Q－>front[ ① ]return0； Q－>data[ ② ]=x； Q－>rear[i]=[ ③ ]; return 1； )
六、简答题
1.（1）什么是递归程序？
（2）递归程序的优、缺点是什么？
（3）递归程序在执行时，应借助于什么来完成？
（4）递归程序的入口语句、出口语句一般用什么语句实现？
2. 当过程P递归调用自身时，过程P内部定义的局部变量在P的2次调用期间是否占用同一数据区？为什么？ 3. 在一个算法中需要建立多个堆栈时可以选用下列三种方案之一，试问：这三种方案之间相比较各有什么优缺点？
（1）分别用多个顺序存储空间建立多个独立的堆栈； （2）多个堆栈共享一个顺序存储空间； （3）分别建立多个独立的链接堆栈。
18
第四章 串
一、单项选择题
1．串是一种特殊的线性表，其特殊性体现在（ ）
A．可以顺序存储 B．数据元素是一个字符C．可以链接存储 D．数据元素可以是多个字符 2．如下陈述中正确的是（ ）
A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串
3．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（ ）
A．O（ ） B．O（n） C．O（n） D．O（n） 4.设有两个串 p和q,求q在p中首次出现的位置的运算称作 。 A.连接 B.模式匹配 C.求串长 D.求子串 5.设字符串 S1=―ABCDEFG‖，S2=―PQRST‖，则运算：
S=CONCAT（SUBSTR（S1，2，LEN（S2））, SUBSTR（S1，LEN（S2），2））；后的串值为 。 A.BCDEF B.BCDEFG C.BCDPQRST D.BCDEFEF
2
3
二、填空题
1. 空格串是指 ，其长度等于 。 2．在串S=“structure”中，以t为首字符的子串有_____个。
三、判断题
1.空格串和空串的长度均为 1。
2.串是一种特殊的线性表，其特殊性体现在数据元素可以使多个字符。 3.判断两个串是否相等，只需要判断这两个串是否包含相同的字符即可。
四、应用题
1．设S1 =―Data Structure Course‖，S2 =―Structure‖，S3 =―Base‖，求： （1）Length(S1)； （2）Compare(S2, S3)； （3）Insert(S1, 5, S3)； （4）Delete(S1, 5, 9)；
（5）SubString(S1, 5, 9, T)； （6）Search(S1, 0, S2)； （7）Replace(S1, 0, S2, S3) 2.令t1=―aaab‖, t2=―abcabaa‖, t3=―abcaabbabcabaacba‖，试分别求出他们的next[j]值。
19
五、算法设计题
1.设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有等于和不等于两种情况。
2.设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有大于、等于和小于三种情况。
3.设串采用静态数组存储结构，编写函数实现串的替换Replace(S, start, T, V)，即要求在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0。
4.设字符串采用单字符的链式存储结构，编写删除串s从位置i开始长度为k的子串的算法。 5．下列算法的功能是比较两个链串的大小，其返回值为：
comstr(s1,s2)=-1（s1
int comstr(LinkString s1,LinkString s2) {//s1和s2为两个链串的头指针 while(s1&&s2){
if(s1－>date
if( ③ )return －1； if( ④ )return 1； ⑤ ； }
六、简答题
1.什么叫串？串和字符在存储方法上有什么不同？空串和空格串是否相同，为什么？ 3.串是由字符组成的，长度为1的串和字符是否相同。为什么？
4.串是不定长的，表示串的长度有几种方法？C语言中的串采用哪种方法？
5.可以说串是数据类型固定为字符类型的线性表，但是串操作和线性表操作的主要不同之处在哪里？ 6.可以用几种存储方法存储串？
7.分别写出串的静态数组存储结构和串的动态数组存储结构的结构体定义。
20
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题(4)在线全文阅读。
相关推荐：