华师网络学院作业答案-数据结构选择题

1、排序趟数与序列的原始状态有关的排序方法是（）排序法。A.插入B.选择C.希尔D.快速答案:D已知森林F=T1,T2,T3,各棵树Ti（i=1,2,3）中所含结点的个数分别为7,3,5,则与F对应的二叉树的右子树中的结点个数为（）。A.10B.12C.8D.15答案:C以下叙述错误的是（）。A.数据可分为数值型和非数值型B.数据类型可分为原子类型和结构类型C.运算可分为加工型和引用型D.数据结构可分为逻辑结构和非逻辑结构答案:D设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是（）。s->next=p->next;p->next=s;t=p->data;

2、p->data=s->data;s->data=t;A.结点*p与结点*s的数据域互换B.在p所指结点的元素之前插入元素C.在p所指结点的元素之后插入元素D.在结点*p之前插入结点*s答案:D对二叉排序树进行（），可以得到各结点键值的递增序列。A.先根遍历'B.中根遍历C.层次遍历D.后根遍历答案:B栈和队列都是（）。A.限制存取位置的线性结构B.顺序存储的线性结构C.链式存储的线性结构D.限制存取位置的非线性结构答案:A设S="abc"；T="xyz"，则strcmp（S,T）的值为（）。A.正数B.负数CWD.不确定答案:B

3、对n个顶点和e条边的有向图，以邻接矩阵存储，则求图中某顶点入度的时间复杂度为A)O(n)B)O(e)C)O(n+e)_2D)O(n)A.AB.BC.CD.D答案:A若下图表示某广义表，则它是一种()。A.线性表B.纯表C.再入表D.递归表答案:B在不完全排序的情况下，就可以找出前几个最大值的方法是()A.快速排序B.直接插入排序C.堆排序D.归并排序答案:C关于哈夫曼树，下列叙述正确的是()。A.可能有度为1的结点B.总是完全二叉树C.有可能是满二叉树D.WPL深度最大叶子的带权路径长度答案:C二叉树的结构如下图所示，其中序遍历的序列为()A.a,b,d,g,c,e,f,hB.d,g,b,a,

4、e,c,h,fC.g,d,b,e,h,f,c,aD.a,b,c,d,e,f,g,h答案:B将数组称为随机存储结构是因为()。A.数组元素是随机的B.随时可以对数组元素进行访问C.对数组的任一元素的存取时间是相等的D.数组的存储结构是不定的答案:C时间复杂性为O(nlog2n)且空间复杂性为0(1)的排序方法是()。A.归并排序B.堆排序C.快速排序D.锦标赛排序答案:B要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为A.逻辑结构、存储结构、机外表示B.存储结构、逻辑结构、机外表示C.机外表示、逻辑结构、存储结构D.机外表示、存储结构、逻辑结构答案:C求单链表中当前结点的后继和前

5、趋的时间复杂度分别是()A.O(n)和O(1)B.O(1)和O(1)C.O(1)和O(n)D.O(n)和O(n)答案:C高度为n、结点数也为n的二叉树，共有()棵。A) nB) 2n-1C) n-1D) 2n-1A.AB.BC.CD.D答案:D对线性表进行二分查找时，要求线性表必须()。A.以顺序方式存储B.以链接方式存储C.顺序存储，且结点按关键字有序排序D.链式存储，且结点按关键字有序排序答案:C下面关于B树和B+M的叙述中，不正确的是A.都是平衡的多叉树B.都是可用于文件的索引结构C.都能有效地支持顺序检索D.都能有效地支持随机检索答案:D设输入序列为A,B,C,D,借助一个栈得到的输出

6、序列不可能是()。A.ABCDB.ACDBC.DABCD.DCBA答案:C连通图是指图中任意两个顶点之间()。A.都连通的无向图B.都不连通的无向图C.都连通的有向图D.都不连通的有向图答案:A设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为()。A)O(nlog2n)B)O(en)C)O(elog2n)D)O(n+e)A.AB.BC.CD.D答案:Dn。从理论上讲，将数据以()结构存放，查找一个数据的时间不依赖于数据的个数A.二叉查找树B.链表C.散列表D.顺序表答案:Cn个记录直接选择排序时所需的记录最多交换次数是()。A.n-1B.nC.n(n-1)/2D.n(n+1)/2答案:

7、A连通网的最小生成树是其所有生成树中()。A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树答案:D下列各式中，按增长率由小至大的顺序正确排列的是()。A. n：n!,2n,n3/2B. n3/2,2n,nlogn,2100C. 2n,logn,nlogn,n3/2D. 2100,logn,2n,nnA.AB.BC.CD.D答案:D若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用()存储方式最节省运算时间()。A.单链表B.顺序表C.双链表D.单循环链表答案:B下述序列中，哪个可能是在二叉排序树上查找35时所比较过的关键字序

8、列？A.2254039533435B.2539240533435C.5340,225343935D.39,25405334235答案:C导致队列下溢的操作是()A.队满时执行出队B.队满时执行入队C.队空时执行出队D.队空时执行入队答案:C以下广义表关系正确的是()。A.线性表再入表纯表递归表B.线性表纯表递归表再入表C.纯表线性表再入表递归表D.线性表纯表再入表递归表答案:D对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8,查找后面5个元素的概率相同，均为3/40,则查找任一元素的平均查找长度为()。A.5.5B.5C.39/8D.19/4答案:C用链表表示线性表的优点

9、是()0A.便于随机存取B.花费的存储空间较顺序存储少C.便于插入和删除D.数据元素的物理顺序与逻辑顺序相同答案:C线索二叉树中某结点没有左孩子的条件是()oA.p!=NULLB.p-ltag=0C.p-ltag=1D.p-lchild!=NULL答案:C以下叙述错误的是()。A.树的先根遍历需要借助栈来实现。B.树的层次遍历需要借助队列来实现。C.树的后根遍历与对应二叉树的后根遍历相同。D.树的先根序列与对应二叉树的先根序列相同。答案:C算法的时间复杂度取决于()。A.问题的规模B.数据的初始状态C.A和BD.以上都不是答案:C单链表中增加头结点的目的是为了()oA.使单链表至少有一个结点B

10、.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储答案:C在索引顺序表中查找一个元素，可用的且最快的方法是()。A.用顺序查找法确定元素所在块,再用顺序查找法在相应块中查找B.用顺序查找法确定元素所在块，再用二分查找法在相应块中查找C.用二分查找法确定元素所在块，再用顺序查找法在相应块中查找D.用二分查找法确定元素所在块，再用二分查找法在相应块中查找答案:C栈操作的原则是()oA.先进先出B.后进先出C.栈底删除D.以上都不是答案:B下列关于用的叙述中，正确的是()。A.一个用的字符个数即该用的长度B.一个串的长度至少是1C.空用是由空格字符组成的用D.两个用若长度相

11、同，则它们相等答案:A假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行()次探侧A.k-1B.kC.k+1D.k(k+1)/2答案:Dn个记录直接插入排序时所需的记录最少比较次数是()。A.n-1B.nC.n(n-1)/2D.n(n+1)/2答案:A某二叉树的先根遍历序列和后根遍历序列相同，则该二叉树的特征是()。A.高度等于其结点数B.任一结点无左孩子C.任一结点无右孩子D.空或只有一个结点答案:D下面关于图的存储的叙述中，()是正确的。A.邻接矩阵表示时，占用的存储空间数只与图中结点个数有关，而与边数无关B.邻接矩阵表示时，占用的存储空间数只与图中边数有关，

12、而与结点个数无关C.邻接表表示时，占用的存储空间数只与图中结点个数有关，而与边数无关D.邻接表表示时，占用的存储空间数只与图中边数有关，而与结点个数无关答案:A二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序()A.可能改变B.一定会改变C.一定不改变D.可能变也可能不变答案:C关于矩阵的三元组表表示，以下叙述正确的是()。A.转置运算时只需把每个三元组的行、列下标互换即可。B.存储时只需要各非零元素的三元组信息，不需要其它信息。C.适合于对称矩阵的压缩存储。D.访问元素时不能随机存取。答案:D线性表采用链式存储时，其地址()oA.必须连续B.部分地址必须连续C.一定不连续D.连续与否均

13、可答案:D在AVL树中，任一结点的()。A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左、右子树的结点数均相同D.左、右子树结点数差的绝对值不超过1答案:B用是()oA.一些符号构成的序列B.有限个字母构成的序列C.一个以上的字符构成的序列D.有限个字符构成的序列答案:D基数排序中的“基数”可以是()。A.10B.8C.16D.以上都可以答案:D()存储方式适用于折半查找。A.键值有序的单链表B.键值有序的顺序表C.键值有序的双链表D.键值无序的顺序表答案:B在需要经常查找结点的前趋与后继的场合中，使用()比较合适。A.单链表B.双链表C.循环链表D.顺序表答案:Dn个顶点

14、的强连通图若只有n条边，则该有向图的形状是()。A.无回路B.有回路C.环状D.树状答案:C若结点的存储地址与结点内容有某种确定的关系，则相应的存储结构应为()A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构答案:D下列有关线性表的叙述中，正确的是()。A.元素之间是线性关系B.线性表中至少有一个元素C.任一元素有且仅有一个直接前趋D.任一元素有且仅有一个直接后继答案:A若只在线性表的首、尾两端进行插入操作，宜采用的存储结构为()oA.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表答案:C队列操作的原则是()oA.先进先出B.后进先出C.队尾删除D.队

15、头插入答案:A下列查找方法中，不属于动态的查找方法是()。A.二叉排序树法B.平衡树法C.散列法D.二分查找法答案:DXtn个元素进行冒泡排序，最好情况下的只需进行()对相邻元素之间的比较A.nB.n-1C.n+1D.n/2答案:B线索二叉树中某结点为叶子的条件是()A.p->lchild!=NULL|p->rchild!=NULLB.p->ltag=0|p->rtag=0C.p->lchild!=NULL&&p->rchild!=NULLD.p->ltag=1&&p->rtag=1答案:D图的深度遍历必须借助()

16、作为辅助空间A.栈B.队列C.查找表D.数组答案:A下图是一棵()A.4阶B-树B.4阶B+WC.3阶B-树D.3阶B+W答案:DA.AB.BC.CD.D答案:C对有向图，下面()种说法是正确的。A.每个顶点的入度等于出度B.每个顶点的度等于其入度与出度之和C.每个顶点的入度为0D.每个顶点的出度为0答案:B下列排序算法中，当初始数据有序时，花费时间反而最多的是（）。A.起泡排序B.希尔排序C.堆排序D.快速排序答案:D下列编码中属前缀码的是（）。A.1,01,000,001）B.1,01,011,010）C.0,10,110,11D.0,1,00,11答案:A稀疏矩阵常用的压缩存储方法有两种

17、，即（）。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表答案:C执行下列程序段后，XX的值为（）oS="abc"；T="xyz"；X=strcat（S,T）;A.”abcxyz”B. xyzabcC. abcD. xyz答案:A循环链表的主要优点是（）。A.不在需要头指针了B.已知某个结点的位置后，能够容易找到他的直接前趋C.在进行插入、删除运算时，能更好的保证链表不断开D.从表中的任意结点出发都能扫描到整个链表答案:D若要在O（1）的时间内将两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向A.各自的头结点B

18、.各自的尾结点C.各自的第一个元素结点D.一个表的头结点，另一个表的尾结点答案:B有n个顶点的图形成一个环，则其生成树的个数为（）A.1B.n-1C.nD.n+1答案:C栈和队列通常采用的两种存储方式是()A.散列存储和索引存储B.索引存储和链式存储C.顺序存储和链式存储D.散列存储和顺序存储答案:C若进栈序列为a,b,c,则通过入出栈操作能得到的a,b,c的不同排列个数为()A.4B.5C.6D.7答案:B若下图表示某广义表，则它是一种()A.线性表B.纯表C.再入表D.递归表答案:C在有头结点的单链表L中，向表头插入一个由指针p指向的结点，则执行()A.L=p;p->next=L;B

19、.p->next=L;L=p;C.p->next=L;p=L;D.p->next=L->next;L->next=p;答案:D对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为()oA.求顶点的邻接点B.求顶点的度C.深度优先遍历D.广度优先遍历答案:B为便于判别有向图中是否存在回路，可借助于()。A.广度优先搜索算法B.最小生成树算法C.最短路径算法D.拓扑排序算法答案:D若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用()存储方式最节省运算时间。A.单链表B,仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表答案:D在二叉链表上交换所有分支结点左右子树的位置，则利用()遍历方法最合适。A.前序B.中序C.后序D.按层次答案:C又tn个顶点的有向图，若所有顶点的出度之和为s,则所有顶点的入度之和为()oA.sB.s-1C.s+1D.n答案:A在AVL树中