山东专升本计算机科学与技术（综合二）模拟试卷1（共334题）

山东专升本计算机科学与技术（综合二）模拟试卷1（共8套）（共334题）山东专升本计算机科学与技术（综合二）模拟试卷第1套一、单项选择题(本题共10题，每题1.0分，共10分。)1、数据结构，与所使用的计算机无关的是数据的哪种结构?()A、存储B、物理C、逻辑D、物理和存储标准答案：C知识点解析：数据的逻辑结构是指数据的各数据元素之间的逻辑关系，与计算机无关。2、线性表是()。A、一个有限序列，可以为空B、一个有限序列，不能为空C、一个无限序列，可以为空D、一个无限序列，不能为空标准答案：A知识点解析：线性表是由相同类型的结点组成的有限序列。结点的个数称为其长度。长蔓为O的线性表称为空表。3、下列哪个选项的邻接矩阵必定是对称矩阵?()A、有向图B、无向图C、AOV网D、AOE网标准答案：B知识点解析：无向图的邻接矩阵，存在(i，j)的边，必定有一条(j，i)的边，故它是对称矩阵。4、串是一种特殊的线性表，其特殊性体现在()。A、可以顺序存储B、数据元素是一个字符C、可以链式存储D、数据元素可以是多个字符标准答案：D知识点解析：串是由零个或多个字符组成的有限序列。5、不含任何结点的空树是()。A、是一棵树B、是一棵二叉树C、是一棵树也是一棵二叉树D、既不是树也不是二叉树标准答案：C知识点解析：树是n(n≥0)个结点的有限集合，若n=0，则称为空树。空树也可以是空二叉树。6、已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是()。A、108B、180C、176D、112标准答案：D知识点解析：地址计算公式：Loc(A[i])=L1+(i一1)×d=L1+8×4=144，所以L1=112。7、链表适用于哪种查找方法?()A、顺序B、二分法C、顺序，也能二分法D、随机标准答案：A知识点解析：顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。折半查找要求查找表用顺序存储结构存放且各数据元素按关键字有序(升序或降序)排列，也就是说折半查找只适用于对有序顺序表进行查找。有序顺序表也称为有序表。8、用邻接表表示图，进行广度优先遍历时，通常是采用哪种结构来实现算法的?()A、栈B、队列C、树D、图标准答案：B知识点解析：广度优先搜索算法可以使用队列结构实现。9、任何一个无向连通图的最小生成树是()。A、只有一棵B、一棵或多棵C、一定有多棵D、可能不存在标准答案：B知识点解析：看较小的边里面有没有两条边的和是相同的，如果有就可能出现多个最小生成树的，不过MST的总代价是唯一的。10、若某完全二叉树的结点个数为：100，则第60个结点的度为()。A、0B、1C、2D、不确定标准答案：A知识点解析：具有n个结点的完全二叉树的深度为：(log2n)+1，所以100个结点的完全二叉树的深度为7。深度为k的二又树至多有2k一1个结点。第60个结点为叶子结点，所以度为0。二、判断题(本题共10题，每题1.0分，共10分。)11、线性表的顺序存储结构是一种随机存储结构。()A、正确B、错误标准答案：A知识点解析：顺序存储结构的特点：(1)利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构(物理结构)一致；(2)在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。12、一个栈的入栈序列是a、b、c、d、e，则d、c、e、a、b是一个不可能的输出序列。()A、正确B、错误标准答案：A知识点解析：考查堆栈“后进先出”的特点。第一个出栈元素是d，说明a、b、c已经入栈，因为a先于b进栈，所以必定在b之后出栈。13、广义表(a，(a，b)，d，e，(i，j)，k)的深度是2。()A、正确B、错误标准答案：B知识点解析：广义表的深度定义为所含括弧的重数，所以深度应为3。14、树是一种重要的线性数据结构。()A、正确B、错误标准答案：B知识点解析：线性表、堆栈、队列都可认为是线性结构，树和二叉树都是树形结构，而图则属于图状结构。15、按照二叉树的定义，具有三个结点的二叉树有5种。()A、正确B、错误标准答案：A知识点解析：如图所示：16、已知一个有向图的邻接矩阵表示，计算第i个结点的出度的方法是求矩阵第i列非零元的个数。()A、正确B、错误标准答案：A知识点解析：第i列非零元的个数表示的是第i个结点的入度，第i行非零元的个数表示的是第i个结点的出度。17、将递归算法转换为对应的非递归算法时，通常需要使用队列。()A、正确B、错误标准答案：B知识点解析：将递归算法转换为对应的非递归算法时，通常需要使用栈。18、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同。()A、正确B、错误标准答案：B知识点解析：在哈夫曼编码中，当两个字符出现的频率相同时，权重相同，但这两个字符的位置不同，所以其编码也不同。19、散列法存储的基本思想是由关键字的值决定数据的存储地址。()A、正确B、错误标准答案：B知识点解析：散列法存储的基本思想是由关键字的值决定数据的存储地址，也即是把关键字的值作为自变量，通过一定的函数(称为散列函数)计算出对应的函数值，把这个函数值解释为数据的存储地址，而不是直接把关键字的值作为数据的存储地址。20、(101，88，46，70，34，39，45，58，66，10)是堆。()A、正确B、错误标准答案：A知识点解析：是大顶堆。三、填空题(本题共10题，每题1.0分，共10分。)21、广义表A((()，(a，(b)，c)))，}lead(tail(head(tail(Ilead(A))))等于________。标准答案：(b)知识点解析：暂无解析22、已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是________。标准答案：DGEBFCA知识点解析：暂无解析23、在顺序表(8，11，15，19，25，26，30，33，42，48，50)中，用二分(折半)法查找关键码值20，需做的关键码比较次数为________。标准答案：4知识点解析：暂无解析24、设串s1=“Iamastudent”，则串长为________。标准答案：14知识点解析：空格也计算在串的长度之中。25、数组A[0．．5，0．．6]的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续内存单元中，则元素a[5][5]的地址为________。标准答案：1175知识点解析：aES]E5]的地址=1000+(5*6+5)*5=1175。26、深度为k的完全二叉树至少有________个结点，至多有________个结点。标准答案：2k-1，2k一1知识点解析：暂无解析27、对二叉树进行________遍历，可以得到安关键字从小到大排列的结点序列。标准答案：中序知识点解析：暂无解析28、下面程序段的时间复杂度是________。i=1：while(i<=n)i=i*3：标准答案：0(log3n)知识点解析：暂无解析29、假定一个有向图的边集为{＜a，c＞，＜a，e＞，＜c，f＞，＜d，c＞，＜e，b＞，＜e，d＞}，对该图进行拓扑排序得到的顶点序列为________。标准答案：aebdcf(答案不唯一)知识点解析：暂无解析30、假定一组记录为(46，79，56，38，40，80)，对其进行快速排序的过程中，共需要________趟排序。标准答案：3知识点解析：暂无解析四、操作计算题(本题共5题，每题1.0分，共5分。)已知待排序的序列为(503，87，512，61，908，170，897，275，653，462)，试完成下列各题。31、根据以上序列建立一个堆(画出第一步和最后堆的结果图)，希望先输出最小值。标准答案：建小堆知识点解析：暂无解析32、输出最小值后，如何得到次小值(并画出相应结果图)。标准答案：求次小值知识点解析：暂无解析下表给出了某工程各工序之间的优先关系和各工序所需时间。33、画出相应的AOE网。标准答案：AOE网如图。图中虚线表示在时间上前后工序之间仅是接续顺序关系不存在依赖关系。顶点代表事件，弧代表活动，弧上的权代表活动持续时间。题中顶点1代表工程开始事件，顶点11代表工程结束事件。知识点解析：暂无解析34、列出各事件的最早发生时问，最迟发生时间。标准答案：各事件发生的最早和最晚时间如下表。知识点解析：暂无解析35、找出关键路径并指明完成该工程所需最短时间。标准答案：关键路径为顶点序列：1一>2一>4一>6一>8一>9一>10一>11；事件序列：A一>C一>E一>G一>H一>L一>M，完成工程所需的最短时间为445。知识点解析：暂无解析一、单项选择题(本题共10题，每题1.0分，共10分。)36、下面标识符中，不合法的用户标识符为()。A、PadB、a10C、124D、a#b标准答案：D知识点解析：C语言中规定，标识符只能是字母(A～Z，a～z)、数字(0～9)、下划线(一)组成的字符串，并且其第一个字符必须是字母或下划线。D包含’#’，是不合法的。37、下列字符串不符合标识符规定的是()。A、SUMB、sumC、3cdD、end标准答案：C知识点解析：标识符规定只能由26个英文字母(大小写均可)，数字0～9和下划线组成，且不能以数字开头，题中的3cd不符合规定。本题答案为C。38、设有如下的变量定义：inti=8，k，a，b；unsignedlongw=5：dotlblex=1，42，y=5．2；则以下符合C语言语法的表达式是()A、a+=a一=(b=4)*(a=3)B、x％(一3)；C、a=a*3=2D、y=float(i)标准答案：A知识点解析：A项是赋值表达式和算术表达式的结合，符合C语言语法；B项中，％是拟运算符，要求运算符两侧均为整数，x为double，显然错误；c项是赋值表达式，要求赋值运算符的左侧是变量，3=2部分显然错误；D项，强制类型转换运算符使用错误，应为y=(float)i。39、以下程序的输出为()。main(){inta=20，b=30，c=40；if(a>b)a=b，b=c；c=a；printf(“a=％d，b=％d，c=％d”，a，b，c)；A、a=20，b=30，c=20B、a=20，b=40，c=20C、a===30，b=40，c=20D、a=30，b=40，c=30标准答案：A知识点解析：题中的“a=b，b=c；”是一个语句书写在了两行，因a＞b为假，所此句不执行，又“c=a”与if语句无关，总要执行，故a，b值不变，c值为20。40、设j为int型变量，则下面for循环语句的执行结果是()。for(j=10；j>3；j一一){if(j％3)j一一；一一j；一一j；printf(“％d”，j)；}A、63B、74C、62D、73标准答案：B知识点解析：for循环初值，j=10，进行第一次循环：j％3=1，if语句为真，j自减为9，之后两次自减，j值变为7，打印输出，得第一次输出为7，第一次循环结束；j再一次自减，值为6，j满足for循环条件j＞3，继续第二次循环，6％3=0，if语句为假，之后两次自减，j值变为4，打印输出，得第二次输出为4，第二次循环结束；j再一次自减，值为3，循环条件j＞3不再满足，循环结束。41、若有如下定义语句：doublea[s]；inti=0；能正确给a数组元素输入数据的语句是()A、scanf(“％If％If％If％If”，a)；B、for(i=0；i<=5；i++)scanf(“％If”，a+i)；C、while(i＜5)scanf(“％If”，&a[i++])；D、while(i＜5)scanf(“％If”，a+i)；标准答案：C知识点解析：选择式D中a+i，a代表首地址，i代表偏移量，这里的偏移量随变量的数据类型的不同而不同，ehari的偏移量为1，inti的偏移量为2，floati的偏移量为4，doublei的偏移量为8，所以在计算地址的时候除了要考虑首地址和第几个元素外，还要考虑所声明的变量类型，选择式B中共要循环6次，而doublea[5]只声明了5个元素，所以出错。42、有以下程序：voidfun(inta，intb，intc){a=456；b=567；c=678；)main(){intx=10，y=20，z=30；fun(x，y，z)；printf(“％d，％d，％d＼n”，x，y，z)；}输出结果是()A、30，20，10B、10，20，30C、456567678D、678567456标准答案：B知识点解析：main函数为人口函数，程序从main函数开始执行。main函数中，首先定义了整型变量x，y，z，并进行了赋初值：x=10，y=20，z=30，之后调用fun函数，参数为x，y，z，注意fun函数参数的使用只是值传递，只是简单的把x，y，z的值传给了fun的实参a，b，c，在fun函数中对a，b，c重新进行了赋值，执行完毕，返回到main函数，注意x，y，z的值没有改变过，打印输出x，y，z的值还是其初赋值：10，20，30，答案为B。43、以下程序的输出结果是()。#definef(x)x*xmain(){inta=8，b=4，c；c=f(a)／f(b)；printf(“％d＼n”，c)；}A、4B、8C、64D、16标准答案：C知识点解析：此题程序中定义了一个带参数的宏名为f，当程序中遇到此宏名进行展开时，则应使用定义时的字符串x*x进行替换。替换的原则是：遇到形参x，则以实参a代替，其他字符不变。所以，f(x)经宏展开后成为字符串f(x)*f(x)。整个赋值语句的形式变为c=f(a)*f(a)／f(b)*f(b)，则c=8*8／4*4=64。44、下列关于指针变量赋空值的说法错误的是()。A、当赋空值的时候，变量指向地址为0的存储单元B、赋值语句可以表达为变量名=‘＼O’C、赋值语句可以表达为变量名=0D、一个指针变量可以被赋空值标准答案：A知识点解析：除了给指针变量赋地址值外，还可以给指针变量赋NULL值，由于NULL的代码值为0，所以指针变量名=NULL；等同于变量名=‘＼0’；或变量名=0；指针变量并不是指向一个地址为0的存储单元，而是具有一个空值。注意：指针变量赋地址值的方式可以是通过求地址运算、通过指针变量和通过标准函数获得地址值。45、有如下程序：#include＜stdio．h>main(){FILE*fpl；fpl=fopen(“f1．txt”，“w”)；fprintf(fpl，“abc”)；fclose(fpl)；}若文本文件f1．txt中原有内容为good，则运行以上程序后文件f1．txt中的内容为()A、goodabcB、abcdC、abcD、abcgood标准答案：C知识点解析：暂无解析六、程序分析题(本题共6题，每题1.0分，共6分。)阅读下列程序，给出运行结果。46、main(){inta，b；for(a=1，b=1；a<100；a++){if(b>=10)break；if(b％3==1){b+=3：continue；}b=b一5：}printf(“％d＼n”，b)；}标准答案：10知识点解析：break语句其执行过程是：终止对switch语句或循环语句的执行，即跳出这两种语句，而转入下一语句执行。使用break语句应注意如下几个问题：break语句只能用于循环语句或SWitch语句中。如果在程序中有下列语句：if(…)break：则此时的if语句一定位于循环体中或S’Witch语句中，break语句跳出的也不是if语句，而是跳出包含此if语句的循环体或switch语句。continue语句，其作用是结束本次循环，即跳过本层循环体中余下尚未执行的语句，接着再一次进行循环的条件判定。注意：执行continue语句并没有使整个循环终止。47、intm=13：intfun(intx，inty){intm=3：return(X*y—m)；}main(){inta=7，b=5：print{(“％d＼n”，fun(a，b)／m)：}标准答案：2知识点解析：全局变量是指在函数之外定义的变量。全局变量的定义位置可以在所有函数之前，也可以在各个函数之间。一般情况下，全局变量的作用范围是从定义全局变量的位置起到本源程序结束止。所谓局部变量是指在一定范围内有效的变量。局部变量定义位置不同，其作用域也不同。注意：在函数体内定义的变量，在本函数范围内有效，即其作用域只局限在本函数体内；在复合语句内定义的变量，仅在本复合语句范围内有效；有参函数中，的形式参数也是局部变量，只在其所在的函数范围内有效。局部变量遇到全局变量时，局部变量发挥作用。48、main(){chara[]=”ABCDEFG”，k，*P；fun(a，0，2)；fun(a，4，6)；print{(“％s＼n”，a)；}fun(char*S，intpl，intp2){charC；while(pl＜op2){c=s[pl]；s[p1]=s[p2]；s[p2]=C；p1++；p2一一；}}标准答案：CBADGFE知识点解析：fun函数完成字符的交换功能。49、#defineP(a，b)a+b#defineQ(c)3*P(a，b)+Cmain(){inta=1，b=2，c=3，X：x=Q(c)*2：print{(“％d”，x)；}标准答案：8知识点解析：宏替换要注意原样替换而不要臆造，x=Q(c)*2=3*P(a，b)+c=3*a+b+C，所以结果为3*1+2+3=8。50、#include#include(string．h>main(){charstr[100]=”Howdoyoudo”：strcpy(str+strlen(str)／2，“esshe”)：print{(“％s＼n”，str)；}标准答案：HOWdoesshe知识点解析：strlen(str)的值为13，strcpy(字符数组名1，字符数组名2)，功能：把字符数组2中的字符串拷贝到字符数组1中。串结束标志”＼0”也一同拷贝。字符数名2，也可以是一个字符串常量。这时相当于把一个字符串赋予一个字符数组。51、f(inta){intb=0：staticc=3；a=c++，b++：return(a)；}main(){inta=2，i，k；for(i=0；i<2；i++)k=f(a++)；print{(“％d＼n”，k)；}标准答案：4知识点解析：所谓静态存储方式指的是在程序编译时就给相关的变量分配固定的存储空间(即在程序运行的整个期间内都不变)的方式。说明：(1)静态局部变量的存储空间是在程序编译时由系统分配的，且在程序运行的整个期间都固定不变。因此，该类变量在其所在函数调用结束后仍然可以保留变量值。(2)静态局部变量的初值是在程序编译时一次性赋予的，即在程序运行期间不再赋初值。山东专升本计算机科学与技术（综合二）模拟试卷第2套一、单项选择题(本题共10题，每题1.0分，共10分。)1、在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为()个。A、4B、5C、6D、7标准答案：A知识点解析：暂无解析2、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E={＜V1，V2＞，＜V1，V3＞，＜V1，V4＞，＜V3，V5＞，＜V3，A、V1，V3，V4,V6，V2，V5，V7B、V，V1，V2，V6，V4，V5，V7C、V1，V3，V4，V5，V2，V6，V7D、V1，V2，V5，V3，V4，V6，V7标准答案：A知识点解析：在给定的有向图G中，若顶点序列vi1,vi2…vin满足下列条件：若在有向图G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前，便称这个序列为一个拓扑序列。3、设一个顺序有序表A[1：14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为()。A、A[1]，A[2]，A[3]，A[4]B、AD]，A[14]，A[7]，A[4]C、A[7]，A[3]，A[5]，A[4]D、A[7]，A[5]，A[3]，A[4]标准答案：C知识点解析：暂无解析4、设一组初始记录关键字序列为(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，Y标准答案：D知识点解析：暂无解析5、设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为()。A、40，50，20，95B、15，40，60，20C、15，20，40，45D、45，40，15，20标准答案：B知识点解析：暂无解析6、设有二维数组A[1：U1，1：U2]，已知数据元素A[1，1]在位置2，A[2，3]在位置18，A[3，2]在位置28，则元素A[4，5]的位置()。A、46B、45C、48D、30标准答案：A知识点解析：题目中没有给出该数组是行优先存储还是列优先存储，因此需要首先判断数组的存储方式。因为Loc(A[3，2])＞Loc(A[2，3])，所以数组一定是按行存储的。因为A[1，1]是起始位置，则有L1=2。利用已知条件，根据计算地址的公式有：Loc(A[2，3])=L1+(2—1)×U2×d+(3—1)×d=18，即2+U2×d+2×d=18(方程1)Loc(A[3，2])=L1+(3—1)×U2×d+(2—1)×d=28，即2+2×U2×d+d=28(方程2)由以上两方程联立，得方程组，解得：U2=6，d=27、将一个A[1．．100，1．．100]的下三角矩阵，按行优先存入一维数组B[1..5050]中，A中元素A[66，65]，在B数组中的位置K为()。A、4419B、2209C、4417D、2319标准答案：B知识点解析：k=i(i一1)／2+j一1。8、设某棵二叉树的高度为10，则该二叉树上叶子结点最多有()。A、20B、255C、511D、1023标准答案：D知识点解析：一棵深度为k、结点个数为2k一1的二叉树称为满二叉树。满二叉树是深度为k的结点数目最多的二叉树。9、设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个。A、n—1B、nC、n+1D、n+2标准答案：C知识点解析：增加两个指示域Ltag和Rtag，并分别定义如下：LTag：取值为0时，作用不变(指向左孩子)，取值为1时，指示当前结点的前驱结点；RTag：取值为0时，作用不变(指向右孩子)，取值为1时，指示当前结点的后继结点；数据结构为：typefenumPointerTag{Link，Thread}；／／Link：指针，值为0；Thread：线索，值为1typedefstructBiThrNode；{TElemTypedata；structBiThrNode*lchild，*rchild；／／指向左孩子和右孩子PointerTagLTag，RTag；／／左、右标志，它们的取值决定了lchild、rchiltl的指向含义}BiThrNode，*BiThrTree；以上述结构构成的二叉链表称为线索链表。线索链表中指向前驱结点和后继结点的指针，称为线索。加上线索的二叉树称为线索二叉树(ThreaoledBinaryTree)。对二叉树按照某种次序遍历从而使其变为线索二叉树的过程叫做线索化。10、当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[1．．n]中时，数组中第i个结点的左孩子为()。A、A[2i](2i<=n)B、A[2i+1](2i+1<=n)C、A[i／2]D、无法确定标准答案：D知识点解析：如果2i+1<=n，则左孩子为A[2i+1]，否则就没有左孩子。所以无法确定。二、判断题(本题共10题，每题1.0分，共10分。)11、链表中结点数据域占的存储空间越多，存储密度越小。()A、正确B、错误标准答案：B知识点解析：存储密度=数据域占的存储空间／整个结点占的存储空问。12、带头结点和不带头结点的单链表在查找、删除、求长度等操作上无区别。()A、正确B、错误标准答案：B知识点解析：单链表在保存时，一般在第一个结点之前铺设一个结点，称为头结点。头结点的数据域可以不存任何信息，也可以存储线性表的长度等附加信息，其指针域中存储指向第一个结点的指针(即第一个元素结点的存储位置)。故单链表的头指针指向头结点，如果头结点的指针域为空，则说明是空表。为了在第一个数据元素前面加入新元素或者删除第一个节点时头指针的值不变，在第一个数据元素前面要加一个所谓的头节点。13、如果两个串的长度相等且对应字符也相同，则这两个串相等。()A、正确B、错误标准答案：A知识点解析：两个串相等的充要条件：两个串的长度相等，并且各个对应位置的字符都相等。14、压缩存储的三角矩阵和对称矩阵的存储空间不相同。()A、正确B、错误标准答案：B知识点解析：上、下三角矩阵元素个数为：1+2+3+…+n=n(n+1)／2。因为取值为0的元素不必保存，则可用一个B[n(n+1)／2]的一维数组来保存上、下三角矩阵的非零值。n阶对称方阵A中的元素满足下述条件：aij=aji(1<=i，j<=n)。对称矩阵(方阵)中的每一对数据元素可以共用一个存储空间，因此可以将n2个元素压缩存储到n(n+1)／2个元的空间中，所以存储空间相同。15、满二叉树是完全二叉树。()A、正确B、错误标准答案：A知识点解析：①满二叉树：一棵深度为k、结点个数为2k一1的二叉树称为满二叉树。满二叉树是深度为k的结点数目最多的二叉树。②完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树一一对应时，称为完全二叉树。深度为k的完全二叉树结点个数范围：最小结点数2k-1，最大结点数2k一1。满二叉树一定是完全二叉树。16、对于给定的树，与其对应的二叉树是唯一的。()A、正确B、错误标准答案：A知识点解析：将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。一棵树转换成二叉树后，根结点没有右孩子。17、线索二叉树的指针域中，指向前驱或后继的个数少于指向孩子的个数。()A、正确B、错误标准答案：B知识点解析：二叉树的二叉链表表示法有n+1个空链。同时，二叉链表(或三叉链表)虽然能方便地找到当前结点的双亲结点或左、右子结点，但如果要求寻找当前结点的前驱结点或者后继结点(按照某种遍历方法)，则上述方法就不方便了，只能在遍历过程中动态得到。如将二叉链表法中的n+1个空链利用起来，让其指向当前结点的前驱结点(如果指向左子树的指针域为空)或后继结点(如果指向右子树的指针域为空)，则可解决以上问题，这就是线索二叉树提出的原因。指向孩子的指针个数为n一1。18、给定图的邻接矩阵存储不一定唯一。()A、正确B、错误标准答案：B知识点解析：邻接矩阵法是图的一种顺序存储结构。设G有n个顶点，则可用n*n矩阵A(称为G的邻接矩阵，行标从1．．n，列标从1．．n)保存该有向图。对无向图：如果vi，vj之间有边，则A的元素aij=aji=1，否则aji=aji=0；A为对称矩阵。对有向图：如果vi有指向vj的弧，则A的元素aij=1，否则aij=0。对带权图：如果vi，vj之间有边或者弧(vi指向vj)，则A的元素aij=wij，否则aij=IN—FINITY。利用邻接矩阵，可以判断任意两顶点之间是否有边(弧)，并可方便求各顶点的度，图的边数等。例如：对无向图：顶点vi的度TD(vi)是A中第i行(或者第i列)的元素之和。对有向图：顶点vi的出度OD(vi)是第i行的元素之和，入度ID(vi)第i列的元素之和。对带权图：顶点vi的度的求法同上类似，但不再是求和，而是求行、列中不为零的元素个数。19、若一个有向图的邻接矩阵主对角线以下的元素均为0，则该图拓扑有序序列存在。()A、正确B、错误标准答案：A知识点解析：矩阵主对角线以下的元素全部为0，即满足如下条件的矩阵。aij=0，i＞=j如下图：该图为有向无环图，所以拓扑有序序列存在。20、对n个记录进行直接插入排序，其平均时间复杂度为0(nlog2n)。()A、正确B、错误标准答案：B知识点解析：三、填空题(本题共5题，每题1.0分，共5分。)21、一棵深度为6的满二叉树有________个分支点和________个叶子。标准答案：6232知识点解析：一棵深度为k，结点个数为2k一1的二叉树称为满二叉树。一棵深度为6的满二叉树，结点个数为63，二叉树的分支数B=n一1(分支数比结点数少1)，所以为62。因为：n=n0+n1+n2n0=n2+1所以：n0=32。22、一个字符串相等的充要条件是_______和________。标准答案：两个串的长度相等各个对应位置的字符都相等知识点解析：两个串相等的充要条件：两个串的长度相等，并且各个对应位置的字符都相等。23、从邻接矩阵可以看出，该图共有_______个顶点。如果是有向图，该图共有_______条弧。标准答案：34知识点解析：暂无解析24、栈的特点是______，队列的特点是______。标准答案：后进先出先进先出知识点解析：栈是一种特殊的线性表，它的操作被限制在某一端，即栈顶。栈是一种具有后进先出特性的数据结构。队列也是一种特殊类型的线性表，按照先进先出的原则对其中的元素进行操作。排在队首的先出队，然后后面的元素依次前移。进入队列必须存队尾进行，删除必须在队首进行。25、三元组表中的每个节点对应与稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的______、________和值。标准答案：行标列标知识点解析：稀疏矩阵可采用压缩存储，仅存储其中的非零元素。存储时，除了记下非零元素的值外，还要记录其行标i和列标j，即用(i，j，aij)三元素表示。四、算法设计题(本题共4题，每题1.0分，共4分。)已知关键字序列为{46，57，84，32，73，36，15，48，90，20)，要求：26、构造一棵二叉排序树。标准答案：构造过程如下：知识点解析：暂无解析27、在等概率情况下，该二叉排序树查找成功的平均查找长度。标准答案：平均查找长度为：(1+2*2+3*4+4*3)／10=2．9知识点解析：暂无解析28、假设在长度大于1的循环链表中，既无头结点，也无头指针，p为指向该链表中某个结点的指针。设计一个算法，删除p指向结点的前趋结点。标准答案：已知指向这个结点的指针是P，那么要删除这个结点的直接前趋结点，就要找到一个结点，它的指针域是指向P的直接前趋，然后用后删结点法，将结点P的直接前趋结点删除即可。算法如下：voidDeleteNode(ListNode*D){／／删除单循环链表中指定结点的直接前趋结点ListNode*s，*q；s=p：while(S-＞next-＞next!=p)S=S一>next；／／删除结点q=s一>next；s一>next=q一>next；free(s)；／／释放空间}注意：若单循环链表的长知识点解析：暂无解析29、设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号和花括号，嵌套的顺序任意，如([()]()}是正确的。请编写一个算法，实现判别给定表达式中所含括号是否正确配对。标准答案：算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。(1)当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；(2)从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；(3)算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。下面是解决这知识点解析：暂无解析一、单项选择题(本题共10题，每题1.0分，共10分。)30、下列说法中正确的是()。A、C程序书写时，不区分大小写字母B、C程序书写时，一行只能写一个语句C、C程序书写时，一个语句可分成几行书写D、C程序书写时每行必须有行号标准答案：C知识点解析：C语言严格区分大小写字母，如”A1”和”a1”被认为是两个不同的标识符，C程序的书写非常灵活，既可以一行多句，又可以一句多行，且每行不加行号。本题正确答案为C。31、当c的值不为0时，在下列选项中能正确将C的值赋给变量a、b的是()。A、c=b=a；B、(a=c)‖(b=c)；C、(a=c)8L8L(b=c)；D、a=c=b；标准答案：C知识点解析：赋值运算符是自右向左运算的。A项是将a的值赋给了b，又将b的值赋给了a，与题意不符；B项和C项都是逻辑运算，且都自左向右运算，它们的区别是：或运算是先计算左边表达式的值，若为真，则结束运算，若为假，继续计算右边表达式，所以，如果a=c为真(只需要a＞0)，那么b=c语句不会执行，即不能完成c给b的赋值；与运算则是两边的表达式都要计算，所以，a=c和b=c都能得到执行，C为正确答案；D项是将b的值赋给了c和a。32、对下述程序，正确的判断是()。mainO{inta，b；scanf(“％d，b，6d”，＆a，＆b)；if(a＞b)a=b；b=a；elsea++；b++；printf(“％d，％d”，a，b)；}A、有语法错误不能通过编译B、若输入4，5则输出5，6C、若输入5，4则输出4，5D、若输入5，4则输出5，5标准答案：A知识点解析：不管if语句中的条件真假，它只能执行一个语句，要想根据条件执行多个语句，应写成复合语句，程序中if和else的后面都有两个语句，违反了这一点。33、以下程序的输出结果是()。main(){intn=4；while(n一一)printf(“％d”，一一n)；}A、20B、31C、321D、210标准答案：A知识点解析：n=4，此时比较的仍是n=41=0，所以进行循环，但在循环之前，n执行减操作，此时n=3，待输出时输出的是一一n，即输出2。n=2，此时比较的仍是n=2!=0，所以进行循环，但在循环之前，n执行减操作，此时n=1，待输出时输出的是一一n，即输出0。n=0，此时比较的仍是n=0=0，所以不进行循环，没有输出。所以答案为A。34、有以下程序：main()inta[][3]={{1，2，3)，{4，5，0}}，i；for(i=0；i<3；i++)if(i<2)A11][i]=a[1][i]一1；elseaEl][i]=1；printf(“％d＼n”，a[0][1]+a[1][1]+a[1][2])；}执行后输出结果是()。A、7B、6C、8D、无确定植标准答案：A知识点解析：二维数组输入一个2行3列的值。在这里，一维数组的上限值没有指定，在C语言中是允许的，这样可以根据输入数值的多少确定上限的大小。在：For循环中输入I2的值，即输入0，1，2。当i=0时，得到a[1][0]=a[1][0]一1=3；当i=1时，得到a[1][1]=a[1][1]一1=4；当i=2时，执行else语句，得到a[1][2]=1；最后执行输出语句，求a[0][1]+a[1][1]+a[1][2]=2+4+1=7所以答案为7。35、有如下程序：intrune(inta，intb){return(a+b)；)main(){intx=2，y=5，z=8，r；r=func(func(X，y)，z)；printf(“％d＼n”，r)；}该程序的输出的结果是()。A、12B、13C、14D、15标准答案：D知识点解析：函数func第一次调用的返回值作为第二次调用的实参，第一次调用func(x，y)即func(2，5)的返回值是7，第二次调用func(7，z)即func(7，8)的返回值是15，所以r的值为15。36、若有说明：inta=2，*p=&a，*q=P；则以下非法的赋值语句是()。A、P=qB、*p=*qC、a=*qD、q=a标准答案：D知识点解析：所谓指针是一种特殊的变量，它存放的是另一个简单变量、数组等的地址。由计算机组成原理可知，内存的每一个存储单元都对应一个地址，CPU正是通过这个地址来访问每个存储单元的。而变量名最终仍要翻译成地址，才能找到所对应的真正的存储单元，进行读／写操作。当定义了一个指针后，对这个指针变量进行使用时，可以简单的理解为：加*后，对应一个数(变量值)，不加*，对应一个地址。所以：当由如下定义：inta，*p，*q，b；可以进行如下的赋值操作，类型才能兼容。如：p=&a；q=p；*q=5；q=&b；a=b；b=*p；37、有如下定义：Structdate{intyear，month，day；}；Structworklist{Charname[20]；Charsex；Structdatebirthday；}person；对结构体变量person的出生年份进行赋值时，下面正确的赋值语句是()。A、year=1978B、birthday．year=1978C、person．birthday．year=1958D、person．year=1958标准答案：C知识点解析：暂无解析38、要求函数的功能是在一维数组a中查找x值。若找到，则返回所在的下标值；否则，返回0。设数据放在数组元素的a[1]到a[n]中。在以下给出的函数中，不能正确执行此功能的函数是()。A、funa(int*a，intn，intx){*a=x；whlie(aEn]!=x)nm一；returnn；}B、funb(int*a，intn，intx){intk；for(k=1；k<=n；k++)if(a[k]==x)returnk；return0；}C、func(inta[]，intn，intx){int*k；a[o]=x；k=a+n；while(*k!=x)k一一；returnk—n：}D、fund(inta[]，intn，intx){intk=0；dok++；while((k标准答案：C知识点解析：在数组中找指定值是经常遇到的计算要求，有多种编程方法。在这里，数据预放在数组下标1至n的元素中，下标为0的元素没有放数据，程序可以利用这个位置简化查找函数。函数funa先将要查找的数放入a[0]，从数据表的最后一个元素开始逆序向前查找。这样做的好处是循环条件不必担心因数组中原先没有值为x的元素而一直顺序查找下去，访问不是数表的元素，需插入条件n＞0。在a[0]处放入x后，这个条件就不必要了，循环至少在访问了a[0]后终止，并返回0值。所以该函数能完成指定的功能。函数funb采用常规的办法编写，循环在a[1]与a[n]之间顺序寻找，一旦找到立即返回找到处的下标，直至查找循环结束，查不到指定的值而返回0值。函数func采用与函数funa相同的方法，不过是另外引入一个指针变量。但是该函数return语句后的表达式有严重的错误，应返回k—a，两指针的差，其值等于找到元素的下标。表达式k—n是指针k向前移n个位置的指针值。函数fund预置k为0，循环让k增1，并在k在界内和a[k]不等于x的情况下循环。循环结束有两种情况，或k已不在界内，或k在界内，并且a[k]等于x。若是后者，函数返回k，而若前者，函数返回比该函数也能正确完成查找工作。这样，不能正确完成查找工作的函数是函数{onec。所以正确选择是C。39、设有代码“int(*ptr)[10]；”，其中的ptr是()。A、10个指向整型变量的指针B、指向10个整型变量的函数指针C、一个指向具有10个元素的一维数组的指针D、具有10个指针元素的一维数组标准答案：C知识点解析：代码”int(*ptr)[10]；”的分析过程是：因圆括号内的ptr先与字符*结合，字符*修饰标识符ptr是一种指针；接着与后面的一对方括号结合，表示是这样的一种指针，是指向一维数组的；再有方括号中的10，说明这种数组有10个元素。至此，ptr是指向含10个元素的一维数组的指针。六、编程题(本题共2题，每题1.0分，共2分。)40、编写一个函数，完成如下功能：数组a中存放N(N为常整数)个由小到大排列的有序整数，从键盘输入一整数x，使用二分法在数组a中查找是否有此整数。标准答案：intBinSrch(inta[]，intN，intx)／／在长为N的中查找关键字x，若查找成功，返回k所在位置，查找失败返回0。{intlow=0；inthigh=N一1：intmid；if(10w<=high)／／low和high分别是数组a的下界和上界{mid=(10w+high)／2；if(a[mid]==x)return(mid)；elseif(a[mid]>x)high=mid一1；elselow=mid+1；}elsereturn(0)；／／查找失知识点解析：暂无解析41、编写如下C程序：主函数读入20个学生的成绩，每个学生5门课程。然后，用两个函数分别实现计算并输出每个学生的平均分和每门课程的平均分；按学生的平均成绩由高到低排序，并输出排序后的结果。标准答案：可设一个二维数组a[20][5]存放20个人5门课的成绩。再设一个一维数组v[5]存放所求得各科平均成绩，设数组average[20]为每个同学平均成绩。编程如下：#include”stdio．h”／／求每个学生的平均分和每门课程的平均分voidPJF(intM，intN，inta[][]){inti，j；floataverage[20]，v[5]；floatsum；for(i=0；i知识点解析：暂无解析七、程序分析题(本题共6题，每题1.0分，共6分。)阅读下列程序，给出运行结果。42、voidmain(){inti，j，x，Y，n，g；voidfun(inti，intj)；i=2；j=3；g=x=5；y=9；n=7；fun(n，6)：printf(“g=％d；i=％d“=％d＼n”，g，i，j)；printf(“x=％d；y=％d＼n”，x，y)；fun(n，6)；}voidfun(inti，intj){intx，y，g；g=8；x=7；y=2：printf(”g=％0d；i=％d“i=％dkn”，g，i，j)；printf(标准答案：g=8；i=7；j=6x=7；y=2g=5；i=2；j=3x=5；y=9g=8；i=7；j=6x=7；y=2知识点解析：暂无解析43、#include“stdio．h”#include“string．h”int*P；main()(intx=1，y=2，z=3：p=&y；fun(x+z，&y)；printf(“(1)％d％d％d＼n”，x，y，*p)；}fun(intx，int*y){intz=4：*p=*y+z：x=*P—z：print”(2)％d％dGdkn”，x，*y，*p)；}标准答案：(1)1；6；6(2)2；6；6知识点解析：第一步：调用fun函数之前，进行了如图所示的操作：全局变量p指向main函数中的局部变量y。第二步：当发生函数调用时，实参向形参传递。这时，新开辟了整型变量x和指向main中的变量y的指针y，显然，它和全局变量p一样指向了同一个单元。fun函数中的x，y和main中的x，y是两个不同的变量，x、y代替fun中的x，y。第三步：执行’fun函数。按顺序先进行两个赋值运算：(1)*p=*y’+z’；(2)x’=*p—z’；这时候，没有改变p的指向，而是改变了p所指向变量y(main中的变量y)的数值，即“*p=*yf+z’；”等价于“y=y+z’；”，故main中的变量y等于6；同时，因为*p的值改变，fun函数的形参x’的值因执行“x’=*p—z’；”语句而变为2。然后接着执行一个打印输出语句”printf(“(2)％d％d％d＼n”，x’，*y’，*p)；”，所以，该步的输出结果应为：(2)266第四步：函数调用结束，返回主调函数。被调用函数中的形参都消失，当然各种指向也消失。输出结果应该为：(1)16644、main(){intk=8：switch(k){case?9：k+=1：case10：k+=1：case11：k+=1；break：default：k+=1：}printf(“％dkn”，k)：}标准答案：9知识点解析：暂无解析45、main(){inta，b，c，d，i，j，k；a=10；b=c=d=5；i=k=0；for(；a>b；++b)i++：while(a>++c)j++；dok++：while(a>d++)；printf(“i：％d，j=％d，k=％d＼n”，i，j，k)；}标准答案：i=5，j=4，k=6知识点解析：暂无解析46、#includevoidmain(){inti，j，row，col，min；inta[3][4]={{1，2，3，4}，{9，8，7，6}，(一1，一2，0，5}}；min=a[0][0]；for(i=0；i<3；i++)for(j=0；j<4；j++)if(a[i][j]标准答案：一221知识点解析：暂无解析47、#include<2stdio．h>main(){chars[20]=“14321645216431”；inti=0，p[6]={0)；while(s[i++])P[SEi]一‘0’一1]++；for(i=0；i<6；i++)printf(“％3d”，p[i])；putchar(‘＼n’)；}标准答案：4；2；2；3；1；2知识点解析：暂无解析山东专升本计算机科学与技术（综合二）模拟试卷第3套一、单项选择题(本题共10题，每题1.0分，共10分。)1、一个栈的输入序列为1，2，3，…，n，若输出序列的第一个元素是n，输出第i(1<=i<=n)个元素是()。A、不确定B、n—i+1C、iD、n—i标准答案：B知识点解析：按照堆栈“后进先出”的特点，n是最后一个入栈的，即n为栈顶元素。若输出的第一个元素为n，则其余所有元素必定仍在堆栈中。第一个输出元素为n，则第二个输出元素为n一1，第i个输出元素为n—i+1，最后一个(第n个)输出元素为1。2、有六个元素按6，5，4，3，2，1的顺序进栈，下列()不是合法的出栈序列?A、543612B、453126C、346521D、234156标准答案：C知识点解析：考查堆栈“后进先出”的特点。对选项A来说，第一个出栈元素是5，因为6先于5进栈，所以必定在5之后出栈，其余的元素出栈顺序任意；对选项B来说，第一个出栈元素是4，所以5和6两个元素必定在4之后依次出栈；对选项C来说，第一个出栈元素是3，则必有4，5，6三个元素依次在3后面出栈，但是选项C中的顺序是3，4，6，5，这是不符合要求的；对选项D来说，第一个出栈元素是2，则必有3，4，5，6依次在2后面出栈，D也是符合要求的，因此答案选C。3、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足()。A、所有的结点均无左孩子B、所有的结点均无右孩子C、只有一个叶子结点D、是任意一棵二叉树标准答案：C知识点解析：前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。4、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为()。A、5B、6C、7D、8标准答案：C知识点解析：n=n0+n1+n2+n3+n4；n=1*4+2*2+3*1+4*1：所以n0=7。5、已知一棵二叉树先序遍历结果为ABDEFG，中序遍历结果为BAEDGF，则后序遍历结果为()。A、BCDEFAB、BFDECAC、BEGFDAD、BEFGDA标准答案：C知识点解析：1)根据前序遍历ABDEFG知，根结点一定是A；根据中序遍历BAEDGF，得：A的左侧全部为左子树结点(B)，A的右侧全部为右子树结点(EDGF)，于是有：因为左子树只有一个结点，故不必再分析，否则将分析左子树。下面直接分析右子树。2)对右子树的所有结点来说，其前序遍历是DEFG，因此右子树的根结点是D；根据中序遍历EDGF，得：D的左侧为E结点(构成D的左子树结点集合)，D的右侧为G、F结点(构成D的右子树结点集合)，于是有：D的左子树只有E，故不必再分析，否则将分析D的左子树。下面直接分析D的右子树。3)对D的右子树的所有结点来说，其前序遍历是FG，因此D的右子树的根结点是F；根据中序遍历GF，得：F得左侧为G结点，右侧无结点。即F只有左子树，没有右子树。于是有：4)对得到的树进行后序遍历，得到BEGFDA。6、由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为()。A、24B、48C、72D、53标准答案：D知识点解析：生成的哈夫曼树如上图所示，路径长度为：3*(2+3)+2*(8+5+6)=53。7、设无向图的顶点个数为n，则该图最多有()条边。A、n一1B、n(n一1)／2C、n(n+1)／2D、0标准答案：B知识点解析：无向图G中边数目的取值范围：0＜=e＜=n(n—1)／2。有n(n一1)／2条边的无向图称为完全图。8、散列表的地址区间为0—17，散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是()。A、8B、9C、10D、11标准答案：D知识点解析：H(26)=26％17=9H(25)=25％17=8H(72)=72％17=4H(38)=38％17=4H(8)=8％17=8H(18)=18％17=1H(59)=59％17=7存储地址为：9、对序列{15，9，7，8，20，一1，4}进行排序，进行一趟后数据的排列变为{4，9，一1，8，20，7，15}；则采用的是()排序。A、选择B、快速C、希尔D、冒泡标准答案：C知识点解析：希尔排序又称缩小增量排序，是一种改进的插入排序，在时间效率上有了较大的改进。对直接插入排序来说，比较的步长为1。这种情况下，如果较小的数在序列的较后面部分，则需要一步一步地向前移动，无疑是比较慢的。如果采用步长＞1的方法，则可以使较小的数向前推进是跳跃式进行，故可以提高排序效率。方法：将整个序列分成若干子序列，对各个子序列进行直接插入排序，得到一趟希尔排序序列；然后缩短步长，重复以上动作，直到步长为1。具体步骤如下：①先取一正整数d(d＜n，一般可取d(=(n／2))，把所有距离为d的倍数的记录编在一组，组成一个子序列，这样将整个待排序序列分成若干组；②在各个子序列中进行直接插入排序；③取一个新的d(比原来的要小，一般取原来的l／2)，重复执行①，②，直到d=1为止(此时，整个序列变成直接插入排序)。10、下列四个序列中，()是堆。A、75，65，30，15，25，45，20，10B、75，65，45，10，30，25，20，15C、75，45，65，30，15，25，20，10D、75，45，65，10，25，30，20，15标准答案：C知识点解析：堆排序是另一种基于选择的排序方法。n个元素的序列{k1，k2，k3，…，kn)，当且仅当满足以下关系时，称之为堆：ki＜=k2i;ki＜=k2i+1或者ki＞=k2i;ki＞=k2i+1其中i=1，2，…，n／2。若将同以上序列对应的一维数组看成是一棵完全二叉树，则堆的含义表明：该完全二叉树的所有非终端结点均不大于(或不小于)其左、右孩子结点的值。由此，若{k1，k2，k3，…，kn)是堆，则堆顶元素(或完全二叉树的根结点)必定是该序列n个元素中的最小值(或者最大值)。若将堆看成是一棵以k1为根的完全二叉树，则这棵完全二叉树中的每个非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此可以看出，若一棵完全二叉树是堆，则根结点一定是这n个结点中的最小者(或最大者)。下面图给出的两个堆的示例。从堆的定义可以看出，若将堆用一棵完全二叉树表示，则根结点是当前堆中所有结点的最小者(或最大者)。堆排序的基本思想是：首先将待排序的记录序列构造一个堆，此时，选出了堆中所有记录的最小者或最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小(或次大)的记录，以此类推，直到堆中只有一个记录为止，每个记录出堆的顺序就是一个有序序列。二、判断题(本题共5题，每题1.0分，共5分。)11、树的子树是无序的。()A、正确B、错误标准答案：B知识点解析：暂无解析12、广义表的表头可以是广义表，也可以是单个元素。()A、正确B、错误标准答案：A知识点解析：暂无解析13、数据对象就是数据元素的集合。()A、正确B、错误标准答案：B知识点解析：这里未强调数据元素的性质相同。14、如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。()A、正确B、错误标准答案：B知识点解析：完全有向图的邻接矩阵是对称矩阵。15、栈与队列是一种特殊操作的线性表。()A、正确B、错误标准答案：A知识点解析：暂无解析三、填空题(本题共3题，每题1.0分，共3分。)16、下列函数的功能是实现带头结点的单链表逆置。voidturn(slink*L)slink*p，*q；p=_________；I一>next=NULL：while(_________){q=p；p=_________；q一>next=L一>next；L一>next=q；}}标准答案：p=L一>nextp!=nullp=p一＞next知识点解析：逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。17、“算法”(Algorithm)就是对求解问题步骤的一种描述，也称为算法设计。它具有五个特征：有穷性，_________，_________，输入和输出。标准答案：确定性可行性知识点解析：暂无解析18、评价算法好坏的五个方面_________，_________，正确性，可读性，健壮性。标准答案：时间效率空间效率知识点解析：暂无解析四、操作计算题(本题共3题，每题1.0分，共3分。)19、设一组记录的关键字按以下次序进行插入：4、5、7、2、1、3、6。要求构造平衡二叉树。标准答案：构造过程为：知识点解析：暂无解析20、非递归遍历求二叉树上的叶子结点个数。标准答案：intCount(BiTreebt)／／非递归遍历求二叉树上的叶子结点个数{intnum=0；BiTrees[]；／／s是栈，栈中元素是二叉树结点指针，栈容量足够大whlie(bt!=null｜｜top>0){while(bt!=null){push(s，bt)．bt=bt一>lchild；)／／沿左分支向下if(!StackEmpty(s)){bt=pop(s)；if(bt一>lchild==null&&bt一>rchild==null)num++；／／叶子结点bt=bt一>rc知识点解析：暂无解析21、在单链表上实现线性表的求表长ListLength(L)运算。标准答案：intListLength(LinkList*L){／／求带头结点的单链表的表长intlen=0：ListList*p；p=L；while(p一>next!=NULL){p=p一>next；len++：}return(1en)：}知识点解析：暂无解析一、单项选择题(本题共10题，每题1.0分，共10分。)22、一个C语言程序是由()。A、一个主程序和若干子程序组成B、函数组成C、若干过程组成D、若干子程序组成标准答案：B知识点解析：C程序由若干程序文件组成，一个程序文件由若干函数构成。23、设有说明语句：charw；intx；floaty；doublez；则表达式w*x+z—y值的数据类型为()。A、floatB、charC、intD、double标准答案：D知识点解析：自动转换发生在不同类型的数据混合运算时，由编译系统自动完成。自动转换遵循以下规则：若参与运算量的类型不同，则先转换成同一类型，然后进行运算。转换按数据长度增加的方向进行，以保证精度不降低。如int型和long型运算时，先把int量转成long型后再进行运算。所有的浮点运算都是以双精度进行的，即使仅含float单精度量运算的表达式，也要先转换成double型，再作运算。char型和short型参与运算时，必须先转换成int型。在赋值运算中，赋值号两边量的数据类型不同时，赋值号右边量的类型将转换为左边量的类型。如果右边量的数据类型长度比左边长时，将丢失一部分数据，这样会降低精度，丢失的部分按四舍五人向前舍入。24、以下能正确地定义整形变量a，b和c并为其赋值为5的语句是()。A、inta—b=c一5B、inta，b，c=5C、inta=5’b=5，c=5D、a=b=c=5标准答案：C知识点解析：在变量说明中，不允许连续给多个变量赋初值。如下说明是错误的：inta=b=c=5：必须写为：inta=5,b=5，c=5；25、为了避免在嵌套的条件语句if一else中产生二义性，C语言规定else子句总是与()配对。A、缩排位置相同的ifB、其之前最近的ifC、其之后最近的ifD、同一行上的if标准答案：A知识点解析：多重if_else嵌套时，else总是与它上面最近的并且未配对过的if配对，即缩排位置相同的if。26、下面有关for循环的正确描述是()。A、for循环只能用于循环次数已经确定的情况B、for循环是先执行循环体语句，后判断表达式C、for循环中，不能用break语句跳出循环体D、for循环的循环体语句中，可包含多条语句，但必须用花括号括起来标准答案：D知识点解析：for循环即可以用于循环次数固定的情况，也可用于循环次数不固定的情况；执行顺序是先判断条件后执行，可以使用break语句退出循环。27、在C语言中，引用数组元素时，其数组下标的数据类型不允许是()。A、整型常量B、整型表达式C、整型常量或整型表达式D、任何类型的表达式标准答案：D知识点解析：数组下标可以是符号常数或常量表达式。28、C语言规定，简单变量作为实参时，它和对应形参之间的数据传递方式是()。A、地址传递B、单向值传递C、双向传递D、由用户指定传递方式标准答案：B知识点解析：数据只能由实参向形参进行传递，即单项传递。29、以下关于编译处理的叙述中错误的是()。A、预处理命令必须以#开始B、一条有效的预处理命令必须单独占据一行C、预处理命令只能位于源程序中所有语句中D、预处理命令不是C语言本身的组成部分标准答案：B知识点解析：预处理命令不是C语句。而预处理命令是由ANsIc统一规定的，它不是c语句本身的组成部分。所以，不能直接对它们进行编译(因为编译程序不能识别它们)，必须在对程序进行通常的编译之前，先对程序中的这些特殊的命令进行预处理。30、若有定义：inta[5]；则a数组中首元素的地址可以表示为()。A、&aB、a+1C、aD、&a[l]标准答案：C知识点解析：数组a的首地址表示方法：&a[0]或a。31、说明一个结构体变量时，系统分配给它的内存是()。A、各成员所需内存量的总和B、结构中第一个成员所需内存量C、成员中占内存量最大者所需的容量D、结构中最后一个成员所需内存量标准答案：A知识点解析：结构体分配的内存空间是所有成员所需空间的总和，而联合体是占内存空间最大的成员的所需容量。三、填空题(本题共4题，每题1.0分，共4分。)32、一个C语言的语句至少应包含一个_______。标准答案：分号知识点解析：暂无解析33、下面程序段的输出结果是_______。intk=10：floata=3．5，b=6．7，C；c===a+k％3*(int)(a+b)％2／4；标准答案：3.5知识点解析：本题考查运算符的优先级概念，式中要先算(a+b)的值，再算强制类型变换*、／、％是同级的，要从左到右计算，最后算加法和赋值。34、“FILE*P”的作用是定义一个_______，其中的“FILE”是在_______头文件中定义的。标准答案：文件指针变量，stdio．h知识点解析：代码“FILE*P”的作用是定义一个文件指针变量，其中的FILE是在标准辎入输出头文件stdio．h中定义的。35、设有char*a=“ABCD”，则printf(“％s”，a)的输出是_______；而printf(“％C”，*a)的输出是_______。标准答案：ABCD。A知识点解析：若给字符指针变量a赋一个字符串常量“ABCD”，实际上是给a赋指向字符串常量首字符’A咱勺指针。程序通过它访问字符串中的各字符。如用代码printf(“％S”a)输出这个字符串常量”ABCD”的字符列ABCD，用代码printf(“％C”，*a)输出a所指的字符A。七、程序填空题(本题共2题，每题1.0分，共2分。)36、根据下式填空，将程序补充完整。已知：程序：main(){floatx，y；scanf(“％f．t，&x)；i(_________)y=一1．0；elseif((______)8L&(x!=1))y=2．0／(x一1．0)；elseif(_______)y=3．0／x；elsey=4．0；printf(“％f／n”，y)；)标准答案：x＜0．0；x＜10．0；x＜20．0知识点解析：本题可根据已知的分段函数式中x与y之间的关系和条件判断语句if的先后顺序，将x的值按从小到大进行判断填空。37、已知有如下计算公式：π≈4*(1／1—1／3+1／5—1／7+……)下列程序就是根据这一公式计算圆周率的。其中，精度控制在0．00001；变量s表示当前符号项，item表示当前项，n表示当前项的序号。阅读程序，并填空。#include“math．h”main(){floatpai=0．0，item=1．0，s=1．0；intn=1：while(_______){pai+=item；S=—S：item=s／(2*n+1)；(_________)；}pai=4*pai；标准答案：fabs(item)＞=0．00001；n+=2知识点解析：暂无解析八、编程题(本题共2题，每题1.0分，共2分。)38、输入一个3×5的整数矩阵，输出其中最大值、最小值和它们的下标。标准答案：#include”stdio．h”main(){inta[3][5]，i，j，t，n=3，m=5，min，max，minrow，mineol，maxrow，maxcol；printf(“Enter％d*％dnumbers!＼n”，