2005年上半年全国自考数据结构真题及答案.doc

更多优质自考资料尽在百度贴吧自考乐园俱乐部（/club/5346389）欢迎加入.欢迎交流.止不住的惊喜等着你.2005年上半年全国自考数据结构真题一、单项选择题（每小题2分，共30分）在每小题的四个备选答案中选出一个正确答案，并将其代码写在题干后面的括号内。不选、错选或多选者，该题无分。1.语句for(i=1；i=n；i+) x+;的时间复杂度为（）A.AB.BC.CD.D答案：B2.用单链表方式存储的线性表,存储每个结点需要两个域，一个是数据域，另一个是（）A.当前结点所在地址域B.指针域C.空指针域D.空闲域答案：B3.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d,则第i个结点的地址为（）A.d+(i-1)*mB.d+i*mC.d-i*mD.d+(i+1)*m答案：A4.在栈中存取数据的原则是（）A.后进先出B.先进先出C.后进后出D.随意进出答案：A5.设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为（）A.AB.BC.CD.D答案：A6.假设有如下的串说明：char s130=stocktom,ca,s230=march 5,1999,则调用函数strcmp（s1,s2）的返回值是（）A.等于零B.小于零C.大于零D.小于等于零答案：C7.下列广义表是线性表的为（）A.E=(a,(b,c)B.E=(a,E)C.E=(a,L);L=()D.E=(a,b)答案：D8.A.AB.BC.CD.D答案：D9.某二叉树前序遍历序列为IJKLMNO，中序遍历序列为JLKINMO，则后序遍历序列为（）A.JLKMNOIB.LKNJOMIC.LKJNOMID.LKNOJMI答案：C10.在一个图中，所有顶点的度数之和等于图的边数的（）倍。A.3B.1C.2D.4答案：C11.A.AB.BC.CD.D答案：D12.有8个顶点的无向图最多有（）条边。A.14B.28C.56D.112答案：B13.下列关键字序列中（）是堆。A.16，72，31，23，94，53B.94，23，31，72，16，53C.6，53，23，94，31，72D.16，23，53，31，94，72答案：D14.下列排序方法中最稳定的为（）A.冒泡排序B.直接选择排序C.希尔排序D.快速排序答案：A15.设有100个元素，用二分查找法进行查找时，最小比较次数是（）A.7B.1C.2D.4答案：B二、填空题（每小题2分，共20分）1.数据的逻辑结构有两大类，它们分别是_和_。答案：线性结构 非线性结构2.按顺序存储方法存储的线性表称为_，按链式存储方法存储的线性表称为_。答案：顺序表 链表3.在队列结构中，允许插入的一端称为_，允许删除的一端称为_。答案：队尾 队头4._称为空串；_称为空白串。答案：长度为零的串（或不包含任何字符的串） 由一个或多个空格组成的串5.对称矩阵按行优先存放于Sa0.n(n+1)/2-1中，元素aij与Sak的对应关系为k=_。答案：I(I+1)/2+J其中I=max(i,j)J=min(i,j)6.含有n个结点的二叉树用二叉链表表示时，有_个空链域。答案：n+17.具有n个叶结点的哈夫曼树共有_个结点。答案：2n-18.对有向图进行拓扑排序的方法有_和_。答案：无前趋的顶点优先 无后继的顶点优先9.含有n个记录的文件进行直接选择排序，其平均时间复杂度为_。答案：10.在线性表上进行查找的方法有顺序查找、_和_。答案：二分查找 分块查找三、简答题（每小题5分，共15分）1.简述什么是数据结构。答案：数据结构指的是数据之间的相互关系，即数据的组织形式。（3分）它包括数据的逻辑结构、数据的存储结构和数据的运算三个方面的内容。（5分）2.已知权值：4，2，5，7，5，请画出相应的哈夫曼树并计算其带权路径长度WPL。答案：WPL=（5+5+7）2+（2+4）3=34+18=52（2分）3.图G=（V，E），其中：V=0，1，2，3，4，5，E=0，1，0，2，1，4，2，5，5，44，3，5，3。试写出图G中顶点的所有拓扑排序。答案：所有的拓扑排序为：0 1 2 5 4 3（2分） 0 2 1 5 4 3（2分） 0 2 5 1 4 3（1分）四、求解下列问题（共15分）1.答案：2.试分别画出下图所示二叉树的前序、中序线索链表。（7分）答案：五、读程序填空题（8分）1.下面的算法是用直接选择排序法完成对文件中各个记录按关键字递增次序排序，请仔细阅读程序并把未完成的部分填上。Void selectsort(seqlist R)int i,j,k；for(i=1；in;i+)k=(_);for(j=i+1;j=n;j+)if(Rj.keyRk.key)k=(_);if(3)R0=Ri;Ri=(_);Rk=(_);答案：i（1分）j（2分）k!=i（5分）Rk（7分）R0（8分六、算法设计题（12分）1.设单链表的数据域是字符串，试写一算法将一已知字符串插入到带头结点的单链表中且不允许将重复的串插入表中。答案：#includestdio.h(1分)#define stringsize 10/*字符串最大长度，可更改*/（2分） typedef struct nodechar datastringsize;struct node*next; listnode;（4分）typedef listnode*linklist;(5分)void insertlist(linklist L,char s)更多优质自考资料尽在百度贴吧自考乐园俱乐部（/club/5346389）欢迎加入.欢迎交流.止不住的惊喜等着你.listnode*r,*q=L,*p=L-next;(6分)while(p&strcmp(p-data,s)!=0)q=p；p=p-next; if（p）printf（the inserted string has been in Ln）；（9分） else r=（listnode*）malloc(sizeof(