2001年度高级程序员级上午试题
●一棵查找二叉树,其结点A、B、C、D、E、F依次存放在一个起始地址为 n ( 假定地址以字节为单位顺序编号 ) 的连续区域中,每个结点占4个字节:前二个字节存放结点值,后二个字节依次放左指针、右指针。
若该查找二叉树的根结点为 E ,则它的一种可能的前序遍历为__(1)__ ,相应的层次遍历为__(2)__。在以上两种遍历情况下,结点C的左指针Lc的存放地址为__(3)__,Lc的内容为__(4)__。结点A的右指针RA的内容为__(5)__。
(1):A.EAFCBD B.EFACDB C.EABCFD D.EACBDF (2):A.EAFCBD B.EFACDB C.EABCFD D.EACBDF (3):A.n+9 B.n+10 C.n+12 D.n+13 (4):A.n+4 B.n+8 C.n+12 D.n+16 (5):A.n+4 B.n+8 C.n+12 D.n+16
●用来辅助软件开发、运行、维护、管理、支持等过程中的活动的软件称为软件开发工具,通常也称为__(6)__工具。
(6):A.CAD B.CAI C.CAM D.CASE
●使用软件开发工具有助于提高软件的开发、维护和管理的效率。集成型软件开发环境通常由工具集和环境集成机制组成。这种环境应具有__(7)__。环境集成机制主要有数据集成机制、控制集成机制和界面集成机制。
(7):A.开放性和可剪裁性 B.开放性和不可剪裁性 C.封闭性和可剪裁性 D.封闭性和不可剪裁性
●·数据集成机制为环境中的工具提供统一的__(8)__；控制集成机制为__(9)__提供支持。
界面集成机制使得环境中的所有工具具有__(10)__。
(8):A.数据类型 B.数据模式 C.数据接口规范 D.数据仓库 (9):A.使各工具具有统一的控制结构 B.备工具之间的通信、切换、调度和协同工作
C.使备工具具有统一的控制接口 D.各工具之间的同步开发 (10):A.同一个界面 B.相同的图标和图标的含义 C.统一的界丽风格相操作方式 D.相同个数的窗口和菜单项
●递归算法的执行过程,一般来说,可先后分成__(11)__和__(12)__两个阶段。
(11):A.试探 B.递推 C.枚举 D.分析 (12):A.回溯 B.回归 C.返回 D.合成
●若一个问题的求解既可以用递归算法,也可以用递推算法,则往往用__(13)__算法,因为__(14)__。 (13):A.先递归后递推 B.先递推后递归 C.递归 D.递推 (14):A.递推的效率比递归高 B.递归宜于问题分解 C.递归的效率比递推高 D.递推宜于问题分解
●贪婪法是一种__(15)__的算法。
(15):A.不求最优,只求满意 B.只求最优 C.求取全部可行解 D.求取全部最优解
●考察下列文法: G( VT ,VN ,E ,P ) 其中: VT = { + , * ,( , ) , i } VN = { E , T , F } E 是开始符号 P: E → E + T | T
T → T * F | F
F → (E)| i
F*F+T是该文法的一个句型,其中 ,__(16)__是句柄 ,__(17)__是素短语。__(18)__是该句型的直接推导,__(19)__是该句型的最左推导。__(20)__是该文法的一个句子。
(16):A.F B.F*F C.F+T D.F*F+,T (17):A.F B.F*F C.F+T D.F*F+T (18):A.F*F+i B.F*F+T*F C.F*F+F*F D.i*i+T (19):A.F*F+T*F B.F*F+T C.F*(E)+T D.(E)*F+T (20):A.T+(i+i) B.i+(i+F) C.i D.(E)
●软件开发模型用于指导软件的开发。演化模型是在快速开发一个__(21)__的基础上,逐步演化成最终的软件。
(21):A.模块 B.运行平台 C.原型 D.主程序
●螺旋模型综合了__(22)__的优点,并增加了__(23)__。
(22):A.瀑布模型和演化模型 B.瀑布模型和喷泉模型 C.演化模型和喷泉模型 D.原型和喷泉模型
(23):A.质量评价 B.进度控制 C.版本控制 D.风险分析
●喷泉模型描述的是面向__(24)__的开发过程,反映了该开发过程的__(25)__特征。
(24):A.数据流 B.数据结构 C.对象 D.构件(component) (25):A.迭代和有间隙 B.迭代和无间隙 C.无迭代和有间隙 D.无迭代和无间隙
●MIDI是一种数字音乐的国际标准,MIDI文件存储的__(26)__。它的重要特色是__(27)__。
(26):A.不是乐谱而是波形 B.不是波形而是指令序列 C.不是指令序列而是波形 D.不是指令序列而是乐谱 (27):A.占用的存储空间少 B.乐曲的失真度少 C.读写速度快 D.修改方便
●MPEG是一种__(28)__,它能够__(29)__。
(28):A.静止图像的存储标准 B.音频、视频的压缩标准 C.动态图像的传输标准 D.图形国家传输标准 (29):A.快速读写 B.有高达200:1的压缩比 C.无失真地传输视频信号 D.提供大量基本模板
●MPEG-4相对于MPEG的以前版本的最大特点是__(30)__。
(30):A.更高的压缩比 B.更多的基本图形的模板 C.更强的交互能力 D.更快的运算速度
●关系数据库设计理论主要包括三个方面内容,其中起核心作用的是__(31)__。
(31):A.范式 B.数据模式 C.数据依赖 D.范式和数据依赖
●在关系模型的完整性约束中,实体完整性规则是指关系中__(32)__。引用完整性规则要求__(33)__。
(32):A.不允许有主行 B.属性值不允许为空 C.主键值不允许为空 D.外键值不允许为空 (33):A.不允许引用不存在的元组 B.允许引用不存在的元组 C.不允许引用不存在的属性 D.允许引用不存在的属性
●设关系P和Q分别为2元和3元关系,则与关系代数表达式P的是__(30)__。
(34):A.σ1
Q)
Q等价●对于基本表 S( S#,NAME,SEX,BIRTEBAY)和 SC( S#,C#,GRADE),其中S#、NAME、SEX、BIRTHDAY、C#和GRADE分别表示学号、姓名、性别、生日、课程号和成绩。
有一SQL语句: SELECT S# NAME FROM S WHERE S# NOT IN ( SELECT S# FROM S WHERE C# = \'c102\'); 其等价的关系代数表达式是__(35)__。 (35):A.∏s#,name(σ
c#≠ \'c102\'
(SSC))
c#= \'c102\' B.∏s#,name(S)-∏s#,name (σ C.∏s#,name(S
σ
(SSC))
c# ≠ \'c102\'
(SC)) D.∏s#name(SSC)
●因争用资源产生死锁的必要条件是互斥、循环等待、不可抢占和__(36)__。对于缓冲池(大量缓冲区)的管理,采用生产者-消费者方式解决同步或互斥时,通常需要用__(37)__个信号量。
(36):A.请求与释放 B.释放与保持 C.释放与阻塞 D.保持与等待。
(37):A.1 B.2 C.3 D.4
●虚存页面调度算法有多种,__(38)__调度算法不是页面调度算法。 (38):A.后进先出 B.先进先出 C.最近最少使用 D.随机选择
●实存的存储分配算法用来决定输入的程序和数据放到主存中的位置,采用“总是把程序装入主存中最大的空闲区域”的算法称为__(39)__。
(39):A.最佳适应算法 B.最差适应算法 C.首次适应算法 D.循环首次适应算法
●在文件存储设备管理中,有三类常用的空闲块管理方法,即位图向量法,空闲块链表链接法和__(40)__。
(40):A.一级目录法 B.多级自录法 C.分区法 D.索引法
●用二进制加法器对二一十进制编码的十进制数求和,当和的本位十进制数二一十进制编码小于等于1001且向高位无进位时,__(41)__;当和小于等于100l且向高位有进位时,__(42)__;当和大于1001时,__(43)__。
(41)～(43):A.不需进行修正 B.需进行加6修正
C.需进行减6修正 D.进行加6或减6修正,需进一步判别
●微机用的系统,总线有多种,其中__(44)__是早期工业标准体系结构单总线的直接扩展,并向下与其兼容;__(45)__首先应用于奔腾机,数据线宽度已可为64位,并有数据缓冲能力。
(44)、(45):A.VESA B.SCSI C.EISA D.PCI
●被操作数的最高位移入“进位”,位,其余所有位接收其相邻低位值,最低位移入0的操作是__(46)__指令。被操作数的最高位保持不变,其余所有位接收其相邻高位值,最低位移到“进位“位中的操作是__(47)__指令。在程序执行过程中改变按程序计数器顺序读出指令的指令属于__(48)__。相对寻址方式的实际地址是__(49)__。特权指令在多用户、多任务的计算机系统中必不可少,它主要用于__(50)__。
(46)、(47):A.逻辑左移 B.算术左移 C.乘2运算 D.除2运算
(48):A.特权指令 B.传送指令 C.输入输出指令 D.转移指令
(49):A.程序计数器的内容加上指令中形式地址值 B.基值寄存器的内容加上指令中形式地址值
C.指令中形式地址中的内容 D.栈顶内容。 (50):A.检查用户的权限 B.系统硬件自检和配置 C.用户写汇编程序时调用 D.系统资源的分配和管理
●利用并行处理技术可以缩短计算机的处理时间,所谓并行性是指__(51)__。可以采用多种措施来提高计算机系统的并行性,它们可分成三类,即__(52)__。
提供专门用途的一类并行处理机(亦称阵列处理机)以__(53)__方式工作,它适用于__(54)__。多处理机是目前较高性能计算机的基本结构,它的并行任务的派生是__(55)__。
(50):A.多道程序工作 B.多用户工作
C.非单指令流单数据流方式工作 D.在同一时间完成两种或两种以上工作
(52):A.多处理机,多级存储器和互连网络 B.流水结构,高速缓存和精简指令集
C.微指令,虚拟存储和I/O通道 D.资源重复,资源共享和时间重叠。
(53):A.SISD B.SIMD C.MISD D.MB4D (54):A.事务处理 B.工业控制 C.矩阵运算 D.大量浮点计算 (55):A.需要专门的指令来表示程序中并发关系和控制并发执行 B.靠指令本身就可以启动多个处理单元并行工作 C.只执行没有并发约束关系的程序
D.先并行执行,事后再用专门程序去解决并发约束
●发展容错技术可提高计算机系统的可靠性。利用元件冗余可保证在局部有故障情况下系统的正常工作。带有热备份的系统称为__(56)__系统。它是__(57)__,因此只要有一个子系统能正常工作,整个系统仍能正常工作。
当子系统只能处于正常工作和不工作两种状态时,我们可以采用图 A 的并联模型,若单个子系统的可靠性都为0.8时,图示的三个子系统并联后的系统可靠性为__(58)__。若子系统能处于正常和不正常状态时,我们可以采用图 B 所示的表决模型,若图中有任何二个或三个子系统输出相同时,则选择该相同的输出作为系统输出,设单个子系统的可靠性为0.8时,整个系统的可靠性为__(59)__;若单个子系统的可靠性为0.5时,整个系统的可靠性为__(60)__。
[图A] [图B]
(56):A.并发 B.双工 C.双重 D.并行。
(57):A.两子系统同时同步运行,当联机子系统出错时,它退出服务,由备份系统接替
B.备份系统处于电源开机状态,一旦联机子系统出错时,立即切换到备份系统
C.两子系统交替处于工作和自检状态,当发现一子系统出错时,它不再交替到工作状态
D.两子系统并行工作,提高机器速度,一旦一个子系统出错,放弃并行工作。
(58):A.0.9 B.O.94 C.O.992 D.O.996 (59):A.0.882 B.O.896 C.O.925 D.O.94 (60):A.0.5 B.O.54 C.O.62 D.O.65
●WWW页面访问的大致过程如下:用户在浏览器中输入要访问的 WWW 页面的__(61)__地址(http://hostnane/dirctory/fi1e);浏览器通过__(62)__查询上述输入信息所指的 Web 服务器的IP 地址；浏览器通过网络与该 IP 地址处的 Web 服务器的__(63)__服务端口间建立一条__(64)__连接；浏览器依照相关协议发送__(65)__命令；Web 服务器根据命令取出文档,发送回来；浏览器释放连接,显示该文档。
(60):A.URL B.EMS C.NDS D.DNS (62):A.NAT B.EMS C.NDS D.DNS (63):A.HTML B.HTTP C.SMTP D.SNMP (64):A.RTP B.IP C.TCP D.UDP (65):A.TCP B.GET C.UDP D.PUT
●MIMD systems can be claified into __(66)__-oriented systems ,high-avai1ability systems and response-oriented systems.The goal of __(66)__ .orlented multiproce is to obtain h1gh __(66)__ __(67)__ minimal computing cost .The techniques employed by multiproceor operating systems to achieve this goal take advantage of an inherent proceing versus input/output balance in the workload to produce __(68)__ and__(69)__ loading of system __(70)__ . (66):A.though B.through C.throughout D.throughput (67):A.at B.of C.on D.to (68):A.balance B.balanced C.balances D.balancing (69):A.uniform B.unique C.unit D.united (70):A resource B.resources C.source D.sources ●Soon,more of the informtion we receive via the internet could come __(71)__ in digital wrappers.Wrappers sre made up __(72)__ software code that\'s targeted to do specific things with the data __(73)__ within them , such as helping to define queries for search engines .They also keep __(74)__ from __(75)__ acce to that code. (71):A.package B.packaged C.packages D.packaging (72):A.of B.off C.on D.out (73):A.close B.closed C.enclose D.enclosed (74):A.insiders B.money C.outsiders D.warehouse (75):A.gain B.gained C.gains D.gaining
2001年度高级程序员级下午试题
试题一
阅读下列说明和流程图,回答问题1至问题3,把解答填入答题纸的对应栏内。 [说明] 某计算机厂生产多种型号的计算机,通过分布在世界各地的销售点销售,销售点应在收到计算机商品后的规定时间内把货款汇给该计算机厂。
流程图 1 描述了该厂发货、收款、催款的处理过程。其中商品文件、销售点文件、发货文件和收款文件的记录格式如下: 商品文件 = 商品代号 + 计算机规格名称 + 单价
销售点文件 = 销售点代号 + 销售点名称 + 地址
发货文件 = 发货单号 + 发出日期 + 销售点代号 + 商品代号 + 数量 + 金额
收款文件 = 收款单号 + 收款日期 + 销售点代号 + 商品代号 + 数量 + 金额 + 发货单号
在流程图中,处理 1～处理 3 把当天的发货单合并到发货文件。处理 4～处理 6 把当天的收款单合并到收款文件。每天在处理 3 和处理 5 完成之后,由处理 7 在发货文件中当天已收款的记录上加上已收款标记。处理 8 在月末执行一次,它有三个功能: ①汇总输出本月发货清单; ②删除发货文件中已收款的所有记录,形成一个新的发货文件,作为下月初处理时的初始文件
③产生催款通知单,以便对那些一个月以前已发货但至今仍未收到货款的销售点催款。
[问题1] 指出流程图 l 中应在哪几个处理框中检查发货单和收款单的错误，并分别说明它们各能指出什么错误。
[问题2] 如果把流程图 1 中从日收款分类文件到处理 7 的连线改成从日收款文件到处理 7 的连线,则有什么缺点,理由是什么? [问题3] 处理 9 每月末执行一次如流程图所示，利用收款文件产生月收款报告并更新收款文件。要求指出它对收款文件做什么更新操作。
试题二
阅读下列说明和流程图,回答问题 1 至问题 3 ,把解答填入答题纸的对应栏内。
[说明] 某考务处理系统具有以下功能: 1.输入报名单; 2.自动编制准考证号; 3.输出准考证; 4.输入成绩清单; 5.输出成绩通知单; 6.输出成绩分布表; 7.输入合格标准、输出录取通知单; 8.试题难度分析,并输出试题难度分析表。
这里给出了实现上述要求的部分不完整的数据流图,其中部分数据流的组成如下所示: 报名单 = 报名号 + 姓名 + 通信地址
考生名册 = 报名号 + 准考证号 + 姓名 + 通信地址
成绩册 = 准考证号 + { 课程号 + 成绩 } (其中{W}表示W重复多次) 准考证 = 报名号 + 姓名 + 准考证号 [问题1] 指出 0 层图中可以删去的部分。 [问题2] 在加工 1 子图中将遗漏的数据流添加在答题纸上。 [问题3] 加工 2 子图分解成如图所示的 4 个子加工及相关的文件(即数据存储)。试在此基础上将相关的DFD 成份添加在答题纸上,以完全该加工子图。
[数据流图] 顶层
试题三
在COMET型计算机上可以使用试卷上所附的 CASL 汇编语言。阅读程序说明和 CASL 程序,将应填入__(n)__处的字句,写在答题纸的对应栏内。
[程序3说明] 子程序 DEHZ 用来对 HZ 编码的字串做解码处理。
HZ 编码是海外华人创造的一种将含有高位为 1 的汉字双字节字串转换成易于在网络中传输的ASCII 字符串的变换方式。编码过程中,被转换字符串中的原汉字子字符串各字节高位作清零处理,使之成为 ASCII 子字符串,并在其前后两端分别添加 ~{ 和 ~} 作为标记；而对于原 ASCII 子字符串,则将其中的 ~ 改写为 ~~,其余字符不变。
DEHZ 解码子程序则是 HZ 编码的复原过程。复原 ASCII 子字符串过程中遇有 ~~ 字符则改写为一个 ~ ,遇有 ~{ 则将其后直至 ~} 标记前的各字节高位置1,复原为汉字子字符串,同时删除其前后标记。~的后续字符不属于以上情况均作为错误处理。
调用该子程序时, GR1 存放原始字符串首地址, GR2 存放还原后的目标字符串首地址。工作寄存器 GR3 用作处理汉字子字符串的识别标志,进入子程序时应初始化为处理 ASCII 子字符串。程序按照 CASL 语言的标准约定,字符串的每个字符只占用一个存储字的低八位。原始字符串和目标字符串均以 0 作为结束标志。
[程序3] START DEHZ PUSH 0,GR3 PUSH 0,GR2 PUSH 0,GR1 LEA GR3,0 LOOP __(1)__ CPA GR0,MARK0 JNZ GOON LEA GR1,1,GR1 LD GR0,0,GR1 CPA GR0,MARK0 __(2)__ CPA GR0,MARK1,GR3 JNZ ERROR __(3)__ LEA GR1,1,GR1 JMP LOOP ERROR OUT ERS1R,ERLEN JMP EXIT GOON __(4)__ ST GR0,0,GR2 LEA GR2,1,GR2 LEA GR1,1,GR1 CPA GR0,VO __(5)__ EXIT P0P GR1 P0P GR2 P0P GR3 RET V1 DC 1 V0 DC O DC #0080 MARK0 DC \'~ \' MARK1 DC \'{ }\' ERSTR DC \'ERROR!\' ERLEN DC 6 END 试题四
阅读下列程序说明和C代码,将应填入__(n)__处的字句写在答题纸的对应栏内。
[程序4说明] 设 M 叉树采用列表法表示,即每棵子树对应一个列表,列表的结构为:子树根结点的值部分 (设为一个字符) 和用“( )”,括起来的各子树的列表 (如有子树的话) ,各子列表间用“,”,分隔。例如下面的三叉树可用列表 a( b( c,d ),e,f( g,h,i ))表示。
本程序输入列表,生成一棵 M 叉树,并由 M 叉树输出列表。假定输入无错误。
[程序4] #include〈stdio.h〉 #include〈stdlib.h〉 #define M 3 typedef struct node{ char val; struct node *subTree[M]; } NODE; char buf[255] ,*str = buf NODE *d = NULL NODE *mackTree( ) /*由列表生成M叉树*/ { int k; NODE *s ; s = __(1)__ s -> val = *str++ ; for ( k = 0 ; k subTree[k] = NULL ; if(*str=\'( \'){ k = 0; do { str++; s -> subTree[k] = __(2)__ ; if ( *str == \')\' ) { str++; break ; } k = k+l ; } while ( __(3)__ ); } return s ; } void walkTree( NODE *t ) /*由 M 叉树输出列表*/ { int i ; if t != NULL ) { __(4)__ if ( t -> subTree[0] == NULL ) return ; putchar ( \'( \' ) ; for ( i = 0 ; i subTree[i+l] != NULL ) putchar ( \', \' ) ; } putchar ( \') \' ) ; } }
void main( ) { printf( \"Enter exp:\" ) ; scanf( \"%S\" , str ) ; d = makeTree() ; walkTree( d ) ; putchar( \'\\n\') ; }
试题五
阅读下列程序说明和C代码,将应填入__(n)__处的字句写在答题纸的对应栏内。
[程序5说明] 著名的四色定理指出任何平面区域图均可用四种颜色着色,使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过四种颜色的着色方案。程序中用 1～4 表示四种颜色。要着色的 N 个区域用 0～N一1编号,区域相邻关系用 adj[][] 矩阵表示,矩阵的 i 行 j 列的元素为 1 ,表示区域 i 与区域 j 相邻；矩阵的 i 行 j 列的元素为 0 ,表示区域 i 与区域 j 不相邻。数组 color[] 用来存储着色结果, color[i] 的值为区域 i 所着颜色。
【程序5】
#include〈stdio.h〉 #define N 10 void output(int color[])/*输出一种着色方案*/ { int i ; for ( i = 0 ; i
/*为区域i选一种可着的颜色*/ int select( int i ,int c ,int adj[][N] , int color[ ] ) { int k ; for ( k = c ; k
2001年度高级程序员级答案
上午答案
(1)D (6)D (ll)B (16)A (21)C (26)B (31)C (36)D (41)A (46)A (51)D (56)C (61)A (66)D (71)B
(2)A (7)A (12)B (17)B (22)A (27)A (32)C (37)C (42)B (47)D (52)D (57)A (62)D (67)A (72)A
(3)B (8)C (13)D (18)B (23)D (28)B (33)A (38)A (43)B (48)D (53)B (58)C (63)B (68)B (73)D
(4)A (9)B (14)A (19)D (24)C (29)B (34)B (39)B (44)C (49)A (54)C (59)B (64)C (69)A (74)C
(5)B (10)C (15)A (20)C (25)B (30)C (35)B (40)D (45)D (50)D (55)A (60)A (65)B (70)B (75)D
下午答案 试题一
[问题1) 处理l和处理4：发货单和受款单中的非法销售代号、商品代号；
数量和金额非正整；单位I*数量，i金额；输入中的非法字符； 处理7：重复付款和找不到与收款单位相对应发货单； [问题2] 因文件分类，处理时要增加访问外存的时间或需大量内存，从而降低了处理速度 [问题3] 删除收款文件中的所有记录 试题二
[问题1]成绩文件可删 试题二
(1) LD GR0,0GR1 (2) JZE GOON (3) EOR GR3,V1 (4) OR GR0,V0, GR3 (5) JNZ LOOP 试题四
(1) (NODE*) malloc (sizeof (NODE)) (2) makeTree ( ) (3) *str == \',\' (4) putchar (t->val) (5) walkTree (t->subTree[i]) 试题五
(1) color[*ip] (2) adj[i][j] != 0 && color[j] == c (3) i,k,adj,color (4) select (i,c+l,adj,color) (5) color[i]=c
