数据结构——串

数据结构复习题：串

填空题

1、串的两种最基本的方式是_________。

2、两个串相等的充分必要条件是________。

3、空串是________,其长度等于_________。

4、空白串是________,其长度等于_________。

5、设s='I_AM_A_TEACHER',(其中,_表示一个空格字符),其长度是_______。

6、设s1='GOOD',s2=' ',s3='BYE!',则s1,s2和s3连接后的结果是________。

7、队列是一种具有______特性的线性表。

8、顺序队和链队的区别仅在于______的不同。

9、如果队列的最大长度以难以估计,则最好使用______。

10、在队列中,新插入的元素只能插入到______。

11、环形队列的优点是______。

12、设有数组A[0..m]作为环形队列的存储空间,front为队头指针,rear为队尾指针,则元素x执行入队的操作是______。

13、设有数组A[0..m]作为环形队列的存储空间,front为队头指针,rear为队尾指针,假设队列车不空,则元素出队并保存到x中的操作是______。

14、若用带头结点的单链表来表示链队,则队列空的标志是______。

15、若用不带头结点的单链表来表示链队,则创建一个空队列所要执行的操作是______。

16、若用带头结点的单链表来表示链队,则创建一个空队列所要执行的操作是______。

17、己知链队的头、尾指针分别是f和r,则将值x入队的操作序列是_____。

18、在顺序队列实现的时候,通常将数组看成是一个首尾相连的环,这样做的目的是为避免产生______现象.

19、环形队列用数组A[0..m-1]存放其元素值,己知其头尾指针分别是front和rear,则当前队列中的元素个数是______.

20、队列的插入操作在____________进行，删除操作在____________进行。

实验三

一、实验目的及要求

理解、掌握串的有关概念，串的存储形式及常见基本的实现。

二、实验环境

硬件：计算机 软件：Microsoft Visual C++

三、实验内容

用定长顺序存储表示串，实现求子串的操作。

四、调试过程及实验结果

在输入字符串时出现错误，由于scanf("%c",&S[i]);中&S[i]错误写成S[i]。

五、总结

通过本次实验，加深了我对串的理解，了解了串的一些基本操作，看似很简单的操作，很少写程序的人，在编译过程中还是会遇到许多错误，所以只有不断写程序，编译才能发现问题，提高自己的编程能力。

六、附录（源程序清单）

#include

#define T 22

#define MAXSTRLEN 255

typedef unsigned char SString[MAXSTRLEN+1];

int InitString(SString &S);

int SubString(SString &Sub,SString S,int pos,int len);

int main()

{

SString S,Sub;

int pos,len;

S[0]=T;

InitString(S);

SubString(Sub,S,pos,len); 课程名称：数据结构 班级：嵌入式1班 完成日期：2011、10、27

姓名郝祥海 学号：1010431079 指导教师：

实验名称：串的基本操作 实验序号： 实验成绩： return 0;

}

int InitString(SString &S)

{

printf("请输入字符串:");

for(int i=1;i<=S[0];i++)

scanf("%c",&S[i]);

return 0;

}

int SubString(SString &Sub,SString S,int pos,int len)

第四章 串

一、选择题

1 ．下面关于串的的叙述中，哪一个是不正确的？（ ）【北方交通大学 2001 一、 5 （ 2 分）】

A ．串是字符的有限序列 B ．空串是由空格构成的串

C ．模式匹配是串的一种重要运算 D ．串既可以采用顺序存储，也可以采用链式存储

2 若串 S 1 = ‘ ABCDEFG ' , S2= ‘ 9898 ' ,S3= ‘ ### ' ,S4= ‘ 012345 ' , 执行

concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2, ‘ 8 ' ),length(S2)))

其结果为（ ）【北方交通大学 1999 一、 5 （ 25/7 分）】

A ． ABC###G0123 B ． ABCD###2345 C ． ABC###G2345 D ． ABC###2345

E ． ABC###G1234 F ． ABCD###1234 G ． ABC###01234

3 ．设有两个串 p 和 q ，其中 q 是 p 的子串，求 q 在 p 中首次出现的位置的算法称为（ ）

A ．求子串 B ．联接 C ．匹配 D ．求串长

4 ．已知串 S= ‘ aaab ' , 其 Next 数组值为（ ）。【西安电子科技大学 1996 一、 7 （ 2

分）】

A ． 0123 B ． 1123 C ． 1231 D ． 1211

5 ．串 ‘ ababaaababaa ' 的 next 数组为（ ）。【中山大学 1999 一、 7 】

A ． 012345678999 B ． 012121111212 C ． 011234223456 D ． 0123012322345

6 ．字符串‘ ababaabab ' 的 nextval 为（ ）

A ． (0,1,0,1,04,1,0,1) B ． (0,1,0,1,0,2,1,0,1)

中北大学

数 据 结 构

课 程 设 计 说 明 书

学生姓名: 杨彦军 学 号： **********

学 院: 软件学院

专 业: 信息管理与信息系统

题 目: 串的查找与替换

成 绩:

指导教师 李玉蓉、李华玲

2011年01月06日 杨彦军-0921030336

1 1 设计目的

《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的：

 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

2. 设计内容和要求

设计内容：

打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘。

设计要求：

(1) 符合课题要求，实现相应功能；

(2) 操作方便易行；

(3) 注意程序的实用性、安全性；

3．本设计所采用的数据结构

3.1数组

数组在编程应用时调用很方便随意，但在更改数组时比较麻烦必须调用数组中的所有元素。

char keyWords[SIZE];

char copyWords[SIZE];

char strOne[MAXLEN];

char strTwo[MAXLEN];

3.2串的匹配

if (keyWords[0] == strOne[i])

if (keyWords[j] != strOne[countFlag++])

4．功能模块详细设计

4.1 详细设计思想 杨彦军-0921030336

2 a）需求分析