全国2012年1月自考数据结构导论考试试题,答案,笔记
- 格式：doc
- 大小：289.00 KB
- 文档页数：6
全国2012年1月高等教育自学考试 数据结构导论试题 课程代码：02142
一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( B ) A.集合 B.线性结构 C.树形结构 D.图状结构 （任意两个结点可以邻接的结构） 2.下面算法程序段的时间复杂度为( C ) for ( int i=0; ifor ( int j=0; ja［i］［j］=i*j; A. O(m2) B. O(n2) C. O(mn) D. O(m+n) 3.线性结构是( A ) A.具有n（n≥0）个表元素的有穷序列 B.具有n（n≥0）个字符的有穷序列 C.具有n（n≥0）个结点的有穷序列 D.具有n（n≥0）个数据项的有穷序列 4.单链表中删除由某个指针变量指向的结点的直接后继，该算法的时间复杂度是( D ) A. O(1) B. O(n) C. O(log2n) D. O(n) 5.关于串的叙述，正确的是( D ) A.串是含有一个或多个字符的有穷序列 B.空串是只含有空格字符的串 C.空串是含有零个字符或含有空格字符的串 注：空串不等于空格串 D.串是含有零个或多个字符的有穷序列 6.栈的输入序列依次为1，2，3，4，则不可能的出栈序列是( D ) A.1243 B. 1432 C. 2134 D.4312 (不符合后进先出原则) 7.队列是( A ) A. 先进先出的线性表 B. 先进后出的线性表 （栈） C. 后进先出的线性表 D.随意进出的线性表
注：1.插入与删除运算，顺序表与线性表的时间复杂度都为O（n）。 2.查找运算，顺序表的时间复杂度为O（1） 单列表的时间复杂度为O（n） 8.10阶上三角矩阵压缩存储时需存储的元素个数为( B ) A.11 B.56 C.100 D.101 9.深度为k（k≥1）的二叉树，结点数最多有( B ) A.2k 个 B.(2k -1)个 C.2k-1个 D.(2k+1)个 10.具有12个结点的二叉树的二叉链表存储结构中，空链域NULL的个数为( B ) A. 11 B.13 注：孩子有n-1个，空子域有n+1个，指针域有2n个。 C. 23 D. 25 11.具有n个顶点的无向图的边数最多为( C ) A.n+1 B.n(n+1) C.n(n-1)/2 D.2n(n+1)
12.三个顶点v1,v2,v3的图的邻接矩阵为010001010，该图中顶点v3的入度为( B )
A. 0 B. 1 C. 2 D. 3 13.顺序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字值不相同。用顺序查找法查找时，平均比较次数约为( B ) A.20000 B.30000 C.40000 D.60000 14.外存储器的主要特点是( B ) A.容量小和存取速度低 B.容量大和存取速度低 C.容量大和存取速度高 D.容量小和存取速度高 15.在待排数据基本有序的前提下，效率最高的排序算法是( A ) A.直接插入排序 B.直接选择排序 C.快速排序 D.归并排序 二、填空题(本大题共13小题，每小题2分，共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.数据的不可分割的最小标识单位是__数据项____，它通常不具有完整确定的实际意义，或不被当作一个整体对待。 17.运算分为加工型运算和引用型运算，读取操作是__引用____ 运算。 18.带有头结点的单向循环链表L（L为头指针）中，指针p所指结点为尾结点的条件是 _p->next=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. 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图所示的一棵二叉树转换成对应的森林。
T1 T2 T3 题29图 30.给定权值｛3，9，13，5，7｝，构造相应的哈夫曼（Huffman）树，并计算其带权路径长度。 答：（1）由题可得哈夫曼树如下：
A B D E C GH J F I
35813 15 9 22 7
37 （2）带权路径长度为=2*（13+9+7）+3*（3+5）=82 哈夫曼树构造过程： 1． 先从给定权值表中找出最小的两个数字相加。 2． 形成的新权值点与给定权值中的最小值在相加，形成权值。（注意，若表中有两个数相加小于这个权值点，那么是这两个小的权值先相加，形成另一个新的权值点，与其相加） 3． 权值路径相加是不包括结点的。其公式为：∑层数*权值（i1+i2+…）
1. 序列中不能重复出现的路径叫简单路径。 2. 第一个顶点和最后一个顶点相同的路径称为回路或环。 31.写出题31图的邻接矩阵和每个顶点的入度与出度。 题31图
注：下图为各种情况 答：（1）邻接矩阵为： A B C D E F A 0 0 0 1 0 0 B 0 0 0 0 1 0 C 0 1 0 0 0 0 D 0 0 1 0 0 1 E 0 0 1 1 0 1 F 0 0 0 0 0 0 （2）入度与出度： 结点 入度 出度 A 0 1 B 1 1 C 2 1 D 2 1 E 1 3 F 2 0
注：1.邻接矩阵就是箭头指向的，没有指向的，或为逆箭头的，其元素为零。 2.入度就是有几个箭头指向圈，出度就是有几个键尾指向圈。 32. 二叉排序树的各结点的值依次为20~28，请在题32图中标出各结点的值。 题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） 当m≤n时； 或者 C=（a1, b1, …, an ,bn ,an+1, …,am） 当m>n时。 线性表A，B和C均以带头结点的单链表作为存储结构，且C表利用A表和B表中的结点空间构成。（注意：单链表的长度值m和n均未显式存储。） Status ListMerge_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb; pa=A->next; pb=B->next; C=A; while(pa&&pb) { qa=pa;qb=pb;
23 21 26
20 22 25 28 24 27
解题要点：1.先确定最高分界点左面有几个圈，然后确定分界点。如本题，分界点左面有3个圈，则 20 21 22 23 24 25 26 27 28 --23为分界点 2.以根节点为界，左孩子小于右孩子。 3.若出现连续左孩子，或连续又孩子，注意左孩子连续减小原则，右孩子连续增大原则。 4.圈的之间差值最小原则。 5.最左面的圈最小，最右面的圈最大。
