数据结构精选试题之算法设计
算法设计
1．设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。如果是，输出子串所在位置（第一个字符），否则输出0。（注：用程序实现）【南京航空航天大学 1997 九（10分）】
2．输入一个字符串，内有数字和非数字字符，如：ak123x456 17960?302gef4563，将其中连续的数字作为一个整体，依次存放到一数组a中，例如123放入a[0]，456放入a[1]，… … 。编程统计其共有多少个整数，并输出这些数。【上海大学 1998 一 （13分）】
3． 以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。【东南大学 2000 五 （15分）】
类似本题的另外叙述有：
（1）如果字符串的一个子串（其长度大于1）的各个字符均相同，则称之为等值子串。试设计一算法，输入字符串S，以“！”作为结束标志。如果串S中不存在等值子串，则输出信息“无等值子串”，否则求出（输出）一个长度最大的等值子串。
例如：若S＝“abc123abc123！”，则输出“无等值子串”；若S＝“abceebccadddddaaadd！”，则输出“ddddd”。
【华中科技大学 2001】
4．假设串的存储结构如下所示，编写算法实现串的置换操作。【清华大学 1995 五（15分）】
TYPE strtp ＝RECORD
ch： ARRAY[1．．maxlen] OF char；
curlen：0．．maxlen
END；
5．函数void insert（char*s，char*t，int pos）将字符串t插入到字符串s中，插入位置为pos。请用c语言实现该函数。假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数）
【北京航空航天大学 2001 六 （10分）】
6．设计一个二分检索的算法，在一组字符串中找出给定的字符串，假设所有字符串的长度为4。
（1）简述算法的主要思想；（3分）
（2）用PASCAL语言分别对算法中用到的类型和变量作出说明；（3分）
（3）用类PASCAL语言或自然语言写算法的非递归过程； （8分）
（4）分析该算法的最大检索长度；（3分）
（5）必要处加上中文注释。（3分）
【山东工业大学 1995 八 （20分）】
7．设计一PASCAL 或C语言的函数 atoi（x）．其中X 为字符串，由0－－9十个数字符和表示正负数的‘－’组成，返回值为整型数值 。【浙江大学 1994 二 （7分）】
8．已知字符串S1中存放一段英文，写出算法format（s1，s2，s3，n），将其按给定的长度n格式化成两端对齐的字符串S2， 其多余的字符送S3。 【首都经贸大学 1998 三、8（15分）】
9．串以静态存储结构存储，结构如下所述，试实现串操作equal算法．
CONST maxlen＝串被确认的最大长度
TYPE strtp＝RECORD
ch：ARRAY[1．．maxlen] OF char；
curlen：0．．maxlen
END；
（以一维数组存放串值，并设指示器curlen指示当前串长）【北京轻工业大学 1998 一 （12分）】
10．编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A－Z这26个字母和0－9这10个数字）。【西北大学 2000 四 （10分）】
11．写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。 【西南交通大学 2000 三、2】
12．已知三个字符串分别为s＝’ab…abcaabcbca…a’，s’＝’caab’， s’’＝’bcb’。利用所学字符串基本运算的函数得到结果串为：s’’’＝’caabcbca…aca…a’，要求写出得到上结果串S’’’所用的函数及执行算法。【东北大学 1998 一、1 （10分）】
13．S＝“S1S2…Sn”是一个长为N的字符串，存放在一个数组中，编程序将S改造之后输出：
（1）将S的所有第偶数个字符按照其原来的下标从大到小的次序放在S的后半部分；
（2）将S的所有第奇数个字符按照其原来的下标从小到大的次序放在S的前半部分；
例如：
S＝‘ABCDEFGHIJKL’
则改造后的S为‘ACEGIKLJHFDB’。【中科院计算所 1995】
14．编一程序，对输入的一表达式（字符串），输出其TOKEN表示。表达式由变量A，B，C，常数（数字）0，1，…，9，运算符＋，*和括号“（”，“）”组成。首先定义符号的类码：
符号变量常量*＋（）
类码012345
其次定义符号的TOKEN表示：
其中NAMEL是变量名表（不允许有相同名），CONST是常量表（不允许有相同数）。
例如，假设有表达式（A＋A*2）＋2*B*3#，则将生成如下TOKENL：
最新评论（共0条）评论一句
Copyright©2007–2021 www.100xuexi.com All rights reserved 圣才学习网 版权所有
全国热线：400-900-8858（09:00-22:00），18001260133（09:00-22:00）
增值电信业务经营许可证 出版物经营许可证 网络文化经营许可证 广播电视节目制作经营许可证
