山东科技大学2012-2013学年数据结构试卷

山东科技大学2012—2013学年第二学期《数据结构》考试试卷班级姓名学号题号一二三四总得分评卷人审核人得分1、在顺序表中插入或删除一个元素，需要平均移动__________元素，具体移动的元素个数与_______有关。2、表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是_______。3、数据结构中评价算法的两个重要指标是和__________。4、下列程序判断字符串s是否对称，对称则返回1，否则返回0；如f(abba)返回1，f(abab)返回0；intf((1)________){inti=0,j=0;while(s[j])(2)________;for(j--;ij&&s[i]==s[j];i++,j--);return((3)_______)}．5、设广义表L=((),()),则head(L)是___；tail(L)是____；L的长度是___；深度是__。6、已知一无向图G=（V，E），其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。7、写出图2所示的AOV网的两个拓扑序列：；；8、循环队列求队列中元素个数的公式是：；顺序栈栈满的判定条件是：10、一棵完全二叉树有892个结点，则该树的高度为；其叶子结点数为。1、选择题：18分（每个2分）1、在双向链表指针p的结点前插入一个指针q的结点操作是（）。A.p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B.p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C.q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D.q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;2、执行完下列语句段后，i值为：（）intf(intx){return((x0)?x*f(x-1):2);}inti;i=f(f(1));A．2B.4C.8D.无限递归3、在带头结点的单链表中查找x应选择的程序体是（）。（A）node*p=head-next;while(p&&p-info!=x)p=p-next;if（p-info==x）returnpelsereturnNULL;（B）node*p=head;while(p&&p-info!=x)p=p-next;returnp;（C）node*p=head-next;while(p&&p-info!=x)p=p-next;returnp;（D）node*p=head;while(p-info!=x)p=p-next;returnp;4、若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为()A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点5、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7},G的拓扑序列是（）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V76、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q,若6个元素出队的序列为e2、e4、e3、e6、e5和e1,则栈S的容量至少应该为（）。（A）6（B）4（C）3（D）27、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。（A）不发生改变（B）发生改变（C）不能确定（D）以上都不对2、应用题：24分1、一棵二叉树的中序遍历结果为：DBFEAGHCI，后序遍历结果为：DFEBHGICA。（1）画出这棵二叉树，并写出它的前序遍历结果；（2）将这棵二叉树转换成等价的森林或树。2、给出有向图G如图3所示，试求顶点V0到其他各顶点的最短距离和路径，并写出源点V0到V5的最短路径。3、设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使编码最短。3、算法设计题：20分①用自然语言说明算法思想；②给出所需的数据结构定义,做必要说明；③用C语言写出算法程序，做必要注释。1、设计算法求树的叶子数。10分2、有一个带头结点的单链表，每个结点包括两个域，一个是整型域data，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得data域相等的结点只保留一个。（10分）将树看做一个森林，则森林的叶子数可如下递归求取:若森林为空则叶子数为0，否则，将森林分为两部分。第一部分是第一颗树，第二部分是第二颗树及其后面的树组成的子森林。第二部分可以递归求叶子数，至于第一部分，当树只有一个结点时叶子数为1，否则，为第一颗树的子树森林的叶子数（可以递归求）。两部分加起来即可