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

1、信息学奥林匹克信息学奥林匹克分区联赛的初赛知识分区联赛的初赛知识 数据结构篇数据结构篇1、一个高度为h 的二叉树最小元素数目是（）。A）2h+1 B）h C）2h-1 D）2h E）2h-1B2、一个向量第一个元素的存储地址是100,每个元素的长度是2,则第5个元素的地址是()。A)110 B)108 C)100 D)109B数组A3.10,2.10以行优先的方式存储,每个元素占8个字节,且已知A4,3的地址为200,则A9,6的地址为:_。如果以列优先存储,则为:_。3,24,62009,64,10899994（8+9*4+4）*8+200=584数组A3.10,2.10以行优先的方式存储,

2、每个元素占8个字节,且已知A4,3的地址为200,则A9,6的地址为:_。如果以列优先存储,则为:_。数组数组A2.10,3.10200 a3,4 a6,9432数组A0.5,0.6的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续的内存单元中，则元素A5,5的地址为（）。A.1175B.1180C.1205D.1210 E.1190 a3,4的地址是多少（）答：A。(5-0+1)*(5-0)+(5-0)*5+1000=35*5+1000=1175；若求；若求A3,4=(5-0+1)*(3-0)+(4-0)*5+10003、设有一个含有13个元素的Hash表(012),Has

3、h函数是:H(key)=key%13,其中%是求余数运算。用线性探查法解决冲突,则对于序列(2、31、20、19、18、53、27),18应放在第几号格中()。A)5 B)9 C)4 D)0B012345678910111228312019185327解答过程：2、8、31、20、19、18、53、272 mod 13=2，所以2放第2格8 mod 13=8，所以8放第8格31 mod 13=5，所以31放第5格20 mod 13=7，所以20放第7格19 mod 13=6，所以19放第6格18 mod 13=5，18放第5格，第5格被占，放第6格，也被占，放第7格，还是被占，放第8格，仍然被

4、占，所以放第9格4.设有一个含有13个元素的Hash表(012),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 8 mod 13=8，所以8放第8格31 mod 13=5，所以31放第5格20 mod 13=7，所以20放第7格33 mod 13=7，33放第7格，但是第

5、7格被占，放第8格，也被占，所以放第6格18 mod 13=5，18放第5格，但是第5格被占，放第6格，也被占，所以放第4格53 mod 13=1，所以53放第1格27 mod 13=1，27放第1格，但是第1格被占，所以放第2格 总上所述，选BCDE275、按照二叉树的定义,具有3个结点的二叉树有()种。A)3 B)4 C)5 D)6C6、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的()倍。A)1/2 B)1 C)2 D)4B7、要使1.8号格子的访问顺序为:8、2、6、5、7、3、1、4,则下图中的空格中应填入()。12345678461-1732A)6 B)O C)5 D)

6、3C8、设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若出队的顺序为e2,e4,e3,e6,e5,e1,则栈S的容量至少应该为()。A)2 B)3 C)4 D)5B9、设有一棵k叉树,其中只有度为0和k两种结点,设n0,nk分别表示度为0和度为k的结点个数,试求出n0,nk之间的关系(n0=数学表达式,数学表达式仅含nk,k和数字)N0=(K1)Nk+110、若已知一个栈的入栈顺序是1，2，3，n，其输出序列为P1，P2，P3，Pn，若P1是n，则Pi是()A)i B)n-1 C)n-i+1 D)不确定C11、以下哪一个不是栈的基

7、本运算()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+1B15、无向图G=(V，E)，其中V=a,b,c,d,e,f E=(a,b),(a

8、,e),(a,c),(b,e),(c,f),(f,d),(e,d)对该图进行深度优先遍历,得到的顶点序列正确的是()A)a,b,e,c,d,fB)a,c,f,e,b,dC)a,e,b,c,f,dD)a,b,e,d,f,cDABCDEF从A点出发，以ABCDEF的顺序进行扩展16、已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ 与 CGEBHFJIDA则该二叉树的先序遍历的顺序为：ABCEGDFHIJ17、在有N个叶子节点的哈夫曼树中，其节点总数为（）A.不确定B.2N-1C.2N+1D.2NB4560Wpl=30*1+60*2+45*2例最优二叉树即要

9、wpl的值达到最小。5 29 7 8 14 23 3 11第二步：从中选择两个根的权值最小的树第二步：从中选择两个根的权值最小的树3，5作为左右子树构造作为左右子树构造一棵新树，并将这两棵树从森林中删除，并将新树添加进去一棵新树，并将这两棵树从森林中删除，并将新树添加进去3 529 7 8 14 23 118n第三步：重复第二步过程，直到森林中只有一棵树第三步：重复第二步过程，直到森林中只有一棵树为止为止n选择选择7，829 14 23 117 8153 5829 14 23 7 81583 51911n选择选择8，11n选择选择14，15n选择选择19，233 5 29 157 829148

10、42231911n选择29，297 815582929143 5842231911n选择42，581007 815582929143 5842231911、某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索（binary-search），在最坏的情况下，需检视（）个单元。A.1000B.10C.100D.500B const n=15;var a:array1.n of integer;mid,top,bot,x,i:integer;find:boolean;begin for i:=1 to n do read(ai);readln;readln(x);top:=

11、1;bot:=n;find:=false;while(top=bot)and not(find)do begin mid:=(top+bot)div 2;if(x=amid)then find:=true else if(xamid)then bot:=mid-1 else top:=mid+1;end;if find then writeln(x,at,mid:6)else writeln(not found!);end.19、线性表若采用链表存贮结构，要求内存中可用存贮单元地址（）A.必须连续B.部分地址必须连续C.一定不连续D.连续不连续均可D、下列叙述中，正确的是（）A.线性表的线性存

12、贮结构优于链表存贮结构B.队列的操作方式是先进后出C.栈的操作方式是先进先出D.二维数组是指它的每个数据元素为一个线性表的线性表D、已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。5种种abcabcabcabcbac22.（1998年初中组）设栈S的初始状态为空,现有5个元素组成的序列1,2,3,4,5,对该序列在S 栈上依次进行如下操作(从序列中的1开始,出栈后不在进栈):进栈,进栈,进栈,出栈,进栈,出栈,进栈,问出栈的元素序列是:_,栈顶指针的值为_，栈顶元素为:_。解答：出栈序列为3，4，栈顶指针值为3，栈顶元素为5。考查了数据

13、结构中的栈。还可以把栈和队列结合起来考！如下题 23如2002年高中组：设栈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的容量至少应该为_。解答：为3。补充队知识点24（2000年初中组）设循环队列中数组的下标范围是1.n，其头尾指针分别为f和r，则其元素个数为：_。解答：（r-f+n）mod n演示25.（1998年高中组）给出一棵二叉树的中序遍历:DBGEACHFI与后序遍历:DGEBHIFCA,画出此二叉树。ABCDEBFHI26.（1996年高中组）

14、下面是一个利用完全二叉树特性,用顺序表来存储的一个二叉树,结点数据为字符型(结点层次从小到大,同一层从左到右顺序存储,#表示空结点,表示存储数据结束)。结点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15数据 A B C#D E#G F 请画出对应的二叉树。27.（1999年初中组）在磁盘的目录结构中，我们将与某个子目录有关联的目录数称为度。例如下图该图表达了A盘的目录结构：D1，Dll，D2均表示子目录的名字。在这里，根目录的度为2，D1子目录的度为3，D11子目录的度为4，D12，D2，D111，D112，D113的度均为1。不考虑子目录的名字，则可简单的图示为如下

15、所示的树结构：若知道一个磁盘的目录结构中，度为2的子目录有2个，度为3的子目录有1个，度为4的子目录有3个。试问：度为1的子目录有几个？总度数=边的两倍边=总结点数-1总度数=2(总结点数-1)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（N3）F（N2）F（N1）（N4）29、表达式(1+34)*5-56/7 的后缀表达式为（）。A）1+34*5-56/7 B）-*+1 34 5/5

16、6 7 C）1 34+5*56 7/-D）1 34 5*+56 7/-E）1 34+5 56 7-*/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

17、，14，20D31、下列关于程序语言的叙述，不正确的是()。A)编写机器代码不比编写汇编代码容易。B)高级语言需要编译成目标代码或通过解释器解释后才能被CPU执行。C)同样一段高级语言程序通过不同的编译器可能产生不同的可执行程序。D)汇编代码可被CPU直接运行。E)不同的高级语言语法略有不同。32、下列哪个程序设计语言不支持面向对象程序设计方法（）。A.C+B.Object Pascal C.C D.Smalltalk E.JavaDC33、二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为（）。A.4 2 5 7 6 3 1

18、 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 1B34、满二叉树的叶结点个数为N，则它的结点总数为（）。A.N B.2*N C.2*N 1 D.2*N+1 E.2N 1C假设些二叉树树高为h，则叶结点数n=2h-1而所有的结点为2h-135、完全二叉树的结点个数为4*N+3，则它的叶结点个数为（）。A.2*N B.2*N-1 C.2*N+1 D.2*N-2 E.2*N+2E36、二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D 是G 的父结点，F 是I 的父结点，树中所有结点的

19、最大深度为3（根结点深度设为0），可知F的父结点是（）。A.无法确定 B.B C.C D.D E.EC37、在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是()。A)希尔排序 B)起泡排序 C)插入排序 D)选择排序BD插入排序、冒泡排序、归并排序、基数排序是稳定排序选择排序、希尔排序、快速排序、堆排序是不稳定的希尔排序：是直接插入排序的改进，是一个不稳定的排序方法。快速排序：是一个不稳定的排序方法，当待排的记录已经排好后快排反而慢。稳定性：通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai=Aj,Ai原来在位置前，排序后Ai还是要在Aj位置前。5 8 5 2 9 祝您成功！祝您成功！