算法与数据结构试题.docx

《算法与数据结构试题.docx》由会员分享，可在线阅读，更多相关《算法与数据结构试题.docx（16页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、算法与数据结构类试题1、算法是指（） A为解决问题而编写的计算机程序B为解决问题而采取的方法与步骤(正确答案)C为解决问题而需要采用的计算机语言D为解决问题而采用的计算方法2、设栈S的初始状态为空，现有5个元素组成的序列1，2，3，4，5，对该序列在S栈上依次进行如下操作(从序列中的1开始，出栈后不再进栈)：进栈、进栈、进栈、出栈、进栈、出栈、进栈。试问出栈的元素序列是（） A5，4，3，2，1B2，1C2，3D3，4(正确答案)3、设循环队列中数组的下标范围是n，其中头尾指针分别是f和r，则其元素个数是( ) Ar-fBr-f+1C(r-f) MOD n+1D(r-f+n) MOD n(正确

2、答案)4、在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是（） A堆排序B希尔排序C冒泡排序D快速排序(正确答案)5、在有n个子叶节点的哈夫曼树中，其节点总数为（） A不确定B2n-1(正确答案)C2n+1D2n6、某数列有1000个各不相同的单元，由低到高按序排列，现要对该数列进行二分法检索，在最坏的情况下，需要检视( )个单元（） A1000B10(正确答案)C100D5007.已知数组A中，每个元素AI，J在存储时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存储分配的。试问：A5，8的起始地址为（） ASA+141(正确答案)B BS

3、A+180C CSA+222D DSA+2258、线性表若采用链表存储结构，要求内存中可用存储单元地址（） A必须连续B部分地址必须连续C一定不连续D连续不连续均可(正确答案)9、下列叙述中，正确的是（） A线性表的线性存储结构优于链表存储结构B队列的操作方式是先进后出C栈的操作方式是先进先出D二维数组是指它的每个数据元素为一个线性表的线性表(正确答案)10、电线上停着两种鸟(A，B)，可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可公为两类：一类是两端的小鸟相同；另一类是两端的小鸟不相同。已知：电线上两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是（） A奇数B偶数(正

4、确答案)C可奇可偶D数目固定11、在列车转辙网络中，有四个车皮编号为1，2，3，4，并按此顺序送入栈中进行调度，这些车皮取出的顺序是（） A4123B3241(正确答案)C3412D431212、从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)的一端，这种排序方法称为（） A插入排序B归并排序C选择排序(正确答案)D快速排序13.在计算递归函数时，如不使用递归过程，则一般情况下必须借助于( )数据结构（） A栈(正确答案)B树CC双向队列D D广义表14、使用双向链表存放数据的优点是（） A提高检索速度B很方便地插入和删除数据(正确答案)C节约存储空间D很快回收存储空间15、对一

5、个满二叉树，m个树叶，l分枝结点，n个结点，则（） An=l+m(正确答案)Bl+m=2nCm=l-1Dn=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.那么

6、，排序方法是（） A选择排序B希尔排序C合并排序D快速排序(正确答案)18、具有12个记录的序列，采用冒泡排序最少的比较次数是（） A1B144C11(正确答案)D6619、下面关于二叉树的叙述正确的是（） A一棵二叉树中叶子结点的个数等于度为2的结点个数加1(正确答案)B一棵二又树中的结点个数大于0C二叉树中任何一个结点要么是叶，要么恰有两个子女D二叉树中，任何一个结点的左子树和右子树上的结点个数一定相等20、先序序列和中序序列相同的二叉树为空树或（） A任一结点均无右孩子的非空二叉树B仅有两个结点的二叉树C任一结点均无左孩子的非空二叉树(正确答案)D不存在这样的二叉树21、设有三个元素A、

7、B、C顺序进栈，在进栈过程中可以出栈，出栈次序错误的排列是（） AABCBBCACCAB(正确答案)DCBA22、下面四种内排序方法中，要求内存容量最大的是（） A插入排序B选择排序C快速排序D归并排序(正确答案)23、设有序列F：(49，38，65，97，76，13，27，50)，使用快速排序法，其趟数为（） A3(正确答案)B2C1D424.给出一组整型数28、10、37、63、35、30、23，请用二叉树对它进行排序。为此，首先要生成一棵二叉树，规则是把第一数放在根处，接着凡比它小的数放在左子树，比它大的数放在右子树，直到把所有的数均安排好。然后对此二叉树进行( )，得到的就是按照升序排

8、列好的序列。 （） 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的满二叉树中结点的个数是（） A2bB. 2(b-1)C2b-1(正确答案)D2(b+1)-127、深度为5的二叉树至多有几个结点（） A16B32C31(正确答案

9、)D1028、下面关于线性表的描述，错误的是（） A栈是线性表的一种B任给一个索引I(1=I=表中元素个数)，就能在线性表中唯一确定一个元素C线性表的任一元素都有前驱和后继(正确答案)D线性表是一个线性序列29、带权路径长度最小的二叉树是（） A顺序二叉树B二叉排序树C判定树D哈夫曼树(正确答案)30、有12个结点的平衡二叉树的最大深度是（） A4B5(正确答案)C6D331、若用冒泡排序法对序列18，14，6，27，8，12，16，52，10，26，47，29，41，24从小到大进行排序，共要进行( )次比较。（） A33B45C70(正确答案)D9132、设n，m为某二叉树上的两个结点，在

10、中序遍历时，n在m前的条件是（） An在m右方Bn是m祖先Cn在m左方(正确答案)Dn是m子孙33、下列四种排序方法，如果被排序的序列中诸元素恰好已经按要求(由小到大或由大到小排序，就元素的比较次数和移动次数而言，哪种方法最少？（） A冒泡排序B直接选择排序C直接插入排序(正确答案)D归并排序34、如果某二叉树的前序为STUWV，中序为UWTVS，那么该二叉树的后序是（） AWUVTS(正确答案)BUWVTSCVWUTSDWUTSV35、按照二叉树的定义，具有3个结点的二叉树有（） A3种B4种C5种(正确答案)D6种36、对以下关键字序列用快速排序法进行排序，速度最慢的情况是（） A19，2

11、3，3，15，7，21，8B23，21，28，15，19，3，7C19，7，15，28，23，21，3D3，7，15，19，21，23，28(正确答案)37、数组A中，每个元素AI，j的长度为3个字节，行下标I为1到8，列下标j从1到10。从首地址SA开始连续存放在存储器中，存放该数组至少需要的单元数是（） A80B100C240(正确答案)D27038、树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。正确的结论是（） A树的先根遍历序列与其对应的二叉树的先序遍历序列相同(正确答案)B树的

12、先根遍历序列与其对应的二叉树的中序遍历序列相同C树的后根遍历序列与其对应的二叉树的先序遍历序列相同D树的后根遍历序列与其对应的二叉树的后序遍历序列相同39、在数据结构中，从逻辑上可以把数据结构分成（） A动态结构和静态结构B线性结构和非线性结构(正确答案)C内部结构和外部结构D紧凑结构和非紧凑结构40、如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（） A前序B中序(正确答案)C后序D层次序41、某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（） AbdgcefhaBgdbecfhaCbdgae

13、chfDgdbehfca(正确答案)42.从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)的一端，这种排序方法称为（） A插入排序B选择排序(正确答案)C归并排序D快速排序43.快速排序方法在( )情况下最不利于发挥其长处（） A被排序的数据量太大B B被排序数据中含有多个相同值C被排序数据已基本有序(正确答案)D被排序数据数目为奇44、下面关于数据结构的叙述中，正确的叙述是（） A顺序存储方式的优点是存储密度大，且插入、删除运算效率高B链表中的每一个结点都包含一个指针C包含n个结点的二叉排序树的最大检索长度为log-2nD将一棵树转换为二又树后，根结点没有右子树(正确答案)45

14、.在计算机科学领域中,算法分为两类:数值型算法和非数值型算法。下面的算法，哪一个属于数值算法类（） A迭代法(正确答案)B冒泡法C黑盒法D杂凑(Hash)法46.若已知一个栈的输入序列为1，2，3，n，其输出序列为P1，P2，Pn。若P1=n，则Pi为（） AIBn+ICn-I+1(正确答案)D不确定47、带头结点的单链表Head为空的判定条件是（） AHead=NILBHead.Next=NIL(正确答案)CHead.Next=HeadDHead=Head48、二维数组a的成员是6个字符组成的串，行下标I的范围从0到8，列下标j的范围从1到10，则存放a至少需要( )个字节 （） A90B1

15、80C240D540(正确答案)49、由3个结点可以构造出多少种不同的有向树（） A2(正确答案)B3C4D550、二维数组MI，j的元素是4个字符(每个字符占一个存储单元)组成的串，行下标I的范围从0到4，列下标j的范围从0到5。M按行存储元素M3，5的起始地址与M按列存储时元素( )的起始地址相同。（） Am2,4Bm3,4(正确答案)Cm3,5Dm4,451、判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（） A求关键路径的方法B求最短路径的方法C广度优先遍历方法D深度优先遍历方法(正确答案)52、在一非空二叉树的中序遍历序列中，根结点的右边（） A只有右子树上的所有结

16、点(正确答案)B只有右子树上的部分结点C只有左子树上的所有结点D只有左子树上的部分结点53、一个队列的入列序列是1，2，3，4，则队列的输出序列是（） A4，3，2，1B1，2，3，4(正确答案)C1，4，3，2D3，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,1

17、9,20.所用的排序方法是（） A直接插入排序(正确答案)B冒泡排序C希尔排序D堆排序56计算机算法一般被划分为数值算法和非数值算法两大类，下列叙述中，哪个不属于数值算法（） A迭代法B直接法C杂凑(Hash)法(正确答案)D消去法57、用归并排序方法对线性表(49，38，65，97，76，13，27，49，55，04)进行排序时，其第三趟的排序结果为（） A12，27，38，49，49，65，76，97，04，55(正确答案)B38，49，65，97，13，27，49，76，04，55C38，49，65，97，13，76，27，49，04，55D01，13，27，38，49，49，55，65

18、，76，9758、栈和队列都是（） A顺序存储的线性结构(正确答案)B链式存储的非线性结构C限制存取点的线性结构D限制存取点的非线性结构59、对N个结点的线性表进行查找，用顺序查找的时间复杂性为（） ANNBNlog2nCn(正确答案)Dlog2n60、若进栈序列为1，2，34假定进栈和出栈可以穿插进行，则可能的出栈序列是（） A2，4，1，3B3，1，4，2C3，4，1，2D1，2，3，4(正确答案)61、设计一个判别表达式中左、右括号是否配对的算法，采用( )数据结构最佳（） A线性表的顺序存储结构B栈(正确答案)C队列D线性表的链式存储结构62设一棵二叉树，其叶子结点分别带权10，12，

19、4，7，5，18，2则其带权路径长度最小为（） A120B130C140(正确答案)D15063、以下关于数据结构的叙述，正确的是（） A线性表的线性存储结构优于链式结构B二叉树的第I层上有2的(I-1)次幂个结点，深度为K的二叉树上有2的(k-1)次幂个结点(正确答案)C二维数组是其数据元素为线性表的线性表D栈的操作方式是先进先出64、循环队列用数组A0m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（） A(rear-front+m)MOD m(正确答案)Brear-front-1Crear-front+1Drear-front65、下列哪一种图的邻接

20、矩阵是对称矩阵（） A有向图B无向图(正确答案)CAOV网DAOE网66、计算机算法必须具备的三个特性是（） A可执行性、可移植性和可扩充性B可执行性、确定性和有穷性(正确答案)C确定性、有穷性和稳定性D易读性、稳定性和安全性67、对长度为10的有序表进行折半查找，设在等概率时查找成功的平均查找长度是（） A2.9(正确答案)B3.1C3.4D2.668.设有6个结点的无向图，该图至少应该有( )条边才能确保是一个连通图（） A5(正确答案)B6C7D870.二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为（）。 A. 4

21、2 5 7 6 3 1B. 4 2 7 5 6 3 1(正确答案)C. 4 2 7 5 3 6 1D. 4 7 2 3 5 6 1E. 4 5 2 6 3 7 171. 假设A=true,B=false,C=ture,D=ture,逻辑运算表达式ABCD的值是（）。 A) ture(正确答案)B)falseC)0D)1E)NULL72 已知队列(13，2，11，34，41，77，5，7，18，26，15)，第一个进入队列的元素是13，则第五个出队列的元素是（）。 A 5B 41(正确答案)C 77D 13E 1873. 设全集E=1，2，3，4，5，集合A=1，4，B=1，2，5，C=2，4，则集合(A B)C 为（）。 A 空集B 1C 3，5D 1，5E 1，3，5(正确答案)74. 表达式(1+34)5-56/7 的后缀表达式为（）。 A 1+345-56/7B -+1 34 5/56 7C 1 34 +556 7/-(正确答案)D 1 34 5 +56 7/-E 1 34+5 56 7-/