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

1、数据结构09一. 填空题(26分，每空2分)1. 声明抽彖数据类型的目的是O2. 已知结点类Node<T>有data和next域，下列数据存储结构声明分别为uiblc«hUi nextI I H I A Itable daio 肚匕和I +T I人|3. 己知SStringsl(“aababbabac)s2化b);，执行下列语句后，si字符串是。(0,1),S2);(0,2)；4. 中缀表达式A+B*(C-D*(E+F)/G+H)-(I+J)*K的后缀表达式为°5. 设一个顺序循环队列容量为60,当front=47, rear=23时，该队列有个元素。6. 已知

2、二维数组a108采用行主序存储，数组首地址是1000,每个元素占用4字节，则数组元素a的存储地址是7. 已知一棵完全二叉树的根(第0个)结点层次为1,则第100个结点的层次为。8. 中根遍历序列和后根遍历序列相反的二叉树是。9. 由256个权值构造一棵哈夫曼树，则该二叉树共有结点。10. 由n个顶点组成的无向连通图，最多可以有条边。11. 10个元素的排序数据序列采用折半查找的平均查找长度是(写出算式)12. 已知关键字序列为67,41,34,10,69,24,78,54,41*,采用快速排序算法按升序排序，以第 一个元素为基准值，其第一趟排序后的关键字序列为。二. 问答题(45分，每小题5分

3、)1. 已知目标串为"aabcbabcaabcaababc",模式串为"abcaababc",写出模式串改进的next数 组；画出KMP算法的匹配过程，给出字符比较次数。2. 什么是栈和队列？两者有何异同？什么情况卞需要使用栈或队列？采用顺序存储结构 的栈和队列，在进行插入、删除操作时需要移动数据元素吗？为什么？什么是队列的假溢 出？为什么顺序存储结构队列会出现假溢出？怎样解决队列的假溢出问题？链式存储结构 队列会出现假溢出吗？顺序存储结构的栈会出现假溢出吗？为什么？3. 已知一棵二叉树中根次序遍历序列为GCBHKAMFDJE ,后根次序遍历序列为 CB

4、GHMAJEDFK,画出这棵二叉树并进行中序线索化。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%ll,画出采

5、用链地址法构造的散列表，计算（写出算式）。8. 画出对关键字序列93,17,56,42,78,15,42*,25,19进行希尔排序（升序）的每一趟排序过程, 说明希尔排序算法的稳定性并解释原因，以及希尔排序适用于什么存储结构。9. 将关键字序列29,10,25,26,58,12,31,18,47用筛选法分别建成一个最人堆和一个最小堆， 写出两个堆序列并画出其对应的完全二叉树。三. 程序阅读和改错题(15分，每小题5分)1. 阅读以下函数，回答问题。template <class T>void CirHDoublyLinkedList<T>:concat(CirHDoub

6、lyLinkedList<T> &ist)DLinkNode<T> *rear=head->prev;rear->next = >n ext;>n ext->prev = rear;rear=>prev;rear->next = this->head;this->head->prev = rear;>prev =;>n ext =;上述函数功能是什么？以下调用语句的运行结果是什么？CirHDoublyLinkedList<char> source("abcdef&quo

7、t;,6), list("xyz",3);(list);cout«Hsource： ,«source«,list： H«list;2. 下列trim()函数欲删除当前字符串对彖中的所有空格字符。void SString:trim()已知三叉链表表示的二叉树结点类TriNode声明如下：template <class T>class TriNode程序设计题(14分，每小题7分)1. 在带头结点的单链表类HSLinkedList中，增加以下成员函数：void HSLinkedList<T>:removeAll(H

8、SLinkedList<T> &list)求二叉树中指定结点的层次。一.填空题(26分，每空2分)1. 使数据类型的定义和实现分离，使一种定义有多种实现。2. Node<T>*table4; Node<T> table4;target a3.45.6.7.8.9.10.11.12. 1.t；tatTho tilt”tnh XtargelaabcbabcaabcaababciiUjattemabcaababc代P：P*P，®第1次匹酣t0=p),屯 如 比较2次，rextl=Ob 切 tn ti? tu tn t/ b. ti7 a| Il

9、II Hpattern臼 pi S 由 陆 P 庄 p 曲第2次匹酉“匕=阿，仔Pp比较软，nextra1aabcbabcaabcaababciiiiiiiiiiii%,patternabcaababcppip?p；ppp.ppc(c)第3次匹削，t，岛，血却，比较7次，iwxt问2hti屯t)btt?teip切tnh：tut“ t/t“ti7aacbabcabcaabciiiiiiiiiiiiiifatterribcaababct，t.targeitaigeih 1 tho til h? ki h* m t1(i t17?o pi F? Pi pi p- p. p-(d)第4次匹配，t1L=

10、PM，n-pc，比较?次，匹酉减功，与槿式串匹酉啲子串序号为9"abac"ABCDEF+*G/-H+*+IJ+K*-3611487右单支二叉树(包拾空二叉树、只有根结点的二叉树)511n*(n-l)/2“ 1 1g(-xz) = -(l + 2x2 + 4x3 + 3x4) = 2.941* 4134 10 54 24 67 78 69问答题(45分，每小题5分)模式串"abcaababc11进的next数组为01234567模式串abCaababc“ PoPi - Pj-1 中最长相同的前后缀子串长度k00011212Pk与P）比较H改进的nextj100110

11、2002. 栈和队列都属于线性表结构，它们是两种特殊的线性表，栈的插入和删除操作都在线性 表的一端进行，所以栈的特点是“后进先出”；而队列的插入和删除操作分别在线性表的两 端进行，所以队列的特点是“先进先出”。深度优先搜索遍历算法需要使用栈作为辅助结构, 广度优先搜索遍历算法需要使用队列作为辅助结构。采用顺序存储结构的栈和队列，在进行 插入、删除操作时不需要移动数据元素，因为栈和队列均不能进行中间插入、删除操作。 顺序队列，当入队的元素个数（包括已出队元素）超过数组容量时，队列尾卞标越界，数据 溢出。此时，由于之前已有若干元素出队，数组前部已空出许多存储单元，所以，这种溢出 并不是因存储空间不

12、够而产生的，称之为假溢出。顺序队列之所以会产生假溢出现象，是因 为顺序队列的存储单元没有重复使用机制。解决的办法是将顺序队列设计成循坏结构。链式存储结构队列不会出现假溢出。因为每次元素入队，都要申请新结点，数据不会溢出。 顺序存储结构的栈不会出现假溢出。因为顺序栈的存储单元可以重复使用，如果数组容屋不 够，则是数据溢出，而不是假溢出。Huffman 编码A： 111B： 11011C： 100D： 11010E： 1100F： 01G： 00H： 101(5) A01231oOssoOB120oOoOaCaCoOC31oO0oOaCaCoOEoOoOoO0527oOFoOoOoO506317G

13、oOoOoO2763018H_oOoOoOoO17180代价是45ASQ功二右(Ix9 + 2x4) =哎功(a)最大堆58,47,31,29,10,12,25,18,26(b)最小堆10,18,12,26,58,25,31,29,470123456789317564278154翠251911119154才25781756429319151756257842931517192542+42567893希尔排序算法是不稳定的，因为与距离较远的元素进行比较，不能保证排序稳定性。希尔排 序算法仅适用于顺序存储结构，因为与距离较远的元素进行比较，需要利用随机存储特性。三.程序阅读题(15分，每小题5分)

14、1. 将list链表合并连接到当前链表最后，设置list链表为空source： (a, b, c, d, e, £ x, y, z)list：()2. 运行结果为“abcdefxyz e fxyz",正确的运行结果是“abcdefxyz”。® trim()函数首先寻找串的第一个空格字符，用i记住空格字符卞标；再遍历串，将串中的 非空格字符(用j记住其下标)逐个向前移动到空格字符位置(i卜标)：算法存在错误，删 除后没将字符串结束符VT向前移动到len处，导致cout输出仍然到、0第如下图所示。elementAbCdefX7z別除前字持豺俵示空格字符下桁1 j友示非

15、空格字符下椅abcdfXyzfyzV2便用空问demgiitkir-1 lenlen(b)删除后串 改正：函数体最后增加以下一句: elementlenl =、0；3. 深拷贝创建二叉树时，没有为各结点建立指向父母结点的链。改正如下： 当TriNode构造函数不指定parent时 template <class T>TriNode<T>* TriBinaryTree<T>:copy(TriNode<T> *p)TriNode<T> *q=NULL;if (p!=NULL) q = newTriNode<T>(p->d

16、ata);程序设计题(14 分，每小题 7 分)以下给出参考程序，阅卷老师可根据实际情况评分，重点是表达算法思想。1.在带头结点的单链表类HSLinkedList中，增加以下成员函数，删除所有与list匹配的 子表。template <class T>void HSLinkedList<T>:removeAII(HSLinkedList<T> &list) Node<T> *start=head->next/ *front=head;while (start!=NULL) Node<T> *p=start, *q=>

17、;next;while (p!=NULL && q!=NULL && p->data=q->data)求二叉树中指定结点的层次。一棵二叉树中结点所在的层次定义：令根结点的层次为1,其他结点的层次是其父母结 点的层次加lo 在二叉链表存储的二叉树类BinaryTree中增加成员函数如下：template <class T>int BinaryTree<T>:getLevel(T x)返回 x 结点所在的层次若空树或未查找到X返回-1if (root=NULL)return -1;return getLevel(root, 1,

18、x);令根结点的层次为 1template <class T>int BinaryTree<T>:getLevel(BinaryNode<T> *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!=-l) return level;return getLevel(p->right, i+1, x);

19、return -1; 在二叉链表结点类BinaryNode中增加表示结点层次的成员变量level,结点构造函数 声明如下：BinaryNode(T data, BinaryNode<T> *left=NULL, BinaryNode<T> *right=NULL, int level=0) 构造二叉树时设置每个结点的层次属性。例如，二叉树类BinaryTree的一种构造函数声 明如下：template <class T>BinaryTree<T>:BinaryTree仃prelist, int n) 以标明空子树的先根序列构造一棵二 叉树 int

20、 i=0;root=create(prelist/ n, i, NULL, 1);根结点的层次为 1以标明空子树的先根次序遍历序列创建一棵子树，该子树根结点是prelisti, 根结点层次是level,其父母结点由parent指向，返回创建子树的根结点指针 template <class T>BinaryNode<T>* BinaryTree<T>:create(T prelist, int n, int &iz int level) BinaryNode<T> *p=NULL;if (i<n) T elem = prelisti+;讦(elem!=NULL) p = new Binar