2010年山东专升本（计算机科学与技术综合二）真题试卷
(总分：70.00，做题时间：90分钟)
一、 数据结构(总题数：21，分数：34.00)
1.单项选择题
__________________________________________________________________________________________
解析：
2.以下数据结构中哪一个是线性结构( )。
（分数：2.00）
 A.栈 √
 B.线索二叉树
 C.AOV网
 D.二叉排序树
解析：解析：线性表、堆栈、队列都可认为是线性结构。线索二叉树、二叉排序树是树状结构，AOV网属于图状结构。
3.若有a，b，c三个字符的字符序列执行入栈操作，则其所有可能的输出排列共有( )。
（分数：2.00）
 A.4种
 B.5种 √
 C.6种
 D.其他
解析：解析：a，b，c三个字符的字符序列为abc，acb，bca,bac，cba，共5种可能。
4.一棵树的广义表表示为a(b，c(e，f(g))，d)，当用左孩子一右兄弟链表表示时，右指针域非
空的节点个数为( )。
（分数：2.00）
 A.1
 B.2
 C.3 √
 D.4
解析：解析：孩子兄弟表示法：用二叉链表作为树的存储结构，链表结点的两个指针域意义发生变化。原左子树指针域指向当前结点的第一个孩子结点，原右子树指针指向当前结点的第一个兄弟结点。从另一个角度出发，当前结点的左子树的右子树，实际上是当前结点的其他孩子结点。
5.下面关于图的存储的叙述中正确的是( )。
（分数：2.00）
 A.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关
二叉树中序遍历非递归算法
 B.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
 C.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
 D.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 √
解析：解析：邻接矩阵法是图的一种顺序存储结构。设G有n个顶点，则可用n*n矩阵A(称为G的邻接矩阵，行标从1…n，列标从1…n)保存该有向图。邻接表法是图的链式存储方法，类似于树的孩子表示法。针对图中的每个顶点(设v)都建立一个单链表，单链表中的结点表示依附于当前顶点v的所有的边(对有向图来说则是以v为弧尾的弧)。每个结点(称为表结点)有三个域构成：邻接点域(adjvex)表示与顶点v邻接的点在图中的位置，链域指示下一条边或弧的结点，数据域存储和边或弧相联系的其他信息(如权值等)。
6.对长度为12的有序表采用顺序存储结构，折半查技术，在等概率情况下，查成功的平均查长度是( )。
（分数：2.00）
 A.13850 √
 B.62／13
 C.18233
 D.其他
解析：解析：折半查生成一棵二叉树，如图所示，所以平均查长度为(1+2*2+3*4+A*5)／12=37／12.
7.判断题
__________________________________________________________________________________________
解析：
8.算法的执行时间和所需的存储空间都是问题规模的函数，进行算法分析就是要出这种函数关系。( )
（分数：2.00）
 A.正确
 B.错误 √
解析：解析：算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。
9.完全二叉树只能采用顺序存储方法，不能采用链表存储方法。( )
（分数：2.00）
 A.正确
 B.错误 √
解析：解析：二叉树既可以采用顺序存储方法，也可以采用二叉链表或三叉链表法进行存储。
10.在顺序循环队列的第i个元素之后插入一个元素是顺序循环队列的基本运算。( )
（分数：2.00）
 A.正确
 B.错误 √
解析：解析：队列是一种特殊类型的线性表，按照先进先出的原则对其中的元素进行操作。排在队首的先出队，后面的元素依次前移。进入队列必须在队尾进行，删除必须在队首进行。
11.若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历的最后一个结点。( )
（分数：2.00）
 A.正确
 B.错误 √
解析：
12.直接插入排序的关键码比较次数与初始排列有关。( )
（分数：2.00）
 A.正确 √
 B.错误
解析：解析：直接插入排序基本操作为：将一个记录插入到一个已经排好序的有序表中，从而得到一个新的、长度增1的有序表。
13.算法设计题
__________________________________________________________________________________________
解析：
14.已知顺序栈S，简述f1函数功能，当输入80时，输出结果是多少?fl( ){initstack(s)；scanf(“％d”，&n)；while(n){push(s，n ％8)；n=n／8)}while(!Emptystcak(s)){pop(S，x)；printf(“％d”，x)；)}
（分数：2.00）
__________________________________________________________________________________________
正确答案：(正确答案：把十进制整型数转化为8进制数。当输入80时，输出结果是：120。)
解析：
15.写出二叉树前序遍历非递归算法的设计思想，然后写出算法。
（分数：2.00）
__________________________________________________________________________________________
正确答案：(正确答案：void PreOrderUnrec(Bitree*t) { Stack s： StackInit(s)； Bitree*p=t； while(p!=NULL｜｜!StackEmpty(s)) { while(p!=NULL)／／遍历左子树 { visite(p一＞data)； push(s，p)； p=p一＞lchild； } if(!StackEmpty(s))／／通过下一次循环中的内嵌while实现右子树遍历 { p=pop(s)； p=p一＞rchild； }／／endit }／／endw)
解析：
16.写出直接插入排序算法。
（分数：2.00）
__________________________________________________________________________________________
正确答案：(正确答案：直接插入排序的基本思想：依次将记录序列中的每一个记录插入到有序段中，使有序段的长度不断地扩大。其具体的排序过程可以描述如下：首先将待排序记录序列中的第一个记录作为一个有序段，将记录序列中的第二个记录插入到上述有序段中形成由两个记录组成的有序段，再将记录序列中的第三个记录插入到这个有序段中，形成由三个记录组成的有序段，……依此类推，每一趟都是将一个记录插入到前面的有序段中，假设当前欲处理第i个记录，则应该将这个记录插入到由前i一1个记录组成的有序段中，从而形成一个由i个记录组成的按关键字值排列的有序序列，直到所有记录都插入到有序段中。一共需要经过n一1趟就可以将初始序列的n个记录重新排列成按关键字值大小排列的有序序列。算法为： void insertSort(DataType a，int n) for(i=2；i＜=n；i++)／／需要n一1趟 { a[0]=a[i]；／／将a[i]赋予监视哨 j=i一1； while(a[0]．key＜a[j]．key)／／搜索插入位置 {a[j+1]=a[j]； j=j一1； a[j+1]=a[0]；／／将原a[i]中的记录放入第j+1个位置 } })
解析：
17.应用题
__________________________________________________________________________________________
解析：
18.已知一棵三叉树的存储结构如下表所示，其中root=0，n=7。画出该二叉树。
（分数：2.00）
__________________________________________________________________________________________
正确答案：(正确答案：)
解析：
19.用克鲁斯卡尔算法求下图的最小生成树。
（分数：2.00）
__________________________________________________________________________________________
正确答案：(正确答案：)
解析：
20.下图是一棵二叉排序树，规定当二叉排序树被删除的结点既有左子树，又有右子树时，以其中序前驱替代。画出删除55后的二叉排序树。
（分数：2.00）
__________________________________________________________________________________________
正确答案：(正确答案：中序遍历序列为：10，20，30，35，40，55，60，80，85，99。删除55后，40成为根结点，画出的二叉排序树如下：)
解析：
21.已知散列表地址空间为HT[0．．8]，散列函数为H(key)=key％7，采用线性探测法处理冲突，将数据序列{107，27，28，42，3，25，99，38}依次存入散列表中。试画出相应的散列表；并计算等概率下搜索成功的平均搜索长度。散列表及其查各关键字要比较的次数如下所示：搜索成功的平均搜索长度为：ASL=
（分数：2.00）
__________________________________________________________________________________________
正确答案：(正确答案：搜索成功的平均搜索长度为：ASL=10／8=1．25)
解析：
二、 C语言(总题数：22，分数：36.00)
22.单项选择题
__________________________________________________________________________________________
解析：
23.在C语言中，合法的字符常量是( )
（分数：2.00）
 A.‘＼084’
 B.‘＼x43’ √
 C.‘ab’
 D.“＼0”
解析：解析：字符常量是用单引号括起来的一个字符。例如‘a’，‘b’，‘A’，‘+’‘?’嘟是合法字符常量。在C语言中，字符常量有以下特点：a)字符常量只能用单引号括起来，不能用双引号或其他括号；b)字符常量只能是单个字符，不能是字符串；c)字符可以是字符集中任意字符。但数字被定义为字符型之后就不再是原来的数值了。如‘5’和5是不同的量。‘5’是字符常量，5是整型常量。
24.在C语言中，要求运算数必须是整型的运算符是( )。
（分数：2.00）
 A.／
 B.++
 C.!=
 D.％ √
解析：解析：使用求余运算符(模运算符)“％”时，要求参与运算的变量必须均为整型，其结果值为两数相除所得的余数。一般情况下，所得的余数与被除数符号相同。
25.有整型变量X，单精度变量y=5．5，表达式：x=float(Y*3+((int)y％4))执行后，x的值为( )。
（分数：2.00）
 A.17
 B.17.5 √
 C.18
 D.16
解析：解析：(int)y把y的值强制转化为整型，然后进行％运算。
26.若从键盘上输入5，则程序的输出结果是( )。 #include void main( ) {int x；scanf(“％d”，&x)； if(x十+>5)printf(“％d＼n”，x)?； else printf(“％d＼n”，x一一)； }
（分数：2.00）

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