数据结构与算法考试试卷

1、第第 页共9页】【第4页共9页】【第4页共9页】江西财经大学第学期期末考试试卷试卷代码：授课课时：课程名称：数据结构与算法适用对象：本科一、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共24分。）1算.法分析的目的是分析算法的效率以求改进，算法分析的两个主要方面是_。_空间复杂度和时间复杂度正确性和简单性可读性和文档性数据复杂性和程序复杂性2向.量第一个元素的存储地址是10，0每个元素的长度为2，则第5个元素的地址是栈.结构通常采用的两种存储结构是_。_线性存储结构和链表存储结构散列方式和索引方式链表存储结构和

2、数组线性存储结构和非线性存储结构一.个队列的入队序列是1、2、3、4，则队列输出序列是_。_A、.3、42、1、2、B3.、14、4、C3.、12、2、4D、.1判断一个循环队列最多元素为为满队列的条件是。在一个单链表中，若删除所指结点的后续结点，则执行设两个字符串和，求在中首次出现的位置的运算称作。连接模式匹配求子串求串长某二叉树的前序遍历结点访问顺序是，中序遍历结点访问顺序是则其后序遍历结点访问顺序是_。_深.度为5的二叉树至多有_个_结_点。0具.有4个顶点的无向完全图有_条_边_。1对.线性表进行二分查找时，要求线性表必须_。_以顺序方式存储以顺序方式存储，且结点按关键字有序排列以链接

3、方式存储以链接方式存储，且结点按关键字有序排列2排.序方法中，从未排序序列中依次取出元素与已排序序列（注：初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为_。_希尔排序起泡排序插入排序选择排序二、填空题（请在每小题的横线上填入正确内容，每空1分，共7分。）TOC o 1-5 h z在图形结构中，每个结点的前驱结点个数和后续结点个数可以。两个串相等的充分必要条件是。在双链表中，每个结点有两个指针域，一个指向，另一个指向在一棵二叉树中，度为零的结点的个数为，度为的结点的个数为，则有在各种查找方法中，平均查找长度与结点个数无关的查找方法是。已知模式串=其用法求得的每个字符对应

4、的函数值为。三、简答题（本大题共3小题，每小题5分，共15分）1简在述栈的特点以及栈与一般线性表的区别。，简在述什么是内部排序，什么是外部排序。3什在么是满二叉树？什么是完全二叉树？满二叉树和完全二叉树有何关系？四、判断题本大题共10小题，命题正确的在题后括号内写“T”,错误的在题后括号内写“F”,每小题1分，共10分1在数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的（。），在线性表的逻辑顺序与物理顺序总是一致的（。）深度为的非空二叉树的第层最多有个结点4线在性表的顺序存储结构特点是逻辑关系上相邻的两个元素在物理位置上也相邻。（5在最优二叉搜索树一定是平衡的二叉搜索树。（）

5、6任在何无环的有向图，其结点都可以排在一个拓扑序列里。（）7在关键活动不按期完成就会影响整个工程的完成时间。（）8在若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。（）9快在速排序是对起泡排序的一种改进。（）1，邻在接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（）五、分析应用题（本题共26分，1、4小题各6分，2、3小题各7分）设有对堆栈操作的算法：（判断栈空）、（压栈）、（出栈）,请仔细阅读下面算法，指出其功能。（分）将在下面的森林变换成二叉树（7分）。设记录的关键字集合，请“除留余数法”设计一合适的哈希函数，在01的2散列地址空间填入各关键字，解决冲突的方法为“二次探测再散列”，画出散列表，并计算等概率情况下的。（分）设待排序的排序码序列为画出用堆排序排序方法得到的初始堆及前两次输出堆顶元素后，每次堆的调整变化结果。（分）六、算法设计题（本题共18分，第1小题10分，第2小题8分）设有一个表头指针为的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有