数据结构题目

课堂练习一、单选题1、树形结构是数据元素之间存在一种（D）。A.一对一关系B.多对多关系C.多对一关系D.一对多关系2、数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（B）。A.低B.高C.相同D.不好说3、数据结构只是研究数据的逻辑结构和物理结构，这种观点（B）。A.正确B.错误C.前半句对，后半句错D.前半句错，后半句对4、在一个长度为n的顺序表中删除第i个元素(0=i=n)时，需向前移动（A）个元素。A．n-iB．n-i+lC．n-i-1D．i5、在一个长度为n的顺序表中向第i个元素(0in+l)之前插入一个新元素时，需向后移动（B）个元素。A．n-iB．n-i+lC．n-i-1D．i6、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（A）个元素结点。A．n/2B．nC．（n+1）/2D．（n-1）/27、设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（A）。A．p-next=p-next-next;B．p=p-next;C．p=p-next-next;D．p-next=p;8、在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（B）。A．s-next=p-next;p-next=sB．q-next=s;s-next=pC．p-next=s-next;s-next=pD．p-next=s;s-next=q9、在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是（B）。A．O(1)B．O(n)C．O(n2)D．O(log2n)10、在（C）运算中，使用顺序表比链表好。A．插入B．删除C．根据序号查找D．根据元素值查找11、向一个栈顶指针为hs的链栈中插入一个s结点时，应执行（C）。A．hs-next=s;B．s-next=hs;hs=s;C．s-next=hs-next;hs-next=s;D．s-next=hs;hs=hs-next;12、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（D）。A．rear％n==frontB．（front+l）％n==rearC．rear％n-1==frontD．(rear+l)％n==front13、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（A）。A．front=front-nextB．rear=rear-nextC．rear=front-nextD．front=rear-next14、空串与空格字符组成的串的区别在于（B）。A.没有区别B.两串的长度不相等C.两串的长度相等D.两串包含的字符不相同15、设二维数组A[0…m-1][0…n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（A）。A.p+[i*n+j]*kB.p+[(i-1)*n+j-1]*kC.p+[(j-1)*n+i-1]*kD.p+[j*n+i-1]*k16、若数组A[0…m-1][0…n-1]按列优先顺序存储，则aij地址为（A）。A.LOC(a00)+[j*m+i]B.LOC(a00)+[j*n+i]C.LOC(a00)+[(j-1)*n+i-1]D.LOC(a00)+[(j-1)*m+i-1]17、二维数组A的每一个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…10，若A以行为主序存储元素，A[8][5]的物理地址与当A按列为主序存储时的元素（B）的物理地址相同。设每个字符占一个字节。A．A[8][5]B．A[3][10]C．A[5][8]D．A[0][9]18.一个广义表的表头总是一个（D）。A.广义表B.元素C.空表D.元素或广义表19.一个广义表的表尾总是一个（A）。A.广义表B.元素C.空表D.元素或广义表20、广义表A=（a），则表尾为（B）。A.aB.(())C.空表D.(a)21、假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（B）个。A.15B.16C.17D.4722、在一棵二叉树上第4层的结点数最多为（D）。A.2B.4C.6D.823、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（B）。A.R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1]24、任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（A）。A.不发生改变B.发生改变C.不能确定D.以上都不对25、根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树（BD）。A.是完全二叉树B.不是完全二叉树C.是满二叉树D.不是满二叉树26、在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为(A)。A.sB.s-1C.s+1D.n27、在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为(D)。A.nB.eC.n+eD.2e28、在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为(B)。A.kB.k+1C.k+2D.2k29、对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为(B)。A.0B.1C.nD.n+130、若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用(A)次深度优先搜索遍历的算法。A.kB.1C.k-1D.k+1二、填空题1、数据结构按逻辑结构可分为两大类，分别是__线性结构__和_非线性结构___。2、数据的逻辑结构有四种基本形态，分别是__集合____、__线性结构_、_树形结构______和___图形结构_____。3、下面程序段的时间复杂度是___O(n)____。i=n-1;while((i=0)&&A[i]!=k))i--;return(i);4、在线性表的顺序存储中，元素之间的逻辑关系是通过___相邻位置____决定的；在线性表的链接存储中，元素之间的逻辑关系是通过__链接指针_____决定的。5、对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为_O(1)，在给定值为x的结点后插入一个新结点的时间复杂度为___O(n)____。6、在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是__s-next=p-next;s-prior=p;p-next-prior=s;p-next=s;。7、设有一空栈，现有输入序列1，2，3，4，5，经过push,push,pop,push,pop,push,push后，输出序列是___2、3______。8、已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10的地址为___520______。9、设有广义表D=(a,b,D)，其长度为__3____，深度为__无穷大_____。11、对于一个有n个结点的二叉树，当它为一棵___完全_____二叉树时具有最小高度，高度为__[log2n]+1_____，当它为一棵单支树具有__最大_____高度，高度为___n____。12、在一棵二叉排序树上按_先序______遍历得到的结点序列是一个有序序列。13、对于一棵具有n个结点的二叉树,当用二叉链表作为存储结构时,其二叉链表中的指针域的总数为__2n_____个，其中___n-1____个用于链接孩子结点，___n+1____个空闲着。14、一棵深度为k的满二叉树的结点总数为__2k-1_____，一棵深度为k的完全二叉树的结点总数的最小值为__2k-1___，最大值为__2k-1____。15、线索是指______指向前趋和后继结点的指针___。16、在一个图中，所有顶点的度数之和等于所有边数的___2_____倍。17、表示图的两种存储结构为___邻接矩阵_______和____邻接表______。18、图的____深度____优先搜索遍历算法是一种递归算法，图的___广度_____优先搜索遍历算法需要使用队列。19、假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接表表示时，其相应的空间复杂度分别为__O(n2)______和___O(n+e)_____。20、假定一个有向图的边集为{a,c,a,e,c,f,d,c,e,b,e,d}，对该图进行拓扑排序得到的顶点序列为____a,c,e,b,d,f_（按照字母表）___。三、应用题1、线性表的两种存储结构各有哪些优缺点？链式：优点：插入和删除不需要移动，空间有效利用缺点：缺点：大量访问操作时不如顺序存储结构。顺序：优点：可随机存取表中任一元素。缺点：插入或删除操作时，需大量移动元素。2、下述算法的功能是什么?LinkList*Demo(LinkList*L)//L是无头结点的单链表{LinkList*q,*p;if(L&&L-next){q=L;L=L-next;p=L;while(p-next)p=p-next;p-next=q;q-next=NULL;}return(L);}（删除链表）3、假设主串acabaabaabcacaabc，模式串abaabcac。要求：先求出模式串的next值，然后再写出kmp算法的具体匹配过程。next[8]={0,1,1,2,2,3,1,2}4、假定用于通信的电文由8个字符A、B、C、D、E、F、G、H组成，各字母在电文中出现的概率为5％、25％、4％、7％、9％、12％、30％、8％，试为这8个字母设计哈夫曼编码。排序：C,A,D,H,E,F,B,G对应4,5,7,8,9,12,25,30A:0001B:01C:0000D:1010E:001F:100G:11H:1011(遵循小数的在左边的原则)5、将下图所示的森林转换成二叉树，并写出它的先序、中序、后序遍历结果。先序：ABCDEFGHIJ中序：BCDAFEHJIG后序：DCBFJIHGEA6、对于右图所示的带权无向图，用图示说明：（1）利用Prim算法从顶点v1开始构造最小生成树的过程；（2）利用Kruskal算法构造最小生成树的过程；(1)V1-V3-V6-V4-V2-V5(2)V1-V3V6-V4V5-V2V3-V6V2-V37、下图所示为一个有向网图，要求对有向图采用Dijkstra算法，求从V1到其余各顶点的最短路径，写出计算过程。8、有一个11个数的有序序列3，4，6，7，8，9，13，16，21，26，35，请画出查找关键字7的折半查找过程。Low=1;high=11;mid=6Low=1;high=5;mid=3Low=4;high=5;mid=4;9、画出在初始为空的AVL树中依次插入30,45,50,46,55,49,40时该树的生长全过程，并在有“旋转”时说出“旋转”的类型。10、散列表长度为11，散列函数H(x)=x%11，给定的关键字序列为：1,13,12,34,38,33,27,22，画出分别用拉链法（假设链表头插入）和线性探测法解决冲突时所构造的散列表。12.已知一组元素为（46，25，78，62，12，37，70，29），画出按照元素顺序输入生成一棵二叉排序树的过程13.将整数序列{40，7，12，34，50，91，75，65，25，25*}进行升序排序，写出每一趟的排序结果。排序算法分别为：1．直接插入排序2．希尔排序3．冒泡排序4．快速排序（写出第一趟的排序过程和结果）5．简单选择排序6．堆排序7．归并排序8．链式基数排序（每一趟分配和收集的结果）1.40,7,12,34,50,91,75,65,25,25*7,40,12,34,50,91,75,65,25,25*7,12,40,34,50,91,75