中科院研究生院专业课数据结构复习资料模拟题目.pdfVIP

数据结构模拟题 一、判断题（共 10 分，每小题 1 分） (1)顺序查找法适用于存储结构为顺序或链接存储的线性表。 【对】 (2)数据元素是数据的基本单位，数据元素可以由数据项组成，数据项是数据的最小单位。 【对】 (3)对一个具有 n 个元素的线性表，建立其有序单链表的时间复杂度为 O(n) 。【 错 】 (4)若一个有向图的邻接矩阵为下三角，且主对角线上的元素全为零，则该有向图不含回路。 【 对 】 (5)霍夫曼树的结点个数一定是奇数。【 对 】 (6)若一个广义表的表头为空表，则此广义表亦为空表。【错】 (7)折半查找的时间复杂度为O(log n) 。【 对 】 (8) 树和二叉树之间最主要的区别是：二叉树的结点的子树要区分为左子树和右子树，即使 在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。【对】 (9)有 n 个数存放在一维数组 A[1..n] 中，在进行顺序查找时，这n 个数的排序有序或无序其 平均查找长度不同。【错】 （10）完全二叉树的某结点若无左孩子，则必是叶结点。【对】 二、选择题（共 20 分，每题 2 分） 1、无向图有n 个顶点，则该无向图最多有【B 】条边。 2 A n-1 B n(n-1)/2 C n(n+1)/2 D n 2 、线性表是具有n 个【C 】的有限序列。 A 表元素 B 数据项 C 数据元素 D 数据对象 3、一般情况下，将递归算法转换成等价的非递归算法应该设置【A 】 A 堆栈 B 队列 C 堆栈和队列 D 数组 4 、若以{4，5，6，3，8}作为叶子结点的权值构造哈夫曼树，则带权路径长度是【C 】 A 55 B 68 C 59 D 28 科目名称：数据结构 第 1 页 共 6 页 5、若广义表A 满足 Head(A)=Tail(A) ，则A 为【B 】 A () B (()) C ((), ()) D ((), (), ()) 6、设待排序关键码序列为{25，18，9，33，67，82，53，95，12，70} 。要按关键码值递增 的顺序进行排序，采取以第一个关键码为分界元素的快速排序法，第一趟排序完成后关键码 95 被放置在第几个位置？【 B 】。 A ．7 B ．8 C． 9 D ．10 7、哈希表的平均查找长度和【A 】无直接关系。 A 哈希表记录类型 B 哈希函数 C 处理冲突的方法 D 装填因子 8、设哈希表的长度为 16，哈希函数为H(key)=key%13，表中已有数据的关键字为 18，23 ， 32，46 共四个，现要将关键字为 58 的结点加入到表中，用二次探测再哈希法解决冲突，则 放入的位置是【 D 】。 A. 8 B. 4 C. 10 D. 2 9、当一个有N 个顶点的图用邻接矩阵 A 表示时，顶点 V 的度为【 B 】。 i n n A ． A[i , j ]