南京工程学院数据结构样卷09级加答案Word格式.docx
《南京工程学院数据结构样卷09级加答案Word格式.docx》由会员分享,可在线阅读,更多相关《南京工程学院数据结构样卷09级加答案Word格式.docx(19页珍藏版)》请在冰点文库上搜索。
为什么顺序存储结构队列会出现假溢出?
怎样解决队列的假溢出问题?
链式存储结构队列会出现假溢出吗?
顺序存储结构的栈会出现假溢出吗?
3.已知一棵二叉树中根次序遍历序列为GCBHKAMFDJE,后根次序遍历序列为CBGHMAJEDFK,画出这棵二叉树并进行中序线索化。
4.设一段正文由字符集{A,B,C,D,E,F,G,H}组成,其中每个字符在正文中的出现次数依次为{23,5,17,4,9,31,29,18},采用哈夫曼编码对这段正文进行压缩存储,画出所构造的哈夫曼树,并写出每个字符的哈夫曼编码。
5.删除以下带权无向图中的顶点D,画出删除D后图的邻接矩阵表示和邻接表表示。
6.构造以下带权无向图的最小生成树,并给出该最小生成树的代价。
7.已知关键字序列为{16,74,60,43,54,90,46,31,29,88,71,64,50},散列表长度为11,采用除留余数法的散列函数为hash(k)=k%11,画出采用链地址法构造的散列表,计算(写出算式)。
8.画出对关键字序列{93,17,56,42,78,15,42*,25,19}进行希尔排序(升序)的每一趟排序过程,说明希尔排序算法的稳定性并解释原因,以及希尔排序适用于什么存储结构。
9.将关键字序列{29,10,25,26,58,12,31,18,47}用筛选法分别建成一个最大堆和一个最小堆,写出两个堆序列并画出其对应的完全二叉树。
三.程序阅读和改错题(15分,每小题5分)
1.阅读以下函数,回答问题。
template<
classT>
voidCirHDoublyLinkedList<
:
concat(CirHDoublyLinkedList<
&
list)
{
DLinkNode<
*rear=head->
prev;
rear->
next=list.head->
next;
list.head->
next->
prev=rear;
rear=list.head->
next=this->
head;
this->
head->
prev=list.head;
next=list.head;
}
上述函数功能是什么?
以下调用语句的运行结果是什么?
CirHDoublyLinkedList<
char>
source("
abcdef"
6),list("
xyz"
3);
source.concat(list);
cout<
<
"
source:
source<
list:
list;
2.下列trim()函数欲删除当前字符串对象中的所有空格字符。
voidSString:
trim()//删除串对象中的所有空格字符
{inti=0;
while(element[i]!
='
'
&
element[i]!
\0'
)//寻找第1个空格
i++;
//i记住第1个空格下标
for(intj=i;
element[j]!
;
j++)
if(element[j]!
)
element[i++]=element[j];
//非空格字符向前移动到空格字符位置
len=i;
①对于以下调用语句,运行结果是什么?
正确的运行结果是什么?
SStringstr("
abcdefxyz"
str.trim();
str="
str<
endl;
②trim()函数怎样实现所求功能?
算法存在什么错误?
③如何改正?
3.已知三叉链表表示的二叉树结点类TriNode声明如下:
classTriNode//二叉树的三叉链表结点类
public:
Tdata;
//数据域,保存元素
TriNode<
*parent,*left,*right;
//指针域,分别指向父母、左、右孩子结点
//构造结点,参数依次分别指定元素、左孩子和右孩子结点
TriNode(Tdata,TriNode<
*left=NULL,TriNode<
*right=NULL)
{
data=data;
left=left;
right=right;
}
};
三叉链表表示的二叉树类TriBinaryTree及部分函数声明如下:
classTriBinaryTree//二叉树类(三叉链表)
*root;
//指向根结点
TriBinaryTree(TriBinaryTree<
bitree);
//拷贝构造函数
private:
*copy(TriNode<
*p);
//复制以p为根的子二叉树
TriBinaryTree<
TriBinaryTree(TriBinaryTree<
bitree)//拷贝构造函数
root=copy(bitree.root);
//复制以p为根的子二叉树,返回新建子树的根结点
TriNode<
*TriBinaryTree<
copy(TriNode<
*p)
*q=NULL;
if(p!
=NULL)
q=newTriNode<
(p->
data);
q->
left=copy(p->
left);
right=copy(p->
right);
returnq;
上述函数中存在什么错误?
如何改正?
四.程序设计题(14分,每小题7分)
1.在带头结点的单链表类HSLinkedList中,增加以下成员函数:
voidHSLinkedList<
removeAll(HSLinkedList<
list)//删除所有与list匹配的子表
2.求二叉树中指定结点的层次。
1.使数据类型的定义和实现分离,使一种定义有多种实现。
2.Node<
*table[4];
Node<
table[4];
3."
abac"
4.ABCDEF+*G/-H+*+IJ+K*-
5.36
6.1148
7.7
8.右单支二叉树(包括空二叉树、只有根结点的二叉树)
9.511
10.n*(n-1)/2
11.
12.{41*4134105424}67{7869}
1.模式串"
改进的next数组为
j
1
2
3
4
5
6
7
8
模式串
a
b
c
"
中最长相同的前后缀子串长度k
-1
与
比较
≠
=
改进的next[j]
2.栈和队列都属于线性表结构,它们是两种特殊的线性表,栈的插入和删除操作都在线性表的一端进行,所以栈的特点是“后进先出”;
而队列的插入和删除操作分别在线性表的两端进行,所以队列的特点是“先进先出”。
深度优先搜索遍历算法需要使用栈作为辅助结构,广度优先搜索遍历算法需要使用队列作为辅助结构。
采用顺序存储结构的栈和队列,在进行插入、删除操作时不需要移动数据元素,因为栈和队列均不能进行中间插入、删除操作。
顺序队列,当入队的元素个数(包括已出队元素)超过数组容量时,队列尾下标越界,数据溢出。
此时,由于之前已有若干元素出队,数组前部已空出许多存储单元,所以,这种溢出并不是因存储空间不够而产生的,称之为假溢出。
顺序队列之所以会产生假溢出现象,是因为顺序队列的存储单元没有重复使用机制。
解决的办法是将顺序队列设计成循环结构。
链式存储结构队列不会出现假溢出。
因为每次元素入队,都要申请新结点,数据不会溢出。
顺序存储结构的栈不会出现假溢出。
因为顺序栈的存储单元可以重复使用,如果数组容量不够,则是数据溢出,而不是假溢出。
(3)
(4)
(5)
.
(6)
,代价是45
(7)
(8)
希尔排序算法是不稳定的,因为与距离较远的元素进行比较,不能保证排序稳定性。
希尔排序算法仅适用于顺序存储结构,因为与距离较远的元素进行比较,需要利用随机存储特性。
(9)
三.程序阅读题(15分,每小题5分)
1.将list链表合并连接到当前链表最后,设置list链表为空
(a,b,c,d,e,f,x,y,z)
()
2.①运行结果为“abcdefxyzefxyz”,正确的运行结果是“abcdefxyz”。
②trim()函数首先寻找串的第一个空格字符,用i记住空格字符下标;
再遍历串,将串中的非空格字符(用j记住其下标)逐个向前移动到空格字符位置(i下标);
算法存在错误,删除后没将字符串结束符'
向前移动到len处,导致cout输出仍然到'
,如下图所示。
③改正:
函数体最后增加以下一句:
element[len]='
3.深拷贝创建二叉树时,没有为各结点建立指向父母结点的链。
改正如下:
①当TriNode构造函数不指定parent时
{q=newTriNode<
//创建结点,父母结点parent为空
//复制左子树,递归调用
if(q->
left!
=NULL)
left->
parent=q;
//为左孩子设置parent链
//复制右子树,递归调用
right!
right->
//为右孩子设置parent链
//返回建立子树的根结点
②如果TriNode类声明以下构造函数,参数包括指定父母结点:
TriNode(Tdata,TriNode<
*parent=NULL,TriNode<
则TriNode类深拷贝构造函数可实现如下:
bitree)//拷贝构造函数,深拷贝
{this->
root=copy(bitree.root,NULL,1);
//复制以p为根的子二叉树,parent指向p的父母结点,返回新建子树的根结点
*p,TriNode<
*parent)
data,parent);
//创建结点,父母结点是parent
left,p);
right,p);
以下给出参考程序,阅卷老师可根据实际情况评分,重点是表达算法思想。
1.在带头结点的单链表类HSLinkedList中,增加以下成员函数,删除所有与list匹配的子表。
{Node<
*start=head->
next,*front=head;
while(start!
{Node<
*p=start,*q=list.head->
while(p!
=NULL&
q!
p->
data==q->
data)//一次匹配
{p=p->
q=q->
if(q!
=NULL)//一次匹配失败,再进行下一次匹配
{front=start;
start=start->
else//一次匹配成功,删除一个子表
{q=list.head->
while(q!
=NULL)//删除从start开始与list匹配的子表
{front->
next=start->
//删除start结点
deletestart;
start=front->
一棵二叉树中结点所在的层次定义:
令根结点的层次为1,其他结点的层次是其父母结点的层次加1。
①在二叉链表存储的二叉树类BinaryTree中增加成员函数如下:
intBinaryTree<
getLevel(Tx)//返回x结点所在的层次
{//若空树或未查找到x返回-1
if(root==NULL)
return-1;
returngetLevel(root,1,x);
//令根结点的层次为1
getLevel(BinaryNode<
*p,inti,Tx)
{//在以p结点(层次为i)为根的子树中求x结点所在层次
{if(p->
data==x)
returni;
//查找成功
intlevel=getLevel(p->
left,i+1,x);
//在左子树查找
if(level!
=-1)
returnlevel;
returngetLevel(p->
right,i+1,x);
//继续在右子树中查找
//查找不成功
②在二叉链表结点类BinaryNode中增加表示结点层次的成员变量level,结点构造函数声明如下:
BinaryNode(Tdata,BinaryNode<
*left=NULL,BinaryNode<
*right=NULL,intlevel=0)
构造二叉树时设置每个结点的层次属性。
例如,二叉树类BinaryTree的一种构造函数声明如下:
BinaryTree<
BinaryTree(Tprelist[],intn)//以标明空子树的先根序列构造一棵二叉树
root=create(prelist,n,i,NULL,1);
//根结点的层次为1
//以标明空子树的先根次序遍历序列创建一棵子树,该子树根结点是prelist[i],
//根结点层次是level,其父母结点由parent指向,返回创建子树的根结点指针
BinaryNode<
*BinaryTree<
create(Tprelist[],intn,int&
i,intlevel)
{BinaryNode<
*p=NULL;
if(i<
n)
{Telem=prelist[i++];
if(elem!
{p=newBinaryNode<
(elem,NULL,NULL,level);
//创建结点,层次是level
p->
left=create(prelist,n,i,level+1);
//创建左子树
right=create(prelist,n,i,level+1);
//创建右子树
returnp;
BinaryTree类的getLevel(p)成员函数声明如下,算法同查找。
getLevel(Tx)//返回值为x结点所在的层次,若空树或未查找到x返回-1
*find=search(x);
//查找
if(find==NULL)
returnfind->
level;
在二叉树中插入一个结点时,以插入结点为根的子树中所有结点的层次也随之改变,因此,BinaryTree类需要提供以下setLevel()方法动态维护层次属性。
//设置以p结点(层次为level)为根的子树中所有结点的层次
voidBinaryTree<
setLevel(BinaryNode<
*p,intlevel)
{if(p!
{p->
level=level;
setLevel(p->
left,level+1);
right,level+1);