北京师范大学 2002年招收攻读硕士学位研究生入学考试试题 专业:情报学、图书馆学 科目代码:574 研究方向:信息管理技术与信息系统、考试科目:计算机综合 图书馆技术方法 (所有题目的答案均写在答题纸上) 给出以下名词的中文含义(若为英文缩写请给出英文全称),并 作简单解释(20分) 1. ADT 2.B→tree 3. Relational model 4. CASE 5.3NF 简要回答(本题共6小题,每小题5分,共30分) .什么是软件开发的原型方法?原型法开发包括哪几个阶段 各阶段的工作是什么? 树结构有哪些存储表示方法?请用算法描述语言给出其结构 的定义。 3.以下程序段的时间复杂度是多少。 while(i<=n 4.以下为字符串匹配算法,即返回子串T在主串S中第pos个 字符之后的位置,若不存在,则函数值为0。请在程序中的空格处 填写适当的语句。 int Index(char *S, char * T, int pos)( pos while( i <= length(S) < length (T))i if( s[i] = T[j] else return i- length(T) else return 0: 5.已知一棵二叉树中序遍历结果是 DCBGEAHFIJK,后序遍历结果 是 DCEGBFHKJIA,请画出此二叉树。 6.软件设计的任务是什么?软件设计应遵循哪些基本原则 第1页共2页
三、请用算法描述语言写出二分法查找折半查找)的算法(10分) 四、请回答以下问题(本题共2小题,每小题10分,共20分) 1.在数据库系统中,利用日志进行数据库恢复有哪些方法,请 简要说明其恢复过程。 2.银行数据库系统中存在一个转帐事务,用来完成帐户1和帐 户2两个帐户之间的转帐,它由下面的操作组成 (1)加钱到帐户2; (2)测试帐户1是否有足够的钱,如果没有足够的钱,则将加到帐 户2的钱去掉然后 ROLLBACK;如果有足够的钱,从帐户1中减去 相应的钱然后 COMMIT 该事务由程序P来执行 假设存在三个帐户: 帐户余额 1000 3000 事务T1执行P,完成A1到A2的转帐,转帐金额为1500;事务T2 在大致相同的时间执行P,完成A2到A3的转帐,转帐金额为2500 请问在以上过程中存在什么问题,为什么会有该问题,如何解决? 五、现需设计一情报检索系统,要求能进行关键词的检索和相应 的逻辑运算。要求当用户从键盘输入关键词后,系统能立即给出所 命中的文献篇数和文献编号,系统最多能记忆用户所检索的10个 关键词及命中结果,并对其中的任两个进行逻辑与、或、非的运算, 运算对象和运算类型由用户通过键盘指令指定,如指令“12”是 用户对第一次和第二次检索关键词的结果进行逻辑非运算,若第 次命中的文献编号为3、4、5、6,第二次命中的文献编号为5、6、 7、8,则1-2的结果是3、4。请根据以上要求写出实现检索和逻辑 运算功能所需的数据结构,并写出进行“逻辑非”运算的程序。(2 分) 第2页共2页