数据结构第三次作业题及答案

《数据结构第三次作业题及答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第3次作业一、填空题（本大题共30分，共10小题，每小题3分）1.具有8个顶点的无向图，边的总数最多为______。2.树在计算机内的表示方式有，，。3.设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。4.队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。5.在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为_______域和_______域。6. 构

2、造连通网最小生成树的两个典型算法是______。7.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的________、________和________三项。8.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有个叶子结点。9.非空的单循环链表head的尾结点（由p指针所指）满足条件________________。10.在哈希文件中，处理冲突的方法通常有______、______、______和______四种。二、算法设计题（本大题共20分，共2小题，每小题10分）1.回文是指正读反读均相同的字符序列

3、，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。2.编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有原链表A中序号为奇数的元素，而链表B中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。三、简答题（本大题共20分，共4小题，每小题5分）1.何时选用顺序表、何时选用链表作为线性表的存储结构为宜？2. 一棵度为2的树与一棵二叉树有何区别？3.指出下述程序段的功能是什么? voidDemo1(SeqStack*S,int

4、m) 　　　{//设DataType为int型　　　　SeqStackT;inti;　　　　InitStack(&T);　　　　while(!StackEmpty(S))　　　　　if((i=Pop(S))!=m)Push(&T,i);　　　　while(!StackEmpty(&T))　　　　　{　　　　　　i=Pop(&T);Push(S,i);　　　　　}　　　}4. 给定集合{15,3,14,2,6,9,16,17}(1)（3分）用□表示外部结点，用○表示内部结点，构造相应的huffman树：(2)(2分)计算它的带权路径长度：(3)（

5、2分)写出它的huffman编码：(4)（3分)huffman编码常用来译码，请用语言叙述写出其译码的过程。四、程序设计题（本大题共30分，共2小题，每小题15分）1.以二叉链表为存储结构，写出求二叉树叶子总数的算法2.设线性表的n个结点定义为(a0,a1,...an-1)，重写顺序表上实现的插入算法：InsertList答案：一、填空题（30分，共10题，每小题3分）1.参考答案：28解题方案：评分标准：2.参考答案：双亲链表表示法，孩子链表表示法，孩子兄弟表示法解题方案：评分标准：3.参考答案：i(i+1)/2+j-1解题方案：评分标准：4

6、.参考答案：先进先出解题方案：评分标准：5.参考答案：值（或data），子表指针（或sublist）解题方案：评分标准：6.参考答案：普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法解题方案：评分标准：7.参考答案：行号、列号、元素值解题方案：评分标准：8.参考答案：12解题方案：评分标准：9.参考答案：p->next==head解题方案：评分标准：10.参考答案：开放地址法、再哈希法、链地址法、建立一个公共溢出区解题方案：评分标准：二、算法设计题（20分，共2题，每小题10分）1.参考答案：算法可设计为：　//以下为顺序栈的存储结构定

7、义　#defineStackSize100//假定预分配的栈空间最多为100个元素　typedefcharDataType;//假定栈元素的数据类型为字符　typedefstruct{　　DataTypedata[StackSize];　　inttop;　}SeqStack; 　intIsHuiwen(char*t)　　{//判断t字符向量是否为回文，若是，返回1，否则返回0　　　SeqStacks;　　　inti,len;　　　chartemp;　　　InitStack(&s);　　　len=strlen(t);//求向量长度　　　for(i

8、=0;i