第四章 串
第四章串
一、选择题
1．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。
A. “STRUCTURE”
B.“DATA”
C. “ASTRUCTUR”
D. “DATASTRUCTURE”
2．字符串的长度是指（）。
A. 串中不同字符的个数
B. 串中不同字母的个数
C. 串中所含字符的个数
D. 串中不同数字的个数
3．两个字符串相等的充要条件是（）。
A. 两个字符串的长度相等
B. 两个字符串中对应位置上的字符相等
C. 同时具备(A)和(B)两个条件
D. 以上答案都不对
4．关于串的叙述中，正确的是（）
A．空串是只含有零个字符的串
B.空串是只含有空格字符的串
C.空串是含有零个字符或含有空格字符的串
D.串是含有一个或多个字符的有穷序列
5．下面关于串的的叙述中，哪一个是不正确的？（）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储
6．设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作( ) A．求子串 B.判断是否相等 C．模型匹配 D.连接
7．若串S=’software’,其子串的数目是( )。
A．8 B．37 C．36 D．9
8．串的长度是指（）
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
9．串是一种特殊的线性表，其特殊性体现在( )。
A．数据元素是一个字符 B. 可以顺序存储
C. 数据元素可以是多个字符
D. 可以链接存储
10．下面关于串的的叙述中，哪一个是不正确的（B）
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
11．若串＝‘software’，其非平凡子串（非空且不同于串本身）的数目是（C）A. 8 B. 37 C. 35 D. 9
12．串是一种特殊的线性表，其特殊性体现在（B）
A. 可以顺序存储
B. 数组元素是一个字符
C. 可以连续存储
D. 数据元素可以是多个字符
13. 下面关于串的的叙述中，哪一个是不正确的？（B）
A．串是字符的有限序列
B．空串是由空格构成的串
C．模式匹配是串的一种重要运算
D．串既可以采用顺序存储，也可以采用链式存储
二、填空题
1．两个串是相等的，当且仅当两个串的长度相等且___对应位置_____的字符都相同。
2．串是一种特殊的线性表，串常见的存储结构有顺序存储和_____链式存储_两种方式。
3．空格串是指_______，其长度等于_______。 (1) 由空格字符（ASCII值32）所组成的字符串 (2)空格个数
4．一个字符串中________称为该串的子串。任意个连续的字符组成的子序列5．字符串’ababaaab’的nextval函数值为________。01010421
6．串是一种特殊的线性表，其特殊性表现在__(1)__；串的两种最基本的存储方式是__(2)__、__(3)__；两个串相等的充分必要条件是__(4)__。(1)其数据元素都是字符
(2)顺序存储
(3)和链式存储
(4)串的长度相等且两串中对应位置的字符也相等
7．下列程序读入无符号16进制数（出现的字母为小写），将其转换为十进制数输出。请将程序空缺部分补全。
int f(char *s)
｛int n=0, i;
for(i=0;s［i］!=’\0’; i++) n=n*16+ (1) ;
return n;
｝
main()
｛char s[10];
scanf(“%s”,s); printf(“%d\n”, (2) );
｝
(1)(s[i]>=97?s[i]-87:s[i]-48) ∥‘a’到’f’的ASCII码是97到102
(2)f(s)
8．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。
void maxcomstr(orderstring *s,*t, int index, length)
{int i,j,k,length1,con;
index=0;length=0;i=1;
while (i<=s.len)
{j=1;
while(j<=t.len)
{ if (s[i]==t[j])
{ k=1;length1=1;con=1;
while(con)
if (1) _ { length1=length1+1;k=k+1; } else (2) __;
if (length1>length) { index=i; length=length1; }
(3)____;
}
else (4) ___;
}
(5) __
} }
[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。串s用i 指针（1<=i<=s.len）。t串用j指针（1<=j<=t.len）。算法思想是对每个i （1<=i<=s.len，即程序中第一个while循环），来求从i开始的连续字符串与从j（1<=j<=t.len，即程序中第二个while循环）开始的连续字符串的最大匹配。程序中第三个（即最内层）的while循环，是当s中某字符(s[i])与t中某字符(t[j])相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的长度要修改。
(1)i+k<=s.len && j+k<=t.len && s[i+k]==t[j+k]
∥如果在s和t的长度内，对应字符相等，则指针k 后移（加1）（2）con=0 ∥s和t对应字符不等时置标记退出
（3）j=j+k ∥在t串中，从第j+k字符再与s[i]比较
（4）j=j+1 ∥t串取下一字符
(5) i=i+1 ∥s串指针i后移（加1）。
9．试利用下列栈和串的基本操作完成下述填空题。
initstack(s) 置s为空栈；
push(s,x) 元素x入栈;
pop(s) 出栈操作;
gettop(s) 返回栈顶元素；
sempty(s) 判栈空函数；
setnull(st) 置串st为空串；
length(st) 返回串st的长度；
equal(s1,s2) 判串s1和s2是否相等的函数；
concat(s1,s2) 返回联接s1和s2之后的串；
sub(s,i,1) 返回s中第i个字符；
empty(st) 判串空函数
FUNC invert(pre:string; VAR exp:string):boolean;
{若给定的表达式的前缀式pre正确，本过程求得和它相应的表达式exp并返回“true”，否则exp为空串，并返回“false”。已知原表达式中不包含括弧，opset为运算符的集合。}
VAR s:stack; i,n:integer; succ:boolean; ch: char;
BEGIN
i:=1; n:=length(pre); succ:=true;
(1)__; (2)__;
WHILE (i BEGIN ch:=sub（pre,i,l）; IF (3)_ THEN (4)__ ELSE IF (5)__THEN (6)_ ELSE BEGIN exp:=concat((7)___,(8)____); exp:=concat((9)___,(10)___); (11)__; END; i:=i+1 END; IF (12)___THEN BEGIN exp:=concat(exp,sub(pre,n,1)); invert:=true END ELSE BEGIN setnull(exp); invert:=false END END; 注意：每个空格只填一个语句。 （1）initstack（s）∥栈s初始化为空栈 (2) setnull (exp) ∥串exp初始化为空串 (3) ch in opset ∥判取出字符是否是操作符 (4) push (s,ch) ∥如ch是运算符，则入运算符栈s (5) sempty (s) ∥判栈s是否为空 (6) succ := false ∥若读出ch是操作数且栈为空，则按出错处理 (7) exp (8) ch ∥若ch是操作数且栈非空，则形成部分中缀表达式 (9) exp (10) gettop(s) ∥取栈顶操作符 (11) pop(s) ∥操作符取出后，退栈 (12) sempty(s) ∥将pre的最后一个字符（操作数）加入到中缀式exp 的最后 三、判断题 1．( )子串“ABC”在主串“AABCABCD”中的位置为2。T 2．（）KMP算法的特点是在模式匹配时指示主串的指针不会变小。√ 3．（）设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。√ 4．（）串是一种数据对象和操作都特殊的线性表。√ 5．（）串长度是指串中不同字符的个数。× 6．( ) 如果两个串含有相同的字符，则这两个串相等。X 7．（）KMP算法的最大特点是指示主串的指针不回溯。√ 四、简答题 1．KMP算法(字符串匹配算法)较Brute(朴素的字符串匹配)算法有哪些改进? 朴素的模式匹配（Brute－Force）时间复杂度是Ｏ(m＊n），KMP算法有一定改进，时间复杂度达到Ｏ(m＋n）。主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。 2．给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。 模式串的next函数定义如下： 根据此定义，可求解模式串’abacabaaad’的next和nextval值如下： 3．模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m，模式的长度为n，则在主串中寻找模式的KMP算法的时间复杂性是多少？如果，某一模式 P=’abcaacabaca’，请给出它的NEXT函数值及NEXT函数的修正值NEXTVAL之值。 KMP算法的时间复杂性是O（m+n）。 p的next和nextval值分别为01112212321和01102201320。 4．设目标为S=‘abcaabbcaaabababaabca’，模式为P=‘babab’。 （1）手工计算模式P的nextval数组的值； （2）写出利用求得的nextval数组，按KMP算法对目标S进行模式匹配的过程。（1）p的nextval函数值为01010。（next函数值为01123） （2）利用所得nextval数值，手工模拟对s的匹配过程。 5．s是字符数组，s[0]中存放的是该字符串的有效长度，假设s[1..7]中字符串的内容为“abcabaa”，说明下列程序的功能及执行结果。 #define len 8 int k, n[len]； char s[len]=“7abcabaa”； void unknown3(char T[]） {int i, j; i=1; n[1]=0; j=0; while (i {if (j==0 || T[i]==T[j]) {++i; ++j; if(T[i]!=T[j]) n[i]=j; else n[i]=n[j]; } else j=n[j]; } } main() {unknown3(s); for (k=1;k 本程序的功能是求字符串的nextval函数，程序执行结果是0110132。 6．给出KMP算法中失败函数f的定义，并说明利用f进行串模式匹配的规则，该算法的技术特点是什么？ 这里失败函数f，即是通常讲的模式串的next函数，其定义见本章应用题的第5题。 进行模式匹配时，若主串第i个字符与模式串第j个字符发生失配，主串指针i 不回溯，和主串第i个字符进行比较的是模式串的第next[j]个字符。模式串的next函数值，只依赖于模式串，和主串无关，可以预先求出。 该算法的技术特点是主串指针i不回溯。在经常发生“部分匹配”和主串很大不能一次调入内存时，优点特别突出。 7．已知：s='(xyz)+＊'，t='(x+z)*y'。试利用联结、求子串和置换等基本运算，将s转化为t 。【北方交通大学 1996 一.3（5分）】 题中所给操作的含义如下： ∥：连接函数，将两个串连接成一个串 substr（s,i,j）：取子串函数，从串s的第i个字符开始，取连续j个字符形成子串 replace（s1,i,j,s2）：置换函数，用s2串替换s1串中从第i个字符开始的连续j个字符 本题有多种解法，下面是其中的一种： （1） s1=substr(s,3,1）∥取出字符：‘y’ （2） s2=substr(s,6,1）∥取出字符：‘+’ （3） s3=substr(s,1,5）∥取出子串：‘(xyz)’ （4） s4=substr(s,7,1）∥取出字符：‘*’ （5） s5=replace(s3,3,1,s2）∥形成部分串：‘（x+z）’ （6） s=s5∥s4∥s1 ∥形成串t即‘（x+z）*y’ 8. 已知模式串pat=’ADABBADADA’,写出该模式串的next函数值和nextval 值；（4分） 五、应用题 评分标准：全题4分，错误酌情扣分 六、算法设计题 1．设计在顺序存储结构上实现求子串算法。 void substring(char s[ ], long start, long count, char t[ ]) { long i,j,length=strlen(s); if (start<1 || start>length) printf("The copy position is wrong"); else if (start+count-1>length) printf("Too characters to be copied"); else { for(i=start-1,j=0; i } 2．设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。如果是，输出子串所在位置（第一个字符），否则输出0。（注：用程序实现） 【中科院研究生院2003九(15分)】【南京航空航天大学 1997 九(10分)】[题目分析]判断字符串t是否是字符串s的子串，称为串的模式匹配，其基本思想是对串s和t各设一个指针i和j，i的值域是0..m-n，j的值域是0..n-1。 初始值i和j均为0。模式匹配从s 0和t 开始，若s =t ，则i和j指针增加1， 若在某个位置s i !=t j ，则主串指针i回溯到i=i-j+1，j仍从0开始，进行下一 轮的比较，直到匹配成功（j>n-1），返回子串在主串的位置（i-j）。否则，当i>m-n则为匹配失败。 int index(char s[],t[],int m,n) ∥字符串s和t用一维数组存储，其长度分别为m和n ∥本算法求字符串t在字符串s中的第一次出现,匹配成功输出t串在s中的位置,否则输出0 {int i=0,j=0; while(i<=m-n && j<=n-1) if(s[i]==t[j]){i++;j++;} ∥对应字符相等，指针后移 else {i=i-j+1;j=0;} ∥对应字符不相等，i回溯，j仍为0 if(i<=m-n && j==n) {printf(“t在s串中位置是%d”,i-n+1);return(i-n+1);}∥匹配成功 else return(0); ∥匹配失败 }∥算法index结束 main ()∥主函数 {char s[],t[]; int m,n,i; scanf(“%d%d”,&m,&n); ∥输入两字符串的长度 scanf(“%s”,s); ∥输入主串 scanf(“%s”,t); ∥输入子串 i=index(s,t,m,n); }∥程序结束 [程序讨论]因用C语言实现，一维数组的下标从0开始，m-1是主串最后一个字符的下标，n-1是t串的最后一个字符的下标。若匹配成功，最佳情况是s串下标0到n-1的字符与t匹配，时间复杂度为O(n）；匹配成功的最差情况是，每 次均在t的最后一个字符才失败，直到s串的下标为m-n时成功，其时间复杂度为O((m-n)*n)，即O(m*n)。失败的情况是s串的第m-n个字符比t串某字符比较失败，时间复杂度为O(m*n)。之所以串s的指针i最大到m-n，是因为在m-n 之后,所剩串的长度已经小于子串长度n，故不必再去比较。算法中未讨论输入错误(如s串长度小于t串长度）。 另外，根据子串的定义，返回值i-n+1是子串在主串中的位置，子串在主串中的下标是i-n。 3．以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。【东南大学 2000五（15分）】【西北大学2002六（15分）】 [题目分析]设以字符数组s表示串，重复子串的含义是由一个或多个连续相等的字符组成的子串，其长度用max表示，初始长度为0，将每个局部重复子串的长度与max相比，若比max大，则需要更新max，并用index记住其开始位置。 int LongestString(char s[]) ∥串用一维数组s存储,本算法求最长重复子串，返回其长度 {int index=0,max=0; ∥index记最长的串在s串中的开始位置，max记其长度int length=1,i=0,start=0;∥length记局部重复子串长度，i为字符数组下标while(s[i]!=’\0’) if(s[i]==s[i+1]) {i++; length++;} else∥上一个重复子串结束 {if(max i++;start=i;length=1; ∥初始化下一重复子串的起始位置和长度} printf(“最长重复子串的长度为%d，在串中的位置%d\n”，max,index); return(max); }∥算法结束 算法的时间复杂度为O(n），每个字符与其后继比较一次。 4．编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件 【西北大学 2000 （字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。 四 (10分)】 ［问题分析］由于字母共26个，加上数字符号10个共36个，所以设一长36的整型数组，前10个分量存放数字字符出现的次数，余下存放字母出现的次数。从字符串中读出数字字符时，字符的ASCII代码值减去数字字符‘0’的ASCII 代码值，得出其数值(0..9)，字母的ASCII代码值减去字符‘A’的ASCII代码值加上10，存入其数组的对应下标分量中。遇其它符号不作处理，直至输入字符串结束。 void Count（） ∥统计输入字符串中数字字符和字母字符的个数 ｛int i，num[36]； char ch； for（i＝0；i<36；i++）num[i]＝０；∥初始化 while（（ch＝getchar（））!=‘#’）∥‘#’表示输入字符串结束if（ch>=‘0’&& ch<=‘9’）｛i=ch－48;num[i]++；｝∥数字字符 else if（ch>=‘A’&& ch<=‘Z’）｛i=ch-65+10;num[i]++；｝∥字母字符 for（i=0；i<10；i++）∥输出数字字符的个数 printf（“数字％d的个数＝％d\n”，i，num[i]）； for（i＝10；i<36；i++）∥求出字母字符的个数 printf（“字母字符％c的个数＝％d\n”，i＋55，num[i]）； ｝∥算法结束。 5．写出一个递归算法来实现字符串逆序存储。【中科院研究生院2004四(7分)】[题目分析]实现字符串的逆置并不难，但本题“要求不另设串存储空间”来实现字符串逆序存储，即第一个输入的字符最后存储，最后输入的字符先存储，使用递归可容易做到。 void InvertStore(char A[]) ∥字符串逆序存储的递归算法 {char ch; static int i = 0; ∥需要使用静态变量 scanf ("%c",&ch); if(ch!= '.') ∥规定'.'是字符串输入结束标志 {InvertStore(A); A[i++] = ch; ∥字符串逆序存储 } A[i] = '\0'; ∥字符串结尾标记 }∥结束算法InvertStore 6．S=“S 1S 2 …S n ”是一个长为N的字符串，存放在一个数组中，编程序将S改造 之后输出： （1）将S的所有第偶数个字符按照其原来的下标从大到小的次序放在S的后半部分； （2）将S的所有第奇数个字符按照其原来的下标从小到大的次序放在S的前半部分； 例如： S=‘ABCDEFGHIJKL’ 则改造后的S为‘ACEGIKLJHFDB’。【中科院计算所 1995】 [题目分析]对读入的字符串的第奇数个字符，直接放在数组前面，对第偶数个字符，先入栈，到读字符串结束，再将栈中字符出栈，送入数组中。限于篇幅，这里编写算法，未编程序。 void ReArrangeString() ∥对字符串改造，将第偶数个字符放在串的后半部分，第奇数个字符前半部分。{char ch,s[],stk[]; ∥s和stk是字符数组（表示字符串）和字符栈 int i=1,j; ∥i和j字符串和字符栈指针 while((ch=getchar())!=’#’)s[i++]=ch;∥读入字符串,’#’是字符串结束标志 s[i]=’\0’; ∥字符数组中字符串结束标志 i=1;j=1; while(s[i]) ∥改造字符串 {if(i%2==0) stk[i/2]=s[i]; else s[j++]=s[i]; i++; }∥while i--; i=i/2; ∥i先从’\0’后退，然后其含义是第偶数字符的个数 while(i>0) s[j++]=stk[i--] ∥将第偶数个字符逆序填入原字符数组} 7．若x和y是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。 【中国航天科研机构2005六(7分)】 [题目分析]两串相等指长度相等且对应位置的字符相同。以下算法设串采用堆结构存储。 int StringEqual(STRING x, STRING y) ∥本算法判断两个顺序存储的串x和y是否相等，相等返回1，否则返回0 {if(x.length!=y.length) return(0); p=x.str; q=y.str; while(p && q && *p==*q) {p++; q++;} ∥对应字符相等，指针后移 if(!p && !q) return(1); else return(0); } 8．设计一个程序，使输入的句子按如下方式改造之后输出: (1) 单词之间只留一个空格做间隔； (2) 句子结束后必须紧跟句号； (3) 如果把句子的单词从左到右依次编号为1，2，3，…则对于第奇数个单词，只要直接复制就行了，而对于第偶数个单词，应按反序打印。例如： 输入句子是: this is a silly program ; 改造后的输出是:this si a yllis program. 【中国科学技术大学1995十六.2(15分)】 #include void transf(char *s) ∥本算法将串s按要求改造 {char *s,sk[]; ∥sk是栈，存储第偶数个单词 int i,j,k,flag,finished=0;∥flag是单词开始与结束的标记 scanf(“%s”,s); i=j=k=flag=0; ∥k是单词个数，用于标记奇数或偶数单词while(*s!=’\0 ’&& !finished) switch(*s) {case‘’:while(*s!=’\0’ && *s==’’)s++;∥滤去前导空格if(flag==1) ∥单词结束 {if(k%2==0) ∥第偶数个单词逆置 while(i>0) s[++j]=sk[i--]; s[++j]=’’; ∥用一个空格分割单词}； flag=0; s++; break; case‘;’:while(s[j]==’’)j--; ∥分号为句子结束标志 s[++j]=’.’; finished=1; break; ∥句子结束后要紧跟句号 default: if(flag==0) {flag=1; k++;} ∥开始新单词 if(k%2==1) s[++j]=*s++; ∥奇数单词直接复制 else sk[++i]=*s++; ∥偶数单词进栈 }∥switch } main() {char s[]; scanf(“%s”,s); transf(s); } 9．试设计一个C算法（或C程序）：用单链表作存储结构，以回车为结束标志，输入一个任意长度的字符串；然后判断该字符串是否为“回文”（正向读和反向读时，串值相同的字符串称为“回文”），输出信息“Yes”或“No”；最后删除字符串并释放全部空间。例如： 若输入“ABCD12321DCBA”是回文，则输出“Yes”; 若输入“ABCD123DCBA”，不是回文，则输出“No”。 要求：定义相关数据类型，不得使用数组（顺序表）作字符串的存诸结构和辅助存储空间。假定字符串的长度为n ,试分析上述算法的时间复杂度。【华中科技大学2004五(10分)】 [题目分析]利用栈存放字符串的前半部分，将后半部分与栈中弹出元素比较。int Symmetry(Linkedlist head,int n) ∥本算法判断数据域为字符且长为n的单链表是否是“回文”，返回1或0表示成功或失败 {char s[]; ∥字符栈，容量足够大 p=head->next ∥设链表带头结点 int i=0; while(i<=n/2) ∥前一半字符入栈，链表指针后移 {s[i]=p->data; p=p->next; i++;} if(n%2==1) p=p->next;∥若链表有奇数个结点，则跳过中间结点 while(p) if(p->data==s[i]) {p=p->next; i--;} else break; ∥不是回文 if(!p && i==0) return(1); else return(0); } 4.2.1 有一电源和负载都是星形联结的对称三相电路,已知电源相电压为 220 V,负载每相 阻抗模 Z 为10Ω,试求负载的相电流和线电流,电源的相电流和线电流。 解：负载相电压 220P U V = 负载相电流 220 2210P P U I A Z === 负载线电流 22L P I I A == 电源线电流 22SL L I I A == 电源相电流 22SP SL I I A == 4.2.3 有一电源为三角形联结, 而负载为星形联结的对称三相电路, 已知电源相电压为 220 V, 每相负载的阻抗模Z 为 10 Ω, 试求负载和电源的相电流和线电流。 解：电源线电压 220SL U V = 负载线电压 220L SL U U V == 负载相电压 127 P U V === 负载相电流 12712.710P P U I A Z === 负载线电流 12.7L P I I A == 电源线电流 12.7SL L I I A == 电源相电流 7.33 SP I A === 4.3.1. 有三个相同的电感性单相负载,额定电压为 380 V,功率因素为 0.8, 在此电压下消耗的有功功率为 1.5 kW 。把它接到线电压为 380 V 的对称三相电源上, 试问应采用什么样的联结方式? 负载的 R 和 X L 是多少? 解：三角形联接。31.510 4.933800.838077.14.93cos 77.10.861.7sin 77.10.646.3P P P P L P I A U U Z I R Z X Z λ???= ==??===Ω ==?=Ω ==?=Ω 4.3.2 某三相负载,额定相电压为 220 V,每相负载的电阻为4Ω, 感抗为 3Ω, 接于线电压为 380 V 的对称三相电源上, 试问该负载应采用什么联结方式?负载的有功功率、无功功率和视在功率? 解：星形联接。 5 Z = ==Ω 2204454cos 0.853sin 0.6 5P P L U I A Z R Z X Z ??== ======= 3cos 32200.8232323sin 32200.6174243322029040P P P P P P P U I W Q U I Var S U I V A ??==??===??===?=? 4.3.6 电路如图所示,在 220/380 V 的低压供电系统中, 分别接有30只日光灯和一台三相电动机, 已知每只日光灯的额定值为:U N = 220 V, P N = 40 W, λN = cos ?N = 0.5,日光灯分三 组均匀接入三相电源。电动机的额定电压为380 V,输入功率为3 kW,功率因素为 0.8, 三角形联结,求电源供给的线电流。 解： 01arccos 0.560?== 02arccos 0.836.9?== 3P = P1 + P2 = (4030310)W =4 200W ?+? L 1 L 2 L 3 N I L 第四章作业参考答案 4. 用推广的Euclid算法求67 mod 119的逆元 解：初始化：(1,0,119), (0,1,67) 1：Q=119/67=1，(0,1,67) , (1,-1,52) 2：Q=67/52=1，(1,-1,52), (-1,2,15) 3：Q=52/15=3，(-1,2,15), (4,-7,7) 4：Q=15/7=2，(4,-7,7), (-9,16,1) 所以67－1 mod 119＝16 10．设通信双方使用RSA加密体制，接收方的公开钥是(e，n)＝(5,35)，接收到的密文是C ＝10，求明文M。 解：由n＝35，易知35＝5×7，进而?(n)=?(35)=24， 由RSA加密体制可知，ed≡1 mod ?(n)，即5d≡1 mod 24，所以d＝5 ∴M=C d mod n＝105 mod 35＝5 11. 已知c d mod n的运行时间是O(log3n)，用中国剩余定理改进RSA的解密运算。如果不 考虑中国剩余定理的计算代价，证明改进后的解密运算速度是原解密运算速度的4倍。证明：RSA的两个大素因子p，q的长度近似相等，约为模数n的比特长度log n的一半，即(log n)/2，而在中国剩余定理中要计算模p和模q两个模指数运算，与c d mod n的运行时间规律相似，每一个模指数运算的运行时间仍然是其模长的三次幂，即O[((log n)/2)3]= O(log3n)/8，这样在不考虑中国剩余定理计算代价的情况下，总的运行时间为两个模指数的运行时间之和，即O(log3n)/8＋O(log3n)/8＝O(log3n)/4，得证。 12. 设RSA加密体制的公开钥是(e，n)＝(77，221)。 (1) 用重复平方法加密明文160，得中间结果为 1602(mod 221)=185，1604(mod 221)=191，1608(mod 221)=16，16016(mod 221)=35，16032(mod 221)=120，16064(mod 221)=35，16072(mod 221)=118，16076(mod 221)=217，16077(mod 221)=23， 若敌手得到以上中间结果就很容易分解n，问敌手如何分解n 解：由以上中间结果得16016(mod 221)=35＝16064(mod 221)， 此即16064－16016=0 (mod 221) 即(16032－1608) (16032+1608)=0 (mod 221) (120－16)(120＋16)=0 (mod 221) 104×136＝0 (mod 221) 由gcd(104,221)=13及gcd(136,221)=17，可知221的分解为221＝13×17 (2) 求解密密钥d d＝e－1mod ?(221)=77-1 mod 12×16 由扩展Eucild算法可得d＝5。 13．在ElGamal体制中，设素数p＝71，本原根g＝7， （1）如果接收方B的公开钥是y B＝3，发送方A选择的随机整数k＝3，求明文M＝30所对应的密文。 解：C1=g k mod p＝73 mod 71＝59 C2=y B k M mod p＝33×30 mod 71＝29 所以密文为(59，29) （2）如果A选择另一个随机数k，使得明文M=30，加密后的密文是C＝（59，C2），求C2解：由C1=g k mod p得59＝g k mod p＝7k mod 71，即k＝3 而C2=y B k M mod p＝33×30 mod 71＝29 14．设背包密码系统得超递增序列为（3，4，9，17，35），乘数为t＝19，模数k＝73，试对good night加密。 解：由A=（3，4，9，17，35），乘数为t＝19，模数k＝73， 第四章串习题及答案 一、基础知识题 4.1 简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 4.2 假设有如下的串说明： 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))的返回值是什么? 4.3 设T[0..n-1]="adaabaabcaabaa",P[0..m-1]="aab".当用模式串匹配目标串T时,请给出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一个位移。 二、算法设计题： 4.4 利用C的库函数strlen,strcpy和strcat写一算法void StrInsert(char *S, char *T, int i),将串T插入到串S的第i个位置上。若i大于S的长度,则插入不执行。 4.5 利用C的库函数strlen 和strcpy(或strncpy)写一算法void StrDelete(char *S,int i, int m)删去串S中从位置i开始的连续m个字符。若i≥strlen(S),则没有字符被删除；若i+m≥strlen(S),则将S中从位置i开始直至末尾的字符均删去。 4.6 以HString为存储表示,写一个求子串的算法。 4.7 一个文本串可用事先给定的字母映射表进行加密。例如,设字母映射表为： a b c d e f g h i j k l m n o p q r s t u v w x y z n g z q t c o b m u h e l k p d a w x f y i v r s j 则字符串"encrypt"被加密为"tkzwsdf".试写一算法将输入的文本串进行加密后输出；另写一算法,将输入的已加密的文本串进行解密后输出。 4.8 写一算法void StrReplace(char *T, char *P, char *S),将T中首次出现的子串P替换为串S。注意：S和P的长度不一定相等。可以使用已有的串操作。 4.9 将NaveStrMatch改写为输出目标串中所有也模式串匹配的有效位移。 *4.10 利用4.9的结果写一算法void StrReplaceAll(char *T, char *P, char *S),将T中出现的所有与P相等的不重叠子串替换为S,这里S和P的长度不一定相等。 4.11 若S和T是用结点大小为1的单链表存储的两个串,试设计一个算法找出S中第一个不在T中出现的字符。 答案： 4.1 简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 答：空串是指不包含任何字符的串,它的长度为零。 空白串是指包含一个或多个空格的串,空格也是字符。 串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 主串和子串是相对的,一个串中任意个连续字符组成的串就是这个串的子串,而包含子串的串就称为主串。 静态分配的顺序串是指串的存储空间是确定的,即串值空间的大小是静态的,在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间,在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定,也是顺序存储空间)。 目标串和模式串:在串匹配运算过程中,将主串称为目标串,而将需要匹配的子串称为模式串,两者是相对的。 有效位移和无效位移：在串定位运算中,模式串从目标的首位开始向右位移,每一次合法位移后如果模式串与目标中相应的字符相同,则这次位移就是有效位移(也就是从此位置开始的匹配成功),反之,若有不相同的字符存在,则此次位移就是无效位移(也就是从此位置开始的匹配失败)。 4、2 解：(1) stchr(*s,c)函数的效用是查找字符c在串s中的位置,若找到,则返回该位置,否则返回NULL。 因此: 执行p=stchr(s1,'t');后p的值是指向字符t的位置, 也就是p==&s1[5]。 执行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" 书中图4.18是否错了。 G2A 输入控制端 习 题 一、填空题 1. 常用的译码器电路有二-四译码器、二-十进制译码器和三-八译码器。 2. 由发光二极管构成的七段数码管的两种接法分别为共阳极接法和共阴极接法。 3. 在优先编码器中，是优先级别高的编码排斥优先级别低的。 4. 消除组合逻辑电路竞争冒险的方法有引入选通脉冲、输出接滤波电容和修改逻辑设计等。 5. 如果对键盘上108个符号进行二进制编码，则至少要7位二进制数码。 6. 一个二进制译码器由n 个输入端，它的输出端最多有2n 个。 二、分析与设计题 1. 写出题图4.1所示电路的输出信号表达式，并说明其功能。 A B Y 题图4.1 解：'')')')'(()')'(((B A AB B A B B A A Y +=+++++= 实现同或功能 2. 分析题图4.2所示电路的逻辑功能。 解：B A AB AB B AB A Y '')')')'(()')'(((+== 实现异或功能 3. 分析题图 4.3所示电路的逻辑功能，并判断能否化简，若能，则化简，并修改逻辑设计。 解： C B BC C B C B BC C B BC C AB C B AB C A F ⊕=+=+=++=⊕++='')'''()'''''()'')'()''(( 能化简，化简结果为B 异或C 。 修改逻辑设计如图 B C F A B Y Z A B C F 题图4.2 题图4.3 4. 用与非门设计一个4变量的多数表决电路。设输出为Y，当输入A、B、C、D有3个或3个以上为1时，输出为1，其他情况输出为0。要求：列出真值表，写出输出逻辑表达式，画出逻辑电路图。 解：列真值表 A B C D Y 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 写出逻辑表达式 )')' ()' ()' ()' ((' ' ' ' BCD ACD ABD ABC ABC ABD ACD BCD ABCD ABCD D ABC CD AB BCD A Y = + + + = + + + + = 画出逻辑电路图如图 第二章一元线性回归模型 1、最小二乘法对随机误差项u作了哪些假定？说明这些假定条件的意义。 答：假定条件： (1)均值假设：E(u i)=0,i=1,2,…； (2)同方差假设：Var(u i)=E[u i-E(u i)]2=E(u i2)=σu2 ,i=1,2,…； (3)序列不相关假设：Cov(u i,u j)=E[u i-E(u i)][u j-E(u j)]=E(u i u j)=0,i≠j,i,j=1,2,…； (4)Cov(u i,X i)=E[u i-E(u i)][X i-E(X i)]=E(u i X i)=0； (5)u i服从正态分布, u i～N(0,σu2)。 意义：有了这些假定条件，就可以用普通最小二乘法估计回归模型的参数。 2、阐述对样本回归模型拟合优度的检验及回归系数估计值显著性检验的步骤。答：样本回归模型拟合优度的检验：可通过总离差平方和的分解、样本可决系数、样本相关系数来检验。 回归系数估计值显著性检验的步骤： (1)提出原假设H0 ：β1=0； (2)备择假设H1 ：β1≠0； (3)计算t=β1/Sβ1； (4)给出显著性水平α，查自由度v=n-2的t分布表，得临界值tα/2(n-2)； (5)作出判断。如果|t| 第四章 习题4.2.1：考虑上下文无关文法： S->S S +|S S *|a 以及串aa + a* (1)给出这个串的一个最左推导 S -> S S * -> S S + S * -> a S + S * -> a a + S * -> aa + a* (3)给出这个串的一棵语法分析树 习题4.3.1：下面是一个只包含符号a和b的正则表达式的文法。它使用+替代表示并运算的符号|，以避免和文法中作为元符号使用的竖线相混淆： rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 1)对这个文法提取公因子 2)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？ 3)提取公因子之后，原文法中消除左递归 4)得到的文法适用于自顶向下的语法分析吗？ 解 1)提取左公因子之后的文法变为 rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 2)不可以，文法中存在左递归，而自顶向下技术不适合左递归文法 3)消除左递归后的文法 rexpr -> rterm rexpr’ rexpr’-> + rterm rexpr’|ε rterm-> rfactor rterm’ rterm’-> rfactor rterm’|ε rfactor-> rprimay rfactor’ rfactor’-> *rfactor’|ε rprimary-> a | b 4)该文法无左递归，适合于自顶向下的语法分析 习题4.4.1：为下面的每一个文法设计一个预测分析器，并给出预测分析表。可能要先对文法进行提取左公因子或消除左递归 (3)S->S(S)S|ε (5)S->(L)|a L->L,S|S 解 (3) ①消除该文法的左递归后得到文法 S->S’ S’->(S)SS’|ε ②计算FIRST和FOLLOW集合 FIRST(S)={(,ε} FOLLOW(S)={),$} FIRST(S’)={(,ε} FOLLOW(S’)={),$} ③ (5) ①消除该文法的左递归得到文法 S->(L)|a 习题四参考答案 一、选择题 1．下面关于串的叙述中，哪一个是不正确的？（B ） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2．串的长度是指( A ) A. 串中包含的字符个数 B. 串中包含的不同字符个数 C. 串中除空格以外的字符个数 D. 串中包含的不同字母个数 3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ）A．求子串B．联接C．模式匹配D．求串长 4．设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是( C )。 A. O(m) B. O(n) C. O(n + m) D. O(n×m) 5. 串也是一种线性表，只不过( A )。 A. 数据元素均为字符 B. 数据元素是子串 C. 数据元素数据类型不受限制 D. 表长受到限制 6.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a11为第一元素， 其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。 A. 13 B. 33 C. 18 D. 40 7. 有一个二维数组A[1..6, 0..7] ，每个数组元素用相邻的6个字节存储，存储器按字节编址， 那么这个数组占用的存储空间大小是（D ）个字节。 A. 48 B. 96 C. 252 D. 288 8.设有数组A[1..8,1..10]，数组的每个元素占3字节，数组从内存首地址BA开始以列序 为主序顺序存放，则数组元素 A[5，8]的存储首地址为( B )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 9. 稀疏矩阵的三元组存储表示方法( B ) A. 实现转置操作很简单，只需将每个三元组中行下标和列下标交换即可 B. 矩阵的非零元素个数和位置在操作过程中变化不大时较有效 C. 是一种链式存储方法 D. 比十字链表更高效 10. 用十字链表表示一个稀疏矩阵，每个非零元素一般用一个含有( A )域的结点表示。 A.5 B.4 C. 3 D. 2 二、填空题 1. 一个串的任意连续字符组成的子序列称为串的子串，该串称为主串。2．串长度为0的串称为空串，只包含空格的串称为空格串。 3. 若两个串的长度相等且对应位置上的字符也相等，则称两个串相等。 4. 寻找子串在主串中的位置，称为模式匹配。其中，子串又称为模式串。 5. 模式串t="ababaab"的next[]数组值为-1001231，nextval[]数组值为-10-10-130。 6. 设数组A[1..5,1..6]的基地址为1000，每个元素占5个存储单元，若以行序为主序顺序 存储，则元素A[5,5]的存储地址为1140。 第四章作业答案 6.确定{1, 2,…, 8}的下列排列的逆序列。 ⅰ) 35168274 ⅱ) 83476215 解ⅰ) 35168274的逆序列是2, 4, 0, 4, 0, 0, 1, 0。 ⅱ) 83476215的逆序列是6, 5, 1, 1, 3, 2, 1, 0。 7.构造{1, 2,…, 8}的排列，其逆序列是 ⅰ) 2, 5, 5, 0, 2, 1, 1, 0 ⅱ) 6, 6, 1, 4, 2, 1, 0, 0 解ⅰ) □□1□□□□□ □□1□□□2□ □□1□□□23 4□1□□□23 4□1□5□23 4□165□23 4□165723 4 8 1 6 5 7 2 3 逆序列是2, 5, 5, 0, 2, 1, 1, 0的排列是48165723。 ⅱ)□□□□□□ 1 □ □□□□□□ 1 2 □ 3 □□□□12 □ 3 □□□412 □ 3 □5□412 □ 3 65□412 7 3 65□412 7 3 658412 逆序列是6, 6, 1, 4, 2, 1, 0, 0的排列是73658412。 15.对于{x7, x6,…, x1, x0}的下列每一个组合，通过使用基为2的生成 算法确定其直接后继组合： ⅰ) {x4, x1, x0} ⅱ) {x7, x5, x3} ⅲ) {x7, x5, x4, x3, x2, x1, x0} ⅳ) {x0} 解ⅰ) {x4, x1, x0} 对应0和1的8-元组00010011，使用基为2的生成算法求得j = 2，确定00010011的下一个8-元组是00010100，其对应的组合是{x4, x2}。因此，{x4, x1, x0}的直接后继组合是 {x4, x2}。 ⅱ) {x7, x5, x3}对应0和1的8-元组10101000，使用基为2的生成算法求得j= 0，确定10101000的下一个8-元组是10101001，其对应的组合是{x7, x5, x3, x0}。因此，{x7, x5, x3}的直接后继组合是 {x7, x5, x3, x0}。 ⅲ) {x7, x5, x4, x3, x2, x1, x0}对应0和1的8-元组10111111，使用基为2的生成算法求得j= 6，确定10111111的下一个8-元组是11000000，其对应的组合是{x7, x6}。因此，{x7, x5, x4, x3, x2, x1, x0} 第四章作业参考答案 4-05 IP地址分为几类？各如何表示？IP地址的主要特点是什么？ 答：在IPv4的地址中，所有的地址都是32个二进制位，并且可记为 IP地址::= { <网络号>, <主机号>} IP地址被分为A、 A类地址：网络号字段为1字节，最前面的1位是0。 B类地址：网络号字段为2字节，最前面的2位是10。 C类地址：网络号字段为3字节，最前面的3位是110。 D类地址：用于多播，最前面的4位是1110。 E类地址：保留今后使用，最前面的4位是1111。 IP 地址特点如下： 1.每一个IP 地址都由网络号和主机号两部分组成。从这个意义上说，IP 地址是一种分等级的地址机构； 2.IP地址是标志一个主机（或路由器）和一条链路的接口； 3.具有相同网络号的主机集合构成一个网络，因此，由转发器或网桥连接起来的若干个局域网仍为一个网络。具有不同网络号的局域网互连必须使用路由器； 4.所有分配到网络号的网络都是平等的。 4-07 试说明IP地址与硬件地址的区别。为什么要使用这两种不同的地址？ 答：如下图所示，IP地址在IP数据报的首部，而硬件地址则位于MAC帧的首部。在网络层以上使用的是IP地址，数据链路层及以下使用的是硬件地址。 由于全世界存在着各式各样的网络，它们使用不同的硬件地址。要使这些异构网络能够互相通信就必须进行非常复杂的硬件地址转换工作，因此由用户或用户主机来完成这项工作几乎是不可能的事。但统一的IP地址把这个复杂问题解决了。连接到因特网的主机只需拥有统一的IP地址，它们之间的通信就像连接在同一个网络上那样简单方便，当需要把IP地址转换为物理地址时，调用ARP的复杂过程都是由计算机软件自动进行的，而用户是看不见这种调用过程的。因此，在虚拟的IP网络上用IP地址进行通信给广大计算机用户带来很大的方便。 4-09 试回答下列问题： （1）子网掩码为255.255.255.0 代表什么意思？ 读书破万卷下笔如有神 《一定能摸到红球吗？》说课稿 林银花 教材说明：一、１、课题：《一定能摸到红球吗？》 ２、本节内容的地位和作用 在现代社会中，人们面临着更多的机会和选择，常常需要在不确定情境中作出合理的决策,概率正是通过对不确定现象和事件发生的可能性的刻画,来为人们更好的制定决策提供依据和建议.本节内容又是 义务教育阶段,唯一培养学生从不确定的角度来观察世界的数学内容,让学生了解可能性是普遍的,有助于他们理解社会,适应生活. ３、教学目标设计： (１)认知目标： （Ａ）经历猜测．实验．收集与分析试验结果等过程 （Ｂ）体会事件的发生的不确定性知道事情发生的可能性有多大。 （２）、能力目标： (Ａ)经历游戏等的活动过程，初步认识确定事件和不确定事件 （Ｂ）在与其它人交流的过程中，能合理清晰地表达自己的思维过程； （３）、情感目标： （Ａ）通过创设游戏情境，让学生主动参与，做“数学实验”，激发学生学习的热情和兴趣，激活学生思维。 （Ｂ）在与他人的合作过程中，增强互相帮助、团结协作的精神。 （Ｃ）体会到在生活中我们可以从确定和不确定两方面分析一件事情. ４、本课重点、难点分析： 学习的重点是初步体验事情发生的确定性和不确定性. 学习的难点是确定事件发生的可能性大小. 学习本节知识应注意猜测,试验,收集与分析实验结果,从中体会事件发生的可能性及大小. 二、教学对象分析： 1、初一学生性格开朗活泼，对新鲜事物特别敏感，且较易接受，因此，教学过程中创设的问题情境应较生动活泼，直观形象，且贴近学生的生活，从而引起学生的有意注意。 2、初一学生的概括能力较弱，推理能力还有待不断发展，所以在教学时，可让学生充分试验, 收集，分析,帮助他们直观形象地感知。 8、 (a) 用户王明对两个表有select权力 GRANT SELECT ON职工 TO 王明 GRANT SELECT ON部门 TO 王明 (b) 用户李勇对两个表有insert和delete权力 GRANT INSERT, DELETE ON职工 TO 李勇； GRANT INSERT, DELETE ON部门 TO 李勇； (d) 用户刘星对职工表有select权力，对工资字段具有更新权力 GRANT SELECT ,UPDATE(工资) ON 职工 TO 刘星 (e) 用户张新具有修改这两个表的结构的权力 GRANT ALTER TABLE ON 职工 TO 张新； GRANT ALTER TABLE ON 部门 TO 张新； (f) 用户周平具有对两个表所有权力，并具有给其他用户授权的权利 GRANT ALL PRIVILIGES ON 职工 TO 周平 WITH GRANT OPTION; GRANT ALL PRIVILIGES ON部门 TO 周平 WITH GRANT OPTION; (g) 用户杨兰具有从每个部门职工中select最高工资，最低工资，平均工资的权力，他不能 查看每个人的工资 --创建视图 CREATE VIEW 部门工资 AS SELECT 部门号，MAX（工资），MIN（工资），AVG（工资） FROM 职工 GROUP BY部门号； --在视图上授权 GRANT SELECT ON 部门工资 TO 杨兰； 9、把习题8中的每一种情况，撤销各用户所授予的权力 (a) REVOKE SELECT ON职工 FROM 王明； REVOKE SELECT ON部门 FROM 王明； (b) 第四章串作业 参考答案： 1、简述空串和空格串（或称空格符串）的区别？ 1）空串是指不包括任何字符的串，空格串指包含若干个空格字符的字符串； 2）空串长度为零，空格串长度为所包括的空格字符的个数。2、设s=‘I AM A STUDENT ’,t=‘GOOD’,q=‘WORKER’.求： 1）StrLength（s） 2）StrLength（t） 3）SubString（s，8，7） 4）SubSting（t，2，1） 5）Index（s，’A’） 6）index（s，t） 7）Replace（s，’STUDENT’，q） 8）Concat（SubString（s，6，2）,Concat（t，SubString （s，7，8））） 答： 1)StrLength（s）=14 2)StrLength（t）=4 3)SubString（s，8，7） = ‘STUDENT’ 4)SubSting（t，2，1） = ‘O’ 5)Index（s，’A’）= 3 6)index（s，t） = 0 7)Replace（s，’STUDENT’，q） = ‘I AM A WORKER ’ 8)Concat（SubString（s，6，2）,Concat（t，SubString（s， 7，8））） = ‘A GOOD STUDENT’ 3、若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),subs tr(S4,index(S2,‘8’),length(S2)))其结果是多少？ 答：ABC###G1234 4、下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。请将空格处填上正确的语句。 void maxcomstr(orderstring *s,*t; int index, length) { int i,j,k,length1,con; index=0;length=0;i=1; while (i<=s.len) { j=1; while(j<=t.len) { if (s[i]= =t[j]) { k=1; length1=1; con=1; while(con) if (1) _ { length1=length1+1;k=k+1; } else (2) __; if (length1>length) { index=i; length=length1; } (3)____; } else (4) ___; P1774.14 为练习4.3的文法构造一个预测语法分析器 bexpr→bexpr or bterm|bterm bterm→bterm and bfactor | bfactor bfactor→not bfactor|(bexpr)|true |false 解1 非递归方法 1)消除左递归 ①bexpr→bterm A ②A→or bterm A ③A→ε ④bterm→bfactor B ⑤B→and bfactor B ⑥B→ε ⑦bfactor→not bfactor ⑧bfactor→(bexpr) ⑨bfactor→true ⑩bfactor→false 2)求first集与follow集 针对以同一非总结符开头的产生式右部求first集如果该非终结符能产生ε则需要求其follow集 ①bexpr→bterm A first(bterm A)= {not,(,true,false} ②A→or bterm A first(or bterm A)={or} ③A→εfollow(A）=follow(bexpr)= {$, )} ④bterm→bfactor B first(bfactor B)={not,(,true,false} ⑤B→and bfactor B first(and bfactor B)={and} ⑥B→εfollow(B）=follow(bterm)=first(A) 因为first(A)= {or , ε} 包含ε 所以follow(B）=follow(bterm) =first(A)∪follow(A）-{ε}={or, $, )} ⑦bfactor→not bfactor first(not bfactor)={not} ⑧bfactor→(bexpr)first((bexpr))={(} ⑨bfactor→true first(true)={true} ⑩bfactor→false first(false)={false} 表中空白处填error，表示调用错误处理程序 4)根据步骤3）编写预测分析程序 下面给出通用的预测分析算法，具体程序留给同学们根据算法自己完善。 repeat 4-2 有一复合墙壁，它由2.5cm 的铜板，3.2mm 的石棉层和5cm 的玻璃纤维层组成。墙壁两侧温差为560℃，试计算通过该复合墙壁单位面积的导热量。 解：由表查得铜板，石棉层和玻璃纤维层的导热系数分别为： =1λ398 W/(m·K ) =2λ 0.1W/(m·K ) =3λ0.06 W/(m·K ) ∴导热热阻为：R=11λδ+22λδ+33λδ==++06.005.01.00032.0398 025.00.86 由傅里叶定律得：q= R t ?=86.0560=651W/m 2 4-3 厚5cm 的铜板一侧温度为250℃，另一侧覆盖了2.5cm 厚的玻璃纤维层。玻璃纤维层外侧温度为35℃，通过该复合壁的总热流量为52 kW ，试求该壁的面积是多少？ 解：由表查得铜板和玻璃纤维层的导热系数分别为： =1λ 398W/(m·K ) =2λ 0.06W/(m·K ) ∴导热热阻为：R=11λδ+2 2λδ=0.42 由傅里叶定律得：q= R t ?=42.035250-=511.9 W/m 2 ∴A= q Q =101.6 m 2 4-4 有一平板，其材料的导热系数与温度的关系可表示为20(1)k k T =+β。试推导该壁面导热热流量的表达式。 解：由傅里叶定律得：Q=-A dx dt t )(λ ∴212121)3 *()1()(13020t t t t o t t t t k t d t k t d t dx A Q ββλδ +-=+-=-=??? 即：Q=)](3)[(131321200t t t t dx A k -+-?βδ 4-5 一导热系数为k =46 W/(m ﹒℃)的钢管，内径为3.0cm ，管壁厚2mm 。一种流体流过管内，使管内侧对流换热系数为1500 W/(m 2 ﹒℃)，而另一种流体横向冲刷圆管外侧，使外侧对流换热系数为197 W/(m 2﹒℃)。管内流体温度为223℃，管外流体温度为57℃。试 计算机组成原理第四章作业答案(终板) 第四章作业答案 4.1 解释概念：主存、辅存，Cache, RAM, SRAM, DRAM, ROM, PROM ,EPROM ,EEPROM CDROM, Flash Memory. 解：1主存：主存又称为内存，直接与CPU交换信息。 2辅存：辅存可作为主存的后备存储器，不直接与CPU交换信息，容量比主存大，速度比主存慢。 3 Cache: Cache缓存是为了解决主存和CPU的速度匹配、提高访存速度的一种存储器。它设在主存和CPU之间，速度比主存快，容量比主存小，存放CPU最近期要用的信息。 4 RAM; RAM是随机存取存储器，在程序的执行过程中既可读出信息又可 写入信息。 5 SRAM: 是静态RAM，属于随机存取存储器，在程序的执行过程中既可读出信息又可写入信息。靠触发器原理存储信息，只要不掉电，信息就不会丢失。 6 DRAM 是动态RAM，属于随机存取存储器，在程序的执行过程中既可读出信息又可写入信息。靠电容存储电荷原理存储信息，即使电源不掉电，由于电容要放电，信息就会丢失，故需再生。 7 ROM: 是只读存储器，在程序执行过程中只能读出信息，不能写入信息。 8 PROM: 是可一次性编程的只读存储器。 9 EPROM 是可擦洗的只读存储器，可多次编程。 10 EEPROM: 即电可改写型只读存储器，可多次编程。 11 CDROM 即只读型光盘存储器。 12 Flash Memory 即可擦写、非易失性的存储器。 4.3 存储器的层次结构主要体现在什么地方？为什么要分这些层次？计算机如何管理这些层次？ 答：存储器的层次结构主要体现在Cache—主存和主存—辅存这两个存储层次上。 Cache—主存层次在存储系统中主要对CPU访存起加速作用，即从整体运行的效果分析，CPU访存速度加快，接近于Cache的速度，而寻址空间和位价却接近于主存。 主存—辅存层次在存储系统中主要起扩容作用，即从程序员的角度看，他所使用的存储器其容量和位价接近于辅存，而速度接近于主存。 综合上述两个存储层次的作用，从整个存储系统来看，就达到了速度快、容量大、位价低的优化效果。 主存与Cache之间的信息调度功能全部由硬件自动完成。而主存—辅存层次的调度目前广泛采用虚拟存储技术实现，即将主存与辅存的一部份通过软硬结合的技术组成虚拟存储器，程序员可使用这个比主存实际空间（物理地址空间）大得多的虚拟地址空间（逻辑地址空间）编程，当程序运行时，再由软、硬件自动配合完成虚拟地址空间与主存实际物理空间的转换。因此，这两个层次上的调度或转换操作对于程序员来说都是透明的。 第4章作业答案 一、选择题 23．液压缸差动连接工作时，缸的速度( A ) 增加了，缸的输出力( D )。 A．运动速度增加了B．输出力增加了C．运动速度减少了D．输出力减少了 24．在某一液压设备中需要一个完成很长工作行程的液压缸，宜采用下述液压缸中的( D ) A．单活塞液压缸B．双活塞籽液压缸c．性塞液压缸D．伸缩式液压缸 43．单杆活塞液压缸作为差动液压缸使用时，若使其往复速度相等，其活塞直径应为活塞杆直径的( C ) 倍。 A、2 B、3 C、2 D、3 47．一般单杆油缸在快速缩回时，往往采用( C )。． A、有杆腔回油无杆腔进油；． B、差动连接； c、有杆腔进油无杆腔回油。53．摆动气缸传递的是( B)。 A、力 B、转矩 C、曲线运动。 二．判断题正确的在括号内填Y 错的在括号内填 N 9．如果不考虑液压缸的泄漏，液压缸的运动速度只决定于进入液压缸的流量 ( Y ) 10．单活塞杆液压缸缸筒固定时液压缸运动所占长度与活塞杆固定的不相等 ( Y ) 11．液压缸输出推力的大小决定进入液压缸油液压力的大小 ( Y ) 22、在流量相同的情况下，液压缸直径越大，活塞运动速度越快。 ( N ) 23、在液压传动系统中，为了实现机床工作台的往复速度一样，采用双出杆活塞式液压缸。( Y ) 24、由于油液在管道中流动时有压力损失和泄漏，所以液压泵输入功率要小于输送到液压缸的功率。( N ) 25、将单杆活塞式液压缸的左右两腔接通，同时引入压力油，可使活塞获得快速运动。( Y ) 16．因存在泄漏，因此输入液压马达的实际流量大于其理论流量，而液压泵的实际输出 流量小于其理论流量。（ Y ） 三、计算题 1、某液压马达排量V M=250mL／r，人口压力为9．8MPa，出口压力为0．49MPa， 其总效率为η=0．9，容积效率为ηv=0．92。当输人流量为22L／min时，试求： ①液压马达的输出转矩； ②液压马达的输出转速(nM)。 [答案] ①T=362．6 N·m ②nm=81 r／|min 液压马达的输出转矩为 液压马达的转速nM为 第四章存货作业与答案 第四章存货练习题及答案 一、单项选择题 1．某企业采用成本与可变现净值孰低法的个别比较法确定期末存货的价值。期初"存货跌价准备"科目的余额为4400元。假设2002年12月31日三种存货的成本和可变现净值分别为：A存货成本30000元,可变现净值30000元；B存货成本15000元,可变现净值14000元；C存货成本50000元,可变现净值48000元。该企业12月31日记入"资产减值损失"科目的金额为(C )元。C A、借方3000 B、借方1400 C、贷方1400 D、贷方3000 : 公司计提跌价准备对2002年利润的影响额为(B)万元。（根据分录确定） A、1 B、5 C、-5 D、10 3.某商场采用毛利率法对商品的发出和结存进行日常核算。2003年7月,甲类商品期初库存余额为15万元。该类商品本月购进为20万元,本月销售收入为25万元,本月销售折让为1万元。上月该类商品按扣除销售折让后计算的毛利率为20%。假定不考虑相关税费,2003年7月该类商品月末库存成本为( B)万元。 A、10 B、15.8 C、15 D、19.2 4.甲公司存货的日常核算采用毛利率计算发出存货成本。该企业2003年4月份销售收入500万元,销售成本460万元,4月末存货成本300万元。5月份购入存货700万元,本月销售收入600万元,发生销售退回40万元。假定不考虑相关税费,该企业2003年5月末存货成本为(B )万元。 A、448 B、484.8 C、540 D、440 5.当物价持续上涨时,存货计价采用先进先出法,会出现的情况是(B )。 A、高估企业当期利润 B、低估企业当期利润 C、高估期末存货价值 D、低估当期销货成本 6.某增值税一般纳税工业企业购进免税农产品一批,支付买价12000元,装卸费1000元,入库前挑选整理费400元,该批农产品的采购成本为(B )元。 A、12000 B、12200 C、13000 D、13400 7.某工业企业为增值税小规模纳税人，2005年10月9日购入材料一批，取得增值税专用发票上注明的价款为21200元，增值税额为3604元，该企业适用的增值税征收率为6%，材料入库前挑选整理费为200元，材料已验收入库。则该企业取得的该材料的入账价值应为（D）元。 A、20200 B、21400 C、23804 D、25004 8．某企业为增值税小规模纳税企业，该企业购入甲材料600公斤，每公斤含税单价为50元，发生运杂费2000元，运输途中发生合理损耗10公斤，入库前发生挑选整理费用200元，该批甲材料的入账价值为（C）元 A、30000 B、32000 C、32200 D、32700 9．某企业月初结存材料的计划成本为30000元，成本差异为超支200元，本月入库材料的计划成本为70000元，成本差异为节约700元。当月生产车间领用材料的计划成本为60000元，当月生产车间领用材料应负担的材料成本差异为（A）元第四章 作业答案
第四章 作业参考答案
第四章-串-习题及答案.doc
第4章习题答案
(新)计量作业第2章-第4章
编译原理第4章作业答案
第4章 串与数组 习题参考答案
第四章作业答案
《计算机网络》第四章-作业参考答案
严蔚敏数据结构c语言版习题集答案第四章串
第4章作业答案
第4章串 作业(参考答案)
龙书 第四章课后作业答案
作业第四章
计算机组成原理第四章作业答案(终板)学习资料
第4章作业答案
第四章 存货作业与答案