北邮数据结构1999.docVIP

北京邮电大学99考研题 注意事项： 1.答案一律写在答题纸上； 2.答案应字迹清楚语义贴切 ； 3 .算法应说明基本思路，应对主要数据类型, 变量出说明，所写算法应思路清晰简明易懂，应加必要注释。 4．算法可用pascal语言,c语言等你所熟悉的高级语言编写，但要注明语种。 一、选择填空。 1字符串‘ababaabab’ 的nextval 为（ ）； a(0,1,0,1,04,1,0,1) b(0,1,01,0,2,1,0,1) c(0,1,0,1,0,0,0,1,1) d (0,1,0,1,0,1,1,1 ) 2广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）； head(tail(head(tail(tail(A))))) a(g) b(d) c.c d.d 3输入序列为（A,B,C,D ）,则不可能得到的输出序列有（ ）； a(A,B,C,D) b(D,C,B,A) c(A,C,D,B) d(C,A,D,B ) 4散列函数有一个共同性质即函数值应按（ ） 取其值域的每一个值； a 最大概率 b最小概率 c 同等概率 d 平均概率 5 直接插入序列在最好情况下时间复杂度为（ ）； a O(logn) b O(n) c O(n*logn) d(n2) 二、判断是否正确。（10分） 1（101，88，46，70，34，45，58，66，10）是堆； 2 将一棵树转成二叉树，根结点没有左子树； 3 用树的前序遍历和中序遍历可以导出树的后序遍历； 4 即使不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也应一定相同； 5 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 三、有一个高个比他人至少高一头，找他的人都说根本不用和别人比较，一眼就能看到他。你认为此话正确吗？为什么？请简要描述两种求个数中最大值的方法，并给出所须的最少比较次数。(10分) 四、下面是邻接表的存储图，画出此图，比写出从点c开始按优先深度遍历该图的结果。(10分) 五、 将图中所有有向边按权重从大到小排序为（e1,e2,……em） i:=1 while (所剩边书 =顶点树) begin 从图中删去 ei 若图不再连通，则恢复ei i:=i+1 end. 试证明这个算法生成的图是原图的最小代价生成树。 六、G和G’互为补图（结点相同，边不重叠，两图合并是完整图），试证明G或G’是连通的.(10) 七、(46,88,45,39,70,58,101,10,66,34)建一个排序二叉树，画出该树，并在等概率下查找成功的平均查找长度.(10) 八、(10)。 program ex (input,output); type ttt=Array[1..20] of integer; var l,j,k,l,n:integer; a:ttt; FUNCTION P（VAR a：ttt；var m，n：integer）：integer； VAR x，y，z：integer； begin if n=1 then begin m:=1; p:=a[1]; end else begin x:=n;n:=n-1;y:=P(a,z,n);n:=x if a[n]=y then begin m:=n;P:=a[n] end else begin m:=z;P:=y end end end end; begin readln(n); for i:=1 to n do l:=n; for i:=1 to l do begin k:=P(a,j,n); a[j]:=a[n];