样题习题数据结构复习

—二三四一.单项选择题（共12分）请将所选项的编号填入各题左边的括号【B组成数据的基本单位数据 [B]数据元 [C]数据类[D]据变【A采用链式结构便于实现对线性表插 [B]遍 [C]查[D]【A3.循环队列用数组A[0..m-1]存放元素其头尾指针分别为frontrear，[A](rear–front+m)% [B][C] [D](rear–front)%【=（a，b，c（d，e，f，[A] [B][C]tail(head(tail(head(A))))[D]【C5.有2000结点的二叉树，其高度至少[A] [B] [C] [D]D6.邻接矩阵A，第i点的入A[A]第i行非∞元素个 [B]第i列非∞元素个[C]第i行非∞且非0元素个 【B7.一个长度为12有序表进行等概率的折半查找，查找成功所需的关键[A] [B] [C] [D]【C8.果对下列顺序表分别作快速排序，所需比较次数最少的[A] [B][C] [D]12 和基本 循环链表的主要优点 从表中任一结点出发均可找到表中其他结 两个串相等的充分必要条件 字符依次对应相同且长度相同_？？12.设有一个10阶的对称矩阵A，以行为主序其下三角中的元素，A的第一个元素a11的地址为1，每个元素占用1个单元，则a85的地址为 。13.前序和中序序列相同的二叉树的特征 各结点均无左孩子_？？14.具有n个顶点的强连通图至少有 15.外排序是 在排序过程中需要外 的排序方法16.直接存取文件是用杂凑 方法组织的（3617（5分）请直接在以下二叉树中添加后序线索EEDBCKAF18.（10分）已知一个长度为12的表设哈希表长度为13，哈希函数H（k）=i/2，其中i为关键字k中第一个字母在4，19.（5分）假设电文中ah8个字母组成，字母在电文中出现的频度依次，8个字母相应的哈夫曼编码。20.（8分）若对序列（25，19，7，41，29，12，23，26）按升序排序，请分别给步长为4的一趟希尔排序的结果初始大根堆52 21.（8分）对于右边的带权图52 画出G的邻接矩阵画出G的最小生成树（4022（6分）函数f22定义如下，其中函数调用Insert(L,i,k)在顺序表L的第位置插入kvoidf22(SqList&L,inti){if(i>0){f22(L,i-for(intk=1;k<=i;k++)Insert(L,i,k);}}设有空顺序表L＝（，请写出调用递归函数f22(L,3)L的长度L＝（1，2，3， 23.（6分）算法f23(L)将结点的单链表L逆置。请在画线处填空voidf23(LinkList&L){LinkListp=L->next;L->next=NULL while(p){LinkLists=P— p->next=L->next;L->next=p;p=}}24.OK（6分）s是一个升序静态查找表，请简要说明函数调用f24(s,1,s.length,k)的意义。intf24(SSTables,intlow,inthigh,KeyTypek){if(low>high)return0;intif(k==s.elem[mid].key)returnif(k>s.elem[mid].key)returnf24(s,mid+1,high,k);elsereturnf24(s,low,mid-1,k);}答：在s中递归折半查找25（6分）请对以下函数填空，实现求二叉树T中各结点的子孙总数，并填入结点um域中的算法intf25(BiTreeT)if(!T )return-1;else{ um=f25(T->lchild)+ returnT- }}26（6分）图的邻接矩阵表示和算法f26描述如下#defineMaxNum5typedefstruct{charintarcs[MaxNum][MaxNum];intn,e;}intf26(MGraphG,inti){intd=0;for(intj=0;j<G.n;j++){if(G.arcs[i][j])d++;if(G.arcs[j][i])}return}已知一个图G的邻接矩阵如下所示 0 0G.arcs= 1 0 027（10后写出算法的C语言描述。voidpurge(LListL){LLists,q,p=L->next;while(p){q=while(q-if(q->next->data!=p->data)q=q->next;{s=q->next;q->next