1、山东专升本计算机科学与技术（综合二）模拟试卷 3 及答案与解析判断题1 数据元素是数据的最小单位。( )（A）正确（B）错误2 顺序存储结构的主要缺点是不利于插入或删除操作。( )（A）正确（B）错误3 两个栈共用静态存储空间，对头使用也存在空间溢出问题。( )（A）正确（B）错误4 数组是同类型值的集合。( )（A）正确（B）错误5 对于有 N 个结点的二叉树，其高度为 log2n。( )（A）正确（B）错误6 强连通图的各顶点间均可达。( )（A）正确（B）错误7 查找相同结点的效率折半查找总比顺序查找高。( )（A）正确（B）错误8 在初始数据表已经有序时，快速排序算法的时间复杂度为 O
2、(nog2n)。( )（A）正确（B）错误9 (101，88，46，70，34，39，45，58，66，10)是堆。( )（A）正确（B）错误10 最小代价生成树是唯一的。( )（A）正确（B）错误填空题11 下面是对不带头结点的单链表进行就地逆置的算法，该算法用 L 返回逆置后的链表的头指针，试在空缺处填入适当的语句。void reverse(1inklist&L)p=null；q=L；while(q!=null)_；q-next=p；p=q；_；_；void reverse(1inklist&L)12 设有一个空栈，栈顶指针为 1000H(十六进制)，现有输入序列为1，2，3，4，5，经过
3、 PUSH，PUSH ，POP，PUSH，POP，PUSH，PUSH 之后，输出序列是_，而栈顶指针值是_H。13 设字符串 S1=“ABCDEF”，S2=”PQRS” ，则运算S=CONCAT(SUB(S1，2，LEN(S2)，SUB(S1，LEN(s2)，2)后的串值为_。14 从有序表(12，18，30，43，56，78，82，95)中分别折半查找 43 和 56 元素时，其比较次数分别为_和_。15 假定一组记录为(46，79，56，38，40，84)，在冒泡排序的过程中进行第一趟排序后的结果为_。简答题16 已知二叉树，请给出它的 3 种遍历序列。先序：中序：后序：17 简述数据结构
4、的概念?在讨论数据结构时，一般会从哪三个方面进行?操作计算题17 对有五个结点A，B，C ，D，E的图的邻接矩阵：18 画出逻辑图。19 基于邻接矩阵写出图的深度、广度优先遍历序列。20 计算图的关键路径。算法设计题21 给定二叉树，采用链式结构存储，编写算法 void count(BitTree bt)，实现功能：统计二叉树中度为 1 的结点数目。应用题21 设矩阵 A 为22 若将 A 视为对称矩阵，画出对其压缩存储的存储表。23 若将 A 视为稀疏矩阵，画出 A 的十字链表结构。24 有向图的邻接表存储如下：(1)画出其邻接矩阵存储，(2)写出图的所有强连通分量。(3)写出顶点 a 到顶
5、点 i 的全部简单路径。单项选择题25 C 语言程序的执行，总是起始于( )。（A）程序中的第一条可执行语句（B）程序中的第一个函数（C） main 函数（D）包含文件中的第一个函数26 以下程序运行后，输出结果是( )。main( )char*S=“abcde”：s+=2：printf(“ld n”，s)；（A）cde（B）字符 c 的 ASC码值（C）字符 C 的地址（D）出错27 下面程序运行结果为( )。main( )char c=a：if(a(2)main( )(3)(4)char C；(5)c=getchar( )；(6)c=(c=一 Acnext 暂存后继(2)q=L待逆置结点(
6、3)L=p头指针仍为 L12 【正确答案】 23 100CH13 【正确答案】 BCDEDE14 【正确答案】 1315 【正确答案】 (46，56，38，40，79，84)简答题16 【正确答案】 先序：D E F C G D H 中序：F E B G C H D 后序：F E G H D C B17 【正确答案】 数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。或者说，数据结构是相互之间存在一种或多种特定逻辑关系的数据元素的集合。数据元素之间的相互关系称为结构(Structure)。讨论数据结构时，一般会从逻辑结构、存储结构、数据操作三个方面
7、进行。操作计算题18 【正确答案】 如下图所示19 【正确答案】 深度优先遍历序列：ABCDE；广度优先遍历序列： ABCED。20 【正确答案】 所以，关键路径 AB(长 100)。算法设计题21 【正确答案】 void count(BitTree bt)int i=0：if(bt=NULL)break；else if(bt 一lchild=0&bt 一rchild!=0bt 一Ichild!=0bt 一rchild=0)i+：elsei+=count(btlchild)：i+=count(btrchild)：printf(“d”，i)：应用题22 【正确答案】 将对称矩阵对角线及以下元素按
8、行序存入一维数组中，结果如下：23 【正确答案】 因行列表头的“行列域” 值用了 0 和 0，下面十字链表中行和列下标均从 1 开始。24 【正确答案】 (1) (2)强连通分量：(a)，(d)，(h)。(3)顶点 a 到顶点 i 的简单路径： (abei)，(acgi)，(acbei)单项选择题25 【正确答案】 C【试题解析】 在一个 C 语言源程序中，无论 main 函数书写在程序的前部，还是后部，程序的执行总是从 main 函数开始，并且在 main 函数中结束。本题正确答案为 C。26 【正确答案】 C【试题解析】 char*s=“abcde”，声明 s 是一个字符串指针，并且将字符数组“abcde”的首地址赋值给了 s，s+=2 ，即是在原来的 s 地址上向前推进两个字节，又因为数组是在连续空间上存储的一组数据，且一个字符占一个字节，那么也就等价于由数组的第一个字节地址推进到第三个字符的地址，即字符 c 的地址。答案为C。27 【正确答案】 A【试题解析】 关系运算符“一A c=Z)?c+32：c；41 【正确答案】 错误的行是：(8)改为：if(d 2=0)42 【正确答案】 错误的行是：(6)改为：for(i=0；stri；i+)43 【正确答案】 错误的行是：(22)改为：if(!flag2)
