全国2010年1月自考数据结构导论考试试题-答案-笔记.doc

全国2010年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.下述文件中适合于磁带存储的是（ A ）A.顺序文件B.索引文件C.散列文件D.多关键字文件2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（ D ）A.acbedB.becabC.deabcD.cedba3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( C )A.n-1B.nC.n+1D.n+2 注：子域为2n个，有n-1个孩子。4.在一个图中，所有顶点的度数之和与图的边数的比是( C )A.12B.11C.21D.415.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( A )A.O(1)B.O(1og2n) 二分法 注：若只有尾指针，那么入和出都为O(1)C.O(n) （入队）D.O(n2) -冒泡6.下述几种排序方法中，要求内存量最大的是( C )A.插入排序B.快速排序C.归并排序D.选择排序7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( D )A.n-1B.nC.n+1D.n(n-1)28.对线性表进行二分查找时，要求线性表必须( C )A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( B )A.O(1)B.O(n) 注：在双向循环链表中，删除最后一个结点C.O(nlog2n)D.O(n2) 的时间复杂度为O(1)10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( B )A.n-2B.n-1C.nD.n+111.有关插入排序的叙述，错误的是( C )A.插入排序在最坏情况下需要O(n2)时间B.插入排序在最佳情况可在O(n)时间内完成C.插入排序平均需要O(nlog2n)时间 -快速排序需要o（nlog2n） 树：是n各节点的有限集合。1. 当n=0时，称为空树。2. 当n0时，有且仅有一个根的结点。D.插入排序的空间复杂度为O(1)12.有关树的叙述正确的是( C )A.每一个内部结点至少有一个兄弟B.每一个叶结点均有父结点C.有的树没有子树D.每个树至少有一个根结点与一个叶结点。(有且仅有一个结点)13.循环队列存储在数组元素A0至Am中，则入队时的操作为( D )A.rear=rear+1B.rear=(rear+1)(m-1)C.rear=(rear+1)mD.rear=(rear+1)(m+1)14.关于串的的叙述，不正确的是( B )A.串是字符的有限序列B.空串是由空格构成的串 注：空格串是只包括空格的串，空格串是有长度的，而空串没有长度。C.替换是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储15.对称矩阵ANN，A11为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T1至TN(N+1)2中，则任一上三角元素Aij存于Tk中，下标k为( B )A .i (i-1)2+jB. j(j-1)2+iC .i (j-i)2+1D. j(i-1)2+l 二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。错填、不填均无分。16.下列程序段的时间复杂度为_O(n3)_。for(i=1；i=n；i+)for(j=1；j=n；j+)for(k=1；k -,3 exit -3, 此时，剩下 -。 对应着，把里已输入的 3，删掉。然后把标明已产生排序，然 Push(-)push(3)pop(3) 后以此类推。 注：退的时候，从后往前划。30.已知一棵二叉树的先根遍历序列为ABCDEGHF，中根遍历序列为CBEDAGFH，画出该二叉树。答：由题可知，该二叉树为： 解题要点：1.先确定最高分界点左面有几个圈，然后确定分界点。如本题，分界点左面有4个圈，则32 33 34 35 36 37 38 39 4036为分界点2.以根节点为界，左孩子小于又孩子。3.若出现连续左孩子，或连续又孩子，注意左孩子连续减小原则，又孩子连续增大原则。4.圈的之间差值最小原则。31.题31图中二叉排序树的各结点的值为3240，标出各结点的值。40363240353733383439题31图32.下述矩阵表示一个无向网，画出该无向网，并构造出其最小生成树。答：1连通图为：0 0 1 2 3 4 50123453651125532644560解题思路：1.画连通图时的一个技巧是，数字基本按顺序写，0为最高端。然后根据下标找出路线即可。 2.最小生成树和最优路径选着法一样，记住两点之间只有一条线连接。注意：一个点出去的最短不代表到下一个点最短，要把两条路径加起来比较一下。2.最小生成树为：131253235433.什么是堆?写出对应于序列(10，20，7，75，41，67，3，9，30，45)的初始堆(堆顶元素取最小值)。答：1堆是一键值序列k1,k2,kn,对所有i=1,2,3 n/2 满足kik2i解题思路：1. 先将给出的序列以完全二叉树依次写出。2. 然后从最右边的看起，若要求最小根，那么找小的作为根。若要求最大根，那么找最大的作为根。3. 总之，求最大根，从总根开始，结点根依次减小，求最小根，结点根逐渐减大。4. 调整位置即可。3 Kik2i+1由题意可以得出如下初始堆972010674133075四、算法设计题(本大题共2小题，每小题7分，共14分)34.二叉树按二叉链表形式存储，编写一个算法判别给定的二叉树是否为完全二叉树。Int Judgecomplete(Bitree bt) /判断是否是二叉树，是返回1，否返回0Int tag=0,Bitree p=bt,Q; /Q是队列，元素是二叉树的结点指针，容量足够大If (p=null) return (1); QueueInit(Q),Queuelint(Q,p); /初始化队列，根节点入队 While (!QueueEmpty(Q) p=QueueOut(Q); /出队 If（p-lchild&!tag）QueneIn(Q,p-lchild) /左孩子入队Else if (p-lchild) return 0; /前面已有节点为空，此结点不为空 Else tag=1; /首次出现结点为空 If (p-right&!tag) QueneIn(Q,p-rchild) /又孩子入队Elseif (p-rchild) return 0; Else tag=1;/while return 1 ;/JudgeComplete35.试写出直接插入排序算法。Void StraightInseartSort (list r, int n)/对顺序表直接进行插入排序 int i , j; For (i=2,i=n,i+) /n为表长，从第二个记录起进行插入。 R0=Ri; /第i个值赋值为岗哨j=i-1； while(R0.keyRj.key) /与岗哨比较，直至键值不大于岗哨值Rj+1=Rj; /将第J个值赋给第J+1个值 j-; Rj+1=R0; /将第i个值插入到系列中 （注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）