数据结构小课堂(67讲师版)

考试形式：选择：小知识点填空：小的知识点以及相关重点算法的代码填空简答（40分）：不用编程（画出构造一个堆的流程、构造一棵哈夫曼编码树。。。）编程（30分）：需要编程实现（逆序一个链表）现学的数据结构：顺序表栈队列二叉树（二叉搜索树）堆要求掌握：定义编程实现（数组，链表）应用一、单选：1.以下数据结构中哪一个是非线性结构？(D)A、队列B、栈C、线性表D、二叉树2.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)。每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。（C）A、688B、678C、692D、6963.二叉树的第K层的结点数最多为(D).A、2k-1B、2K+1C、2K-1+1D、2k-14.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。A、BADCB、BCDAC、CDABD、CBDA5.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B）个空指针域。A、2m-1B、2mC、2m+1D、4m6.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C）。A、R-FB、F-RC、(R-F+M)％MD、(F-R+M)％M7.下面程序的时间复杂为（B）for（i=1，s=0；i=n；i++）{t=1；for(j=1；j=i；j++)t=t*j；s=s+t；}A、O(n)B、O(n2)C、O(n3)D、O(n4)8.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（B）。A、O(1)B、O(log2n)C、O(n)D、O(n2)9.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C）。A、O(n)B、O(nlog2n)C、O(1)D、O(n2)10.设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（D）。A、20B、30C、40D、45二、填空：1.后缀算式923+-102/-的值为（-1）。中缀算式（3+4X）-2Y/3对应的后缀算式为（34X*+2Y*3/-）。2.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有（2n）个指针域，其中有（n-1）个指针域是存放了地址，有（n+1）个指针是空指针。3.在堆排序的过程中，对任一分支结点进行筛选运算的时间复杂度为（O(log2n)），整个堆排序过程的时间复杂度为（O(nlog2n)）。4.数据的物理结构主要包括（顺序存储结构）和（链式存储结构）两种情况。5.设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为（pllink-rlink=p-rlink;p-rlink-llink=p-rlink）（设结点中的两个指针域分别为llink和rlink）。6.深度为k的完全二叉树中最少有（2k-1）个结点。7.设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有(i(i+1)/2+j-1)个数据元素。8.补充二分查找代码：templateclassTypeintorderedListType::BinarySearch(constType&x)const{//折半搜索的迭代算法inthigh=,low=0,mid;while(){mid=(low+high)/2;if(Element[mid].getKey()x);elseif(Element[mid].getKey()x);elsereturnmid;}return-1;}9.下面程序段的功能实现数据x进栈，要求在括号处填上正确的语句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(stack.top==m-1)printf(“overflow”);else{（stack.s[stack.top]=x）;（stack.top++）;}}10.templateclassTypevoidBinaryTreeType::PreOrder(BinTreeNodeType*current){if(current!=NULL){coutcurrent→data;PreOrder(current→leftChild);PreOrder(current→rightChild);}}三、简答题1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。参考答案：AEBFGCDHFKJNULL2.下图所示的森林：(1)求树（a）的先根序列和后根序列；(2)求森林先序序列和中序序列；（3）将此森林转换为相应的二叉树；ABCDEFGHIJK(a)(b)参考答案：(1)ABCDEF;BDEFCA；(2)ABCDEFGHIJK;BDEFCAIJKHG（3）转换为相应的二叉树AGBCDEFHIJK3.设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。参考答案：4545804580484580484045804840四、编程题1.根据函数的定义，利用递归完成计算二叉树大小和高度的函数。（1）intBinaryTreeType::Size(constBinTreeNodeType*t)const{if(t==NULL)return0;elsereturn1+Size(t→leftChild)+Size(t→rightChild);}（2）intBinaryTreeType::Depth(constBinTreeNodeType*t)const{if(t==NULL)return-1;elsereturn1+Max(Depth(t→leftChild),Depth(t→rightChild));}2.实现在链表上进行插入操作的功能函数。intList::Insert(constintx,constinti){//Insertanodewithdataequaltoxafterthei-1’thListNode*p=first;intk=0;while(p!=NULL&&ki-1){p=p→link;k++;}//Locatei-1’thelementif(i0||p==NULL&&i!=0){cout“无效的插入位置!\n”;return0;}ListNode*newnode=newListNode(x,NULL);//Allocatememoryforthenewnodeif(i==0){//Insertinthefrontoflistnewnode→link=first;first=newnode;}else{//elsenewnode→link=p→link;p→link=newnode;4580484022458048402278}if(newnode-link==NULL)last=newnode;return1;}3.借助栈，实现二叉树的中序遍历。templateclassTypevoidBinaryTreeType::InOrderTraverse(){stackBiTreeNode*S;BiTreeNode*p;S.makeEmpty();p=root;//初始化do{while(p){S.push(p);p=p→leftChild;}if(!S.empty()){//栈非空p=S.top();S.pop();//退栈coutp→data;//访问根结点p=p→rightChild;//向右链走}}while(p||!S.empty());}