1、数据结构导论自考题-5 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.要将现实生活中的数据转换为计算机所能表示的形式，其转移过程为( )A原始数据、存储结构、逻辑结构 B原始数据、逻辑结构、存储结构C逻辑结构、存储结构、原始数据 D逻辑结构、原始数据、存储结构（分数：2.00）A.B.C.D.2.算法在发生非法操作时可以作出处理的特性称为( )A正确性 B易读性C健壮性 D时空性（分数：2.00）A.B.C.D.3.下列算法的时间复杂度是( )for(i=0, j=0; in; i+)cij=i+j;AO(1) BO(n)CO(log
2、 2n) DO(n 2)（分数：2.00）A.B.C.D.4.设顺序表有 9个元素，则在第 3个元素前插入一个元素所需移动元素的个数为( )A5 B6C7 D9（分数：2.00）A.B.C.D.5.在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，该指针域用于存放一个指针，此指针指向该结点的( )A直接前驱 B直接后继C开始结点 D终端结点（分数：2.00）A.B.C.D.6.对于一个具有 n个元素的线性表，建立其单链表的最小时间复杂度为( )AO(log 2n) BO(1)CO(n 2) DO(n)（分数：2.00）A.B.C.D.7.在循环链表的一个结点中有( )个指针。
3、A1 B2C0 D3（分数：2.00）A.B.C.D.8.栈和队列共同具有的特点是( )A都是先进后出 B都是先进先出C只允许在端点进行操作运算 D既能先进先出，也能先进后出（分数：2.00）A.B.C.D.9.队列通常采用的两种存储结构是( )A顺序存储结构和链式存储结构 B散列方式和索引方式C链表存储结构和数组 D线性存储结构和非线性存储结构（分数：2.00）A.B.C.D.10.一个栈的输入序列是 12345，则下列序列中不可能是栈的输出序列的是( )A23415 B54132C23145 D15432（分数：2.00）A.B.C.D.11.一个队列的输入序列是 abcd，则队列的输出序
4、列是( )Aacdb BabcdCadcb Dcbda（分数：2.00）A.B.C.D.12.数组 A05，06每个元素占 5个单元，将其按列优先次序存储在起始地址为 1000的连续内存单元中，则元素 a55的地址为( )A1175 B1180C1205 D1210（分数：2.00）A.B.C.D.13.按照二叉树的定义，具有 3个结点的二叉树有( )A3 利 B4 种C5 种 D6 种（分数：2.00）A.B.C.D.14.在一棵二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序( )A都不相同B完全相同C先序序列和中序序列相同，而与后序序列不同D中序序列和后序序列相同，而与
5、先序序列不同（分数：2.00）A.B.C.D.15.深度为 6的二叉树最多拥有的结点数目是( )A64 B63C32 D31（分数：2.00）A.B.C.D.二、填空题(总题数：13，分数：26.00)16.数据的基本单位是 1。（分数：2.00）填空项 1:_17.所有结点按一对一的邻接关系构成的整体就是 1 结构。（分数：2.00）填空项 1:_18.双向循环链表找前驱结点和后继结点的时间复杂度为 1。（分数：2.00）填空项 1:_19.顺序表定位运算的基本操作是 1。（分数：2.00）填空项 1:_20.带头结点的双向循环链表 L为空的条件是 1。（分数：2.00）填空项 1:_21.
6、单链表表示法的基本思想是用 1 表示结点间的逻辑关系。（分数：2.00）填空项 1:_22.在一个用一维数组 AN表示的循环队列中，该队列中的元素个数最少为_个，最多为_个。（分数：2.00）填空项 1:_23.在栈中，可进行插入和删除操作的一端称为 1。（分数：2.00）填空项 1:_24. 1是指非零元素或零元素的分布有一定规律的矩阵。（分数：2.00）填空项 1:_25.多个值相同的元素只分配一个存储空间，零元素不分配空间，称为 1。（分数：2.00）填空项 1:_26.具有 10个叶子结点的二叉树中有 1 个度为 2的结点。（分数：2.00）填空项 1:_27.已知一棵度为 3的树有
7、2个度为 1的结点，3 个度为 2的结点，4 个度为 3的结点，则该树有 1 个叶子结点。（分数：2.00）填空项 1:_28.设 F是一个森林，B 是由 F转换得到的二叉树。若 F中有 n个非终端结点，则 B中右指针域为空的结点有 1 个。（分数：2.00）填空项 1:_三、应用题(总题数：5，分数：30.00)29.有 5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素 C，D 最先出栈(即 C第一个且 D第二个出栈)的次序有哪几个?（分数：6.00）_30.逻辑结构与存储结构是什么关系?（分数：6.00）_31.运算与运算的实现是什么关系? 有哪些相同点和不同点?
8、（分数：6.00）_32.分别画出题图所示二叉树的二叉链表、三叉链表和顺序存储结构。（分数：6.00）_33.给定权值 7，18，3，32，5，26，12，8，构造相应的哈夫曼树。（分数：6.00）_四、算法设计题(总题数：2，分数：14.00)34.设某单链表中，存在多个结点其数据值均为 D，试编写一算法统计该类结点的个数。（分数：7.00）_35.以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。（分数：7.00）_数据结构导论自考题-5 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.要将现实生活中的数据转换为计算机所能表示的形
9、式，其转移过程为( )A原始数据、存储结构、逻辑结构 B原始数据、逻辑结构、存储结构C逻辑结构、存储结构、原始数据 D逻辑结构、原始数据、存储结构（分数：2.00）A.B. C.D.解析：解析 本题主要考查的知识点是计算机解决问题的步骤。要点透析 在数学模型中，需要把原始数据按照某种方式组织起来，以便很好地体现数据之间的关系，数据及数据的组织方式称为数据的逻辑结构。为了能用计算机加工处理，逻辑结构还必须转换为能被计算机存储的存储结构。2.算法在发生非法操作时可以作出处理的特性称为( )A正确性 B易读性C健壮性 D时空性（分数：2.00）A.B.C. D.解析：解析 本题主要考查的知识点是算法
10、的健壮性。要点透析 算法的健壮性是指即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果。3.下列算法的时间复杂度是( )for(i=0, j=0; in; i+)cij=i+j;AO(1) BO(n)CO(log 2n) DO(n 2)（分数：2.00）A.B. C.D.解析：4.设顺序表有 9个元素，则在第 3个元素前插入一个元素所需移动元素的个数为( )A5 B6C7 D9（分数：2.00）A.B.C. D.解析：解析 本题主要考查的知识点是插入算法。要点透析 插入算法的基本步骤是：将结点 ai，a n各后移一位以便腾出第 i个位置；将 x置入该空位；表长加一。
11、5.在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，该指针域用于存放一个指针，此指针指向该结点的( )A直接前驱 B直接后继C开始结点 D终端结点（分数：2.00）A.B. C.D.解析：解析 本题主要考查的知识点是单链表中的指针域。要点透析 单链表的一个存储结点包含 data和 next两个部分，其中，data 部分称为数据域，用于存储线性表的一个数据元素；next 部分称为指针域或链域，用于存放一个指针，该指针指向本结点所含数据元素的直接后继结点。6.对于一个具有 n个元素的线性表，建立其单链表的最小时间复杂度为( )AO(log 2n) BO(1)CO(n 2) DO
12、(n)（分数：2.00）A.B.C.D. 解析：解析 本题主要考查的知识点是单链表的建立。要点透析 无论采用什么方式建立单链表，都需要扫描这 n个元素，边扫描边创建单链表中的结点并链接起来，其时间复杂度为 O(n)。本题答案为 D。7.在循环链表的一个结点中有( )个指针。A1 B2C0 D3（分数：2.00）A. B.C.D.解析：8.栈和队列共同具有的特点是( )A都是先进后出 B都是先进先出C只允许在端点进行操作运算 D既能先进先出，也能先进后出（分数：2.00）A.B.C. D.解析：解析 本题主要考查的知识点是栈和队列的特点。要点透析 栈的特点是先进后出，队列的特点是先进先出，栈只允
13、许在栈顶进行插入和删除运算，而队列只允许在队尾插入和队首删除，共同点是都只能在端点进行运算。9.队列通常采用的两种存储结构是( )A顺序存储结构和链式存储结构 B散列方式和索引方式C链表存储结构和数组 D线性存储结构和非线性存储结构（分数：2.00）A. B.C.D.解析：解析 本题主要考查的知识点是队列的存储结构。要点透析 队列可看成是一种运算受限的线性表，它包括两种存储结构：顺序存储结构和链式存储结构，其中顺序存储结构是在内存中开辟一个连续的空间用来存储数据，而链式存储结构采用链表指针来指示数据的存储位置。10.一个栈的输入序列是 12345，则下列序列中不可能是栈的输出序列的是( )A2
14、3415 B54132C23145 D15432（分数：2.00）A.B. C.D.解析：解析 本题主要考查的知识点是栈的输出序列。要点透析 此题可用排除法。栈的出入原则是后进先出。选项 B中显示 5最先输出，说明其余四个元素已经入栈，其输出序列应为 54321。11.一个队列的输入序列是 abcd，则队列的输出序列是( )Aacdb BabcdCadcb Dcbda（分数：2.00）A.B. C.D.解析：12.数组 A05，06每个元素占 5个单元，将其按列优先次序存储在起始地址为 1000的连续内存单元中，则元素 a55的地址为( )A1175 B1180C1205 D1210（分数：2
15、.00）A. B.C.D.解析：解析 本题主要考查的知识点是二维数组元素的地址计算。要点透析 a55的地址是 1000+(56+5)5=1175。13.按照二叉树的定义，具有 3个结点的二叉树有( )A3 利 B4 种C5 种 D6 种（分数：2.00）A.B.C. D.解析：解析 本题主要考查的知识点是二叉树的定义。要点透析 非空二叉树的判定条件是：有且只有一个根结点；其余结点分为两个互不相交的集合T1、T 2，T 1与 T2都是二叉树，并且 T1与 T2有顺序关系(T 1在 T2之前)。由此可知，3 个结点的二叉树有 5种。14.在一棵二叉树结点的先序序列、中序序列和后序序列中，所有叶子结
16、点的先后顺序( )A都不相同B完全相同C先序序列和中序序列相同，而与后序序列不同D中序序列和后序序列相同，而与先序序列不同（分数：2.00）A.B. C.D.解析：解析 本题主要考查的知识点是在二叉树遍历中对叶子结点的访问顺序。要点透析 显然遍历方法中的先序、中序、后序指的是对根的访问顺序，而对于叶子结点都采用先遍历左子树，后遍历右子树。15.深度为 6的二叉树最多拥有的结点数目是( )A64 B63C32 D31（分数：2.00）A.B. C.D.解析：解析 本题主要考查的知识点是二叉树的性质。要点透析 深度为 k(k1)的二叉树至多有 2k-1个结点。二、填空题(总题数：13，分数：26.
17、00)16.数据的基本单位是 1。（分数：2.00）填空项 1:_ （正确答案：数据元素）解析：17.所有结点按一对一的邻接关系构成的整体就是 1 结构。（分数：2.00）填空项 1:_ （正确答案：线性）解析：18.双向循环链表找前驱结点和后继结点的时间复杂度为 1。（分数：2.00）填空项 1:_ （正确答案：O(1)）解析：19.顺序表定位运算的基本操作是 1。（分数：2.00）填空项 1:_ （正确答案：比较）解析：20.带头结点的双向循环链表 L为空的条件是 1。（分数：2.00）填空项 1:_ （正确答案：(L-next=L)Node * p;int n=0;p=headwhile
18、 ( p ! = NULL)if (p-data=D) n+;p=p-next;return(n);)解析：35.以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。（分数：7.00）_正确答案：(本算法的基本思想是：先求左子树的叶子数，再求右子树的叶子数，两者相加就是根结点的叶子数，也就是对应二叉树的叶子数、int leafcount(BinTree T)/求二叉树 T的叶子数 if(T=NULL) leaf=0;/当二叉树为空时, 叶子数等于 0else if(T-lchild=NULL)/当二叉树仅含一个根结点时, 叶子数为 1else L=leafcount(T-lchild);/求左子树的叶子数R=leafcount(T-rchild);/求右子树的叶子数leaf=L+R;/左、右子树叶子数之和等于二叉树的叶子数return(leaf);)解析：
