《数据结构 张铭 习题》由会员分享,可在线阅读,更多相关《数据结构 张铭 习题(51页珍藏版)》请在金锄头文库上搜索。
1、 第一章概论 练习答案上一章 下一章本章练习题 答案分页: 1 21、解答: 【题意解析】本题指定了字符的顺序,所以不能按照 ASCII 字符顺序来排序。 【典型错误】1.不按照题目给出的字符顺序进行排序,而按照 ASCII 字符顺序。2.没有给出排序结果3.认为顺序存储法比较节约空间,事实上由于字符空隙,顺序法并不节约空间;4. 没有比较各种方法的优劣。 【数据结构】本题可以采用的存储结构有顺序(数组)和链表。1. 用二维数组 arrayNUMOFSTRINGMAX_LENGTH,此题可定义 const int NUMOFSTRING=8, MAX_LENGTH=5; B8990 B90 C
2、RSI0 CXY0 PAB0 PABC0 5C0 70 优点:为紧凑存储结构,没有用于存储其他附加的信息,表示方法比较直观简单, 代码实现十分容易。缺点:为每个但此都开辟了同样长度的空间,造成空间的浪费。 2. 用链表的结构存储,结点为结构struct stringschar stringMAX_LENGTH;strings *pNext;优点:如果有后续工作如反复增删结点,效率很高.并且可以使用不连续的空间。缺点:操作过程相对复杂,容易出错.而且排序过程需要从表头开始沿链索一个结 点一个结点的比较搜索,相当费时。 3. 索引存储是顺序存储的一种推广.使用一个字符串 char data500,
3、其中将大小长度不等 的数据结点(单词)顺序存储其中.令使用一个字符指针数组 char* indexn,存储一 系列指针,每个指针指向存储区域的一个数据结点.排序时,直接对 index 中的地址值进行调换修改即可,而不用修改 data 中的任何 内容。索引存储的优点是:由于单词长度不同,在存储时充分考虑了这个因素,可以节 省空间,此外由于交换的不是单词本身而是单词的地址,可以节省时间,从时空两方面 得到了优化。 【排序结果】 B899,B9,CRSI,CXY,PAB,PABC,5C,7 2、解答: 【题意解析】本题没有指明这 100 个实数是否存在相等的情况,在这里,我们考虑存在多个最大值的情形
4、(即 100 个实数可能有相等的),为了保存其位置,利用 int pos100(因为有可能这 100 个实数都是相同的)来保存最大值的所有位置。【典型错误】1. 用 int 类型的数组来保存这 100 个元素,没有注意题目中说的是“每个元素的值都是实数”。2. 求最大值的时候代码如下:temp=0;for(int i=0;itemp)temp=Numi;评注:这样是错误的,例如:当 Numi都是负数的时候。3. 未考虑可能存在多个最大值的情况,只保存了一个最大值的位置。【数据结构】本题可以采用的存储结构有顺序(数组),链表和索引。本题最好使用数组存储结构。由于其他存储方法需要记录附加信息,使得
5、空间有效利用不能够最大化。因此在空间上顺序存储是最优的。时间上,无论如何此题都要遍历所有的数,因此 O(n)为可能的最优时间代价。加之此题的规模较小,因此使用大家最熟悉的顺序存储是较为优先的选择。【算法描述】1. 由于最大值可能不止一个,甚至可能都是最大值,所以创建一个长度为 100 的整型数组 pos100,用来记录最大值的位置。2. 初始情况,取这个数组的第一个位置为最大值所在的位置,存入变量 position 中。3. 假设有 n(1n99)个最大值,那么 pos0, 1, 2, , n-1记录这些最大值的位置,且 posn=-1(-1 是标记值,表明 pos 数组下标为 n-1 及以前
6、的元素记录了最大值的位置);假设有 n(n=100)个最大值,那么 pos0, 1, 2, , n-1记录这些最大值的位置,pos 数组不再设-1 的标记值。具体源码如下:# include 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
7、=1;iNumposition) 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(jclass table/当程序使用此 table 模板时,应该在前面附加#includepublic:/创建一张空课程表tab
8、le t; /创建一张天数为 k 的课程表,可默认 k 为 7table t(int k); /设置某天的课程(时间地点等),该结点的地址可由索引表找出virtual void Setcourse( ELEM /把一个新的结点插入课程表,使该结点在表中位置是 nPos 如果 nPos = -1/则插入到表尾部(同时地址加入索引表) virtual void Addday( const ELEM * pday, int nPos = -1 ) = 0; /删除课程表中某天(结点),释放该结点的空间,该结点的地址可由索引表找出virtual void Removeday( ELEM /清空整个课程
9、表,成功返回 truevirtual bool Clearall() = 0; /清空某天(结点)的所有内容,该结点的地址可由索引表找出,成功返回 truevirtual bool Clearday( ELEM /修改某天(结点)的课程(时间 地点等),该结点的地址可由索引表找出virtual void Changecourse( ELEM /输出某天(结点)的课程内容,该结点的地址可由索引表找出virtual void Printday( ELEM /输出所有课程内容(结点)virtual void PrintList() = 0; /根据系统时间查询当天课程virtual void Cur
10、rent() = 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
11、.10)环状的队列,写出计算队列元素个数的程序。 5、(教材习题 2.19)现有 4 个元素作为双端队列的输入,问可以得到多少种不同的排列? 参考答案参考答案 第二章线性表、栈和队列 练习答案上一章 下一章本章练习题 答案分页: 1 21、解答: 【题意解析】本题没有指明是否存在多个内容为 a 的地址,在这里,我们考虑存在多个结点 内容为 a 的情形。 【典型错误】没有考虑内容为 a 的地址可能有多个。 【数据结构】 由于链表中内容为 a 的结点数目不确定,可以选择用一个新链表来存放找到的结点 地址。这样的存储结构 优于定长数组。 本题中涉及到两个链表:原链表 ListNode 和用于存储结点
12、地址的新链表 ListAddress。 【算法描述】1. 设 pfirst 和 qfirst 分别是这两个链表的头指针,p,q 为指针变量。2. p 从链表 X 的表头开始向后移动,每当遇到原链表中内容为 a 的结点,就 在新链表中增 加一个结点记录下其地址(用指针指向该结点来进行记录),如此循环直到链表 X 的表尾。struct ListNode /链表结点定义ELEM data; /数据类型为 ELEMListNode* plink; /指向后继结点的指针;ListNode* pfirst; /pfirst 指向原链表第一个结点ListNode* p; /原链表的指针变量,程序运行时可对其
13、所指结点进 行各种运算p=pfirst; /指向头指针Struct ListAddress /用于存放地址的新链表ListNode * address; /存放地址,类型为指向链表 X 的结点的指针ListAddress* qlink; /新链表的指针变量;ListAddress* qfirst; /qfirst 指向新链表第一个结点qfirst-qlink=NULL; /空表ListAddress* q=qfirst; /指向头指针void find(ELEM a) /用于查找内容为 a 的结点,并记录其地址,参数为 待查数据 awhile(p!=NULL) /未到达链表尾结点if(p-da
14、ta= =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 ListNodeEL
15、EM data;ListNode* link;int Length (ListNode* first) /first 为循环表的头指针ListNode* p;p=first;int count=0; /用于记录结点数,空链表时结点数为 0while(p-link!=first) /未到达尾结点p=p-link; /指针向后移count+; /结点数加 1return count;3、解答:有 14 种可能:【思路】先进站的车可以先开,也可以后开。只有一种情况不可能:编号大的车开出后,比其编号小的车反序开出。也即编号大的车开出后,编号比其小的车只能由大到小依次开出(中间可以插入编号更大的车,但此车后面的编号小的车也要遵守此规则)。例如 312