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

第三章 栈和队列3.10借助栈实现单链表上的逆置运算。/ stdafx.h #include #include #includetime.husing namespace std;/结点类struct LinkNodeint data; LinkNode *link;LinkNode(const int& item, LinkNode *ptr = NULL)data=item; link=ptr;LinkNode( LinkNode *ptr = NULL)link=ptr;/list.h#pragma once/带附加头结点的单链表class Listpublic:List(void);/构造函数List(const int& x);/构造函数List(void);/析构函数void input(int n);/输入void output(void);/输出void makeEmpty(void);/清空void inverse(void);/逆转函数protected:LinkNode* first;/链表头指针;/ stack.h#pragma once#include .list.h class stackpublic:stack(void);stack(void);protected: LinkNode* top;friend class List;public:void Push(const int& x);bool Pop();bool IsEmpty(void)return(top=NULL)?true:false;/ list.cpp#include StdAfx.h#include .list.h#using List:List(const int& x)first= new LinkNode(x);List:List(void)first= new LinkNode;List:List(void)makeEmpty();void List:input(int n)LinkNode * newNode;first=new LinkNode;for(int i=0;ilink=first-link;first-link=newNode;void List:output(void)LinkNode *current=first-link;while(current!=NULL)coutdatalink;coutlink!=NULL)p=first-link;first-link=p-link;delete p;/逆转函数void List:inverse(void)stack s;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();/ Stack.cpp#include StdAfx.h#include .stack.h#using stack:stack(void): top(NULL) stack:stack(void)/入栈void stack:Push(const int& x)top=new LinkNode(x,top);/出栈bool stack:Pop()if(IsEmpty()=true) return false; LinkNode *p=top;top=top-link;delete p;return true;/Main.cpp#include stdafx.h#include .list.h#using using namespace System;int _tmain() srand(time(NULL); List l; /调用输入函数 l.input(10); /调用输出函数 l.output(); cout调用逆转函数endl; l.inverse(); /调用输出函数 l.output();return 0;3.12编写一个算法，将一个非负的十进制整数N转换为另一个基为B的B进制数。/ stdafx.h #include #include using namespace std;struct LinkNodeint data;LinkNode *link;LinkNode(const int& item, LinkNode *ptr = NULL)data=item; link=ptr;LinkNode( LinkNode *ptr = NULL)link=ptr;/stack.h#pragma onceclass stackpublic:stack(void);stack(void);void Push(const int& x);bool Pop(int& x);bool IsEmpty(void)return(top=NULL)?true:false;protected:LinkNode* top;/stack.cpp#include StdAfx.h#include .stack.h#using stack:stack(void): top(NULL) stack:stack(void) void stack:Push(const int& x)top=new LinkNode(x,top);bool stack:Pop(int& x)if(IsEmpty()=true) return false; LinkNode *p=top;top=top-link;x=p-data;delete p;return true;/main.cpp#include stdafx.h#include .stack.h#using using namespace System;int _tmain() int n, m, temp,yu; coutn; coutm; stack l; while(n!=0 & m!=0) temp=n%m; n=n/m; l.Push(temp); while(!l.IsEmpty() l.Pop(yu); coutyu; coutendl;return 0;3.21试编写一个算法，求解最大公因数问题：在求两个正整数m和n的最大公因数常常使用辗转相除法，反复计算直到余数为零为止。其递归定义为：/ stdafx.h #include #include #include using namespace std;int f(int n1,int n2);/main.cpp#include stdafx.h#using using namespace System; int _tmain() int n1,n2; coutEnter the first positive number: n1; coutEnter the second positive number: n2; if(n10 & n20) cout n1 和 n2 的最大公约数是： f( n1, n2) endl; else cout非法数据endl;return 0;int f(int n1,int n2) int t;while(n2!=0) t= n1 % n2;n1= n2;n2= t; return n1;3.23假设以数组Qm存放循环队列中的元素，同时设置一个标志tag,以tag=0和tag=1来区别在对头指针（front）和对尾指针（rear）相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入（EnQueue）和删除（DeQueue）算法。/ stdafx.h#include #include #includeusing namespace std;/SeqQueue.h#pragma onceclass SeqQueuepublic:SeqQueue(int size=10);SeqQueue(void);protected:int rear,front,tag;int *element;int maxSize;public:bool EnQueue(const int& x);bool DeQueue(void);bool IsEmpty(void)return (front=rear & tag=0)?true:false;bool IsFull(void)return (front=rear & tag=1)?true:false;friend ostream& operator (ostream& os,SeqQueue& Q);/SeqQueue.cpp#include StdAfx.h#include .SeqQueue.h#using SeqQueue:SeqQueue(int size):rear(0),front(0),tag(0),maxSize(size)element=new intmaxSize;SeqQueue:SeqQueue(void)delete element;bool SeqQueue:EnQueue(const int& x)if(IsFull()=true) return false;elementrear=x;rear=(rear+1) % maxSize;tag=1;return true;bool SeqQueue:DeQueue(void)if(IsEmpty()=true) return false;front=(front+1) % maxSize;tag=0;return true;ostream& operator (ostream& os,SeqQueue& Q)int num;if(Q.front=Q.rear & Q.tag=1)num=Q.maxSize;elsenum=(Q.rear-Q.front+Q.maxSize)%Q.maxSize;for(int i=0;inum;i+)os(i+Q.front)%Q.maxSize:Q.element(i+Q.front)%Q.maxSizet;return os;/main.cpp#include stdafx.h#include .SeqQueue.h#using using namespace System;int _tmain()srand(time(NULL); SeqQueue q;coutCall the EnQueue functionendl;for(int i=0;i9;i+)q.EnQueue(rand()%100);coutqendl;coutCall the DeQueue functionendl;q.DeQueue();q.DeQueue();coutqendl;return 0;第四章 数组、串与广义表4.12若矩阵Am*n中的某一元素Aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵，试编写一个函数，确定鞍点在数组中的位置（若鞍点存放在时），并分析该函数的时间复杂度。/ stdafx.h#include #include using namespace std;/main.cpp#include stdafx.h#include#using using namespace System;int _tmain() int A1010,rsize,row,column,maxC,minD,max,min; srand(time(NULL); for(row=0;row10;row+) for (column=0;column10;column+) Arowcolumn=rand()%(100/(10-row)+100/(10-column); coutArowcolumnt; for(rsize=0;rsize10;rsize+) minD=0; min=Arsize0; for(column=1;columnArsizecolumn) minD=column; min=ArsizeminD; maxC=0; max=A0minD; for(row=1;row10;row+) if(maxArowminD) maxC=row; max=ArowminD; if(max=min) coutArrayrsize+1minD+1是鞍点endl; return 0;时间复杂度分析：第二个for的嵌套循环是寻找鞍点的主要程序，假设数组Amn，则第一、二个内嵌循环时间代价分别为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(maxmn , mm)4.13所谓回文，是指从前向后顺读和从后向前读都一样的不含空白字符的串。例如did,madamimadam,pop即是回文。试编写一个算法，以判断一个串是否是回文。/ stdafx.h#include #include #includeusing namespace std;/结点类#ifndef stdafx_h#define stdafx_htemplatestruct LinkNodeT data;LinkNode *link;LinkNode(const T& item, LinkNode *ptr = NULL)data=item; link=ptr;LinkNode( LinkNode *ptr = NULL)link=ptr;#endif/stack.h#pragma oncetemplateclass CCStackpublic:CCStack(void);CCStack(void);protected:LinkNode* top;public:void Push(const T& x);bool Pop();bool IsEmpty(void)return(top=NULL)?true:false;T getTop();/stack.cpp#include StdAfx.h#include .cstack.h#using templateCCStack:CCStack(void): top(NULL)templateCCStack:CCStack(void)templatevoid CCStack:Push(const T& x)top=new LinkNode(x,top);templatebool CCStack:Pop()if(IsEmpty()=true) return false; LinkNode *p=top;top=top-link;delete p;return true;templateT CCStack:getTop()T x;if(IsEmpty()=true) return NULL;x=top-data;return x;/main.cpp#include stdafx.h#include .cstack.cpp#using using namespace System;int _tmain() string a;bool temp=true;int i=0;CCStack st;cina;while(ai!=0)st.Push(ai);i+;i=0;while(ai!=0)if(ai=st.getTop()st.Pop(); i+;elsetemp=false;break;if(temp)cout此字符是回文endl;elsecout此字符不是回文endl;return 0;4.15编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。/ stdafx.h #include #include #includeusing namespace std;/main.cpp#include stdafx.h#using using namespace System;int _tmain() string a;int k,*num;char *A; cina; k=a.length();A = new chark;num = new intk;frequency(a, A, num,k=0 );for ( int i = 0; i k; i+ )coutAi:numi个endl;delete A;delete num;return 0;void frequency( string s, char A , int C , int &k ) int i, j, len = s.length( );A0 = s0; C0 = 1; /种类数k = 1; for ( i = 1; i len; i+ )Ci = 0;for ( i = 1; i len; i+ ) j = 0;while ( j k & Aj != si ) j+;if ( j = k ) Ak = si;Ck+;k+; else Cj+; 第五章 树5.2使用顺序表示和二叉链表表示法，分别画出图示二叉树的存储表示。答：1234567891 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 185.15写出向堆中加入数据4，2，5，8，3，6，10，14时，每加入一个数据后堆的变化。答：5.16判断以下序列是否是最小堆？如果不是，将它调整为：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设散列表为HT13，散列函数为H（key）=key%13，用闭散列法解决冲突，对下列关键码序列12，23，45，57，20，03，78，31，15，36造表。采用线性探查法寻找下一个空位，画出相应的散列表。答：Hash(12)=12 Hash(23)=10 Hash(45)=6 Hash(57)=5Hash(20)=7 Hash(3)=3 Hash(78)=0 Hash(31)=5Hash(15)=2 Hash(36)=100 1 2 3 4 5 6 7 8 9 10 11 1278153574520312336126.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 的边结点的desk域有i，则可判断i和j相连。（3）用邻接矩阵表示无向图时，统计处第i行或第i列的非零元素个数，就可得到顶点i的度。用邻接表表示时，统计顶点i的边链表中边结点个数即为其度。用邻接矩阵表示有向图时，第i行和i列的非零元素个数总数即为其度。用邻接表表示时，统计顶点i的边链表中边结点个数和其他所有顶点对应的边链表中边结点的desk域为i的个数之和即为其度。8.4