数据结构试题及答案(13)

数据结构试题及答案

30、对于一个具有n个顶点肯e 条边的无向图，进行拓朴排序时，总的进间为（n）

31、构造哈希函数有三种方法，分别为(平方取中)法、(除留余数)法、(折迭移位)法。

32、处理冲突的三种方法，分别为(线性探测)、（ 随机探测 ）、（ 链地址法）。 33、对于含有n个顶点和e条边的无向连通图，利用普里姆算法产生的最小生成树，其时间复杂度为（ Ｏ（n2） ）、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（Ｏ（elog2e） ）

34、快速排序在平均情况下的时间复杂度为（Ｏ（nlog2n）），在最坏情况下的时间复杂度为（Ｏ（n2））；快速排序在平均情况下的空间复杂度为（Ｏ（log2n）），在最坏情况下的空间复杂度为（Ｏ（n））。

35、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行归并排序的过程中，第二趟排序后的结果是（［３８ ４６ ５６ ７９］［４０ ８０］）

36、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行快速排序的第一次划分的结果是（［３８ ４０］４６［５６ ７９ ８０］）。 37、一个结点的子树的（ 个数 ）称为该结点的度。度为（ 零 ）的结点称为叶结点或终端结点。度不为（ 零 ）的结点称为分支结点或非终端结点。树中各结点度的（ 最大值 ）称为树的度。

38、设Ki=Kj (1<=i<=n, 1<=j<=n,j<>i)且在排序前的序列中Ri领先于Rj (i<j),若排序后的序列中Ri仍领先于 Rj，则这种排序方法是（稳定的），反之是（不稳定的）。

40 、在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为（Ｏ（log2n）），整个排序过程的时间复杂度为（Ｏ（nlog2n））。

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新教学研究数据结构试题及答案(13)全文阅读和word下载服务。