《天大《数据结构》在线作业二答案》由会员分享，可在线阅读，更多相关《天大《数据结构》在线作业二答案（11页珍藏版）》请在金锄头文库上搜索。
1、数据结构在线作业二试卷总分:100 得分:100一、单选题 (共 40 道试题,共 100 分)1.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（ ）。A.P，A，C，S，Q，D，F，X，R，H，M，YB.H，C，Q，P，A，M，S，R，D，F，X，YC.F，H，C，D，P，A，M，Q，R，S，Y，XD.A，D，C，R，F，Q，M，S，Y，P，H，X答案:B2.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ ）。A.5，3，4，6，1，2B.3，2，5，6，4，1C.3，1，2，5，4，6D
2、.1，5，4，6，2，3答案:B3.数组的逻辑结构不同于下列（?）的逻辑结构。A.队列B.线性表C.树D.栈答案:C4.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。A.top=top-next;B.top=top-1;C.top=top+1;D.top-next=top;答案:A5.一个有n个顶点的无向图最多有（）条边。A.n(n-1)/2B.n(n-1)C.nD.2n答案:A6.设一个顺序有序表A1:14中有14个元素，则采用二分法查找元素A4的过程中比较 元素的顺序为( )。A.A7，A5 ，A3，A4B.A7，A3，A5，A4C.A1，A2，A3，A4D.A1
3、，A14，A7，A4答案:B7.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。A.43/12B.39/12C.37/12D.35/12答案:C8.在二叉排序树中插入一个关键字值的平均时间复杂度为（ ）。A.O(nlog2n)B.O(n2 )C.O(n)D.O(1og2n)答案:D9.设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（ ）。A.小于等于m的最大素数B.小于等于m的最大奇数C.小于等于m的最大合数D.小于等于m的最大偶数答案:A10.设F是由T1、T2和T3三棵树组成的森林，与F对应的二
4、叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（ ）。A.N2+N3B.N2-1C.N1+N3D.N1-1答案:D11.堆的形状是一棵（）。A.满二叉树B.平衡二叉树C.完全二叉树D.二叉排序树答案:C12.采用线性探测法解决冲突问题，所产生的一系列后继散列地址（）。A.必须小于等于原散列地址B.必须大于等于原散列地址C.地址大小没有具体限制D.可以大于或小于但不能等于原散列地址答案:D13.在一个图中，所有顶点的度数之和等于所有边数的（）倍。A.4B.2C.1/2D.1答案:B14.树最适合用来表示（）。A.有序数据元素B.无序数据元素C.元素
5、之间无联系的数据D.元素之间具有分支层次关系的数据答案:D15.设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点， 则该三叉链权中有（ ）个度数为0的结点。A.8B.7C.6D.5答案:B16.设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（ ）。A.99B.97C.93D.91答案:B17.对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为（）。A.k2B.k1-k2C.k1+k2D.k1答案:D18.设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ ）。A.head=0B
6、.head-next=headC.head-next=0D.head!=0答案:B19.队列是一种（ ）的线性表。A.只能插入B.只能删除C.先进后出D.先进先出答案:D20.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（ ）个结点。A.n+lB.2n+lC.2n-1D.2n答案:C21.设数据结构A=(D，R)，其中D=1，2，3，4，R=r，r=，则数据结构A是（?）。A.集合B.线性结构C.树型结构D.图型结构答案:D22.下述几种排序方法中，要求内存量最大的是（）。A.选择排序B.插入排序C.快速排序D.归并排序答案:D23.一组记录的关键码为（4
7、6，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A.40，38，46，84，56，79B.40，38，46，79，56，84C.40，38，46，56，79，84D.38，40，46，56，79，84答案:C24.设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A54地址与A00的地址之差为（ ）。A.55B.28C.19D.10答案:C25.任何一个无向连通图的最小生成树（）。A.有一棵或多棵B.可能不存在C.只有一棵D.一定有多棵答案:A26.设顺
8、序表的长度为n，则顺序查找的平均比较次数为（ ）。A.n/2B.nC.(n-1)/2D.(n+1)/2答案:D27.把一棵树转换为二叉树后，这棵二叉树的形态是（）。A.有多种，但根结点都没有左孩子B.有多种，但根结点都没有右孩子C.有多种D.唯一的答案:D28.二叉树是非线性数据结构，所以（）。A.顺序存储结构和链式存储结构都能存储B.顺序存储结构和链式存储结构都不能使用C.它不能用顺序存储结构存储D.它不能用链式存储结构存储答案:A29.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）.A.n/2B.nC.(n-1)/2D.(n+1)/2答案:D30.用某种排序方法对线性
9、表（ 25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下： 25，84，21，47，15，27，68，35，20； 20，15，21，25，47，27，68，35，84； 15，20，21，25，35，27，47，68，84； 15，20，21，25，27，35，47，68，84。则所采用的排序方法是（）。A.选择排序B.快速排序C.归并排序D.希尔排序答案:B31.二叉树中第i(i1)层上的结点数最多有（?）个。A.2i-1B.2i-1C.2iD.2i答案:B32.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X
10、，则在结点A和结点B插入结点X的操作序列为（ ）。A.s-next=p-next；p-next=-s；B.q-next=s； s-next=p；C.p-next=s；s-next=q；D.p-next=s-next；s-next=p；答案:B33.设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（ ）。A.s-left=p；s-right=p-right；p-right=s； p-right-left=s；B.s-left=p；s-right=p-right；p-right-left=s； p-right=s；C.p-right=s； s-
11、left=p； p-right-left=s； s-right=p-right；D.p-right=s； p-right-left=s； s-left=p； s-right=p-right；答案:B34.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论（）是正确的。A.树的后根遍历序列与其对应的二叉树的后序遍历序列相同B.树的先根遍历序列与其对应的二叉树的先序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对答案:B35.有8个结点的无向图最多有（）条边。
12、A.56B.28C.14D.112答案:B36.快速排序方法在（）情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据已基本有序C.要排序的数据中含有多个相同值D.要排序的数据个数为奇数答案:B37.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是（）。A.逆拓朴有序的B.无序的C.拓朴有序的D.不确定的答案:A38.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A.4B.2C.1/2D.1答案:D39.下述几种排序方法中，平均查找长度最小的是（）。A.选择排序B.插入排序C.快速排序D.归并排序答案:C40.二叉排序树中左子树上所有结点的值均（ ）根结点的值。A.B.=C.D.!=答案:C
