数据结构-总结.doc

命题说明
章节
考核得重点及命题说明
第1章
各种基本概念与术语(0分)；
掌握算法描述与分析得方法(0分)
第2章
线性表得逻辑结构与各种存储表示方法(0分)；
以及定义在逻辑结构上得各种基本运算及其在存储结构上如何实现这些基本运算(0分)
第3章
栈与队列得特点(0分)；
栈在两种存储结构表示时得基本操作实现算法(0分)；
循环队列与链队列得基本操作实现算法(0分)
第6章
二叉树得各种存储结构得特点(0分)；
二叉树各种遍历策略得递归与非递归算法(0分)；
已知先序序列与中序序列或中序序列与后序序列建立二叉树得方法(0分)；
二叉树得线索化过程；(0分)
树得各种存储结构及特点；(0分)
建立最优树与哈夫曼编码得方法(0分)
第7章
图得各种存储结构(0分)；
图得两种搜索路径得遍历（深度与广度）(0分)；
最小生成树(0分)；
拓扑排序(0分)；
关键路径(0分)；
最短路径(0分)
第9章
顺序表与有序表得查找(0分)；
二叉排序树得构造与查找(0分)；
哈希表得构造方法(0分)
第10章
各种排序方法得执行过程与其依据得原则(0分)；
各种排序方法时间复杂度得分析(0分)

备注

一、单项选择（每题2分，共 20 分）
1、分析下面程序段得时间复杂度： ( )
i=1;j=1;
while(i<=n) i=i*3;
while(j<=n) j++;
A、O(n+log3n) B、O(n) C、O(log3n) D、O(n*log3n)
2、下面关于串得得叙述中，哪一个就是不正确得： （ ）
A、串就是字符得有限序列 B、空串就是由空格构成得串
C、模式匹配就是串得一种重要运算 D、串既可以采用顺序存储，也可以采用链式存储
3、从逻辑上可以把数据结构分为两大类 （ ）
A．动态结构、静态结构 B．顺序结构、链式结构
C．线性结构、非线性结构 D．初等结构、构造型结构
4、若某线性表最常用得操作就是存取任一指定序号得元素与在最后进行插入与删除运算，则利用（ ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点得双循环链表 D．单循环链表
5、有六个元素6，5，4，3，2，1 得顺序进栈，问下列哪一个不就是合法得出栈序列？ （ ）
A、 5 4 3 6 1 2 B、 4 5 3 1 2 6 C、 3 4 6 5 2 1 D、 2 3 4 1 5 6
6、最大容量为n得循环队列，队尾指针就是rear，队头就是front，则队满得条件就是 （ ）
A、 (rear+1) MOD n=front B、 rear=front
C．rear+1=front D、 (rear-l) MOD n=front
7、在一个长度为n得顺序表中删除第i个元素，需向前移动（ ）个元素。
A、 n B、i-1 C、n-i D、n-i+1
8、对一颗具有n个节点得树，其中所有度之与等于（ ）。
A、 n B、n-1 C、n-2 D、n+1
9、某二叉树得前序与后序序列正好相反，则该二叉树一定就是： ( )
A、高度等于其结点数 B、任意一个二叉树 C、所有节点均无左孩子 D、所有节点均无右孩子
10、已知一棵完全二叉树得第6层（根节点为第一层）有8个叶子节点，则完全二叉树得节点个数至多就是： A、39 B、52 C、111 D、119 ( )
11、以下数据结构中，（ ）就是非线性数据结构。
A．树 B．字符串 C．队 D．栈
12、设栈N与队列M初始状态为空，元素1,2,3,4,5,6依次通过栈N，一个元素出栈后进队列M，若6个元素出队得序列就是2,4,3,6,5,1,则栈N得容量至少应该就是： ( )
A、2 B、3 C、4 D、5
13、一棵完全二叉树上有100个结点，其中叶子结点得个数就是 （ ）
A． 50 B． 51 C．52 D．49
14、有关二叉树下列说法正确得就是 （ ）
A．二叉树得度为2 B．一棵二叉树得度可以小于2
C．二叉树中至少有一个结点得度为2 D．二叉树中任何一个结点得度都为2
15、一棵二叉树得前序遍历序列为ABCDEFG，它得中序遍历序列可能就是 （ ）
A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG
二、填空题（每题2分，共 20 分）
1、设一行优先顺序存储得数组A[5][5]，A[0][0]得地址为1000，且每个元素占2个存储单元，则A[2][3]得地址为 。
2、设循环队列用数组A[M]表示，队首、队尾指针分别就是front与rear，则循环队列得元素个数为 。
3、假定一棵二叉树得结点个数为200，则它得深度最少为 。
4、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素得概率相同，则删除一个元素平均需要移动元素得个数就是________。
5、带头结点得循环链表L中只有一个元素结点得条件就是：___ _____
三、简答题（每题5分，共1 0分）
1、什么就是数据得逻辑结构？数据得逻辑结构主要有哪几种基本得类型？
2、线性表有哪几种存储结构？分别有哪些优点？
四、综合应用题（每题5分，共2 0分）
1、已知一棵二叉树得先序遍历为ABECDFGHIJ，中序遍历为EBCDAFHIGJ。
（1）给出后序遍历序列，（2）将该二叉树转换为森林。
2、设有正文AADBAACACCDACACAADBB,字符集为A,B,C,D,设计一套二进制编码，使得上述正文得编码最短。
3、画出该逻辑结构得结构图。
S={D,R}, D={a,b,c,d,e,f,g}, R={<a,b>,<b,d>,<c,d>,<e,f>,<f,g>,<c,f>,<d,g>}
4、已知图如下：
(1) 给出该图得邻接矩阵与邻接表；
(2) 若从顶点V1出发对该图进行遍历，分别给出本图得按深度优先搜索与按广度优先搜索得顶点序列；
(3) 给出拓扑排序序列 。

5、给出如下图深度优先与广度优先遍历序列。
。
6、应用普里姆算法与克鲁斯卡尔算法求图得最小生成树。（具体步骤）
(v0,v4),(v0,v1),(v1,v2),(v1,v3),(v1,v5)
(v0,v4),(v1,v2),(v1,v3),(v1,v5),(v0,v1)
7、下图为带权有向图，求：
（1）给出拓扑排序序列；
（2）从顶点A到顶点I得关键路径。要求：给出具体计算过程，即列出所有事件得最早与最晚开始时间，所有活动得最早与最晚开始时间。

8、给出a到其她顶点得单源最短路径，根据dijkstra算法给出计算步骤。

9、已知有序顺序表得元素分别为：10,15,20,25,30,35,40,45,50,55,60
（1）使用顺序查找时查找成功情况下得平均查找长度为多少？
（2）使用折半查找方法，画出二分查找树。
10、输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），
（1）画出按元素排列顺序输入生成得一棵二叉排序树。
（2）请写出递归算法，从小到大输出该二叉排序树得所有结点。
11、设散列函数为H(K)=K %11,解决冲突得方法分别为（1）线性探测法与（2）链地址法，试将下列关键字集合{35,67,42,21,29,86,95,47}依次插入到散列表中（画出散列表得示意图），散列表长度为11。画出两种冲突解决方法得查找表。
12、已知序列（15，35，11，51，45，55，60，30），进行？？排序算法得每一趟得结果。
五、算法设计题（每题10分，共20分）
1、编写一个函数完成以下功能，删除链表中倒数第i个结点。
2、设计算法编写一个函数完成以下功能，统计一棵二叉树中所有度为0得结点得数目。