搜索
一．选择题1.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（）A.s-next=p-next;p-next=sB.p-next=s-next;s-next=pC.q-next=s;s-next=pD.p-next=s;s-next=q2.判断一个队列QU（最多元素为m0）为满队列的条件是（）A.QU-rear-QU-front==m0B.QU-rear-QU-front-1==m0C.QU-front==QU-rearD.QU-front==QU-rear+13.设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为A.fedcbaB.bcafedC.dcefbaD.cabdef4.下面算法的时间复杂度是（）i=1;while(in){i=i*2;}A.O(1)B.O(lgn)C.O(log2n)D.O(n)5.设有一个二位数组A[m][n]，假设A[0][0]，存放在位置600，A[3][3]存放在位置678，每个元素占一个空间，问A[2][3]存放在（）位置（m3）A.658B.648C.633D.6536.根据使用频率，为五个字符设计的哈夫曼编码不可能是（）A.111,110,10,01,00B.100,11,10,1,0C.000,001,010,011,1D.001,000,01,11,107.串是（）A.不少于一个字母的序列B.任意个字母的序列C.不少于一个字符的序列D.有限个字符的序列8.设某二叉树中的度数为0的结点数为N0，度数为1的结点输为N1，度数为2的结点数为N2，则下列等式成立的是（）A.N0=N2+1B.N0=N1+N2C.N0=N1+1D.N0=2N1+19.从空二叉排序树开始，用下列序列中的（），构造的二叉排序树的高度最小A.45,25,55,15,35,95,30B.35,25,15,30,55,45,95C.15,25,30,35,45,55,95D.30,25,15,35,45,95,5510.若一个具有N个顶点K条边的无向图是一个森林（NK），则该森林中必有（）棵树A.KB.NC.N-KD.N-K+111.数组的逻辑结构不同于下列（）的逻辑结构A.线性表B.栈C.队列D.树12.关键路径是指AOE网中（）A.从源点到汇点（结束顶点）的最短路径B.最长的回路C.从源点到汇点（结束顶点）的最长路径D.最短的回路二．填空题1.数据的逻辑结构被分为集合结构、线性结构、________和图结构四种2.若要求一个稠密图的最小生成树，最好用_______算法求解3.高度为h的完全二叉树最少有____个结点4.设广义表L=（（），（）），则GetHead（L）是（），GetTail（L）是________5.768个结点的完全二叉树有____个叶子结点，19个结点的哈夫曼树有____个叶子结点6.一组记录的关键字为{12,38,35,25,74,50,63,90}，按二路归并排序对该序列进行一趟归并后的结果是________7.有____种不同形态的二叉树可以按照中序遍历得到相同的abc序列8.对于具有144个记录的文件，采用分块查找法查找，块间和块内均采用顺序查找，假定每块长度为12个记录，则平均查找长度为______三．判断题1.循环链表可以在尾部设置头指针（）2.Dijkstra最短路径算法是求图中每一对顶点之间的最短路径（）3.给定一组权值，可以唯一构造出一颗哈夫曼树（）4.二叉树线索化后，任意一个结点均有指向其前驱和后继的线索（）5.在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1（）6.设与一颗树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点不一定是子结点（）7.直接选择排序是一种不稳定的排序算法（）8.由于希尔排序中的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多9.当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径（）10.如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串（）四．简答题1.将下图所示的森林转换为二叉树2.如图所示的3阶B-树依次执行下列操作，试画出每步的操作结果○1EA.插入300A○2EA.插入70A○3EA.插入30A○4EA.删除1503.已知图G如图所示，写出图G的邻接表和图G的一个拓扑排序列4.已知一组关键字（19,11,23,1,67,20,84,27,55,11,10,79），哈希函数为：H(key)=keyMOD13，哈希表长为m=16，设每个记录的查找概率相等，用二次探测再散列处理冲突，将上面数据序列依次存入该散列表中，并求出在查找成功时的平均查找长度5.写出利用希尔排序对关键字序列（40,24,80,39,43,18,20,10,90,70）进行从小到大排序的每一趟结果（假设步长gap取值分别为：5、3、1）五．算法题1.假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针编写一个函数删除该结点的前趋结点（写出单链表的数据结构）2.设二叉树以二叉链表为存储结构，设计一个算法，求在先根序列中处于第k个位置的结点（请写出二叉树链式存储的数据结构）3.设计出堆排序算法（写出数据结构的定义）