资源描述：
《一、请回答下列关于图（graph）的一些问题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、一、请回答下列关于图(Graph)的一些问题：(1)(4分)有n个顶点的有向强连通图最多有多少条边？最少有多少条边？(2)(4分)表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？(3)(4分)对于一个有向图，不用拓扑排序，如何判断图中是否存在环？二、斐波那契数列Fn定义如下：请就此斐波那契数列，回答下列问题。(1)（7分）在递归计算Fn的时候，需要对较小的Fn-1,Fn-2,…,F1,F0精确计算多少次？(2)（5分）如果用大O表示法，试给出递归计算Fn时递归函数的时间复杂度是多少？三、有一种
2、简单的排序算法，叫做计数排序（countSorting）。这种排序算法对一个待排序的表（用数组表示）进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同。计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。(1)（3分）给出适用于计数排序的数据表定义；(2)（7分）使用Pascal或C语言编写实现计数排序的算法；(3)（4分）对于有n个记录的表，关键码比较次数
3、是多少？(4)（3分）与简单选择排序相比较，这种方法是否更好？为什么？四、（10分）在一棵表示有序集S的二叉搜索树（binarysearchtree）中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S1；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S=S1ÈS2ÈS3。若对于任意的aÎS1,bÎS2,cÎS3，是否总有a£b£c？为什么？五、请回答下列关于堆(Heap)的一些问题：(1)（4分）堆的存储表示是顺序的，还是链接的？(2)（4分）设有一个最小堆,即堆中任
4、意结点的关键码均大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？(3)（4分）对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O表示法)？六、（12分）已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量，使用Pascal或C语言编写一个算法，将队列Q中的所有元素逆置。栈的ADT函数有makeEmpty(s:stack);置空栈push(s:stack;value:datatype);新元素value进栈pop(s:stack):datatype;出栈，返回栈顶值isEmpty(s
5、:stack):boolean;判栈空否队列的ADT函数有enqueue(q:queue;value:datatype);元素value进队deQueue(q:queue):datatype;出队列,返回队头值isEmpty(q:queue):boolean;判队列空否数据结构与程序设计八、设散列表为HT[0..12]，即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为：H0(key)=key%13;注：%是求余数运算(=mod)Hi=(Hi-1+REV(key+1)%11+1)%13;i=1,2,3,¼,m-
6、1其中，函数REV(x)表示颠倒10进制数x的各位，如REV(37)=73，REV(7)=7等。若插入的关键码序列为{2,8,31,20,19,18,53,27}。(1)(8分）试画出插入这8个关键码后的散列表。(2)(5分）计算搜索成功的平均搜索长度ASL。九、从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆转，如下图所示。在图中的指针p指向当前正在访问的结点，指针pr指向指针p所指结点的左侧的结点。此时，指针p所指结点左侧的所有结点的链接方向都已逆转。(1)（6分）使用Pascal或C语言编写
7、一个算法，从任一给定位置(pr,p)开始，将指针p右移1个结点。如果p移出链表，则将p置为NULL，并让pr停留在链表最右边的结点上。(2)（6分）使用Pascal或C语言编写一个算法，从任一给定位置(pr,p)开始，将指针p左移1个结点。如果p移出链表，则将p置为NULL，并让pr停留在链表最左边的结点上。一、回答有关图的问题：(1)有n个顶点的有向强连通图最多有n*(n-1)条边，最少有n条边。(2)有1000个顶点、1000条边的有向图的邻接矩阵有1000000个矩阵元素，其中只有1000个非零元素，是一个稀疏矩阵。(3)对一
8、个有向图，不用拓扑排序，可以用以下方法判断图中是否存在环：¬如果图中所有顶点的出度至少为1，入度也至少为1，则图中存在环。这个条件太强。如果对图进行深度优先搜索，从某个顶点出发，又走到以前已经访问过的顶点，则图中存在环。二、关于斐波那
