数据结构练习题解答(17页).doc

-数据结构练习题解答-第 17 页第二章 线性表1.将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) pa=La->next; pb=Lb->next; Lc=pc=La; /用La的头结点作为Lc的头结点 while(pa && pb) if(pa->data<pb->data) pc->next=pa;pc=pa;pa=pa->next; else if(pa->data>pb->data) pc->next=pb; pc=pb; pb=pb->next; else / 相等时取La的元素，删除Lb的元素 pc->next=pa;pc=pa;pa=pa->next; q=pb->next;delete pb ;pb =q; pc->next=pa?pa:pb; /插入剩余段 delete Lb; /释放Lb的头结点 2.将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。void union(LinkList& La, LinkList& Lb, LinkList& Lc, ) pa = La->next; pb = Lb->next; / 初始化 Lc=pc=La; /用La的头结点作为Lc的头结点 Lc->next = NULL; while ( pa | pb ) if ( !pa ) q = pb; pb = pb->next; else if ( !pb ) q = pa; pa = pa->next; else if (pa->data <= pb->data ) q = pa; pa = pa->next; else q = pb; pb = pb->next; q->next = Lc->next; Lc->next = q; / 插入 delete Lb; /释放Lb的头结点 3.已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出A与B的交集，并存放于A链表中。void Mix(LinkList& La, LinkList& Lb, LinkList& Lc, ) pa=la->next;pb=lb->next;设工作指针pa和pb；Lc=pc=La; /用La的头结点作为Lc的头结点while(pa&&pb) if(pa->data=pb->data)交集并入结果表中。 pc->next=pa;pc=pa;pa=pa->next; u=pb;pb=pb->next; delete u; else if(pa->data<pb->data) u=pa;pa=pa->next; delete u;else u=pb; pb=pb->next; delete u;while(pa) u=pa; pa=pa->next; delete u; 释放结点空间while(pb) u=pb; pb=pb->next; delete u;释放结点空间pc->next=null;置链表尾标记。delete Lb; 注： 本算法中也可对B表不作释放空间的处理3.已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B 的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。void Difference（LinkedList A，B，*n）A和B均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的差集，存储于单链表A中，*n是结果集合中元素个数，调用时为0p=A->next； p和q分别是链表A和B的工作指针。 q=B->next； pre=A； pre为A中p所指结点的前驱结点的指针。 while（p!=null && q!=null）if（p->data<q->data）pre=p；p=p->next；*n+； A链表中当前结点指针后移。else if（p->data>q->data）q=q->next； B链表中当前结点指针后移。else pre->next=p->next； 处理A，B中元素值相同的结点，应删除。 u=p； p=p->next； delete u； 删除结点4.设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。5.设计一个算法，通过一趟遍历在单链表中确定值最大的结点。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;6.设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。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;7.设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同 ）。void delete(LinkList &L, int mink, int maxk) p=L->next; /首元结点 while (p && p->data<=mink) pre=p; p=p->next; /查找第一个值>mink的结点 if (p) while (p && p->data<maxk) p=p->next; / 查找第一个值 maxk 的结点 q=pre->next; pre->next=p; / 修改指针 while (q!=p) s=q->next; delete q; q=s; / 释放结点空间 /if9.已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（p结点，前驱结点，前驱的前驱结点，后继结点）六条链。void Exchange（LinkedList p）p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。q=p->llink； q->llink->rlink=p； p的前驱的前驱之后继为p p->llink=q->llink； p的前驱指向其前驱的前驱。 q->rlink=p->rlink； p的前驱的后继为p的后继。 q->llink=p； p与其前驱交换 p->rlink->llink=q； p的后继的前驱指向原p的前驱 p->rlink=q； p的后继指向其原来的前驱算法exchange结束。10.删除线性表a中第i个元素起的k个元素int DeleteK(SqList &a,int i,int k)   if(i<1|k<0|i+k-1>a.length) return -1;  for(int count=1;i+count-1<=a.length-k;count+) /注意循环结束的条件    a.elemi+count-1=a.elemi+count+k-1;  a.length-=k;  return 1 11. 把x插入递增有序表va中int Insert_SqList(SqList &va,int x)  if(va.length+1>va.listsize) return -1;  va.length+;  for(i=va.length-1;va.elemi>x&&i>=0;i-)    va.elemi+1=va.elemi;  va.elemi+1=x;  return 1; 12在链表上查找元素x,返回指针LNode* Locate(LinkList L,int x)   for(p=L->next;p&&p->data!=x;p=p->next);  return p; 13在无头结点链表L的第i个元素之前插入元素bint Insert(LinkList &L,int i,int b)   p=L;q=new LNode;  q.data=b;  if(i=1)      q.next=p;L=q; /插入在链表头部    else      while(-i>1) p=p->next;    q->next=p->next;p->next=q; /插入在第i个元素的位置  14在无头结点链表L中删除第i个元素int Delete(LinkList &L,int i)  if(i=1) L=L->next; /删除第一个元素  else      p=L;    while(-i>1) p=p->next;    p->next=p->next->next; /删除第i个元素  第三章 栈与队列1.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。 算法如下：/先定义链队结构:typedef struct queuenodeDatatype data;struct queuenode *next;QueueNode; /以上是结点类型的定义typedef structqueuenode *rear;LinkQueue; /只设一个指向队尾元素的指针(1)置空队void InitQueue( LinkQueue *Q) /置空队：就是使头结点成为队尾元素QueueNode *s;Q->rear = Q->rear->next;/将队尾指针指向头结点while (Q->rear!=Q->rear->next)/当队列非空，将队中元素逐个出队s=Q->rear->next;Q->rear->next=s->next;free(s);/回收结点空间(2)判队空 int EmptyQueue( LinkQueue *Q) /判队空/当头结点的next指针指向自己时为空队return Q->rear->next->next=Q->rear->next;(3)入队void EnQueue( LinkQueue *Q, Datatype x) /入队/也就是在尾结点处插入元素QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode);/申请新结点p->data=x; p->next=Q->rear->next;/初始化新结点并链入Q-rear->next=p; Q->rear=p;/将尾指针移至新结点(4)出队Datatype DeQueue( LinkQueue *Q)/出队,把头结点之后的元素摘下Datatype t;QueueNode *p;if(EmptyQueue( Q )Error("Queue underflow");p=Q->rear->next->next; /p指向将要摘下的结点x=p->data; /保存结点中数据if (p=Q->rear)/当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点Q->rear = Q->rear->next; Q->rear->next=p->next;else Q->rear->next->next=p->next;/摘下结点pfree(p);/释放被删结点return x;2.假设以数组Qm存放循环队列中的元素, 同时设置一个标志tag，以tag = 0和tag = 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。循环队列类定义#include <assert.h>template <class Type> 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 <class Type>Queue<Type>: Queue ( int sz ) : rear (0), front (0), tag(0), m (sz) /建立一个最大具有m个元素的空队列。 Q = new Typem;/创建队列空间 assert ( Q != 0 );/断言: 动态存储分配成功与否插入函数template<class Type> void Queue<Type> : EnQueue ( Type &item ) assert ( ! IsFull ( ) );/判队列是否不满，满则出错处理rear = ( rear + 1 ) % m;/队尾位置进1, 队尾指针指示实际队尾位置Qrear = item;/进队列tag = 1;/标志改1，表示队列不空删除函数template<class Type> Type Queue<Type> : DeQueue ( ) assert ( ! IsEmpty ( ) );/判断队列是否不空，空则出错处理front = ( front + 1 ) % m;/队头位置进1, 队头指针指示实际队头的前一位置tag = 0;/标志改0, 表示栈不满return Qfront;/返回原队头元素的值读取队头元素函数template<class Type> Type Queue<Type> : GetFront ( ) assert ( ! IsEmpty ( ) );/判断队列是否不空，空则出错处理return Q(front + 1) % m;/返回队头元素的值3.如果允许在循环队列的两端都可以进行插入和删除操作。要求： 写出循环队列的类型定义； 写出“从队尾删除”和“从队头插入”的算法。题目分析 用一维数组 v0.M-1实现循环队列，其中M是队列长度。设队头指针 front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队空，(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。（1）#define M 队列可能达到的最大长度typedef struct elemtp dataM; int front,rear; cycqueue;（2）elemtp delqueue ( cycqueue Q) /Q是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，否则给出出错信息。 if (Q.front=Q.rear) printf(“队列空”); exit(0); Q.rear=(Q.rear-1+M)%M; /修改队尾指针。 return(Q.data(Q.rear+1+M)%M); /返回出队元素。/从队尾删除算法结束void enqueue (cycqueue Q, elemtp x)/ Q是顺序存储的循环队列，本算法实现“从队头插入”元素x。if (Q.rear=(Q.front-1+M)%M) printf(“队满”; exit(0);) Q.dataQ.front=x; /x 入队列Q.front=(Q.front-1+M)%M; /修改队头指针。/ 结束从队头插入第七章 树与二叉树1. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 试为这8个字母设计赫夫曼编码。 试设计另一种由二进制表示的等长编码方案。 对于上述实例，比较两种方案的优缺点。解：方案1；哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。 w=7,19,2,6,32,3,21,10，按哈夫曼规则：【（2,3），6, (7,10)】, 19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3方案比较：字母编号对应编码出现频率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10字母编号对应编码出现频率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案1的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3结论：哈夫曼编码优于等长二进制编码(ppt)第八章 图1.已知如图6.27所示的有向图，请给出： 每个顶点的入度和出度； 邻接矩阵； 邻接表； 逆邻接表。 图6.27 有向图（2）已知如图6.28所示的无向网，请给出： 邻接矩阵； 邻接表； 最小生成树图6.28 无向网 ab4c3ba4c5d5e9ca3b5d5h5db5c5e7f6g5h4eb9d7f3fd6e3g2gd5f2h6hc5d4g6第九章 查找1.设哈希表的地址范围为017，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题： 画出哈希表的示意图； 若查找关键字63，需要依次与哪些关键字进行比较？ 若查找关键字60，需要依次与哪些关键字比较？ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。画表如下：012345678910111213141516173217634924401030314647查找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（623×3+6）23/112. 设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key %7 ，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。散列地址0123456789关键字140192384275520  比较次数1112 3 412  平均查找长度：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次。3.设哈希函数H（K）=3 K mod 11，哈希地址空间为010，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。 线性探测法； 链地址法。散列地址012345678910关键字 4 12493813243221 比较次数 1 1121212 ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11 ASLsucc =（1*5+2*3）/8=11/8ASLunsucc=（1+2+1+2+3+1+3+1+3+1+1）/11=19/114.设哈希表的地址范围为017，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题： 画出哈希表的示意图； 若查找关键字63，需要依次与哪些关键字进行比较？ 若查找关键字60，需要依次与哪些关键字比较？ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。解： （1）画表如下：012345678910111213141516173217634924401030314647（2） 查找63,首先要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。（4） 对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（623×3+6）23/115.设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key %7 ，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。散列地址0123456789关键字140192384275520  比较次数1112 3 412  平均查找长度：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次。（7）设哈希函数H（K）=3 K mod 11，哈希地址空间为010，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。 线性探测法； 链地址法。散列地址012345678910关键字 4 12493813243221 比较次数 1 1121212 ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11第十章 排序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 302 6 10 12 16 16* 18 20 28 30 快速排序12 6 2 10 12 28 30 16* 20 16 18 6 2 6 10 12 28 30 16* 20 16 18 28 2 6 10 12 18 16 16* 20 28 30 18 2 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