数据构造考试题库含答案.docx

数据构造考试题库含答案选择题第一章绪论1.数据构造这门学科是针对什么问题而产生的AA、针对非数值计算的程序设计问题B、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2.数据构造这门学科的研究内容下面选项最准确的是DA、研究数据对象和数据之间的关系B、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据构造考了90分，那么下面关于数据对象、数据元素、数据项描绘正确的是CA、某班级的学生成绩表是数据元素，90分是数据项B、某班级的学生成绩表是数据对象，90分是数据元素C、某班级的学生成绩表是数据对象，90分是数据项D、某班级的学生成绩表是数据元素，90分是数据元素4.*数据构造是指A。A、数据元素的组织形式B、数据类型C、数据存储构造D、数据定义5.数据在计算机存储器内表示时，物理地址与逻辑地址不一样，称之为C。A、存储构造B、逻辑构造C、链式存储构造D、顺序存储构造6.算法分析的目的是CA、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改良D、分析算法的易懂性和文档型性7.算法分析的主要方法A。A、空间复杂度和时间复杂度B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性8.计算机内部处理的基本单元是BA、数据B、数据元素C、数据项D、数据库9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵敏性上，链式存储比顺序存储要B。A、低B、高C、一样D、不好讲10.算法的时间复杂度取决于CA、问题的规模B、待处理数据的初始状态C、问题的规模和待处理数据的初始状态D、不好讲11.数据构造既研究数据的逻辑构造，又研究物理构造，这种观点B。A、正确B、错误C、前半句对，后半句错D、前半句错，后半句对12.在数据构造中，从逻辑上能够把数据构造分成CA、动态构造和静态构造B、紧凑构造和非紧凑构造C、线性构造和非线性构造D、内部构造和外部构造13.线性表的顺序存储构造是一种()的存储构造，线性表的链式存储构造是一种A存储构造。A、随机存取B、顺序存取C、索引存取D、散列存取14.*下列程序的时间复杂度是Afor(i=1;iA、O(n2)B、O(n)C、O(2n)D、O(2n2)15.*下列程序的空间复杂度是Afor(i=1;i5.在单链表中设置头结点的作用是()。A、单链表定义罢了B、指定表的起始位置C、为双向链表做准备D、为循环链表做准备6.根据线性表链式存储构造中每一个结点包含的指针数，将线性链表分成CA、单链表与循环链表B、单链表与十字链表C、单链表与双链表D、循环链表与多链表7.链接存储的特点是利用什么来表示数据元素之间的逻辑关系AA、引用B、串联C、挂接D、指派8.已知指针p指向单链表L中的某结点，则删除其后继结点的语句是DA、p=B、p=nullC、=null9.*在单链表L中，指针p所指结点有后继结点的条件是BA、p=B、!=nullC、=null10.*在单链表p结点之后插入s结点的操作是CA、=s;=;C、=;=s;D、=p;=s;第三章栈和队列1.栈、队列通常采用两种存储构造，它们是(B)A、散列方式和索引方式B、顺序存储构造和链式存储构造C、链表存储构造和数组D、线性和非线性存储构造2.一个栈入栈序列是a,b,c,d,则栈输出序列不可能是(C)A、d,c,b,aB、c,d,b,aC、d,c,a,bD、a,b,c,d3.判定顺序栈最多结点数为m为栈满的条件是DA、top=0B、top!=mC、top!=0D、top=m4.栈存取数据原则或栈特点是BA、后进后出B、后进先出C、先进先出D、随意进出5.*经过下面栈运算后，x的值是AInitStack(s);Push(s,d);Push(s,e);Pop(s,x);Pop(s,x);GetTop(s,x);A、dB、eC、xD、s6.一个队列的进队序列为：a，b，c，d，则出队序列是：(A)A、a，b，c，dB、d，c，b，aC、a，d，c，bD、c，b，d，a7.循环队列为空队列的条件是：DA、=0B、Q.rear+1)%MaxSize=C、=0D、=8.在存储构造上，假如用带头节点单链表实现队列假定front和rear分别为队首和队尾指针，则删除一个结点的操作为A。A、B、rear=C、rear=D、front=9.栈和队列共同点是CA、先进后出B、先进先出C、允许在端点处进行操作线性表D、无共同点10.插入和删除只能在一端进行的线性表是BA、循环队列B、栈C、队列D、循环栈11.插入和删除分别在两端端进行的线性表是CA、循环队列B、栈C、队列D、循环栈12.循环队列为满队列的条件是：BA、=0B、Q.rear+1)%MaxSize=C、=0D、=第四章串1.关于串的叙述，错误的是：BA串是字符有限序列B空串是由空格构成的串C形式匹配是串的重要运算D串有用顺序、链式两种存储方式2.串长度是指BA串所含不同字母数目B串所含字符数目C串所含不同字符数目D串所含非空格字符数目3.*若串S=database,其子串数目是B。A16B37C8D364.设串S1是串S子串，则求S1在S中定位运算称为BA求子串B串匹配C连接D求串长5.设有串s1=welcometozdsoftcolleage!和s2=so,那么s2在s1中的索引位置是CA12B14C13D106.*若串S=“software“,其子串的数目是B。A8B37C36D9第五章数组和广义表第六章树和二叉树1.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为B个。A.15B.16C.17D.472.假定一棵三叉树的结点数为50，则它的最小高度为C。A.3B.4C.5D.63.在一棵二叉树上第4层的结点数最多为D。A.2B.4C.6D.84.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R1.n，结点Ri若有左孩子，其左孩子的编号为结点B。A.R2i+1B.R2iC.Ri/2D.R2i-15.设n,m为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是B。A.n在m右方B.n在m左方C.n是m的祖先D.n是m的子孙6.下面叙述正确的是D。A.二叉树是特殊的树B.二叉树等价于度为2的树C.完全二叉树必为满二叉树D.二叉树的左右子树有次序之分7.现有一深度为5的二叉树，请问其最多有D个结点。A.32B.5D.318.现有一深度为4的二叉树，请问其最多有A个结点。A.15B.169.在一棵二叉排序树上按B遍历得到的结点序列是一个有序序列。A.先序B.中序C.后序D.头序10.在一棵二叉树中，度为0的结点数为n0，度为2的结点数为n2，则n=CA.n+1B.n+2+1+111.由三个结点构成的二叉树，共有B种不同的形态。A.4B.512.一棵含有n个结点的树，A形态到达最大深度。A.单支树B.二叉树C.三叉树叉树13.不含任何结点的空树C。.是一棵树;.是一棵二叉树;.是一棵树也是一棵二叉树;.既不是树也不是二叉树14.二叉树是非线性数据构造，所以(C)。.它不能用顺序存储构造存储;.它不能用链式存储构造存储;.顺序存储构造和链式存储构造都能存储;.顺序存储构造和链式存储构造都不能使用15.具有n(n>0)个结点的完全二叉树的深度为(C)。.log2(n).log2(n).log2(n)+1.log2(n)+116.在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为D个。A.4B.517.有关二叉树下列讲法正确的是BA二叉树的度为2B一棵二叉树的度能够小于2C二叉树中至少有一个结点的度为2D二叉树中任何一个结点的度都为218.在完全二叉树中，若一个结点是叶结点，则它没C。A左子结点B右子结点C左子结点和右子结点D左子结点，右子结点和兄弟结点19.在下列情况中，可称为二叉树的是BA每个结点至多有两棵子树的树B.哈夫曼树C每个结点至多有两棵子树的有序树D.每个结点只要一棵右子树第七章图1.图的深度优先遍历类似于二叉树的A。A先序遍历B中序遍历C后序遍历D层次遍历2.已知一个图如下图，若从顶点a出发按深度优先遍历，则可能得到的一种顶点序列为CAabecdfBacfebdCaebcfdDaedfcb3.若从无向图的任意一个顶点出发进行一次深度优先搜索能够访问图中所有的顶点，则该图一定是B图。A非连通B连通C强连通D有向4.在一个图中，所有顶点的度数之和等于所有边数的C倍。A1/2B1C2D35.在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的B倍。A1/2B1C2D36.一个有N个顶点的有向图最多有B条边。ANBN(N-1)CN(n-1)/2D2N7.具有4个顶点的无向完全图有A条边。A6B12C18D208.具有6个顶点的无向图至少有A条边才能确保是一个连通图。A5B6C7D89.对于一个具有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是DANB(N-1)2CN-1DN*N10.一个具有N个顶点的无向图中，要连通全部顶点至少要C条边ANBN+1CN-1DN/211.*已知图的邻接矩阵如下图，则从顶点0出发按深度优先遍历的结果是C。?0100011101100001011010110011001000110010011011110A0243156B0136542C0134256D036154212.已知图的邻接表下列图所示，则从顶点0出发按广度优先遍历的结果是，按深度优先遍历的结果是D。A0132B0231C0321D012313.已知图的邻接表下列图所示，则从顶点0出发按广度优先遍历的结果是，按深度优先遍历的结果是。A0132B0231C0321D012314.当在一个有序的顺序表上查找一个数据时，既可用折半查找，可以用顺序查找，但前者比后者的查找速度C。A必定快B不一定C在大部分情况下要快D取决于表递增还是递减15.折半查找有序表4，6，10，12，20，30，50，70，88，100。若查找表中元素58，则它将依次与表中A比拟大小，查找结果是失败。A20，70，30，50B30，88，70，50C20，50D30，88，50第八章查找1.顺序查找法合适于存储构造为B的线性表。A散列存储B顺序存储或链式存储C压缩存储D索引存储2.在查找经过中，若同时还要增、删工作，这种查找称为B。A、静态查找B、动态查找C、内查找D、外查找3.索引顺序表的特点是顺序表中的数据A。A、有序B、无序C、块间有序D、散列4.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为CA、nB、n/2C、(n+1)/2D、(n-1)/25.*将10个元素散列到1000000个单元的哈希表，则C产生冲突。A、一定会B、一定不会C、仍可能会D、以上都不对6.*散列表的地址区间为016，散列函数H(k)=k%17，采用线性探测法解决地址冲突，将关键字26、25、72、38、1、18、59依次存储到散列表中。元素59存放在散列表中的地址为AA、8B、9C、10D、117.设有序表的关键字序列为1,3,9,12,32,41,45,62,75,77,82,95,100，当采用二分查找法查找值为82的节点时，经C次比拟后查找成功。A、1B、2C、3D、48.设有100个元素，用折半查找法进行查找时，最大、最小比拟次数分别时AA、7,1B、6,1C、5,1D、8, 1