数据结构与 c 语言模拟题一
第一部分C 语言( 90 分)
一.选择题( 20 分)
1、执行下面程序后，输出结果是()
main()
{ a=45,b=27,c=0;
c=max(a,b);
printf("%d\n",c);
}
int max(x,y)
int x,y;
{ int z;
if(x>y) z=x;
else z=y;
return(z);
}
A:45 B:27 C:18 D:72
2、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 array[][4]; B:int array[][]; C:int array[][][5]; D:int array[3][];
6、下面有关for 循环的正确描述是( )
A:for 循环只能用于循环次数已经确定的情况
B:for 循环是先执行循环体语句,后判断表达式
C:在for循环中，不能用break语句跳出循环体
D:for 循环的循环体语句中,可以包含多条语句,但必须用花括号括起来
7、若有下列定义int a[5],*p=a;,则对a数组元素地址的正确引用是()
A:*(p+5) B:*p+2 C: &a[4] D: *p
8、以下( )是正确的变量名
A: 5f B: if C: f.5 D: _f5
9、在 C 语言中，形参的缺省存储类是（
）
A:auto B:register C:static D:extern
10、下列程序的输出结果是 ( ) 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=%d\n",a,b); }
A:a=1,b=0 B:a=2,b=1 C:a=1,b=1 D:a=2,b=2
11、以下能对二维数组 a 进行正确初始化的语句是( )
13、设有说明 :char w;int x;float y;double z; 则表达式 w*x+z-y 值的数据类型 为（ ）
A:float B:char C:int D:double 14、若已定义 x 为 int 类型变量 ,下列语句中说明指针变量 p 的正确语句是 ( ) A:int p=&x; B:int *p=x; C:int *p=&x; D:*p=*x;
15、 若有以下定义int k=7,x=12;,则能使值为3的表达式是 ()
A:x%=(k%=5) B:x%=(k-k%5) C:x%=k-k%5 D:(x%=k)-(k%=5)
16、 经过int x=1,y=2,z=3;语句定义后,表达式z+=x>y?++x:++y 的值为()
A:2 B:3 C:6 D:5
17、 下面程序段的输出结果为 ( )
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%2
19、执行 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=10
A:int a[2][]={{1,0,1},{5,2,3}};
C:int a[2][4]={{1,2,3},{4,5},{6}};
12、以下程序的运行结果是
( main()
{ int n; for(n=1;n<=10;n++)
{
if(n%3==0) continue;
printf("%d",n);
}
}
A:12457810 B:369 C:12
B:int a[][3]={{1,2,3},{4,5,6}}; D:int a[][4]={{1,0,1}{},{1,1}}; ) D:1234567890
20、有如下程序段,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，%d\n”，a，x)；
3、当a=1、b=2、c=3 时，执行以下if 语句后，a= 、b= 、c=
if (a>c)；b=a；a=c；c=b；
4、将以下嵌套的if 语句改写成不嵌套的if 语句：。
if (w<0) k=0；else if( w<= 1 00) k=1；else k=0；
5、以下程序的输出结果。
main()
{ int x=2 ；while(x--)；printf (“%d\n”，x)；}
6、若有定义：int a[3][4]={{1 ，2}，{0} ，{4 ，6，8，1 0}} ；则初始化后，a[1][2]得到的初值是,a[2][1 ]得到的初值是。
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=%d\n",a,b);
}
2、#include
{
char ch1 = 'E'; if (ch1 >= 'A') ch1++;
else ch1+=32;
printf("ch1 = %c\n", ch1);
}
3、#include
{
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
{
int number , digit; number= 1234; while ( number!= 0 )
{
digit = number%10 ; printf( "%d" , digit ) ; number = number / 10 ;
}
}
5、#include
{
int i=10,m=0,n=0; do
{
if(i%2!=0)
m=m+i;
else
n=n+i;
i--;
}while(i>=0); printf("m=%d,n=%d\n",m,n); return 0;
}
6、#include
void main()
{
int a,b;
for(a=1,b=1;a<=100;a++)
{
if(b>20) break;
if(b%4==1)
{
b=b+4;
continue;
}
b=b-5;
}
printf("a=%d\n",a);
}
7、#include
void main()
{
char ch;
while((ch=getchar())!='\n')
{
if (ch>='A'&&ch<='Z') ch=ch+32;
else if (ch>='a'&&ch<='z')
ch=ch-32;
printf("%c",ch);
}
}
输入：ABCdefv回车>
8、#include
int main ()
{
int a, b;
for (a = 1, b = 1 ; a <= 100 ; a++) {
if (b >= 9) break;
if (b % 3 == 1)
{ b += 3 ; continue ;
} b -= 5;
} printf("%d,%d\n", 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 3
4、快速排序在最坏情况下的时间复杂度为( ) A．O(log2n) B ．O(nlog2n) C．0(n) D．0(n2)
5、二叉树的第k 层的结点数最多为( )
A．2k-1 B.2K+1 C.2K-1 D. 2k-1
6、对于线性表( 7，34，55，25，64，46，20，10)进行散列存储时，
若选用H(K)=K%9 作为散列函数，则散列地址为 1 的元素有( )个A．1 B．2 C．3 D．4
7、设有6 个结点的无向图，该图至少应有( )条边才能确保是一个连通
精品文档
图
A.5
B.6
C.7
D.8
8、将长度为n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度为（）
A．O（1）B．O（n）C．O（m）D．O（m+n）
9、用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（）
A ?选择排序
B ?希尔排序
C ?归并排序
D ?快速排序
10、根据二叉树的定义可知二叉树共有（）种不同的形态。
A．4 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，贝U该二叉树的后序遍历序列为__________ 。
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)，设散列表为HT[0..12]，散列函数为H (key) = key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。
四.算法设计题(20分)
1. 假设以带头结点的单链表表示线性表，单链表的类型定义如下：
typedef int DataType;
typedef struct node {
DataType data;
struct node * n ext;
}LinkNode, * LinkList;
编写算法，删除线性表中最大元素(假设最大值唯一存在)。函数原型为：void fun (Lin kList head);
2. 设二叉树T采用二叉链表结构存储，数据元素为int型，试设计一个算法,
若结点左孩子的data域的值大于右孩子的data域的值，则交换其左、右子树。
void algo2(Bitreptr bt)
{
Bitreptr x;
if(bt){
if((bt-
>lchil
d&&bt
->rchi
ld)&&
(bt-
lchild-
>data
>bt-
rchild-
>data
))
{ x=bt->lchild; bt->lchild=bt->rchild;
bt->rchild=x;
}
algo2(bt->lchild);
algo2(bt->rchild);
}
}