11年福建省专升本数字媒体艺术试卷(3)

10. 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（C ）。

a) n b) (n-1)*(n-1) c) n-1 d) n2

11. 在一个具有n个顶点的有向完全途中，所含有的边数是（ A ）。 a) n b) n*(n-1) c) n(n-1)/2 d) n(n+1)/2

12. 含有n个顶点e条边得无向连通图，利用Prim算法生成的最小生成树其时间复杂度为（ C ）。

a) O(e*n) b) O(elog2e) c) O(n2) d) O(nlog2n) 二． 填空题（本大题共7小题，每空2分，共16分）

13. 在数据结构中，从逻辑上可以把数据结构分成 线性结构 和 非线性结构 。

14. 从栈顶指针为top的链栈中删除一个结点，并将被删除结点的值保存在x中，其操作步骤为 x=top->data top=top->next 。

15. 对n个元素进行冒泡排序时，最少比较次数是 n-1 。

16. 在一棵具有10个叶子结点的二叉树中，度为2的结点个数为 9 个。 17. 对一棵二叉搜索树进行 中序 遍历，可得到一个关键字递增有序序列。

18. 已知有向图的邻接矩阵，要计算第i号顶点的出度，计算方法是将 第i个 元素累加。

19. 用深度优先搜索策略来遍历一个图类似于树的 先序 遍历。 三、应用题（本大题共4小题，每小题10分，共40分）

20. 对于图1所示的树：画出其转换成相应的二叉树树型。写出相应二叉树的中序遍历。

21. 已知关键字序列（25,89,12,34,76,45,9,56），采用直接插入排序法关键字递增（从小到大）排序，给出每一趟排序的结果。

22. 已知闭散列表的长度为10（散列地址空间为0?9），散列函数H（k）=k%8，采用线性重新散列技术解决冲突。将下列一组数据（25,16,38,47,79,82,5,39）依次插入散列表中，请画出插入这组数据后的散列表。

23. 用克鲁斯卡尔（Kruskal）算法求图2所示的无向带权连通图的最小生成树，请依次画出生成最小生成树的过程，并计算最小生成树的权。

24. 算法设计题（本大题共2小题，每小题10分，共20分） 请将答案填写在答题纸相应的位置上。

25. 阅读下面程序，假设以两个元素递增（从小到大）有序排列的线性表A和B分别表示两个集合，且同一表中无相同元素，现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，C同样以元素递增方式排序。集合的链表结点结构定义如下，请完善下列程序。

Typedef struct LNode{ElemType data; struct LNode *next;}*LinkList;

LinkList Intersect(LinkList A,LinkList B) {

LNode *p,*q,*r,*s; LinkList C;

C = (LNode)*malloc(sizeof(LNode)); C->next = NULL; r=C;p=A;q=B;

while( (1) ) {

if(p->datadata)p=p->next; else if( (2) ) {

s=(LNode*)malloc(sizeof(LNode)); s->data = p->data; r->next = s; r = s;

(3) ; q=q->next; } else

(4) ; }

r->next = NULL; C=C->next;

return (5) ; }

26. 对于二叉树以二叉链表为存储结构，其根指针为root，树结点结构定义如下，请写出求二叉树的深度（设根的深度为1）的算法。 typedef int TreeItem;

typedef struct btnode *btlink; struct btnode {

TreeItem element; btlink left; btlink right; }Btnode;

第三部分 关系数据库与sql语言（共100分）

一、单项选择题（本大题共20小题，每小题2分，共40分）

在每小题列出的四个备选项中，只有一个是符合题目要求的，请将正确答案代码填写在答题纸相应位置上。

1. 数据库管理系统的英文缩写是：C

a) DB b) DBS c) DBMS d) DBRS

2. 要在表中插入新记录，需要使用以下哪个语句?A

a) Insert b) Select c) Update d) Delete

3. 数据管理技术的发展经过了三个阶段，以下哪个不是这三个阶段之中的？B

a) 人工管理阶段 b) 高级语言阶段 c) 文件系统阶段 d) 数据库系统阶段 4. 数据库系统的模式/内模式映像，确保了数据的什么独立性？D

a) 软件独立性 b) 存取独立性 c) 逻辑独立性 d) 物理独立性 5. 以下哪种模型不是数据库系统中的数据模型？A

a) 还原模型 b) 层次模型 c) 网状模型 d) 关系模型

6. 如果一个关系R∈1NF，并且每一个非主属性都完全函数依赖于码（键），则称关系R 于：A

a) 2NF b) 3NF c) 4NF d) BCNF

7. 现有学生表S(Sno,Sname)和选课表SC(Sno,Cno,G)，其中Sno表示学号，Sname表示姓名，Cno表示课程号，G表示成绩。要查询学生李琳选修的所有课程的成绩，下列关系代数表达式中正确的是：B

a) πG（σS.Sno = SC.Sno(S∞SC)） b) πG（σS.Sname = ‘李琳’(SｘSC)） c) πG（σS.Sname = ‘李琳’(S∞SC)） d) πG（σS.Sname = ‘李琳’(S)ｘSC)）

8. 如果R属于第三范式，则下列描述哪一项是错误的？B a) R中不存在非主属性部分依赖于码（键）的情况 b) R不属于第二范式

c) R中不存在非主属性传递依赖于码（键）的情况 d) R属于第一范式

9. SQL中，“DELETE FROM 表名“表示：A a) 从基本表中删除所有元组 b) 从基本表中删除所有属性 c) 从数据库中撤销这个基本表 d) 从基本表中删除重复元组

10. 将E-R图转换为关系模型是，关于实体的转换原则，下列描述错误的是：B a) 一个实体转换为一个关系模型 b) 两个实体转换为一个关系模式 c) 实体的键就是关系的键 d) 实体的属性就是关系的属性

11. 下述SQL语句中，修改表中数据的命令是：C a) ALTER b) CREATE c) UPDATE d) INSERT 12. 在SQL语句中，与“MIN d)

13. 设有关系模型R(A,B,C,D),F是R上成立的函数依赖集，F={B->C,C->D},则R的候选码（候选键）为：B

a) BCD b) AB c) CD d) BC

14. 在select语句中，指定选择条件的是哪个子句？ C

a) Select b) From c) Where d) Group by 15. 数据库管理系统提供的DML语言是：D

a) 数据定义语言 b) 数据备份语言 c) 数据控制语言 d) 数据操纵语言 16. 数据库在磁盘上的基本组织形式是：B

a) 模型 b) 文件 c) 二维表 d) 二叉树

17. 设有关系R（A,B,C）的值如下：A A B C 2 2 3 2 3 4 3 3 5

a) 函数依赖A->B在上述关系中成立 b) 函数依赖BC->A在上述关系中成立 c) 函数依赖B->A在上述关系中成立 d) 函数依赖A->BC在上述关系中成立

18. 以下哪一个不属于数据库的三级模式结构？D

a) 外模式 b) 模式 c) 内模式 d) 组合模式 19. 以下描述正确的是：B a) 交运算可以用并运算来表示 b) 交运算可以用差运算来表示 c) 并运算可以用差运算来表示 d) 并运算可以用交运算来表示 20. 五种基本关系代数运算是：A a) ∩，-，Ⅹ，π和σ b) ∪，-，∞，π和σ c) ∪，∩，Ⅹ，π和σ d) ∪，∩，∞，π和σ

二、 填空题（本大题共8小题，每空2分，共20）

21. 关系的 实体 完整性约束：说明了键的属性列值必须唯一，其值不能为空或者部分为空。

22. 关系模型可以形式化地表示为R(U,D,DOM,F)，其中R表示关系名，U表示属性名集合，D表示属性来自的域，DOM表示属性向域的映像集合，F表示属性间 集合。 23. SQL(S …… 此处隐藏：3634字，全部文档内容请下载后查看。喜欢就下载吧 ……