下载文档原格式
一. 名词解释（1）栈——只允许在一端进行插入或删除操作的线性表称为栈。
其最大的特点是“后进先出”。
（2）顺序栈——采用顺序存储结构的栈称为顺序栈。
（3）链栈——采用链式存储结构的栈称为链栈。
（5）队列——只允许在一端进行插入，另一端进行删除操作的线性表称为队列。
其最大的特点是“先进先出”。
（6）顺序队列——采用顺序存储结构的队列称为顺序队列。
（7）链队列——采用链式存储结构的称队列为链队列。
（8）循环队列——为了解决顺序队列中“假溢出”现象，将队列的存储空间想象为一个首尾相链的环（即把队头元素与对尾元素链结起来），存储在其中的队列称为循环队列。
二．判断题（下列各题，正确的请在前面的括号内打√；错误的打ㄨ）（1）√（2）√（3）ㄨ（4）ㄨ（5）ㄨ（6）ㄨ（7）√（8）√（9）ㄨ（10）√（11）ㄨ（12）ㄨ三. 填空题（1）后进先出（2）栈顶栈底（3）栈空栈满（4）O（1）O（1）（5）必须一致（6）栈（7）栈空（8）p->next=top top=p（9）- - + +（10）LS->next 首（11）先进先出（12）队尾队头（13）队列是否为空队列是否为满（14）可变的（15）-1 NULL（16）O(n) O(1) O(1) O(1)（17）front==rear front==(rear+1)% MAXLEN MAXLEN-front （18）空只含有一个结点（19）front==rear && front <>NULL（20）队尾指针写入四. 选择题（1）C （2）A （3）D （4）B （5）C（6）D （7）B （8）A （9）A （10）D（11）A （12）A （13）C （14）A （15）B (16) A五、简答题答：n个（同类）数据元素的有限序列称为线性表。
线性表的特点是数据元素之间存在“一对一”的关系。
栈和队列都是操作受限制的线性表，它们和线性表一样，数据元素之间都存在“一对一”的关系。
11． 写算法，实现顺序串的基本操作 StrReplace(&s,t,v)r1 中第 index 个字符起求出首次与串 r2 相同的子串的起始位置。
写一个函数将顺序串 s1 中的第 i 个字符到第 j 个字符之间的字符用 s2 串替换。
写算法，实现顺序串的基本操作 StrCompare(s,t) 。
第四章习题1. 设 s=' I AM A STUDENT , t= ' GOO D,q=' WORKER 给出下列操作的结果: StrLength(s); SubString(sub1,s,1,7);SubString(sub2,s,7,1);StrIndex(s, ' A ' ,4); StrReplace(s, ' STUDEN 'T,q); StrCat(StrCat(sub1,t), StrCat(sub2,q));2. 编写算法，实现串的基本操作 StrReplace(S,T,V) 。
3. 假设以块链结构表示串，块的大小为 1，且附设头结点。
试编写算法，实现串的下列基本操作：StrAsign(S,chars) ； StrCopy(S,T) ； StrCompare(S,T) ； StrLength(S) ； StrCat(S,T) ； SubString(Sub,S,pos,len) 。
4． 叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变 量的值。
5． 已知：S=”(xyz)* ” ,T= ”(x+z)*y ”。
试利用联接、求子串和置换等操作，将 S 转换为T. 6． S 和T 是用结点大小为1的单链表存储的两个串，设计一个算法将串 S 中首次与T 匹配的子串逆 置。
7． S 是用结点大小为4的单链表存储的串，分别编写算法在第k 个字符后插入串T ,及从第k 个字符 删除 len 个字符。
第4章（数组和广义表）作业参考答案一、单项选择题1.将一个A[1..100，1..100]的三对角矩阵，按行优先压缩存储到一维数组B[1‥298]中，A 中元素A[66][65]在B数组中的位置K为（C ）。
A. 198B. 197C. 195D. 1962.广义表（a,(b,c),d,e）的表头为（ A ）。
A. aB. a,(b,c)C. (a,(b,c))D. (a)3.在三对角矩阵中，非零元素的行标i和列标j的关系是（ A ）。
A. |i-j|≤1B. i>jC. i==jD. i<j4.广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（ D ）。
A. cB. b，cC.（b，c）D.（（b，c））5.设二维数组A[1..m,1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（ D ）。
A. j*m+i-1B. (i-1)*n+j-1C. i*(j-1)D. (i-1)*n+j6.广义表(( ),( ),( ))的深度为（ C ）。
A. 0B. 1C. 2D. 37.假设以行序为主序存储二维数组A[0..99,0..99]，设每个数据元素占2个存储单元，基地址为10，则LOC（A[4][4]）=（ C ）。
A. 1020B. 1010C. 818D. 8088.已知广义表A=((a,b),(c,d))，则head(A)等于（ A ）。
A. (a,b)B. ((a,b))C. a,bD. a9.已知一个稀疏矩阵的三元组表如下：(1，2，3)，(1，6，1)，(3，1，5)，(3，2，-1)，(4，5，4)，(5，1，-3)则其转置矩阵的三元组表中第3个三元组为（ C ）。
A. (2，3，-1)B. (3，1，5)C. (2，1，3)D. (3，2，-1)10.广义表（(b,c),d,e）的表尾为（ C ）。
第四章习题1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’。
给出下列操作的结果：StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1);StrIndex(s,’A’,4); StrReplace(s,’STUDENT’,q);StrCat(StrCat(sub1,t), StrCat(sub2,q));2. 编写算法，实现串的基本操作StrReplace(S,T,V)。
3. 假设以块链结构表示串，块的大小为1，且附设头结点。
试编写算法，实现串的下列基本操作：StrAsign(S,chars)；StrCopy(S,T)；StrCompare(S,T)；StrLength(S)；StrCat(S,T)；SubString(Sub,S,pos,len)。
4．叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。
5．已知：S=”(xyz)*”,T=”(x+z)*y”。
试利用联接、求子串和置换等操作，将S转换为T. 6．S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置。
7．S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及从第k个字符删除len个字符。
以下算法用定长顺序串：8．编写下列算法：（1）将顺序串r中所有值为ch1的字符换成ch2的字符。
（2）将顺序串r中所有字符按照相反的次序仍存放在r中。
（3）从顺序串r中删除其值等于ch的所有字符。
（4）从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置。
（5）从顺序串r中删除所有与串r1相同的子串。
9．写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。
10．写算法，实现顺序串的基本操作StrCompare(s,t)。
《数据结构（C语言版第2版）》（严蔚敏著）第四章练习题答案第4章串、数组和广义表1．选择题（1）串是一种特殊的线性表，其特殊性体现在（）。
A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符若答案：B（2）串下面关于串的的叙述中，（）是不正确的？A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储答案：B解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串，零个字符的串成为空串，其长度为零。
（3）串“ababaaababaa”的next数组为（）。
A．012345678999 B．012121111212 C．011234223456 D．0123012322345答案：C（4）串“ababaabab”的nextval为（）。
A．010104101B．010102101 C．010100011 D．010101011答案：A（5）串的长度是指（）。
A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数答案：B解释：串中字符的数目称为串的长度。
（6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（）。
A．808 B．818 C．1010 D．1020答案：B解释：以行序为主，则LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。
（7）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（）。
A．BA+141 B．BA+180 C．BA+222 D．BA+225答案：B解释：以列序为主，则LOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。
《数据结构》第四章习题一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、KMP算法的特点是在模式匹配时指示主串的指针不会变小。
( √)2、串是一种数据对象和操作都特殊的线性表。
( √)3、只包含空白字符的串称为空串（空白串）。
( ×)4、稀疏矩阵压缩存储后，必会（不会）失去随机存取功能。
( ×)5、使用三元组表示稀疏矩阵的非零元素能节省存储空间。
( √)6、插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常使用。
（×）7、若采用三元组表存储稀疏矩阵，只要把每个元素的行下标和列下标互换（错的），就完成了对该矩阵的转置运算。
（×）二、单项选择题1．下面关于串的的叙述中，哪一个是不正确的？（ B ）A．串是字符的有限序列B．空串是由空格构成的串（空串是长度为零的串）C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．有串S1=’ABCDEFG’，S2 = ’PQRST’，假设函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回中s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（ D ）。
A．BCDEF B．BCDEFG C．BCPQRST D．CDEFGFG3、串的长度是指（ B ）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数三、填空题1、串是一种特殊的线性表，其特殊性表现在_数据元素为字符，操作集也不同__；串的两种最基本的存储方式是_顺序存储_、__ 链式存储_；两个串相等的充分必要条件是__两串的长度相等且两串中对应位置的字符也相等__。
2、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为_O(m+n)__。
数据结构答案第4章本页仅作为文档封面，使用时可以删除This document is for reference only-rar21year.March第 4 章广义线性表——多维数组和广义表2005-07-14第 4 章广义线性表——多维数组和广义表课后习题讲解1. 填空⑴数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。
【解答】存取，修改，顺序存储【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。
除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。
⑵二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（）。
【解答】1140【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。
⑶设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。
【解答】d+41【分析】元素A[8][5]的前面共存储了(1+2+…+8)+5=41个元素。
⑷稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。
【解答】三元组顺序表，十字链表⑸广义表((a), (((b),c)),(d))的长度是（），深度是（），表头是（），表尾是（）。
【解答】3，4，(a)，((((b),c)),(d))⑹已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（）。
【解答】Head(Head(Tail(LS)))2. 选择题⑴二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（）个字节，A的第8列和第5行共占（）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（）元素的起始地址一致。
第四章
一、简述下列每对术语的区别：
空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。
答：
●空串是指不包含任何字符的串，它的长度为零。
空白串是指包含一个或多个空格的串，空格也是字符。
●串常量是指在程序中只可引用但不可改变其值的串。
串变量是可以在运行中改变其值的。
●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。
●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。
动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。
●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。
●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。
二、假设有如下的串说明：
char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p;
(1)在执行如下的每个语句后p的值是什么?
p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6');
(2)在执行下列语句后，s3的值是什么?
strcpy(s3,s1); strcat(s3,","); strcat(s3,s2);
(3)调用函数strcmp(s1,s2)的返回值是什么?
(4)调用函数strcmp(&s1[5],"ton")的返回值是什么?
(5)调用函数stlen(strcat(s1,s2))的返回值是什么?
解：
(1) stchr(*s,c)函数的功能是查找字符c在串s中的位置，若找到，则返回该位置，否则返回NULL。
因此:
执行p=stchr(s1,'t');后p的值是指向第一个字符t的位置, 也就是p==&s1[1]。
执行p=strchr(s2,'9');后p的值是指向s2串中第一个9所在的位置,也就是p==&s2[9]。
` 执行p=strchr(s2,'6');之后，p的返回值是NULL。
(2)strcpy函数功能是串拷贝，strcat函数的功能是串联接。
所以:
在执行strcpy(s3,s1); 后，s3的值是"Stocktom,CA"
在执行strcat(s3,","); 后，s3的值变成"Stocktom,Ca,"
在执行完strcat(s3,s2);后，s3的值就成了"Stocktom,Ca,March 5,1999"
(3)函数strcmp(串1，串2)的功能是串比较，按串的大小进行比较，返回大于0，等于0或小于0的值以表示串1比串2 大，串1等于串2 ，串1小于串2。
因此在调用函数strcmp(s1,s2)后，返回值是大于0的数(字符比较是以ascii码值相比的)
(4)首先，我们要知道&s1[5]是一个地址，当放在函数strcmp中时，它就表示指向以它为首地址的一个字符串，所以在strcmp( &s1[5],"ton")中，前一个字符串值是"tom,CA",用它和"ton"比较，应该是后者更大，所以返回值是小于0的数。
(5)strlen是求串长的函数，我们先将s1,s2联接起来，值是"Stocktom,CAMarch 5,1999",数一数有几个字符?是不是23个(空格也是一个)? 所以返回值是23。
三、设有A=' '，B='mule'，C='old'，D='my'，计算下列运算的结果（注：“A＋B”是Concat的简写）。
（a）A+B （b）B+A （c）D+C+B （d）SubStr(B,3,2)
（e）SubStr(C,1,0) （f）StrLength(A) （g）StrLength(D) （h）StrIndex(B,D)
（i）StrIndex(C,"d") （j）StrInsert(D,2,C) （k）StrInsert (B,I,A)（l）StrDelete(B,2,2)
（m）StrDelete(B,2,0) （n）StrRep(C,2,2, "k")
【解答】
（a）A+B="#mule"; （b）B+A="mule#"
（c）D+C+B="myoldmule" （d）SubStr(B,3,2)= "le"
（e）SubStr(C,1,0)= " " （f）StrLength(A)=1
（g）StrLength(D)=2 （h）StrIndex(B,D)=0
（i）StrIndex(C, "d")=3 （j）StrInsert(D,2,C)= "myldy"
（k）StrInsert (B,I,A)="m#ule" （l）StrDelete(B,2,2)="me"
（m）StrDelete(B,2,0)="mule" （n）StrRep(C,2,2, "k")="ok" 四、假设有如下的串说明：
char sl[30]="Stocktom,CA",s2[30]= "March 5,1999",s3[30];
（1）调用函数strCmp(s1,s2)的返回值是什么？
（2）调用函数strCmp(&s1[5], "ton")的返回值是什么？
（3）调用函数Strlength(StrConcat(s1,s2))的返回值是什么？
【解答】
（1）正数，表示s1大于s2。
（2）负数，表示“tom，CA”小于“ton”。
（3）23，即为s1与s2连接后的长度。
