1、报名号_ 姓名_ 科目_ 线封密姓黄冈师范学院2008年“专升本”考试试题科目：计算机科学与技术专业综合（总分200分） 注意：答案一律书写在答题纸上，在试卷上答题一律无效。一、选择题（2分4590分）1、一个C语言程序是由（ ）。 A) 一个主程序和若干子程序组成 B) 函数组成C) 若干过程组成 D) 若干子程序组成2、C语言中的标识符只能由字母、数字和下划线三种字符组成，且第一个字符（ ）。A) 必须为字母 B) 必须为下划线C) 必须为字母或下划线 D) 可以是字母、数字和下划线中任一字符3、以下不正确的叙述是（ ）。A) 在C程序中，逗号运算符的优先级最低B) 在C程序中，APH和a
2、ph是两个不同的变量C) 若a和b类型相同，在计算了赋值表达式a=b后b中的值将放入a中，而b中的值不变D) 从键盘输入数据时，对于整型变量只能输入整型数值，对于实型变量只能输入实型数值4、以下变量赋初值不正确的是（ ）。A) int a = 3B) int a,b=2,c=3C) int a=1,b=2,c=3D) int a=b=c=35、设变量f,a,b,c都为int型，其中a=3,b=2,c=1,有表达式f=abc,则变量f的值为（ ）。A) 3 B) 2 C) 1 D) 06、有以下程序main( ) char k; int i;for(i=1;i3;i+) scanf(“%c”,&
3、k);switch(k) case 0: printf(“anothern”); case 1: printf(“numbern”); 程序运行时，从键盘输入：01，程序执行后的输出结果是（ ）。A) another B) another C) another D) number number number number number another number7、已知x,y,z均为整型变量，且值均为1，则执行语句+x|+y&+z;后，表达式x+y的值为（ ）。A）1 B）2 C）3 D）48、有以下程序main( ) int i,s=0;for(i=1;i10;i+=2) s+=i+1;p
4、rintf(“%dn”,s); 程序执行后的输出结果是（ ）。A) 自然数19的累加和 B) 自然数110的累加和C) 自然数19中的奇数之和 D) 自然数110中的偶数之和9、在C语言中，引用数组元素时，其数组下标的数据类型允许是（ ）。A) 整型常量 B) 整型表达式C) 整型常量或整型表达式 D) 任何类型的表达式10、以下数组元素的初始化不正确的是（ ）。A) int a5= 0 B) int a5= 1,2,3 C) int a = 1,2,3,4,5 D) int a5;a=1,2,3,4,511、已知：char a20,b20=Student;则在程序中能将字符串Student赋
5、给数组a的正确语句是（ ）。A）a=Student; B）strcpy（b,a）; C）a=b; D）strcpy（a,b）;12、有以下程序#include main（） int y=9; for（ ; y0;y-） if（y%3=0） printf（%d,y）; 程序的运行结果是 （ ）。A）321 B）963 C）987654 D）98765432113、有以下程序main( ) int num44=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,i,j; for(i=0;i4;i+) for(j=_;j4;j+)printf(%4d,numij); pri
6、ntf(n); 若要按以下形式输出数组元素 1 2 3 4 6 7 8 11 12 16 则在程序下划线处应填入的是 （ ）。A) i-1 B) i C) i+1 D) 4-i14、阅读下面程序，输出结果是（ ）。#include stdio.hvoid 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,%dn,a,b）;A）6,5 B）5,6 C）20,25 D）3,515、有以下程序int f(int b4) int i,j,s=0;for(j=0;j2) i=3-
7、j;s+=bij;return s;main( ) int a44=1,2,3,4,0,2,4,5,3,6,9,12,3,2,1,0;printf(“%dn”,f(a); 执行后的输出结果是（ ）。A) 12 B) 11 C) 18 D) 1616、有以下程序void f(char *p) p + = 3 ; main( ) char b4=a,b,c,d,*p=b; f(p);printf(%cn,*p); 程序运行后的输出结果是 （ ）。A) a B) b C) c D) d17、有定义：int n=0,*p=&n,*q=&p;则以下选项中，正确的赋值语句是（ ）。A) p=1; B) *
8、q=2; C) q=p; D) *p=5;18、有以下程序段int a10=1,2,3,4,5,6,7,8,9,10,*p=&a3,b;b=p5;b中的值是（ ）。A) 5 B) 6 C) 9 D) 819、以下语句或语句组中,能正确进行字符串赋值的是（ ）。A) char *sp;*sp=right!; B) char s10;s=right!; C) char s10;*s=right!; D) char *sp=right!;20、有以下结构体说明和变量定义： struct node int data;struct node *next;*p,*q,*r; 假设指针p、q、r分别指向此链
9、表中的三个连续结点，现要将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) 插入与删除时不必移动元
10、素 D) 所需空间与线性表长度成正比24、长度为N的线性表，进行顺序查找，在查找不成功时，与关键字的比较次数为 ( )。A) N B) 1 C) N-1 D) 0 25、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）。（0=inext=NULLC) head-next=head D) head!=NULL27、串的长度是指（ ）。A) 串中所含不同字母的个数 B) 串中所含字符的个数C) 串中所含不同字符的个数 D) 串中所含非空格字符的个数28、（ ）是C语言中“abcd321ABCD”的子串。A) abcd B) 321AB C) “abcABC
11、” D) “21AB”29、队列操作的原则是（ ）。A) 先进先出 B) 后进先出 C) 只能进行插入 D) 只能进行删除30、向顺序栈中压入新元素时，应当（ ）。A) 先移动栈顶指针，再存入元素 B) 先存入元素，再移动栈顶指针C) 先后次序无关紧要 D) 同时进行31、设栈的输入序列是（1、2、3、4），则（ ）是不可能的输出序列。A) 1243 B) 2134 C) 1432 D) 431232、下列有关二叉树的说法正确的是（ ）。A) 二叉树的度为2 B) 一棵二叉树的度可以小于2 C) 二叉树中至少有一个结点的度为2 D) 二叉树中任何一个结点的度为233、一棵有16个节点的完全二叉
12、树，对它按层编号，根节点的层次为0，则对编号为6的节点X，它的双亲节点及右孩子节点的编号分别为（ ）。A) 3，14 B) 2，15 C) 2，14 D) 3，1534、在一棵高度为h(根结点层号为0)的完全二叉树中，所含结点个数不小于( )。A) 2h-1 B) 2h+1 C) 2h-1 D) 2h35、若在线性表中采用折半查找法查找元素，该线性表应该（ ）。A) 元素按值有序 B) 采用顺序存储结构C) 元素按值有序，且采用顺序存储结构 D) 元素按值有序，且采用链式存储结构36、顺序存储设计时存储单元的地址（ ）。A) 一定连续 B) 一定不连续 C) 不一定连续 D) 部分连续，部分不
13、连续37、若用冒泡法对关键字序列20，17，11，8，6，2从小到大进行排序，则需要交换的总次数为（ ）。A) 3 B) 6 C) 12 D) 1538、用二分法在有序表1，5，10，13，33，42，46，63，76，78，88，96，120中查找88时，需进行的比较次数为（ ）。A) 2 B) 4 C) 3 D) 539、在有n个叶子结点的哈夫曼树中，其结点总数为（ ）。A) 不确定 B) 2n C) 2n+1 D) 2n-140、具有n个顶点的无向图最多可包含（ ）条边。A) n-1 B) n C) n(n-1)/2 D) n(n-1)41、一个带权的无向连通图的最小生成树（ ）。A)
14、有一棵或多棵 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) C) q=(a1,a2, ,ai-1,ai+1,ai
15、+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分3060分）1、设a=3,b=4,c=5,表达式a+bc & b= =c的值为： 。2、有下列if语句if（ab） max = a;else max = b;转换成条件表达式为： 。 3、下面程序的运行结果是： 。#include main( )int i
16、,j,m,n;i = 5;j = 6;m = +i;n = j+;printf(“%d,%d,%d,%d”,i,j,m,n);4、下面程序的功能是输出以下形式的金字塔图案：*main( ) int i,j;for(i=1; （1） ; i+) for(j=1;j= （2） ;j+) printf(“*”);printf(“n”);5、下面程序是求出数组arr的两条对角线上元素之和，请填空。#include stdio.hmain（ ） int arr33=2,3,4,8,3,2,7,9,8,a=0,b=0,i,j;for（i=0;i3;i+）for（j=0;j3;j+）if（ （1） ）a=a
17、+arrij;for（i=0;i3;i+）for（ j=2 ; （2） ; j- -）if（ （3） ）b=b+ arrij;printf（%d,%dn,a,b）;6、下面程序的功能是将一个字符串str的内容颠倒过来，请填空。#includemain（ ） int i,j, （1） ;char str=1234567;for（i=0,j=strlen（str）-1;iamax）amax=x;elseif( （3） )amin=x; scanf（%f,&x）;printf （n amax=%fn amin=%fn,amax,amin）;8、下面程序从终端读入20个字符放入字符数组中，然后利用指针
18、变量输出上述字符串，请填空。#include main（ ） int i; char s21,*p;for（i=0；i20；i+）si=getchar（）;si= （1） ;p =s;while （*p） putchar （ （2） ）;p+; 9、在链表中进行插入和 操作的效率比在顺序存储结构中进行相同操作的效率高。10、向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的 上。11、n 个顶点的连通图至少有 条边。12、在用于表示有向图的邻接矩阵中，对第i行的元素进行累加，可得到第i个顶点的 度，而对第j列的元素进行累加，可得到第j个顶点的 度。13、给定序列
19、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,DataT
20、ype a ,DataType b ) int i; for(i=0;isize=MaxSize | iL-size) return 0; for(j=L-size;ji;j-) （1）; L-listi=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;
21、printf(“%dn”,t); 执行后输出结果是 。（5分）2（10分）、如有以下函数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 s81,c;printf(nPlease input a string:);gets(s); printf(nPlease input a char:);c=getchar(); printf(nThe number of the char is: %dn, ); 问题（1）函数f
22、unc的作用是什么？（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 aj ) k=j; if ( k!=i ) t=ak;ak=ai;ai=t; main( ) int i,a10=3,5,7,6,4,9,8,1,2,10; ； for( i=0;i=9;i+) printf(%d,ai);问题（1）sort函数的功能是什么？（5分）问题（2）将主函数补充完整。（5分）问题（3）函数sort中
23、，变量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）计算该哈希表在等概率情况下查找成功的平均查找长度。第 11 页 共 11 页
