福师《数据结构概论》在线作业二

福师《数据结构概论》在线作业二试卷总分：100测试时间：--试卷得分：100一、单选题（共25道试题，共50分。）得分：501.若要求尽可能快地对序列进行稳定的排序，则应选（）A.快速排序B.归并排序C.冒泡排序D.堆答案:B满分：2分得分：22.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）A.（N+1）/2B.N/2C.ND.[（1+N）*N]/2答案:A满分：2分得分：23.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A.9B.11C.15D.不确定答案:B满分：2分得分：24.数组A[0..4,-1..-3,5..7]中含有元素的个数（）A.55B.45C.36D.16答案:B满分：2分得分：25.线性表是具有n个（）的有限序列。A.表元素B.字符C.数据元素D.数据项答案:C满分：2分得分：26.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A.m-nB.m-n-1C.n+1D.条件不足，无法确定答案:A满分：2分得分：27.在下列存储形式中，哪一个不是树的存储形式（）A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法答案:D满分：2分得分：28.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（）(1=i=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)答案:C满分：2分得分：29.具有10个叶结点的二叉树中有（）个度为2的结点，A.8B.9C.10D.ll答案:B满分：2分得分：210.设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈答案:D满分：2分得分：211.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A.求子串B.联接C.匹配D.求串长答案:C满分：2分得分：212.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。A.插入B.选择C.希尔D.二路归并答案:A满分：2分得分：213.若串S=’software’,其子串的数目是（）A.8B.37C.36D.9答案:B满分：2分得分：214.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）A.(rear+1)MODn=frontB.rear=frontC.rear+1=frontD.(rear-l)MODn=front答案:B满分：2分得分：215.从逻辑上可以把数据结构分为（）两大类A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构答案:B满分：2分得分：216.有n个叶子的哈夫曼树的结点总数为（）A.不确定B.2nC.2n+1D.2n-1答案:D满分：2分得分：217.一个递归算法必须包括（）A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分答案:B满分：2分得分：218.在完全二叉树中，若一个结点是叶结点，则它没（）A.左子结点B.右子结点C.左子结点和右子结点D.左子结点，右子结点和兄弟结点答案:C满分：2分得分：219.下面的程序段中，对x的赋值语句的频度为（）FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A.O(2n)B.O(n)C.O(n2)D.O(log2n)答案:C满分：2分得分：220.下列排序算法中，占用辅助空间最多的是（）A.归并排序B.快速排序C.希尔排序D.堆排序答案:A满分：2分得分：221.线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A.O（i）B.O（1）C.O（n）D.O（i-1）答案:C满分：2分得分：222.设给定权值总数有n个，其哈夫曼树的结点总数为（）A.不确定B.2nC.2n+1D.2n-1答案:D满分：2分得分：223.链表不具有的特点是（）A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比答案:B满分：2分得分：224.适用于折半查找的表的存储方式及元素排列要求为（）A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序答案:D满分：2分得分：225.就平均性能而言，目前最好的内部排序方法是（）排序法。A.冒泡B.希尔插入C.交换D.快速答案:D满分：2分得分：2二、判断题（共20道试题，共40分。）得分：401.算法的优劣与算法描述语言无关，但与所用计算机有关（）A.错误B.正确答案:A满分：2分得分：22.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构（）。A.错误B.正确答案:A满分：2分得分：23.通常使用队列来处理函数或过程的调用（）A.错误B.正确答案:A满分：2分得分：24.顺序查找法适用于存储结构为顺序或链接存储的线性表（）A.错误B.正确答案:B满分：2分得分：25.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（）A.错误B.正确答案:A满分：2分得分：26.健壮的算法不会因非法的输入数据而出现莫名其妙的状态（）。A.错误B.正确答案:B满分：2分得分：27.任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间（）A.错误B.正确答案:A满分：2分得分：28.栈和队列都是限制存取点的线性结构（）A.错误B.正确答案:B满分：2分得分：29.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止（）A.错误B.正确答案:A满分：2分得分：210.排序算法中的比较次数与初始元素序列的排列无关（）A.错误B.正确答案:A满分：2分得分：211.顺序存储方式只能用于存储线性结构（）A.错误B.正确答案:A满分：2分得分：212.循环队列通常用指针来实现队列的头尾相接（）A.错误B.正确答案:A满分：2分得分：213.二叉树的遍历结果不是唯一的（）A.错误B.正确答案:B满分：2分得分：214.对任何数据结构链式存储结构一定优于顺序存储结构（）。A.错误B.正确答案:A满分：2分得分：215.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（）A.错误B.正确答案:B满分：2分得分：216.两分法插入排序所需比较次数与待排序记录的初始排列状态相关（）A.错误B.正确答案:A满分：2分得分：217.在顺序存储结构中，有时也存储数据结构中元素之间的关系（）A.错误B.正确答案:A满分：2分得分：218.若一个广义表的表头为空表，则此广义表亦为空表（）A.错误B.正确答案:A满分：2分得分：219.用一维数组存储二叉树时，总是以前序遍历顺序存储结点（）A.错误B.正确答案:A满分：2分得分：220.内部排序要求数据一定要以顺序方式存储（）A.错误B.正确答案:A满分：2分得分：2三、多选题（共5道试题，共10分。）得分：101.下面关于哈希(Hash)查找的说法不正确的是（）A.哈希函数构造的越复杂越好，因为这样随机性好，冲突小B.除留余数法是所有哈希函数中最好的C.不存在特别好与坏的哈希函数，要视情况而定D.若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可答案:ABD满分：2分得分：22.有关二叉树下列说法不正确的是（）A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2答案:ACD满分：2分得分：23.下列说法正确的是（）A.图的遍历是从给定的源点出发每一个顶点仅被访问一次B.图的深度遍历不适用于有向图C.遍历的基本算法有两种：深度遍历和广度遍历D.图的深度遍历是一个递归过程答案:ABD满分：2分得分：24.在下列情况中，不能为二叉树的是（）A.每个结点至多有两棵子树的树B.哈夫曼树C.每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树答案:ACD满分：2分得分：25.下面关于串的的叙述中，正确的是（）A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储答案:ACD满分：2分得分：2