数据结构大量练习(免费提供).doc

题型1、选择题 20道 40分2、填空题 10道 20分3、判断题 10道 10分4、简答题 5道 30分一、选择题1、 在一棵二叉树上第5层的结点数最多是_。 A）8 B）16 C）32 D）152、 以下数据结构中不属于线性数据结构的是_。A）队列 B）线形表 C）二叉树 D）栈3、 对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为_。A）N+1 B）N C）（N+1）/2 D）N/24、 下列关于栈的叙述中正确的是_。A）在栈中只能插入数据 B）在栈中只能删除数据 C）栈是先进先出线性表 D）栈是先进后出线形表5、 下列叙述中正确的是_。A）线形表是线形结构 B）栈和队列是非线形结构 C）线形链表是非线形结构 D）二叉树是线形结构6、 在下列选项中，哪个不是一个算法一般应该具有的基本特征_。A）确定性 B）可行性 C）无穷性 D）拥有足够情报7、 7、设有下列二叉树： 对此二叉树中序遍历的结果为_。A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA8、 在单链表中，增加头结点的目的是_。A）方便运算的实现 B）使单链表至少有一个结点 C）标识表结点中首结点的位置 D）说明单链表是线形表的链式存储实现9、 数据的存储结构是指_。A）存储在外存中的数据 B）数据所占的存储空间量 C）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示10、 下列关于栈的描述中错误的是_。A）栈是先进后出线形表 B）栈只能顺序存储 C）栈具有记忆作用 D）对栈的插入和删除操作中，不需要改变栈底指针11、 下列对于线性链表的描述中正确的是_。A）存储空间不一定是连续，且各元素的存储顺序是任意的 B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C）存储空间必须连续，且前件元素一定存储在后件元素的前面 D）存储空间必须连续，且各元素的存储顺序是任意的下列关于栈的描述正确的是_。A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素 C）栈是特殊的线形表，只能在一端插入和删除元素 D）栈是特殊的线形表，只能在一端插入元素，而在另一端删除元素12、 下列描述中正确的是_。A）线形链表是线形表的链式存储结构 B）栈和队列是非线形结构 C）双向链表是非线形结构 D）只有根结点的二叉树是线形结构13、 在深度为7的满二叉树中，叶子结点的个数为_。A）32 B）31 C）64 D）6314、 按照后进先出原则组织数据的数据结构是_。A）队列 B）栈 C）双向链表 D）二叉树15、 对如下二叉树进行后序遍历的结果为_。A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA16、 在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为_。A）63 B）64 C）6 D）717、 下列叙述中正确的是_。A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的空间复杂度大，则其时间复杂度也必定小 C）一个算法的时间复杂度大，则其空间复杂度也必定小 D）上述三种说法都不对18、 对下列二叉树进行中序遍历的结果是_。A）ACBDFEG B）ACBDFGE C）ABDCGEF D）FCADBEG19、 下列对队列的叙述正确的是_。A）队列属于非线形表 B）队列按“先进后出”原则组织数据 C）队列在队尾删除数据 D）队列按“先进先出”原则组织数据20、 某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为_。A）n+1 B）n-1 C）2n D）n/221、 对下列二叉树进行前序遍历的结果为_。A）DYBEAFCZX B）YDEBFZXCA C）ABDYECFXZ D）ABCDEFXYZ22、 冒泡排序在最坏情况下的比较次数是_。A）n(n+1)/2 B）nlog2n C）n(n-1)/2 D）n/223、 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为_。A）219 B）221 C）229 D）23124、 设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为_。A）349 B）350 C）255 D）35125、 一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是_。A）12345ABCDE B）EDCBA54321 C）ABCDE12345 D）54321EDCBA26、 下列叙述中正确的是_。A）循环队列中有队头和队尾两个指针，因此，循环队列是非线形结构B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化D）循环队列中元素的个数是由队头指针和队尾指针共同决定27、 算法的空间复杂度是指_。A）算法程序的长度 B）算法程序中的指令条数 C）算法程序所占的存储空间 D）算法执行过程中所需要的存储空间28、 下列关于队列的叙述中正确的是_。A）在队列中只能插入数据 B）在队列中只能删除数据 C）队列是先进先出的线形表 D）队列是先进后出线形表29、 已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。A）cedba B）acbed C）decab D）deabc30、 栈和队列的共同点是_。A）都是先进后出 B）都是先进先出 C）只允许在端点处插入和删除元素 D）没有共同点31、 数据结构中，与所使用的计算机无关的是数据的_。A）存储结构 B）物理结构 C）逻辑结构 D）物理和存储结构32、 栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是_。33、 用链表表示线性表的优点是_。A）便于插入和删除操作 B）数据元素的物理顺序和逻辑顺序相同 C）花费的存储空间较顺序存储少 D）便于随机存取34、 n个顶点的强连通图的边数至少有_。A）n-1 B）n(n-1) C）n D）n+135、 非空的循环单链表head的尾结点p满足（ ）。A）p-next=head B）p-next=NULL C）p=NULL D）p= head36、 设单链表中结点的结构为（data，next）。已知指针p所指结点不是尾结点的，若在*p之后插入结点*s，则应执行下列哪一个操作？A s-next=p; p-next=s;B s-next=p-next; p-next=s;C s-next=p-next; p=s;D p-next=s; s-next=p;37、 设单链表中结点的结构为（data，next）。若想摘除结点*p的直接后继，则应执行下列哪一个操作？A p-next=p-next -next;B p=p-next; p-next=p-next -next;C p-next=p-next;D p =p-next -next;38、 下面关于线性表的叙述中，错误的是哪一个？ A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。39、 设二叉树的根为第一层，则第i层上结点数最多为：_A 2iB 2i+1C 2i-1D 2i-140、 与线性表的链接存储不相符的特性是：_A 便于插入、删除运算B 存储空间动态分配C 需要连续存储空间D 只能顺序查找41、 当利用大小为n的数组顺序存储一个栈时，假定用top=0表示栈空，则向这个栈插入一个元素时，首先应执行 语句修改top指针。A、top+； B、top一 一； C、top =0 ； D、 top；42、 若让元素1，2，3依次进栈，则出栈次序不可能出现 种情况。A 、3，2，1 B、 2，1，3 C、 3，1，2 D、1，3，243、 对于队列操作数据的原则是（ ）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序44、 n 个顶点的连通图的生成树有 条边。A、 n-1 B、n C、n+1 D、 045、 图的广度优先搜索类似于树的 次序遍历。 A、 先根 B、 中根C、 后根 D、 层次46、 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构47、 一个一维数组第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 （A）110 （B）108 （C）100 （D）12048、 向一个有126个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 个元素（A）8 （B）63.5 （C）63 （D）749、 链表是一种采用 存储结构存储的线性表；（A）顺序 （B）链式 （C）星式 （D）网状50、 线性表在 情况下适用于使用链式结构实现。（）需经常修改中的结点值 （）需不断对进行删除插入 （）中含有大量的结点 （）中结点结构复杂51、 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为 i n-i n-i+1 不确定52、 数据的存储结构包括顺序、_、索引和散列四种基本类型。A）向量B）数组 C）集合D）链接53、 不带头结点的单链表head为空的判别条件是 。 （A）head= =NULL (B) headnext= =NULL (C) headnext= =head (D) head !=NULL54、 带头结点的单向链表head为空的判别条件是 。（A） head= =NULL （B）headnext= =NULL (C) headnext= =head (D) head !=NULL55、 head所指非空循环单向链表的尾结点（由指针p描述）满足 。（A）Pnext=NULL （B）PNULL (C) Pnext=head (D) P=head56、 栈的插入和删除操作在 进行。A、 栈顶 B、 栈底 C、 任意位置 D、 指定位置二、填空题1、 算法的复杂度主要包括_时间_复杂度和空间复杂度。2、 顺序存储方法是把逻辑上相邻的结点存储在物理位置_相邻_的存储单元中。3、 在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、_中序_遍历和后序遍历。4、 数据结构包括数据的逻辑结构、数据的 存储结构_以及对数据的操作运算。5、 5、某二叉树中度为2的结点有18个，则该二叉树中有 19 个叶子结点。6、 数据结构分为逻辑结构和存储结构，循环队列属于_逻辑_结构。7、 算法复杂度主要包括时间复杂度和_空间_复杂度。8、 一棵二叉树第六层（根结点为第一层）的结点数最多为_32_个。9、 按先进后出原则组织数据的数据结构是_栈_。10、 数据结构分为线性结构和非线性结构，带链的队列属于_线形结构_。11、 在深度为7的满二叉树中，度为2的结点个数为_63_。12、 对下列二叉树进行中序遍历的结果为_ACBDFEHGP_。13、 设某循环队列的容量为50，头指针front=5（指向队头元素的前一位置），尾指针rear=29（指向队尾元素），则该循环队列中共有_24_个元素。14、 深度为5的满二叉树有_16_个叶子结点。15、 对下列二叉树进行中序遍历的结果是_DBXEAYFZC_。16、 数据结构包括数据的_逻辑_结构和数据的存储结构。17、 栈的基本运算有三种：入栈、退栈和_读栈顶元素_。 。18、 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ ，中序遍历的结果是EBCDAFHIGJ,则这棵树的后序遍历结果是 EDCBIEJGFA 。19、 一棵高度为5的满二叉树中的结点数为 31 个。20、 常用的图的二种存储结构为 邻接矩阵 和 邻接表 21、 栈是特殊的线性表，其运算遵循_ 后进先出 _的原则。 22、 一棵树中，除根结点以外的每个结点均有 _1_ 个双亲节点。23、 一个算法的复杂度可分为 时间 复杂度和 空间 复杂度。24、 在一个循环队列中，队首指针指向队首元素的 前一个 位置。25、 在具有n个单元的循环队列中，队满时共有 n-1 个元素。26、 在双向链表中每个结点包含有两个指针域，一个指向其 前驱 结点，另一个指向其 后继 结点。27、 若无向图邻接矩阵中的Aij的值为1，则Aj i 的值为 1 。三、判断题（T）1、从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。（F）2、线性表的逻辑顺序与物理顺序总是一致的。（F）3、在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（F）4、由二叉树的前序序列和后序序列一定能唯一确定一颗二叉树。（F）5、循环链表不是线性表。（F）6、线性表的特点是每个元素都有一个前驱和一个后继。（T）7、高度为4的完全二叉树最少有 8 个结点。（F）8、 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（T）9、 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （F）10、二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （T）11、对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i1个结点。 （F）1