2010年全国自考数据结构模拟试卷(五)及答案.doc

更多优质自考资料，请访问自考乐园俱乐部/club/53463892010年全国自考数据结构模拟试卷(五)一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项目中只有一个是符号题目要求的,请将其代码填写的括号内.错选、多选或未选均无分。1.设矩阵A(aij,1i,j10)的元素满足：aij0(ij,1i,j10)aij0(inext=NULLC.head-next=headD.head!=NULL答案：B更多优质自考资料，请访问自考乐园俱乐部/club/53463897.在下图中，从顶点V1出发，按广度优选遍历图的顶点序列是()A.V1V5V3V4V2V6V7B.V1V5V3V4V2V7V6C.V1V7V2V6V4V5V3D.V1V2V4V7V6V5V3答案：A8.已知一棵二叉树结点的先根序列为ABDGCFK，中根序列为DGBAFCK，则结点的后根序列为()A.ACFKBDGB.GDBFKCAC.KCFAGDBD.ABCDFKG答案：B9.C语言数组Datam+1作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为()A.front=front+1B.front=(front+1)%mC.rear=(rear+1)%mD.front=(front+1)%(m+1)答案：D10.任何一个带权的无向连通图的最小生成树()A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在答案：B更多优质自考资料，请访问自考乐园俱乐部/club/534638911.将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的结点的双亲结点编号为()A.42B.40C.21D.20答案：D12.采用分治法进行排序的方法是()A.快速排序B.插入排序C.堆排序D.希尔排序答案：A13.设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数量少()个。A.k+1B.2kC.2k-1D.2k+1答案：C14.一个长度为10的有序表，按照二分查找法对该表进行查找，在表内各元素等概率的情况下，查找成功所需要的平均比较次数为()A.25/10B.27/10C.29/10D.31/10答案：C15.索引非顺序文件是指()A.主文件无序，索引表有序B.主文件有序，索引表无序C.主文件有序，索引表有序D.主文件无序，索引表无序答案：A更多优质自考资料，请访问自考乐园俱乐部/club/5346389二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填写上正确答案。错填、不填均无分。1.在B树上进行删除操作分为两个步骤，即：_和_。答案：在树上查找被删除关键字K所在的地点删除K2.在图的邻接表表示中，每个顶点邻接表中的顶点数，对于有向图来说是_，对于无向图来说是_。答案：出度数度数3.若一棵二叉树中只有叶结点和左、右子树皆非空的结点，设叶结点的个数为1，则左、右子树皆非空的结点个数为_。答案：1-14.朴素的串匹配算法的特点是简单，但是其效率较低，其时间匹配算法的最坏时间是_(假设模式串的长度是m,目标串的长度是n)。答案：O(m+n)5.一个nn的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为_。答案：n(n+1)/26.假设在线索二叉树中，结点的标志域的值为0时，表示其指针域是指向孩子的指针，当结点的标志域为1时，表示其指针域是指向前趋或者后继的线索，则一个结点是叶结点的充要条件是_。答案：结点的左右标志都是17.在分块查找法中，首先查找_，然后再查找相应的_。答案：索引表 块8.对于一个二维数组Amn，若按行序为主序存储，则任一元素Aij相对于A00的地址为_。答案：ij+i全元素位置9.就文件而言，按用户的观点所确定的基本存储单元称为_。按外设的观点所确定的基本存储单元称为_。答案：逻辑记录 物理记录更多优质自考资料，请访问自考乐园俱乐部/club/534638910.在顺序表中，插入或者删除一个元素，需要平均移动_个元素，具体移动的元素个数与_有关。答案：约表长的一半 该元素在线性表中的位置三、解答题（本大题共4小题，每小题5分，共20分）1.已知连通图如下：分别以邻接矩阵的邻接表实现存储，试给出该图的邻接矩阵和邻接表，若从顶点B出发对该图进行遍历，分别给出一个按深度优先搜索和广度优先搜索的顶点序列。答案：2.假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。答案：更多优质自考资料，请访问自考乐园俱乐部/club/53463893.已知一棵二叉树按照顺序结构存储，其存储结构如下：(1)请画出此二叉树的树形结构。(2)请写出此二叉树的前序遍历、中序遍历和后序遍历序列。(3)此二叉树的高度是多少?(4)结点F的双亲、孩子，以及祖先分别是什么?(5)此树中，度数为1的结点共有几个?分别是哪几个?(6)结点C有左孩子吗?如果有左孩子，则C的左孩子的编号应该是什么?答案：此二叉树如图所示：(2)前序遍历序列为：ABDEFGMCHJ中序遍历序列为：EDGFMBACHJ后序遍历序列为：EGMFDBAJHC(3)此树的高度是5。更多优质自考资料，请访问自考乐园俱乐部/club/5346389(4)结点F的双亲是D，孩子是G，M(其中G是其左孩子，M是其右孩子)，祖先是D，B，A。(5)此树中度数为1的结点共有3个，分别为B，C，H。(6)结点C没有左孩子，如果它有左孩子，则左孩子的编号为6(23=6)4.已知有一组长度为9的关键字序列为22，63，72，54，97，17，37，80，92，现在假设散列表的地址空间为T0.10,请用除余法构造散列函数，如果存在冲突问题，请用线性探查法解决冲突，并给出相应的散列表。答案：因为散列函数为：h(key)=key%11,则根据此函数得到上述关键字序列的散列地址为：(0，8，6，10，9，6，1，3，4)，前5个关键字在插入时，其相应的地址是开放地址，可以直接插入到T0，T8，T6，T10，T9中，在插入到6个关键字时，其散列地址6已被关键字72占用，所以探查h1=(6+1)%11=7。此地址开放，所以将关键字17插入到T7中，然后再依次将关键字34，80，92插入到相应的散列地址中即可。则相应的散列表为：更多优质自考资料，请访问自考乐园俱乐部/club/5346389四、算法阅读题（本大题共4小题，每小题5分，共20分）1.写出下列程序段的输出结果。(假设此栈中元素的类型是char)voide main()stack s;char x,y;InitStack(s)x=1,y=Opush(s,x);push(s,x);push(s,y);push(s,x);push(s,e);push(s,x);pop(s,x);push(s,h)；while(! stackEmpty(s)pop(s,y);printf(y);prinft(x)答案：此题的输出结果是hello。2.以下运算实现在循环队上的入队列，请在_处用适当的语句予以填充。int EnCycQueue(CycqueueTp *sq,DataType x) if(sq-rear+1)% maxsize=_)error(队满);return(0);else_;_;return(1);更多优质自考资料，请访问自考乐园俱乐部/club/5346389答案：sq-front sq-rear=(sq-rear+1)% maxsize sq-datasq-rear=x3.以下算法实现若开散列表HP中存在键值为K的结点，则将其删除。请分析程序，并在_上填充合适的语句。void delete-openhash(keytype K,openhash HP) i=H(K);if(HPi=NULL) return; /*空表则退出*/p=HPi;if(p-key=K)_=p-next;free(p);return;/*表首结点为待删除结点时的删除*/while(p-next!=NULL)/*其他情况下的删除*/ q=p;p=p-next;if(p-key=K)_=p-next;delete(p);return; 答案：HPi q-next4.根据文字说明，请在以下_处填充适当的语句。采用静态链表作存储结构，设置一个大小为2n-1的数组，令数组的每个元素由四个域组成：wt是结点的权值；lchild、rchild分别为结点的左、右孩子指针；parent是结点的双亲在数组中的下标。其数组元素类型定义如下：typedef struct float wt；/*权值*/int parent,lchild rchild;/*指针域*/node;typedef node hftree2*n-1;在这种存储结构上的哈夫曼算法可描述如下：void huffman(int k,float Wk,hftree T)/*求给定权值W的哈夫曼树T*/ int i,j,x,y;float m,n;for(i=0;i2*k-1;i+) Ti.parent=-1;Ti.lchild=-1;Ti.rchild=-1;if(_)Ti.wt=Wi;else Ti.wt=0for(i=0;ik-1;i+) x=0;y=0;m=maxint;n=maxint;for(j=0;jk-i,j+)if(Tj.wtm)&(Tj.parent=-1)n=m;y=;m=;x=j;else if(Tj.wtn)&(Tj.parent=-1)n=Tj.wt;y=j;Tx.parent=_;Ty.parent=_;Tk+i.wt=_;Tk+i.lchild=;Tk+i.rchild=_;更多优质自考资料，请访问自考乐园俱乐部/club/5346389答案：ik x Tj.wt k+i k+i m+n x y五、算法设计题（本题10分）1.设计一个双向起泡排序算法，即在排序过程中交替改变扫描方向。答案：可通过设置一个标志位进行区分的方式来进行交替扫描，算法描述如下：Alterbubblesort(r)/*交替扫描法起泡排序*/Rectype R