黑发不知勤学早，白发方悔读书迟——颜真卿
计算机系《数据结构》试题2003.6.
班级        学号              姓名         
一、填空题（每空2分，共20分）
字符串长度排序1． 与链式存储结构相比，顺序存储结构的优点是                                           
2． 设字符a、b、c、d、e 的权分别为23，29，14，19 和15，设计一棵Huffman树，则该Huffman树根结点的权为               
3．设某二叉树的前序和中序序列均为ABCDE，则它的后序序列是                               
4．在排序过程中，每一趟都不能确定任何一个元素的最终位置，但能适用于链表排序的排序算法是              排序 
  5．以数组]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，则队列第一个元素的实际位置是                           
6．将长度分别为m，n的两个有序子表进行归并，至多需要比较      次
7．设源串S="bcdcdcb"，模式串P="cdcb"，按KMP算法进行模式匹配，当"S2S3S4"="P1P2P3"，而S5≠P4时，S5应与          比较
  8．设序列{12，34，19，23，8，56}，试建立表长为7的Hash表
Hash函数为H（key）=key MOD 7，用线性探测法解决冲突，则56冲突      次
9．设n>0，且有如下程序段：
int  i;    i = n;
while (i>0)  i=i/10;
  则该程序的时间复杂性为___________________
  10．假设以一维数组作为n阶对称矩阵A的存储空间，以行序为主序存储A的下三角，则元素A[9][7]的值存储在S[_______]中
二、求解图的最小生成树有哪些算法？这些算法各有什么特点？各适用于
  什么情况？时间复杂性分别如何？（10分）
三．设有一个表长为12的有序顺序表用二分查算法进行查操作，试求解查成功情况下该表的平均查长度，要求写出求解过程
（10分）
四、快速排序是稳定的吗？若不稳定，则举出一个不稳定的实例
（10分）
五、试编写一个算法统计字符串s中含有子串t的个数
（10分）
六、试编写一个算法将线性表L中的数据建立一棵二叉排序树
（12分）
  七、已知有向图G用邻接表存储，试写出邻接表的类型定义，并编写一个算法求图中每个顶点的出度和入度
（14分）
八、任你选择一个算法进行改进，试给出改进前后的算法描述，并说明算法改进前后的性能区别
（14分）
2001级计算机专业《数据结构》试卷
第 1 页 共 6页
黑发不知勤学早，白发方悔读书迟——颜真卿

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。