江西财经大学数据结构A罗翠兰.docx

江西财经大学现代经济管理学院2013-2014学年第一学期期末考试试卷试卷代码：A卷课时：80课程名称：数据结构适用对象：12计算机、12信管试卷命题人：罗翠兰试卷审核人：曾日波一、选择题（每小题2分，共28分）1.数据结构被形式地定义为（D,S）,其中D是的有限集，S是D上的关系有限集。A.算法B.数据元素C.数据操作D.逻辑结构2 .在数据结构中，从逻辑上可以把数据结构分成oA.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构3 .以下的叙述中，正确的是oA.线性表的存储结构优于链式存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出4 .若一个栈的入栈序列是1、2、3、n,其输出序列为pl、P2、p3、pn,若pl=n,则Pi为。A.iB.n=iC.n-i+1D.不确定5 .判断一个循环队列QU（最多元素为m）为空的条件是oA.QU->front-QU->rearB.QU->front!=QU->rearC.QU->front=（QU->rear+l）%mD.QU->front!=（QU->rear+l）%m6.在某单链表中，已知p所指结点不是最后结点，在p之后插入S所指结点，则执行oA.s->next=p;p->next=s;B.s->next-p->next;p->next=s;C.s->next=p->next;p=s;D.p->next=s;s->next-p;7 .串是一种特殊的线性表，其特殊性体现在oA.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符8 .已知某完全二叉树深度为k,则该树的结点数至少有一个。A.2kB.k2C.2klD.2k9 .对于一个满二叉树，In个树叶，n个结点，深度为h,则oA.n=h+mB.h+m=2nC.m=h-lD.n=2h-110 .一个有n个顶点的无向图最多有条边。A.nB.n（n-l）C.n（n-l）2D.2n11 .顺序查找法适合于存储结构为的线性表。A.散列存储B.顺序存储或链接存储C.压缩存储D.索引存储12 .在待排序的元素序列基本有序的前提下，效率最高的排序方法是oA.插入排序B.选择排序C.快速排序D.归并排序13 .设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为OA.第i行非0元素的个数之和B.第i列非0元素的个数之和C.第i行0元素的个数之和D.第i列0元素的个数之和14 .设某无向图中有n个顶点e条边，则该无向图中所有顶点的度之和为oA.nB.eC.2nD.2e二、判断题（共8分）1 .数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的（）02 .线性表的逻辑顺序与物理顺序总是一致的（）。3 .线性表的顺序存储结构特点是逻辑关系上相邻的两个元素在物理位置上也相邻。（）4 .最优二叉搜索树一定是平衡的二叉搜索树。（）5 .任何无环的有向图，其结点都可以排在一个拓扑序列里。（）6 .关键活动不按期完成就会影响整个工程的完成时间。（）7 .快速排序是对起泡排序的一种改进。（）8 .邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（）三、简答题（每小题6分，共12分）1 .说明线性表、栈与队列的异同点。2 .简述什么是稳定排序，什么是不稳定排序。四、分析应用题（每小题IO分，共40分）1 .给定二叉树的两种遍历序列，分别是：前序遍历序列：Dacebhfgi,中序遍历序列：Dcbehagif,试画出该二叉树，并确定其后序遍历序列。请完成下列操作：画出该二叉树的树形表示；写出按后序遍历该二叉树所得到的节点序列；画出该二叉树的中序线索树。2 .无向带权图如下图所示，画出该图的邻接矩阵，并按克鲁斯卡尔算法求其最小生成树。3 .设关键字序列是(12,25,45,63,17,03,78,31),哈希表长度是11,哈希函数是H(kcy)=kcyMOD11,采用开放地址法的线性探测方法解决冲突，构造该关键字序列的哈希表。求出在等概率情况下，该方法的查找成功的平均查找长度ASL4.设待排序的排序码序列为12,2,16,30,28,10,16*,20,6,18,画出用堆排序排序方法得到的初始堆及前两次输出堆顶元素后，每次堆的调整变化结果。(10分)五、算法设计题(每小题6分，共12分)1.设计判断单链表中元素是否是递增的算法。2.以二叉链表为存储结构，写出求二叉树的叶子结点总数的算法。