南开大学22春“计算机科学与技术”《数据结构》平时作业（一）答案参考10

《南开大学22春“计算机科学与技术”《数据结构》平时作业（一）答案参考10》由会员分享，可在线阅读，更多相关《南开大学22春“计算机科学与技术”《数据结构》平时作业（一）答案参考10（13页珍藏版）》请在装配图网上搜索。

1、书山有路勤为径，学海无涯苦作舟！ 住在富人区的她南开大学22春“计算机科学与技术”数据结构平时作业（一）答案参考一.综合考核(共50题)1.已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是()A.0 2 4 3 1 5 6B.0 1 3 6 5 4 2C.0 4 2 3 1 6 5D.0 3 6 1 5 4 2参考答案：C2.任何一个无向连通图的最小生成树()。A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在参考答案：A3.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。()A.正确B.错误参考答案：B4.对于一棵非空二叉树

2、，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。()A.错误B.正确参考答案：A5.任何一个无向连通图的最小生成树()A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在参考答案：A6.数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为()A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构参考答案：C7.链表的每个结点中都恰好包含一个指针。()A.正确B.错误参考答案：B8.设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为()。A.循环链表B.单链表C.双向循环链表D.双向链表参考答案：B9.数组Qn用来表示一个循环队列

3、，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素的公式为()A.r-fB.(n+f-r)% nC.n+r-fD.(n+r-f)% n参考答案：D10.排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()。A.希尔排序B.冒泡排序C.插入排序D.选择排序参考答案：C11.单链表的存储密度()A.等于1B.小于1C.大于1D.不能确定参考答案：B12.折半搜索与二叉搜索树的时间性能()A.相同B.完全不同C.有时不相同D.数量级都是O(log2n)参考答案：C13.已知图的邻接

4、矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是()。A.0 2 4 3 1 5 6B.0 1 3 5 6 4 2C.0 4 2 3 1 6 5D.0 1 3 4 2 5 6参考答案：D14.设串s1=ABCDEFG，s2=PQRST，函数con(x，y)返回x和y串的连接串，subs(s， i， j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1， 2， len(s2)， subs(s1， len(s2)， 2)的结果串是()A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF参考答案：D15.折半查找有序表(4，6，

5、10，12，20，30，50，70，88，100)。若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。A.30，88，70，50B.30，88，50C.20，70，30，50D.20，50参考答案：C16.若已知一个栈的入栈序列是1，2，3，.，n，其输出序列为p1，p2，p3，.，pn，若p1=n，则pi为()。A.iB.n=iC.n-i+1D.不确定参考答案：C17.若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为()A.iB.n=iC.n-i+1D.不确定参考答案：C18.链表适用于()查找A.顺序B.二分法C.顺序，也能二

6、分法D.随机参考答案：A19.广度优先遍历类似于二叉树的()A.先序遍历B.中序遍历C.后序遍历D.层次遍历参考答案：D20.有8个结点的有向完全图有()条边。A.14B.28C.56D.112参考答案：C21.下述几种排序方法中，要求内存最大的是()A.插入排序B.快速排序C.归并排序D.选择排序参考答案：C22.二叉树中每个结点的两棵子树是有序的。()A.正确B.错误参考答案：A23.串是一种特殊的线性表，其特殊性体现在()A.可以顺序存储B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符参考答案：B24.顺序存储方式只能用于存储线性结构。()A.正确B.错误参考答案：B25

7、.判定一个栈ST(最多元素为m0)为空的条件是()A.ST-top0B.ST-top=0C.ST-topm0D.ST-top=m0参考答案：B26.若已知一个栈的入栈序列是1，2，3，.，n，其输出序列为p1，p2，p3，.，pn，若p1=n，则pi为()A.iB.n=iC.n-i+1D.不确定参考答案：C27.一棵具有n个结点的完全二叉树的树高度(深度)是()A.logn+1B.logn+1C.lognD.logn-1参考答案：A28.已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是()。A.0 2 4 3 6 5 1B.0 1 3 6 4 2 5C.0 4 2 3 1

8、 5 6D.0 1 3 4 2 5 6参考答案：B29.已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是()A.0 2 4 3 1 5 6B.0 1 3 6 5 4 2C.0 4 2 3 1 6 5D.0 3 6 1 5 4 2参考答案：C30.对个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。()A.从小到大排列好的B.从大到小排列好的C.元素无序D.元素基本有序参考答案：B31.下列关键字序列中，()是堆A.94，23，31，72，16，53B.16，72，31，23，94，53C.16，53，23，94，31，72D.16，23，53，31，94，72

9、参考答案：D32.线性表L在()情况下适用于使用链式结构实现。A.需经常修改L中的结点值B.需不断对L进行删除插入C.L中结点结构复杂D.L中含有大量的结点参考答案：B33.已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是()A.0 2 4 3 1 5 6B.0 1 3 6 5 4 2C.0 4 2 3 1 6 5D.0 3 6 1 5 4 2参考答案：C34.在表结构中最常用的是线性表，栈和队列不太常用。()A.正确B.错误参考答案：B35.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。()A.正确B.错误参考答案：B36.链表的物理存储结构具有

10、同链表一样的顺序。()A.正确B.错误参考答案：B37.把一棵树转换为二叉树后，这棵二叉树的形态是()。A.唯一的B.有多种C.有多种，但根结点都没有左孩子D.有多种，但根结点都没有右孩子参考答案：A38.链表的物理存储结构具有同链表一样的顺序。()A.错误B.正确参考答案：A39.链表适用于()查找。A.顺序B.二分法C.顺序，也能二分法D.随机参考答案：A40.设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。参考答案：链式存储结构略，前序：ABDEC，中序：DBEAC，后序：DEBCA。41.有8个结点的有向完全图有(

11、)条边A.56B.28C.14D.112参考答案：A42.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。()A.错误B.正确参考答案：A43.单链表的存储密度()A.大于1B.等于1C.小于1D.不能确定参考答案：C44.下述几种排序方法中，要求内存最大的是()A.选择排序B.插入排序C.快速排序D.归并排序参考答案：D45.用二叉链表法(link-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。()A.错误B.正确参考答案：B46.有8个结点的无向连通图最少有()条边A.8B.7C.6D.5参考答案：B47.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。()A.正确B.错误参考答案：A48.对n个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多?()A.从小到大排列好的B.从大到小排列好的C.元素无序D.元素基本有序参考答案：B49.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。()A.正确B.错误参考答案：B50.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动()个元素A.8B.63.5C.63D.7参考答案：B