发布时间 : 星期一 文章数据结构习题集1更新完毕开始阅读
if(t1==t2&&t2==NULL) return(1); else
if(t1==NULL &&t2!=NULL||t1!=NULL&&t2==NULL) return(0); else {
like1=like(t1->lchild,t2->lchild); like2=like(t1->rchild ,t2->rchild ); return(like1&&like2); } }
char a[100]; //数组顺序存储二叉树
void change(NODE *t,int i) //将二叉树的链接存储转换为顺序存储 {
if(t!=NULL) {a[i]=t->data;
change(t->lchild,2*i); change(t->rchild,2*i+1); } }
int complete(NODE *t) //判断二叉树是否为完全二叉树 {
int i,flag=0; change(t,1);
for(i=1;i<100;i++)
{if(!flag&&a[i]=='\\0') flag=1; if(flag&&a[i]!='\\0') break; }
if(i==100) return(1); else return(0); }
第七章 图
一、判断题
1.一个无向图的邻接矩阵中各非零元素之和与图中边的条数相等。（ ） 2.一个有向图的邻接矩阵中各非零元素之和与图中边的条数相等。（ ） 3.一个对称矩阵一定对应着一个无向图。（ ）
4.一个有向图的邻接矩阵一定是一个非对称矩阵。（ ） 二、选择题
1.在一个图中,所有顶点的度数之和等于所有边数的（ ）倍。 A．1/2 B．1 C．2 D．4 2.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A．1/2 B．1 C．2 D．4 3.一个有n个顶点的无向图最多有（ ）条边。 A．n B．n(n-1) C．n(n-1）/2 D．2n 4.具有4个顶点的无向完全图有（ ）条边。 A．6 B．12 C．16 D．20
15
5.具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图。 A．5 B．6 C．7 D．8 6.在一个具有n个顶点的无向图中,要连通全部顶点至少需要（ ）条边。 A．n B．n+1 C．n-1 D．n/2 7.对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小（ ） A．n B．(n-1) 2 C．n-1 D．n2
8.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为（ ），所有邻接表中的结点总数是（ ）。
①A．n B．n+1 C．n-1 D．n+e ②A．e/2 B．e C．2e D．n+e 9.采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ ）。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历 10.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（ ）。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历 11.判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（ ）。 A．求关键路径的方法 B．求最短路径的Dijkstm方法 C．宽度优先遍历算法 D．深度优先遍历算法
12.用Prim算法求下列连通的带权图的最小代价生成树，在算法执行的某刻，已选取的顶点集合U＝{1，2，5}，边的集合TE＝{（1，2），（2，5）}，要选取下一条权值最小的边，应当从（ ）组中选取。
3 12 A．{（1，4），（3，4），（3，5），（2，5）}
2 3 12 B．{（5，4），（5，3），（5，6）} 1 3 10 C．{（1，2），（2，3），（3，5）}
6 D．{（3，4），（3，5），（4，5），（1，4）} 5 11 7 三、填空题
6 1.n个顶点的连通图至少________条边。 4 5 4 2.在一个无环有向图G中，若存在一条从顶点i8 到顶点j的弧，则在顶点的拓扑序列中，顶点i与顶点j的先后次序是________。
3.在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是________条。 4. 如果从一个顶点出发又回到该顶点，则此路径叫做________。
5.如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是________。
6.若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的________遍历。
7. 一个连通图的生成树是该图的________连通子图。若这个连通图有n个顶点, 则它的生成树有________条边。
四、算法设计：
1.试在无向图的邻接矩阵和邻接链表上实现如下算法： (1)往图中插入一个顶点 (2)往图中插入一条边 (3)删去图中某顶点 (4)删去图中某条边
16
2.下面的伪代码是一个广度优先搜索算法，试以下图中的v0为源点执行该算法，请回答下述问题：
(1)对图中顶点vn+1，它需入队多少次？它被重复访问多少次?
(2)若要避免重复访问同一个顶点的错误，应如何修改此算法?
void BFS(ALGraph *G,int k)
{//以下省略局部变量的说明，visited各分量初值为假
InitQueue(&Q);//置空队列 EnQueue(&Q,k);//k入队 while(!QueueEmpty(&Q)){
i=DeQueue(&Q);//vi出队 visited[i]=TRUE;//置访问标记
printf(\访问vi for(p=G->adjlist[i].firstedge;p;p=p->next)
//依次搜索vi的邻接点vj(不妨设p->adjvex=j) if(!visited[p->adjvex])//若vj没有访问过
EnQueue(&Q,p->adjvex);//vj入队 }//endofwhile }//BFS
3.试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点vi和vj(i<>j)之间是否有路径。
4.试分别写出求DFS和BFS生成树(或生成森林)的算法，要求打印出所有的树边。 5.写一算法求连通分量的个数并输出各连通分量的顶点集。
6.设图中各边的权值都相等，试以邻接矩阵和邻接表为存储结构，分别写出算法： (1)求顶点vi到顶点vj(i<>j)的最短路径 (2)求源点vi到其余各顶点的最短路径
要求输出路径上的所有顶点(提示：利用BFS遍历的思想) 7.以邻接表为存储结构，写一个基于DFS遍历策略的算法，求图中通过某顶点vk的简单回路(若存在)。
8.写一算法求有向图的所有根(若存在)，分析算法的时间复杂度。
第八章 排 序
一、选择题
1.在所有排序方法中，关键字比较的次数与记录得初始排列次序无关的是（ ） A．希尔排序 B．起泡排序 C．插入排序 D．选择排序 2.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好（ ）排序法。 A．起泡排序 B．快速排序 C．堆排序 D．基数排序 3.在待排序的元素序列基本有序的前提下,效率最高的排序方法是（ ）。 A．插入排序 B．选择排序 C．快速排序 D．归并排序 4.一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始推为（ ）。 A．79,46,56,38,40,80 B．84,79,56,38,40,46 C．84,79,56,46,40,38 D．84,56,79,40,46,38
5.一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为（ ）。
A．38,40,46,56,79,84 B．40,38,46,79,56,84
17
C．40,38,46,56,79,84 D．40,38,46,84,56,79
6.一组记录的排序码为(25,48,16,35,79,82,23,40,36,72),其中含有5个长度为2的有序表,按归并排序的方法对该序列进行一趟归并后的结果为（ ）。
A．16,25,35,48,23,40,79,82,36,72 B．16,25,35,48,79,82,23,36,40,72 C．16,25,48,35,79,82,23,36,40,72 D．16,25,35,48,79,23,36,40,72,82
7.排序方法中,从未排序序列中依次取出元素与己排序序列(初始时为空)中的元素进行比较,将其放入己排序序列的正确位置上的方法,称为（ ）。
A．希尔排序 B．起泡排序 C．插入排序 D．选择排序
8.排序方法中,从未排序序列中挑选元素并将其依次放入己排序序列(初始为空)的一端的方法,称为（ ）。
A．希尔排序 B．归并排序 C．插入排序 D．选择排序
9.用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,元素序列的变化情况如下: (1)25,84,21,47,15,27,68,35,20 (2)20,15,21,25,47,27,68,35,84 (3)15,20,21,25,35,27,47,68,84 (4)15,20,21,25,27,35,47,68,845 则所采用的排序方法是（ ）。 A．选择排序 B．希尔排序 C．归并排序 D．快速排序 10.下述几种排序方法中,平均查找长度最小的是（ ）。 A．插入排序 B．选择排序 C．快速排序 D．归并排序 11.下述几种排序方法中,要求内存量最大的是（ ）。 A．插入排序 B．选择排序 C．快速排序 D．归并排序 12.快速排序方法在情况下最不利于发挥其长处。( ) A．要排序的数据量太大 B．要排序的数据中含有多个相同值 C．要排序的数据已基本有序 D．要排序的数据个数为奇数
13.设有10000个元素组成的无序序列,希望尽快挑选出其中前10个最大值元素,在不改变已有算法结构的前提下,以下几种内排序算法中( )最合适。
A．选择排序法 B．快速排序法 C．堆排序法 D．冒泡排序法 14.下列四种排序方法中，不稳定的方法是（ ） A．直接插入排序 B．冒泡排序 C．归并排序 D．直接选择排序 二、判断题
1.用直接选择排序方法分别对序列S1＝（1，2，3，4，5，6，7）和序列S2＝（7，5，3，2，4，1，6）进行排序，两者的比较次数不相同。（ ）
2.快速排序是所有排序中速度最快的一种。（ ）
3.堆排序是直到最后一趟排序结束之前所有元素才能在其最终的位置上。（ ） 三、填空题
1.试五种排序方法与对应的操作联系起来: (A)归并排序________ (B)选择排序________ (C)冒泡排序________ (D)插入排序________ (E)快速排序________
(1)从待排序序列中依次取出元素与己排序序列中的元素作比较将其放入己排序序列中的正确的位置上。
(2)从待排序序列中挑选元素,并将其放入己排序序列的一端。 (3)依次将相邻的有序表合并成一个有序表。
18