2017 年 851 数据结构试题总结
一、简答题[每小题5分，共20分]
1.抽象数据类型定义与特点。
抽象数据类型（abstract data type, ADT）是指一个数学模型以及定义在该模型上的一组操作。它通常是指对数据的某种抽象，定义了数据的取值范围及其结构形式，以及对数据的操作的集合。特点：数据抽象，数据封装。
2.图的遍历中，设置访问标志数组的作用。
防止节点被遗漏访问和重复访问。
3.什么是关键路径？求解关键路径的意义何在。
路径上各个任务所持续的时间之和被称为路径长度，从起点到终点的所有路径中，具有最长路径长度的路径称为关键路径，关键路径中的各个任务称为关键任务。意义：可使花费总时间最短。
4.什么是哈弗曼树？其作用是什么？
假设有n个权值{w1,w2,w3,…wn}，构造一颗有n个节点的二叉树，若树的带权路径最小，则这棵树称作哈弗曼树。
哈弗曼树又称为最优二叉树。哈弗曼树是指具有相同节点的树中，加权路径长度最小的树，是一种带权路径最短的最优二叉树。
作用：进行哈弗曼编码，用于无损数据压缩。编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
二、分析题[每小题10分，共30分]
1.已知一棵完全二叉树第6层有6个叶子节点，该二叉树最多有个节点？最少有多少个节点？给出简单分析过程。
节点最多的情况：该完全二叉树共有7层。1~6层为满二叉树，第6层有6个叶子节点，其余26个是第7层的根节点。总结点数为：1+2+4+8+16+32+26x2=115个。
节点最少的情况：该完全二叉树共有6层。1~5层为满二叉树，第6层只有6个叶子节点。总结点数为：1+2+4+8+16+6=37个。
2.一个图有n个顶点，e条边。分析采用邻接矩阵和邻接表存储时所需要的存储空间。
3.设有10000个待排序的记录关键字，需要用最快的方法选出其中最小的十个记录关键字，则快速排序、简单选择排序、堆排序、直接插入排序、归并排序中哪些排序方法效率较高，简要说明理由。还有哪些适合该要求的高效排序方法。
用堆排序：最坏情况下的时间复杂度为O(log2n)。适用于记录多的情况，总共进行的关键字比较不超过4n。调整建新堆的比较次数不超过2log2n次(共不超4n+2klog2n)。
用快速排序：最好情况下的时间复杂度为O(nlog2n)，且快速排序在序列越无序的情况下效率越高。
用归并排序：时间复杂度为O(nlog2n)。排序过程中要选出前k个最大元素(k<
简单选择排序、直接插入排序的时间复杂度均为O(n2)，所以舍弃。
三、构造结果
1.N阶对称矩阵A，压缩存储在一维数组B中。假设存储下三角矩阵，请分析对于A[i,j]，其在B中的存储位置的下标。（下标从1开始）。
对于N阶对称矩阵，共需存储数据个，即一维数组大小为。
先存储下三角部分，再存储对角线上的元素。
一维数组B[k](k从1开始)，对应公式为：。
2.用克鲁斯卡尔算法，构造如图所示连通网的最小生成树（写出每步结果）。
步骤：
代价为：10 + 14 + 16 + 12 + 22 + 25 = 99
3.画出11个结点的折半判定树，并计算等概率情况下的查找成功的平均查找长度。
ASL = 11 + 22 + 34 + 44 = 33
4.某报文长度为60个字符，统计发现共含6种字，符其出现的次数分别为{5,1,3,6,8,21,16}。要求①为该报文设计一种编码，使其报文长度最短；②计算编码后的报文长度。
5.对关键字序列{25,18,45,40,26,22,16,10}按从小到大排序，[1]写出1趟快速排序的结果；[2]写出用堆排序时建立的初堆。
[1]
①先从后往前找出小鱼基准数25的数，并与之交换
10 18 45 40 26 22 16 25
②再从前往后找出大于基准数25的数，并与之交换
10 18 25 40 26 22 16 45
10 18 16 40 26 22 25 45
10 18 16 25 26 22 40 45
10 18 16 22 26 25 40 45
10 18 16 22 25 26 40 45 第一趟快速排序结果
[2]
首先根据序列构建一个完全二叉树
在完全二叉树的基础上，从最后一个
四、编写算法
1.已知带头结点的单链表L，编写算法删除值最大的结点。
1 void delmaxnode(LinkList *&L) 2 { 3 LinkList *p = L->next, *pre = L, *maxp = p, *maxpre = pre; 4 while(p != NULL) 5 { 6 if(maxp->data < p->data) 7 { 8 maxp = p; 9 maxpre = pre; 10 } 11 pre = p; 12 p = p->next; 13 } 14 maxpre->next = maxp->next; 15 free(maxp); 16 }
2.二叉树采用二叉链表方式存储，编写算法实现二叉树的层次遍历。
五、编写算法
一棵二叉树采用二叉链表方式存储编，写算法判定给定的这棵二叉树是否为二叉排序树。
六、编写算法
某关键字序列按除留取余法构建了哈希表，H(key)=key%P(P小于等于m)，采用线性探测再散列解决冲突。编写算法，对给定长度为m、元素个数为n的哈希表(m大于等于n)，计算等概率情况下查找成功的平均查找长度。