内容发布更新时间 : 2024/6/29 12:47:17星期一 下面是文章的全部内容请认真阅读。

(182) 有向图G用邻接表矩阵存储，其第i行的所有非零元素之和等于顶点i的 。出度

(183) 如果n个顶点的图是一个环，则它有 棵生成树。 n （以任意一顶点为起点，得到n-1条边）

(184) n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 。O(n2) (185) n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 。O(n+e) (186) 设有一稀疏图G，则G采用 邻接表 存储较省空间。 (187) 设有一稠密图G，则G采用 邻接矩阵 存储较省空间。 (188) 图的逆邻接表存储结构只适用于 有向 图。

(189) 已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是 将邻接矩阵的第i行全部置0 。

(190) 图的深度优先遍历序列 不是 惟一的。

(191) n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 O(n2) ；若采用邻接表存储时，该算法的时间复杂度为 O(n+e) 。

(192) n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 O(n2)；若采用邻接表存储，该算法的时间复杂度为 O(n+e) 。

(193) 图的BFS生成树的树高比DFS生成树的树高 小或相等 。

(194) 用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 O(n2)；用克鲁斯卡尔(Kruskal)算法的时间复杂度是 O(elog2e) 。

(195) 若要求一个稀疏图G的最小生成树，最好用 克鲁斯卡尔(Kruskal) 算法来求解。

(196) 若要求一个稠密图G的最小生成树，最好用 普里姆(Prim) 算法来求解。 (197) 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 递增 的次序来得到最短路径的。

(198) 拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。 (199) 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。

(200) 散列法存储的基本思想是由 关键字的值决定数据的存储地址。 (201) 大多数排序算法都有两个基本的操作： 。比较和移动 (202) 由于查找算法的基本运算是关键字之间的比较操作，所以可用 平均查找长度来衡量查找算法的性能。

(203) 查找有静态查找和动态查找，当查找不成功时动态查找会 将查找关键字插入在表中。

(204) 顺序查找法中设置监视哨，可以起到 防止越界的作用。

(205) 假设列表长度为n，那么查找第i个数据元素时需进行 n-i+1次比较。

(206) 假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为： ASL=(n+1)/2。

(207) 折半查找法又称为二分法查找法，这种方法要求待查找的列表必须是 按关键字大小有序排列的顺序表。

(208) 假定将长度为n的表分成b块，且每块含s个元素，则b=n/s。又假定表中每个元素的查找概率相等，

(209) 在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为 2。

(210) 折半查找有序表（4,6,12,20,28,38,50,70,88,100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。

(211) 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找。 (212) 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。

(213) 当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即 k1≠k2 ，但 H（k1）=H（k2），这种现象称为 冲突.

(214) 产生冲突现象的两个关键字称为该散列函数的 ____同义词________ 。 (215) 在散列函数 H(key)=key MOD p 中，p应取 素数。

(216) 设哈希表长m=14, 哈希函数H(key)=key MOD11.表中已有4个结点；addr(15)=4, addr(38)=5, addr(61)=6, addr(84)=7, 其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是 。9

(217) 希尔排序是属于 插入排序的改进方法。

(218) 给出一组关键字T＝（20,4,34,5,16,33,18,29,2,40,7），要求从下到大进行排序，试给出快速排序（选一个记录为枢纽）第一趟排序结果 。7,4,2,85,16,18,20,,29,33,40,34

(219) 大多数排序算法都有两个基本的操作： 比较和移动 。

(220) 在对一组记录（54,38,96,23,15,72,60,45,83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较 次。6。

(221) 在插入和选择排序中，若初始数据基本正序，则选用 插入 ；若初始数据基本反序，则选用 选择 。

(222) 在堆排序和快速排序中，若初始记录接近正序或反序，则选用 堆排序 ；若初始记录基本无序，则最好选用 快速排序 。

(223) 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是 O(n2) 。若对其进行快速排序，在最坏的情况下所需要的时间是 O(n2) (234) 对于n个记录的集合进行归并排序，所需要的平均时间是 O(nlog2n) ，所

需要的附加空间是 O(n) 。

7． 对于n个记录的表进行2路归并排序，整个归并排序需进行 ┌log2n┐ 趟（遍）。 8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ；

初始步长为4的希尔（shell）排序一趟的结果是 P A C S Q H F X R D M Y ； 二路归并排序一趟扫描的结果是 H Q C Y A P M S D R F X； 快速排序一趟扫描的结果是 F H C D P A M Q R S Y X ； 堆排序初始建堆的结果是 A D C R F Q M S Y P H X 。

9. 在堆排序、快速排序和归并排序中，

若只从存储空间考虑，则应首先选取 方法，其次选取 快速排序方法，最后选取归并排序方法； 若只从排序结果的稳定性考虑，则应 选取 归并排序 方法； 若只从平均情况下最快考虑，则应选取 堆排序、快速排序和归并排序 方法； 若只从最坏情况下最快并且要节省内存考虑，则应选取 堆排序 方法。 三、程序填空题

(235) 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 void reverse(pointer h) /* h为附加头结点指针；*/ { pointer p,q;

p=h->next; h->next=NULL; while((1)________) {q=p; p=p->next; q->next=h->next; h->next=(2)________; } }

(1)p!=null ∥链表未到尾就一直作

(2)q ∥将当前结点作为头结点后的第一元素结点插入

(236) 下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针，试在空缺处填入适当的语句。

void reverse（linklist &L）{

p=null；q=L； while（q！=null）

{ (1) ; q->next=p；p=q；(2)___ ; }

(3)_____; }

(1) L=L->next; ∥暂存后继

(2)q=L; ∥待逆置结点 (3)L=p; ∥头指针仍为L

(237) 以下算法的功能是用头插法建立单链表的算法，请填空完善之。 Linklist CreateFromHead( ) { LinkList L; Node *s; char c;

L=(Linklist)malloc(sizeof(Node)); /*为头结点分配存储空间*/ L->next=NULL ; While( ( c=getchar()) !=?*? )

{ s=(Node*)malloc(sizeof(Node)); /*为读入的字符分配存储空间*/

s->data=c;

s->next=L->next ; L->next=s ; }

return L; }

(238) 以下算法的功能是尾插法创建链表，请填空完善之。 typedef struct Node /*结点类型定义*/ { char data;

struct Node * next;

} Node, *LinkList; /* LinkList为结构指针类型*/

Linklist CreateFromTail( ) /*将新增的字符追加到链表的末尾*/ { LinkList L; Node *r, *s; char c;

L=(Node * )malloc(sizeof(Node)); /*为头结点分配存储空间*/ L->next=NULL;

r=L; /*r指针指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/ while( ( c=getchar()) !=?$? ) /*当输入?$?时，建表结束*/

{ s=(Node*)malloc(sizeof(Node)); s->data=c; ；r->next=s; r=s; }

； r->next=NULL /*将最后一个结点的next链域置为空，表示链表的结束*/

return L;

} /*CreateFromTail*/

(239) 下列算法在顺序表L中依次存放着线性表中的元素，在表中查找与e相等的元素，若 L.elem[i]=e,则找到该元素，并返回i+1，若找不到，则返回“-1” ，请填空完善之。

int Locate(SeqList L，int e)

{ i=0 ; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/ while ((i<=L.last)&&(L.elem[i]!=e) ) i++;

/*顺序扫描表，直到找到值为key的元素,或扫描到表尾而没找到*/

if ( i<=L.last ) return(i+1); /*若找到值为e的元素，则返回其序号*/

else return(-1); /*若没找到，则返回空序号*/ }

(240) 下列算法在顺序表L中第i个数据元素之前插入一个元素e。 插入前表长n=L->last+1，i的合法取值范围是 1≤i≤L->last+2，请填空完善之。

void InsList(SeqList *L, int i, int e) { int k;

if((i<1) || (i>L->last+2)) printf(“插入位置i值不合法”)； if(L->last>=maxsize-1) printf(“表已满无法插入”)；

for(k=L->last;k>=i-1;k--) /*为插入元素而移动位置*/

L->elem[k+1]=L->elem[k] ;

L->elem[i-1]=e ; /*在C语言数组中，第i个元素的下标为i-1*/ L->last++ ;

}

(241) 下列算法是在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1≤i≤L.last+1，请填空完善之。

int DelList(SeqList *L, int i, int *e) { int k;

if((i<1)||(i> L->last+1 )) printf(“删除位置不合法！”)；