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

南昌大学 20062007学年第 1 学期期末考试试卷 试卷编号： 信9 ( A )卷课程编号： X61050001 课程名称： 计算机软件技术基础 考试形式： 闭卷 适用班级： 生物医学04级 姓名： 学号： 班级： 学院： 专业： 考试日期： 2007.01.15 题号一二三四五六七八九十总分累分人 签名题分2020202020 100得分一、 单项选择题 (每小题1分，共20分) 得分评阅人 1. 下列数据结构中，能用二分法进行查找的是 A. 顺序存储的有序线性表 B. 线性链表C. 二叉链表 D. 有序线性链表2若进栈序列为1、2、3、4(进栈过程可以出栈)，不可能得到的出栈序列是 。 A. 1432 B. 2341 C. 3142 D. 3421 3用数组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下列进程状态的转换中，不正确的是 A就绪运行 B运行就绪 C就绪等待 D等待就绪6. 深度为5的二叉树至多有 个结点。A. 16 B. 32 C. 31 D. 107. 对于下三角矩阵A，若采用一个一维数组B以行为主顺序存放压缩矩阵A，则A3,3存放在 中A.B5B.B6C.B7D.B88. 一个有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. 设关键码序列为（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） 12 SQL是那几个英文单词的缩写 。A. Standard Query Language B. Structured Query Language全国计算C. Select Query Language D. 以上都不是13目前较有影响的数据库，如Oracle 、SQL Server、Visual Foxpro等，基于的数据模型是 。 试A. 层次模型 B. 关系模型 C. 网状模型 D. 混合型14正在运行的进程在信号量S上作P操作之后，当S0，进程进入信号的 。A. 就绪队列 B. 提交队列 C. 后备队列 D. 等待队列15下列关于栈的描述正确的是 。A. 在栈中只能插入元素而不能删除元素B. 在栈中只能删除元素而不能插入元素C. 栈是特殊的线性表，只能在一端插入或删除元素D. 栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素16用链表表示线性表的优点是 。 A、花费的存储空间比顺序表少 B、便于随机存取C、数据元素的物理顺序与逻辑顺序相同 D、便于插入与删除17在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码值11，所需的关键码比较次数为 。 A. 2 B. 3 C. 4 D. 5 18学生关系模式 S（ S，Sname，Sex，Age），S的属性分别表示学生的学号、姓名、性别、年龄。要在表S中删除一个属性“年龄”，可选用的SQL语句是 。 A. DELETE Age from S B. ALTER TABLE S DROP Age C. UPDATE S Age D. ALTER TABLE S Age19. 关系代数中的联接操作是由 操作组合而成 。 A. 选择和投影 B.选择和笛卡尔积 C.投影、选择、笛卡尔积 D.投影和笛卡尔积 20. 进程和程序的本质区别在于 。A独占与共享资源 B串行和并行C可重定位与不可重定位 D动态与静态二、 填空题 (每空1分，共20分) 得分评阅人 1. 算法的基本特征有能行性、 、有穷性和 。2. 结点最少的树为 ，结点最少的二叉树为 。3.进程的三种基本状态是 、 和 。4. 在操作系统中，PCB的中文意思是指 ，而JCB是指 。5. 系统中各进程间必须协调且相互制约，这种协调和制约关系主要表现在两个方面： 一是进程之间的 ；二是进程之间的 。6. 一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有_子女。7、从某个给定的关系中选出满足条件的元组的一元关系运算是 。8、数据的存储结构有四种基本的存储映射方式：顺序、 、 和散列存储方式。9、进程具有 、 和异步性三个基本特征。10、在学校教务信息中，实体班级与实体班长的联系是 、而实体教研室与实体教师的联系是 、而实体学生与实体课程的联系是 。三、 简答题 (每小题5分，共20分) 得分评阅人 1. 什么是死锁？产生死锁的必要条件是什么？2. 简述冒泡排序的基本思想3. 试比较常用的三种检索方法-顺序检索、二分法检索和分块检索，在检索速度和对表的要求方面的不同。4. 简述进程的3种基本状态，并说明各状态之间的转换关系。四、 应用题 (每小题5分，共20分) 得分评阅人 1 要在单链表中的p所指结点之后插入一个结点q,如下图所示，请写出所执行的操作。 2. 写出如下图所示的二叉树按前序和中序遍历的结点序列。3. 已知某二叉树的先序和中序序列如下：先序序列：ABDCEFG中序序列：DBCAFGE请画出这棵二叉树。4. 给定以下关系R,S和T