1、数据结构导论自考题-1 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.算法的便于阅读和理解的特性称为( )A正确性 B易读性C健壮性 D时空性（分数：2.00）A.B.C.D.2.给定有 n 个元素，建立一个有序单链表的时间复杂度为( )AO(1) BO(n)CO(n 2) DO(nlog 2n)（分数：2.00）A.B.C.D.3.在双链表中某结点(已知其地址)前插入一新结点，其时间复杂度为( )AO(n) BO(1)CO(n 2) DO(log 2n)（分数：2.00）A.B.C.D.4.顺序栈 s 中 top 为栈顶指针，指向栈
2、顶元素所在的位置，elem 为存放栈的数组，则元素 e 进栈操作的主要语句为( )As.elemtop=e;s.top=s.top+1;Bs.elemtop+1=e;s.top=s.top+1;Cs.top=s.top+1;s.elemtop+1=e;Ds.top=s.top+1;s.elemtop=e;（分数：2.00）A.B.C.D.5.一个数组的第一个元素的存储地址是 100，每个元素占 2 个存储单元，则第 5 个元素的存储地址是( )A110 B108C100 D120（分数：2.00）A.B.C.D.6.已知某完全二叉树采用顺序存储结构，结点数据的存放顺序依次为 A、B、C、D、E
3、、F、G、H，该完全二叉树的后序遍历序列为( )AHDBEFCGA BHDEBFGCACDHEBFGACA DDEHBFGCA（分数：2.00）A.B.C.D.7.除根结点外，树上每个结点( )A可有任意多个孩子、一个双亲 B可有任意多个孩子、任意多个双亲C可有一个孩子、任意多个双亲 D只有一个孩子、一个双亲（分数：2.00）A.B.C.D.8.一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是( )A250 B500C501 D505（分数：2.00）A.B.C.D.9.设有 6 个结点的无向图，若要确保此图是一个连通图，则至少应有边的条数是( )A5 B6C7 D8（分数：2.00
4、）A.B.C.D.10.在含有 n 个顶点 e 条边的无向图的邻接矩阵中，零元素的个数为( )Ae B2eCn 2-e Dn 2-2e（分数：2.00）A.B.C.D.11.设有无向图 G=(V，E)和(G=(V，E)，如 G为 G 的生成树，则下面说法不正确的是( )AG为 G 的子图 BG为 G 的连通分量CG为 G 的极小连通子图且 V=V DG是 G 的无环子图（分数：2.00）A.B.C.D.12.利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素 35 要进行元素间比较的次数是( )A4 次 B5 次C7 次 D10
5、次（分数：2.00）A.B.C.D.13.采用二分查找法，若当前取得的中间位置 MID 的元素值小于被查找值，则表明待查元素可能在表的后半部分，下次查找的起始位置通常应( )A从 MID/2 位置开始 B从 MID 位置开始C从 MID-1 位置开始 D从 MID+1 位置开始（分数：2.00）A.B.C.D.14.当待排序序列中记录数较少或基本有序时，最适合的排序方法为( )A直接插入排序法 B快速排序法C堆排序法 D归并排序法（分数：2.00）A.B.C.D.15.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )A
6、(38，40，46，56，79，84) B(40，38，46，79，56，84)C(40，38，46，56，79，84) D(40，38，46，84，56，79)（分数：2.00）A.B.C.D.二、填空题(总题数：13，分数：26.00)16.算法的空间性能是指算法需要的 1。（分数：2.00）填空项 1:_17.程序段“i=1; while(i=n) i=i*2;”的时间复杂度 T(n)= 1。（分数：2.00）填空项 1:_18.对顺序表执行删除操作，其删除算法的平均时间复杂度为 1。（分数：2.00）填空项 1:_19.顺序队的出、入队操作会产生 1。（分数：2.00）填空项 1:_2
7、0.若 front 和 rear 分别表示循环队列 Q 的头指针和尾指针，m 0表示该队列的最大容量，则循环队列为空的条件是 1。（分数：2.00）填空项 1:_21.二维数组 A56采用按列为主序的存储方式，每个元素占 3 个存储单元，若 A00的存储地址是100，则 A43的存储地址是 1。（分数：2.00）填空项 1:_22.对一棵深度为 10 的满二叉树按层编号，则编号为 51 的结点，它的双亲结点编号为 1。（分数：2.00）填空项 1:_23.对于一棵具有 n 个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为 2n 个，其中 1 个用于链接孩子结点。（分数：2.00）
8、填空项 1:_24.设 F、C 是二叉树中的两个结点，若 F 是 C 的祖先结点，则在采用后序遍历方法遍历该二叉树时，F 和C 的位置关系为：F 必定在 C 的 1。（分数：2.00）填空项 1:_25.在无向图 G 的邻接矩阵 A 中，若 Aij等于 0，则 Aji等于 1。（分数：2.00）填空项 1:_26.有 n 个顶点的强连通图最多有 1 条弧。（分数：2.00）填空项 1:_27.先在所有的记录中选出键值最小的记录，将它与第一个记录交换；然后在其余的记录中再选出最小的记录与第二个记录交换，依此类推，直至所有记录排序完成。这种排序方法称为 1。（分数：2.00）填空项 1:_28.对
9、 n 个元素进行冒泡排序时，第一趟排序的比较次数为 1。（分数：2.00）填空项 1:_三、应用题(总题数：5，分数：30.00)29.已知一棵二叉树的中序序列和后序序列分别为 BDCEAFHG 和 DECBHGFA，试画出这棵二叉树，并给出其先序序列。（分数：6.00）_30.分别写出删除单向和双向循环链表中指针 P 所指的结点的直接后继结点(非尾结点)对应的语句。(1)单向循环链表。(2)双向循环链表。（分数：6.00）_31.假设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，问此类二叉树中的结点数可能达到的最大值和最小值各为多少? 并说明是什么样的二叉树?（分数：6.00）_3
10、2.试写出下图的拓扑序列。（分数：6.00）_33.已知数据序列为(12，5，9，20，6，31，24)，对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。（分数：6.00）_四、算法设计题(总题数：2，分数：14.00)34.设某带头结点的单链表的结点结构说明如下：typedef struct nodelint data;struct nodel*next;node;试设计一个算法：void copy(node*head1, node*head2)，将以 head1 为头指针的单链表复制到一个不带有头结点且以 head2 为头指针的单链表中。（分数：7.00）_35.试编写算法求键值
11、为 k 结点在给定的二叉排序树中所在的层数。（分数：7.00）_数据结构导论自考题-1 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.算法的便于阅读和理解的特性称为( )A正确性 B易读性C健壮性 D时空性（分数：2.00）A.B. C.D.解析：解析 本题主要考查的知识点是算法的易读性。要点透析 算法的易读性是指易于阅读、理解和交流，便于调试、修改和扩充。2.给定有 n 个元素，建立一个有序单链表的时间复杂度为( )AO(1) BO(n)CO(n 2) DO(nlog 2n)（分数：2.00）A.B. C.D.解析：解析 本题主要考查
12、的知识点是建立有序单链表的时间复杂度。要点透析 在创建有序单链表的过程中，每一次将新结点链接入有序表的时间分两部分，其一是查找插入的合适位置，其二是将元素插入。后者的时间复杂度是常量 O(1)，而前者的时间复杂度由比较元素的次数决定，由于元素比较的次数是不确定的，只能取平均比较次数，为(n+1)/2，故其时间复杂度为 O(n)。由线性累加规则可得整个算法的时间复杂度为：O(n)。3.在双链表中某结点(已知其地址)前插入一新结点，其时间复杂度为( )AO(n) BO(1)CO(n 2) DO(log 2n)（分数：2.00）A.B. C.D.解析：4.顺序栈 s 中 top 为栈顶指针，指向栈顶
13、元素所在的位置，elem 为存放栈的数组，则元素 e 进栈操作的主要语句为( )As.elemtop=e;s.top=s.top+1;Bs.elemtop+1=e;s.top=s.top+1;Cs.top=s.top+1;s.elemtop+1=e;Ds.top=s.top+1;s.elemtop=e;（分数：2.00）A.B.C.D. 解析：5.一个数组的第一个元素的存储地址是 100，每个元素占 2 个存储单元，则第 5 个元素的存储地址是( )A110 B108C100 D120（分数：2.00）A.B. C.D.解析：6.已知某完全二叉树采用顺序存储结构，结点数据的存放顺序依次为 A、
14、B、C、D、E、F、G、H，该完全二叉树的后序遍历序列为( )AHDBEFCGA BHDEBFGCACDHEBFGACA DDEHBFGCA（分数：2.00）A.B. C.D.解析：解析 本题主要考查的知识点是完全二叉树的后序遍历。要点透析 要求得二叉树的后序遍历序列。必须首先将二叉树构造出来。根据题意可求得二叉树如下图所示。对二叉树进行后序遍历，可知正确答案为 B 项。7.除根结点外，树上每个结点( )A可有任意多个孩子、一个双亲 B可有任意多个孩子、任意多个双亲C可有一个孩子、任意多个双亲 D只有一个孩子、一个双亲（分数：2.00）A. B.C.D.解析：8.一棵完全二叉树上有 1001
15、个结点，其中叶子结点的个数是( )A250 B500C501 D505（分数：2.00）A.B.C. D.解析：解析 本题主要考查的知识点是完全二叉树。要点透析 由二叉树结点的公式：n=n 0十 n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为 n=1001，所以1002=2n0+n1，在完全二叉树中，n 1只能取 0 或 1，在本题中只能取 0(如果取 1 则 n0=500.5 是不可能的)，故 n=501。9.设有 6 个结点的无向图，若要确保此图是一个连通图，则至少应有边的条数是( )A5 B6C7 D8（分数：2.00）A. B.C.D.解析：解析 本题主要考查的知识点是无
16、向图的连通图。要点透析 无向图的顶点数为 n，则其含有全部顶点的连通图的边数最少为 n-1。10.在含有 n 个顶点 e 条边的无向图的邻接矩阵中，零元素的个数为( )Ae B2eCn 2-e Dn 2-2e（分数：2.00）A.B.C.D. 解析：11.设有无向图 G=(V，E)和(G=(V，E)，如 G为 G 的生成树，则下面说法不正确的是( )AG为 G 的子图 BG为 G 的连通分量CG为 G 的极小连通子图且 V=V DG是 G 的无环子图（分数：2.00）A.B. C.D.解析：解析 本题主要考查的知识点是无向图。要点透析 一个连通图的生成树，是含有该连通图的全部顶点的一个极小连通
17、子图，但不一定含有全部的边，也就不满足连通分量的定义。因此不能说 G为 G 的连通分量。12.利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素 35 要进行元素间比较的次数是( )A4 次 B5 次C7 次 D10 次（分数：2.00）A. B.C.D.解析：解析 本题主要考查的知识点是二叉排序树的查找。要点透析 建立起二叉排序树如图所示。查找元素 35 需要比较 4 次，所以选 A。13.采用二分查找法，若当前取得的中间位置 MID 的元素值小于被查找值，则表明待查元素可能在表的后半部分，下次查找的起始位置通常应( )A从 M
18、ID/2 位置开始 B从 MID 位置开始C从 MID-1 位置开始 D从 MID+1 位置开始（分数：2.00）A.B.C.D. 解析：14.当待排序序列中记录数较少或基本有序时，最适合的排序方法为( )A直接插入排序法 B快速排序法C堆排序法 D归并排序法（分数：2.00）A. B.C.D.解析：15.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )A(38，40，46，56，79，84) B(40，38，46，79，56，84)C(40，38，46，56，79，84) D(40，38，46，84，56，79)（分
19、数：2.00）A.B.C. D.解析：解析 本题主要考查的知识点是快速排序的方法。要点透析 快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。初始序列：46 79 56 38 40 84第 1 次交换：40 79 56 38 46 84第 2 次交换：40 46 56 38 79 84第 3 次交换：40 38 56 46 79 84第 4 次交换：40 38 46 56 79 84二、填空题(总题数：13，分数：26.00)16.算法的空间性能是指算法需要的 1。（分数：2.00）填空项 1:_
20、（正确答案：存储量）解析：17.程序段“i=1; while(i=n) i=i*2;”的时间复杂度 T(n)= 1。（分数：2.00）填空项 1:_ （正确答案：O(log 2n)）解析：18.对顺序表执行删除操作，其删除算法的平均时间复杂度为 1。（分数：2.00）填空项 1:_ （正确答案：O(n)）解析：19.顺序队的出、入队操作会产生 1。（分数：2.00）填空项 1:_ （正确答案：假溢出）解析：20.若 front 和 rear 分别表示循环队列 Q 的头指针和尾指针，m 0表示该队列的最大容量，则循环队列为空的条件是 1。（分数：2.00）填空项 1:_ （正确答案：Q.rear
21、=Q.front）解析：21.二维数组 A56采用按列为主序的存储方式，每个元素占 3 个存储单元，若 A00的存储地址是100，则 A43的存储地址是 1。（分数：2.00）填空项 1:_ （正确答案：157）解析：22.对一棵深度为 10 的满二叉树按层编号，则编号为 51 的结点，它的双亲结点编号为 1。（分数：2.00）填空项 1:_ （正确答案：25）解析：23.对于一棵具有 n 个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为 2n 个，其中 1 个用于链接孩子结点。（分数：2.00）填空项 1:_ （正确答案：n-1）解析：24.设 F、C 是二叉树中的两个结点，若
22、 F 是 C 的祖先结点，则在采用后序遍历方法遍历该二叉树时，F 和C 的位置关系为：F 必定在 C 的 1。（分数：2.00）填空项 1:_ （正确答案：后面）解析：25.在无向图 G 的邻接矩阵 A 中，若 Aij等于 0，则 Aji等于 1。（分数：2.00）填空项 1:_ （正确答案：0）解析：26.有 n 个顶点的强连通图最多有 1 条弧。（分数：2.00）填空项 1:_ （正确答案：n(n-1)）解析：27.先在所有的记录中选出键值最小的记录，将它与第一个记录交换；然后在其余的记录中再选出最小的记录与第二个记录交换，依此类推，直至所有记录排序完成。这种排序方法称为 1。（分数：2.
23、00）填空项 1:_ （正确答案：直接选择排序）解析：28.对 n 个元素进行冒泡排序时，第一趟排序的比较次数为 1。（分数：2.00）填空项 1:_ （正确答案：n-1）解析：三、应用题(总题数：5，分数：30.00)29.已知一棵二叉树的中序序列和后序序列分别为 BDCEAFHG 和 DECBHGFA，试画出这棵二叉树，并给出其先序序列。（分数：6.00）_正确答案：(先序序列为：ABCDEFGH，所求二叉树如图所示：)解析：30.分别写出删除单向和双向循环链表中指针 P 所指的结点的直接后继结点(非尾结点)对应的语句。(1)单向循环链表。(2)双向循环链表。（分数：6.00）_正确答案：
24、(1)单向循环链表：p-next=p-next-next;(2)双向循环链表：p-next=p-next-next;p-next-prior=P;)解析：31.假设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，问此类二叉树中的结点数可能达到的最大值和最小值各为多少? 并说明是什么样的二叉树?（分数：6.00）_正确答案：(结点数的最大值为 2h-1，最小值为 2h-1(第一层根结点，其余每层均两个结点且互为兄弟)。结点最多时为满二叉树。h=5 时最小值的情况之一：)解析：32.试写出下图的拓扑序列。（分数：6.00）_正确答案：(有以下三个拓扑序列：v1 v5 v2 v3 v6 v4
25、v1 v5 v6 v2 v3 v4v5 v6 v1 v2 v3 v4)解析：33.已知数据序列为(12，5，9，20，6，31，24)，对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。（分数：6.00）_正确答案：(1)插入排序的每趟的结果：初始值键值序列 12 5 9 20 6 31 24i=2512 9 20 6 31 24i=35 912 20 6 31 24i=45 9 1220 6 31 24i=55 6 9 1220 31 24i=65 6 9 12 2031 24i=75 6 9 12 20 2431排序结果5 6 9 12 20 24 31(2)冒泡排序的每趟的结果：
26、初始键值序列12 5 9 20 6 31 24第一趟之后5 9 12 6 20 2431第二趟之后5 9 6 12 2024 31第三趟之后5 6 9 1220 24 31第四趟之后 5 6 9 12 20 24 31)解析：四、算法设计题(总题数：2，分数：14.00)34.设某带头结点的单链表的结点结构说明如下：typedef struct nodelint data;struct nodel*next;node;试设计一个算法：void copy(node*head1, node*head2)，将以 head1 为头指针的单链表复制到一个不带有头结点且以 head2 为头指针的单链表中。
27、（分数：7.00）_正确答案：(算法描述如下：void copy(node* head1, node*head2) node*p, *q;head2=(node*) malloc(sizeof(node) )q=head2; p=head1-next;while(p!=NULL)s=(node*)malloc (sizeof(node);s-data=p-data;q-next=s;q=s;p=p-next;q-next=NULL;p=head2;head2=head2-next;free(p);)解析：35.试编写算法求键值为 k 结点在给定的二叉排序树中所在的层数。（分数：7.00）_正确答案：(算法描述如下：int level_count(BinTree bst, KeyType k)/求键值为 k 结点在给定的二叉排序树中所在/的层数int lev=0;BSTNode*p=bst;while(p!=NULL)lev+;if(p-data=k) return lev; /返回结果if(p-datak);p=p-rchild;/向右走elsep=P-lchild; /向左走return 0; /没有对应结点)解析：
