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

数据结构模拟题 一、判断题（共 10 分，每小题 1 分） (1) 在快速排序、堆排序、归并排序和插入排序中，堆排序所需要的附加存储开销最 大。 【 错 】 (2) 用二分（对半）查找表的元素的速度不一定比顺序查找快。【 对 】 (3) 对于大小均为 m 的有序表和无序表分别进行顺序查找，在等概率查找的情况下， 对于查找成功，它们的平均查找长度相同。【 错 】 (4) 若一个有向图的邻接矩阵中，主对角线以下的元素为零，则存在该图的拓扑有序 序列。【 对 】 (5) 霍夫曼树的结点个数不能是偶数。【 对 】 (6) 一个二叉树的前序序列和后序序列正好相反，则该二叉树一定是高度等于其结点 数的二叉树。【 对 】 (7) 对一个具有 n 个元素的线性表，建立其有序单链表的时间复杂度为 O(n) 。【 错 】 (8) n 个顶点的强连通图至少有 n 条边。【 对 】 (9) 在完全二叉树中，对于结点 i 和 j ，如果 log i log j ，则说明这两个结点处  2   2      于同一层。【 对 】 二、选择题（共 20 分，每题 2 分） 1、在双向链表中，如果要在指针p 所指的结点后插入 q 所指的新结点，下面哪个操作 序列是正确的？【 C 】 A ．p rlinkllink=q ； p rlink=q ；qllink=p ；qrlink=prlink ； B ．p llinkrlink=q ； p llink=q ；qrlink=p ；qllink=pllink ； C ．qllink=p ； q rlink=prlink ；p rlinkllink=q ；p rlink=q ； D ．qrlink=p ； q llink=pllink ；pllinkrlink=q ；p llink=q ； 2 、如下是一个稀疏矩阵的三元组法存储表示和基于此表示法所得出的相关叙述 【 D 】 行下标 列下标 值 1 1 3 1 4 5 科目名称：数据结构 第 1 页 共 5 页 2 3 2 3 2 6 3 4 5 5 3 3 I. 该稀疏矩阵有 5 行 II. 该稀疏矩阵有 4 列 III. 该稀疏矩阵有 6 个非0元素 A ．只有I B ．I 和 II