[2018年必威体育精装版整理]2011年数据结构本科试题及答案.doc

武汉大学计算机学院 2011年－2012学年第一学期“数据结构”考试试题（A） 要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。 一、单项选择题（共20小题，每小题2分，共40分） 1. 下列各选项中属于逻辑结构的是 。 A.哈希表 B.有序表 C.单链表 D.顺序表 2. 对于数据结构，以下叙述中不正确的是 。 A.数据的逻辑结构与数据元素本身的形式和内容无关 B.数据的逻辑结构是数据的各数据项之间的逻辑关系 C.数据元素是数据的基本单位 D.数据项是数据的最小单位 3. 某算法的时间复杂度为O(n2)，表明该算法的 A.问题规模是n2 B.执行时间等于n2C.执行时间与n2成正比 D.问题规模与n2成正比A.使单链表至少有一个节点 B.标识表节点中首节点的位置 C.方便单链表运算的实现 D.说明单链表是线性表的链式存储 5. 删除某个双链表中的一个节点（非首、尾节点），需要修改 个指针域。 A.1 B.2 C.3 D.4 6. 栈和队列是两种不同的数据结构，但它们中的元素具有相同的 。 A.抽象数据类型 B.逻辑结构 C.存储结构 D.运算 7. 元素a、b、c、d、e依次进栈，进栈栈栈栈A.3 B.4 C.5 D.6 8. 设环形队列中数组的下标是0～N-1，其头尾指针分别为f和r（f指向队列中队头元素的前一个位置，r指向队尾元素的位置），则其元素个数为 。 A.r-f B.r-f-1 C.(r-f)％N+1 D.(r-f+N)％N 9. 已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是 。 A.0，0 B.0，n-1 C.n-1，0 D.n-1，n-1 10. 对于n阶（n≥2）对称矩阵，采用压缩方法以行序优先存放到内存中，则需要 个存储单元。 A.n(n+1)/2 B.n(n-1)/2 C.n2 D.n2/2 11. 一棵度为4的树T中，若有20个度为4的节点，10个度为3的节点，1个度为2的节点，10个度为1的节点，则树T的叶子节点个数是A.41 B.82 C.113 D.122 12. 一个具有n（n≥2）个顶点的无向图，至少有 ① 个连通分量，最多有 ② 个连通分量。 A.0 B.1 C.n-1 D.n 13. 含有n（n≥2）个顶点的无向图的邻接矩阵是一个 。A.对称矩阵 B.零矩阵C.上三角矩阵 D.对角矩阵 A出发得到的广度优先序列可能是 。 A.ABECD B.ACBDE C.ACDBE D.ABDEC 图1 一个无向图 15. 设有100个元素的有序顺序表，用折半查找时，成功时最大的比较次数是 。 A.25 B.50 C.10 D.7 16. 已知一个长度为16的顺序表，其元素按关键字有序排序，若采用折半查找法查找一个不存在的元素，则比较的次数是A.70/17 B.70/16 C.60/17 D.60/16 17. 以下关于m阶B-树的叙述中正确的是 。 A.每个节点至少有两棵非空子树 B.树中每个节点至多有(m/2(-1个关键字 C.所有叶子节点均在同一层上 D.当插入一个关键字引起B-树节点分裂时，树增高一层 18. 为提高散列（哈希）表的查找效率，可以采取的正确措施是 。 Ⅰ.增大装填（载）因子 Ⅱ.设计冲突（碰撞）少的散列函数 Ⅲ.处理冲突（碰撞）时避免产生聚集（堆积）现象 A.仅Ⅰ B.仅Ⅱ C.仅Ⅰ、Ⅱ D.仅Ⅱ、Ⅲ 19. 数据序列{8,9,10,4,5,6,20,1,2}只能是 的两趟排序后的结果。 A.简单选择排序 B.冒泡排序C.直接插入排序D.堆排序 图2 一个无向图 3. 简要叙述堆和二叉排序树的区别，并给出关键字序列{3,26,12,61,38,40,97,75,53,87}调整为大根堆后的结果（直接画出调整后的大根堆）。 三、算法设计题（共3小题，每小题10分，共30分） 1．有一个线性表(a1a2,…,an)，采用带头节点的单链表L存储，设计一个算法将其逆置。所谓就地指为O(1)。. 假设一个不带权的有向图G采用邻接表存储，设计一个算法判断图G中是否存在顶点i到顶点j的边，若存在这