软件技术基础2006-2007第一学期期末试卷B.doc

南昌大学 20062007学年第 1 学期期末考试试卷 试卷编号： 信9 (B )卷课程编号： X61050001 课程名称： 计算机软件技术基础 考试形式： 闭卷 适用班级： 生物医学04级 姓名： 学号： 班级： 学院： 专业： 考试日期： 2007.01.15 题号一二三四五六七八九十总分累分人 签名题分2020202020 100得分一、 单项选择题 (每小题1分，共20分) 得分评阅人 1. 一个向量第一个元素的存储地址是1000，每个元素的长度为2，则第4个元素的地址是 。A. 1010 B. 1008 C. 1004 D. 10122下列选项中，不是算法基本特征的是 。 A可行性 B. 有穷性 C. 确定性 D.高效率 3在一个单链表中，若p结点不是最后一结点。在p结点之后插入s结点的正确是 。 A. s-next=p; p-next=s; B. s-next=p; p=p C. s-next=p-next ; p-next=s; D. p-next=s; s-next=p; 4. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用 排序法。 A. 冒泡排序 B. 快速排序 C. 堆排序 D.选择排序5描述数据库全体数据的全局逻辑结构和特性的是 。 A. 模式 B. 内模式 C. 外模式 D. 用户模式6. 在一棵二叉树中有30个叶子结点，仅有一个孩子的结点有20个，则该二叉树共有 个结点A、79 B、76 C、56 D、817. 对于下三角矩阵A，若采用一个一维数组B以行为主顺序存放压缩矩阵A，则A43存放在 中A. B7B. B8C. B9D. B108. 顺序查找适合于存储结构为 的线性表。 A. 散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储 第 6 页 共 6页9. 排序方法中，从未排序序列中挑选元素最小的记录，并将其顺序放在已排序序列的末端的方法，称为 。A. 希尔排序 B. 冒泡排序 C. 插入排序 D. 选择排序10. SQL是一种 语言。A. 高级算法 B. 人工智能 C. 关系数据库 D. 函数型 11. 目前较有影响的数据库，如Oracle 、SQL Server、Visual Foxpro等，基于的数据模型是 。 试A. 层次模型 B. 关系模型 C. 网状模型 D. 混合型12对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0= 。A、n1+1 B、n1+n2 C、n2+1 D、2n1+113设关键码序列为（16，9，4，25，15，2，13，18，17，5，8，24），要按关键码值递增的次序排列，采用直接选择排序法，一趟排序后的结果是 。 A.（15，2，4，18，16，5，8，24，17，9，13，25） B.（2，9，4，25，15，16，13，18，17，5，8，24） C.（9，4，16，15，2，13，18，17，5，8，24，25） D.（9，16，4，25，21，5，13，18，5，17，8，24） 14对于深度为4的完全二叉树，则该二叉树叶结点数是 。A. 16 B. 31 C. 32 D. 815下列关于时间片轮转法的叙述中，错误的是 。A、如果时间片长度很小，则调度程序剥夺CPU的次数频繁，加重系统开销B、当时间片结束时，运行进程自动让出CPU，该进程进入等待队列C、就绪队列中的诸进程轮流上CPU运行，每次最多运行一个时间片D、 在时间片轮转法中，系统将CPU的处理时间划分成若干个时间段16用链表表示线性表的优点是 。 A、花费的存储空间比顺序表少 B、便于随机存取C、数据元素的物理顺序与逻辑顺序相同 D、便于插入与删除17实体间的联系方式是 。A、 1：1 B、1：N C、M:N D、前三种圴可18假设学生关系S（S，SNAME，SEX），课程关系C（C，CNAME），学生选课关系SC（S，C，GRADE）。要查询选修“Computer”课的男生姓名，将涉及到关系 。 A. S B. S，SC C. C，SC D. S，C，SC 19. 专门的关系运算不包括下列中的 。A. 连接运算 B. 选择运算 C. 投影运算 D. 交运算20. n 个顶点的连通图至少有 条边。 A、n-1 B、n C、n+1 D、0二、 填空题 (每空1分，共20分) 得分评阅人 1.算法的复杂度包括 和 两个方面。2.栈是一种 的线性表；而队列是一种 的线性表。3.数据库中三种基本的数据模型是： 、 和 。4. 在线性表的散列存储中，处理冲突有 和 两种方法。5. 操作系统中利用P/V操作可实现进程的 和 。6. 数据的 结构与数据元素本身的内容、形式、个数和相对位置无关。7.一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个_ _。8、数据的存储结构有四种基本的存储映射方式：顺序 、索引和 存储方式。9、进程具有 、并发性和 三个基本特征。10、死锁的四个必要条件是_、_、不可抢夺资源和_ _ 。三、 简答题 (每小题5分，共20分) 得分评阅人 1. 关系代数中包括哪些集合运算和专门的关系运算。2.简述快速排序的基本思想。3.什么是虚拟存储技术？4. 从宏观上看，操作系统有哪几个主要功能？。四、 应用题 (每小题5分，共20分) 得分评阅人 1.求右图所示二叉树的前序和中序遍历的结点序列。2.一座山上有一个隧道，规定每次只允许一辆汽车通过，现在遂道两端都有车辆要过遂道。如果把每辆过遂道的汽车看作一个进程，为保证安全，请用PV操作实现正确管理。（同时说明信号量的初值）3. 输入一个正整数序列40，28，6，72，100，3，54，1，80，91，38, 建立一棵二叉排序树，然后删除结点80，分别画出该二叉排序树和删除结点80后的二叉排序树。4. 根据如下的“教师”表，用SQL语句完成下面的问题：职工号姓名职称年龄工资11020011102002110200311020041102005肖海天王远刘星李名玉孙明山副教授教授讲师教授教授354030455520003000120035004000（1）用SQL语句向教师表中插入一条记录：（1102006，张平，副教授，38，1500）（2）查询所有职称为教授的教师信息（3）用SQL语句完成：将所有职称为教授的教师的工资