一、单项选择题, 共十五小题，每小题2分，全题总分为30分

Size: px

Start display at page:

Download "一、单项选择题, 共十五小题，每小题2分，全题总分为30分"

歪前江
7 years ago
Views:

810 华南理工大学 2011 年攻读硕士学位研究生入学考试试卷 ( 请在答题纸上做答, 试卷上做答无效, 试后本卷必须与答题纸一同交回 ) 科目名称 : 物流信息基础 ( 含数据库数据结构 ) 适用专业 : 物流工程与管理, 物流工程 ( 专业学位 ) 本卷满分 :150 分共 8 页说明 : 本卷分为数据库和数据结构共两部分内容, 全卷满分 150 分, 其中数据库部分满分 75

1 810 华南理工大学 2011 年攻读硕士学位研究生入学考试试卷 ( 请在答题纸上做答, 试卷上做答无效, 试后本卷必须与答题纸一同交回 ) 科目名称 : 物流信息基础 ( 含数据库数据结构 ) 适用专业 : 物流工程与管理, 物流工程 ( 专业学位 ) 本卷满分 :150 分共 8 页说明 : 本卷分为数据库和数据结构共两部分内容, 全卷满分 150 分, 其中数据库部分满分 75 分, 数据结构满分 75 分一. 选择题 ( 每题 2 分, 共 24 分 ) 一. 数据库部分 1. 在 E-R 概念模型中, 一个学生是实体, 学生实体可由学号姓名性别等属性组成, 那么性别的取值范围是实体的 ( ) A. 主码 B. 属性 C. 联系 D. 域 2. 关系数据库用下列哪项来表示实体之间的联系?( ) A. 树结构 B. 网结构 C. 二维表 D. 线性表 3. 物理结构的改变不影响逻辑结构的性质, 称为数据库的 ( ) A. 物理数据独立性 B. 物理结构独立性 C. 逻辑数据独立性 D. 逻辑结构独立性 4. 在基本的关系中, 下列说法正确的是 ( ) A. 行列顺序有关 B. 属性名允许重名 C. 任意两个元组不允许完全相同 D. 列是非同质的 5. 若两个实体之间的联系是 1:m, 则实现 1:m 联系的方法是 ( ) A. 在 m 端实体转换的关系中加入 1 端实体转换关系的码 B. 将 m 端实体转换关系的码加入到 1 端的关系中 C. 在两个实体转换的关系中, 分别加入另一个关系的码 D. 将两个实体转换成一个关系 6. 如果采用关系数据库来实现应用, 在数据库设计的 ( ) 阶段将关系模式进行规范化处理 A. 需求分析 B. 概念设计 C. 逻辑设计 D. 物理设计 7. 数据库系统中, 用户使用的数据视图属于 ( ) A. 外模式 B. 存储模式 C. 内模式 D. 概念模式 8. 如果事务 T 获得了数据项 X 上的排它锁, 则 T( ) 第 1 页

2 A. 可以读 X, 不能写 X B. 可以读 X, 也可以写 X C. 不能读 X, 可以写 X D. 不能读 X, 也不能写 X 9.DBMS 提供授权功能控制不同用户访问数据的权限, 主要目的是为了实现数据库的 ( ) A. 一致性 B. 完整性 C. 安全性 D. 可靠性 10. 在 SQL 语言中, 与 X BETWEEN 10 AND 20 等价的表达式是 ( ) A.X>10 AND X<20 B.X>=10 AND X<20 C.X>10 AND X<=20 D.X>=10 AND X<= 从一个数据库文件中取出满足某个条件的所有记录的操作是 ( ) A. 选择 B. 连接 C. 投影 D. 复制 12. 设关系模式 R(A,B,C) 上有函数依赖 A->B, 则把 R 分解为 R1(A,B) 和 R2(A,C) 属于 () A. 无损分解 B. 有损分解 C. 不确定, 但与 R 的最高范数有关 D. 不确定, 但与 R 的最高范数无关二. 填空题 ( 每空 3 分, 共 15 分 ) 1. 在 SQL SELECT 语句查询中, 要去掉查询结果中的重复记录, 应该使用关键字 2. 设有关系模式 S(A,B,C,D), 则与等价的 SQL 语句 select A, C from S 等价的关系代数表达式是 : 3. 事务必须具有的四个性质是 : 原子性一致性和持久性 4. 视图是从一个或多个基本表导出的虚表, 在数据库中只存储有关视图的 5. 数据库恢复操作的依据是后备副本和三. 问答题 ( 第 1 题 7 分, 第 2 题第 1 小题 6 分, 第 2 小题 8 分, 共 21 分 ) 1. 现有一个事务集 {T1,T2,T3}, 其中这四个事务在运行过程中需要读写 X Y 和 Z 设 Ti 对 X 的读操作记作 TiR(X),Ti 对 X 的写操作记作 TiW(X) 事务对 XYZ 的访问情况如下 : T1:T1R(x) T2:T2R(Y),T2W(X) T3:T3W(Y),T3W(X),T3W(Z) 现知各事务之间的依赖关系如下 : 第 2 页

3 T2 T1 T3 请问调度 T3W(Y), T2R(Y),T3W(X),T2W(X), TIR(X),T3W(Z) 是否正确? 若正确请说明理由, 若否请举出反例 2. 已知有关系 R S T 如下 ( 各表第一行为字段名 ): R RX RY a1 b1 a2 b2 a3 b3 S SX SY a1 b2 a2 b3 a3 b1 T TX TY b1 c1 b2 c2 b3 c3 (1) 请顺次写出以下关系运算的结果 : 1 R S 2 R-S 3 σ TY!='c2' or TY!= c3 (S T) (2) 请根据以下结果, 写出相应的 SQL 语句 ( 请注意以下不允许使用重命名操作 ): 1 RX TX TY a1 b1 c1 a2 b2 c2 a3 b3 c3 第 3 页

4 2 RX SY a1 b1 a2 b2 a3 b3 四. 设计题, 共 15 分假设某旅馆业务规定, 每张账单对应一个顾客, 账单的发票号是惟一的, 账单包含一个顾客姓名到达日期和顾客每日的消费项目汇总 ( 同一顾客的同一消费项目每天只作一次汇总 ) 它的一个具体的实例如下图所示: 发票号到达日期顾客姓名消费日期项目金额 /12/10 顾全德 2005/12/10 房租 /12/10 顾全德 2005/12/10 餐费 /12/10 顾全德 2005/12/10 电话费 /12/10 顾全德 2005/12/11 餐费如果根据上述业务规则, 设计一个关系模式 : R( 发票号, 到达日期, 顾客姓名, 消费日期, 项目, 金额 ) 请回答下列问题 : (1) 列出 R 的所有候选键 (5 分 ) (2)R 最高可达到第几范式? 请说明理由 (5 分 ) (3) 给出 R 的一个可能的 3NF 分解 (5 分 ) 二. 数据结构部分一. 单项选择题 ( 每题 2 分, 共 24 分 ) 1. 在数据结构中, 从逻辑上可以把数据结构分成 ( ) A. 线性结构和非线性结构 B. 紧凑结构和非紧凑结构 C. 动态结构和静态结构 D. 内部结构和外部结构 2.for(i=0;i<m;i++) for(j=0;j<n;j++) A[i][ j]=i*j; 上面算法的时间复杂度为 ( ) A.O(m 2 ) B.O(n 2 ) C.O(m n) D.O(m+n) 3. 设顺序表有 9 个元素, 则在第 3 个元素前插入一个元素所需移动元素的个数为第 4 页

5 ( ) A.5 B.6 C.7 D.9 4. 设有一个栈, 按 A B C D 的顺序进栈, 则可能为出栈序列的是 ( ) A. DCBA B.CDAB C. DBAC D.DCAB 5. 下列说法正确的是 ( ) A. 线性表的逻辑顺序与存储顺序总是一致的 B. 线性表的链式存储结构中, 要求内存中可用的存储单元可以是连续的, 也可以不连续 C. 线性表的顺序存储结构优于链式存储结构 D. 每种数据结构都具有插入删除和查找三种基本运算 6. 将一棵有 50 个结点的完全二叉树按层编号, 则对编号为 25 的结点 x, 该结点 ( ) A. 无左右孩子 B. 有左孩子, 无右孩子 C. 有右孩子, 无左孩子 D. 有左右孩子 7. 如果从无向图的任一顶点出发均可使用宽度搜索算法访问所有顶点, 则该图一定是 ( ) A. 完全图 B. 连通图 C. 有回路 D. 一棵树 8. 用快速排序方法对包含有 n 个关键字的序列进行排序, 最坏情况下执行的时间复杂度为 ( ) A.O(n) B.O(log 2 n) C.O(nlog 2 n) D.O(n 2 ) 9. 对于只在表的首尾两端进行插入操作的线性表, 宜采用的存储结构为 ( ) A. 顺序表 B. 用头指针表示的单循环链表 C. 用尾指针表示的单循环链表 D. 单链表 10. 已知一个有向图如下所示, 则从顶点 a 出发进行深度优先偏历, 不可能得到的 DFS 序列为 ( ) A. a d b e f c B.a d c e f b C. a d c b f e D.a d e f c b 第 5 页

6 11. 设循环队列中数组的下标范围是 1~n, 其头尾指针分别为 f 和 r, 则其元素个数为 ( ) A. r-f B. r-f+1 C. ((r-f) mod n) +1 D. (r-f+n) mod n 12. 在有 n 个结点的二叉链表中, 值为非空的链域的个数为 ( ) A. n-1 B. 2n-1 C. n+1 D. 2n+1 二. 填空题 ( 每空 2 分, 共 10 分 ) 1. 在对一组关键字为 (54,38,96,23,15,72,60,45,83) 的记录采用直接选择排序法进行排序时, 整个排序过程总共需进行次比较 2. 对于堆排序和快速排序这两种算法, 在待排序数据的情况下, 选用堆排序算法较为合适 3. 若一个算法中的语句频度之和为 T(n)=3720n+4nlogn-2105, 则算法的时间复杂度为 4. 在有 n 个结点的无向图中, 其边数最多为 5. 结点数为 100 的二叉树可能达到的最大高度为 ( 叶节点的高度计为 0) 三. 问答题 (1 2 题每题各 5 分,3 4 题每题各 8 分, 共 26 分 ) 1. 设顺序表的表长为 n, 且查找每个元素的概率相等, 则采用顺序查找法查找表中任一元素, 在查找成功时的平均查找长度为多少? 请写出计算过程 2. 现有某二叉树, 按前序遍历的序列为 ABDEFCGH, 按中序遍历的序列为 DEFBGHCA, 试画出此二叉树 3. 请根据 Kruskal 算法画出下图的一棵最小生成树, 要求要有详细的过程 4. 下面程序段为删除循环链表中第一个 data 域值等于某正整数 x 的结点, 若删除成功则返回 x, 否则返回 0 请填上程序中缺少的部分循环链表的结构如下图所示( 假设循环链表的入口为节点 head, 当链表为空时,head 的 next 指针指向自身 ): 第 6 页

7 class node{ int data; node next; } int Delete (node head, int x) { node p, q; p=_(1) ; q=_(2) ; while ( (3) ) { } p=p.next; q=q.next; if ( (4) ) return 0; q.next=p.next; return (x); } 四. 程序设计题 ( 第一小题 9 分, 第二小题 6 分, 共 15 分 ) 已知自顶向下的二路归并排序的算法的基本思想是 : 对于待排序数组 A, 可以递归的把 A 划分为前后两部分, 对这两部分排序完成后, 再合并为一个有序数组请根据以上描述, 回答以下问题 : 1. 请编写 Merge 函数, 函数原型为 boolean Merge(int A[],int low, int mid, int high) 要求实现的功能为 : 已知 A[] 中从 A[low]~A[mid],A[mid+1]~A[high] 分别递增有序, 要求函数调用完毕后 A[low]~A[high] 递增有序 2. 请在以下程序段中填上合适的语句, 完成自顶向下的二路归并排序的算法 : void MergeSortDC(int A[], int low, int high) { int mid; 第 7 页

8 if ( ){ mid=(low+high)/2; ; ; Merge(R, low, mid, high); } } 第 8 页

一、单项选择题, 共十五小题，每小题2分，全题总分为30分

一、单项选择题, 共十五小题，每小题2分，全题总分为30分 810 华南理工大学 2010 年攻读硕士学位研究生入学考试试卷 ( 请在答题纸上做答, 试卷上做答无效, 试后本卷必须与答题纸一同交回 ) 科目名称 : 物流信息基础 ( 含数据库数据结构 ) 适用专业 : 物流工程与管理, 物流工程共 6 页说明 : 本卷分为数据库和数据结构共两部分内容, 全卷满分 150 分, 其中数据库部分满分 75 分, 数据结构满分 75 分一. 数据库部分一. 单项选择题,