5-数据结构历年题答案新

1、PAGE 数据结构基础题一、单选题2014-C10、链表不具有的特点是( B )。 A、不必事先估计存储空间 B、可随机访问任一元索 C、插入删除不需要移动元素 D、所储空间与线性表长度成正比2014-C16、一棵具有5层的满二叉树中结点数为（ A ）。A、31 B、32 C、33 D、162014-C17、有向图中每个顶点的度等于该顶点的 ( C )。A、入度 B、出度 C、入度与出度之和 D、入度与出度之差2013-C5、 将（2, 6, 10, 17）分别存储到某个地址区间为 010 的哈希表中，如果哈希函数h(x) =（ D ），将不会产生冲突，其中 a mod b 表示 a 除以 b

2、 的余数。 A、x mod 11 B. x2 mod 11 C、2x mod 11 D、 mod 11，其中表示下取整2013-C7、下图中所使用的数据结构是（ B ）。2013-C9、已知一棵二叉树有 10 个节点，则其中至多有（ A ）个节点有 2 个子节点。A、4 B、5 C、6 D、72013-C10、在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4 个顶点、6 条边的连通图。若要使它不再是连通图，至少要删去其中的（ C ）条边。A、1 B、2 C、3 D、42013-C11、二叉树的（ A ）第一个访问的节点是根节点。 A、先序遍历 B、中序遍历 C、后

3、序遍历 D、以上都是2013-C12、以 A0 作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（ A ）。 A、A0, A1, A2, A3 B、A0, A1, A3, A2 C、A0, A2, A1, A3 D、A0, A3, A1, A22012-C6、如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（ C ）。 A、ABC B、CBA C、ACB D、BAC 2012-C12、 如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a，b，c，另有元素d已经出栈，则可能的入栈顺序是（ D ）。A、a, d, c, b B、b, a, c, d C、a, c, b

4、, d D、d, a, b, c 2012-C18、在程序运行过程中，如果递归调用的层数过多，会因为（A ）引发错误。A、系统分配的栈空间溢出 B、系统分配的堆空间溢出 C、系统分配的队列空间溢出 D、系统分配的链表空间溢出 2011-C5、无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图 G 有 7 个顶点，则它共有（ B ）条边。 A、7 B、21 C、42 D、49 答案：7*6/2=212011-C7、如果根结点的深度记为 1，则一棵恰有 2011 个叶结点的二叉树的深度最少是（ C ）。 A、10 B、11 C、12 D、13 答案：11层叶节点数是210=1024,

5、12层叶节点数是211=2048，所以结果是C。2011-C19、对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，右图就是一个强连通图。事实上，在删掉边（ A ）后，它依然是强连通的。A、a B、b C、c D、d2011-G3右图是一棵二叉树，它的先序遍历是（ A ）。 A、ABDEFC B、DBEFAC C、DFEBCA D、ABCDEF2011-G5广度优先搜索时，需要用到的数据结构是（ B ）。 A、链表 B、队列 C、栈D、散列表2010-C5、如果树根算第1层，那么一棵N层的二叉树最多有（ A ）个结点。 A、2 n-1 B、2 n C、2n

6、 + 1 D、2 n+1 答：N层的满二叉树是节点最多的，结点数是2 n-1 2010-C9、前缀表达式“+ 3 * 2 + 5 12”的值是（ C ）。 A. 23 B. 25 C. 37 D. 65 答：由前缀表达式写出表达式树，在写出中缀式即可。 中缀表达式：3+2*（5+12）2010-C15、元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的不可能是（ B ）。 A. R1 B. R2 C. R4 D. R5 答：模拟试验一下即可。2010-C16、双向链表中有两个指针域llink和rlink，分别指向该节点的前驱和后继

7、。设p指向链表中的一个结点，它的左右结点均非空。现要求删除结点p，则下面语句序列中错误的是（ ）。 A. p .rlink.llink=p.rlink; p.llinkrlink=pllink; dispose(p); B. pllink.rlink=p.rlink; P.rlink.llink=pllink;dispose(p); C. p.rlink.llink=p.llink; prlink.llink.rlink=p.rlink;dispose(p); D. p.llink.rlink=p.rlink; pllink.rlink.llink=p.llink;dispose(p); 答：

8、根据题意画一个示意图即可排除选项A。 2010-C17、一棵二叉树的前序遍历是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（ A ）。 A. 2 B. 3 C. 4 D. 5 答：由前序和后序进行分析，可以得出结论。ABCDEFG CBFEGDA2010-C18、关于拓扑排序，下面说法正确的是（ D ）。 A. 所有连通的有向图都可以实现拓扑排序 B.对同一个图而言，拓扑排序的结果是唯一的 C.拓扑排序中入度为0的结点总会排在入度大于0的结点的前面 D.拓扑排序结果序列中的第一个结点一定是入度为0的点 答：D正是拓扑排序的定义。2010-C19、完全二叉树的顺

9、序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置，则第k号结点的父结点如果存在的话，应当存放在数组的（ C ）号位置 A. 2k B. 2k+1 C. k/2下取整 D. (k+1)/2下取整 答：第k个元素的父结点(k/2)取整，例如k=6，父结点是3, k=7,父结点也是3。2009-C12、有六个元素FEDCBA从左到右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？ （ C ）A、EDCFAB B、DECABF C、CDFEBA D、BCDAEF答：D先出的话，不可能在先出F,再出E。20

10、09-C13、表达式a*(b+c)-d的后缀表达式是（ B ）A、abcd*+- B、abc+*d- C、abc*+d- D、-+*abcd 答：先画出表达式树，再写出后缀表达式。2009-C14、一个包含n个分支节点（非叶节点）的非空二叉树，它的叶节点数目最多为：A、2n+1 B、2n-1 C、n-1 D、n+1答：考虑满二叉树的情况2009-C18、已知n个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点），则该图中最少有多少条有向边？( A ) A、n B、n+1 C、n-1 D、n*(n-1)答：考虑环形图，这时有向边数为n。2009-G5、一个包含n个分支结点（非叶结

11、点）的非空满k叉树，k=1，它的叶结点数目为：( D ) A）nk+1B）nk-1C）(k+1)n-1D）(k-1)n+1 答：针对k=2看看那个结果正确，可以看出D是对的。2009-G6、表达式a*(b+c)-d的后缀表达式是：( B ) A）abcd*+-B）abc+*d-C）abc*+d-D）-+*abcd 答：与C13一样。2009-G7、最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码：( B ) A）（00，01，10，11） B）（0，1，00，11） C）（0，10，110，

12、111） D）（1，01，000，001） 答：前缀码：给定一个序列的集合，若不存在一个序列是另一个序列的前缀，则该序列集合称为前缀码。B）中0与00,1与11有前缀关系，所以不是。2008-C5完全二叉树共有2*N-1个结点，则它的叶节点数是（ B ）。A. N-1 B. N C. 2*N D. 2N-1 答：设定N=2，这时2*N-1=3,即有3个节点的完全二叉树，有两个叶子节点，显然应该选择B.2008-C7. 设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是（ C ）。A. 6 B. 5 C. 4 D. 3 答：模拟

13、试验一下，可以看到应该选C.2008-C11 递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（ D ）的数据结构。A. 队列 B. 多维数组 C. 线性表 D. 栈 答：递归用到栈，这是定义来的。2008-C13. 二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为结点的编号，以下同），中根遍历是2 4 1 5 7 3 6，则该二叉树的后根遍历是（ B ）。A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 7 4 2 5 6 3 1 D. 4 2 7 6 5 3 1 答：先由先根和中根画出二叉树，再写出后根遍历。2008-C18. 设T是一棵有n个

14、顶点的树，下列说法不正确的是（ A ）。A. T有n条边 B. T是连通的 C. T是无环的 D. T有n-1条边 答：n个顶点的树不可能有n条边，只能是n-1条边。2007-C2在关系数据库中，存放在数据库中的数据的逻辑结构以（ D ）为主。 A二叉树B多叉树C哈希表D二维表 答：关系数据库的定义来的。2007-G2. 在关系数据库中, 存放在数据库中的数据的逻辑结构以( E )为主。A. 二叉树 B. 多叉树 C. 哈希表 D. B+树 E. 二维表 答：同上。2007-C16/G7地面上有标号为A、B、C的三根柱，在A柱上放有10个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3，将

15、A柱上的部分盘子经过B柱移入C柱，也可以在B柱上暂存。如果B柱上的操作记录为“进、进、出、进、进、出、出、进、进、出、进、出、出”。那么，在C柱上，从下到上的编号为（ D ）。 A243657B241257C243176D243675 E. 2 1 4 3 7 5 答：模拟一下即可。2007-C20已知7个节点的二叉树的先根遍历是1245637（数字为节点的编号，以下同），中根遍历是4265173，则该二叉树的后根遍历是（ A）。 A4652731B4652137C4231547D4653172 答：由前两种画出二叉树，再得出后根遍历即可。2007-G 9. 欧拉图G是指可以构成一个闭回路的图

16、，且图G的每一条边恰好在这个闭回路上出现一次（即一笔画成）。在以下各个描述中, 不一定是欧拉图的是：（ D ）。图G中没有度为奇数的顶点 B. 包括欧拉环游的图(欧拉环游是指通过图中每边恰好一次的闭路径) C. 包括欧拉闭迹的图(欧拉迹是指通过途中每边恰好一次的路径) D. 存在一条回路, 通过每个顶点恰好一次 E. 本身为闭迹的图 答：D是哈密尔顿图，不是欧拉图。2006-C10：在编程时（使用任一种高级语言，不一定是 Pascal），如果需要从磁盘文件中输入一个很大的二维数组（例如 1000*1000 的double 型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）

17、相比，在输入效率上（ D ）。 A. 没有区别 B. 按行读的方式要高一些 C. 按列读的方式要高一些 D. 取决于数组的存储方式。 答：按行按列只是形式，关键看存储方式，是顺序的还是链式的。2006-C13：某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的 顺序为 1，2，3，则车辆出站的顺序为（ C ）。 A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2 答：模拟一下即可。20

18、06-C14：高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。 在这里，树高等于叶结点的最大深度，根结点的深度为 0，如果某个均衡的二叉树共有2381个结点， 则该树的树高为（ B）。 A. 10 B. 11 C. 12 D. 13 答：因为211 = 2048；所以一颗满二叉树从深度为0（根节点）到深度10的总节点数是2047，剩下2381-2047 = 334个节点，这剩下的节点的深度都是11。2006-C19： 设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（ C ）。 A. a, b, c, e, d

19、B. b, c, a, e, d C. a, e, c, b, d D. d, c, e, b, a 答：模拟一下即可。2006-C20：已知6个结点的二叉树的先根遍历是 1 2 3 4 5 6 （数字为结点的编号，以下同），后根遍历是 3 2 5 6 4 1，则该二叉树的可能的中根遍历是（ B ） A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 1 3 5 4 6 D. 2 3 1 4 6 5 答：由前两种画出可能的二叉树，再得出可能的中根遍历即可。2006-G4在编程时（使用任一种高级语言，不一定是Pascal），如果需要从磁盘文件中输入一个很大的二维数组（例如 10

20、00*1000 的double 型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（ E ）。 A. 没有区别 B. 有一些区别，但机器处理速度很快，可忽略不计 C. 按行读的方式要高一些 D. 按列读的方式要高一些 E. 取决于数组的存储方式。 答：与C10一致。2006-G7某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为 1，2，3，则车辆出站的顺序为（ C ）。 A. 1, 2, 3, 4, 5 B. 1, 2,

21、 4, 5, 7 C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2 E. 1, 4, 3, 7, 5 答：与C13一致。2006-G8高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。 在这里，树高等于叶结点的最大深度，根结点的深度为 0，如果某个均衡的二叉树共有2381个结点， 则该树的树高为（ B ）。 A. 10 B. 11 C. 12 D. 13 E. 210 1 答：与C14一致。 2005-C4: 完全二叉树的结点个数为11，则它的叶结点个数为（ E ）。A、4 B、3 C、5 D、2 E、6答：画出该完全二叉树即可。2005

22、-C5: 平面上有五个点A（5,3),B(3,5),C(2,1),D(3,3),E(5,1)。以这五点作为完全图G的顶点，每两点之间的直线距离是图G中对应边的权值。以下哪条边不是图G的最小生成树中的边（ D）。A、AD B、BD C、CD D、DE E、EA答：在坐标中画出该完全图（带权），再生成最小生成树树。2005-C19: 二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父交点，D是G的父交点，F是I的父交点，数中所有结点的最大深度为3，（根结点深度设为0），可知F的父结点是（ C ）。 A、无法确定 B、B C、C D、D E、E答：根据题意，模拟画出二叉树

23、即可。2005-C20: 设栈S的初始状态为空，元素a,b,c,d,e,f,g依次入栈，以下出栈序列不可能出现的是（ E）。 A.a,b,c,e,d,f,g B.b,c,a,f,e,g,d C.a,e,d,c,b,f,g D.d,c,f,e,b,a,g E.g,e,f,d,c,b,a 答：模拟一下即可。2005-G4: 4. 完全二叉树的结点个数为4 * N + 3，则它的叶结点个数为（ E ）。 A、2*N B、2*N-1 C、2*N+1 D、2*N-2 E、2*N+2 答：令N=1，则结点个数为7，画出的是一个满二叉树，叶子书为4，所以选E。2005-G5: 平面上有五个点A(5, 3),

24、 B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为完全图G 的顶点，每两点之间的直线距离是图G 中对应边的权值。图G 的最小生成树中的所有边的权值综合为（ D）。 A、8 B、7+ C、9 D、6+ E、4+2+答：与2005-C5类似。2004-C14/G3：某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。假设车辆入站的顺序为1，2，3，则车辆出站的顺序为（ E ）。A、1, 2, 3, 4, 5 B、1, 2, 4, 5, 7 C、1, 3,

25、 5, 4, 6 D、1, 3, 5, 6, 7 E、1, 3, 6, 5, 7 答：模拟一下即可。2004-C15/G5：二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为（ B ）。A、4 2 5 7 6 3 1 B、4 2 7 5 6 3 1 C、4 2 7 5 3 6 1 D、4 7 2 3 5 6 1 E、4 5 2 6 3 7 1 答：由前两种遍历画出二叉树，再写出后序遍历。2004-C16/G4：满二叉树的叶结点个数为N，则它的结点总数为（ C ）。A、N B、2 * N C、2 * N 1 D、2 * N +

26、1 E、2N 1 答：令N=2，则结点总数应高为3，所以选C。2004-C19：在下图中，从顶点（ E ）出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次。A、A点 B、B点 C、C点 D、D点 E、E点 答：该图中有（只有）两个点度数为奇数3，因此存在欧拉路，起点为任一度数为奇数的点，因此E点可做出发点。选择E。2004-C20：某大学计算机专业的必修课及其先修课程如下表所示：请你判断下列课程安排方案哪个是不合理的（ D ）。A、C0, C6, C7, C1, C2, C3, C4, C5 B、C0, C1, C2, C3, C4, C6, C7, C5C、C0, C1, C6, C

27、7, C2, C3, C4, C5 D、C0, C1, C6, C7, C5, C2, C3, C4E、C0, C1, C2, C3, C6, C7, C5, C4答：模拟一下即可。只有D满足。 2004-G2：二叉树T已知其前序遍历序列为1243576，中序遍历序列为4215736，则其后序遍历为（ B ）。 A、4257631 B、4275631 C、4275361 D、4723561 E、4526371 答：由前两种遍历画出二叉树，再写出后序遍历。2003-C1/G1：一个高度为h 的二叉树最小元素数目是（B ）。A、2h+1B、hC、2h-1 D、2hE、2h-1答：最小元素数的二叉树

28、是线性树，元素个数为h，选择B。 要注意什么事树的高，一个点的树的高为1。2003-C2/G2：已知队列（13，2，11，34，41，77，5，7，18，26，15），第一个进入队列的元素是13，则第五个出队列的元素是（B ）。 A、5B、41C、77D、13E、18 答：模拟一下即可。2003-G3：表达式(1+34)*5-56/7 的后缀表达式为（C ）。 A、1+34*5-56/7 B、-*+1 34 5/56 7 C、1 34 +5*56 7/- D、1 34 5* +56 7/- E、1 34+5 56 7-*/ 答：先写出表达式树，再写出后缀（后序）表达式。2002-C1/G1：一

29、个向量第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（ B）。 A、110 B、108 C、100 D、109 答：模拟一下即可，注意起点是100。2002-C3/G2：设有一个含有13个元素的Hash表（0 12），Hash函数是：H（key）= key % 13，其中%是求余数运算。用线性探查法解决冲突，则对于序列（2、8、31、20、19、18、53、27），18应放在第（ B ）号格中。 A、5 B、9 C、4 D、0 答：模拟一下即可。注意若某个单元已经被占用，则向后找到第一个空的位置。2002-G3：按照二叉数的定义，具有3个结点的二叉树有（ C ）种。 A

30、、3 B、4 C、5 D、6 答:穷举画出所有满足条件的二叉树即可。2002-G4：在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A、1/2 B、1 C、2 D、4 答：所有入度之和等于出度之和。2002-C4/G5：要使1 8号格字的访问顺序为：8、2、6、5、7、3、1、4，则下图中的空格中应填入（ C ）。12345678461-1732A、6 B、0 C、5 D、3答：模拟一下即可。2002-G6：设栈S和队列Q的初始状态为空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e 2 ，e 4 ，

31、e 3 ，e 6 ，e 5 ，e 1 ，则栈S的容量至少应该为（ B ）。 A、2 B、3 C、4 D、5答：模拟一下即可。2001-C1/G1：若已知一个栈的入栈顺序是1，2，3，n，其输出序列为P1，P2，P3，Pn，若P1是n，则Pi是( ) A、i B、n-1 C、n-i+1 D、不确定答：模拟一下即可。2001-G2：以下哪一个不是栈的基本运算( B ) A、删除栈顶元素 B、删除栈底的元素 C、判断栈是否为空 D、将栈置为空栈答：栈的基本运算中没有B。2001-C2/G3：在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的关键码比较的

32、次数为( C ) A、2 B、3 C、4 D、5答：模拟一下即可。 2001-G4：一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有( B )个结点A、2h-1 B、2h-1 C、2h+1 D、h+1 答：满足条件的是哈夫曼树，哈夫曼树的结点数是2h-1。 2001-G5：无向图G=(V，E)，其中V=a,b,c,d,e,f E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)对该图进行深度优先遍历,得到的顶点序列正确的是( D ) A、a,b,e,c,d,f B、a,c,f,e,b,d C、a,e,b,c,f,d D、a,b,e,d,f,c 答：

33、先画出该图，再判断哪一个满足深度优先遍历即可。 2000-C1：设循环队列中数组的下标范围是1n，其头尾指针分别为f和r，则其元素个数为（D）A、r-f B、r-f+1 C、(r-f) MOD n+1 D、(r-f+n) MOD n答：只要对循环队列真正理解，知道尾指针r可能小于头指针f，那么只有D是正确的。2000-C2：在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是（D） A、堆排序 B）因特网 C）冒泡排序 D）快速排序 答：只要了解各种排序的算法即可，选项B不是排序？2000-C3/G1：某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索（b

34、inary search），在最坏的情况下，需检视（10）个单元。A、1000 B、10 C、100 D、500答：因为210 =1024，所以选择B。 2000-C4/G2：已知数组A中，每个元素AI,J在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A5,8的起始地址为（A） A、SA+141 B、SA+180 C、SA+222 D、SA+225 答：起始地址=SA+（5-1）*10*3+7*3=120+21=141 注意，第一各院是从地址Sa+0开始的。 2000-C5：线性表若采用链表存贮结构,要求内存中可用存贮单元地址（D

35、）A、必须连续 B、部分地址必须连续 C、一定不连续 D、连续不连续均可答：链表存储的优点正是可连续，也可不连续。2000-C6/G3：下列叙述中,正确的是（D）A、线性表的线性存贮结构优于链表存贮结构 B、队列的操作方式是先进后出C、栈的操作方式是先进先出 D、二维数组是指它的每个数据元素为一个线性表的线性表 答：用排除法，A、B、C、都是错误的，而D的说法是正确的。2000-G4：在有N个叶子节点的哈夫曼树中，其节点总数为（B）A、不确定 B、2N-1C、2N+1 D、2N 答：同2001G4，画一个哈夫曼树检验一下即可。2000-G5：线性表若采用链表存贮结构，要求内存中可用存贮单元地址

36、（D）A）必须连续B）部分地址必须连续C）一定不连续D）连续不连续均可 答：与2000C5一样。2000-G5：一个文本屏幕有25列及80行，屏幕的左上角以（1，1）表示，而右下角则以（80，25）表示，屏幕上每一个字符占用两字节（byte），整个屏幕则以线性方式存储在电脑的存储器内，由屏幕左上角开始，位移为0，然后逐列逐列存储。求位於屏幕（X，Y）的第一个字节的位移是（B）A、(Y*80+X)*2-1B、(Y-1)*80+X-1)*2 C、(Y*80+X-1)*2D、(Y-1)*80+X)*2-1答：首先因为是逐列存储，所以Y列之前Y-1列共有(Y-1)*80，所以排除A和C； 令X=1，Y

37、=1，则选项B为0，选项D为1，所以选择B。二、多选题2011-G1如果根结点的深度记为1，则一棵恰有2011个叶子结点的二叉树的深度可能是（ CD ）。 A、10B、11C、12 D、13 答：至少为12，也可以是13。2011-G7对于序列“7、5、1、9、3、6、8、4”，在不改变顺序的情况下，去掉（ CD ）会使逆序对的个数减少3。 A7 B5C3 D6 答：所有的逆序对有(7,5),(7,1)(7,3)(7,6)(7,4) (5,1)(5,3)(5,4) (9,3)(9,6),(9,8),(9,4) (6,5), (8,4)共14个 很显然，去掉3，减少了(7,3)，(5,3),(9

38、,3)等3个，去掉6，减少了(7,6),(9,6),(6,5)等3个。而去掉7或5则减少的数量大于3个。2009-G16、若3个顶点的无权图G的邻接矩阵用数组存储为0，1，11，0，10，1，0，假定在具体存储中顶点依次为：v1，v2，v3关于该图，下面的说法哪些是正确的：( ) A、该图是有向图。 B、该图是强联通的。 C、该图所有顶点的入度之和减所有顶点的出度之和等于1。 D、从v1开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的。2009-17G、在带尾指针（链表指针clist指向尾结点）的非空循环单链表中每个结点都以next字段的指针指向下一个节点。假定其中已经有了2个以上的结点。下面哪些说法是正确的：( ) A、如果p指向一个待插入的新结点，在头部插入一个元素的语句序列为： p.next:=clist.next;clist.next:=p; B、如果p指向一个待插入的新结点，在尾部插入一个元素的语句序列为： p.next:=clist;clist.next:=p; C、在头部删除一个结点的语句序列为： p:=clist.next;clist.next:=clist.next.next;dispose(p); D、在尾部删除一个结点的语句序列为： p:=clist;clist:=clist.