算数提高课件ds总复习

1总复习算法与数据结构张路

2基本题型基本的题型选择填空判断解答算法设计此胶片内容仅仅作为题型参考,决非重点!!!!!3主要内容基础内容绪论线性表栈和队列树和二叉树字典和检索排序图4基础部分习题数据结构的基本概念和术语算法与算法评价（时间复杂性和空间复杂性）线性表的表示和实现顺序表单链表循环链表和双链表线性表的应用栈队列字符串5判断题顺序存储的线性表可以随机存取.在单链表中,任何两个元素的存储位置之间都有固定的联系,因为可以从头结点进行查找任何一个元素.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关在顺序表中取出第i个元素所花费的时间与i成正比YNYYN6选择题数据结构是研究数据的（A）和（B），以及这个结构具有的行为特征，定义相应的（C），设计出相应的（D）。供选择的答案A.B:1.理想结构2.抽象结构

3.存储结构4逻辑结构C.D:1.运算2.算法3.结构 4.规则5.现在的6.原来的34127选择题对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。A.n/2B.（n+1）/2C.（n-1）/2D.nE.n+1F.n-1A在下标为i（第i+1个）元素之前要插入一个元素，要移动n-(i+1)+1=n-i个元素；推理过程：8选择题链表不具有的特点是（）。可随机访问任意元素插入和删除不需要移动元素不必事先估计存储空间所需空间与线性表长度成正比A9选择题若线性表最常用的操作是读取第i个元素及其前趋的值，则采用（）存储方式节省时间。A单链表B双链表C单循环链表D顺序表D10选择题在双向链表存储结构中删除p所指的结点时需修改指针()。A.(p－>llink)->rlink=p->rlink；

(p－>rlink)->llink=p－>llink;B.p->llink=(p->llink)->llink;((p->llink)->llink)->rlink=p;C.((p->llink)->llink)->rlink=p;p->llink=(p->llink)->llink;A11解答题1、有如下函数，分析其时间复杂度：intsum(intn){ intsum=0; inti,j,p; for(i=1;i<=n;i++) { p=1; for(j=1;j<=n;j++) p=p*j; sum=sum+p; } return(sum);}解答：该函数嵌套最深的语句是：p=p*j该语句执行的次数为：n*n所以其时间复杂度为O(n2)12算法设计已知线性表A长度为n,并且采用顺序存储结构，写一算法删除线性表中所有值为x的元素。main(){ intsuccess,i; PSeqListpSeqList;...... for(i=0;i<pSeqList->n;i++) {if(pSeqList->element[i]==“x”) success=delete_seq(pSeqList,i); if(success==0) {printf(“fault”);exit(0); }}}13算法设计单链表遍历：设计算法依次打印链表中所有结点的值voidprint(){ p=L; while(p!=NULL) { printf(p->info); p=p->link; }}将L的值赋给Pp为空？打印p的值指针p后移NendYa1a2an^……L14算法设计若链表L带有头结点，如何修改本算法？

a2an^……La1voidprint(){

p=L->link; while(p!=NULL) { printf(p->info); p=p->link; }}15算法设计对本算法做哪些修改可以得到链表的长度？intprint(){

intlength;

length=0; p=L->link; while(p!=NULL) { printf(p->info); p=p->link;

length++; } return(length);}16算法设计若L为带头结点的单循环链表，怎样修改本算法？

a2an

……La1voidprint(){

p=L->link;if(p==NULL)return; do { printf(p->info); p=p->link; }while(p!=L->link)}17带头结点的链表与不带头结点的链表比较若链表L1带有头结点，L2不带头结点，删除a2的算法？

a2an^……L1a1voiddelete-a1(){

p=L1->link;

while(p!=NULL&&p->data!=a2) p=p->link;if(p!=NULL) {

删除操作

}else printf(“nonode”)}a2an^……L2a1voiddelete-a2(){

if(L2!=NULL)

p=L2;else printf(“thelistisempty!”) while(p!=NULL&&p->data!=a2) p=p->link;

if(p!=NULL) {

删除操作

}else printf(“nonode”)}18算法设计假设有两个已排序的单链表A和B，编写一个函数将它们合并成一个链表C而不改变其排序性思路：采用链表合并的方法，设原链表的头指针分别为p和q，每次比较p->data和q->data的值，把值较小的结点作为新链表的结点，这一过程直到进行到其中一个链表为空为止 当一个链表为空而另一个链表不为空时，只要将不空的链表指针赋给新链表中最后一个结点的指针域即可怎样做最节省空间？？19树和二叉树部分习题二叉树基本概念、术语、性质、两种特殊的二叉树二叉树的基本运算二叉树的实现二叉树的周游树与树林基本概念树的周游哈夫曼算法及其应用哈夫曼树和哈夫曼算法哈夫曼编码、译码20选择题如果结点A有3个兄弟（不包括A本身）,而且B是A的双亲,则B的度是（）。A.3B.4C.5D.1B21如图所示二叉树的中序遍历序列是（）。AabcdgefBdfebagcCdbaefcgDdefbagc选择题Babcdgef22选择题已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是（）。AacbedBdecabCdeabcDcedbaD23选择题设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（）。An在m右方Bn在m祖先Cn在m左方Dn在m子孙C24选择题某二叉树T有n个结点,设按某种顺序对T中的每个结点进行编号，编号值为1,2,...n.且有如下性质：T中任意结点v，其编号等于左子树上的最小编号减一，而v的右子树的结点中，其最小编号等于v左子树上结点的最大编号加一，这时按()编号的。A.中序遍历序列B.前序遍历序列C.后序遍历序列D.层次顺序B25选择题在一非空二叉树的中序遍历序列中，根结点的右边()。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的所有结点D.只有左子树上的部分结点A26解答假设某一类电文d={d1，d2，…，dm}组成，它们的出现频率w={2，3，5，7，11，13，17，19，23，29，31，37，41}，试给出d1的哈夫曼编码，并给出d1d2dm的编码和解码过程。27算法设计二叉树采用链接存储结构，设计一个按层次顺序（同一层自左向右）/后根顺序遍历二叉树的算法解题思路：采用一个队列q，先讲二叉树根结点入队列，然后退队列，输出该结点，若它有左子树，便将左子树的根结点入队列，若它有右子树，便将右子树根结点入队列，如此直到队列为空为止因为队列是先进先出的，从而达到按层次顺序遍历二叉树的目的p11228字典和检索习题顺序表表示顺序检索算法\二分法检索算法散列构造的字典和检索散列函数\碰撞处理二叉树表示二叉排序树的检索\二叉排序树的插入和构造\二叉排序树的删除AVL树索引简介29判断题散列法存储的基本思想是由关键码的值决定数据的存储地址一个二叉排序树的查找时间一定小于用顺序查找同样结点的线形表的查找时间YN30选择题对线性表进行二分查找时，要求线性表必须()。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储,且结点按关键字有序排序D.以链接方式存储,且结点按关键字有序排序C31选择题有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当二分查找值为82的结点时，()次比较后成功。A.1B.2C.4D.8C32选择题采用二分查找方法进行查找时，数据文件应为（A），且限于（B）。要进行顺序查找，则线性表（C）。

A,B：1.有序表2.随机表3.散列存储结构4.链式存储结构5.顺序存储结构6.线性表C：1.必须以顺序方式存储2.必须以链式方式存储3.既可以以顺序方式存储，也可以以链是方式存储

15333解答题设一组关键字{19，1，14，20，84，27，53，11，56，23}，采用哈希函数：H(key)=keyMOD10，采用开放地址法的随机探测再散列方法解决冲突，试在0～10的散列地址空间中对该关键字序列构造哈希表。

34排序习题排序的基本概念插入排序=>直接插入排序/折半插入排序/Shell排序选择排序=>直接选择排序/堆排序交换排序=>起泡排序/快速排序分配排序=>基数排序归并排序=>归并排序排序算法的比较和选择35判断题如果某种算法是不稳定的,则该方法没有实际应用价值对于n个记录的集合进行冒泡排序，所需要的平均时间是O(n）对于n个记录的集合进行快速排序，在最坏情况下所需要的平均时间是O(n2）对n个元素的序列进行起泡排序时,最小的比较次数是n-1NNYY36选择题对n个不同的排序码的元素进行不减序冒泡排序，在（A）情况下比较的次数最少，其比较次数为（B）;在（C）情况下比较的次数最多，其比较次数为（D）。供选择的答案A.C:1.从大到小排列好的2.从小到大排列好的3.元素无序4元素基本有序逻辑结构B,D:1.n+12.n3.n-14.n(n-1)/2231437选择题排序的方法有很多种，（A）法从未排序序列中依次取出元素，与以排序序列（初始时为空）中的元素做比较，将其放入以排序序列的正确位置上。（B）法从未排序序列中挑选元素，并将其放入以排序序列的一端。交换排序法是对序列中元素进行一系列比较，当被比较的元素为逆序时，进行交换；（C）和（D）是基于这类方法的两种排序方法，而D是比C效率更高的方法。供选择的答案1，选择排序2，快速排序3，插入排序4，冒泡排序5，折半排序

314238选择题在内排序的过程中，通常需要对待排序的关键码集合进行多便扫描。采取不同排序方法会产生不同的排序中间结果。设要将序列{Q，H，C，Y，P，A，M，S，R，D，F，X}中的关键码按字母序的升序重新排列，则（A）是冒泡排序的一躺扫描结果，（B）是初始步长为4的希尔排序一趟的结果，（C）是二路归并排序的一躺扫描结果。（D）是以第一个元素为分界元素的快速排序的一躺扫描结果。

供选择的答案A~E：1，F，H，C，D，P，A，M，Q，R，S，Y，X2，P，A，C，S，Q，D，F，X，R，H，M，Y3，A，D，C，R，F，Q，M，S，Y，P，H，X4，H，C，Q，P，A，M，S，R，D，F，X，Y5，H，Q，C，Y，A，P，M，S，D，R，F，X

425139选择题下述几种排序方法中，平均情况下要求内存量最大的是()。A.插入排序B.选择排序C.快速排序D.冒泡排序

C40填空题在下列冒泡排序算法中填入适当内容,以使该算法发现有序时能及时停止:a为一数组,定义为inta[n]VoidBuble(int*a){inti=1;boolexchanged;do{ exchanged=false; for(intj=n-1;

;j--){ if(a[j]<a[j-1]){ ;; ;;} i++;}while(i<n&&

)}exchangedj>=iint