2005级数据结构试题A卷

12005级数据结构试题A卷注：回答问题，请在答题卡上回答，不要回答在试题上。一、是非判断（回答’Y’或者’N’即可，不许多答、不许用其他符号替代24分）（1）线性表的逻辑顺序与物理顺序总是一致的。（2）线性表的顺序存储表示优于链式存储表示。（3）线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（4）二维数组是其数组元素为线性表的线性表。（5）每种数据结构都应具备三种基本运算：插入、删除和搜索。(6)二叉树必须有父结点、但不一定有左孩子结点或是右孩子结点。（7）用n个结点构造Huffman树，这个树有2n个结点。（8）有n个顶点的有向图，各个顶点完全连通则有n-1条边。（9）拓扑排序的有向图，要求图入度为0的顶点只能有一个。（10）在二叉排序树上查找，其效率总是高于顺序表上查找。（11）归并排序是稳定排序且时间复杂度为O(nLogn)。（12）Floyd最短路计算需要深度遍历图、且仅仅适合于有向图。二，选择判断（每个题目仅有一个答案30分）1．算法指的是A．计算机程序B．解决问题的计算方法C．排序算法D．解决问题的有限运算序列2．关于以下图问题的计算，使用深度编历算法的是：A．Dijkstra最短路B．拓扑排序C．关键路径计算D．Prim最小生成树3．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为A．O（1）B．O（n）C．O（m）D．O（m+n）4．哈希表查找中，填充因子和查找效率的关系是：A．填充因子越大、查找效率越好B．填充因子越小、查找效率越好C．填充因子要根据查找对象计算D．填充因子和查找效率没直接关系5．图的拓扑排序中，主要使用了哪种数据结构存储来暂存顶点?A．顺序表B．栈C．队列D．数组6．如下陈述中正确的是A．串是一种特殊的线性表B．串的长度必须大于零C．串中元素只能是字母D．空串就是空白串7．图的顶点个数是n，深度遍历该图，时间复杂度是：A．O（1）B．O（n）C．O（n2）D．O（n3）8、有数组charA[3][3][3]，按行存放于一个连续的存储空间中,如A[0][0][0]存储地址是2002（10进制），则它的数组元素A[1][1][2]在内存中的位置是：A．212B．211C．214D．2159．对一个单向链表，下列程序段中，p指针类型为：structNode{intX;structNode*next;}如p开始指向链表头结点，最后p一定指向尾结点的是：A．while(p!=NULL)p=p-next;B．while(p!=NULL)p++；C．while(p-next!=NULL)p++;D．while(p++-next!=NULL);10．索引文件通常由索引表和主文件两部分构成，其中A．索引表和主文件均必须是有序文件B．索引表和主文件均可以是无序文件C．索引表必须是有序文件D．主文件必须是有序文件11．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为A．eB．2*eC．n2－eD．n2－2*e12．假设一个有n个顶点和e条弧的有向图用邻接矩阵表示,则删除与某个顶点Vi相关的所有弧的时间复杂度是A．O(n)B．O(e)C．O(n+e)D．O(n*e)13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是A．选择排序B．希尔排序C．归并排序D．快速排序14．对n个不同值元素的集合，找到最大/最小元的算法，应该进行多少种比较?A．nB．n-1C．n2D．n2-115．下列排序方法中，属于不稳定的排序方法是A．直接插入排序法B．快速排序法C．冒泡排序法D．希尔排序法三、计算、简答题(28分)1有二叉树，先序遍历结果EBADCFHGIKJ，中序遍历结果为ABCDEFGHIJK，则后序遍历结果是什么？2有数字序列（40，28，16，56，50，32，30，63），按次序插入每个对象生成一棵AVL树，对该树插入完成后，给出该树的后序遍历结果。3无向图G深度遍历结果是一个2叉树，该先序遍历结果是ABDECFG、中序遍历结果是DBEAFCG。(1)请还原G的邻接矩阵。3(2)给出能满足上述遍历结果的有向图邻接矩阵。4希尔排序intA[]={49,38,65,97,76,13,27,49,55,4};分别使用增量5,3,1，写出过程5使用快速排序方法，完成{49,38,65,97,76,13,27,49}排序，写出过程。6有电文使用字母-频率表如下：字母ABCDEFGH频率719263232110求各字母的Huffman码四、算法分析、设计与编程(18)1有查找程序系统，查找表内容是字符A、B、C、D、E、F、G，原来按A-G的次序、按顺序表结构组织查找。经过运行一段时间后，统计得出以下查找规律：查找内容ABCDEFG查找概率0．220．180．200．050．250．020．08（1）请针对上述内容，修改查找表，以加快查找速度；（2）给出你的查找函数或者子程序（可以用C、VB6、C#中的任意一种语言描述）函数原型为：Char*Find(charKey)Key是’A’到’G’的任何一个字符，如果找到返回这个字符，如果没找到返回NULL（3）计算出100次查找中、你的函数对每个元素可能的对比次数，并和以前的表加以对照。2大规模数据排序，一直是一个很困难的事情，但今天计算机网络已经很普及了。一个排序的方法就是把需要排序的数据等份分配到一个网络中的各个计算机上去，让网络中的每个计算机都参与到排序工作中来。现有2G个整数数据需要排序，它们都是值为0到10000的整数构成的数据，现有一个200台计算机的网络，每个计算机都分配有10M(10485760)个数据。问题如下：（1）每一台计算机应该使用方面方法排序？（仅回答方法即可）（2）网络中每个计算机排序的结果，都通过网络传到一台性能很好的服务器上，并存储在A1[]、A2[]、A3[]…A200[]数组中。服务器上用什么方法，可以让这200个有序序列、合并成为一个完整的有序结果？写出能合并两个数组的程序函数（可以用C、VB6、C#中的任意一种语言描述）。3，二叉树复制，树结构如下：structBiTree{intE;structBiTree*lchild,*rChild;};函数名称及类型：voidBiTreeCopy(structBitTree*S，structBitTree*T)将S树复制到T树.42005级数据结构试题A卷答题卡姓名：学号：成绩：一、是非判断（回答’Y’或者’N’即可，不许多答、不许用其他符号替代，24分）123456789101112二，选择判断（每个题目仅有一个答案，30分）123456789101112131415三、计算、简答题(28分)123（1）3（2）456ABCDEFGH5四、算法分析、设计与编程(18)1（6分）（1）（2）（3）2（6分）(1)(2)63（6分）(该题目如使用VB、C#做答，请添加必要的类)72005级数据结构试题A卷答案及评分标准一、是非判断（回答’Y’或者’N’即可，不许多答、不许用其他符号替代，24分）1N2N3N4Y5Y6N7N8N9N10N11Y12N二，选择判断（每个题目仅有一个答案，30分）1D2C3A4B5B6A7C8C9A10C11D12D13C14B15D三、计算、简答题(28分)1ACDBGJKIHFE216,30,32,28,50,63,56,403（1）01100001001100100001100000000000000000000000000003（2）0110000000110000000110000000000000000000000000000449,38,65,97,76,13,27,49,55,413,27,49,55,4,49,38,65,97,7813,4,49,38,27,49,55,65,97,764,13,27,38,49,49,55,65,76,97549,38,65,97,76,13,27,4927,38,13,49,65,97,76,4913,27,38,49,49,65,76,976ABCDEFGH1010001000010011110001011011注：6题的Huffman码可能01表达不一致，但码长确定不变。8四、算法分析、设计与编程(18)1（6分）（1）依然是顺序表，次序重新排列即可，原则是概率大的放前面：E，A，C，B，D，G，F（2）char*Find(charKey){chartable[]={‘E’，’A’，’C’，’B’，’G’，’D’，’F’};char*p;inti,n=7;p=table;i=0;while(*p!=Key&&in)p++;if(i==n)returnNULL;returnp;}（3）E:100*0.25*1A:100*0.22*2C:100*0.20*3B:100*0.18*4G:100*0.08*5D:100*0.05*6F:100*0.02*7共计：285不调整的是100*(n+1)/2，就是400次。2（6分）(1)基数排序(2)该问题本质是归并排序的核心：两个有序表的归并。//这个规模的数据量，位置变量全部应该是longvoidMerge(inta[],longaLength,intb[],longbLength,intc[]){longi,j,k;i=0;j=0;k=0;for(k=0;kaLength+bLength;k++){if(i=aLength){c[k]=b[j++];continue;}if(j=bLength){c[k]=a[i++];continue;}c[k]=(a[i]b[j])?a[i++]:b[j++];}}93（6分）(该题目如使用VB、C#做答，请添加必要的类)voidBiTreeCopy(structBitTree*S，structBitTree*T){structBitTree*pt;If(S==NULL){Pt=NULL;return;}If(S-lChild!=NULL){pt=(structBitTree*)malloc(sizeof(structBitTree));pt-E=S-E;pt-lChild=NULL;pt-rChild=NULL;T-lChild=pt;}BiTreeEqual(S-lChild,pt);If(S-rChild!=NULL){pt=(structBitTree*)malloc(sizeof(structBitTree));pt-E=S-E;pt-lChild=NULL;pt-rChild=NULL;T-rChild=pt;}BiTreeEqual(S-rChild,pt);}102005级地信专业《数据结构》试卷说明1、试题来源以及参考资料2003级的《数据结构》期末试卷，内容主要来自历年中央电视大学自考《数据结构》、《数据结构题集C语言版》（严蔚敏吴伟民编著），自遍程序设计部分试题。2范围考试范围包括线形表、链表、树、图和排序。3、难度同中央广播电视大学计算机专业数据结构自考试题相比，选择题难度大致相同。程序设计试题难度大于国家自考试题。4、试题类型试题形式有两种：选择题和填空题，所以答案基本是唯一的，这类试题参考答案与学生实际答案对比，试题评卷中不存在主观判卷问题。程序设计试题总分达24分，考生实际答题与标准答案可能有出入，这类试题判分要根据实际情况。5、试题数量试题数量为12个选择题，22个填充点，3个算法程序设计题。6、试题得分点分布试题各得分点，12个选择题每题2分、15个填充点每题2分，计算、简答28分，程序设计18分。112005级地信专业《数据结构》考试成绩分析1、期末总评成绩分析平