南京工程的学院大数据结构样卷09级加详解

1、实用标准文案精彩文档数据结构09一. 填空题(26分，每空2分)1. 声明抽象数据类型的目的是 2. 已知结点类Node<T> 有data和next域，下列数据存储结构声明分别为tabledull mu山輛 fitt3. 已知 SStri ngs1("aababbabac"),s2("aba"); ，执行下列语句后，si 字符串是s1.replaceAII(s1.substri ng(0,1),s2);s1.removeAII(s2.substri ng(0,2);4. 中缀表达式A+B*(C-D*(E+F)/G+H)-(I+J)*K 的后缀

2、表达式为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

3、,54,41*,采用快速排序算法按升序排序，以第一个元素为基准值，其第一趟排序后的关键字序列为 。_二. 问答题（45分，每小题5分）1. 已知目标串为"aabcbabcaabcaababc" ，模式串为"abcaababc"，写出模式串改进的next数组；画出KMP算法的匹配过程，给出字符比较次数。2. 什么是栈和队列？两者有何异同？什么情况下需要使用栈或队列？采用顺序存储结构 的栈和队列，在进行插入、删除操作时需要移动数据元素吗？为什么？什么是队列的假溢 出？为什么顺序存储结构队列会出现假溢出？怎样解决队列的假溢出问题？链式存储结构 队列会出现假溢出

4、吗？顺序存储结构的栈会出现假溢出吗？为什么？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,

5、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. 阅读以下函数，回答问题。templat

6、e <class T>void CirHDoublyLi nkedList<T>:co ncat(CirHDoublyLi nkedList<T> & list)DLin kNode<T> *rear=head->prev;rear->n ext = list.head->n ext;list.head->n ext->prev = rear;rear=list.head->prev;rear- >n ext = this->head;this->head->prev = rea

7、r;list.head->prev = list.head;list.head->next = list.head;上述函数功能是什么？以下调用语句的运行结果是什么？CirHDoublyLi nkedList<char> source("abcdef',6), list("xyz",3);source.c on cat(list);cout<<"source : "<<source<<"list : "<<list;2. 下列trim()函数欲删

8、除当前字符串对象中的所有空格字符。/删除串对象中的所有空格字void SStri ng:trim()符 int i=0;/寻找第1个空格/i记住第1个空格下标/非空格字符向前移动到while (eleme nti !=' ' && eleme nti!='O')i+；for (int j=i; eleme nt j!='0' j+)if (elementj!='')eleme nti+ = eleme ntj;空格字符位置len = i; 对于以下调用语句，运行结果是什么？正确的运行结果是什么?SStri ng s

9、tr(" a be d e f xyz");str.trim();cout<<"str="<<str<<e ndl; trim()函数怎样实现所求功能？算法存在什么错误？ 如何改正？3. 已知三叉链表表示的二叉树结点类TriNode声明如下：template <class T>class TriNodeII二叉树的三叉链表结点类public:T data;II数据域，保存元素TriNode<T> *parent, *left, *right;/ 指针域，分别指向父母、左、右孩子结点/构造结点，参

10、数依次分别指定元素、左孩子和右孩子结点TriNode(T data, TriNode<T> *left=NULL, TriNode<T> *right=NULL)this->data = data;this->left = left;this->right = right;三叉链表表示的二叉树类TriBi naryTree及部分函数声明如下:class TriB in aryTreepublic:TriNode<T> *root;/二叉树类（三叉链表）/指向根结点TriBinaryTree(TriBinaryTree<T> &a

11、mp;bitree); private:TriNode<T>* copy(TriNode<T> *p);二叉树;template <class T>/拷贝构造函数/复制以p为根的子/拷贝构造函数TriBi naryTree<T>:TriBi naryTree(TriBi naryTree<T> &bitree) this->root = copy(bitree.root);/复制以p为根的子二叉树，返回新建子树的根结点template <class T>TriNode<T>* TriBin ary

12、Tree<T>:copy(TriNode<T> *p)TriNode<T> *q=NULL;if (p!=NULL)q = new TriNode<T>(p->data);q->left = copy(p->left);q->right = copy(p->right);return q;上述函数中存在什么错误？如何改正？四. 程序设计题（14分，每小题7分）1.在带头结点的单链表类 HSLi nkedList中，增加以下成员函数:void HSLi nkedList<T>:removeAII(HSLi

13、nkedList<T> & list)匹配的子表删除所有与list2.求二叉树中指定结点的层次。一. 填空题（26分，每空2分）1.使数据类型的定义和实现分离，使一种定义有多种实现。pj pi pj pj p* p-p； p p；第1次匹配 E 旳,比曲次，renl-oh ttarget 出at* t?betpa. babGahabcH.patternp> 典 p 阴 H P， 卩产 氏(b)第2次匹酣 ti=pji *tpp 比较欽* nextH=-lfc b 加 hi 缸ti+target3lpattern a.po pi p? Pj p p p» p；

14、 fCW)第欠匹配，b=w -灯译F“比较?無Hext旬=2tfltlt:£t<t7ttotntl:tuaatlcb1bca8.bc3.ababcHIINIINIIMpatiEixia.bc讯abbcpipJtfpp*target第嗾匹酉h Wa，tr知比较以匹酉喊如与桎式串匹酉啲子串序号郑3. "abac"4. ABCDEF+*G/-H+*+IJ+K*-5. 366. 11487. 78. 右单支二叉树(包括空二叉树、只有根结点的二叉树)9. 51110. n*(n-1)/211.(-i) -(1 2 2 4 3 3 4) 29 n 1012. 41*41

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

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

17、单元可以重复使用，如果数组容量不够，则是数据溢出，而不是假溢出。136Huffman 编码A: 111B: 11011C: 100D: 11010E: 1100F: 01G: 00H: 101(5)data adjlink0 12 3ABCo12A3037 8 01 18122H63O18226 3 063仃5 7E OF50 1234 5 6F13162010，代价是45D(b)最小生成树，代价为45ASL成功1存1 9 2 4)(8)9317564276152519II11131542*257817564293I1191542*1756257842931517192542*4256?893

18、羌逐孚序列曲屁二4矗加二2盅加=1希尔排序算法是不稳定的，因为与距离较远的元素进行比较，不能保证排序稳定性。希尔排序算法仅适用于顺序存储结构，因为与距离较远的元素进行比较，需要利用随机存储特性。(a)最大堆58,47,31,29,10,12,25,18,26(b)最小堆10,18,12,26,58,25,31,29,47三. 程序阅读题(15分，每小题5分)1. 将list链表合并连接到当前链表最后，设置list链表为空source : (a, b, c, d, e, f, x, y, z)list :()2. 运行结果为"abcdefxyz e f xyz ”，正确的运行结果是&q

19、uot;abcdefxyz ”。trim()函数首先寻找串的第一个空格字符，用i记住空格字符下标；再遍历串，将串中的非空格字符(用j记住其下标)逐个向前移动到空格字符位置(i下标)；算法存在错误，删除后没将字符串结束符0'向前移动到len处，导致cout输出仍然到'0'，如下图所示。宜hciir乂y色fXys痈1余空间使用空间0 krr-1 lenleu-1deimnt(旬剧陥前钾r串，表示仝搐字秤下柿，j窃示非空+s字序下标改正：函数体最后增加以下一句:eleme ntle n = '0：3.深拷贝创建二叉树时，没有为各结点建立指向父母结点的链。改正如下:当T

20、riNode构造函数不指定 pare nt时template <class T>TriNode<T>* TriBin aryTree<T>:copy(TriNode<T> *p)TriNode<T> *q=NULL;if (p!=NULL) q = new TriNode<T>(p->data); parent 为空q->left = copy(p->left);if (q->left!=NULL)q->left->pare nt = q; q_>right = copy(p_&g

21、t;right); if (q->right!=NULL) q->right->pare nt = q;return q;/创建结点，父母结点/复制左子树，递归调用/为左孩子设置pare nt链/复制右子树，递归调用/为右孩子设置pare nt链/返回建立子树的根结点 如果TriNode类声明以下构造函数，参数包括指定父母结点：TriNode(T data, TriNode<T>*pare nt=NULL,TriNode<T> *left=NULL,TriNode<T> *right=NULL)则TriNode类深拷贝构造函数可实现如下：t

22、emplate <class T>TriBinaryTree<T>:TriBinaryTree(TriBinaryTree<T> &bitree)/ 拷贝构造函数， 深拷贝 this->root = copy(bitree.root, NULL, 1);/复制以p为根的子二叉树，parent指向p的父母结点，返回新建子树的根结点template <class T>TriNode<T>* TriBi naryTree<T>:copy(TriNode<T> *p, TriNode<T>Tr

23、iNode<T> *q=NULL;if (p!=NULL) q = new TriNode<T>(p->data, pare nt);结点是pare ntq->left = copy(p->left, p);用q->right = copy(p->right, p);用return q;结点pare nt)/创建结点，父母/复制左子树，递归调/复制右子树，递归调/返回建立子树的根四.程序设计题（14分，每小题7分）/ 一次匹配p=p->n ext;q=q_>n ext;if (q!=NULL)一次匹配fron t=start;s

24、tart=start- >n ext;else子表q=list.head->n ext;while (q!=NULL)/ 一次匹配失败，再进行下/ 一次匹配成功，删除一个/删除从start开始与list以下给出参考程序，阅卷老师可根据实际情况评分，重点是表达算法思想。1.在带头结点的单链表类HSLinkedList中，增加以下成员函数，删除所有与list匹配的子表。template <class T>void HSLinkedList<T>:removeAII(HSLinkedList<T> &list) Node<T> *s

25、tart=head->n ext, *fr on t=head;while (start!=NULL) Node<T> *p=start, *q=list.head->n ext;while (p!=NULL && q!=NULL && p->data=q->data)匹配的子表II删除start结点template <class T>int Bi naryTree<T>:getLevel(T x)/返回x结点所在的层次/若空树或未查找到x返回-1if (root=NULL)return -1;retu

26、r n getLevel(root, 1, x);template <class T>/令根结点的层次为1int Bin aryTree<T>:getLevel(B in aryNode<T> *p, int i, T x)front->n ext = start- >n ext;delete start;start=fro nt->n ext;q=q_>n ext;2. 求二叉树中指定结点的层次。一棵二叉树中结点所在的层次定义：令根结点的层次为1 ,其他结点的层次是其父母结点的层次加1。在二叉链表存储的二叉树类BinaryTree中

27、增加成员函数如下：所在层次/在以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;retur n getLevel(p->right, i+1, x);找return -1;/查找成功/在左子树查找/继续在右子树中查/查找不成功在二叉链表结点类BinaryNode中增加表示结点层次的成员变量level，结点构造函数声明如下:Bin aryNode(T data, Bin aryNode<

28、;T> *left=NULL, Bin aryNode<T> *right=NULL,in t level=0)构造二叉树时设置每个结点的层次属性。例如，二叉树类Bin aryTree的一种构造函数声明如下：/以标明空子树的先根序列构造template <class T>Bi naryTree<T>:Bi naryTree(T prelist, i nt n)一棵二叉树 int i=0;root=create(prelist, n, i, NULL, 1);/ 根结点的层次为 1/以标明空子树的先根次序遍历序列创建一棵子树，该子树根结点是prelisti,/