重庆大学2018年 数据结构第3次作业
第3次作业一、填空题（本大题共30分，共 10 小题，每小题 3 分）
1.
具有8个顶点的无向图，边的总数最多为______。
2.
树在计算机内的表示方式有 ， ， 。
3.
设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A与A之间有_______个数据元素。
4.
队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。
5.
在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为_______域和_______域。
6.
构造连通网最小生成树的两个典型算法是______。
7.
在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的________、________和________三项。
8.
已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有 个叶子结点。
9.
非空的单循环链表head的尾结点（由p指针所指）满足条件________________。
10.
在哈希文件中，处理冲突的方法通常有______、______ 、______和______四种。
二、算法设计题（本大题共20分，共 2 小题，每小题 10 分）
1.
回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。
2.
编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有原链表A中序号为奇数的元素，而链表B中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。
三、简答题（本大题共20分，共 4 小题，每小题 5 分）
1.
何时选用顺序表、何时选用链表作为线性表的存储结构为宜？
2.
一棵度为2的树与一棵二叉树有何区别？
3.
指出下述程序段的功能是什么?
void Demo1( SeqStack *S, int m)
{ // 设DataType 为int 型
SeqStack T; 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)（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.
参考答案：
先进先出
解题方案：
评分标准：
5.
参考答案：
值（或data）， 子表指针（或sublist）
解题方案：
评分标准：
6.
参考答案：
普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法
解题方案：
评分标准：
7.
参考答案：
行号、列号、元素值
解题方案：
评分标准：
8.
参考答案：
12
解题方案：
评分标准：
9.
参考答案：
p->next==head
解题方案：
评分标准：
10.
参考答案：
开放地址法、再哈希法、链地址法、建立一个公共溢出区
解题方案：
评分标准：
二、算法设计题（20分，共 2 题，每小题 10 分）
1.
参考答案：
算法可设计为：
//以下为顺序栈的存储结构定义
#define StackSize 100 //假定预分配的栈空间最多为100个元素
typedef char DataType;//假定栈元素的数据类型为字符
typedefstruct{
DataType data;
int top;
}SeqStack;
intIsHuiwen( char *t)
{//判断t字符向量是否为回文，若是，返回1，否则返回0
SeqStack s;
inti , len;
char temp;
InitStack( &s);
len=strlen(t); //求向量长度
for ( i=0; i<len/2; i++)//将一半字符入栈
Push( &s, t);
while( !EmptyStack( &s))
{// 每弹出一个字符与相应字符比较
temp=Pop (&s);
if( temp!=S)return 0 ;// 不等则返回0
else i++;
}
return 1 ; // 比较完毕均相等则返回 1
}
解题方案：
评分标准：
2.
参考答案：
将单链表A中的所有偶数序号的结点删除，并在删除时把这些结点链接起来构成单链表B。算法如下：
#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
typedef struct LNode
{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;
void divide(LinkList&pa, LinkList&pb)
{pb=(LNode *)malloc(sizeof(LNode *));
pb->next=NULL;
r=pb;
p=pa->next;
while(p!=NULL && p->next!=NULL)
{
q=p->next;
if(q!=NULL)
{
p->next=q->next;
r->next=q;
r=q;
p=p->next;
}
}
r->next=NULL;
}
解题方案：
评分标准：
三、简答题（20分，共 4 题，每小题 5 分）
1.
参考答案：
在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：
（1）基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。
（2）基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。
解题方案：
评分标准：
2.
参考答案：
度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。
解题方案：
评分标准：
3.
参考答案：
程序段的功能是利用栈T，将一个非空栈S中值等于m的元素全部删去。
解题方案：
评分标准：
4.
参考答案：
（1）
（2）wpl=(2+3)*5+6*4+(9+14+15)*3+(16+17)*2=229
（3）编码为：15:111, 3:10101, 14:110, 2:10100, 6:1011, 9:100, 16:00, 17:01
(4) 常用哈夫曼树为通讯用的字符编码，本题中集合的数值解释为字符发生的频率（次数）。由哈夫曼树构造出哈夫曼编码。译码时，进行编码的“匹配”，即从左往右扫描对方发来的“编码串”，用字符编码去匹配，得到原来的元素（本题中的数）。
解题方案：
评分标准：
四、程序设计题（30分，共 2 题，每小题 15 分）
1.
参考答案：
typedef char DataType;//定义DataType类型
typedefstruct node
{
DataType data;
struct node *lchild, *rchild;//左右孩子子树
}BinTNode; //结点类型
typedefBinTNode *BinTree ;//二叉树类型
int Leaf(BinTree T)
{ //算叶子数
if(T)
if (T->lchild==NULL)&&(T->rchild==NULL)
return 1;
else
return Leaf(T->lchild)+Node(T->rchild);
else
return 0;
}
解题方案：
评分标准：
2.
参考答案：
#define ListSize 100 // 假定表空间大小为100
typedef int DataType;//假定DataType的类型为int型
typedef struct{
DataType data;// 向量data用于存放表结点
int length; // 当前的表长度
} Seqlist;
//以上为定义表结构
void InsertList ( Seqlist *L, Datatype x, int i)
{
//将新结点x插入L所指的顺序表的第i个结点ai的位置上，即插入的合法位置为：0<=i<=L->length
int j;
if ( i < 0 || i > L -> length )
Error("position error");// 非法位置，退出，该函数定义见教材P7.
if ( L->length>=ListSize )
Error(“overflow");
for ( j=L->length-1 ; j >= i ; j --)
L->data[ j+1]=L->data [ j ];
L->data[ i ]=x ;
L->length++ ;
}
解题方案：
评分标准：
页:
[1]