数据结构综合练习一.doc

综合练习题一一、判断题：（正确打，错误打并改正）1、哈希文件是一种直接存取文件。（ ）2、线性结构的数据可以采用顺序存储，也可以采用链式存储。非线性结构的数据只能采用链式存储。（ ）3、栈和队列逻辑都是线性结构，串逻辑上不是线性结构。（ ）4、从双向循环链表中任何一个结点出发，查找该结点的前驱和后继都很方便。（ ）5、对于无向连通图，从图中的任何一个顶点出发，都可以遍历图中的所有顶点。（ ）6、序列101,88,49,75,33,39,43构成最大堆。（ ）7、二叉树的中序和后序遍历序列可以唯一确定一颗二叉树。（ ）。8、在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的增序排列存放，则可得到最小的平均搜索长度。（ ）二、简答题1、将n阶对称矩阵按上三角压缩存储在一维数组A中，请分析A中应包含多少个数据元素（需要推导过程）？ 2、队列可以用循环单链表来实现,故可以只设置头指针或者只设置一个尾指针,请问哪一个种方案更合适? 请从算法的时间复杂度分析为什么? 3、请简述顺序存储结构的优点和不足。三、分析题1、为了方便访问树中任何一个结点的孩子结点和双亲结点，设计应采用的存储结构，并画出此树的存储示意图。abcfed应采用双亲孩子表示法。存储示意图： 序号 data parent 0a-11b02c03d14e15f12 1 5 4 3 2、设哈希表为HT7, 哈希函数为 H (key) = key %7 , 按下列关键码序列 1，17，15，45，22，12，41 构造哈希表。（1）画出采用链表法解决冲突的哈希表；下标 data link01123174512641 221545（2）计算等概率下搜索成功时的平均搜索长度。（2）平均搜索长度=（1*4+2*2+3*1）/7=11/7 3、假设系统在某通信中只使用6种字符，其出现概率分别为0.03，0.06，0.07，0.08，0.29，0.47， 现需要对通信文本文件进行压缩。（1）画出相应的Huffman树(约定左子树权值小于右子树) ;（2）设计出每个字符的Huffman编码(左为0右为1)编码：0.47: 0 0.29: 11 0.07: 1010 0.08: 1011 0.03:1000 0.06:1001 ;（3）简述译码的过程。译码为根结点到叶结点的匹配过程。4、待排序的关键码序列为56，7，18，33，29，1，20，25，分别写出使用下列排序方法第一趟排序后的结果。（1）直接选择排序；（2）二路归并排序；（3）冒泡排序；（4）直接插入排序。5、画出下网的所有最小生成树。a15725921ebcf112015d四、算法设计题1、阅读下面顺序表的算法：const int MaxListSize=200; /设定表可容纳的元素最大个数templateclass SeqList T dataMaxListSize;int size; /当前表的大小public:void Insert(const T& item,int pos); templatevoid SeqList:Insert(const T& item,int pos)/把item插入到第pos位之前 int i;if( ) cout”顺序表已满！”; exit(0); if(pos0| ) /检查参数的合法性 coutpos; i-) （ ）; /数据移位（ ）; /插入数据 size+; /表长增1 （1）补充完成算法Insert（）；（2）计算算法Insert（）的时间复杂度； （3）若不需要考虑数据固有的顺序，如何使算法的效率达到O（1）？2、补充算法，完成链式堆栈的入栈操作。template class LinStack /定义链式堆栈类模板StackNode *top; /T为栈中元素类型,top指向栈顶int size; /栈当前大小 public:void Push(const T& item); /入栈;templatevoid LinStack:Push(const T& item) /新元素入栈/构造新结点newNode，newNode的数据域为da