数据结构与算法复习提纲

数据结构与算法复习提纲第一部分概念题见练习一、二、三及习题等注意二叉树的5条性质的运用等例:选择题表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为(E)，删除一个元素所需移动元素的平均个数为(A)。A．(n-1)/2 B．n C．n+1 D．n-1E．n/2 F．(n+1)/2 G．(n-2)/2设栈S和队列Q的初始状态为空，元素el、e2、e3、e4、e5和e6依次通过栈S,一个元素出栈后即进入队列Q，若6个元素出队的序列为e2、e4、e3、e6、e5和el,则栈S的容量至少应该为(C)。A．6 B．4 C．3 D．2设栈的输入序列为1、2、3...n，若输出序列的第一个元素为n,则第i个输出的元素为(B)。A.不确定B.n-i+1C.iD.n-i在一个长度为n的顺序表中删除第i个元素(lv=i<=n)时，需向前移动(A)个A.n-i B.n-i+1C.n-i-1D.i若长度为n的线性表采用顺序存储结构存储，在第i个位置上插入一个新元素的时间复杂度为(A)。A.O(n)B.O(1)C.O(n2)D.O(n3)队列是一种特殊的线性表，其特殊性在于(C)。插入和删除在表的不同位置执彳丁B.插入和删除在表的两端位置执彳丁C.插入和删除分别在表的两端执行D.插入和删除都在表的某一端执行栈是一种特殊的线性表，具有(B)性质。A.先进先出B.先进后出C.后进后出D.顺序进出顺序循环队列中(数组的大小为n),队头指示front指向队列的第1个元素，队尾指示rear指向队列最后元素的后1个位置，则循环队列中存放了n-1个元素，即循环队列满的条件为(B)。A.(rear+1)%n=front-1 B.(rear+1)%n=frontC.(rear)%n=front D.rear+1=front顺序循环队列中(数组的大小为6),队头指示front和队尾指示rear的值分别为3和0,当从队列中删除1个元素，再插入2个元素后，front和rear的值分别为(D)。A.A.5和1B.2和4 C.1和5D.4和2前序遍历和中序遍历结果相同的二叉树为(F)；前序遍历和后序遍历结果相同的二叉树为(B)。—般二叉树只有根结点的二叉树根结点无左孩子的二叉树根结点无右孩子的二叉树所有结点只有左子树的二叉树所有结点只有右子树的二叉树。以下有关二叉树的说法正确的是(B)。A.二叉树的度为2 B.—棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任一个结点的度均为2用一维数组存放完全二叉树：ABCDEFGHI,则后序遍历该二叉树的结点序列为(HIDEBFGCA)。(首先画出完全二叉树,然后再后序遍历该二叉树)在关键字序列(12,23,34,45,56,67,78,89,91)中二分查找关键字为45、89和12的结点时,所需进行的比较次数分别为(B)A.4,4,3B.4,3,3C.3,4,4D.3,3,4适用于折半查找的表的存储方式及元素排列要求为(D)。A.链式方式存储，元素无序B.链式方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序在一个带权连通图G中，权值最小的边一定包含在G的(A)。A.最小生成树中B.深度优先生成树中C.广度优先生成树中D.深度优先生成森林中已知一个有向图下图所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为(A)。A.adbefcB.adcefbC.adcbfeD.adefcb下列说法错误的是(D)A.冒泡排序在数据有序的情况下具有最少的比较次数。B•直接插入排序在数据有序的情况下具有最少的比较次数。二路归并排序需要借助O(n)的存储空间。基数排序适合于实型数据的排序。下面的序列中初始序列构成最小堆(小根堆)的是(D)10、60、20、50、30、26、35、4070、40、36、30、20、16、28、10C．20、60、50、40、30、10、8、72D．10、30、20、50、40、26、35、60（4）在下列算法中，（C）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。A.堆排序B.插入排序C.冒泡排序D.快速排序（6） 以下排序方法中，不稳定的排序方法是（AC）。A.直接选择排序B.二分法插入排序C.堆排序D.基数排序（7） 一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用（B）方法。A•快速排序B.堆排序C•插入排序D.二路归并排序（8） 若要求尽可能快地对实数数组进行稳定的排序，则应选（C）A.快速排序B.堆排序C.归并排序D.基数排序（9） 排序的趟数与待排序元素的原始状态有关的排序方法是（A）。A.冒泡排序B.快速排序C.插入排序D.选择排序（10） 直接插入排序在最好情况下的时间复杂度为（A）。A.O（n）B.O（logn）C.O（nlogn）D.O（n2）第二部分计算题和证明题1、 数组元素地址的计算例:在一个C语言程序中，有结构类型STUDENT的定义和结构数组allstudents的声明如下：structSTUDENT{charname[8];intnumber;}STUDENTallstudents[10][50];allstudents是一个二维数组，它的每个元素都是包含name和number的结构类型。已知在C语言中，二维数组使用以行序为主序的存储结构，char类型占用1字节，int类型占用4字节。假定allstudents在内存中的起始存储位置是2000，请写出计算allstudents[i][j]的存储位置的算式，并计算allstudents[3][5啲存储位置。答:（1）allstudents[i][j]的存储位置=2000+（i*50+j）*12（2） allstudents[3]⑸的存储位置=2000（3*50+5）*12=3860见练习一、二、三2、 计算树的结点数等例:（1）一棵完全二叉树上有1001个结点，其中叶子结点的个数为（D）。A.250B.500 C.254D.5012k-1深度为k的二叉树至多有 个结点（k>=1）0（2io=1024）可先求2度结点数,再由此得到叶子总数。前9层总结点数为29-1=511首先，前k-2层的28-1（255）个结点肯定都是2度的（完全二叉）另外，末层叶子为489（末层叶子数为1001-511=490个所对应的双亲也是度=2,（共有|_490/2」=245个）。所以，全部2度结点数为255（前k-2层）+245（第k-1层）=500个；总叶子数=2度结点数＋1=501个。（2）一棵完全二叉树有999个结点，它的深度为（B）。A．9 B．10 C．11 D．12深度为k的二叉树至多有2k-1个结点（k>=1）°（2io=1O24）（3）一棵具有5层的满二叉树所包含的结点个数为（B）。A．15B．31C．63 D．32深度为k的二叉树至多有2k-1个结点（4）有n个结点的二叉树，已知叶结点个数为n0,则该树中度为1的结点的个数为（n-2n0+1）（因为n0=n2+l）；若此树是深度为k的完全二叉树，贝肮的最小值为（2k-1）2k-lWn<2k（5） 设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B。已知T1、T2和T3的结点数分别是n1、n2和n3，则二叉树B的左子树中有（n1-1）个结点，二叉树B的右子树中有（n2+n3）结点。（首先将森林转为二叉数（兄弟相连长兄为父，孩子靠左头根为根），然后可得左子树由T1构成，右由T2和3构成）（6）高度为k的二叉树的最大结点数为（2^1），最小结点数为（k）。（7） 对于一棵具有n个结点的二叉树，该二叉树中所有结点的度数之和为（n-1）。（8） 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（B）。见习题A．1.0B．2.9C．3.4D．5.5（9） 画出对长度为10的有序表进行折半查找的判定树，并求其概率时查找成功的平均查找长度。见习题9.3（平均查找长度=2.9）（10）将一棵有100个节点的完全二叉树从上到下，从左到右依次对节点进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为__A__。A:99B:98C:50D:48f生质5:对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号必为2i+1；其双亲的编号必为"2（Z=1时为根，除外）。3、证明题例：任意一棵有N个结点的二叉树，已知它有M个叶子结点。试证明非叶子结点中度数为2的有M-1个，其余的度数为1。证：设二叉树中度为0的结点数为n0,度为1的结点数为nl,度为2的结点数为n2,二叉树中分支数为B*.* N=n0+n1+n2N=M+n1+n2又•・•B=0+n1+2*n2 （其中：0---度为0的结点的分支数（叶子结点），n1---度为1的结点的分支数,2*n2---度为2的结点的分支数.又• N=B+1M+n1+n2=0+n1+2*n2+1M=n2+1・•・n2=M-1第三部分操作题（一）给出一个图,用普里姆算法求最小生成树1、画邻接距阵、邻接表2、 写出深度和广度搜索的序列（由画邻接距阵、邻接表才能惟一）3、 用普里姆算法求最小生成树见练习二第七大题（二） 给出一个图，用Dijkstra（迪杰斯特拉）算法求最短路径1、画邻接距阵、邻接表2、 写出深度和广度搜索的序列（由画邻接距阵、邻接表才能惟一）3、 用迪杰斯特拉算法求最短路径见练习一、三第七大题（三） 构造Huffman树1、构造Huffman树（填表格）2、 对各字符编码（使用频率高的码长短）3、 求带权路径长度见练习一、二、三第六大题（四） 散列函数的应用1、填写对应的散列表（记下冲突情况）2、求出平均查找长度见练习一、二第八题（五） 排序给出序列，写出1、希尔排序2、冒泡排序3、快速排序4、堆排序5、 归并排序6、 基数排序例：已知序列｛24,8,30,50,42,19,21,40,11,15｝要求：1、 用希尔排序法排序（增量序列为5、3、1）写出每趟的结果2、 用快速排序法排序，写出每趟的结果3、 用冒泡排序法排序，写出每趟的结果（前两趟）

4、用堆排序法排序，画出初始堆（大顶堆或小顶堆）并输出一个元素5、用归并排序法排序，写出每趟的结果6、用基数排序法排序，写出每趟的结果解：1、用希尔排序法排序（增量序列为5、3、1）写出每趟的结果198（六） 树的操作1、建立二叉排序树（或给出有序序列画出判定树）画出插入结点后和删除结点后的二叉排序树具有如下性质的非空二叉树：1）左子树的所有结点均小于根的值；（2） 右子树的所有结点均大于根的值；（3） 它的左右子树也分别为二叉排序树。（4）二叉排序树中序遍历后的结果是有序序列例1:已知序列17，31，13，11，20，35，25，8，4，11，24，40，27。请画出由该输入序列构成的二叉排序树，并分别给出下列操作后的二叉排序树。1)〔c〉fff隐1?之后的二灵排序树m口之后的二咒排序树插入数据9；（2）删除结点1)〔c〉fff隐1?之后的二灵排序树m口之后的二咒排序树例2:给出有序序列画出判定树习题9.9已知如下所示长度为12的表（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）（1） 试按表中元素的顺序依次插入一棵初始为空的二叉排列树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。（3.5）（2） 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行拆半查找时查找成功的平均查找长度。(3.1)Apr,Aug,Dec,Feb,Jan,July,June,Mar,May,Nov,Oct,Sep2、二叉树的遍历3、 由前（或后）序遍历和中序遍历画出对应的树例:已知一棵二叉树的中序遍历的结果为ABCEFGHD，后序遍历的结果为ABFHGEDC,试画出此二叉树。7.10己和一楹二又树的中字堰历的给果为AECEFC3HD,序遍历的结果为ABFHGEDCz试画出此二叉树\【答】:7.11已知一棵二叉树的前序遍历的第果为ABCDEF^中序遍历的结杲为CBAEDF.试画出此二XWo【兰】4、 二叉树与森林的转换见练习一、二、三树如何转为二叉树？方法：stepl:将树中同一结点的兄弟相连；step2:保留结点的最左孩子连线，删除其它孩子连线;step3:将同一孩子的连线绕左孩子旋转45度角。例：

bh回垂纤CF.定凡弟相连长凡为父孩子盍左二叉树如何还原为森林树转二叉树举例：bh回垂纤CF.定凡弟相连长凡为父孩子盍左二叉树如何还原为森林树转二叉树举例：方法：则线一^未线一旋掩把最右边的子树变为森林，其余右子树变为兄弟从根开始，顺右链直到没有右链为止，把遇到的右链”砍断”，这样，可以分割出若干个二叉树,其个数正好是原树林中树的个数对每一棵分割出的二叉树中的所有结点,如果某个结点i为其双亲结点左子树的根结点，则顺右链找到所有由右链相连的结点，并将其”砍断”，然后把分割出来的结点与结点i的双亲结点相连.RB}•■"5XH])]■开姐施右锻直到汝有右龍为止.把鋤劉的右確“:ttar.这样.可以井割出若干牛二叉拮真亍数正好是扁树林中樹的牛数2.对毎一杭分斟出的二艮拥中的耐结总如果某亍皓点为其眾亲结点左子材的規结点一IMU』■琏找到所有由右毬相连凶结点RB}•■"5XH])]■开姐施右锻直到汝有右龍为止.把鋤劉的右確“:ttar.这样.可以井割出若干牛二叉拮真亍数正好是扁树林中樹的牛数2.对毎一杭分斟出的二艮拥中的耐结总如果某亍皓点为其眾亲结点左子材的規结点一IMU』■琏找到所有由右毬相连凶结点./■将其-戰断-撫后把为割［U*的詰A'；给Ai的以亲结直相门・3.试述树和二叉树的主要区别。【答】：（1）树的结点个数至少为1，而二叉树的结点个数可以为0。（2）树中结点的最大度数没有限制，而二叉树结点的最大度数为2。（3）树分为有序树与无序树，而二叉树一定是有序树，它的结点有左，右之分。（七） 求关键路径题见教材pl86图7.30例题（八） 其他操作题循环队列操作例:循环队列存储在一个数组中，数组大小为n,队首指针和队尾指针分别为front和rear,请写出求循环队列中当前结点个数的表达式。【答】：循环队列中当前结点个数的计算公式是：（n+rear-front）%n2.给出有向图画出拓扑排序序列栈的操作等例:一个栈的入栈序列是a，b，c，d，e,则栈的不可能的输出序列是_C.A:edcbaB:decbaC:dceabD:abcde如下图所示的是某个无向图的邻接表，试：1）画出此图；（2） 写出从顶点A开始的DFS遍历结果；从顶点A开始的DFS遍历结果是：A,B,C,F,E,G,D（3） 写出从顶点A开始的BFS遍历结果。3）从顶点A开始的BFS遍历结果是：A,B,C,D,F,E,G已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。A、 在P结点后插入S结点的语句序列是：（7） ,（12）,（3）,（6）/（6）,（7）,（12）,（3）B、 在P结点前插入S结点的语句序列是：（8） ,（13）,（5）,（4）/（5）,（8）,（2）,（4）C、 删除P结点的直接后继结点的语句序列是：（1）,（11）/（15）,（1）,（11）,（18）D、 删除P结点的直接前驱结点的语句序列是：2），（10）/（16），（2），（10），（18）E、删除P结点的语句序列是：(9)，(14)，(17)/(14)，(9)，(17)P->next=P->next->next;P->prior=P->prior->prior;P->next=S;P->prior=S;S->next=P;S->prior=P;S->next=P->next;S->prior=P->prior;P->prior->next=P->next;P->prior->next=P;P->next->prior=P;P->next->prior=S;P->prior->next=S;P->next->prior=P->prior;Q=P->next;Q=P->prior;Free(p);Free(Q);A．(7)，(12)，(3)，(6)/(6)，(7)，(12)，(3)B．(8)，(13)，(5)，(4)/(5)，(8)，(2)，(4)C．（1），（11）/（15），（1），（11），（18）D．（2），（10）/（16），（2），（10），（18）E．（9），（14），（17）/（14），（9），（17）第四部分算法题1、已知非递减线性表La,Lb.将所有La和Lb中的数据元素归并，到Lc中,使Lc的数据元素也是非递减的.voidMergeList(ListLa,ListLb,List&Lc){InitList(&Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);While((iv=La」en)&&(jv=Lb」en))//La和Lb均非空{GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}while(i<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}2、试编写出将两个顺序存储的有序表A和B合成一个有序表C的算法解：假设A、B和C的类型为下述SqList类型：#definemaxlen1000typedefintelemtypetypedefstruct{elemtypeelem[maxlen];intlen;}SqList;设A和B的数据元素均为整数且为升序排列，设A的长度为m,B的长度为n则合并后C的长度为m+n。合并时进行A、B元素的比较，将较小的链入C中，算法描述如下:intmerge(SqList*A,SqList*B,SqList*C)//将两个有序表A和B合成一个有序表C{intm,n,i,j,k;m=(*A).len;n=(*B).len;if(m+n>maxlen-1){printf("overflow");exit(0);}i=0;j=0;//i和j分别作为扫描顺序表A和B的指针k=o；//k指示顺序表C中当前位置while((i<=m)&&(j<=n))if((*A).elem[i]<=(*B).elem[j]){(*C).elem[k]=(*A)elem[i];i++； k++；}else{(*C).elem[k]=(*B)elem[j];j++; k++;}while(i<=m)//表B已结束，表A没有结束，链入表A的剩余部分{(*C).elem[k]=(*A).elem[i];i++;k++;}while(j<=m)//表A已结束，表B没有结束，链入表B的剩余部分{(*C).elem[k]=(*B).elem[j];i++;k++;}return(1);}3、写一算法实现单链表的逆置解：假设单链表的表头指针用head表示，其类型为上面定义的LinkList,并且单链表不带头结点。逆置后原来的最后一个结点成为第一个结点，于是从第一个结点开始逐个修改每个结点的指针域进行逆置，且刚被逆置的结点总是新链表的第一个结点，故令head指向它(如图2-1所示)。具体算法描述如下：(a)单链表初始状态(b)第三个结点逆置图2-1单链表逆置示意图voidcontray(LinkList*head){//将head单链表中所有结点按相反次序链接LinkList*p,*q;p=head;//p指向未被逆序的第一个结点,初始时指向原表头结点head=NULL;while(p!=NULL){q=p;//q指向将被逆序链接的结点p=p->next;q->next=head;head=q;}}带表头结点：voidInverseList(LinkList&head){ListNode*p,*t,*h;h=head->next;p=h->next;h->next=NULL;while(p!=NULL){t=p->next;p->next=h;h=p;p=t;}head->next=h;4、写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表爼卫2,…气）逆置为（an,an-l，…,ai）。答:#defineListSize100//假定表空间大小为100typedefintDataType;//假定DataType的类型为int型typedefstruct{DataTypedata[ListSize];//向量data用于存放表结点intlength;//当前的表长度}Seqlist;//顺序表结构定义同上题voidReverseList(Seqlist*L){DataTypetemp;/设置临时空间用于存放datainti;for(i=0;i<L->length/2;i++)//L->length/2为整除运算{temp=L->data[i];//交换数据L->data[i]=L->data[L->length-1-i];L->data[L->length-1-i]=temp;}}5、 写一算法，实现统计带表头的单链表中元素值为奇数的结点个数单链表结点的类型定义如下:typedefintelemtype; //定义数据域的类型typedefstructLnode{ //定义结点类型elemtypedata;structLnode*next;}Lnode,*LinkList;intsum(linklistL){listnode*p;//linklistp;ints=0;for(p=L->next;p!=NULL;p=p->next)if(p->data%2==1)s++;returns;}个删除表中6、已知线性表的元素是无序的，且以带头结点的单链表作为存储结构所有值小于max但大于min的元素的算法。个删除表中算法描述如下：delete(LinkList*head,intmax,intmin){LinkList*p,*q;q=head;p=head->next;while(p!=NULL)if((p->data<=min)||(p->data>=max)){q=p;p=p->next;}else{q->next=p->next;free(p);p=q->next;}}设计一个算法，求顺序表中值为X的结点的个数。【答】：顺序表的存储结构定义如下(文件名seqlist.h)：#include<stdio.h>#defineN100/*预定义最大的数据域空间*/typedefintdatatype;/*假设数据类型为整型*/typedefstruct{datatypedata[N];/*此处假设数据元素只包含一个整型的关键字域*/intle