软件技术基础期末试卷B.doc

南昌大学 20042005学年第一学期期末考试试卷 试卷编号： ( B )卷课程名称： 计算机软件技术基础 适用班级： 电子、通信 姓名： 学号： 班级： 专业： 学院： 系别： 考试日期： 2005.01.13 题号一二三四五六七八九十总分累分人 签名题分2020203010 100得分一、 选择题(每题1分，共20分) 得分评阅人 1. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第6个元素的地址是 。A. 110 B. 108 C. 104 D. 1122设输入序列为1，2，3，4，借助一个栈得到的输出序列可以是 。A3，4，1，2 B4，2，1，3 C4，1，2，3 D1，3，4，23用数组Am存放循环队列的元素值，若其头尾指针分别为front和rear，则循环队列中当前元素的个数为 。A(rear+front)%m B(rear-front+m)%mC(rear-front)%m D(rear-front+1)%m4. 栈和队列的共同点是 。A. 都是先进后出 B. 都是先进先出C. 只允许在端点处插入和删除元素 D. 没有共同点5. 按照二叉树的定义，具有3个结点的二叉树共有 种。A. 3 B. 4 C. 5 D. 66. 深度为5的二叉树至多有 个结点。A. 16 B. 32 C. 31 D. 107. 对一棵满二叉树，有m个树叶，n个结点，深度为h，则 。A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-18. 一个有n个顶点的无向图最多有 条边。A. n B. n(n-1) C. n(n-1)/2 D. 2n第 6 页 共 6页9.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 。A. 希尔排序 B. 冒泡排序 C. 插入排序 D. 选择排序10.专门的关系运算不包括下列中的 。A. 连接运算 B. 选择运算 C. 投影运算 D. 交运算11. SQL是那几个英文单词的缩写 。A. Standard Query Language B. Structured Query Language全国计算C. Select Query Language D. 以上都不是12. 目前较有影响的数据库，如Oracle 、SQL Server、Visual Foxpro等，基于的数据模型是 。 试A. 层次模型 B. 关系模型 C. 网状模型 D. 混合型13与数据元素本身的形式、内容、相对位置及个数无关的是数据的 。A存储结构 B存储实现C逻辑结构 D运算实现14逻辑记录必须存放在连续物理块上的文件是 。A顺序文件 B链接文件 C索引文件 D均不是15设有如下关系R、S和T，则关系T是由关系R和S经过哪种操作得到的？ ARS BR-S CRS DRS16如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用 查找方法。A分块 B顺序 C二分 D散列17文件按用途可分为三种，选出不属于该分类方法的一种。 A系统文件 B库文件 C档案文件 D用户文件18下列不是进程特征的是 。A动态性 B并发性 C异步性 D实时性19. 下列哪种排序是稳定的排序？ A直接选择排序 B快速排序 C冒泡排序 D希尔（shell）排序20. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 。A希尔排序 B冒泡排序 C插入排序 D选择排序二、 填空题(每题1分，共20分)得分评阅人 1处理机的指令系统分为两类：一类是 ，另一类是 。2在批处理系统中，作业由 和 构成。3数据库系统的三级模式结构中，存在着两种映射，一个是 之间的映射，另一个是 之间的映射。4数据库中三种基本的数据模型是： 、 和 。5专门的关系运算包括 、 、 和除法运算等。6算法的复杂性包括 和 两个方面。7.一棵二叉树有30个叶子结点,仅有一个孩子的结点有20个,则该二叉树共有 个结点；若完全二叉树共有100个结点，则其叶子结点数为 。8.从某个给定的关系中选出满足条件的元组的一元关系运算是 。9有n个顶点的无向连通图G, 其最小生成树有 条边。10栈是一种 的线性表；队列是一种 的线性表。三、 简答题（每小题5分，共20分）得分评阅人 1 写出进程的三种基本状态及其各状态之间的转换关系。2 简述存储管理的功能。3 简述希尔排序（Shell）排序的基本思想。4 试比较常用的三种检索方法-顺序检索、二分法检索和分块检索，在检索速度和对表的要求方面的不同。四、 应用题（每小题5分，共30分）得分评阅人 1 根据二叉树的定义，二叉树有几种不同的形态？分别画出其形态。2 要在单链表中的p所指结点之后插入一个结点q,如下图所示，请写出所执行的操作。 3根据Kruskal / Prim算法构造如下图所示的带权有向图的最小生成树。4. 画出如下图所示图G的邻接表 。5. 已知关系R和S如下，试求RS 6. 根据如下的“教师”表，用SQL语句完成下面的问题：职工号姓名职称年龄工资11020011102002110200311020041102005肖海天王远刘星李名玉孙明山副教授教授讲师教授教授354030455520003000120035004000（1）用SQL语句向教师表中插入一条记录：（1102006，张平，副教授，38，1500）（2）查