线第页共页第页共页

《线第页共页第页共页》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、石家庄学院考试命题专用纸（计05本）2005－2006学年第1学期__计算机科学与技术方法论__课程试题（A卷）一二三四五六七八九十总分一、名词解释。（每题2分，共6分）1．效率：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　2．算法：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　.3．定性模型：　　　　　　　　　　　　　二、填空题。（每空1分，共20分）1．在统一对学科的认识之后，ACM和IEEE/CS联合小组将计算机科学、计算机工程、计算机科学和工程、计算机信息学以及其它类似名称的专业及其研究范畴统称为。2．乔姆斯

2、基把人所具有的创造和理解正确句子的能力称为语言的“创造性”（Creativity）。而语言“创造性”过程的本质，其实就是由有限数量的词根据一定的规则产生正确句子的过程，进一步而言，其实质也就是一个字符串到的变换过程。3．计算机器之父：　　　　　图论和拓扑学之父：　　　　　。4．算法重要特性：　　　　　　、确定性、输入、输出、　　　　　　　　5．　　　　　　　是系统科学的基本方法。6．算法与算法复杂性领域中有代表性典型问题有　　　　　　　　、　　　　等。7．等价关系要满足三个条件　　　　　、　　　　　、　　　　　　。8．计算机语言是一种　　　　　　　

3、　语言。9．ENIAC是　　　　（国家）宾夕法尼亚大学于　　　　　　（时间）研制成功的是世界第一台多功能、全电子数字计算机。10.尽管计算学科已成为一个极为宽广的学科，但其根本问题仍然是：　　　。甚至还可以更为直率地说，学科所有分支领域的根本任务就是进行计算，其实质就是　　　　的变换。11.模型与实现包括建模、验证、实现。其中，______主要属于学科抽象形态方面的内容，验证主要属于学科理论形态方面的内容，_____则主要属于学科设计形态方面的内容。12.计算机科学与技术方法论是对计算领域认识和实践过程中一般方法及其的学问。三、判断题。（每题.2分

4、，共20分）1．《计算机科学与技术方法论》课程要求本科一年级学生对教材的内容完全掌握。（）2．西尔勒的“中文屋子”从功能的角度来判定机器能否思维，标志着现代机器思维问题讨论的开始。（）3．梵天塔问题中，需要移动的盘子次数为h(n)=2n-1，则该问题的算法时间复杂度表示为O(2n)。（）4．各国对并行计算机系统的研制非常重视，由此，我们可以断定发展并行计算技术就是提高计算机系统性能的根本性出路。（）5．根据图灵的观点可以得到这样的结论：凡是能用算法方法解决的问题，也一定能用图灵机所解决；反之则不一定，即图灵机解决不了的问题，而算法却有可能解决。（）

5、6．由阿达尔定律的定量形式可知，如果某一计算中所含的必须串行执行的操作占10%，那么，不管一台并行计算机系统中有多少个处理器，其最大可能的加速只能是10。（）7．外存上的信息读入内存之后才能被控制器和运算器运用。()8．二叉树是n（n>=0）个结点组成的有限集合，它或者是空集，或者由一个结点及两棵互不相交的子树组成，且这两个子树有左、右之分，其次序不能任意颠倒。()9．虚拟机可分为固件虚拟机、操作系统虚拟机、汇编语言虚拟机、高级语言虚拟机和应用语言虚拟机。()10．流程图是介于自然语言与计算机语言之间、用文字和符号来描述算法的工具。（　　）四、计算

6、题。（前3题每题各5分，第4题8分，共23分）(请写出计算步骤)专业班级姓名学号线第页共页第页共页封密系别第1页共3页五、算法题。（每题5分，共15分）1．用系统的观点对正整数进行划分，并建立相应的数学模型。2．请用自然语言叙述　S=1＋2+3……＋100　算法。3　3．现有一个具体的形式语法,其中：V　　　Vn为非终结符号的有限集合；Vt为终结符号的有限集合；Po为生成式(或称产生式)的有限集合，即形式规则；S为开始符号。　　该形式语法的定义为：V　　　Vn={S,NP,VP,N,V}Vt={我，他，学，教，英语，汉语，希

7、望}Po={S→NPVP,NP→N,VP→VNP,VP→VS,N→我,N→他,V→学,V→教,V→希望,N→英语,N→汉语}。其中：(1)S表示句子(2)NP表示名词短语(3)VP表示动词谓语(4)N表示名词(5)V表示动词(6)S→NPVP表示：句子由名词和动词短语组成；(7)NP→N表示：名词短语由名词构成。其他转换规则依此类推。请按照以上语法规则给出下列句子的派生过程：1．在图灵的带子机中，设b表示空格，q1表示机器的初始状态，q4表示机器的结束状态，如果带子上的输入信息是11100101，读入头位对准最右边第一个为1的方格，状态为初始状态q

8、1。执行以下命令后，请写出计算结果。q100Lq2q110Lq3q1bbNq4q200Lq2q210Lq2q2bbNq4q