南京工程学院数据结构样卷09级附答案.doc

南京工程学院试卷（样） 2010 /2011 学年 第 2 学期 课程所属部门： 计算机工程学院 课程名称： 数据结构 考试方式： 闭卷 使用班级： 计算机专业2009级各班 命题人：叶核亚、黄纬 教研室主任审核： 主管领导批准： 题号 一 二 三 四 五 总分 得分  共 8 页 第1页 班级 学号 姓名 本题 得分 填空题（26分，每空2分） 声明抽象数据类型的目的是________________________________________。 已知结点类NodeT有data和next域，下列数据存储结构声明分别为 __________________________________和_____________________________________。 已知SString s1(aababbabac),s2(aba);，执行下列语句后，s1字符串是______________。 s1.replaceAll(s1.substring(0,1),s2); s1.removeAll(s2.substring(0,2)); 中缀表达式A+B*(C-D*(E+F)/G+H)-(I+J)*K的后缀表达式为______________________。 设一个顺序循环队列容量为60，当front=47，rear=23时，该队列有__________个元素。 已知二维数组a[10][8]采用行主序存储，数组首地址是1000，每个元素占用4字节，则数组元素a[4][5]的存储地址是__________________________。 已知一棵完全二叉树的根（第0个）结点层次为1，则第100个结点的层次为_______。 中根遍历序列和后根遍历序列相反的二叉树是_________________________________。 由256个权值构造一棵哈夫曼树，则该二叉树共有________________结点。 由n个顶点组成的无向连通图，最多可以有_____________________条边。 10个元素的排序数据序列采用折半查找的平均查找长度是（写出算式）_____________________________________________________。 已知关键字序列为{67,41,34,10,69,24,78,54,41*}，采用快速排序算法按升序排序，以第一个元素为基准值，其第一趟排序后的关键字序列为____________________________。 问答题（45分，每小题5分） 已知目标串为aabcbabcaabcaababc，模式串为abcaababc，写出模式串改进的next数组；画出KMP算法的匹配过程，给出字符比较次数。 什么是栈和队列？两者有何异同？什么情况下需要使用栈或队列？采用顺序存储结构的栈和队列，在进行插入、删除操作时需要移动数据元素吗？为什么？什么是队列的假溢出？为什么顺序存储结构队列会出现假溢出？怎样解决队列的假溢出问题？链式存储结构队列会出现假溢出吗？顺序存储结构的栈会出现假溢出吗？为什么？ 已知一棵二叉树中根次序遍历序列为GCBHKAMFDJE，后根次序遍历序列为CBGHMAJEDFK，画出这棵二叉树并进行中序线索化。 设一段正文由字符集{A,B,C,D,E,F,G,H}组成，其中每个字符在正文中的出现次数依次为