数据结构(c语言版)课后习题答案完整版.pdf

第 1 章绪论5选择题：CCBDCA 6试分析下面各程序段的时间复杂度。（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为 x+共执行了n-1+n-2+,1=n(n-1)/2，所以执行时间为O（n2）（6）O(n)第 2 章线性表1选择题babadbcabdcddac 2算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。ElemType Max(LinkList L)if(L-next=NULL)return NULL;pmax=L-next;/假定第一个结点中数据具有最大值p=L-next-next;while(p!=NULL)/如果下一个结点存在if(p-data pmax-data)pmax=p;p=p-next;return pmax-data;（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。void inverse(LinkList&L)/逆置带头结点的单链表 L p=L-next;L-next=NULL;while(p)q=p-next;/q指向*p 的后继 p-next=L-next;L-next=p;/*p插入在头结点之后 p=q;（10）已知长度为n 的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为 O(1)的算法，该算法删除线性表中所有值为item 的数据元素。题目分析 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i 个元素，第i+1 至第 n 个元素要依次前移）。本题要求删除线性表中所有值为item 的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item 的数据元素时，直接将右端元素左移至值为item 的数据元素位置。void Delete（ElemType A，int n）A是有 n 个元素的一维数组，本算法删除A中所有值为item 的元素。i=1；j=n；设置数组低、高端指针（下标）。while（ij）while（ij&Ai!=item）i+；若值不为item，左移指针。if（ij）while（ij&Aj=item）j-；若右端元素值为item，指针左移if（ij）Ai+=Aj-；算法讨论 因元素只扫描一趟，算法时间复杂度为O（n）。删除元素未使用其它辅助空间，最后线性表中的元素个数是j。第 3 章栈和队列1选择题CCDAADABCDDDBCB 2.算法设计题（2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)根据提示，算法可设计为：/以下为顺序栈的存储结构定义#define StackSize 100/假定预分配的栈空间最多为100 个元素typedef char DataType;/假定栈元素的数据类型为字符typedef struct DataType dataStackSize;int top;SeqStack;int IsHuiwen(char*t)/判断 t 字符向量是否为回文，若是，返回1，否则返回0 SeqStack s;int i,len;char temp;InitStack(&s);len=strlen(t);/求向量长度for(i=0;ilen/2;i+)/将一半字符入栈Push(&s,ti);while(!EmptyStack(&s)/每弹出一个字符与相应字符比较temp=Pop(&s);if(temp!=Si)return 0;/不等则返回0 else i+;return 1;/比较完毕均相等则返回 1 （7）假设以数组Q m存放循环队列中的元素,同时设置一个标志tag，以 tag=0 和tag=1 来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。【解答】循环队列类定义#include template class Queue /循环队列的类定义public:Queue(int=10);Queue()delete Q;void EnQueue(Type&item);Type DeQueue();Type GetFront();void MakeEmpty()front=rear=tag=0;/置空队列int IsEmpty()const return front=rear&tag=0;/判队列空否int IsFull ()const return front=rear&tag=1;/判队列满否private:int rear,front,tag;/队尾指针、队头指针和队满标志Type*Q;/存放队列元素的数组int m;/队列最大可容纳元素个数构造函数template Queue:Queue(int sz):rear(0),front(0),tag(0),m(sz)/建立一个最大具有m 个元素的空队列。Q=new Typem;/创建队列空间assert(Q!=0);/断言:动态存储分配成功与否插入函数template void Queue:EnQueue(Type&item)assert(!IsFull ();/判队列是否不满，满则出错处理rear=(rear+1)%m;/队尾位置进1,队尾指针指示实际队尾位置Qrear=item;/进队列tag=1;/标志改 1，表示队列不空 删除函数template Type Queue:DeQueue()assert(!IsEmpty();/判断队列是否不空，空则出错处理front=(front+1)%m;/队头位置进1,队头指针指示实际队头的前一位置tag=0;/标志改 0,表示栈不满return Qfront;/返回原队头元素的值 读取队头元素函数template Type Queue:GetFront()assert(!IsEmpty();/判断队列是否不空，空则出错处理return Q(front+1)%m;/返回队头元素的值 第 4 章串、数组和广义表1选择题BBCABBBCBBABDCBC 2.综合应用题（1）已知模式串t=abcaabbabcab 写出用KMP法求得的每个字符对应的next和nextval函数值。模式串 t 的 next 和 nextval值如下：j 1 2 3 4 5 6 7 8 9 10 11 12 t 串a b c a a b b a b c a bnextj0 1 1 1 2 2 3 1 2 3 4 5nextvalj0 1 1 0 2 1 3 0 1 1 0 5（3）数组 A中，每个元素Ai,j的长度均为32 个二进位,行下标从-1 到 9，列下标从1 到 11，从首地址S开始连续存放主存储器中，主存储器字长为16 位。求：存放该数组所需多少单元？存放数组第4 列所有元素至少需多少单元？数组按行存放时，元素A7,4 的起始地址是多少？数组按列存放时，元素A4,7 的起始地址是多少？每个元素 32 个二进制位，主存字长16 位，故每个元素占2 个字长，行下标可平移至1到 11。（1）242 （2）22 （3）s+182 （4）s+142(4)请将香蕉banana 用工具 H()Head()，T()Tail()从 L 中取出。L=(apple,(orange,(strawberry,(banana),peach),pear)H（H（T（H（T（H（T（L）（5）写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z 这 26 个字母和0-9 这 10 个数字）。void Count（）/统计输入字符串中数字字符和字母字符的个数。int i，num36；char ch；for（i 0；i36；i+）numi；/初始化while（chgetchar（）!=#）/#表示输入字符串结束。if（0=ch=9）i=ch 48;numi+；/数字字符elseif（A=ch=Z）i=ch-65+10;numi+；/字母字符for（i=0；i10；i+）/输出数字字符的个数printf（“数字 d 的个数 dn”，i，numi）；for（i 10；ilchild=NULL&T-rchild=NULL)return 1;/判断该结点是否是叶子结点（左孩子右孩子都为空），若是则返回 1 else return LeafNodeCount(T-lchild)+LeafNodeCount(T-rchild);（3）交换二叉树每个结点的左孩子和右孩子。void ChangeLR(BiTree&T)BiTree temp;if(T-lchild=NULL&T-rchild=NULL)return;else temp=T-lchild;T-lchild=T-rchild;T-rchild=temp;ChangeLR(T-lchild);ChangeLR(T-rchild);第6章图1选择题CBBBCBABAADCCDDB 2应用题（1）已知如图6.27 所示的有向图，请给出：每个顶点的入度和出度；邻接矩阵；邻接表；逆邻接表。（2）已知如图6.28 所示的无向网，请给出：邻接矩阵；邻接表；最小生成树a b 4 c 3 b a 4 c 5 d 5 e 9 c a 3 b 5 d 5 h 5 d b 5 c 5 e 7 f 6 g 5 h 4 e b 9 d 7 f 3 f d 6 e 3 g 2 g d 5 f 2 h 6 h c 5 d 4 g 6 图 6.28 无6456252363794567555553955434（3）已知图的邻接矩阵如6.29所示。试分别画出自顶点1 出发进行遍历所得的深度优先生成树和广度优先生成树。（4）有向网如图6.29 所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。D 终点i=1 i=2 i=3 i=4 i=5 i=6 b 15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)c 2(a,c)d 12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)e 10(a,c,e)10(a,c,e)f 6(a,c,f)g 16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S 终点集a,c a,c,f a,c,f,e a,c,f,e,d a,c,f,e,d,g a,c,f,e,d,g,b 图 6.29 邻接矩阵第 7 章查找1选择题CDCABCCCDCBCADA 2应用题（1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：画出描述折半查找过程的判定树；若查找元素54，需依次与哪些元素比较？若查找元素90，需依次与哪些元素比较？假定每个元素的查找概率相等，求查找成功时的平均查找长度。先画出判定树如下（注：mid=(1+12)/2=6）：30 5 63 3 7 42 87 4 24 54 72 95 查找元素54，需依次与30,63,42,54 元素比较；查找元素90，需依次与30,63,87,95 元素比较；求 ASL 之前，需要统计每个元素的查找次数。判定树的前3 层共查找 122 43=17次；但最后一层未满，不能用84，只能用54=20 次，所以 ASL 1/12（1720）37/123.08（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。12 717 2 11 16 21 4 9 13 验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17，21（5）设哈希表的地址范围为017，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：画出哈希表的示意图；若查找关键字63，需要依次与哪些关键字进行比较？若查找关键字60，需要依次与哪些关键字比较？假定每个关键字的查找概率相等，求查找成功时的平均查找长度。画表如下：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 查找 63,首先要与H(63)=63%16=15 号单元内容比较，即63 vs 31,no;然后顺移，与46,47,32,17,63相比，一共比较了6 次！查找 60,首先要与 H(60)=60%16=12 号单元内容比较，但因为 12 号单元为空（应当有空标记），所以 应当只比较这一次即可。对于黑色数据元素，各比较1次；共 6 次；对红色元素则各不相同，要统计移位的位数。“63”需要 6 次，“49”需要 3 次，“40”需要2 次，“46”需要 3 次，“47”需要 3 次，所以 ASL=1/11（6 233+6）23/11（6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key%7，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。散列地址0 1 2 3 4 5 6 7 8 9 关键字14 01 9 23 84 27 55 20 比较次数1 1 1 2 3 4 1 2 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8 以关键字 27 为例：H（27）=27%7=6（冲突）H1=（6+1）%10=7（冲突）H2=（6+22）%10=0（冲突）H3=（6+33）%10=5 所以比较了4 次。第 8 章排序1选择题CDBDCBCDBCBCCCA 2应用题（1）设待排序的关键字序列为12，2，16，30，28，10，16*，20，6，18，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。直接插入排序 折半插入排序 希尔排序（增量选取5，3，1）冒泡排序 快速排序 简单选择排序 堆排序 二路归并排序直接插入排序2 12 16 30 28 10 16*20 6 18 2 12 16 30 28 10 16*20 6 18 2 12 16 30 28 10 16*20 6 18 2 12 16 28 30 10 16*20 6 18 2 10 12 16 28 30 16*20 6 18 2 10 12 16 16*28 30 20 6 18 2 10 12 16 16*20 28 30 6 18 2 6 10 12 16 16*20 28 30 18 2 6 10 12 16 16*18 20 28 30 折半插入排序排序过程同 希尔排序（增量选取5，3，1）10 2 16 6 18 12 16*20 30 28（增量选取5）6 2 12 10 18 16 16*20 30 28（增量选取3）2 6 10 12 16 16*18 20 28 30（增量选取1）冒泡排序2 12 16 28 10 16*20 6 18 30 2 12 16 10 16*20 6 18 28 30 2 12 10 16 16*6 18 20 28 30 2 10 12 16 6 16*18 20 28 30 2 10 12 6 16 16*18 20 28 30 2 10 6 12 16 16*18 20 28 30 2 6 10 12 16 16*18 20 28 30 2 6 10 12 16 16*18 20 28 30 快速排序126 2 10 1228 30 16*20 16 18 62 6 10 12 28 30 16*20 16 18 282 6 10 12 18 16 16*20 2830 182 6 10 12 16*16 18 20 28 30 16*2 6 10 12 16*16 18 20 28 30 左子序列递归深度为1，右子序列递归深度为3 简单选择排序2 12 16 30 28 10 16*20 6 18 2 6 16 30 28 10 16*20 12 18 2 6 10 30 28 16 16*20 12 18 2 6 10 12 28 16 16*20 30 18 2 6 10 12 16 28 16*20 30 18 2 6 10 12 16 16*28 20 30 18 2 6 10 12 16 16*18 20 30 28 2 6 10 12 16 16*18 20 28 30 2 6 10 12 16 16*18 20 28 30 二路归并排序2 12 16 30 10 28 16*20 6 18 2 12 16 30 10 16*20 28 6 18 2 10 12 16 16*20 28 30 6 18 2 6 10 12 16 16*18 20 28 30 堆排序第一步,形成初始大根堆（详细过程略），第二步做堆排序。初始排序不是大根堆形成初始大根堆交换 1 与 10 对象从 1 到 9 重新形成堆交换 1 与 9对象从 1 到 8 重新形成堆交换 1 与 8 对象从 1 到 7 重新形成堆2 18 16 20 10 12 16*6 28 30 18 12 16 10 2 16*12 20 30 28 6 20 16 2 10 12 16*18 28 30 20 18 16 10 12 16*6 2 30 28 12 28 16 2 10 20 16*18 6 30 28 20 16 10 12 16*18 2 30 6 12 2 16 20 10 3016*28 6 18 30 28 16 10 20 16*18 2 12 6 交换 1 与 7 对象从 1 到 6 重新形成堆交换 1 与 6 对象从 1 到 5 重新形成堆交换 1 与 5 对象从 1 到 4 重新形成堆交换 1 与 4 对象从 1 到 3 重新形成堆12 6 10 20 16*12 18 16 28 30 10 6 2 16*12 18 16 20 30 28 6 12 10 20 16*2 18 16 28 30 12 6 10 16*2 18 16 20 30 28 10 12 16 20 16*2 18 6 28 30 16 12 10 16*2 18 6 20 30 28 16*12 16 20 10 2 18 6 28 30 16*12 16 10 2 18 6 20 30 28 交换 1 与 3 对象从 1 到 2重新形成堆交换 1 与 2 对象得到结果3算法设计题（1）试以单链表为存储结构，实现简单选择排序算法。void LinkedListSelectSort(LinkedList head)/本算法一趟找出一个关键字最小的结点，其数据和当前结点进行交换;若要交换指针，则须记下/当前结点和最小结点的前驱指针p=head-next;while(p!=null)q=p-next;r=p;/设 r 是指向关键字最小的结点的指针while(q!=null)if(q-datadata)r=q;q:=q-next;if(r!=p)r-datap-data;p=p-next;2 6 10 20 16*12 18 16 28 30 2 6 10 16*12 18 16 20 30 28 2 6 10 20 16*12 18 16 28 30 6 2 10 16*12 18 16 20 30 28