【学历类职业资格】2009年山东专升本（计算机科学与技术综合二）真题试卷及答案解析.doc

1、2009 年山东专升本（计算机科学与技术综合二）真题试卷及答案解析(总分：84.00，做题时间：90 分钟)一、数据结构(总题数：27，分数：46.00)1.单项选择题_2.一个具有 10 个顶点的无向完全图应有( )条边。（分数：2.00）A.9B.45C.55D.903.长度为 n(1n)的顺序循环队列中，front 和 rear 分别指示队首和队尾，判断队列为满队列的条件是( )。（分数：2.00）A.rear=frontB.(rear+1)n=frontC.rear=0D.front=04.由( )组成的集合是一个数据对象。（分数：2.00）A.不同类型的数据项B.不同类型的数据元素C

2、.相同类型的数据项D.相同类型的数据元素5.( )是表示线性数据结构的。（分数：2.00）A.循环链表B.邻接多重表C.孩子链表D.单链表6.设一个栈的入栈元素序列为 a，b，c，d，e，则不可得到出栈的元素序列有( )。（分数：2.00）A.edcbaB.decbaC.dceabD.abcde7.( )又是一棵满二叉树。（分数：2.00）A.二叉排序树B.深度为 5 有 31 个结点的二叉树C.有 15 个结点的完全二叉树D.哈夫曼(Huffman)树8.折半查找有序表(2，5，8，20，25，36，40，60)，若查找元素 60，需依次与表中元素( )进行比较。（分数：2.00）A.20，

3、36，40，60B.25，40C.25，40，60D.20，36，409.查找哈希(Hash)表，解决冲突的方法有( )。（分数：2.00）A.链地址法B.线性探测再散列法C.直接地址法D.除留余数法10.一个排序算法时间复杂度的大小( )有关。（分数：2.00）A.不与所需移动记录的数目B.与该算法的稳定性C.与所需比较关键字的次数D.与所需辅助存储空问的大小11.数据的基本单位是( )。（分数：2.00）A.结点B.数据元素C.数据类型D.数据项12.填空题_13.根据数据元素之间关系的不同，数据的逻辑结构划分为 1、 2、 3 和 4。（分数：2.00）填空项 1:_14.在线性表的二分

4、查找法中要求线性表的存储结构必须是采用 1，且表中的元素必须是 2。（分数：2.00）填空项 1:_15.栈是一种特殊的线性表，它允许在表的一端进行 1 操作，栈中元素的进出原则为 2。（分数：2.00）填空项 1:_16.深度为 k 的二叉树其结点数最多有 1 个结点。（分数：2.00）填空项 1:_17.通常像交通、道路问题的数学模型是一种称为 1 的数据结构。（分数：2.00）填空项 1:_18.算法的五个重要的特征是 1、 2、 3、 4 和 5。（分数：2.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_19.两个字符串相等的充分必要条件是 1。（分数：2

5、.00）填空项 1:_20.在一棵二叉树中，度为零的结点个数为 n 0 ，度为 2 的结点个数为 n 2 ，则有 n 0 1。（分数：2.00）填空项 1:_21.树的度是指 1 的最大值。（分数：2.00）填空项 1:_22.在一个有向图中，某个结点的度是指该结点的 1 和 2 之和。（分数：2.00）填空项 1:_填空项 1:_23.操作计算题_24.将下面的一个普通书转换成一棵二叉树，并写出它先序、中序、后序三种遍历的遍历序列。（分数：2.00）_25.用克鲁斯卡尔算法将下面的图构造成最小生成树，画出生成过程。 （分数：2.00）_26.应用题_27.已知 S 为顺序栈，写出 S 的存储

6、结构类型描述。编写算法实现将元素 x 入栈操作 Push(S，x)，人栈成功返回 1，否则返回 0 和删除栈顶元素的出栈操作 Pop(S)出栈成功返回 1，否则返回 0。（分数：2.00）_二、C 语言(总题数：23，分数：38.00)28.填空题_29.若 a 是 int 型变量，且 a=5，则下面表达式的值为： 1。(a+100)2+a2（分数：2.00）填空项 1:_30.C 语言程序中引用标准输入输出库函数，必须在每个源文件的首部写下#include。（分数：2.00）填空项 1:_31.若 int 型变量占内存 2 个字节、double 型变量占内存 8 个字节，有如下定义：unio

7、n dataint i；double d；a；则变量 a 在内存中所占字节数为： 1。（分数：2.00）填空项 1:_32.当文件关闭成功后，fclose 函数的返回值为： 1。（分数：2.00）填空项 1:_33.程序填空题_34.将下面折半查找算法补充完整。算法说明：已知 r1n是 n 个记录的递增有序表，用折半查找法查找关键字为 k 的记录，若查找失败返回零；否则返回该记录的序号值。查找表顺序存储结构定义如下：#define MAXSIZE 100typedef structkeytype key；Nodetype；typedef Nodetype SqlistMAXSIZE；算法(C

8、函数)：int binsearch(Sqlist r，datatype k，int n)int low=1，high=（分数：2.00）_35.将下面单链表的插入算法补充完整。算法说明：在带有头结点的单链线性表中第 i 个位置之前插入元素 x：typedefDataType data；struct node*next；LNode，*LinkList：lnt listinsert(LinkList head，int i，DataType x)LinkList P=headSint j=0；while(p!=NULL&j_36.下面程序的运行结果是_。 #incl ude main( ) int

9、i=2，j=3，k； k=i+j； int k=8： if(i=3) printf(“d”，k)； else printf(“d”，j)； printf(“dd”，i，k)； （分数：2.00）_37.下面程序的运行结果是_。 #include #define SIZE 8 main( ) char s=”GDBFHACE”； int i，j，t； for(i=0；isEj) t=si； seri=sj； sj=t； for(i=0；i_38.下面程序的运行结果是_。 #include int fun(int a，int b，int*cn，int*dn) *en=a*a+b*b： *dn=a*

10、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)： （分数：2.00）_39.下面程序的运行结果是_。 #include int fun(int x) static y=2； y+； x+=y： return x； void main( ) int k； k=fun(3)； printf(“d，dn”，k，fun(k)； （分数：2.00）_40.下面程序的运行结果是_。 #include main( ) int S=0，m； for(m=7；m=3；m

11、 一一) 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)： （分数：2.00）_41.编程改错题_42.(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 one of the biggest c

12、ity”，a)； (12)retllrn； (13) (14)p20 (15) (16)printf(“in the wor（分数：2.00）_43.求 （分数：2.00）_44.本程序能够在屏幕中央显示出如下图形。 （分数：2.00）_45.程序分析题_46.下面程序的功能是找出 100 至 200 之间不能被 3 整除但能被 5 整除的数。#includestdioh(int m；for(m=100；m=200；m+)if(_)printf(“dt”，m)；（分数：2.00）_47.下面程序通过指向整型变量的指针将数组 m43的内容按 4 行 3 列的格式输出，请给 printf( )填入

13、适当的参数，使之通过指针 p 将数组元素按要求输出。 #include int m43=1，2，3，4，5，6)，7，8，9)，10，1l，12； int i，j，*P=m； for(i=0；i_48.下面程序能够完成交换数组 a 和数组 b 中的对应元素的功能。#includestdiohswap(int*p1，int*p2)int temp； main( )int a5=1，3，5，7，9)，int b5=2，4，6，8，10。int i；for(i=0；i5；i+)swap(&ai，&bi；for(i=0；i5；i+)printf(“a96d=d”，i，ai)；print(“n”)；fo

14、r(i=0；i5；（分数：2.00）_49.在某大学举行的演讲比赛中，有十个评委为参赛的选手打分，分数为 0100 分。选手最后得分为：去掉一个最高分和一个最低分后，其余八个分数的平均值。#includestdiohmain( )int max，min，score，i；int SLIm=0；max=0；min=100；for(i=0；i_50.把指针 str 所指的字符串按相反的顺序赋给 rev。#includestdiohmajn( )char*str=“abcdefg”；char rev10；int i；printf(“n”)；for(i=0；i_2009 年山东专升本（计算机科学与技术综

15、合二）真题试卷答案解析(总分：84.00，做题时间：90 分钟)一、数据结构(总题数：27，分数：46.00)1.单项选择题_解析：2.一个具有 10 个顶点的无向完全图应有( )条边。（分数：2.00）A.9B.45 C.55D.90解析：解析：无向图 G 中边数目的取值范围：0=e=n(n 一 1)2。有 n(n 一 1)2 条边的无向图称为完全图。n(n 一 1)2=10*92=45。3.长度为 n(1n)的顺序循环队列中，front 和 rear 分别指示队首和队尾，判断队列为满队列的条件是( )。（分数：2.00）A.rear=frontB.(rear+1)n=front C.rea

16、r=0D.front=0解析：4.由( )组成的集合是一个数据对象。（分数：2.00）A.不同类型的数据项B.不同类型的数据元素C.相同类型的数据项D.相同类型的数据元素 解析：解析：线性表是由相同类型的结点组成的有限序列。如：由 n 个结点组成的(a1，a2，an)a1是最前结点，an 是最后结点。结点也称为数据元素或者记录。5.( )是表示线性数据结构的。（分数：2.00）A.循环链表B.邻接多重表C.孩子链表D.单链表 解析：解析：线性表、堆栈、队列都可认为是线性结构。6.设一个栈的入栈元素序列为 a，b，c，d，e，则不可得到出栈的元素序列有( )。（分数：2.00）A.edcbaB.

17、decbaC.dceab D.abcde解析：解析：考查堆栈“后进先出”的特点。对选项 C 来说，第一个出栈元素是 d，则必有 c，b，a 三个元素依次在 3 后面出栈，但是选项 C 中的顺序是 dceab，这是不符合要求的因此答案选 C。7.( )又是一棵满二叉树。（分数：2.00）A.二叉排序树B.深度为 5 有 31 个结点的二叉树 C.有 15 个结点的完全二叉树D.哈夫曼(Huffman)树解析：解析：一棵深度为 k，结点个数为 2k 一 1 的二叉树称为满二叉树。8.折半查找有序表(2，5，8，20，25，36，40，60)，若查找元素 60，需依次与表中元素( )进行比较。（分数

18、：2.00）A.20，36，40，60 B.25，40C.25，40，60D.20，36，40解析：解析：第一步：9.查找哈希(Hash)表，解决冲突的方法有( )。（分数：2.00）A.链地址法 B.线性探测再散列法C.直接地址法D.除留余数法解析：解析：处理冲突的方法(1)开放定址法：从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生了冲突的待插入元素存到该单元中。重新确定地址的方法为：Hi=(H(key)+di)m i=1，2，k (k=m 一 1)其中：H(key)为哈希函数；m 为哈希表的长度；di 为增量序列，可有三种取法，对应三种方法：线性探测再

19、散列：di=1，2，3，m 一 1；(容易产生“二次聚集”)二次探测再散列：di=12，一 12，22，一 22，32，一 32，k2(k=m2)；伪随机探测再散列：di=伪随机数序列。(2)再哈希法：Hi=RHi(key)，i=1，2，3，kRHi 都是不同的哈希函数，即在同义词发生地址冲突时利用另一个哈希函数计算地址，直到冲突不再发生。这种方法不易产生“二次聚集”，但增加了计算时间。(3)链地址法：将所有关键字为同义词的记录存储在同一线性链表中。(4)建立一个公共溢出区。10.一个排序算法时间复杂度的大小( )有关。（分数：2.00）A.不与所需移动记录的数目B.与该算法的稳定性C.与所需

20、比较关键字的次数 D.与所需辅助存储空问的大小解析：解析：评价排序算法的效率主要有两点：一是在数据量规模一定的条件下，算法执行所消耗的平均时间，对于排序操作，时间主要消耗在关键字之间的比较和数据元素的移动上，因此我们认为，高效率的排序算法应该是尽可能少的比较次数和尽可能少的数据元素移动次数；二是执行算法所需要的辅助存储空间，辅助存储空间是指在数据量规模一定的条件下，除了存放待排序数据元素占用的存储空间之外，执行算法所需要的其他存储空间，理想的空间效率是算法执行期间所需要的辅助空间与待排序的数据量无关。11.数据的基本单位是( )。（分数：2.00）A.结点B.数据元素 C.数据类型D.数据项解

21、析：解析：数据元素：是数据集合中的一个实体，是计算机程序中加工处理的基本单位。数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所谓数据项就是数据中不可再分割的最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。12.填空题_解析：13.根据数据元素之间关系的不同，数据的逻辑结构划分为 1、 2、 3 和 4。（分数：2.00）填空项 1:_ （正确答案：正确答案：集合线性结构 树形结构 图状结构或网状结构）解析：解析：根据数据元素之间的关系，有四类基本的结构：集合(元素之间无密切关系)；线性结构(元素之间有一个对一个的关系(1：1)

22、；树形结构(元素之间有一个对多个(1：n)的关系；图状结构或网状结构(元素之间有多个对多个(n：m)的关系)其中数据元素之间的关系如图所示。14.在线性表的二分查找法中要求线性表的存储结构必须是采用 1，且表中的元素必须是 2。（分数：2.00）填空项 1:_ （正确答案：正确答案：顺序关键字有序(升序或降序)排列）解析：解析：折半查找(二分查找法)要求查找表用顺序存储结构存放且各数据元素按关键字有序(升序或降序)排列，也就是说折半查找只适用于对有序顺序表进行查找。有序顺序表也称为有序表。15.栈是一种特殊的线性表，它允许在表的一端进行 1 操作，栈中元素的进出原则为 2。（分数：2.00）填

23、空项 1:_ （正确答案：正确答案：插入或删除后进先出）解析：解析：堆栈是一种特殊的线性表，它的操作被限制在某一端，即栈顶。若有一个栈S=(a1，a2，an)称 a1 为栈底结点，an 为栈顶结点。习惯上称插入结点为人栈(压栈，进栈)，删除结点成为出栈(弹栈)。最先进栈的结点必定最后出栈，最后进栈的结点必定最先出栈，因此，栈是一种具有后进先出特性的数据结构。16.深度为 k 的二叉树其结点数最多有 1 个结点。（分数：2.00）填空项 1:_ （正确答案：正确答案：2k1）解析：解析：深度为 k 的二叉树至多有 2k 一 1(k=1)个结点。证明：从第 1 层到第 k 层，二叉树每层的最大结点

24、数分别为：1、2、22、23、2k 一 1，该数列为等比数列，第一项为 a1=1，公比 q=2，项数为k，利用等比数列求和公式得：17.通常像交通、道路问题的数学模型是一种称为 1 的数据结构。（分数：2.00）填空项 1:_ （正确答案：正确答案：图状或网状）解析：18.算法的五个重要的特征是 1、 2、 3、 4 和 5。（分数：2.00）填空项 1:_ （正确答案：正确答案：有穷性）填空项 1:_ （正确答案：确定性）填空项 1:_ （正确答案：可行性）填空项 1:_ （正确答案：输入）填空项 1:_ （正确答案：输出）解析：19.两个字符串相等的充分必要条件是 1。（分数：2.00）填

25、空项 1:_ （正确答案：正确答案：两个串的长度相等，并且各个对应位置的字符都相等）解析：20.在一棵二叉树中，度为零的结点个数为 n 0 ，度为 2 的结点个数为 n 2 ，则有 n 0 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：n2+1）解析：解析：假设二叉树中度为 1 的结点个数为 n1，结点总数为 n。因为二叉树中任何结点的度最大不超过 2，因此有：n=n0+n1+n2(1)从另一个角度看，我们来研究二叉树的分支数。对所有结点来说，除了根结点，任何其余结点都有一个分支进入(指向)。不妨设 B(Branch)为二叉树的分支数，则有：B=n 一 1(分支数比结点数少 1)

26、(2)而分支是由度为 1 的结点和度为 2 的结点贡献的：每个度为 1 的结点贡献 1 个分支，每个度为 2 的结点贡献 2 个分支。则有：B=n11+n22=n1+2n2(3)由(2)、(3)得 n=n1+2n2+1(4)由(1)、(4)得 n0=n2+1 由此得出结论：二叉树叶子结点个数总是比度为 2 的结点个数多 1。21.树的度是指 1 的最大值。（分数：2.00）填空项 1:_ （正确答案：正确答案：树中所有结点度）解析：22.在一个有向图中，某个结点的度是指该结点的 1 和 2 之和。（分数：2.00）填空项 1:_ （正确答案：正确答案：出度）填空项 1:_ （正确答案：入度）解

27、析：23.操作计算题_解析：24.将下面的一个普通书转换成一棵二叉树，并写出它先序、中序、后序三种遍历的遍历序列。（分数：2.00）_正确答案：(正确答案：(1)转换后的二叉树： )解析：25.用克鲁斯卡尔算法将下面的图构造成最小生成树，画出生成过程。 （分数：2.00）_正确答案：(正确答案： )解析：26.应用题_解析：27.已知 S 为顺序栈，写出 S 的存储结构类型描述。编写算法实现将元素 x 入栈操作 Push(S，x)，人栈成功返回 1，否则返回 0 和删除栈顶元素的出栈操作 Pop(S)出栈成功返回 1，否则返回 0。（分数：2.00）_正确答案：(正确答案：define MAX

28、_STACK 10栈的最大数据元素数目 typedef struet stack StackEntry 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 一itemS-top 一一；

29、 return flag； )解析：二、C 语言(总题数：23，分数：38.00)28.填空题_解析：29.若 a 是 int 型变量，且 a=5，则下面表达式的值为： 1。(a+100)2+a2（分数：2.00）填空项 1:_ （正确答案：正确答案：3）解析：解析：a=5，(a+100)2=1，a2=2，所以结果为 3。30.C 语言程序中引用标准输入输出库函数，必须在每个源文件的首部写下#include。（分数：2.00）填空项 1:_ （正确答案：正确答案：stdio h）解析：解析：C 语言本身没有输入输出语句，scanf 函数和 printf 函数是标准输入输出库函数，其头文件为 s

30、tdioh。31.若 int 型变量占内存 2 个字节、double 型变量占内存 8 个字节，有如下定义：union dataint i；double d；a；则变量 a 在内存中所占字节数为： 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：8）解析：解析：一个联合体变量所占内存长度等于其所有成员中最长的成员的长度，所有成员共用一段内存单元。32.当文件关闭成功后，fclose 函数的返回值为： 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：0）解析：解析：文件使用完毕后必须关闭，以避免数据丢失。用 fclose 函数关闭文件。fclose 函数也带回一个值，当顺

31、利地执行了关闭操作，则返回值为 0；如果返回值为非零值，则表示关闭时有错误。33.程序填空题_解析：34.将下面折半查找算法补充完整。算法说明：已知 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=（分数：2

32、.00）_正确答案：(正确答案：10w=high mid=(10w+high)2；return mid；high=mid 一 1；low=mid+1；)解析：解析：折半查找的基本思想是：首先以整个查找表作为查找范围，用查找条件中给定值 k 与中间位置结点的关键字比较，若相等，则查找成功；否则，根据比较结果缩小查找范围，如果 k 的值小于关键字的值，根据查找表的有序性可知查找的数据元素只有可能在表的前半部分，即在左半部分子表中，所以继续对左子表进行折半查找；若 k 的值大于中间结点的关键字值，则可以判定查找的数据元素只有可能在表的后半部分，即在半部分子表中，所以应该继续对右子表进行折半查找。每进

33、行一次折半查找，要么查成功，结束查找，要么将查找范围缩小一半，如此重复，直到查找成功或查找范围缩小空即查找失败为止。35.将下面单链表的插入算法补充完整。算法说明：在带有头结点的单链线性表中第 i 个位置之前插入元素 x：typedefDataType data；struct node*next；LNode，*LinkList：lnt listinsert(LinkList head，int i，DataType x)LinkList P=headSint j=0；while(p!=NULL&j_正确答案：(正确答案：struet LNode P=P 一next(LinkList)snext=

34、P 一next P 一nE=S：)解析：36.下面程序的运行结果是_。 #incl ude main( ) int i=2，j=3，k； k=i+j； int k=8： if(i=3) printf(“d”，k)； else printf(“d”，j)； printf(“dd”，i，k)； （分数：2.00）_正确答案：(正确答案：835)解析：解析：本题注意两点：第一，int k=8；k 为局部变量，只在大括号中有效；第二，if(i=3)此语句恒成立。37.下面程序的运行结果是_。 #include #define SIZE 8 main( ) char s=”GDBFHACE”； int i，j，t； for(i=0；isEj) t=si； seri=sj； sj=t； for(i=0；i_正确答案：(正确答案：ABCDEFGH)解析：解析：此题的目的是按照字母从小到大进行排序。38.下面程序的运行结果是_。 #include int 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)： （分数：2.00）_