试题
200804
一、选择题
在下列各题的A)、B)、C)、D)四个选项中,只有一个选项是正确的,请将正确的选项涂写在答题卡相应位置上,答在试卷上不得分。(1)程序流程图中带有箭头的线段表示的是
A)图元关系B)数据流
C)控制流D)调用关系(2)结构化程序设计的基本原则不包括
A)多态性B)自顶向下
C)模块化D)逐步求精(3)软件设计中模块划分应遵循的准则是
A)低内聚低耦合
B)高内聚低耦合
C)低内聚高耦合
D)高内聚高耦合
(4)在软件开发中,需求分析阶段产生的主要文档是
A)可行性分析报告
B)软件需求规格说明书
C)概要设计说明书
D)集成测试计划
(5)算法的有穷性是指
A)算法程序的运行时间是有限的B)算法程序所处理
的数据量是有限的C)算法
程序的长度是有限的D)算
法只能被有限的用户使用(6)对长度为n的线性表排序,在最坏情况下,比较次数不是n(n-1)/2的排序方法是
A)快速排序B)冒泡排序C)直接插入排序D)堆排序(7)下列关于栈的叙述正确的是
A)栈按"先进先出"组织数据B)栈按"先进后出"组织数据C)只能在栈底插入数据D)不能删除数据
(8)在数据库设计中,将E -R图转换成关系数据模型
的过程属于
A)需求分析阶段
B)概念设计阶段
C)逻辑设计阶段
D)物理设计阶段
(9)有三个关系R、S和T如
下:
由关系R和S通过运算得到关
系T,则所使用的运算为
A)并B)自然连接
C)笛卡尔积D)交
(10)设有表示学生选课的
三张表,学生S(学号,姓名,
性别,年龄,身份证号),课
程C(课号,课名),选课SC(学
号,课号,成绩),则表SC的
关键字(键或码)为
A)课号,成绩
B)学号,成绩
C)学号,课号
D)学号,姓名,成绩
(11)以下叙述中正确的是
A)C程序中的注释只能出
现在程序的开始位置和语句
的后面B)C程序书写格式严
格,要求一行内只能写一个
语句C)C程序书写格式自
由,一个语句可以写在多行
上D)用C语言编写的程序
只能放在一个程序文件中
(12)以下选项中不合法的
标识符是
A)print B)FOR
C)& a D)_00
(13)以下选项中不属于字
符常量的是
A)′C′B)′′C′′
C)′\xCC′D)′\072′
(14)设变量已正确定义并
赋值,以下正确的表达式是
A)x=y*5=x+z
B)int(15.8%5)
C)x=y+z+5,++y
D)x=25%5.0
(15)以下定义语句中正确
的是
A)int a=b=0;
B)char A=65+1,b=′b′;
C)float a=1,*b=&a,*c
=&b;
D)double a=0.0;b=1.1;
(16)有以下程序段:
char ch;
int k;
ch=′a′;
k=12;
printf("%c,%d,",ch,
ch,k);
printf("k=%d\n",k);
已知字符a的ASCII码值为
97,则执行上述程序段后输
出结果是
A)因变量类型与格式描
述符的类型不匹配输出无定
值B)输出项与格式描述符个
数不符,输出为零或不定值
C)a,97,12k=12
D)a,97,k=12
(17)已知字母A的ASCII码
值为65,若变量kk为char型,
以下不能正确判断出kk中的
值为大写字母的表达式是
A)kk>=′A′&& kk<=′Z′
B)!(kk>=′A′||kk<=′Z′)
C)(kk+32)>=′a′&&(k k
+32)<=′Z′
D)isalpha(kk)&&(kk<91)
(18)当变量c的值不为2、4、6时,值也为"真"的表达式是
A)(c==2)||(c==4)||(c ==6)
B)(c>=2&& c<=6)||(c!=3)||(c!=5)
C)(c>=2&&c<=6)&&!(c%2)
D)(c>=2&& c<=
6)&&(c%2!=1)
(19)若变量已正确定义,有以下程序段:
int a=3,b=5,c=7;
if(a>b) a=b;c=a;
if(c!=a) c=b;printf("%d,%d,%d\n",a,b,c);
其输出结果是
A)程序段有语法错
B)3,5,3 C)3,5,5 D)3,5,7
(20)有以下程序:
#include
main()
{int x=1,y=0,a =0,b=0;
switch(x)
{case 1:
switch(y)
{case 0: a++;break;
case 1: b++;break;
}
case 2:a++;b++;break;
case 3:a++;b++;
}
printf("a=%d,b =%d\n",a,b);
}
程序的运行结果是
A)a=1,b=0
B)a=2,b=2
C)a=1,b=1
D)a=2,b=1
(21)有以下程序:
#include
main()
{int x=8;
for(;x>0;x--)
{if(x%3)
{printf("%d,",x--);
continue;}
printf("%d,",--x);
}
}
程序的运行结果是
A)7,4,2,
B)8,7,5,2,
C)9,7,6,4,
D)8,5,4,2,
(22)以下不构成无限循环
的语句或语句组是
A)n=0;
do{++n;}while(n<=0);
B)n=0;
while(1){n++;}
C)n=10;
while(n);{n--;}
D)for(n=0,i=1;;i++)
n+=i;
(23)有以下程序:
#include
main()
{int a[ ]={1,2,3,4},
y,*p=&a[3];
--p;y=*p;printf("y
=%d\n",y);
}
程序的运行结果是
A)y=0 B)y=1
C)y=2 D)y=3
(24)以下错误的定义语句
是
A)int x[][3]={{0},
{1},{1,2,3}};
B)int x[4][3]=
{{1,2,3},{1,2,3},{1,2,3},
{1,2,3}};
C)int x[4][]={{1,2,3},
{1,2,3},{1,2,3},{1,2,3}};
D)int x[][3]=
{1,2,3,4};
(25)设有如下程序段:
char s[20]=
"Beijing",*p;
p=s;
则执行p=s;语句后,以下
叙述正确的是
A)可以用*p表示s[0]
B)s数组中元素的个数
和p所指字符串长度相等
C)s和p都是指针变量
D)数组s中的内容和指
针变量p中的内容相同
(26)若有定义:int
a[2][3];,以下选项中对a数组
元素正确引用的是
A)a[2][!1] B)a[2][3]
C)a[0][3] D)a[1>2][!1]
(27)有定义语句:char
s[10];,若要从终端给s输入5
个字符,错误的输入语句是
A)gets(&s[0]);
B)scanf("%s",s+1);
C)gets(s);
D)scanf("%s",s[1]);
(28)以下叙述中错误的是
A)在程序中凡是以"#"
开始的语句行都是预处理命
令行
B)预处理命令行的最后
不能以分号表示结束
C)#define MAX是合法
的宏定义命令行
D)C程序对预处理命令
行的处理是在程序执行的过
程中进行的
(29)以下结构体类型说明
和变量定义中正确的是
A)typedef struct
{int n; char c;}REC;
REC t1,t2;
B)struct REC;
{int n; char c;};
REC t1,t2;
C)typedef struct REC ;
{int n=0; char
c='A';}t1,t2;
D)struct
{int n; char c;}REC;
REC t1,t2;
(30)以下叙述中错误的是
A)gets函数用于从终端
读入字符串
B)getchar函数用于从磁
盘文件读入字符
C)fputs函数用于把字符串输出到文件
D)fwrite函数用于以二进制形式输出数据到文件(31)有以下程序:
#include
main()
{int s[12]={1,2,3,4,4,3,2,1,1,1,2,3},c[5]={0},i;
for(i=0;i<12;i++) c[s[i]]++;
for(i=1;i<5;i++) printf("%d",c[i]);
printf("\n");
}
程序的运行结果是
A)1 2 3 4 B)2 3 4 4
C)4 3 3 2D)1 1 2 3
(32)有以下程序:
#include
void fun(int*s,int n1,int n2)
{int i,j,t;
i=n1;j=n2;
while(i main() {int a[10]={1,2,3,4,5,6,7,8,9,0},k; fun(a,0,3);fun(a,4,9);fun(a,0,9); for(k=0;k } 程序的运行结果是 A)0987654321 B)4321098765 C)5678901234 D)0987651234 (33)有以下程序: #include #include for(i=0;i for(j=i+1;j if(strlen(s[i])>strlen(s[j])){t =s[i];s[i]=s[j];s[j]=t;} } main() {char*ss[]={"bcc","bbcc","xy","aaaacc", "aabcc"}; fun(ss,5); printf("%s,%s\n",ss[0], ss[4]); } 程序的运行结果是 A)xy,aaaacc B)aaaacc,xy C)bcc,aabcc D)aabcc,bcc (34)有以下程序: #include int f(int x) {int y; if(x==0||x==1) return(3); y=x*x-f(x-2); return y; } main() {int z; z=f(3); printf("%d\n",z); } 程序的运行结果是 A)0 B)9C)6 D)8 (35)有以下程序: #include void fun(char*a,char *b) {while(*a==′*′)a+ +; while(*b=*a){b++;a ++;} } main() {char*s= "*****a*b****",t[80]; fun(s,t);puts(t); } 程序的运行结果是 A)*****a*b B)a*b C)a*b**** D)ab (36)有以下程序: #include #include typedef struct{char name[9];char sex;float score[2];}STU; void f(STU a) {STU b= {"Zhao",′m′,85.0,90.0}; int i; strcpy(https://www.wendangku.net/doc/eb1605103.html,,https://www.wendangku.net/doc/eb1605103.html,); a.sex=b.sex; for(i=0;i<2;i++) a.score[i]=b.score[i]; } main() {STU c= {"Qian",′f′,95.0,92.0}; f(c); printf("%s,%c,%2.0f,%2 .0f\n",https://www.wendangku.net/doc/eb1605103.html,,c.sex, c.score[0],c.score[1]); } 程序的运行结果是 A)Qian,f,95,92 B)Qian,m,85,90 C)Zhao,f,95,92 D)Zhao,m,85,90 (37)有以下程序: #include main() {FILE*fp;int a[10]={1,2,3},i,n; fp=fopen("d1.dat", "w"); for(i=0;i<3;i++) fprintf(fp,"%d",a[i]); fprintf(fp,"\n"); fclose(fp); fp=fopen("d1.dat","r"); fscanf(fp,"%d",&n); fclose(fp); printf("%d\n",n); } 程序的运行结果是 A)12300 B)123 C)1 D)321 (38)变量a中的数据用二进制表示的形式是01011101,变量b中的数据用二进制表示的形式是11110000。若要求将a的高4位取反,低4位不变,所要执行的运算是 A)a^b B)a|b C)a&b D)a<<4 (39)在C语言中,只有在使用时才占用内存单元的变量,其存储类型是 A)auto和register B)extern和register C)auto和static D)static和register (40)设有定义语句int (*f)(int);,则以下叙述正确的是 A)f是基类型为int的指针变量 B)f是指向函数的指针变量,该函数具有一个int类型的形参 C)f是指向int类型一维数组的指针变量 D)f是函数名,该函数的返回值是基类型为int类型的地址 二、填空题 请将每一个空的正确答案写在答题卡序号的横线上,答在试卷上不给分。 (1)测试用例包括输入值集和__【1】__值集。 (2)深度为5的满二叉树有__【2】__个叶子结点。(3)设某循环队列的容量为50,头指针front=5(指向队头元素的前一位置),尾指针rear=29(指向队尾元素),则该循环队列中共有__【3】__个元素。 (4)在关系数据库中,用来表示实体之间联系的是__【4】__。 (5)在数据库管理系统提供的数据定义语言、数据 操纵语言和数据控制语言 中,__【5】__负责数据的模 式定义与数据的物理存取构 建。 (6)已有定义:char c =′′;int a=1,b;(此处c 的初值为空格字符),执行b =!c&&a;后b的值为__【6】 __。 (7)设变量已正确定义为整 型,则表达式n=i=2,++i, i++的值为__【7】__。 (8)若有定义:int k;, 以下程序段的输出结果是__ 【8】__。 for(k=2;k<6;k++, k++)printf("##%d",k); (9)以下程序的定义语 句中,x[1]的初值是__【9】 __,程序运行后输出的内容 是__【10】__。 #include main() {int x[]= {1,2,3,4,5,6,7,8,9,10,11,12,13, 14,15,16},*p[4],i; for(i=0;i<4;i++) {p[i]= &x[2*i+1];printf("%d,p[i][0]" ); } printf("\n"); } (10)以下程序的输出 结果是__【11】__。 #include void swap(int*a, int*b) {int*t; t=a;a=b;b=t; } main() {int i=3,j=5,*p =&i,*q=&j; swap(p,q); printf("%d%d\n",*p,*q); } (11)以下程序的输出 结果是__【12】__。 #include main() {int a[5]= {2,4,6,8,10},*p; p=a;p++; printf("%d",*p); } (12)以下程序的输出 结果是__【13】__。 #include void fun(int x) {if(x/2>0)fun(x/2); printf("%d",x); } main() {fun(3); printf("\n");} (13)以下程序中函数 fun的功能是:统计person所 指结构体数组中所有性别 (sex)为M的记录的个数,存 入变量n中,并作为函数值返 回。请填空。 #include #define N 3 typedef struct { int num;char nam[10];char sex; } SS; int fun(SS person[]) {int i,n=0; for(i=0;i if(__【14】__==′M′)n ++; return n; } main() {SS W[N]={{1, "AA",′F′},{2,"BB",′M′}, {3,"CC",′M′}};int n; n=fun(W);printf("n =%d\n",n); (14)以下程序的功能 是从名为filea.dat的文本文件 中逐个读入字符并显示在屏幕上。请填空。 #include main() {FILE*fp;char ch; fp=fopen(__【15】__); ch=fgetc(fp); while(!feof(fp)) {putchar(ch);ch=fgetc(fp);} putchar(′\n′);fclose(fp); } 200909 一、选择题 在下列各题的A)、B)、C)、D)四个选项中,只有一个选项是正确的,请将正确的选项涂写在答题卡相应位置上,答在试卷上不得分。 (1)一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈,然后依次出栈,则元素出栈的顺序是________。 A)12345ABCDE B)EDCBA54321 C)ABCDE12345 D)54321EDCBA (2)下列叙述中正确的是________。 A)循环队列有队头和队尾两个指针,因此,循环队列是非线性结构 B)在循环队列中,只需要队头指针就能反映队列中元素的动态变化情况 C)在循环队列中,只需要队尾指针就能反映队列中元素的动态变化情况 D)循环队列中元素 的个数是由队头指针和队尾指针共同决定的 (3)在长度为n的有序线性表中进行二分查找,最坏情况下需要比较的次数是________。A)O(n) B)O(n2) C)O(log2n) D)O(nlog2n) (4)下列叙述中正确的 是________。 A)顺序存储结构的存储 一定是连续的,链式存储结 构的存储空间不一定是连续 的 B)顺序存储结构只针对 线性结构,链式存储结构只 针对非线性结构 C)顺序存储结构能存储 有序表,链式存储结构不能 存储有序表 D)链式存储结构比 顺序存储结构节省存储空间 (5)数据流图中带有箭 头的线段表示的是 ________。 A)控制流B)事件驱动 C)模块调用D)数据流 (6)在软件开发中,需 求分析阶段可以使用的工具 是________。 A)N-S图B)DFD图 C)PAD图D)程序流程图 (7)在面向对象方法 中,不属于"对象"基本特点的 是________。 A)一致性B)分类性 C)多态性D)标识唯一性 (8)一间宿舍可住多个 学生,则实体宿舍和学生之 间的联系是________。 A)一对一B)一对多 C)多对一D)多对多 (9)在数据管理技术发 展的三个阶段中,数据共享 最好的是________。 A)人工管理阶段 B)文件系统阶段 C)数据库系统阶段 D)三个阶段相同 (10)有三个关系R、S 和T如下: 由关系R和S通过运算得 到关系T,则所使用的运算为 ________。 A)笛卡尔积B)交 C)并D)自然连接 (11)以下叙述中正确 的是________。 A)C程序的基本组成单 位是语句 B)C程序中的每一行只 能写一条语句 C)简单C语句必须以分 号结束 D)C语句必须在一行内 写完 (12)计算机能直接执行的 程序是________。 A)源程序B)目标程序 C)汇编程序D)可执行程序 (13)以下选项中不能 作为C语言合法常量的是 ________。 A)'cd' B)0.1e+6 C)"\\a" D)'\011' (14)以下选项中正确 的定义语句是________。 A)double a;b; B)double a=b=7; C)double a=7,b=7; D)double,a,b; (15)以下不能正确表示代 数式 2ab cd的C语言表达式是 ________。 A)2*a*b/c/d B)a*b/c/d*2 C)a/c/d*b*2 D)2*a*b/c*d (16)C源程序中不能表示的数制是________。 A)二进制B)八进制 C)十进制D)十六进制 (17)若有表达式(w)?(--x):(++y),则其中与w等价的表达式是________。 A)w==1 B)w==0 C)w!=1 D)w!=0 (18)执行以下程序段后,w的值为________。 int w='A',x=14,y =15; w=((x‖y)&&(w<'a')); A)-1 B)NULL C)1 D)0 (19)若变量已正确定义为int型,要通过语句scanf("%d,%d,%d",&a,&b,&c);给a赋值1、给b赋值2、给c赋值3,以下输入形 式中错误的是 (代表一个 空格符)________。 A)1,2,3<回车> B)123<回车> C)1 ,2 , <回车> D)1,2,3<回车> (20)有以下程序段: int a,b,c; a=10;b=50;c =30; if(a>b)a=b,b=c; c=a; printf("a=%d b=%d c=%d\n",a,b,c); 程序的输出结果是 ________。 A)a=10 b=50 c=10 B)a=10 b=50 c=30 C)a=10 b=30 c=10 D)a=50 b=30 c=50 (21)若有定义语句:int m[]={5,4,3,2,1},i=4;,则 下面对m数组元素的引用中 错误是________。 A)m[--i] B)m[2*2] C)m[m[0]] D)m[m[i]] (22)下面的函数调用 语句中func函数的实参个数 是________。 func(f2(v1,v2),(v3, v4,v5),(v6,max(v7,v8))); A)3 B)4 C)5 D)8 (23)若有定义语句: double x[5]= {1.0,2.0,3.0,4.0,5.0},*p=x; 则错误引用x数组元素的是 ________。 A)*p B)x[5] C)*(p+1) D)*x (24)若有定义语句: char s[10]= "1234567\0\0";,则strlen(s) 的值是________。 A)7 B)8 C)9 D)10 (25)以下叙述中错误 的是________。 A)用户定义的函数中可 以没有return语句 B)用户定义的函数中可 以有多个return语句,以便可 以调用一次就返回多个函数 值 C)用户定义的函数中若 没有return语句,则应当定义 函数为void类型 D)函数的return语句中 可以没有表达式 (26)以下关于宏的叙 述中正确的是________。 A)宏名必须用大写字母表示 B)宏定义必须位于源程序中 所有语句之前 C)宏替换没有数据类型限制 D)宏调用比函数调用耗费时 间 (27)有以下程序: #include main() {int i,j; for(i=3;i>=1;i--) {for(j=1;j<=2; j++)printf("%d",i+j); printf("\\n"); } } 程序的运行结果是 ________。 A)2 3 4 B)4 3 2 3 4 5 5 4 3 C)2 3 D)4 5 3 4 3 4 4 5 2 3 (28)有以下程序: #include main() {int x=1,y=2,z =3; if(x>y) if(y ++z); else printf("%d",+ +y); printf("%d\n",x++); } 程序的运行结果是 ________。 A)331 B)41 C)2 D)1 (29)有以下程序: #include main() {int i=5; do {if(i%3==1) if(i%5==2) {printf("*%d",i); break;} i++: }while(i!=0); printf("\n"); } 程序的运行结果是 ________。 A)*7 B)*3*5 C)*5 D)*2*6 (30)有以下程序: #include int fun(int a,int b) {if(b==0)return a; else return(fun(--a,--b)); } main() {printf("%d\n",fun(4,2));} 程序的运行结果是________。 A)1 B)2 C)3 D)4 (31)有以下程序: #include #include int fun(int n) {int*p; p=(int*)malloc(sizeof(int)); *p=n;return*p; } main() {int a; a=fun(10);printf("%d\n",a+fun(10)); } 程序的运行结果是________。 A)0 B)10 C)20 D)出错 (32)有以下程序: #include void fun(int a,int b) {int t; t=a; a=b; b=t; } main() {int c[10]={1,2,3,4,5,6,7,8,9,0},i; for(i=0;i<10;i+=2)fun(c[i],c[i+1]); for(i=0;i<10;i++)printf("%d,",c[i]); printf("\n"); } 程序的运行结果是________。 A)1,2,3,4,5,6,7,8,9,0, B)2,1,4,3,6,5,8,7,0,9, C)0,9,8,7,6,5,4,3,2,1, D)0,1,2,3,4,5,6,7,8,9, (33)有以下程序: #include struct st {int x,y;}data[2] ={1,10,2,20}; main() {struct st*p= data; printf("%d,",p ->y);printf("%d\n',(+ +p)->x); } 程序的运行结果是 ________。 A)10,1 B)20,1 C)10,2 D)20,2 (34)有以下程序: #include void fun(int a[],int n) {int i,t; for(i=0;i +){t=a[i];a[i]=a[n-1 -i];a[n-1-i]=t;} } main() {int k[10]= {1,2,3,4,5,6,7,8,9,10},i; fun(k,5); for(i=2;i<8;i+ +)printf("%d",k[i]); printf("\n"); } 程序的运行结果是 ________。 A)345678 B)876543 C)1098765 D)321678 (35)有以下程序: #include #define N 4 void fun(int a[][N], int b[]) {int i; for(i=0;i b[i]=a[i][i]; } main() {int x[][N]= {{1,2,3},{4},{5,6,7,8}, {9,10}},y[N],i; fun(x,y); for(i=0;i +)printf("%d,",y[i]); printf("\n"); } 程序的运行结果是 ________。 A)1,2,3,4, B)1,0,7,0, C)1,4,5,9, D)3,4,8,10, (36)有以下程序: #include int fun(int(*s)[4],int n,int k) {int m,i; m=s[0][k]; for(i=l;i if(s[i][k]>m)m=s[i][k]; return m; } main() {int a[4][4]= {{1,2,3,4),{11,12,13,14}, {21,22,23,24}, {31,32,33,34}}; printf("%d\n", fun(a,4,0)); } 程序的运行结果是 ________。 A)4 B)34C)31 D)32 (37)有以下程序: #include main() {struct STU{char name[9];char sex; double score[2];}; struct STU a= {"Zhao",'m',85.0,90.0},b= {"Qian",'f',95.0,92.0}; b=a; printf("%s,%c,%2.0f,%2 .0f\n",https://www.wendangku.net/doc/eb1605103.html,,b.sex, b.score[0],b.score[1]); } 程序的运行结果是 ________。 A)Qian,f,95,92 B)Qian,m,85,90 C)Zhao,f,95,92 D)Zhao,m,85,90 (38)假定已建立以下链表结构,且指针p和q已指向如下图所示的结点: 则以下选项中可将q所指结点从链表中删除并释放该结点的语句组是。 A)(*p).next=(*q).next;free(p); B)p=q->next;free(q); C)p=q;free(q); D)p->next=q->next;free(q); (39)有以下程序: #include main() {char a=4; printf("%d\n",a=a<<1); } 程序的运行结果是________。 A)40 B)16C)8 D)4 (40)有以下程序: #include main() {FILE*pf; char*s1="China",*s2="Beijing"; pf=fopen("abc.dat","wb+"); fwrite(s2,7,1,pf); rewind(pf);/*文件位置指针回到文件开头*/ fwrite(s1,5,1,pf); fclose(pf); } 以上程序执行后abc.dat 文件的内容是________。 A)China B)Chinang C)ChinaBeijing D)BeijingChina 二、填空题 请将每一个空的正确答案写 在答题卡序号的横线上,答 在试卷上不给分。 (1)对下列二叉树进行 中序遍历的结果是__【1】__。 (2)按照软件测试的一 般步骤,集成测试应在__【2】 __测试之后进行。 (3)软件工程三要素包括方 法、工具和过程,其中,__ 【3】__支持软件开发的各个 环节的控制和管理。 (4)数据库设计包括概念设 计、__【4】__和物理设计。 (5)在二维表中,元组的__ 【5】__不能再分成更小的数 据项。 (6)设变量a和b已正确 定义并赋初值。请写出与a- =a+b等价的赋值表达式 __【6】__。 (7)若整型变量a和b中的值 分别为7和9,要求按以下格 式输出a和b的值: a=7 b=9 请完成输出语句: printf("__【7】__",a,b);。 (8)以下程序的输出结 果是__【8】__。 #include main() {int i,j,sum; for(i=3;i>=1;i- -) {sum=0; for(j=1;j<=i;j++) sum+=i*j; } printf("%d\n",sum); } (9)以下程序的输出结 果是__【9】__。 #include main() {int j,a[]= {1,3,5,7,9,11,13,15},*p=a +5; for(j=3;j;j--) {switch(j) {case1: case2: printf("%d",*p++); break; case3: printf("%d",*(--p)); } } } (10)以下程序的输出 结果是__【10】__。 #include #define N 5 int fun(int*s,int a, int n) {int j; *s=a;j=n; while(a!=s[j])j- -; return j; } main() {int s[N+1];int k; for(k=1;k<=N;k ++)s[k]=k+1; printf("%d\n", fun(s,4,N)); } (11)以下程序的输出 结果是__【11】__。 #include int fun(int x) {static int t=0; return(t+=x); } main() {int s,i; for(i=1;i<=5;i++)s=fun(i); printf("%d\n",s); } (12)以下程序按下面指定的数据给x数组的下三角置数,并按如下形式输出,请填空。 4 37 269 15810 #include main() {int x[4][4],n=0,i,j; for(j=0;j<4;j++) for(i=3;i>=j;__【12】__){n++;x[i][j]=__【13】__;} for(i=0;i<4;i++) {for(j=0;j<=i;j++)printf("%3d",x[i][j]); printf("\n"); } } (13)以下程序的功能是:通过函数func输入字符并统计输入字符的个数。输入时用字符@作为输入结束标志。请填空。 #include long__【14】__;/*函数说明语句*/ main() {long n; n=func();printf("n=%ld\n",n); } long func() {long m; for(m=0; getchar()!='@';__【15】 __); return m; } 200903 一、选择题 在下列各题的A)、B)、C)、 D)四个选项中,只有一个选 项是正确的,请将正确的选 项涂写在答题卡相应位置 上,答在试卷上不得分。 (1)下列叙述中正确的 是________。 A)栈是"先进先出" 的线性表 B)队列是"先进后 出"的线性表 C)循环队列是非线 性结构 D)有序线性表既可以采 用顺序存储结构,也可以采 用链式存储结构 (2)支持子程序调用的 数据结构是________。 A)栈B)树 C)队列D)二叉树 (3)某二叉树有5个度 为2的结点,则该二叉树中的 叶子结点数是________。 A)10 B)8 C)6 D)4 (4)下列排序方法中, 最坏情况下比较次数最少的 是________。 A)冒泡排序B)简单选择排 序C)直接插入排序D)堆排序 (5)软件按功能可以分 为:应用软件、系统软件和 支撑软件(或工具软件)。下面 属于应用软件的是 ________。 A)编译程序B)操作系统C) 教务管理系统D)汇编程序 (6)下面叙述中错误的 是________。 A)软件测试的目的是发现错 误并改正错误B)对被调试 的程序进行"错误定位"是程 序调试的必要步骤C)程序调 试通常也称为DebugD)软件 测试应严格执行测试计划, 排除测试的随意性 (7)耦合性和内聚性是对模 块独立性度量的两个标准。 下列叙述中正确的是 ________。A)提高耦合性降 低内聚性有利于提高模块的 独立性B)降低耦合性提高内 聚性有利于提高模块的独立 性C)耦合性是指一个模块内 部各个元素间彼此结合的紧 密程度D)内聚性是指模块间 互相连接的紧密程度 (8)数据库应用系统中 的核心问题是________。 A)数据库设计B)数据库 系统设计C)数据库维护 D)数据库管理员培训 (9)有两个关系R,S如下: R S 关系S,则所使用的运算为 ________。 A)选择B)投影 C)插入D)连接 (10)将E-R图转换为 关系模式时,实体和联系都 可以表示为________。 A)属性B)键 C)关系D)域 (11)以下选项中合法 的标识符是________。 A)1_1 B)1-1 C)_11 D)1_ _ (12)若函数中有定义语句:int k;,则________。 A)系统将自动给k赋初值0 B)这时k中的值无定义 C)系统将自动给k赋初值-1 D)这时k中无任何值 (13)以下选项中,能用作数据常量的是________。 A)o115 B)0118 C)1.5e1.5 D)115L (14)设有定义:int x =2;,以下表达式中,值不为6的是________。 A)x*=x+1 B)x++,2*x C)x*=(1+x) D)2*x,x+=2 (15)程序段:int x=12;double y= 3.141593;printf("%d%8.6f",x,y);的输出结果是________。 A)123.141593 B)12 3.141593 C)12,3.141593 D)123.1415930 (16)若有定义语句:double x,y,*px,*py;执行了px=&x;py=&y;之后,正确的输入语句是________。 A)scanf("%f%f",x,y); B)scanf("%f%f"&x,&y); C)scanf("%lf%le",px,py); D)scanf("%lf%lf",x,y); (17)以下是if语句的基本形式: if(表达式)语句 其中"表达式"________。 A)必须是逻辑表达式 B)必须是关系表达式 C)必须是逻辑表达式或关系表达式 D)可以是任意合法的表达式 (18)有以下程序: #include main() {int x; scanf("%d",& x); if(x<=3); else if(x!=10) printf("%d\n",x); } 程序运行时,输入的值 在哪个范围才会有输出结果 ________。 A)不等于10的整数 B)大于3且不等10的整 数 C)大于3或等于10的整 数 D)小于3的整数 (19)有以下程序: #include < stdio.h> main() {int a=l,b=2,c =3,d=0; if(a==l && b+ +==2) if(b!=2||c--! =3) printf("%d,%d,%d\n",a, b,c); else printf("%d,%d,%d\n",a, b,c); else printf("%d,%d,%d\n",a, b,c); } 程序运行后的输出结果 是________。 A)1,2,3 B)1,3,2 C)l,3,3 D)3,2,1 (20)以下程序段中的 变量已正确定义: for(i=0;i<4;i ++,i++) for(k=l;k<3;k ++);printf("*"); 程序段的输出结果 是________。 A)******** B)**** C)** D)* (21)有以下程序: #include main() { char *s= {"ABC"}; do {printf("%d", *s%10);s++; }while(*s); } 注意:字母A的ASCII码 值为65。程序运行后的输出 结果是________。 A)5670 B)656667 C)567 D)ABC (22)设变量已正确定 义,以下不能统计出一行中 输入字符个数(不包含回车符) 的程序段是________。 A)n=0;while((ch= getchar())!='\n')n++; B)n=0;while(getchar()! ='\n')n++; C)for(n=0;getchar()! ='n';n++); D)n=0;for(ch= getchar();ch!='\n';n++); (23)有以下程序: #include main() { int a1, a2; char c1,c2; scanf("%d%c%d%c", &a1,&c1,&a2,&c2); printf("%d,%c,%d,%c", a1,c1,a2,c2); } 若想通过键盘输入,使 得a1的值为12,a2的值为34, c1的值为字符a,c2的值为字 符b,程序输出结果是:12, a,34,b。正确的输入格式是 (以下ㄩ代表空格, 回车)________。 A)12a34b B)12ㄩa ㄩ34 ㄩb C)12,a,34,b D)12 ㄩa34 ㄩb (24)有以下程序: #include int f(int x,int y) {return((y-x)*x);} main() { int a=3,b=4,c=5,d; d=f(f(a,b),f(a,c)); printf("%d\n",d); } 程序运行后的输出结果是________。 A)10 B)9 C)8 D)7 (25)有以下程序: #include void fun(char *s) { while(*s) {if(*s%2==0) printf("%c",*s); s++; } } main() {char a[]={"good"}; fun(a); printf("\n"); } 注意:字母a的ASCII码值为97,程序运行后的输出结果是________。A)dB)goC)god D)good (26)有以下程序: #include void fun(int*a,int*b) { int*c; c=a;a=b;b=c; } main() { int x=3, y=5, *p=&x, *q=&y; fun(p,q);printf("%d,%d,",*p,*q);fun(&x,&y);printf("%d,%d\n",*p,*q); } 程序运行后的输出结果是________。 A)3,5,5,3 B)3,5,3,5 C)5,3,3,5 D)5,3,5,3 (27)有以下程序: #include void f(int *p,int *q); main() { int m=1,n=2, *r=&m; f(r,&n); printf("%d,%d",m,n); } void f(int *p,int *q) {p=p+1;*q=*q +1;} 程序运行后的输出 结果是________。 A)1,3 B)2,3 C)1,4 D)1,2 (28)以下函数按每行8 个输出数组中的数据: void fun(int *w,int n) { int i; for(i=0;i {________ printf("%d",w[i]); } printf("\n"); } 下划线处应填入的 语句是________。 A)if(i/8==0)printf("\n"); B)if(i/8==0)continue; C)if(i%8==0)printf("\n"); D)if(i%8==0)continue; (29)若有以下定义: int x[10],*pt=x; 则对x数组元素的 正确引用是________。 A)*&x[10] B)*(x+3) C)*(pt+10) D)pt+3 (30)设有定义:char s[81];int i=0;,以下不能将 一行(不超过80个字符)带有 空格的字符串正确读入的语 句或语句组是________。 A)gets(s); B)while((s[i++]= getchar())!=′\n′);s[i]==′\0′ C)scanf("%s",s); D)do{scanf("%c", &s[i]);}while(s[i++]! =′\n′);s[i]=′\0′; (31)有以下程序: #include main() { char *a[]= {"abcd","ef","gh","ijk"); int i; for(i=0;i<4;i+ +)printf("%c",*a[i]); } 程序运行后的输出结果 是________。 A)aegi B)dfhk C)abcd D)abcdefghijk (32)以下选项中正确的语 句组是________。 A)char s[];s= "BOOK!"; B)char *s;s={"BOOK! "); C)char s[10];s= "BOOK!"; D)char *s;s="BOOK! "; (33)有以下程序: #include int fun(int x,int y) { if(x==y)return(x); else return((x+ y)/2); } main() { int a=4,b=5,c=6; printf("%d\n", fun(2*a,fun(b,c))):。 A)3 B)6 C)8 D)12 (34)设函数中有整型 变量n,为保证其在未赋初值 的情况下初值为0,应选择的 存储类别是________。 A)auto B)register C)static D)auto或register (35)有以下程序: #include int b=2; int fun(int *k) { b=*k+b;return(b);} main() { int a[10]={1,2,3,4,5,6,7,8},i; for(i=2;i<4;i++){b =fun(&a[i])+b; printf("%d",b);} printf("\n"); } 程序运行后的输出结果是________。 A)10 12 B)8 10 C)10 28 D)10 16 (36)有以下程序: #include #define PT 3.5; #define S(x) PT*x*x; main() { int a=l,b=2;printf("%4.1f\n",S(a+b));} 程序运行后的输出结果是________。 A)14.0 B)31.5 C)7.5 D)程序有错无输出结果 (37)有以下程序: #include struct ord { int x,y;} dt[2]={1,2,3,4}; main() { struct ord *p=dt; printf("%d,",++p ->x);printf("%d\n",++p ->y); } 程序的运行结果是________。 A)1,2 B)2,3 C)3,4 D)4,l (38)设有宏定义:#define IsDIV(k,n) ((k%n ==1)?1:0)且变量m已正确定义并赋值,则宏调用:IsDIV(m,5)&&IsDIV(m,7)为真时所要表达的是________。 A)判断m是否能被5或 者7整除 B)判断m是否能被5和7 整除 C)判断m被5或者7整除 是否余1 D)判断m被5和7整除是 否都余1 (39)有以下程序: #include main() { int a=5,b=l,t; t=(a<<2)|b; printf("%d\n",t); } 程序运行后的输出结果 是________。 A)2l B)11 C)6 D)1 (40)有以下程序: #include main() { FILE *f; f=fopen("filea.txt", "w"); fprintf(f,"abc"); fclose(f); } 若文本文件filea.txt 中原有内容为:hello,则运 行以上程序后,文件filea.txt 中的内容为________。 A)helloabc B)abclo C)abc D)abchello 二、填空题 请将每一个空的正确答案写 在答题卡序号的横线上,答 在试卷上不给分。 (1)假设用一个长度为50的 数组(数组元素的下标从0到 49)作为栈的存储空间,栈底 指针bottom指向栈底元素,栈 顶指针top指向栈顶元素,如 果bottom=49,top=30(数组 下标),则栈中具有__【1】__ 个元素。 (2)软件测试可分为白盒测 试和黑盒测试。基本路径测 试属于__【2】__测试。 (3)符合结构化原则的三种 基本控制结构是:选择结构、 循环结构和__【3】__。 (4)数据库系统的核心是__ 【4】__。 (5)在E-R图中,图形包括 矩形框、菱形框、椭圆框。 其中表示实体联系的是__ 【5】__框。 (6)表达式(int)((double)(5/2) +2.5)的值是__【6】__。 (7)若变量x、y已定义为int 类型且x的值为99,y的值为 9,请将输出语句printf(__【7】 __,x/y); 补充完整,使其 输出的计算结果形式为:x/y =11。 (8)有以下程序: #include main() { char c1,c2 ; scanf("%c",&c1); while(c1<65||c1>90) scanf("%c",&c1); c2=c1+32; printf("%c,%c\n",c1, c2); } 程序运行输入65回车后,能 否输出结果、结束运行(请回 答能或不能)__【8】__。 (9)以下程序运行后的 输出结果是__【9】__。 #include main() { int k=1,s=0; do{ if((k%2)!=0)continue; s+=k; k++; }while(k>10); printf("s=%d\n",s); } (10)下列程序运行时, 若输入1abcedf2df<回车> 输出结果为__【10】__。 #include main() { char a=0,ch; while((ch=getchar())!=′\n′) { if(a%2!=0&&(ch>=′a′&&ch<=′z′)) ch=ch-′a′+′A′; a++;putchar(ch); } printf("\n"); } (11)有以下程序,程序执行后,输出结果是__【11】__。 #include void fun(int *a) { a[0]=a[1];} main() { int a[10]={10,9,8,7,6,5,4,3,2,1),i; for(i=2;i>=0;i--)fun(&a[i]); for(i=0;i<10;i++)printf("%d",a[i]); printf("\n"); } (12)请将以下程序中的函数声明语句补充完整。 #include int__【12】__; main() { int x,y,(*p)(); scanf("%d%d",&x,&y); p=max; printf("%d\n",(*p)(x,y)); } int max(int a,int b) { return(a>b?a:b);} (13)以下程序用来判断指定文件是否能正常打开,请填空。 #include main() { FILE *fp; if(((fp=fopen("test.txt","r"))==__【13】__)) printf("未能打开文件!\n"); else printf("文件打开成功! \n"); } (14)下列程序的运行 结果为__【14】__。 #include #include struct A { int a; char b[10]; double c; }; void f(struct A *t); main() { struct A a={1001, "ZhangDa",1098.0); f(&a); printf("%d,%s,%6.1f\n", a.a,a.b,a.c); } void f(struct A *t) { strcpy(t->b, "ChangRong");} (15)以下程序把三个 NODETYPE型的变量链接成 一个简单的链表,并在while 循环中输出链表结点数据域 中的数据。请填空。 #include struct node { int data;struct node *next;}; typedef struct node NODETYPE; main() { NODETYPE a,b,c, *h,*P; a.data=10;b.data= 20;c.data=30;h=&a; a.next=&b;b.next =&c;c.next=′\0′; p=h; while(p){printf("%d, ",p->data);__【15】__;} printf("\n"); } 200909 一、选择题 在下列各题的A)、B)、C)、 D)四个选项中,只有一个选 项是正确的,请将正确的选 项涂写在答题卡相应位置 上,答在试卷上不得分。 (1)下列数据结构中, 属于非线性结构的是 ________。 A)循环队列B)带链队列 C)二叉树D)带链栈 (2)下列数据结构中, 能够按照"先进后出"原则存 取数据的是________。 A)循环队列B)栈 C)队列D)二叉树 (3)对于循环队列,下 列叙述中正确的是 ________。 A)队头指针是固定不变 的 B)队头指针一定大于队 尾指针 C)队头指针一定小于队 尾指针 D)队头指针可以大 于队尾指针,也可以小于队 尾指针 (4)算法的空间复杂度 是指________。 A)算法在执行过程中所 需要的计算机存储空间 B)算法所处理的数据量 C)算法程序中的语句或 指令条数 D)算法在执行过程中所 需要的临时工作单元数 (5)软件设计中划分模 块的一个准则是________。 A)低内聚低耦合B)高 内聚低耦合C)低内聚高耦 合D)高内聚高耦合 (6)下列选项中不属于 结构化程序设计原则的是 ________。 A)可封装B)自顶向下 C)模块化D)逐步求精 (7)软件详细设计产生 的图如下: 该图是。 A)N-S图B)PAD图C)程序流程图D)E-R图 (8)数据库管理系统是________。 A)操作系统的一部分B)在操作系统支持下的系统软件C)一种编译系统D)一种操作系统 (9)在E-R图中,用来表示实体联系的图形是________。 A)椭圆形B)矩形 C)菱形D)三角形 (10)有三个关系R,S 和T如下: 其中关系T由关系R和S 通过某种操作得到,该操作为________。 A)选择B)投影C)交D)并 (11)以下叙述中正确的是________。 A)程序设计的任务就是 编写程序代码并上机调试 B)程序设计的任务就是 确定所用数据结构 C)程序设计的任务就是 确定所用算法 D)以上三种说法都 不完整 (12)以下选项中,能 用作用户标识符的是 ________。 A)void B) 8_8 C)_0_ D)unsigned (13)阅读以下程序: #include main() {int case;float printF; printf("请输入2个数:"); scanf("%d%f",&case, &printF); printf("% d%f\n", case,printF); } 该程序在编译时产生错 误,其出错原因是________。 A)定义语句出错,case 是关键字,不能用作用户自 定义标识符 B)定义语句出错,printF 不能用作用户自定义标识符 C)定义语句无错,scanf 不能作为输入函数使用 D)定义语句无错,printf 不能输出case的值 (14)表达式: (int)((double)9/2)-(9)%2的 值是________。 A)0 B)3 C)4 D)5 (15)若有定义语句:int x =10;,则表达式x-=x+x 的值为________。 A)-20 B)-10 C)0 D)10 (16)有以下程序: #include main() {int a=1,b=0; printf("%d,",b=a+b); printf("%d\n",a=2] 程序运行后的输出结果 是________。 A)0,0 B)1,0 C)3,2 D)1,2 (17)设有定义:int a =1,b=2,c=3;,以下语 句中执行效果与其他三个不 同的是________。 A)if(a>b)c=a,a=b,b =c; B)if(a>b){c=a,a=b,b =c;} C)if(a>b)c=a;a=b;b =c; D)if(a>b){c=a;a=b;b =c;} (18)有以下程序: #include main() {int c=0,k; for(k=1;k<3;k++) switch(k) {default: c+=k; case 2:c++;break; case 4:c+=2;break; } printf("%d\n",c); } 程序运行后的输出结果 是________。 A)3 B)5 C)7 D)9 (19)以下程序段中, 与语句:k=a>b?(b>c?1: 0):0;功能相同的是 ________。 A)if((a>b)&&(b>c))k=1; else k=0; B)if((a>b)‖(b>c))k=1; else k=0; C)if(a<=b)k=0; else if(b<=c)k=1; D)if(a>b)k=1; else if(b>c)k=1; else k=0; (20)有以下程序: #include main() {char s[]={"012xy"};int i,n=0; for(i=0;s[i]!=0;i++) if (s[i]>='a'&&s[i]<='z')n++; printf("%d\n",n); } 程序运行后的输出结果是________。 A)0 B)2 C)3 D)5 (21)有以下程序: #include main() {int n=2,k=0;while(k++&&n++>2);printf("%d%d\n",k,n); } 程序运行后的输出结果是________。 A)0 2 B)1 3 C)57 D)1 2 (22)有以下定义语句,编译时会出现编译错误的是________。 A)char a='a'; B)char a='\n'; C)char a='aa'; D)char a='\x2d'; (23)有以下程序: #include main() {char cl,c2; cl='A'+'8'-'4'; c2='A'+'8'-'5'; printf("%c,%d\n",cl,c2); } 已知字母A的ASCIl码为65,程序运行后的输出结果是________。 A)E,68 B)D,69 C)E,D D)输出无定值 (24)有以下程序: #include void fun(int p) {int d=2; p=d++; printf("%d",p);} main() {int a=1; fun(a);printf("%d\n", a);} 程序运行后的输出结果 是________。 A)32 B)12 C)21 D)22 (25)以下函数findmax 拟实现在数组中查找最大值 并作为函数值返回,但程序 中有错导致 不能实现预定功能。 #define MIN - 2147483647 int findmax(int x[],int n) {int i,max; for(i=0;i {max=MIN; if(max return max; } 造成错误的原因是 ________。 A)定义语句int i,max; 中max未赋初值 B)赋值语句max=MIN; 中,不应给max赋MIN值 C)语句if(max =x[i];中判断条件设置错误 D)赋值语句max= MIN;放错了位置 (26)有以下程序: #include main() {int m=1,n=2,*p =&m,*q=&n,*r; r=p;p=q;q=r; printf("%d,%d,%d, %d\n",m,n,*p,*q); } 程序运行后的输出结果 是________。 A)1,2,1,2 B)1,2,2,1 C)2,1,2,1 D)2,1,1,2 (27)若有定义语句:int a[4][10],*p,*q[4];且0≤i<4, 则错误的赋值是________。 A)p=a B)q[i] =a[i] C)p=a[i] D)p =&a[2][1] (28)有以下程序: #include #include main() {char str[][20]= {"Qne*World","one*Dream! "},*p=str[1]; printf("%d,", strlen(p));printf("%s\n",p); } 程序运行后的输出结果 是________。 A)9,One*World B)9,One*Dream! C)10,One*Dream! D)10,One*World (29)有以下程序: #include main() {int a[]={2,3,5,4}, i; for(i=0;i<4;i++) switch(i%2) {case 0: switch(a[i]%2) {case 0:a[i] ++;break; case 1:a[i] --; }break; case 1:a[i]=0; } for(i=0;i<4;i++) printf("%d",a[i]); printf("\n"); } 程序运行后的输出结果 是________。 A)3 3 4 4 B)2 0 5 0 C)3 0 4 0 D)0 3 0 4 (30)有以下程序: #include #include main() {char a[10]="abcd"; printf("%d,%d\n",strlen(a),sizeof(a)); } 程序运行后的输出结果是________。 A)7,4 B)4,10 C)8,8 D)10,10 (31)下面是有关C语言字符数组的描述,其中错误的是________。 A)不可以用赋值语句给字符数组名赋字符串 B)可以用输入语句把字符串整体输入给字符数组 C)字符数组中的内容不一定是字符串 D)字符数组只能存放字符串 (32)下列函数的功能是________。 fun(char*a,char*b) {while((*b=*a)!='\0') {a++;b++;}} A)将a所指字符串赋给b 所指空间 B)使指针b指向a所指字符串 C)将a所指字符串和b所指字符串进行比较 D)检查a和b所指字 符串中是否有'\0' (33)设有以下函数: void fun(int n,char *s){ …… } 则下面对函数指针的定义和赋值均正确的是________。 A)void(*pf)();pf=fun; B)void*pf();pf=fun; C)void*pf()*pf=fun;D)void(*pf)(int,char);pf =&fun; (34)有以下程序: #include int f(int n); main() {int a=3,s; s=f(a);s=s+f(a); printf("%d\n",s); } int f(int n) {static int a=1; n+=a++; return n; } 程序运行后的输出结果 是________。 A)7 B)8 C)9 D)10 (35)有以下程序: #include #define f(x) x*x*x main() {int a=3,s,t; s=f(a+1);t=f((a+1)); printf("%d,%d\n",s,t); } 程序运行后的输出结果 是________。 A)10,64 B)10,10 C)64,10 D)64,64 (36)下面结构体的定 义语句中,错误的是 ________。 A)struct ord{int x; int y;int z;};struct ord a; B)struct ord{int x; int y;int z;}struct ord a; C)struct ord{int x; int y;int z;}a; D)struct{int x; int y;int z;)a; (37)设有定义:char *c;,以下选项中能够使字符 型指针c正确指向一个字符 串的是________。 A)char str[]="string";c =str; B)scanf("%s",c); C)c=getchar(); D)*c="string"; (38)有以下程序: #include #include struct A {int a;char b[10]; double c;}; struct A f(struct A t); main() {struct A a={1001, "ZhangDa",1098.0); a=f(a); printf("%d,%s,%6.1f\n", a.a,a.b,a.c); } struct A f(struct A t) {t.a=1002; strcpy(t.b,"changRong");t.c =1202.0;return t;} 程序运行后的输出结果 是________。 A)1001,ZhangDa,1098.0 B)1002,ZhangDa,1202.0 C)1001, ChangRong,1098.0 D)1002, ChangRong,1202.0 (39)若有以下程序段: int r=8; printf("%d\n",r>>1); 输出结果是________。 A)16 B)8 C)4 D)2 (40)下列关于C语言文 件的叙述中正确的是 ________。 A)文件由一系列数据依 次排列组成,只能构成二进 制文件 B)文件由结构序列组 成,可以构成二进制文件或 文本文件 C)文件由数据序列组 成,可以构成二进制文件或 文本文件 D)文件由字符序列 组成,其类型只能是文本文件 二、填空题 请将每一个空的正确答案写在答题卡序号的横线上,答在试卷上不给分。 (1)某二叉树有5个度为2的结点以及3个度为1的结点,则该二叉树中共有__【1】__个结点。 (2)程序流程图中的菱形框表示的是__【2】__。 (3)软件开发过程主要分为需求分析、设计、编码与测试四个阶段,其中__【3】__ 阶段产生"软件需求规 格说明书"。 (4)在数据库技术中,实体集之间的联系可以是一对一或一对多或多对多的,那么"学生"和"可选课程"的联系为__【4】__。 (5)人员基本信息一般包括:身份证号,姓名,性别,年龄等。其中可以作为主关键字是__【5】__。 (6)若有定义语句:int a=5;,则表达式:a++的值是__【6】__。 (7)若有语句double x=17;int y;,当执行y= (int)(x/5)%2;之后y的值为__【7】__。 (8)以下程序运行后的输出结果是__【8】__。 #include main() {int x=20; printf("%d",0 0 (9)以下程序运行后的输出结果是__【9】__。 #include main() {int a=1,b=7; do{ b=b/2; a+=b; } while(b>1); printf("%d\n",a);} (10)有以下程序: #include main() {int f,fl,f2,i; f1=0;f2=1; printf("%d%d",f1,f2); for(i=3;i<=5;i+ +) { f=f1+f2; printf("%d",f); f1=f2;f2=f; } printf("\n"); } 程序运行后的输出结果是__ 【10】__。 (11)有以下程序: #include int a=5; void fun(int b) {int a=10; a+=b;printf("%d",a); } main() {int c=20; fun(c);a+=c; printf("%d\n",a); } 程序运行后的输出结果是__ 【11】__。 (12)设有定义: struct person {int ID;char name[12];}p; 请将scanf("%d",__【12】 __);语句补充完整,使其能 够为结构体变量p的成员ID 正确读入数据。 (13)有以下程序: #include main() {char a[20]="How are you?",b[20]; scanf("%s",b); printf("%s %s\n",a,b); } 程序运行时从键盘输 入:How are you?<回车> 则输出结果为__【13】 __。 (14)有以下程序: #include typedef struct {int num;double s;}REC; void funl(REC x) {x.num=23;x.s=88.5;} main() {REC a={16,90.0); fun1(a); printf("%d\n",a.num); } 程序运行后的输出结果是__ 【14】__。 (15)有以下程序: #include fun(int x) {if(x/2>0) fun(x/2); printf("%d.",x); } main() {fun(6), printf("\n");} 程序运行后的输出结果是__ 【15】__。 答案 200804 一、选择题 (1)C解析:程序流程图是人们 对解决问题的方法、思路或 算法的一种描述。其中,图 框表示各种操作的类型,图 框中的文字和符号表示操作 的内容,流程线表示操作的 先后次序。带箭头的线段在 数据流程图中表示数据流, 而在程序流程图中表示控制 流。在所给出的选项中,在 图元之间用带有箭头的线段 表示图元关系。在模块之间 用带有箭头的线段表示调用 关系。构成程序流程图的基 本图符及其含义是:→或↓表示控制流,□表示加工步骤,◇表示逻辑条件。 (2)A解析:结构化程序设计的原则包括:"自顶而下,逐步求精"的设计思想,"独立功能,单出口、单入口"的模块化设计等。多态性是面向对象程序语言的特征 (3)B解析:模块划分应遵循的准则包括模块之间的耦合和内聚。一般来说,要求模块之间的耦合尽可能地低,即模块尽可能独立,要求模块的内聚程度尽可能地高,即高内聚、低耦合的原则。(4)B解析:需求分析阶段的工作主要包括需求获取、需求分析、编写需求规格说明书和需求评审等四方面。产生的主要文档为软件需求规格说明书,它可以为用户、分析人员和设计人员之间的交流提供方便,可以直接支持目标软件系统的确认,又可以作为控制软件开发进程的依据。 (5)A解析:算法具有6个特性。 ①有穷性:一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束,且每一步都可在有限时间内完成,即运行时间是有限的。 ②确定性:算法中每一条指令必须有确切的含义,读者理解时不会产生歧义。③可行性:一个算法是可行的,即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。④输入:一个算法有零个或多个输入,这些输入取自于某个特定的对象的集合。⑤输出:一个算法有一个或多个输出。 (6)D解析:在最坏情况下,快速排序、冒泡排序和直接插入排序需要的比较次数都是 n(n-1)/2,堆排序需要比较 的次数为nlog2n。 (7)B解析:在栈中,允许插入 与删除的一端称为栈顶,而 不允许插入与删除的一端称 为栈底。栈顶元素总是最后 被插入的元素,从而也是最 先被删除的元素;栈底元素 总是最先被插入的元素,从 而也是最后才能被删除的元 素。因而栈是按照"先进后出 "或"后进先出"的原则组织数 据的。 (8)C解析:数据库的逻辑设计 分为:①将概念模型转换成 一般的数据模型;②将一般 的数据模型转换为特定的数 据库管理系统所支持的数据 模型。把概念模型转换成关 系数据模型就是把E-R图转 换成一组关系模式。 (9)D解析:在关系运算中,交 的定义如下:设R1和R2为参 加运算的两个关系,它们具 有相同的度n,且相对应的属 性值取自同一个域,则 R1∩R2为交运算,结果仍为 度等于n的关系,其中,交运 算的结果既属于R1又属于 R2。 (10)C解析: "选课SC" 表是 "学生S" 表和"课程C" 表的 映射表,主键是两个表主键 的组合。 (11)C解析:在C语言中,注释 可以加在程序中的任何位 置,选项A)错误。C程序可以 分模块写在不同的文件中, 编译时再将其组合在一起, 选项D)错误。C程序的书写风 格很自由,不但一行可以写 多个语句,还可以将一个语 句写在多行中。所以正确答 案为选项C)。 (12)C解析:C语言合法标识 符的命名规则是:标识符只 能由字母、数字和下划线组 成,并且第一个字符必须为 字母或下划线。因为选项C) 中的标识符的第一个字符为 "&",所以选项C)为本题的正 确答案。 (13)B解析:在C语言程序中, 用单引号把一个字符或反斜 线后跟一个特定的字符括起 来表示一个字符常量。选项 A)、C)和D)为正确的字符常 量;而选项B)是用双引号括 起来的字符,表示一个字符 串常量,所以正确答案为选 项B)。 (14)C解析:求余运算符"%" 两边的运算对象必须是整 型,而选项B)和D)中"%"两 边的运算对象有浮点整数 据,所以选项B)和D)是错误 的表达式;在选项A)中赋值 表达式的两边出现相同的变 量x,也是错误的;选项C)是 一个逗号表达式,所以正确 答案为C)。 (15)B解析:本题考查变量的 定义方法。如果要一次进行 多个变量的定义,则在它们 之间要用逗号隔开。因此选 项A)和D)错误;在选项C)中, 变量c是一个浮点型指针,它 只能指向一个浮点型数据, 不能指向指针变量b;所以正 确答案为B)。 (16)D解析:输出格式控制 符%c表示将变量以字符的形 式输出;输出格式控制符%d 表示将变量以带符号的十进 制整型数输出。所以第一个 输出语句输出的结果为a,97, 第二个输出语句输出的结果 为k=12,所以选项D)为正确 答案。 (17)B解析:C语言的字符以 其ASCII码的形式存在,所以 要确定某个字符是大写字 母,只要确定它的ASCII码在 'A'和'Z'之间就可以了,选项A)和C)符合此要求。在选项D)中,函数isalpha用来确定一个字符是否为字母,大写字母的ASCII码值的范围为65到90,所以如果一个字母的ASCII码小于91,那么就能确定它是大写字母。本题答案选B)。 (18)B解析:满足表达式(c>=2&& c<=6)的整型变量c的 值是2,3,4,5,6。当变量c的值不为2,4,6时,其值只能为3或5,所以表达式c!=3和c!=5中至少有一个为真,即不论c为何值,选项B)中表达式的值都为"真"。正确答案为 B)。 (19)B解析:两个if语句的判 断条件都不满足,程序只执行了c=a这条语句,所以变量c的值等于3,变量b的值没能变化,程序输出的结果为3,5,3。所以正确答案为选项 B)。 (20)D解析:本题考查switch 结构的内容。在C语言中,程序执行完一个case标号的内 容后,如果没有break语句,控制结构会转移到下一个case继续执行,因为case 常量表达式只是起语句标号作用,并不是在该处进行条件判断。本题程序在执行完内部switch结构后,继续执行了外部switch结构的case 2分支。最后a和b的值分别为2和1。 (21)D解析:在本题中,程序每执行一次循环x的值就减2,循环共执行4次。当x的值为8,4,2时,printf语句先输出x 的值,再将x的值减1。而当x 为6时,if语句条件成立,程序先将x的值减1,再将其输出。所以输出结果为选项D)。 (22)A解析:项A)中变量n的值,先自加1,再进行循环条 件判断,此时循环条件n<=0 不成立,跳出循环。所以正 确答案为A)。 (23)D解析:在程序中指针变 量p初始指向a[3],执行p减1 后,p指向a[2],语句y=*p的 作用是把a[2]的值赋给变量 y,所以输出为y=3。正确答 案为D)。 (24)C解析:本题考查的是二 维数组的定义和初始化方 法。C语言中,在定义并初始 化二维数组时,可以省略数 组的第一维的长度,但是不 能省略第二维的长度。故选 项C)错误。 (25)A解析:语句p=s的作用 是把字符数组s的首地址作 为初值赋给了指针变量p,并 且使p指向了字符数组s的第 一个字符s[0]。 (26)D解析:C语言中数组下 标是从0开始的,所以二维数 组a[2][3]的第一维下标取值 为0、1;第二维的下标取值 为0、1、2,因而选项A)、B)、 C)都是错误的,选项D)表示 的是数组元素a[0][0]。所以正 确答案为D)。 (27)解析:在格式输入中,要 求给出的是变量的地址,而 D)答案中给出的s[1]是一个 值的表达式。 (28)D 解析:C语言中的预处理 命令以符号#开头,这些命令 是在程序编译之前进行处理 的,选项D)的描述错误。故 答案选D)。 (29)A 解析:本题考查的是 typedef的用法和结构体变量 的定义方法。typedef可用于 声明结构体类型,其格式为 "typedef struct {结构元素定 义}结构类型;"。本题正确 答案为A)。 (30)B解析:getchar函数的作 用是从终端读入一个字符。 (31)C解析:在for(i=0;i<12; i++) c[s[i]]++中,数组 元素s[i]的值作为数组c的下 标,当退出循环时,数组c的 4个元素的值分别为4、3、3、 2。所以选项C)正确。 (32)C解析:函数fun(int *s,int n1,int n2)的功能是对数组s 中的元素进行首尾互相调 换。所以在主函数中,当 fun(a,0,3)执行完后,数组a[12] ={4,3,2,1,5,6,7,8,9,0};再执 行fun(a,4,9),数组a[12]= {4,3,2,1,0,9,8,7,6,5};再执行 fun(a,0,9)后,数组a[12]= {5,6,7,8,9,0,1,2,3,4}。所以正 确答案为C)。 (33)A解析:函数fun(char *s[],int n)的功能是对字符串 数组的元素按照字符串的长 度从小到大排序。在主函数 中执行fun(ss,5)语句后,*ss[] ={"xy","bcc","bbcc", "aabcc","aaaacc"},ss[0], ss[4]的输出结果为xy, aaaacc。所以选项A)为正确答 案。 (34)C解析:函数int f(int x)是 一个递归函数调用,当x的值 等于0或1时,函数值等于3, 其他情况下y=x2-f(x-2)。 所以在主函数中执行语句"z =f(3)"时,y= 3*3-f(3-2)=9-f(1)=6。 (35)C解析:在函数fun(char *a,char *b)中,while(*a== '*')a++的功能是:如果*a的 内容为'*',则a指针向后移动, 直到遇到非'*'字符为止,退出 循环进入下一个while循环, 在while(*b=*a){b++;a+ +;}中,把字符数组a中的 字符逐个赋给字符数组b。所 以在主函数中,执行fun(s,t) 语句后,字符数组t中的内容为"a*b****"。所以选项C)为正确答案。 (36)A解析:本题考查的是函数调用时的参数传递问题。程序在调用函数f时,传给函数f的参数只是结构变量c在栈中的一个复制,函数f所做的所有操作只是针对这个数据复制进行的修改,这些都不会影响变量c的值。 (37)B解析:在函数中首先把整型数组a[10]中的每个元素写入文件d1.dat中,然后再次打开这个文件,把文件d1.dat 中的内容读入到整型变量n 中,最后输出变量n的值。所以正确答案为B)。 (38)A解析:本题考查的是位运算的知识。对于任何二进制数,与1进行异或运算会让其取反,而与0进行异或运算不会产生任何变化,故本题答案选A)。 (39)A解析:在C语言中只有 自动变量和寄存器变量在使用时才占用内存单元。所以正确答案为A)。 (40)B解析:本题考查的是指向函数的指针。语句"int (* f)(int);"是对一个函数的声明,其中f是指向该函数的指针,该函数有一个整型的参数,函数返回值类型为整型。故答案选B)。 二、填空题 (1)【1】输出 解析:软件测试用例是为了有效发现软件缺陷而编写的,包含测试目的,测试步骤,期望测试结果的特定集合。正确认识和设计软件测试用例可以提高软件测试的有效性,便于测试质量的度量,增强测试过程的可管理性。软件测试用例包括输入值集和输出值集。测试用例是软件测试的核心。 (2)【2】 16 解析:在满二叉树中,叶 子结点数目的计算公式为2n- 1,其中n为树的深度。 (3)【3】 24 解析:实现循环队列时, 头指针指向第一个元素的前 一个空间,尾指针指向最后 一个元素。因此,此时队列 中6,7,8,...,29这24个空间存 有元素,即队列中有29-5= 24个元素。 (4)【4】关系 解析:在关系数据库中, 用关系(二维表结构)表示实 体及其之间联系的模型称为 关系数据模型。 (5)【5】数据定义语言 解析:数据定义语言:负 责数据的模式定义与数据的 物理存取构建。数据操纵语 言:负责数据的操纵,如查 询、增加、删除、修改等。 数据控制语言:负责数据完 整性、安全性的定义与检查, 以及并发控制、故障恢复等。 (6)【6】 0 解析:字符空格的ASCII 码不为0,所以本题中表达 式!c的值为0, b=0&&1的 结果显然为0。 (7)【7】 3 解析:本题考查的是C语 言逗号表达式的相关知识。 程序在计算逗号表达式时, 从左到右计算由逗号分隔的 各表达式的值,整个逗号表 达式的值等于其中的最后一 个表达式的值。本题中,首 先i被赋值为2,再自加1,最 后i++的值计算为3。 (8)【8】 ##2##4 解析:在for循环语句中, 自变量k的自增表达式为k+ +,k++。这是一个逗号表 达式,所以输出结果为 ##2##4。 (9)【9】 2 【10】 2 4 6 8 解析:在主函数中根据整 型数组x[]的定义可知,x[1] 的初值等于2。在for循环语句 中,当i=0时,p[0]=&x[1], p[0][0]=2; 当i=1时,p[1] =&x[3],p[1][0]=4;当i=2 时,p[2]=&x[5],p[2][0]=6; 当i=3时,p[3]=&x[7], p[3][0]=8。所以程序输出的 结果为2 4 6 8。 (10)【11】 3 5 解析: 函数swap(int *a, int *b)的功能是实现*a和*b 中两个数据的交换,在主函 数中调用swap(p,q)后,参形 指针变量a和b分别指向i和j, 在swap(int *a,int *b)执行完 后,指针变量a和b分别指向j 和i,而指针变量p,q所指向 变量的值没有发生变化,所 以输出结果为3 5。 (11)【12】 4 解析: 在主函数中,语句 p=a;p++使用指针p指向 数组a[1],所以输出结果为4。 (12)【13】 1 3 解析: 在主函数中调用 fun(3)时,实参3传递给形参 x。在fun(x)内,执行第一条 语句,输出1,然后执行第二 条语句,输出3,所以结果为 1 3。 (13)【14】 person[i].sex 解析: 在函数fun(SS person[])中对person[]的性别 进行判断,所以其正确的调 用格式为person[i].sex。 (14)【15】”filea.dat”,”r” 解析: fopen函数的调用 方式通常为fopen(文件名, 使用文件方式)。本题中要求 程序可以打开filea.dat文件, 并且读取文件中的内容。所 以空白处应当填入 目录 二级公共基础知识考纲 (1) 第一章数据结构与算法 (2) 第二章程序设计基础 (19) 第三章软件工程基础 (23) 第四章数据库设计基础 (32) 全国计算机等级考试二级公共基础知识考纲 考试内容 一、基本数据结构与算法 1.算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度)。 2.数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。 3.线性表的定义;线性表的顺序存储结构及其插入与删除运算。 4.栈和队列的定义;栈和队列的顺序存储结构及其基本运算。 5.线性单链表、双向链表与循环链表的结构及其基本运算。 6.树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。 7.顺序查找与二分法查找算法;基本排序算法(交换类排序,选择类排序,插入类排序)。 二、程序设计基础 1.程序设计方法与风格。 2.结构化程序设计。 3.面向对象的程序设计方法,对象,方法,属性及继承与多态性。 三、软件工程基础 1.软件工程基本概念,软件生命周戎概念,软件工具与软件开发环境。 2.结构化分析方法,数据流图,数据字典,软件需求规格说明书。 3.结构化设计方法,总体设计与详细设计。 4.软件测试的方法,白盒测试与黑盒测试,测试用例设计,软件测试的实施,单元测试、集成测试和系统测试。 5.程序的调试,静态调试与动态调试。 四、数据库设计基础 1.数据库的基本概念:数据库,数据库管理系统,数据库系统。 2.数据模型,实体联系模型及E-R图,从E-R图导出关系数据模型。 3.关系代数运算,包括集合运算及选择、投影、连接运算,数据库规范化理论。 4.数据库设计方法和步骤:需求分析、概念设计、逻辑设计和物理设计的相关策略。 考试方式 公共基础的考试方式为笔试,与C语言(V isualBASIC、V isual FoxPro、Java、Access、Visual C++)的笔试部分合为一张试卷。 公共基础部分占全卷的30分。公共基础知识有10道选择题和5道填空题。 第一章数据结构与算法 一、内容要点 (一)算法 1.算法的基本概念 算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明确的,没有二义性,同时该规则将在有限次运算后可终止。 1)算法的基本特征 (1)可行性 由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的,因此,它总是受到计算工具的限制,使执行产生偏差。 全国计算机等级考试二级公共基础知识要点汇总 第一章数据结构与算法 1.1 算法 算法:是指解题方案的准确而完整的描述。 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括: (1)可行性; (2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性; (3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义; (4)拥有足够的情报。 算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。 指令系统:一个计算机系统能执行的所有指令的集合。 基本运算包括:算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构:顺序结构、选择结构、循环结构。 算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度:算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本概念 数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;(3)对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含: (1)表示数据元素的信息; (2)表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件: (1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。 非线性结构:不满足线性结构条件的数据结构。 1.3 线性表及其顺序存储结构 线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。 在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。 非空线性表的结构特征: (1)且只有一个根结点a1,它无前件; 二级公共基础知识分类模拟题43 单项选择题 1、下列叙述中正确的是______。 A.所谓算法就是计算方法 B.程序可以作为算法的一种描述方法 C.算法设计只需考虑得到计算结果 D.算法设计可以忽略算法的运算时间 2、下列叙述中正确的是______。 A.算法的复杂度包括时间复杂度与空间复杂度 B.算法的复杂度是指算法控制结构的复杂程度 C.算法的复杂度是指算法程序中指令的数量 D.算法的复杂度是指算法所处理的数据量 3、下列叙述中正确的是______。 A.算法的时间复杂度与计算机的运行速度有关 B.算法的时间复杂度与运行算法时特定的输入有关 C.算法的时间复杂度与算法程序中的语句条数成正比 D.算法的时间复杂度与算法程序编制者的水平有关 4、下列叙述中正确的是______。 A.非线性结构可以为空 B.只有一个根结点和一个叶子结点的必定是线性结构 C.只有一个根结点的必定是线性结构或二叉树 D.没有根结点的一定是非线性结构 5、设数据结构B=(D,R),其中 D={a,b,c,d,e,f} R={(f,a),(d,b),(e,d),(c,e),(a,c)} 该数据结构为______。 A.线性结构 B.循环队列 C.循环链表 D.非线性结构 6、下列叙述中正确的是______。 A.矩阵是非线性结构 B.数组是长度固定的线性表 C.对线性表只能作插入与删除运算 D.线性表中各元素的数据类型可以不同 7、在线性表的顺序存储结构中,其存储空间连续,各个元素所占的字节数______。 A.不同,但元素的存储顺序与逻辑顺序一致 B.不同,且其元素的存储顺序可以与逻辑顺序不一致 C.相同,元素的存储顺序与逻辑顺序一致 D.相同,但其元素的存储顺序可以与逻辑顺序不一致 8、下列叙述中正确的是______。 A.能采用顺序存储的必定是线性结构 B.所有的线性结构都可以采用顺序存储结构 C.具有两个以上指针的链表必定是非线性结构 D.循环队列是队列的链式存储结构 9、下列叙述中正确的是______。 A.在栈中,栈顶指针的动态变化决定栈中元素的个数 全国计算机二级考试公共基础知识总结 第一章数据结构与算法 1.1 算法 算法:是指解题方案的准确而完整的描述。 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括:(1)可行性; (2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性; (3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义; (4)拥有足够的情报。 算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。 指令系统:一个计算机系统能执行的所有指令的集合。 基本运算包括:算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构:顺序结构、选择结构、循环结构。 算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度:算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本基本概念 数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构; (3)对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含: (1)表示数据元素的信息; (2)表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件: (1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。 非线性结构:不满足线性结构条件的数据结构。 1.3 线性表及其顺序存储结构 线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。 在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由 1.1 算法 考点1 算法的基本概念 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 算法(algorithm)是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,同时是明确的;此顺序将在有限的次数后终止。算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。 1算法的基本特征 (1)可行性(effectiveness):针对实际问题而设计的算法,执行后能够得到满意的结果。 (2)确定性(definiteness):算法中的每一个步骤都必须有明确的定义,不允许有模棱两可的解释和多义性。 (3)有穷性(finiteness):算法必需在有限时间内做完,即算法必需能在执行有限个步骤之后终止。 (4)拥有足够的情报:要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时,此算法才最有效的;而当提供的情报不够时,算法可能无效。 2算法的基本要素 (1)算法中对数据的运算和操作:每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。 计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合,称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中,基本的运算和操作有以下4类: ①算术运算:主要包括加、减、乘、除等运算; ②逻辑运算:主要包括“与”、“或”、“非”等运算; ③关系运算:主要包括“大于”、“小于”、“等于”、“不等于”等运算; ④数据传输:主要包括赋值、输入、输出等操作。 (2)算法的控制结构:一个算法的功能不仅仅取决于所选用的操作,而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。 算法的控制结构给出了算法的基本框架,它不仅决定了算法中各操作的执行顺序,而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 (3)算法设计的基本方法 计算机算法不同于人工处理的方法,下面是工程上常用的几种算法设计,在实际应用时,各种方法之间往往存在着一定的联系。 (1)列举法 列举法是计算机算法中的一个基础算法。列举法的基本思想是,根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的。 列举法的特点是算法比较简单。但当列举的可能情况较多时,执行列举算法的工作量将会很大。因此,在用列举法设计算法时,使方案优化,尽量减少运算工作量,是应该重点注意的。 (2)归纳法 归纳法的基本思想是,通过列举少量的特殊情况,经过分析,最后找出一般的关系。从本质上讲,归纳就是通过观察一些简单而特殊的情况,最后总结出一般性的结论。 全国计算机等级考试二级公共基础知识练习题 及答案 全国计算机二级考试主要考核使用一种高级计算机语言编写程序以及 上机调试的基本技能,以下是由我整理关于的内容,希望大家喜欢! (一) 1、域名是ISP的计算机名,域名中的后缀、gov表示机构所属类型为( )。 A、政府机构 B、教育机构 C、商业机构 D、军事机构考试用书 答案:A 2、中文EXCEL的分类汇总方式不包括( )。 A、乘积 B、平均值 C、值 D、求和 答案:A 3、地址为202、18、66、5的IP地址属于( )类IP地址。 A、A B、C C、D D、B 答案:B 4、微型计算机硬件系统中最核心的部件是( )。 A、硬件 B、I/O 设备 C、内存储器 D、CPU 答案:D 5、在计算机技术指标中,MIPS用来描述计算机的( )。 A、运算速度 B、时钟频率 C、存储容量 D、字长 答案:A (二) 1、Excel的主要功能是( )。 A、表格处理,文字处理,文件管理 B、表格处理,网络通讯,图表处理 C、表格处理,数据库管理,图表处理 D、表格处理,数据库管理,网络通讯 答案:C 2、关于Word中的文本框,下列说法( )是不正确的。 A、文本框可以做出冲蚀效果 B、文本框可以做出三维效果 C、文本框只能存放文本,不能放置图片 D、文本框可以设置底纹 答案:C 3、局域网的英文缩写是( )。 A、WAN B、LAN C、MAN D、Internet 答案:B 4、在WORD编辑状态下,当前编辑文档中的字体是宋体,选择了一段文字使之反显,先设定了楷体,又设定了黑体,则( )。 A、文档全文都是楷体 B、被选择的内容仍是宋体 C、被选择的内容便成了黑体 D、文档全部文字字体不变 答案:C 5、下列叙述中,正确的是( )。 A、CPU 能直接读取硬盘上的数据 B、CPU 能直接存取内存储器中的数据 C、CPU 由存储器和控制器组成 全国计算机等级考试二级公共基础知识复习资料 全国计算机等级考试二级公共基础知识复习资料 第一章数据结构与算法 1.1 算法 算法:是指解题方案的准确而完整的描述。 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括: (1)可行性; (2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性; (3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义; (4)拥有足够的情报。 算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。 指令系统:一个计算机系统能执行的所有指令的集合。 基本运算包括:算术运算、逻辑运算、关系运算、数据传输。算法的控制结构:顺序结构、选择结构、循环结构。 算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度:算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。1.2 数据结构的基本基本概念 数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构; (3)对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。数据的逻辑结构包含: (1)表示数据元素的信息; (2)表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件:(1)有且只有一个根结点;(2)每一个结点最多有一个前件,也最多有一个后件。非线性结构:不满足线性结构条件的数据结构。 1.3 线性表及其顺序存储结构 线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。 计算机二级公共基础知识要点总结 1.栈按先进后出的原则组织数据,所以入栈最早的最后出栈,而队列是先进先出的线性 表。 2.循环队列有队头和队尾两个指针,但是循环队列仍是线性结构的线性表。 在循环队列中只需要对头指针与队尾两个指针来共同反映队列中元素的动态变化情况。 3.当有序线性表为顺序存储时才能用二分法查找。可以证明的是对于长度为n的有序线性 表,在最坏的情况下二分法查找只需要比较log2n次,而顺序查找需要比较n次。 4.链式存储结构既可以针对线性结构也可以针对非线性结构。 链式存储结构中每个结点都由数据域与指针域两部分组成,增加了存储空间。 顺序存储结构的存储一定是连续的,链式存储结构的存储空间不一定是连续的。 5.数据流图中带箭头的线段表示的是数据流,即沿箭头方向传送数据的通道一般在旁边标 注数据流名。 程序流程图中带有箭头的线段表示的是控制流。 6.在软件开发中,需求分析阶段可以使用的工具有数据流图DFD图,数据字典DD,判定 树与判定表。 7.“对象”有如下一些基本特点:标识唯一性,分类型,多态性,封装性,模块独立性好。 8.数据管理发展至今已经历了三个阶段:人工管理阶段,文件系统阶段和数据库系统阶段。 其中最后一个阶段结构简单,使用方便,逻辑性强,物理性少,在各方面的表现都最好,一直占据数据库领域的主导地位。 9.自然链接是一种特殊的等值连接,它要求两个关系中进行比较的分量必须是相同的属性 组,并且在结果中把重复的属性列去掉。 10.内存又称主存,是CPU能直接寻址的存储空间,由半导体器件制成。内存的特点是存取 速率快。所以微机中访问速度最快的存储器是内存。 11.计算机能直接识别和执行的语言是机器语言,机器语言是用二进制代码表示的计算机能 直接识别和执行的一种机器指令的集合。它是计算机的设计者通过计算机的硬件结构赋予计算机的操作功能。机器语言具有灵活,直接执行和速度快等特点。 12.1MB=1024KB=1024*1024B=220B 13.Internet的四层结构分别是:网络接口层,网络层,传输层和应用层。 14.有序线性表既可以采用顺序存储结构,也可以采用链式存储结构。 15.栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表。 16.二叉树的基本性质:在任意一棵二叉树中,度为0的叶子结点总是比度为2的结点多一 个。 例如:某二叉树有五个度为2的结点,则该二叉树中的叶子结点数是5+1=6个。 17.冒泡排序与简单插入排序与简单选择排序法在最坏情况下均需要比较n(n-1)/2次,而堆 排序在最坏的情况下需要比较的次数是nlog2n,即在排序方法中,最坏情况下比较次数最少的是堆排序。 18.软件按功能可分为:应用软件,系统软件和支撑软件(或工具软件)。 19.软件测试的目的是为了发现错误而执行程序的过程,并不涉及改正错误。 程序调试的基本步骤有:错误定位,修改设计和代码,以排除错误进行回归测试,防止引进新的错误。程序调试通常称为Debug,即排错。 20.软件测试的基本准则有:所有测试都应追溯到需求,严格执行测试计划,排除测试的随 意性,充分注意测试中的群集现象,程序员应避免检查自己的程序,穷举测试不可能, 全国计算机等级考试二级公共基础知识考纲 考试内容 一、基本数据结构与算法 1、算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度)。 2、数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。 3、线性表的定义;线性表的顺序存储结构及其插入与删除运算。 4、栈和队列的定义;栈和队列的顺序存储结构及其基本运算。 5、线性单链表、双向链表与循环链表的结构及其基本运算。 6、树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。 7、顺序查找与二分法查找算法;基本排序算法(交换类排序,选择类排序,插入类排序)。 二、程序设计基础 1、程序设计方法与风格。 2、结构化程序设计。 3、面向对象的程序设计方法,对象,方法,属性及继承与多态性。 三、软件工程基础 1、软件工程基本概念,软件生命周戎概念,软件工具与软件开发环境。 2、结构化分析方法,数据流图,数据字典,软件需求规格说明书。 3、结构化设计方法,总体设计与详细设计。 4、软件测试的方法,白盒测试与黑盒测试,测试用例设计,软件测试的实施,单元测试、集成测试和系统 测试。 5、程序的调试,静态调试与动态调试。 四、数据库设计基础 1、数据库的基本概念:数据库,数据库管理系统,数据库系统。 2、数据模型,实体联系模型及E-R图,从E-R图导出关系数据模型。 3、关系代数运算,包括集合运算及选择、投影、连接运算,数据库规范化理论。 4、数据库设计方法和步骤:需求分析、概念设计、逻辑设计和物理设计的相关策略。 考试方式:公共基础的考试方式为笔试,与C语言(VisualBASIC、Visual FoxPro、Java、Access、Visual C++)的笔试部分合为一张试卷。公共基础部分占全卷的30分。公共基础知识有10道选择题和5道填空题。 第一章数据结构与算法 一、内容要点 (一)算法 1.算法的基本概念:算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则,并且 第一章数据结构与算法 算法 1、算法:是指解题方案的准确而完整的描述。算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 2、算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括:(1)可行性;(2)确定性(3)有穷性(4)拥有足够的情报。 3、算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。 4、指令系统:一个计算机系统能执行的所有指令的集合。 5、基本运算包括:算术运算、逻辑运算、关系运算、数据传输。 6、算法的控制结构:顺序结构、选择结构、循环结构。 7、算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。 8、算法复杂度:算法时间复杂度和算法空间复杂度。 9、算法时间复杂度是指执行算法所需要的计算工作量。 10、算法空间复杂度是指执行这个算法所需要的内存空间。 数据结构的基本基本概念 1、数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;(3)对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集合。 2、数据的逻辑结构包含:(1)表示数据元素的信息;(2)表示各数据元素之间的前后件关系。数据的存储结构有顺序、链接、索引等。 3、线性结构条件:(1)有且只有一个根结点;(2)每一个结点最多有一个前件,也最多有一个后件。非线性结构:不满足线性结构条件的数据结构。 线性表及其顺序存储结构 1、线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。 2、非空线性表的结构特征: (1)且只有一个根结点a1,它无前件;(2)有且只有一个终端结点an,它无后件; (3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当n=0时,称为空表。 3、线性表的顺序存储结构具有以下两个基本特点:(1)线性表中所有元素的所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 4、顺序表的运算:插入、删除。 栈和队列 1、栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据,栈具有记忆作用。用top表示栈顶位置,用bottom 表示栈底。 2、栈的基本运算:(1)插入元素称为入栈运算;(2)删除元素称为退栈运算;(3)读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。 3、队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。Rear指针指向队尾,front 指针指向队头。 4、队列是“先进行出”(FIFO)或“后进后出”(LILO)的线性表。 线性链表 计算机二级公共基础 2009-09-14 15:13第一章数据结构与算法 1.1 算法 算法:是指解题方案的准确而完整的描述。 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括: (1)可行性; (2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性; (3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义; (4)拥有足够的情报。 算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。 指令系统:一个计算机系统能执行的所有指令的集合。 基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构:顺序结构、选择结构、循环结构。 算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。算法复杂度:算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本基本概念 数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构; (3)对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含: (1)表示数据元素的信息; (2)表示各数据元素之间的前后件关系。 数据元素之间的前后件关系是指他们的逻辑关系(反映数据元素之间逻辑关系的数据结构),而与他们在计算机中的存储位置无关。 数据的逻辑结构有两个要素:一、数据元素的集合,通常记为D;二、D上的关系,它反映D中各数据元素之间的前后间关系,通常记为R;即一个数据结构可以表示成 B=(D,R)其中B表示数据结构。未反应数据元素间的前后件关系,一般用二元组表示。a,b是D中的两个数据,二元组(a,b)表示a是b的前件,b是a 的后件。 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(数据的物理结构)。数据的存储结构有顺序、链接、索引等。 线性结构条件: (1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。 非线性结构:不满足线性结构条件的数据结构。 计算机二级公共基础知识试题及答案 一、选择题 1.在深度为7的满二叉树中,叶子结点的个数为() A.32 B.31 C.64 D.63 参考答案:C 参考解析:在满二叉树中每层的结点数都达到最大值,而且叶子结点全部出现在最底层。第1层(根结点所在的层)有20个结点,第 2层有21个结点,……第n层有2n-1个结点。在深度为7的满二 叉树中,第7层有27-1=64个结点(全部是叶子结点)、在深度为7 的满二叉树中,共有2^(7-1)=64个结点、因此本题的正确答案是C。 2.下列叙述中正确的是() A.程序执行的效率与数据的存储结构密切相关 B.程序执行的效率只取决于程序的控制结构 C.程序执行的效率只取决于所处理的数据量 D.以上三种说法都不对 参考答案:A 参考解析:程序的执行效率与算法和数据结构有密切的关系,瑞士科学家沃士说过“程序=算法+数据结构”。所以程序执行的效率 与数据的存储结构密切相关;程序执行的效率与程序的控制结构、所 处理的数据量有关,但不绝对相关。因此本题的正确答案是A。 3.下列工具为需求分析常用工具的是 A.PAD B.PFD C.N-S D.DFD 参考答案:D 4.以下算法设计基本方法中基本思想不属于归纳法的.是() A.递推法 B.递归法 C.减半递推技术 D.回溯法 参考答案:D 5.对长度n的线性表排序,在最坏情况下,比较次数不是n(n-1)/2的排序方法是() A.快速排序 B.冒泡排序 C.直接插入排序 D.堆排序 参考答案:D 参考解析:排序技术有:①交换类排序法(冒泡排序法、快速排序法);②插入类排序法(简单插入排序、希尔排序);③选择类排序法(简单选择排序法、堆排序法)。在最坏情况下,希尔排序需要的比较次数是O(nl.5)、堆排序需要的比较次数是O(nlog2n)、其它排序方法需要的比较次数都是n(n.1)/2。因此本题的正确答案是D。 6.按软件的功能划分,需求分析工具软件属于 A.应用软件 B.系统软件 C.支撑软件 D.专用软件 参考答案:C 7.对右下图二叉树进行后序遍历的结果为() A.ABCDEF B.DBEAFC C.ABDECF D.D.EBFCA 参考答案:D 参考解析:后序遍历的方法是:若二叉树为空,则结束返回。否则先后序遍历左子树,再后序遍历右子树,最后访问根结点。本题 1.1 算法 考点1 算法的基本概念计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 算法(algorithm)是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,同时是明确的;此顺序将在有限的次数后终止。算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。 1 算法的基本特征 (1) 可行性(effectiveness):针对实际问题而设计的算法,执行后能够得到满意的结果。 (2) 确定性(definiteness):算法中的每一个步骤都必须有明确的定义,不允许有模棱两可的解释和多义性。 ⑶有穷性(finiteness):算法必需在有限时间内做完,即算法必需能在执行有限个步骤之后终止。 (4)拥有足够的情报:要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时,此算法才最有效的;而当提供的情报不够时,算法可能无效。 2 算法的基本要素 (1) 算法中对数据的运算和操作:每个算法实际上是按解题要求从环境能进行的所 有操作中选择合适的操作所组成的一组指令序列。计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合,称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中,基本的运算和操作有以下 4 类: ①算术运算:主要包括加、减、乘、除等运算; ②逻辑运算:主要包括“与” 、“或”、“非”等运算; ③关系运算:主要包括“大于” 、“小于”、“等于”、“不等于”等运算; ④数据传输:主要包括赋值、输入、输出等操作。 (2) 算法的控制结构:一个算法的功能不仅仅取决于所选用的操作,而且还与各操 作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架,它不仅决定了算法中各操作的执行顺序,而且 也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S 结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3 种基本控制结构组合而成。 (3) 算法设计的基本方法 计算机算法不同于人工处理的方法,下面是工程上常用的几种算法设计,在实际应用时,各种方法之间往往存在着一定的联系。 (1) 列举法 列举法是计算机算法中的一个基础算法。列举法的基本思想是,根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的。 列举法的特点是算法比较简单。但当列举的可能情况较多时,执行列举算法的工作量将会很大。因此,在用列举法设计算法时,使方案优化,尽量减少运算工作量,是应该重点注意的。 (2) 归纳法 归纳法的基本思想是,通过列举少量的特殊情况,经过分析,最后找出一般的关系。从 本质上讲,归纳就是通过观察一些简单而特殊的情况,最后总结出一般性的结论。 (3) 递推递推是指从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已经给定,或是通过对问题的分析与化简而确定。递推本质上也属于归纳法,工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的,因此,递推 关系式往往是归纳的结果。对于数值型的递推算法必须要注意数值计算的稳定性问题。 第1章数据结构与算法 经过对部分考生的调查以及对近年真题的总结分析,笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找,读者应对此部分进行重点学习。 详细重点学习知识点: 1.算法的概念、算法时间复杂度及空间复杂度的概念 2.数据结构的定义、数据逻辑结构及物理结构的定义 3.栈的定义及其运算、线性链表的存储方式 4.树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历 5.二分查找法 6.冒泡排序法 1.1算法 考点1 算法的基本概念 考试链接: 考点1在笔试考试中考核的几率为30%,主要是以填空题的形式出现,分值为2分,此考点为识记内容,读者还应该了解算法中对数据的基本运算。 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 1.算法的基本特征:可行性、确定性、有穷性、拥有足够的情报。 2.算法的基本要素: (1)算法中对数据的运算和操作 基本的运算和操作有以下4类:算术运算、逻辑运算、关系运算和数据传输。 (2)算法的控制结构:算法中各操作之间的执行顺序称为算法的控制结构。 描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。 一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 考点2 算法复杂度 考试链接: 考点2在笔试考试中,是一个经常考查的内容,在笔试考试中出现的几率为70%,主要是以选择的形式出现,分值为2分,此考点为重点识记内容,读者还应该识记算法时间复杂度及空间复杂度的概念。 1.算法的时间复杂度 算法的时间复杂度是指执行算法所需要的计算工作量。 同一个算法用不同的语言实现,或者用不同的编译程序进行编译,或者在不同的计算机上运行,效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素,可以认为一个特定算法"运行工作量"的大小,只依赖于问题的规模(通常用整数n表示),它是问题规模的函数。即 算法的工作量=f(n) 2.算法的空间复杂度 算法的空间复杂度是指执行这个算法所需要的内存空间。 全国计算机二级考试公共基础知识(全) (2010-01-13 17:13:54) 转载 标签:it 分类:天下快报(热点聚焦) 第一章数据结构与算法 经过对部分考生的调查以及对近年真题的总结分析,笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找,读者应对此部分进行重点学习。 详细重点学习知识点: 1.算法的概念、算法时间复杂度及空间复杂度的概念 2.数据结构的定义、数据逻辑结构及物理结构的定义 3.栈的定义及其运算、线性链表的存储方式 4.树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历 5.二分查找法 6.冒泡排序法 1.1算法 考点1 算法的基本概念 考试链接: 考点1在笔试考试中考核的几率为30%,主要是以填空题的形式出现,分值为2分,此考点为识记内容,读者还应该了解算法中对数据的基本运算。 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 1.算法的基本特征:可行性、确定性、有穷性、拥有足够的情报。 2.算法的基本要素: (1)算法中对数据的运算和操作 一个算法由两种基本要素组成:一是对数据对象的运算和操作;二是算法的控制结构。 在一般的计算机系统中,基本的运算和操作有以下4类:算术运算、逻辑运算、关系运算和数据传输。 (2)算法的控制结构:算法中各操作之间的执行顺序称为算法的控制结构。 描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 考点2 算法复杂度 考试链接: 考点2在笔试考试中,是一个经常考查的内容,在笔试考试中出现的几率为70%,主要是以选择的形式出现,分值为2分,此考点为重点识记内容,读者还应该识记算法时间复杂度及空间复杂度的概念。 1.算法的时间复杂度 算法的时间复杂度是指执行算法所需要的计算工作量。 同一个算法用不同的语言实现,或者用不同的编译程序进行编译,或者在不同的计算机上运行,效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素,可以认为一个特定算法"运行工作量"的大小,只依赖于问题的规模(通常用整数n表示),它是问题规模的函数。即 算法的工作量=f(n) 2.算法的空间复杂度 算法的空间复杂度是指执行这个算法所需要的内存空间。 一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数,则称该算法是原地工作的。在许多实际问题中,为了减少算法所占的存储空间,通常采用压缩存储技术,以便尽量减少不必要的额外空间。 疑难解答:算法的工作量用什么来计算? 算法的工作量用算法所执行的基本运算次数来计算,而算法所执行的基本运算次数是问题规模的函数,即算法的工作量=f(n),其中n 是问题的规模。 1.2数据结构的基本概念 考点3 数据结构的定义 考试链接: 考点3在笔试考试中,是一个经常考查的内容,在笔试考试中出现的几率为70%,主要是以选择的形式出现,分值为2分,此考点为识记内容,读者还应该识记数据的逻辑结构和存储结构的概念。 数据结构作为计算机的一门学科,主要研究和讨论以下三个方面: (1)数据集合中个数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据元素进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构; (3)对各种数据结构进行的运算。 2020年全国计算机等级考试二级公共基础知识必 考重点提纲(精华版) 第一章数据结构与算法 1.1算法 算法:是指解题方案的准确而完整的描述。 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。 特征包括: (1)可行性; (2)确定性,算法中每一步骤都必须有明确定义,不允许有模棱两可的解释,不允许有多义性; (3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义; (4)拥有足够的情报。 算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。 基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构:顺序结构、选择结构、循环结构。 算法基本设计方法:列举法、归纳法、递推、递归、减半递推技术、回溯法。 算法复杂度:算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 一般来说,算法的工作量用其执行的基本运算次数来度量,而算法执行的基本运算次数是问题规模的函数。在同一个问题规模下,用平均性态和最坏情况复杂性来分析。一般情况下,用最坏情况复杂性来分析算法的时间复杂度。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2数据结构的基本概念 数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构; (3)对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据结构是反映数据元素之间关系的数据元素集合的表示。 数据的逻辑结构包含: (1)表示数据元素的信息; (2)表示各数据元素之间的前后件关系。(逻辑关系,与在计算机内的存储位置无关) 一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系有可能不同。 数据的存储结构是数据的逻辑结构在计算机存储空间中的存放形式。 常用的存储结构有顺序、链接、索引等。 整理好的超完整计算机二级公共基础知识 第1章数据结构与算法 经过对部分考生的调查以及对近年真题的总结分析,笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找,读者应对此部分进行重点学习。 详细重点学习知识点: 1.算法的概念、算法时间复杂度及空间复杂度的概念 2.数据结构的定义、数据逻辑结构及物理结构的定义 3.栈的定义及其运算、线性链表的存储方式 4.树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历 5.二分查找法 6.冒泡排序法 1.1算法 考点1 算法的基本概念 考试链接: 考点1在笔试考试中考核的几率为30%,主要是以填空题的形式出现,分值为2分,此考点为识记内容,读者还应该了解算法中对数据的基本运算。 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 1.算法的基本特征:可行性、确定性、有穷性、拥有足够的情报。 2.算法的基本要素: (1)算法中对数据的运算和操作 基本的运算和操作有以下4类:算术运算、逻辑运算、关系运算和数据传输。 (2)算法的控制结构:算法中各操作之间的执行顺序称为算法的控制结构。 描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。 一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 考点2 算法复杂度 考试链接: 考点2在笔试考试中,是一个经常考查的内容,在笔试考试中出现的几率为70%,主要是以选择的形式出现,分值为2分,此考点为重点识记内容,读者还应该识记算法时间复杂度及空间复杂度的概念。 1.算法的时间复杂度 算法的时间复杂度是指执行算法所需要的计算工作量。 同一个算法用不同的语言实现,或者用不同的编译程序进行编译,或者在不同的计算机上运行,效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素,可以认为一个特定 .WORD.格式.2011全国计算机等级考试二级公共基础知识教程
全国计算机等级考试二级公共基础知识要点汇总
二级公共基础知识分类模拟题43
全国计算机二级考试公共基础知识总结
计算机二级公共基础知识(全)
全国计算机等级考试二级公共基础知识练习题及答案.doc
全国计算机等级考试二级公共基础知识
计算机二级公共基础知识要点总结
全国计算机等级考试二级公共基础知识考纲
计算机二级公共基础知识高频考点归纳总结
二级公共基础知识
计算机二级公共基础知识试题及答案
计算机二级公共基础知识(全)
整理好的超完整计算机二级公共基础知识
全国计算机二级考试公共基础知识
2020年全国计算机等级考试二级公共基础知识必考重点提纲(精华版)
整理好的超完整计算机二级公共基础知识
全国计算机等级考试二级公共基础知识__复习试题提纲
1.1 算法 算法:是解题方案的准确而完整的描述。通俗地说,算法就是计算机解题的过程。算 法不等于程序,也不等于计算方法,程序的编制不可能优于算法的设计。 (1)确定性,算法中每一步骤都必须有明确定义,不允许有模棱两可的解释,不允许有 多义性; (2)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止; (3)可行性,算法原则上能够精确地执行; (4)拥有足够的情报。 算法效率的度量—算法复杂度:算法时间复杂度和算法空间复杂度。★★★ 算法时间复杂度:指执行算法所需要的计算工作量。即算法执行过程中所需要的基本 运算次数。 算法空间复杂度:指执行这个算法所需要的内存空间。 1.2 数据结构的基本概念 数据结构:指相互有关联的数据元素的集合。 数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构; (3)对各种数据结构进行的运算。 线性结构的条件,(一个非空数据结构): (1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。 非线性结构:不满足线性结构条件的数据结构。 1.3 线性表及其顺序存储结构 线性表的顺序存储结构具有以下两个基本特点: (1)线性表中所有元素所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 顺序表的运算:查找、插入、删除。 1.4 线性链表 数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点,简称结 点。 结点由两部分组成: (1) 用于存储数据元素值,称为数据域; (2) 用于存放指针,称为指针域,用于指向前一个或后一个结点。 在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与 数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。 链式存储方式即可用于表示线性结构,也可用于表示非线性结构。 线性链表的基本运算:查找、插入、删除。
.专业资料.整理分享.