北语-18春《数据结构》

《北语-18春《数据结构》》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、18春《数据结构》作业_1一、单选题(每题4分，共20道小题，总分值80分)1.若已知一个栈序列是l，2,3，...,n，其输出序列为pl，p2，p3，...，pn，若pl=n:则pi为。A.iB.n-iC.n-i+1D.不确定答案：C2.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着_。A.数据元素具有同一特点B.不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C.每个数据元素都一样D.数据元素所包含的数据项的个数要相等答案：B3.设某有向图中有n个顶点，则该有向图对应的邻接表中有_个

2、表头结点。A.n-1B.nC.n+1D.2n-l答案：B4.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_倍。A.1/2B.1C.2D.4答案：B5.已知广义表L=((x，y,z),(u,w)),从L表中取出原子t的运算是□【A】head[tail[tail[L]]]【B】tail[head[head[tail[L]]]]【C】head[tail[head[tail[L]]]]【D】head[head[tail[tail[L]]]]A.(A)B.(B)C.(C)D.(D)答案：C6.采用邻接表存储的图的深度

3、优先遍历算法类似于二叉树的_。A.先序遍历B.中序遍历A.A=f序遍历B.按层遍历7.经过以下栈运箄后，x的值是。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x);【A】a【B】b【C】1【D】0A.(A)B.(B)C.(C)D.(D)8.没有以下四种排序方法，则_的空间复杂度最大。A.冒泡排序B.快速排序C.堆排序D.希尔排序9.以下排序方法中，需要进行关键字的比较。【A1快速排序【B】归并排序【C】基数排序【DI堆排序A.(A)B.(B)C.(C)D.(D)9

4、.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是_。A.单链表B.静态链表C.线性链表D.顺序存储结构11.设散列表扶度为m，散列涵数为H(key)=key%p，为了减少发生冲突的哥能性，p应取O【A】小于m的最大奇数【B】大于m的最小素数【C】小于m的最大偶数【D】大于m的最小合数A.(A)B.(B)C.(C)D.(D)12.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的吋间复杂度是A.O(1)B.O(n)C.O(n2)D.O(nlog2n)13.对线性表进行二分查找时，要求线性表必须

5、。【A】键值有序的链接表【B】键值有序的顺序表【C】链接表担键值不一定有序【D】顺序表但键值不一定有序A.（A）B.（B）C.（C）D.（D）14.无向图G=（V，E），其中:V=｛a，b，c,d，e，f｝，E=｛（a，b），（a，e），（a，c），（b，e），（c，f），（f，d），（e，d）｝，对该图进行深度优先遍历，得到的顶点序列正确的是（）。A.a，b，e，c，d，fB.a，c，f，e，b，dC.a，e，b,c，f，dD.a,e，d，f，c，b15.设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数

6、为_。A.3B.4C.5D.116.某二叉树结点的中序序列为ABCDEFG,后序序列为BDCAFGE,则其左子树中结点数目为_。A.3B.2C.4D.517.对广义表（（a），（b））进行head（head（（a）,（b）））操作后的结果是【A】a【B】（a）【C】（）【D】不确定A.(A)B.(B)A.(C)B.(D)18.线性表是具有n个_的有限序列。A.字符B.数据元素C.数据项D.表元素19.在一个长度为n的顺序线性表屮顺序査找值为x的元素时，查找成功时的平均查找长度(即x与元素的平均比较次数，假定查找每个元素的

7、概率都相等)为_。A.nB.n/2C.(n+l)/2D.(n-l)/220.设哈夫曼树中的叶子结点总数力m，若用二叉链表作力存储结构，则该哈夫曼树巾总共有_个空指针域。A.2m-1B.2mC.2m+lD.4m二、多选题(每题4分，共3道小题，总分值12分)1.下面关于线性表的叙述中，哪些是正确的_。A.线性表采川顺序存储，必须占川一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链式存储，不必占用一片连续的存储单元D.线性表采用链式存储，便于进行插入和删除操作答案：ACD2.关于串的叙述正确的

8、是()。A.串是字符的有限序列B.空串是空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链是存储3.()二叉排序树不可以得到一个从小到大的有序序列。A.先序遍历B.中序遍历C.后序遍历D.层次遍历三、判断题(每题4分，共2道小题，总分值8分)1.顺序存储的线性表可以按序号随机存取。1.栈