2010年山东专升本(计算机科学与技术综合二)真题试卷

2010年山东专升本（计算机科学与技术综合二）真题试卷(总分：70.00，做题时间：90分钟)一、数据结构(总题数：21，分数：34.00)1.单项选择题__________________________________________________________________________________________解析：2.以下数据结构中哪一个是线性结构2.00）A.栈√()。（分数：B.线索二叉树C.AOV网D.二叉排序树解析：解析：线性表、堆栈、队列都可认为是线性结构。线索二叉树、二叉排序树是树状结构，于图状结构。AOV网属3.若有a，b，c三个字符的字符序列执行入栈操作，则其所有可能的输出排列共有()。（分数：2.00）A.4种B.5种√C.6种D.其他解析：解析：a，b，c三个字符的字符序列为abc，acb，bca,bac，cba，共5种可能。4.一棵树的广义表表示为a(b，c(e，f(g))，d)，当用左孩子一右兄弟链表表示时，右指针域非空的节点()。个数为（分数：2.00）A.1B.2C.3√D.4解析：解析：孩子兄弟表示法：用二叉链表作为树的存储结构，链表结点的两个指针域意义发生变化。原左子树指针域指向当前结点的第一个孩子结点，原右子树指针指向当前结点的第一个兄弟结点。从另一个角度出发，当前结点的左子树的右子树，实际上是当前结点的其他孩子结点。5.下面关于图的存储的叙述中正确的是()。（分数：2.00）A.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关B.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关C.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关D.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关解析：解析：邻接矩阵法是图的一种顺序存储结构。设√G有n个顶点，则可用n*n矩阵A(称为G的邻接矩阵，行标从1…n，列标从1…n)保存该有向图。邻接表法是图的链式存储方法，类似于树的孩子表示法。(设v)都建立一个单链表，单链表中的结点表示依附于当前顶点针对图中的每个顶点图来说则是以v的所有的边(对有向v邻接v为弧尾的弧)。每个结点(称为表结点)有三个域构成：邻接点域(adjvex)表示与顶点的点在图中的位置，链域指示下一条边或弧的结点，数据域存储和边或弧相联系的其他信息(如权值等)。6.对长度为12的有序表采用顺序存储结构，折半查找技术，在等概率情况下，查找成功的平均查找长度是()。（分数：2.00）A.13850√B.62／13

C.18233D.其他解析：解析：折半查找生成一棵二叉树，如图所示，所以平均查找长度为(1+2*2+3*4+A*5)／12=37／12.7.判断题__________________________________________________________________________________________解析：8.算法的执行时间和所需的存储空间都是问题规模的函数，进行算法分析就是要找出这种函数关系。()（分数：2.00）A.正确B.错误√解析：解析：算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。9.完全二叉树只能采用顺序存储方法，不能采用链表存储方法。（分数：2.00）()A.正确B.错误√解析：解析：二叉树既可以采用顺序存储方法，也可以采用二叉链表或三叉链表法进行存储。10.在顺序循环队列的第（分数：2.00）A.正确i个元素之后插入一个元素是顺序循环队列的基本运算。()B.错误√解析：解析：队列是一种特殊类型的线性表，按照先进先出的原则对其中的元素进行操作。排在队首的先出队，后面的元素依次前移。进入队列必须在队尾进行，删除必须在队首进行。11.若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历的最后一个结点。()（分数：2.00）A.正确B.错误√解析：12.直接插入排序的关键码比较次数与初始排列有关。()（分数：2.00）A.正确√B.错误解析：解析：直接插入排序基本操作为：将一个记录插入到一个已经排好序的有序表中，从而得到一个新的、长度增1的有序表。13.算法设计题__________________________________________________________________________________________解析：14.已知顺序栈S，简述f1函数功能，当输入80时，输出结果是多少?fl(){initstack(s)；scanf(“％d”，&n)；while(n){push(s，n％8)；n=n／8)}while(!Emptystcak(s)){pop(S，x)；printf(“％d”，x)；)}（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：把十进制整型数转化为8进制数。当输入80时，输出结果是：120。)解析：15.写出二叉树前序遍历非递归算法的设计思想，然后写出算法。（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：voidPreOrderUnrec(Bitree*t){Stacks：StackInit(s)；Bitree*p=t；{visite(p一＞data)；push(s，while(p!=NULL｜｜!StackEmpty(s)){while(p!=NULL)／／遍历左子树p)；p=p一＞lchild；}if(!StackEmpty(s))／／通过下一次循环中的内嵌while实现右子树遍历{p=pop(s)；p=p一＞rchild；}／／endit}／／endw)解析：16.写出直接插入排序算法。（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：直接插入排序的基本思想：依次将记录序列中的每一个记录插入到有序段中，使有序段的长度不断地扩大。其具体的排序过程可以描述如下：首先将待排序记录序列中的第一个记录作为一个有序段，将记录序列中的第二个记录插入到上述有序段中形成由两个记录组成的有序段，再将记录序列中的第三个记录插入到这个有序段中，形成由三个记录组成的有序段，……依此类推，每一趟都是将一个记录插入到前面的有序段中，假设当前欲处理第成的有序段中，从而形成一个由i个记录，则应该将这个记录插入到由前i一1个记录组i个记录组成的按关键字值排列的有序序列，直到所有记录都插入到有序段中。一共需要经过n一1趟就可以将初始序列的voidinsertSort(DataTypea，intn)for(i=2；i＜=n；i++)／／需要n一1趟{a[0]=a[i]；j=i一1；while(a[0]．key＜a[j]．key)／／搜索插入位置{a[j+1]=a[j]；j=jn个记录重新排列成按关键字值大小排列的有序序列。算法为：／／将a[i]赋予监视哨一1；a[j+1]=a[0]；／／将原a[i]中的记录放入第j+1个位置}})解析：17.应用题__________________________________________________________________________________________解析：18.已知一棵三叉树的存储结构如下表所示，其中root=0，n=7。画出该二叉树。（分数：2.00）__________________________________________________________________________________________正确答案：解析：(正确答案：)19.用克鲁斯卡尔算法求下图的最小生成树。（分数：2.00）__________________________________________________________________________________________正确答案：解析：(正确答案：)20.下图是一棵二叉排序树，规定当二叉排序树被删除的结点既有左子树，又有右子树时，以其中序前驱替代。画出删除55后的二叉排序树。（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：中序遍历序列为：10，20，30，35，40，55，60，80，85，99。删除55后，40成为根结点，画出的二叉排序树如下：解析：)21.已知散列表地址空间为HT[0．．8]，散列函数为H(key)=key％7，采用线性探测法处理冲突，将数据序列{107，27，28，42，3，25，99，38}依次存入散列表中。试画出相应的散列表；并计算等概率下搜索成功的平均搜索长度。ASL=散列表及其查找各关键字要比较的次数如下所示：搜索成功的平均搜索长度为：（分数：2.00）__________________________________________________________________________________________正确答案：解析：(正确答案：搜索成功的平均搜索长度为：ASL=10／8=1．25)二、C语言(总题数：22，分数：36.00)22.单项选择题__________________________________________________________________________________________解析：23.在C语言中，合法的字符常量是（分数：2.00）A.‘＼084’()B.‘＼x43’C.‘ab’√D.“＼0”解析：解析：字符常量是用单引号括起来的一个字符。例如‘a’，‘b’，‘A’，‘+’‘?’嘟是合法字符常量。在C语言中，字符常量有以下特点：a)字符常量只能用单引号括起来，c)字符可以是字符集中任意字符。但数字被定义为字符型之5是不同的量。‘5’是字符常量，()。不能用双引号或其他括号；b)字符常量只能是单个字符，不能是字符串；后就不再是原来的数值了。如‘5’和5是整型常量。24.在C语言中，要求运算数必须是整型的运算符是（分数：2.00）A.／B.++C.!=D.％√解析：解析：使用求余运算符(模运算符)“％”时，要求参与运算的变量必须均为整型，其结果值为两数相除所得的余数。一般情况下，所得的余数与被除数符号相同。25.有整型变量（分数：2.00）A.17X，单精度变量y=5．5，表达式：x=float(Y*3+((int)y％4))执行后，x的值为()。B.17.5√C.18D.16解析：解析：(int)y把y的值强制转化为整型，然后进行％运算。5，则程序的输出结果是26.若从键盘上输入()。#includevoidmain(){intx；scanf(“％d”，&x)；if(x十+>5)printf(“％d＼n”，x)?；elseprintf(“％d＼n”，x一一)；}（分数：2.00）A.7B.6√C.5D.4解析：解析：首先判断x++>5这个条件，x=5所以该条件不成立，d＼n”，x一一)；输出6后，x一一，x的值为5。判断后x++，x的值为6，最后printf(“％27.以下程序的输出结果是d％d”，x一一，y)；}（分数：2.00）A.10192()。#includevoidmain(){intx=10，y=10，i；for(i=0；x>8；y=++i)printf(“％B.9876C.10990D.101091√解析：解析：第一次：x=10，y=10，i=0；x>8条件成立，输出x=10，y=10后，x一一，x值为9。第二次：x=9，y=++i=1，i=1；x>8条件成立，输出x=9，y=1后，x一一，x值为8()。28.不能对二维数组a进行正确初始化的语句是（分数：2.00）A.inta[2][3]={0}B.inta[2][3]={{1，2}，{3，4}，{5，6})；√C.inta[][3]={{1，2)，{0))D.inta[][3]={1，2，3，4，5，6)解析：解析：而维数组初始化也是在类型说明时给各下标变量赋以初值。二维数组可按行分段赋值，也可inta[5][3]={{80，75，92)，{61，65，inta[5][3]={80，75，92，按行连续赋值。例如对数组a[5][3]：按行分段赋值可写为：71)，{59，63，70)，{85，87，90)，{76，77，85}}；按行连续赋值可写为：61，65，71，59，63，70，85，87，90，76，77，85}；这两种赋初值的结果是完全相同的。对于二维数组初始化赋值还有以下说明：可以只对部分元素赋初值，未赋初值的元素自动取0值。例如：inta[3][3]=((1}，{2)，{3}}；是对每一行的第一列元素赋值，未赋值的元素取100200300如对全部元素赋初值，则第一维的长度可以不给出。0值。赋值后各元素的值为：例如：inta[3][3]={1，2，3，4，5，6，7，8，9}；可以写为：29.有程序段如下：运行该程序的结果是（分数：2.00）inta[][3]={1，2，3，4，5，6，7，8，9)；()。chara[3]，b[]=“China”；a=b：printf(“％S”，a)；A.编译出错√B.运行结果为C.运行结果为D.运行结果为ChinaChChi解析：解析：字符串不能直接赋值，而应使用字符串拷贝函数30.以下对C语言函数的有关描述中，正确的是（分数：2.00）strcpy。()。A.在C语言中，调用函数时，只能把实参的值传递给形参，形参的值不能传递给实参B.C语言函数既可以嵌套定义又可以递归调用√C.函数必须有返回值，否则不能使用函数D.c程序中有调用关系的所有函数必须放在同一个源程序文件中解析：解析：函数不可以嵌套定义；函数可以有返回值也可以没有，默认的为int型。31.有如下程序段：（分数：2.00）A.编译出错int*P，a=10，b=1；p=&a；a=*p+b；执行该程序段后，a的值为()。B.10C.11√D.12解析：解析：指针P指向整型数a，所以*p的值为10。32.若执行fopen函数时发生错误，则函数的返回值是()。（分数：2.00）A.地址值B.1C.0√D.EOF解析：解析：如果不能实现“打开”的任务，fopen函数将会带回一个出错信息。此时fopen函数将带回一个空指针值NULL(NULL在stdio．h文件中已被定义0)。33.程序填空题__________________________________________________________________________________________解析：

34.下列程序用来计算一个英文句子中最长单词的长度(字母个数)max。假设该英文句子中只含有字母和空格，在空格之间连续的字母串称为单词，句子以“．”为结束。请填空。char*P，a[]={“Iamhappy．”}；#includevoidmain(){staticintmax=0，m=0：P=a：while(”P!=‘．’){while(((。p<='Z')&&(*p>=‘A’))I1((“p<=‘z’)&&(。p>=‘a’))){p++；（分数：2.00）)if(__________________________________________________________________________________________正确答案：(正确答案：①m++；②m＞m表示每一个单词的长度，max；③m=0；)解析：解析：max表示当前最大单词的长度。prime判断其是否为素数。是素数则输出35.下列程序对输入的一个整数，调用函数YES，否则输出NO，请填空。#include＜stdio．h＞intprime(inta){inte，1，yes；yes=1；e=a／2；i=2：while((i＜=e)&&yes!=0)if()yes=0；elsei++：}voidmain(){intX；printf(“＼ninputaintegerX：”)；scanf(“％d”，&x)；if(prime(x))（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：④a％2==0；⑤return(yes)；)解析：解析：只能被每一个整数，如果36.编程题1和它本身整除的数是素数。为了判断a是不是素数，可以让13是素数。a除以2到a／2之间的a能被某个数整除，则说明a不是素数，否则__________________________________________________________________________________________解析：37.实现：从键盘输入任意（分数：2.00）10个整数，按从小到大的顺序排列成有序数并输出。__________________________________________________________________________________________正确答案：(正确答案：includemain(){ints[10]，t，i，j，X；print{(“input10nHmbers：＼n”)；for(t=0；tsEj+1]){t—=[j]；s[j]=s[j+1]；s[j+1]=t；}printf(“theresultis：＼n”)；for(j=10；j解析：解析：此题采用任何一种排序方法均可。38.实现：20个学生，输入姓名，学号，三科成绩，计算每科的平均分。（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：include“stdio．h”floatscore[3]；}students[N]；voidmain(){floats1=0，s2=0，s3=0；printf(“输入9／6d个学生的编号、姓名、三门课程成绩n”，N)；for(inti=0：i＜N；i++){scanf(“％S”，＆students[i]．no)；#defineN20struetStu{charnoe[10]；charname[20]；scanf(“％S”，&stu)解析：解析：由于输入内容较多，所以采用结构体数组比较方便。39.程序分析题__________________________________________________________________________________________解析：40.下列程序运行后，如果从键盘上输入china#，则输出结果是：_______________________.#includevoidmain(){intv1=0，v2=0；charch；while((ch=getchar()!=‘#’))switch(ch){ease‘a’：case‘h’：default：v1++；ease‘0’：v2++；}printf(“％d％d＼n”，v1．v2)；}（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：55)解析：解析：由于没有break语句，所以执行switch语句，v1，v2依次执行。41.下列程序运行后，则输出结果是：________。#includevoidsub(inta，intb，int*