《数据结构与算法》模拟试卷四

《数据结构与算法》模拟试卷四

ID:6694967

大小:41.00 KB

页数:3页

时间:2018-01-22

《数据结构与算法》模拟试卷四_第1页
《数据结构与算法》模拟试卷四_第2页
《数据结构与算法》模拟试卷四_第3页
资源描述:

《《数据结构与算法》模拟试卷四》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、《数据结构与算法》模拟试卷四一、名词解释(5*3=15分)数据结构满二叉树栈哈夫曼树拓扑排序二、填空题(1*16=16分)1.在一个长度为n的循环链表中,删除其元素值为x的结点的时间复杂度为______。2.已知指针p指向某单链表中的一个结点,则判别该结点有且仅有一个后继结点的条件是_____。3.如果入栈序列是1,3,5,…,97,99,且出栈序列的第一个元素为99,则出栈序列中第30个元素为______。4.根据数据元素之间关系的不同特性,通常有下列四类基本结构:_____、_____、_____、_____。5.数据元素之间的关系在计算机中可用顺序映像和非顺序映像表示,由此得到

2、两种存储结构是:_____、_____。6.线性表的链式存储方式中,每个结点包括两个域,分别是:_____和_____。7.在以HL为表头指针的带表头附加结点的单链表和循环单链表中,判断链表为空的条件分别为_____和_____。8.一棵高度为5的二叉树中最少含有_____个结点,最多含有_____个结点;9.在对一组记录(54,38,96,72,60,15,60,45,83)进行直接插入排序时,当把第6个记录60插入到有序表时,为寻找插入位置需比较________次。三、选择题(10*1=10分)1.对线性表进行折半查找最方便的存储结构是_____。A、顺序表B、有序的顺序表C、链

3、表D、有序的链表2.计算递归函数如不用递归过程通常借助的数据结构是_____。A、线性表B、双向队列C、树D、栈3.如果T2是由有序树T转换来的二叉树,则T中结点的后序排列是T2结点的_____。A、先序排列B、中序排列C、后序排列D、层序排列4.n个结点的线索二叉树中线索的数目为_____。A、(n-1)个B、n个C、(n+1)个D、(n+2)个5.设数组A[m]为循环队列Q的存储空间,front为队头指针,rear为队尾指针,则判定Q为空队列的条件是_____。A.(rear-front)%m==1B.front==rearC.(rear-front)%m==m-1D.front

4、==(rear+1)%m6.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中,其中根结点存放在BT[0],若BT[i]中的结点有左孩子,则左孩子存放在_____。A.BT[i/2]B.BT[2*i-1]C.BT[2*i]D.BT[2*i+1]1.连通图是指图中任意两个顶点之间_____。A.都连通的无向图B.都不连通的无向图C.都连通的有向图D.都不连通的有向图2.在一个长度为n的顺序线性表中顺序查找值为x的元素时,查找成功时的平均查找长度(即x与元素的平均比较次数,假定查找每个元素的概率都相等)为_____。AnBn/2C(n+1)/2D(n-1)/23.若一个栈的输入

5、序列是1,2,3,4,…,n,输出序列的第一个元素是n,则第i个输出元素是_____。A不确定Bn-iCn-i+1Dn-i-14.在单链表中插入一个结点,要修改____个结点的指针域。A1B2C3D4四、计算和应用题(共21分)1.已知一二叉树先序遍历顺序为ABDCEGHIJF,中序为DBAGEIJHCF,试构造该二叉树。2.证明:具有n个结点的完全二叉树的深度为。3.待排序关键字(34,12,28,45,66,7,3,21),写出快速排序的第一趟快排过程。五、算法阅读题(9*2=18分)1.如果希望循环队列中的向量单元都能得到利用,则可设置一个标志域tag,每当尾指针和头指针值相同

6、时,以tag的值为0或1来区分队列状态是“空”还是“满”。请对下列函数填空,使其分别实现与此结构相应的入队列和出队列的算法。intEnQueue(CirQueue*Q,DataTypex){if((1))return0;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%MAXQSIZE(2)return1;}intDeQueue(CirQueue*Q,DataType*x){if((3))return0;*x=Q->data[Q->front];Q->front=(4);;return1;}(1)(2)(3)(4)(5)1.下列算法利用二分查找方法在有序表

7、r中插入元素x,并保持表r的有序性,其中参数*n为表r的长度。请在空缺处填入合适的内容,使其成为一个完整的算法。voidBinInsert(SeqListr,int*n,DataTypex){intlow=1,high=*n,mid,i;while(low<=high){mid=(1);if(x.key

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。