2012年浙江农林大学信息技术综合考研真题及答案
2012年浙江农林大学信息技术综合考研真题及答案
一、数据结构部分
（一）单选题（20 分）
1、有一个算法由 3 个部分的代码嵌套连接组成，每部分的时间复杂度分别为 O（1）、O（n2）、O（n3）,该算法的时间复杂度为（）。
A. O（1）+（n2）+（n3）
B. O（n2）
C. （n3）
D. （n5）
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
6、具有 65 个结点的完全二叉树的高度为（）。（根的层次号为 0）
A．8B．7C．6D．5
7、对某二叉树进行前序遍历的结果为 ABDEFC，中序遍历的结果为 DBFEAC，则后序遍历的结果为（）。
A．DBFEAC B．DFEBCA
C．BDFECAD．BDEFAC
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 分）
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 中一张表的聚簇索引个数可以有多个（）
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.19
2.1/24 中的 24 表示____
A、IP 地址 168.95.192.1 中前 24 位为主机地址
B、IP 地址 168.95.192.1 中前 24 位为网络地址
C、IP 地址 168.95.192.1 中后 24 位为主机地址
D、IP 地址 168.95.192.1 中后 24 位为网络地址
2．IPv4 的 IP 地址为（）位。
A、16
B、32
C、64
D、128
3. 完成 IP 地址到 MAC 地址转换工作的协议是___
A、ICMP
B、RARP
C、ARP
D、DNS
4．下面可以用来作为子网掩码的是 ( )
A、255.255.255.160
B、255.255.255.176
C、255.255.255.184
D、255.255.255.192
5. 政府部门的域名应该包含（）
A、com
B、edu
C、gov
D、org
6．下列串中，不是一个合法 IP 地址的是( )。
A、1.2.3.4
B、191.122.23.4
C、204.17.206.10
D、350.267.45.128
7. 完成将域名转换成 IP 地址需要使用下列哪种服务（）
A、WWW
B、FTP
C、SMTP
D、DNS
8. CSMA/CD 监听冲突/检测工作在___
A、物理层
B、数据链路层
C、网络层
D、传输层
9. HTTP 使用的熟知端口号是：
A、21
B、23
C、53
D、80
10．21.12.240.17 是下列哪一类地址？
A、A 类
B、B 类
C、C 类
D、D 类
（二）简答题（5 题，每题 6 分，共 30 分）
1. ARP 的作用是什么？如何实现的？
2. 请说明 CSMA/CD 协议的工作原理。
3. 什么是单工？什么是半双工？什么是全双工？
4. 为了解决 IPv4 地址紧张的问题，出现了哪些技术？并对它们进行简要说明。
5. 请举例说明网络中的一台计算机是如何判断另一个 IP 地址是否与自己同一个网络。（三）计算题（5 分）
1. （5 分）一个单位一共有 5 个部门，因此希望能有 5 个单独的网络，但此单位只拥有一个 C 类 IP 地址 20
2.112.144.0。请完成下面两个问题：
1）将此单位拥有的 IP 地址分成 5 个子网，指出各个子网的 IP 地址范围。
2）分成的 5 个子网的子网掩码都一样，是多少？
1 2 3 4 5 6 7 8 9 10
D B A A A B B A B C
（二）填空题（7 分，每题 1 分）
①确定性②有穷性③O（ n4）④双向链表
⑤循环链表⑥n-i+1 ⑦n2+1
（三）综合题（18 分）
1、6 分，每个 2 分
前序：CABEFDHG
中序：BAFECHDG
后序：BFEAHGDC
2、5 分，每个 1 分
a :10 b: 00 c: 01 d:110 e :111
3、7 分，每趟 1 分
第一趟：83，69，41，22，15，33，8
第二趟：69，83，41，22，15，33，8
第三趟：41，69，83，22，15，33，8
第四趟：22，41，69，83， 15，33，8
第五趟：15，22，41，69，83， 33，8
第六趟：15，22，33，41，69，83， 8
第七趟：8，15，22，33，41，69，83
二、数据库部分
（一）填空题（１5%，每空１分）
1、现实世界中，事务的个体在信息世界中称为：_（1）实体_ ，在机器世界中称为_（2）记录_。
2、数据库的三要素包含数据结构、 _（3）_数据操作_ 、_（4）_完整性约束_
3、创建数据库的 SQL 命令为：CREATE _（5）DATABASE _。（注：不区分字母大小写）
4、数据库管理系统提供的数据保护功能主要包括：_（6）数据完整性控制_、_ (7)数据安全性控制_、_ (8)并发控制_和_ (9)数据库恢复_。（注：（6）－（9）顺序可互换）
5、在 SQL 中，如果希望将查询结果排序，应在 SELECT 语句中使用：_ (10)ORDERBY_
，其中_ (11)ASC _ 选项表示升序，_(12)DESC_选项表示降序。（注：不区分字母大小写）
6、 SELECT 语句中进行查询，若希望查询的结果不出现重复无组，应在 SELECT 子句
中使用_(13)DISTINCT_保留字。（注：不区分字母大小写）
7、数据库系统通常采用三级结构：外模式、_(14) 模式/概念模式/逻辑模式_、_(15)内模式/存储模式/物理模式_。（注（14）、（15）顺序可互换）
（二）是非题（15%，每空 1 分）
1、 SQL 中创建基本表使用 CREATE TABLE 语句（√）
2、视图创建完毕后，数据字典中存放的是视图定义（√）
3、 WHERE 子句的条件表达式中，可以匹配 0 到多个字符的通配符是“?”（╳）
4、 Select 语句是一种查询语句（√）
5、 ALTER 语句可实现对表中数据的修改（╳）
6、 select 语句中与 having 子句同时使用的是 GROUP BY 子句（√）
7、 SQL SERVER 中，MODEL 数据库是示例数据库（╳）
8、假设表中某列的数据类型为 VARCHAR（10），输入字符串“123”后，数据库中存储的是 3 个字节（√）
9、 SQL SERVER 中一张表的聚簇索引个数可以有多个（╳）
10、通过 DELETE 语句可以将数据插入到某个表中（╳）
11、候选码中的属性称为非主属性（╳）
12、SQL SERVER 是一种关系数据库管理系统（√）
13、当两个关系没有公共属性时，其自然连接表现为迪卡尔积（√）
14、关系数据库的逻辑模型设计阶段，任务是将概念模型转换成关系模型（√）
15、数据库中，“脏数据”指未提交的数据（√）
（三）简答题（30%，每小题 5 分）
设学生选课数据库有如下三个表。
学生（学号，姓名，性别，年龄）；
课程（课程号，课程名，学分）；
成绩（学号，课程号，成绩）
其中：
1) 学生表的主码为“学号”；2) 课程表的主码为“课程号”；3) 成绩表的主码为“学号＋课程号”。且学号为外码，其被参照表为学生表，对应属性为学号；课程号为外码，其被参照表为课程表，对应属性为课程号。
试用 SQL 语句表达下列操作：
1、查询男同学的基本信息
答案：SELECT * FROM 学生 WHERE 性别＝‘男’（其中“*”可用“学号，姓名，性别，年龄”代替评分标准：SELECT （1 分）* （1 分）FROM（1 分）学生（1 分）WHERE 性别＝‘男’（1 分）
2、查询统计低于 60 分的学生人数
答案：SELECT COUNT(*) FROM 成绩 WHERE 成绩<60
评分标准：SELECT（1 分） COUNT(*)（2 分）FROM 成绩（1 分）WHERE 成绩<60（1 分）
3、查询选修了“数据库原理与技术”的课程的学生成绩
答案：1) SELECT 学号,成绩 FROM 成绩 WHERE 课程号=(SELECT 课程号 FROM 课程 WHERE 课程名＝‘数据库原理与技术’2) SELECT 学号,成绩 FROM 课程,成绩 WHERE 课程.课程号=成绩.课程号 AND 课程名=‘数据库原理与技术’评分标准：1）SELECT 学号,成绩（1 分）FROM 成绩（1 分） WHERE 课程号=（1分）(SELECT 课程号 FROM 课程 WHERE 课程名＝‘数据库原理与技术’)（2分）
注：“SELECT 学号,成绩”也可改成“SELECT 学号,课程号,成绩”或改成“SELECT *”，“……课程号=……”可以改成“……课程号 IN …….”
2）SELECT 学号,成绩（1 分） FROM 课程,成绩（2 分） WHERE 课程.课程号=成绩.课程（1 分） AND 课程名=‘数据库原理与技术’（1 分）
4、查询各学生平均成绩，并按平均成绩从高到低进行排序
答案：SELECT 学号,AVG(成绩) FROM 成绩 ORDER BY 成绩 DESC
评分标准：SELECT 学号（1 分）,AVG(成绩)（1 分） FROM 成绩（1 分） GRROUP BY 学号（1 分） ORDER BY AVG(成绩)（1 分） DESC（1 分）
5、将记录（’C07’，’C 语言’，3）插入到课程表中
答案：INSERT INTO 课程 VALUES(’C07’，’C 语言’，3) 或者 INSERT INTO 课程（学号,课程号,成绩）VALUES(’C07’，’C 语言’，3)
评分标准：INSERT INTO（1 分）课程（1 分）VALUES(’C07’，’C 语言’，（3 分）
6、将学号为‘S01’，课程号为‘C01’的记录的成绩修改为 80。
答案：UPDATE 成绩 SET 成绩＝80 WHERE 学号=‘S01’AND 课程号＝‘C01’
评分标准：UPDATE 成绩（2 分） SET 成绩＝80（2 分）WHERE 学号=‘S01’
AND 课程号＝‘C01’（1 分）
三、计算机网络部分
（二）简答题（5 题，每题 6 分，共 30 分）
1、ARP 的作用和实现
首先，每台主机都会在自己的 ARP 缓冲区中建立一个 ARP 列表，以表示 IP 地址和 MAC 地址的对应关系。（2 分）
当源主机需要将一个数据包要发送到目的主机时，会首先检查自己 ARP 列表中是否存在该IP 地址对应的 MAC 地址，如果有，就直接将数据包发送到这个 MAC 地址；如果没有，就向本地网段发起一个 ARP 请求的广播包，查询此目的主机对应的 MAC 地址。此 ARP 请求数据包里包括源主机的 IP 地址、硬件地址、以及目的主机的 IP 地址。（2 分）
网络中所有的主机收到这个 ARP 请求后，会检查数据包中的目的 IP 是否和自己的 IP地址一致。如果不相同就忽略此数据包；如果相同，该主机首先将发送端的 MAC 地址和 IP 地址添加到自己的 ARP 列表中，如果 ARP 表中已经存在该 IP 的信息，则将其覆盖，然后给源主机发送一个 ARP 响应数据包，告诉对方自己是它需要查找的 MAC 地址；源主机收到这个 ARP 响应数据包后，将得到的目的主机的 IP 地址和 MAC 地址添加到自己的 ARP 列表中，并利用此信息开始数据的传输。如果源主机一直没有收到 ARP 响应数据包，表示 ARP 查询失败。（2 分）
2、CSMA/CD 协议的工作原理CSMA/CD（Carrier Sense Multiple Access/Collision Derect），即载波监听多路访问/冲突检测方法是一种争用型的介质访问控制协议。它起源于美国夏威夷大学开发的ALOHA 网所采用的争用型协议，并进行了改进，使之具有比 ALOHA 协议更高的介质利用率。（2 分）
CSMA/CD 是一种分布式介质访问控制协议，网中的各个站（节点）都能独立地决定数据帧的
发送与接收。每个站在发送数据帧之前，首先要进行载波监听，只有介质空闲时，才允许发送帧。这时，如果两个以上的站同时监听到介质空闲并发送帧，则会产生冲突现象，这使发送的帧都成为无效帧，发送随即宣告失败。（2 分）
每个站必须有能力随时检测冲突是否发生，一旦发生冲突，则应停止发送，以免介质带宽因传送无效帧而被白白浪费，然后随机延时一段时间后，再重新争用介质，重发送帧。CSMA/CD 协议简单、可靠，其网络系统（如 Ethernet）被广泛使用。（2 分）
3、单工:发送端、接收端角色固定。（2 分）
半双工:发送端、接收端角色不固定，但不能同时双向传输。（2 分）
全双工:发送端、接收端角色不固定，并可以同时双向传输。（2 分）
4、1）采用无分类编址 CIDR，使得 IP 地址的分配更加合理（2 分）
2）采用网络地址转换 NAT，可节省许多全球 IP 地址（2 分）
3）采用具有更大地址空间的 IP 协议，即 IPV6 （2 分）
5、答：一台计算机要判断另一个 IP 是否与自己同一个网络，要计算两个值：
1) 自己 IP 与自己的子网掩码相“与”，得到自己所处的网络地址。（2 分）
2）对方的 IP 与自己的子网掩码相“与”，得到对方所处的网络地址，如果两次计算的结果相同，则表明此计算机认为另一 IP 与自己处于同一个网络，否则就认为另一 IP 与自己不处于同一个网络。（2 分）
例如 A 计算机的 IP 为 192.168.7.44，子网掩码为 255.255.255.0，如果 B 计算机的IP 为 192.168.7.45，则两次计算出来的结果都是 192.168.7.0，A 就认为双方处于同一个网络；如果 B 的 IP 为 192.168.8.45，则两次计算的结果分别为 192.168.7.0 与
192.168.8.0，两者不同，A 就认为 B 与自己不处于同一网络。（2 分）
（三）计算题（5 分）
1．（5 分）
1) 由 2n－2≥5 知 n=3，即 5 个子网决定子网地址为 3 位，即子网掩码为：
11111111 11111111 11111111 11100000 (255.255.255.224) （1 分）
子网地址 3 位，则主机地址位数为 8－3=5，主机地址为 00001～11110，即 1~30。另外，3 为子网地址，可形成 8 个子网，除去全 0 和全 1，剩余 6 个：（1 分）
任选下面的 5 个：
001 00000 (32), 1~30, 202.112.144.33~202.112.144.62
010 00000 (64), 1~30, 202.112.144.65~202.112.144.94 （1 分）
011 00000 (96), 1~30, 202.112.144.97~202.112.144.126
100 00000 (128), 1~30, 202.112.144.129~202.112.144.158
101 00000 (160), 1~30, 202.112.144.161~202.112.144.190
110 00000 (192), 1~30, 202.112.144.193~202.112.144.222 （1 分）
选择其中五个 IP 地址段分给各个部门即可。
2）5 个子网的子网掩码都是 255.255.255.224 （1 分）