1、2009 年山东专升本（计算机科学与技术综合二）真题试卷及答案与解析单项选择题1 一个具有 10 个顶点的无向完全图应有( )条边。（A）9（B） 45（C） 55（D）902 长度为 n(1n)的顺序循环队列中，front 和 rear 分别指示队首和队尾，判断队列为满队列的条件是( ) 。（A）rear=front（B） (rear+1)n=front（C） rear=0 （D）front=03 由( )组成的集合是一个数据对象。（A）不同类型的数据项（B）不同类型的数据元素（C）相同类型的数据项（D）相同类型的数据元素4 ( )是表示线性数据结构的。（A）循环链表（B）邻接多重表（C）孩
2、子链表（D）单链表5 设一个栈的入栈元素序列为 a，b，c ，d，e，则不可得到出栈的元素序列有( )。（A）edcba（B） decba（C） dceab （D）abcde6 ( )又是一棵满二叉树。（A）二叉排序树（B）深度为 5 有 31 个结点的二叉树（C）有 15 个结点的完全二叉树（D）哈夫曼(Huffman) 树7 折半查找有序表(2，5，8，20，25，36，40，60)，若查找元素 60，需依次与表中元素( ) 进行比较。（A）20，36，40，60（B） 25，40（C） 25，40，60（D）20，36，408 查找哈希(Hash)表，解决冲突的方法有 ( )。（A）链地
3、址法（B）线性探测再散列法（C）直接地址法（D）除留余数法9 一个排序算法时间复杂度的大小( )有关。（A）不与所需移动记录的数目（B）与该算法的稳定性（C）与所需比较关键字的次数（D）与所需辅助存储空问的大小10 数据的基本单位是( )。（A）结点（B）数据元素（C）数据类型（D）数据项填空题11 根据数据元素之间关系的不同，数据的逻辑结构划分为_、_、_和_。12 在线性表的二分查找法中要求线性表的存储结构必须是采用_，且表中的元素必须是_。13 栈是一种特殊的线性表，它允许在表的一端进行_操作，栈中元素的进出原则为_。14 深度为 k 的二叉树其结点数最多有_个结点。15 通常像交通、道
4、路问题的数学模型是一种称为_的数据结构。16 算法的五个重要的特征是_、_、_、_和_。17 两个字符串相等的充分必要条件是_。18 在一棵二叉树中，度为零的结点个数为 n0，度为 2 的结点个数为 n2，则有n0_。19 树的度是指_的最大值。20 在一个有向图中，某个结点的度是指该结点的_和_之和。操作计算题21 将下面的一个普通书转换成一棵二叉树，并写出它先序、中序、后序三种遍历的遍历序列。 转换后的二叉树：先序遍历序列：中序遍历序列：后序遍历序列：22 用克鲁斯卡尔算法将下面的图构造成最小生成树，画出生成过程。应用题23 已知 S 为顺序栈，写出 S 的存储结构类型描述。编写算法实现将
5、元素 x 入栈操作 Push(S，x)，人栈成功返回 1，否则返回 0 和删除栈顶元素的出栈操作 Pop(S)出栈成功返回 1，否则返回 0。填空题24 若 a 是 int 型变量，且 a=5，则下面表达式的值为：_。(a+100)2+a225 C 语言程序中引用标准输入输出库函数，必须在每个源文件的首部写下#include。26 若 int 型变量占内存 2 个字节、double 型变量占内存 8 个字节，有如下定义：union dataint i；double d；a；则变量 a 在内存中所占字节数为：_。27 当文件关闭成功后，fclose 函数的返回值为：_ 。程序填空题28 将下面折
6、半查找算法补充完整。算法说明：已知 r1n是 n 个记录的递增有序表，用折半查找法查找关键字为 k的记录，若查找失败返回零；否则返回该记录的序号值。查找表顺序存储结构定义如下：#define MAXSIZE 100typedef structkeytype key；Nodetype；typedef Nodetype SqlistMAXSIZE；算法(C 函数)：int binsearch(Sqlist r，datatype k，int n)int low=1，high=29 将下面单链表的插入算法补充完整。算法说明：在带有头结点的单链线性表中第 i 个位置之前插入元素 x：typedefDat
7、aType data；struct node*next；LNode，*LinkList：lnt listinsert(LinkList head，int i，DataType x)LinkList P=headSint j=0；while(p!=NULL&jmain( )int i=2，j=3，k；k=i+j；int k=8：if(i=3)printf(“d”，k)；elseprintf(“d”，j)；printf(“d d”，i，k)；31 下面程序的运行结果是_。#include#define SIZE 8main( )char s=”GDBFHACE”；int i，j ，t；for(i=
8、0；isEj)t=si；seri=sj；sj=t；for(i=0；iint fun(int a，int b，int*cn，int*dn)*en=a*a+b*b：*dn=a*ab*b：a=5：b=6：main( )int a=4，b=3，c=5，d=6：fun(a，b，&c，&d)；printf(“a=d ，b= d，c=d，d= dn”，a，b，c，d)：33 下面程序的运行结果是_。#includeint fun(int x)static y=2；y+；x+=y：return x；void main( )int k；k=fun(3)；printf(“d， dn”，k，fun(k) ；34 下
9、面程序的运行结果是_。#includemain( )int S=0，m；for(m=7；m=3；m 一一)switch(m)case 1：case 4：case 7： s+；break；case 2：case 3：case 6： s+=2：case 5： s+=3；break；printf(“s=dn”，S)：编程改错题35 (1)#include(2)char a=“Beijing”；(3)main( )(4)(5)printf(“s is one city in China.n”，a)；(6)pl( )；(7)p2( )；(8)(9)pl( )(10)(11)printf(“s is on
10、e of the biggest city”，a) ；(12)retllrn；(13)(14)p20(15)(16)printf(“in the wor36 求 (1)#include(2)inaiin( )(3)(4)int n1=100，n2=50，n3=10；(5)int k；(6)float s1：0，s2=0，s3=0 ；(7)for(k=1；k37 本程序能够在屏幕中央显示出如下图形。 (1)#include(2)void main( )(3) (4)int i，j，k；(5)for(i=1；i程序分析题38 下面程序的功能是找出 100 至 200 之间不能被 3 整除但能被 5
11、 整除的数。#includestdioh(int m；for(m=100；m =200；m+)if(_)printf(“d t”，m)；39 下面程序通过指向整型变量的指针将数组 m43的内容按 4 行 3 列的格式输出，请给 printf( )填入适当的参数，使之通过指针 p 将数组元素按要求输出。#includeint m43=1，2，3 ， 4，5，6)，7，8，9)， 10，1l ，12；int i，j ，*P=m；for(i=0；iswap(int*p1， int*p2)int temp；main( )int a5=1，3，5，7，9)，int b5=2，4，6，8，10。int i
12、；for(i=0；imain( )int max，min，score，i；int SLIm=0；max=0；min=100；for(i=0；imajn( )char*str=“abcdefg”；char rev10；int i；printf(“n”) ；for(i=0；i60 第二步：由以上判断可知，如果记录中存在 60，则一定在 R4之后(因为 R 是非递减有序的)。故修改 low 和 high如下：high 值不变，仍然有 high=8；10w 的值修改：使其指向 R4的后一个元素，即使 low=mid+1=5；比较范围缩小至 R5R8。 mid=(10w+high)j2)=6 则有Rmi
13、d=R6=368 【正确答案】 A【试题解析】 处理冲突的方法(1)开放定址法：从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生了冲突的待插入元素存到该单元中。重新确定地址的方法为：Hi=(H(key)+di) m i=1，2，k (k=1)个结点。证明：从第 1 层到第 k 层，二叉树每层的最大结点数分别为：1、2、22、23、2k 一 1，该数列为等比数列，第一项为 a1=1，公比 q=2，项数为 k，利用等比数列求和公式得：15 【正确答案】 图状或网状16 【正确答案】 有穷性；确定性；可行性；输入；输出17 【正确答案】 两个串的长度相等，并且各个
14、对应位置的字符都相等18 【正确答案】 n2+1【试题解析】 假设二叉树中度为 1 的结点个数为 n1，结点总数为 n。因为二叉树中任何结点的度最大不超过 2，因此有：n=n0+n1+n2(1)从另一个角度看，我们来研究二叉树的分支数。对所有结点来说，除了根结点，任何其余结点都有一个分支进入(指向 )。不妨设 B(Branch)为二叉树的分支数，则有：B=n 一 1(分支数比结点数少 1)(2)而分支是由度为 1 的结点和度为 2 的结点贡献的：每个度为 1 的结点贡献 1 个分支，每个度为 2 的结点贡献 2 个分支。则有：B=n11+n22=n1+2n2(3)由(2)、(3)得 n=n1+
15、2n2+1(4)由(1)、(4) 得 n0=n2+1 由此得出结论：二叉树叶子结点个数总是比度为 2 的结点个数多 1。19 【正确答案】 树中所有结点度20 【正确答案】 出度 入度操作计算题21 【正确答案】 (1)转换后的二叉树： (2)先序遍历序列：A B C D F E G H I J K L M(3)中序遍历序列：C F D E B J I L K M H G A(4)后序遍历序列：F E D C J M L K I H G B A22 【正确答案】 应用题23 【正确答案】 define MAX_STACK 10栈的最大数据元素数目typedef struet stackStac
16、kEntry itemMAX_STACK；存放栈中数据元素的存储单元int top； 栈顶指针STACK：入栈Int Push(STACK*S，StackEntry x)flag=1；if(S 一to=MAXSTACK 一 1)flag=0；else s 一item-+s 一top=x：return flag；出栈void Pop(STACK*S)flag=1：StackEntry x：if(StackEmpty(*S)flag=0；else x=s 一itemStop 一一；return flag；填空题24 【正确答案】 3【试题解析】 a=5，(a+100)2=1，a2=2，所以结果为
17、3。25 【正确答案】 stdio h【试题解析】 C 语言本身没有输入输出语句，scanf 函数和 printf 函数是标准输入输出库函数，其头文件为 stdioh 。26 【正确答案】 8【试题解析】 一个联合体变量所占内存长度等于其所有成员中最长的成员的长度，所有成员共用一段内存单元。27 【正确答案】 0【试题解析】 文件使用完毕后必须关闭，以避免数据丢失。用 fclose 函数关闭文件。fclose 函数也带回一个值，当顺利地执行了关闭操作，则返回值为 0；如果返回值为非零值，则表示关闭时有错误。程序填空题28 【正确答案】 10wnext(LinkList)snext=P 一nex
18、t P 一nE=S：30 【正确答案】 835【试题解析】 本题注意两点：第一，int k=8 ；k 为局部变量，只在大括号中有效；第二，if(i=3)此语句恒成立。31 【正确答案】 ABCDEFGH【试题解析】 此题的目的是按照字母从小到大进行排序。32 【正确答案】 a=4，b=3，C=25，d=7【试题解析】 a，b 为局部变量，只在定义处发挥作用。C ，d 由于交换的是地址所以其值发生改变。33 【正确答案】 6，10【试题解析】 y 是 static 型变量，可以保存上一次运算的结果。34 【正确答案】 s=15【试题解析】 break 语句其执行过程是：终止对 switch 语句
19、或循环语句的执行，即跳出这两种语句，而转入下一语句执行。此题中 break 语句跳出 switch 语句，继续执行 for 循环。编程改错题35 【正确答案】 错误的行是：(2)改为：char*a=“Beijing”：【试题解析】 如果 a 为字符型变量只能存储一个字符，而字符指针才可以存储一个字符串。36 【正确答案】 错误的行是：(12)改为：s3=s3+10k：【试题解析】 求 1k 的和，要注意必须是 10k ，因为 k 是整数。37 【正确答案】 错误的行是：(9)改为：for(j=1；j=72*(i 一 1)；j+)；【试题解析】 #的个数分别为 7，5，3，1 个。程序分析题38
20、 【正确答案】 m3 !=0 m5=039 【正确答案】 *(*(p+i)+j)【试题解析】 指针变量 P 指向包含 4 个整型的一维数组，若将二维数组名 m 赋给 P，P+i 表示第 i 行首地址，*(p+i)表示第 i 行第 0 列元素的地址，此时将行指针转换成列指针，*(p+i)+j 表示第 i 行第 j 行元素的地址，而*(*(p+i)+j) 代表第 i 行第j 列元素的值。40 【正确答案】 temp=*pl ；*p1=*p2；*p2=temp?；【试题解析】 函数完成了地址的交换。41 【正确答案】 (summaxmin)8【试题解析】 sum 表示 10 个评委的打分，max、rain 分别表示 10 个分数中的最高分、最低分。42 【正确答案】 reviii=*(str+6 一 i)：【试题解析】 str 表示字符串的首地址，str+6 i 表示依次从字符串的后边取字符。
