数据结构 张铭 习题.doc
【精品文档】如有侵权，请联系网站删除，仅供学习与交流数据结构 张铭 习题 本章练习题 答案分页： 1 2 1、解答：【题意解析】 本题指定了字符的顺序，所以不能按照ASCII字符顺序来排序。【典型错误】 1.不按照题目给出的字符顺序进行排序，而按照ASCII字符顺序。 2.没有给出排序结果 3.认为顺序存储法比较节约空间，事实上由于字符空隙，顺序法并不节约空间； 4. 没有比较各种方法的优劣。【数据结构】 本题可以采用的存储结构有顺序（数组）和链表。 1. 用二维数组arrayNUMOFSTRINGMAX_LENGTH，此题可定义const int NUMOFSTRING=8, MAX_LENGTH=5;B8990B90 CRSI0CXY0 PAB0 PABC05C0 70 优点:为紧凑存储结构，没有用于存储其他附加的信息，表示方法比较直观简单，代码实现十分容易。 缺点:为每个但此都开辟了同样长度的空间,造成空间的浪费。 2. 用链表的结构存储，结点为结构 struct strings char stringMAX_LENGTH; strings *pNext; 优点:如果有后续工作如反复增删结点,效率很高.并且可以使用不连续的空间。 缺点:操作过程相对复杂,容易出错.而且排序过程需要从表头开始沿链索一个结点一个结点的比较搜索,相当费时。 3. 索引存储 是顺序存储的一种推广.使用一个字符串char data500,其中将大小长度不等的数据结点(单词)顺序存储其中.令使用一个字符指针数组 char* indexn,存储一系列指针,每个指针指向存储区域的一个数据结点. 排序时,直接对index中的地址值进行调换修改即可,而不用修改data中的任何内容。索引存储的优点是:由于单词长度不同,在存储时充分考虑了这个因素,可以节省空间,此外由于交换的不是单词本身而是单词的地址,可以节省时间,从时空两方面得到了优化。【排序结果】B899，B9，CRSI，CXY，PAB，PABC，5C，7 2、解答： 【题意解析】 本题没有指明这100个实数是否存在相等的情况，在这里，我们考虑存在多个最大值的情形（即100个实数可能有相等的），为了保存其位置，利用int pos100（因为有可能这100个实数都是相同的）来保存最大值的所有位置。【典型错误】 1. 用int类型的数组来保存这100个元素，没有注意题目中说的是“每个元素的值都是实数”。 2. 求最大值的时候代码如下： temp=0; for(int i=0;i<100;i+) if(Numi>temp) temp=Numi;评注：这样是错误的，例如：当Numi都是负数的时候。 3. 未考虑可能存在多个最大值的情况，只保存了一个最大值的位置。【数据结构】 本题可以采用的存储结构有顺序（数组），链表和索引。本题最好使用数组存储结构。由于其他存储方法需要记录附加信息，使得空间有效利用不能够最大化。因此在空间上顺序存储是最优的。时间上，无论如何此题都要遍历所有的数，因此O(n)为可能的最优时间代价。加之此题的规模较小，因此使用大家最熟悉的顺序存储是较为优先的选择。【算法描述】 1. 由于最大值可能不止一个，甚至可能都是最大值，所以创建一个长度为100的整型数组pos100，用来记录最大值的位置。 2. 初始情况，取这个数组的第一个位置为最大值所在的位置，存入变量position中。 3. 假设有n（1n99）个最大值，那么pos0, 1, 2, , n-1记录这些最大值的位置，且posn=-1(-1是标记值，表明pos数组下标为n-1及以前的元素记录了最大值的位置)；假设有n（n=100）个最大值，那么pos0, 1, 2, , n-1记录这些最大值的位置，pos数组不再设-1的标记值。具体源码如下： # include <iostream.h> void main() /存放100个实数的数组 double Num100=4543.9,4543.9,3,45,654.7,7,66,35,45,4,6,4543.9,5,46,54,6,43,5.980,34; /记录最大值所在位置的数组 int pos100; /初始设定数组的第1个元素为最大值 int position=0; /j指示位置数组pos的下标 int j=1; for(int i=1;i<100;+i) if(Numi>Numposition) position=i; /记下新的最大值的位置 j=1; /位置数组pos的下标恢复为1，下标为0的位置为position预留 else if(Numi= Numposition) posj+=i; /记下重复最大值的位置 /位置数组pos的下标为0的位置为position预留 pos0=position; /-1为标识值，表示位置数组pos下标为0, 1, 2(j-1)的位置存 /放的是最大值所在的位置 if(j<100) posj=-1; cout<<"最大值为："<< Numposition<<endl; cout<<"最大值所在的位置为："<<endl; for(i=0; i<100; +i) if(posi=-1) /-1是标识值 break; cout<<"第"<<(posi+1)<<"个元素"<<endl; 第一章概论 练习答案上一章 下一章 本章练习题 答案分页： 1 2 3、解答：【逻辑结构】 逻辑结构由结点集合K和关系集合R来表示,以学生每周的课程表为例:将每天的课程安排数据作为结点，一共引入7个结点，它们的名称依次为“星期一”，“星期二”，“星期三”，“星期日”。全部结点组成结点集K。 这些结点是复合类型，是一个结构体，包括当日课程的名称，时间和地点等。这些结点两两之间有一个时间关系r,r=(“星期一“，“星期二”)，（“星期二”，“星期三”），（“星期三”，“星期四”），（“星期四”，“星期五”），（“星期五”，“星期六”），（“星期六”，“星期日”）。此集合中的6个元素描述了“时间先后”关系r。此外，还引入一个关系r*=“星期日”，“星期一”，r*只含有一个元素，以表示星期日和下一周工作日的时间顺序。r和r*共同构成关系集R。其中r属于线性结构。R是一种环行的关系。【存储结构】 几种可行的存储方案比较 1.顺序表：见图一 优点：逻辑清晰,查阅修改方便；缺点：需要占用整块的存储空间，对空间要求较大 星期课次一二三四五六日12 课程名上课地点授课老师 34 56 78 910 图一 顺序表存储课程表 2.索引图二 索引结构的课程表构造索引表，其中的指针分别指向每一天的课程 优点：逻辑较清晰，不占用整块的存储空间，缺点：算法较复杂，附加的空间代价较高（有索引表） 3链表：链接的方法是可以采纳的一个方法,每个指针都指向逻辑关系中的紧邻后继,最后一个结点的指针指向首结点,构成一个循环链表.链表结构检索较繁琐.【相关运算】 常见的运算包括增、删、查、改运算，课程表的抽象数据类型可以定义如下：template<class ELEM> class table /当程序使用此table模板时，应该在前面附加#include<table> public: /创建一张空课程表 table < ELEM > t; /创建一张天数为k的课程表，可默认k为7 table < ELEM > t(int k); /设置某天的课程(时间地点等),该结点的地址可由索引表找出 virtual void Setcourse( ELEM & pday ) = 0; /把一个新的结点插入课程表，使该结点在表中位置是nPos 如果nPos = -1 /则插入到表尾部(同时地址加入索引表) virtual void Addday( const ELEM * pday, int nPos = -1 ) = 0; /删除课程表中某天(结点),释放该结点的空间,该结点的地址可由索引表找出 virtual void Removeday( ELEM & pday ) = 0; /清空整个课程表，成功返回true virtual bool Clearall() = 0; /清空某天(结点)的所有内容，该结点的地址可由索引表找出,成功返回true virtual bool Clearday( ELEM & pday )= 0; /修改某天(结点)的课程(时间 地点等),该结点的地址可由索引表找出 virtual void Changecourse( ELEM & pday ) = 0; /输出某天(结点)的课程内容,该结点的地址可由索引表找出 virtual void Printday( ELEM & pday) = 0; /输出所有课程内容（结点） virtual void PrintList() = 0; /根据系统时间查询当天课程 virtual void Current() = 0; /统计课程总数 virtual int Number() = 0; / 析构函数，清空课程表 table(); private: ELEM * m_index; /索引表头指针 本章练习题 答案分页： 1 2 本章练习题 答案分页： 1 2第二章线性表、栈和队列 练习上一章 下一章本章练习1、（教材习题2.1）给出一个算法，求单链表X中，内容为a的结点地址。 2、（教材习题2.5）给出一个算法，求出循环表中结点的个数。 3、（教材习题2.8）编号为1，2，3，4的四辆列车，顺序开进一个栈式结构的站台；问开出车站的顺序有多少种可能，请具体写出来。4、（教材习题2.10）环状的队列，写出计算队列元素个数的程序。 5、（教材习题2.19）现有4个元素作为双端队列的输入，问可以得到多少种不同的排列？ 参考答案 第二章线性表、栈和队列 练习答案上一章 下一章 本章练习题 答案分页： 1 2 1、解答：【题意解析】 本题没有指明是否存在多个内容为a的地址，在这里，我们考虑存在多个结点内容为a的情形。【典型错误】 没有考虑内容为a的地址可能有多个。【数据结构】由于链表中内容为a的结点数目不确定，可以选择用一个新链表来存放找到的结点地址。这样的存储结构优于定长数组。本题中涉及到两个链表：原链表ListNode和用于存储结点地址的新链表ListAddress。【算法描述】 1. 设pfirst和qfirst分别是这两个链表的头指针，p，q为指针变量。 2. p从链表X的表头开始向后移动，每当遇到原链表中内容为a的结点，就在新链表中增加一个结点记录下其地址（用指针指向该结点来进行记录），如此循环直到链表X的表尾。struct ListNode /链表结点定义 ELEM data; /数据类型为ELEM ListNode* plink; /指向后继结点的指针 ; ListNode* pfirst; /pfirst指向原链表第一个结点 ListNode* p; /原链表的指针变量，程序运行时可对其所指结点进行各种运算 p=pfirst; /指向头指针 Struct ListAddress /用于存放地址的新链表 ListNode * address; /存放地址,类型为指向链表X的结点的指针 ListAddress* qlink; /新链表的指针变量 ; ListAddress* qfirst; /qfirst指向新链表第一个结点 qfirst->qlink=NULL; /空表 ListAddress* q=qfirst; /指向头指针 void find(ELEM a) /用于查找内容为a的结点，并记录其地址，参数为待查数据a while(p!=NULL) /未到达链表尾结点 if(p->data= =a) /找到符合条件的结点，插入新链表 q->qlink=new ListAddress; /创建内存空间 q->qlink->address=p; /存储指向该结点的指针 q=q->qlink; /指针向后移 q->qlink=NULL; p=p->plink; /指针后移继续查找 2、解答： 【算法描述】 判断已经遍历整个循环表的方法：使用一个指针变量link从链表首元素向后遍历整个链表，直到link=first时，说明该结点即尾结点。设空表时结点数count为0（此时first->link=first），每经过一个结点count加1，直到到达尾结点。 struct ListNode ELEM data; ListNode* link; ; int Length (ListNode* first) /first为循环表的头指针 ListNode* p; p=first; int count=0; /用于记录结点数,空链表时结点数为0 while(p->link!=first) /未到达尾结点 p=p->link; /指针向后移 count+; /结点数加1 return count; 3、解答：有14种可能：【思路】 先进站的车可以先开，也可以后开。只有一种情况不可能：编号大的车开出后，比其编号小的车反序开出。也即编号大的车开出后，编号比其小的车只能由大到小依次开出（中间可以插入编号更大的车，但此车后面的编号小的车也要遵守此规则）。例如312的开出顺序是不可能的。对所有车进行全排列共有24种出法。但4开头的只能有一种：4321。所以少了3的全排列-1=5种。三开头的时候，必须先2后1开出，先1后2时4的位置有三种： 3124、3142、3412，所以少了三种。1或2开头的时候，后面的车如果是4，则最后两辆必须是3、2或3、1。所以又少了1423、2413两种。总共少了5+3+2=10种，有24-10=14种开出法。 下面用+表示进站，-表示出站： 1234：1+ 1- 2+ 2- 3+ 3- 4+ 4- 1243：1+ 1- 2+ 2- 3+ 4+ 4- 3- 1324：1+ 1- 2+ 3+ 3- 2- 4+ 4- 1342：1+ 1- 2+ 3+ 3- 4+ 4- 2- 1432：1+ 1- 2+ 3+ 4+ 4- 3- 2- 2134：1+ 2+ 2- 1- 3+ 3- 4+ 4- 2143：1+ 2+ 2- 1- 3+ 4+ 4- 3- 2314：1+ 2+ 2- 3+ 3- 1- 4+ 4- 2341：1+ 2+ 2- 3+ 3- 4+ 4- 1- 2431：1+ 2+ 2- 3+ 4+ 4- 3- 1- 3214：1+ 2+ 3+ 3 2 1 4+ 4 - 3241：1+ 2+ 3+ 3- 2- 4+ 4- 1- 3421：1+ 2+ 3+ 3- 4+ 4- 2- 1- 4321：1+ 2+ 3+ 4+ 4- 3- 2- 1- 本章练习题 答案分页： 1 2 第二章线性表、栈和队列 练习答案上一章 下一章 本章练习题 答案分页： 1 2 4、解答：【算法描述】 对于顺序队列 int Queue:length_of_queue() if(IsEmpty() return 0; if(front<=rear)return rear-front; else return maxsize+rear-front; 对于链式队列 int Queue:length_of_queue() if(IsEmpty() return 0; int total=0; for(ListPtr temp=front;temp!=rear;temp=temp->link)total+; return total; 5、解答： 双端队列可以在队列的两端进行插入和删除操作，既可在队尾进行插入/删除，又可在队头进行插入/删除。但第一个元素从左或右入队没有区别，以后每个元素都有两种入队方式。即有23=8种方法。不妨设元素为a,b,c,d,各种排列如下： 第一次放入a： a 第二次放入b： ab ba 第三次放入c： cab abc cba bac 第四次放入d： dcab cabd dabc abcd dcba cbad dbac bacd 故共有8种。 本章练习题 答案分页： 1 2 第三章字符串 练习上一章 下一章本章练习1、（教材习题3.1）设有字符串变量String A ''，B'MULE'，C'OLD'，D'MY' ; 请计算下列表达式 (a) A+B (b) B+A (c) D+C+B (d) B.substr(3，2) (e) C.substr(1，1) (f) A.str1ength() (g) D.str1ength() (h) B.Find('L') (i) C.FindLast('D') (j) D.insert(B,2) (k) B.insert(B,1) (1) B.remove(2，2) (m) B.remove(0，5) 2、（教材习题3.2）计算下列字符串P的特征向量Ni (a) 'A B C D E F G H' (b) 'I I I I I I I I' (c) 'B A B B A B A B' 注意串内字符间有空格隔开 3、设计算法用顺序结构存储的串s和串t的一个最长公共子串。4、编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。 参考答案 第三章字符串 练习答案上一章 下一章 本章练习题 答案分页： 1 2 1、解答：【典型错误】1. 在计算字符串长度时容易把结束符算在内，比如： A.strlength()=2 D.strlength()=32在计算子串的时候容易加入结束符，比如： B.substr(3,2)="En"3字符串的下标从从1开始，正确的是从0开始。4. D.insert(B,2) 应当在D字符串的第2个下标处插入B字符串，而不是插入B字符， B.remove(2,2) 是从B字符串的第2个下标处开始删除2个字符，这两个表达式的计算容易出错【计算结果】 (a) A+B="MULE" (b) B+A="MULE" (c) D+C+B="MYOLDMULE" (d) B.substr(3,2)="E" (e) C.substr(1,1)="L" (f) A.strlength()=0 (g) D.strlength()=2 (h) B.Find('L')=2 (i) C.FindLast('D')=2 (j) D.insert(B,2)="MYMULE" (k) B.insert(B,1)="MMULEULE" (l) B.remove(2,2)="MU" (m) B.remove(0,5)="" （空串） 2、解答： (a) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (b) 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 (c) 0 0 0 0 1 2 1 2 3 4 5 6 3 4 5 本章练习题 答案分页： 1 2 第三章字符串 练习答案上一章 下一章 本章练习题 答案分页： 1 2 3、解答：【算法描述】串s用i指针(1<=i<=s.len)。t串用j指针(1<=j<=t.len)。算法思想是对每个i(1<=i<=s.len，即程序中第一个while循环)，来求从i开始的连续字符串与从j(1<=j<=t.len，即程序中第二个WHILE循环)开始的连续字符串的最大匹配。程序中第三个(即最内层)的while循环，是当s中某字符(si)与t中某字符(tj)相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串(初始为0)，则最长公共子串的长度要修改。void maxcomstr(orderstring *s,*t; int index, length) int i,j,k,length1,con; index=0;length=0;i=1; while (i<=s.len) j=1; while(j<=t.len) if (si= =tj) k=1;length1=1;con=1; while(con) if(i+k<=s.len && j+k<=t.len && si+k=tj+k) /如果在s和t的长度内，对应字符相等，则指针k 后移 length1=length1+1;k=k+1; else con=0; /s和t对应字符不等时置标记退出 if(length1>length) index=i; length=length1; j+=k; /在t串中，从第j+k字符再与si比较 else j+; /t串取下一字符 i+; /s串指针i后移 4、解答：【算法描述】 由于字母共26个，加上数字符号10个共36个，所以设一长36的整型数组，前10个分量存放数字字符出现的次数，余下存放字母出现的次数。从字符串中读出数字字符时，字符的ASCII代码值减去数字字符 0的ASCII代码值，得出其数值(0.9)，字母的ASCII代码值减去字符A的ASCII代码值加上10，存入其数组的对应下标分量中。遇其它符号不作处理，直至输入字符串结束。void Count()/统计输入字符串中数字字符和字母字符的个数。 int i，num36； char ch； for(i0；i<36；i+)numi0；/ 初始化 while(chgetchar()!=#) /#表示输入字符串结束。 if(0<=ch<=9)i=ch48;numi+； / 数字字符 elseif(A<=ch<=Z)i=ch-65+10;numi+；/ 字母字符 for(i=0；i<10；i+) / 输出数字字符的个数 printf(“数字d的个数dn”，i，numi)； for(i10；i<36；i+)/ 求出字母字符的个数 printf(“字母字符c的个数dn”，i55，numi)； 本章练习题 答案分页： 1 2 第四章检索 练习上一章 下一章本章练习1、（教材习题4.5）写一个递归函数计算二叉树叶结点的个数。2、（教材习题4.11）写出在中序穿线二叉树里找指定结点在后序下的前驱的算法。3、（教材习题4.15）证明二叉搜索树结点的中序序列就是二叉搜索树结点按关键码值排序的序列。4、（教材习题4.19）递归程序smallcount,传入二叉搜索树BST的根和至K,返回值小于或等于K的结点个数。相应写出非递归函数。参考答案 第四章二叉树 练习答案上一章 下一章 本章练习题 答案分页： 1 2 1、解答：【算法描述】统计二叉树叶结点的个数的递归函数如下：template <class T> int BinaryTree<T>:leafnumber( BinaryTreeNode<T> * root) if (root=NULL) return 0; /为空子树，无叶子结点 if (root->isLeaf() return 1; /为叶子结点 /返回统计左、右子树中的叶结点数 return leafnumber(root->leftchild()+leafnumber(root->rightchild(); 2、解答： 【题意解析】 在后序排列的二叉树中，如果给定节点有右子树，则给定节点的前驱是其右子树的根节点。否则，如果给定节点的有左子树，则其前驱是其左子树的根结点。 如果给定的节点既没有右子树，也没有左子树。即，给定的节点是叶节点。则可以利用穿线树的结构很容易地找到给定结点在中序周游下的前驱x。根据中序周游的特点，如果给定结点有前驱x，给定节点是x的右子树在中序周游下的第一个结点，则其也是x的右子树在后序周游下的第一个结点。所以，如果x有左子树，则其根结点就是x的左子树在后序周游下的最后一个结点，也就是给定结点在后序周游下的前驱。 如果x没有左子树，则找到x在中序周游下的前驱x'，可以判定，给定节点也是x'的右子树在后序周游下的第一个结点，所以x'如果有左子树，则其根结点是给定结点在后序周游下的前驱。如果没有，则依照这个方法继续寻找x'的在中序周游下的前驱。直到找出一个有左子树的结点为止。【算法描述】ThreadBinaryTreeNode *FindPreInsorder( ThreadBinaryTreeNode *pointer) /在中序穿线二叉树中找指定结点在后序下的前驱 ThreadBinaryTreeNode * temppointer = NULL; /指定结点有右子女 if (pointer -> rTag = 0) return pointer -> rightchild(); else temppointer = pointer; while (temppointer -> lTag = 1) /结点在中序下的前驱 temppointer = temppointer -> leftchild(); temppointer = temppointer -> leftchild(); return temppointer; 本章练习题 答案分页： 1 2 第四章二叉树 练习答案上一章 下一章 本章练习题 答案分页： 1 23、解答：【证明】本题可以有多种解法，反证、归纳等等，下面给出归纳法证明。 设二叉搜索树共有n个结点。(1) 当N=0，即二叉树为空时显然成立；(2) 当N=1,即二叉树只有一个结点时显然成立；(3) 假设当NK，即二叉树有小于或等于K个结点时，这些个结点的中序排列就是它们按关键码值排序的序列。则对有K+1个结点的二叉搜索树，其根结点的左右子树的结点个数均小于或等于K，所以其左右子树结点的中序排列都是这些结点按关键码值排序的序列。整棵树的中序序列为A=左子树中序序列根右子树中序序列。根据二叉搜索树的性质，根结点的左子树中所有结点的关键码值都小于根结点的关键码值，而右子树中所有结点的关键码都大于根结点的关键码值。序列A仍是按关键码排序的序列； 由(1)、(2)、(3)可知，二叉搜索树的结点的中序排列就是二叉搜索树结点按关键码值排序的序列。4、解答： 【题意解析】 采取中序周游该二叉树，但为了保证尽可能少的访问结点，可通过比较结点值与k值的大小来判断周游的路径。【算法描述】方法一：递归算法template<class T> int smallcount(BinaryTreeNode<T> * root,T k) if (root=NULL) return 0; else if (k>=root->value() return (1+smallcount(root->leftchild(),k)+smallcount(root->rightchild(),k); else return smallcou
