《数据结构习题及答案.docx》由会员分享,可在线阅读,更多相关《数据结构习题及答案.docx(21页珍藏版)》请在第一文库网上搜索。
1、数据结构习题及答案一、单选题(共IOO题,每题1分,共100分)1、具有35个结点的完全二叉树的深度为()A、6B、7C、8D、5正确答案:A2、在一个单链表中,若q所指结点是P所指结点的前驱结点,若在q与P之间插入一个S所指的结点,则执行()。A、p-*1ink=s-1ink;Sf1ink=p;Bq1ink=s;s1ink=p;CSfIink=Pf1ink;Pfiink=s;D、p-*1ink=s;SfIink二q;正确答案:B3、采用线性链表表示一个向量时,要求占用的存储空间地址()。A、部分地址必须是连续的B、一定是不连续的C、必须是连续的D、可连续可不连续正确答案:D4、在以单链表为存
2、储结构的线性表中,数据元素之间的逻辑关系用()A、数据元素的值表示B、数据元素在表中的序号表示C、数据元素的相邻地址表示D、指向后继元素的指针表示正确答案:D5、在长度为n的顺序表中删除第i个元素(IWiWn)时,元素移动的次数为()A、i+1B、 n-i+1C、ID、n-i正确答案:D6、在数组A中,每一个数组元素Aij占用3个存储字,行下标i从1到8,列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中,则存放该数组至少需要的存储字数是()oA、80B、100C、240D、270正确答案:C7、设森林F中有三棵树,第一、第二和第三棵树的结点个数分别为m1,m2和m3与森林F对应的
3、二叉树根结点的右子树上的结点个数是()。m1+m2B、m2C、 m2+m3Dsm3正确答案:C8、利用二叉链表存储树,则根结点的右指针是()。A、非空B、空C、指向最右孩子Ds指向最左孩子正确答案:B9、广度优先遍历类似于二叉树的()oA、层次遍历B、先序遍历C、后序遍历D、中序遍历正确答案:A10、设有一个栈,按A、B、C、D的顺序进栈,则可能为出栈序列的是()A、 DCBAB、 CDABC、 DBACD、 DCAB正确答案:A11、用链接方式存储的队列,在进行插入运算时()。A、仅修改尾指针B、头、尾指针可能都要修改C、仅修改头指针D、头、尾指针都要修改正确答案:B12、在关键字序列(12
4、,23,34,45,56,67,78,89,91)中二分查找关键字为45、89和12的结点时,所需进行的比较次数分别为()A、 4,4,3B、 4,3,3C、 3,3,4D、 3,4,4正确答案:B13、循环队列A0r1存放其元素值,分别用front和rear表示队头和队尾,则当前队列的元素个数是()。A、 (rear-front+m)%mB、 rear-front+1Crear-front-1D、rear-front正确答案:A14、含有10个结点的二叉树中,度为0的结点数为4,则度为2的结点数为()A、6B、5C、4D、3正确答案:D15、对包含n个元素的散列表进行搜索,平均搜索长度为()
5、A、不直接依赖于nBs0(Iog2n)C、上述都不对D、0(n)正确答案:A16、对于一组记录的关键字值(25,38,63,74),采用折半查找25时,()次查找成功。A、1B、2C、4D、3正确答案:B17、队和栈的主要区别是()A、所包含的运算个数不同B、限定插入和删除的位置不同C、存储结构不同D、逻辑结构不同正确答案:B18、导致栈上溢的操作是()A、栈空时执行的入栈B、栈空时执行的出栈C、栈满时执行的出栈D、栈满时执行的入栈正确答案:D19、数据的四种基本逻辑结构是指()A、线性结构、链表、树、图形结构B、集合、线性结构、树、图形结构C、数组、链表、树、图形结构D、线性表、链表、栈队列
6、、数组广义表正确答案:B20、队列操作的原则是()oA后进先出B、只能进行插入C、只能进行删除D、先进先出正确答案:D21、线性表采用链式存储时,结点的存储地址()A、必须是不连续的Bs连续与否均可C、必须是连续的D、和头结点的存储地址相连续正确答案:B22、在一个具有n个单元的顺序栈中,假定以地址低端(即O单元)作为栈底,以top作为栈顶指针,当做出栈处理时,top变化为()。A、top不变Bstop=0C、top+Dtop-正确答案:D23、设指针变量P指向单链表结点A,则删除结点A的后继结点B需要的操作为()。Ap-next=p-next-nextB、 p=p-nextC、 p=p-ne
7、xt-nextDsp-next=p正确答案:A24、在按层次遍历二叉树的算法中,需要借助的辅助数据结构是()栈B、队列C、有序表D、线性表正确答案:B25、假设以数组An存放循环队列的元素,其头、尾指针分别为front和rearo若设定尾指针指向队列中的队尾元素,头指针指向队列中队头元素的前一个位置,则当前存于队列中的元素个数为()A(rear-front-1)%nBs(rear-front)%nC、(front-rear+1)%nD(rear-front+n)%n正确答案:D26、向一个栈顶指针为hs的链栈中插入一个S结点时,应执行()。Ahs-next=s;B、 s-next=hs;hs=
8、s;C、 s-next=hs;hs=hs-next;D、 s-next=hs-next;hs-next=s;正确答案:B27、连通图G中有n个顶点,G的生成树是()的连通子图。A、包含G的所有顶点B、不必包含G的所有顶点C、包含G的所有边D、包含G的所有顶点和所有边正确答案:A28、对于一个有向图,若一个顶点的度为k1,出度为k2,则对应邻接表中该顶点单链表中的边结点数为()。A、k1+k2B、k2C、k1-k2D、k1正确答案:B29、与数据元素本身的形式、内容、相对位置、个数无关的是数据的()。A、操作B、存储结构C、算法D、逻辑结构正确答案:D30、以下数据结构中哪一个是非线性结构?()
9、A、线性表B、队列C、栈D、二叉树正确答案:D31、从一个具有n个结点的单链表中查找其值等于X的结点时,在查找成功的情况下,需平均比较()个元素结点。A、 (n-1)/2B、 (n+1)/2C、n/2D、n正确答案:B32、数据结构的定义为(D,S),其中D是()的集合。A、算法B、数据元素C、数据操作D、逻辑结构正确答案:B33、设用邻接矩阵A表示有向图G的存储结构,则有向图G中顶点i的入度为()。A、第i行非O元素的个数之和B、第i列非O元素的个数之和C、第i行O元素的个数之和D、第i列O元素的个数之和正确答案:B34、排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元
10、素进行比较,将其放入已排序序列的正确位置上的方法,称为()A、冒泡排序B、插入排序C、希尔排序D、选择排序正确答案:B35、已知含10个结点的二叉排序树是一棵完全二叉树,则该二叉排序树在等概率情况下查找成功的平均查找长度等于()A、3.4B、2.9C、1D、5.5正确答案:B36、若根据查找表(23,44,36,48,52,73,64,58)建立哈希表,采用h(K)=K%13计算哈希地址,则元素64的哈希地址为()。A、12B、8C、4D、13正确答案:A37、对待排序的元素序列进行划分,将其分为左、右两个子序列,再对两个子序列进行同样的排序操作,直到子序列为空或只剩下一个元素为止。这样的排序
11、方法是()oA、直接选择排序B、直接插入排序C、快速排序D、冒泡排序正确答案:C38、对于含n个顶点和e条边的图,采用邻接矩阵表示的空间复杂度为()A、0(e)B、0(n)Cn0(n+e)D、0(n2)正确答案:D39、链式栈与顺序栈相比,一个比较明显的优点是()oA、删除操作更加方便B、通常不会出现栈满的情况C、插入操作更加方便D、不会出现栈空的情况正确答案:B40、设指针变量top指向当前链式栈的栈顶,则删除栈顶元素的操作序列为()。Atop=top-1;B、 top=top-next;C、 top-next=top;D、 top=top+1;正确答案:B41、树最适合用来表示()oA、元
12、素之间无联系的数据B、无序数据元素C、元素之间具有分支层次关系的数据D、有序数据元素正确答案:C42、在一个具有n个顶点和e条边的无向图的邻接表中,边结点的个数为()。A、eBsneC、2eDn正确答案:C43、设顺序循环队列Q0:MT的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置,尾指针R总是指向队尾元素的当前位置,则该循环队列中的元素个数为()A、R-FB、(R-F+M)%MC、(F-R+M)%MD、F-R正确答案:B44、假设在一棵二叉树中,双分支结点数为15,单分支结点数为30个,则叶子结点数为()个。A、16B、15C、17D、47正确答案:A45、若采用孩子兄弟链
13、表作为树的存储结构,则树的后序遍历应采用二叉树的()A、前序遍历算法B、层次遍历算法C、中序遍历算法D、后序遍历算法正确答案:C46、设有序顺序表中有n个数据元素,则利用二分查找法查找数据元素X的最多比较次数不超过()oA、 1og2-1B、 1og2n+1C、 1og2(n+1)Ds1og2n正确答案:B47、在对n个元素进行冒泡排序的过程中,第一趟排序至多需要进行()对相邻元素之间的交换。A、nB、n/2Cnn-1D、n+1正确答案:C48、以下数据结构中,哪一个是线性结构()oA、线索二叉树B、有向图C、串D、二叉树正确答案:C49、若进栈次序为a,b,c,且进栈和出栈可以穿插进行,则可
14、能出现的含3个元素的出栈序列个数是()A、3B、7C、5D、6正确答案:C50、设一组记录的关键字key值为62,50,14,28,19,35,47,56,83),散列函数为H(key)=keymod13,则它的开散列表中散列地址为1的链中的结点个数是()A、4B、1C、2D、3正确答案:B51、下列排序方法中,稳定的排序方法为()A、堆排序B、直接插入排序C、希尔排序D、快速排序正确答案:B52、下面程序段的时间复杂度为()for(inti=0;im;i+)for(intj=0;jn;j+)aij=i*j;A、0(n2)B、0(m*n)Cn0(m+n)D、0(m2)正确答案:B53、为了有效地利用散列查找技术,主要解决的问题是()。找一个好的散列函数。有效地解决冲突。用整数表示关键值A、和B、和C、和D、和正确答案:A54、用邻接表表示图进行广度优先遍历时,通常是采用()来实现算法的。