计算机软件基础(2010年考试试题讲解)(自考本科)

计算机 软件基础,2010年考试试题讲解,一、单项选择题,1. 已知int x = 17 , y = 5 ; , 则表达式 x / y 的值是（ ）,A. 0 B. 2C. 3 D. 3.4,答题要点：两个整数相除，商为整数。,答 案：C,一、单项选择题,2. 已知int x = 3 , y = 5 , z = 7 ; , 则表达式 x y ? x : ( y z ? y : z)的值是（ ）,A. 0 B. 3C. 5 D. 7,答题要点：表达式1 ？表达式2 ：表达式3 ；,答 案：D,一、单项选择题,3. 执行下列C语言程序段，循环体被执行的次数是（ ）,A. 2 B. 3C. 4 D. 无限,答 案：c,for ( i = 0 , j = 0 ; ( j != 4 ) | ( i num B. * pp - numC. ( * pp ) - num D. ( * pp ) . num,则对结构变量成员正确的引用是（ ）,一、单项选择题,答题要点：结构变量的引用问题。,(1) - 符号前面必须是某结构类型指针；,(2) . 符号前面必须是某结构类型变量或某结构类型指针所指的变量；,一、单项选择题,8. 若入栈数据元素序列是 a , b , c , d , 则不可能的出栈序列是（ ）,答 案：D,A. a , b , c , d B. c , b , a , dC. d , c , b , a D. d , b , c , a,答题要点：原序列中最后一个元素最先出栈时，所有元素的出栈顺序必须与原序列相反，否则，是不可能的。,一、单项选择题,9. 对100个有序数据，若采用二分法查找某一个元素，比较次数最多是（ ）,答 案：B,A. 6 B. 7C. 8 D. 100,答题要点：构建一棵判定树,一、单项选择题,10. 线性表采用链式储时，其存储空间（ ）,答 案：C,必须是连续 B. 一定是不连续的可连续，也可不连续 D. 多个节点地址必须是连续的,一、单项选择题,11. 对顺序存储的线性表，其长度为 n ，在等概率情况下，插入一个元素需要移动元素的平均次数是（ ）,答 案：A,A. n/2 B. n-1C. (n+1)/2 D. (n-1)/2,一、单项选择题,12. 一个深度为k的完全二叉树中节点数至少有（ ）,答 案：B,A. 2k B. 2k-1C. 2k+1 D. 2k -1,答题要点：p160二叉树的性质 2 和满二叉树的定义。,一、单项选择题,13. 对 n 个元素进行直接插入排序时，最多需要进行的趟数是（ ）,答 案：B,A. n B. n-1C. n+1 D. 2n,一、单项选择题,14. 下列 C 语言程序段的时间复杂度是（ ） for ( i = 1 ; i = n ; i + ) y = y + 1 ; for ( j= 1 ; j = 2 *n ; j+ ) x = x + 1 ; ,答 案：B,A. O ( 2 n ) B. O ( n2 )C. O ( n3 ) D. O (n ),答题要点：两重for循环,一、单项选择题,15. 软件编码属于软件生存周期的（ ）,答 案：D,A. 软件定义时期 B. 软件维护时期C. 软件运行时期 D. 软件开发时期,二、填空题,16. 已知int a = 1 , b = 2 , d ; , 执行语句d = a 0b next = q - next ;,q - next = s ;,p,P-next,s,(1),s-next=p-next;,(2),p-next=s;,二、填空题,22. 若循环队列用数组 data m 存储元素值，用front 和 rear 分别作为头、尾指针，则判断循环队列空的条件是（ ）,front=rear,二、填空题,23.已知二叉树的后序遍历序列是dabec,中序遍历序列是debac，它的前序遍历序列是（ ）,cedba,答题要点：,记住口诀：,答题关键：,由给定条件构建二叉树。,c,e,d,b,a,二、填空题,24.一个无向连通图G中顶点数为n，图G的边数最少是（ ）,n-1,答题要点：,记住连通图的必要条件：,一个具有n个顶点的连通图，则至少有n-1条边。,二、填空题,25.在软件设计时期，设计模块独立性的一般度量准则是耦合和（ ）,内聚,答题要点：,课本P217,三、解答题,26.已知下图所示的二叉树，要求： （1）将该二叉树还原成森林； （2）写出森林的先序（先根）遍历序列和后序（后根）遍历序列,解（1）将该二叉树还原成森林:,解（1）将该二叉树还原成森林（续）：,竖线变成左子树，横线变成右子树,解（1）将该二叉树还原成森林（续）：,口诀：竖线连接左孩子，横线连接亲兄弟。,解（2）先序遍历序列：abdgcefhij,后序遍历序列：bgdaecihjf,森林的先序遍历=对应二叉树的先序遍历;,森林的后序遍历=对应二叉树的中序遍历;,注意：,三、解答题,27.如下图所示的无向图，从顶点1开始，分别按邻接顶点序号由小到大顺序给出广度优先遍历和深度优先遍历的顶点序号。,广度优先遍历结果：,1，2，3，7，4，5，6,深度优先遍历结果：,1，2，4，5，6，3，7,三、解答题,28.已知一组关健字 49，31，12，68，27，要求对其按升序排序，写出使用直接选择排序的每趟结果。,三、解答题,29.某大学图书馆对读者借阅读书制定有关规定如下：（1）本科学生可以借阅5本； （2）研究生：硕士研究生可以借阅7本，博士研究生可以借阅10本； （3）教职工：教授、副教授职称的教师可以借阅15本，其他教职工可以借阅12本。 用判定树表示上述算法。,四、程序分析题,30.写出下列C语言程序的运行结果 main ( ) int a = 7 ; do switch ( a % 2 ) case 1 : a- ; break ; case 0 : a+ ; break ; a- ; printf ( “ % 5d n ” , a ) ; while ( a 0 ) ; ,四、程序分析题,30.解：,四、程序分析题,31.运行下列C语言程序，从健盘上输入数字5，写出程序的输出结果,int fun ( int n ) static int f = 1 ; int k; for ( k = 1 ; k = n ; k+ ) f *= k ; return f ;main( ) int n , i ;,scanf ( “ %d “ , ,四、程序分析题,31.解：,四、程序分析题,31.解：,四、程序分析题,31.解：,四、程序分析题,31.解：,31、答题要点,四、程序分析题,32. 下列程序是求一个有规律的数值序列：1，1，2，4，7，13，从第4个数开始，每一个数都是它前边3个数的和，一直求到该数列的第n（4n18）个数，填空完成程序,main () int i=3, n, a=1,b=1,c=2,d; scanf(“%d”, ,c =d,in,四、程序分析题,33. 已知顺序栈的结构为： #define N 100 struct char data N; int top; s ; 利用顺序栈的基本操作（设push (s, x)和pop (s)函数已存在，pop (s)函数返回栈顶元素），设计一个算法如下，判断一个字符串是否具有中心对称（即构成回文），若是则返回1，否则返回0。如：ababbaba、abcba都是中心对称的字符串。填空完成算法。,四、程序分析题,int symmetry (char str ) int i, j, k; i=strlen (str); for (j=0; ji/2; j+) ; if ( i % 2 ! = 0 ) k= ( i+1) /2 else k=i/2; for (j=k; j 10时,当 | x | 10时,当 x 10 )y = sin ( x ) * sin ( x