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

南京工程学院试卷（样）共 8 页 第1页2010 /2011 学年 第 2 学期 课程所属部门： 计算机工程学院 课程名称： 数据结构 考试方式： 闭卷 使用班级： 计算机专业2009级各班 命题人：叶核亚、黄纬 教研室主任审核： 主管领导批准： 班级 学号 姓名 题号一二三四五总分得分本题得分一. 填空题（26分，每空2分）1. 声明抽象数据类型的目的是_。2. 已知结点类Node有data和next域，下列数据存储结构声明分别为_和_。3. 已知SString s1(aababbabac),s2(aba);，执行下列语句后，s1字符串是_。s1.replaceAll(s1.substring(0,1),s2);s1.removeAll(s2.substring(0,2);4. 中缀表达式A+B*(C-D*(E+F)/G+H)-(I+J)*K的后缀表达式为_。5. 设一个顺序循环队列容量为60，当front=47，rear=23时，该队列有_个元素。6. 已知二维数组a108采用行主序存储，数组首地址是1000，每个元素占用4字节，则数组元素a45的存储地址是_。7. 已知一棵完全二叉树的根（第0个）结点层次为1，则第100个结点的层次为_。8. 中根遍历序列和后根遍历序列相反的二叉树是_。9. 由256个权值构造一棵哈夫曼树，则该二叉树共有_结点。10. 由n个顶点组成的无向连通图，最多可以有_条边。11. 10个元素的排序数据序列采用折半查找的平均查找长度是（写出算式）_。12. 已知关键字序列为67,41,34,10,69,24,78,54,41*，采用快速排序算法按升序排序，以第一个元素为基准值，其第一趟排序后的关键字序列为_。二. 问答题（45分，每小题5分）1. 已知目标串为aabcbabcaabcaababc，模式串为abcaababc，写出模式串改进的next数组；画出KMP算法的匹配过程，给出字符比较次数。2. 什么是栈和队列？两者有何异同？什么情况下需要使用栈或队列？采用顺序存储结构的栈和队列，在进行插入、删除操作时需要移动数据元素吗？为什么？什么是队列的假溢出？为什么顺序存储结构队列会出现假溢出？怎样解决队列的假溢出问题？链式存储结构队列会出现假溢出吗？顺序存储结构的栈会出现假溢出吗？为什么？3. 已知一棵二叉树中根次序遍历序列为GCBHKAMFDJE，后根次序遍历序列为CBGHMAJEDFK，画出这棵二叉树并进行中序线索化。4. 设一段正文由字符集A,B,C,D,E,F,G,H组成，其中每个字符在正文中的出现次数依次为23,5,17,4,9,31,29,18，采用哈夫曼编码对这段正文进行压缩存储，画出所构造的哈夫曼树，并写出每个字符的哈夫曼编码。5. 删除以下带权无向图中的顶点D，画出删除D后图的邻接矩阵表示和邻接表表示。6. 构造以下带权无向图的最小生成树，并给出该最小生成树的代价。7. 已知关键字序列为16,74,60,43,54,90,46,31,29,88,71,64,50，散列表长度为11，采用除留余数法的散列函数为hash(k)=k % 11，画出采用链地址法构造的散列表，计算（写出算式）。8. 画出对关键字序列93,17,56,42,78,15,42*,25,19进行希尔排序（升序）的每一趟排序过程，说明希尔排序算法的稳定性并解释原因，以及希尔排序适用于什么存储结构。9. 将关键字序列29,10,25,26,58,12,31,18,47用筛选法分别建成一个最大堆和一个最小堆，写出两个堆序列并画出其对应的完全二叉树。三. 程序阅读和改错题（15分，每小题5分） 1. 阅读以下函数，回答问题。template void CirHDoublyLinkedList:concat(CirHDoublyLinkedList &list) DLinkNode *rear=head-prev; rear-next = list.head-next; list.head-next-prev = rear; rear=list.head-prev; rear-next = this-head; this-head-prev = rear; list.head-prev = list.head; list.head-next = list.head; 上述函数功能是什么？以下调用语句的运行结果是什么？CirHDoublyLinkedList source(abcdef,6), list(xyz,3);source.concat(list);coutsource：sourcelist：list;2. 下列trim()函数欲删除当前字符串对象中的所有空格字符。void SString:trim() /删除串对象中的所有空格字符 int i=0; while (elementi!= & elementi!=0) /寻找第1个空格 i+; /i记住第1个空格下标 for (int j=i; elementj!=0; j+) if (elementj!= ) elementi+ = elementj; /非空格字符向前移动到空格字符位置 len = i; 对于以下调用语句，运行结果是什么？正确的运行结果是什么？SString str( a bc d e f xyz);str.trim();coutstr=strendl; trim()函数怎样实现所求功能？算法存在什么错误？ 如何改正？3. 已知三叉链表表示的二叉树结点类TriNode声明如下：template class TriNode /二叉树的三叉链表结点类 public: T data; /数据域，保存元素 TriNode *parent, *left, *right; /指针域，分别指向父母、左、右孩子结点 /构造结点，参数依次分别指定元素、左孩子和右孩子结点 TriNode(T data, TriNode *left=NULL, TriNode *right=NULL) this-data = data; this-left = left; this-right = right; ;三叉链表表示的二叉树类TriBinaryTree及部分函数声明如下：class TriBinaryTree /二叉树类（三叉链表） public: TriNode *root; /指向根结点 TriBinaryTree(TriBinaryTree &bitree); /拷贝构造函数 private: TriNode* copy(TriNode *p); /复制以p为根的子二叉树;template TriBinaryTree:TriBinaryTree(TriBinaryTree &bitree) /拷贝构造函数 this-root = copy(bitree.root);/复制以p为根的子二叉树，返回新建子树的根结点template TriNode* TriBinaryTree:copy(TriNode *p) TriNode *q=NULL; if (p!=NULL) q = new TriNode(p-data); q-left = copy(p-left); q-right = copy(p-right); return q; 上述函数中存在什么错误？如何改正？四. 程序设计题（14分，每小题7分） 1. 在带头结点的单链表类HSLinkedList中，增加以下成员函数： void HSLinkedList:removeAll(HSLinkedList &list) /删除所有与list匹配的子表2. 求二叉树中指定结点的层次。 南京工程学院试卷 共 8 页 第 2 页 本题得分 南京工程学院试卷 共 8 页 第 3 页 南京工程学院试卷 共 8 页 第 4 页 南京工程学院试卷 共 8 页 第 5 页 本题得分 南京工程学院试卷 共 8 页 第 6 页 南京工程学院试卷 共 8 页 第 7 页 南京工程学院试卷 共 8 页 第 8 页 本题得分南京工程学院试题评分标准及参考答案(样) 共7页 第 1 页 2010 / 2011 学年第 2 学期课程所属部门： 计算机工程学院 课程名称： 数据结构 使用班级：计算机专业2009级各班 制作人：叶核亚、黄纬 2011年5月24日五. 填空题（26分，每空2分）1. 使数据类型的定义和实现分离，使一种定义有多种实现。2. Node* table4;Node table4;3. abac4. ABCDEF+*G/-H+*+IJ+K*-5. 366. 11487. 78. 右单支二叉树（包括空二叉树、只有根结点的二叉树）9. 51110. n*(n-1)/211. 12. 41* 41 34 10 54 24 67 78 69六. 问答题（45分，每小题5分）1. 模式串abcaababc改进的next数组为j012345678模式串abcaababc中最长相同的前后缀子串长度k-100011212与比较=改进的nextj-100-1102002. 栈和队列都属于线性表结构，它们是两种特殊的线性表，栈的插入和删除操作都在线性表的一端进行，所以栈的特点是“后进先出”；而队列的插入和删除操作分别在线性表的两端进行，所以队列的特点是“先进先出”。深度优先搜索遍历算法需要使用栈作为辅助结构，广度优先搜索遍历算法需要使用队列作为辅助结构。采用顺序存储结构的栈和队列，在进行插入、删除操作时不需要移动数据元素，因为栈和队列均不能进行中间插入、删除操作。顺序队列，当入队的元素个数（包括已出队元素）超过数组容量时，队列尾下标越界，数据溢出。此时，由于之前已有若干元素出队，数组前部已空出许多存储单元，所以，这种溢出并不是因存储空间不够而产生的，称之为假溢出。顺序队列之所以会产生假溢出现象，是因为顺序队列的存储单元没有重复使用机制。解决的办法是将顺序队列设计成循环结构。链式存储结构队列不会出现假溢出。因为每次元素入队，都要申请新结点，数据不会溢出。顺序存储结构的栈不会出现假溢出。因为顺序栈的存储单元可以重复使用，如果数组容量不够，则是数据溢出，而不是假溢出。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. 运行结果为“abcdefxyz e f xyz”，正确的运行结果是“abcdefxyz”。 trim()函数首先寻找串的第一个空格字符，用i记住空格字符下标；再遍历串，将串中的非空格字符（用j记住其下标）逐个向前移动到空格字符位置（i下标）；算法存在错误，删除后没将字符串结束符0向前移动到len处，导致cout输出仍然到0，如下图所示。 改正：函数体最后增加以下一句： elementlen = 0;3. 深拷贝创建二叉树时，没有为各结点建立指向父母结点的链。改正如下： 当TriNode构造函数不指定parent时template TriNode* TriBinaryTree:copy(TriNode *p) TriNode *q=NULL; if (p!=NULL) q = new TriNode(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链 return q; /返回建立子树的根结点 如果TriNode类声明以下构造函数，参数包括指定父母结点：TriNode(T data, TriNode *parent=NULL, TriNode *left=NULL, TriNode *right=NULL)则TriNode类深拷贝构造函数可实现如下：template TriBinaryTree:TriBinaryTree(TriBinaryTree &bitree) /拷贝构造函数，深拷贝 this-root = copy(bitree.root, NULL, 1);/复制以p为根的子二叉树，parent指向p的父母结点，返回新建子树的根结点template TriNode* TriBinaryTree:copy(TriNode *p, TriNode *parent) TriNode *q=NULL; if (p!=NULL) q = new TriNode(p-data, parent); /创建结点，父母结点是parent q-left = copy(p-left, p); /复制左子树，递归调用 q-right = copy(p-right, p); /复制右子树，递归调用 return q; /返回建立子树的根结点八. 程序设计题（14分，每小题7分） 以下给出参考程序，阅卷老师可根据实际情况评分，重点是表达算法思想。1. 在带头结点的单链表类HSLinkedList中，增加以下成员函数，删除所有与list匹配的子表。template void HSLinkedList:removeAll(HSLinkedList &list) Node *start=head-next, *front=head; while (start!=NULL) Node *p=start, *q=list.head-next; while (p!=NULL & q!=NULL & p-data=q-data) /一次匹配 p=p-next; q=q-next; if (q!=NULL) /一次匹配失败，再进行下一次匹配 front=start; start=start-next; else /一次匹配成功，删除一个子表 q=list.head-next; while (q!=NULL) /删除从start开始与list匹配的子表 front-next = start-next; /删除start结点 delete start; start=front-next; q=q-next; 2. 求二叉树中指定结点的层次。一棵二叉树中结点所在的层次定义：令根结点的层次为1，其他结点的层次是其父母结点的层次加1。 在二叉链表存储的二叉树类BinaryTree中增加成员函数如下：template int BinaryTree:getLevel(T x) /返回x结点所在的层次 /若空树或未查找到x返回-1 if (root=NULL) return -1; return getLevel(root, 1, x); /令根结点的层次为1template int BinaryTree:getLevel(BinaryNode *p, int i, T x) /在以p结点（层次为i）为根的子树中求x结点所在层次 if (p!=NULL) if (p-data=x) return i; /查找成功 int level = getLevel(p-left, i+1, x); /在左子树查找 if (level!=-1) return level; return getLevel(p-right, i+1, x); /继续在右子树中查找 return -1; /查找不成功 在二叉链表结点类BinaryNode中增加表示结点层次的成员变量level，结点构造函数声明如下：BinaryNode(T data, BinaryNode *left=NULL, BinaryNode *right=NULL, int level=0)构造二叉树时设置每个结点的层次属性。例如，二叉树类BinaryTree的一种构造函数声明如下：template BinaryTree:BinaryTree(T prelist, int n) /以标明空子树的先根序列构造一棵二叉树 int i=0; root=create(prelist, n, i, NULL, 1); /根结点的层次为1 /以标明空子树的先根次序遍历序列创建一棵子树，该子树根结点是prelisti， /根结点层次是level，其父母结点由parent指向，返回创建子树的根结点指针template BinaryNode* BinaryTree:create(T prelist, int n, int &i, int level) BinaryNode *p=NULL; if (in)