数据结构第三章到第九章练习题答案

第三章栈和队列借助栈实现单链表上的逆置运算。//stdafx.h#include<iostream>#include<tchar.h>#include"time.h"usingnamespacestd;//结点类structLinkNode{ intdata; LinkNode*link; LinkNode(constint&item,LinkNode*ptr=NULL) {data=item;link=ptr;} LinkNode(LinkNode*ptr=NULL){link=ptr;}};#pragmaonce//带附加头结点的单链表classList{public: List(void);//构造函数 List(constint&x);//构造函数 ~List(void);//析构函数 voidinput(intn);//输入 voidoutput(void);//输出 voidmakeEmpty(void);//清空 voidinverse(void);//逆转函数protected: LinkNode*first;//链表头指针};#pragmaonce#include".\list.h"classstack{public: stack(void); ~stack(void);protected: LinkNode*top; friendclassList;public: voidPush(constint&x); boolPop(); boolIsEmpty(void){return(top==NULL)?true:false;};};#include"StdAfx.h"#include".\list.h"#using<mscorlib.dll>List::List(constint&x){ first=newLinkNode(x);}List::List(void){ first=newLinkNode;}List::~List(void){ makeEmpty();}voidList::input(intn){ LinkNode*newNode; first=newLinkNode; for(inti=0;i<n;i++) { intx=rand()%100; newNode=newLinkNode(x); newNode->link=first->link; first->link=newNode; }}voidList::output(void){ LinkNode*current=first->link; while(current!=NULL) { cout<<current->data<<""; current=current->link; } cout<<endl;}voidList::makeEmpty(void){ LinkNode*p; while(first->link!=NULL){ p=first->link; first->link=p->link; deletep; }}//逆转函数voidList::inverse(void){ stacks; LinkNode*p=first->link,*q; while(p!=NULL) { s.Push(p->data); p=p->link; } p=first->link; while(!s.IsEmpty()) { q=s.top; p->data=q->data; p=p->link; s.Pop(); }}#include"StdAfx.h"#include".\stack.h"#using<mscorlib.dll>stack::stack(void):top(NULL){}stack::~stack(void){}//入栈voidstack::Push(constint&x){ top=newLinkNode(x,top);}//出栈boolstack::Pop(){ if(IsEmpty()==true)returnfalse; LinkNode*p=top; top=top->link; deletep; returntrue;}#include"stdafx.h"#include".\list.h"#usingll>usingnamespaceSystem;int_tmain(){srand(time(NULL));Listl;//调用输入函数l.input(10);//调用输出函数l.output();cout<<"调用逆转函数"<<endl;l.inverse();//调用输出函数l.output(); return0;}编写一个算法，将一个非负的十进制整数N转换为另一个基为B的B进制数。//stdafx.h#include<iostream>#include<tchar.h>usingnamespacestd;structLinkNode{ intdata; LinkNode*link; LinkNode(constint&item,LinkNode*ptr=NULL) {data=item;link=ptr;} LinkNode(LinkNode*ptr=NULL){link=ptr;}};#pragmaonceclassstack{public: stack(void); ~stack(void);voidPush(constint&x); boolPop(int&x); boolIsEmpty(void){return(top==NULL)?true:false;};protected: LinkNode*top;};#include"StdAfx.h"#include".\stack.h"#using<mscorlib.dll>stack::stack(void):top(NULL){}stack::~stack(void){}voidstack::Push(constint&x){ top=newLinkNode(x,top);}boolstack::Pop(int&x){ if(IsEmpty()==true)returnfalse; LinkNode*p=top; top=top->link; x=p->data; deletep; returntrue;}#include"stdafx.h"#include".\stack.h"#using<mscorlib.dll>usingnamespaceSystem;int_tmain(){intn,m,temp,yu;cout<<"输入十进制数:";cin>>n;cout<<"输入基数:";cin>>m;stackl;while(n!=0&&m!=0){ temp=n%m; n=n/m; l.Push(temp);}while(!l.IsEmpty()){ l.Pop(yu); cout<<yu; }cout<<endl; return0;}试编写一个算法，求解最大公因数问题：在求两个正整数m和n的最大公因数常常使用辗转相除法，反复计算直到余数为零为止。其递归定义为：//stdafx.h#include<iostream>#include<tchar.h>#include<math.h>usingnamespacestd;intf(intn1,intn2);#include"stdafx.h"#using<mscorlib.dll>usingnamespaceSystem;int_tmain(){intn1,n2;cout<<"Enterthefirstpositivenumber:"<<endl;cin>>n1;cout<<"Enterthesecondpositivenumber:"<<endl;cin>>n2;if(n1>0&&n2>0){cout<<n1<<"和"<<n2<<"的最大公约数是："<<f(n1,n2)<<endl;}else cout<<"非法数据"<<endl; return0;}intf(intn1,intn2){intt; while(n2!=0) { t=n1%n2; n1=n2; n2=t; } returnn1;}3.23假设以数组Q[m]存放循环队列中的元素，同时设置一个标志tag,以tag==0和tag==1来区别在对头指针〔front〕和对尾指针〔rear〕相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入〔EnQueue〕和删除〔DeQueue〕算法。#include<iostream>#include<tchar.h>#include<time.h>usingnamespacestd;#pragmaonceclassSeqQueue{public: SeqQueue(intsize=10); ~SeqQueue(void);protected: intrear,front,tag; int*element; intmaxSize;public: boolEnQueue(constint&x); boolDeQueue(void); boolIsEmpty(void){return(front==rear&&tag==0)?true:false;} boolIsFull(void){return(front==rear&&tag==1)?true:false;} friendostream&operator<<(ostream&os,SeqQueue&Q);};#include"StdAfx.h"#include".\SeqQueue.h"#using<mscorlib.dll>SeqQueue::SeqQueue(intsize):rear(0),front(0),tag(0),maxSize(size){ element=newint[maxSize];}SeqQueue::~SeqQueue(void){ delete[]element;}boolSeqQueue::EnQueue(constint&x){ if(IsFull()==true)returnfalse; element[rear]=x; rear=(rear+1)%maxSize; tag=1; returntrue;}boolSeqQueue::DeQueue(void){ if(IsEmpty()==true)returnfalse; front=(front+1)%maxSize; tag=0; returntrue;}ostream&operator<<(ostream&os,SeqQueue&Q){ intnum; if(Q.front==Q.rear&&Q.tag==1) num=Q.maxSize; else num=(Q.rear-Q.front+Q.maxSize)%Q.maxSize; for(inti=0;i<num;i++) os<<(i+Q.front)%Q.maxSize<<":"<<Q.element[(i+Q.front)%Q.maxSize]<<'\t'; returnos;}#include"stdafx.h"#include".\SeqQueue.h"#using<mscorlib.dll>usingnamespaceSystem;int_tmain(){srand(time(NULL));SeqQueueq; cout<<"CalltheEnQueuefunction"<<endl; for(inti=0;i<9;i++) { q.EnQueue(rand()%100); } cout<<q<<endl; cout<<"CalltheDeQueuefunction"<<endl; q.DeQueue(); q.DeQueue(); cout<<q<<endl; return0;}数组、串与广义表Am*n中的某一元素A[i][j]是第i行中的最小值，同时又是第j列中的最大值，那么称此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵，试编写一个函数，确定鞍点在数组中的位置〔假设鞍点存放在时〕，并分析该函数的时间复杂度。#include<iostream>#include<tchar.h>usingnamespacestd;#include"stdafx.h"#include<time.h>#using<mscorlib.dll>usingnamespaceSystem;int_tmain(){intA[10][10],rsize,row,column,maxC,minD,max,min;srand(time(NULL));for(row=0;row<10;row++) {for(column=0;column<10;column++) { A[row][column]=rand()%(100/(10-row)+100/(10-column)); cout<<A[row][column]<<'\t'; }}for(rsize=0;rsize<10;rsize++) {minD=0; min=A[rsize][0];for(column=1;column<10;column++) { if(min>A[rsize][column]) { minD=column; min=A[rsize][minD]; }}maxC=0; max=A[0][minD];for(row=1;row<10;row++) { if(max<A[row][minD]) { maxC=row; max=A[row][minD]; }} if(max==min) cout<<"Array["<<rsize+1<<"]["<<minD+1<<"]是鞍点"<<endl;} return0;}时间复杂度分析：第二个for的嵌套循环是寻找鞍点的主要程序，假设数组A[m][n]，那么第一、二个内嵌循环时间代价分别为t1(n)=O〔f〔n〕〕和t2(m)=O〔g〔m〕〕，外循环的时间复杂度为t〔m〕=O〔F〔m〕〕那么整个程序段的时间复杂度为T=t〔m〕×〔t1(n)+t2(m)〕因为for语句里if后面语句被执行的平均次数为〔n-1〕+〔n-2〕…+1+0=n/2；所以f〔n〕=n/2*2+n*3+2=n*4+2；那么t1(n)=O〔f〔n〕〕=O〔n〕，同理得t2(m)=O〔g〔m〕〕=O〔m〕，而最后的if后面语句被执行的平均次数为〔m+1〕/2那么T=O((2+2+t1+2+t2+1)×m+2+(m+1)/2)=O(max{m×n,m×m})4.13所谓回文，是指从前向后顺读和从后向前读都一样的不含空白字符的串。例如did,madamimadam,pop即是回文。试编写一个算法，以判断一个串是否是回文。#include<iostream>#include<tchar.h>#include<string>usingnamespacestd;//结点类#ifndefstdafx_h#definestdafx_htemplate<classT>structLinkNode{ Tdata; LinkNode*link; LinkNode(constT&item,LinkNode*ptr=NULL) {data=item;link=ptr;} LinkNode(LinkNode*ptr=NULL){link=ptr;}};#endif/#pragmaoncetemplate<classT>classCCStack{public: CCStack(void); ~CCStack(void);protected: LinkNode<T>*top;public: voidPush(constT&x); boolPop(); boolIsEmpty(void){return(top==NULL)?true:false;}; TgetTop();};#include"StdAfx.h"#include".\cstack.h"#using<mscorlib.dll>template<classT>CCStack<T>::CCStack(void):top(NULL){}template<classT>CCStack<T>::~CCStack(void){}template<classT>voidCCStack<T>::Push(constT&x){ top=newLinkNode<T>(x,top);}template<classT>boolCCStack<T>::Pop(){ if(IsEmpty()==true)returnfalse; LinkNode<T>*p=top; top=top->link; deletep; returntrue;}template<typenameT>TCCStack<T>::getTop(){ Tx; if(IsEmpty()==true)returnNULL; x=top->data; returnx;}#include"stdafx.h"#include".\cstack.cpp"#using<mscorlib.dll>usingnamespaceSystem;int_tmain(){stringa; booltemp=true; inti=0; CCStack<char>st; cin>>a; while(a[i]!='\0') { st.Push(a[i]); i++; } i=0; while(a[i]!='\0') { if(a[i]==st.getTop()) { st.Pop(); i++; } else { temp=false; break; } } if(temp) cout<<"此字符是回文"<<endl; else cout<<"此字符不是回文"<<endl; return0;}4.15编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。//stdafx.h#include<iostream>#include<tchar.h>#include<string>usingnamespacestd;#include"stdafx.h"#using<mscorlib.dll>usingnamespaceSystem;int_tmain(){stringa; intk,*num; char*A; cin>>a;k=a.length(); A=newchar[k]; num=newint[k]; frequency(a,A,num,k=0); for(inti=0;i<k;i++) { cout<<A[i]<<":"<<num[i]<<"个"<<endl; } delete[]A; delete[]num; return0;}voidfrequency(strings,charA[],intC[],int&k){ inti,j,len=s.length(); A[0]=s[0];C[0]=1; //种类数 k=1; for(i=1;i<len;i++) C[i]=0; for(i=1;i<len;i++) { j=0; while(j<k&&A[j]!=s[i])j++; if(j==k) { A[k]=s[i]; C[k]++; k++; } elseC[j]++; }}第五章树表示法，分别画出图示二叉树的存储表示。答：1234567891234567891011121314151617185.15写出向堆中参加数据4，2，5，8，3，6，10，14时，每参加一个数据后堆的变化。答：判断以下序列是否是最小堆？如果不是，将它调整为：｛100，86，48，73，35，39，42，57，66，21｝答：不是5.18一棵二叉树的前序遍历的结果是ABECDFGHIJ，中序遍历是EBCDAFHIGJ，试画出这颗二叉树。答：5.19给定权值集合｛15，03，14，02，06，09，16，17｝，构造相应的Huffman树，并计算它的带权外部路径长度。答：它的带权外部路径长度WPL=229第六章集合与字典6.1设A=｛1，2，3｝，B=｛3，4，5｝，求以下结果：〔1〕A+B；〔2〕A*B；〔3〕A-B；〔4〕A.Contains(1)；〔5〕A.AddMember(1)；〔6〕A.DelMember〔1〕；〔7〕A.Min〔〕。答：〔1〕A+B=｛1，2，3，4，5｝〔2〕A*B={3}〔3〕A-B={1，2}〔4〕A.Contains(1)=true〔5〕A.AddMember(1)=false，集合A不变〔6〕A.DelMember〔1〕=true，集合A={2，3}〔7〕A.Min〔〕=16.9设散列表为HT[13]，散列函数为H〔key〕=key%13，用闭散列法解决冲突，对以下关键码序列12，23，45，57，20，03，78，31，15，36造表。采用线性探查法寻找下一个空位，画出相应的散列表。答：Hash(12)=12Hash(23)=10Hash(45)=6Hash(57)=5Hash(20)=7Hash(3)=3Hash(78)=0Hash(31)=5Hash(15)=2Hash(36)=10012345678910111278153574520312336126.10设有150个记录要存储到散列表中，并利用线性探查法解决冲突，要求找到所需记录的平均比拟次数不超过2次。试问散列表需要设计多大？〔设a是散列表的装载因子，那么有ASLsucc=(1+1/(1-a))/2〕答：设散列表的长度为m；因为a=150/m，ASLsucc=〔1+1/〔1-a〕〕/2且ASLsucc<=2;所以得m=225搜索结构7.2设有序顺序表中的元素依次为017，094，154，170，275，503，509，512，553，612，677，765，897，908。试画出对其进行顺序搜索时的判定树。答：7.3设有序顺序表中的元素依次为017，094，154，170，275，503，509，512，553，612，677，765，897，908。试画出对其进行折半搜索时的判定树。答：8.1请给出该图的邻接矩阵，邻接表和逆邻接表。解：邻接矩阵：邻接表：逆邻接表：8.2对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判断以下有关问题;(1)图中有多少条边？(2)任意两个顶点i和j是否有边相连？(3)任意一个顶点的度是多少？解：〔1〕用邻接矩阵表示无向图时，由于其为对称矩阵，所以统计矩阵的上三角或者下三角非零元素个数即为图的边数，用邻接表表示时，邻接表中的边链表的边结点个数。除以2便是其边数。用邻接矩阵表示有向图时，矩阵的上非零个数即为其边数，用邻接表表示时，邻接表中的边链表的边结点个数便是其边数。〔2〕用邻接矩阵表示无向图时，如果邻接矩阵中i行、j列不为非零元素那么表示其有边相连。用邻接表表示时，如果顶点i的边结点的desk域有j，那么可判断i和j相连。用邻接矩阵表示有向图时，如果邻接矩阵中i行、j列或j行、i列不为非零元素表示此i和j有边连。用邻接表表示时，如果顶点i的边结点的desk域有j或顶点j的边结点的de