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

《数据结构样卷答案09级.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、南京工程学院试题评分标准及参考答案(样)共7页第1页2010/2011学年第2学期课程所属部门：计算机工程学院课程名称：数据结构使用班级：计算机专业2009级各班制作人：叶核亚、黄纬2011年5月24日一.填空题（26分，每空2分）（1）使数据类型的定义和实现分离，使一种定义有多种实现。（2）Node*table[4];Nodetable[4];（3）"abac"（4）ABCDEF+*G/-H+*+IJ+K*-（5）36（6）1148（7）7（8）右单支二叉树（包括空二叉树、只有根结点的二叉树）（9）511（10）n*(n-1)/2（11）（12

2、）{41*4134105424}67{7869}二.问答题（45分，每小题5分）（1）模式串"abcaababc"改进的next数组为j012345678模式串abcaababc""中最长相同的前后缀子串长度k-100011212与比较≠≠===≠==改进的next[j]-100-110200（2）栈和队列都属于线性表结构，它们是两种特殊的线性表，栈的插入和删除操作都在线性表的一端进行，所以栈的特点是“后进先出”；而队列的插入和删除操作分别在线性表的两端进行，所以队列的特点是“先进先出”。深度优先搜索遍历算法需要使用栈作为辅助结构，广度优先搜索遍历算法需要使

3、用队列作为辅助结构。采用顺序存储结构的栈和队列，在进行插入、删除操作时不需要移动数据元素，因为栈和队列均不能进行中间插入、删除操作。顺序队列，当入队的元素个数（包括已出队元素）超过数组容量时，队列尾下标越界，数据溢出。此时，由于之前已有若干元素出队，数组前部已空出许多存储单元，所以，这种溢出并不是因存储空间不够而产生的，称之为假溢出。顺序队列之所以会产生假溢出现象，是因为顺序队列的存储单元没有重复使用机制。解决的办法是将顺序队列设计成循环结构。链式存储结构队列不会出现假溢出。因为每次元素入队，都要申请新结点，数据不会溢出。顺序存储结构的栈不会出现假溢出。因为

4、顺序栈的存储单元可以重复使用，如果数组容量不够，则是数据溢出，而不是假溢出。（3）（4）（5）（6），代价是45（7）（8）希尔排序算法是不稳定的，因为与距离较远的元素进行比较，不能保证排序稳定性。希尔排序算法仅适用于顺序存储结构，因为与距离较远的元素进行比较，需要利用随机存储特性。（9）三.程序阅读题（15分，每小题5分）（1）将list链表合并连接到当前链表最后，设置list链表为空source：(a,b,c,d,e,f,x,y,z)list：()（2）①运行结果为“abcdefxyzefxyz”，正确的运行结果是“abcdefxyz”。②trim()函

5、数首先寻找串的第一个空格字符，用i记住空格字符下标；再遍历串，将串中的非空格字符（用j记住其下标）逐个向前移动到空格字符位置（i下标）；算法存在错误，删除后没将字符串结束符''向前移动到len处，导致cout输出仍然到''，如下图所示。③改正：函数体最后增加以下一句：element[len]='';（3）深拷贝创建二叉树时，没有为各结点建立指向父母结点的链。改正如下：①当TriNode构造函数不指定parent时templateTriNode*TriBinaryTree::copy(TriNode*p){TriN

6、ode*q=NULL;if(p!=NULL){q=newTriNode(p->data);//创建结点，父母结点parent为空q->left=copy(p->left);//复制左子树，递归调用if(q->left!=NULL)q->left->parent=q;//为左孩子设置parent链q->right=copy(p->right);//复制右子树，递归调用if(q->right!=NULL)q->right->parent=q;//为右孩子设置parent链}returnq;//返回建立子树的根结点}②如果TriNode类声明以下构造函

7、数，参数包括指定父母结点：TriNode(Tdata,TriNode*parent=NULL,TriNode*left=NULL,TriNode*right=NULL)则TriNode类深拷贝构造函数可实现如下：templateTriBinaryTree::TriBinaryTree(TriBinaryTree&bitree)//拷贝构造函数，深拷贝{this->root=copy(bitree.root,NULL,1);}//复制以p为根的子二叉树，parent指向p的父母结点，返回新建子树的根结点templa

8、teTriNode*TriBi