软件水平考试（中级）软件设计师上午（基础知识）试题模拟试卷11

(42)

(40)

(41)

The　Turing　machine　is　an　abstract(71)of　computer　execution　and　storage　introduced　in　1936　by　Alan　Turing　to　give　a　mathematically　precise　definition　of(72).　or　'mechanical　procedure'.　As　such　it　is　still　widely　used　in　theoretical　computer　science,　especially　in(73)theory　and　the　theory　of　computation.　The　thesis　that　states　that　Turing　machines　indeed　capture　the　informal　notion　of　effective　or　mechanical　method　in　logic　and　mathematics　is　known　as　Turing's　thesis.

Every　Turing　machine　computes　a　certain(74)partial　function　over　the　strings　over　its　alphabet.　In　that　sense　it　behaves　like　a　computer　with　a　fixed　program.　However,　as　Alan　luring　already　described,　we　can　encode　the　action　table　of　every　Turing　machine　in　a　string.　Thus　we　might　try　to　construct　a　Turing　machine　that　expects　on　its　tape　a　string　describing　an　action　table　followed　by　a　string　describing　the　input　tape,　and　then　computes　the　tape　that　the　encoded　Turing　machine　would　have　computed.　As　Turing　showed,　such　a　luring　machine　is　indeed　possible　and　since　it　is　able　to　simulate　any　other　Turing　machine　it　is　called　a(75)Turing　machine.

(39)

(35)

(36)

(37)

The　notion　of　NP-completeness　has　provided　a(66)mathematical　definition　for(67)intractability　of　NP　problems.　But　this　measure　applies　only　to　worst-case　complexity.　Being　NP-complete　does　not(68)that　a　problem　is　intractable　on　the　average　case.　Indeed,　some　NP-complete　problems　are　"(69)on　average",　though　some　may　not　be.　Levin　initiated　the　study　of　average-case　intractability,　He　showed　that　a　bounded　tiling　problem　under　a　simple　distribution　is　average-case　NP-complete.　Since　then,　several　additional　average-case　NP-complete　problems　have　been　shown　within　Levin's(70).　This　paper　is　intended　to　provide　a　comprehensive　survey　of　average-case　NP-complete　problems　that　have　been　published　so　far,　and　the　techniques　of　obtaining　these　results.

(34)

(32)

(31)

(30)

(28)

(29)

(26)

按照规范的设计方法，一个完整的数据库设计一般分为以下6个阶段：(51)：分析用户的需求，包括数据、功能和性能需求。

(52)：主要采用E—R模型进行设计，包括画E—R图。

(53)：通过将E—R图转换成表，实现从E—R模型到关系模型的转换。

(54)：主要是为所设计的数据库选择合适的存储结构和存取路径。

(55)：包括编程、测试和试运行。

(56)：系统的运行与数据库的日常维护。

(24)

(25)

(23)

(21)

一棵深度为1的满k叉树有如下性质：第1层上的结点都是叶子结点，其余各层上每个结点都有　k棵非空子树，如果按层次顺序从1开始对全部结点编号，则各层的结点数目是(42)；编号为　n的双亲结点(若存在)的编号是(43)；编号为n的结点的第i个孩子结点(若存在)的编号是(44)；编号为n的结点有右兄弟的条件是(45)，其右兄弟的编号是(46)。

(19)

在微型计算机中，下列设备属于输出设备的是(52)。下列设备属于输入设备的是(53)。

(17)

考虑一个具有等距间隔的站点的基带总线LAN，数据输率为10Mbps；总线长度为1000m，传播速度为200m/μs，发送一个1000bit的帧给另一个站，从发送开始到接收结束的平均时间是(49)；如果两个站严格地在同一时刻开始发送，它们的帧将会彼此干扰，如果每个发送站在发送期间监听总线，(50)可发现干扰。

某趾M芯片，其存储容量为16K×8位，则该芯片引出线的最小数目应为(3)。存储器芯片的地址范围是(4)。

(15)

某机主存的读写周期为1μs，今采用增设Cache　方案和多体交叉存取方案来使其有效访问周期减少到0.2μs，设Cache的命中率为90%，则Cache的读写周期应为(42)才能满足要求。设在多体交叉存取访问时，产生存储体访问冲突的概率为10%，则应由(43)存储体并行工作才能满足要求。

软件是一种逻辑产品，它的开发主要是(1)。软件工程和计算机科学性质不同，软件工程着重于(2)。

(13)

面向对象分析阶段建立的三个模型中，核心的模型是(62)。

优化可生成(62)的目标代码。

设有以下程序段　　　　int　x=0，s=0；　　　　while(!x!=0)s+=++x；　　　　printf(“%d”，s)；　　　　则(50)。

以文档作为驱动，适合于软件需求很明确的软件项目的生存周期模型是(49)。

下列程序段执行后s值为：(38)int　i=1,　s=0;　　　　do　{　if(!(i%2))continue;　s+　=i;　}　while(+　+i＜10);

要使下表中描述的状态安全，可用资源的最小数目应为(32)。

线性表采用链式存储时，其地址(31)。

基本块内的优化为(25)。

若项目集IK含有A→α.，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α.”动作的一定是(19)。

在下列存储器中，访问速度最快的是(24)。

在计算机系统中，表征系统运行状态的部件是()。