数据结构复习一、选择每题2分共30简单冒泡排序归并稳定

一、选择：(每题2分，共30分 简单选择排序冒泡排序归并排序稳 ）是稳定的。堆排序排序快速排序基数排序不稳A)堆排序，冒泡排 B)快速排序，堆排C)直接选择排序，排 D)归并排序，冒泡排 堆排 C)排 312345，则下列序列中不可能是栈的输出序列的是（2341 B)5413 C)2314 D)15434、非空循环链表head的尾结点*p满足下列 A)head->next==p;B)head==p;C)p->next==head;D)p- 6、对于哈希函数H(key)=key%7,被称为同义词的关键字是 A)36和 C)15和 A) B)n- C) D)n- A. B. C. D.9、高度为K的二叉树最大的结点数为 C)2k- D)2k-1- A)(n- B)C) D) 12、已知有向图的正邻接链表的结构如下，从顶点1出发的按深度优先遍历序列是()A)123 142 132 D)143 413front,rear，则队列中元素个数为()（maxlenA)(rear-front+maxlen)%maxlenB)(rear-front)%C)rear-front+1D)front-14n（深度）是（ D)logn- A)插入 B)冒泡 C)二路归并 D)快速排序二、填空题：(每空2分，共20分) 个结点，则前序一定是3、利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为(756648293137 49的结点的孩子编号为 6AOEe(i)l(i)分别表示活动ai的最早开始时间和最晚开始时间，则当且仅当 ai FORi:=1TOnDOFORj:=iTOnDO 后 9、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次 691110、n个顶点的连通无向图，其边的条数至少为 三、解答题：(每题6分，共30分)1、已知一棵二叉树的前序扫描序列和中序扫描序列分别为CDFHJ和CDFHJG，试给出该二叉树的2、已知一棵二叉树的前序序列和中序序列分别为abdghcefigdhbaecif,请画出该二叉树。 I(I为f左e为叶子AB1CDEFAB1CDEF FDC5、指定Hash函数H(k)=3*kmod11及线性探测开地址法处理，试在0~10的散列空间中对关键字序列0123456789四、算法题：(1020分1stintSimilar(BiTreep,q)//判断二叉树pq是否相{if(p==null&&q==null)return(1);elseif(!p&&q||p&&!q)return(0);elsereturn(Similar(p->lchild,q->lchild)&&Similar(p->rchild,q-}//结束A无HB无IECJID8BKF、EC、LH、J、FBMLGE12345678900一、选择：(230分 C)最长回 4、非空循环链表head的尾结点p满足下列 A.head->next==p B.head==p C.p->next==head D.p->next==nil7、将一个长度为n的向量的第i个元素删除时，需要前移( A) B)n- C) D)n- )A) B)p→next→next:= D)s→next:=p→next; 12、从下列有关树的叙述中,选出正确的叙述（五、填空题：(220分)1、树中结点的最大层次称为树的高度或深 六、解答题：(630分1n个结点的K（k>=2)K2abdghcefigdhbaecif,请画出该二叉树。 I(I为f左e为叶子3(46,79,56,38,40,84),则利用快速排序的方法,分别写出以第一个记录为基准得到的前三4038465679 3840465679 384046567901∞4∞0923508∞∞60AV1->v21->v44^V2->v39->v4V3->v13->v25->v88^V4->v36->v40^5 AVL插入22

插入4后 插入1后 七、算法题：(1020分11，H（key）为关键字（标识符）的第一个字母在字母表中的序号，voidPrint_Hash(HashTableH)//按第一个字母顺序输出Hash表中的所有关键字,1voidPrint_Hash(HashTableH)//按第一个字母顺序输出Hash表中的所有关键字,其中处理采用线性探测开放定{for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex线性探测if(H(H.elem[j].key)==i)printf("%s\n",H.elem[j]);intH(char*s)//Hash{if(s)returns[0]-96;//求关键一个字母的字母序号(小写)elsereturn0;IntDeepth(PBiTNodeT)ReturnIntleft=Deepth(T->rchild);Intright=Deepth(T->rchild);If(left>right)returnleft+1;Elsereturnright+1;}选择：(230分 5、A)插入 B)冒泡 C)二路归并 D)快速排序八、算法题：(每题10分，共20分)1llinkdatarlinkP所指结点与其rlink2sqqueue1的循环顺序队列只用一个rearcount用于记录队列中的元素个数。编写算法实现队列的初始化、进队、出队、取队头元素操作。sqqueue1类型的循环顺序队#define elemtypdata[maxlen]; rear,count;九、算法题：(1020分1typedefstructDLNode{ElemTypedata;structDLNodeStatusSwapANode(DLNode*&P){if(!P||!(P->rlink))returnERROR;q=P->rlink;P->rlink=NULL;else{P->rlink=q->rlink;q->rlink->llink=}{q->llink=NULL;q->rlink=P;P->llink=}elseq->llink=P->llink;q->rlink=P;P->llink->rlink=q;P->llink=q;}return}2 } q, (q.count==maxlen)print(“overflow!”);else{} } } if else }}十、选择：(230分 A)堆排 C)排 （1）8447251521（2）1547258421（3）1521258447(4）15212547则采用的排序是 )A)选 B)冒 C)快 D)插G=(V,E<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V6,V7>},G（ A)下面的B，C，D都不对。 D)9，4，7，8，7，-1，15，20十一、算法题：(每题10分，共20分)VoidPostOrder（PBiTNodeT,(void*)(visit)char{Visit(T-}}13front,rear，则队列中元素个数为()（maxlenA)(rear-front+maxlen)%maxl