数据结构复习题

练习题：一、填空题1、_元素项_____是数据的最小单位，__数据元素______是讨论数据结构时涉及的最小数据单位。2、设一棵完全二叉树具有100个结点，则此完全二叉树有49个度为2的结点。1513、在用于表示有向图的邻接矩阵中，对第i列的元素进行累加，可得到第i个顶点的__入_度。4、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有____12________个叶子的结点。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。17619、在线性表的散列存储中，装填因子又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则等于___n/m_____。25820、排序的主要目的是为了以后对已排序的数据元素进行查找。21、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为__O(1)___,在给定值为x的结点后插入一个新结点的时间复杂度为_O(n)_______。22、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_n/2_______。23、两个栈共享空间时栈满的条件__top1=top2-1_____。24、深度为H的完全二叉树至少有H__个结点；至多有_2^H-1__个结点；H和结点总数N之间的关系是H=[log2n]+1__。15025、在有序表A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是__136811131619_26、设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较_7_次就可以断定数据元素X是否在查找表中。27、根据初始关键字序列(17，25，3，39，12)建立的二叉排序树的高度为___3_________。23628、设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_((i＋１)＊ｉ／２__＋ｊ__个数据元素。11929、栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__后进先出表_______；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。30、设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为_ABDEF_________，中序遍历序列为__DBEAFC_________，后序遍历序列为__DEBFCA_。31、设一棵完全二叉树有128个结点，则该完全二叉树的深度为_8_，有____65__个叶子结点。15132、设有向图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)___t-lchild=t-rchild=0__________;elseif(t-keyk)t=t-lchild;else___t=t-lchild;__________;}34、下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。voidbubble(intr[n])272{for(i=1;i=n-1;i++){for(exchange=0,j=0;jn-i;j++)if(r[j]r[j+1]){temp=r[j+1];__r[j]=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){___mid=(low+high)/2__________________________;if(r[mid].key==k)return(mid+1);elseif(__r[mid].keyk__________)high=mid-1;elselow=mid+1;}return(0);}36、设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有___129____个结点数。15137、设有向图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}，则给出该图的一种拓扑排序序列__13_245______。38、设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为___4913275076386597__。39、设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_h次.二、选择题1、从逻辑上可以把数据结构分为（C）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C）(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)。A.iB.n-iC.n-i+1D.不确定4、已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（D）。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、下列陈述中正确的是（D）。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分6、设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（A）。173A．m-nB．m-n-1C．n+1D．条件不足，无法确定7、．算术表达式a+b*（c+d/e）转为后缀表达式后为（B）。A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++8、关键路径是事件结点网络中（A）。220A．从源点到终点的最长路径B．从源点到终点的最短路径C．最长回路D．最短回路9、具有12个关键字的有序表，二分查找的平均查找长度（C）。236A.2.5B.4C.3.1D.510、AVL树是一种平衡的二叉排序树，树中任一结点的（B）245A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度11、线性表采用链接存储时，其地址（D）。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续与否均可以12、栈和队列是两种特殊的线性表，只能在它们的（B）处添加或删除结点。Ａ．中间点Ｂ．端点Ｃ．随机存取点Ｄ．结点13、输入序列为ABC，可以变为BAC时，经过的栈操作为（C）。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、下面（C）不是算法所具有的特性。Ａ．有穷性Ｂ．确切性Ｃ．高效性Ｄ．可行性15、下面关于串的的叙述中，（B）是不正确的？A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储16、数组A[6][7]的每个元素占五个字节，将其按行优先次序存储在起始地址为1000的内存单元中，则元素A[3][5]的地址是(A)。117A.1130B.1180C.1205D.121017、对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（D）。195A．nB．(n-1)2C．n-1D．n218、若广义表A满足Head(A)=Tail(A)，则A为（B）。A．（）B．（（））C．（（），（））D．（（），（），（））19、堆的形状是一棵(C)。A.二叉排序树B.满二叉树C.完全二叉树D.判定树20、若要在单链表中的结点*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；21、链表不具有的特点是（Ｂ）。A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比22、一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（B）。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