200711数据结构部分试题及答案

《200711数据结构部分试题及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机应用基础数据结构部分试题及答案1．选择题：1.下面程序段的时间复杂度的量级为（）for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;A.O(1)B.O(n)C.O(n2)D.O(n3)2.在数据结构中，从逻辑上可以把数据结构分成（）A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构3．数据结构的（）包括集合、线性、树形和图形结构四种基本类型。A.存储结构B.逻辑结构C.基本运算D.算法描述4．数据的（）包括查找、插入、删除、更新和排序等。A.存储结构B.逻辑结构C

2、.基本运算D.算法描述5．数据的存储结构包括顺序、链接、散列和（）四种基本类型。A.线性B.数组C.集合D.索引6．下面（）的时间复杂性最好，即执行时间最短。A.O(n)B.O(logn)C.O(nlogn)D.O(n2)7.下面程序段的时间复杂性的量级为（）for(inti=0;i

3、31245B.41325C.23415D.1425310．在有n个结点的二叉链表中，值为空的链域个数为（）。P.109A.n-1B.2n-1C.n+1D.2n+11-5DCBCD6-11BCCCC11．已知完全二叉树有30个结点，则整个二叉树有（）个度为1的结点。A.0B.1C.2D.不确定12．深度为k的完全二叉树至少有（）个结点。A.2k-1B.2k-2C.2k-1D.2k-213．深度为k的完全二叉树至多有（）个结点。A.2k-1B.2k-2C.2k-1D.2k-214．对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序，当把第7个记

4、录60插入到有序表时，为寻找插入位置需比较（）次。A.1B.2C.3D.415．折半查找有序表（6，15，30，37，65，68，70，72，89，99），若查找元素37，需依次与表中元素（）进行比较。A.65，15，37B.68，30，37C.65，15，30D.65，15，30，3716．一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤n+1)位置插入一个新元素时，需要从后面向前依次后移（）个元素。A.n-iB.n-i+1C.n-i-1D.I17．如图所示的4棵二叉树中，（）不是完全二叉树。（A）(B)(C)(D)18．对于长度为18的顺序存储的有序表，若采用

5、折半查找，则查找第15个元素的查找长度为（）。A.3B.4C.5D.619．设有10000个无序元素，希望用最快的速度挑选出其中前10个最大元素，最好选用（）排序法。A.堆排序B.快速排序C.起泡排序D.插入排序20．计算机算法指的是（）。A.计算方法B.排序方法C.解决问题的有序序列D.调度方法11-15BCACD16-20BABAC21．一个栈的入栈序列1，2，3，4，则它的不可能的输出序列是（）。A.1，2，3，4B.4，3，2，1C.1，3，4，2D.4，1，2，322．对于任何一棵二叉树，如果其终端结点数为N0，度为2的结点数为N2，则N0=（）。A.N2-1B

6、.N2+1C.N2D.N2-223．线性表是（）A.一个有限序列，可以为空B.一个有限序列，不能为空C.一个无限序列，可以为空D.一个无限序列，不能为空24．在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）A.（n+1）/2B.n/2C.nD.n+125．在一个顺序表的表尾插入一个元素的时间复杂度的量级为（）A.O(n)B.O(1)C.O(n2)D.O(logn)26．设单链表中指针p指向结点ai,若要删除ai之后的结点（若存在），则需修改指针的操作为（）。A.p->next=p->next->nextB.p=p->nextC.p=p->n

7、ext->nextD.next=p27．设单链表中指针p指向结点ai,指针f指向将要插入的新结点x，则当x插在链表中两个数据元素ai和ai+1之间时，只要先修改（）后修改（）即可。A.p->next=fB.p->next=p->next->nextC.p->next=f->nextD.f->next=p->nextE.f->next=nullF.f->next=p28．设单链表中指针p指向结点ai,指针f指向将要插入的新结点x，则在链表中最后一个结点an之后插入时，只要先修改（）后修改（）即可。A.f->next=pB.f->