2、+jD．j×(j+1)/2+i4、树是以结点的分支定义______结构，表示数据元素之间______的关系。①网状②层次③一对多④多对多A．①④B．②④C．②③D．①③5、一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足______。A．其中任意一个节点均无左孩子B．其中任意一个节点均无右孩子C．其中只有一个叶结点D．其中度为2的结点最多为一个6、一个含有n个顶点和e条边得简单无向图，在其邻接矩阵存储结构中共有______个零元素。A.eB.2eC.n2-eD.n2-2e7、设网中的定点数为n，边的
3、条数为e，则普里姆(Prim)最小生成树算法和克鲁斯卡尔(Kruskal)最小生成树算法的时间复杂度分别为______。A．O(n2),O(n2)B．O(n2),O(eloge)C．O(n2),O(nlogn)D．O(nlogn),O(eloge)8、用顺序查找方法查找长度为n的线性表时，在等概率情况下的平均查找长度为______。A.nB.n/2C.(n-1)/2D.(n+1)/29、某类排序方法的稳定性是指______。A．该算法不允许有相同的关键字记录B．该算法允许有相同的关键字记录C．平均时间为O(nlog
4、n)的排序方法D．以上都不对10、一组记录的关键码为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为______。A．(38,40,46,56,79,84)B．(40,38,46,79,56,84)C．(40,38,46,56，79,84)D．(40,38,46,84,56,79)二、综合应用题1、试设计一个实现下属要求的Locate运算函数。设有一个带头结点的双向链表L。每个节点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存储数据的
5、成员data和访问频度freq，结点定义如下所示：TypedefstructDb1Node{DataTypedata;Intfreq;StructDb1Node*lLink;StructDb1Node*rLink;}Db1Node;所有结点的freq初始时都为0。每当在链表上进行一次Locate(L,x)操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频度访问的结点总是靠近表头。试利用C/C++实现满足上述要求
6、的函数：VoidLocate(Db1Node*first,DataTypex)//first指向链表的头结点2、已知先序遍历和中序遍历某棵二叉树的结点序列分别为ACKIJHLDBEGF和IKJCHLAEGBDF，请给出这棵二叉树。全真模拟试卷（2）一、单项选择题1、对于顺序存储的线性表，其访问结点的时间复杂和插入、删除节点的时间复杂度分别____A．O(n)O(n)B．O(n)O(1)C．O(1)O(n)D．O(1)O(1)2.用单循环链表表示队列，下列说法中正确的是___。A．必须设头指针和尾指针才能入队、出队都
7、是方便B．只设一个头指针，就可以入队、、出队都方便C．只设一个尾指针，就可以入队、出队都方便D．无论无何，上述3者方法都可能使入队方便3.下列判断中吧，____是正确的。A．二叉树就是度为2的树B．二叉树中不存在度大于2的结点C．二叉树是有序树D．二叉树的每个结点的度都为24.在平衡二叉树中，_____.A任意结点的左右子树结点数目相同B任意结点的左右子树高度相同C任意结点的左右子树高度之差的绝对值不大于1D不存在度为1的结点5无向图G=(V,E),其中V=
8、a,b,c,d,e,f,
9、E=
10、(a,b),(a,e),
11、(a,c),(b,e),(c,f),(f,d),(e,d)
12、,对该图进行深度优先遍历，得到的顶点序列正确的是_____。A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b6在用邻接表表示图时，扩扑排序算法时间复杂度为____。A．O（n）B．O(n+e)C．O(n2)D．O(N3)7在一棵含有n个关键字的
