雨课堂学堂在线学堂云数据结构云南大学单元测试考核答案

注：不含主观题第1题数据结构研究的内容涉及()A数据如何组织B数据如何存储C数据的运算如何实现D算法用什么语言来描述正确答案：ABC测试题第1题数据元素是数据的最小单位（）测试题第1题在数据结构中，从逻辑上可以将之分为()A动态结构和静态结构B紧凑结构和非紧凑结构C内部结构和外部结构D线性结构和非线性结构第2题数据结构中数据元素之间的逻辑关系被称为()A数据的存储结构B数据的基本操作C程序的算法D数据的逻辑结构测试题第1题可以用()定义一个完整的数据结构A数据元素B数据对象C数据关系D抽象数据类型测试题第1题算法的时间复杂度是属于一种()A事前统计的方法B事前分析估算的方法C事后统计的方法D事后分析估算的方法第2题算法分析的目的是（）A找出数据结构的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性第3题计算机算法必须具备输入、输出和()等5个特性。A可行性、可移植性和可扩充性B可行性、确定性和有穷性C确定性、有穷性和稳定性D易读性、稳定性和安全性第4题算法即程序（）第5题健壮的程序不会因非法的输入数据而出现莫名其妙的状态。()测试题第1题程序段for(i:=n-1;i>=1;i--)for(j:=1;j<=i;j++)if(A[j]>A[j+1])A[j]←→A[j+1]；其中n为正整数，则最后一行的语句频度在最坏情况下是（）AO（n）BO(nlogn)CO(n3)DO(n2)测试题第1题线性表是具有n个（）的有限序列。A表元素B字符C数据元素D数据项测试题第1题若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。AO(0)BO(1)CO(n)DO(n2)第2题顺序存储的线性表是一种非随机存储结构()第3题下述哪一条是顺序存储结构的优点？（）A插入运算方便B可方便地用于各种逻辑结构的存储表示C存储密度大D删除运算方便测试题第1题在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。Ap->next=s;s->next=p->next;Bs->next=p->next;p->next=s;Cp->next=s;p->next=s->next;Dp->next=s->next;p->next=s;第2题链表不具有的特点是（）A插入、删除不需要移动元素B可随机访问任一元素C不必事先估计存储空间D所需空间与线性长度成正比第3题对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）Ahead==NULLBhead→next==NULLChead→next==headDhead!=NULL第4题线性表的逻辑顺序与存储顺序总是一致的。（）测试题第1题静态链表中指针表示的是（）A内存地址B数组下标C下一元素下标D左、右孩子地址测试题第1题某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A单链表B仅有头指针的单循环链表C双链表D仅有尾指针的单循环链表第2题下面关于线性表的叙述中，错误的是哪一个？（）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元D线性表采用链接存储，便于插入和删除操作。第3题若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A顺序表B双链表C带头结点的双循环链表D单循环链表测试题第1题对于栈,操作数据的原则是（）。A先进先出B后进先出C后进后出D不分顺序第2题有六个元素6，5，4，3，2，1顺序进栈，问下列哪一个不是合法的出栈序列？（）A543612B453126C346521D234156第3题如进栈序列是1，2，3，4，5。可能得到的出栈序列为()A1,2,5,3,4B3,1,2,5,4C3,2,5,4,1D1,4,2,3,5第4题一个栈的入栈序列为A,B,C,D,E，则栈的不可能的出栈序列是()。AABCDEBEDCBACDECBADDCEAB测试题第1题栈和链表是两种不同的数据结构。()第2题两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。()测试题第1题4个园盘的Hahoi塔，总的移动次数为()A7B8C15D16测试题第1题用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时()A仅修改队头指针B仅修改队尾指针C队头，队尾指针都可能要修改D队头，队尾指针都要修改第2题栈和队列是一种非线性数据结构。()测试题第1题对于循环队列()。A无法判断队列是否为空B无法判断队列是否为满C队列不可能满D以上说法都不是第2题循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是()。A(rear-front+m)%mBrear-front+1Crear-front-1Drear-front测试题第1题若串S=’software’,其子串的数目是()。A8B37C36D9第2题串是一种特殊的线性表，其特殊性体现在()。A数据元素是一个字符B可以顺序存储C数据元素可以是多个字符D可以链接存储第3题空串与空格串是相同的。（）第4题两个字符串相等的充分必要条件是长度相等，并且各个对应位置上的字符都相等()第5题下面关于串的的叙述中，哪一个是不正确的？（）A串是字符的有限序列B空串是由空格构成的串C模式匹配是串的一种重要运算D串既可以采用顺序存储，也可以采用链式存储测试题第1题数组通常具有的两种基本操作是()。A查找和修改B查找和索引C索引和修改D建立和删除第2题若6行5列的数组以列序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素（假定无第0行第0列）的地址是(

)。A1040B1042C1026DA，B，C都不对第3题数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（）测试题第1题对矩阵压缩存储是为了()。A方便运算B方便存储C提高运算速度D减少存储空间第2题设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为()。A13B33C18D40测试题第1题设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A5B6C7D8第2题对于有N个结点的二叉树，其高度为log2n。（）第3题完全二叉树中，若一个结点没有左孩子，则它必是树叶。（）第4题若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（

）A9B11C15D不确定第5题已知一棵完全二叉树中共有626个结点，叶子结点的个数应为()。A311B312C313D314第6题一个具有1025个结点的二叉树的高h为（）A11B10C11至1025之间D10至1024之间第7题有n（n>0）个分支结点的满二叉树的深度是()。An2-1Blog2(n+1)+1Clog(2*(n+1))Dlog2(n-1)第8题将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（）A4B5C6D7测试题第1题二叉树只能用二叉链表表示。（）测试题第1题一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A所有的结点均无左孩子B所有的结点均无右孩子C只有一个叶子结点D是任意一棵二叉树第2题二叉树的遍历结果不是唯一的.（）第3题一棵二叉树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（）第4题用二叉树的前序遍历和中序遍历可以导出树的后序遍历。（）第5题某二叉树结点的中序序列为BDAECF,后序序列为DBEFCA,则该二叉树对应的森林包括()棵树。A1B2C3D4第6题在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A都不相同B完全相同C先序和中序相同，而与后序不同D中序和后序相同，而与先序不同第7题若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用()遍历方法最合适。A先序B中序C后序D层序测试题第1题引入二叉线索树的目的是（）A加快查找结点的前驱或后继的速度B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲D使二叉树的遍历结果唯一第2题（）的遍历仍需要栈的支持.A先序线索树B中序线索树C后序线索树第3题一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：(

)A不确定B1C2第4题后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。（）测试题第1题设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（）个。An-1BnCn+1Dn+2第2题一棵二叉树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（）第3题设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。AM1BM1+M2CM3DM2+M3第4题树的后根遍历序列等同于该树对应的二叉树的()A先序序列B中序序列C后序序列测试题第1题下述编码中哪一个不是前缀码（）。A00，01，10，11B0，1，00，11C0，10，110，111D1，01，000，001第2题

一棵Huffman树共有215个结点，对其进行Huffman编码，共能得到()个不同的码字A107B108C214D215第3题设给定权值总数有n个，其哈夫曼树的结点总数为()A不确定B2nC2n+1D2n-1测试题第1题树中的结点和图中的顶点都是指数据结构中的数据元素。（）第2题在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（）第3题有e条边的无向图，在邻接表中有e个结点。（）第4题连通分量指的是有向图中的极大连通子图。（）第5题图中有关路径的定义是（）。A由顶点和相邻顶点序偶构成的边所形成的序列B由不同顶点所形成的序列C由不同边所形成的序列D上述定义都不是第6题具有4个顶点的无向完全图有()条边。A6B12C16D20第7题图G是n个顶点的无向完全图，则下列说法正确的有：（）AG的邻接多重表需要n(n-1)个边结点和n个顶点结点；BG的连通分量个数最少CG为连通图DG所有顶点的度的总和为n(n-1)正确答案：BCD第8题要连通具有n个顶点的有向图，至少需要（）条边。An-1BnCn+1D2n第9题一个n个顶点的连通无向图，其边的个数至少为（）。An-1BnCn+1Dnlogn测试题第1题有e条边的无向图，在邻接表中有e个结点。（）第2题用数组表示法存储一个图所需的存储单元数目与图的边数有关。（）第3题一个有向图的邻接表和逆邻接表中结点的个数可能不等。（）第4题在有向图的邻接表存储结构中，顶点v在链表中出现的次数是()。A顶点v的度B顶点v的出度C顶点v的入度D依附于顶点v的边数第5题n个顶点的无向图的邻接表最多有(

)个表结点。An2Bn(n-1)Cn(n+1)Dn(n-1)/2第6题下列哪一种图的邻接矩阵是对称矩阵？（）A有向图B无向图CAOV网DAOE网测试题第1题广度优先遍历类似于二叉树的()A先序遍历B中序遍历C后序遍历D层次遍历测试题第1题图的BFS生成树的树高比DFS生成树的树高().A.小或相等B小C大或相等D大第2题连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）第3题在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。AO(n)BO(n+e)CO(n2)DO(n3)测试题第1题已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（

）。AV1,V3,V4,V6,V2,V5,V7BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7DV1,V2,V5,V3,V4,V6,V7第2题无环有向图才能进行拓扑排序。（）第3题若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）第4题在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。AG中有弧BG中有一条从Vi到Vj的路径CG中没有弧DG中有一条从Vj到Vi的路径第5题下列关于AOE网的叙述中，不正确的是（）。A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前完成C所有的关键活动提前完成，那么整个工程将会提前完成D某些关键活动若提前完成，那么整个工程将会提前完成测试题第1题当各边上的权值(

)时，BFS算法可用来解决单源最短路径问题。A均相等B均互不相等C不一定相等第2题求解最短路径的Floyd算法的时间复杂度为()AO（n）BO（n+c）CO（n*n）DO（n*n*n）测试题第1题采用顺序查找方法查找长度为n的线性表，每个元素的平均查找长度为()。AnBn/2C(n+1)/2D(n-1)/2第2题在一个有N个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为()AO(1)BO(N)CO（N2）DO(NlogN)测试题第1题查找相同结点的效率折半查找总比顺序查找高。（）第2题有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当用二分法查找值为82的结点时（）次比较后查找成功A1B2C4D8第3题对线性表进行二分查找时，要求线性表必须（）A以顺序方式存储B以顺序方式存储,且数据元素有序C以链接方式存储D以链接方式存储,且数据元素有序测试题第1题对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。（）第2题N个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。（）第3题设二叉排序中关键字由1到1000的鳖数构成,现要查找关健字为363的结点,下述关键字序列中,不可能是在二叉排序树上查找的序列的是()。A2,252.401,398,330,344,397,363B924,220,911,244,898,258,363C925,202,911,240,912,245,363D2,399,387,219,266,382,381,278,363测试题第1题设T为一棵平衡树，在其中插入一个结点n，然后立即删除该结点后得到T1，则T与T1必定相同。（）第2题下列二叉排序树中查找效率最高的是()A平衡二叉树B二叉查找树C没有左子树的二叉排序树D没有右子树的二叉排序树第3题在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作()型调整以使其平衡。ALLBLRCRLDRR第4题在平衡二叉树中,进行查找的效率与()有关。A二叉树的深度B二叉排序树的结点的个数C后序线索树D所有线索树测试题第1题下面关于哈希(Hash，杂凑)查找的说法正确的是()A哈希函数构造的越复杂越好，因为这样随机性好，冲突小B除留余数法是所有哈希函数中最好的C不存在特别好与坏的哈希函数，要视情况而定D若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可第2题设哈希表长M=14，哈希函数H(KEY)=KEY

MOD11。表中已有4个结点：ADDR(15)=4，ADDR(38)=5，ADDR(61)=6，ADDR(84)=7，其余地址为空，如用二次探测再散列处理冲突，关键字为49的结点的地址是()。A8B3C5D9第3题将10个元素散列到100000个单元的哈希表中，则（）产生冲突。A一定会B一定不会C仍可能会第4题假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？()Ak-1次Bk次Ck+1次Dk（k+1）/2次第5题Hash表的平均查找长度与处理冲突的方法无关。（）测试题第1题一个排序算法的时间复杂度与()有关。A排序算法的稳定性B所需比较关键字的次数C所采用的存诸结构D所需辅助存诸空间的大小第2题排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。第3题用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（）。A94,32,40,90,80,46,21,69B32,40,21,46,69,94,90,80C21,32,46,40,80,69,90,94D90,69,80,46,21,32,94,40第4题直接插入排序在最好情况下的时间复杂度为（）AO(logn)BO(n)CO(n*logn)DO(n2)测试题第1题在排序记录序列“基本有序”或记录序列较短的情况下，最佳内部排序方法是（）。A直接插入排序B起泡排序C简单选择排序第2题对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是

()

A1B4C3D2测试题第1题对ｎ个不同的排序码进行冒泡排序，最终序列自小到大，在下列（）情况下比较的次数最多。A从小到大排列好的B从大到小排列好的C元素无序D元素基本有序第2题一组记录的关键字为（46，79，56，38，40，84），则利用快速排序方法，以第一个记录的关键字为分割点，得到的一次划分结果为（）A38，40，46，56，79，84

B40，38，46，79，56，84C40，38，46，56，79，84D40，38，46，84，56，79第3题快速排序在下列