资源描述：
《算法与数据结构习题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《算法与数据结构》习题1第一部分一、单项选择题1.()二叉排序树可以得到一个从小到人的有序序列。A^先序遍历B、中序遍历C、后序遍历D、层次遍历2.设按照从上到卜-、从左到右的顺序从1开始对完全二义树进行顺序编号，则编号为i结点的左孩子结点的编号为()。A、2i+lB、2iC、i/2D、2i-l3.设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列为()oA、q二p->next；p->data=q->data；p->next二q->next；free(q)；q二p->n
2、ext；q->data=p->data；p->next二q->next；free(q)；C^q二p->next；p->next=q-〉next；free(q)；D、q二p->r)ext；p->data=q->data；free(q):4.设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为()。A、BADCB、BCDA5.6.7.C、CDABD、CBDA设某冇向图的邻接表中冇n个表头结点和m个表结点，则该图中冇(AsnBxnTC^mD、m-1设二叉排序树中冇n
3、个结点，则在二叉排序树的平均平均查找长度为(A、0仃)B、O(log2n)C、0(nlog2n)D、0(n2)设有序表中有1000个元素，则用二分查找查找元素X最多需耍比较(A、25B、10C、7D、1)条冇向边。)。)次。二、填空题1.设指针变量P指向双向链表中的结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X的操作序列为二p；s->right=p->right；二s；p->right->left=s；(设结点中的两个指针域分别为left和right)o2.一个算法的时间复杂度为
4、(n：Wlog2n+14n)/n2,其数量级表示为一__。3.设一棵三叉树中冇50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数有个。4.后缀算式923+-102/-的值为o中缀算式(3+4X)-2Y/3对应的后缀算式为o5.设初始记录关键字序列为(KI,K2,,,,Kn),则用筛选法思想建堆必须从第个元素开始进行筛选。1.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别冇个和个。2.遍历二叉排序树屮的结点可以得到一个递增的关键字序列(填先序、
5、中序或后序)。3.完全二叉树中第5层上最少有个结点，最多有个结点。三、计算题1.设散列表的地址范围是［0..9］，散列函数为H(key)=(key2+2)MOD9,并釆用链表处理冲突，请画出元素2、4、5、3、6、7、8、9依次插入散列表的存储结构。2.请下图所示的森林：1)求树(a)的先根序列和后根序列；2)求森林先序序列和中序序列；3)将此森林转换为相应的二叉树；3.己知二叉树的前序遍丿力序列是AEFBGCDH1KJ,屮序遍历序列是EFAGBCHK1JD,画出此二叉树，并应出它的后序线索二叉树
6、。四、算法填空下列算法实现在顺序散列表屮杳找值为k的关键字，请在下划线处填上正确的语句：structrecord{intkey;intothers;};inthashsqsearch(structrecordhashtable[],intk){inti,j;j=i=k%p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=()%m;if(i==j)return(T);}if()return(j);elsereturn(-1);五、编写算法1、设计
7、计算二叉树屮所有结点值之和的算法。2、设计将所有奇数移到所有偶数之前的算法。第一部分参考答案一、单项选择题题号1234567答案BBAACBB二、填空题1.s->left=p,p->right2.0(n)3.144.-134X*+2Y*3/・5.n/26.c2c7.中序&116三、计算题1.H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=601234567891)ABCDEF；BDEFCA；2)ABCDEFGHIJK；BDEFCAIJKHG3)森林转换为
8、相应的二叉树：3.线索二叉树为:四、算法填空j+1,hashtable[j]・key==k五、编写算法1、voidsum(bitree*bt,int&s){if(bt!=0){s二s+bt->data;sum(bt->lchiId,s);sum(bt->rchild,s);}}voidquickpass(intr[],ints,intt){inti=sj=t,x=r[sj;while(i
