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

《南京工程的学院大数据结构样卷09级加详解.docx》由会员分享，可在线阅读，更多相关《南京工程的学院大数据结构样卷09级加详解.docx（23页珍藏版）》请在三一办公上搜索。

1、数据结构09一.填空题(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采用行

2、主序存储，数组首地址是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. 已知目标串为a

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

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. 画出对关键字序列9

5、3,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 =

6、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()函数欲

7、删除当前字符串对象中的所有空格字符。void SString:trim()删除串对象中的所有空格字符( int i=0;i+;/i记住第1个空格下标寻找第1个空格while (elementi! = & elementi! = 0)for (int j = i; element。!=0; j+)if (elementj! = )elementi + = element。;非空格字符向前移动到空格字符位置len = i; 对于以下调用语句，运行结果是什么？正确的运行结果是什么？SString str( a bc d e f xyz);str.trim();coutstr=”strendl; tr

8、im()函数怎样实现所求功能？算法存在什么错误？ 如何改正？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;

9、三叉链表表示的二叉树类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为根的子二叉树，返回新建子树的根

10、结点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中，增加以下成员函数：删除所有与listvoid HSLinkedList:removeAll(HSLinkedList &list)匹配的子表2.求二叉树中指

11、定结点的层次。一.填空题（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. 11Z ( Xi) =(1+2X2+4X3+3x4) = 2.9nTOi=i12. 41* 41 34 10 54 24 67 78 69二 问答题（45分，每小题5分）1.模式串”abcaababc”改进的next数组为j012345678模式串a

12、bcaababcp0P1A七-1 ”中最长相同的前后缀子串长度k-100011212pk与，比较/改进的nextj-100-1102002.栈和队列都属于线性表结构，它们是两种特殊的线性表，栈的插入和删除操作都在线性 表的一端进行，所以栈的特点是后进先出，而队列的插入和删除操作分别在线性表的两 端进行，所以队列的特点是先进先出。深度优先搜索遍历算法需要使用栈作为辅助结构， 广度优先搜索遍历算法需要使用队列作为辅助结构。采用顺序存储结构的栈和队列，在进行 插入、删除操作时不需要移动数据元素，因为栈和队列均不能进行中间插入、删除操作。顺序队列，当入队的元素个数（包括已出队元素）超过数组容量时，队列

13、尾下标越界，数据 溢出。此时，由于之前已有若干元素出队，数组前部已空出许多存储单元，所以，这种溢出 并不是因存储空间不够而产生的，称之为假溢出。顺序队列之所以会产生假溢出现象，是因 为顺序队列的存储单元没有重复使用机制。解决的办法是将顺序队列设计成循环结构。链式存储结构队列不会出现假溢出。因为每次元素入队，都要申请新结点，数据不会溢出。 顺序存储结构的栈不会出现假溢出。因为顺序栈的存储单元可以重复使用，如果数组容量不 够，则是数据溢出，而不是假溢出。Huffman 编码A： 111B： 11011C： 100D： 11010E： 1100F： 01G： 00H：101data adjlink-

14、A-012318888BBE1212088888C31a80858638188Es招805278F88C85170H317Gs882763018H888817180 _01234560 A1 B2 C3 E4 F5 G6 H131610(b)最小生成树，代价为45图G3ASL成功13希尔排序算法是不稳定的，因为与距离较远的元素进行比较，不能保证排序稳定性。希尔排 序算法仅适用于顺序存储结构，因为与距离较远的元素进行比较，需要利用随机存储特性。（9）(a)最大堆58,47,31,29,10,12,25,18,26(b)最小堆10,18,12,26,58,25,31,29,47三 程序阅读题（15

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，如下图所示。1司州降前字苻串.f表示空格字苻下标，J表示非空格字符下标便用空间嗣彖空间0改正：函数体最后增

16、加以下一句： 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(

17、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

18、 = copy(bitree.root, NULL, 1);/复制以p为根的子二叉树，parent指向p的父母结点，返回新建子树的根结点template TriNode* TriBinaryTree:copy(TriNode TriNode *q = NULL;if (p! = NULL) q = new TriNode(p-data, parent);结点是parentq-left = copy(p-left, p);用q-right = copy(p-right, p);用return q;结点*p, TriNode *parent)创建结点，父母复制左子树，递归调复制右子树，递归调返回建

19、立子树的根四 程序设计题（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-d

20、ata)一次匹配( p=p-next;q=q-next;if (q! = NULL)一次匹配( front=start;start二start-next;else子表( q = list.head-next;while (q! = NULL)匹配的子表/一次匹配失败，再进行下/一次匹配成功，删除一个/删除从start开始与list删除start结点( front-next = start-next;delete start;start二front-next;q=q-next;2.求二叉树中指定结点的层次。一棵二叉树中结点所在的层次定义：令根结点的层次为1，其他结点的层次是其父母结 点的层次加1

21、。在二叉链表存储的二叉树类BinaryTree中增加成员函数如下：template /返回x结点所在的层次/若空树或未查找到x返回-1/令根结点的层次为1int BinaryTree:getLevel(T x)if (root= = NULL)return -1;return getLevel(root, 1, x);template int BinaryTree:getLevel(BinaryNode *p, int i, T x)(在以p结点(层次为i)为根的子树中求x结点所在层次if (p!二NULL)( if (p-data = =x)return i;查找成功int level =

22、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的一种构造函数 声明如下：temp

23、late 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

24、)( T elem = prelisti+;if (elem! = NULL)( p = new BinaryNode(elem, NULL, NULL, level); 创建结点，层 次是levelp-left = create(prelist, n, i, level + 1);创建左子树p-right = create(prelist, n, i, level + 1);创建右子树return p;BinaryTree类的getLevel(p)成员函数声明如下，算法同查找。template int BinaryTree:getLevel(T x)/返回值为x结点所在的层次,若空树或未查找

25、到乂返回-1( BinaryNode *find二search(x);查找if (find = = NULL)return -1;return find-level;在二叉树中插入一个结点时，以插入结点为根的子树中所有结点的层次也随之改变，因 此，BinaryTree类需要提供以下setLevel()方法动态维护层次属性。/设置以p结点(层次为level)为根的子树中所有结点的层次template void BinaryTree:setLevel(BinaryNode *p, int level)if (p! = NULL)( p-level = level;setLevel(p-left, level + 1);setLevel(p-right, level + 1);