经典数据结构习题集含答案.doc

线性表1.下列有关线性表的叙述中，正确的是（ A ）。A）线性表中元素之间的关系是线性关系B）线性表中至少有一个元素C）线性表中的任一元素有且仅有一个直接前趋D）线性表中的任一元素有且仅有一个直接后继2.下述哪一条是顺序存储结构的优点？（A ）A）存储密度大 B）插入方便C）删除方便 D）可方便地用于各种逻辑结构的存储表示3.在一个长度为n的顺序表中，在第i个元素（1<=i<=n）之前插入一个新元素时需向后移动（ D ）个元素。A）1 B）n-i C）n-i-1 D）n-i+14.如果某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，那么采用（ A ）存储方式最节省时间。A）顺序表 B）单链表C）双链表 D）循环链表5.对顺序存储的线性表，设其长度为n，且在任何位置上插入或删除操作都是等概率的。则插入一个元素时平均要移动表中的（A ）个元素。A）n/2 B）(n+1)/2 C）(n-1)/2 D）n6.下述哪一条是顺序存储结构的缺点？（ C ）A）存储密度太大 B）随机存取C）一般要估计最大的需要空间 D）只能应用于少数几种逻辑结构的存储表示7.在单链表中，增加头结点的目的是（ C ）。A）使单链表至少有一个结点B）标志表中首结点的位置C）方便运算的实现D）说明单链表是线性表的链式存储表示8.单链表不具有的特点是（ A ）。A)可随机访问任一元素 B)插入和删除不需要移动元素C)不必事先估计存储空间 D)所需空间和线性表长度成正比9.循环链表的主要优点是（ D）。 A）不再需要头指针了B）已知某个结点的位置后，能够容易找到他的直接前趋C）在进行插入、删除运算时，能更好的保证链表不断开D）从表中的任意结点出发都能扫描到整个链表10.链表对于数据元素的插入与删除是（ B ）。A）不需移动结点，不需改变结点指针B）不需移动结点，只需改变结点指针C）只需移动结点，不需改变结点指针D）既需移动结点，又需改变结点指针11.在一个单链表中,已知q所指结点是p所指结点的前驱结点,若要在q 和p所指结点之间插入s所指的结点,则执行（B ）。A）s->next = p->next; p->next = s;B）q->next = s; s->next = p;C）p->next = s; s->next = q;D）p->next = s->next; s->next = p;12.向一个有115个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ C ）个元素。A) 115 B) 114 C) 58 D) 57 13.带头结点的单链表Head为空表的判定条件是 ( B ) 。A) Head->next=Head B) Head->next=NULLC) Head!=NULL D) Head=NULL14.若要求能快速地实现在链表的末尾插入结点和删除第一个结点的运算，则选择( B )最合适。A) 单链表 B) 带尾指针的单循环链表C) 双链表 D) 双循环链表15.给定有n个元素的向量，建立一个有序单链表的时间复杂度是( D )。A)O(n) B)O(log2n) C)O(nlog2n) D. O(n2)16.线性表采用链式存储时，其地址( C)。A)必须是连续的 B)必须是不连续的C)连续与否均可 D)部分地址必须是连续的17.在一个具有n个结点的有序单链表中，插入一个新的结点并使之仍然有序的时间复杂度是(A )。A)O(n) B)O(log2n) C)O(1) D)O(n2) 排序1.在下列排序算法中，时间复杂度不受数据初始特性影响，恒为O(n2)的是（C ）。A）插入排序 B）冒泡排序 C）选择排序 D）堆排序2.在各种排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ C）。A）希尔排序 B）冒泡排序 C）插入排序 D）选择排序3.快速排序方法在（C）情况下最不利于发挥其长处。A）要排序的数据量太大 B）要排序的数据含有多个相同值C）要排序的数据已基本有序 D）要排序的数据个数为奇数4.已知10个数据元素为(54,28,16,34,73,62,95,60,26,43),对该数列按从小到大排序，经过一趟冒泡排序后的序列为（B）。A）16，28，34，54，73，62，60，26，43，95B）28，16，34，54，62，73，60，26，43，95C）28，16，34，54，62，60，73，26，43，95D）16，28，34，54，62，60，73，26，43，955.一组记录的关键字为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为（ C ）。A）38,40,46,56,79,84 B）40,38,46,79,56,84 C）40,38,46,56,79,84 D）40,38,46,84,56,79 6.用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,元素序列的变化情况如下:(1)20,15,21,25,47,27,68,35,84 (2)15,20,21,25,35,27,47,68,84(3)15,20,21,25,27,35,47,68,84则所采用的排序方法是（D ）。A）选择排序 B）希尔排序 C）归并排序 D）快速排序7.在待排序的元素序列基本有序的前提下，效率最高的排序方法是（A）。 A）插入排序 B）快速排序C）归并排序 D）选择排序8.一组记录的排序码为（20,29,11,74,35,3,8,56）,则利用堆排序方法建立的初始(小顶)堆为（B ）。A）20,29,11,74,35,3,8,56B）3,29,8,56,35,11,20,74C）3,8,11,20,29,35,56,74D）20,29,3,8,11,35,74,569.下列关键码序列中，属于堆的是（A）。A)（15，30，22，93，52，71） B)（15，71，30，22，93，52）C)（15，52，22，93，30，71）D)（93，30，52，22，15，71）10.若要求尽可能快地对实数数组进行稳定的排序，则应选(C)。A)快速排序 B)堆排序 C)归并排序 D)基数排序11.下列排序算法的时间复杂度最小的是（D）。A)冒泡排序 B)希尔排序C)简单选择排序 D)归并排序12.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好（ C）排序法。A)起泡排序 B)快速排序 C)堆排序 D)基数排序13.插入排序算法在每一趟都能选取出一个元素放在其最终的位置上。( B )A)正确 B)不正确14.直接插入排序是不稳定的排序方法。( B )A)正确 B)不正确15.直接插入排序的最坏情况是初始序列为（ B ）序。A)正 B)反 C)正和反 D)无16.在各排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为(D )。A)希尔排序 B)归并排序 C)插入排序 D)选择排序栈和队列1.栈的特点是( B )。A）先进先出 B）后进先出C）进优于出 D）出优于进2.栈和队列都是（C）。 A）顺序存储的线性结构 B）链式存储的线性结构C）操作受限的线性结构 D）操作受限的非线性结构3.链栈与顺序栈相比，有一个比较明显的优点是（B）。A）插入操作更加方便 B）通常不会出现栈满的情况C）不会出现栈满的情况 D）删除操作更加方便4.一个栈的入栈序列是a,b,c,d, 则下列序列中不可能的输出序列是（ D ）。A）acbd B）dcbaC）acdb D）dbac5.设有一空栈,现有输入序列为1,2,3,4,5,经过PUSH,PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列为（C ）。A）5,4,3,2,1 B）2,1 C）2,3 D）2,4 6.下面哪种数据结构不适合作栈的存储结构（D ）。A）数组 B）单链表 C）静态链表 D）二叉树结构7.设计一个判别表达式中左右括号是否配对出现的算法，最好采用（C ）结构。A）线性表 B）队列 C）堆栈 D）树8.队列的操作原则是( A ) 。A）先进先出 B）先进后出C）只能进行插入 D）只能进行删除 9. 判断一个循环队列是空队列的条件是（A ）。 A）Q.rear = Q.front B）Q.front = 0C）Q.rear = 0 D）(Q.rear+1)%maxsize = Q.front10.在具有n个单元顺序存储的循环队列中，队满时共有（B ）个元素。A）n+1 B）n-1 C）n D）n+211.若一个栈的输入序列是1,2,3,n,输出序列的第一个元素是n,则第i个输出元素是( B )。A) n-i B) n-i+1 C) i D) 不确定 12.判断当字符序列 x5y 作为字符堆栈的输入时，输出长度为3的且可以作为C语言标识符的个数是（ A ）。A) 3个 B) 4个 C) 5个 D) 6个 13.采用不带尾指针的单链表方式表示一个栈，便于结点的插入与删除。栈顶结点的插入与删除通常在链表的（C）进行。A)任意位置 B)链表头尾两端C)链表头一端 D)链表尾一端14.在一个链队列中,若Q.front、Q.rear分别为队首、队尾指针，则插入s所指结点的操作为（ B ）。A) Q.front->next=s; Q.front=s; B) Q.rear->next=s; Q.rear=s;C) s->next=Q.front; Q.rear=s;D) s->next=Q.front; Q.front=s;串和数组1.串是一种特殊的线性表，其特殊性体现在( C ) 。 A)可以顺序存储 B)可以用链表存储 C)数据元素是一个字符 D)数据元素可以是多个字符2.串是（ D ）。 A）少于一个字母的序列 B）任意个字母的序列C）不少于一个字符的序列 D）有限个字符的序列3.串的长度是（ D ）。A）串中不同字母的个数 B）串中不同字符的个数C）串中所含字符的个数，且大于0D）串中所含字符的个数4.设有两个串p和q,求q在p中首次出现的位置的运算(B ). A）连接 B）模式匹配C）求子串 D）求串长5.若某串的长度小于一个常数，则采用( C )存储方式最为节省空间。A)链式 B)堆结构 C)顺序6.串中任意多个连续字符组成的子序列称为该串的子串(A ).A)正确 B)不正确7.如果两个串含有相同的字符集，则说两者相等( B ). A)正确 B)不正确8.存取数组中任一元素的时间都是相等的，这种存取方式为（ B）存取方式。A）顺序 B）随机 C）线性 D）非线性 9.设一个一维数组第一个元素的存储单元的地址是100，每个元素的长度是6，则它的第5个元素的地址是（D ）。A）130 B）105 C）106 D）12410.设n阶方阵是一个上三角矩阵，则需要存储的元素个数是（B）。A）n2/2 B）n(n+1)/2 C）n D）n211.对一些特殊矩阵采用压缩存储的目的主要是为（B ）。A）表达变得简单 B）减少不必要的存储空间的开销C）去掉矩阵中的多余元素 D）对矩阵元素的存取变得简单 二叉树和树1.树最适合用来表示（C ）。 A)有序数据元素 B)无序数据元素C)元素之间具有分支层次关系的数据D)元素之间无联系的数据2.设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至多为( A )。A)2h-1 B)2(h-1) C)2*h-1 D)2*h3.在一棵二叉树中，第5层上的结点数最多有( C )。A)10 B)15 C)16 D)32 4.下图所示的二叉树中，( C )不是完全二叉树。5.有100个结点的完全二叉树,叶子结点的个数为:( B )。A)49 B)50 C)51 D)526.具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其中（ D ）个指针域为空。A）50 B）99 C）100 D）1017.首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为（C ）。 A）前序遍历 B）后序遍历 C）中序遍历 D）层次遍历8.任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序（ A ）。A）不发生变化 B）发生变化C）不能确定 D）以上都不对9.某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是（B ）的二叉树。A）空或只有一个结点 B）高度等于其结点数C）任一结点无左孩子 D）任一结点无右孩子10.如果某二叉树的先序遍历序列是abdcef，中序遍历序列是dbaefc，则其后序遍历序列是（ C ）。A）dbafec B）fecdba C）efcdba D）dbfeca11.按照二叉树的定义，具有3个结点的二叉树形态有(C )种。A）3 B）4 C）5 D）612.二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的前面（B ）。A）正确 B）错误13.n个结点深度为h的二叉树的线索化所需的时间复杂度是(C )。A)O(1) B)O(hn) C)O(n) D)O(nlog2h)14.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是( C )。A)a是b祖先 B)a是b子孙 C)a在b左方 D)a在b右方15.关于二叉树的三种遍历，下列说法正确的是( D )。A)任意两种遍历序列都不可以唯一决定该二叉树B)任意两种遍历序列都可以唯一决定该二叉树C)先序遍历序列和后序遍历序列可以唯一决定该二叉树D)先序遍历序列和中序遍历序列可以唯一决定该二叉树16.在某棵二叉树的一种序列中，如果发现其中每一结点的左孩子均是其前趋，则可判断定这种序列为中序序列( B )。A)正确 B)不正确17.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是（ D ）。A)acbed B)decab C)deabc D)cedba18.前序遍历和中序遍历结果相同的二叉树为（ B ）。A)只有根结点的二叉树 B)所有非叶子结点只有右子树的二叉树C)根结点无右孩子的二叉树D)根结点无左孩子的二叉树 19.前序遍历和后序遍历结果相同的二叉树为（ A ）。A)只有根结点的二叉树B)所有非叶子结点只有右子树的二叉树C)根结点无右孩子的二叉树D)根结点无左孩子的二叉树Power by YOZOSOFT