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

公共计算机基础教学部本科生 2009－2010学年第二学期《软件基础》课程期末考试试卷A 学院： 专业（班级）： 学号： 姓名： 成绩： 题 目 一 二 三 四 卷面成绩 分 数 得 分 一 、单项选择题（本题共35分，每小题1分） （答案必须写在本题后的答题卡内，否则无效） 1.算法的时间复杂度是指（ ）。 A）执行算法程序所需要的时间 B）算法程序中的指令条数 C）算法执行过程中所需要的基本运算次数 D）算法程序的长度 2. 下面程序段的时间复杂度为（ ）。 int i=0,s1=0,s2=0; while(in) { if(i%2) s1+=i; else s2+=i; i++; } A）O(1 ) B）O( ) C）O(n ) D）O(n2) 3. 通常用平均性态分析和（ ）两种方式来确定一个算法的工作量。 A）最坏情况复杂性 B）最好情况复杂性 C）次好情况复杂性 D）次坏情况复杂性 4. 在数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A）逻辑 B）存储 C）逻辑和存储 D）物理 5. 如果一个非空的数据结构满足两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为（ ）。 A）线性结构 B）非线性结构 C）物理结构 D）逻辑结构 6. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。 A）数据元素具有同一特点 B）不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C）每个数据元素都一样 D）数据元素所包含的数据项的个数要相等 7. 利用数组a[N]顺序存储一个栈时，用top表示栈顶指针，用top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作是（ ）。 A）a[--top]=x; B）a[top--]=x; C）a[++top]=x; D）a[top++]=x; 8.若让元素1，2，3依次进栈，则出栈次序不可能出现（ ）的情况。 A）3，2，1 B）2，1，3 C）3，1，2 D）1，3，2 9. 假设一个链队列的队头指针和队尾指针分别为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; 10. 在一棵具有n个结点的二叉树的第i层上，最多具有（ ）个结点。 A）2i B）2i-1 C）2i -1 D）2n 11. 在一棵完全二叉树中，根节点的编号为1，按照由上到下由左到右的顺序为二叉树节点编号。若编号为i的结点存在右孩子，则右孩子结点的编号为（ ）。 A）2i - 1 B）2i C）2i+2 D）2i+1 12. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（ ）。 A）发生改变 B）不发生改变 C）不能确定 D）以上都不对 13. 对线性表进行折半查找的前提条件是（ ）。 A）线性表以顺序方式存储，并且按关键字的查找频率排好序 B）线性表以顺序方式存储，并且按关键字的大小排好序 C）线性表以链式方式存储，并且按关键字的大小排好序 D）线性表以链式方式存储，并且按关键字的查找频率排好序 14. 在对n个元素进行冒泡排序的过程中，第一遍排序，最多需要进行（ ）对相邻元素之间的交换。 A）n-1 B）n C）n/2 D）n+1 15. 在对下列四个序列进行快速排序时，各以第一个元素为基准进行第一遍划分，则在该次划分过程中，需要移动元素次数最多的序列为（ ）。 A）1，3，5，7，9