16．下面算法的功能是______。 int count(adjmatrix GA，int i，int n) {int d=0;
for (int j=0; j return(d); } A．计算图中边的数目 B．计算图中i顶点的度 C．计算图中i顶点的入度 D．计算图中i顶点的出度 17． (1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义； (2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3 ) ；（图用邻接矩阵表示） (3). Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。 上面不正确的是_______。 A．(1),(2),(3) B．(1) C．(1),(3) D．(2),(3) 18．以下算法的功能是_______。 void AI(adjmatrix GA，int i，int n) { printf(“%d”,i)； visited[i]＝true； for(intj＝0；j＜n；j++) if(Ga[i][j]!＝0&&GA[i][j]!＝MaxValue &&!visited[j]) AI(GA，j，n)； } A．对图GA进行广度优先遍历 B．对图GA进行深度优先遍历 C．对图GA输出i到j的路径 D．求图GA中边的数目 二、判断对错题：（正确的选A，错误的选B） 1. 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ ） 2. 在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（ ） 3. 用邻接矩阵表示图时，矩阵元素的个数与边的条数有关。（ ） 4. 图型结构中元素之间存在1对多关系。（ ） 5. 若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。（ ） 6. 树中的结点和图中的顶点就是指数据结构中的数据元素。（ ） 7. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（ ） 8. 带权的有向图和无向图，只能使用邻接表存储形式来存储它。（ ） 9. 连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ） 10. 邻接多重表是无向图和有向图的链式存储结构。（ ） 11. 强连通图的各顶点间均可达。（ ） 12. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图。（ ） 13. 一个有向图的邻接表和逆邻接表中结点的个数可能不等。（ ） 14. 图最适合用来表示元素之间具有分支层次关系的数据。（ ） 15. 有e条边的无向图，在邻接表中有e个结点。（ ） 16. 强连通分量是无向图的极大强连通子图。（ ） 17. 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。（ ） 18. 一个有向图的邻接表和逆邻接表中的结点个数一定相等。（ ） 三、应用题 1. 写出求正权图的最短路径算法。 2. 写出求图的拓扑排序算法 3. 写出求图的最小生成树的算法。 4. 写出图的深度优先遍历算法。 5. 写出图的广度优先遍历算法。 第5章 排序与查找 一、单项选择题：（从给定的选项中选择出一个最恰当的答案） 1．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为_____。 A．f,c,b B．f,d,b C．g,c,b D．g,d,b 2．散列函数有一个共同的性质，即函数值应按_______取其值域中的每一个值。 A． 最大概率 B．最小概率 C．同等概率 D．平均概率 3．某内排序方法的稳定性是指______。 A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对 4．下面是一算法的核心部分，该算法的功能是______。 pre=L->next; {L是一带头结点单链表，结点有数据域 data和指针域 next} if (pre!=null) while (pre->next!=null) {p=pre->next; if(p->data>=pre->data) pre=p ELSE return(false)} return(true); A．判断L中相邻的两个结点是否升序排列 B．判断L中相邻的两个结点是否降序排列 C．判断L中的结点是否升序排列 D．判断L中的结点是否降序排列 5．若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为_______。 A． (n-1)/2 B． n/2 C． (n+1)/2 D． n 6．下列排序方法中，_______不是稳定的排序方法？ A．直接选择排序 B．二分法插入排序 C．二路归并排序 D．快速排序 7. 既希望较快的查找又便于线性表动态变化的查找方法是 _____ 。 A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找 8.以下算法的功能（栈中的数据元素类型为int）是_______。 void algo（Queue &Q）｛ Stack S； int d； InitStack（S）； while (!QueueEmpty(Q)) {DeQueue(Q,d); Push(S,d);；｝ while (!StackEmpty(S)) {pop(S,d); EnQueue(Q,d); ｝ ｝ A．将栈S中的元素逆置 B．将队列Q中的元素逆置 C．输出栈S中的元素 D．输出队列Q中的元素 9．当采用分快查找时，数据的组织方式为________。 A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C． 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D． 数据分成若干块，每块（除最后一块外）中数据个数需相同 10．若用数组S[0..n-1]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是_______。 A．S1的栈底位置为0，S2的栈底位置为n-1 B．S1的栈底位置为0，S2的栈底位置为n/2-1 C．S1的栈底位置为1，S2的栈底位置为n D．S1的栈底位置为1，S2的栈底位置为n/2 11 对线性表进行二分查找时，要求线性表必须______. A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序 12．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为_______。 A．(38,40,46,56,79,84) B. (40,38,46,79,56,84) C．(40,38,46,56,79,84) D. (40,38,46,84,56,79) 13．既希望较快的查找又便于线性表动态变化的查找方法是 _____ 。 A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找 14．排序趟数与序列的原始状态有关的排序方法是_______排序法。 A．插入 B. 选择 C. 冒泡 D. 快速 15．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的_______的两趟排序后的结果。 A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序 16．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 _______。 A. 选择 B. 冒泡 C. 快速 D. 插入 17．具有12个关键字的有序表，折半查找的平均查找长度_______。 A. 3.1 B. 4 C. 2.5 D. 5 18．折半查找的时间复杂性为_______。 A. O（n2） B. O（n） C. O（nlogn） D. O（logn） 19．关于杂凑查找说法不正确的有几个_______。 （1）采用链地址法解决冲突时，查找一个元素的时间是相同的 （2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的 （3）用链地址法解决冲突易引起聚集现象 （4）再哈希法不易产生聚集 A. 1 B. 2 C. 3 D. 4 20．假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行_______次探测？ A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次 21．散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是_______。 A． 8 B. 9 C. 10 D. 11 22．对序列（22，86，19，49，12，30，65，35，18）进行一趟排序后得到的结果如下： （18，12，19，22，49，30，65，35，86），则可以认为使用的排序方法是______。 A．选择排序 B．冒泡排序 C．快速排序 D．插入排序 二、判断对错题：（正确的选A，错误的选B） 1. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（ ） 2. Hash表的平均查找长度与处理冲突的方法无关。（ ） 3. 直接选择排序算法在最好情况下的时间复杂度为O（N），N是数据元素的个数。（ ） 4. 排序算法中的比较次数与初始元素序列的排列无关。（ ） 5. 适用于折半查找的表的存储方式及元素排列要求是：链接方式存储，元素无序 。（ ） 6. 当采用分快查找时，数据的组织方式为数据分成若干块，每块内数据有序。（ ） 7. 散列函数越复杂越好，因为这样随机性好，冲突概率小。（ ） 8. 冒泡排序和快速排序都是基于交换两个逆序元素的排序方法。（ ） 9. 在排序过程中，主要进行的两种基本操作是关键字的比较和记录的移动。（ ） 10. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ） 11. 快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。（ ） 12. 采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（ ） 13. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ ） 14. 在任何情况下，归并排序都比简单插入排序快。（ ） 15 哈希表的结点中只包含数据元素自身的信息，不包含任何指针。（ ） 16 当待排序记录已从小到大排序或者已从大到小排序时，快速排序的执行时间最省。（ ） 17. 采取链地址法来解决冲突时, 其装载因子的取值一定在(0,1)之间。（ ） 三、应用题 1. 给出一组关键字（7，14，9，21，9，10，12）进行快速排序，试列出每一趟排序后关键字的排列次序，并比较每遍排序所进行的关键字比较次数。 2. 给出一组关键字（7，14，9，21，9，10，12）进行堆排序，试列出每一趟排序后关键字的排列次序，并比较每遍排序所进行的关键字比较次数。 3. 给出一组关键字（7，14，9，21，9，10，12）进行SHELL（希尔）排序，试列出每一趟排序后关键字的排列次序，并比较每遍排序所进行的关键字比较次数。 4. 写出冒泡排序的算法。 5．写出快速排序的算法。 6．写出堆排序的算法。 7．写出SHELL（希尔）排序的算法。