《数据结构 张铭 习题》由会员分享，可在线阅读，更多相关《数据结构 张铭 习题（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
