大工13春《数据结构》模拟试卷B答案
机密★启用前大连理工大学网络教育学院
2013年9月份《数据结构》课程考试 模拟试卷答案
考试形式：闭卷 试卷类型：B
一、单项选择题（本大题共10小题，每小题3分，共30分）
1、C 2、D 3、C 4、C 5、D
6、A 7、C 8、B 9、C 10、D
二、判断题（本大题共10小题，每小题3分，共30分）
1、A 2、B 3、A 4、A 5、A
6、B 7、A 8、A 9、B 10、A
三、填空题（本大题共5个空，每空3分，共15分）
1、1、2、3、4 2、n(n-1)/2 3、n-1 4、稀疏 5、O(n2)
四、简答题（本大题共3小题，每小题5分，共15分）
1、答：二叉树如下图所示。（3分）
后序遍历的结点序列为：DCBGFEA（2分）
2、答：
如果待排序的文件中，存在多个排序码相等的记录，用某种方法进行排序后，这些记录的相对次序仍然保持不变，则称这种排序方法是“稳定的”。（3分）
例：12，11，18，15，11，经过快速排序后得到的序列为11，11，12，15，18。
其中11与11的次序与原记录的次序不相同，所以快速排序是不稳定的排序。（2分）
3、答：全部的输出序列为：
ABC, ACB, BAC, BCA, CBA（每个1分）
五、算法题（本大题1小题，共10分）
1、（程序中变量名称定义，及实现过程可能不统一，请酌情给分。）
int compare(char *s, char *t)
{
int m,n,i;
m=length(s);
n=length(t);
if(m!=n)
return 0;
for(i=0; i<m; i++)
if(s!=t)
return 0;
return 1;
}
机密★启用前
大连理工大学网络教育学院
2013年9月份《数据结构》课程考试
模 拟 试 卷
考试形式：闭卷 试卷类型：（B）
☆ 注意事项： 1、本考卷满分共：100分；考试时间：90分钟。
2、所有试题必须答到试卷答题纸上，答到试卷上无效。
3、考试结束后，考生须将试卷和试卷答题纸一并交回。
学习中心______________ 姓名____________ 学号____________
一、单项选择题（本大题共10小题，每小题3分，共30分）
1、在表长为n的顺序表中第i（1≤i≤n）个数据元素之前插入一个新的数据元素需要移动（ ）个数据元素。
A．i
B．n-i
C．n-i+1
D．n-i-1
2、设有四个元素A，B，C，D 顺序进栈（进栈的过程中允许出栈），则不可能的出栈序列是（ ）。
A．ABCD
B．DCBA
C．ACDB
D．DABC
3、（ ）又称作先进先出表。
A．栈
B．堆
C．队列
D．数组
4、带表头结点单循环链表h为空表的判断条件是（ ）。
A．h==NULL
B．h->link==NULL
C．h->link==h
D．h!=NULL
5、若一棵完全二叉树中某结点无左孩子，则该结点一定是（ ）。
A．度为1的结点
B．度为2的结点
C．分支结点
D．叶子结点
6、若一个串非空，子串的定位操作通常称为（ ）。
A．串的模式匹配
B．原串的子串
C．串的长度
D．串的连接
7、设用二叉链表存储具有8个结点的二叉树，则二叉链表中空链域的个数是（ ）。
A．7
B．8
C．9
D．0
8、高度为10的二叉树中只有度为0和度为2的结点，则此二叉树中所含结点总数至少为（ ）。
A．18
B．19
C．20
D．21
9、二分法查找要求线性表一定是（ ）。
A．顺序存储的无序表
B．链式存储的无序表
C．顺序存储的有序表
D．链式存储的有序表
10、用直接插入排序方法对下面四个序列进行从小到大排序，元素比较次数最少的是（ ）。
A．90,69,80,46,21,40
B．40,21,46,69,90,80
C．90,80,69,46,40,21
D．21,40,46,69,80,90
二、判断题（本大题共10小题，每小题3分，共30分）
1、顺序表中存取每一个元素的时间相同。（ ）
A．正确
B．错误
2、插入和删除只能在表的一端进行的线性表，称为队列。（ ）
A．正确
B．错误
3、若n阶方阵的对角线右上方的元素均等于零，称为下三角矩阵。（ ）
A．正确
B．错误
4、4个元素按a,b,c,d顺序连续进入队列，队头的元素是a。（ ）
A．正确
B．错误
5、设树根为第1层，在一棵二叉树上第5层的结点数最多为16。（ ）
A．正确
B．错误
6、遍历一棵具有n个结点的二叉树，在先序序列、中序序列和后序序列中所有叶子结点的相对次序都不相同。（ ）
A．正确
B．错误
7、index(s,t)表示子串定位运算。若串t是串s的子串，则函数返回值是串t在串s中第一次出现的开始位置，否则返回值是0。（ ）
A．正确
B．错误
8、具有n个顶点的无向图至少应有n-1条边才能确保是一个连通图。（ ）
A．正确
B．错误
9、直接插入排序是不稳定的排序法。（ ）
A．正确
B．错误
10、交换排序的基本思想是两两比较待排序记录的排序码，并交换不满足顺序要求的那些偶对，直到全部满足顺序要求为止。（ ）
A．正确
B．错误
三、填空题（本大题共5个空，每空3分，共15分）
1、一个队列的入队序列是1、2、3、4，则队列的输出序列是 。
2、在有n个结点的无向图中，其边数最多为 。
3、对n个元素的序列进行起泡排序时，最少的比较次数是 。
4、数组的三元组存储是对 矩阵的压缩存储。
5、一个算法的时间复杂度为（n2+2nlog2n），其数量级表示为 。
四、简答题（本大题共3小题，每小题5分，共15分）
1、已知一棵二叉树的前序遍历的结点序列为ABCDEFG，中序遍历的结点序列为BDCAGFE，试画出这棵二叉树，并写出后序遍历时得到的结点序列。
2、什么样的排序方法是“稳定的”？举例说明为什么快速排序是“不稳定的”。
3、对于一个栈，给出输入序列A,B,C,试给出全部可能的输出序列。
五、算法题（本大题1小题，共10分）
1、编写程序实现字符串的比较函数：int compare(char *s, char *t)；若串s等于串t函数返回值为1，否则函数返回值为0。
页:
[1]