华中科技大学计算机学院 1 1 《数据结构》试卷 (A 卷) 2010 —2011 年度第二学期计算机学院 班级______ 学号___________ 姓名_________ 考试时间：2011 年 月 日 考试形式：闭卷 题号 一 二 三 四 五 六 七 八 总分 核对人 题分 10 10 10 12 32 10 6 10 100 得分 一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D)写在下表中,每小题1 分,共 10 分) 题号 1 2 3 4 5 6 7 8 9 10 答案 1．对于栈的进栈和出栈运算，采用______存储结构时运算效率最高。 A．单链表 B．容量足够大的顺序表 C．单向循环链表 D．双向循环链表 2．链式队列和顺序队列比较，具有_____这个优势。 A．进队操作方便 B．出队操作方便 C．通常不会出现满队列情况 D．求队列元素个数方便 3．下列关于串的叙述中，正确的是_____。 A．2 个串的长度相等，则 2 个串相等 B．空串至少包一个空格 C．替换操作可以实现字符的删除 D．一个串的长度至少是 1 4．二叉树在线索化后，下列问题中相对难解决的是____。 A．先根线索二叉树中求先根后继 B．中根线索二叉树中求中根前趋 C．中根线索二叉树中求中根后继 D．后根线索二叉树中求后根后继 5．对序列（30，26，18，16，5，66）进行 2 遍 ________排序后得到序列（5，16，18，26，30，66）。 A．选择 B．冒泡 C．插入 D．归并 得分 评卷人 华中科技大学计算机学院 2 2 6．在下列排序算法中，_______算法可能出现如下情况：在最后一趟排序之前，所有元素均不在其最终的位置上。 A．堆排序 B．快速排序 C．冒泡排序 D．插入排序 7．由4 个结点可以组成______棵不同形态的二叉树。 A．10 B．12 C．14 D．16 8．对包含n 个元素的散列表进行检索，平均查找长度为____。 A．O(lo gn ) B．O(n ) C．O(n lo gn ) D．不直接依赖于n 9．广义表 ((a,(b),c),((),(d)),(((((e)),f))),())的长度是____。 A．2 B．3 C．4 D．5 10．对某无向图进行一次深度优先搜索遍历，如果能访问到所有的顶点，则该无向图一定是________。 A．连通图 B．树图 C．有回路的连通图 D．完全图 二、填空题(在下表中填写正确的答案,每空 1分,共 10分) 题号 1 2 3 4 5 6 7 8 9 10 答案 1．具有n 个单元、用首尾指针、无标志位的循环队列中，队满时共有_______个元素。 2．设顶点数为n ，弧数为e...
