1、2010 年山东专升本（计算机科学与技术综合二）真题试卷及答案与解析单项选择题1 以下数据结构中哪一个是线性结构( )。（A）栈（B）线索二叉树 （C） AOV 网（D）二叉排序树2 若有 a，b， c 三个字符的字符序列执行入栈操作，则其所有可能的输出排列共有( )。（A）4 种（B） 5 种（C） 6 种（D）其他3 一棵树的广义表表示为 a(b，c(e，f(g)，d)，当用左孩子一右兄弟链表表示时，右指针域非空的节点个数为( )。（A）1（B） 2（C） 3（D）44 下面关于图的存储的叙述中正确的是( )。（A）用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关（B）用邻
2、接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关（C）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关（D）用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关5 对长度为 12 的有序表采用顺序存储结构，折半查找技术，在等概率情况下，查找成功的平均查找长度是( )。（A）13850（B） 6213（C） 18233（D）其他判断题6 算法的执行时间和所需的存储空间都是问题规模的函数，进行算法分析就是要找出这种函数关系。( )（A）正确（B）错误7 完全二叉树只能采用顺序存储方法，不能采用链表存储方法。( )（A）正确（B）错误8 在顺序循环
3、队列的第 i 个元素之后插入一个元素是顺序循环队列的基本运算。 ( )（A）正确（B）错误9 若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历的最后一个结点。( )（A）正确（B）错误10 直接插入排序的关键码比较次数与初始排列有关。( )（A）正确（B）错误算法设计题11 已知顺序栈 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)；)12 写出二叉树前序遍
4、历非递归算法的设计思想，然后写出算法。13 写出直接插入排序算法。应用题14 已知一棵三叉树的存储结构如下表所示，其中 root=0，n=7。画出该二叉树。15 用克鲁斯卡尔算法求下图的最小生成树。16 下图是一棵二叉排序树，规定当二叉排序树被删除的结点既有左子树，又有右子树时，以其中序前驱替代。画出删除 55 后的二叉排序树。17 已知散列表地址空间为 HT08，散列函数为 H(key)=key7，采用线性探测法处理冲突，将数据序列107，27，28，42，3，25，99，38 依次存入散列表中。试画出相应的散列表；并计算等概率下搜索成功的平均搜索长度。散列表及其查找各关键字要比较的次数如下
5、所示：搜索成功的平均搜索长度为：ASL=单项选择题18 在 C 语言中，合法的字符常量是( )（A）084（B） x43（C） ab（D）“0”19 在 C 语言中，要求运算数必须是整型的运算符是( )。（A）（B） +（C） !=（D）20 有整型变量 X，单精度变量 y=55，表达式： x=float(Y*3+(int)y4) 执行后，x 的值为( )。（A）17（B） 17.5（C） 18（D）1621 若从键盘上输入 5，则程序的输出结果是( )。#includevoid main( )int x；scanf(“d” ，&x) ；if(x 十+5)printf(“dn”，x)?；els
6、e printf(“dn” ，x 一一 )；（A）7（B） 6（C） 5（D）422 以下程序的输出结果是( )。#includevoid main( )int x=10，y=10，i；for(i=0；x8；y=+i)printf(“d d”，x 一一，y)；（A）10 1 9 2（B） 9 8 7 6（C） 10 9 9 0 （D）10 10 9 123 不能对二维数组 a 进行正确初始化的语句是 ( )。（A）int a23=0（B） int a23=1，2，3，4 ，5，6)；（C） int a3=1，2)， 0)（D）int a3=1，2，3，4，5，6)24 有程序段如下：运行该程序
7、的结果是( )。char a3，b=“China”；a=b：printf(“S”， a)；（A）编译出错（B）运行结果为 China（C）运行结果为 Ch（D）运行结果为 Chi25 以下对 C 语言函数的有关描述中，正确的是( )。（A）在 C 语言中，调用函数时，只能把实参的值传递给形参，形参的值不能传递给实参（B） C 语言函数既可以嵌套定义又可以递归调用（C）函数必须有返回值，否则不能使用函数（D）c 程序中有调用关系的所有函数必须放在同一个源程序文件中26 有如下程序段：int*P，a=10 ， b=1；p=&a；a=*p+b；执行该程序段后，a 的值为 ( )。（A）编译出错（B）
8、 10（C） 11（D）1227 若执行 fopen 函数时发生错误，则函数的返回值是( )。（A）地址值（B） 1（C） 0（D）EOF程序填空题28 下列程序用来计算一个英文句子中最长单词的长度(字母个数)max。假设该英文句子中只含有字母和空格，在空格之间连续的字母串称为单词，句子以“” 为结束。请填空。#includevoid main( )static char*P， a=“I am happy”；int max=0，m=0：P=a：while(”P!=)while(。p=A)I 1(“p=a)p+；)if(29 下列程序对输入的一个整数，调用函数 prime 判断其是否为素数。是素
9、数则输出 YES，否则输出 NO，请填空。#includestdiohint prime(int a)int e，1，yes；yes=1；e=a2；i=2：while(i，则输出结果是：_.#includevoid main( )int v1=0，v2=0；char ch；while(ch=getchar( )!=#)switch(ch)easea：caseh：default：v1+；ease0：v2+ ；printf(“d dn”，v1v2)；33 下列程序运行后，则输出结果是：_。#includevoid sub(int a，int b，int*c)*c=ba；)void main( )i
10、nt x，y，z；sub(10，5，&x)；sub(7，x，&y)?；sub(x，y，&z)?；printf(“d， d，dn”，x，y，z)?；34 下列程序运行后，则输出结果是：_。#includevoid main( )int a10=1，2，3，4，5，6，7，8，9，10；int k=0，i ；float s=0，ave：for(i=0；ivoid fun( )static int a；a+=2：printf(“d”，a)；void main( )int CC；for(cc=1；ccdata)；push(s，p)；p=p 一 lchild；if(!StackEmpty(s)通过下一次
11、循环中的内嵌 while 实现右子树遍历p=pop(s)；p=p 一 rchild；enditendw13 【正确答案】 直接插入排序的基本思想：依次将记录序列中的每一个记录插入到有序段中，使有序段的长度不断地扩大。其具体的排序过程可以描述如下：首先将待排序记录序列中的第一个记录作为一个有序段，将记录序列中的第二个记录插入到上述有序段中形成由两个记录组成的有序段，再将记录序列中的第三个记录插入到这个有序段中，形成由三个记录组成的有序段，依此类推，每一趟都是将一个记录插入到前面的有序段中，假设当前欲处理第 i 个记录，则应该将这个记录插入到由前 i 一 1 个记录组成的有序段中，从而形成一个由
12、i 个记录组成的按关键字值排列的有序序列，直到所有记录都插入到有序段中。一共需要经过 n 一 1 趟就可以将初始序列的 n 个记录重新排列成按关键字值大小排列的有序序列。算法为：void insertSort(DataType a，int n)for(i=2；i5 这个条件，x=5 所以该条件不成立，判断后x+，x 的值为 6，最后 printf(“dn” ，x 一一)；输出 6 后，x 一一，x 的值为5。22 【正确答案】 D【试题解析】 第一次：x=10，y=10，i=0 ；x8 条件成立，输出 x=10，y=10 后，x 一一，x 值为 9。第二次：x=9，y=+i=1，i=1； x8
13、 条件成立，输出 x=9，y=1后，x 一一，x 值为 823 【正确答案】 B【试题解析】 而维数组初始化也是在类型说明时给各下标变量赋以初值。二维数组可按行分段赋值，也可按行连续赋值。例如对数组 a53：按行分段赋值可写为：int a53=80，75，92) ，61 ，65，71)，59，63，70)，85，87，90)，76，77，85 ；按行连续赋值可写为：int a53=80，75，92，61，65，71，59，63，70，85，87，90，76，77，85；这两种赋初值的结果是完全相同的。对于二维数组初始化赋值还有以下说明：可以只对部分元素赋初值，未赋初值的元素自动取 0 值。例如
14、：int a33=(1，2) ，3 ；是对每一行的第一列元素赋值，未赋值的元素取 0 值。赋值后各元素的值为：1 0 02 0 03 0 0如对全部元素赋初值，则第一维的长度可以不给出。例如：int a33=1，2，3，4，5，6，7，8，9；可以写为：int a3=1，2，3，4，5，6，7，8，9)；24 【正确答案】 A【试题解析】 字符串不能直接赋值，而应使用字符串拷贝函数 strcpy。25 【正确答案】 A【试题解析】 函数不可以嵌套定义；函数可以有返回值也可以没有，默认的为int 型。26 【正确答案】 C【试题解析】 指针 P 指向整型数 a，所以*p 的值为 10。27 【正
15、确答案】 C【试题解析】 如果不能实现“打开”的任务，fopen 函数将会带回一个出错信息。此时 fopen 函数将带回一个空指针值 NULL(NULL 在 stdioh 文件中已被定义 0)。程序填空题28 【正确答案】 m+；mmax；m=0 ；【试题解析】 m 表示每一个单词的长度，max 表示当前最大单词的长度。29 【正确答案】 a 2=0；return(yes)；【试题解析】 只能被 1 和它本身整除的数是素数。为了判断 a 是不是素数，可以让 a 除以 2 到 a2 之间的每一个整数，如果 a 能被某个数整除，则说明 a 不是素数，否则 13 是素数。编程题30 【正确答案】 i
16、ncludemain( )int s10，t，i，j，X；print(“input 10 nHmbers：n”) ；for(t=0；tsEj+1)t=j；sj=sj+1；sj+1=t；printf(“the result is：n”)；for(j=10；j10；j+)printf【试题解析】 此题采用任何一种排序方法均可。31 【正确答案】 include“stdio h”#define N 20struet Stuchar noe10；char name20；float score3；studentsN；void main( )float s1=0，s2=0，s3=0；printf(“输入
17、96d 个学生的编号、姓名、三门课程成绩 n”，N)；for(int i=0：iN；i+)scanf(“S”，studentsino)；scanf(“S”，&stu【试题解析】 由于输入内容较多，所以采用结构体数组比较方便。程序分析题32 【正确答案】 55【试题解析】 由于没有 break 语句，所以执行 switch 语句，v1，v2 依次执行。33 【正确答案】 一 5，一 12，一 7【试题解析】 函数 sub(int a，int b，int*c)中 a，b 表示值运算，*c 表示指针运算。34 【正确答案】 ave=50【试题解析】 当 ai值为偶数时，退出本层循环，所以 S 求得是所有奇数的和，即 s=1+3+5+7+9，这 5 个数的平均值为 5。35 【正确答案】 2468【试题解析】 a 属于静态变量，能够保持上次运行的结果。
