数据结构综合习题集(含答案)

数据结构综合习题集(含答案)数据结构综合习题集(含答案)数据结构综合习题集(含答案)数据结构综合习题集(含答案)编制仅供参考审核批准生效日期地址：电话：传真:邮编:数据结构习题集一、选择题1．数据结构中所定义的数据元素，是用于表示数据的。（C）A.最小单位

B.最大单位

C.基本单位

D.不可分割的单位2．从逻辑上可以把数据结构分为（C）A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构3．当待排序序列中记录数较少或基本有序时，最适合的排序方法为(A

)A.直接插入排序法

B.快速排序法C.堆排序法

D.归并排序法4．关于串的的叙述，不正确的是(B)A.串是字符的有限序列B.空串是由空格构成的串C.替换是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储5．带表头结点链队列的队头和队尾指针分别为front和rear，则判断队空的条件为（A）==rear!=NULL!=NULL==NULL6．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（B）2

C.(n+1)/2

+17．将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（A）-18．设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为(B).239C9．一个栈的入栈序列是a,b,c,d,e，则栈的输出序列不可能是(A)10．元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为(D)=top=-1C11．设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（B）.35C12．栈和队列(

C

)A.共同之处在于二者都是先进先出的特殊的线性表B.共同之处在于二者都是先进后出的特殊的线性表C.共同之处在于二者都只允许在顶端执行删除操作D.没有共同之处13．含有n个结点的二叉树用二叉链表表示时，空指针域个数为(C)+1+214．对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（B）15．在一个图中，所有顶点的度数之和与图的边数的比是(C)∶2∶1∶1∶116．在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为(A)+1217．在一个具有n个顶点的无向图中，每个顶点度的最大值为（

B

）

+1

(n-1)18．若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（D）A.先序遍历

B.中序遍历C.后序遍历

D.层次遍历19．对线性表进行二分查找时，要求线性表必须(C)A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列20．二分查找算法的时间复杂度是（D）(n2)(nlog2n)(n)(log2n)21．采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（C）A.插入和快速B.冒泡和快速C.选择和插入D.选择和冒泡22.闭散列表中由于散列到同一个地址而引起的“堆积”现象，是(B)A.由同义词之间发生冲突引起的B.由非同义词之间发生冲突引起的C.由同义词之间或非同义词之间发生冲突引起的D.由散列表“溢出”引起的23．在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于(B)A.静态查找表B.动态查找表C.静态查找表与动态查找表D.静态查找表或动态查找表24．排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是(B)A.选择排序B.插入排序C.冒泡排序D.快速排序25．下列程序段的时间复杂度为。（C）for（i=0；i<m；i++）for（j=0；j<t；j++）c［i］［j］=0；for（i=0；i<m；i++）for（j=0；j<t；j++）for（k=0；k<n；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；(m+n×t)(m+n+t)(m×n×t)(m×t+n)26．数据的四种基本逻辑结构是指（D）A.数组、链表、树、图形结构

B.线性表、链表、栈队列、数组广义表C.线性结构、链表、树、图形结构

D.集合、线性结构、树、图形结构27．在表长为n的顺序表上做插入运算，平均要移动的结点数为（C）。43228．含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（A）。29．定义二维数组A[1‥8，0‥10]，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（D）。+28L+36L+50L+52L30．下列程序段的时间复杂度为____________。（D）for(i=1；i<=n；i++)for(j=1；j<=n；j++)for(k=1；k<=n；k++)s=i+j+k；(m2)(m3)(n2)(n3)31．排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是(B)。A.选择排序B.插入排序C.冒泡排序D.快速排序32．设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是(A)。B.CDABC.DBACD.DCAB33．对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（A）。A.24B.2534．对一棵二叉排序树采用中序遍历进行输出的数据一定是（D）。A.递增或递减序列B.递减序列C.无序序列D.递增序列35．散列表中由于散列到同一个地址而引起的“堆积”现象，是(B)。A.由同义词之间发生冲突引起的B.由非同义词之间发生冲突引起的C.由同义词之间或非同义词之间发生冲突引起的D.由散列表“溢出”引起的36．要解决散列引起的冲突问题，常采用的方法有（D）。A.数字分析法、平方取中法

B.数字分析法、线性探测法C.二次探测法、平方取中法D.二次探测法、链地址法37．下列程序段的时间复杂度为____________。（A）k=1;for（i=0；i<n；i++）for（j=0；j<n；j++）A［i］［j］=k++；（n2）（n）（2n）（1）38．数据的四种基本存储结构是指（B）

A..顺序存储结构、索引存储结构、直接存储结构、倒排存储结构

B.顺序存储结构、索引存储结构、链式存储结构、散列存储结构

C.顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构

D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构39．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（

C

）A.线性结构

B.树形结构C.线性结构和树型结构

D.线性结构和图状结构40．在表长为n的顺序表上做删除运算，其平均时间复杂度为(B)(1)(n)(nlog2n)(n2)41．顺序表中有19个元素，第一个元素的地址为200，且每个元素占一个字节，则第14个元素的存储地址为（B）.213C42．当待排序序列中记录数较少或基本有序时，最适合的排序方法为(

A

)A.直接插入排序法

B.快速排序法C.堆排序法

D.归并排序法43．在完全二叉树中，若一个结点是叶结点，则它没有(C)A.左孩子结点B.右孩子结点C.左孩子结点和右孩子结点D.左孩子结点，右孩子结点和兄弟结点44．设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为(C)45．二维数组A［11］［20］采用按行为主序的存储方式，每个元素占4个存储单元，若A［0］［0］的存储地址为300，则A［10］［10］的地址为（A）

.1120C46．用n个值构造一棵二叉排序树，它的最大高度为（B）2B.nC.n+147．含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（A）.448．一个具有n个顶点的无向连通图，它所包含的连通分量数为（B）.1CD.不确定49．对线性表进行二分查找时，要求线性表必须(C)A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列50．散列表中由于散列到同一个地址而引起的“堆积”现象，是(B)A.由同义词之间发生冲突引起的B.由非同义词之间发生冲突引起的C.由同义词之间或非同义词之间发生冲突引起的D.由散列表“溢出”引起的51．在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于(B)A.静态查找表B.动态查找表C.静态查找表与动态查找表D.静态查找表或动态查找表52．要解决散列引起的冲突问题，常采用的方法有(

D

)A.数字分析法、平方取中法

B.数字分析法、线性探测法C.二次探测法、平方取中法D.二次探测法、链地址法53．设用链表作为栈的存储结构，则进行出栈操作时（）。A必须判别栈是否为满B必须判别栈是否为空C判别栈元素的类型 D对栈不作任何判别54.栈和队列的共同特点是(A)。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点55.若有10个元素的有序表存放在一维数组A[11]中，第一个元素放A[1]中，最后一个数据存入A[10],对这组数据进行二分查找，则查找A［3］的比较序列的下标依次为(A)A.5，2，3 B.6，4，3C.6，2，3 D.4，2，356.用链表方式存储的队列，在进行插入运算时(C).A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改57.下列各项键值序列中不是堆的为（C）A.{5，23，16，68，94，72，71，73}B.{5，16，23，68，94，72，71，73}C.{5，23，16，73，94，72，71，68}D.{5，23，16，68，73，71，72，94}58.以下数据结构中哪一个是非线性结构(D)A.队列B.栈C.线性表D.二叉树59二叉树的第k层的结点数最多为(A).A．2k-1+1D.2k-160.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为(D)A.1，2，3 B.9，5，2，3C.9，5，3 D.9，4，2，361.设有6个结点的无向图，该图至少应有(A)条边才能确保是一个连通图。.6C62．下面关于线性表的叙述错误的是（D）。A线性表采用顺序存储必须占用一片连续的存储空间 B线性表采用链式存储不必占用一片连续的存储空间C线性表采用链式存储便于插入和删除操作的实现D线性表采用顺序存储便于插入和删除操作的实现63．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B）个空指针域。A2m-1 B2m C2m+1 D64．设某完全无向图中有n个顶点，则该完全无向图中有（A）条边。An(n-1)/2 Bn(n-1)Cn2 Dn2-165．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（C）。A2，3，5，8，6B3，2，5，8，6C3，2，5，6，8 D2，3，6，5，866．设指针变量p指向单链表中结点A的前驱节点，若删除单链表中结点A，则需要执行的操作序列为（C）。Aq=p->next；p->data=q->data；p->next=q->next；free(q)；Bq=p->next；q->data=p->data；p->next=q->next；free(q)；Cq=p->next；p->next=q->next；free(q)；Dq=p->next；p->data=q->data；free(q)；67.设某强连通图中有n个顶点，则该强连通图中至少有（C）条边。An(n-1) Bn+1 Cn Dn(n68．设用链表作为栈的存储结构则出栈操作时（B）。A必须判别栈是否为满 B必须判别栈是否为空C判别栈元素的类型 D对栈不作任何判别69．数据的最小单位是（A）。A数据项 B数据类型 C数据元素 D数据变量70．若入栈顺序为1、2、3、4、5、6，则出栈序列为（B）。A5，3，4，6，1，2 B3，2，5，6，4，1C3，1，2，5，4，6 D1，5，4，6，2，371.下列关键码序列中，属于堆的是（A）A．（15，30，22，93，52，71）

B．（15，71，30，22，93，52）C．（15，52，22，93，30，71）

D．（93，30，52，22，15，71）二、填空题1．在栈结构中，允许插入的一端称为__栈顶______。2．从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动___n-i_______个元素。3．深度为k的二叉树，结点数最多有__2k-1______个。4．在图中，第一个顶点和最后一个顶点相同的路径称为__回路或环__________。5．对于具有n个元素的数据序列，采用顺序查找法，其平均查找长度为___（n+1）/2______。6．快速排序算法的时间复杂度为_O（nlogn）______。7．若图的邻接矩阵不是一个对称矩阵，则该图一定是一个__有向图_________。8．若一个无向完全图具有n个顶点，则该图的边的条数为_n(n-1)/2_________。9．有m个叶子结点的哈夫曼树，其结点总数是_2m-1___________。10．堆排序需_1_______个记录大小的辅助存储空间。11．在队结构中，允许插入的一端称为队尾;在栈结构中，允许插入的一端称为。12．在数据结构中，数据的存储结构有存储、存储、存储和存储四种方式。13．若某二叉树中度为1的结点数为4，度为2的结点数为6，则该树叶子结点数为7。14．树在数据结构中常采用、、三种存储结构表示15．设一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的退栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为3。16．对一棵深度为10的满二叉树按层编号，则编号为51的结点，它的双亲结点编号为25。17．一个具有10个顶点的完全无向图中有45条边。18．在无向图G的邻接矩阵A中，若A[i][j]等于0，则A[j][i]等于0。19．对二叉排序树进行遍历，可得到排好序的递增结点序列。20．设顺序表的表长为n，且查找每个元素的概率相等，则采用顺序查找法查找表中任一元素，在查找成功时的平均查找长度为。21．实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是的。22．对顺序表执行删除操作，其删除算法的平均时间复杂性为O（n）。23．对于具有n个元素的有序序列，若采用冒泡排序，最多需要进行1趟起泡。24．在图中，第一个顶点和最后一个顶点相同的路径称为。25．在栈结构中，允许插入的一端称为________，另一端称为________。26．从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动__n-i________个元素。27．一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为__n-i+1__________。28．深度为k的二叉树，结点数最多有________个。29．二路归并排序算法的时间复杂度为_______。30．含有n个顶点和n-1条边的连通图G采用__邻接表_____存储结构较省空间。31．在图中，第一个顶点和最后一个顶点相同的路径称为____________。32．对于具有n个元素的数据序列，采用顺序查找法，其平均查找长度为_________。33．索引顺序查找通常分两个阶段进行，首先采用顺序查找法或二分法确定所要查找的块，然后再用______查找法在块中找到具体的元素值。34．对n个元素进行冒泡排序时，最少的比较次数为__n-1______。35．快速排序法在待排序数据___基本有序________的情况下最不利于发挥其长处。36．快速排序算法的时间复杂度为__O(nlogn)_____。37．在一棵二叉排序树上按______遍历得到的结点序列是一个有序序列。38．若图的邻接矩阵不是一个对称矩阵，则该图一定是一个___________。39．若一个无向完全图具有n个顶点，则该图的边的条数为__________。40．有m个叶子结点的哈夫曼树，其结点总数是____________。41．对一棵深度为10的满二叉树按层编号，则编号为51的结点，它的双亲结点编号为__25_____。42．具有n个顶点的连通图至少需有__________条边。43．堆排序需_______1_____个记录大小的辅助存储空间。44.队列是一种___________线性表。45．算法的特性有：输入、___________、___________、可行性、输出。46．对任意非空二叉树，若叶子结点数为n0，度为1的结点数为n1，度为2的结点数为n2，则n0＝___________47．中序遍历二叉树步骤是：若二叉树非空，1)中序遍历左子树，2）___________，3)中序遍历右子树48.n阶上三角矩阵采用一维数组存放时，可压缩存储到___________个元素中。49．连通图的最小生成树中有n个顶点，_________条边，并不能存在_________。50．n个结点的完全二叉树，结点按从上到下从左到右编号，其中序号为i结点的左孩子序号___2i______三、应用题1．有一字符串序列为5*-x-y/x+2，利用栈的运算将其输出结果变为5x-*yx+/-2，描述栈的操作特点，试写出该操作的入栈和出栈过程（用push(a)表示a入栈，pop(a)表示a出栈）。特点自己从书上找。Push(5)pop(5)push(*)push(-)push(x)pop(x)pop(-)pop(x)push(-)push(y)pop(y)push(/)push(x)pop(x)push(+)pop(+)pop(/)pop(-)push(2)pop(2)2．在栈的输入端有6个元素，输入顺序为A，B，C，D，E，F。请描述栈的操作特点，并判断能否在栈的输出端得到序列DCFEBA，若能，给出入栈、出栈操作的过程，若不能，简述其理由。（push（A）表示入栈，pop（A）表示出栈）栈的操作特点自己查找能Push（A）Push（B）Push（C），Push（D），Pop（D），Pop（C）Push（E），Push（F）Pop（F），Pop（E），Pop（B），Pop（A）3.有一字符串的次序为-3*y+a／y！2，试利用栈将输出次序改变为3y*-ay！2／+，描述栈的操作特点，写出该输出序列对应的进栈和退栈的操作步骤。(用push(x)表示x进栈，pop(x)表示x退栈)Push(-)push(3)pop(3)push(*)push(y)pop(y)pop(*)pop(-)push(+)push(a)pop(a)push(/)push(y)pop(y)push(!)pop(!)push(2)pop(2)pop(/)pop(+)4．已知一棵二叉树的先根遍历序列为ABCDEGHF，中根遍历序列为CBEDAGFH，画出该二叉树，并写出后序遍历序列。后序遍历序列：CEDBFHGA5．已知无向图G的邻接矩阵如图所示。请画出该无向图，并写出v0出发按深度优先遍历时的访问序列。6．已知散列函数为H(key)=key%7，散列表长度为7(散列地址空间为0..6)，待散列序列为：(25，48，32，50，68)。根据以上条件构造一散列表，并用线性探测法解决有关地址冲突；若要用该散列表查找元素68，给出所需的比较次数。H（25）=25%7=4H（50）=50%7=1H（48）=48%7=6H（68）=68%7=5H（32）=32%7=4查找68：首先计算：H（68）=68%7=5，68与32比较，68与48比较，68与68比较查找成功，共比较3次。7．给定表（39，14，22，8，65，28，88，29，67，13，10），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，描述二叉排序树的定义，画出插入完成后的二叉排序树。定义自己从书上找8．用冒泡排序算法对数据序列（49，38，65，97，76，134，27，49）进行升序排序，写出整个冒泡排序的各趟排序过程。第一趟排序结果：38,49,65,76,97,27,49,134第二趟排序结果：38,49,65,76,27,49,97,134第三趟排序结果：38,49,65,27,49,76,97,134第四趟排序结果：38,49,27,49,65,76,97,134第五趟排序结果：38,27,49,49,65,76,97,134第六趟排序结果：27,38,49,49,65,76,97,1349．某通讯电文由A，B，C，D，E，F六个字符编码组成，每个字符编码在电文中出现的次数分别是6，5，9，10，20，1，请描述哈夫曼树的特点，并画出这六个字符编码所用的哈夫曼树，写出每个字符的哈夫曼编码。哈夫曼树特点从教材上找。10．已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请构造出该二叉树，描述后序遍历过程，给出该二叉树的后序序列。后序遍历过程：若根不为空，则执行如下操作，否则结束1）后序访问根的左子树；2）后序访问根的右子树；3）访问根；后序遍历序列：CDBGFEA11．已知无向网的邻接矩阵A如图，试画出该网，描述最小生成树算法，并画出该网的最小生成树。12．设散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34）,散列函数H（K）=K%6，采用线性探测法解决冲突。要求：（1）构造散列表；（2）求查找数34需要比较的次数。13．用冒泡排序算法对数据序列（49，38，65，97，76，134，27，49）进行升序排序，写出整个冒泡排序的各趟排序过程。第一趟排序结果：38,49,65,76,97,27,49,134第二趟排序结果：38,49,65,76,27,49,97,134第三趟排序结果：38,49,65,27,49,76,97,134第四趟排序结果：38,49,27,49,65,76,97,134第五趟排序结果：38,27,49,49,65,76,97,134第六趟排序结果：27,38,49,49,65,