搜索
1北京化工大学2010—2011年第一学期《软件技术基础》期末考试试卷班级：学号：姓名：分数：题号一二三四五六总分得分一、判断题(共10分，每题1分)1.线性表的顺序存储结构中，逻辑上相邻的数据元素在物理位置上也是相邻的。【】2.栈只能在栈顶进行插入和删除。【】3.队列只能在队首进行插入，在队尾进行删除。【】4.有向图中，所有结点的出度之和等于入度之和。【】5.由二叉树的先根序列和后根序列可以唯一的确定一棵二叉树。【】6.使用二分查找时，要求数据元素有序，与存储结构无关。【】7.希尔排序方法是一种稳定的排序方法。【】8.PCB是进程之间的一种高级通信方式。【】9.死锁的形成除了与资源的分配策略有关外，也与并发进程的执行速度有关。【】10.视图也属于一个表，它是从基本表中通过连接生成的。【】二、填空题(共10分，每空1分)(1)一个队列的入列序列是3,1,2,4，则队列的输出序列是________。(2)单链表中，p为指向当前结点指针，如果想删除当前结点之后的结点，使用语句为________________。(3)在一棵完全二叉树中，若编号为i的结点有右孩子，则该右孩子结点的编号为________。(4)图有两种基本的遍历方式，分别是________和________。(5)操作系统中，进程调度通常有先来先服务调度、________、时间片轮转调度和分级调度等调度算法。2(6)进程创建后，最初处于________态，经过调度后进入________态。(7)E-R模型一般用在数据库设计的________设计阶段。(8)在SQL语言中，权限授予命令是________。三、名词解释(共12分，每题3分)(1)算法(2)二叉树(3)死锁(4)DBMS四、问答题(共28分，每题7分)(1)已知二叉树的前序序列为DBACFEG，中序序列为ABCDEFG，试画出该二叉树，并写出该二叉树的后序序列？(2)使用快速排序算法对关键词序列(64,98,204,13,48,35,105,52,43,48*)进行排序，描述排序过程？(以一趟排序为单位，每次选第一个关键字为轴枢记录)。(3)什么是操作系统?从资源管理的角度看，操作系统应具有哪些功能?(4)数据库设计过程包含哪几个阶段，各阶段主要工作是什么？五、算法设计题(共16分，每题8分)(1)有一线性单链表，其结点值均为正整数。试设计算法找出链表中值最大的结点，输出该结点的值并将它从链表中删除。typedef struct LNode { int data; struct LNode *next; } LNode, *LinkedList; 函数定义为： void removeMaximum(LinkedList head){ // head为指向链表头结点的指针 } (2)试编写算法实现快速排序过程？六、应用题(共24分，每题8分)(1)已知一个有向图G=(V,E)，其中V={A,B,C,D,E,F}，邻接矩阵表示如下。3000011000000010010101000010001001100⎛⎞⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎝⎠z请画出对应的图G。z画出图G的邻接表存储结构。z给出深度优先和广度优先序列。(2)有如下关键字{47,7,29,11,16,92,22,8,3,50,37,89,46}，设Hash函数为H(Key)=KeyMOD13，采用线性探测序列法来处理冲突，试设计Hash表并说明关键字50的查找过程。(3)设有学生关系Student和选课关系SC如下：Student#SNoSNameAgeDept220011陈道明21计算机系220012高军22自动化系220485刘翔20测控系220647林双19信工系SC#SNo#CNoScore220011102084220012108576220485108592220485102052用关系表达式和SQL语言进行查询。z查询计算机系年龄大于20岁的学生学号和姓名。z查询成绩超过80分的学生姓名。z查询计算机系和自动化系成绩及格学生学号和姓名。