选择题 - 数据结构

历届竞赛数据结构选择题

单项选择题（共10题，每题1.5分）

[10]7. 前缀表达式“+ 3 * 2 + 5 12 ” 的值是（ ）。 A. 23 B. 25 C. 37 D. 65

[10]9. 完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（ ）号位置。

A. 2k B. 2k+1 C. k/2下取整 D. (k+1)/2

[09]4. 在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。其对应的十进制整数应该是：( )

A. 19 B. -19 C. 18 D.-18

[09]5. 一个包含n个分支结点(非叶结点)的非空满k叉树，k>=1，它的叶结点数目为：( )

A. nk+1 B. nk-1 C. (k+1)n-1 D. (k-1)n+1 [09]6. 表达式a*(b+c)-d的后缀表达式是：( )

A. abcd*+- B. abc+*d- C. abc*+d- D.-+*abcd

[09]7. 最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码：( )

A.（00，01，10，11） B.（0，1，00，11） C.（0，10，110，111） D.（1，01，000，001） [09]9. 左图给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。则依次加入最小生成树的顶点集合的顶点序列为：( )

A. V0，V1，V2，V3，V5，V4 B. V0，V1，V5，V4，V3，V3 C. V1，V2，V3，V0，V5，V4 D. V1，V2，V3，V0，V4，V5 [08]4．完全二叉树共有2*N-1个结点，则它的叶节点数是（ ）。

A．N-1 B．N C．2*N D．2N-1 E. N/2

[08]6．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，c，f，e，a，则栈S的容量至少应该是（ ）。

A．6 B．5 C．4 D．3 E. 2

[08]8．递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（ ）的数据结构。

A. 队列 B. 多维数组 C. 线性表 D. 链表 E. 栈 [07]2．在关系数据库中，存放在数据库中的数据的逻辑结构以（ ）为主。

A. 二叉树 B. 多叉树 C.哈希表 D. B+树 E.二维表

[07]7．地面上有标号为A、B、C 的3 根细柱，在A 柱上放有10 个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3，??，将A 柱上的部分盘子经过B 柱移入C 柱，也可以在B 柱上暂存。如果B 柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么，在C 柱上，从下到上的盘子的编号为（ ）。

A. 2 4 3 6 5 7 B. 2 4 1 2 5 7 C. 2 4 3 1 7 6 D. 2 4 3 6 7 5 E. 2 1 4 3 7 5

[07]9．欧拉图G 是指可以构成一个闭回路的图，且图G 的每一条边恰好在这个闭回路上出现一次（即一笔画成）。在以下各个描述中，不一定是欧拉图的是（ ）。

A. 图G 中没有度为奇数的顶点

B. 包含欧拉环游的图（欧拉环游是指通过图中每边恰好一次的闭路径） C. 包含欧拉闭迹的图（欧拉迹是指通过图中每边恰好一次的路径）

1

D. 存在一条回路，通过每个顶点恰好一次 E. 本身为闭迹的图

[06]7．某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从 这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的 顺序为 1，2，3，??，则车辆出站的顺序为（ ）。

A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2 E. 1, 4, 3, 7, 5 [06]8．高度为 n 的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为 n-1 的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为 0，如果某个均衡的二叉树共有 2381 个结点， 则该树的树高为（）。 A. 10 B. 11 C. 12 D. 13 E. 210 – 1

[05]4. 完全二叉树的结点个数为4 * N + 3，则它的叶结点个数为（ ）。

A. 2 * N B. 2 * N - 1 C. 2 * N + 1 D. 2 * N - 2 E. 2 * N + 2 [05]5. 平面上有五个点A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为完全图G 的顶点，每两点之间的直线距离是图G 中对应边的权值。图G 的最小生成树中的所有边的权值综合为（ ）。

A. 8 B. 7+ 5 C. 9 D. 6+ 5 E. 4+2 2 + 5

[04]3．某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。假设车辆入站的顺序为1，2，3，??，则车辆出站的顺序为（ ）。

A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 D. 1, 3, 5, 6, 7 E. 1, 3, 6, 5, 7 [04]4．满二叉树的叶结点个数为N，则它的结点总数为（ ）。

A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 1

[04]5．二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为（ ）。

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 [03]5．一个高度为h 的二叉树最小元素数目是（ ）。

A） 2h+1 B） h C） 2h-1 D） 2h E） 2h-1 [03]6．已知队列（13，2，11，34，41，77，5，7，18，26，15），第一个进入队列的元素是13，则第五个出队列的元素是（ ）。

A） 5 B） 41 C） 77 D） 13 E） 18 [02]16．设有一个含有13个元素的Hash表（0 ~ 12），Hash函数是：H（key）= key % 13，，其中%是求余数运算。用线性探查法解决冲突，则对于序列（2、8、31、20、19、18、53、27），18应放在第（ ）号格中。

A）5 B）9 C）4 D）0

[02]17．按照二叉数的定义，具有3个结点的二叉树有（ ）种。 A）3 B）4 C）5 D）6

[02]18。在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A）1/2 B）1 C）2 D）4 [02]19。要使1 ．．．8号格字的访问顺序为：8、2、6、5、7、3、1、4，则下图中的空格中应填入（ ）。

1 2 3 4 5 6 7 8 4 6 1 -1 7 3 2 A）6 B）0 C）5 D）3 [02]20。设栈S和队列Q的初始状态为空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈S的容量至少应该为（ ）。 A）2 B）3 C）4 D）5

[01]13。若已知一个栈的入栈顺序是1，2，3，?，n，其输出序列为P1，P2，P3，?，Pn，若P1是n，

2

则Pi是( )

A)i B)n-1 C)n-i+1 D)不确定 [01]17．以下哪一个不是栈的基本运算( )

A)删除栈顶元素 B)删除栈底的元素 C)判断栈是否为空 D)将栈置为空栈

[01]18．在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的关键码比较的次数为( )

A)2 B)3 C)4 D)5

[01]19．一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有( )个结点

h

A)2-1 B)2h-1 C)2h+1 D)h+1

[01]20．无向图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)},对该图进行深度优先遍历,得到的顶点序列正确的是( )

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 [00]12．在有N个叶子节点的哈夫曼树中，其节点总数为（ ）

A．不确定 B．2N-1 C．2N+1 D．2N [00]17．线性表若采用链表存贮结构，要求内存中可用存贮单元地址（ ）。

A．必须连续 B．部分地址必须连续 C．一定不连续 D．连续不连续均可 [00]18．下列叙述中，正确的是（ ）。

A． 线性表的线性存贮结构优于链表存贮结构 B． 队列的操作方式是先进后出 C． 栈的操作方式是先进先出

D．二维数组是指它的每个数据元素为一个线性表的线性表

[98]10．设栈S的初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在S栈上依次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈、进栈、进栈，出栈、进栈、出栈、进栈。试问出栈的元素序列是______________。

（A）{ 5，4，3，2，1} （B）{2，1} （C）{ 2，3} （D）{3，4}

[97]7．为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为前缀{运算符在前，如X/Y写为/XY} 和后缀 { 运算符在后，如X/Y写为XY/}的表达形式。在这样的表示中可以不用括号即可确定求值的顺序，如：

（P+Q）*（R-S）→*+PQ-RS 或 → PQ + RS -*

① 试将下面的表达式改写成前缀与后缀的表示形式：

A+B*C/D A-C*D+B∧E

② 试将下面的前缀表示还原成中缀的表示形式，同时写出后缀表示： +△A *B△C {前缀式中△表示一元运算符取负号，如△A表示（-A）} 答案：

①前缀形式为：+A/*BCD；后缀形式为：ABC*D/+

前缀形式为：+-A*CD∧BE；后缀形式为：ACD*-BE∧+ ② 中缀形式为（-A）+B*（-C）；后缀形式为：A△BC△*+

不定项选择题（共10题，每题1.5分，共计15分。每题正确答案的个数大于或等于1。多选或少选均不得分）。

[10]1.元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的可能是( )。

A.R1 B.R2 C.R4 D.R5

[10]5. 一颗二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数

3

可能是（ ）。

A．0 B. 2 C. 4 D. 6 [10]7 .关于拓扑排序，下列说法正确的是( )。 A．所有连通的有向图都可以实现拓扑排序 B．对同一个图而言，拓扑排序的结构是唯一的

C．拓扑排序中入度为0的结点总会排在入度大于0的结点的前面 D．拓扑排序结果序列中的第一个结点一定是入度大于0的点

[10]9. 双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。设p指向链表中的一个结点，他的左右结点均为非空。现要求删除结点p，则下列语句序列中正确的是( )。 A．p^.rlink^.llink=p^.rlink; P^.llink^.rlink=p^.llink; dispose(p); B．p^.llink^.rlink=p^.rlink; P^.rlink^.llink=p^.llink; dispose(p);

C．p^.rlink^.llink=p^.llink; P^.rlink^.llink^.rlink=p^.rlink; dispose(p); D．p^.llink^.rlink=p^.rlink; P^.llink^.rlink^.llink=p^.llink; dispose(p);

[09]6. 若3个顶点的无权图G的邻接矩阵用数组存储为{{0，1，1}{1，0，1}{0，1，0}}，假定在具体存储中顶点依次为：v1，v2，v3 关于该图，下面的说法哪些是正确的：(ABD)

A）该图是有向图。 B）该图是强联通的。

C）该图所有顶点的入度之和减所有顶点的出度之和等于1。

D）从v1开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的。

[09]7. 在带尾指针（链表指针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^.next;dispose(p);

[09]8. 散列表的地址区间为0-10，散列函数为H(K)=K mod 11。采用开地址法的线性探查法处理冲突，并将关键字序列26，25，72，38，8，18，59存储到散列表中，这些元素存入散列表的顺序并不确定。假 定之前散列表为空，则元素59存放在散列表中的可能地址有：

A）5 B）7 C）9 D）10

[08]16. 二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为结点的编号，以下同），后根遍历是4 2 7 5 6 3 1，则该二叉树的可能的中根遍历是（ ）。

A. 4 2 1 7 5 3 6 B. 2 4 1 7 5 3 6 C. 4 2 1 7 5 6 3 D. 2 4 1 5 7 3 6 [08]18. 设T是一棵有n个顶点的树，下列说法正确的是（ ）。

A. T是连通的、无环的 B. T是连通的，有n-1条边 C. T是无环的，有n-1条边 D. 以上都不对

[07]14. 已知7 个结点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为结点的编号，以下同），后根遍历是4 6 5 2 7 3 1，则该二叉树的可能的中根遍历是（ ）

A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7 C. 4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3 [06]13. 设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（ ）。 A. a, b, c, e, d B. b, c, a, e, d C. a, e, c, b, d D. d, c, e, b, a

4

[06]14. 已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（ ） A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 3 1 5 4 6 D. 2 3 1 4 6 5

[05]13. 二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D 是G 的父结点，F 是I 的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知E的父结点可能是（ ）。

A. A B. B C. C D. D E. F

[05]14. 设栈S的初始状态为空，元素a, b, c, d, e, f, g依次入栈，以下出栈序列不可能出现的有（ ）。

A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, c, b, d, f, g D. d, c, f, e, b, a, g E. g, e, f, d, c, b, a

[03]19. 已知元素（8，25，14，87，51，90，6，19，20），问这些元素以怎样的顺序进入栈，才能使出栈由OIFans.cn收集

的顺序满足：8在51前面；90在87的后面；20在14的后面；25在6的前面；19在90的后面。（ A）20，6，8，51，90，25，14，19，87 B）51，6，19，20，14，8，87，90，25 C）19，20，90，7，6，25，51，14，87 D）6，25，51，8，20，19，90，87，14 E）25，6，8，51，87，90，19，14，20

[03]20. 假设我们用d=(a1,a2,...,a5),表示无向图G的5个顶点的度数，下面给出的哪（些）组d 值合理（ A）{5，4，4，3，1} B）{4，2，2，1，1} C）{3，3，3，2，2} D）{5，4，3，2，1} E）{2，2，2，2，2}

5

）。 ）。

单项选择题

[10]7 C [07]2 E [03]6 B B [10]9 C [07]7 D B D [09]4 B [07]9 D C D [09]5 D [06]7 C B D [09]6 B [06]8 B C [09]7 B [05]4 E B

[09]9 A [05]5 D C [08]4 C [04]3 E B [08]6 D [04]4 C C [08]11 E [04]5 B B [03]5 B D [02]16 [02]17 [02]18 [02]19 [02]20 [01]13 [01]17 [01]18 [01]19 [01]20 [00]12 [00]17 [00]18 [98]10 不定项选择题 [10]1 ACD [08]16 ABD [07]14 ABD

[10]5 B [08]18 ABC [06]13 C [10]7 D [06]14 BC [10]9 BCD [05]13 BC [09]6 ABD [05]14 CE [09]7 AC [03]19 D [09]8 ABC [03]20 BE 6