数据结构习题和答案

1习题课填空1、对于一棵二叉树，若一个结点的编号为i，则它的左孩子结点的编号为，双亲结点的编号为。2、向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动个元素。3、在一棵二叉树中，若双分支结点数为5个，单分支结点数为6个，则叶子结点数为个。4、为了实现折半查找，线性表必须采用方法存储。顺序5、一种抽象数据类型包括数据对象和。6、在以L为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为__________和_______。7、数据结构被形式地定义为（D,R），其中D是的有限集合，R是D上的有限集合。8、队列的插入操作在进行，删除操作在进行。9、二叉搜索树的中序遍历得到的结点序列为________。10、在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。11、栈的特点是。12、在单链表中，除了首元结点外，任一结点的存储位置由。13、在一个具有n个顶点的无向图中，要连通所有顶点则至少需要条边。14、深度为k（设根的层数为1）的完全二叉树至少有个结点，至多有个结点。15、一棵深度为6的满二叉树有个分支结点和个叶子结点。16、一个算法的效率可分为效率和效率。17、队列的特点是。18、一棵深度为5的满二叉树中的结点数为个。19、在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。2简答题1、已知一组元素为（38，26，62，94，35，50，28，55），画出按元素排列顺序输入生成的一棵二叉搜索树。答:2、假设有二维数组A[0..5,0..7]，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，计算：（1）末尾元素A57的第一个字节地址为；（2）若按列存储时，元素A47的第一个字节地址为。(3)数组A的体积（存储量）；(4)若按行存储时，元素A14的第一个字节地址为。33、已知二叉树结点的先序序列是ABCDEFGHIJ，中序序列是CBAEFDIHJG，请画出这棵二叉树。4、试给出下图所示的有向图的邻接表和邻接矩阵。5、试给出下图所示的有向图的邻接表和邻接矩阵。答:4115312646、已知一组元素为（38，52，25，74，68，16，30，54，90，72），画出按线性表中元素的次序生成的一棵二叉排序树，并求出其在等概率的情况下查找成功的平均查找长度。，7、利用普里姆算法，求下图对应的最小生成树。答：8、已知一组元素为（46,25,78,62,12,37,70,29）画出按线性表中元素的次序生成的一棵二叉排序树，并求出其在等概率的情况下查找成功的平均查找长度。5算法分析题1、语句频度(a)设n为正整数，试确定下面程序段中前置以记号@的语句的频度。x＝91;y＝100;while(y0){@if(x100){x-＝10;y--;}elsex++;}语句频度为：(b)设n为正整数，试确定下面程序段中前置以记号@的语句的频度。x＝n;y＝0;while(x＝(y+1)*(y+1)){@y++;}语句频度为：(c)设n为正整数，试确定下面程序段中前置以记号@的语句的频度。i＝1;j＝0;while(i+j＝n){@if(ij)j++;elsei++;}语句频度为：2、顺序表操作(a)已知L是采用顺序结构存储的线性表，试完成删除表中第i个数据元素的算法。StatusListDelete＿Sq(SqList&L,intI,ElemTyep&e){if()returnERROR;//表空if()returnERROR;//删除位置不合法e=L.elem[i-1];for(j=i-1;j=L.length-1;j++)//元素后移L.length--;//表长减1returnOK;}6(b)已知L是采用顺序结构存储的线性表，试完成在第i个数据元素之前插入一个数据元素的算法。StatusListInsert＿Sq(SqList&L,inti,ElemTyepe){if()returnERROR;//插入位置不合法if()returnERROR;//表满for(j=L.length-1;j=i-1;j--)//元素后移L.elem[i-1]=e;L.length++;//表长增1}3、简述下面算法的功能。(a)Statusalto(StackS,inte){StackT;intd;InitStack(T);While(!StackEmpty(S)){Pop(S,d);if(d!＝e)push(T,d);}While(!StackEmpty(T)){Pop(T,d);push(S,d);}}算法功能为：(b)voidBB(LNode*s,LNode*q){p=s;while(p-next!=q)p=p-next;p-next=s;]//BBvoidAA(LNode*pa,LNode*pb){//pa和pb分别指向单循环链表中的两个结点BB(pa,pb);BB(pb,pa);}//AAprintf(x);}算法功能为：(c)StatusA(LinkedListL){//L是无表头结点的单链表if(L&&L-next){7Q＝L;L＝L-next;While(p-next)p＝p-next;p-next＝Q;Q-next＝NULL;}returnOK;}算法功能为：4、二叉树相关(a)下面函数的功能是求二叉树的深度，若二叉树为空树，则深度为0，否则它的深度等于左子树和右子树中的最大深度加1，请完善程序。intDepthBTree(BTreeNode*BT){if(BT＝＝NULL)return0;else{intdepl＝;//计算左子树的深度intdepr＝;//计算右子树的深度if(depldepr)returnelsereturn;}}(b)下面函数的功能是从二叉树查找值为x的结点，若存在则由x带回完整值并返回真，否则返回假，请完善程序。boolFindBTree(BTreeNode*BT,ElemTypex){if(BT＝＝NULL)returnfalse;else{if(){x＝BT→data;returntrue;}else{if()returntrue;//向左子树查找若成功返回真if()returntrue;//向右子树查找若成功返回真}}5、单链表题目(a)已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试写出删除表尾结点的语句序列。(b)已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试写出在P结点之前插入S结点的语句序列。8(c)已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试写出删除p结点的语句序列。综合题1、有7个带权结点，其权值分别为3、7、8、2、6、10、14，试以它们为叶子结点构造一棵赫夫曼树，并计算出带权路径长度WPL。2、已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、5、8、11，构造一棵赫夫曼树并计算出带权路径长度WPL。解:3、已知哈希表地址为0..8,哈希函数为H(k)=kmod7,采用线性探查法处理冲突。将下面数9据序列100,20,21,35,3,78,99,45依次存入该散列表中,并求出在等概率下的平均查找长度。（要求写出计算过程）012345678解:4、一个待散列存储的数据集合为{32,75,29,63,48,94,25,46,18,70,56}，散列地址空间为HT[13]，若采用除留余数法构造散列函数和线性探查法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求平均查找长度。选择题1、非空单循环链表L的尾结点*p满足（）。循环链表A.p-next==NULLB.p==NULLC.p-next==LD.p==L102、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的（）和运算的学科。A.结构B.关系C.运算D.算法3、计算机算法指的是（）。A.解决某一问题的有限运算序列B.计算方法C.排序方法D.调度方法4、若广义表A满足Head(A)=Tail(A)，则A为（）。A.()B.(())C.((),())D.((),(),())5、线性表L在（）情况下适用于使用链式结构实现。A.需经常修改Ｌ中的结点值（顺序存储）B.需不断对L进行删除插入C.L中含有大量的结点（顺链）D.L中结点结构复杂6、带表头结点的单链表L为空的条件是（）。A.L==NULLB.L-next==NULLC.L-next=LD.L!=NULL7、假定一个循环队列存储于数组A[n]中，其队首和队尾指针分别用front和rear表示，则判队满的条件是（）。（16题）A.(rear-1)%n==frontB.(rear+1)%n==frontC.rear==(front-1)%nD.rear==(front+1)%n8、具有n(n0)个结点的完全二叉树的深度为（）。A.log2(n)B.log2(n)C.log2(n)+1D.log2(n)+19、在一颗具有n个结点的二叉树第i层上，最多具有（）个结点。A.2iB.2i+1C.2i-1D.2i-110、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A.1/2B.1C.2D.411、下列关键字序列中，（）是堆。A.16,72,31,23,94,53B.94,23,31,72,16,53C.16,53,23,94，31,72D.16,23,53,31,94,7212、在一个长度为N的数组空间中，顺序存储着一个队列，该队列的队首和队尾指针分别为front和rear表示，则该队列中的元素个数为（）。A.(rear-front)%NB.(rear-front+N)%NC.(rear+N)%ND.(front+N)%N13、二叉树上叶子结点的个数等于（）。A.分支结点个数加1B.单分支结点个数加111C.双分支结点个数加1D.双分支结点个数减114、在一个具有n顶点的无向图中，若具有e条边，则所有顶点的度数之和为（）。A.nB.eC.n+eD.2e15、算法在发生非法操作时可以做出处理的特性称为（）。A.正确性B.易读性C.健壮型D.可靠性16、假定一个循环队列的队首和队尾指针分别用front和rear表示，则判队空的条件是（）。A.front+1==rearB.front==rear+1C.front==0D.front==rear17、树中所有结点的度等于所有结点数加（）。A.0B.1C.-1D.218、对线性表进行二分查找时，要求线性表必须（）。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序19、堆的形状是一棵（）。A.二叉排序树B.满二叉树C.完全二叉树D.平衡二叉树判断题1、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。()2、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()3、一个广义表可以为其它广义表所共享。（）4、链表中的头结点仅起到标识的作用。()5、完全二叉树中，若一个结点没有左孩子，则它必是树叶。（）（定义）6、两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（）7、数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（）8、广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（）9、二叉树只能用二叉链表表示。（）10、二叉树的遍历只是为了在应用中找到一种线性次序。（）11、用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（）1212、二叉树是度为2的有序树。（）13、完全二叉树的存储结构通常采用顺序存储结构。（）14、在散列检索中，“比较”操作一般也是不可