数据结构样卷答案09级.docVIP

南京工程学院 试题评分标准及参考答案(样) 共7页 第 1 页 2010 / 2011 学年第 2 学期 课程所属部门： 计算机工程学院 课程名称： 数据结构 使用班级：计算机专业2009级各班 制作人：叶核亚、黄纬 2011年5月24日 填空题（26分，每空2分） 使数据类型的定义和实现分离，使一种定义有多种实现。 NodeT* table[4]; NodeT table[4]; abac ABCDEF+*G/-H+*+IJ+K*- 36 1148 7 右单支二叉树（包括空二叉树、只有根结点的二叉树） 511 n*(n-1)/2 {41* 41 34 10 54 24} 67 {78 69} 问答题（45分，每小题5分） 模式串abcaababc改进的next数组为 j 0 1 2 3 4 5 6 7 8 模式串 a b c a a b a b c 中最长相同的前后缀子串长度k -1 0 0 0 1 1 2 1 2 与比较 ≠ ≠ = = = ≠ = = 改进的next[j] -1 0 0 -1 1 0 2 0 0 栈和队列都属于线性表结构，它们是两种特殊的线性表，栈的插入和删除操作都在线性表的一端进行，所以栈的特点是“后进先出”；而队列的插入和删除操作分别在线性表的两端进行，所以队列的特点是“先进先出”。深度优先有哪些信誉好的足球投注网站遍历算法需要使用栈作为辅助结构，广度优先有哪些信誉好的足球投注网站遍历算法需要使用队列作为辅助结构。采用顺序存储结构的栈和队列，在进行插入、删除操作时不需要移动数据元素，因为栈和队列均不能进行中间插入、删除操作。 顺序队列，当入队的元素个数（包括已出队元素）超过数组容量时，队列尾下标越界，数据溢出。此时，由于之前已有若干元素出队，数组前部已空出许多存储单元，所以，这种溢出并不是因存储空间不够而产生的，称之为假溢出。顺序队列之所以会产生假溢出现象，是因为顺序队列的存储单元没有重复使用机制。解决的办法是将顺序队列设计成循环结构。 链式存储结构队列不会出现假溢出。因为每次元素入队，都要申请新结点，数据不会溢出。顺序存储结构的栈不会出现假溢出。因为顺序栈的存储单元可以重复使用，如果数组容量不够，则是数据溢出，而不是假溢出。 （4）（5） （6），代价是45 （7） （8） 希尔排序算法是不稳定的，因为与距离较远的元素进行比较，不能保证排序稳定性。希尔排序算法仅适用于顺序存储结构，因为与距离较远的元素进行比较，需要利用随机存储特性。 （9） 程序阅读题（15分，每小题5分） 将list链表合并连接到当前链表最后，设置list链表为空 source：(a, b, c, d, e, f, x, y, z) list：() ①运行结果为“abcdefxyz e f xyz”，正确的运行结果是“abcdefxyz”。 ② trim()函数首先寻找串的第一个空格字符，用i记住空格字符下标；再遍历串，将串中的非空格字符（用j记住其下标）逐个向前移动到空格字符位置（i下标）；算法存在错误，删除后没将字符串结束符\0向前移动到len处，导致cout输出仍然到\0，如下图所示。 ③ 改正：函数体最后增加以下一句： element[len] = \0; 深拷贝创建二叉树时，没有为各结点建立指向父母结点的链。改正如下： ① 当TriNode构造函数不指定parent时 template class T TriNodeT* TriBinaryTreeT::copy(TriNodeT *p) { Tri