数据结构期末复习题2

复习题2一、选择题1.下述程序段中语句①的频度是（）。s=0;for(i=1;i<m;i++)for(j=0;j<=i;j++)①s+=j;A． B．C． D．2.设p结点是带表头结点的双循环链表中的结点，在p结点后插入s结点的语句序列中正确的是（）。A.s->next=p->next；p->next=s；p->next->prior=s；s->prior=p；B.p->next=s；s->next=p->next；p->next->prior=s；s->prior=p；C.s->next=p->next；s->prior=p;p->next->prior=s；p->next=s；D.p->next->prior=s；p->next=s；s->next=p->next；s->prior=p；3设栈的初始状态为空，元素1、2、3、4、5、6依次入栈，得到的出栈序列是（2,4,3,6,5,1）,则栈的容量至少是（）。A．2 B．3C．4 D．6已知二维数组A[6][10]，每个数组元素占4个存储单元，若按行优先顺序存放数组元素a[3][5]的存储地址是1000，假设a[0][0]是该数组的首元素，则a[0][0]的存储地址是（）。A．860B．864C．868D．872一棵完全二叉树中有128个叶子节点，则该树最少有个结点。A.255 B.254 C.253 D.2566.已知二叉树的前序遍历序列是abdgcefh，中序遍历序列是dgbaechf，它的后序遍历序列是。A．bdgcefhaB.gdbehfcaC．bdgechfaD．gdbecfha7.对下图进行拓扑排序，正确的拓扑序列是（）。A．v1，v2，v3，v4，v5，v6，v7 B．v1，v2，v4，v3，v6，v5，v7C．v1，v2，v4，v3，v5，v7，v6 D．v1，v2，v3，v4，v5，v6，v7对记录序列(314，298，508，123，486，145)依次按个位和十位进行两趟基数排序之后所得结果为_________。A．314，298，508，123，486，145B．123，314，145，486，298，508C．123，145，298，314，486，586D．508，314，123，145，486，2989.下列二叉树中，不平衡的二叉树是（）。10、在给出的四棵二叉树中，只有()满足一个小顶堆的形状。二、填空题1.在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是________和________。2.已知广义表C=((a，b)，(c，(d，(e)))，f)，则：tail(tail(head(C)))=_____（）____。3.使用一个20个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=5，rear=18，则队列中的元素个数为___________；如果队列中插入2个元素，则rear的值为。4.设有下三角矩阵A=0A=0004200657013911压缩存储到一维数组F[m]中，m为数组长度，0元素不存储，则m为，a00是二维数组首元素，元素a32按行优先顺序存放到F[k2]中，k2值为。5.对长度为31的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为___________，查找第10个元素需要比较次数为。三、应用题1、设模式串t=”abaabacababa”，试求出t的next和nextval函数值。2．由字符集{s，t，a，e，i}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为101100000111，请根据该哈夫曼树进行译码，写出原来的电文。3.设散列长度为9，散列函数为H(k)=kmod9，给出关键字序列：23，45，14，17，9，29，37，18，25，41，33，采用链地址法解决冲突。(1)请画出散列表；(2)计算在等概率情况下，查找成功的平均查找长度。4、利用Dijkstra算法，求图中顶点V0到其它各顶点的最短路径，写出求解过程。V0CV0C1010010100V4V1B30V4V1B3050106050106020V3V220V3V25、已知3阶B-树如图所示。已知3阶B-树如图所示，画出将关键字10、78、110、120依次插入之后的B-树。四、程序阅读题1.下列函数的功能是，将两个递增有序单链表La和Lb进行合并，要求合并之后的新单链表没有重复的元素并且递增有序。请在下列算法LinkMerge空缺处填入合适内容，使其成为一个完整的算法。voidLinkMerge(LinkListLa,LinkListLb，LinkList&pc) { //本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中 LinkListq; LinkListpa=La->next; LinkListpb=Lb->next; free(Lb); while(pa&&pb) { if(pa->data<pb->data) {(1);pc=pa;pa=pa->next;} elseif(pa->data>pb->data) { pc->next=pb; pc=pb; ; } else { pc->next=pa;pc=pa;pa=pa->next; q=pb;pb=pb->next;(3); } } if(pa) pc->next=pa; if(pb)(4);}2、二叉树采用二叉链表存储如右图所示：阅读下列算法,并回答问题：voidSwap（BinTreeT）{BinTrees;if（T）{s=T->lchild；T->lchild=T->rchild;T->rchild=s；Swap（T->lchild）；Swap（T->rchild）；}}假如用Swap函数执行右图的二叉树，写出执行之后的二叉树。3、以下算法实现在二叉排序树插入一个结点key，在算法空白位置填写适当的内容使算法完整。BinTreeInsert(BinTreet,intkey){ BinTreep=t; BinTrees,f; while(p!=NULL) { f=p; if(key==p->key)returnt; if((1))p=p->lchild; elsep=p->rchild; } s=(2); s->key=key; s->lchild=NULL; s->rchild=NULL; if(t==NULL)returns;//新节点为二叉排序树的根 if(key<f->key)(3); elsef->rchild=s; returnt;}4.对以下函数填空，实现以带头结点的单链表h为存储结构的直接选择排序。voidSelectSort(LinkListh){LinkListp，q，m；inttemp；p=h->next；while(p!=NULL){q=p->next；m=p；while(q!=NULL){if(m->key>q->key)；；}if(p!=m){temp=p->key；p->key=m->key；m->