2009年山东专升本（计算机科学与技术综合二）真题试卷
(总分：84.00，做题时间：90分钟)
一、 数据结构(总题数：27，分数：46.00)
1.单项选择题
__________________________________________________________________________________________
解析：
2.一个具有10个顶点的无向完全图应有( )条边。
（分数：2.00）
 A.9
 B.45 √
 C.55
 D.90
解析：解析：无向图G中边数目的取值范围：0＜=e＜=n(n一1)／2。有n(n一1)／2条边的无向图称为完全图。n(n一1)／2=10*9／2=45。
3.长度为n(1…n)的顺序循环队列中，front和rear分别指示队首和队尾，判断队列为满队列的条件是( )。
（分数：2.00）
&ar=front
 B.(rear+1)％n=front √
&ar=0
 D.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.edcba
 B.decba
 C.dceab √
 D.abcde
解析：解析：考查堆栈“后进先出”的特点。对选项C来说，第一个出栈元素是d，则必有c，b，a三个元素依次在3后面出栈，但是选项C中的顺序是dceab，这是不符合要求的因此答案选C。
7.( )又是一棵满二叉树。
（分数：2.00）
 A.二叉排序树
 B.深度为5有31个结点的二叉树 √
二叉树的深度为k C.有15个结点的完全二叉树
 D.哈夫曼(Huffman)树
解析：解析：一棵深度为k，结点个数为2k一1的二叉树称为满二叉树。
8.折半查有序表(2，5，8，20，25，36，40，60)，若查元素60，需依次与表中元素( )进行比较。
（分数：2.00）
 A.20，36，40，60 √
 B.25，40
 C.25，40，60
 D.20，36，40
解析：解析：第一步：设low指向首元素(赋值为1)，high指向尾元素(赋值为8)，计算下边中值得：mid=((10w+high)／2)=4则有 R[mid]=R[4]=20＞60 第二步：由以上判断可知，如果记录中存在60，则一定在R[4]之后(因为R是非递减有序的)。故修改low和high如下：high值不变，仍然有high=8；10w的值修改：使其指向R[4]的后一个元素，即使low=mid+1=5；比较范围缩小至R[5]～R[8]。mid=((10w+high)j2)=6则有R[mid]=R[6]=36＜60 第三步：由以上判断可知．如果记录中存在60，则一定在R[6]之后(同样因为R是非递减有序的)。故修改low和high的值如下：low的值修改，使其指向R[6]的下一个元素，即low=mid+1=7；high不变，仍然是8。mid=((10w+high)／2)=7则有R[mid]=R[7]=40。 第四步：由以上判断可知，如果记录中存在60，则一定在R[7]之后(同样因为R是非递减有序的)。故修改10w和high的值如下：low的值修改，使其指向R[7]的下一个元素，即low=mid+1=8；high不变，仍然是8。mid=((10w+high)／2)=8则有R[mid]=R[8]=60。查成功。
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为增量序列，可有三种取法，对应三种方法：①线性探测再散列：di=1，2，3，…，m一1；(容易产生“二次聚集”)②二次探测再散列：di=12，一12，22，一22，32，一32，…，±k2(k＜=m／2)；③伪随机探测再散列：di=伪随机数序列。(2)再哈希法：Hi=RHi(key)，i=1，2，3，…，kRHi都是不同的哈希函数，即在同义词发生地址冲突时利用另一个哈希函数计算地址，直到冲突不再发生。这种方法不易产生“二次聚集”，
但增加了计算时间。(3)链地址法：将所有关键字为同义词的记录存储在同一线性链表中。(4)建立一个公共溢出区。
10.一个排序算法时间复杂度的大小( )有关。
（分数：2.00）
 A.不与所需移动记录的数目
 B.与该算法的稳定性
 C.与所需比较关键字的次数 √
 D.与所需辅助存储空问的大小
解析：解析：评价排序算法的效率主要有两点：一是在数据量规模一定的条件下，算法执行所消耗的平均时间，对于排序操作，时间主要消耗在关键字之间的比较和数据元素的移动上，因此我们认为，高效率的排序算法应该是尽可能少的比较次数和尽可能少的数据元素移动次数；二是执行算法所需要的辅助存储空间，辅助存储空间是指在数据量规模一定的条件
下，除了存放待排序数据元素占用的存储空间之外，执行算法所需要的其他存储空间，理想的空间效率是算法执行期间所需要的辅助空间与待排序的数据量无关。
11.数据的基本单位是( )。
（分数：2.00）
 A.结点
 B.数据元素 √
 C.数据类型
 D.数据项
解析：解析：数据元素：是数据集合中的一个实体，是计算机程序中加工处理的基本单位。数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所谓数据项就是数据中不可再分割的最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。
12.填空题
__________________________________________________________________________________________
解析：
13.根据数据元素之间关系的不同，数据的逻辑结构划分为 1、 2、 3和 4。
（分数：2.00）
填空项1:__________________ （正确答案：正确答案：集合线性结构 树形结构 图状结构或网状结构）
解析：解析：根据数据元素之间的关系，有四类基本的结构：①集合(元素之间无密切关系)；②线性结构(元素之间有一个对一个的关系(1：1))；③树形结构(元素之间有一个对多个(1：n)的关系；④图状结构或网状结构(元素之间有多个对多个(n：m)的关系)其中数据元素之间的关系如图所示。
14.在线性表的二分查法中要求线性表的存储结构必须是采用 1，且表中的元素必须是 2。
（分数：2.00）
填空项1:__________________ （正确答案：正确答案：顺序关键字有序(升序或降序)排列）
解析：解析：折半查(二分查法)要求查表用顺序存储结构存放且各数据元素按关键字有序(升序或降序)排列，也就是说折半查只适用于对有序顺序表进行查。有序顺序表也称为有序表。
15.栈是一种特殊的线性表，它允许在表的一端进行 1操作，栈中元素的进出原则为 2。
（分数：2.00）
填空项1:__________________ （正确答案：正确答案：插入或删除后进先出）
解析：解析：堆栈是一种特殊的线性表，它的操作被限制在某一端，即栈顶。若有一个栈S=(a1，a2，…，an)称a1为栈底结点，an为栈顶结点。习惯上称插入结点为人栈(压栈，进栈)，删除结点成为出栈(弹栈)。最先进栈的结点必定最后出栈，最后进栈的结点必定最先出栈，因此，栈是一种具有后进先出特性的数据结构。
16.深度为k的二叉树其结点数最多有 1个结点。
（分数：2.00）
填空项1:__________________ （正确答案：正确答案：2k—1）
解析：解析：深度为k的二叉树至多有2k一1(k>=1)个结点。证明：从第1层到第k层，二叉树每层的最大结点数分别为：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）
填空项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)(2)而分支是由度为1的结点和度为2的结点贡献的：每个度为1的结点贡献1个分支，每个度为2的结点贡献2个分支。则有：B=n1×1+n2×2=n1+2n2(3)由(2)、(3)得n=n1+2n2+1(4)由(1)、(4)得n0=n2+1由此得出结论：二叉树叶子结点个数总是比度为2的结点个数多1。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。