安徽大学期末考试数据结构试卷

第1页共7页安徽大学《数据结构》考试试卷（A卷）一、填空题1、在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。2、下面程序段的时间复杂度是。for(i=0;in;i++)for(j=0;jm;j++)A[i][j]=0;3、在具有n个单元的循环队列中，队满时共有个元素。4、假定一棵二叉树的结点数为18，则它的最小深度为，最大深度为。5、在一个单链表中p所指结点之后插入一个s所指结点时，应执行下面的操作：s—＞next=____;p—＞next=___;6、从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为和。7、.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有___________________个。8、在堆排序和快速排序中，若原始记录接近正序或反序，则选用____。9、若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的________遍历。二、单向选择题（每小题1.5分，共15分）1、n个顶点的强连通图中至少含有()。A、n—l条有向边B、n条有向边C、n(n—1)／2条有向边D、n(n一1)条有向边2、在一个不带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，执行()。A、HL＝p;p一next＝HL;B、p一next＝HL；HL＝p;C、p一next＝HL;p＝HL;D、p一next＝HL一next;HL一next＝p;3、采用线性链表表示一个向量时，要求占用的存储空间地址（）。A:必须是连续的B部分地址必须是连续的C:一定是不连续的D:可连续可不连续4、如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。A:起泡排序B:堆排序C:锦标赛排序D:快速排序5、在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。A:(front-rear+1)%mB:(rear-front+1)%mC:(front-rear+m)%mD:(rear-front+m)%m6、数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是()。第2页共7页A:1175B:1180C:1205D:12107、已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是()A:head(tail(LS))B:tail(head(LS))C:head(tail(head(tail(LS)))D:head(tail(tail(head(LS))))8、某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（）。A:bdgcefhaB:gdbecfhaC:bdgaechfD:gdbehfca9、在一个无向图中,所有顶点的度数之和等于所有边数的（）倍。A:1/2B:1C:2D:410、设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（）。A：BCDEFB：BCDEFGC：BCPQRSTD：BCDEFEF三、应用题（每小题8分，共32分）1．一棵深度为h的满m叉树具有如下性质:第h层上的结点都是叶结点,其余各层上每个结点都有m棵非空子树。若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,试计算:(1)第k层结点数(1≤k≤h)。(2)整棵树结点数。(3)编号为i的结点的双亲结点的编号。(4)编号为i的结点的第j个孩子结点(若有)的编号。得分第3页共7页2已知图G的邻接表如图1所示，请写出：（1）其从顶点v1出发的深度有限搜索序列；（2）其从顶点v1出发的广度优先搜索序列。图1图G的邻接表3、以关键码序列（503,087,512,061,908,170,897,275,653,426），为例，手工执行快速排序排序算法，写出每一趟排序结束时的关键码状态：v1v2v3v4^v5v6^V2V5V4^v3V5^V4V6V3^V6^第4页共7页4．使用哈希函数H(key)=key%11，把一个整数值转换成哈希表下标，现要把数据1、13、12、34、38、33、27、22插入到哈希表（表1）中。（1）使用线性探测再散列法构造哈希表，请在表1所示的哈希表中与哈希地址对应的位置上，填写出相应的关键字值和元素插入时的探查次数。（2）假设查找每个元素的概率相同，求出查找成功时的平均查找长度。表1哈希地址012345678910关键字值探查次数第5页共7页四、算法阅读题（每小题9分，共18分）1、完成二叉树按层遍历的算法。voidleveltravel(structtreenode*bt){structtreenode*p,*a[n];intrear=front=-1;p=bt;rear=__________;a[rear]=p;while(rear!=front){front=___________;p=a[front];printf(“%c”,p-data);If(p-left!=null){rear=(rear+1)%na[rear]=_________;}If(p-right!=null){rear=(rear+1)%n;a[rear]=_________;}}}2、下面算法是对直接插入排序算法的改进，请填写完整voidweizhisort(structnoder[n+1],intn){intlow,high,mid,j,i;for(i=2;i=n;i++){r[0]=r[i];low=__________;high=_________;while(low=high){mid=(low+high)/2;if(r[0].keyr[mid].key)_______________;elselow=mid+1;}for(j=i-1;j=low;j--)r[j+1]=r[j];r[low]=r[0];}}得分第6页共7页五、算法设计题（每小题10分，共20分）1、已知二叉树中的结点类型BinTreeNode定义为：structBinTreeNode{ElemTypedata；BinTreeNode*left，*right}；其中data为结点值域，left和right分别为指向左、右子女结点的指针域。请写一函数，功能是返回二叉树BT中值为x的结点所在的层号。IntNodeLevel(BinTreeNode*BT，ElemTypeX){}NodeLevel2、从一维数组A[n]中二分查找关键字为K的元素的递归算法，若查找成功则返回对应元素的下标，否则返回一1。intBinsch(ElemTypeA[]，intlow，inthigh，KeyTypeK){第7页共7页}Binsch