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

全国2012年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( B )A.集合 B.线性结构 C.树形结构 D.图状结构 （任意两个结点可以邻接的结构）2.下面算法程序段的时间复杂度为( C )for ( int i=0; im; i+)for ( int j=0; jnext=L_。19.在双链表中，前趋指针和后继指针分别为prior和next。若使指针p往后移动两个结点，则需执行语句 _P=P-next-next_。注：1.向一个栈顶指针hs的栈中插入一个*s指针，须执行的操作为；s-next=hs; hs=s;2.单列表中指针p要删除其后面的A结点（直接后继）需要执行的操作为：p-next=p-next-next （ 下一个下一个原则）20.元素s1，s2，s3，s4，s5，s6依次进入顺序栈S，如果6个元素的退栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为 _3_。21. 稀疏矩阵一般采用的压缩存储方法是_三元组表_ 。22. 在一棵树中，_根_ 结点没有双亲。23.一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右给所有结点编号。设根结点编号为1，若编号为i的结点有父结点，那么其父结点的编号为 _i/2 _。 注：左孩子：为2i，右孩子为2i+1.1. 序列中不能重复出现的路径叫简单路径。2. 第一个顶点和最后一个顶点相同的路径称为回路或环。24.二叉树的二叉链表存储结构中判断指针p所指结点为叶子结点的条件是_（p-lchild=Null）&（p-rchild=Null）_。25.边稀疏的无向图采用 _邻接表_存储较省空间。注：有向图采用邻接矩阵。26.除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为 _（简单）回路或（简单）环_。27.二分查找算法的时间复杂度是 _O（log2n）_。28.要将序列51，18，23，68，94，70，73建成堆，则只需把18与 _51_相互交换。三、应用题(本大题共5小题，每小题6分，共30分)29.将题29图所示的一棵二叉树转换成对应的森林。GHCAIJHFEDB T1 T2 T3题29图30.给定权值3，9，13，5，7，构造相应的哈夫曼（Huffman）树，并计算其带权路径长度。答：（1）由题可得哈夫曼树如下：（2）带权路径长度为=2*（13+9+7）+3*（3+5）=8237哈夫曼树构造过程：1 先从给定权值表中找出最小的两个数字相加。2 形成的新权值点与给定权值中的最小值在相加，形成权值。（注意，若表中有两个数相加小于这个权值点，那么是这两个小的权值先相加，形成另一个新的权值点，与其相加）3 权值路径相加是不包括结点的。其公式为：层数*权值（i1+i2+）9158H5H227133H注：下图为各种情况31.写出题31图的邻接矩阵和每个顶点的入度与出度。答：（1）邻接矩阵为：ABCDEFA000100B000010C010000D001001E001101F000000 （2）入度与出度：结点入度出度A01B11C21D21E13F20注：1.邻接矩阵就是箭头指向的，没有指向的，或为逆箭头的，其元素为零。 2.入度就是有几个箭头指向圈，出度就是有几个键尾指向圈。题31图32. 二叉排序树的各结点的值依次为2028，请在题32图中标出各结点的值。解题要点：1.先确定最高分界点左面有几个圈，然后确定分界点。如本题，分界点左面有3个圈，则20 21 22 23 24 25 26 27 28 -23为分界点2.以根节点为界，左孩子小于右孩子。3.若出现连续左孩子，或连续又孩子，注意左孩子连续减小原则，右孩子连续增大原则。4.圈的之间差值最小原则。5.最左面的圈最小，最右面的圈最大。262324252728222021题32图33.用冒泡排序法对数据序列（55，38，65，97，76，138，27，49）进行排序，写出排序过程中的各趟结果。 答：初始关键字（55 38 65 97 76 138 27 49） 第一趟排序（38 55 65 76 97 27 49 138） 第二趟排序（38 55 65 76 27 49 97 138） 第三趟排序（38 55 65 27 49 76 97 138） 第四趟排序（38 55 27 49 65 76 97 138） 第五趟排序（38 27 49 55 65 76 97 138） 第六趟排序（27 38 49 55 65 76 97 138）四、算法设计题(本大题共2小题，每小题7分，共14分)34.设线性表A =（a1， a2， ,am），B=（b1, b2, ,bn），试写一个按下列规则合并A，B为线性表C的算法，使得C=（a1, b1, , am ,bm ,bm+1, ,bn） 当mn时；或者 C=（a1, b1, , an ,bn ,an+1, ,am） 当mn时。线性表A，B和C均以带头结点的单链表作为存储结构，且C表利用A表和B表中的结点空间构成。（注意：单链表的长度值m和n均未显式存储。）StatusListMerge_L(LinkList&A,LinkList&B,LinkList&C)LinkListpa,pb,qa,qb;pa=A-next;pb=B-next;C=A;while(pa&pb)qa=pa;qb=pb;pa=pa-next;pb=pb-next;qb-next=qa-next;qa-next=qb; if(!pa)qb-next=pb;pb=B;free(pb);returnOK;35. 二叉树的二叉链表类型定义如下：typedef struct btnode datatype data; struct btnode *lchild,*rchild; bitreptr;写出后根遍历根指针为t的二叉树的递归算法( void postorder (bitreptr *t) )。Void preorder(bitreptr*t)if (t!=NULL) visit(t); Perorder(t-lchild); Perorder(t-rchild); 先根遍历void inorder(bitreptr*t) if (t!=N