合肥学院期末考试卷及答案

合肥学院至学年第学期数据结构与算法设计课程考试卷系级专业学号姓名题号一二三四五六七八九十总分得分阅卷一选择题分分栈和队列的共同特点是只允许在端点处插入和删除元素都是先进后出都是先进先出没有共同点以下数据结构中哪一个是非线性结构队列栈线性表二叉树下面程序的时间复杂为在一个单链表中已知结点是结点的前趋结点若在和之间插入结点则须执行设一组初始记录关键字序列为则以第一个记录关键字为基准而得到一趟快速排序的结果是设一个有序的单链表中有个结点现要求插入一个新结点后使得单链表仍然保持有序则该操作的时间复杂度为设有个结点的无向图该图至少应有条边才能确保是一个连通图设连通图中的边集则从顶点出发可以得到一种深度优先遍历的顶点序列为设散列表长散列函数已知表中已有个结点其他地址为空如用二次探测再散列处理冲突关键字为的结点地址是设用邻接矩阵表示有向图的存储结构则有向图中顶点的入度为第行非元素的个数之和第列非元素的个数之和第行元素的个数之和第列元素的个数之和设指针变量指向当前链式栈的栈顶则删除栈顶元素的操作序列为大题得分装订线命题教师胡春玲共页第页二叉树的第层的结点数最多为设有向无环图中的有向边集合则下列属于该有向图的一种拓扑排序序列的是设有一组初始记录关键字序列为则由这组记录关键字生成的二叉排序树的深度为图的深度优先遍历类似于二叉树的先序遍历中序遍历后序遍历层次遍历二填空题分分设顺序线性表中有个数据元素则在第个位置上插入一个数据元素需要移动表中数据元素个数是设指针变量指向单链表中结点指针变量指向被插入的新结点则在后进行插入操作的语句序列为设结点的指针域为设有一组初始关键字序列为则第趟直接插入排序结束后的结果的是设某无向图中有个顶点用邻接矩阵作为该图的存储结构则顶点和顶点互为邻接点的条件是设二叉排序树的高度为则在该树中查找关键字最多需要比较次设一组初始记录关键字序列是小根堆则对而言满足的条件为且下面程序段的功能是实现二分查找算法请在下划线处填上正确的语句若要对某二叉排序树进行遍历保证输出所有结点的值序列有序排列应对该二叉排序树采用中序遍历法三应用题分分设一棵树中边的集合为要求用孩子兄弟表示法二叉链表表示出该树的存储结构并将该树转化成对应的二叉树大题得分大题得分小题得分请画出下图的邻接矩阵和邻接表设有一组初始记录关键字为要求构造一棵二叉排序树并给出构造过程设有无向图要求给出用普里姆算法构造最小生成树和所走过的边的集合小题得分小题得分小题得分装订线共页第页假设一棵二叉树的先序序列是和中序序列是请画出该树四算法阅读题分分是不带头结点的单链表的头指针请回答下列问题说明语句的功能查询链表的尾结点说明语句组的功能将第一个结点连接到链表的尾部作为新的尾结点设链表表示的线性表为写出算法执行后的返回值所表示的线性表返回的线性表为分该算法的功能是后序遍历二叉树递归算法五算法设计题分设计两个有序单链表的合并排序算法分小题得分大题得分小题得分小题得分大题得分小题得分共页第页共页第页设计在链式存储结构上交换二叉树中所有结点左右子树的算法分小题得分共页第页装订线