北航算法与数据结构复习题

#D、堆排序17、以下说法正确的是（ABD）A、直接插入排序的空间复杂度为0（1）B、快速排序附加存储开销为O（log2n）C、堆排序的空间复杂度为O（n）D、二路归并排序的空间复杂度为O（n）18、图的存储结构有（ABCD）A、邻接矩阵B、邻接表C、数组表示法D、十字链表19、属于插入排序的排序方法有（ABC）A、直接插入排序B、对半插入排序C、渐减增量排序D、冒泡排序20、二叉树的遍历方式有（ABC）A、先序遍历B、中序遍历C、后序遍历D、线索遍历简答题（每小题15分，总分30分1、类C语言与标准C语言的主要区别是什么？类C语言只是在C语言编程过程中的一个思路的编写过程2、请用类C语言描述链串的类型定义。:typedefs^rucidnode*dpointer;structdnode；datatypedata：dpointerprior.,next;}typedafdpinterdlklist;链域pnm■和next别指向本结点数据域西说所含数据元素的直接前趋和直接后继所任的结点。所有结点诵讨前為和后驴指针清捋科一起.再扣卜捉标识作用的头指针・就得到敢向循环游表「*[fhl注释：]代码后面的文字是解释说明，如果题目不要求解释，可以不写。3、叙述以下概念的区别：头指针变量、头指针、头结点、首结点，并说明头指针变量和头结点的作用。链表里有“头指针”变量,它存放一个地址,该地址指向一个元素。链表里的每个元素称为“节点”。头指针是指向链表中第一个结点的指针ohead是头指针，而不是头结点，它只占用4字节大小空间（如果是32位）头节点是链表中第一个有效的节点，而不是用来存储第一个节点地址的头节点首结点是指链表中存储第一个数据元素的节点。头结点是在首节点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元节点，其作用主要是为了方便对链表的操作。它可以对空表、非空表一级首元节点的操作技能型统一处理。4、简述二次探测法解决冲突的基本思想。二次探查采用的形式如下：h(k,i)=(h'(k)+c1i+c2i)modm其中h'是一个辅助散列函数，cl和c2为辅助常数，i=O,l,・・・m-l。处事的探查位置为T[h'(k)],后续的探查位置要在此基础上加上一个偏移量，该偏移量是以二次的方式依赖于探查号i的。如果两个关键字的初始探查位置是相同的，那么他们的后续二次探查的序列也是相同的。这种性质会导致一种程度较轻的群集现象，成为二次群集。简单地说就是遇到冲突，就以n-2,n=1,2,...的序列探查，如果找到首个没有冲突的位置，就插入,否则继续探查.5、算法的设计要求有哪些？1、正确性2、可读性；3、健壮性4、效率与低存储量需求6、图的存储有几种方式？1、数组表示法2、邻接表表示法3、十字链表4、链接多重表7、简述开散列表的组织方式及类型定义笞；幵散列表的组织方式女吓:设选定的散歹怪数为H小的值域〔即散列地址的集合}^0..n-1.谡蚩一个“地址向蚩朋pointerH?[n\苴中的每个指针HP[i「指向个里旌表用于存储所有散列业址为1肉数据7L尋,R卩祈有馭列地ii的同XIpo每一-“-样的单司义订亍表。日地址台里以及向童中抽毎个指针所指的司义词子表构戌行■■诸结拘彩力开散列表。注卡□开散列解决冲突的方法灵祢“拉链法讯开散列表类型定汶如卜：typedefstructtagnode{keytypekeystructtacnode^next……其他其3也域幻■Winterj.ncdtyed&fpoineropenhahln^36.0102030-10506070a091&111213idL516U0060871551S82.20465aOa508oil5S66566/0"00766S9790Stttloirnidhig@00&0071551S8汹465aOa508oil5S6656670700766897908tttlow□idhig⑤QQO087155Lae220i0D505508oil5S6&SO67070070689790Etttlownidhim8、简述循环队列的类型定义=defineMAX<QSIZE100:ypedefstruc-intreax;}SqQueue：9、简述闭散列表的类型定义答：闭散列表是一个一维数组，其元素的类型与动态查找表中数据元素的类型一致:^deSnemajisizc冈散列表的容量t^'pedefstruct{keytyp亡key疳其他域旷}elementtyped亡felementclosehash[maxsize]分析题(每小题20分，总分40分)1、编程实现单链表的测长。答案：/*单链表的测长*/intlength(node*head)/*返回单链表长度*/{intlen=0;node*p;/*新建一个节点指针*/p=head->next;/*指针指向头节点的下一个节点*/while(p!=NULL)/*遍历链表*/{len++;p=p->next;}returnlen;}/*由于链表末尾节点的next指针被置为NULL，因此可以使用while循环进行遍历链表所有节点，当遇到NULL时结束循环*/2、完成以下递归算法，它将二叉树中所有结点的左、右子树相互交换。typedefstructBiTNode{chardata;//结点信息是字符structBiTNode*lchild,*rchild;//左右孩子指针}*BiTree;Statusexchangelr(BiTree&T)//算法用函数名exchangelr表示{BiTreep;//临时工作指针//待完成的若干语句；}答案：StatusexohangelrfBilree&T)算法用函数容亡盘tmgelr表示^BiTreep;冷临时工作指针if['T]returnOK:else{p=T待完成的若干语句jT->lcliild=I-M€hild:T->icliiid=p;exchangelr(T->lchild);亡jcchati呂亡lr(T->fchiId};3、对于循环队列，试写出求队列长度的算法。include<stdio.h>include<stdlib.h>#defineMAXQSIZE100typedefstruct{int*base;intfront;intrear;}SqQueue;voidInitQueue(SqQueue*Q){Q->base=(int*)malloc(sizeof(int));if(!Q->base)exit(l);Q->front=Q->rear=0;}intQueueLength(SqQueue*Q){return(Q->rear-Q->front+MAXQSIZE)%MAXQSIZE;}4、已知一个散列表如下图所示：35203348590123456789101112其散列函数为h(key)=key%13,处理冲突的方法为双重散列法，探查序列为：hi=(h(key)+i*h1(key))%mi=0,1,…,m_1其中h1(key)=key%11+1回答下列问题：对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？该散列表在等概率查找时查找成功的平均查找长度为多少？答案：5、2、事去⑴的功能是—从顺序存储结构的线性表a中地除第1个元素起的k个元素算