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

1、20121数据结构导论试题课程代码：02142一、单项选择题(本大题共 15 小题，每小题 2 分，共 30 分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。结点按逻辑关系依次排列形成一条锁链的数据结构是(B)集合C.树形结构下面算法程序段的时间复杂度为(C)for ( int i=0; im; i+) for ( int j=0; jnext=L。在双链表中，前趋指针和后继指针分别为prior 和 next。若使指针 p 往后移动两个结点，则需执行语句_P=P-next-next。注：1.向一个栈顶指针hs 的栈中插入一个*s 指

2、针，须执行的操作为；s-next=hs; hs=s;2.单列表中指针p 要删除其后面的A 结点（直接后继）需要执行的操作为：p-next=p-next-next（ 下一个下一个原则）s ，s ，s ，s 依次进入顺序栈 S，如果 6 个元素的退栈顺序为s ，s ，s ，s ，s ，s ，则顺序栈的容12345623651量至少为 _3。稀疏矩阵一般采用的压缩存储方法三元组。在一棵树中，根结点没有双亲。一棵具有 n 个结点的完全二叉树中，从树根起，自上而下、自左至右给所有结点编号。设根结点编号为1，若号为i 的结点有父结点，那么其父结点的编号为i/2。注：左孩子：为22i+1.二叉树的二叉链表存

3、储结构中判断指针p _（p-lchild=Null）&（p-rchild=Null） 。边稀疏的无向图采用邻接存储较省空间注：有向图采用邻接矩阵。序列中不能重复出现的路径叫简单路径。环。除第一个顶点和最后一个顶相同外，其余顶点不重复的回路，称为 _（简单）回路或（简单）。二分查找算法的时间复杂度是O（log2n）。28.要将序列51，18，23，68，94，70，73建成堆，则只需把18 与51相互交换。三、应用题5 6 30 分29.29 图所示的一棵二叉树转换成对应的森林。ACGBEFHJDIT1T2T3题 29 图给定权值，1，5，构造相应的哈夫曼（Huffma）（）由题可得哈夫曼树如下

4、：（2）带权路径长度为=2*（13+9+7）+3*（3+5）=82哈夫曼树构造过程：加。形成的新权值点与给定权值中的最小值在（相加小于这个权值点，那么是这两个小的权值先相加，形成另一个新的权值点，与其相加）层数*权值（i1+i2+）3722157891335注：下图为各种情况31 图的邻接矩阵和每个顶点的入度与出度。（）邻接矩阵为：ABCDEFA000100B000010C010000D001001E001101F000000（2）入度与出度：结点入度出度A结点入度出度A01B11C21D21E13F20注：1.邻接矩阵就是箭头指向的，没有指向的，或为逆箭头的，其元素为零。2.入度就是有几个箭

5、头指向圈，出度就是有几个键尾指向圈。202832 图中标出各结点的值。23解题要点：1.先确定最高分界点左面有几个圈，然后确定分界 点。如本题，分界点左面有3 2621202225282427圈，则20 21 22 23 24 25 26 27 28 -23为分界点孩子。孩子，注意左孩子连续减小原 则，右孩子连续增大原则。圈的之间差值最小原则。最左面的圈最小最大。题 32 图用冒泡排序法对数据序列（55，38，65，97，76，138，27，49）进行排序，写出排序过程中的各趟结果。答：初始关键字（55386597761382749）第一趟排序（38556576972749138）第二趟排序（

6、38556576274997138）第三趟排序（38556527497697138）第四趟排序（38552749657697138）第五趟排序（38274955657697138）第六趟排序（27384955657697138）四、算法设计题(本大题共 2 小题，每小题 7 分，共 14 分)设线性表A （a ，a ， ,a，B（b , b , ,b ，试写一个按下列规则合并AB为线性表C的算法，使得12m12nnC=（a1, b1, , am ,bm ,bm+1, ,b ） 当 mn 时；nm或者C=（a1, b1, , ,bn ,an+1, m） 当 mn 时。线性表和C 均以带头结点的单

7、链表作为存储结构，且C 表利用A 表和B 表中的结点空间构成（链表的长度值m n ）Status ListMerge_L(LinkList &A,LinkList &B,LinkList &C) LinkList pa,pb,qa,qb;pa=A-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);return OK; 二叉树的二叉链表类型定义如下：typedef struct btnode datatype data;struct btnode *lchild,*rchild; bitreptr;Void preorder(bitreptr*t)if (t!=NULL)visit(t);Perorder(t-lchild); Perorder(t-rchild);Void preorder(bitreptr*t)if (t!=NULL)visit(t);Perorder(t-lchild); Perorder(t-rchild);先根遍历void inorder(bitreptr*t) if (t!=NULL)Inorder(t-lch