第4章 串
第4章串
一、选择题
1．下面关于串的的叙述中，哪一个是不正确的？（）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储
2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行
concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,
‘8’),length(S2)))
其结果为（）
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数组值为（）。
A．0123 B．1123 C．1231 D．1211
5．串‘ababaaababaa’的next数组为（）。
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)
C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 )
7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval数组的值为（）。
A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1 8．若串S=’software’,其子串的数目是（）。
A．8 B．37 C．36 D．9
9．设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（）。
A．2n-1 B．n2 C．(n2/2)+(n/2) D．(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1 F.其他情况
10．串的长度是指（）
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
二、判断题
1．KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）
2．设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）
3．串是一种数据对象和操作都特殊的线性表。（）
三、填空题
1．空格串是指__(1)__，其长度等于___(2)__。
2．组成串的数据元素只能是________。
3．一个字符串中________称为该串的子串。
4．INDEX（‘DATASTRUCTURE’，‘STR’）=________。
5．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为________。6．模式串P=‘abaabcac’的next函数值序列为________。
7．字符串’ababaaab’的nextval函数值为________。
8．设T和P是两个给定的串，在T中寻找等于P的子串的过程称为__(1)__，又称P为__(2)__。9．串是一种特殊的线性表，其特殊性表现在__(1)__；串的两种最基本的存储方式是__(2)__、__(3)__；两个串相等的充分必要条件是__(4)__。
10．两个字符串相等的充分必要条件是_______。
11．知U=‘xyxyxyxxyxy’；t=‘xxy’；
ASSIGN（S，U）；
ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））；
ASSIGN（m，‘ww’）
求REPLACE（S，V，m）= ________。
12．实现字符串拷贝的函数 strcpy为：
void strcpy(char *s , char *t) /*copy t to s*/
{ while (________)
}
13．下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f("abba")返回1，f("abab")返回0；
int f((1)________)
{int i=0,j=0;
while (s[j])(2)________;
for(j--; i return((3)_______) } 14．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。 程序（a） PROCEDURE maxcomstr(VAR s,t : orderstring; VAR index,length : integer); VAR i,j,k,length1:integer; con:boolean; BEGIN index :=0; length :=0; i :=1; WHILE(i<=s.len) DO [j:=1; WHILE (j<=t.len) DO [ IF (s[i]=t[j]) THEN [ k:=1; length1:=1; con:=true; WHILE con DO IF (1)__THEN [length1:=length1+1;k:=k+1;] ELSE(2) _; IF (length1>length) THEN [index:=i; length:=length1; ] (3)____; ] ELSE (4)____; ] (5) ___; ] END; 程序(b) 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) __ } } 15．完善算法：求KMP算法中next数组。 PROC get _next(t:string,VAR next:ARRAY[1..t.len] OF integer); BEGIN j:=1; k:=(1)__; next[1]:=0; WHILE j IF k=0 OR t.ch[j]=t.ch[k] THEN BEGIN j:=j+1; k:=k+1; next[j]:=k;END ELSE k:=(2)___; END; 16．下面函数index用于求t是否为s的子串，若是返回t第一次出现在s中的序号(从1开始计)，否则返回0。 例如:s=‘abcdefcdek’，t=‘cde’,则indse(s,t)=3, index(s,’aaa’)=0 。已知t，s的串长分别是mt,ms FUNC index(s,t,ms,mt); i:=1;j:=1; WHILE (i IF s[i]=t[j] THEN [ (1)__; (2)__] ELSE [ (3)___; (4)_ ] IF j>mt THEN return (5)____; ELSE return (6)__ ENDF; 17．阅读下列程序说明和pascal程序,把应填入其中的（）处的字句写在答题纸上。 程序说明： 本程序用于判别输入的字符串是否为如下形式的字符串: W&M$ 其中,子字符串M是子字符串W的字符反向排列,在此假定W不含有字符&和字 符$,字符&用作W与M的分隔符,字符$用作字符串的输入结束符。 例如,对输入字符串ab&ba$、11&12$、ab&dd$、&$,程序将分别输出 Ok.(是),No.(不是)。 程序 PROGRAM accept(input,output); CONST midch=’&’; endch=’$’; VAR an:boolean; ch:char; PROCEDURE match(VAR answer: boolean); VAR ch1,ch2:char; f:boolean; BEGIN read(ch1); IF ch1<>endch THEN IF (1)__ THEN BEGIN match(f); IF f THEN BEGIN read(ch2); answer:=(2)_ END ELSE answer:=false END ELSE (3)___ ELSE (4)___ END; BEGIN W riteln(‘Enter String:’); match(an); IF an THEN BEGIN (5)__ IF (6)_ THEN writeln(‘Ok.’) ELSE writeln(‘No.’) END ELSE writeln(‘No.’) END. 18．试利用下列栈和串的基本操作完成下述填空题。 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．名词解释：串 2．描述以下概念的区别：空格串与空串。 3．两个字符串S1和S2的长度分别为m和n。求这两个字符串最大共同子串算法的时间复杂度为T(m,n)。估算最优的T(m,n)，并简要说明理由。 4．设主串S=‘xxyxxxyxxxxyxyx’，模式串T=‘xxyxy’。请问：如何用最少的比较次数找到T在S中出现的位置？相应的比较次数是多少？ 5．KMP算法(字符串匹配算法)较Brute(朴素的字符串匹配)算法有哪些改进? 6．已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval 函数值。 7．给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。 8．令t=‘abcabaa’,求其next 函数值和nextval函数值。 9．已知字符串‘cddcdececdea’，计算每个字符的next和nextval函数的值。 10．试利用KMP算法和改进算法分别求p1=‘abaabaa’和p2=‘aabbaab’的next函数和nextval函数。 11．已知KMP串匹配算法中子串为babababaa,写出next数组改进后的next数组信息值（要求写出数组下标起点）。 12．求模式串T=‘abcaabbac' 的失败函数Next(j)值。 13．字符串的模式匹配KMP算法中,失败函数(NEXT)是如何定义的?计算模式串p=‘aabaabaaabc’中各字符的失败函数值. 14．设字符串S=‘aabaabaabaac'，P=‘aabaac' （1）给出S和P的next值和nextval值； （2）若S作主串，P作模式串，试给出利用BF算法和KMP算法的匹配过程。 15．设目标为t=‘abcaabbabcabaacbacba’,模式为p=‘abcabaa’ （1）计算模式p的naxtval函数值； （2）不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。 16．模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m，模式的长度为n，则在主串中寻找模式的KMP算法的时间复杂性是多少？如果，某一模式 P=’abcaacabaca’，请给出它的NEXT函数值及NEXT函数的修正值NEXTVAL之值。 17．设目标为S=‘abcaabbcaaabababaabca’，模式为P=‘babab’， （1）手工计算模式P的nextval数组的值； （2）写出利用求得的nextval数组，按KMP算法对目标S进行模式匹配的过程。 18．用无回溯的模式匹配法（KMP法）及快速的无回溯的模式匹配法求模式串T的next[j]值，添入下面表中： 19nextval 值的算法。 TYPE SAR=ARRAY[1..m] OF INTEGER; PTY=ARRAY[1..m] OF CHAR; PROCEDURE next2(P:PTY;VAR NEXTVAL:SAR); {在模式P中求nextval数组的值} BEGIN J:=1;NEXTVAL[1]:=0;K:=0 REPEAT IF (K=0) OR (P[J]=P[K]) THEN [ J:=J+1;K:=K+1; IF P[J]=P[K] THEN NEXTVAL[J]:=NEXTVAL[K] ELSE NEXTVAL[J]:=K ] ELSE K:=NEXTVAL[K] UNTIL J=m END; 算法中第4行有P[J]=P[K],第六行中也有P[J]=P[K]。两处比较语句相同。请分析说明此两处比较语句的含义是什么？分析此算法在最坏情况下的时间复杂度是多少？ 20．在字符串模式匹配的KMP算法中，求模式的next数组值的定义如下： next［j］=? ? ? ? ? = < < = - + - - 其它情况 ‘ 且 时 当 1 }' ... '' ... j k 1| k max{ 1 1 1 1 1j k j k p p p p j 请问： （1）当j=1时，为什么要取next[1]=0？ （2）为什么要取max{K},K最大是多少？ （3）其它情况是什么情况，为什么取next[j]=1? 21．给出KMP算法中失败函数f的定义，并说明利用f进行串模式匹配的规则，该算法的技术特点是什么？ 22．在模试匹配KMP算法中所用失败函数f的定义中，为何要求p1p2……pf(j)为p1p2……pj两头匹配的真子串？且为最大真子串？ 23．如果两个串含有相等的字符，能否说它们相等？ 24．设S1,S2为串，请给出使S1//S2=S2//S1成立的所有可能的条件（//为连接符）。25．已知：s ＝'（xyz）＋＊'，t ＝'（x＋z）＊y'。试利用联结、求子串和置换等基本运算，将 s 转化为 t 。 第五部分、算法设计 1．设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s 的子串。如果是，输出子串所在位置（第一个字符），否则输出0。（注：用程序实现）2．输入一个字符串，内有数字和非数字字符，如：ak123x456 17960?302gef4563，将其中连续的数字作为一个整体，依次存放到一数组ａ中，例如123放入ａ［０］,456放入ａ［１］，……。编程统计其共有多少个整数，并输出这些数。 3．以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。 类似本题的另外叙述有： （1）如果字符串的一个子串（其长度大于1）的各个字符均相同，则称之为等值子串。试设计一算法，输入字符串S，以“！”作为结束标志。如果串S中不存在等值子串，则输出信息“无等值子串”，否则求出（输出）一个长度最大的等值子串。 例如：若S=“abc123abc123!”，则输出“无等值子串”；若S=“abceebccadddddaaadd!”，则输出“ddddd”。 4．假设串的存储结构如下所示，编写算法实现串的置换操作。 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插入。（说明：不得使用任何库函数） 6．设计一个二分检索的算法,在一组字符串中找出给定的字符串,假设所有字符串的长度为4。 （1）简述算法的主要思想； （2）用PASCAL语言分别对算法中用到的类型和变量作出说明； （3）用类PASCAL语言或自然语言写算法的非递归过程； （4）分析该算法的最大检索长度； （5）必要处加上中文注释。 7．设计一PASCAL 或C语言的函数 atoi(x).其中X 为字符串，由0--9十个数字符和表示正负数的‘-’组成，返回值为整型数值。 8．已知字符串S1中存放一段英文，写出算法format(s1,s2,s3,n),将其按给定的长度n 格式化成两端对齐的字符串S2, 其多余的字符送S3。 9．串以静态存储结构存储，结构如下所述，试实现串操作equal 算法. CONST maxlen=串被确认的最大长度 TYPE strtp=RECORD ch:ARRAY[1..maxlen] OF char; curlen:0..maxlen END; (以一维数组存放串值，并设指示器curlen 指示当前串长) 10．编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z 这26个字母和0-9这10个数字）。 11．写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。 12．已知三个字符串分别为s=’ab …abcaabcbca …a ’，s ’=’caab ’, s ’’=’bcb ’。利用所学字符串基本运算的函数得到结果串为：s ’’’=’caabcbca …aca …a ’，要求写出得到上结果串S ’’’所用的函数及执行算法。 13．S=“S1S2…Sn ”是一个长为N 的字符串，存放在一个数组中，编程序将S 改造之后输出： （1）将S 的所有第偶数个字符按照其原来的下标从大到小的次序放在S 的后半部分； （2）将S 的所有第奇数个字符按照其原来的下标从小到大的次序放在S 的前半部分； 例如： S=‘ABCDEFGHIJKL ’ 则改造后的S 为‘ACEGIKLJHFDB ’。 14．编一程序，对输入的一表达式（字符串），输出其TOKEN 表示。表达式由变量A ，B ，C ，常数（数字）0，1，…，9，运算符+，*和括号“（”，“）”组成。首先定义符号的类码： 其次定义符号的TOKEN 表示： 其中NAMEL 是变量名表（不允许有相同名），CONST 是常量表（不允许有相同数）。 变量常量+ * （ ） 例如，假设有表达式（A+A*2）+2*B*3#，则将生成如下TOKENL ： 123456A +A * 2 789101112）+*132B *3 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章作业答案
第四章 存货作业与答案