大工13春《数据结构》模拟试卷A答案
机密★启用前大连理工大学网络教育学院
2013年9月份《数据结构》课程考试
模 拟 试 卷
考试形式：闭卷 试卷类型：（A）
☆ 注意事项： 1、本考卷满分共：100分；考试时间：90分钟。
2、所有试题必须答到试卷答题纸上，答到试卷上无效。
3、考试结束后，考生须将试卷和试卷答题纸一并交回。
学习中心______________ 姓名____________ 学号____________
一、单项选择题（本大题共10小题，每小题3分，共30分）
1、在表长为n的顺序表中,若在每个位置插入数据元素的概率相等，插入一个数据元素平均需要移动（ ）个数据元素。
A．(n-1)/2
B．n/2
C．n-1
D．n
2、线性表采用顺序存储结构时，其地址（ ）。
A．必须是连续的
B．部分地址必须是连续的
C．一定是不连续的
D．连续与否均可以
3、队列操作的原则是（ ）。
A．先进先出
B．后进先出
C．只能插入
D．只能删除
4、一个顺序栈S，元素a，b，c，d，e依次进栈，如果5个元素的出栈顺序为b，e，d，c，a，则顺序栈的容量至少应为（ ）。
A．2
B．3
C．4
D．5
5、广义表((e))的表头是（ ）。
A．e
B．(e)
C．( )
D．((e))
6、按照二叉树的定义，具有3个结点二叉树有（ ）种不同形态。
A．3
B．4
C．5
D．6
7、一棵二叉树的结点个数为60，则它的最小高度为（ ）。
A．5
B．6
C．7
D．8
8、具有6个顶点9条边的有向图中，所有顶点的出度之和等于（ ）。
A．6
B．9
C．12
D．18
9、具有10个顶点的简单无向图最多可包含（ ）条边。
A．7
B．8
C．45
D．90
10、对数据元素按从小到大次序进行排序。如果待排序的数据元素的初始状态是按从小到大次序排列,用下列（ ）方法进行排序速度最慢。
A．快速排序
B．堆排序
C．直接插入排序
D．起泡排序
二、判断题（本大题共10小题，每小题3分，共30分）
1、算法分析的两个主要方面为空间复杂度和时间复杂度。（ ）
A．正确
B．错误
2、顺序表的长度是表中的数据元素个数。（ ）
A．正确
B．错误
3、在栈中，出栈操作的时间复杂度为O(n)。（ ）
A．正确
B．错误
4、栈和队列的共同特点是先进先出。（ ）
A．正确
B．错误
5、中缀表达式A-(B+C/D)*E的后缀形式是ABCD/+E*-。（ ）
A．正确
B．错误
6、具有5个顶点的无向图至少应有4条边才能确保是一个连通图。（ ）
A．正确
B．错误
7、在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为2e。（ ）
A．正确
B．错误
8、difference(A,B,C)表示求集合A和B的差集C。（ ）
A．正确
B．错误
9、快速排序是稳定的排序方法。（ ）
A．正确
B．错误
10、堆是完全二叉树。（ ）
A．正确
B．错误
三、填空题（本大题共5个空，每空3分，共15分）
1、用顺序存储结构存放的线性表称做 。
2、对于顺序存储的栈，因为栈的空间是有限的，在进行 运算时，可能发生上溢出。
3、n个顶点的有向完全图具有 条弧。
4、在树结构里，有且仅有一个结点没有前驱，称为 。
5、若将8阶下三角矩阵A中下三角元素按行优先顺序压缩存储于一维数组sa中,则m等于 。
四、简答题（本大题共3小题，每小题5分，共15分）
1、写出下图所示二叉树的前序、中序及后序遍历序列。
2、下面列举的是常用的排序方法：直接插入排序、二分插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序、二路归并排序。试问哪些排序方法是稳定的？哪种排序占用的辅助空间最大？
3、若串s="software"，其子串的数目是多少？给出分析计算过程。
五、算法题（本大题1小题，共10分）
1、已知二叉树中的结点类型用BtreeNode表示，被定义为：
struct BtreeNode
{
char data;
struct BtreeNode *left;
struct BtreeNode *right;
};
其中data为结点值域，left和right分别为指向左、右孩子结点的指针域，根据下面函数声明编写求一棵二叉树高度的算法，该高度由函数返回。假定根结点的层次为1，参数BT初始指向这棵二叉树的根结点。int BTreeDepth(BtreeNode *BT)；
机密★启用前
大连理工大学网络教育学院
2013年9月份《数据结构》课程考试 模拟试卷答案
考试形式：闭卷 试卷类型：A
一、单项选择题（本大题共10小题，每小题3分，共30分）
1、B 2、A 3、A 4、C 5、B
6、C 7、B 8、B 9、C 10、A
二、判断题（本大题共10小题，每小题3分，共30分）
1、A 2、A 3、B 4、B 5、A
6、A 7、A 8、A 9、B 10、A
三、填空题（本大题共5个空，每空3分，共15分）
1、顺序表 2、进栈 3、n*(n-1) 4、根 5、36
四、简答题（本大题共3小题，每小题5分，共15分）
1、答：
该二叉树的前序序列为：CABEFDHG(2分)
该二叉树的中序序列为：BAFECHDG(2分)
该二叉树的后序序列为：BFEAHGDC(1分)
2、答：
稳定的排序方法有：直接插入排序、二分插入排序、起泡排序、二路归并排序。（3分）
占用辅助空间最大的排序是：二路归并排序。（2分）
3、答：分析计算过程：
串s中共有8个字符，一个字符的子串有8个，两个字符的子串有7个，三个字符的子串有6个，四个字符的子串有5个，五个字符的子串有4个，六个字符的子串有3个，七个字符的子串有2个，八个字符的子串有1个，另有一个空串（4分）。因此，子串的数目为： 8+7+6+5+4+3+2+1+1=37（1分）
五、算法题（本大题1小题，共10分）
1、（程序中变量名称定义，及实现过程可能不统一，请酌情给分。）
int BTreeDepth(BtreeNode *BT)//求由BT指针指向一棵二叉树的高度
{
if(BT == Null)
return 0;//对于空树返回高度为0
else
{
int dep1=BTreeDepth(BT->left); //计算左子树的高度
int dep2=BTreeDepth(BT->right);//计算右子树的高度
if(dep1>dep2)
return dep1+1;
else
return dep2+1;
}
}
页:
[1]