上海交通大学继续教育学院网络教育——期末复习样卷答案课程名称：数据结构一、单项选择题（每题 2 分，共 30 分）1、 包含 64 个结点的完全二叉树，其深度为（ ）(根的层次为 1)。A、8B、7C、6D、52、 关于算法的空间复杂度的理解错误的是（ ）。 A. 空间复杂度，即为算法的存储空间需求。B. 空间复杂度是指算法在执行过程中所需要的最大的存储空间。C. 空间复杂度，包括算法在执行过程中指令、常数、变量、输入数据，以及程序执行过程中所需要的辅助空间。D. 算法的空间复杂度与算法无关。3、 数据结构包括 3 个方面的内容，它们分别是（ ）。A、数据、数据元素、数据项B、数据元素、数据处理、算法实现C、数据元素、数据的逻辑结构、数据的存储结构D、数据的逻辑结构、数据的存储结构、数据的操作4、 一个栈的入栈序列是 a、b、c、d，则下列序列中不可能是栈的输出序列的是（ ）。A、acbdB、 dcbaC、acdbD、dbac5、 将 5 个不同的数据进行插入排序，至多需要比较（ ）次。A. 8B. 9C. 10D. 256、 栈和队列的共同点是（ ）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点7、 设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字 5 为基准进行一趟快速排序的结果为（ ）。A、 2,3,5,8,6B、3,2,5,8,6C、 3,2,5,6,8D、 2,3,6,5,88、 设有一顺序栈 S，元素 s1,s2,s3,s4,s5,s6 依次进栈，假如 6 个元素出线的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是（ ）。 A.2B.3C.5D.69、 设某无向图中有 n 个顶点 e 条边，则该无向图中所有顶点的入度之和为（ ）。A、 nB、 eC、 2nD、 2e10、设无向图 G 中有 n 个顶点 e 条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。A. n，eB. e，nC. 2n，eD. n，2e11、下列关键字序列中，( ) 是堆。A、16, 72, 31, 23, 94, 53B、94, 23, 31, 72, 16, 53 C、16, 53, 23, 94，31, 72 D、16, 23, 53, 31, 94, 7212、以下说法错误的是（ ）。 A.一般在哈夫曼树中，权值越大的叶子离根结点越近B.哈夫曼树中没有度数为 1 的分支结点C.若初始森林中共有 n 裸二叉树，最终求得的哈夫曼树共有 2n-1 个结点D.若初始森林中共有 n 裸二叉树，进行 2n-1 次合并后才能剩下一棵最终的哈夫曼树13、设有序表中有 1000 个元素，则用二分查找法查找...
