数据结构 模拟试题1 参考答案

数据结构 模拟试题1 参考答案

一、回答问题

1.算法是对特定问题求解步骤的一种描述，可以用自然语言、流程图、伪代码、程序代码来表示。程序是算法的具体实现，可以用不同的语言实现。

2.(1)双亲表示法——以一组连续空间存储树的结点，在每个结点中设一个指示器指示双亲结点的位置。

(2)孩子表示法——每个结点的孩子以单链表的形式存储，n个结点有n个孩子链表，n个头指针又组成一个线性表，并以顺序存储结构存储。

(3)孩子兄弟表示法——以二叉链表作为树的存储结构，链表中的结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。

双亲表示法： 孩子表示法：

孩子兄弟表示法：

3.

ASL = 1/10 *(1+2*2+4*3+3*4) = 2.9 4.深度优先搜索，宽度优先搜索。例如：

深度优先搜索遍历：ABXFYDEC 宽度优先搜索遍历：ABCDXEYF 5.

#define ATOM 0 #define LIST 1 typedef enum {

ATOM, LIST }ElemTag;

//表头表尾结构 struct GLNode {

ElemTag tag; //区分原子结点表结点 union {

int atom; struct {

struct GLNode *hp; struct GLNode *tp; }ptr; }; };

//后继结点结构 struct GLNode {

ElemTag tag; union {

int atom; //原子结点的值域 struct GLNode *hp; //表结点的头指针 };

struct GLNode *tp; //下一个元素结点 };

采用后继结点的存储结构

6. B树：

B+树：

B树与B+树的区别：

1) B树：每个结点的关键字个数等于指针个数减1。 B+树：每个结点的关键字个数等于指针个数。

2) B+树中所有叶子结点包含了全部关键字信息，以及指向关键字记录的指针，叶子节点依关键字大小自小到大链接。非终端结点作索引，结点中含有其子树根结点的最大（最小）关键字。 7.

排序算法 直接插入排序 冒泡排序 快速排序 时间复杂度 O(n2) O(n2) O(nlogn) 空间复杂度 O(1) O(1) O(logn) 稳定性 稳定 稳定 不稳定 选择排序 堆排序 归并排序 基数排序 8. O(n2) O(nlogn) O(nlogn) O(d(n+rd)) O(1) O(1) O(n) O(rd) 不稳定 不稳定 稳定 不稳定

7=7 查找1次成功 15=4 查找1次成功 20=9 查找1次成功 31=9 9+1=10 查找2次成功 48=4 4+1 =5 查找2次成功 53=9 9+1+1-11=0 查找3次成功 64=9 9+1+1+1-11=1 查找4次成功 76=10 10+1+1+1-11=2 查找4次成功 82=5 5+1=6 查找2次成功 99=0 0+1+1+1=3 查找4次成功 二、

Dijkstra算法思想：

(1)求解顺序：按最短路径递增的顺序求解。

(2)到某个定点的最短路径找到后，考察它对其余顶点当前最短路径的影响。 算法步骤：

1）设arcs存储带权有向图的边的权值，v为出发顶点，S为已找到的从v出发的最短路径的终点集合，开始为空。从v出发到图中其余顶点vi最短路径长度初始值为D[i]=arcs[o][i] o, i为v, vi的位置 2）选择vj，使得D[j]=Min{D[i]| vi∈V-S} vj是从v出发的最短路径的终点。S=S∪{j} 3）修改从v出发到集合V-S任一顶点vk可达的最短路径长度。如果D[j]+arcs[j][k]

4）重复2，3 n-1次，由此求出从v到其它顶点的最短路径。 三、

#include

//将有序的SR[i...m]和SR[m+1...n]归并为有序的TR[i...n] void Merge(int SR[], int TR[], int i, int m, int n) {

int j,k; j = m+1;

查找成功时的平均查找长度：(1+1+1+2+2+3+4+4+2+4)/10=2.4 查找失败的平均查找长度：（1+2+3+4+5+6+7+8+9+10+11）/11=6