1、计算机专业基础综合数据结构（串）历年真题试卷汇编 2及答案解析(总分：40.00，做题时间：90 分钟)一、综合题(总题数：4，分数：8.00)1.如果两个串含有相等的字符，能否说它们相等?【西安电子科技大学 2000一、3(5 分)】（分数：2.00）_2.设 S1、S2 为串，请给出使 S1$2=S2S1 成立的所有可能的条件(为连接符)。【国防科技大学 1999一】【长沙铁道学院 1997三、5(3 分)】（分数：2.00）_3.已知：s=(xyz)+*，t=(x+z)*。试利用联结、求子串和置换等基本运算，将 s转化为 t。【北方交通大学 1996一、3(5 分)】【山东科技大学 20
2、02一、6(5 分)】（分数：2.00）_4.s是字符数组，s0中存放的是该字符串的有效长度，假设 s17中字符串的内容为“abcabaa“，说明下列程序的功能及执行结果。 #define len 8 int k nlen， char slen=“7abcabaa”； void unknown3(char T) int i， j； i=1； n1=0； j=0； while(i_二、设计题(总题数：16，分数：32.00)5.设 s、t 为两个字符串，分别放在两个一维数组中，m、n 分别为其长度，判断 t是否为 s的子串。如果是，输出子串所在位置(第一个字符)，否则输出 0。(注：用程序实现。
3、)【中科院研究生院 2003九(15 分)】【南京航空航天大学 1997九(10 分)】（分数：2.00）_6.输入一个字符串，内有数字和非数字字符，如：ak123x456 1 79607302gef4563，将其中连续的数字作为一个整体，依次存放到一数组口中，例如 123放入 a0，456 放入 a1，编程统计其共有多少个整数，并输出这些数。【上海大学 1998一(13 分)】（分数：2.00）_7.以顺序存储结构表示串，设计算法。求串 S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。【东南大学 2000五(15 分)】【西北大学 2002六(15 分)】（分数：2.00）_8.
4、假设串的存储结构如下(略)，编写算法实现串的置换操作。【清华大学 1995五(15 分)】（分数：2.00）_9.函数 void insert(char*s，char*t，int pos)将字符串 t插入字符串 s中，插入位置为 pos。请用 C语言实现该函数。假设分配给字符串 s的空间足够让字符串 t插入。(说明：不得使用任何库函数。)【北京航空航天大学 2001六(10 分)】（分数：2.00）_10.设计一个二分检索的算法，在一组字符串中找出给定的字符串，假设所有字符串的长度为 4。(1)简述算法的主要思想； (3 分)(2)用 Pascal语言分别对算法中用到的类型和变量作出说明； (
5、3 分)(3)用类Pascal语言或自然语言写算法的非递归过程； (8 分)(4)分析该算法的最大检索长度； (3 分)(5)必要处加上中文注释。 (3 分)【山东工业大学 1995八(20 分)】（分数：2.00）_11.设计一 Pascal或 C语言的函数 atoi(X)，其中 X为字符串，由 09 十个数字符和表示正负数的“组成，返回值为整型数值。 【浙江大学 1994二(7 分)】（分数：2.00）_12.设一个由字母组成的字符串，编写算法对它们的字母顺序进行调整，使输出时所有大写字母 都在小写字母之前，并且同类字母之间的相对位置不变。(5 分)例如，原有字符串为：AbcDEfghiJ
6、Klmn 输出序列为：ADEJKbcfhilinn【华南理工大学 2006三、1(5 分)】（分数：2.00）_13.编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为AZ 这 26个字母和 09 这 10个数字)。 【西北大学 2000四(10 分)】（分数：2.00）_14.写出一个递归算法来实现字符串逆序存储。【中科院研究生院 2004四(7 分)】（分数：2.00）_15.已知三个字符串分别为s=ababcaabcbcaa，s“=“caab“，s”=Ibcb。利用所学字符串基本运算的函数得到结果串为：s“=“caabcbca，acaa，要求写出得到
7、以上结果串 s “ 所用的函数及执行算法。【东北大学 1998一、1(10 分)】（分数：2.00）_16.S=“S 1 S 2 S n ”是一个长为 N的字符串，存放在一个数组中，编程序将 S改造之后输出： (1)将 S的所有第偶数个字符按照其原来的下标从大到小的次序放在 S的后半部分； (2)将 S的所有第奇数个字符按照其原来的下标从小到大的次序放在 S的前半部分；例如：S=“ABCDEFGHI 舭则改造后的 S为“ACEGIKLJHFDB“。【中科院计算所 1995】（分数：2.00）_17.若 x和 y是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。【中国航天科研机构20
8、05六(7 分)】（分数：2.00）_18.试设计一个 C算法(或 C程序)：用单链表作存储结构，以回车符为结束标志，输入一个任意长度的字符串；然后判断该字符串是否为“回文”(正向读和反向读时，串值相同的字符串称为“回文”)，输出信息“Yes”或“No”；最后删除字符串并释放全部空间。例如：若输入“ABCDl2321DCBA”，是回文，则输出“YeS”；若输入“ABCDl23DCBA”，不是回文，则输出“No”。要求：定义相关数据类型，不得使用数组(顺序表)作字符串的存诸结构和辅助存储空间。假定字符串的长度为 n，试分析上述算法的时间复杂度。【华中科技大学 2004五(10 分)】（分数：2.
9、00）_19.试写一个算法，识别依法读入的一个以为结束符的字符序列是否为形如序列 1 else return(0)；)解析：18.试设计一个 C算法(或 C程序)：用单链表作存储结构，以回车符为结束标志，输入一个任意长度的字符串；然后判断该字符串是否为“回文”(正向读和反向读时，串值相同的字符串称为“回文”)，输出信息“Yes”或“No”；最后删除字符串并释放全部空间。例如：若输入“ABCDl2321DCBA”，是回文，则输出“YeS”；若输入“ABCDl23DCBA”，不是回文，则输出“No”。要求：定义相关数据类型，不得使用数组(顺序表)作字符串的存诸结构和辅助存储空间。假定字符串的长度为
10、 n，试分析上述算法的时间复杂度。【华中科技大学 2004五(10 分)】（分数：2.00）_正确答案：(正确答案：利用栈存放字符串的前半部分，将后半部分与栈中弹出元素比较。核心语句段如下： char S； 字符栈，容量足够大 p=head 一next 设链表带头结点 int i=0； while(ic=n2) 前一半字符入栈，链表指针后移 (Si=p 一data；p=p 一next； i+；) if(n2=1)p=p 一next； 若链表有奇数个结点，则跳过中间结点 while(p) if(p 一data=si)(p=p一next；i 一一；) else break； 不是回文 if(!P 串长为偶数或奇数 if(Sfront!=Srear) return 0; return huiwenchuan(S，front+1，rear-1); )解析：
