数据结构试卷与答案

1．算法与程序有何区别和联系？（6分）算法是对特定问题求解步骤的一种描述，可以用自然语言、流程图、伪代码、程序代码来表示。程序是算法的具体实现，可以用不同的语言实现。2．树的存储方法主要有哪些？任你画一个树举例说明具体存储结构。（6分）（1）双亲表示法——以一组连续空间存储树的结点，在每个结点中设一个指示器指示双亲结点的位置。（2） 孩子表示法——每个结点的孩子以单链表的形式存储，n个结点有n个孩子链表，n个头指针又组成一个线性表，并以顺序存储结构存储。（3） 孩子兄弟表示法——以二叉链表作为树的存储结构，链表中的结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。3．设有序表的长度为10，用二分查找方法进行查找，试计算查找成功情况下的平均查找长度（6分）ASL=1/10*（1+2*2+4*3+3*4）=2.94．图的遍历方法主要有哪些？任你画一个图举例具体说明。（6分）//区分原子结点表结点*hp;*tp;//区分原子结点表结点*hp;*tp;c）））的存储结构，并写出广义表类型定义。};};//后继结点结构structGLNode{ElemTagtag;union{intatom;值域structGLNode*hp;};structGLNode*tp;};采用后继结点的存储结构深度优先搜索，宽度优先搜索。例如：深度优先搜索遍历：ABXFYDEC宽度优先搜索遍历：ABCDXEYF5．画出广义表D=(()，x，(a，(b#defineATOM0#defineLIST1typedefenum{ATOM,LIST}ElemTag;//表头表尾结构structGLNode{ElemTagtag;union{intatom;struct{structGLNodestructGLNode}ptr;//原子结点的//表结点的头指针//下一个元素结点分别画出一个B树和B+树的例子，并指出它们之间的区别。（6分）B树与B+树的区别：B树：每个结点的关键字个数等于指针个数减1。B+树：每个结点的关键字个数等于指针个数。B+树中所有叶子结点包含了全部关键字信息，以及指向关键字记录的指针，叶子节点依关键字大小自小到大链接。非终端结点作索引，结点中含有其子树根结点的最大(最小)关键字。你知道有哪些排序算法？试比较各种排序算法的性能。(8分)排序算法时间复杂度空间复杂度稳定性直接插入排序0(n2)0(1)稳定冒泡排序0(n2)0(1)稳定快速排序O(nlogn)O(logn)不稳定选择排序0(n2)0(1)不稳定堆排序O(nlogn)0(1)不稳定归并排序O(nlogn)0(n)稳定基数排序O(d(n+rd))O(rd)不稳定8.设一组关键字为(7,15,20,31,48,53,64,76,82,99),Hash函数H(key)=key%11,Hash表表长m=11，用线性探测法解决冲突，试构造Hash表，并分别计算查找成功和查找失败情况下的平均查找长度。(8分)7%11=7找1次成功查15%11=4找1次成功查20%11=9找1次成功查31%11=9功9+1=10查找2次成48%11=4功4+1=5查找2次成53%11=99+1+1-11=0查找3次成功64%11=99+1+1+1-11=1查找4次成功76%11=1010+1+1+1-11=2查找4次成功82%11=5成功5+1=6查找2次99%11=00+1+1+1=3查找4次成功查找成功时的平均查找长度：(1+1+1+2+2+3+4+4+2+4)/10=2.4查找失败的平均查找长度：1+2+3+4+5+6+7+8+9+10+11)/11=6二、简述利用Dijkstra算法求解从某顶点到其余各顶点最短路径的步骤。Dijkstra算法思想：(1)求解顺序：按最短路径递增的顺序求解。(2)到某个定点的最短路径找到后,考察它对其余顶点当前最短路径的影响。算法步骤：1） 设arcs存储带权有向图的边的权值，v为出发顶点，S为已找到的从v出发的最短路径的终点集合，开始为空。从v出发到图中其余顶点vi最短路径长度初始值为D[i]=arcs[o][i]o,i为v,vi的位置2） 选择vj,使得D[j]=Min{D[i]lviWV-S}vj是从v出发的最短路径的终点。S=SU{j}3） 修改从v出发到集合V-S任一顶点vk可达的最短路径长度。如果D[j]+arcs[j][k]vD[k],则D[k]=D[j]+arcs[j][k]。4） 重复2,3n-1次，由此求出从v到其它顶点的最短路径。三、试编写归并排序算法。(12分)#include<stdio.h>//将有序的SR[i...m]和SR[m+l...n]归并为有序的TR[i...n]voidMerge(intSR[],intTR[],inti,intm,intn){intj,k;j=m+1;k=i;while(i<=m&&j<=n)if(SR[i]<=SR[j])TR[k++]=SR[i++];elseTR[k++]=SR[j++];while(i<=m)TR[k++]=SR[i++];while(j<=n)TR[k++]=SR[j++];}//将SR[s...t]归并排序为TRl[s...t]voidMSort(intSR[],intTR1[],ints,intt){intm;intTR2[10];TR1[s]=SR[s];else{m=(s+t)/2;//SR[s...t]平分为SR[s...m]和SR[m+1...t]MSort(SR,TR2,s,m);//递归地将SR[s...m]归并为有序的TR2[s...m]MSort(SR,TR2,m+l,t);//递归地将SR[m+l...t]归并为有序的TR2[m+l...t]Merge(TR2,TR1,s,m,t);//将TR2[s...m]和TR2[m+l...t]归并到TRl[s...t]}}//主函数，调用归并排序MSortvoidmain(){ints[10]={2,6,7,4,5,10,9,1,3,8};MSort(s,s,0,9);inti;for(i=0;i<10;i++)printf("%d",s[i]);}if(s==t)四、试编写一个算法将线性表L中的数据建立一棵二叉排序树。（12分）//线性表结点typedefstructSqList{int*elem;intlength;intlistsize;}SqList;//二叉树结点typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;}BiTNode;//建立二叉排序树voidCreateBST(SqListl,BiTNode*&root){inti;BiTNode*p,*q,*r;if(l.lenght==0){root=NULL;return;}root=(BiTNode*)malloc(sizeof(BiTNode));root->data=l.elem[0];root->lchild=root->rchild=NULL;//二叉排序树的根节点for(i=1;i<l.length;i++){p=root;while(p!=NULL)//新结点定位if(l.elem[i]<p->data){q=p;p=p->lchild;}elseif(l.elem[i]>p->data){q=p;p=p->rchild;}else//该值已在排序树中出现，不再插入break;if(p==NULL){r=(BiTNode*)malloc(sizeof(BiTNode));r->data=l.elem[i];r->lchild=NULL;r-〉rchild=NULL;//生成新结点if(l.elem[i]<q->data)q->lchild=r;elseq->rchild=r;//新结点作q的叶子结点}}}五、设单链表L中的结点按data域数值递减排列，试设计一个算法将L中的结点按data域数值递增加排列，要求算法的时间复杂性为O（n）°（12分）typedefstructLNode{intdata;structLNode*next;}LNode;voidTraverseList(LNode*&l){LNode*head=NULL;LNode*p=l,*q;while(p){head=q;q=p;p=p->next;}l=head;q->next=head;}一、填空题（每空2分，共20分）当 时，快速排序算法的时间复杂性最差。对于具有300个记录的文件，采用分块索引查找法查找，其中用二分查TOC\o"1-5"\h\z找法查找索引表，用顺序查找法查找块内元素，假定每块长度均为30个元素，则平均查找长度为 。设某二叉树的前序和中序序列均为ABCDE，则它的后序序列是 。假设以一维数组S\n（n+1）/2〕作为n阶对称矩阵A的存储空间，以行序为主序存储A的下三角，则元素A⑸⑹的值存储在S[—]中。若一棵树中度为1的结点有N1个，度为2结点有N2个，……度为m的结点有Nm个，则该树的叶结点有 个。设循环队列的元素存放在一维数组Q[O..3O]中，front指向队头元素的前一个位置,rear指向队尾元素。若front=25,rear=5,则该队列中的元素个数为 。图的遍历方法主要是 。设源串S=“bcdcdcb”，模式串P=“cdcb”，按KMP算法进行模式匹配,当“s2s3s4”="p1p2p3"，而s5hp4时，s5应与 比较。9.设序列｛12，34，19，23，8，56｝，试建立表长为7的Hash表。Hash函数为H（key）=key%7,用线性探测法解决冲突，则56冲突 次。10.求解图的最小生成树的算法有两个，分别是一、填空题待排数据本身已排好序18.426N2+2N3+・“+(mT)Nm11EDCBA宽度优先搜索深度优先搜索9.38.P210.Prim算法和Kruskal8.P2二、根据要求解答下列问题。（共34分）1.画出广义表D=（（）,x,（a,（b,c）））的存储结构。（5分）2．根据图的邻接表画邻接矩阵。（5分）3．请给出堆排序不稳定的例子。（6分）堆排序不稳定1224排序后结果为12244．设输入下列关键字序列：12,34,56,8,5,18,15试建立一棵平衡的二叉排序树,写出步骤。（6分）分别画出一个B树和B+树的例子,B树与B+树的区别：B树：每个结点的关键字个数等于指

针个数减1。B+树：每个结点的关键字个数等于指针个数。举例说明栈和队列的应用。（6分）并指出它们之间的区别。（6分）B+树中所有叶子结点包含了全部关

键字信息,以及指向关键字记录的指

针,叶子节点依关键字大小自小到大

链接。非终端结点作索引,结点中含

有其子树根结点的最大（最小）关键

字。栈是一种后进先出的数据结构,可应用于递归操作、表达式求值、括号匹配等。队列是一种先进先出的数据结构,可应用于树的层次遍历,操作系统中的作业排队,先来先服务在《数据结构》课程中,你学习了哪些算法？请至少列举20个算法名称。有序线性表的合并、KMP算法、顺序查找、二分查找、Hash查找、建立二叉排序树的算法、冒泡排序、选择排序、插入排序、堆排序、快速排序、归并排序、基数排序、Prim算法、Kruskal算法、图的深度优先搜索算法、图的广度优先搜索算法、Dijkstra算法、拓扑排序算法、Huffman算法、二叉树的先序遍历算法、中序线索二叉树算法。四、试编写对顺序表L进行归并排序的算法。（12分）#include<stdio.h>#include<stdlib.h>//线性表结点typedefstructSqList{int*elem;intlength;intlistsize;}SqList;//将有序的SR[i...m]和SR[m+l...n]归并为有序的TR[i...n]voidMerge(intSR[],intTR[],inti,intm,intn){intj,k;j=m+1;k=i;while(i<=m&&j<=n)if(SR[i]<=SR[j])TR[k++]=SR[i++];elseTR[k++]=SR[j++];while(i<=m)TR[k++]=SR[i++];while(j<=n)TR[k++]=SR[j++];}//将SR[s...t]归并排序为TRl[s...t]voidMSort(intSR[],intTR1[],ints,intt)intm;intTR2[10];if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;//SR[s...t]平分为SR[s...m]和SR[m+1...t]MSort(SR,TR2,s,m);//递归地将SR[s...m]归并为有序的TR2[s...m]MSort(SR,TR2,m+1,t);//递归地将SR[m+1...t]归并为有序的TR2[m+1...t]Merge(TR2,TR1,s,m,t);//将TR2[s...m]和TR2[m+l...t]归并到TRl[s...t]}}//主程序，供测试用voidmain(){SqListl;inti;l.listsize=l.length=10;l.elem=(int*)malloc(sizeof(int)*l.listsize);for(i=0;i<l.length;i++)scanf("%d",&l.elem[i]);MSort(l.elem,l.elem,0,l.length-1);//for(i=0;i<l.length;i++)//printf("%d",l.elem[i]);五、已知二叉树T的结点结构为leftdatarightbal其中，bal存储结点的平衡因子（bal=左子树高度-右子树高度），试编写算法求树T中各结点的平衡因子。(12分)typedefstructBiTNode{intdata;intbal;structBiTNode*left,*right;}BiTNode;intGetHeight(BiTNode*t){inthl,hr;if(t==NULL){hl=GetHeight(t->left);hr=GetHeight(t->right);t->bal=hl-hr;if(hl<hr)returnhr+1;elsereturnhl+1;}}return0;else六、设采用邻接表作为有向图的存储结构六、设采用邻接表作为有向图的存储结构点的出度和入度。(12分，一、typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode{intdata;intin;intout;试编写算法：计算有向图中每个顶ArcNode*firstarc;}VNode;typedefstruct{VNodevertices[NUM];intvexnum;intarcnum;}AlGraph;//获得结点的入度和出度voidGetInAndOut(AlGraph&g)//开始时所有结点的入度出度 inti;为0 ArcNode*p;{ for(i=0;i<g.vexnum;i++)二、 填空题(每空2分，共20分)1．提高程序可读性的措施TOC\o"1-5"\h\z是： 。设n>0,且有如下程序段：inti;i=n;while(i>0)i=i/10;则该程序的时间复杂性为 。稀疏矩阵的压缩存储方法是 。以数组Q[0..m]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，则队列第一个元素的实际位置是 O将序列(50，38，66，98，77，13，28，50)建立一个堆，该堆是 。下列函数的功能是实现两个字符串的比较，试根据字符串比较运算的定义，完善该函数：intstrcmp(chars[],chart[]){inti;for(i=0;s[i]&&t[i];i++)if(s[i]!=t[i]) ;7．下列算法的功能是求带头结点的单链表的表长，请完善。intcount（LinkListhead）{ ;length=0;while（p!=NULL）{length++; ； }7.p=head->next7.p=head->nextp=p->nextreturnlength1.设计良好的程序结构;函数名及变量名的命名规范化;使用合理的注释2.O（log10N）只存储非零元素（三元组表，十字链表）(rear+m-qulen+2)mod(m+1)(13,38,28,50,77,66,50,98)returns[i]-t[i]returnstrlen(s)-strlen(t)二．简要回答下列问题（共44分）1.分别说明Huffman算法、Dijkstra算法、Prim算法、Kruskal算法的功能。（8分）Huffman算法:求Huffman树（带权路径长度最短的二叉树）Dijkstra算法:求图中从某个源点到其余各顶点的最短路径Prim算法:求最小生成树2.举例说明选择排序是不稳定的选择排序不稳定举例:{256256*512128}i=1{128256*512256}i=2Kruskal算法:求最小生成树（6分）{128256*256512}256和256*在排序前后相对位置发生变化,所以说选择排序是不稳定的。{128256*512256}i=33．设有一个广义表L=(a,(),(x,(y,z)),(a,b))，试画出它的存储结构。(6分)4．图的存储方法主要有哪些？试举例说明它们的具体存储结构。(8分)5．设一组关键字为(7，15，20，31，48，53，64，76，82，99)，Hash函数H(key)=key%11,Hash表表长m=11，用线性探测法解决冲突，试构造Hash表，并计算查找成功情况下的平均查找长度。(8分)查找成功情况下的平均查找长度为(3+4+4+4+1+2+2+1+1+2)/10=2.46.时间复杂性为O(nlogn)的排序方法有哪些？任选其中一种方法举例说明其排序过程。(8分)快速排序,堆排序,归并排序以归并排序说明:假设初始序列含有快速排序,堆排序,归并排序以归并排序说明:假设初始序列含有n个记录，则可看成是n个有序的子序列,每个子序列的长度为1,然后两两归并，得到n/2个长度为2或1的有序子序列;再两两归并,，如此重复,直至得到一个长度为n的有序序列为止.举例如下编写算法：从键盘读入一组整数，以9999作为结束标志，将这些数据建立一棵二叉排序树。(这些数据建立一棵二叉排序树。(12分)typedefstruct T，KeyTypekey，BiTreeBiTNode f，BiTree&p)TelemTypedata;structBiTNode*lchild，*rchild;}BiTNode，*BiTree;StatusSearchBST(BiTreeif(!T){p=f;returnFALSE;}elseifEQ(key，T->data.key){p=T;returnTRUE;}elseifLT(key，T->data.key)SearchBST(T->lchild，key，T，p);elseifSearchBST(T->rchild，key，T，p);}StausInsertBST(BiTree&T,ElemTypee){if(!SearchBST(T,e.key,NULL,p){s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;elseifLT(e.key,p->data.key)p->lchild=s;elsep->rchild=s;returnTR