数据结构答案

1、河北省”高师本科”自考培训计算机专业题库答案1 单项选择：（本大题共有122小题，每小题1分）1-4-1-101 B1-4-1-202 C1-4-1-203 A1-4-2-604 D1-4-2-505 D1-4-1-206 A1-4-2-507 D2-4-1-108 A2-4-4-809 C2-4-4-610 D2-4-4-1011 A2-4-4-612 A3-4-1-113 B3-4-4-314 B3-4-4-115 D3-4-4-316 C3-4-4-317 D3-4-4-718 B3-4-4-919 C3-4-2-320 A3-4-2-821 A3-4-2-922 B3-4-4-323

2、A3-4-4-324 B3-4-2-625 B3-4-4-1026 D3-4-2-1027 A4-4-2-128 A4-4-2-129 B4-4-2-130 D4-4-2-131 A4-4-2-132 C4-4-2-133 B4-4-2-134 B5-4-2-135 D5-4-2-136 C5-4-2-137 B5-4-1-238 D5-4-1-239 C 5-4-2-240 B6-4-3-241 C6-4-3-242 A6-4-2-243 D6-4-2-244 B6-4-2-245 B 6-4-2-246 C6-4-2-247 B6-4-3-248 D6-4-3-249 B6-4-3-250

3、 D6-4-3-251 A6-4-2-452 A6-4-2-453 B6-4-2-454 A6-4-2-355 A6-4-2-556 A6-4-3-357 C6-4-3-258 A6-4-3-259 B6-4-3-260 B7-4-1-161 A7-4-2-162 C7-4-2-163 B7-4-1-164 B7-4-2-165 D 7-4-2-266 C7-4-2-167 A7-4-2-268 B7-4-2-269 C7-4-2-370 B7-4-2-371 A7-4-2-272 C7-4-3-273 B7-4-3-274 B7-4-3-275 C7-4-3-276 C7-4-3-377 D

4、7-4-2-278 C7-4-2-279 C7-4-3-480 A7-4-3-281 C7-4-3-282 A7-4-3-283 D7-4-3-184 A7-4-3-185 B8-4-2-286 C8-4-1-287 B8-4-2-388 A8-4-2-389 A8-4-1-390 A8-4-1-491 B8-4-1-592 A8-4-2-593 C8-4-2-594 A8-4-2-595 D8-4-1-796 B8-4-1-797 D8-4-1-798 C8-4-3-799 B8-4-2-7100 D9-4-3-1101 B9-4-3-1102 D9-4-3-3103 B9-4-3-3104

5、 A9-4-3-5105 D9-4-2-5106 B9-4-2-5107 C9-4-2-5108 D9-4-2-5109 A9-4-2-5110 A9-4-2-5111 C9-4-1-7112 C9-4-3-3113 D9-4-3-3114 C9-4-1-1115 B9-4-1-2116 B9-4-3-1117 C9-4-3-6118 C9-4-3-3119 A10-4-1-1120 B10-4-1-3121 C10-4-2-4122 D2 填空：（本大题共有96小题，每小题2分）1-1-1-101 逻辑结构1-1-1-502 查找1-1-1-503 读取1-1-1-504 插入1-1-1-5

6、05 删除1-1-2-606 索引存储1-1-2-607 所需要的时间1-1-1-108 逻辑结构1-1-1-209 存储结构2-1-4-610 n-i+12-1-4-911 n-i2-1-4-1212 p-next=head2-1-4-1113 p！=NULL2-1-1-114 L*（i-1）2-1-3-1215 s-next=s 2-1-3-1316 s-next=s-prior=s3-1-1-117 先进先出3-1-4-118 S.top=-13-1-4-119 S.top=maxsize-13-1-3-220 栈满3-1-3-221 空栈3-1-4-222 n-13-1-4-223 x

7、=s.datas.top;s.top=s.top+1;3-1-2-624 队尾3-1-3-525 ls-next3-1-3-526 ls-next=NULL3-1-3-527 首3-1-4-328 b3-1-2-929 队空否3-1-4-930 sq.datai3-1-4-931 sq.datamax3-1-4-932 max+13-1-4-933 03-1-4-934 04-1-2-135 124-1-2-136 abcdefgdef5-1-2-137 LOC（A00）+（n*i+j）*k5-1-2-138 3325-1-2-239 426-1-1-240 2k-16-1-2-241 2k-

8、16-1-2-242 n0-16-1-1-243 2i-16-1-3-244 56-1-3-245 06-1-2-246 n+16-1-2-347 2n-16-1-1-448 中序6-1-2-149 双亲链表表示法6-1-2-150 孩子链表表示法6-1-2-251 2k-16-1-2-252 76-1-2-553 187-1-2-154 n-17-1-3-255 17-1-3-356 O(n+e)7-1-3-357 O(n+e)7-1-3-258 求矩阵第i列非零元素之和7-1-3-259 将矩阵第i行全部元素置为07-1-1-460 最小7-1-1-461 n-17-1-3-262 17-

9、1-3-263 2(n-1)7-1-3-264 n(n-1)7-1-2-165 287-1-2-366 先序7-1-2-367 按层次7-1-3-268 邻接表7-1-3-269 逆邻接表8-1-1-170 分配排序8-1-1-171 静态查找8-1-1-172 动态查找8-1-1-773 冲突8-1-1-174 排序8-1-1-775 哈希函数（散列函数）8-1-2-276 n-18-1-2-277 09-1-1-178 动态查找表9-1-1-679 散列函数（哈希函数）9-1-2-680 散列表的长度9-1-3-581 289-1-3-582 609-1-3-583 39-1-3-584

10、59-1-3-585 359-1-3-586 279-1-2-287 (n+1)/29-1-2-388 log2(n+1)-19-1-2-489 (s2+2s+n)/(2s)9-1-3-690 散列查找方法9-1-2-391 按关键字有序10-1-1-192 性质10-1-1-193 文件维护10-1-2-194 索引文件10-1-2-195 插入10-1-3-196 关键字 3 简答（本大题共有24小题，每小题4分）1-6-1-101数据类型：是一个值的集合以及在这些值上定义的一组操作的总称（1分）数据结构：指的是数据之间的逻辑关系也称数据的逻辑结构。它包括线性结构和非线性结构两大类。（2分

11、）存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。（1分）1-6-1-302顺序存储结构是将各数据元素按其之间的逻辑关系存放在一块连续的存储空间内，由数据元素的存储位置体现数据元素之间的逻辑关系。（2分）链式存储结构各数据元素不一定是存储在连续的一块存储空间内，数据元素之间的逻辑关系与存储位置没有一一对应的关系，数据元素之间的逻辑关系，是依靠附加在存储数据元素的结点中的指针表示（2分）1-6-2-503a.算法必须是正确的（1分）b.执行算法所耗费的时间（1分）c.执行算法所耗费的空间，其中主要考虑辅助存储空间（1分）d.算法应易于理解、易于编码、易于调试等等。（1分）2

12、-6-1-104 在开始结点之前附设的一个结点称为头结点，它的数据域值是无意义的（2分）而开始结点是链表中存储线性表中第一个元素的结点。（2分）2-6-1-105 a.线性表的顺序存储表示结构简单，不需要额外的存储空间，数据记录在逻辑上相邻，在存储位置上亦相邻，可随机存取，有些运算容易实现；但在做插入和删除运算时要移动大量的元素，表长是固定的，不易扩展。（2分）b.链式存储表示是动态结构，表长可任意扩充，插入和删除不需要移动大量的元素；但不能随机存取，需要增加相应的存储空间。（2分）3-6-4-306所有可能的出站顺序有：123，132，213，231，321，不可能是312（2分）因为当3号

13、车进站并出站后，站台上有1号车和2号车，不可能先出1号而后出2号。（2分）3-6-4-707入队操作的指针移动语句为：cq.rear=(cq.rear+1)%QueueSize；（2分）出队操作的指针移动语句为：cq.front=(cq.front+1)%QueueSize；（2分）6-6-1-208 二叉树：是n(n0)个结点的有限集（1分），它或者是空集（n=0）（1分）,或者由一个根结点及两个互不相交的（1分）、分别称作这个根的左子树和右子树的二叉树组成（1分）。6-6-2-509哈夫曼树：在权为w1,w2,，wn的n个结点（1分）所构成的所有二叉树中（1分），带权路径长度最小（2分）的

14、二叉树称为最优二叉树，又称哈夫曼树。 7-6-2-510 拓扑排序：对于一个有向无环图（1分）进行拓扑排序，是将G中所有顶点排成一个线性序列（1分），使得对图中任意一个顶点u和v，若E(G)，则u在线性序列中出现在v之前（2分）。7-6-1-111连通图：在无向图G中，若从顶点vi到顶点vj有路径，则称vi和vj是连通的（2分），若V（G）上任意两个不同的顶点vi和vj都连通，则称G为连通图（2分）。7-6-1-112强连通图：在有向图中（1分），若对于V（G）中任意两个不同的顶点vi和vj（1分），都存在从vi到vj以及vj到vi的路径，则称G是强连通图（2分）。7-6-2-413最小生成树

15、：对于连通的带权图G（1分），其生成树也是带权的（1分），我们把生成树T的各边的权值总和称为该树的权（1分），将权值最小的生成树称为G的最小生成树，简记MST（1分）。8-6-3-114简述稳定排序和非稳定排序。若待排序的文件中，存在有多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的；（2分）反之若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。（2分）8-6-4-215简述插入排序算法中的哨兵作用在插入排序算法中，将要前插的记录ri保存在r0称作为哨兵。它的主要作用是用来在查找循环中“监视”下标变量j是否越界（2

16、分），因为r0就是ri本身，所以一旦越界（即j=0）则循环条件r0.keyrj.key不再成立使得查找循环正常结束，从而避免了在该循环内要检测j下标是否越界的判断（2分）。9-6-3-116什么是平均查找路径长度ASL。通常把查找过程当中对关键字比较的平均次数作为平均查找路径长度（2分）。若n是查找表的结点数，pi是查找第i个结点的概率，ci是找到第i个结点的比较次数，则平均查找路径长度 ASL= pici。（2分）9-6-4-317简述二分查找的基本思想。设rlowhigh为当前的查找区间，首先确定区间的中点位置m=(low+high)/2；然后将待查关键字K与rm.key进行比较，若相等则

17、查找成功并返回位置m（2分）；若Krm.key，则令low=m+1；确定新的查找区间再次进行查找，直到查找成功或查找区间为零时（查找失败）结束（2分）。9-6-2-518简述二叉排序树的性质。若它的左子树非空，则左子树上所有结点的值均小于根结点的值；（1分）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；（1分）左、右子树本身仍是一棵二叉排序树（2分）。9-6-4-619简述散列表中的冲突（碰橦）概念。有两个不同的关键字k1和k2，通过散列函数计算映射到表的同一个位置空间时（2分），即：H(k1)=H(k2)，则称之为发生冲突（碰橦），而发生冲突的两个关键字称为该散列函数的同义词（2

18、分）。9-6-4-720散列函数的选择标准是什么？散列函数选择有两条标准：简单和均匀（2分）。简单是指散列函数的计算简单快捷（1分）；均匀是指散列函数能将集合中的关键字以等概率映射到查找表的任何一个位置空间（1分）。9-6-4-921简述在散列表中拉链法解决冲突的基本思想。拉链法解决冲突的做法是，将所有关键字为同义词的结点链接在同一个单链表中（2分）。首先选定散列表的长度m，然后构造由m个头指针组成的指针数组T0m-1，凡是映射地址为i的结点，均插入以Ti为头指针的链表中（2分）。10-6-2-322 什么是索引文件？除文件本身之外，另建立一张索引表（2分），用来指明逻辑记录和物理记录之间的一

19、一对应关系，索引表和文件本身一起构成索引文件（2分）。10-6-3-423散列文件的查找过程以及散列查找的优点。在散列文件中进行查找时，首先根据给定值求出散列桶的地址，然后将基桶的记录读入内存进行顺序查找，若找到则检索成功（2分）；否则读入溢出桶的记录继续查找。散列文件查找的优点是：文件随机存放，记录不需要进行排序；插入、删除方便；存取速度快；不需索引区，节省存储空间（2分）。10-6-2-124什么是文件检索和文件维护？文件检索就是在文件中查找满足给定条件的记录，它即可以按记录的逻辑号查找，也可以按关键字查找（2分）。文件的维护操作是指对文件进行记录的插入、删除和修改等更新操作（2分）。4

20、应用（本大题共有24小题，每小题5分）3-30-3-501 简述下列算法的功能借助数组S（2分）将栈内的元素倒置（3分）3-30-3-502 简述下列算法的功能借助T栈（2分）将S栈内和c相同值的元素删除（3分）3-30-3-1103 写出下列程序段的输出结果输出结果：stack（5分） 3-30-4-504 简述下列算法的功能借助数组（2分）将S栈内的元素倒置（3分）3-30-4-505 简述下列算法的功能借助队列Q（2分）将S栈内的元素倒置（3分） 3-30-3-1106简述下列算法的功 借助栈S（2分）将Q队列内的元素倒置（3分） 6-30-4-307 二叉树正确3分，后序遍历序列2分b

21、dgacehf 后序遍历序列：gdbehfca6-30-4-308 二叉树正确3分，先序遍历序列2分 先序遍历序列：abcdefghbchadefg6-30-3-409 每棵树的对应二叉树各1分，关系正确1分BCHADEFGJI6-30-3-410 四个链表每个1分，向量1分 data firstchild12 3 4 5 6 78 9 ABCDE F G H I J root 0 1 2 3 4 5 6 7 8 96-30-3-411 向量形式2分，parent域3分 下标0123456789 MaxTreeSize-1 dataABCDEFGHIJparent-10001123336-30

22、-3-412 给出各结点正确形式2分，表示出结点关系3分 D H F I C G J A B E T6-30-4-513 构造出哈夫曼树3分，求出带权路径长度2分假设7个结点分别为a、b、c、d、e、f、g，它们对应的权值为8、11、13、5、17、25、21，构造的哈夫曼树如下：gfedbca 100 45 5521 24 25 30 11 13 17 13 8 5 该哈夫曼树的带权路径长度为：WPL=84+54+173+113+133+252+212 =2877-30-3-514 序列正确5分拓扑排序序列：123654123546231427-30-4-415 最小生成树：生成树正确3分，

23、权值正确2分7-30-3-316 邻接矩阵：（1分）广度优先遍历结果（2分）：124536深度优先遍历结果（2分）：1234567-30-3-217图G的邻接表（每个链表1分）：01234 3 4 4 2 2 1 2 3 0 1 0 1 V1 V2 V3 V4 V57-30-3-218图G的逆邻接表（3分）： 3 0 0 2 V1 V2 V3 V4E F G H I J 0123顶点入度（1 分）出度（1分）V112V210V311V411 8-30-3-219 给定数据35，27，86，39，58，19，46，74；请写出按插入排序的每一趟结果。3527 86 39 58 19 46 742

24、7 3586 39 58 19 46 74 （1分）27 35 8639 58 19 46 7427 35 39 8658 19 46 74 （2分）27 35 39 58 8619 46 7419 27 35 39 58 8646 74 （1分）19 27 35 39 46 58 867419 27 35 39 46 58 74 86 （1分）8-30-4-220给定数据49，33，61，82，75，12，25，58，29；请写出按快速排序的每一趟结果。49 33 61 82 75 12 25 58 2929 33 25 124975 82 58 61 （2分）12 2529334961 5

25、87582122529 33 49 5861 75 82 （2分） 12 25 29 33 49 58 61 75 82 （1分）8-30-3-221给定数据35，27，86，39，58，19，46，74；请写出按选择排序的每一趟结果。1927 86 39 58 35 46 7419 2786 39 58 35 46 74 （1分）19 27 3539 58 86 46 7419 27 35 3958 86 46 7419 27 35 39 4686 58 74 （2分）19 27 35 39 46 5886 7419 27 35 39 46 58 748619 27 35 39 46 58 74 86 （2分）8-30-4-222给定数据48，32，61，82，75，19，25，58；请写出按冒泡排序的每一趟结果。48 32 61 82 75 19 25 581948 32 61 82 75 25 58 19 2548 32 61 82 75 58 （2分）19 25 3248 58 61 82 7519 25 32 4858 61 75 82 （2分）19 25 32 4858 61 75 8219 25 32 48 58 61 75 82 （1分） 9-30-3-923按拉链法构造构造散列函数表图表正确（3分），计算结果正确（2分） 012345651