数据结构习题

数据结构试题共8页第1页一、单项选择题1.下面程序段的时间复杂度为(C)。for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;A．O(m2)B．O(n2)C．O(m*n)D．O(m+n)2.设有一个递归算法如下intfact(intn){//n大于等于0if(n=0)return1；elsereturnn*fact(--n)；}则计算fact(n)需要调用该函数的次数为(D)次，不计fact(n)。A．nB．n+1C．n+2D．n-l3.评价排序算法好坏的标准主要是(D)。A．执行时间B．辅助空间C．算法本身的复杂度D．执行时间和所需的辅助空间4.在需要经常查找结点的前驱与后继的场合中，使用(B)比较合适。A．单链表B．双链表C．顺序表D．循环链表5.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（C）。A．p=q-next;p-next=q-next;B．p=q-next;q-next=p;C．p=q-next;q-next=p-next;D．q-next=q-next-next;q-next=q;6.已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为(B)。A．O(1)B．O(m)C．O(n)D．O(m+n)7.链表不具有的特点是（A）。A．可随机访问任一元素B．插入删除不需要移动元素C．不必事先估计存储空间D．所需空间与线性表长度成正比8.若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是(A)。A．s-next=p-next;p-next=s;B．p-next=s;s-next=p-next;C．p-next=s-next;s-next=p;D．s-next=p;p-next=s-next;9.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为(D)。A．front==NULLB．front!=NULL数据结构试题共8页第2页C．rear!=NULLD．front==rear10.栈和队列都是（C）。A．链式存储的线性结构B．顺序存储的线性结构C．限制存取位置的线性结构D．限制存取位置的非线性结构11.对于给定的结点序列abcdef，规定进栈只能从序列的左端开始。通过栈的操作，能得到的序列为（A）。A．abcfedB．cabfedC．abcfdeD．cbafde12.队列通常采用两种存储结构是(A)。A．顺序存储结构和链表存储结构B．散列方式和索引方式C．链表存储结构和数组D．线性存储结构和非线性存储结构13.若让元素1，2，3依次进栈，则出栈次序不可能出现（C）种情况。A．3，2，1B．2，1，3C．3，1，2D．1，3，214.若一个串非空，子串的定位操作通常称为(C)。A.串的长度B.原串的子串C.串的模式匹配D.串的连接15.设有一个n×n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中(C)处。A．(i+3)*i／2B．(i+1)*i／2C．(2n-i+1)*i／2D．(2n-i-1)*i／216.在(C)运算中，使用顺序表比链表好。A．插入B．删除C．根据序号查找D．根据元素值查找17.带头结点的单链表head为空的判断条件是(C)。A．head==NULLB．head-next==NULLC．head-next=headD．head!=NULL18.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（C）最节省时间。A）单链表B）循环链单表C）带尾指针的循环链单表D）带头结点的双循环链表19.栈的插入与删除操作在（A）进行。A．栈顶B．栈底C．任意位置D．指定位置20.设一个栈的输入序列为A、B、C、D，则借助一个栈所能得到的输出序列不可能是（D）。A．ABCDB．DCBAC．ACDBD．DABC21.在一个链队中，假设F和R分别是队首和队尾指针，则删除一个结点的运算是(C)。A．R=F-next;B．R=R-next;C．F=F-next;D．F=R-next;22.串是一种特殊的线性表，其特殊性体现在(B)。A．可以顺序存储B．数据元素是一个字符数据结构试题共8页第3页C．可以链接存储D．数据元素可以是多个字符23.以下说法正确的是（C）。A）空串与空格串是相同的B）“fox”是“FoxBase”的子串C）空串是零个字符组成的串D）空串长度等于124.若n为主串长，m为子串长（mn），则用简单模式匹配算法最坏情况下，需要比较字符总数是（C）。A．mB．m(n-m+1)C．n*mD．(n-m)*(m-1)25.将一个A[1..100,1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，A中元素A[66，65]在B数组中的位置k为（B）。A）198B）195C）19726.一个稀疏矩阵的转置矩阵应是（B）。A.下三角矩阵B．稀疏矩阵C．非稀疏矩阵D．有时为稀疏矩阵27.广义表（（e））的表头是（C）。A）eB）()C）(e)D）((e))28.深度为5的二叉树至多有(C)个结点。A．16B．32C．31D．1029.具有10个叶子结点的二叉树中有（B）个度为2的结点。A．8B．9C．10D．1130.在二叉树的中序遍历递归算法中，顺着搜索路径，在第(B)次经过结点时作访问操作。A．1B．2C．3D．431.在中序线索二叉树中，若某结点有右孩子，则该结点的直接后继是(D)。A左子树的最右下结点B右子树的最右下结点C左子树的最左下结点D右子树的最左下结点32.按照二叉树的定义，具有3个结点的二叉树有(C)种形态。A．3B．4C．5D．633.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（B）的二叉树。A．空或只有一个结点B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子34.图的广度优先搜索类似于树的(D)次序遍历。A．先根B．中根C．后根D．层次35.n个顶点的强连通图中至少含有(B)。A．n-l条有向边B．n条有向边C．n(n-1)/2条有向边D．n(n-1)条有向边36.任何一个无向连通图的最小生成树（B）。数据结构试题共8页第4页A．只有一棵B．有一棵或多棵C．一定有多棵D．可能不存在37.设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V2包含V1，E2包含E1，则称(A)。A．G1是G2的子图B．G1是G2的连通分量C．G2是G1的连通分量D．G2是G1的子图38.下面关于图的存储的叙述中，哪一个是正确的。(A)A．用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,与边数无关B．用邻接矩阵法存储图,占用的存储空间数只与图中边数有关,与结点个数无关C．用邻接表存储图，占用的存储空间数只与图中结点个数有关，与边数无关D．用邻接表存储图，占用的存储空间数只与图中边数有关，与结点个数无关39.(D)适合用邻接表表示。A．稠密图B．有向完全图C．无向完全图D．稀疏图40.一般，图的DFS生成树的高度(C)BFS生成树的高度。A．小于B．等于C．大于D．小于或等于41.从一棵二叉排序树中查找一个元素时，其平均时间复杂度为(C)。A．O(1)B．O(n)C．O(1og2n)D．O(n2)42.二分查找法要求查找表中各元素的键值必须是(A)排列。A．递增或递减B．递增C．递减D．无序43.向具有n个结点的、结构均衡的二叉排序树中插入一个元素的时间复杂度为(B)。A．O(1)B．O(log2n)C．O(n)D．O(nlog2n)44.线性表必须是(D)，才能进行二分查找。A．用向量存储的线性表B．用链表存储的有序表C．用链表存储的线性表D．用向量存储的有序表45.按照不同的顺序输入4，5，6三个关键字，能建立（B）棵不同的二叉排序树。A）6B）5C）4D）346.在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点的分裂，则该结点中原有（D）个关键字。A）m/2B）m/2-1C）mD）m-1E）m/2F）m/2-147.设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大数据结构试题共8页第5页的元素，最好选用(C)法。A．冒泡排序B．快速排序C．堆排序D．基数排序48.下列序列中(B)是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。A．[da,ax,eb,de,bb]ff[ba,gc]B．[cd,eb,ax,da,bb]ff[ha,gc]C．[gc,ax,cb,cd,bb]ff[da,ba]D．[ax,bb,cd,da]ff[eb,gc,ba]49.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是(B)。A．O(1)B．O(n)C．O(n2)D．O(log2n)50.以下排序方法中，稳定的排序方法是(B)。A．直接插入排序和希尔排序B．直接插入排序和冒泡排序C．希尔排序和快速排序D．冒泡排序和快速排序51.在快速排序中，每次划分选择的基准元素为该区间的(D)时，得到的两个子区间是均匀的。A．最大值B．最小值C．任意值D．中间值52.若从二叉树的任一结点出发到根的路径上所经过的结点序列按关键字有序，则该二叉树是下列树中的哪种?（C）A.二叉排序树B.哈夫曼树C.堆。二、填空题1.在一个长度为n的顺序表中删除第i个元素，要移动__n-i___个元素。2.在顺序表中插入或删除一个元素，需要平均移动表长的一半元素，具体移动元素的个数与元素所在的位置有关。3.若线性表采用顺序存储结构存放，那么在长度为n的线性表中删除第i（1≤i≤n）个数据元素需要移动n-i个数据元素，在长度为n的线性表中第i（1≤i≤n）个数据元素之前插入一个新的数据元素需要移动n-i+1个数据元素。4.在非空的单循环链表h中，某个结点p为尾结点的条件是p-next=h。5.一个队列的入队序列是a、b、c、d，则队列的输出序列为__abcd___。6.栈结构通常采用的两种存储结构是__顺序栈___和_链栈___。7.设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b、d、c、f、e、a，则栈S的容量至少应该是3。8.设有一个n×n的对称矩阵A，将其上三角部分按行存放在一个一维数数据结构试题共8页第6页组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中(2n-i+1)*i／2处。9.设有5对角矩阵A=(aij)20*20，按特殊矩阵压缩存储的方式将其5条对角线上的元素存于数组B[0：m]中，计算元素A[10,10]的存储位置44。10.已知广义表L=（a,((),b),((e))），利用取表头和取表尾的操作分离出原子e的运算是GetHead(GetHead(GetHead(GetTail(GetTail(L)))))。11.设广义表B=((),(a,(b,c)),(e,f)，())，表头为()，表尾为(a,(b,c)),(e,f)，()。12.在空串和空格串中，长度不为0的是___空格串__。13.有n个结点的二叉链表中，其中空的指针域为n+1.指向孩子的指针个数为__n-1__。14.中缀算术表达式5+6/(23-(6+15))*8所对应的后缀算术表达式为__5,6,23,6,15,+,-,/,8,*,+___。15.假定一棵二叉树的结点个数为50，则它的最小深度为___6___，最大深度为__50___。16.一棵树的后根序列与其转换的二叉树的中序列相同,先根序列与其转换的二叉树的先序列相同。17.具有400个结点的完全二叉树的深度为____9_____。18.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有__33___个。19.已知森林的先序访问序列为ABCDEFGHIJKL；