07-08学年第二学期软件基础试卷B.docVIP

公共计算机基础教学部本科生 2007－2008学年第二学期《计算机软件基础》期末考试试卷B 任课教师： 学院： 专业： 学号： 姓名： 题 目 一 二 三 四 卷面成绩 分 数 得分 一、填空题（本题共30分，每小题2分） （答案必须写在本题最后的答题卡内，否则无效） 1. 一个算法的时间复杂度的计算式为 ( 3n4+2n+5 ) / n ，其数量级表示为 。 2. 在单链表中指针p所指结点的后面，插入一个指针q所指的结点时，首先把p-next的值赋给q-next，然后把 的值赋给p-next。 3.假设一个链栈的栈顶指针为top，每个结点包含值域data和指针域next，当p所指向的结点入栈时，则首先执行 操作，然后执行top=p操作。 4.一种数据结构的元素集合为D，它在D上的二元关系R为： D={a,b,c,d,e,f,g,h} R={d,b,d,g,b,a,b,c,g,e,g,h,e,f} 则该数据结构具有 结构。 5.已知一棵二叉树的中序和后序遍历序列如下： 中序遍历序列：D，B，A，E，C, F 后序遍历序列：D，B，E，F, C，A 则其先序遍历序列为： 。 6. 若对一组记录（46，79，56，38，40，84）进行冒泡排序，则进行第二遍排序的结果为 。 7.以下语句的输出结果是 。 s$ = Print Mid(s, 3, 4) 8.有下列语句 a = InputBox(请输入一个整数)b = InputBox(请输入一个整数)Print a + b 运行后输入168和结果为 二、单项选择题（本题共35分，每小题1分） （答案必须写在本题后的答题卡内，否则无效） 1. 一个数据结构可形象地表示成B=(D,R)，其中D是数据元素的有限集合，R是D上的（ ）有限集合。 A）关系 B）映像 C）存储 D）操作 2. 以下关于线性表的链式存储结构的叙述中，正确的是（ ）。 A）结点存储较少的信息 B）逻辑上相邻的结点物理上不必相邻 C）可以通过计算直接确定第i个结点的存储地址 D）插入、删除运算操作不方便 3. 下列叙述中正确的是（ ）。 A）线性表是顺序结构 B）栈与队列是链式结构 C）线性链表是线性结构 D）树是线性结构 4. 在一个顺序循环队列中，队尾指针指向队尾元素的（ ）位置。 A）前一个 B）后一个 C）当前 D）最后 5. 在一棵树中，每个结点最多可以有（ ）个后件结点。 A）0 B）1 C）2 D）任意多 6.算法执行过程中所需要的基本运算次数是（ ）。 A）执行算法程序所需要的时间 B）算法程序中的指令条数 C）算法的时间复杂度 D）算法程序的长度 7.下面（ ）的时间复杂度最好。 A）O() B）O(n ) C）O(n ) D）O(n2)A） B） C） D） 模型是对现实世界的抽象，在数据库技术中，用模型的概念描述数据库的结构与语义，对现实世界进行抽象。表示实体类型及实体间联系的模型称为()。数据模型 B）概念模型C）逻辑模型 D）物理模型在B）一个指针 C）一条记录 D）一张二维表 15. 通常E-R图中的实体、属性、联系，依次用（ ）表示。 A）矩形、菱形、椭圆形 B）椭圆形、矩形、菱形 C）矩形、椭圆形、菱形 D）椭圆形、菱形、矩形 16. 在一棵深度为k的完全二叉树中，所含结点个数不大于（ ）。 A）2k-1 B）2k+1 C）2k –1 D）2k 17. 在一棵完全二叉树中，若编号为i的结点存在左孩子，则左孩子结点的编号为（ ）。 A）2i - 1 B）2i C）2i+2 D）2i+1 18. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（ ）。 A）不能确定