第一章 绪论
1.(第18页,第(5)题)
确定下列各程序段的程序步,确定划线语句的执行次数,计算它们的渐近时间复杂度。
(1) i=1; k=0;
do {
k=k+10*i; i++;
} while(i<=n-1)
划线语句的执行次数为 n-1 。
(2)i=1; x=0;
do{
x++; i=2*i;
} while (i
=(y+1)*(y+1)) y++;
划线语句的执行次数为 n 。
第二章 线性
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
1.第37页 习题(2).2
在类LinearList 中增加一个成员函数,将顺序表逆置,实现该函数并分析算法的时间复杂度。不利用类SeqList 提供的操作直接实现。
template
void SeqList::Invert()
{
T e;
for (int i=1;i<=length/2;i++){
e=elements[i-1];
elements[i-1]=elements[length-i];
elements[length-i]=e;
}
}
2.第37页习题(5)
在类SingleList中增加一个成员函数,将单链表逆置运算,直接实现该函数并分析其时间复杂度。
template
void SingleList::invert()
{
Node *p=first,*q;
first=NULL;
while (p){
q=p->link; p->link=first;
first=p; p=q;
}
}
3.(第37页,第7题) 单链表中结点按元素值递增链接,在类SingleList中增加一个成员函数,直接实现删除结点值在a至b之间的结点(ab)。
template
void SingleList::DeleteAb(T a,T b)//第37页,习题(7)
{
Node *p=first,*q=first;
while (p && p->datadata<=a){
q=p;p=p->link;
}
else if (q==first){
q=p->link;
delete p;
p=first=q;
}
else{
q->link=p->link;
delete p;
p=q->link;
}
}
}
4.(第37页,第8题) 在类CircularList中增加一个成员函数,在不增加新结点的情况下,直接实现两个链表合并为一个链表的算法,并分析其时间复杂度。
template
void Merge(CircularList &a,
CircularList &b)
{
Node *p=b.first;
while (p->link!=b.first) p=p->link;
p->link=a.first->link;
a.first->link=b.first->link;
b.first->link=b.first;
b.length=0;
}
template
void Merge1(CircularList &a,
CircularList &b)
{
Node *p=b.first->link;
b.first->data=b.first->link->data;
b.first->link=a.first->link;
a.first->link=p->link;
p->link=p;
b.first=p;
}
第三章 栈与队列
1. 第50页 习题(1)
设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈),问能否得到下列序列。若能得到,则给出相应的push和pop序列;若不能,则说明理由。
1)A,B,C,D,E 2) A,C,E,B,D
3) C,A,B,D,E 4) E,D,C,B,A
答:2)和3)不能。对2)中的E,B,D而言,E最先出栈,则表明,此时B和D均在栈中,由于,B先于D进栈,所以应有D先出栈。同理3)。
2. 第50页 习题(9)
利用栈可以检查表达式中括号是否配对,试编写算法实现之。
bool match(char a[],int n)
{
int top=-1;
for (int i=0;i-1) top--;
else return true;
if (top>-1) return true;
return false;
}
3. 第50页 习题(10)
声明并实现链式队列类LinkedQueue。
template
class LinkedStack: public Stack
{
public:
LinkedStack();
~LinkedStack();
virtual bool IsEmpty() const;
virtual bool IsFull() const;
virtual bool GetTop(T& x);
virtual bool Push(const T x);
virtual bool Pop();
virtual void SetNull();
private:
Node *top;
};
template
LinkedStack::LinkedStack()
{
top=NULL;
}
template
LinkedStack::~LinkedStack()
{
Node *q;
while (top){
q=top->link;
delete top;
top=q;
}
}
template
bool LinkedStack::IsEmpty() const
{
return !top;
}
template
bool LinkedStack::IsFull() const
{
return false;
}
template
bool LinkedStack::GetTop(T &x)
{
if (IsEmpty()){
cout<<"Empty stack"<data;
return true;
}
template
bool LinkedStack::Push(const T x)
{
Node *q=new Node;
q->data=x;
q->link=top;
top=q;
return true;
}
template
bool LinkedStack::Pop()
{
Node *q=top;
if (IsEmpty()){
cout<<"Empty stack"<link;
delete q;
return true;
}
template
void LinkedStack::SetNull()
{
Node *q;
while (top){
q=top->link;
delete top;
top=q;
}
}
第四章 数组与字符串
1. 给出三维数组元素A[i][j][k]的存储地址loc(A[i][j][k])。
答: 设有三维数组声明为A[n1][n2][n3],每个元素占k个存储单元,则
loc(A[i][j][k])=loc(A[0][0][0])+k*(i*n2*n3+j*n3+k)
2.(第68页,第5题)给出下列稀疏矩阵的
顺序三元组的行优先和列优先表示。
答:
3.(第68页,第6题)
对题图4-5的稀疏矩阵执行矩阵转置时数组num[]和k[]的值。
答:
4. (第69页,第15题(2))
在顺序串类String中增加一个成员函数,实现统计该串中出现的字符、字符个数和每个字符出现的次数。
void String::count(char ch[],int &n, int num[])
{
n=0;
for (int i=0;i
int SeqList::Search4(const T& x) const
{
elements[length]=1000;
return Sch4(x,0);
}
template
int SeqList::Sch4(const T& x,int i) const
{
if (x
void BTree::Exch(BTNode *p)
{
if (p){
BTNode *q=p->lchild;
p->lchild=p->rchild;
p->rchild=q;
Exch(p->lchild);
Exch(p->rchild);
}
}
4. 第107页,第10题
将图题6-24中的树转换成二叉树,并将图6-23中的二叉树转换成森林。
5. 第107页,第11题
给出对图6-24中的树的先序遍历和后序遍历的结果。
答:先序:A,D,E,F,J,G,M,B,L,H,C,K
后序:J,G,F,E,D,M,H,L,K,C,B,A
6. 第107页,第12题
分别以下列数据为输入,构造最小堆。
(1) 10,20,30,40,50,60,70,80
(2) 80,70,60,50,40,30,20,10
(3) 80,10,70,20,60,30,50,40
(1)
(2)
(3)
7. 第107页,第13题
分别以上题的数据为输入,从空的优先权队列开始,依此插入这些元素,求结果优先权队列的状态。
8. 第108页,第14题第(1)、(2)小题
设S={A,B,C,D,E,F},W={2,3,5,7,9,12},对字符集合进行哈夫曼编码,W为各字符的频率。
(1) 画出哈夫曼树
(2)计算带权路径长度
第七章 集合与搜索树
1.第137页,第(5),
建立37,45,91,25,14,76,56,65为输入时的二叉搜索树,再从该树上依此删除76,45,则树形分别如何?
2. 第137页,第(6)
试写一个判定任意给定的二叉树是否二叉搜索树算法。
int k=-; bool fail=false;
template
void BTree::IsBiTree(BTNode *p,int &k,bool &fail)
{
if (p&& !fail){
IsBiTree(p->lchild,k,fail);
if(k< p->element) k=p->element;
else fail=true;
IsBiTree(p->rchild,k,fail);
}
}
3. 第137页,第(8)
以下列序列为输入,从空树开始构造AVL搜索树。
(1)A,Z,B,Y,C,X
(2)A,V,L,T,R,E,I,S,O,K
4. 第137页,第(12)
5阶B-树的高度为2时,树中元素个数最少为多少?
答: 5
5. 第137页,第(13)题
从空树开始,以关键字序列:a,g,f,b,k,d,h,m,j,e,s,i,r,x ,建立
(1) 4阶B-树;
(2) 5阶B-树。
(1)
4阶B-树
(2) 5阶B-树
6. 第137页,第(14)题
从上题的4阶B-树上依次删除a,e,f,h。
第八章 散列与跳表
1. 第154页,第(3)题
设散列表ht[11],散列函数h(key)=key % 11。采用线性探查法解决冲突,试用关键字值序
列:70,25,80,35,60,45,50,55 建立散列表。
2. 第154页,第(6)题
给出用拉链方法解决冲突的散列表搜索操作的C++函数实现。
template
bool LinkedHashTable::Search(const K &k,E&e)const
{
int i=k % M,j;
HNode* p=ht[i];//元素结点类型Hnode
while (p){
if(p->element==k)return true;
p=p->nextsynonym;
}
return false;
}
3. 第154页,第(3)题
设散列表ht[11],散列函数h(key)=key % 11。采用二次探查法解决冲突,试用关键字值
序列:70,25,80,35,60,45,50,55 建立散列表。
4. 第154页,第(4)题
对上题的例子,若采用双散列法,试以散列函数h1(key)=key % 11,h2(key)= key % 9+1
建立散列表。
第九章 图
1. 第188页,第(1)题
对下面的有向图求
(1) 每个顶点的入度和出度;
(2) 强连通分量
(3) 邻接矩阵
2. 第188页,第(2)题
当以边〈1,0〉,〈1,3〉,〈2,1〉,〈2,4〉,〈3,2〉,〈3,4〉,〈4,0〉,〈4,1〉,〈4,5〉,
〈5,0〉的次序从只有6个顶点没有边的图开始,通过依此插入这些边,建立邻接表结构。
画出该邻接表。
3. 第188页,第(4)题
已知有向图的邻接表,试写出计算各顶点的入度的算法。
template
void LinkedGraph::Degree()
{
int *d=new int[n];int i;
ENode* p;
for ( i=0;iadjvex]++;
p=p->nextarc;
}
}
for ( i=0;i
void MGraph::DFS(int v,bool visited[])
{
visited[v]=true;
cout<<" "<
void SingleList::select_sort()
{ Node *p,*r,*small;
p=first->link;
if(p)
for(; p->link; p=p->link)
{ for(small=p,r=p->link; r; r=r->link)
if(small->data>r->data) small=r;
if(small!=p) swap(p->data, small->data);
}
};
直接插入排序:
template //用带表头节点的单链表存储
void SingleList::DirInsert()
{ Node *head,*q,*p1,*p2;
if(first->link)
{ head=first->link->link; //head是待插入元素的链表头
first->link->link=NULL; //first是只有一个节点的有序链表
while(head)
{ q=head; head=head->link;//从待插入链中取下一个节点
p1=first; p2=first->link; //p1是p2的直接前驱节点
while(p2&&p2->datadata) //从前往后找插入位置
{ p1=p2; p2=p2->link; }
if(p2) //q插入在p1和p2之间
{ q->link=p2; p1->link=q; }
else //q插入在p2之后,即有序链的最后
{ q->link=NULL; p1->link=q; }
}
}
}
10.4
template
void sort(T a[],int n)
{ int i,j,k=0,m=-1,s,t;
T x;
while (ka[i+1])
{ x=a[i]; a[i]=a[i+1]; a[i+1]=x; s=i; }
m=s; t=m;
for (j=m;j>k;j--) //从下向上冒泡
if (a[j]
证明
住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问
: 快速排序算法的基本思想时,每次把一个集合划分成大于和小于某个基准值的两个子集合。最坏情况是两个子集合中总有一个是空集合,即将一个集合分成了一个子集合和一个作为基准值的元素。即最坏情况下划分的自己和比原集合的元素只少一个。故要划分n-1次才能使得子集合中的元素少于2,而每次划分子集合都要扫描整个集合,所以时间复杂度是O(n2)。
10.7
template //方法一
void sort(T a[],int n)
{
int i=0,j=n-1;
T x=a[0];
while (i=0&&j>i) j--; //找负数
if (j>i) a[i++]=a[j];
while (a[i]<0&&i
void Merge(T A[],T Temp[],int i1,int j1,int i2,int j2,int &k)
{ if (i1>j1&&i2>j2) cout << "wrong ! \n";
else if (i1>j1) while (i2<=j2) Temp[k++]=A[i2++];
else if (i2>j2) while (i1<=j1) Temp[k++]=A[i1++];
else if (A[i1] //p.196
void MergeSort(T A[],int n)
{ T *Temp=new T [n];
int i1,i2,j1,j2,i,k,size=1;
while (sizen-1) j2=n-1; else j2=j1+size;
Merge(A,Temp,i1,j1,i2,j2,k);
i1=j2+1;
}
for (i=0;i
本文档为【数据结构(陈惠南主编第二版)习题答案1-9章 【全】】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。