2011数据结构模拟真题5.doc

一、选择题1设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V2 V1，E2 E1，则称( D )。A、G1是G2的子图 B、G1是G2的连通分量C、G2是G1的连通分量 D、G2是G1的子图2在一个图中，所有顶点的度数之和等于所有边数的（ C ）倍。A、1/2 B、1 C、2D、43在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。A、1/2 B、1 C、2 D、44下面关于图的存储的叙述中，哪一个是正确的。 ( A )A用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,与边数无关B用邻接矩阵法存储图,占用的存储空间数只与图中边数有关,与结点个数无关C用邻接表存储图，占用的存储空间数只与图中结点个数有关，与边数无关D用邻接表存储图，占用的存储空间数只与图中边数有关，与结点个数无关5在图的表示法中，表示形式唯一的是( A )。A、邻接矩阵表示法 B、邻接表表示法C、逆邻接表表示法 D、邻接表和逆邻接表表示6任何一个无向连通图的最小生成树（ B ）A、只有一棵B、有一棵或多棵C、一定有多棵 D、可能不存在7对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为( A ).A、n B、n+1C、 n-1D、 n+e8线性表必须是( D ),才能进行二分查找。A、用向量存储的线性表B、用链表存储的有序表C、用链表存储的线性表D、用向量存储的有序表9与其他查找方法相比，散列表查找法的特点是( C )。A、通过关键字比较进行查找 B、通过关键字计算记录存储地址进行比较C、通过关键字计算记录存储地址，并进行一定的比较进行查找D、按存储顺序查找10表长是N的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数( C )。A、N B、1 C、N+1 D、N-111在散列表技术中，冲突是不可避免的。它的频繁程度和( D )有关。A、散列函数 B、表长C、结点多少 D、散列函数和装填因子12一个待排序文件的关键字如下：265，301，751，129，937，863，742，694，076，438经过( C )趟直接插入排序后可得到如下序列：129，265，301，751，937，863，742，694，076，438A、 1B、 2C、 3 D、 413冒泡排序对关键字序列18，16，14，12，10，8进行从小到大的排序，所要进行的关键字比较总次数为( B )。A、10 B、15C、21D、3414堆是（ A ）。A、完全二叉树 B、线性表 C、二叉排序树 D、平衡二叉树15堆排序在最坏情况下的时间复杂度是( C )。 A、 O(log n) B、 O(log n 2)C、O(n log n)D、 O(n2)二、填空题1具有n个顶点的有向图至多有”n(n-1)条边。 2设连通图G的顶点数为n，则G的生成树的边数为”n-13。3在有向图的邻接表存储结构中，第i个链表中的结点个数是顶点vi的“出度。4在无权图G的邻接矩阵中，若(vi, vj)或 属于图G的边集合，则对应元素Aij等于“15。5用分块查找时，除表本身外，尚需建立一个索引表，用来存放每一块中的最大“关键字及该块的起始地址。6用“直接定址法构造的哈希函数一定不会发生冲突 。7假设在有序线性表A0A19进行折半查找，则比较一次查找成功的结点数为 “18.8采用散列技术来实现查找，需要解决的问题有选择“哈希函数和设定处理冲突的方法。9采用散列技术来实现查找，需要解决的问题有选择哈希函数和设定“处理冲突的方法。10若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变。则这种排序方法是“稳定的排序方法。 11内部排序的五类主要方法分别是“插入排序、交换排序、选择排序、归并排序和基数排序。12快速排序是属于五类排序方法中的“交换类类排序。三、算法填空1以下是一个建立有向图邻接表的算法，结点偶对由用户输入，以（0，0）结束，每条边上无信息。Status CreateDG(ALGraph &G) /采用邻接表表示法，构造有向图G scanf(&G.vexnum,&G.arcnum); for (i=0;iadjvex=; s-nextarc= G.verticesi.firstarc; G.verticesi.firstarc=; scanf(); /CreateDG 2设图G是用邻接表存储的，以下是一个从顶点Vi出发深度优先遍历图的算法。 Status (*VisitFunc)(int v); /函数变量,全局量 void DFSTraverse(ALGraph G,Status(*Visit)(int v) / 对以邻接表表示的图G作深度优先遍历 Boolean visitedG.vexnum; / 附设访问标识数组 VisitFunc=Visit; /使用全局量VisitFunc,使DFS不必设函数指针参数for (v=0; ; +v)visitedv = FALSE; / 访问标识数组初始化for (v=0; vnextarc) / p 为指向弧结点的指针w = p-adjvex;if (!) DFS(G, w);/ 对v的尚未访问过的邻接顶点w递归调用DFS / for / DFS 3设图G是用邻接矩阵存储的，以下是一个从顶点Vi出发广度优先遍历图的算法。 void BFSTraverse(MGraph G,Status(*Visit)(int v) / 对以数组存储表示的图G进行广度优先搜索遍历 bool visitedG.vexnum;/ 附设访问标识数组 Queue Q;/ 附设队列 Q for (v=0; vG.vexnum; +v) visitedv = FALSE; InitQueue(Q);/ 设置空队列 Q for ( v=0; v; +v ) if () / 从每一个未被访问的顶点出发进行广度优先搜索 visitedv = TRUE; Visit ();/ 访问图中第 v 个顶点 EnQueue(Q, v); / v 入队列 while (!QueueEmpty(Q) DeQueue(Q, u); / 队头元素出队并置为 u for ( w=0; wG.vexnum; w+; ) if ( G.arcsu, w.adj &) visitedw = TRUE; Visit(w);/ 访问图中第 w 个顶点 EnQueue(Q, w); / 当前访问的顶点 w 入队列 Q / if / while / ifDestroyQueue(Q); / BFSTraverse四、作图题1给出下图的邻接表。 2 给出下图的逆邻接表。 3按prim算法画出下图的最小生成树（起始结点为a）。再按kruskal算法画出下图的最小生成树（图示给出构造过程）。 4有二叉树结点的后序序列和中序序列如下，试画出该二叉树。后序序列：A B F H G E D C中序序列：A B C E F G H D5在地址空间为015的散列区中，对关键字序列(19，14，23，01，68，20，84，27，55，11，10，79)构造哈希表。用线性探测开放定址法处理冲突，设哈希函数为：H(key)=key mod 13。五、计算题1以关键