武汉大学计算机学院2010年－2011学年第一学期“数据结构”考试试题（A）一、单项选择题（每小题2分，共计40分）
1下列各项中属于逻辑结构的是。A哈希表B有序表C单链表2以下算法的时间复杂度为。
voidfu
i
t
i
ti1whilei
ii2
D顺序表
AO
BO
2CO
log2
DOlog2
3在一个长度为
的顺序表中删除第i个元素（1≤i≤
）时，需向前移动个元素。A
Bi1C
iD
i14判断带头结点的循环单链表L中只有一个结点的条件是。ALNULLBL
extLCL
ext
extLDL
extNULL5中缀表达式abcd的后缀表达式是。AabcdBabcdCabcdDabcd6设环形队列中数组的下标是0～N1，其头尾指针分别为f和r（f指向队列中队头元素的前。一个位置，r指向队尾元素的位置），则其元素个数为ArfBrf1Crf％N1DrfN％N7若用一个大小为6的数组来实现环形队列，队头指针fro
t指向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置。若当前rear和fro
t的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和fro
t的值分别为。A1和5B2和4C4和2D5和18稀疏矩阵采用压缩存储后，通常必会失去功能。A顺序存储B随机存取C输入输出D以上都不对9一棵有124个叶子结点的完全二叉树，最多有个结点。A247B248C249D25010
个结点的线索二叉树上含有的线索个数为。A2
B
1C
1D
11由带权为9、2、5、7的4个叶子结点构成的一棵哈夫曼树的带权路径长度是A23B37C46D4412若邻接表中有奇数个边表结点，则一定是。A图中有奇数个结点B图中有偶数个结点C图为无向图D图为有向图13最小生成树指的是。A由连通图所得到的边数最少的生成树B由连通图所得到的顶点数相对较少的生成树C连通图中所有生成树中权值之和为最小的生成树D连通图的极小连通子图14以下关于图的叙述中正确的是。
1
。
fA最短路径一定是简单路径BDijkstra算法不适合有回路的带权图求最短路径CDijkstra算法不适合求任意两个顶点的最短路径DFloyd算法求两个顶点的最短路径时，pathk1一定是pathk的子集15一棵平衡二叉树一定是一棵。A完全二叉树B二叉排序树C堆D哈夫曼树个关键字。16m阶B树除根节点外，非叶子节点至少包含Am2Bm21Cm2Dm2117对于AOE网的关键路径，以下叙述是正确的。A任何一个关键活动提前完成，则整个工程也会提前完成B完成工程的最短时间是从源点到汇点的最短路径长度C一个Ar