初赛第二课习题

您的姓名：*

111、算法是指( )*

A．为解决问题而编写的计算机程序

B．为解决问题而采取的方法与步骤

C．为解决问题而需要采用的计算机语言

D．为解决问题而采用的计算方法

112、设栈S的初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在S栈上依次进行如下操作(从序列中的1开始，出栈后不再进栈):进栈、进栈、进栈、出栈、进栈、出栈、进栈。试问出栈的元素序列是( )*

A．{5，4，3，2，1}

B．{2，1}

C．{2，3}

D．{3，4}

113、设循环队列中数组的下标范围是n，其中头尾指针分别是f和r，则其元素个数是( )*

A．r-f

B．r-f+1

C．(r-f) MOD n+1

D．(r-f+n) MOD n

114、在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是( )*

A．堆排序

B．希尔排序

C．冒泡排序

D．快速排序

115、在有n个子叶节点的哈夫曼树中，其节点总数为( )*

A．不确定

B．2n-1

C．2n+1

D．2n

116、某数列有1000个各不相同的单元，由低到高按序排列，现要对该数列进行二分法检索，在最坏的情况下，需要检视( )个单元( )*

A．1000

B．10

C．100

D．500

117、已知数组A中，每个元素A[I，J]在存储时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存储分配的。试问:A[5，8]的起始地址为( )*

A．SA+141

B．SA+180

C．SA+222

D．SA+225

118、线性表若采用链表存储结构，要求内存中可用存储单元地址( )*

A．必须连续

B．部分地址必须连续

C．一定不连续

D．连续不连续均可

119、下列叙述中，正确的是( )*

A．线性表的线性存储结构优于链表存储结构

B．队列的操作方式是先进后出

C．栈的操作方式是先进先出

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

120、电线上停着两种鸟(A，B)，可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可公为两类:一类是两端的小鸟相同;另一类是两端的小鸟不相同。已知:电线上两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是( )*

A．奇数

B．偶数

C．可奇可偶

D．数目固定

121、在列车转辙网络中，有四个车皮编号为1，2，3，4，并按此顺序送入栈中进行调度，这些车皮取出的顺序是( )*

A．4123

B．3241

C．3412

D．4312

122、从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端，这种排序方法称为( )*

A．插入排序

B．归并排序

C．选择排序

D．快速排序

123、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于( )数据结构( )*

A．栈

B．树

C．双向队列

D．广义表

124、使用双向链表存放数据的优点是( )*

A．提高检索速度

B．很方便地插入和删除数据

C．节约存储空间

D．很快回收存储空间

125、对一个满二叉树，m个树叶，l分枝结点，n个结点，则( )*

A．n=l+m

B．l+m=2n

C．m=l-1

D．n=2l-1

126、一维数组与线性表的区别是( )*

A．前者长度固定，后者长度可变

B．后者长度固定，前者长度可变

C．两者长度均固定

D．两者长度均可变

127、用某种排序方法对线性表25,84,21,47,15,27,68,35,20进行排序，结点变化如下:(1)25,84,21,47,15,27,68,35,20;(2)20,15,21,25,47,27,68,35,84;(3)15,20,21,25,35,27,47,68,84;(4)15,20,21,25,27,35,47,68,84.那么，排序方法是( )*

A．选择排序

B．希尔排序

C．合并排序

D．快速排序

128、具有12个记录的序列，采用冒泡排序最少的比较次数是( )*

A．1

B．144

C．11

D．66

129、下面关于二叉树的叙述正确的是( )*

A．一棵二叉树中叶子结点的个数等于度为2的结点个数加1

B．一棵二又树中的结点个数大于0

C．二叉树中任何一个结点要么是叶，要么恰有两个子女

D．二叉树中，任何一个结点的左子树和右子树上的结点个数一定相等

130、先序序列和中序序列相同的二叉树为空树或( )*

A．任一结点均无右孩子的非空二叉树

B．仅有两个结点的二叉树

C．任一结点均无左孩子的非空二叉树

D．不存在这样的二叉树

131、设有三个元素A、B、C顺序进栈，在进栈过程中可以出栈，出栈次序错误的排列是( )*

A．ABC

B．BCA

C．CAB

D．CBA

132、下面四种内排序方法中，要求内存容量最大的是( )*

A．插入排序

B．选择排序

C．快速排序

D．归并排序

133、设有序列F:（49，38，65，97，76，13，27，50），使用快速排序法，其趟数为( )*

A．3

B．2

C．1

D．4

134、给出一组整型数28、10、37、63、35、30、23，请用二叉树对它进行排序。为此，首先要生成一棵二叉树，规则是把第一数放在根处，接着凡比它小的数放在左子树，比它大的数放在右子树，直到把所有的数均安排好。然后对此二叉树进行( )，得到的就是按照升序排列好的序列。*

A．前序遍历

B．中序遍历

C．后序遍历

D．横向遍历

135、用某种排序方法对线性表(84,47,25,15,21)进行排序时，结点序列的变化如下: (1)84,47,25,15,21;(2)15,47,25,84,21;(3)15,21,25,84,47;(4)15,21,25,47,84.那么，所采用的排序方法是( )*

A．选择排序

B．冒泡排序

C．插入排序

D．快速排序

136、设二叉树根结点的层次为0，一棵高度为*

B的满二叉树中结点的个数是( )

A．2^B

B．2^(B-1)

C．2^B-1

D．2^(B+1)-1

137、深度为5的二叉树至多有( )个结点*

A．16

B．32

C．31

D．10

138、下面关于线性表的描述，错误的是( )*

A．栈是线性表的一种

B．任给一个索引I（1<=I<=表中元素个数），就能在线性表中唯一确定一个元素

C．线性表的任一元素都有前驱和后继

D．线性表是一个线性序列

139、带权路径长度最小的二叉树是( )*

A．顺序二叉树

B．二叉排序树

C．判定树

D．哈夫曼树

140、有12个结点的平衡二叉树的最大深度是( )*

A．4

B．5

C．6

D．3

141、若用冒泡排序法对序列18，14，6，27，8，12，16，52，10，26，47，29，41，24从小到大进行排序，共要进行( )次比较。*

A．33

B．45

C．70

D．91

142、设n，m为某二叉树上的两个结点，在中序遍历时，n在m前的条件是( )*

A．n在m右方

B．n是m祖先

C．n在m左方

D．n是m子孙

143、下列四种排序方法，如果被排序的序列中诸元素恰好已经按要求（由小到大或由大到小排序，就元素的比较次数和移动次数而言，哪种方法最少?( )*

A．冒泡排序

B．直接选择排序

C．直接插入排序

D．归并排序

144、如果某二叉树的前序为STUWV，中序为UWTVS，那么该二叉树的后序是( )*

A．WUVTS

B．UWVTS

C．VWUTS

D．WUTSV

145、按照二叉树的定义，具有3个结点的二叉树有( )*

A．3种

B．4种

C．5种

D．6种

146、对以下关键字序列用快速排序法进行排序，速度最慢的情况是( )*

A．{19，23，3，15，7，21，8}

B．{23，21，28，15，19，3，7}

C．{19，7，15，28，23，21，3}

D．{3，7，15，19，21，23，28}

147、数组A中，每个元素A[I，j]的长度为3个字节，行下标I为1到8，列下标j从1到10。从首地址SA开始连续存放在存储器中，存放该数组至少需要的单元数是( )*

A．80

B．100

C．240

D．270

148、树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。正确的结论是( )*

A．树的先根遍历序列与其对应的二叉树的先序遍历序列相同

B．树的先根遍历序列与其对应的二叉树的中序遍历序列相同

C．树的后根遍历序列与其对应的二叉树的先序遍历序列相同

D．树的后根遍历序列与其对应的二叉树的后序遍历序列相同

149、在数据结构中，从逻辑上可以把数据结构分成( )*

A．动态结构和静态结构

B．线性结构和非线性结构

C．内部结构和外部结构

D．紧凑结构和非紧凑结构

150、如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的( )*

A．前序

B．中序

C．后序

D．层次序

151、某二叉树的前序遍历结点访问顺序是aBDgCefh，中序遍历的结点访问顺序是DgBaeChf，则其后序遍历的结点访问顺序是( )*

A．BDgCefha

B．gDBeCfha

C．BDgaeChf

D．gDBehfCa

152、从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端，这种排序方法称为( )*

A．插入排序

B．选择排序

C．归并排序

D．快速排序

153、快速排序方法在( )情况下最不利于发挥其长处*

A．被排序的数据量太大

B．被排序数据中含有多个相同值

C．被排序数据已基本有序

D．被排序数据数目为奇

154、下面关于数据结构的叙述中，正确的叙述是( )*

A．顺序存储方式的优点是存储密度大，且插入、删除运算效率高

B．链表中的每一个结点都包含一个指针

C．包含n个结点的二叉排序树的最大检索长度为log\-2n

D．将一棵树转换为二又树后，根结点没有右子树

155、在计算机科学领域中,算法分为两类:数值型算法和非数值型算法。下面的算法，哪一个属于数值算法类( )*

A．迭代法

B．冒泡法

C．黑盒法

D．杂凑（Hash）法

156、若已知一个栈的输入序列为1，2，3…，n，其输出序列为P1，P2，…，Pn。若P1=n，则Pi为( )*

A．I

B．n+I

C．n-I+1

D．不确定

157、带头结点的单链表HeaD为空的判定条件是( )*

A．HeaD=NIL

B．HeaD^.Next=NIL

C．HeaD^.Next=HeaD

D．HeaD=HeaD

158、二维数组a的成员是6个字符组成的串，行下标I的范围从0到8，列下标j的范围从1到10，则存放a至少需要( )个字节*

A．90

B．180

C．240

D．540

159、由3个结点可以构造出多少种不同的有向树( )*

A．2

B．3

C．4

D．5

160、二维数组M[I，j]的元素是4个字符（每个字符占一个存储单元）组成的串，行下标I的范围从0到4，列下标j的范围从0到5。M按行存储元素M[3，5]的起始地址与M按列存储时元素( )的起始地址相同。*

A．m[2,4]

B．m[3,4]

C．m[3,5]

D．m[4,4]

161、判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用( )*

A．求关键路径的方法

B．求最短路径的方法

C．广度优先遍历方法

D．深度优先遍历方法

162、在一非空二叉树的中序遍历序列中，根结点的右边( )*

A．只有右子树上的所有结点

B．只有右子树上的部分结点

C．只有左子树上的所有结点

D．只有左子树上的部分结点

163、一个队列的入列序列是1，2，3，4，则队列的输出序列是( )*

A．4，3，2，1

B．1，2，3，4

C．1，4，3，2

D．3，2，4，1

164、邻接表存储结构下图的深度优先遍历算法结构类似于二叉树的( )*

A．先序遍历

B．中序遍历

C．后序遍历

D．按层遍历

165、设待排序的记录为(20,16,13,14,19)，经过下列过程将这些记录排序:(1)20,16,13,14,19;(2)16,20,13,14,19;(3)13,16,20,14,19;(4)13,14,16,20,19;(5)13,14,16,19,20.所用的排序方法是( )*

A．直接插入排序

B．冒泡排序

C．希尔排序

D．堆排序

166、计算机算法一般被划分为数值算法和非数值算法两大类，下列叙述中，哪个不属于数值算法( )*

A．迭代法

B．直接法

C．杂凑（Hash）法

D．消去法

167、用归并排序方法对线性表（49，38，65，97，76，13，27，49，55，04）进行排序时，其第三趟的排序结果为( )*

A．12，27，38，49，49，65，76，97，04，55

B．38，49，65，97，13，27，49，76，04，55

C．38，49，65，97，13，76，27，49，04，55

D．01，13，27，38，49，49，55，65，76，97

168、栈和队列都是( )*

A．顺序存储的线性结构

B．链式存储的非线性结构

C．限制存取点的线性结构

D．限制存取点的非线性结构

169、对N个结点的线性表进行查找，用顺序查找的时间复杂性为( )*

A．N*N

B．Nlog2n

C．n

D．log2n

170、若进栈序列为1，2，3．4假定进栈和出栈可以穿插进行，则可能的出栈序列是( )*

A．2，4，1，3

B．3，1，4，2

C．3，4，1，2

D．1，2，3，4

171、设计一个判别表达式中左、右括号是否配对的算法，采用( )数据结构最佳( )*

A．线性表的顺序存储结构

B．栈

C．队列

D．线性表的链式存储结构

172、设一棵二叉树，其叶子结点分别带权10，12，4，7，5，18，2则其带权路径长度最小为( )*

A．120

B．130

C．140

D．150

173、以下关于数据结构的叙述，正确的是( )*

A．线性表的线性存储结构优于链式结构

B．二叉树的第I层上有2的（I-1）次幂个结点，深度为K的二叉树上有2的（k-1）次幂个结点

C．二维数组是其数据元素为线性表的线性表

D．栈的操作方式是先进先出

174、循环队列用数组A[0…m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是( )*

A．（rear-front+m）MOD m

B．rear-front-1

C．rear-front+1

D．rear-front

175、把一般树转化为二叉树的方法是:对每一结点的子树，在其根之间加水平连线，然后仅保留( )而抹掉该结点和其它子树之间的连线，最后以树的根结点为轴，将树顺时针转45度即可*

A．最右子树

B．右子树

C．左子树

D．最左子树

176、下列哪一种图的邻接矩阵是对称矩阵( )*

A．有向图

B．无向图

C．AOV网

D．AOE网

177、计算机算法必须具备的三个特性是( )*

A．可执行性、可移植性和可扩充性

B．可执行性、确定性和有穷性

C．确定性、有穷性和稳定性

D．易读性、稳定性和安全性

178、对长度为10的有序表进行折半查找，设在等概率时查找成功的平均查找长度是( )*

A．2.9

B．3.1

C．3.4

D．2.6

179、设有6个结点的无向图，该图至少应该有( )条边才能确保是一个连通图( )*

A．5

B．6

C．7

D．8

180、有6个元素按6，5，4，3，2．1的顺序进栈，问下列哪一个不是合法的出栈序列( )*

A．5，4，3，6，1，2

B．4，5，3，1，2，6

C．3，4，6，5，2，1

D．2，3，1，4，5，6

181.设全集I = {a, B, C, D, e, f, g}，集合A = {a, B, C}，B = {B, D, e}，C = {e, f, g}，那么集合为（ ）。*

A. {a, B, C, D}

B. {a, B, D, e}

C. {B, D, e}

D. {B, C, D, e}

E. {D, f, g}

182.由3个a，5个B和2个C构成的所有字符串中，包含子串“aBC”的共有（ ）个。*

A. 40320

B. 39600

C. 840

D. 780

E. 60

183.某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为:“进，出，进，进，出，进，进，进，出，出，进，出”。假设车辆入站的顺序为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

184.满二叉树的叶结点个数为N，则它的结点总数为（ ）。*

A. N

B. 2 * N

C. 2 * N – 1

D. 2 * N + 1

E. 2N – 1

185.二叉树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

186.十进制数100.625等值于二进制数（ ）。*

A. 1001100.101

B. 1100100.101

C. 1100100.011

D. 1001100.11

E. 1001100.01

187.下面哪个部件对于个人桌面电脑的正常运行不是必需的（ ）。*

A.CPU

B.图形卡（显卡）

C. 光驱

D. 主板

E. 内存

188.下列哪个网络上常用的名字缩写是错误的（ ）。*

A. WWW（WorlD WiDe WeB）

B. URL（Uniform ResourCe LoCator）

C. HTTP（Hypertext Transfer Protool）

D. FTP（Fast Transfer Protool）

E.TCP（Transfer Control ProtoCol）。

189.用静电吸附墨粉后转移到纸张上，是哪种输出设备的工作方式（ ）。*

A. 针式打印机

B. 喷墨打印机

C. 激光打印机

D. 笔式绘图仪

E. 喷墨绘图仪

190.一台计算机如果要利用电话线上网，就必须配置能够对数字信号和模拟信号进行相互转换的设备，这种设备是（ ）。*

A. 调制解调器

B. 路由器

C. 网卡

D. 网关

E. 网桥

191.  图灵 (Alan Turing) 是 （      ）。*

A） 美国人

B） 英国人

C） 德国人

D） 匈牙利人

E） 法国人

192.  第一个给计算机写程序的人是（      ）。*

A） Alan Mathison Turing

B） ADa LovelaCe

C） John von Neumann

D） John MC-Carthy

E） EDsger WyBeDijkstra

193.  十进制数2003等值于二进制数（      ）。*

A） 0100000111

B） 10000011

C） 110000111

D） 11111010011

E） 1111010011

194.  假设A=true,B=false,C=ture,D=ture,逻辑运算表达式A∧B∨C∧D的值是（   ）。*

A） ture

B） false

C） 0

D） 1

E） NULL

195.  一个高度为h 的二叉树最小元素数目是（          ）。*

A） 2h+1

B） h

C） 2h-1

D） 2h

E） 2h-1

196.  已知队列（13，2，11，34，41，77，5，7，18，26，15），第一个进入队列的元素是13，则第五个出队列的元素是（         ）。*

A） 5

B） 41

C） 77

D） 13

E） 18

197.  下面一段程序是用（       ）语言书写的。
int funC1(int n){
int i,sum=0;
for(i=1;i<=n;i++)
sum+=i*i;
return sum;        }*

A) FORTRAN

B) PASCAL

C) C

D) PROLOG

E) BASIC

198.  设全集E={1，2，3，4，5}，集合A={1，4}，B={1，2，5}，C={2，4}，则集合（A ∩B）∪~C 为（      ）。*

A） 空集

B） {1}

C） {3，5}

D）{1，5}

E） {1，3，5}

199.  表达式(1+34)*5-56/7 的后缀表达式为（        ）。*

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-*/

200.  下列计算机设备，即是输入设备，又是输出设备的是（       ）。*

A） 键盘

B） 触摸屏

C） 扫描仪

D）投影仪

E） 数字化仪