《数据结构与算法》期末考试复习题库（含答案）

PAGEPAGE1《数据结构与算法》期末考试复习题库（含答案）一、单选题1.从一个具有n个结点的单链表中查找值为x结点,在查找成功情况下,需平均比较()个结点。A、nB、n/2C、(n-1)/2D、(n+1)/2答案：D2.在逻辑上可以把数据结构分成（）。A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构答案：C3.链式存储结构所占存储空间（）A、分两部分，一部分存储结点的值，另一部分存放表示结点间关系的指针B、只有一部分，存放结点的值C、只有一部分，存储表示结点间关系的指针D、分两部分，一部分存放结点的值，另一部分存放结点所占单元数答案：A4.算法能正确的实现预定功能的特性称为算法的（）。A、正确性B、易读性C、健壮性D、高效性答案：A5.队列是限定在（）进行操作的线性表。A、中间B、队首C、队尾D、端点答案：D6.下列算法的时间复杂度是（）for(i=0;i<n;i++)for(j=0;j<n;j++)C[i][j]=i+j;A、O(2)B、O(n)C、O(log2n)D、O(n)答案：D7.带头结点的单链表head为空的判定条件是()。A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL答案：B8.计算机算法必须具备输入、输出和（）。1A、计算方法B、排序方法C、解决问题的有限运算步骤D、程序设计方法答案：C9.下面程序的时间复杂为（）。for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}A、O(n)B、O(n)C、O(n）D、O(n)答案：B10.同一队列内各元素的类型()。A、必须一致B、不能一致C、可以不一致D、不限制答案：A11.冒泡排序的方法对n个数据进行排序，第一趟排序共需要比较（）次。A、1B、2C、n-1D、n答案：C12.具有64个结点的完全二叉树的深度为()A、5B、6C、7D、8答案：C13.二叉树按某种顺序线索化后，任一结点均有指向其前趋和后继的线索，这种说法()。A、正确B、错误C、不确定D、不存在答案：B14.数据在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（）。A、存储结构B、逻辑结构C、顺序存储结构D、链式存储结构答案：C15.下列4种基本逻辑结构中，数据元素之间关系最弱的是（）。A、集合B、线性结构C、树形结构D、图形结构答案：A16.队列是一个(C)线性表结构。A、不加限制的B、推广了的C、加了限制的D、非答案：C17.在一个长度为n的顺序存储线性表中，删除第i个元素(1...i...n)时，需要从前向后依次前移()个元素。A、n-iB、n-i+1C、n-i-1D、i答案：A18.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）个。A、45B、15C、16D、31答案：C19.就平均性而言，下面最好的内排序方法是（）排序法A、冒泡排序B、快速排序C、选择排序D、希尔排序答案：B20.队列中的元素个数是()。A、不变的B、可变的C、任意的D、0答案：B21.在按行优先顺序存储的三元组表中,下述陈述错误的是()。A、同一行的非零元,是按列号递增次序存储的B、同一列的非零元,是按行号递增次序存储的C、三元组表中三元组行号递增的D、三元组表中三元组列号递增的答案：D22.某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，则其后序遍历序列是（）。A、gdbehfcaB、abcdefghC、gdbaefchD、ghbcdefa答案：A23.动态查找包括（）查找。A、顺序表B、二叉排序树C、有序表D、索引顺序表答案：B24.下列关于算法的说法,正确的是()。A、程序一定是算法。B、算法的可行性是指指令不能有二义性。C、算法可以没有输入但必须有1个以上的输出。D、算法必须是用计算机语言描述的。答案：C25.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。A、q=p.next；p.data=q.data；p.next=q.next；B、q=p.next；q.data=p.data；p.next=q.next；C、q=p.next；p.next=q.next；D、q=p.next；p.data=q.data；答案：A26.在下列链表中不能从当前结点出发访问到其余各结点的是()。A、双向链表B、单循环链表C、单链表D、双向循环链表答案：C27.经过下列栈的运算后,x的值是()。InitStack(s)(初始化栈);Push(s,a);Push(s,b);ReadTop(s);Pop(s,x);A、B、C、1D、0答案：B28.在一个长度为n的顺序存储线性表中，向第i个元素(1...i...n)之前插入一个新元素时，需要从后向前依次后移()个元素。.A、n-iB、n-i+1C、n-i-1D、i答案：B解析：；29.非线性结构中的每个结点()。A、无直接前趋结点B、无直接后继结点C、只有一个直接前趋结点和一个直接后继结点D、可能有多个直接前趋结点和多个直接后继结点答案：D30.无向图顶点v的度是关联于该顶点（）的数目。A、顶点B、边C、序号D、下标答案：B31.对线性表进行二分查找时，要求线性表必须（）。A、以顺序方式存储B、以链接方式存储，且结点按关键字有序排序C、以链接方式存储D、以顺序方式存储，且结点按关键字有序排序答案：D32.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为()。A、2B、2-1C、2D、h+1答案：B33.数据结构通常是研究数据的（）及它们之间的相互关系。A、存储结构和逻辑结构B、存储和抽象C、联系和抽象D、联系与逻辑答案：A判断题1.链队列在一定范围内不会出现队满的情况。A、正确B、错误答案：A2.一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。A、正确B、错误答案：B3.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。A、正确B、错误答案：B4.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。A、正确B、错误答案：A5.如果二叉树中某结点的度为1，则说该结点只有一棵子树。A、正确B、错误答案：A6.在完全二叉树中,若一个结点没有左孩子,则它必然是叶子结点。A、正确B、错误答案：A7.(10)具有n个叶子结点的哈夫曼树共有2n-1个结点。A、正确B、错误答案：A8.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。A、正确B、错误答案：A9.在C或C++语言中设顺序栈的长度为MAXLEN，则top=MAXLEN时表示队满。A、正确B、错误答案：B10.1.哈夫曼树的结点个数不可能是偶数。A、正确B、错误答案：A11.循环链队列中无溢出现象。A、正确B、错误答案：B12.递归定义就是循环定义。A、正确B、错误答案：B13.顺序队和循环队关于队满和队空的判断条件是一样的。A、正确B、错误答案：B14.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。A、正确B、错误答案：A15.空栈就是所有元素都为0的栈。A、正确B、错误答案：B16.栈和队列都是顺序存储的线性结构。A、正确B、错误答案：B17.哈希表是一种将关键字转换为存储地址的存储方法。A、正确B、错误答案：A18.顺序存储方式的优点是存储密度大，插入、删除效率高。A、正确B、错误答案：B19.子串的定位运算称为模式匹配。A、正确B、错误答案：A20.栈一定是顺序存储的线性结构。A、正确B、错误答案：B21.所谓时间复杂度,是指最坏情况下,估算算法执行时间的一个上界。编程题如下A、正确B、错误答案：A22.串的堆分配存储是一种动态存储结构。A、正确B、错误答案：A23.8.为了方便插入和删除,可以使用双向链表存放数据。A、正确B、错误答案：A24.图的遍历要比树的遍历复杂，因为图中一般存在回路，也就是在访问了某个顶点后，可能会沿着某条路径再次回到该顶点。A、正确B、错误答案：A25.顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。A、正确B、错误答案：B26.1.消除递归一定需要使用栈。A、正确B、错误答案：B27.“DT”是“DATA”的子串。A、正确B、错误答案：B28.6.队列逻辑上是一端既能增加又能减少的线性表。A、正确B、错误答案：B29.链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。A、正确B、错误答案：A30.在链串中为了提高存储密度，应该增大结点的大小。A、正确B、错误答案：A31.判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。A、正确B、错误答案：A32.数据的逻辑结构与数据元素本身的内容和形式无关。A、正确B、错误答案：A33.9.Hash表的平均查找长度与处理冲突的方法无关。A、正确B、错误答案：B34.数据的逻辑结构是依赖于计算机的。A、正确B、错误答案：B35.在队列中允许删除的一端称为队尾。A、正确B、错误答案：B36.数据的存储结构是数据的逻辑结构的存储映像。A、正确B、错误答案：A37.将十进制数转换为二进制数是栈的典型应用之一。A、正确B、错误答案：A38.空栈就是所有元素都为0的栈。A、正确B、错误答案：B39.链表的每个结点都恰好包含一个指针域。A、正确B、错误答案：B40.数据的逻辑结构和数据的存储结构是相同的。A、正确B、错误答案：B41.队列是限制在两端进行操作的线性表。A、正确B、错误答案：A42.栈是运算受限制的线性表。A、正确B、错误答案：A43.在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。A、正确B、错误答案：B44.4.哈夫曼编码是前缀编码。A、正确B、错误答案：A45.在链队列上做出队操作时,会改变front指针的值。A、正确B、错误答案：B46.数据元素是数据的最小单位。A、正确B、错误答案：B47.6.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上并不一定紧邻。A、正确B、错误答案：B48.冒泡排序是不稳定的排序。A、正确B、错误答案：B49.串是n个字母的有限序列。A、正确B、错误答案：B50.在循环链队列中无溢出现象。A、正确B、错误答案：B51.线性表采用顺序存储，必须占用一片连续的存储单元。A、正确B、错误答案：A52.在循环队列中，若尾指针rear大于头指针front，其元素个数为rear-front。A、正确B、错误答案：A53.删除二叉排序树中的一个结点，再重新插入上去，一定能得到原来的二叉排序树。A、正确B、错误答案：B54.7.堆是满二叉树。A、正确B、错误答案：B55.在栈空的情况下，不能作出栈操作，否则产生下溢出。A、正确B、错误答案：A56.如果两个串含有相同的字符，则说明它们相等。A、正确B、错误答案：B57.已知一棵树的先序序列和后序序列，一定能构造出该树。A、正确B、错误答案：B58.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。A、正确B、错误答案：B59.在链队列上做出队操作时，会改变front指针的值。A、正确B、错误答案：B60.哈夫曼树一定是满二叉树。A、正确B、错误答案：B61.在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。A、正确B、错误答案：A62.二叉树中的叶子结点就是二叉树中没有左右子树的结点。A、正确B、错误答案：B63.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。A、正确B、错误答案：B64.线性表的链式存储结构优于顺序存储。A、正确B、错误答案：B65.串中任意个字符组成的子序列称为该串的子串。A、正确B、错误答案：B66.程序一定是算法。A、正确B、错误答案：B67.串的数据元素是一个字符。A、正确B、错误答案：A68.3.在AOE网中,关键路径上某个活动的时间缩短,整个工程的时间也就必定缩短。A、正确B、错误答案：B69.数据的物理结构是指数据在计算机内实际的存储形式。A、正确B、错误答案：A70.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。A、正确B、错误答案：A71.串的长度是指串中不同字符的个数。A、正确B、错误答案：B72.栈的特点是“后进先出”。A、正确B、错误答案：A73.如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。A、正确B、错误答案：B74.插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。A、正确B、错误答案：B75.数据表示是设想计算机是如何一步一步完成这个任务的。A、正确B、错误答案：B76.线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。A、正确B、错误答案：B77.线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。A、正确B、错误答案：A78.栈的特点是“后进先出”。A、正确B、错误答案：A填空题1.()是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。答案：队列2.请完成以下代码填空：/**判断带头结点的单链表是否为空*判断头结点是否有后继引用()*如果头结点没有后继引用()，则表示单链表空，返回true，否则返回false*///first为指向头结点的引用变量public()isEmpty(){if().next==()){//判断首结点是否为空return();}else{return();}}boolean；first；null；true；false；答案：也就是头结点的指针域next是否为空|即头结点的指针域next为空|||（|||3.向一个循环队列中插入元素时,首先要判断(),然后再向指针所指的位置写入新的数据。答案：队尾指针4.若一个算法中的语句频度之和为T()=6n+3nlog2n,则算法的时间复杂度为()。O()答案：n||nlog2n5.单链表中需知道()才能遍历整个链表。答案：头指针6.请完成以下代码填空：//带头结点的单链表遍历，依次输出单链表中的结点数据//first为指向头结点的引用变量publicvoidprintList(){//引用变量p初始化，指向首结点()LinkedNode<T>p=();while(){Tdata=();//取出当前结点的数据域data的值System.out.print(data+"");//输出数据元素的值p=();//指向后继结点}System.out.println();}first.next；p.data；p.next；答案：|第一个数据元素所在结点||p!=null|||7.完成以下代码填空：//求带头结点单链表中的数据元素个数并返回其值，first为指向头结点的头引用publicintlength(){intlength=();//计数器，用来累计结点个数LinkedNode<T>p=().next;//初始化，引用变量p指向第一个结点()while(){//从首结点向后查找，直到p为空();//若当前结点非空，则结点个数递增1p=();//指向后继结点}returnlength;}；first；length++；p.next；答案：|||首结点|p!=null||8.顺序查找、二分查找、分块查找都属于（）查找。答案：静态9.非连通图的极大连通子图称为（）。答案：连通分量10.由树转换成二叉树时,其根结点无()。答案：右孩子11.解：()先根次序遍历：ABEFCGDHIJK()后根次序遍历：EFBGCIJKHDA答案：1|212.有一组字符C={a,b,c,d}，其权值为W={7,5,2,4}：()求其构造的哈夫曼树()求其哈夫曼树的WPL()并且对各字符进行哈夫曼编码。答案：1|2|313.数据的存储结构形式包括:顺序存储、链式存储、索引存储和()。答案：散列存储简答题1.4.叶子权值(5,6,17,8,19)所构造的哈夫曼树带权路径长度为_______________。答案：1212.已知一棵二叉树的先序遍历序列为：ABDGHCEFI，中序遍历序列为：GDHBAECIF，试恢复该二叉树，并写出它的后序遍历的序列。答案：GHDBEIFCA3.1.已知二叉树有50个叶子结点,则该二叉树的总结点数至少是_______________。答案：994.在最坏情况下，在第i趟直接插入排序中，要进行次关键字的比较。答案：i-15.5.从长度为n的采用顺序存储结构的线性表中删除第i个元素(1≤i≤n),需向前移动________个元素。答案：n-i；6.算法的时间复杂度与空间复杂度相比,通常以作为主要度量指标。答案：时间复杂度7.给出下面二叉树的前序遍历、中序遍历、后序遍历的结果。答案：先序