北京邮电大学1999年数据结构试题

北京邮电大学1999年数据结构试题 http://ww.kaoyan.com2001/8/15考研加油站 注意事项 1.答案一律写在答题纸上 2答案卷应字迹清楚、语义确切; 3算法应说明基本思路,应对主要数据类型、变量给出说明,所写算法应结构清晰 简明易懂,应加上必要的注释; 4算法可用(类) PASCAL语言、C语言等你所熟悉的高级语言编写,但要注明语 种 (10分) 选择填空 ①字符串 ababaabab的 nextv a为 (0,1,0,1,0,4,1,0,1)B.(0, C.(0,1,0,1,0,0,0,1,1,)D.(0,1,0,1,0,1,0,1,1) ②广义表A=(abcd)、e,(g),则下面式子的值为 Head(Tail(Head(Tail(TaIl(A)) (d) Cc Dd

北京邮电大学 1999 年数据结构试题 http://www.kaoyan.com 2001/8/15 考研加油站 注意事项： 1.答案一律写在答题纸上； 2.答案卷应字迹清楚、语义确切； 3.算法应说明基本思路，应对主要数据类型、变量给出说明，所写算法应结构清晰、 简明易懂，应加上必要的注释； 4.算法可用（类）PASCAL 语言、C 语言等你所熟悉的高级语言编写，但要注明语 种。 1 （10 分） 选择填空 ① 字符串’ababaabab’的 nextval 为 A．（0，1，0，1，0，4，1，0，1） B.（0，1，0，1，0，2，1，0，1，） C．（0，1，0，1，0，0，0，1，1，） D.（0，1，0，1，0，1，0，1，1） ②广义表 A=（a,b,(c,d),(e,(f,g))）,则下面式子的值为 ； Head(Tail(Head(Tail(Tail(A))))) A．（g） B.(d) C.c D.d

③输入序列为(A,B,C,D),不可能得到的输出序列有 C, D) (D, C,B, A) C. (A,C,D,B)D.(C, A, B, D) ④散列函数有一个共同性质,即函数值应按取其值域的每一个值 A.最大概率B最小概率C.同等概率D.平均概率 ⑤直接插入排序在最好情况下的时间复杂度为 A.O(logn)B. o(n)C O(nlogn) D(n2 2(10分) 判断下列叙述是否正确 ①(101,88,46,70,34,39,45,58,66,10)是堆 ②将一棵树转换成二叉树后,根结点没有左子树; ③用树的前序遍历和中序遍历可以导出树的后序遍历; ④即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操 作,所得的输出序列也一定相同 ⑤哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离很较近。 3(10分) 有一高个比他人都至少高出一头,找他的人都说“根本不用与别人比较,一眼就能 找到他”,你认为此话正确吗?为什么?请简要描述两种求N个数中最大值的方法,并 给出所需的最少比较次数

③ 输入序列为（A，B，C，D），不可能得到的输出序列有 ； A．（A，B，C，D） B．（D，C，B，A） C．（A，C，D，B） D．（C，A， B，D） ④ 散列函数有一个共同性质，即函数值应按 取其值域的每一个值； A.最大概率 B.最小概率 C.同等概率 D.平均概率 ⑤ 直接插入排序在最好情况下的时间复杂度为 。 A. O (logn) B. O (n) C. O (n*logn) D(n2 ) 2 （10 分） 判断下列叙述是否正确 ①（101，88，46，70，34，39，45，58，66，10）是堆； ② 将一棵树转换成二叉树后，根结点没有左子树； ③ 用树的前序遍历和中序遍历可以导出树的后序遍历； ④ 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操 作，所得的输出序列也一定相同； ⑤ 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离很较近。 3 （10 分） 有一高个比他人都至少高出一头，找他的人都说“根本不用与别人比较，一眼就能 找到他”，你认为此话正确吗？为什么？请简要描述两种求 N 个数中最大值的方法，并 给出所需的最少比较次数

4(10分) 图1是用邻接表存储的图,画出此图,并写出从C点开始按深度优先遍历该图的结 果。 A B D B F D A D E 图1题4图 5(10分) 下面是求无向连通图的最小代价生成树的一种算法 将图中所有边按权重从大到小排序为(e1e2…em) Whe(所剩边数≥顶点数) 从图中删去ei 若图不再连通,则恢复ei

4 （10 分） 图 1 是用邻接表存储的图，画出此图，并写出从 C 点开始按深度优先遍历该图的结 果。 图 1 题 4 图 5（10 分） 下面是求无向连通图的最小代价生成 树的一种算法： 将图中所有边按权重从大到小排序为(e1,e2,…,em) i:=1; W hile (所剩边数≥顶点数) Begin 从图中删去 ei 若图不再连通，则恢复 ei i:=i+1

End 试证明这个算法所得的图是原图的最小代价生成树。 6(10分) 已知无向图G和G’互为补图(结点相同、边不重叠、两图合起来为完全图),试 证明G或G’是连通的 7(10分) 用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树,画 出该树,并求在等概率情况下查找成功的平均查找长度 8(10分) 写出下面程序段的运行结果。 Program Ex(Input, Output) ty pe Ttt=Array[1.20]OF Integer I,J, K, L, N: Integer: Function P(Var A: Ttt; Var M, N: Integer): Integer;

End 试证明这个算法所得的图是原图的最小代价生成树。 6 （10 分） 已知无向图 G 和 G’互为补图（结点相同、边不重叠、两图合起来为完全图），试 证明 G 或 G’是连通的。 7 （10 分） 用序列（46，88，45，39，70，58，101，10，66，34）建立一个排序二叉树，画 出该树，并求在等概率情况下查找成功的平均查找长度。 8 （10 分） 写出下面程序段的运行结果。 Program Ex(Input, O utput); type Ttt=Array[1..20] O F Integer; Var I,J,K,L,N:Integer; A:Ttt; Function P (Var A:Ttt; Var M ,N:Integer):Integer; var

X,Y, Z: Integer; If N=1 Then p:=a[1 End else Y:=P(A, Z, N) N:=X If A[N]>=Y Then Begi End else

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

M: =Z. End End ReadIn (n); For I: =1 To n do Read(a[) Readln. For 1: =1 To L Do Begin K=P9A.N A[J]:=A[N]; A[N]: =K: N:=N1

Begin M :=Z; P:=Y End End End; Begin Readln(N); For I:=1 To N Do Read(A[I]); Readln; L:=N; For I:=1 To L Do Begin K=P9A,J,N); A[J]:=A[N]; A[N]:=K; N:=N-1

End For 1; =1 To L Do Write (A[]: 3); Write 输入数据为 61843527 9(10分) 已知二叉树用下面的顺序结构存储,写出中序遍历该二叉树的算法 Array [1. axn] of Record Data:Char;∥存结点值 Lc, Rc: Integer左、右孩子下标,0表示无左、右孩子 如树T=A(B(D,E),C(#,F(H,1)))存储如表1所示 表1树T的存储

End; For I;=1 To L Do W rite(A[I]:3); W riteln; End; 输入数据为： 8 6 1 8 4 3 5 2 7 9 （10 分） 已知二叉树用下面的顺序结构存储，写出中序遍历该二叉树的算法。 Type Array [1..m axn] of Record Data:Char; //存结点值 Lc,Rc:Integer //左、右孩子下标，0 表示无左、右孩子 如树 T=A（B（D，E），C（#，F（H，I）））存储如表 1 所示： 表 1 树 T 的存储 1 2 3 4 5 6 7 8 9

A E FG 240008000 0 0 0 10(10分) 试写出以带头结点单链表为存储结构实现简单选择排序的算法

A B C D E F G H I 2 4 0 0 0 8 0 0 0 3 5 6 0 7 9 0 0 0 10 （10 分） 试写出以带头结点单链表为存储结构实现简单选择排序的算法