数据结构期末复习70题经典题目

数据结构1．算法是指()A．为解决问题而编写的计算机程序B．为解决问题而采取的方法与步骤C．为解决问题而需要采用的计算机语言D．为解决问题而采用的计算方法2．设栈S的初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在S栈上依次进行如下操作(从序列中的1开始，出栈后不再进栈)：进栈、进栈、进栈、出栈、进栈、出栈、进栈。试问出栈的元素序列是()A．{5，4，3，2，1}B．{2，1}C．{2，3}D．{3，4}3．设循环队列中数组的下标范围是1-n，其中头尾指针分别是f和r，则其元素个数是()A．r-fB．r-f+1C．(r-f)MODn+1D．(r-f+n)MODn4．在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是()A．堆排序B．希尔排序C．冒泡排序D．快速排序5．在有n个子叶节点的哈夫曼树中，其节点总数为()A．不确定B．2n-1C．2n+1D．2n6．某数列有1000个各不相同的单元，由低到高按序排列，现要对该数列进行二分法检索，在最坏的情况下，需要检视()个单元A．1000B．10C．100D．5007、已知数组A中，每个元素A[I，J]在存储时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存储分配的。试问：A[5，8]的起始地址为()A．SA+141B．SA+180C．SA+222D．SA+2258．线性表若采用链表存储结构，要求内存中可用存储单元地址()A．必须连续B．部分地址必须连续C．一定不连续D．连续不连续均可9．下列叙述中，正确的是()A．线性表的线性存储结构优于链表存储结构B．队列的操作方式是先进后出C．栈的操作方式是先进先出D．二维数组是指它的每个数据元素为一个线性表的线性表10．电线上停着两种鸟(A，B)，可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可公为两类：一类是两端的小鸟相同；另一类是两端的小鸟不相同。已知：电线上两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是()A．奇数B．偶数C．可奇可偶D．数目固定11．在列车转辙网络中，有四个车皮编号为1，2，3，4，并按此顺序送入栈中进行调度，这些车皮取出的顺序是()A．4123B．3241C．3412D．431212．从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端，这种排序方法称为()A．插入排序B．归并排序C．选择排序D．快速排序13．在计算递归函数，如不用递归过程，则一般情况下必须借助()数据结构A．栈B．树C．双向队列D．广义表14．使用双向链表存放数据的优点是()A．提高检索速度B．很方便地插入和删除数据C．节约存储空间D．很快回收存储空间15．对一个满二叉树，m个树叶，l分枝结点，n个结点，则()A．n=l+mB．l+m=2nC．m=l-1D．n=2l-116．一维数组与线性表的区别是()A．前者长度固定，后者长度可变B．后者长度固定，前者长度可变C．两者长度均固定D．两者长度均可变17.用某种排序方法对线性表25,84,21,47,15,27,68,35,20进行排序，结点变化如下：(1)25,84,21,47,15,27,68,35,20;(2)20,15,21,25,47,27,68,35,84;(3)15,20,21,25,35,27,47,68,84;(4)15,20,21,25,27,35,47,68,84.那么，排序方法是()A．选择排序B．希尔排序C．合并排序D．快速排序18．具有12个记录的序列，采用冒泡排序最少的比较次数是()A．1B．144C．11D．6619．下面关于二叉树的叙述正确的是()A．一棵二叉树中叶子结点的个数等于度为2的结点个数加1B．一棵二又树中的结点个数大于0C．二叉树中任何一个结点要么是叶，要么恰有两个子女D．二叉树中，任何一个结点的左子树和右子树上的结点个数一定相等20．先序序列和中序序列相同的二叉树为空树或()A．任一结点均无右孩子的非空二叉树B．仅有两个结点的二叉树C．任一结点均无左孩子的非空二叉树D．不存在这样的二叉树21．设有三个元素A、B、C顺序进栈，在进栈过程中可以出栈，出栈次序错误的排列是()A．ABCB．BCAC．CABD．CBA22．下面四种内排序方法中，要求内存容量最大的是()A．插入排序B．选择排序C．快速排序D．归并排序23．设有序列F：（49，38，65，97，76，13，27，50），使用快速排序法，其趟数为()A．3B．2C．1D．424．给出一组整型数28、10、37、63、35、30、23，请用二叉树对它进行排序。为此，首先要生成一棵二叉树，规则是把第一数放在根处，接着凡比它小的数放在左子树，比它大的数放在右子树，直到把所有的数均安排好。然后对此二叉树进行()，得到的就是按照升序排列好的序列。A．前序遍历B．中序遍历C．后序遍历D．横向遍历25．用某种排序方法对线性表(84,47,25,15,21)进行排序，结点序列的变化如下(1)84,47,25,15,21;(2)15,47,25,84,21;(3)15,21,25,84,47;(4)15,21,25,47,84那么，所采用的排序方法是()A．选择排序B．冒泡排序C．插入排序D．快速排序26．设二叉树根结点的层次为0，一棵高度为b的满二叉树中结点的个数是()A．2^bB．2^(b-1)C．2^b-1D．2^(b+1)-127．深度为5的二叉树至多有()个结点()A．16B．32C．31D．1028．下面关于线性表的描述，错误的是()A．栈是线性表的一种B．任给一索引I（1=I=表中元素个数），就能在线性表中唯一确定一个元素C．线性表的任一元素都有前驱和后继D．线性表是一个线性序列29．带权路径长度最小的二叉树是()A．顺序二叉树B．二叉排序树C．判定树D．哈夫曼树30．有12个结点的平衡二叉树的最大深度是()A．4B．5C．6D．331．若用冒泡排序法对序列18，14，6，27，8，12，16，52，10，26，47，29，41，24从小到大进行排序，共要进行()次比较。A．33B．45C．70D．9132．设n，m为某二叉树上的两个结点，在中序遍历时，n在m前的条件是()A．n在m右方B．n是m祖先C．n在m左方D．n是m子孙33．下列四种排序方法，如果被排序的序列中诸元素恰好已经按要求（由小到大或由大到小排序，就元素的比较次数和移动次数而言，哪种方法最少？()A．冒泡排序B．直接选择排序C．直接插入排序D．归并排序34．如果某二叉树的前序为STUWV，中序为UWTVS，那么该二叉树的后序是()A．WUVTSB．UWVTSC．VWUTSD．WUTSV35．按照二叉树的定义，具有3个结点的二叉树有()A．3种B．4种C．5种D．6种36．对以下关键字序列用快速排序法进行排序，速度最慢的情况是()A．{19，23，3，15，7，21，8}B．{23，21，28，15，19，3，7}C．{19，7，15，28，23，21，3}D．{3，7，15，19，21，23，28}37．数组A中，每个元素A[I，j]的长度为3个字节，行下标I为1到8，列下标j从1到10。从首地址SA开始连续存放在存储器中，存放该数组至少需要的单元数是()A．80B．100C．240D．27038．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。正确的结论是()A．树的先根遍历序列与其对应的二叉树的先序遍历序列相同B．树的先根遍历序列与其对应的二叉树的中序遍历序列相同C．树的后根遍历序列与其对应的二叉树的先序遍历序列相同D．树的后根遍历序列与其对应的二叉树的后序遍历序列相同39．在数据结构中，从逻辑上可以把数据结构分成()A．动态结构和静态结构B．线性结构和非线性结构C．内部结构和外部结构D．紧凑结构和非紧凑结构40．如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的()A．前序B．中序C．后序D．层次序41．某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是()A．bdgcefhaB．gdbecfhaC．bdgaechfD．gdbehfca42．从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端，这种排序方法称为()A．插入排序B．选择排序C．归并排序D．快速排序43．快速排序方法在()情况下最不利于发挥其长处A．被排序的数据量太大B．被排序数据中含有多个相同值C．被排序数据已基本有序D．被排序数据数目为奇44．下面关于数据结构的叙述中，正确的叙述是()A．顺序存储方式的优点是存储密度大，且插入、删除运算效率高B．链表中的每一个结点都包含一个指针C．包含n个结点的二叉排序树的最大检索长度为log＼-2nD．将一棵树转换为二又树后，根结点没有右子树45．在计算机科学领域中,算法分为两类:数值型算法和非数值型算法。下面的算法，哪一个属于数值算法类()A．迭代法B．冒泡法C．黑盒法D．杂凑（Hash）法46．若已知一个栈的输入序列为1，2，3…，n，其输出序列为P1，P2，…，Pn。若P1=n，则Pi为()A．IB．n+IC．n-I+1D．不确定47．带头结点的单链表Head为空的判定条件是()A．Head=NILB．Head^.Next=NILC．Head^.Next=HeadD．Head=Head48．二维数组a的成员是6个字符组成的串，行下标I的范围从0到8，列下标j的范围从1到10，则存放a至少需要()个字节A．90B．180C．240D．54049．由3个结点可以构造出多少种不同的有向树()A．2B．3C．4D．550．二维数组M[I，j]的元素是4个字符（每个字符占一个存储单元）组成的串，行下标I的范围从0到4，列下标j的范围从0到5。M按行存储元素M[3，5]的起始地址与M按列存储时元素()_的起始地址相同。A．m[2,4]B．m[3,4]C．m[3,5]D．m[4,4]51．判断一有向图是否存在回路除可以利用拓扑排序方法外，还可以利用()A．求关键路径的方法B．求最短路径的方法C．广度优先遍历方法D．深度优先遍历方法52．在一非空二叉树的中序遍历序列中，根结点的右边()A．只有右子树上的所有结点B．只有右子树上的部分结点C．只有左子树上的所有结点D．只有左子树上的部分结点53．一个队列的入列序列是1，2，3，4，则队列的输出序列是()A．4，3，2，1B．1，2，3，4C．1，4，3，2D．3，2，4，154．邻接表存储结构下图的深度优先遍历算法结构类似于二叉树的()A．先序遍历B．中序遍历C．后序遍历D．按层遍历55．设待排序的记录为(20,16,13,14,19)，经过下列过程将这些记录排序：(1)20,16,13,14,19;(2)16,20,13,14,19;(3)13,16,20,14,19;(4)13,14,16,20,19;(5)13,14,16,19,20.所用的排序方法是()A．直接插入排序B．冒泡排序C．希尔排序D．堆排序56．计算机算法一般被划分为数值算法和非数值算法两大类，下列叙述中，哪个不属于数值算法()A．迭代法B．直接法C．杂凑（Hash）法D．消去法57．用归并排序方法对线性表（49，38，65，97，76，13，27，49，55，04）进行排序时，其第三趟的排序结果为()A．12，27，38，49，49，65，76，97，04，55B．38，49，65，97，13，27，49，76，04，55C．38，49，65，97，13，76，27，49，04，55D．01，13，27，38，49，49，55，65，76，9758．栈和队列都是()A．顺序存储的线性结构B．链式存储的非线性结构C．限制存取点的线性结构D．限制存取点的非线性结构59．对N个结点的线