………密………封………线………以………内………答………题………无………效……一、填空题（共20分，共 11题，每空1分）1．若经常需要对线性表进行插入和删除运算，则最好采用_ _存储结构，若经常需要对线性表进行查找运算，则最好采用_ ___存储结构。

2．在操作过程中会出现“假溢出”现象的是 ，解决此问题的方法是 。

3．已知一棵二叉树的顺序存储结构为 则元素G 的父结点是 。

4． 假定一个有向图的顶点集合为{1,2,3,4,5,6},边集合为{<1,2>，<1,3>，<2,5>，<3,2>，<3,4>，<4,6>，<5,1>，<5,6>}，则出度为2的顶点个数为 ，入度为1的顶点个数为 。

5．二分查找算法适用于 数据结构，且数据的组织应该 。

6． 虚拟存储方式分为： 、 、 。

7． 用户通过操作系统提供的 、 、 图形用户接口来使用计算机。

8． 文件的物理结构分为： 、 、 。

9． 因特网是由许多大小不同、类型不同的 互连而成。

10． 有表score （stuid ，name,engish ），写出查询姓名和英语成绩的查询语句 。

11．数据库表中能唯一标识出实体的属性也称为 。

二、选择题（共30分，共 30题，每题1分）1．线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。

A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以 2．下面哪个结构不是线性结构（ ）。

A . 队列B . 图C 线性表D . 栈3．一个下图所示的双链表，定义P 为指针变量，则P->next->next->.prior 和P->prior->next 指向的数………密………封………线………以………内………答………题………无………效……据域的值分别是（）。

A．80和20 B. 64和47 C. 64和20 D. 80和474．在一个无向图中，所有顶点的度数之和等于所有边数（）倍。

A．1/2 B．1 C．2 D．45．一棵树中，树的深度是（）。

A．结点的最大层次值B．子树总的数目C．结点的数目D．结点子树的最大数6．一棵二叉树采用顺序存储结构，数组下标从0开始，若存放某结点的数组元素下标为11，则存放它的父结点的数组元素下标为（）。

A．3 B．4 C．5 D．67．对链式存储的数据实现平均速度较快的查找，应该将数据以（）形式存放。

A．双链表B．循环链表C．二叉链表D．二叉排序树8．一个栈的入栈序列是a,b,c,d,e，且每个字符只进栈一次，则栈的不可能的输出序列是（）。

A．e,d,c,b,a B．d,e,c,b,a C．d,c,e,a,b D．a,b,c,d,e 9．一个所有非终端节点都有非空的左右子树的二叉树，叶子节点的个数为n，那么二叉树上的节点总数为（）。

A．不确定B．2n C．2n+1 D．2n-1 10．在排序算法中设置一个变量来记录排序过程中是否有元素交换存放位置，从而可以提前结束排序操作的是（）。

A．冒泡排序B．归并排序C．简单插入排序D．简单选择排序11．进程的状态是可以转换的，而以下哪个状态转换是不可能的（）。

A．就绪 执行B．执行 就绪C．等待 执行D．等待 就绪12．下面（）不是操作系统的特征。

A．并发性B．共享性C．虚拟性D．确定性………密………封………线………以………内………答………题………无………效……13．临界资源是（）。

A．以同步关系使用的共享资源B．以互斥关系使用的共享资源C．以共享关系使用的资源D．允许多个进程使用的共享资源14．进程由程序块、进程控制块和（）三部分组成。

A．数据块B．作业C．文件D．设备15．作为编程人员，在程序设计中可以通过（）获得操作系统服务。

A．命令接口B．作业调度C．进程调度D．系统调用16．下面哪一种说法对IP地址而言是正确的（）。

A．它恰好分为两类B．它包含一个长度固定的主机地址C．它是层次结构的地址D．它有48比特长17．网络中ARP的作用是在给定（）时找到（）。

A．域名，IP地址B．物理地址，IP地址C．IP地址，域名D．IP地址，物理地址18．以下哪种类型的寻址方式是专门为传输层所用的？（）A．物理地址B．IP地址C．应用程序端口D．A和B19．域名解析实现（）。

A．域名到物理地址的解析B．域名到IP地址的解析C．IP地址到物理地址的解析D．A 和B20．如果IP地址为199.55.60.122，不进行子网化，则该工作站的子网掩码可能为：（）A．255.0.0.0 B．255.255.0.0 C．255.255.255.0 D．255.255.255.24021．在局域网中，计算机接收带有如下地址的帧（）。

A．目标地址为广播地址B．目标地址为网络地址C．目标地址为该计算机硬件地址D．A和C22．以太网采用（）来确定对传输介质的控制。

A．令牌B．优先级C．先后次序D．载波侦听冲突检测23．当数据链路层将帧从一条链路发送到另一条链路时，它检查（）。

A．主机地址B．IP地址C．域名D．物理地址24．在数据管理技术的发展过程中，经历了人工管理阶段，文件系统阶段和数据库系统阶段。

在这………密………封………线………以………内………答………题………无………效……几个阶段中，（）是数据独立性最高的阶段。

A．人工B．文件系统C．数据库系统D．数据项管理25．数据库中存储的是（）。

A．数据B．数据模型C．数据以及数据之间的联系D．信息26．数据库的特点之一是数据的共享，严格的讲，这里的数据共享是指（）。

A．同一个应用中的多个程序共享一个数据集合B．多个用户、同一种语言共享数据C．多个用户共享一个数据文件D．多种应用、多种语言、多个用户相互覆盖地使用数据集合27．关于数据库系统的正确叙述（）。

A．数据库系统减少了数据冗余B．数据库系统避免了一切冗余C．数据库系统中数据的一致性是数据类型的一致D．数据库系统比文件系统能管理更多的数据28．下列哪一项不属于数据库管理系统（DBMS）中的主要功能（）。

A．数据库定义B．数据库保护C．数据字典D．操作系统29．常见的数据模型有（）。

A．大型、中型、小型B．数据、图形、多媒体C．西文、中文、兼容D．层次，网状、关系30．下面哪个协议是应用层协议（）。

A．IP B．TCP C．UDP D．HTTP三、简答题（共36分）．设元素1、2、3、4、5依次进栈，在输出端得到序列32451，给出应进行的各入栈和出栈操作。

(5分)………密………封………线………以………内………答………题………无………效……2．设单链表结点结构定义如下，现要在单链表中删除指针p所指结点的直接后继（此结点及其直接后继均存在），给出各操作语句。

(5分)struct node{ int data;struct node *next;};3．给出下图二叉树的先序、中序和后序遍历序列，其中左右子树的遍历先左后右。

(6分)4．以关键字序列（53，12，80，64，32，92，17，75，45，26）为例，写出快速排序的各趟结果。

（8分）5．已知一个图的边集为{（1，2），（1，4），（1，7），（2，3），（2，4），（3，5），（3，6），（4，………密………封………线………以………内………答………题………无………效……5），（5，8），（6，7），（6，8）}，画出这张图的邻接矩阵和邻接表结构示意图，并给出从2开始的深度优先和广度优先遍历序列。

（8分）6．已知有一组序列为（17，26，38，27，46，72，82，93），设哈希表长m=14，哈希函数H(key)=key%11。

利用二次探测再散列处理冲突，建立哈希表。

（4分）………密………封………线………以………内………答………题………无………效……四、编程题（共14分）对一个班级学生数学成绩进行管理：由给出的数据结构和初始化的按数学成绩递增有序的成绩表，编写程序：1．完成插入一个学生数据的函数，要求插入操作后学生数据依然递增有序。

（5分）2．完成主函数main: 实现成绩表数据的初始化（调用给出的初始化函数：initlist）、实现成绩表数据插入操作（调用第1题中编写的函数）并输出成绩表中的所有数据。

（9分）#include "string.h"#define STUDENTNUMBER 30// 学生数据结构typedef struct{ int studyid;char name[10];float mathscore;}STUDENT;// 班级学生表结构typedef struct{STUDENT data[STUDENTNUMBER];int num;}listtype;// 初始化班级学生表中数据void initlist(listtype *p){ p->data[0].studeyid=1;strcpy(p->data[0].name,"李一");p->data[0].mathscore=82;………密………封………线………以………内………答………题………无………效……p->data[1].studeyid=2;strcpy(p->data[1].name,"张二");p->data[1].mathscore=85;p->data[2].studeyid=3;strcpy(p->data[2].name,"赵三");p->data[2].mathscore=88;……/* 班级中按数学成绩递增有序的学生总共有20位*/p->num=20;}int main(int argc, char* argv[]){}。