全国2010年1月高等教育自学考试数据结构试题及参考答案

═════════════════════════════════════════════════════════════════════════════════-本套试题共分7页，当前页是第1页-全国2010年1月高等教育自学考试数据结构试题及参考答案课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．若一个算法的时间复杂度用T(n)表示，其中n的含义是（A）A．问题规模B．语句条数C．循环层数D．函数数量2．具有线性结构的数据结构是（C）A．树B．图C．栈和队列D．广义表3．将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（B）A．O(1)B．O(m)C．O(n)D．O(m+n)4．在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（C）A．2个B．3个C．4个D．6个5．假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（B）A．3B．37C．50D．976．若栈采用链式存储结构，则下列说法中正确的是（B）A．需要判断栈满且需要判断栈空B．不需要判断栈满但需要判断栈空C．需要判断栈满但不需要判断栈空D．不需要判断栈满也不需要判断栈空7．若串str=”Software”，其子串的数目是（D）A．8B．9C．36D．378．设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为（C）A．1012B．1017═════════════════════════════════════════════════════════════════════════════════-本套试题共分7页，当前页是第2页-C．1032D．10399．允许结点共享的广义表称为（D）A．纯表B．线性表C．递归表D．再入表10．下列数据结构中，不属于二叉树的是（A）A．B树B．AVL树C．二叉排序树D．哈夫曼树11．对下面有向图给出了四种可能的拓扑序列，其中错误．．的是（C）A．1，5，2，6，3，4B．1，5，6，2，3，4C．5，1，6，3，4，2D．5，1，2，6，4，312．以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（D）A．v1，v2，v3，v4，v5，v6，v7B．v1，v2，v5，v4，v3，v7，v6C．v1，v2，v3，v4，v7，v5，v6D．v1，v2，v5，v6，v7，v3，v413．下列排序算法中不稳定的是（A）A．快速排序B．归并排序C．冒泡排序D．直接插入排序14．一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值32时，查找成功需要的比较次数是（B）A．2B．3C．4D．815．采用ISAM组织文件的方式属于（D）A．链组织B．顺序组织C．散列组织D．索引组织═════════════════════════════════════════════════════════════════════════════════-本套试题共分7页，当前页是第3页-二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。错填、不填均无分。16．数据元素及其关系在计算机存储器内的表示称为__存储结构_______。17．长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是___O（n）______。18．下面是在顺序栈上实现的一个栈基本操作，该操作的功能是_________。typedefstruct{DataTypedata[100]；inttop；}SeqStack；DataTypef18(SeqStack*S){if(StackEmpty(S))Error(”Stackisempty”)；returnS-data[S-top]；}19．在串匹配中，一般将主串称为目标串，将子串称为___模式串______。20．已知广义表C=(a(b，c)，d)，则：tail(head(tail(C)))=___()______。21．用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为___221______。22．已知有向图如下所示，其中顶点A到顶点C的最短路径长度是___35______。23．对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是_10,42,12,94,55,01,46,17。24．高度为3的3阶B-树最少的关键字总数是__13_______。25．VSAM通常作为大型索引顺序文件的标准组织，其动态索引结构采用的是___B+______。三、解答题(本大题共4小题，每小题5分，共20分)26．假设二叉树的RNL遍历算法定义如下：若二叉树非空，则依次执行如下操作：(1)遍历右子树；(2)访问根节点；═════════════════════════════════════════════════════════════════════════════════-本套试题共分7页，当前页是第4页-(3)遍历左子树。已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。GCFABDC27．已知一个无向图G=(V，E)，其中V={A，B，C，D，E，F}，邻接矩阵表示如下所示。请回答下列问题：(1)请画出对应的图G。(2)画出图G的邻接表存储结构。28．已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，请给出初始建堆后的序列。29．已知一棵二叉排序树如图所示。请回答下列问题：(1)画出插入元素23后的树结构；(2)请画出在原图中删除元素57后的树结构。四、算法阅读题(本大题共4小题，每小题5分，共20分)30．已知下列程序，Ls指向带头结点的单链表。Typedefstructnode{DataTypedata;structnode*next;}*LinkList;voidf30(LinkListLs){LinkListp,q;q=Ls-next;if(q&&q-next){Ls-next=q-next;p=q═════════════════════════════════════════════════════════════════════════════════-本套试题共分7页，当前页是第5页-while(p-next)p=p-next;p-next=q;q-next=NULL;}}请回答下列问题：(1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。(2)请简述算法的功能。31．已知字符串处理函数f31程序如下。intf31(char*strl，char*str2){while(*strl==*str2&&(*strl!=’＼0’)){strl++；str2++；}return(*strl-*str2?l∶0)；}请回答下列问题：(1)若调用语句是f31(”abcde”，”abcdf’)，则函数的返回值是什么?若调用语句是f31(”abcde”，”abcde”)，则函数的返回值是什么?(2)简述该函数的功能。32．数组A[]中存储有n个整数，请阅读下列程序。voidf32(intA[]，intn){inti，j，k，x；k=n-l；while(k0){i=k；k=0；for(j=O；ji；j++)if(A[j]A[j+1]){x=A[j]；A[j]=A[j+l]；A[j+1]=x；k=j；═════════════════════════════════════════════════════════════════════════════════-本套试题共分7页，当前页是第6页-}／／endofif}／／endofwhilereturn；}请回答下列问题：(1)当A[]={10，8，2，4，6，7}时，执行f32(A，6)后，数组A中存储的结果是什么?(2)说明该算法的功能。33．下面程序实现二分查找算法。Typedefstruct{KeyTypekey；InfoTypeotherinfo；}SeqList[N+1]；intBinSearch(SeqListR,intn，KeyTypeK){intlow=1，high=n；while((1)){mid=(1ow+high)／2；if((2))returnmid；if(R[mid]．keyK)high=mid-1；else(3)；}returnO；}／／BinSearch请在空白处填写适当内容，使该程序功能完整。(1)(2)(3)五、算法设计题(本题10分)34．已知二叉树采用二叉链表存储，其结点结构定义如下：typedefstructNode{ElmTypedata；═════════════════════════════════════════════════════════════════════════════════-本套试题共分7页，当前页是第7页-structNode*lchild，*rchild；}*BiTree；请编写递归函数SumNodes(BiTreeT)，返回二叉树T的结点总数。