数据结构习题及答案.docx

《数据结构习题及答案.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、用邻接表表示图进行广度优先遍历时，通常是采用()来实现算法的。