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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信息学奥林匹克,分区联赛的初赛知识,数据结构篇,信息学奥林匹克数据结构篇,1,、一个高度为,h,的二叉树最小元素数目是（）。,A,）,2h+1 B,）,h C,）,2h-1 D,）,2h E,）,2h-1,B,2,、一个向量第一个元素的存储地址是,100,每个元素的长度是,2,则第,5,个元素的地址是,(),。,A)110 B)108 C)100 D)109,B,1、一个高度为h 的二叉树最小元素数目是（,数组,A3.10,2.10,以行优先的方式存储,每个元素占,8,个字节,且已知,A4,3,的地址为,200,则,A9,6,的地址为,:_,。如果以列优先存储,则为,:_,。,3,2,4,6,200,9,6,4,10,8,9,9,9,9,4,（,8+9*4+4,）*,8+200=584,数组A3.10,2.10以行优先的方式存储,每个元素,数组,A3.10,2.10,以行优先的方式存储,每个元素占,8,个字节,且已知,A4,3,的地址为,200,则,A9,6,的地址为,:_,。如果以列优先存储,则为,:_,。,数组,A2.10,3.10,200 a3,4,a6,9,432,数组A3.10,2.10以行优先的方式存储,每个元素,数组,A0.5,0.6,的每个元素占,5,个单元，将其按列优先次序存储在起始地址为,1000,的连续的内存单元中，则元素,A5,5,的地址为（）。,A.1175,B.1180,C.1205,D.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+1000,数组A0.5,0.6的每个元素占5个单元，将其按列优,3,、设有一个含有,13,个元素的,Hash,表,(012),Hash,函数是,:H(key)=key%13,其中,%,是求余数运算。用线性探查法解决冲突,则对于序列,(2,、,31,、,20,、,19,、,18,、,53,、,27),18,应放在第几号格中,(),。,A)5 B)9 C)4 D)0,B,0,1,2,3,4,5,6,7,8,9,10,11,12,2,8,31,20,19,18,53,27,解答过程：,2,、,8,、,31,、,20,、,19,、,18,、,53,、,27,2 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,格，仍然被占，所以放第,9,格,3、设有一个含有13个元素的Hash表(012),Hash,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,号格子中,0,1,2,3,4,5,6,7,8,9,10,11,12,8,31,20,33,18,53,8,、,31,、,20,、,33,、,18,、,53,、,27,8 mod 13=8,，所以,8,放第,8,格,31 mod 13=5,，所以,31,放第,5,格,20 mod 13=7,，所以,20,放第,7,格,33mod 13=7,，,33,放第,7,格，但是第,7,格被占，放第,8,格，也被占，所以放第,6,格,18 mod 13=5,，,18,放第,5,格，但是第,5,格被占，放第,6,格，也被占，所以放第,4,格,53 mod 13=1,，所以,53,放第,1,格,27mod 13=1,，,27,放第,1,格，但是第,1,格被占，所以放第,2,格,总上所述，选,BCDE,27,4.设有一个含有13个元素的Hash表(012),Has,5,、按照二叉树的定义,具有,3,个结点的二叉树有,(),种。,A)3 B)4 C)5 D)6,C,6,、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的,(),倍。,A)1/2 B)1 C)2 D)4,B,7,、要使,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)O C)5 D)3,C,5、按照二叉树的定义,具有3个结点的二叉树有(,8,、设栈,S,和队列,Q,的初始状态为空,元素,e1,e2,e3,e4,e5,e6,依次通过栈,S,一个元素出栈后即进入队列,Q,若出队的顺序为,e2,e4,e3,e6,e5,e1,则栈,S,的容量至少应该为,(),。,A)2 B)3 C)4 D)5,B,9,、设有一棵,k,叉树,其中只有度为,0,和,k,两种结点,设,n0,nk,分别表示度为,0,和度为,k,的结点个数,试求出,n0,nk,之间的关系,(n0=,数学表达式,数学表达式仅含,nk,k,和数字,),N0=(K,1)Nk+1,10,、若已知一个栈的入栈顺序是,1,，,2,，,3,，,，,n,，其输出序列为,P1,，,P2,，,P3,，,，,Pn,，若,P1,是,n,，则,Pi,是,(),A)i,B)n-1,C)n-i+1,D),不确定,C,8、设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,11,、以下哪一个不是栈的基本运算,(),A),删除栈顶元素,B),删除栈底的元素,C),判断栈是否为空,D),将栈置为空栈,B,12,、下面关于算法的错误说法是,(),A),算法必须有输出,B),算法必须在计算机上用某种语言实现,C),算法不一定有输入,D),算法必须在有限步执行后能结束,B,13,、在顺序表,(2,，,5,，,7,，,10,，,14,，,15,，,18,，,23,，,35,，,41,，,52),中，用二分法查找,12,，所需的关键码比较的次数为,(),A)2,B)3,C)4,D)5,C,14,、一棵二叉树的高度为,h,，所有结点的度为,0,，或为,2,，则此树最少有,(),个结点,A)2h-1,B)2h-1,C)2h+1,D)h+1,B,11、以下哪一个不是栈的基本运算()B1,15,、无向图,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,D,A,B,C,D,E,F,从,A,点出发，以,ABCDEF,的顺序进行扩展,15、无向图G=(V，E)，其中V=a,b,c,d,e,f,16,、已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：,CBGEAFHDIJ,与,CGEBHFJIDA,则该二叉树的先序遍历的顺序为：,ABCEGDFHIJ,17,、在有,N,个叶子节点的哈夫曼树中，其节点总数为（）,A.,不确定,B.2N-1,C.2N+1,D.2N,B,假设有,6,个权值分别为,5,29,7,8,14,23,3,11,的结点为叶结点，构造出一棵最优二叉树（哈夫曼树）。,45,60,Wpl=30*1+60*2+45*2,例,最优二叉树即要,wpl,的值达到最小。,16、已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历,第一步：以这,8,个权值作为根结点的权值构造具有,8,棵树的森林,5 29 7 8 14 23 3 11,第二步：从中选择两个根的权值最小的树,3,，,5,作为左右子树构造一棵新树，并将这两棵树从森林中删除，并将新树添加进去,3 5,29 7 8 14 23 11,8,第一步：以这8个权值作为根结点的权值构造具有8棵树的森林5,第三步：重复第二步过程，直到森林中只有一棵树为止,选择,7,，,8,29 14 23 11,7 8,15,3 5,8,29 14 23,7 8,15,8,3 5,19,11,第三步：重复第二步过程，直到森林中只有一棵树为止29,选择,8,，,11,选择,14,，,15,选择,19,，,23,3 5,29,15,7 8,29,14,8,42,23,19,11,选择8，113 5 29 157,选择,29,，,29,7 8,15,58,29,29,14,3 5,8,42,23,19,11,选择29，297 815582929143,选择,42,，,58,100,7 8,15,58,29,29,14,3 5,8,42,23,19,11,选择42，581007 8155829,、某数列有,1000,个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索（,binary-search,），在最坏的情况下，需检视（）个单元。,A.1000,B.10,C.100,D.500,B,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:=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.,、某数列有1000个各不相同的单元，由低至高按序排列；现,19,、线性表若采用链表存贮结构，要求内存中可用存贮单元地址（）,A.,必须连续,B.,部分地址必须连续,C.,一定不连续,D.,连续不连续均可,D,、下列叙述中，正确的是（）,A.,线性表的线性存贮结构优于链表存贮结构,B.,队列的操作方式是先进后出,C.,栈的操作方式是先进先出,D.,二维数组是指它的每个数据元素为一个线性表的线性表,D,、已知，按中序遍历二叉树的结果为：,abc,问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。,5,种,a,b,c,a,b,c,a,b,c,a,b,c,b,a,c,19、线性表若采用链表存贮结构，要求内存中可用存贮单元地址（,22.,（,1998,年初中组）设栈,S,的初始状态为空,现有,5,个元素组成的序列,1,2,3,4,5,对该序列在,S,栈上依次进行如下操作,(,从序列中的,1,开始,出栈后不在进栈,):,进栈,进栈,进栈,出栈,进栈,出栈,进栈,问出栈的元素序列是,:_,栈顶指针的值为,_,，栈顶元素为,:_,。,解答：出栈序列为,3,，,4,，栈顶指针值为,3,，栈顶元素为,5,。,考查了数据结构中的栈。还可以把栈和队列结合起来考！如下题,22.（1998年初中组）设栈S的初始状态为空,现有5个元素,23,如,2002,年