2004年上半年全国高等教育自学考试试题-数据结构

1、2004年上半年全国高等教育自学考试试题一、单项选择题（每小题2分，共30分）在每小题的四个备选答案中选出一个正确答案，并将其代码写在题干后面的括号内。不选、错选或多选者，该题无分。1数据结构研究的是数据的（ ）及它们之间的相互关系。 A存储结构和逻辑结构 B存储和抽象 C理想与抽象 D理想与逻辑2算法分析的两个主要方面是 （ ） A空间复杂度和时间复杂度 B正确性和简明性 C可读性和文档性 D数据复杂性和程序复杂性3线性表若采用链式存储结构时，要求内存中可用存储单元的地址 （ ） A必须是连续的 B部分地址必须是连续的 C一定是不连续的 D连续不连续都可以4在队列中存取数据的原则是 （ ）

2、A后进先出 B先进先出 C后进后出 D随意进出5在栈中，出栈操作的时间复杂度为 （ ） AO() BO(1) CO(n) DO()6假设有如下的串说明： （ ） char s130=”stocktom,ca”,s230=”march,5,1999”,则调用函数strlen(strcat(s1,s2)的返回值是 （ ） A11 B12 C23 D257广义表（a）,a）的表头为 （ ） Aa B(a),) C(a) D(a)8深度为5的二叉树至多有多少个结点 （ ） A16 B32 C10 D319某二叉树前序遍历序列为IJKLMNO，中序遍历序列为JLKINMO，则后序遍历序列为（ ） AJL

3、KMNOI BLKNJMNO CLKJNOMI DLKNOJMI10在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ ）条边。 An-1 Bn Cn+1 Dn/211已知下图，若从顶点a出发按深度优先遍历算法进行遍历，则可以得到的顶点遍历序列是 （ ）bdacfe Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b12有8个顶点的有向图最多有（ ）条边。 A14 B28 C56 D11213下列关键字序列中（ ）是堆。 A16，72，31，23，94，53 B94，23，31，72，16，53C16，53，23，94，31，72 D16

4、，23，53，31，94，7214下列排序方法中不稳定的为 （ ）A冒泡排序 B直接选择排序C直接插入 D归并排序15设有100个元素，用二分查找法进行查找时，最小比较次数是 （ ） A7 B1 C2 D4二、填空题（每小题2分，共20分）1下面程序段的时间复杂度是_; for(i=1;i=n;i+) for(j=1;j=m;j+) ai,j=0;2在长度为n的顺序表的第i (1in+1)个位置之前插入一个新结点时，需向后移动_个结点。3一个栈的输入序列是12345，则栈的输出序列能否是12345_。4设目标串为T=“abccdcdccbaa”,模式串为P=“cdcc”,则第_次匹配成功。5对

5、称矩阵按行优先存放于Sa0n(n+1)/2-1中，元素与Sak的对应关系为k=_。6将一棵树转换成一棵二叉树,二叉树的根结点没有_子树。7编码00,01,10,11是不是前缀码_。8对有向图进行拓扑排序的方法有_和_。9在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时,当把第7个记录60插入到有序区时,为寻找插入位置比较_次。10设线性表的长度为n,则顺序查找法的平均查找长度为_。三、简答题(每小题5分,共15分)1简述数据的存储结构中四种常用的存储方法。2试分别画出稀疏矩阵转置前后的三元组表。3已知权值：4，2，5，7，5。请画出相应的哈夫曼树并计算其带

6、权路径长度WPL。四、求解下列问题（共15分）1 试画出用克鲁斯卡尔（Kruskal）算法构造下图最小生成树的过程(8分) 。2试分别画出下图所示二叉树的前序,中序线索链表(7分)。34514325五、读程序填空题（8分） 下面的算法是用冒泡排序法完成对文件中各个记录按关键字递增次序排序，请仔细阅读程序并把未完成的部分填上。 Void bubblesort (seqlist R) int i,j; Boolean exchange ; for (i=1;i=I; (1) ) if(Rj+1.keyRj.key) R0=Rj+1; Rj+1= (2); (3) =R0;exchange=true

7、; if(!exchange) (4) ; 六、算法设计题(12分)设单链表的数据域是字符串,试写一算法将一字符串从单链表中删除。参考答案及评分标准一、单项选择题（每小题2分，共30分）1A 2A 3D 4B 5B 6C 7C 8D 9C 10A 11D 12C 13D 14B 15B二、填空题(每小题2分,共20分)1O(n*n) 2n-i+1 3可以 465k=I(I+1)/2+J 其中I=max(i,j) J=min(i,j) 6右7是 8无前趋的顶点优先,无后继的顶点优先 9310(n+1)/2三、简答题(每小题5分,共15分)1答：顺序存储方法：把逻辑上的相邻的结点存储在物理位置相邻

8、的存储单元里,这样结点间的逻辑关系由存储单元的邻接关系来体现。（2分） 链接存储方法：除存储结点外，还要由附加的指针字段来表示结点间的逻辑关系。（3分） 索引存储方法：在存储结点的同时，还建立附加的索引表。（4分） 散列存储方法：根据结点的关键字直接计算出该结点的存储地址。（5分）2解：转置前： 转置后： 0 2 2 1 1 3 2 2 -1 3 3 1 1 1 3 2 0 2 2 2 -1 3 3 1 （3分） （5分）3答：WPL=（5+5+7）2+（2+4）3=34+18=52 （2分）235101365247 （5分）四、求解下列问题（共15分）解： （2分） （3分）（5分） （7分

9、） （8分）注：最后一步除可选边（1，2）外，也可以选边（2，4），这说明最小生成树不是唯一的。2解：前序、中序线索链表分别为（虚线代表线索）： 0 1 1 1 2 0 0 3 1 1 4 0 1 5 1 （4分） 0 1 1 1 2 0 0 3 1 1 4 0 1 5 1 （7分）五、读程序填空题（8分）解：(1) j - - (2分) (2) Rj (4分) (3) Rj (6分)(4) return (8分)六、算法设计题（12分）解：算法为： # include (1分) # define stringsize 10 /*字符串最大长度,可更改 */ (2分) typedef struct node char datastringsize; struct node *next; listnode; (4分) typedef listnode *linklist; (5分) void deletelist(linklist L,char s) listnode *q=L,*p=L-n