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

南昌大学 20052006学年第 2 学期期末考试试卷 试卷编号： ( A )卷课程名称： 计算机软件技术基础 适用班级： 电子04级、通信04级 姓名： 学号： 班级： 专业： 学院： 系别： 考试日期： 2005.06.24 题号一二三四五六七八九十总分累分人 签名题分2020202020 100得分一、 单项选择题 (每小题1分，共20分) 得分评阅人 1. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 。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以行为主顺序存放压缩矩阵A，则A43存放在 中A. B7B. B8C. B9D. B105. 按照二叉树的定义，具有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. 下列关于算法的基本特征，说法不正确的是 。A. 能行性是算法中的每一个步骤必须能够实现且能达到预期的目的。B. 算法的确定性是指算法中的每一个步骤必须是有明确的定义，不允许模棱两可。C. 算法的有穷性是指算法必须能在有限的时间内做完。D. 算法与提供情报无关。12 下列说法不正确的是 。A. 线性表可以顺序存储 B. 线性表可以链式存储C. 线性表在顺序存储下可以对分查找 D. 线性表在链式存储下可以对分查找13与数据元素本身的形式、内容、相对位置及个数无关的是数据的 。A存储结构 B存储实现C逻辑结构 D运算实现14正在运行的进程在信号量S上作P操作之后，当S0，进程进入信号的 。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. 子模式，概念模式，用户模式20. 进程和程序的本质区别在于 。A独占与共享资源 B串行和并行C可重定位与不可重定位 D动态与静态二、 填空题 (每空1分，共20分) 得分评阅人 1.算法的复杂度包括 和 两个方面。2.栈是一种 的线性表；而队列是一种 的线性表。3.进程的三种基本状态是 、 和 。4. 若一棵二叉树有30个叶子结点，仅有一个孩子的结点有20个， 则这棵二叉树共有 个结点；若一棵完全二叉树共有100个结点，则其叶子结点数为 。5.数据库中三种基本的数据模型是 、 、 和 。6.在学校教务信息中，实体班级与实体班长的联系是 、而实体教研室与实体教师的联系是 、而实体学生与实体课程的联系是 。7、系统中各进程间必须协调且相互制约，这种协调和制约关系主要表现在两个方面： 一是进程之间的 ；二是进程之间的 。8、系统中不能同时提供给两个或两个以上进程使用的资源称为 。 9、批处理操作系统在作业运行过程中， 的内容反映了作业的运行情况，并且是作业存在的唯一标志。10、数据的 结构与数据元素本身的内容、形式、个数和相对位置无关。三、 简答题 (每小题4分，共20分) 得分评阅人 1. 什么是死锁？产生死锁的必要条件是什么？2. 简述二叉树与树的定义，并描述二者的异同。3. 简述数据库管理系统的主要功能。4简述归并排序的基本思想。5. 简述作业调度的5种常用的调度算法。四、 应用题 (每小题5分，共20分) 得分评阅人 1写出如下图所示图G的求值矩阵 。2. 输入一个正整数序列56，78，34，45，85，58，36，92，84，78, 建立一棵二叉排序树，然后删除结点54，分别画出该二叉排序树和删除结点36后的二叉排序树。3. 两个进程共用一台打印机，请用PV操作实现打印机的正确管理，保证两个进程的输出正确。（同时说明信号量的初值）4. 已给关系R和S，求它们的自然连接R | S。 关系R关系SABCAxy111213171312141516253643171819546875五、 算法设计题（每小题10分，共20分）得分评阅人 1（10分）已给一个带表头结点的单链表head，它含有重复结点，即它