东北林业大学数据结构2001级

数据结构试题

（考试时间120分钟）

姓名：——————————————     考号：——————————————   班级：—————————— 

总  分		题  号	一	二	三	四	平时成绩
核分人		题  分	10	20	40	20
复查人		得  分

一、单项选择题：（总分10分，每小题1分）

1、在顺序存储的线性表(a1,a2,-----,an)中，删除任意结点时所需移动结点的平均次数为（ c   ）。

A．n        B n/2       C  （n-1）/2       D  （n+1）/2

2、已知二叉树如图所示，此二叉树的顺序存储结构是（  d       ）。

1   2   3   4   5

4

A

C

F

G

1    2    3    4

A

C

F

G

                           

A．                          B.

1  2  3  4  5   6

4

A

C

F

G

1   2   3   4   5

A

C

F

G

                              

C．D.                

3、某二叉树的前序遍历结点顺序为：ABCDEFG，中序遍历结点顺序为：CBDAFGE，则后续遍历结点的顺序为：（ a      ）。

A．CDBGFEA      B.CDGFEAB       C.CDBAGFE       D.CDBFAGE

4、6．在一棵高度为H的满三叉树中，结点总数为（ b       ）。

A．3H - 1     B．（3H – 1）/2      C．（3H - 1 ）/3      D．3H

5、设N阶方阵A是一对对称矩阵，为节省存储空间，将其下三角（包括对角线）以行序为主序存储在一维数组B[1----N（N+1）/2]中，则对任一上三角元素        ，在一维数组B中的下标位置K是（        ）

A I(I-1)/2+j             B j(j-1)/2+i           C I(j-1)2+1           D j(I-1)/2+1

6、用孩子兄弟链表表示一棵树，若要找到结点X的第5个孩子，只要先找到X的第一个孩子，然后（   d      ）

A 从孩子域指针连续扫描5个结点即可   B从孩子域指针连续扫描4个结点即可

C从兄弟域指针连续扫描5个结点即可   D从兄弟域指针连续扫描4个结点即可

7、设输入序列为a，b，c，d，借助一个栈得到的输出序列不可能是（ d      ）。

  A．a，b，c，d     B．d，c，b，a      C．a，c，d，b      D．d，a，b，c

8、一个无向连通图的生成树是含有该连通图的全部顶点的（        a      ）“

A 极小连通子图    B 极小子图     C 极大连通子图      D 极大子图

9、有12个节点的平衡二叉树的最大深度是（     b   ）。

A．4         B．5        C．6         D．3

10、对于静态表顺序查找算法，若在表头设置岗哨，则正确的查找方式（      c      ）

A 从第0个元素往后查找该数据元素        B从第1个元素往后查找该数据元素

C从第N个元素开始往前查找该数据元素    D 与查找顺序无关

二、填空题（每题2分，共20分）

1．一般树的遍历结果和它所对应的二叉树的遍历结果之间有一定的对应关系：一般树的前序遍历序列和它所对应二叉树的       先序         遍历序列一致，一般树的后序遍历序列和它所对应二叉树的      中序            遍历序列一致。

Prior  data   next

2、设某双链表的结点形式为                 ，若要在指针Q所指结点（中间结点）的后面插入一个新结点，则需执行下述语句段：

s->prior=q; s->next=q->next ; ____________ ;q->next=s:

3、对50个记录进行折半查找，最多比较次数和最少比较次数分别是     6 1             。

4、设有一中缀表达式（（E-F）*G+A/（B-C））*D，其等价的后缀表达式是                               。

5、设二维数组A[10..20，5..10]按行优先存储，每个元素占4个存储单元，A[10，5]的存储地址为1000，则A[15，10]的存储地址为                       。

6、设有满足二分查找法要求的查找表R（键值按递增顺序排列），查找区间为[l，h],要查找的键值为K，首先被比较元素的位置为mid=(l+h) DIV 2，若R[MID].key >K，则h改为（            ）；二分查找的结束条件是（          ）。

7．设有向图G有n个顶点v1,v2,v3,…vn，它的邻接矩阵为A，顶点vi的入度ID（vi）为（            ）；顶点vi的出度OD（vi）为(             ).

info

link

8．设一个链栈的栈顶指针为ls，栈中结点格式为                 栈空条件是

（           ），如果栈不空，则退栈操作为p=ls； （             ）；free(p)。

data

next

9．设链队列lq中结点的格式为                。头指针为lq->front，尾指针为lq->rear，队列为空的条件（                                ）。

10、查找表分为静态查找表和动态查找表两种，二叉排序树属于               。

三、应用题（共40分）

1．已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清，构造出该二叉树。

先序序列:       _____BC_________E____GH

中序序列:       C______DA_________GHF

后序序列:       ____DB_________FEA

2．已知无向图G的邻接表如下，请画出其所有的连通分量，并写出其按广度优先搜索各连通分量的访问序列。

3．假设用于通信的电文仅由A-H八个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这八个字母设计哈夫曼编码。带权路径长度是多少？权值为10的结点层次是多少？

4．一棵树有度为1的结点n1个，度为2的结点n2个,…,度为m的结点nm个，问它有多少个叶结点?

5．请对无向带权图，写出他的临接矩阵，并按朴里母算法求其最小生成树。

6．给定无序序列{30，19，26，48，59，13，52，11}，试写出建初始堆的过程。

7．如图所示，在栈的输入端元素的输入顺序为A，5，B，求出端可得到的以字母开头的所有输出序列，并给出栈的操作过程（用push表示进栈，pop表示出栈）

                                                                  A 5 B

                                                   输出端        输入端

                                                               

                                                                栈

四、设计题（共20分）

1．某带头结点的单链表的结构说明如下：

typedef  struct  nodel

  {

int  data;

struct  nodel  *next

}node:

试设计一个算法，计算该单链表中数据域的值为K的结点个数。设单链表的头指针为HEAD。（6分）

2．给定一棵用二叉链表表示的二叉树，其根指针为ROOT，试编写求此二叉树的叶子数目的非递归算法。（8分）

3．已知一个有向图的邻接表，试编写一个算法求每个结点的出度和入度。（6分）