【奥鹏】[东北师范大学]数据结构20春在线作业2

【奥鹏】-东北师范大学数据结构20春在线作业2试卷总分:100 得分:100第1题,递归过程的实现需用到 ( )。A、线性表B、链表C、栈D、队列正确答案:C第2题,在下列情况中，可称为二叉树的是 ( )。A、每个结点至多有两棵子树的树B、哈夫曼树C、每个结点至多有两棵子树的有序树D、每个结点只有一棵右子树正确答案:B第3题,经过下列栈的操作后，GetTop(ST)的值是 ( )。InitStack(ST); push(ST,a); push(ST,b); pop(ST,x);A、aB、bC、1D、2正确答案:第4题,若要求尽可能快地对序列进行稳定的排序，则应选 () 。A、快速排序B、归并排序C、起泡排序D、希尔排序正确答案:B第5题,一个算法应该是（）。A、程序B、问题求解步骤的描述C、要满足五个基本特性D、A和C正确答案:B第6题,判断线索二叉树中某结点p有左子女的条件是 ( )。A、p ! = NULLB、p-lchild ! = NULLC、p-ltag = = 0D、p-ltag = = 1正确答案:C第7题,二叉树在中序线索化后，仍不能有效求解的问题是 ( )。A、求指定结点的前序后继B、求指定结点的中序前驱C、求指定结点的中序后继D、求指定结点的后序后继正确答案:D第8题,顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。A、附加文件B、按关键字大小排序C、按记录输入先后排序D、连续排序正确答案:A第9题,广义表A=(a, b, ( c, d ) , (e，( f , g ) ) )，则式子head ( tail ( head ( tail ( tail ( A ) ) ) ) )的值为 ()。A、( g )B、( d )C、cD、d正确答案:D第10题,( ) 的遍历仍需要栈的支持。A、前序线索二叉树B、中序线索二叉树C、后序线索二叉树D、前三种均需要正确答案:C第11题,线索二叉树是一种 ( ) 结构。A、逻辑B、物理C、逻辑和存储D、线性正确答案:B第12题,有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是 () 。A、60B、66C、18000D、33正确答案:A第13题,就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。A、堆排序快速排序归并排序B、堆排序归并排序快速排序C、堆排序归并排序快速排序D、堆排序快速排序归并排序正确答案:A第14题,下列说法不正确的是 ()。A、图的遍历是从给定的源点出发每个顶点仅被访问一次B、遍历的基本方法有两种：深度优先遍历和广度优先遍历C、图的深度优先遍历不适用于有向图D、图的深度优先遍历是一个递归过程正确答案:C第15题,在一个图中，所有顶点的度数之和等于图的边数的几倍 ()。A、1/2B、1C、2D、4正确答案:C第16题,在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行 ( )。A、p-next = s; s-next = q;B、s-next = p-next; p-next = s;C、p-next = s-next; s-next = p;D、q-next = s; s-next = p;正确答案:D第17题,在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是 ()。A、O(log2n )B、O( 1 )C、O(n )D、O(nlog2n )正确答案:B第18题,已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为LOC(a0)，则第i个结点的地址为 ( )。A、LOC(a0)+(i-1)*cB、LOC(a0)+i*cC、LOC(a0)-i*cD、LOC(a0)+(i+1)*c正确答案:B第19题,分块查找要求表中的结点 ()。A、全部无序B、块之间无序C、全部有序D、块之间有序正确答案:D第20题,下面关于串的叙述中，哪一个是不正确的? ( )A、串是字符的有限序列B、空串是由空格构成的串C、模式匹配是串的一种重要运算D、串既可以采用顺序存储，也可以采用链式存储正确答案:B第21题,二叉树按某种次序线索化后，任一结点均有指向其前序结点和后继结点的线索。A、错误B、正确正确答案:A第22题,在执行某个排序算法过程中，出现了排序码朝着它最终排序位置相反的方向移动，则该算法是不稳定的。A、错误B、正确正确答案:A第23题,非空的二叉树一定满足：某结点若有左子女，则其中序前驱一定没有右子女。A、错误B、正确正确答案:B第24题,数组是同类型值的集合。A、错误B、正确正确答案:A第25题,用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。A、错误B、正确正确答案:B第26题,链表中的表头指针与表头结点起到相同的作用。A、错误B、正确正确答案:A第27题,栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。A、错误B、正确正确答案:B第28题,一个有向图的邻接表和逆邻接表中结点的个数可能不等。A、错误B、正确正确答案:A第29题,对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。A、错误B、正确正确答案:B第30题,任何无向图都存在生成树。A、错误B、正确正确答案:A第31题,在完全二叉树中，若一个结点没有左子女，则它必是树叶。A、错误B、正确正确答案:B第32题,链表中的表头结点仅起到标识的作用。A、错误B、正确正确答案:A第33题,将一棵树转成二叉树，根结点没有右子树。A、错误B、正确正确答案:B第34题,连通分量是无向图中的极大连通子图。A、错误B、正确正确答案:B第35题,所谓取广义表的表尾就是返回广义表中最后一个元素。A、错误B、正确正确答案:A第36题,需要借助于一个栈来实现DFS算法。A、错误B、正确正确答案:B第37题,必须把一般的树转换成二叉树后才能进行存储。A、错误B、正确正确答案:A第38题,对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。A、错误B、正确正确答案:B第39题,后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。A、错误B、正确正确答案:B第40题,二维以上的数组其实是一种特殊的广义表。A、错误B、正确正确答案:B