《2009__第一部分_c语言程序设计》由会员分享，可在线阅读，更多相关《2009__第一部分_c语言程序设计（16页珍藏版）》请在金锄头文库上搜索。
1、2009 第一部分 C 语言程序设计（共 100 分） 一、单项选择题（本大题共 30 小题，每小题 2 分，共 60 分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将正确答案代码填写在答题 纸相应的位置上。 1、下列选项中，合法的 C 语言标识符是（ ） （A）my_name （B）$234 （C）my name （D）23b 2、已知：int x=5; 执行完 printf(“%d“,+x); 后，输出的结果是（ ） （A）4 （B）5 （C）6 （D）不确定 3、已知：int x=5,y=3; 则逻辑表达式(x-y) 则执行完语句：a=ab?a:(b0) x*=2; y/=
2、3; printf(“%d,%d“,x,y); （A）8,0 （B）16,0 （C）32,0 （D）64,0 9、如下选项中正确的数组定义是（ ） 。 （A）#define m 10; static int am=3,4,5,6; （B）static int a2=3,4,5,6; （C）static int a10=3,4,5,6; （D）int m=4; static int am=3,4,5,6; 10、执行程序段：char str12; scanf(“%s“,str); 如果输入如下字符串（其中表示空格）： Whatsyouname? 则 str 的值是（ ） 。 （A）Whats （
3、B）Whats （C）Whatsyour （D）Whatsyourname? 11、如下程序段的运行结果是（ ） 。 main() int i=5,sum=100; do sum=sum+(-i);while(i=0); printf(“%d“,sum); （A）100 （B）109 （C）105 （D）110 12、如下程序段的运行结果是（ ） 。 main() int i; for(i=1;iname=ddd; p-score=66.0; p-age=15; （D）p= p.name=“ddd“; p.score=66.0; p.age=15; 22、下面程序段中语法正确的是（ ） 。 （
4、A）int mm(int x,int y)int x,y; return x+y; （B）char str10; scanf(“%s“, （C）int i,a10;for(i=0;i0) （C）!(a=1) （D）(a=1) 24、若变量已经正确定义，要求程序段完成 1 到 100 的累加，下列选项中不能完成此功能 的程序段是（ ） 。/此题有误 （A）for(i=1,sum=0; i2 （D）k=1 26、如下程序段的输出结果是（ ） 。 main() int i,j,a=0; for(i=1;i void main() char str1=“goodmorning!“,str220; ch
5、ar *p,*q; for(p=str1; *p!=0; p+); for(q=str2; -p=str1; q+) *q=*p; *q=0; printf(“%s“,str2); 32、 #include #define n 10 void de(int a,int x,int *m) int i=x+1; for(;i void ch(int *a,int *b) int c; c=*a; *a=*b; *b=c; void main() static int a10=32,5,18,56,98,52,78,15,132,112; int x=0,y=1,i; if(axay) ch( f
6、or(i=2;iay) y=i; ch( for(i=0;i void main() char str=“0342201411“; static int a10; int i; char *p; for(i=0;i #define m 3 #define n 4 int findmax(int an) int i,j,max=a00; for(i=0;imax) max=aij; _; void main() int i,j,max,_; for(i=0;i #include void main() int m,k,i; for(m=101;mk) printf(“%d“,m); 第二部分 数
7、据结构（共 100 分） 一、单项选择题（本大题共 12 小题，每小题 2 分，共 24 分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将正确答案代码填写在答题 纸相应位置上。1、要表示高校的校、系、班级的有关数据及其关系，选择（ ）比较合适。 （A）线性结构 （B）树结构 （C）图结构 （D）集合结构 2、下列函数中渐进时间复杂度最小的是（ ） 。 （A）T(n)=nlogn+5000n （B）T(n)=n*n-8000n （C）T(n)=n 的(log(2n)次方-6000n （D）T(n)=2n 的(log(2n)次方-7000n 3、已知一个栈 s 以及一个输入序列(A,
8、B,C,D,E)，每个元素按照 A、B、C、D、E 顺序进栈一 次，进栈后可立即出栈，也可在栈中停留一段时间后再出栈，则不能得到（ ）序列。 （A）A,B,C,D,E （B）B,A,E,D,C （C）C,B,A,D,E （D）D,C,A,B,E 4、平均排序效率最好的排序方法是（ ） 。 （A）直接插入排序 （B）快速排序 （C）简单选择排序 （D）冒泡排序 5、某链表中最常用的操作是在已知的一个结点之前插入一个新结点和删除其之前一个结点， 则采用（ ）存储方式最节省运算时间。 （A）双向链表 （B）带头结点的单向链表 （C）带尾指针的单向链表 （D）单向循环链表 6、在逻辑结构不变的情况下，
9、不是导致一个图的遍历序列不唯一的因素是（ ） 。/？ （A）出发点不同 （B）存储（物理）结构不同 （C）遍历方法不同 （D）画法不同 7、散列函数有一个共同的要求，即函数值应当尽量以（ ）取其值域的每个值。 （A）最大概率 （B）最小概率 （C）正态分布概率 （D）均等概率 8、下面（ ）方法可以判断出一个图中是否存在环（回路） 。/？ （A）排序 （B）深度和广度遍历 （C）求最短路径 （D）求关键路径 9、最佳二叉搜索（排序）树是（ ） 。 （A）关键码个数最小的二叉搜索树 （B）退化为线性的二叉搜索树 （C）搜索中平均比较次数最小的二叉搜索树 （D）任何结点的度数为 0 或 2 的二叉
10、搜索树 10、 （ ）是数据的基本单位，即数据集合（对象）中的个体 （A）数据结构 （B）数据项 （C）数据元素 （D）数据对象 11、 （线性）表是一个（ ） 。 （A）有限序列，可以为空 （B）有限序列，不能为空 （C）无限序列，可以为空 （D）无限序列，不能为空12、树是结点的集合，它（ ）根结点。 （A）有 0 个或 1 个 （B）有 0 个或多个 （C）有且只有 1 个 （D）有 1 个或 1 个以上 二、填空题（本大题共 7 小题，每空 2 分，共 16 分） 请将答案写在答题纸相应的位置上。 13、在有 n 个顶点的有向图中，每个顶点的度最大可达_。 14、以下程序段的时间复杂度
11、是_。 i=0; j=0; while(i+jj) j+; else i+; 15、下图所示的二叉树后序遍历的结果是_。A/ B F/ E C G/ / D H J/I16、在一个双向链表中 p 所指结点之前插入一个由指针 s 所指的新结点，写出可执行的操 作序列：_。 （前指和后指的指针预分别为 prior 和 next） 17、 （线性）表有两种存储结构：顺序存储结构和链式存储结构，请就这两种存储结构完成 下列填充：_存储密度较大，可以随机存取；_不可以随机存取，插入 和删除操作比较方便。 18、递归的程序执行时使用_来保存各层递归调用时的现场信息，以保证可以正 确返回。 19、设数组 a
12、M（M 为最大空间个数）作为循环队列 Q 的存储空间，front 为队头指针 （指向第一个存放数据的位置） ，rear 为队尾指针（指向最后一个存放数据位置的下一个） ， 则判定 Q 队列的队满条件是_。 三、应用题（本大题共 4 小题，每小题 10 分，共 40 分） 请将答案写在答题纸相应的位置上。 20、设字符集 D=A,B,C,D,E，各字符使用频率 W=10,2,5,6,4。画出对字符进行哈夫曼编码 时所对应的哈夫曼树，并给出各字符的编码。21、用普里姆（Prim）算法从右图中的顶点 1 开始逐步构造最小支撑（代价生成）树，要 求画出构造的每一步。16 5 21 19 14 9 26
13、 11 6 1822、给定待排序关键字集合为23,14,48,25,5,19，按关键字非递归递减（从小到大）排序， 写出采用冒泡排序的每一趟（最外层循环的每一次）排序结果。23、 （1）图示表示右边有向图的邻接表。 （4 分）（2）写出从顶点 1 开始分别进行深度优先和广度优先遍历的顶点序列各一种。 （6 分） 四、算法设计题（本大题共 2 小题，每小题 10 分，共 20 分） 请将答案写在答题纸相应的位置上。24、假定用一个有头结点循环链表来存储一个有序的线性表，线性表从头到尾为非递减 （从小到大）有序（如下图） 。用指针 current 从 head 开始搜索数据域等于 key 的元素在线 性表中位置，如果搜索成功则 current 指向搜索到的结点，函数返回该指针；如果搜索不成 功，函数返回空指针 NULL。请在函数 SortedlistLocate(head,ky)内填空，完成下列算法以实 现这种搜索，并使得搜索不成功的平均比较次数小于链表长度。 head 10 20 30 40 50 60 currenttypedef struct node elemtype data;/数据域 struct node *next; /指针域 lnode,*linklist; linklist SortedlistLocate(linklist h
