计算机等级考试（国家）-数据结构与算法(四)

《计算机等级考试（国家）-数据结构与算法(四)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构与算法（四）一、选择题丄、设用一维数组A[l,…，n]来存储一个栈，令A[11]为栈底，用整型变量，指示当前栈顶位置，A[T]为栈顶元素。当从栈中弹出一个元素时，变量T将变化为oA.T：=T+1B.T：=T-1C・T不变D・T：=n2、下列关键码序列小，是一个堆。A.{93,30,52,22,15,71}B.{15,52,22,93,30,71}C・{15,30,22,93,52,71}D・（15,71,30,22,93,52}3、设森林F中有3棵树。第一、第二和第三棵树的节点个数分别为

2、叫、叫和叫，则与森林，对应的二叉树根节点的右子树上的节点个数是。A.m3B.m2+m3C.nD.mY+m24、下列叙述小，正确的是oA.用指针的方式存储一棵有n个节点的二叉树最少需要n+1个指针B.不使用递归，也可以实现二乂树的前序、中序及后序周游C.已知树的前序周游并不能唯一确定一棵树，因为不知道树的根节点是哪一个D.任一棵树的平均查找时间都小于用顺序查找法查找同样节点的线性表的平均查找时间5、如果二叉树屮任何一个节点的值都小于它的右子树上所有节点的值，且大于左子树上所有节点的值，要得到各节

3、点值的递增序列，应按下列次序排列节点。A.先根B.中根C.后根D.层次6、如果节点A有3个兄弟节点，而且B是A的双亲节点，贝怕的度为A.2B.3C.4D.57、一个满二叉树,A.n=m+lC.n=2m共有n个节点，其中m个为树叶，则B.m=(n+1)/2D.n=2m8、对线性表进行二分法查找，其前提条件是oA.线性表以顺序方式存储，并且按关键码值排好序B.线性表以顺序方式存储，并冃按关键码值的检索频率排好序C.线性表以链接方式存储，并且按关键码值排好序D.线性表以链接方式存储，并且按关键码值的检

4、索频率排好序9、组记录的排序码为字母序列（Q,D,F,X,A,P,N,B,Y,M,C,W)，按归并排序方法对该序列进行一趟归并后的结果为0A.(D,F,Q,X,A,B,N,p,C,M,W,Y)B・(D,F,Q,A,P,X,B,N,Y,C,M,W)C・(D,Q,F,X,A,P,N,B,Y,M,C,W)D・(D,Q,F,X,A,P,B,N,M,Y,C,W）10、设有一个已按各元素的值排好序的线性表，其长度大于2,对给定的值k,分别用顺序查找法和二分查找法查找一个与k值相等的元素，比较的次数分别为s和

5、b。那么，在查找不成功的情况下，正确的s和b的数量关系是。A・与k值大小冇关B.总冇s=bC.总有s＞bD.总有sVb11＞已知待排序的记录的关键字为{50,34,65,76,97,27,13,37,49},釆用直接插入的排序方法将记录按关键字从小到大排序。当插入37时，需要比较的记录个数为。A.2B.3C・4D・512、现有一棵度为3的树，它含有两个度为3的节点，一个度为2的节点和两个度为1的节点，由此可知度为0的节点数为oA.4B.5C・6D.713＞若进栈序列为a,b,c,d,进栈过程中可

6、以出栈，则不可能是一个岀栈序列。A.a,d,c,bB.b,c,d,aC・c,a,d,bD.c,d,b,a14、排序的重要目的是为了以后对已排序的数据元素进行oA.打印输岀B.分类C.查找D.合并15、栈和队列都是oA•限制存取点的线性结构B.限制存取点的非线性结构C.顺序存储的线性结构D.链式存储的线性结构16、具冇X个记录的序列，采用冒泡排序，最少的比较次数是。A.11B.66C・1D・14417、一组记录的排序码为(46,79,56,38,40,84)，则利用堆排序的方法建立的初始堆为。A.

7、(79,46,56,38,40,84)B.(84,79,56,38,40,46)C・(84,79,56,46,40,38)D.(84,56,79,40,38,46)18、以卜•有关数据结构的叙述，正确的是oA.线性表的线性存储结构优于链式存储结构B.二叉树的第i层上有个节点，深度为k的二叉树上有2k-l个节点C.二维数组是其数据元素为线性表的线性表D.栈的操作方式是先进先出19、二维数组M[i,j]的元索是由4个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到4,列卜.标j的范围从0

8、到5。M按行存储时元素M[3,5]的起始地址与M按列存储时元素的起始地址相同。A.M[2,4]B・M[3,4]C・M[3,5]D・M[4,4]20、有一组随机数:25,84,21,47,15,27,68,35,20。现在采用某种算法对它们进行排序,具体过程如下：I・258421471527683520II.201521254727683584III.152021253527476884IV.152021252735476884A.选择排序B.快速排序C.冒泡排序D.希尔排序21、已知8个数据元素