发布时间 : 星期四 文章数据结构习题更新完毕开始阅读
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