关于今天长安保定百度百度爱问爱数据结构练习题 - 安阳市第七中学

关于今天长安保定百度百度爱问爱数据结构练习题 - 安阳市第七中学 的的范德萨的地方地方爱的规格爱你啊好文章初赛数据结构练习题 初赛数据结构练习题 一、选择题: 1(二叉树是一种重要的数据结构，5个结点构成的不同的二叉树有( )棵。 A(22 B(30 C(40 D(42 2(一棵树T有2个度数为2的结点、有1个度数为3的结点、有3个度数为4的结点，那么树T有( )个叶子结点。 A(14 B(6 C(18 D(7 3(一棵深度为K的满二叉树有( )个结点。 A(2K,1 B(2K C(2K D(2K,1 4(在一个图中，所有顶点的度数之和等于所有边数的( )倍。 A(1/2 B(1 C(2 D(4 5(设栈S的初始状态为空，现有5个元素组成的序列,a,b,c,d,e,，对该序列在S栈上依次进行如下操作(从a开始，出栈后不再进栈):进栈，进栈，进栈，出栈，进栈，出栈，进栈。问出栈的序列是( ) A({e,d,c,b,a} B({b,a} C({b,c} D({c,d} 6(对任何一棵二叉树T，设N0、N1、N2分别是度数为0、1、2的结点数，则下列判断正确的是( ) A(N0,N2，1 B(N1,N0，1 C(N2,N0，1 D(N2,N1，1 7(在数据结构中，链表是( ) A(顺序存储的线性表 B(非顺序存储的线性表 C(非顺序存储的非线性表 D(顺序存储的非线性表 8(任意一棵树均可唯一地转换成与它对应的二叉树。由树转换成的二叉树中，顶点N的左右孩子分别是N在原树中对应顶点的( ) A(最左子顶点/最邻近的右兄弟 B(最右子顶点/最右的兄弟 C(最邻近的右兄弟/最左子顶点 D(最邻近的左兄弟/最邻近的右兄弟 9(给定一个数据结构G,(V，E)，V,,V1，V2，V3，V4，V5，V6，V7，V8,，E,,,,,,,,,,,。则G是:A(无向图 B(有向图 C(树 D(无回路图 10(一个栈的输入顺序为1、2、3、4、5，下列序列中可能是栈的输出序列的是( ) A(54312 B(24135 C(21543 D(12543 二、问题解答: 1(给出一组顶点(A、B、C、D、E、F)，其对应的权值分别为2,3，1,7，8,4。请以A、B、C、D、E、F为叶子顶点构造一棵哈夫曼树，并求出它的最小带权路径长度WPL的值。 哈夫曼树的构造算法: ?根据给定的N个权值{W1，W2，……，Wn}构成N棵二叉树的集合F={T1，T2，……，Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，其左右子树均为空。 ?在F中选取二棵根结点权值最小的树作为左右子树构造一棵新的二叉树，并置新的二叉树的根结点的权值为其左右子树上根结点权值之和。 ?在F中删除这两棵树，同时将新得到的二叉树加入到F中。 ?重复?、?两面三刀步，直到F中只有一棵树为止，这棵树便是哈夫曼树。 2(若一个栈中有5个元素，另一个栈中有4个元素，则它们出栈的方法有 种。 选择题练习--数据结构与算法练习题 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-f B(r-f+1 C((r-f) MOD n+1 D((r-f+n) MOD n 4、在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是( ) A(堆排序 B(希尔排序 C(冒泡排序 D(快速排序 5、在有n个子叶节点的哈夫曼树中，其节点总数为( ) A(不确定 B(2n-1 C(2n+1 D(2n 6、某数列有1000个各不相同的单元，由低到高按序排列，现要对该数列进行二分法检索，在最坏的情况下，需要检视( )个单元( ) A(1000 B(10 C(100 D(500 7、已知数组A中，每个元素A[I，J]在存储时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存储分配的。试问:A[5，8]的起始地址为( ) A(SA+141 B(SA+180 C(SA+222 D(SA+225 8、线性表若采用链表存储结构，要求内存中可用存储单元地址( ) A(必须连续 B(部分地址必须连续 C(一定不连续 D(连续不连续均可 9、下列叙述中，正确的是( ) A(线性表的线性存储结构优于链表存储结构 B(队列的操作方式是先进后出 C(栈的操作方式是先进先出D(二维数组是指它的每个数据元素为一个线性表的线性表 10、电线上停着两种鸟(A，B)，可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可公为两类:一类是两端的小鸟相同;另一类是两端的小鸟不相同。已知:电线上两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是( ) A(奇数 B(偶数 C(可奇可偶 D(数目固定 11、在列车转辙网络中，有四个车皮编号为1，2，3，4，并按此顺序送入栈中进行调度，这些车皮取出的顺序是( ) A(4123 B(3241 C(3412 D(4312 12、从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)的一端，这种排序方法称为( ) A(插入排序 B(归并排序 C(选择排序 D(快速排序 13、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于( )数据结构( ) A(栈 B(树 C(双向队列 D(广义表 14、使用双向链表存放数据的优点是( ) A(提高检索速度 B(很方便地插入和删除数据 C(节约存储空间 D(很快回收存储空间 15、对一个满二叉树，m个树叶，l分枝结点，n个结点，则( ) A(n=l+m B(l+m=2n C(m=l-1 D(n=2l-1 16、一维数组与线性表的区别是( ) 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(1 B(144 C(11 D(66 19、下面关于二叉树的叙述正确的是( ) A(一棵二叉树中叶子结点的个数等于度为2的结点个数加1 B(一棵二又树中的结点个数大于0 C(二叉树中任何一个结点要么是叶，要么恰有两个子女 D(二叉树中，任何一个结点的左子树和右子树上的结点个数一定相等 20、先序序列和中序序列相同的二叉树文二叉树的中序遍历序列相同 C(树的后根遍历序列与其对应的二叉树的先序遍历序列相同 D(树的后根遍历序列与其对应的二叉树的后序遍历序列相同 39、在数据结构中，从逻辑上可以把数据结构分成( ) A(动态结构和静态结构 B(线性结构和非线性结构 C(内部结构和外部结构 D(紧凑结构和非紧凑结构 40、如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的( ) A(前序 B(中序 C(后序 D(层次序 41、某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是( ) A(bdgcefha B(gdbecfha C(bdgaechf D(gdbehfca 42、从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)的一端，这种排序方法称为( ) A(插入排序 B(选择排序 C(归并排序 D(快速排序 43、快速排序方法在( )情况下最不利于发挥其长处( ) A(被排序的数据量太大 B(被排序数据中含有多个相同值 C(被排序数据已基本有序 D(被排序数据数目为奇 44、下面关于数据结构的叙述中，正确的叙述是( ) A(顺序存储方式的优点是存储密度大，且插入、删除运算效率高 B(链表中的每一个结点都包含一个指针 C(包含n个结点的二叉排序树的最大检索长度为log,-2n D(将一棵树转换为二又树后，根结点没有右子树 45、在计算机科学领域中,算法分为两类:数值型算法和非数值型算法。下面的算法，哪一个属于数值算法类( ) A(迭代法 B(冒泡法 C(黑盒法 D(杂凑(Hash)法 46、若已知一个栈的输入序列为1，2，3…，n，其输出序列为P1，P2，…，Pn。若P1=n，则Pi为( ) A(I B(n+I C(n-I+1 D(不确定 47、带头结点的单链表Head为空的判定条件是( ) A(Head=NIL B(Head^.Next=NIL C(Head^.Next=Head D(Head=Head 48、二维数组a的成员是6个字符组成的串，行下标I的范围从0到8，列下标j的范围从1到10，则存放a至少需要( )个字节( ) A(90 B(180 C(240 D(540 49、由3个结点可以构造出多少种不同的有向树( ) A(2 B(3 C(4 D(5 50、二维数组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，1 B(1，2，3，4 C(1，4，3，2 D(3，2，4，1 54、邻接表存储结构下图的深度优先遍历算法结构类似于二叉树的( ) 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，55 B(38，49，65，97，13，27，49，76，04，55 C(38，49，65，97，13，76，27，49，04，55 D(01，13，27，38，49，49，55，65，76，97 58、栈和队列都是( ) A(顺序存储的线性结构 B(链式存储的非线性结构 C(限制存取点的线性结构 D(限制存取点的非线性结构 59、对N个结点的线性表进行查找，用顺序查找的时间复杂性为( ) A(N*