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-nex
2、t=s;t=p-data;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.负数C.零D.不确定选择题答案对n个顶点和e条边的有向图，以邻接矩阵
3、存储，则求图中某顶点入 度的时间复杂度为( )。A)O(n)B)O(e)C)O(n+e)D)O(n2)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,e,c
4、,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)且空间复杂性为O(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-1选择题答案D)2n-1A.AB.BC.CD.D答案:D对线性表进行二分查找时，要求线性表必须( )。A.以顺序方式存储B.以链接方式存储C.顺序存储，且结点按关键字有序排序D.链式存储，且结点按关键字有序排序答案:C下面关于B树和B+树的叙述中，不正确的是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答案:D从理论上讲，将数据以( )结构存放，查找一个数据的时间不依赖于数 据的个数n。A.二叉查找树选择题答案D.顺序表答案:Cn个记录直接选择排序时所需的记录最多交换次数是( )。A.n-1B.nC.n(n-1)/2D.n(n+1
7、)/2答案:A连通网的最小生成树是其所有生成树中( )。A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树答案:D下列各式中，按增长率由小至大的顺序正确排列的是( )。1/2n3/2An，n!，2 ，n3/2nlogn100Bn，2，n，2nlogn3/2C2，logn，n，n100nnD2，logn, 2, nA.AB.BC.CD.D答案:D若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元 素，则采用( )存储方式最节省运算时间( )。A.单链表B.顺序表C.双链表D.单循环链表答案:B下述序列中，哪个可能是在二叉排序树上查找35时
8、所比较过的关键 字序列？A.2，25，40，39，53，34，35B.25，39，2，40，53，34，35C.53，40，2，25，34，39，35D.39，25，40，53，34，2，35答案:C导致队列下溢的操作是( )。A.队满时执行出队B.队满时执行入队C.队空时执行出队D.队空时执行入队选择题答案以下广义表关系正确的是( )。A.线性表再入表纯表递归表B.线性表纯表递归表再入表C.纯表线性表再入表递归表D.线性表纯表再入表递归表答案:D对长度为10的顺序表进行查找，若查找前面5个元素的概率相同， 均为1/8，查找后面5个元素的概率相同，均为3/40，则查找任一元素的 平均查找长度为
9、( )。A.5.5B.5C.39/8D.19/4答案:C用链表表示线性表的优点是( )。A.便于随机存取B.花费的存储空间较顺序存储少C.便于插入和删除D.数据元素的物理顺序与逻辑顺序相同 答案:C线索二叉树中某结点没有左孩子的条件是( )。A.p!NULLB.p- ltag=0C.p- ltag=1D.p- lchild!NULL答案:C以下叙述错误的是( )。A.树的先根遍历需要借助栈来实现。B.树的层次遍历需要借助队列来实现。C.树的后根遍历与对应二叉树的后根遍历相同。 D.树的先根序列与对应二叉树的先根序列相同。 答案:C算法的时间复杂度取决于( )。A.问题的规模B.数据的初始状态C
10、.A和BD.以上都不是答案:C单链表中增加头结点的目的是为了( )。A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储 选择题答案 在索引顺序表中查找一个元素，可用的且最快的方法是( )。A.用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找 B.用顺序查找法确定元素所在块，再用二分查找法在相应块中查找 C.用二分查找法确定元素所在块，再用顺序查找法在相应块中查找 D.用二分查找法确定元素所在块，再用二分查找法在相应块中查找 答案:C栈操作的原则是( )。A.先进先出B.后进先出C.栈底删除D.以上都不是答案:B下列关于串的叙述中，正
11、确的是( )。A.一个串的字符个数即该串的长度B.一个串的长度至少是1C.空串是由空格字符组成的串D.两个串若长度相同，则它们相等答案: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下面关于图的存储的叙述中，( )是正确
12、的。A.邻接矩阵表示时，占用的存储空间数只与图中结点个数有关,而与边 数无关B.邻接矩阵表示时，占用的存储空间数只与图中边数有关,而与结点个 数无关C.邻接表表示时，占用的存储空间数只与图中结点个数有关，而与边 数无关D.邻接表表示时，占用的存储空间数只与图中边数有关，而与结点个 数无关答案:A选择题答案二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序( )。A.可能改变B.一定会改变C.一定不改变D.可能变也可能不变答案:C关于矩阵的三元组表表示，以下叙述正确的是( )。A.转置运算时只需把每个三元组的行、列下标互换即可。B.存储时只需要各非零元素的三元组信息，不需要其它信息。C.适合
13、于对称矩阵的压缩存储。D.访问元素时不能随机存取。答案:D线性表采用链式存储时，其地址( )。A.必须连续B.部分地址必须连续C.一定不连续D.连续与否均可答案:D在AVL树中，任一结点的( )。A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左、右子树的结点数均相同D.左、右子树结点数差的绝对值不超过1答案:B串是( )。A.一些符号构成的序列B.有限个字母构成的序列C.一个以上的字符构成的序列D.有限个字符构成的序列答案:D基数排序中的“基数”可以是( )。A.10B.8C.16D.以上都可以答案:D( )存储方式适用于折半查找。A.键值有序的单链表B.键值有序的顺序表C
14、.键值有序的双链表D.键值无序的顺序表答案:B选择题答案A.单链表B.双链表C.循环链表D.顺序表答案:Dn个顶点的强连通图若只有n条边，则该有向图的形状是( )。A.无回路B.有回路C.环状D.树状答案:C若结点的存储地址与结点内容有某种确定的关系，则相应的存储结构应为( )。A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构答案:D下列有关线性表的叙述中，正确的是( )。A.元素之间是线性关系B.线性表中至少有一个元素C.任一元素有且仅有一个直接前趋D.任一元素有且仅有一个直接后继答案:A宜采用的存储结构为( )。若只在线性表的首、尾两端进行插入操作，A.顺序表B.用头指针表
15、示的单循环链表C.用尾指针表示的单循环链表D.单链表答案:C队列操作的原则是( )。A.先进先出B.后进先出C.队尾删除D.队头插入答案:A下列查找方法中，不属于动态的查找方法是( )。A.二叉排序树法B.平衡树法C.散列法D.二分查找法答案:D对n个元素进行冒泡排序，最好情况下的只需进行( )对相邻元素之间 的比较。选择题答案B.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-
16、ltag=1 p- rtag=1答案:D图的深度遍历必须借助( )作为辅助空间。A.栈B.队列C.查找表D.数组答案:A下图是一棵( )。A.4阶B-树B.4阶B+树C.3阶B-树D.3阶B+树答案:D下面的二叉树中，( )不是完全二叉树。A.AB.BC.CD.D答案:C对有向图，下面( )种说法是正确的。A.每个顶点的入度等于出度选择题答案C.每个顶点的入度为0D.每个顶点的出度为0答案:B下列排序算法中，当初始数据有序时，花费时间反而最多的是( )。A.起泡排序B.希尔排序C.堆排序D.快速排序答案:D下列编码中属前缀码的是( )。A.1,01,000,001B.1,01,011,010C
17、.0,10,110,11D.0,1,00,11答案:A稀疏矩阵常用的压缩存储方法有两种，即( )。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表答案:C执行下列程序段后，串X的值为( )。S=”abc”;T=”xyz”;X=strcat(S,T);A.”abcxyz”B.”xyzabc”C.”abc”D.”xyz”答案:A循环链表的主要优点是( )。A.不在需要头指针了B.已知某个结点的位置后，能够容易找到他的直接前趋C.在进行插入、删除运算时，能更好的保证链表不断开D.从表中的任意结点出发都能扫描到整个链表答案:D若要在O(1)的时间内将两个循环链表头尾相接，则
18、应对两个循环链表 各设置一个指针，分别指向( )。A.各自的头结点B.各自的尾结点C.各自的第一个元素结点D.一个表的头结点，另一个表的尾结点答案:B有n个顶点的图形成一个环，则其生成树的个数为( )。A.1B.n-1选择题答案D.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在有头结点的单链表
19、L中，向表头插入一个由指针p指向的结点，则 执行( )。A.L=p; p- next=L;B.p- next=L; L=p;C.p- next=L; p=L;D.p- next=L- next; L- next=p;答案:D对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为( )。A.求顶点的邻接点B.求顶点的度C.深度优先遍历D.广度优先遍历答案:B为便于判别有向图中是否存在回路，可借助于( )。A.广度优先搜索算法B.最小生成树算法C.最短路径算法D.拓扑排序算法选择题答案若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( )存储方式最节省运算时间。
20、A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表答案:D在二叉链表上交换所有分支结点左右子树的位置，则利用( )遍历方法 最合适。A.前序B.中序C.后序D.按层次答案:C对n个顶点的有向图，若所有顶点的出度之和为s，则所有顶点的入 度之和为( )。A.sB.s-1C.s+1D.n答案:A在AVL树中，每个结点的平衡因子的取值范围是( )。A.-11B.-22C.12D.01答案:A最好和最坏时间复杂度均为O(nlog2n)且稳定的排序方法是( )。A.快速排序B.堆排序C.归并排序D.基数排序答案:C树结构最适合用来表示( )。A.有序数据B.无序数据C.元素间具有分
21、支层次关系的数据D.元素间无关联的数据答案:C算法分析的目的是( )。A.找出数据结构的合理性B.研究算法中的输入/输出关系C.分析算法的效率以求改进D.分析算法的易读性选择题答案设输入序列为A,B,C,D，借助一个队列得到的输出序列可能是( )。A.ABCDB.DCBAC.任意顺序D.以上都不是答案:A关键字比较次数与数据的初始状态无关的排序算法是( )。A.直接选择排序B.冒泡排序C.直接插入排序D.希尔排序答案:A若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问 所有顶点，则必须调用( )次深度优先搜索遍历的算法。A.1B.kC.k-1D.k+1答案:B3个结点可构成( )个
22、不同形态的二叉树。A.2B.3C.4D.5答案:D以下关于算法叙述不正确的是( )。A.时间和空间性能往往是一对矛盾B.常常可牺牲空间性能换取时间性能C.常常可牺牲时间性能换取空间性能D.时间和空间性能并不会矛盾答案:D若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是( )。A.s- next=p- next; p- next=s;B.p- next=s; s- next=p- next;C.p- next=s- next; s- next=p;D.s- next=p; p- next=s- next;答案:A设计一个判断表达式中左右括号是否配对出现的算法，采用( )数据结构最好
23、。A.顺序表B.链表C.队列D.栈选择题答案要解决散列引起的冲突问题，常采用的方法有( )。A.数字分析法、平方取中法B.数字分析法、线性探测法C.二次探测法、平方取中法D.二次探测法、链地址法答案:D某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最 后一个元素，则采用( )存储方式最节省运算时间。A.单链表B.双链表C.单循环链表D.带头结点的双循环链表答案:D由同一关键字集合构造的各棵二叉排序树( )。A.形态和平均查找长度都不一定相同B.形态不一定相同，但平均查找长度相同C.形态和平均查找长度都相同D.形态相同，但平均查找长度不一定相同答案:A在散列查找中，平均查找长度主要与
24、( )有关。A.散列表长度B.散列元素的个数C.装填因子D.处理冲突方法答案:C在待排关键字序列基本有序的前提下，效率最高的排序方法是( )。A.直接插入排序B.快速排序C.直接选择排序D.归并排序答案:A在n个顶点和e条边的无向图的邻接表中，存放表头结点的数组的大 小为( )。A.nB.n+eC.n+2eD.e答案:A在顺序表中，数据元素之间的逻辑关系用( )。A.数据元素的相邻地址表示B.数据元素在表中的序号表示C.指向后继元素的指针表示D.数据元素的值表示选择题答案下列哪种情况需要遇到队列( )。A.迷宫求解B.括号匹配C.多级函数调用D.多项打印任务的安排答案:D若下图表示某广义表，则
25、它是一种( )。A.线性表B.纯表C.再入表D.递归表答案:D对关键字序列Q,H,C,Y,P,A,M,S,R,D,F,X，用下列( )方法进行第一趟排 序的结果为F,H,C,D,P,A,M,Q,R,S,Y,X。A.直接插入排序B.二路归并排序C.以第一元素为基准的快速排序D.基数排序答案:C对关键字序列(14,5,19,20,11,19)，第一趟排序的结果为(14,5,19,20,11,19)，则可能的排序方法是( )。A.简单选择排序B.快速排序C.希尔排序D.二路归并排序答案:C下图所示二叉树对应的森林中有( )棵树。A.1B.2选择题答案答案:C在下列排序方法中，空间复杂性为O(log2
26、n)的方法为( )。A.直接选择排序B.归并排序C.堆排序D.快速排序答案:D串是一种( )线性表。A.长度受限B.元素类型受限C.操作受限D.一般答案:B与邻接表表示相比，邻接矩阵表示更适合( )。A.无向图B.有向图C.稠密图D.稀疏图答案:C算法分析是指( )。A.分析算法的正确性B.分析算法的可读性C.分析算法的健壮性D.分析算法的时空性能答案:D下面关于线性表的叙述错误的是( )。A.线性表采用顺序存储，必须占用一片地址连续的单元； B.线性表采用顺序存储，便于进行插入和删除操作； C.线性表采用链式存储，不必占用一片地址连续的单元； D.线性表采用链式存储，便于进行插入和删除操作；
27、 答案:B 在下列排序方法中，空间复杂性为O(n)的方法为( )。A.快速排序B.直接插入排序C.堆排序D.归并排序答案:D除根结点外，树上每个结点( )。A.可有任意多个孩子、一个双亲B.可有任意多个孩子、任意多个双亲C.可有一个孩子、任意多个双亲选择题答案串s=Data Structure中长度为3的子串的数目是( )。A.9B.11C.12D.14答案:C若有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑 有序序列( )。A.存在B.不存在C.不确定答案:B以下叙述错误的是( )。A.数据的三个层次是数据、数据元素、数据项B.数据类型是指相同性质的计算机数据的集合C.每种逻辑结
28、构都有一个运算的集合D.储存结构中不仅要储存数据的内容，还要把数据间的关系表示出 来。答案:B在循环双链表的p所指结点之后插入s所指结点的操作是( )。A.p- next=s; s- prior=p; p- next- prior=s; s- next=p- next;B.p- next=s; p- next- prior=s; s- prior=p; s- next=p- next;C.s- prior=p; s- next=p- next; p- next=s; p- next- prior=s;D.s- prior=p; s- next=p- next; p- next- prior=s
29、; p- next=s;答案:D在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用( )。A.数据元素的相邻地址表示B.数据元素在表中的序号表示C.指向后继元素的指针表示D.数据元素的值表示答案:C如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是 ( )。A.有向完全图B.连通图C.强连通图D.有向无环图答案:D给定整数集合3,5,6,9,12，与之对应的哈夫曼树是( )。选择题答案C.CD.D答案:C静态查找表与动态查找表二者的根本差别在于( )。A.它们的逻辑结构不一样B.施加在其上的操作不同C.所包含的数据元素的类型不一样D.存储实现不一样答案:B多维数组之所以有行优先顺
30、序和列优先顺序两种存储方式是因为( )。A.数组的元素处在行和列两个关系中B.数组的元素必须从左到右顺序排列C.数组的元素之间存在次序关系D.数组是多维结构，内存是一维结构答案:A在索引查找中，若主表长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为( )。A.13B.24C.12D.79答案:A栈和队列的共同特点是( )。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点答案:C希尔排序的增量序列必须是( )。A.递增的B.随机的C.递减的D.任意的答案:C可应用的串运算是( )。为查找某一特定单词在文本中出现的位置，A.插入B.删除C.串联接D.子串定位答案:D某完全二叉树有7个叶子，则其结点总数为( )。
