初赛基础知识题讲解(数据结构)课件

信息学奥林匹克分区联赛的初赛知识

——数据结构篇信息学奥林匹克——数据结构篇1、一个高度为h的二叉树最小元素数目是（

）。

A）2h+1

B）h

C）2h-1

D）2h

E）2h-1B2、一个向量第一个元素的存储地址是100,每个元素的长度是2,则第5个元素的地址是()。A)110B)108C)100D)109B1、一个高度为h的二叉树最小元素数目是（

数组A[3..10,2..10]以行优先的方式存储,每个元素占8个字节,且已知A[4,3]的地址为200,则A[9,6]的地址为:____________。如果以列优先存储,则为:______________。[3,2][4,6]200[9,6][4,10]899994（8+9*4+4）*8+200=584数组A[3..10,2..10]以行优先的方式存储,每个元素数组A[3..10,2..10]以行优先的方式存储,每个元素占8个字节,且已知A[4,3]的地址为200,则A[9,6]的地址为:____________。如果以列优先存储,则为:______________。数组A[2..10,3..10]200a[3,4]a[6,9]432数组A[3..10,2..10]以行优先的方式存储,每个元素数组A[0..5,0..6]的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（）。

A.1175

B.1180

C.1205

D.1210

E.1190

a[3,4]的地址是多少（）答：A。＝[(5-0+1)*(5-0)+(5-0)]*5+1000=35*5+1000=1175；若求A[3,4]=[(5-0+1)*(3-0)+(4-0)]*5+1000数组A[0..5,0..6]的每个元素占5个单元，将其按列优3、设有一个含有13个元素的Hash表(0~12),Hash函数是:H(key)=key%13,其中%是求余数运算。用线性探查法解决冲突,则对于序列(2、８、31、20、19、18、53、27),18应放在第几号格中()。A)5B)9C)4D)0B012345678910111228312019185327解答过程：2、8、31、20、19、18、53、272mod13=2，所以2放第2格8mod13=8，所以8放第8格31mod13=5，所以31放第5格20mod13=7，所以20放第7格19mod13=6，所以19放第6格18mod13=5，18放第5格，第5格被占，放第6格，也被占，放第7格，还是被占，放第8格，仍然被占，所以放第9格3、设有一个含有13个元素的Hash表(0~12),Hash4.设有一个含有13个元素的Hash表(0~12),Hash函数是:H(key)=key%13,其中%是求余数运算。用二次探查法解决冲突,则对于序列(８、31、20、33、18、53、27),则下列说法正确的是(BCDE)。A)27在1号格子中B)33在6号格子中

C)31在5号格子中D)20在7号格子中E)18在4号格子中0123456789101112831203318538、31、20、33、18、53、27

8mod13=8，所以8放第8格31mod13=5，所以31放第5格20mod13=7，所以20放第7格33

mod13=7，33放第7格，但是第7格被占，放第8格，也被占，所以放第6格18mod13=5，18放第5格，但是第5格被占，放第6格，也被占，所以放第4格53mod13=1，所以53放第1格27

mod13=1，27放第1格，但是第1格被占，所以放第2格

总上所述，选BCDE

274.设有一个含有13个元素的Hash表(0~12),Has5、按照二叉树的定义,具有3个结点的二叉树有()种。A)3B)4C)5D)6C6、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的()倍。A)1/2B)1C)2D)4B7、要使1...8号格子的访问顺序为:8、2、6、5、7、3、1、4,则下图中的空格中应填入()。12345678461-1732A)6B)OC)5D)3C5、按照二叉树的定义,具有3个结点的二叉树有(8、设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若出队的顺序为e2,e4,e3,e6,e5,e1,则栈S的容量至少应该为()。A)2B)3C)4D)5B9、设有一棵k叉树,其中只有度为0和k两种结点,设n0,nk分别表示度为0和度为k的结点个数,试求出n0,nk之间的关系(n0=数学表达式,数学表达式仅含nk,k和数字)N0=(K－1)Nk+110、若已知一个栈的入栈顺序是1，2，3，…，n，其输出序列为P1，P2，P3，…，Pn，若P1是n，则Pi是()

A)i

B)n-1

C)n-i+1

D)不确定C8、设栈S和队列Q的初始状态为空,元素e1,e2,e3,e411、以下哪一个不是栈的基本运算()

A)删除栈顶元素B)删除栈底的元素

C)判断栈是否为空D)将栈置为空栈B12、下面关于算法的错误说法是()

A)算法必须有输出B)算法必须在计算机上用某种语言实现

C)算法不一定有输入D)算法必须在有限步执行后能结束B13、在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的关键码比较的次数为()

A)2

B)3

C)4

D)5C14、一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有()个结点

A)2h-1

B)2h-1

C)2h+1

D)h+1B11、以下哪一个不是栈的基本运算()B115、无向图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,cDABCDEF从A点出发，以ABCDEF的顺序进行扩展15、无向图G=(V，E)，其中V={a,b,c,d,e,f16、已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为：ABCEGDFHIJ17、在有N个叶子节点的哈夫曼树中，其节点总数为（）A.不确定B.2N-1

C.2N+1

D.2NB假设有6个权值分别为{5,29,7,8,14,23,3,11}的结点为叶结点，构造出一棵最优二叉树（哈夫曼树）。３０4560Wpl=30*1+60*2+45*2例最优二叉树即要wpl的值达到最小。16、已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历第一步：以这8个权值作为根结点的权值构造具有8棵树的森林529781423311第二步：从中选择两个根的权值最小的树3，5作为左右子树构造一棵新树，并将这两棵树从森林中删除，并将新树添加进去3529781423118第一步：以这8个权值作为根结点的权值构造具有8棵树的森林5第三步：重复第二步过程，直到森林中只有一棵树为止选择7，8291423117815358291423

78158351911第三步：重复第二步过程，直到森林中只有一棵树为止29选择8，11选择14，15选择19，23352915782914842231911选择8，113529157选择29，2978155829291435842231911选择29，297815582929143选择42，5810078155829291435842231911选择42，5810078155829１８、某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索（binary-search），在最坏的情况下，需检视（）个单元。A.1000

B.10

C.100

D.500Bconstn=15;vara:array[1..n]ofinteger;mid,top,bot,x,i:integer;find:boolean;beginfori:=1tondoread(a[i]);readln;readln(x);top:=1;bot:=n;find:=false;while(top<=bot)andnot(find)do

beginmid:=(top+bot)div2;if(x=a[mid])thenfind:=trueelseif(x<a[mid])thenbot:=mid-1elsetop:=mid+1;end;iffindthenwriteln(x,'at',mid:6)elsewriteln('notfound!');end.１８、某数列有1000个各不相同的单元，由低至高按序排列；现19、线性表若采用链表存贮结构，要求内存中可用存贮单元地址（）A.必须连续B.部分地址必须连续C.一定不连续D.连续不连续均可D２０、下列叙述中，正确的是（）A.线性表的线性存贮结构优于链表存贮结构B.队列的操作方式是先进后出C.栈的操作方式是先进先出D.二维数组是指它的每个数据元素为一个线性表的线性表D２１、已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。5种abcabcabcabcbac19、线性表若采用链表存贮结构，要求内存中可用存贮单元地址（22.（1998年初中组）设栈S的初始状态为空,现有5个元素组成的序列{1,2,3,4,5},对该序列在S栈上依次进行如下操作(从序列中的1开始,出栈后不在进栈):进栈,进栈,进栈,出栈,进栈,出栈,进栈,问出栈的元素序列是:_________,栈顶指针的值为______，栈顶元素为:___________________。

解答：出栈序列为{3，4}，栈顶指针值为3，栈顶元素为5。考查了数据结构中的栈。还可以把栈和队列结合起来考！如下题

22.（1998年初中组）设栈S的初始状态为空,现有5个元素23．如2002年高中组：设栈S和队列Q初始状态为空，元素e1，e2，e3，e4，e5，e6依次通过栈S，一个元素出栈后即进入队列Q，若出队顺序为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该为______________。

解答：为3。补充队知识点23．如2002年高中组：设栈S和队列Q初始状态为空，元素e24．（2000年初中组）设循环队列中数组的下标范围是1..n，其头尾指针分别为f和r，则其元素个数为：_____________________。

解答：（r-f+n）modn演示24．（2000年初中组）设循环队列中数组的下标范围是1..25.（1998年高中组）给出一棵二叉树的中序遍历:DBGEACHFI与后序遍历:DGEBHIFCA,画出此二叉树。ABCDEBFHI25.（1998年高中组）给出一棵二叉树的中序遍历:DBGE26.（1996年高中组）下面是一个利用完全二叉树特性,用顺序表来存储的一个二叉树,结点数据为字符型(结点层次从小到大,同一层从左到右顺序存储,#表示空结点,@表示存储数据结束)。结点123456789101112131415数据ABC##DE#####GF@请画出对应的二叉树。26.（1996年高中组）下面是一个利用完全二叉树特性,用顺27.（1999年初中组）在磁盘的目录结构中，我们将与某个子目录有关联的目录数称为度。例如下图该图表达了A盘的目录结构：D1，Dll，…，D2均表示子目录的名字。在这里，根目录的度为2，D1子目录的度为3，D11子目录的度为4，D12，D2，D111，D112，D113的度均为1。不考虑子目录的名字，则可简单的图示为如下所示的树结构：若知道一个磁盘的目录结构中，度为2的子目录有2个，度为3的子目录有1个，度为4的子目录有3个。试问：度为1的子目录有几个？

总度数=边的两倍边=总结点数-1总度数=2(总结点数-1)27.（1999年初中组）在磁盘的目录结构中，我们将与某个子28．（2000年高中组）设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1+1,1+2,2+1,3。解答：F（1）＝1

F（2）＝2

F（3）＝4

F（N）＝F（N－3）＋F（N－2）＋F（N－1）（N≥4）28．（2000年高中组）设有一个共有n级的楼梯，某人每步可29、表达式(1+34)*5-56/7的后缀表达式为（

）。

A）1+34*5-56/7

B）-*+1345/567

C）134+5*567/-

D）1345*+567/-

E）134+5567-*/C30、已知元素（8，25，14，87，51，90，6，19，20），问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足：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，20D29、表达式(1+34)*5-56/7的后缀表达式为（

31、下列关于程序语言的叙述，不正确的是()。A)编写机器代码不比编写汇编代码容易。

B)高级语言需要编译成目标代码或通过解释器解释后才能被CPU执行。

C)同样一段高级语言程序通过不同的编译器可能产生不同的可执行程序。

D)汇编代码可被CPU直接运行。

E)不同的高级语言语法略有不同。32、下列哪个程序设计语言不支持面向对象程序设计方法（）。A.C++B.ObjectPascalC.CD.SmalltalkE.JavaDC31、下列关于程序语言的叙述，不正确的是()。33、二叉树T，已知其前序遍历序列为1243576，中序遍历序列为4215736，则其后序遍历序列为（）。A.4257631B.4275631C.4275361D