《2009年全国自考数据结构模拟试卷(一)及答案.pdf》由会员分享，可在线阅读，更多相关《2009年全国自考数据结构模拟试卷(一)及答案.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！更多试卷，请访问9州考苑（2009年全国自考数据结构模拟试卷(一)一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项目中只有一个是符号题目要求的,请将其代码填写的括号内.错选、多选或未选均无分。1.任何一个带权的无向连通图的最小生成树()A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在答案：B 2.Aarr和Barr两个数组的说明如下：VARAarr:Array07of char;Barr:Array-52,3,8of char;这两个数组分别能存放的字符的最大个
2、数是()A.7和35B.1和5C.8和48D.1和6答案：C 3.下列说法中正确的是()A.任何一棵二叉树中至少有一个结点的度为2B.任何一棵二叉树中的每个结点的度为2C.任何一棵二叉树中的度肯定等于2 D.任何一棵二叉树中的度可以小于2答案：D 4.二分查找算法要求被查找的表是()A.键值有序的链表B.键值不一定有序的链表C.键值有序的顺序表D.键值不一定有序的顺序表答案：C 5.设图G采用邻接表存储，则拓扑排序算法的时间复杂度为()A.O(n)B.O(n+e)C.O(n2)D.O(ne)欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！更多试卷，
3、请访问9州考苑（答案：B 6.设数组data0.m作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为()A.front:front+1B.front:(front+1)mod mC.rear:(rear+1)mod mD.front:(front+1)mod(m+1)答案：D 7.设串s1=ABCDEFG,s2=PQRST,函数con(x,y)返回x和y串的连(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的con(subs(s1,2,len(s2),subs(s1,len(s2),2)的结果串是()A.BCDEFB
4、.BCDEFGC.BCPQRSTD.BCDEFEF答案：D 8.设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是()A.AB.BC.CD.D答案：D 9.森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4，那么当把森林T转换成一棵二叉树后，其根结点的左孩子上有()个结点。A.n1-1B.n1C.n1+n2+n3D.n2+n3+n4答案：A 10.对广义表(a),(b)进行下面的操作head(head(a),(b)后的结果是()A.aB.(a)欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！更多试卷，请访问9州
5、考苑（C.()D.不确定答案：A 11.将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的结点的双亲结点 编号为()A.42B.40C.21D.20答案：D 12.线性表若采用链表存储结构时，要求内存中可用存储单元的地址()A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以答案：D 13.长度为12的有序表：Apr,Aug,Dec,Feb,Jan,Jul,Jun,Mar,May,Nov,Oct,Sep,按折半查找法对该表进行查找。在表内各元素等概率情况下查找 成功所需的平均比较次数为()A.35/12B
6、.37/12C.39/12D.43/12答案：B 14.从一个包含2000个结点的散列表A1.2000中查找结点的平均比较次数()从一个包含200个结点的散列表B1.200中查找结点的平均比 较次数。A.大于B.小于C.等于D.不确定答案：D 15.设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！更多试卷，请访问9州考苑（A.5B.6C.7D.8答案：A 二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填写上正确答案。错填、不填均无分。1.带有一个头结点的单链表h
7、ead为空的条件是_。答案：head-next=NULL 2.散列文件关键在于选择好的_和_方法。答案：散列函数 冲突处理 3.记录的_结构是数据在物理存储器上的存储方式。答案：物理 4.在非空队列中，头指针始终指向_，而尾指针始终指向_。答案：队头元素 队尾元素 5.数组的长度是_，线性表的长度是_。答案：固定的 可变的 6.设二维数组A1020，510按行优先存储，每个元素占4个存储单元，A10，5的存储地址是1000，则A15，10的存储地址是_。答案：1700 7.顺序串是用一组地址连续的存储单元来存储串中的字符序列，所以可以用字符数组来实现，按照存储分配方式的不同可以将顺序串分为两类
8、：即_和_。答案：静态存储分配的顺序串 动态存储分配的顺序串 8.N个顶点的连通图，至少有_条边。答案：N-1 9.假设在线索二叉树中，结点的标志域的值为0时，表示其指针域是指向孩子的指针，当结点的标志域为1时，表示其指针域是指向前趋或者后继的线索，则一个结点是叶结点的充要条件是_。答案：结点的左右标志都是1 10.在双向链表中，每个结点含有两个指针域，一个指向其_结点，另一个指向_结点。答案：前趋 后继 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！更多试卷，请访问9州考苑（三、解答题（本大题共4小题，每小题5分，共20分）1.已知有一关键字序
9、列为486，79，596，34，900，120，789，179，703，307，如果我们采用基数排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。答案：基数排序的基本思想是：从低位到高位依次对kj(j=d-1,d-20)进行箱排序，根据基数排序法的基本方法，我们得到如下的排序结果：初始：486，79，596，34，900，120，789，179，703，307第1趟：(按个位进行排序)：120，900，703，34，486，596，307，79，179，389第2趟：(按十位进行排序)：307，703，900，120，34，79，179，486，789，596第3趟：(按百位进
10、行排序)：34，79，120，179，307，486，596，703，789，900 2.请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图（顶点vi表示）。答案：A，B，C对应的图分别为：3.对于散列文件来说，其存储单位是什么?对于一个能存储m个桶，若需要存放的同义词大于m，则需要如何处理?现在假设一个文件有18个记录，其关键字分别为：30，11，27，04，19，86，73，89，32，05，103，58，45，67，77，81，08，48，假设桶的容量m=3，桶数b=7，现在要求用除余法做散列函数H(key)=key%7，请给出该散列文件的表示方法。答案：磁盘上的文件记录通常是成组存
11、放的，若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做桶。欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！更多试卷，请访问9州考苑（，如果二叉树中有201个结点，则必有101个叶结点，100个度数为2的结点，没有度数为1的结点。四、算法阅读题（本大题共4小题，每小题5分，共20分）1.以下为单链表的删除运算，分析算法，请在_处填上正确的语句。void delete-lklist(lklist head,int i)p=find-lklist(he
12、ad,i-1);if(_)q=_;p-next=q-next;free(q);else error(不存在第i个结点)答案：(p!=NULL)&(p-next!=NULL)p-next 2.以下为单链表的建表算法，分析算法，请在_处填上正确的语句。lklist create-lklist2()/*直接实现的建表算法。*/head=malloc(size);p=head;scanf(%f,&x);while(x!=$)q=malloc(size);q-data=x;p-next=q;_;scanf(%f,&x);_;return(head);此算法的量级为_。答案：p=q p-next=NULL
13、 O(n)3.以下算法在指针T所指的二叉排序树上的查找键值等于K的结点。成功时回送指向该结点的指针；否则回送空指针。请分析程序，并在_上填充合适的语句。bitreptr search-bst(bitreptr T,keytype K)if(T=NULL)return(NULL);else switch case T-key=K:_;欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！更多试卷，请访问9州考苑（case_:return(search-bst(T-lchild,K);case_:return(search-bst(T-rchild,K);答
14、案：return(T)T-keyK T-keykey=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-next 五、算法设计题（本题10分）1.设计一个双向起泡排序算法，即在排序过程中交替改变扫描方向。答案：可通过设置一个标志位进行区分的方式来进行交替扫描，算法描述如下：Alterbubblesort(r)/*交替扫描法起泡排序*/Rectype R;int i,j,temp,flag;/*设置扫描标志flag*/flag=True;i=0;while(flag)/*开始扫描*/flag=False;for(j=n-i,ji,j-)if(Rj,keyRj-1,key)flag=True;temp=Rj;Rj=Rj-1;Rj-1=temp;for(j=1;jRj+1.key)flag=True;temp=Rj;Rj=Rj+1;Rj-1=temp;i+;/*往右扫描*/*Alterbubblesort*/