黄冈师范学院2010年“专升本”考试试题科目：计算机科学与技术专业《专业综合》注意：答案一律书写在答题纸上，在试卷上答题一律无效第一部分c语言一、选择题（2分x20 = 40分）下列关于c语言程序说法正确的是（）是由一个主程序和若干子程序组成是由函数组成是由若干过程组成是由若干子程序组成关于C语言程序执行过程，下列说法正确的是（）从main函数开始，到main函数结束本程序文件的第一个函数开始，到本程序文件的最后一个函数结束本程序文件的第一个函数开始，到main函数结束从main函数开始，到本程序文件的最后一个函数结束C语言中的标识符只能由字母、数字和下划线三种字符组成，且第一个字符（） 必须为字母必须为下划线必须为字母或下划线可以是字母、数字和下划线中任一字符用C语言编写的代码程序（可立即执行经过编译即可执行以下定义语句中正确的是（char a二\，A\，b二\，B\，;int a=10,*b=&a;以下变量赋初值不正确的是int1、A)B)C)D)2、A)B)C)D)3、A)B)C)D)4、A)C)5、A)C)6、A)B)C)D)7、）intinta = 3; a,b=2,c=3; a=l,b=2,c=3; a=b=c=3;A)B)B）经过编译解释才能执行 以上说法都不对B) float a=b=10.0;D) float *a,b=&a;int已知int x=1,y=2,z=3;以下语句执行后，x,y,z的值是()。
if(x〉y) ; z = x; x = y; y = z;1,2,32,1,1C) 2,3,1D) 2,3,28、有以下程序 void main( ) { int m=3,n=4,x;x=-m;x=x+8/n; printf("%d\n",x);}程序运行后的输出结果是( )A) 3 B) 5 C) -1 D) -29、以下不正确的叙述是( )A) 在C程序中，main函数不一定要写在程序的最上面B) 在C程序中，SUM和sum是两个不同的变量C) 若a和b类型相同，在计算了赋值表达式a=b后，b中的值将放入a中，而b中的值不变D) 从键盘输入数据时，对于整型变量只能输入整型数值，对于实型变量只能输入实型数值10、 若有说明int *p,a[5];p=a；则以下表达式中不能表示a[3]的是()A) p[3] B) *(a+3) C) *(p+3 ) D) *(p+6)11、 以下能正确定义二维数组的是( )A) int a[][3]; B) int a[][3]=2{2*3};C) int a[][3]={}; D) int a[2][3]={{1},{2},{3,4}};12、 s1和s2已正确定义并分别指向两个字符串。
若要求：当s1所指串大于s2所指串时，执行语 以下选项中引用结构体变量成员的表达式错误的是（ ）句S;则以下选项中正确的是()A) if(s1>s2) S;C) if(strcmp(s2,s1)>0) S;B) if(strcmp(s1,s2)) S;D) if(strcmp(s1,s2)>0) S;13、 有以下程序void main( ){ int i,s=0;for(i=1;i<10;i+=2)s + = i+1; printf(“%d\n”,s);}程序执行后的输出结果是( )A) 自然数1〜10的累加和C) 自然数1〜10中的偶数之和14、 有以下说明和定义语句B)自然数1〜9的累加和D)自然数1〜9中的奇数之和struct student { int age; char num[8]; };struct student stu[3]={{20,"200701"},{21,"200702"},{19,"200703"}};struct student *p = stu;A) (p++)->numC) (*p).numB) p->numD) stu[3].age15、有以下程序 void f(char *p) { p + = 3 ; } void main( ){ char b[4]={'a','b','c','d'},*p = b; f(p);printf("%c\n",*p);} 程序运行后的输出结果是( )。
A) a B) b C) c D) d16、执行下面程序段后，输出是( ) int j=1,s=0;while (j<=10){ j++;if(j%2)continue;s=s+j;} printf(“%d”,s);A) 22 B) 25 C) 30 D) 5517、有以下程序#define N 20fun(int a[ ],int n,int m){ int i,j;for(i=m;i>=n;i--) a[i+1]=a[i];} void main( ){ int i,a[N]={1,2,3,4,5,6,7,8,9,10}; fun(a,2,9);for(i=0;i<5;i++)printf("%d",a[i]);} 程序运行后的输出结果是( )A) 10234 B) 12344 C) 12334 D) 1223418、有以下程序void main( ){ int a=1,b;for(b=1;b<=10;b++){ if(a>=8)break;if(a%2 ==1 ) { a+=5 ; continue; }a-= 3;}printf("%d\n",b);} 程序运行后的输出结果是( )。
A) 3 B) 4 C)5 D) 619、有以下程序段int a[10] = {l,2,3,4,5,6,7，&9,10},*p=&a[3],b;b=p[5];b 中的值是()A) 5 B) 6 C) 9 D) 120、C语言规定，简单变量做实参时，它和形参之间的数据传递方式是()A) 地址传递B) 单项值传递C) 由实参传给形参，再由形参传给实参D) 由用户指定传递方式二、填空题(1-6 题每空 2 分，7-8 题每题 5 分，共 30 分)1、 C语言源程序的基本单位 2、 在内存中每个存储单元的编号称为 3、 根据对变量的访问方式，可分为直接访问和 访问4、 下面程序的功能是输出以下形式的金字塔图案：****void main(){ int i,j;for(i=l: (1) : i++){ for(j=1;j<= (2) :j++) printf(“*”)：printf(“\n”):}}5、 以下程序的功能是从键盘输入若干学生的成绩，并输出最高成绩和最低成绩，当输入负数时结束, 请填空void main( ){ float x,amax,amin:scanf ("%f", (1) ):amax=x:amin=x:while ( (2) ){ if(x>amax)amax=x:elseif( (3))amin=x;scanf("%f",&x);}printf ("\n amax=%f\n amin=%f\n",amax,amin);}6、下列程序的功能是判断一个正整数是否为素数。
void main( ){int n ,i,f;scanf(“%d”,&n);f = 1;for(i=2 ; i<=sqrt(n) ; (1) )if(n%i==0){(2): break;}}7、下列程序的运行结果是 void main( ){int i ,s = 1;for(i=0;i<=5;i++)s = s *i;printf(“%d”, s);}&当运行以下程序时，输入abed，程序的输出结果是 void insert(char str[ ]){ int i；i = strlen(str)；while(i>0){ str[2*i]=str[i]； str[2*iT] = ‘ *'； i—； }printf("％s\n",str)；}void main(){ char str[40]；scanf("％s"，str)；insert(str)； }三、程序理解题(每题 10 分，共 30 分)1、已知函数f的功能是求1-n的和int f( int n ){int i,sum;for(i=1;i<=n;i++)return sum;}问题(1)将函数f补充完整；(5分) 问题(2)写出主函数，求1-100的和。
5分)2、编程求下列分段函数的值(x,y均为整型变量)/ - 2xT0 x〉0y = y x+5 x=02x+10 x<03、编程对10个正整数排序(可采用起泡法或选择法任意一种完成)第二部分 数据结构一、选择题(2分x25 = 50分)1、数据的最小单位是( )A)数据项 B)数据类型 C)数据元素 D)数据变量2、 字符串的长度是指( )A) 串中不同字符的个数 B) 串中不同字母的个数C) 串中所含字符的个数 D) 串中不同数字的个数3、 以下数据结构中( )是非线性结构？A)队列 B)栈 C)线性表 D)二叉树4、 建立一个长度为n的有序单链表的时间复杂度为()A) O(n) B) O(1) C) O(n2) D) O(logn)A) 两个字符串的长度相等C)同时具备(A)和(B)两个条件6、算法的时间复杂度是指( )A) 执行算法程序所需要的时间5、两个字符串相等的充要条件是( )B) 两个字符串中对应位置上的字符相等D) 以上答案都不对B) 算法程序的长度C) 算法执行过程中所需要的基本运算次数 D) 算法程序中的指令条数7、队列是一种( )的线性表A)先进先出 B)先进后出 C)只能插入 D)只能删除8、长度为N的线性表进行顺序查找，在查找不成功时，与关键字的比较次数为()。
A) N B) 1 C) N-1 D) 0 9、若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则 查找A[3]的比较序列的下标依次为()A) 1，2，3B) 9, 5, 2, 3C) 9，4，3 D) 9，4，2，310、 设某有向图中有n个顶点，则该有向图对应的邻接表中有()个表头结点A) n-1 (B) n (C) n+1 (D) 2n-111、 线性链表不具有的特点是( )A)随机访问 B)不必事先估计所需存储空间大小C) 插入与删除时不必移动元素 D)所需空间与线性表长度成正比12、 设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图A) 5 B) 6 C) 7 D) 813、 设某棵二叉树的中序遍历序列为ABCD，先序遍历序列为CABD,则后序遍历该二叉树得到序列为 ( )A) BADC B) BCDA C) CDAB D) CBDA14、 在有n个叶子结点的正则二叉树(无度为1的结点)中，其结点总数为()A) 2n B) 2n-1 C) 2n+1 D) 2n-115、 设一组初始记录关键字序列为(50, 40，95，20，15，70，60，45)，则以增量d=4的一趟希尔 排序结束后前4条记录关键字为( )。
A) 40，50，20，95 B) 15，40，60，20C) 15，20，40，45 D) 45，40，15，2016、 函数 substr(“DATASTRUCTURE”，5, 9)的返回值为()A) “STRUCTURE” B) “DATA”C) “ASTRUCTUR” D) “DATASTRUCTURE”17、 设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该 操作的时间复杂度为( )A) O(logn) B) O(1) C) 0(e) D) O(n)18、 以下不是堆的是( )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)19、 顺序存储设计时存储单元的地址( )A) 一定连续 B) 一定不连续C) 不一定连续 D) 部分连续，部分不连续20、 设一组权值集合W=(15, 3, 14, 2, 6, 9, 16, 17),要求根据这些权值集合构造一棵哈夫曼树, 则这棵哈夫曼树的带权路径长度为( )。
A) 129 B) 219 C) 189 D) 22921、 设一组初始记录关键字序列为(Q, H, C, Y, P, A, M, S, R, D, F, X),则按字母升序的第一 趟冒泡排序结束后的结果是( )A)F,H,C,D,P,A,M,Q,R,S,Y,XB)P,A,C,S,Q,D,F,X,R,H,M,YC)A,D,C,R,F,Q,M,S,Y,P,H,XD)H,C,Q,P,A,M,S,R,D,F,X,Y22、 设有一组初始记录关键字序列为(34,76,45,18,26,54,92),则由这组记录关键字生成的 二叉排序树的深度为( )A) 4 B) 5 C) 6 D) 723、 具有n个顶点的无向图最多可包含()条边A) n-1 B) n C) n(n-1)/2 D) n(n-1)24、 设无向图 G 中的边的集合 E={(a, b), (a, e), (a, c), (b, e), (e, d), (d, f), (f, c)}, 则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为()A) aedfcb B) acfebd C) aebcfd D) aedfbc25、 对初始状态为递增序列的表按照递增顺序排序,最省时间的是( )算法。
A) 堆排序 B) 插入排序 C) 基数排序 D) 归并排序二、填空题(2分x15 = 30分)1、 从题后给出的选项中选择一个合适的项填空1) 在计算机内实现递归算法时所需要的辅助数据结构 ；银行排队系统实现时需要的辅助数据结构是 可选项：栈、队列)2) 用二叉链表表示具有n个节点的二叉树时，值为空的指针域的个数 可选项：2n、 n+1 )3) —个程序能确切地满足具体问题的需求，表明此程序满足 要求；若能很好地处理异常，表明此程序满足 要求可选项：正确性、可读性、健壮性)4) 向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的 上可选项：左子树、右子树)5) 在用于表示有向图的邻接矩阵中，对第i行的元素进行累加，可得到第i个顶点的 度；而对第j列的元素进行累加，可得到第j个顶点的 度可选项：出、入)2、 算法填空1) 下列算法是在顺序表中的第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;}2) 下面程序段的功能是实现二分查找算法,将此算法补充完整。
struct record{int key;int others;};int bisearch(struct record r[ ], int k){int low=0,mid,high=n-1;while(low<=high){(1);if(r[mid].key==k) return(mid+1);else if( (2) ) high二midT;else (3) ;}return(0);}3) 下面程序段的功能是实现数据x进栈，要求在下划线处填上正确的语句typedef struct { int s[100] ; int top; } sqstack;void push(sqstack *s,int x){if (s->top==m-1) printf(“overflow”);else{ (1);(2) ;}}三、计算分析算法题（每题 10 分，共 20 分）1、写出下列二叉树的先序、中序、后续遍历序列（10 分）2、设一组12 个数据元素的关键字序列为｛30，42，36，9，33，22，85，12，49，39｝，设哈希函数为 H（key）=key % 15,哈希冲突函数采用线性探测法，即冲突函数为：d0 = H（key） di = （di-1 + 1） % m （i=1,2,3, ）其中，m为哈希表空间大小，并设哈希表空间大小m =15。
问题（1）构造数据元素序列的哈希表，把关键字序列填到下表合适的位置（8分）01234567891011121314问题（2）计算该哈希表在等概率情况下查找成功的平均查找长度ASL （2分）。