1月大数据结构问题详解解析汇报

做试题,没答案?上自考365,网校名师为你详细解答!全国2010年1月自学考试数据结构试题课程代码：02331一、单项选择题(本大题共15小题，每一小题2分，共30分) 在每一小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多项选择或未选均无分。1假如一个算法的时间复杂度用T(n)表示，其中n的含义是 A问题规模 B语句条数C循环层数 D函数数量答案：A 解析：常识问题2具有线性结构的数据结构是 A树 B图C栈和队列 D广义表答案：C 解析：顺序表、单链表、双链表、循环链表、栈和队列等都是1:1关系，是线性的。 树：结点之间1：n关系，非线性的。广义表和图是m:n关系，非线性的。3将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为 AO(1) BO(m)CO(n)DO(m+n)答案：B解析：链表A与链表B连接问题，可以这样考虑，链表A和链表B，我们只知道其头指针或头结点，我们连接是把链表A的尾部连接到链表B的头部，要知道链表A的尾部，就必须从链表A的头部做m次判断，得到链表A的尾部，然后直接和链表B的头部连接就可以了。(原来链表A的尾部是指向NULL的，连接链表B就是把链表A尾部的NULL改为链表B的头结点的指针。)4在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是 A2个 B3个 C4个D6个答案：C解析：双向循环链表中结点与结点之间有4条线，所以插入一个新结点，需要修改指针域的数量为4条。5假设以数组A60存放循环队列的元素，其头指针是front=47，当前队列有50个元素，如此队列的尾指针值为 A3 B37C50 D97答案：B解析：循环队列，front=47,如此rear=(front+队列元素个数)%数组长度=(47+50)%60=37。6假如栈采用链式存储结构，如此如下说法中正确的答案是 A需要判断栈满且需要判断栈空 B不需要判断栈满但需要判断栈空 C需要判断栈满但不需要判断栈空 D不需要判断栈满也不需要判断栈空答案：B解析：链栈由于采用链表方式作为存储方式，入栈时，使用malloc申请空间后，用指针相连接，所以结点个数没有限制，但是出栈时，如果栈中的元素个数为0，就不能再出栈了。7假如串str=Software，其子串的数目是 A8 B9C36 D37答案：D解析：字串包括：单字符的字串：S、o等共8个，2个字符的字串So、of共7个，3个字符的字串Sof、oft等共6个，以此类推，可以知道总数量S=8+7+6+5+4+3+2+1=1+8*8/2=36。最后别忘记了，空串是任何字符串的字串，所以S=36+1=37.结论：求字符串的子串个数公式：S=(1+字符串长度)* 字符串长度/2+18设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，如此a85的地址为 A1012 B1017C1032 D1039答案：C解析：按行优先压缩，每一行10个元素。又由于下标从1开始且是下三角，所以a85的前7行共有1+2+3+4+5+6+7=(1+7)*7/2=28个元素，第8行不满，列5前有5-1=4个元素，所以a85前共有28+4=32个元素。又由于每个元素占一个地址单元，所以a85的地址=a11+32个元素的地址增量=1000+32*1=1032。9允许结点共享的广义表称为 A纯表 B线性表C递归表 D再入表答案：D解析：没有共享结点，没有递归结点的表是纯表。有共享结点的表是再入表，有递归结点的表是递归表。10如下数据结构中，不属于二叉树的是 AB树 BAVL树C二叉排序树 D哈夫曼树答案：A解析：根据概念可以得到答案。11对下面有向图给出了四种可能的拓扑序列，其中错误的答案是 A1，5，2，6，3，4 B1，5，6，2，3，4C5，1，6，3，4，2 D5，1，2，6，4，3答案：C解析：根据先找没有前驱的结点的方式，找到没有前驱的结点后，后删除该结点上的连线，可以推出C是错误的。12以v1为起始结点对如下图进展深度优先遍历，正确的遍历序列是 Av1，v2，v3，v4，v5，v6，v7 Bv1，v2，v5，v4，v3，v7，v6Cv1，v2，v3，v4，v7，v5，v6 Dv1，v2，v5，v6，v7，v3，v4答案：D解析：从V1出发，根据标号最小原如此，深度遍历后，容易得出D是正确的。具体遍历方式为：V1-v2-v5-v6，v6没有出度，返回v5，v5-v7，v7没有出度，返回v5，v5的2个出度(v6和v7)都已经遍历，返回v2，v2的2个出度(v5和v6)都已经遍历，返回v1，v1-v3，v3没有出度，返回v1,v1-v4，所以最后的遍历序列为v1-v2-v5-v6-v7-v3-v4。13如下排序算法中不稳定的是 A快速排序 B归并排序C冒泡排序 D直接插入排序答案：A解析：稳定的排序算法共有4个，直插、冒泡、归并、基数，其他的都是不稳定的。14一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值32时，查找成功需要的比拟次数是 A2 B3C4 D8答案：B解析：第一次查找取mid=(low+high)/2=(1+13)/2=7,如果数组名为R，如此R7=45，32比45小，如此应该在前半局部再找，所以high=mid-1=6。第二次查找取mid=(low+high)/2=(1+6)/2=3,如此R3=9,9比32小，应该在后半局部找。所以low=mid+1=4。第三次查找mid=(low+high)/2=(4+6)/2=5,如此R5=32,32=32成立，找到了。总共查找了3次。15采用ISAM组织文件的方式属于 A链组织 B顺序组织C散列组织 D索引组织答案：B二、填空题(本大题共10小题，每一小题2分，共20分) 请在每一小题的空格中填上正确答案。错填、不填均无分。16数据元素与其关系在计算机存储器内的表示称为_。答案：存储结构。解析：数据结构包括三个局部：逻辑结构、存储结构、算法。17长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是_。答案：i解析：由于单链表查找，必须从头指针或头结点开始查找。查找第一个元素时需要的时间为1次，查找第二个元素需要判断的时间为2次，以此类推，查找第i个元素的时间为i次。18下面是在顺序栈上实现的一个栈根本操作，该操作的功能是_。 typedef struct DataType data100；inttop；SeqStack； DataType f18(SeqStack*S) if(StackEmpty(S) Error(Stack is empty)； return S-dataS-top；答案： 取栈顶元素 或 取栈顶元素的值解析：前面是栈的定义，函数f18中，最后一句return s-datas-top。s-top是栈顶的位置，s-dataX，表示栈的X位置上的元素值。19在串匹配中，一般将主串称为目标串，将子串称为_。答案： 模式串解析：概念题，记住它。20广义表C=(a(b，c)，d)，如此：tail(head(tail(C)=_。答案： ()解析：从最里面开始，tail(C)(d),head(tail(C)d,tail(head(tail(C) ()。21用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为_。 答案： 219解析：这6个结点作为哈夫曼树的叶子，先选取2个最小的值作为叶子，生成一个根，可以得到最后的哈夫曼树，算一下就知道答案了。长度=6*4+7*4+13*3+16*2+18*2+30*2=219。22有向图如下所示，其中顶点A到顶点C的最短路径长度是_。答案： 35解析：由最短路径的算法，可以得出A-D-E-C是最短路径，路径长度为2+21+12=35。23对序列55，46，13，05，94，17，42进展基数排序，第一趟排序后的结果是_。答案： 42,13,94,55,05,46,17解析：从个位数开始排，就可以得到答案序列。24高度为3的3阶B-树最少的关键字总数是_。答案：7解析：B树的定义如下：一棵m阶的B-树满足如下条件： (1)树中每个结点至多有m个孩子； (2) 除根结点和叶子结点外，其它每个结点至少有m/2个孩子； (3)假如根结点不是叶子结点，如此至少有2个孩子； (4) 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息； (5) 有k个孩子的非终端结点恰好包含有k-1个关键字。解题思路：(1)根据树的性质可以知道根只有一个。Count=1.(2)根据性质(3),3阶B树的根不是叶子，至少有2个孩子。Count=1+2=3(3)根据性质(2)，可以知道第2层中的每个结点，每个结点至少有m/2个孩子，即2个孩子；所以第三层上有4个结点。Count=1+2+4=7个结点。且每个结点中只包含1个关键字。25VSAM通常作为大型索引顺序文件的标准组织，其动态索引结构采用的是_。三、解答题(本大题共4小题，每一小题5分，共20分)26假设二叉树的RNL遍历算法定义如下： 假如二叉树非空，如此依次执行如下操作：(1)遍历右子树； (2)访问根节点； (3)遍历左子树。一棵二叉树如下列图，请给出其RNL遍历的结果序列。答案：G,C,F,A,B,D。解析：根据定义，比拟容易得到该序列。实质上是前序序列的倒转。27一个无向图G=(V，E)，其中V=A，B，C，D，E，F，邻接矩阵表示如下所示。请回答如下问题：(1)请画出对应的图G。(2)画出图G的邻接表存储结构。答案：如下列图。ABDCEFA13 BCDEF023 1014 3 5 5 2 4 解析：通过矩阵中的1就可以知道哪个结点与哪个结点之间的连线。得到图之后，生成邻接表很容易的。28一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，请给出初始建堆后的序列。1612186015361418258512151418163618258560答案：序列为(12,15,14,18,16,36,18,60,25,85)。解析：如上图所示先构造出出示的完全二叉树，如左图所示，然后先从最后一个非叶子结点开始调整，结点顺序，一定要满足小根堆的性质，以此类推，调整完毕后如右图所示，就是小根堆，写出序列后就是了。29一棵二叉排序树如下列图。 请回答如下问题： (1)画出插入元素23后的树结构；(2)请画出在原图中删除元素57后的树结构。答案：(1)插入元素23后，二叉排序树变成如图中的左图所示。 (2)删除元素57后，二叉排序树变成如下列图的右图所示。4518577364966234518497366623解析：(1)新插入的结点一定是一个新添加的叶子节点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。2二叉排序的删除。分三种情况：假如被删除的结点p是叶子，如此直接删除就可以了。假如被删除的结点p不是叶子，但p只有左子树或右子树，如此将p的左子树或右子树直接修改为p的双亲的子树即可。假如被删除的结点p不是叶子，但p既有左子树，也有右子树，此时需用结点p的(中序)直接前驱或直接后继代替p，然后再从二叉排序树中删除p的直接前驱或直接后继。此题中的结点57既有左孩子又有右孩子，需找到它的直接前驱结点49。用49直接替代57。然后删除49即可。四、算法阅读题(本大题共4小题，每一小题5分，共20分)30如下程序，Ls指向带头结点的单链表。 Typedefstruct node DataType data; struct node * next; * LinkList; void f30( LinkList Ls ) LinkList p, q; q = Ls-next; if ( q & q-next ) Ls-next = q-next; p=q while ( p-next ) p = p-next; p-next = q; q-next = NULL;请回答如下问题：(1)当Ls指向的链表如如下图所示，请画出执行本函数之后的链表的结果。(2)请简述算法的功能。LS23451 答案：第一步的答案如上图所示。 第二步的答案如下：通过结果可以推出，该算法的功能是把第一个结点(开始结点)移动到链表的尾部。解析：根据程序可以很容易的得到如上图所示的结果。第二步的答案是非常明显的。31字符串处理函数f31程序如下。 int f31(char*strl，char*str2) while(*strl=*str2&(*strl!=0) strl+； str2+； return(*strl-*str2 ? l0)； 请回答如下问题： (1)假如调用语句是f31(abcde，abcdf)，如此函数的返回值是?假如调用语句是 f31(abcde，abcde)，如此函数的返回值是?(2)简述该函数的功能。答案：11 0 2判断字符串是否相等，如果相等返回0，否如此返回1。解析：程序比拟简单，关键是理解*str1的作用是？通过函数的参数可以得知str1和str2是分别指向字符串的指针，也就是保存字符串的数组的开始地址，程序中的*str1的功能是求某当前地址下的字符的值。因此，实参为f31(abcde，abcdf)时，要以此判断a=a成立，b=b成立，以此类推，只到e=f不成立完毕。循环完毕后，return(*strl-*str2 ? l0)；即return (e-f?1:0)，e-f不等于0表示条件成立，成立如此返回1。故f31(abcde，abcdf)返回1。f31(abcde，abcde)，循环条件完毕时，*str1的值为0,*str2的值也是0,所以return(*strl-*str2 ? l0)，即return(0-0?1:0)，0-0等于0，0表示不成立，不成立取第二个表达式的值0，所以f31(abcde，abcde)返回值为0。第二部答案：通过分析很容易得出。32数组A中存储有n个整数，请阅读如下程序。 void f32(intA，int n) inti，j，k，x； k=n-l；while(k0) i=k； k=0； for(j=O；jAj+1)x=Aj； Aj=Aj+l； Aj+1=x； k=j； endofif end ofwhile return； 请回答如下问题： (1)当A=10，8，2，4，6，7时，执行f32(A，6)后，数组A中存储的结果是? (2)说明该算法的功能。答案：(1)数组A中的结果2,4,6,7,8,10 (2)该算法的功能是对数组进展A中的前n个元素进展冒泡排序。解析：通过将数组A和6带入后，很容易分析出结果。33下面程序实现二分查找算法。 Typedef struct KeyType key； InfoType otherinfo； SeqListN+1； int BinSearch(SeqList R, int n，KeyType K) int low=1，high=n；while(1) mid=(1ow+high)2； if( (2) return mid； if(RmidkeyK) high=mid-1； else(3) ； return O； BinSearch 请在空白处填写适当内容，使该程序功能完整。 (1) (2) (3)答案：(1)lowlchild=NULL & T-rchild=NULL)/*递归完毕条件*/ count=1; return count; else /*else后面的代码是递归公式,分三种情况，具体见解析局部*/ if(T-lchild!=NULL & T-rchild=NULL) /*表示只有左子树*/ count=1+SumNodes(T-lchild); /*其中1表示根结点的数量*/ else if(T-lchild=NULL & T-rchild!=NULL) /*表示只有右子树*/ count=1+SumNodes(T-rchild); /*其中1表示根结点的数量*/ else if(T-lchild!=NULL & T-rchild!=NULL) /*既有左子树，又有右子树*/ count=1+SumNodes(T-lchild)+SumNode(T-rchild);解析：(一)函数定义中的头局部析。通过题目意思可以得到，我们要写一个函数，函数名为SumNodes()，里面有一个参数BiTree类型的T，该函数是有返回值的，返回值为树T的结点总数，返回值的类型为int，所以函数的类型也为int(因为返回值的类型就是函数的类型)。通过上面的分析可以定义如下：Int SumNodes(BiTree T) (二)函数定义中的函数体分析题目要求用递归算法，递归算法的关键点有2个：一个是递归完毕条件，一个是递归公式。(1)递归完毕条件，根据树的特点我们可以知道如果树T的某个结点，没有左孩子同时也没有右孩子，即该结点是叶子结点，叶子结点可以理解为一颗只有1个结点的树,我们可以确定该叶子结点组成的树只有1个结点。所以递归完毕条件为:if(T-lchild=NULL & T-rchild=NULL) count=1; return count; (2)递归公式，如果某结点不是叶子结点，不是叶子结点有三种情况，a.只有左孩子；b.只有右孩子；c.既有左孩子又有右孩子。a这种情况，可以确定1个结点，即根结点，其他的结点树需继续执行本函数，参数为左孩子的地址。b这种情况,可以确定1个结点，即根结点，其他的结点数需继续调用本函数，参数为右孩子的地址。c这种情况,可以确定一个结点，即根结点,其他的结点数需继续调用本函数，且需要调用2次本函数，参数分别为左孩子地址，右孩子地址。即递归公式为：if(T-lchild!=NULL & T-rchild=NULL) /*表示只有左子树*/ count=1+SumNodes(T-lchild); /*其中1表示根结点的数量*/ else if(T-lchild=NULL & T-rchild!=NULL) /*表示只有右子树*/ count=1+SumNodes(T-rchild); /*其中1表示根结点的数量*/ else if(T-lchild!=NULL & T-rchild!=NULL) /*既有左子树，又有右子树*/ count=1+SumNodes(T-lchild)+SumNode(T-rchild);