试卷试题-数据结构期末考试试题.doc

数据结构期末考试试题 本资源摘要信息涵盖了数据结构期末考试试题的主要知识点，包括单选题、填空题、运算题和阅读算法题等。这些问题涵盖了数据结构的多个方面，包括链表、树、图、堆、排序算法等。 单选题 1. 在一个单链表中，向表头插入一个结点的正确操作是将新结点的next指针指向当前表头，然后将表头指针指向新结点。 2. 一个强连通图中至少含有n条有向边，其中n是顶点的数量。 3. 在二叉搜索树中查找一个元素的时间复杂度大致为O(logn)。 4. 由权值分别为3、8、6、2、5的叶子结点生成的一棵哈夫曼树，它的带权路径长度为72。 5. 当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为引用型参数，以节省参数值的传输时间和存储参数的空间。 6. 向一个长度为n的顺序表中插入一个新元素的平均时间复杂度为O(n)。 填空题 1. 数据的存储结构被分为数组、链表、树和图四种。 2. 在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为value域和next域。 3. 中缀表达式3*x*(2.4/5-6)所对应的后缀表达式为3 2.4 5 / * 6 - *。 4. 在一棵高度为h的3叉树中，最多含有3^h-1个结点。 5. 假定一棵二叉树的结点数为18，则它的最小深度为4，最大深度为18。 6. 在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定小于该结点的值，右子树上所有结点的值一定大于该结点的值。 7. 当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层上浮调整，直到被调整到根结点为止。 8. 表示图的三种存储结构为邻接矩阵、邻接表和边表。 9. 对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为O(n^2)，对用邻接表表示的图进行任一种遍历时，其时间复杂度为O(n+e)。 10. 从有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素时，其查找长度分别为3和4。 运算题 1. 假定一棵二叉树广义表表示为a(b(c,d),e(f,g)),分别写出对它进行先序、中序、后序和后序遍历的结果。 2. 已知一个带权图的顶点集V和边集E分别为：V={0,1,2,3,4,5}；E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(4,5)10},则求出该图的最小生成树的权。 3. 假定一组记录的排序码为(46,79,56,38,40,84,50,42)，则利用堆排序方法建立的初始堆为。 4. 有7个带权结点，其权值分别为3,7,8,2,6,10,14，试以它们为叶子结点生成一棵哈夫曼树，求出该树的带权路径长度、高度、双分支结点数。 阅读算法 1. VOldAC(List&L)算法的主要步骤为：初始化链表L，插入元素25到链表的尾部，插入元素50到链表的头部，然后将数组a中的元素插入到链表中。