数据结构考试题

-1-数据结构试题一、判断题1、栈与队列都是运算受限制的线性表。()2、顺序存储方式的优点是存储密度大，插入、删除效率高。()3、快速排序在任何情况下都比其它排序方法速度快。（）4、将一棵树转换为二叉树表示后,该二叉树的根结点没有右子树。()5、二分查找表元素可以用单链表存储。（）6、数据的逻辑结构与数据元素本身的内容和数据元素的相对位置无关。()7、一棵Huffman树是带权路径长度最短的二叉树，权值较大的外结点离根较远。()8、在用二叉链表示的n个结点的二叉树中，空的链指针有n-1个。()9、n个结点的无向图，若它有n－1条边，则它一定是连通图的。（）10、相邻矩阵表示图所用的存储空间大小与图的边数成正比。（）1、线性表中的数据元素可以是各种各样的，但同一线性表中的数据元素具有相同的特征，因此属于同一数据对象。（）２、顺序表和线性表是同一概念。（）３、循环队列的判空条件是队头指针和队尾指针相等。（）４、二叉树是非线性结构，只能采用链式存储。（）５、拓扑排序是有向无环图的一种应用。（）６、堆排序的效率比直接选择排序高。（）７、有序表的查找要求表必须为有序。（）８、树的度是指结点度的最大值。（）９、在一个图中，所有顶点的度数之和等于图的边数的两倍。（）10、完全二叉树一定是满二叉树。（）二、单项选择题-2-1、对一棵满二叉树，有m个叶子，n个结点，则（）A、n=1+mB、2m=n+1C、n=2m-1D、m-1=2n2、设只含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为()A、2kB、2k+1-1C、2k-1D、2k-13、在已知待排序文件已基本有序的前提下，效率最高的排序方法是（）A、直接插入排序B、直接选择排序C、快速排序D、归并排序4、一个输入序列为1、2、3、4，下面哪一个序列不可能是栈的输出序列？（）A、1，3，2，4B、2，3，4，1C、4，3，1，2D、3，4，2，15、堆的形状是一棵（）。A、二叉排序树B、满二叉树C、不是二叉树D、完全二叉村6、实现对图进行深度优先遍历算法时，用到()数据结构。A、栈B、队列C、树D、A或B7、若一棵二叉树具有15个度为2的结点，度为1的结点5个，则该二叉树的度为0的结点个数是（）。A.20B.16C.15D.不确定8、用顺序表查找元素可以采用的存储结构有()。A、哈希存储B、顺序存储C、链式存储D、B和C9、５个不同的数据元素进行直接插入排序，最多需要进行（）次比较。A、８B、１０C、１５D、２５10、链式存储的存储结构每个结点所分配的存储空间（）A、只有一部分，存放表示结点间关系的指针B、只有一部分，存放结点值C、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针D、分两部分，一部分存放结点值，另一部分存放结点所占单元数11、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）。A、s→next=p→next;p→next=sB、p→next=s;s→next=qC、p→next=s→next;s→next=pD、q→next=s;s→next=p12、在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为front和rear，-3-则当前队列中的元素个数是（）。A.(front-rear+1)%mB.(rear-front+1)%mC.(front-rear+m)%mD.(rear-front+m)%m1、最佳二叉排序树是（）A、关键码个数最少的二叉排序树B、平均比较次数最少的二叉排序树。C、任意一棵二叉排序树。D、单支二叉排序树。2、设二叉树的根结点的层数为1，则第K层最多有（）个结点。A、2kB、2k-1C、2k+1-1D、2k-13、快速排序在（）情况下最不利于发挥其长处。A、要排序的数据已基本有序B、要排序的数据量太大C、要排序的数据中含有多个相同值D、要排序的数据个数为奇数4、若队头指针f指向真正的队头元素位置，则在循环队列中删除一个元素时，需要做的操作是（）。A、队尾指针减1，取得队尾指针所指的元素B、队头指针加1，取得队头指针所指的元素C、取得队头指针所指的元素，队头指针加1D、取得队尾指针所指的元素，队尾指针减15、下列排序方法中，哪一种方法的比较次数与记录的初始排列状态无关？（）A、直接插入排序B、冒泡排序C、快速排序D、直接选择排序6、实现对图进行广度优先遍历算法时，用到()数据结构。A、栈B、队列C、树D、A或B7、若一棵二叉树有16个度为0的结点，5个度为1的结点，则该二叉树的度为2的结点个数是（）。A.20B.16C.15D.不确定8、顺序查找法元素能采用的存储结构为()。A、哈希存储B、顺序存储或链式存储C、压缩存储D、索引存储9、排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。-4-A、起泡排序B、选择排序C、基数排序D、插入排序10、单链表的存储密度（）A、大于1B、等于1C、小于1D、不能确定11、在一个单链表中，两个指针q和p，q所指元素是p所指元素前趋的条件是（）。A、p→next=q→nextB、p=qC、p→next=qD、q→next=p12、在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。A.、(front-rear+1)%mB、(rear-front+1)%mC、(front-rear+m)%mD、(rear-front+m)%m三、填空题1、在散列表中，若同义词发生地址争夺的现象称为，非同义词发生地址争夺的现象称为。2、算法的五个重要特征是：、、、、。3、设s[0..maxsize-1]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是_____________，栈为满的条件是_____________________。4、线性结构中的元素之间存在的关系，树型结构中元素之间存在的关系。在树型结构中，根结点前趋结点，其余每个结点有且仅有个前趋结点。5、数据结构主要研究数据的、和。6、将数据元素2,4,6,8,10,12,14,16,18,20依次存放于一个一维数组中，然后采用折半查找方法查找元素12，被比较过的数据元素依次为_________。7、设二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始地址为1000，则数组A的体积（即存储量）为。1、存储结构的四种基本类型分别是、、、。2、树型结构中元素之间存在的关系。在树型结构中，根结点前趋结点，其余每个结点有且仅有个前趋结；叶子结点后继结点。3、n个顶点的连通图的生成树有条边。-5-4、评价算法的标准有正确性、、和高效性。5、一个有向图G中若有弧〈vi，vj〉、〈vj，vk〉和〈vi，vk〉，则在图G的拓扑序列中，顶点vi，vj和vk的相对位置为。6、查找表按其所涉及的运算不同分为查找表和查找表。7、在散列表中查找时，首先计算，若有冲突发生，则伴随有。8、设有顺序存储的关键字序列10、13、20、28、29、41、72、85、94，当用二分法检索关键字为72的结点时，需要先后比较的关键字有，检索关键字为25的结点时，需要比较的关键字有。四、完成题1、什么是哈夫曼树？假设用于通信的电文由8个字母组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10,试设计哈夫曼编码。2、堆的定义？叙述对一批元素进行堆排序的具体过程。3、已知中根次序为BDCEAFGH，后根次序为DECBHGFA，画出此二叉树，并写出其前序遍历。4、已知一个无向图的顶点集为：{A，B，C，D，E}，其邻接矩阵如下：A00101B00011C10001D01001E11110画出该图的图形并写出从E出发对图进行深度优先遍历序列。5、设散列表的长度m=13；散列函数为H(K)=Kmodm，给定的关键码序列为19、14、23、01、68、20、84、27、55、11，试叙述线性探测法解决冲突的思想，并画出用线性探测法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法的查找成功时的平均查找长度ASLsucc=？-6-１、按照普里姆（Prim）算法，求出下图的一棵最小生成树。2、已知一个无向图的顶点集为：{A，B，C，D，E}，其邻接矩阵如下：A00101B00011C10001D01001E11110画出该图的图形并写出从E出发对图进行广度优先遍历序列。3、堆的定义？叙述对一批元素进行堆排序的具体过程。4、已知中根次序为BDCEAFGH，先根次序为ABCDEFGH，画出此二叉树，并写出后序遍历。5、设散列表的长度m=13；散列函数为H(K)=Kmodm，给定的关键码序列为19、14、23、01、68、20、84、27、55、11，试叙述链地址法解决冲突的思想，并画出用链地址法解决冲突时所构造的散列表。并求出在等概率情况下，这种方法查找成功时的平均查找长度ASLsucc=？五、算法设计题1、已知两个按元素递增有序的单链表Pa和Pb，现将其合并为一个递减有序的单链表并用Pc指向。设Pa、Pb均附加有头结点，表中元素类型为整型，具体语言描述如下，写算法完成相应的运算。-7-Typedefstructlink{intdata;structlink*next;}listnode;typedeflistnode*linklist;linklistPa，Pb，Pc;2、已知二叉树中的结点类型用BiTNode表示，被定义描述为：TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;BiTreeT；其中data为结点值域，LChild和RChild分别为指向左、右孩子结点的指针域，编写算法，求出二叉树中2度结点个数。1、已知两个按元素递增有序的单链表Pa和Pb，现将其合并为一个递增有序的单链表并用Pc指向。设Pa、Pb均附加有头结点，表中元素类型为整型，具体语言描述如下，写算法完成相应的运算。typedefstructlink{intdata;structlink*next;}listnode;typedeflistnode*linklist;linklistPa，Pb，Pc;2、已知二叉树中的结点类型用BiTNode表示，被定义描述为：TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;BiTreeT；其中data为结点值域，LChild和RChild分别为指向左、右孩子结点的指针域，写一算法，求出二叉树中的叶子结点个数。