【学历类职业资格】数据结构导论真题2013年01月及答案解析.doc

1、数据结构导论真题 2013 年 01 月及答案解析(总分：100.00，做题时间：90 分钟)一、第部分 选择题(总题数：15，分数：30.00)1.数据的基本单位是_（分数：2.00）A.数据元素B.数据项C.字段D域2.算法的空间复杂度是指_（分数：2.00）A.算法中输入数据所占用的存储空间的大小B.算法本身所占用的存储空间的大小C.算法中所占用的所有存储空间的大小D.算法中需要的辅助变量所占用存储空间的大小3.从一个长度为 100 的顺序表中删除第 30 个元素，需向前移动的元素个数为_（分数：2.00）A.29B.30C.70D.714.若线性表最常用的操作是存取第 i 个元素及其后

2、继的值，则最节省操作时间的存储结构是_（分数：2.00）A.单链表B.双链表C.单循环链表D.顺序表5.判断链栈 LS 是否为空的条件是_（分数：2.00）A.LS-next=LSB.LS-next=NULLC.LS!=NULLD.LS=NULL6.关于链队列的运算说法正确的是_（分数：2.00）A.入队列需要判断队列是否满B.出队列需要判断队列是否空C.入队列需要判断队列是否空D.出队列需要判断队列是否满7.元素的进栈次序为 A，B，C，D，E，则出栈中不可能的序列是_（分数：2.00）A.A，B，C，D，EB.B，C，D，E，AC.E，A，B，C，DD.E，D，C，B，A8.具有 63 个

3、结点的完全二叉树是_（分数：2.00）A.满二叉树B.二叉排序树C.哈夫曼树D.空树9.将含有 80 个结点的完全二叉树从根这一层开始，每层从左到右依次对结点编号，根结点的编号为 1，则关于编号 40 的结点的左右孩子的说法正确的是_（分数：2.00）A.左孩子编号为 79，右孩子编号为 80B.左孩子不存在，右孩子编号为 80C.左孩子编号为 80，右孩子不存在D.左孩子不存在，右孩子不存在10.将下图所示的一棵树转换为二叉树，结点 D 是_ （分数：2.00）A.A 的右孩子B.B 的右孩子C.C 的右孩子D.E 的右孩子11.无向图的邻接矩阵是_（分数：2.00）A.对称矩阵B.稀疏矩阵

4、C.对角矩阵D.上三角矩阵12.图的广度优先搜索遍历的过程类似于树的_（分数：2.00）A.前序遍历B.中序遍历C.后序遍历D.按层次遍历13.要解决散列引起的冲突问题，最常用的方法是_（分数：2.00）A.数字分析法、除留余数法、平方取中法B.除留余数法、线性探测法、平方取中法C.线性探测法、二次探测法、链地址法D.除留余数法、线性探测法、二次探测法14.下列表述中，正确的是_（分数：2.00）A.序列(102，81，55，62，50，40，58，35，20)是堆B.序列(102，81，55，62，50，40，35，58，20)是堆C.序列(102，81，55，58，50，40，35，62，

5、20)是堆D.序列(102，71，55，40，50，62，35，58，20)是堆15.下列算法中，不稳定的排序算法是_（分数：2.00）A.冒泡排序B.快速排序C.直接插入排序D.二路归并排序二、第部分 非选择题(总题数：13，分数：26.00)16.下面算法程序段的时间复杂度为 1。 for(i=1;i=n;i+) for(j=1;j=i;j+) x=aij; aij=aji; aji=x; （分数：2.00）17.设 p 指向单链表的最后一个结点，要在最后一个结点之后插入 q 所指的结点，需执行的语句序列是p-的next=q； 1；p-next=NuLL。 （分数：2.00）18.向一个长

6、度为 100 的顺序表中第 50 个元素之前插入一个元素时，需向后移动的元素个数为 1。 （分数：2.00）19.一个带头结点的链栈 LS，现将一个新结点入栈，指向该结点的指针为 p，入栈操作为 p-next=LS-next 和 1。 （分数：2.00）20.队列操作的原则是 1。 （分数：2.00）21.含有 n 个顶点的连通图中的任意一条简单路径，其最大长度为 1。 （分数：2.00）22.在一棵度为 3 的树中，度为 3 的结点数为 1 个，度为 2 的结点数为 2 个，度为 1 的结点数为 3 个，则度为 0 的结点数为 1 个。 （分数：2.00）23.某二叉树的中序遍历序列为 BA

7、CDEFGH，后序遍历序列为 BCAEDGHF，则根结点 F 的左子树上共有 1 个结点。 （分数：2.00）24.设有向图 G 的邻接矩阵为 A，如果V i ，V j 是图中的一条弧，则 Aij的值为 1。 （分数：2.00）25.一个有序表 A 含有 15 个数据元素，且第一个元素的下标为 1，按二分查找算法查找元素 A14，所比较的元素下标依次是 1。 （分数：2.00）26.用 n 个值构造一棵二叉排序树，它的最大深度为 1。 （分数：2.00）27.设记录数为 n，则冒泡排序算法在最好情况下所作的比较次数为 1。 （分数：2.00）28.二路归并排序算法的时间复杂度为 1。 （分数：

8、2.00）三、应用题(总题数：5，分数：30.00)29.设有编号为 A，B，C，D 的四辆列车，顺序进入一个栈式结构的站台，试写出这四辆列车开出站台的所有可能的顺序。 （分数：6.00）_30.已知一棵二叉树的先序遍历序列为 ABCDEFGHK，中序遍历序列为 CBEDFAGKH，试建立该二叉树并写出它的后序遍历序列。 （分数：6.00）_31.利用克鲁斯卡尔(Kruskal)算法构造下图的最小生成树，画出它的构造过程。 （分数：6.00）_32.给定表(27，19，50，1，75，12，40，90，66，32，22)，试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树，画出插入完

9、成后的二叉排序树。 （分数：6.00）_33.对初始关键字序列 48，39，68，95，88，12，27，48 的记录进行冒泡排序(升序)，给出排序过程。 （分数：6.00）_四、算法设计题(总题数：2，分数：14.00)34.试写出判断带头结点的单链表 head 中的元素值是否是递减的算法。 （分数：7.00）_35.试写出在有序表 T 中用二分查找法查找键值为 key 的元素的算法。 （分数：7.00）_数据结构导论真题 2013 年 01 月答案解析(总分：100.00，做题时间：90 分钟)一、第部分 选择题(总题数：15，分数：30.00)1.数据的基本单位是_（分数：2.00）A.

10、数据元素 B.数据项C.字段D域解析：考点 数据的基本单位 解析 数据的基本单位是数据元素。2.算法的空间复杂度是指_（分数：2.00）A.算法中输入数据所占用的存储空间的大小B.算法本身所占用的存储空间的大小C.算法中所占用的所有存储空间的大小D.算法中需要的辅助变量所占用存储空间的大小 解析：考点 算法的空间复杂度 解析 算法的空间复杂度是指算法中需要的辅助变量所占用存储空间的大小。3.从一个长度为 100 的顺序表中删除第 30 个元素，需向前移动的元素个数为_（分数：2.00）A.29B.30C.70 D.71解析：考点 顺序表的删除操作 解析 删除第 30 个元素，需要将 31 到

11、100 的 70 个元素向前移动。4.若线性表最常用的操作是存取第 i 个元素及其后继的值，则最节省操作时间的存储结构是_（分数：2.00）A.单链表B.双链表C.单循环链表D.顺序表 解析：考点 顺序表 解析 若线性表最常用的操作是存取第 i 个元素及其后继的值，则最节省操作时间的存储结构是顺序表。5.判断链栈 LS 是否为空的条件是_（分数：2.00）A.LS-next=LSB.LS-next=NULL C.LS!=NULLD.LS=NULL解析：考点 链栈为空的条件 解析 判断链栈 LS 是否为空的条件是 LS-next=NULL。6.关于链队列的运算说法正确的是_（分数：2.00）A.

12、入队列需要判断队列是否满B.出队列需要判断队列是否空 C.入队列需要判断队列是否空D.出队列需要判断队列是否满解析：考点 链队列的运算 解析 出队列需要判断队列是否为空，入队列无需判断是否队列满也无须判断是否为空。出队列需判断队列是否为空。7.元素的进栈次序为 A，B，C，D，E，则出栈中不可能的序列是_（分数：2.00）A.A，B，C，D，EB.B，C，D，E，AC.E，A，B，C，D D.E，D，C，B，A解析：考点 栈的存取原则，后进先出 解析 C 选项中，E 先出栈，则由栈顶到栈底的序列是 DCBA，则不可能出现 EABCD。8.具有 63 个结点的完全二叉树是_（分数：2.00）A.

13、满二叉树 B.二叉排序树C.哈夫曼树D.空树解析：考点 满二叉树、二叉排序树、哈夫曼树、完全二叉树之间的关系 解析 二叉树不是完全二叉树，满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。由题意知完全二叉树的深度为 9.将含有 80 个结点的完全二叉树从根这一层开始，每层从左到右依次对结点编号，根结点的编号为 1，则关于编号 40 的结点的左右孩子的说法正确的是_（分数：2.00）A.左孩子编号为 79，右孩子编号为 80B.左孩子不存在，右孩子编号为 80C.左孩子编号为 80，右孩子不存在 D.左孩子不存在，右孩子不存在解析：考点 完全二叉树某结点的左右孩子编号 解析 因为 240=8

14、0，则左孩子编号为 80，没有右孩子。10.将下图所示的一棵树转换为二叉树，结点 D 是_ （分数：2.00）A.A 的右孩子B.B 的右孩子C.C 的右孩子 D.E 的右孩子解析：考点 树转换为二叉树 解析 将所有兄弟结点连接起来。保留第一个兄弟结点与父结点的连接，断开其他兄弟结点与父结点的连接，然后以根结点为轴心按顺时针方向旋转 45角。可知 D 是 C 的右孩子。11.无向图的邻接矩阵是_（分数：2.00）A.对称矩阵 B.稀疏矩阵C.对角矩阵D.上三角矩阵解析：考点 无向图的邻接矩阵 解析 无向图的邻接矩阵是对称矩阵。12.图的广度优先搜索遍历的过程类似于树的_（分数：2.00）A.前

15、序遍历B.中序遍历C.后序遍历D.按层次遍历 解析：考点 图的广度优先遍历 解析 图的广度优先搜索遍历的过程类似于树的按层次遍历。13.要解决散列引起的冲突问题，最常用的方法是_（分数：2.00）A.数字分析法、除留余数法、平方取中法B.除留余数法、线性探测法、平方取中法C.线性探测法、二次探测法、链地址法 D.除留余数法、线性探测法、二次探测法解析：考点 解决散列引起的冲突问题最常用的方法 解析 解决散列引起的冲突问题，最常用的方法是线性探测法、二次探测法、链地址法。14.下列表述中，正确的是_（分数：2.00）A.序列(102，81，55，62，50，40，58，35，20)是堆B.序列(

16、102，81，55，62，50，40，35，58，20)是堆 C.序列(102，81，55，58，50，40，35，62，20)是堆D.序列(102，71，55，40，50，62，35，58，20)是堆解析：考点 堆排序 解析 堆分为最小堆和最大堆，选项 B 满足最大堆，所有选 B。15.下列算法中，不稳定的排序算法是_（分数：2.00）A.冒泡排序B.快速排序 C.直接插入排序D.二路归并排序解析：考点 排序算法的稳定性 解析 冒泡、直接插入以及二路归并排序都属于稳定排序，快速排序是不稳定排序算法。二、第部分 非选择题(总题数：13，分数：26.00)16.下面算法程序段的时间复杂度为 1。

17、 for(i=1;i=n;i+) for(j=1;j=i;j+) x=aij; aij=aji; aji=x; （分数：2.00）解析：O(n 2 ) 考点 算法时间复杂度的计算 解析 可知该算法是双重循环，时间复杂度为 O(n 2 )。17.设 p 指向单链表的最后一个结点，要在最后一个结点之后插入 q 所指的结点，需执行的语句序列是p-的next=q； 1；p-next=NuLL。 （分数：2.00）解析：p=q 考点 单链表的元素插入操作 解析 设 p 指向单链表的最后一个结点，要在最后一个结点之后插入 q 所指的结点，需执行的语句序列是p-next=q；p=q；p-next=NULL。

18、18.向一个长度为 100 的顺序表中第 50 个元素之前插入一个元素时，需向后移动的元素个数为 1。 （分数：2.00）解析：51 考点 顺序表元素插入操作 解析 在第 50 个元素之前插入元素，需要将 50100 共 51 个元素都向后移动。19.一个带头结点的链栈 LS，现将一个新结点入栈，指向该结点的指针为 p，入栈操作为 p-next=LS-next 和 1。 （分数：2.00）解析：LS-next=p 考点 链栈的入栈操作 解析 入栈操作为 p-next=LS-next 和 LS-next=p。20.队列操作的原则是 1。 （分数：2.00）解析：先进先出 考点 队列操作的原则 解

19、析 队列操作的原则是先进先出。21.含有 n 个顶点的连通图中的任意一条简单路径，其最大长度为 1。 （分数：2.00）解析：n-1 考点 连通图简单路径长度 解析 含有 n 个顶点的连通图中的任意一条简单路径，其最大长度为 n-1。22.在一棵度为 3 的树中，度为 3 的结点数为 1 个，度为 2 的结点数为 2 个，度为 1 的结点数为 3 个，则度为 0 的结点数为 1 个。 （分数：2.00）解析：5 考点 树的叶子结点个数，树的度，结点的度 解析 度为 3 的树，度为 3 的结点一个，产生 3 个子树(孩子结点)；度为 2 的结点 2 个，产生 22=4 子树(孩子结点)，利用 2

20、 个结点，还剩 3+4-2=5 个结点；度为 1 个结点 3 个，产生 3 个子树(孩子结点)，利用 3 个结点，还剩 5 个结点。所以有 5 个结点度为 0。23.某二叉树的中序遍历序列为 BACDEFGH，后序遍历序列为 BCAEDGHF，则根结点 F 的左子树上共有 1 个结点。 （分数：2.00）解析：5 考点 根据二叉树的中、后遍历求某结点的左子树 解析 由中序序列可知 F 左边序列为 F 的左子树上元素结点，可知为 BACDE 共 5 个。24.设有向图 G 的邻接矩阵为 A，如果V i ，V j 是图中的一条弧，则 Aij的值为 1。 （分数：2.00）解析：1 考点 有向图与邻

21、接矩阵转换 解析 如果V i ，V j 是图中的一条弧，则 Aij的值为 1。25.一个有序表 A 含有 15 个数据元素，且第一个元素的下标为 1，按二分查找算法查找元素 A14，所比较的元素下标依次是 1。 （分数：2.00）解析：8、12、14 考点 二分查找算法 解析 所比较元素下标依次为：(15+1)/2=8；(9+15)/2=12；(13+15)/2=14。26.用 n 个值构造一棵二叉排序树，它的最大深度为 1。 （分数：2.00）解析：n 考点 树的深度 解析 用 n 个值构造一棵二叉排序树，它的最大深度为 n。27.设记录数为 n，则冒泡排序算法在最好情况下所作的比较次数为

22、1。 （分数：2.00）解析：n-1 考点 冒泡排序 解析 设录数为 n，则冒泡排序算法在最好情况下所作的比较次数为 n-1。28.二路归并排序算法的时间复杂度为 1。 （分数：2.00）解析：O(nlog 2 n) 考点 二路归并排序 解析 二路归并排序算法的时间复杂度为 O(nlog 2 n)。三、应用题(总题数：5，分数：30.00)29.设有编号为 A，B，C，D 的四辆列车，顺序进入一个栈式结构的站台，试写出这四辆列车开出站台的所有可能的顺序。 （分数：6.00）_正确答案：()解析：若列车 A 最先开出站台，则列车可能的出站顺序有： ABCD、ABDC、ACBD、ACDB、ADCB

23、(注意 ADBC 不是解) 若列车 B 最先开出站台，则列车可能的出站顺序有： BACD、BADC、BCAD、BCDA、BDCA(注意 BDAC 不是解) 若列车 C 最先开出站台，则列车可能的出站顺序有： CBAD、CBDA、CDBA(注意 CABD、CADB、CDAB 不是解) 若列车 D 最先开出站台，则列车可能的出站顺序有： DCBA(注意 DABC、DACB、DBAC、DBCA、DCAB 不是解) 考点 栈的存取原则后进先出30.已知一棵二叉树的先序遍历序列为 ABCDEFGHK，中序遍历序列为 CBEDFAGKH，试建立该二叉树并写出它的后序遍历序列。 （分数：6.00）_正确答案

24、：()解析：由先序遍历序列和中序遍历序列得到如下二叉树： 31.利用克鲁斯卡尔(Kruskal)算法构造下图的最小生成树，画出它的构造过程。 （分数：6.00）_正确答案：()解析：利用 Kruskal 算法构造最小生成树的过程如下： 32.给定表(27，19，50，1，75，12，40，90，66，32，22)，试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。 （分数：6.00）_正确答案：()解析：由给定的表，得到相应的二叉排序树如下： 33.对初始关键字序列 48，39，68，95，88，12，27，48 的记录进行冒泡排序(升序)，给出排序过程

25、。 （分数：6.00）_正确答案：()解析：冒泡排序过程如下： 初始关键字序列：48，39，68，95，88，12，27，48 第一趟排序后：39，48，68，88，12，27，48，95 第二趟排序后：39，48，68，12，27，48，88，95 第三趟排序后：39，48，12，27，48，68，88，95 第四趟排序后：39，12，27，48，48，68，88，95 第五趟排序后：12，27，39，48，48，68，88，95 第六趟排序后：12，27，39，48，48，68，88，95 考点 冒泡排序算法四、算法设计题(总题数：2，分数：14.00)34.试写出判断带头结点的单链表 h

26、ead 中的元素值是否是递减的算法。 （分数：7.00）_正确答案：()解析：算法如下： int list_isfall(LinkList head) LinkList p,q; p=head-next; if(p=NULL)retum 0; if(p-next=NULL)return 1; while(p-next!=NULL) q=p-next; if(q-datap-data) return0; else p=q; return 1; 考点 单链表35.试写出在有序表 T 中用二分查找法查找键值为 key 的元素的算法。 （分数：7.00）_正确答案：()解析：二分查找 key 元素的具体算法如下： int SearchBin(SqTable T,KeyType key) intlow=1,high=T.n; while(low=high) mid=(low+high)/2; if(key=T.elemmid.key)return mid; else if(keyT.elemmid.key)low=mid+1; else high=mid-1; ruturn 0; 考点 二分查找算法