计算机软件基础 自考历年试题.doc

计算机软件基础 02243题型概述 1.单项选择题（共15小题，每题2分，共30分）2.填空题（共10小题，每题2分，共20分）3.解答题（共4小题，每题4分，共16分） 4.程序分析题（共4小题，每题4分，共16分） 5.程序设计题（共2小题，每题9分，共18分）2008年试题解析一、单选题1、下列与k=n+完全等价的表达式是 CA. K=+n B. K+=n+1C. K=n,n=n+1 D. n=n+1,K=n2、已知int a=5,b=3,*p=&b,*q=&a；下列赋值语句中与b=a等价的语句是 AA. *p=*q; B. p=q;C. *p=&q; D. *p=*b;3、已知C语言函数fun（）的定义形式为void fun(char ch,float x)则正确调用fun()的语句是 DA. fun(“a”,3.0); B. fun(ab,19.5);C. t=fun(z,3.6); D. fun(65,3);4、已知char sr20;int i；从键盘向数组sr输入一字符串的正确语句是 AA. gets(sr); B. gets(sr20);C.for(i=0;i20;i+)scanf(sr); D. for(i=0;i20;i+)gets(&sr)5、执行下列C语言程序段，循环结束的条件是 int n=0,p,sum=0;doscanf(“%d”,&p);n+;sum+=p;while(sum!=126&nf8.下列程序是计算两个矩阵的乘积，其算法的时间复杂度是 Dvoid mul_matrix(int n,int a5,int b5,int c5)int i,j,k,x; for(i=0;in;i+) for(j=0;jn;j+) x=0; for(k=0;knext=head D. head-next=NULL10、一个栈的进栈数据元素序列为1、2、3、4、5，则不可能为栈的出栈序列的是 DA. 2、3、4、1、5 B. 1、5、4、3、2C. 2、3、1、4、5 D. 5、4、1、3、211、一棵二叉树的先序遍历序列为ABCD,中序遍历序列为CBAD,则后序遍历序列是 CA. BCDA B. BCAD C. CBDA D. ABDC12、在具有n个顶点、e条边的无向图的邻接表中，所有边的链表中边节点的总数是 CA. e/2 B. e C. 2e D. 2e+n13、已知一个有序表为（12,18,24,35,47,50,62,83,90,115,134),用折半查找法查找值为90的元素时，查找成功所使用的比较次数是 BA. 1 B. 2 C. 3 D. 414、当待排序序列中记录的关键字基本有序或记录个数较少时，则最好的排序方法是 DA. 基数排序 B.冒泡排序C. 直接选择排序 D. 直接插入排序15在瀑布模型中，将软件划分为若干个阶段，软件项目的需求分析一般属于 BA. 维护阶段 B. 开发阶段C. 运行阶段 D.计划阶段二、填空题16、数学式“30y30 &y5017、已知int k,x;则语句for(k=0,x=0;kprior=q-prior;t-next=q; q-prior-next=t; q-prior=t;22、设有一个10X10的对称矩阵A，采用下三角压缩存储方式，以行序为主，A00的存储地址为100，每个元素占一个地址空间，则A32的地址是 10823、在有向图中，以顶点V为终点的边的数目称为V的入度24、将一棵有100个节点的完全二叉树从根这一层开始，每一层从左到右依次对节点进行编号，根节点的编号为1，则编号为49的节点的左孩子的编号是 9825、软件工程包含三个要素，分别为 方法、 工具 和过程。三、解答题26、用盒图（N_S图）画出结构化程序的三种基本结构。27、对于图G-1(1)从顶点1出发，按邻接顶点序号由小到到顺序给出广度优先遍历的顶点序列。(2)给出用克鲁斯卡尔法构造的最小生成树27、 (1)从顶点1出发，按邻接顶点序号由小到到顺序给出广度优先遍历的顶点序列。广度优先遍历序列：1、2、5、6、7、3、4广度优先遍历：尽可能先对横向进行遍历，先访问的节点其邻接点也最先被访问。先访问1的横向邻接点：2、5、6、7再访问2的邻接点3、4(2)给出用克鲁斯卡尔法构造的最小生成树克鲁斯卡尔法构造的最小生成树的思路：应不断找出权值最小的边，逐个连同各边，不形成回路。（1，6）（2，3）（1，7）（7，6回路）（2，4）（2，5）28、假设字符a,b,c,d,e,f使用频率分别是0.07，0.09，0.13，0.21，0.23，0.27，构造哈夫曼编码树（权值小的为左子树，权值大的为右子树），并根据哈夫曼编码树写出a,b,c,d,e,f的哈夫曼编码。1.权值由小到大排序。2.取出两个最小的权值Wi和Wi+1构造二叉树。其中：W= Wi + Wi+13.从权值序列中划去Wi和Wi+1.若序列空，则哈夫曼树已形成；否则，将W加入权值序列，反复作1-3.1)权值序列为0.07，0.09，0.13，0.21，0.23，0.270.07+0.09=0.162)权值序列为0.13，0.16，0.21，0.23，0.27 0.13+0.16=0.293)权值序列为0.21，0.23，0.27，0.29 0.21+0.23=0.444)权值序列为0.27，0.29，0.44 0.27+0.29=0.565)权值序列为0.44，0.560.44+0.56=1 28、假设字符a,b,c,d,e,f使用频率分别是0.07，0.09，0.13，0.21，0.23，0.27，构造哈夫曼编码树（权值小的为左子树，权值大的为右子树），并根据哈夫曼编码树写出a,b,c,d,e,f的哈夫曼编码。哈夫曼编码a:1110b:1111c:110d:00e:01f:1029、已知一数值序列为33，61，12，75，8，54，41，请分别写出按升序进行排序时，直接选择排序、直接插入排序第一趟结束后的数值序列。直接选择排序:8，61，12，75，33，54，41直接插入排序:33，61，12，75，8，54，41直接选择排序:将未排好序的序列中的最小元素依次放到已排好序的序列的一端。直接插入排序:从未排序序列中依次取出元素与已排序序列（初始有一个元素）中的元素进行比较，将其放入已排序序列的正确位置。四、程序分析题30、写出下列程序的运行结果。main()int j,a5=10,11,12,13,14,*p=&a1;for(j=1;j5;j+)if(j%2)printf(“%5d”,aj); else continue; printf(“%5dn”,*p+);11 1112 1231、写出下列程序的运行结果。fun(int a)static int x=5; int y=0,t; x+;y+; t=a+x+y; return(t);main()int a=2,b=3; printf(“%dn”,fun(a); printf(“%dn”,fun(b);91132、下面程序的功能是：将有15个数据元素的整型数组的最大值与末元素对调后输出，填空完成程序。main()int x5,max,n,i; for (i=0;i15;i+) scanf(“%d”,&xi); max=x0;n=0;for(i=1;i15;i+)if( maxximax=xi; n=i;xn=x14; x14=maxfor(i=0;ihead=Q-tail） return 0；*e=Q-dataQ-head; Q-head= (Q-head+1)%100 return 1;五、程序设计题34、编写C语言程序实现：从键盘上输入10个学生某门课的成绩，计算平均成绩，统计并输出所有高于平均分的学生成绩及人数。main()int i,n=0; float x10,av=0; for(i=0;i10;i+) scanf(%f,&xi); av=av+xi; av=av/10; for(i=0;iav) n+;printf(%7d.2fn,xi); printf(%dn,n); 35、设一棵二叉树以二叉链表来存储，节点结构为：LchilddataRchild定义此存储结构的数据类型，用C语言编写一个递归函数，计算此二叉树上度为1的节点个数typedef struct nodeint data; struct node *Lchild,*Rchild;NODE;void leaf(NODE *root)if(root!=NULL) if(root-Lchild!=NULL&root-Rchild=NULL)|(root-Lchild=NULL&root-Rchild!=NULL) n=n+1; leaf(root-Lchild); leaf(root-Rchild); 2009年试题解析一、单选题1、下列合法的C语言标识符是 CA. static B. 3abcC. abc_2 D. am&1C语言规定，变量名只能由字母、数字和下划线三种字符组成，且第一个字符必须为字母或下划线。static是关键字，3abc的第一个字符为数字，am&1多了一个字符&。2、已知int b=4；执行语句b+=b+;后，b的值是 BA. 8 B. 9 C. 10 D. 11b+=b+等价于b=b+(b+),b+意思是在使用b之后，b的值加1，所以b=b+(b+)=5+4=9。3、C语言表达式4！=3&2&4+15的值是 AA. 0 B. 1 C. 2 D. 3优先顺序由高到低：+、!=、&。表达式先计算4+1=5，55不成立，所以第二个&的右侧为0，4!=3成立,即表达式1&2&0的结果为0。4、已知int a100,*d=a;下列错误的语句是 AA. a=d; B. *d=a10;C. d=a+1; D.d=&a2;5、已知int i,s;下列不能实现计算 的程序段是 CA. for(i=1,s=0;i=100;i+)s+=i;B. s=0;for(i=1;i=100;)s=s+i+;C. i=1;s=1;while(i=100)s=s+i;i+;D. i=2;s=1;while(i=100)s=s+i;i+;6、下列叙述正确的是 BA. While语句的循环体至少执行一次B. do-while语句的循环体至少执行一次C. do-while语句的循环体不能是符合语句D. Continue语句能够从循环体内转到循环体外while语句循环可以一次也不执行；d0-while语句的循环体可以是符合语句，break语句能够从循环体内转到循环体外。7、已知char str130,*str2=“student_no”;执行语句strcpy(str1,str2);后，strlen(str1)的值是 BA. 9 B. 10 C. 29 D. 30strcpy(st1,str2):将str2的内容复制到str1中，strlen（str1）：求字符数组所表示串的长度。8.下列语句正确的是 CA. Char s5;s=“abc”; B. Char s5=“abcxyz”;C. Char s=“12345”; D. Char s5=1,2,3,4,5,0;选项A：C语言中没有存放字符串常量的变量，所以s=“abc”；赋值不正确。选项B、D：数组越界。9、下列算法的时间复杂度是 Dfor（int i=1;j=n;i+)for(int j=1;jnext=s-next;s-next=p; B. s-next=p;q-next=s-next;C. p-next=s-next;s-next=q D. s-next=q;p-next=s-next;插入p时，首先将最后一个节点的下一个节点q-next指向s-next,最后将s-next指向第一个节点p。即选项A操作正确。 11、按照1、2、3、4、5的次序依次入栈时，不可能的出栈序列是 DA. 1、2、3、4、5 B. 2、3、4、5、1C. 5、4、3、2、1 D. 5、4、1、2、3若5先出栈，出栈的顺序只能是5、4、3、2、1，1在2、3的前面出栈是不可能的。12、一棵二叉树的先序遍历序列为ABCDE,中序遍历序列为BADCE,则后序遍历序列是 AA. BDECA B. BCADEC. ECBDA D. ABDCE13、下列程序的运行结果是 Cint x=1int fun(int a)static int b=1; b+=a+x; return b;main()int i=2; for(i=0;iage15、黑盒法用在软件开发过程中的 DA. 软件定义阶段 B. 软件设计阶段C. 软件编码阶段 D. 软件测试阶段软件测试方法有黑盒测试和白盒测试。所以黑盒法用在软件测试阶段。二、填空题16、已知int a;,表达式(a=4,a*=2),a+6)的值是 1417、已知int a=6,b=5,c=4;,表达式ab? (ac? a:c)(bc? b:c)的值是 418、已知字母A的ASCII码为65，下列程序段的输出结果是 68Char c=D；Printf（“%d”，c）；19、已知int n=3,k=3;,执行语句n%=k+1；后，n的值是 320、二维数组A1010采用以行为主序的方法存储，每个元素占4个存储单元，设A00的存储地址是1000，则A85的存储地址是 134021、在具有m个节点的循环队列中，头指针为front，尾指针为rear,判断循环队列满的条件是 front=(rear+1)%m循环队列空的条件是：front=rear,满的条件是：front=(rear+1)%m,用牺牲一个空间(f所指空间)的方法来解决当,front=rear时，循环队列既空又满的矛盾。22、已知一个有序表1,4,9,13,32,41,54,62,75,77,87,95,100,用折半法查找关键字值15时，查找不成功的比较次数是 4第一次折半15与54比较，1513,接着在后半部分找,第三次折半15与41比较，1541,接着在前半部分找,第四次折半15与32比较，1532,查找结束。23、实现递归算法所需的数据结构是 栈2i-1 栈在递归的执行中起两点作用：1、保存返回地址；2、保存调用时各个量的值（保护现场）24、二叉树的第i（i1）层上最多的节点数是二叉树的性质1、二叉树第i（i1）层上最多有2i-1个节点2、深度为k的二叉树最多有2k-1个节点3、任意一棵二叉树中，若叶子节点个数为n0，度为2的节点个数为n2,则n0=n2+125、软件生存周期由软件定义、软件开发和 软件维护 三个时期组成。三、解答题26、已知关键字序列为46,57,84,32,73,36,15,48,90,20,要求：（1）按照已给关键字的先后次序构造一棵二叉排列树；（2）在等概率的情况下，计算已构造的二叉排列树查找成功的平均查找次数(ASL)。(层数*每层节点数之和/总节点数(1*1+2*2+3*4+4*3)/10在等概率的情况下，该二叉树查找成功的平均查找次数为29/101、取第一个数为根节点。2、依次将各个数加入到该根的二叉树中每加一个数从根开始逐层比较，不得破坏已形成的树形(层数*每层节点数之和/总节点数(1*1+2*2+3*4+4*3)/10在等概率的情况下，该二叉树查找成功的平均查找次数为29/1027、写出下列AOV网的所有拓扑排序序列。1、输出入度为0的点2、划去从该点引出的箭头28、给定一组权值：4、1、12、2、10，构造对应的哈夫曼树（权值小的为左子树，权值大的为右子树），并求出该树的带权路径长度。1、将权值由小到大排序1、2、4、10、122、取出两个最小的权值1、2构造二叉树。1+2=3，从权值序列中划去1、2，加入3.3、依次构造二叉树，直到哈夫曼树形成构造的哈夫曼树如图：第i个叶子节点的路径长度：从根到第i个叶子节点路径的段数该树的带权路径长度为：WPL=12*1+1*4+2*4+4*3+10*2=5629、用盒图（N-S图）表示求s=1+32+52+(2n-1)2的算法，n的值由键盘输入，其中循环控制用while结构实现。四、程序分析题30、写出下列程序的输出结果。#includeMain()int a=1,2,3,4,i=0; doswitch(ai)case 2: case 3:putchar(A);break; case 4: case 5:putchar(B); case 6:putchar(C);break; default:putchar(X); while(i+3);XAABC31、写出下列程序的输出结果。#includemain()inti,j,a34=1,2,3,0,2,1,5,0,7,6,1,0; for(i=0;i3;i+) for(j=0;j3;j+) ai3+=aij; for(i=0;i3;i+) for(j=0;j4;j+)printf(“%3d”,aij); printf(“n”); 1 2 3 62 1 5 87 6 1 1432、下面程序的功能是用选择法对10个整数按由大到小排序。填空完成程序。#includemain()int i,j,m,t; int a10=5,7,4,2,3,6,1,0,9,8; for(j=0;j9;j+)m= ; i=j+1;while(i10)if(amai) m=i; if(m!=j)t=aj;aj=am;am=t;for(i=0;i10;i+)printf(“%d”,ai);printf(“n”);ji+33、下列fsum()函数的功能是求带头节点的单链表中各节点数据域中数值的和，填空完成程序。#include#define NULL 0struct nodefloat x;struct node *next;float fsum(struct node *head)float s=0; struct node *q; while(q!=Null) s=s+q-x;return s;q=head-nextq=q-next五、程序设计题34、编写程序，计算下列多项式的值并输出，直到最后一项的值小于0.0001.#include main()int i,n,k=1; float s=0,f=1.0; i=1; while(f=1e-4) k=k*i; f=1.0/k; s=s+f; i+; printf(%f,s);35、设二维数组A66表示6节点无向图的邻接矩阵，编写程序，从键盘上输入邻接矩阵的数据，求出该无向图的边数以及各个节点的度，输出所求结果。#includemain()int a66,i,j,b,s; for(i=0;i6;i+) for(j=0;j6;j+) scanf(%d,&aij); s=0; for(i=0);i6;i+) b=0; for(j=0;jy?x:(yz?y:z)的值是 DA.0B.3C.5D.73、执行下列C语言程序段，循环体被执行的次数是 CFor(i=0,j=0;(j!=4)|(inumB.*pp-numC.(*pp)-numD.(*pp).num8.若入栈数据元素序列是a,b,c,d,则不可能的出栈序列是DA.a,b,c,dB.c,b,a,dC.d,c,b,aD.d,b,c,a9.对100个有序数据，若采用二分法查找某一个元素，比较次数最多的是BA.6B.7C.8D.10010.对顺序存储的线性表，其长度为n，在等概率情况下，插入一个元素需要移动元素的平均次数是CA.n/2B.n-1C.(n+1)/2D.(n-1)/212.一个深度为k的完全二叉树中节点数至少有BA.2kB.n-1C.n+1D.2n13.对n个元素进行直接插入排序时，最多需要进行的趟数是BA.nB.n-1C.n+1D.2n14.下列C语言程序段的时间复杂度是BFor(i=1;i=n;i+)y=y+1;For(j=1;j=2*n;j+)X=x+1;A.O(2n)B.O(n2)C.O(n3)D.O()15.软件编码属于软件生存周期的 DA.软件定义时期B.软件维护时期C.软件运行时期D.软件开发时期填空16.已知int a=1,b=2,d;,执行语句 d=a0|bnext=q-next; q-next=s;22.若循环队列用数组data（m）存储元素值，用front和rear分别作为头、尾指针，则判断循环队列空的条件是 front=rear (或front=rear)23.已知二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是 cedba24.一个无向连通图G中顶点数为n，图G的边数最少是 n-125.在软件设计时期，设计模块独立性的一般度量准则是耦合和 内聚三、解答题26.已知下图所示的二叉树，要求：（1）将该二叉树还原成森林；（2）写出森林的先序（先根）遍历序列和后序（后根）遍历序列。先序遍历序列：abdgcefhij后序遍历序列：bgdaecihjf27.如下图所示的无向图，从顶点1开始，分别按邻接顶点序号由小到大顺序给出广度优先遍历和深度优先遍历的顶点序列。广度优先遍历顶点序列：1，2，3，7，4，5，6深度优先遍历顶点序列：1，2，4，5，6，3，728.已知一组关键字49，31，12，68，27，要求对其按升序排序，写出使用直接排序的每趟结果。第一趟：12，31，49，68，27第二趟：12，27，49，68，31第三趟：12，27，31，68，49第四趟：12，27，31，49，6829.某大学图书馆对读者借阅图书制定有关规定如下：（1）本科学生可以借阅5本；（2）研究生：硕士研究生可以借阅7本，博士研究生可以借阅10本；（3）教职工：教授、副教授职称的教师可以借阅15本，其他教职工可以借阅12本。用判定树法表示上述算法。程序分析题30.写出下列C语言程序的运行结果Main（）int a=7；DoSwitch(a%2)case 1:a-;break;Case();a+;break;a-;printf(“%5dn”,a);while(a0);531-131.运行下列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”,&n);For(i=1;in;i+)Printf(“i=%d,r=%dn”,I,fun(i);I=1,r=1I=2,r=2I=3,r=12I=4,r=28832.下列程序是求一个有规律的数值序列：1，1，2，4，7，13，,从第4个数开始，每一个数都市它前边3个数的和，一直求到该数列的第n（4n18）个数，填空完成程序。Main()int i=3,n,a=1,b=1,c=2,d;Scanf(“%d”,&n);Printf(“%d %d %d “,a,b,c);Doi+;D=a+b+c;Printf(“%d “,d);A=b;b=c; c=dwhile (_i=n;33.已知顺序栈的结构为：#define N 100Struct Char dataN;Int top:s;利用顺序栈的基本操作（设 push(s,x)和poop(s)函数已存在，pop(s)函数返回栈顶元素），设计一个算法如下，判断一个字符串是否有中心对称（即构成回文），若是则返回1，否则返回0。如:ababbaba、abcba都是中心对称的字符串。填空完成算法。Int symmetry(char str)int I,j,k;I=strlen(str);For(j=0;ji/2;j+)_; push(s,strj)If(i%2!=0)K=(i+1)/2;ElseK=i/2;For(j=k;jI;j+)If(_) return(); strj!=pop(s)Return 1;程序设计题34.编写C语言函数f（float x）,并用主函数调用该函数，输出计算结果。F(x)=当x1)-n;printf(“%d “,n);执行后的输出结果是 BA.4 3 2B.4321C.54 3D.54324.已知int a45;则对数组a的元素引用正确的是 AA.a04B.a45C.a25D.a455.下列关于C语言函数的叙述，错误的是 CA.允许函数递归调用B.函数形参的作用域只局限于所定义的函数内C.实参的值可以传给形参，形参的值也可以传给实参D.当形参是数组时，改变形参数组中元素的值，则实参数组中元素的值也随之改变6.有如下定义：Struct nuint no;float x;char c;a3=1,86,a,2,89,b,3,78,c,*p=a;则(+p)-x的值是 DA.0B.78C.86D.89 7.下列程序的输出结果是 DMain()long k,abc=0,xyz=13579;Doabc=abc*10+xyz%10;Xyz=xyz/10;while(xyz!=0);Printf(“%1d”,abc);A.1357 B.9753C.13579D.975318.在数据结构中，数据的逻辑结构可分为 AA.线性结构和非线性结构B.动态结构和静态结构C.内部结构和外部结构D.有序结构和无序结构9.在n个结点的顺序存储线性表中，时间复杂度是O（1）的操作是 CA.删除第i个结点（1=1=n）B.将n个结点从小到大排序C.读取第i个结点（1=i=n）D.在第i个结点后插入一个新结点（1=i=next-q-next;free(q);20.一个深度为k的二叉树，最大结点数是 21.若频繁地对线性表进行插入和删除操作，效率最高的存储结构是链式存储结构22.在结构化分析方法中，描述系统内部数据的运动情况的工具是数据流图23.给定一组元素171,28,36,54,30,27,94,15,21,83，按所给次序生成的二叉树排序的深度是 624.下列程序的功能是求整数n的阶乘，填空完成程序Float jiec