2、 一个图采取以下结构，完成下列遍历算法。
void BFSTraverse(Graph G, Status (*Visit)(int v)) { for (v=0; v visited[v] = FALSE; //初始化访问标志 InitQueue(Q); // 置空的辅助队列Q for ( v=0; v if ( ) { // v 尚未访问 visited[v] = TRUE; Visit(v); // 访问u EnQueue(Q, v); // v入队列 while (!QueueEmpty(Q)) { DeQueue(Q, u); // 队头元素出队并置为u for(w=FirstAdjVex(G, u); w>=0; w=NextAdjVex(G,u,w)) if ( ! visited[w]) { visited[w]= ; Visit(w); EnQueue(Q, w); // 访问的顶点w入队列 } // if } // while } //if } // BFSTraverse 3、编程实现：用邻接表的存储方法创建一个图。 4、编程实现：对3题建立的图进行深度优先搜索。 - 31 - 第 9 章 查找 一、单选题 1、静态查找表与动态查找表两者的根本差别在于 A、逻辑结构不同 B、 存储实现不同 C、施加的操作不同 D、 数据元素的类型不同 2、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 Ａ、n B、n/2 C、(n+1)/2 D、(n-1)/2 。 。 。 3、对线性表进行二分查找时，要求线性表必须 A、以顺序方式存储 B、以链式方式存储 C、以顺序方式存储，且结点按关键字有序排序 D、以链式方式存储，且结点按关键字有序排序 4、在表长为n的顺序表中进行顺序查找，在查找不成功时，与关键字比较的次数为 。 A、n B、1 C、 n+1 D、n-1 5、对于有序表（2，5，7，11，22，45，49，62，71，77，90，93，120），折半查找值为90的结点时，经过 比较后查找成功。 A、 1 B、 2 C、4 D、5 6.快速排序在最坏情况下的时间复杂度是( )。 A、O(log2n) B、O(nlog2n) C、O(n) D、O(n) 7、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用 查找方法。 A、分块 B、顺序 C、二分 D、散列 8、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情 况下查找成功所需的平均比较次数为 。 2 3 A、35／12 B、37／12 C、39／12 D、43／12 9、当采用分块查找时，数据的组织方式为 A、数据分为若干块，每块内数据有序 B、数据分为若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小） - 32 - 。 的数据组成索引块 C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D、数据分为若干块，每块（除最后一块外）中数据个数需相同 10.在排序过程中，键值比较的次数与初始序列的排列顺序无关的是()。 A、直接插入排序和快速排序 B、直接插入排序和归并排序 C、直接选择排序和归并排序 D、快速排序和归并排序和归并排 11、从键盘依次输入关键字的值：t,u,r,b,o,p,a,s,c,l。建立二叉排序树，则先序遍历序列为 。 A、 abcloprstu B、 alcpobsrut C、 trbaoclpsu D、 trubsaocpl 12、设有一组记录的关键字为{19，24，23，1，68，20，84，27，55，11，10，79}，用链地址法构造哈希表，哈希函数为H(KEY)=KEY MOD 13 ,哈希地址为1的链中有 个记录。 A、1 B、2 C、3 D、4 13、在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的健值 。 A、一定都是同义词 B、 一定都不是同义词 C、都相同 D 、健值不一定有序的顺序表 14、设哈希表长为14，哈希函数为H(key)= key mod 11,表中已经有4个结点：addr(14)=3, addr(38)=5, addr(61)=6, addr(85)=8,其余地址为空,用线性探测再散列法解决冲突，关键字为49的结点的地址为 。 A、7 B、3 C、5 D、 4 15、设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经 次比较后查找成功。 A、2 B、 3 C、 4 D、 12 16、已知一采用开放地址法解决Hash表冲突，要从此Hash表中删除一个记录，正确的做法是 。 A、将该元素所在的存储单元清空。 B、将该元素用一个特殊的元素代替 C、将与该元素有相同Hash地址的后继元素顺次前移一个位置。 D、用与该元素有相同Hash地址的最后插入表中的元素替代。 - 33 - 17、以下说法错误的是 。 A、数字分析法对健值的各位进行分析，选择分布较均匀的若干位组成散列地址。 B、除余法选择一个适当的正整数p,以p除健值以所得的余数作为散列地址。 C、平方取中法以健值平方的中间几位作为散列地址。 D、基数转换法将健值看成另一种进制的数再转换成原来进制的数，然后选择其中几位作为散列地址。 18、下面关于B-树和B+树的叙述中，不正确的是 。 A、B-树和B+树都是平衡的多叉树 B、B-树和B+树都可用于文件的索引结构 C、B-树和B+树都能有效地支持顺序检索 D、B-树和B+树都能有效地支持随机检索 19、下列关于m阶B-树的说法错误的是 。 A、根结点至多有m棵子树。 B、 所欲叶子都在同一层 C、非叶子结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树 D、根结点中的数据都是有序的。 20、一棵3阶B-树中含有2047个关键字，包含叶结点层，该树的最大深度为 A、11 B、12 C、13 D、 14 21、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有 个结点。 。 A、2k-1-1 B、 2k-1 C、2k-1+1 D、2k-1 22、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是 。 A、 (100,80,90,60,120,110,130) B 、(100,120,110,130,80,60,90) C 、(100,60,80,90,120,110,130) D 、(100,80,60,90,120,130,110) 23、设二叉排序树中关键字由1至1000的整数构成,现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树上查到的序列？ A、2，252，401，398，330，344，397，363； B、924，220，911，244，898，258，362，363； C、925，202，911，240 ，912，245，363； D、2，399，387，219，266，382，381，278，363。 - 34 - 24、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作 A 、LL B、 LR C、 RL D、 RR 二、判断题 1、n个数放在一维数组中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。 2、若散列表的装填因子小于1，则可避免碰撞的产生。 3、哈希表的平均查找长度与处理冲突的方法无关。 4、对无序表用折半法查找比顺序查找法快。 5、在二叉排序树中插入一个新结点，总是插入到叶节点下面。 6、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。 7、对两棵具有相同关键字而形状不同的二叉排序树，按中序遍历得到的序列却是一致的。 8、完全二叉树肯定是平衡二叉树 9、在9阶B-树中，除叶子以外的任意结点的分支数介于5和9之间。 10、如果完全二叉树从根结点开始按层次遍历的序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树。 11、m阶B-树的任何一个结点的左右子树高度都相等。 12、设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。 13、对给定的关键字集合,以不同的次序插入初始为空的树中,将得到同一棵二叉排序树。 三、填空题 1． 动态查找表和静态查找表的重要区别在于前者包含有 后者不包含这两种运算。 2．对n个记录的表中进行折半查找，最大比较次数是 。 和 运算，而 型调整以使其平衡。 3．顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为 次；当使用监视哨时，若查找失败，则比较关键字的次数为 。 4．已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用二分法查找90时，需 次查找成功，查找47时需 次成功，查找100时，需 次才能确定不成功。 - 35 -