09-10学年第二学期软件基础试卷B.docVIP

公共计算机基础教学部本科生 2009－2010学年第二学期《软件基础》课程期末考试试卷B 学院： 专业（班级）： 学号： 姓名： 成绩： 题 目 一 二 三 四 卷面成绩 分 数 得 分 一 、单项选择题（本题共35分，每小题1分） （答案必须写在本题后的答题卡内，否则无效） 1.算法的时间复杂度是指（ ）。 A）执行算法程序所需要的时间 B）算法程序中的指令条数 C）算法执行过程中所需要的基本运算次数 D）算法程序的长度 2. 在数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A）物理 B）存储 C）逻辑和存储 D）逻辑 3. 如果一个非空的数据结构满足两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为（ ）。 A）线性结构 B）非线性结构 C）物理结构 D）逻辑结构 4. 下面程序段的时间复杂度为（ ）。 int i=0,s=0,s1=0; while(in) { if(i%2) s+=i; else s1+=i; i++; } A）O(n ) B）O( ) C）O(1 ) D）O(n2) 5. 通常用平均性态分析和（ ）两种方式来确定一个算法的工作量。 A）最坏情况复杂性 B）最好情况复杂性 C）次好情况复杂性 D）次坏情况复杂性 6.若让元素1，2，3依次进栈，则出栈次序不可能出现（ ）的情况。 A）3，2，1 B）3，1，2 C）2，1，3 D）1，3，2 7. 假设一个链队列的队头指针和队尾指针分别为front和rear，每个结点由一个数值域data和一个指针域next构成，当出队时，所进行的指针操作为（ ）。 A）front=front-next; B）front-next=rear;rear=rear-next; C）rear=rear-next; D）front=front-next;front-next=rear; 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。 A）不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 B）数据元素具有同一特点 C）每个数据元素都一样 D）数据元素所包含的数据项的个数要相等 9. 利用数组a[N]顺序存储一个栈时，用top表示栈顶指针，用top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作是（ ）。 A）a[--top]=x; B）a[top--]=x; C）a[top++]=x; D）a[++top]=x; 10. 在对下列四个序列进行快速排序时，各以第一个元素为基准进行第一遍划分，则在该次划分过程中，需要移动元素次数最多的序列为（ ）。 A）1，3，5，7，9 B）9，7，5，3，1 C）5，3，1，7，9 D）5，7，9，1，3 11. 通常所说的数据库系统（DBS）、数据库管理系统（DBMS）和数据库（DB）三者之间的关系是（ ）。 A）DBMS包含DB和DBS B）DBS包含DB和DBMS C）DB包含DBS和DBMS D）三者都不对 12. 为了使数据库在内模式改变时保持模式不变，从而不必修改应用程序，必须通过改变模式与内模式之间的映像来实现，使数据库具有( )。 A）数据独立性 B）逻辑独立性 C）物理独立性 D）操作独立性 13. 关系模式中下列各级模式的要求由不严格到严格分别为( )。 A）3NF、2NF、1NF B）3NF、1NF、2NF C）1NF、2NF、3NF D）2NF、1NF、3NF 14. E-R图中的实体、属性通常用相应的( )表示。 A）矩形、椭圆形 B）矩形、菱形 C）椭圆形、矩形 D）椭圆形、菱形 15. 概念模型独立于________。 A）E-R模型