数据结构课程学位考试试题（答案在题后）.doc

数据结构课程学位考试试题（参考答案在题后） 判断题：判断下列各小题叙述的正误。对，在题号后的括号内填入“√ ”；错，在题号后填入“ ×”。 1、数据的最小单位是数据项。………………………….( √) 2、多重表文件中主索引为非稠密索引，次索引为稠密索引。……….( √ ) 3、通常数据结构在计算机中有四种不同的表示方法分为顺序存储结构、链式存储结构、索引存储、文件存储。……….…….( × ) 4、算法具有输入、输出、可行性、稳定性、有穷性五个特性。……………….( × ) 5、数据的基本单位是数据项。………………………….( × ) 6、算法的复杂度分为时间复杂度和效率复杂度。………….( × ) 7、性质相同的数据元素的集合成为数据对象。…………….( √ ) 8、所有结点按1对1的邻接关系构成的整体就是集合结构。……….( × ) 9、散列文件不能顺序存取、只能按关键字随机存取。…………….( √ ) 10、数据的基本单位是数据元素。………………………….( √ ) 11、B+树中的K个孩子的结点必有K个关键字。…… ….( √) 12、B+树中的K个孩子的结点必有K个关键字。……….…….( √ ) 13、倒排表的索引项中没有头指针和链表长度项。………….( √ ) 14、磁带是顺序存取的外存储设备。……………………………………….( × ) 15、索引文件只能是磁盘文件。………………………………(√ ) 16、顺序文件只适宜于顺序存取。………………………..………….( × ) 17、磁带是顺序存取的外存储设备。……………………………….( × ) 18、线性的数据结构可以顺序存储，也可以链接存储。……………………………….( √) 20、散列文件不能顺序存取、只能按关键字随机存取。….…….( √ ) 21、栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。（√） 22、循环链表从任何一个结点出发，都能访问到所有结点.......单链表从任何一个结点出发，都能访问到所有结点…….( ×) 24、线性表采用顺序存储表示时，必须占用一片连续的存储单元。(√ ) 25、循环链表从任何一个结点出发，都能访问到所有结点…….( √ ) 26、设串S的长度为n,则S的子串个数为n(n+1)/2… …O(n) ….( ×) 29、线性表中的每个结点最多只有一个前驱和一个后继………… …….( √ ) 30、顺序表上做删除和插入运算时的平均时间复杂度都是O(n) .( √ ) 31、具有n个结点的完全二叉树的高度为┖2log2n┘+1…………….( ×) 32、在只有度为0和度为2的结点的二叉树中，设度为0的结点有n0个，度为2的结点有n2个，则有n0=n2+1…………….( √ ) 33、循环队列判断队列为满的条件是sq-front+1= =sq-rear。……(× ) 34、数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。……….( √ ) 35、若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能惟一地确定一棵二叉树。.... (√ ) 36、有n个结点的不同的二叉树有n！棵。………………………….……….( × ) 37、一般树和二叉树的结点数目都可以为0。................( ) 38、循环队列判断队列为空的条件是sq-front= =sq-rear。……(√ ) 39、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是3。.( √) 40、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个， 度为k的结点有nk个，则有n0=nk+1……………….( × ) 41、一个连通图的生成树，是含该连通图的全部顶点的一个极小连通子图.( √ ) 42、在二叉树的第 i 层上至多有2i-1 个结点……….( √ ) 43、先根遍历树和先根遍历与该树对应的二叉树，其结果不一样。... (× ) 44、由树转化成二叉树，其根的右子女指针总是空的……….( √ ) 45、网络的最小代价生成树是唯一的………………………….……….( × ) 46、深度优先有哪些信誉好的足球投注网站遍历类似于树的先根遍历，它所用到的数据结构是队列。(×) 47、在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中 序遍历和后序遍历，则具有相同的结果。………(√) 48、对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。………..………….( √ ) 49、图的深度优先有哪些信誉好的足球投注网站类似于树的先根次序遍历………….