计算机科学与技术《专业综合》试卷

__…__…__…__…__…__…__…__…__…__…__…__…目…科… … … … 密 … _…__…__…__…__…__…__…_名…姓封 … … … … … …__…__…__…__线__…__…号…名…报………………………………注意：答案一律书写在答题纸上，在试卷上答题一律无效。 一、选择题（2分×45＝90分） 1、一个C语言程序是由（ ）。 A) 一个主程序和若干子程序组成 B) 函数组成 C) 若干过程组成 D) 若干子程序组成 2、C语言中的标识符只能由字母、数字和下划线三种字符组成，且第一个字符（ ）。 A) 必须为字母 B) 必须为下划线 C) 必须为字母或下划线 D) 可以是字母、数字和下划线中任一字符 3、以下不正确的叙述是（ ）。 A) 在C程序中，逗号运算符的优先级最低 B) 在C程序中，APH和aph是两个不同的变量 C) 若a和b类型相同，在计算了赋值表达式a=b后b中的值将放入a中，而b中的值不变 D) 从键盘输入数据时，对于整型变量只能输入整型数值，对于实型变量只能输入实型数值 4、以下变量赋初值不正确的是（ ）。 A) int a = 3 B) int a,b=2,c=3 C) int a=1,b=2,c=3 D) int a=b=c=3 5、设变量f,a,b,c都为int型，其中a=3,b=2,c=1,有表达式f=a>b>c,则变量f的值为（ ）。 A) 3 B) 2 C) 1 D) 0 6、有以下程序 main( ) { char k; int i; for(i=1;i<3;i++) { scanf(“%c”,&k); 第 1 页 共 12 页

switch(k)

{ case ‘0’: printf(“another\\n”);

case ‘1’: printf(“number\\n”);

} } }

程序运行时，从键盘输入：01<回车>，程序执行后的输出结果是（ ）。 A) another B) another C) another D) number number number number number another number

7、已知x,y,z均为整型变量，且值均为1，则执行语句++x||++y&&++z;后，表达式x+y的值为（ ）。

A）1 B）2 C）3 D）4 8、有以下程序

main( ) { int i,s=0;

for(i=1;i<10;i+=2) s+=i+1; printf(“%d\\n”,s); }

程序执行后的输出结果是（ ）。

A) 自然数1～9的累加和 B) 自然数1～10的累加和 C) 自然数1～9中的奇数之和 D) 自然数1～10中的偶数之和 9、在C语言中，引用数组元素时，其数组下标的数据类型允许是（ ）。 A) 整型常量 B) 整型表达式 C) 整型常量或整型表达式 D) 任何类型的表达式 10、以下数组元素的初始化不正确的是（ ）。

A) int a[5]={ 0 } B) int a[5]={ 1,2,3 } C) int a[ ]= {1,2,3,4,5} D) int a[5];a={1,2,3,4,5}

11、已知：char a［20］,b［20］={\"Student\则在程序中能将字符串\"Student\"赋给数组a的正确语句是（ ）。

A）a=\"Student\"; B）strcpy（b,a）; C）a=b; D）strcpy（a,b）; 12、有以下程序 #include main（） { int y=9;

第 2 页 共 12 页

for（ ; y>0;y--）

if（y%3==0） printf（\"%d\）; }

程序的运行结果是 （ ）。

A）321 B）963 C）987654 D）987654321 13、有以下程序 main( )

{ int num[4][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}},i,j; for(i=0;i<4;i++) { for(j=_____;j<4;j++)

printf(\"%4d\

printf(\"\\n\"); } }

若要按以下形式输出数组元素 1 2 3 4 6 7 8 11 12 16

则在程序下划线处应填入的是 （ ）。 A) i-1 B) i C) i+1 D) 4-i 14、阅读下面程序，输出结果是（ ）。 #include \"stdio.h\" void fun（int *a,int *b） { int c=20,d=25; *a=c/3; *b=d/5; } main（ ） { int a=3,b=5; fun（&a,&b）;

printf（\"%d,%d＼n\）; }

A）6,5 B）5,6 C）20,25 D）3,5 15、有以下程序

第 3 页 共 12 页

int f(int b[][4]) { int i,j,s=0; for(j=0;j<4;j++) { i=j;

if(i>2) i=3-j; s+=b[i][j]; } return s; } main( )

{ int a[4][4]={{1,2,3,4},{0,2,4,5},{3,6,9,12},{3,2,1,0}}; printf(“%d\\n”,f(a)); } 执行后的输出结果是（ ）。 A) 12 B) 11 C) 18 D) 16 16、有以下程序 void f(char *p) { p + = 3 ; } main( )

{ char b[4]={'a','b','c','d'},*p=b; f(p);

printf(\"%c\\n\}

程序运行后的输出结果是 （ ）。 A) a B) b C) c D) d

17、有定义：int n=0,*p=&n,**q=&p;则以下选项中，正确的赋值语句是（ ）。 A) p=1; B) *q=2; C) q=p; D) *p=5; 18、有以下程序段

int a[10]={1,2,3,4,5,6,7,8,9,10},*p=&a[3],b;b=p[5];b中的值是（ ）。 A) 5 B) 6 C) 9 D) 8

19、以下语句或语句组中,能正确进行字符串赋值的是（ ）。 A) char *sp;*sp=\"right!\"; B) char s[10];s=\"right!\"; C) char s[10];*s=\"right!\"; D) char *sp=\"right!\"; 20、有以下结构体说明和变量定义： struct node

{int data;struct node *next;}*p,*q,*r; 假设指针p、q、r分别指向此链表中的

第 4 页 共 12 页

三个连续结点，现要将q所指结点从链表中删除，同时要保持链表的连续， 以下不能完成指定操作的语句是（ ）。

A) p->next=q->next; B) p->next=p->next->next; c) p->next=r;

D) p=q->next;

21、算法的时间复杂度是指（ ）。

A) 执行算法程序所需要的时间 B) 算法程序的长度 C) 算法执行过程中所需要的基本运算次数 D) 算法程序中的指令条数 22、具有线形结构的数据结构是（ ）。 A) 树 B) 图 C) 栈和队列 D) 以上都不是 23、线性链表不具有的特点是（ ）。

A) 随机访问 B) 不必事先估计所需存储空间大小 C) 插入与删除时不必移动元素 D) 所需空间与线性表长度成正比

24、长度为N的线性表，进行顺序查找，在查找不成功时，与关键字的比较次数为 ( )。

A) N B) 1 C) N-1 D) 0

25、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）。（0<=i<=n）

A) O(0) B) O(1) C) O(n) D) O(n2)

26、 在一个含有头节点的单链表中,头指针为head,判断其是否为空的条件为（ ）。 A) head==NULL B) head->next==NULL C) head->next==head D) head!=NULL 27、串的长度是指（ ）。

A) 串中所含不同字母的个数 B) 串中所含字符的个数 C) 串中所含不同字符的个数 D) 串中所含非空格字符的个数 28、（ ）是C语言中“abcd321ABCD”的子串。

A) abcd B) 321AB C) “abcABC” D) “21AB” 29、队列操作的原则是（ ）。

A) 先进先出 B) 后进先出 C) 只能进行插入 D) 只能进行删除 30、向顺序栈中压入新元素时，应当（ ）。

A) 先移动栈顶指针，再存入元素 B) 先存入元素，再移动栈顶指针 C) 先后次序无关紧要 D) 同时进行

31、设栈的输入序列是（1、2、3、4），则（ ）是不可能的输出序列。 A) 1243 B) 2134 C) 1432 D) 4312

第 5 页 共 12 页

32、下列有关二叉树的说法正确的是（ ）。

A) 二叉树的度为2 B) 一棵二叉树的度可以小于2 C) 二叉树中至少有一个结点的度为2 D) 二叉树中任何一个结点的度为2 33、一棵有16个节点的完全二叉树，对它按层编号，根节点的层次为0，则对编号为6的节点X，它的双亲节点及右孩子节点的编号分别为（ ）。

A) 3，14 B) 2，15 C) 2，14 D) 3，15

34、在一棵高度为h(根结点层号为0)的完全二叉树中，所含结点个数不小于( )。

A) 2 B) 2 C) 2-1 D) 2

35、若在线性表中采用折半查找法查找元素，该线性表应该（ ）。 A) 元素按值有序 B) 采用顺序存储结构

C) 元素按值有序，且采用顺序存储结构 D) 元素按值有序，且采用链式存储结构 36、顺序存储设计时存储单元的地址（ ）。 A) 一定连续 B) 一定不连续 C) 不一定连续 D) 部分连续，部分不连续

37、若用冒泡法对关键字序列{20，17，11，8，6，2}从小到大进行排序，则需要交换的总次数为（ ）。

A) 3 B) 6 C) 12 D) 15

38、用二分法在有序表{1，5，10，13，33，42，46，63，76，78，88，96，120}中查找88时，需进行的比较次数为（ ）。 A) 2 B) 4 C) 3 D) 5

39、在有n个叶子结点的哈夫曼树中，其结点总数为（ ）。 A) 不确定 B) 2n C) 2n+1 D) 2n-1 40、具有n个顶点的无向图最多可包含（ ）条边。 A) n-1 B) n C) n(n-1)/2 D) n(n-1) 41、一个带权的无向连通图的最小生成树（ ）。

A) 有一棵或多棵 B) 只有一棵 C) 一定有多棵 D) 可能不存在 42、以下不是堆的是（ ）。

A) （100，98，88，82，80，77，66，60，40，28，18） B) （18，28，40，60，66，77，80，82，85，98，100） C) （100，88，98，77，80，60，82，40，28，18，66） D) （100，85，40，77，80，60，66，98，82，18，28）

43、设队列q=(a1,a2,… ,an)，则在q中删去一个元素后，q为（ ）。 A) q=(a2,a3, …,an) B) q=(a1,a2,…,an-1)

第 6 页 共 12 页

h-1h+1hh

C) q=(a1,a2,… ,ai-1,ai+1,ai+2 ,… ,an) D) 以上都有可能

44、对初始状态为递增序列的表按照递增顺序排序，最省时间的是（ ）算法。 A) 堆排序 B) 插入排序 C) 基数排序 D) 归并排序

45、已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（ ）。

A) O(1) B) O(m) C) O(n) D) O(m+n)

二、填空题（2分×30＝60分）

1、设a=3,b=4,c=5,表达式a+b>c && b= =c的值为： 。 2、有下列if语句 if（a>b） max = a; else max = b;

转换成条件表达式为： 。 3、下面程序的运行结果是： 。 #include main( )

{ int i,j,m,n; }

4、下面程序的功能是输出以下形式的金字塔图案： * *** ***** ******* main( ) { int i,j;

for(i=1; （1） ; i++)

{ for(j=1;j<= （2） ;j++) printf(“*”);

printf(“\\n”); }

第 7 页 共 12 页

i = 5; j = 6; m = ++i; n = j++;

printf(“%d,%d,%d,%d”,i,j,m,n);

}

5、下面程序是求出数组arr的两条对角线上元素之和，请填空。 #include \"stdio.h\" main（ ）

{ int arr［3］［3］={2,3,4,8,3,2,7,9,8},a=0,b=0,i,j; for（i=0;i<3;i++） for（j=0;j<3;j++）

if（ （1） ）a=a+arr［i］［j］; for（i=0;i<3;i++）

for（ j=2 ; （2） ; j- -） if（ （3） ） b=b+ arr［i］［j］; printf（\"%d,%d＼n\）; }

6、下面程序的功能是将一个字符串str的内容颠倒过来，请填空。 #include main（ ）

{ int i,j, （1） ;char str［］={\"1234567\for（i=0,j=strlen（str）-1;i7、以下程序的功能是从键盘输入若干学生的成绩，并输出最高成绩和最低成绩，当输入负数时结束,请填空。 main（ ）

{ float x,amax,amin; scanf（\"%f\（1） ）; amax=x; amin=x;

while （ （2） ） { if （x>amax）

amax=x; else

if( （3） ) amin=x;

第 8 页 共 12 页

scanf（\"%f\）;

}

printf （\"＼n amax=%f＼n amin=%f＼n\）; }

8、下面程序从终端读入20个字符放入字符数组中，然后利用指针变量输出上述字符串，请填空。 #include main（ ）

{ int i; char s［21］,*p; for（i=0；i<20；i++） s［i］=getchar（）; s［i］= （1） ; p =s;

while （*p）{ putchar （ （2） ）;p++; } }

9、在链表中进行插入和 操作的效率比在顺序存储结构中进行相同操作的效率高。

10、向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的 上。

11、n 个顶点的连通图至少有 条边。

12、在用于表示有向图的邻接矩阵中，对第i行的元素进行累加，可得到第i个顶点的 度，而对第j列的元素进行累加，可得到第j个顶点的 度。 13、给定序列{100， 86， 48， 73， 35， 39， 42， 57， 66， 21}，按堆结构的定义，则它一定 堆。

14、若二叉排序树某节点的左子树不空，则该节点左子树上的所有节点的关键字值均 该根节点的关键字值。 15、已知一无向图

G=（V，E），其中

V={a,b,c,d,e }

E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a 开始遍历图，得到的序列为abecd，则采用的是 遍历方法。

16、下列算法是将存储在数组中的n个抽象数据元素a0,a1,…,an-1逆置的算法,要求原数组中的数据元素值不能被改变,将算法补充完整。

void Reverse(int n,DataType a[ ],DataType b[ ]) { int i;

for(i=0;i第 9 页 共 12 页

}

17、若一棵二叉树有20个度为2的结点，10个度为1的结点，则它共有 个结点。

18、在有n个顶点的有向图中，每个顶点的度最大可达 。

19、下列算法是在顺序表中的第i个位置插入一个元素x,插入成功返回1,插入不成功返回0,将此算法补充完整。

int ListInsert(Seqlist *L,int i,DataType x) { int j;

if(L->size>=MaxSize || i<0||i>L->size) return 0; for(j=L->size;j>i;j--) （1） ; L->list[i]=x; （2） ; return 1; }

20、单链表的撤销函数如下,将函数补充完整。

void Destroy(SLNode * * head) { （1） *p,*q; p=*head; while( p ) { q=p; （2） ; free(q); }

*head=NULL; }

三、程序理解题（5分+10分+15分＝30分）

1（5分）、有以下程序 main( ) { int t=1;

for(i=5;i>=0;i--) t*=i; printf(“%d\\n”,t);

} 执行后输出结果是 。（5分） 2（10分）、如有以下函数

第 10 页 共 12 页

int func(char *str,char ch) { int count=0;char *pc; for(pc=str;*pc!=‘\\0’;pc++) if(*pc==ch)

count++; return count; } main( ) { char s[81],c;

printf(\"\\nPlease input a string:\"); gets(s);

printf(\"\\nPlease input a char:\"); c=getchar();

printf(\"\\nThe number of the char is: %d\\n\ }

问题（1）函数func的作用是什么？（5分） 问题（2）将主函数补充完整。（5分） 3（15分）、有以下函数 #include void sort(int a[ ],int n) { int i,j,k,t;

for( i = 0 ; i< n-1 ; i++ ) { k=i;

for( j=i+1 ; j < n ; j++ ) { if ( a[k]>a[j] ) k=j; }

if ( k!=i ) {

t=a[k];a[k]=a[i];a[i]=t; } } } main( )

{ int i,a[10]={3,5,7,6,4,9,8,1,2,10};

第 11 页 共 12 页

； for( i=0;i<=9;i++) printf(\"%d\}

问题（1）sort函数的功能是什么？（5分） 问题（2）将主函数补充完整。（5分）

问题（3）函数sort中，变量k的作用是什么？（5分）

四、计算分析题（每题10分，共20分）

1（10分）、线性表有两种存储结构：一是顺序表，二是链表。

问题（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？（5分）

问题（2）若线性表的总数基本稳定且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？（5分）

2（10分）、设一组12个数据元素的关键字序列为{45，40，36，53，57，22，85，14，70，12，13，78}，设哈希函数为H（key）=key % 13,哈希冲突函数采用伪随机探测再散列法，即冲突函数为：

d0=H(key) di=(di-1+R) % m (1<=i<=m-1)

其中，m为哈希表空间大小，R取伪随机数3，9，11，38，18，……，并设哈希表空间大小m=19。

问题（1）构造该数据元素序列的哈希表。

问题（2）计算该哈希表在等概率情况下查找成功的平均查找长度。

第 12 页 共 12 页