搜索
一、单选：1.以下数据结构中哪一个是非线性结构？()A、队列B、栈C、线性表D、二叉树2.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)。每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。（）A、688B、678C、692D、6963.二叉树的第K层的结点数最多为().A、2k-1B、2K+1C、2K-1+1D、2k-14.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。A、BADCB、BCDAC、CDABD、CBDA5.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。A、2m-1B、2mC、2m+1D、4m6.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。A、R-FB、F-RC、(R-F+M)％MD、(F-R+M)％M7.下面程序的时间复杂为（）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个结点，则在二叉排序树的平均平均查找长度为（）。A、O(1)B、O(log2n)C、O(n)D、O(n2)9.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。A、O(n)B、O(nlog2n)C、O(1)D、O(n2)10.设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。A、20B、30C、40D、45二、填空：1.后缀算式923+-102/-的值为_____。中缀算式（3+4X）-2Y/3对应的后缀算式为______________________________。2.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有_____个指针域，其中有_______个指针域是存放了地址，有_______个指针是空指针。3.在堆排序的过程中，对任一分支结点进行筛选运算的时间复杂度为________，整个堆排序过程的时间复杂度为__________。4.数据的物理结构主要包括（顺序存储结构）和（链式存储结构）两种情况。5.设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为____________________（设结点中的两个指针域分别为llink和rlink）。6.深度为k的完全二叉树中最少有_______个结点。7.设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有____________个数据元素。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{______________;____________;}}10.templateclassTypevoidBinaryTreeType::PreOrder(BinTreeNodeType*current){if(current!=NULL){____________________;____________________;____________________;}}三、简答题1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。2.下图所示的森林：(1)求树（a）的先根序列和后根序列；(2)求森林先序序列和中序序列；（3）将此森林转换为相应的二叉树；ABCDEFGHIJK(a)(b)3.设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。四、编程题1.根据函数的定义，利用递归完成计算二叉树大小和高度的函数。（1）intBinaryTreeType::Size(constBinTreeNodeType*t)const{}（2）intBinaryTreeType::Depth(constBinTreeNodeType*t)const{}2.实现在链表上进行插入操作的功能函数。intList::Insert(constintx,constinti){}3.借助栈，实现二叉树的中序遍历。templateclassTypevoidBinaryTreeType::InOrderTraverse(){stackBiTreeNode*S;BiTreeNode*p;}