[自学考试密押题库与答案解析]数据结构导论自考题模拟1

[自学考试密押题库与答案解析]数据结构导论自考题模拟1PAGE1/NUMPAGES1[自学考试密押题库与答案解析]数据结构导论自考题模拟1数据结构导论自考题模拟1一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的。问题:1.要将现实生活中的数据转换为计算机所能表示的形式，其转移过程为A.原始数据、存储结构、逻辑结构B.原始数据、逻辑结构、存储结构C.逻辑结构、存储结构、原始数据D.逻辑结构、原始数据、存储结构答案:B[解析]本题主要考查的知识点是计算机解决问题的步骤。[要点透析]在数学模型中，需要把原始数据按照某种方式组织起来，以便很好地体现数据之间的关系，数据及数据的组织方式称为数据的逻辑结构。为了能用计算机加工处理，逻辑结构还必须转换为能被计算机存储的存储结构。问题:2.算法在发生非法操作时可以作出处理的特性称为A.正确性B.易读性C.健壮性D.时空性答案:C[解析]本题主要考查的知识点是算法的健壮性。[要点透析]算法的健壮性是指即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果。问题:3.下列算法的时间复杂度是for(i=0,j=0;i＜n;i++)c[i][j]=i+j;A.O(1)B.O(n)C.O(log2n)D.O(n2)答案:B问题:4.设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为A.5B.6C.7D.9答案:C[解析]本题主要考查的知识点是插入算法。[要点透析]插入算法的基本步骤是：①将结点ai，…，an各后移一位以便腾出第i个位置；②将x置入该空位；③表长加一。问题:5.在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，该指针域用于存放一个指针，此指针指向该结点的A.直接前驱B.直接后继C.开始结点D.终端结点答案:B[解析]本题主要考查的知识点是单链表中的指针域。[要点透析]单链表的一个存储结点包含data和next两个部分，其中，data部分称为数据域，用于存储线性表的一个数据元素；next部分称为指针域或链域，用于存放一个指针，该指针指向本结点所含数据元素的直接后继结点。问题:6.对于一个具有n个元素的线性表，建立其单链表的最小时间复杂度为A.O(log2n)B.O(1)C.O(n2)D.O(n)答案:D[解析]本题主要考查的知识点是单链表的建立。[要点透析]无论采用什么方式建立单链表，都需要扫描这n个元素，边扫描边创建单链表中的结点并链接起来，其时间复杂度为O(n)。本题答案为D。问题:7.在循环链表的一个结点中有个指针。A.1B.2C.0D.3答案:A问题:8.栈和队列共同具有的特点是A.都是先进后出B.都是先进先出C.只允许在端点进行操作运算D.既能先进先出，也能先进后出答案:C[解析]本题主要考查的知识点是栈和队列的特点。[要点透析]栈的特点是先进后出，队列的特点是先进先出，栈只允许在栈顶进行插入和删除运算，而队列只允许在队尾插入和队首删除，共同点是都只能在端点进行运算。问题:9.队列通常采用的两种存储结构是A.顺序存储结构和链式存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构答案:A[解析]本题主要考查的知识点是队列的存储结构。[要点透析]队列可看成是一种运算受限的线性表，它包括两种存储结构：顺序存储结构和链式存储结构，其中顺序存储结构是在内存中开辟一个连续的空间用来存储数据，而链式存储结构采用链表指针来指示数据的存储位置。问题:10.一个栈的输入序列是12345，则下列序列中不可能是栈的输出序列的是A.23415B.54132C.23145D.15432答案:B[解析]本题主要考查的知识点是栈的输出序列。[要点透析]此题可用排除法。栈的出入原则是后进先出。选项B中显示5最先输出，说明其余四个元素已经入栈，其输出序列应为54321。问题:11.一个队列的输入序列是abcd，则队列的输出序列是A.acdbB.abcdC.adcbD.cbda答案:B问题:12.数组A[0…5，0…6]每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续内存单元中，则元素a[5][5]的地址为A.1175B.1180C.1205D.1210答案:A[解析]本题主要考查的知识点是二维数组元素的地址计算。[要点透析]a[5][5]的地址是1000+(5×6+5)×5=1175。问题:13.按照二叉树的定义，具有3个结点的二叉树有A.3利B.4种C.5种D.6种答案:C[解析]本题主要考查的知识点是二叉树的定义。[要点透析]非空二叉树的判定条件是：①有且只有一个根结点；②其余结点分为两个互不相交的集合T1、T2，T1与T2都是二叉树，并且T1与T2有顺序关系(T1在T2之前)。由此可知，3个结点的二叉树有5种。问题:14.在一棵二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序A.都不相同B.完全相同C.先序序列和中序序列相同，而与后序序列不同D.中序序列和后序序列相同，而与先序序列不同答案:B[解析]本题主要考查的知识点是在二叉树遍历中对叶子结点的访问顺序。[要点透析]显然遍历方法中的先序、中序、后序指的是对根的访问顺序，而对于叶子结点都采用先遍历左子树，后遍历右子树。问题:15.深度为6的二叉树最多拥有的结点数目是A.64B.63C.32D.31答案:B[解析]本题主要考查的知识点是二叉树的性质。[要点透析]深度为k(k≥1)的二叉树至多有2k-1个结点。二、填空题问题:1.数据的基本单位是______。答案:数据元素问题:2.所有结点按一对一的邻接关系构成的整体就是______结构。答案:线性问题:3.双向循环链表找前驱结点和后继结点的时间复杂度为______。答案:O(1)问题:4.顺序表定位运算的基本操作是______。答案:比较问题:5.带头结点的双向循环链表L为空的条件是______。答案:(L-＞next==L)'>答案:指针问题:7.在一个用一维数组A[N]表示的循环队列中，该队列中的元素个数最少为______个，最多为______个。答案:ON-1问题:8.在栈中，可进行插入和删除操作的一端称为______。答案:栈顶问题:9.______是指非零元素或零元素的分布有一定规律的矩阵。答案:特殊矩阵问题:10.多个值相同的元素只分配一个存储空间，零元素不分配空间，称为______。答案:压缩存储问题:11.具有10个叶子结点的二叉树中有______个度为2的结点。答案:9问题:12.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。答案:12问题:13.设F是一个森林，B是由F转换得到的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有______个。答案:n+1三、应用题问题:1.有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈(即C第一个且D第二个出栈)的次序有哪几个?答案:满足条件的序列是：CDEBA，CDBEA，CDBAE。问题:2.逻辑结构与存储结构是什么关系?答案:逻辑结构反映数据元素之间的逻辑关系，而存储结构是数据结构在计算机中的表示，它包括数据元素的表示及其关系的表示。一种逻辑结构可以采用一种或几种存储方式来表达数据元素之间的逻辑关系，相应的存储结构称为给定逻辑结构的存储实现或存储映像。问题:3.运算与运算的实现是什么关系?有哪些相同点和不同点?答案:一般地，运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。一个运算的实现是指一个完成该运算功能的程序。相同点：运算与运算的实现都能完成对数据的“处理”或某种特定的操作。不同点：运算只描述处理功能，不包括处理步骤和方法，而运算实现的核心是处理步骤的规定，即算法没计。问题:4.分别画出题图所示二叉树的二叉链表、三叉链表和顺序存储结构。答案:(1)二叉链表示意图(2)三叉链表示意图(3)顺序存储结构爪意图问题:5.给定权值7，18，3，32，5，26，12，8，构造相应的哈夫曼树。答案:所求哈夫曼树如图所示：四、算法 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 题问题:1.设某单链表中，存在多个结点其数据值均为D，试编写一算法统计该类结点的个数。答案:算法如下：intcount(head)Node*head;{Node*p;intn=0;p=headwhile(p!=NULL){if(p-＞data=='D')n++;p=p-＞next;}return(n);}问题:2.以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。答案:本算法的基本思想是：先求左子树的叶子数，再求右子树的叶子数，两者相加就是根结点的叶子数，也就是对应二叉树的叶子数、intleafcount(BinTreeT)//求二叉树T的叶子数{if(T==NULL)leaf=0;//当二叉树为空时,叶子数等于0elseif((T-＞lchild==NULL)//当二叉树仅含一个根结点时,叶子数为1else{L==leafcount(T-＞lchild);//求左子树的叶子数R=leafcount(T-＞rchild);//求右子树的叶子数leaf=L+R;//左、右子树叶子数之和等于二叉树的叶子数}return(leaf);}