苏大数据结构模拟题

苏州大学 数据结构 课程试卷 1 卷

一、 填空（2 分×16）

1、对于一个栈作进栈运算时，应先判别栈是否为___栈满_____，作退栈运算时，应先判别

栈是否为___空_____。

2、下面程序段的时间复杂度为___o(n³)________。

for (i=0; i<m; i++)

for (j=0; j<n; j++)

for (k=0; k<t; k++)

的时间复杂度为__ O（n + e）________________。

6、哈希表的装填因子定义为__表中填入的记录数/哈希表的长度___；直观地看，装填因子

越________，发生冲突的可能性就越小。

7、拓扑排序的方法为____________________________________________________________

_____________________________________________________________________________。

8、设 F 是森林，B 是由 F 转换得到的二叉树，F 中有 n 个非终端结点，B 中右指针域为空的

结点有___________个。

9、已知一个有序表为（5，13，19，21，37，56，64，75，80，88，92），当折半查找值为

21 的元素时，若采用 binary_search_1 方法，需_______次比较可查找成功。

10、在 Dijkstra 算法中，S 为_________________________________________的集合，算法的

changchun，beijing，jinan，fuzhou，changsha，xian，nanjing，tianjin}，画出生成的二叉排

序树，求出在等查找概率情况下查找成功时的平均查找长度，并画出删除 haerbin 之后所得

的二叉排序树。（12 分）

3、Prim 算法求下图的最小生成树，请写出求解过程。（8 分）