2012年浙江农林大学考研试题905-信息技术综合

考试科目：信息技术综合 第１页，共6页

2012年硕士学位研究生入学考试试题

考试科目:信息技术综合 满分：150分 考试时间：180分钟

注意：所有试题答案写在答题纸上，答案写在试卷上无效。

一、数据结构部分 （一）单选题（20分）

1、有一个算法由3个部分的代码嵌套连接组成，每部分的时间复杂度分别为O（1）、O（n）、O（ n ）,该算法的时间复杂度为( )。

A. O（1）+（ n ）+（ n ） B. O（n） C. （ n ） D. （ n ）

2、设单链表中结点的结构为（data ,next）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？（ ）。

A.s->next=p->next;p->next=s B．q->next=s ;s->next=p C.p->next=s->next;s->next=p D.p->next=s ;s->next=q 3、线性链表不具有的特点是（ ）。

A．随机访问 B．不必事先估计所需存储空间大小 C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比 4、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（ ）。

A. d c e a b B.d e c b a C. e d c b a D.a b c d e

5、在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。 A. 2

B. 1

C. 0

D. –1

3

5

2

3

2

2

3

6、具有65个结点的完全二叉树的高度为（ ）。（根的层次号为0）

A．8 B．7 C．6 D．5

7、对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为（ ）。

A．DBFEAC B．DFEBCA C．BDFECA D．BDEFAC

考试科目：信息技术综合 第２页，共6页

8、在一棵具有5层的满二叉树中结点数为（ ）。

A 31 B 32 C 33 D 16

9、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定

是( )。

A.完全图 B.连通图 C.有回路 D.一棵树

10、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ ）。

A．{38，46，79，56，40，84} B．{38，79，56，46，40，84} C．{40，38，46，56，79，84} D．{38，46，56，79，40，84} （二）填空题（7分）

1、计算机中的算法指的是解决某一问题的有限运算序列，它必须具备输入、输出、可行性、( ① )和( ② )等5个特征。

2、有一个算法由3个部分的线性代码连接组成，每部分的时间复杂度分别为O（n）、O（n2）、O（ n4 ）,该算法的时间复杂度为( ③ )。

3、线性表的常见链式存储结构有单链表、( ④ )和( ⑤ )。

4、若已知一个栈的入栈序列是1，2，3，4，?，n ，其输出序列是P1，P2，P3，?，Pn，若P1=n，则Pi为( ⑥ )。

5、对任何二叉树，若度为2的节点数为n2，则叶子数n0=( ⑦ )。 （三）综合题（18分）

1、给出下列二叉树的前序序列、中序序列、后序序列。（6分）

考试科目：信息技术综合 第３页，共6页

2、假定用于通信的电文仅由5个字母a，b，c，d, e组成，各个字母在电文中出现的频率分别为7，6, 5，2，4。试为这5个字母设计Huffman树且写出对应的Huffman编码。（5分）

3、已知待排序记录的关键字序列为{83，69，41，22，15，33，8}，要求用直接插入排序法按从小到大顺序写出每趟排序的结果，直到排序结束。（7分） 二、数据库部分

（一）填空题（１5%，每空１分）

1、 现实世界中，事务的个体在信息世界中称为：(1) ，在机器世界中称为(2) 。 2、 数据库的三要素包含数据结构、 (3) 、 (4) 3、 创建数据库的SQL命令为：CREATE (5) 。

4、 数据库管理系统提供的数据保护功能主要包括： (6) 、 (7) 、 (8) 和(9) 。

5、 在SQL中，如果希望将查询结果排序，应在SELECT语句中使用： (10) ，

其中 (11) 选项表示升序， (12) 选项表示降序

6、 SELECT语句中进行查询，若希望查询的结果不出现重复无组，应在SELECT子句

中使用(13) 保留字。

7、 数据库系统通常采用三级结构：外模式、(14) 、(15) 。 （二）是非题（15%，每空1分）

1、 SQL中创建基本表使用CREATE TABLE语句 （2、 视图创建完毕后，数据字典中存放的是视图定义

（3、 WHERE子句的条件表达式中，可以匹配0到多个字符的通配符是“?” （4、 Select语句是一种查询语句

（5、 视图定义后，数据字典中存放的是视图的数据

（6、 select语句中与having子句同时使用的是GROUP BY子句 （7、 SQL SERVER中，MODEL数据库是示例数据库

（8、 假设表中某列的数据类型为VARCHAR（10），输入字符串“123”后，数据库中存

（储的是3个字节

9、 SQL SERVER中一张表的聚簇索引个数可以有多个

（

） ） ） ） ） ） ） ）

）

考试科目：信息技术综合 第４页，共6页

10、通过DELETE语句可以将数据插入到某个表中 11、候选码中的属性称为非主属性

12、SQL SERVER是一种关系数据库管理系统

13、当两个关系没有公共属性时，其自然连接表现为迪卡尔积

14、关系数据库的逻辑模型设计阶段，任务是将概念模型转换成关系模型 15、数据库中，“脏数据”指未提交的数据 （ ） （ ） （ ） （ ） （ ） （ ）

（三）简答题（30%，每小题5分）

设学生选课数据库有如下三个表。 学生（学号，姓名，性别，年龄）； 课程（课程号，课程名，学分）； 成绩（学号，课程号，成绩） 其中：

1) 学生表的主码为“学号”；2) 课程表的主码为“课程号”；3) 成绩表的主码为“学号＋课程号”。且学号为外码，其被参照表为学生表，对应属性为学号；课程号为外码，其被参照表为课程表，对应属性为课程号。

试用SQL语句表达下列操作： 1、 查询男同学的基本信息 2、 查询统计低于60分的学生人数

3、 查询选修了“数据库原理与技术”的课程的学生成绩 4、 查询各学生平均成绩，并按平均成绩从高到低进行排序 5、 将记录（’C07’，’C语言’，3）插入到课程表中

6、 将学号为‘S01’，课程号为‘C01’的记录的成绩修改为80。

三、计算机网络部分（45分）

（一）选择题（10题，每题1分，共10分） 1. 168.95.192.1/24中的24表示____ A、IP地址168.95.192.1中前24位为主机地址 B、IP地址168.95.192.1中前24位为网络地址