1、山东专升本计算机科学与技术（综合二）模拟试卷 7 及答案与解析单项选择题1 假设以行序为主序存储二维数组 A=array1100，1100，设每个数据元素占 2 个存储单元，基地址为 10，则 LOC5，5=( )。（A）808（B） 818（C） 1010（D）10202 设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储， a1，1为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a8，5的地址为( )。（A）13（B） 33（C） 18（D）403 一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是( )。（A）250（B） 500（C） 501（D）50
2、54 中缀表达式 DC-A+B*ED*F 的前缀表达式为( )。（A）一+ D-CA*BE*DF（B） DCA-BE*+DF*一（C）一 -CA+D*BE*DF（D）一+ D-C*ABE*DF5 一个具有 1025 个结点的二又树的高 h 为( )。（A）11（B） 10（C） 11 至 1025 之间（D）10 至 1024 之间6 设一棵 m 叉树中有 N1 个度数为 1 的结点，N 2 个度数为 2 的结点，N M 个度数为 m 的结点，则该树中共有( )个叶子结点。（A）（B）（C）（D）7 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( ).（A）O(n)（B）
3、 O(n+e)（C） O(n2)（D）O(n3)8 对于长度为 18 的顺序存储的有序表，若采用折半查找，则查找第 15 个元素的比较次数为( )。（A）3（B） 4（C） 5（D）69 对一组数据(84，47，25，15，21)排序，数据的排列次序在排序的过程中的变化为(1)84 47 25 15 21 (2)15 47 25 84 21(3)15 21 25 84 47 (4)15 21 25 47 84 则采用的排序是( )。（A）选择（B）冒泡（C）快速（D）插入10 若用冒泡排序对关键字序列18，16，14，12，10，8)，进行从小到大的排序，所需进行的关键字比较总次数是( )。（
4、A）10（B） 15（C） 21（D）34填空题11 一个算法的效率可分为_效率和_效率。12 在一棵二叉树中，度为 0 的结点个数为 n0，度为 2 的结点个数为 n2，则n0_。13 一个图的边集为(a，c)，(a ，e)，(b，e) ，(c，d)，(d，e)，从顶点 a 出发进行深度优先搜索遍历得到的顶点序列为_，从顶点 a 出发进行广度优先搜索遍历得到的顶点序列为_。14 假定对线性表(38，25，74，52，48)进行哈希存储，采用 H(K)=K7 作为哈希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到_次存储冲突。15 假定一组记录为(46，79，56，38，40，
5、80，46，75，28，46)，对其进行归并排序的过程中，供需要_趟完成。操作计算题16 有一组关键字序列(24，19，56，13，97，59，41，85，1，87)，写出用堆排序法进行升序排序的初始堆序列及第一趟排序后的堆序列。16 给定如下图所示的带权无向图 G1。17 画出该图的邻接矩阵。18 给出采用普里姆算法从顶点 3 出发构造最小生成树的过程。算法设计题19 设计在无头结点的单链表中删除第 i 个结点的算法。单项选择题20 十进制 95 的二进制为( )。（A）1011111（B） 1100011（C） 1011101（D）101111021 若 a=4，则执行 a*=42 语句后
6、，a 的值为( )。（A）7（B） 9（C） 8（D）1022 若 strl 和 str2 的说明如下：char strl20；char*str2=“teacher”：则语句strcpy(strl，str2)执行后， strlen(str1)的值是( )。（A）7（B） 29（C） 8（D）3023 字符串” x54BNHGbl3，2m”的长度为( )。（A）12（B） 13（C） 11（D）1424 选出合法的 C 语言标识符( )。（A）abc（B） numberof（C） 5)705 （D）PI25 设整型变量 b 的值为 4，执行完语句 b+=b后，b 的值为( )。（A）6（B） 7
7、（C） 8（D）926 C 语言表达式 63&3 8L 8L4+2 则 y 的值是( )。（A）111144（B） 333（C） 111（D）4431 说明外部变量的说明符为( )。（A）global（B） register（C） static （D）extern32 若有以下说明：struct personchar name20；int age；a=”Li”，20)，“p=&a ；则对结构体变量 a 中 age 成员错误的引用方式是( )（A）(*p) age （B） Page（C） age （D）page33 赋值运算 n=i+1 与下面( ) 语句的意义相同。（A）n=(i+1)n （B
8、） n=n(i+1)（C） n=ni+1 （D）都不正确34 向文件中写数据的函数是( )。（A）fgetc（B） fprintf（C） fscanf （D）fopen填空题35 以下程序中，主函数调用了 LineMax 函数，实现在 N 行 M 列的二维数组中，找出每一行上的最大值。请填空。#define N 3#define M 4void LineMax(inv xNM)int i，j，P；for(i=0；iN；i+)p=0；for(j=1；jM；j+)if(xipsk)_；printf(“d n”，k)；45 下面的程序用来统计文件中字符的个数。main( )FILE*fp；long
9、num=0；if(fp=fopen(“fnameday” ，“r”)=NULL)printf“Cannt open filen”)；etit(O)；whilefgetc(fp)；num+ ； )printf(“hum=d n”，num)；fclose(fp)；程序设计题46 利用递归函数调用方式，将所输入的 5 个字符以相反顺序打印出来。47 编写一个程序，将用户输入的十进制整数转换成任意进制的数。山东专升本计算机科学与技术（综合二）模拟试卷 7 答案与解析单项选择题1 【正确答案】 B【试题解析】 公式：Loc(Aij)=10( 基地址)+(51)*100+(5 1)*2=818。2 【正确
10、答案】 B【试题解析】 n 阶对称矩阵 A 中的元素满足下述条件：a ij=aji(1ij 的下标 i、j 的对应关系为：当 i=j 时，k=i(i 一 1)2+j；当 i3 【正确答案】 C【试题解析】 由二叉树结点的公式：n=n 0+n1+n2=n0+n1+(n01)=2n0+n11，因为n=1001，所以 1002=2n0+n1，在完全二叉树树中，n 1 只能取 0 或 1，在本题中只能取 0，故 n=501，因此选 C。4 【正确答案】 A【试题解析】 第一步：加括号 D(CA)+B*E D*F(D (CA)+B*ED*F(D (CA)+(B*E)一 D*F(D (CA)+(B*E)一
11、(D*F)(D(CA)+(B*E)一(D*F)(D(CA)+(B*E)一(D*F)第二步：从最内层括号中的运算符开始前移，取代距其最近的左括号。第三步：将所有右括号去掉，得到前缀表达式：一+DCA*BE*DF。5 【正确答案】 C【试题解析】 最小值为完全二叉树的情况，深度为 k，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树一一对应时，称为完全二叉树。深度为 k 的完全二叉树结点个数范围：最小结点数 2k 一 1，解得结果为 11；单节点二叉树时值最大为 1025。6 【正确答案】 A【试题解析】 N=N0+N1+Nm；N=N1+2N2+mNm：所以；7 【正确答案】
12、 B【试题解析】 设 N=V， E)是连通网，TE 是最小生成树中边的集合，初始为空。定义一个仅含一个顶点的集合 U=u0，u0 V(u0 可从顶点集合 V 中任意选取)，则将 N 中的所有顶点分成了两个集合：U，VU。重复执行以下操作：在所有的uu，v V 决定的边(u，v) E中寻找一条代价最小的边 (u0，v0)，将该边并入 TE集合，同时 v0 并入 U，直到 U=V 为止。以上操作，通俗地讲，实际上是从两大阵营(两个图的顶点的集合) 中寻找一条最短的路。Prim 算法中，最小代价生成树的顶点和边都是逐步生成的，开始的时候顶点集合中有一个顶点，边的集合为空。8 【正确答案】 B【试题解
13、析】 折半查找要求查找表用顺序存储结构存放且各数据元素按关键字有序(升序或降序) 排列，也就是说折半查找只适用于对有序顺序表进行查找，有序顺序表也称为有序表。折半查找的基本思想是：首先以整个查找表作为查找范围，用查找条件中给定值 k 与中间位置结点的关键字比较，若相等，则查找成功；否则，根据比较结果缩小查找范围，如果 k 的值小于关键字的值，根据查找表的有序性可知查找的数据元素只有可能在表的前半部分，即在左半部分子表中，所以继续对左子表进行折半查找；若 k 的值大于中间结点的关键字值，则可以判定查找的数据元素只有可能在表的后半部分，即在右半部分子表中，所以应该继续对右子表进行折半查找。每进行一
14、次折半查找，要么查找成功，结束查找，要么将查找范围缩小一半，如此重复，直到查找成功或查找范围缩小为空，即查找失败为止。9 【正确答案】 A【试题解析】 简单选择排序的基本思想是：每一趟在 ni+1(i=1，2，3，n一 1)个记录中选取关键字最小的记录作为有序序列中的第 i 个记录。它的具体实现过程为：(1)将整个记录序列划分为有序区域和无序区域，有序区域位于最左端，无序区域位于右端，初始状态有序区域为空，无序区域含有待排序的所有 n 个记录。(2)设置一个整型变量 index，用于记录在一趟的比较过程中，当前关键字值最小的记录位置。开始将它设定为当前无序区域的第一个位置，即假设这个位置的关键
15、字最小，然后用它与无序区域中其他记录进行比较，若发现有比它的关键字还小的记录，就将 index 改为这个新的最小记录位置，随后再用 aindexkey 与后面的记录进行比较，并根据比较结果，随时修改 index 的值，一趟结束后 index 中保留的就是本趟选择的关键字最小的记录位置。(3)将 index 位置的记录交换到无序区域的第一个位置，使得有序区域扩展了一个记录，而无序区域减少了一个记录。不断重复 2，3，直到无序区域剩下一个记录为止。此时所有的记录已经按关键字从小到大的顺序排列就位。10 【正确答案】 B填空题11 【正确答案】 时间；空间12 【正确答案】 n2+113 【正确答案
16、】 acdeb ； acedb( 答案不唯一)14 【正确答案】 515 【正确答案】 4操作计算题16 【正确答案】 (1)建小堆所以初始堆序列为：(1，13 ，41，19，87，59，56，85，61，97)(2) 第一趟排序后的堆序列第一趟排序后的堆序列为：(1，13，19，41，61，87，59，56，85。97)17 【正确答案】 18 【正确答案】 说明：第三步答案不唯一。算法设计题19 【正确答案】 算法思想为：(1)应判断删除位置的合法性，当 i0 或 in 一 1 时，不允许进行删除操作；(2)当 i=0 时，删除第一个结点；(3)当 0in 时，允许进行删除操作，但在查找被
17、删除结点时，须用指针记住该结点的前趋结点。算法描述如下：delete(LinkList*q，int i)在无头结点的单链表中删除第 i 个结点LinkList*P，*S ；int j；if(i0)printf(“Cant delete”)；else if(i=0、s=q；q=q 一 next；free(s)单项选择题20 【正确答案】 A【试题解析】 采用除 2 取余法，逆序输出。21 【正确答案】 C【试题解析】 a*=42 相当于 a=a*(42)，a=4，所以结果为 4*2=8，答案为 C。22 【正确答案】 A【试题解析】 strl 为字符数组， str2 为字符指针，经过 strcp
18、y(strl，str2)后，把str2 中内容复制给了 strl，求字符串长度时要注意0是字符串的结束标志，不占长度，所以结果为 7，而不是 8。23 【正确答案】 C【试题解析】 转义字符以反斜线“”，开头，后跟一个或几个字符。转义字符具有特定的含义，不同于字符原有的意义，故称转义字符。转义字符主要用来表示那些用一般字符不便于表示的控制代码。常用的转义字符及其含义见下表。所以x54 表示一个字符，长度为 11，答案为 C。24 【正确答案】 D【试题解析】 C 语言规定，标识符只能是由字母 (AZ，az)、数字(09)、下划线(一 )组成的字符串，并且其第一个字符必须是字母或下划线。以下标识
19、符是合法的：a，x，x3，BOOK1，sum5，num_1 以下标识符是非法的：3s 以数字开头s*T 出现非法字符 *一 3x 以减号开头 bowy 一 1 出现非法字符一(减号)在使用标识符时还必须注意以下几点：在标识符中，大小写是有区别的。例如 BOOK 和 book是两个不同的标识符。习惯上符号常量用大写字母表示，而变量名等用小写字母表示。标识符不能与关键字同名，也不能与系统预先定义的标准标识符(如标准函数)同名。25 【正确答案】 B【试题解析】 b+=b 一一，可以分解为如下两条语句：b+=b b 一一b 的初始值为 4，所以结果为 7。26 【正确答案】 B【试题解析】 关系运算
20、符、算术运算符和逻辑运算符之间的优先次序依次是：算术运算符级别最高，关系运算符次之，逻辑运算符最低。27 【正确答案】 B【试题解析】 d1 为指针， a 为数组名，d1 只能指向一个地址，而不能指向一个确切的值。28 【正确答案】 D【试题解析】 在 C 语言中，逗号运算符即“，”8 ，可以用于将若干个表达式连接起来构成一个逗号表达式。其一般形式为：表达式 1，表达式 2，表达式 n 求解过程为：自左至右，先求解表达式 1，再求解表达式 2，最后求解表达式n。表达式 n 的值即为整个逗号表达式的值。例如：a=(3+5，6+8)是一个逗号表达式，它的值为第 2 个表达式 6+8 的值，即为 1
21、4。逗号运算符在所有运算符中的优先级别最低，且具有从左至右的结合性。它起到了把若干个表达式串联起来的作用。例如：a=3*4，a*5，a+10 求解过程为：先计算 3*4，将值 12 赋给 a，然后计算a*5 的值为 60，最后计算 a+10 的值为 12+10=22，所以整个表达式的值为 22。注意变量 a 的值为 12。使用逗号表达式应注意以下几点：(1)一个逗号表达式可以与另一个表达式组成一个新的逗号表达式。例如：(a=3*4 ，a*5) ，a+10 其中逗号表达式 a=3*4，a*5 与表达式 a+10 构成了新逗号表达式。(2)不是任何地方出现逗号都作为逗号运算符。例如，在变量说明中的
22、逗号只起间隔符的使用，不构成逗号表达式。29 【正确答案】 C【试题解析】 在 C 语言中，可以在被调函数内采用 return 语句获得函数的返回值。一个函数利用 return 语句只能返回一个值。return 语句的格式为：(以下两种写法均可)return( 表达式)或 return 表达式。在进行函数定义时，应使 return 语句中的表达式的类型与函数类型说明一致。当 return 语句中的表达式的类型与函数类型说明不一致时，则以函数类型说明为准，系统自动将 return 语句中的表达式的值转换为函数类型说明所指定的类型。当函数的返回值的数据类型是 int(整型)时，在函数定义时，函数类
23、型说明符可以省略，也就是说，系统默认的返回值类型是整型。当函数没有返回值时，在函数定义时，函数类型说明符可以为 void(空类型)。30 【正确答案】 D【试题解析】 格式字符串的一般形式为：输入数据宽度长度类型，宽度：用十进制整数指定输入的宽度(即字符数)。例如：scanf(“5d”，&a)；输入：12345678 只把 12345 赋予变量 a，其余部分被截去。又如：scanf(“4d4d”，&a， b)；输入：12345678 将把 1234 赋予 a，而把 5678 赋予 b。注意空格为输入数据的分隔符。31 【正确答案】 D【试题解析】 register 是寄存器型存储方式类别符；采
24、用 extern 来声明全局变量可以扩大全局变量的作用域；static 是静态型存储方式类别符； global 是全局变量声明符。32 【正确答案】 B【试题解析】 通过指针去访问所指结构体变量的某个成员时，有如下两种方法：(*p)成员变量或 p 一 成员变量。33 【正确答案】 B【试题解析】 C 语言规定，所有双目运算符都可以和赋值运算符一起组合成复合赋值运算符。共有 10 种复合赋值运算符，即：+=，一=，*= ， =，=，=，&=，=，=其一般形式为：=等价于：=34 【正确答案】 B【试题解析】 fgetc 函数能够从指定文件中读入一个字符；格式化读写函数fprintf、fscanf
25、 与函数 printf、scanf 的作用相仿，区别在于 fprintf 和 fscanf 函数的读写对象不是终端而是磁盘文件；fopen 函数打开文件。填空题35 【正确答案】 xip=xijxipLineMax(x)【试题解析】 在函数 LineMax 中，二重循环求数组的每一行的最大值，取数组中的每一行的第一个元素与后面的元素比较，每一行的最大值存放在第一个元素中，则可知前两个空该填的内容。最后一个空是要在主函数中调用 LineMax 函数，只要给出正确的调用格式即可。36 【正确答案】 d=10 k+ kvoid main( )int i=0，base，n，j，num20；printf(“输入一个十进制数：”)；scanf(“d”， &n)：printf(“输入要转换的进制：”)；scanf(“d”， &base)；doi+：numi=nbase；n=nbase：)while(n!=0)；printf(”转换的结果： ”)；for(j=i；j=1；j 一一)printf(“d f，numj) ；【试题解析】 采用辗转相除法进行进制之间的相互转换，将结果存储在一维数组num 中，最后显示其值即可。
