华中师范大学计算机考研874专业课模拟题.doc

.数据结构与c语言模拟题一第一部分 C语言（90分）一.选择题（20分）1、执行下面程序后，输出结果是（）main() a=45,b=27,c=0;c=max(a,b);printf(%dn,c);int max(x,y)int x,y; int z;if(xy) z=x;else z=y;return(z);A:45 B:27 C:18 D:722、C语言源程序的基本单位是( )A:过程 B:函数 C:子程序 D:标识符3、设C语言中,int类型数据占4个字节,则short类型数据占( )A:1个字节 B:2个字节 C:4个字节 D:8个字节4、以下描述中，正确的是（ ）A:预处理是指完成宏替换和文件包含中指定的文件的调用B:预处理指令只能位于C源文件的开始C:C源程序中凡是行首以#标识的控制行都是预处理指令D:预处理就是完成C编译程序对C源程序第一遍扫描,为编译词法和语法分析作准备5、 下列数组说明中，正确的是（ ）A:int array4; B:int array; C:int array5; D:int array3;6、下面有关for循环的正确描述是 ( )A:for循环只能用于循环次数已经确定的情况B:for循环是先执行循环体语句,后判断表达式C:在for循环中,不能用break语句跳出循环体D:for循环的循环体语句中,可以包含多条语句,但必须用花括号括起来7、 若有下列定义int a5,*p=a;,则对a数组元素地址的正确引用是( ) A:*(p+5) B:*p+2 C: &a4 D: *p8、以下（ ）是正确的变量名A: 5f B: if C: f.5 D: _f59、在C语言中，形参的缺省存储类是（ ）A:auto B:register C:static D:extern10、下列程序的输出结果是( )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+;break;printf(a=%d,b=%dn,a,b);A:a=1,b=0 B:a=2,b=1 C:a=1,b=1 D:a=2,b=211、以下能对二维数组a进行正确初始化的语句是（ ）A:int a2=1,0,1,5,2,3; B:int a3=1,2,3,4,5,6;C:int a24=1,2,3,4,5,6; D:int a4=1,0,1,1,1;12、以下程序的运行结果是（ ）main() int n;for(n=1;ny?+x:+y的值为( )A:2 B:3 C:6 D:517、下面程序段的输出结果为( )int a,b;b=(a=3*5,a*4,a*5); printf(%d,b);A:60 B:75 C:65 D:无确定值18、若希望当A的值为奇数时,表达式的值为真,A的值为偶数时,表达式的值为假,则以下不能满足要求的表达式是( )A:A%2=1 B:!(A%2=0) C:!(A%2) D:A%219、执行y=10;x=y+;后变量x和y的值是( )A:x=10, y=10 B:x=11,y=11 C:x=10,y=11 D:x=11,y=1020、有如下程序段,int x=23; do printf(%d,x-); while(!x); 该程序的输出结果是 ( )A:321 B:23 C:不输出任何内容 D:陷入死循环二.填空题（10分）1、C语言源程序文件的后缀是 ，经过编译后，生成文件的后缀是 ，经过连接后，生成文件的后缀是 。2、以下程序段的输出结果是 。a=3+5，a*4；x=11/3；printf（“%d，%dn”，a，x）；3、当a=1、b=2、c=3时，执行以下if语句后，a= 、b= 、c= 。if（ac）；b=a；a=c；c=b；4、将以下嵌套的if语句改写成不嵌套的if语句： 。if（w0） k=0；else if（w=100） k=1； else k=0；5、以下程序的输出结果 。main（） int x=2；while（x-）；printf（“%dn”，x）；6、若有定义：int a34=1，2，0，4，6，8，10；则初始化后，a12得到的初值是 ，a21得到的初值是 。7、若有定义：char ch；使指针p指向变量ch的赋值语句是 。8、在C程序中数据可以用两种代码形式存放，它们是 和 。9、若s是int型变量，则表达式s%2+(s+1)%2的值为 。10、若a是int 型变量，且a的初值为6，则计算表达式a+=a-=a*a后a的值为 。三、程序阅读题（40分）1、#include void main( ) int x=1,a=2,b=3;switch(x) case 1: a-; break;case 2: b+; break;case 3: a+;b+;printf(na=%d,b=%dn,a,b);2、#include void main( )char ch1 = E;if (ch1 = A)ch1+;elsech1+=32;printf(ch1 = %cn, ch1);3、#include int main()char ch1=A,ch2=B;switch(ch1)case A:switch(ch2)case B: printf(Good!n);break;case A: printf(Better!n);break;case B: printf(Best!n); break;return 0;4、#include void main()int number , digit;number= 1234;while ( number!= 0 ) digit = number%10 ;printf( %d , digit ) ;number = number / 10 ;5、#include int main()int i=10,m=0,n=0;doif(i%2!=0)m=m+i;elsen=n+i;i-;while(i=0);printf(m=%d,n=%dn,m,n);return 0;6、#include void main()int a,b;for(a=1,b=1;a20) break;if(b%4=1)b=b+4;continue;b=b-5;printf(a=%dn,a);7、#include void main()char ch;while(ch=getchar()!=n) if (ch=A&ch=a&ch=z)ch=ch-32;printf(%c,ch);输入：ABCdef8、#include int main ()int a, b;for (a = 1, b = 1 ; a = 9) break;if (b % 3 = 1)b += 3 ;continue ;b -= 5;printf(%d,%dn, a, b);return 0;四、编程题（20分）1、利用字符读写函数实现文件拷贝。2、利用字符指针实现字符串的倒序排列 。第二部分 数据结构（60分）一、选择题（10分）1、在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )A. p-next=HL-next; HL-next=p; B. p-next=HL; HL=p;C. p-next=HL; p=HL; D. HL=p; p-next=HL;2、对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素 B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变3、一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( )A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 34、快速排序在最坏情况下的时间复杂度为（ ）AO(log2n) BO(nlog2n) C0(n) D0(n2)5、二叉树的第k层的结点数最多为( )A2k-1 B.2K+1 C.2K-1 D. 2k-16、对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（ ）个A1 B2 C3 D47、设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图A.5 B.6 C.7 D.88、将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ）AO（1） BO（n） CO（m） DO（m+n）9、用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（ ）A选择排序 B希尔排序 C归并排序 D快速排序10、根据二叉树的定义可知二叉树共有（ ）种不同的形态。A4 B. 5 C.6 D.7二、填空题（10分）1.为了能有效地应用HASH查找技术，必须解决的两个问题是_和_。2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为_，在链式存储结构上实现顺序查找的平均时间复杂度为_。3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有_个指针域，_个空指针域。4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为_。5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_个表头结点和_个表结点。6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有_关系。7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为_。8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是_，编号为8的左孩子结点的编号是_。9. 数据的物理结构主要包括_和_两种情况。10.设一个连通图G中有n个顶点e条边，则其最小生成树上有_条边。三、计算题（20分）1.设有一个输入数据的序列是 46, 25, 78, 62, 12, 80 , 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。2.对于下图所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：(1) 从顶点出发进行深度优先搜索所得到的深度优先生成树；(2) 从顶点出发进行广度优先搜索所得到的广度优先生成树；3.请画出下图的邻接矩阵和邻接表。4.已知一组记录的排序码为（46，79，56，38，40，80, 95），写出对其进行快速排序的前两次划分结果。5.一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT0.12，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。四.算法设计题（20分）1.假设以带头结点的单链表表示线性表，单链表的类型定义如下：typedef int DataType;typedef struct node DataType data;struct node * next;LinkNode, * LinkList;编写算法，删除线性表中最大元素(假设最大值唯一存在)。函数原型为：void fun (LinkList