北京语言大学22春“计算机科学与技术”《数据结构》离线作业（一）辅导答案43

书山有路勤为径，学海无涯苦作舟！ 住在富人区的她北京语言大学22春“计算机科学与技术”数据结构离线作业（一）辅导答案一.综合考核(共50题)1.线性表采用链式存储时，结点的存储地址_。A.连续与否均可B.必须是连续的C.必须是不连续的D.和头结点的存储地址相连续参考答案：A2.用不带头结点的单链表存储队列，其头指针指向队头结点，尾指针指向队尾结点，则在进行出队操作时_。A.队头、队尾指针都要修改B.队头、队尾指针都可能要修改C.仅修改队尾指针D.仅修改队头指针参考答案：B3.树最适合用来表示_。A.有序数据元素B.无序数据元素C.元素之间无联系的数据D.元素之间具有分支层次关系的数据参考答案：D4.广义表(a)，a)的表头是()。A.aB.()C.(a)D.(a)参考答案：C5.按照二叉树的定义，具有3个结点的二叉树有()种。A.3B.4C.5D.6参考答案：C6.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为_。A.O(n2)B.O(n)C.O(1)D.O(0)参考答案：B7.某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为_。A.5B.4C.3D.2参考答案：B8.设一组初始记录关键字序列为(345,253,674,924,627)，则用基数排序需要进行_趟的分配和回收才能使得初始关键字序列变成有序序列。A.8B.5C.4D.3参考答案：D9.在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为_。A.7B.6C.5D.4参考答案：B10.栈的插入和删除操作在()进行。A.栈顶B.栈底C.任意位置D.指定位置参考答案：A11.采用邻接表存储的图的广度优先遍历算法类似于二叉树的_。A.按层遍历B.后序遍历C.先序遍历D.中序遍历参考答案：A12.采用邻接表存储的图的深度优先遍历算法类似于二叉树的()。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：C13.设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数为_。A.5B.4C.3D.1参考答案：B14.不定长文件是指_。A.记录的长度不固定B.文件的长度不固定C.字段的长度不固定D.关键字项的长度不固定参考答案：A15.内部排序是根据关键词的大小重新安排各()的顺序。A.关键词B.数据项C.文件D.数据元素参考答案：B16.栈的插入和删除操作在_进行。A.栈顶B.栈底C.指定位置D.任意位置参考答案：A17.下列说法中，不正确的是()。A.数据元素是数据的基本单位B.数据项是数据中不可分割的最小可标识单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成参考答案：D18.采用邻接表存储的图的广度优先遍历算法类似于二叉树的()。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：D19.具有10个叶子结点的二叉树中有()个度为2的结点。A.8B.9C.10D.11参考答案：B20.算法指的是_。A.计算机程序B.解决问题的计算方法C.解决问题的有限运算序列D.排序算法参考答案：C21.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是()。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)参考答案：B22.与单链表相比，双链表的优点之一是()。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活参考答案：C23.串是一种特殊的线性表，其特殊性体现在()。A.可以顺序存储B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符参考答案：B24.设某棵二叉树中有2000个结点，则该二叉树的最小高度为()。A.9B.10C.11D.12参考答案：C25.如果最常用的操作是取第i个结点及其前驱，则采用_存储方式最节省时间。A.顺序表B.双链表C.单链表D.单循环链表参考答案：A26.串的长度是指_。A.串中所含非空格字符的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含不同字母的个数参考答案：B27.由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为_。A.71B.53C.48D.24参考答案：A28.若已知一个栈序列是1，2，3，.，n，其输出序列为p1，p2，p3，.，pn，若p1=n，则pi为_。A.不确定B.n-i+1C.n-iD.i参考答案：B29.有一个长度为12的有序表R0.11,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为_。A.43/12B.39/12C.37/12D.35/12参考答案：C30.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有_条有向边。A.n-1B.nC.m-1D.m参考答案：D31.在一个无向图中，所有顶点的度数之和等于所有边数的()倍。A.1/2B.1C.2D.4参考答案：C32.设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行()趟的分配和回收才能使得初始关键字序列变成有序序列。A.3B.4C.5D.8参考答案：A33.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序_。A.发生改变B.以上都不对C.不能确定D.不发生改变参考答案：D34.线性表(a1，a2，.，an)以链式方式存储，访问第i位置元素的时间复杂度为()。A.O(0)B.O(1)C.O(n)D.O(n2)参考答案：C35.在一个有向图中所有顶点的入度之和等于所有顶点的出度之和的()倍。A.1/2B.1C.2D.4参考答案：B36.在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度(即x与元素的平均比较次数，假定查找每个元素的概率都相等)为()。A.nB.n/2C.(n+1)/2D.(n-1)/2参考答案：C37.下面关于线性表的叙述错误的是()。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现参考答案：D38.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为_。A.O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)参考答案：D39.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为_。A.O(n)B.O(m+n)C.O(m)D.O(1)参考答案：C40.具有n个结点的连通图至少有()条边。A.n-1B.nC.n(n-1)/2D.2n参考答案：A41.如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用_。A.非循环双链表B.循环双链表C.只有表尾指针没有表头指针的循环单链表D.只有表头指针没有表尾指针的循环单链表参考答案：C42.顺序查找法适合于存储结构为_的线性表。A.顺序存储或链式存储B.索引存储C.散列存储D.压缩存储参考答案：A43.算法分析的目的是()。A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易读性和文档性参考答案：C44.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有()个空指针域。A.2m-1B.2mC.2m+1D.4m参考答案：B45.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为()。A.顺序表B.用头指针表示的循环单链表C.用尾指针表示的循环单链表D.单链表参考答案：C46.采用邻接表存储的图的深度优先遍历算法类似于二叉树的_。A.按层遍历B.后序遍历C.先序遍历D.中序遍历参考答案：C47.若已知一个栈序列是1，2，3，.，n，其输出序列为p1，p2，p3，.，pn，若p1=n，则pi为()。A.iB.n-iC.n-i+1D.不确定参考答案：C48.单链表中，增加一个头结点的目的是为了()。A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储参考答案：C49.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用()存储方式最节省运算时间。A.单链表B.给出表头指针的单循环链表C.双链表D.带头结点的双循环链表参考答案：D50.线性表是具有n个()的有限序列。A.字符B.数据元素C.数据项D.表元素参考答案：B