数据结构练习题2

练习题一、填空题1、__数据项_是数据的最小单位，_数据元素_____是讨论数据结构时涉及的最小数据单位。2、设一棵完全二叉树具有100个结点，则此完全二叉树有49个度为2的结点。3、在用于表示有向图的邻接矩阵中，对第i列的元素进行累加，可得到第i个顶点的__入____度。4、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有_____12___个叶子的结点。根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。5、有一个长度为20的有序表采用二分查找方法进行查找，共有＿4＿＿＿＿＿个元素的查找长度为3。6、对于双向链表，在两个结点之间插入一个新结点需要修改的指针共_4___个。删除一个结点需要修改的指针共______2___个。7、已知广义表LS=(a,(b,c,d),e)，它的深度是______2____，长度是______3____。8、循环队列的引入是为了克服___假溢出_______。9、表达式a*(b+c)-d/f的后缀表达式是__abc+*df/-_________。10、数据结构中评价算法的两个重要指标是时间和空间复杂度。11、设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_r-next=s_____；r=s;r-next=null;。12、设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_23______，而栈顶指针值是___1012____H。设栈为顺序栈，每个元素占4个字节。13、模式串P=‘abaabcac’的next函数值序列为_01122312_______。14、任意连通图的连通分量只有一个，即是其自身。15、栈的特性是后进先出。16、串的长度是串中所包含的字符数。17、如果一个有向图中没有＿回路＿＿＿＿＿，则该图的全部顶点可能排成一个拓扑序列。18、在具有n个叶子结点的哈夫曼树中，分支结点总数为n-1。19、在线性表的散列存储中，装填因子又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则等于____n/m____。20、排序的主要目的是为了以后对已排序的数据元素进行查找。21、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为___O(1)_____,在给定值为x的结点后插入一个新结点的时间复杂度为_O（n）_______。22、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_表长的一半_______。23、两个栈共享空间时栈满的条件_____top2=top1+1__。24、深度为H的完全二叉树至少有_2^（H-1）__个结点；至多有_2^H-1__个结点；H和结点总数N之间的关系是H=log2N+1__。25、在有序表A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是_______136811131619___。26、设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较_____7___次就可以断定数据元素X是否在查找表中。27、根据初始关键字序列(17，25，3，39，12)建立的二叉排序树的高度为___3_________。28、设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。29、栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。30、设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。31、设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶子结点。32、设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。33、typedefstructnode{intkey;structnode*lchild;structnode*rchild;}bitree;bitree*bstsearch(bitree*t,intk){if(t==0)return(0);elsewhile(t!=0)if(t-key==k)_____________;elseif(t-keyk)t=t-lchild;else_____________;}34、下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。voidbubble(intr[n]){for(i=1;i=n-1;i++){for(exchange=0,j=0;j_____________;j++)if(r[j]r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}if(exchange==0)return；}}35、下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low=high){________________________________;if(r[mid].key==k)return(mid+1);elseif(____________)high=mid-1;elselow=mid+1;,}return(0);}36、设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_______个结点数。37、设有向图G的二元组形式表示为G=（D，R），D={1，2，3，4，5}，R={r}，r={1,2，2,4，4,5，1,3，3,2，3,5}，则给出该图的一种拓扑排序序列__________。38、设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为_____________________________。39、设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次.二、选择题1、从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1=i=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)3、若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是()。A.iB.n-iC.n-i+1D.不确定4、已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（）。A.head（tail（tail（L）））B.tail（head（head（tail（L））））C.head（tail（head（tail（L））））D.head（tail(head（tail（tail（L）））)）5、下列陈述中正确的是（）。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分6、设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）。A．m-nB．m-n-1C．n+1D．条件不足，无法确定7、．算术表达式a+b*（c+d/e）转为后缀表达式后为（）。A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++8、关键路径是事件结点网络中（）。A．从源点到终点的最长路径B．从源点到终点的最短路径C．最长回路D．最短回路9、具有12个关键字的有序表，二分查找的平均查找长度（）。A.2.5B.4C.3.1D.510、AVL树是一种平衡的二叉排序树，树中任一结点的（）A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度11、线性表采用链接存储时，其地址（）。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续与否均可以12、栈和队列是两种特殊的线性表，只能在它们的（）处添加或删除结点。Ａ．中间点Ｂ．端点Ｃ．随机存取点Ｄ．结点13、输入序列为ABC，可以变为BAC时，经过的栈操作为（）。A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop14、下面（）不是算法所具有的特性。Ａ．有穷性Ｂ．确切性Ｃ．高效性Ｄ．可行性15、下面关于串的的叙述中，（）是不正确的？A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储16、数组A[6][7]的每个元素占五个字节，将其按行优先次序存储在起始地址为1000的内存单元中，则元素A[3][5]的地址是()。A.1130B.1180C.1205D.121017、对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（）。A．nB．(n-1)2C．n-1D．n218、若广义表A满足Head(A)=Tail(A)，则A为（）。A．（）B．（（））C．（（），（））D．（（），（），（））19、堆的形状是一棵()。A.二叉排序树B.满二叉树C.完全二叉树D.判定树20、若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是()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；21、链表不具有的特点是（）。A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比22、一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（）。A.23415B.54132C.23145D.1543223、递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。A．队列B．多维数组C．栈D.线性表24、设给定权值总数有n个，其哈夫曼树的结点总数为()。A．不确定B．2nC．2n+1D．2n-125、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A.快速排序B.堆排序C.归并排序D.直接插入排序26、设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。A．688B．678C．692D．69627、若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为()A.1，2