数据结构包数据答案

1、2015-2019 数据结构做建议从 2019 年往前做，越是近期的越有参考价值！说明：简答题中略掉的，参考“数据结构名词解释详细版.docx”即可，这些都是属于概念性的知识。时间复杂度相关可以参考“时间复杂度计算方法.doc”。配套：天勤或王道数据结构（首推天勤的数据结构高分笔记），配套考纲学习即可，的串，数组广义表和矩阵这两章不用看。由于历经 10 年学校数据结构专业课有 843 和 855 两种版本，主要题型都差不多，程序题用c 语言或者 c+实现皆可，数据结构这门课主要考验的是考生的算法思维能力。2015 年招生试题一、简答题1. 略。2.1则栈底为 5 栈顶为 2。2则队头为 5，队

2、尾为 93. 检查串是否为回文：直接从和从右读比较即可。近几年串的知识点不在考纲范围，不用看！4.算法步骤：待位置ps->next=p;s->prior=p->prior;s->prior->next=s;p->prior=s;5.左边是 3 个结点的树，右边是二叉树，二叉树区分左右分支6.二叉树：后序序列：A-C-D-B-G-J-K-I-H-F-E层次遍历：E-B-F-A-D-H-C-G-I-K-J7.如上图构建了中序线索二叉树，红色代表中序线索1x 左右子树都，有其前序后继为2x 只有树,其前序后继为x 只有右子树,其前序后继为右孩子34x 为叶子节点，

3、其前序后继为其中序后继结点的右孩子，如果没有右孩子，则继续查找下一个中序后继结点的右孩子，都没有则为空8.先按频率升序排序：2,3,6,7,10,19,21,32构建树：A(7)对应编码：1010B(19)对应编码:00C(2)对应编码:10000D(6)对应编码:1001 E(32)对应编码:11 F(3)对应编码:10001G(21)对应编码:01H(10)对应编码:1011WPL=7*4+19*2+2*5+6*4+32*2+3*5+21*2+10*4=2619.线性探测法构建表10.1基数排序：类似 2018 年综合题第一题第一趟基数排序：503104897012345678910111

4、213141516Ap rAu gSe qDe cFe bJa nJu nJu lMa rMa yOc tNo v输出结果：第一趟：512，503，503,104,104,275,426,087,897,908第二趟基数排序：输出结果：第二趟：503,503，104，104,908,512,426,275,087,897第三趟基数排序：输出结果：第三趟：087,104,104,275,426,503,503,512,897，9082快速排序：第一趟：(<=在左，>在右)426,087,104,104,503，275,503,897,908,512第二趟：426 和 897 作为标志

5、275,087,104,104,426， 503，503， 512,897,908512104503087104275426503897908012345678990810410450342650351227508789701234567895125031042754260879080123456789第三趟：275，512 作为标志104,087，104,275, 426,503，503,512,897,908第四趟：104,897 作为标志087,104,104,275,426,503,503,512,897,908二、程序题1.结构：12单链表结构定义：typedef struct Ln

6、odeint data;sturct Lnode *next;Lnode;3intIsUP(Lnode *a)/是否为递增(返回 1 表示递增)if(a=NULL) return 0;Lnode *b=a; int flag=1;/flag 为 1 表示递增if(b->next=NULL) reurn1;/只有一个元素，认为是递增while (b->next!=NULL)数据域指针域->数据域指针域if(b->next->data<b->data)flag=0;break;/一旦发现后一个比前一个小则不是递增的b=b->next;return f

7、lag;2. 可利用快速排序执行一趟把比小的元素放在左边，比大的元素放在右边的特点，这是对快速排序的经典运用！void QuickSort(int R,int temp,int low,int high)/本题 n 个数据在数组 R 中,temp 初始为 2,high 初始为 n-1,low 初始为 0执行第一趟排序先将比 2 小的 1 都放到 2 前面去，第 2 趟将比 3 小的2 都放到中间int i=low,j=high; int first=0;while(i<j) /从左往右找到第一个 2 或者 3 的位置，然后第一趟排序用 2 来比较if(Ri=3|Ri=2) first=R

8、i;break;+i;if(i<j)while(i<j)while(j>i&&Rj>=temp)-j;/从右向左找到第一个 1if(i<j)Ri=Rj;+i;/把 1 换到左边while(j>i&&Rj<temp)+i;/从左往右找到 2 或者 3if(i<j)Rj=Ri; -j;/把 2 或者 3 换到右边/第一趟结束序列变为：111111123232（左边都是 1，右边 2,3 乱序）Ri=first;temp=first;/temp 置为函数开头找到的 2 或者 3j=high; /j 重置为highwhil

9、e(i<j)while(j>i&&Rj>=3)-j;/从右向左找到第一个 2if(i<j)Ri=Rj;+i;/把 2 换到左边while(j>i&&Rj<3)+i;/从左往右找到 3if(i<j)Rj=Ri; -j;/把 3 换到右边/第二趟结束序列变为：123 有序Ri=temp;/相当于两趟快速排序3.1typedef struct studentint num;/学号int grade; /成绩student;2void downOut(student s,int n)/对s 按成绩降序输出/这里只要在选择类排序过

10、程中输出即可int i,j,k; int temp;for(i=0;i<n;+i)k=i;for(j=i+1;j<n;+j)if(sk>sj)/找到最大k=j;cout<<”学号：”+sk.num+”成绩：”+sk.grade<<endl;temp=si;si=sk;sk=temp;2016 年招生试题一、简答题1. 略。2. 略。3.(1) p->next!=NULL(2)p->next=p->next->next;4.实现功能：(1)当x 大于 100 时输出x-10，否则利用递归计算输出 91（这个函数其实叫91 函数）(

11、2)将栈 S 中的数据逆序存入数组a 中，然后再存入栈 S 中，相当于将栈S 中的数据逆序。5.类似 2017 年综合题第三题：(1)后序序列中最后一个结点为根结点，到中序序列中查找可得左右子树。本题中后序序列根结点为 a，则树的中序序列为 c，b,d,e 后序序列为 c,e,d,b，右子树中序序列为 g,i,h,j,f,后序序列为i,j,h,g,f。(2)深度：5(3)度为 2 的节点数：3，度为 1 的节点数：3，度为 0 的节点数：41. 略。2. 根据出现频率构建树(1)先升序排序：1,3,5,9,16,30具体方法参见 2019 年综合题第三题（2） 带权路径长度WPL=30*1+1

12、6*2+9*3+5*4+1*5+3*5=1298.(1)邻接表：(2)V2 出发深度遍历序列：v2->v1->v5->v4->v6->v39.(1)链地址法：所有同义词用单链表连接(2)查找的ASL：（1+1+1+1+2+1+1+2+1+1+2+1）/12=15/12=1.2510.快速排序过程：从右向左扫描然后从左往右第一趟：小于 50 的在左：45,10,40,50,50,85,80第二趟分别对 50 左边和右边进行快速排序：40,10,45,50，50,85,80第三趟分别对 45 左边，50 右边快速排序：0123456789101112270887310

13、25704763V1->v2->v5V2->v1->v3->v6V3->v2->v6V4->v5->v6V5->v1->v4->v6V6->v2->v3->v4->v510,40，45，50，50，80,85排序完成二、程序题1.同 2017 年最后一题！2.(1)假设该算数运算符以中序遍历的顺序在二叉树中，其父亲结点为运算符，孩子结点为数字。例如：(a-(b+c)*(d/e)在下图中，则先计算树表的值，再计算右子树表的值最后相乘得到结果。(符合先树再右子树最后根节点的后序遍历思想,则套用后序遍历模

14、板)(2)int comp(BTnode *p)int A,B;if(p!=NULL)if(p->lchild!=NULL&&p->rchild!=NULL)A=comp(p->lchild); /后序遍历求树的值B=comp(->rchild);/后序遍历树的值return op(A,B,p->data);else return p->data-0; /结点类型为字符类型，如果该字符为数字的话，-0可以转换为整型数字else retun 0;int op(int A,int B,char op)/根据op 运算符计算A，Bif(op=+)r

15、eturnA+B;if(op=-)returnA-B;if(op=*)returnA*B;if(op=/&&B!=0) return A/B;3.结构(即顺序表的结构)：typedef structint datamaxsize;int length;Sqlist;直接排序：void insertSort(Sqlist R)int i,j;int temp;for(i=1;i<R.length;+i)temp=R.datai;/待关键字存在temp 中j=i-1;while(j>=0&&temp<R.dataj)/从关键字位置向前扫描，如果大于

16、关键字则后移一位R.dataj+1=R.dataj;-j;R.dataj+1=temp;2017 年招生试题一、简答题3. 略。4. 略。5. 略。6. 类似 2018 年简答题第 3 题。利用二叉树的数学性质;n0+n1+n2-1=2*n2+1*n1(即总节点数-1=总分分支数)化简为n0-1=n2（2）n0 为叶子节点（0 分支），n1 为单分支节点，n2 为双分支节点，本题中n1 个数为 0，非叶子节点个数即为双分支结点个数。则式子（2）可证。7. 略。二、程序阅读题1.(1)函数功能：升序冒泡排序(2)数组v 的变化情况：第一趟： 2,4,3,9第二趟：2,3,4,9第三趟：2,3,4

17、,9第四趟：2,3,4,92.(1)函数功能：将 num 转换为b 进制（b<=16）的数字，并且按照该数字从低位到每位对应的 10 进制的值从字符串中取值存入栈中，最后利用栈的先入后出实现从到低位的输出，即输出流num 的b 进制转换结果。(2)Fun（300,16）即按 300 的 16 进制：12C 取值位置为 12,2，1，即返回numStr 为：”12C”；此时相当于计算了 300 的 16 进制值并输出。其中stk 栈在第一个循环依次存入了C，2,1在第二个循环依次出栈，出栈顺序为：1，2，C3.(1)实现功能：使用栈的中序非递归遍历二叉树，计算叶子节点个数。2018 年的第

18、二题是逆中序(2)代码（2）root 数据域值：即为出栈顺序（中序遍历二叉树顺序），B，G，D，A，E，H，C，F三、综合题1.(1)后缀表：62/7942*5-+*-。(2)处 理字符符号栈当前表结果注释66/62/62-62/出栈，-入栈2018,2019 年都考到了同题型题目!2.AVL 树即平衡二叉树类似 2018 年综合题的第四题7-62/7*-*62/7(-*(62/79-*(62/79+-*(+62/794-*(+62/794*-*(+*62/7942-*(+*62/7942-*(-62/7942*+*+出栈，-入栈5-*(-62/7942*+5)-*62/7942*+5-()匹

19、配，-出栈62/7942*+5-*-全部出栈3.根据前序序列和中序序列确定二叉树过程：1前序序列的第一个节点为根节点，找到中序序列中相同节点。中序序列根结点左边的为树的中序序列，右边为右子树的中序序列；在上步骤基础上找到左右子树的先序和中序序列，并重复 1-22步骤的操作。本题中：原二叉树先序序列根结点为 A，到中序序列中可得树中序序列为DGB，右子树中序序列为 HEICF，其树对应先序序列为BDG，右子树对应先序序列为 CEHIF，则 B，C 分别为左右子树的根结点。依此逻辑可得：其后序遍历序列为：G-D-B-H-I-E-F-C-A。4.(1)（从 0 开始）深度优先搜索遍历序列：0-1-2

20、-3-4广度优先搜索遍历序列：0-1-2-4-3(2)Dijkstra 算法：同 2018 年综合题第五题！一毛一样（皿）（）四、程序设计题1.void findSame(Lnode *a,Lnode *b)/在单向链表a 和b 中查找相同元素结点，并输出Lnode *p=a,*q；while(p->next!=NULL)q=b;while（q->next！=NULL）if(q->next->data=p->next->data)cout<<q->next->data;->next;p=p->next;2.大根堆的：即到完

21、全二叉树的最后位置然后向上调整void insert(int t,int n，int a) /在n 个结点的大根堆中元素 a,大根堆按完全二叉树的形式在数组中，下标从 1 开始方便计算t+n=a;/直接插到数组尾部/当总结点个数大于 1 向上调整int child=n;int father=child/2;/father 表示父亲节点while(n>1&&father>=1)if(tchild>tfather)tchild=tfather; /如果比父亲结点大就向上调整child=child/2;father=child/2；else break;if(fat

22、her>=1) tfather=a; /调整到最终位置3.有序链表合并：(假设为非递减的两个有序链表a，b，合并成新的非递减有序链表c)void merge(Lnode *a,Lnode *b.Lnode *&c)Lnode *p=a->next;Lnode *q=b->next;Lnode *r;/用p 来跟踪a 的最小值结点，q 来跟踪b 的最小值结点c=a;c->next=NULL;free(b);r=c; /r 始终指向c 的终端结点while(p!=NULL&&q!=NULL)if(p->data<=q->data)/

23、（尾插法）r->next=p;p=p->next;r=r->next;elser->next=q;->next;r=r->next;r->next=NULL;/如果链表有剩余则直接到c 尾部，因为原本都是有序的if(p!=NULL)r->next=p;if(q!=NULL)r->next=q;2018 年招生试题一、简答题1.略。2.栈与队列的相同点：都是输入或者输出受限的线性结构。12都可以通过顺序结构和链式结构实现。栈与队列的不同点：1删除数据元素的位置不同，栈的删除操作在栈顶进行，队列的删除操作在队头进行。栈先进后出，队列先进先出2a

24、0是栈底元素，因为栈底位置必须固定。3.利用二叉树的数学性质;n0+n1+n2-1=2*n2+1*n1(即总节点数-1=总分分支数)化简为n0-1=n2（2）n0 为叶子节点（0 分支），n1 为单分支节点，n2 为双分支节点，叶子节点空指针域个数为 2，单分支结点空指针域个数为 1。空指针域个数=2n0+n1节点个数=n0+n1+n2 将上式（2）代入得节点个数=2n0+n1 -14.即空指针域个数比节点数多一。时间复杂度：O(log2n)12时间复杂度：O( n )对于n->+ ，log2n< n则算法 1 更优。5.略。二、程序阅读题1.(1)函数功能：将数组a 循环右移k%

25、n 个(2)时间复杂度：O(n)单循环，基本操作次数为n(3)f(t,10,16)即把将数组t 循环右移 16%10 (6)个55,64,73,12,9,1,19,28,37,462.(1)函数功能：使用逆中序的非递归遍历来计算二叉树中非叶子结点的个数；(2)Root 的数据域即为遍历顺序：F,C,H,E,A,D,G,B(逆序 则为中序遍历序列，所以称之为逆中序)(3)返回值：5（A,B,C,D,E 是非叶子结点）3.那契数列：1,1,2,3,5,8,13,21。(1)代码一:用循环求解那契数列第num 项题目中f3=f2 写错应该是f2=f3出错概率是存在的，考场上遇到请冷静分析，不要慌,（

26、皿）（） 。代码二：递归求解那契数列第num 项(2)f1(5)输出 5; f2(6)输出 8(3)时间复杂度上 f1 为 O(n)，f2 为 O(2n),且递归使用系统栈，空间复杂度较高，所以代码一更好其中求解代码二的 F(n),必须先计算 F(n-1)和 F(n-2),计算 F(n-1)和F(n-2)，又必须先计算F(n-3)和F(n-4)。以此类推，直至必须先计算F(1)和F(0),然后逆推得到F(n-1)和F(n-2)的结果，从而得到 F(n)要计算很多重复的值，在时间上造成了很大的浪费，算法的时间复杂度随着 N 的增大呈现指数增长，时间的复杂度为O(2n)，即 2 的n 次方三、综合

27、题1. 该题使用基数排序思想第一趟基数排序：输出结果：第一趟：90,211,112,82,143,13,214,515,316,367第二趟基数排序：输出结果：第二趟：211,112,13,214,515,316,143,367,82,90第三趟基数排序：316515214013112211143367082090012345678909021108201321451531636711289输出结果：第三趟：13,82,90,112,143,211,214,316,367,515完整的输出结果即三趟输出基数排序:底部输出2.线性开地址散列：平均查找长度ASL1=(1+1+2+1+5+2+6+2

28、+1+1)/10=2.23.中缀表（a+b）/5-c*（3-d）+e）转后缀表：类似 2019 年综合题第四题处 理字符符号栈当前表结果注释(a(a+(+ab(+ab）ab+（）匹配,+号出栈88672358991234567891009008214321436701311221131651501234567894.空的平衡二叉树：以字母表为先后顺序，从小到大/ab+5/ab+5-ab+5/出栈-入栈c-ab+5/c*-*ab+5/c(-*(ab+5/c(-*(ab+5/c3-*(ab+5/c3-*(-ab+5/c3d-*(-ab+5/c3d)-*(ab+5/c3d-内层()匹配，-出栈+-*

29、(+ab+5/c3d-e-*(+ab+5/c3d-e)-*ab+5/c3d-e+()匹配，+出栈ab+5/c3d-e+*-*-出栈，转换结束5.(1)邻接矩阵：01234005321026(2)DijKstra 求 0 点到其余点最短路径：0 到 1 最短路径：0->2->1;0 到 2 最短路径：0->20 到 3 最短路径：0->2->3;0 到 4 最短路径：0->4四、程序设计题1.结点单项链表添加值到表尾：思路分析：先遍历到表尾指针再执行void Add2Last(Node* head,int item)Node *insert,*p=head;i

30、f(p->next=NULL)/链表为空，则待结点为第一个数据结点insert=new Node (item);/根据题目定义创建新结点已 并 入顶点剩 余 顶点Distpath0 1 2 340 1 2 3 4012340 5 3 2-1 0 0 -1 0041230 5 3 62-1 0 0 4 0042130 4 3 52-1 2 0 2 0042130 4 3 52-1 2 0 2 0042130 4 3 52-1 2 0 2 0210230461040head->next=insert；While(!p->next=NULL) p=p->next; /遍历到尾

31、部结点insert=new Node (item);p->next=insert；/到表尾2.大根堆删除堆顶元素：void deleteMax_HeapTop(int v,int high)/删除堆顶元素相当于大根堆排序的中间过程，删除后放到原数组尾部实现升序排序,大根堆是按完全二叉树的顺序在数组中的，假设从 1 下标开始（方便计算），1 下标为堆顶元素;high 表示要调整的下标范围（从 1 到high）v1=vhigh;/删除堆顶元素即将最后一个结点替换到堆顶并进行调整int temp=v1;int i=1；j=2*i；/将堆顶元素交换到表尾实现堆顶的删除和升序排序while（j&l

32、t;=high）if(j<high&&vj<vj+1)+j;/如果右孩子大，则把 j 指向右孩子，j 此时为 2i+1if(temp<vj)vi=vj;/将vj调整到双亲结点位置i=j;j=2*i+1;else break；/调整结束vj=temp;high-; /删除堆顶之后总长度减一3.类似 2019 年程序设计题第三题，可见重复率！(1)参见 2019 年程序设计题第三题(2)二叉查找树查找：BinNode* BST_find(BinNode* root,intitem)if(root=NULL)return NULL:elseif(root->k

33、ey=item) return root;else if(root->key>item)return BST_find( root->lchild,item);else return BST_find( root->rchild,item);2019 年招生试题一、简答题1. 略。2.根结点为 0 层，则最高 999 层，最矮则为完全二叉树 9 层，根据满二叉树的结点总数公式： 2n -1 （n 为总层数）可推算出。3. 略。4.写出一种即可：深度优先遍历：A->B->E->C->F->D(遍历结果存在多种可能，题目没给详细要求)；广度优先

34、遍历：A->B->C->D->E->F。5. 所谓的大O 表示法其实就是我们认识中的 O（n）这样的表示方法。程序功能：在含有 n 个元素的数组a 中循环查找target 元素，1查找则将数组下标赋值给pos，查找失败赋值为-1。时间复杂度：O（n）2程序功能：功能同上，但使用了折半查找法，效率更高。时间复杂度：O（log2n） 更优策略 2 不适合有序的单向链表，因为单向链表的查找只能从头到尾依次查找。（具体参见概念文档中顺序表和链表的区别）二、程序阅读题（30，每题 10）1.push_back() 实现在Vector 最后添加一个元素1函数 f 功能：vec

35、tor 是 c+中表示向量的数据类型。代码实现查找a 中出现b 中不出现的元素，并输出。2时间复杂度：函数基本操作是内层循环的 if，基本操作次数为a.size()*b.size()输出结果：28,37,55,64,73,9,1。32.1函数f 功能：递归的输出了树的逆先序遍历序列。先序：（根，左，右） 中序：（左，根，右） 后序：（左，右，根）逆先序即先输出右子树，然后树，最后根节点。2二叉树：即下图中的root。3先序：3-12-6-7-10-4-5-8-11则输出结果为逆先序：11-8-5-4-10-7-6-12-3。3.代码能：将十进制数字 num 转换为 16 进制数字，逆序存1整型

36、数组a 中，然后for 循环正序输出该 16 进制数字。代码二功能：使用递归的方法将 10 进制数字转换成 8 进制，并正序输出（因为递归中最内层的函数第一个输出，所以这里是正序）。2f1（100）：64F2（200）：310三、综合题（55）1.1使用线性开散列法，散列值：56:56%11=123：23%11=1->2（ 1 已经被占用） 88:88%11=045%11=1->3 （ 1,2 都被占用）99%11=0->4(0,1,2,3 被占用)7 ：7%11=774：74%11=836：36%11=3->5(3,4 被占用)43:43%11=10299 的查找长度

37、是5 (比较了 5 次)2.构建Huffman 树的方法。1(1)先按使用频率递增排序：7，10,12,12,18,20,21(2)取出序列中最小两个值：a,b，构建新的节点a+b，从列删去a,b，将a+b列。(3)循环执行（2）的操作直到结束。2字符对应编码： (规则：从根节点开始向左为 0，向右为 1)A：100B:00Q:1100K:01T:101J:111U:11013长度：20*2+21*2+12*3+12*3+7*4+10*4+18*3=2763.新的查找树：即为 50 的右孩子12平衡因子：树高度-右子树高度先找到最小不平衡子树（红框部分）再调整：（上图3右）4.中缀转后缀：处

38、理字符符号栈当前表结果注释aa*a25.1邻接表：A->B->C->EB->D->E->FC空 ，C 出度为 0D->G(*(ab*(ab-*(-abc*(ab-出栈)*abc-()括号匹配/abc-*出栈(/(abc-*d/(abc-*d+/(+abc-*de/(+abc-*de*/(+*abc-*def/(+*abc-*def)/abc-*def*+()匹配，（右边的出栈*abc-*def*+/出栈h*abc-*def*+/habc-*def*+/h* 结果*出栈，2Dijkstra 算法（最短路径）：最短路径：A 到B:A->BA 到C：A

39、->B->E->CA 到D：A->B->DA 到E：A->B->EA 到F：A->B->E->FA 到G：A->B->E->G四、程序设计题（35）1.Void DeleteKeys(node* first,int key)/删除链表中所有重复的key 值,假设为节点的链表，严谨地说如果不重复则不可以删除例如：1,2,3,4 DeleteKeys（first，1）就删除任何节点已 并 入顶点剩 余 顶点DistpathABCDEFGABCDEFGABCDEFG0 11 15 26 -1 A A -1 A -1 -1A

40、BCDEFG0 11 15 23 13 34 -1 A A B B B -1ABECDFG0 11 14 23 13 18 16-1 A E B B E EABECDFG0 11 14 23 13 18 16-1 A E B B E EABECGDF0 11 14 23 13 18 16-1 A E B B E EABECGFD0 11 14 23 13 18 16-1 A E B B E EABECGFD0 11 14 23 13 18 16-1 A E B B E EE->C->D->F->GF->C->GG空 ，G 出度为 0node*p=first;node*q;node*re;/第一次遇见 key 值的节点的前一个节点，如果后面第二次遇见key 值，说明是重复的节点，那么全部删除int num