数据结构初试复试真题-南邮上课

考试题型考试题型一、填空题二、选择题三、简答题四、解答题五、程序阅读题六、算法题七、设计题第一章基础知识数据结构研究三方面主要内容数据结构的四种基本逻辑结构两种基本的存储表示方法算法分析的基本方法算法的时间复杂度1.20确定划线语句的执行次数，计算它们的渐近时间复杂度。(1) i=1;k=0; do {

k=k+10*i;i++; }while(i<=n-1)答： 划线语句的执行次数为n-1

渐近时间复杂度O(n)(2） i=1;x=0; do {

x++;i=2*i;

}while（i<n）;答： 划线语句的执行次数为

log2n。

渐近时间复杂度

O(log2n)k(循环次数)2*i121<n222<nk2k<nk+1因为要求2k<n,因此k<log2n,k=log2n(3) for(inti=1;i<=n;i++) for(intj=1;j<=i;j++) for(intk=1;k<=j;k++)

x++;

答： 划线语句的执行次数为

n(n+1)(n+2)/6

渐近时间复杂度

O(n3)

(4） x=n;y=0; while(x>=(y+1)*(y+1))y++;

答： 划线语句的执行次数为(

-1)+1=

（因为y从0开始）

渐近时间复杂度

O()(y+1)2<=n第二章线性表两种线性表表示方式：顺序表、链表链表的四种形式：单链表、双向链表、带表头结点的链表、单循环链表在顺序表/单链表/带表头结点的单链表/双向链表中：查找/删除/插入元素顺序和链接表示的优缺点比较多项式的算术运算2.3类SeqList的插入函数Insert，在表满时只简单地给出提示信息“Overflow”。试重写该函数，在表满时能使表容量加倍，并将新元素插入表中。template<classT>BoolSeqList<T>::Insert2(inti,Tx){}if(i<-1||i>n-1){cout<<“Outofbounds”<<endl;returnfalse;}if(n==maxLength)//表满时{}回顾线形表类的数据成员和关系： LinearList：线性表类 (protected: intn——实际长度)SeqList：顺序表类(private:intmaxLength—最大长度T*elements)SingleList：单链表类(private:Node<T>*first)T*elem=newT[2*maxLength];maxLength=maxLength*2;for(intj=0;j<=i;j++)

//扩充线性表容量的同时插入x

elem[j]=elements[j];elem[i+1]=x;for(j=i+1;j<n;j++) elem[j+1]=elements[j];n++;delete[]elements;elements=elem;returntrue;//n!=maxLength时,即表未满时for(intj=n-1;j>i;j--) elements[j+1]=elements[j];elements[i+1]=x;n++;returntrue;先扩充线性表容量，然后在位置i后统一做该插入x的操作也可以2.4在类SeqList中增加一个成员函数，删除表中所有值为x的元素，直接实现该函数并分析其时间复杂度。template<classT>boolSeqList<T>::Del(Tx){

}if(!n)//下溢出检查{ cout<<"UnderFlow"<<endl; returnfalse; }intflag=0;for(inti=0;i<n;i++) //删除所有值为x的元素{ if(elements[i]==x) { for(intj=i+1;j<n;j++) elements[j-1]=elements[j]; n--; i--; flag=1; }}returnflag;时间复杂度O(n)2.6在类SingleList中增加一个成员函数，将单链表逆置，直接实现该函数并分析其时间复杂度，要求设计的算法的空间复杂度为O(n)。template<classT>voidSingleList<T>::invert(){Node<T>*p=first,*q;first=NULL;while(p){

q=p->link;p->link=first;first=p;p=q;}}

时间复杂度O(n)2.7在类SingleList中增加一个成员函数，删除表中指定的元素x，并分析其时间复杂度。

template<classT>boolSingleList<T>::Del(constT&x){}while(p&&p->element!=x)//删除的不是第一个元素{q=p;p=p->link;}if(p)//p->element==x时删除{q->link=p->link;delete(p);n--;returntrue;}returnfalse;//否则p==NULL时失败if(!n) //下溢判断{ cout<<"UnderFlow!"<<endl; returnfalse;}Node<T>*p=first,*q;if(first->element==x)//若删除的是第一个元素{ first=first->link; deletep; n--;

returntrue;}时间复杂度O(n)第三章堆栈和队列堆栈——后进先出(LIFO) 插入/删除操作都在表的同一端队列——先进先出(FIFO)

一端插入，另一端删除顺序栈的操作：出栈/入栈循环队列的操作：入队/出队 空队列/满队列后缀表达式的计算后缀/中缀/前缀表达式间的转换*3.1设A，B，C，D，E五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。（1）A，B，C，D，E（2）A，C，E，B，D（3）C，A，B，D，E（4）E，D，C，B，A（1）能得到该序列。相应的push和pop序列为：push(A);pop();push(B);pop();push(C);pop();push(D);pop();push(E);pop();（2）不能得到该序列，在E出栈时，B和D在栈中，B比D先进栈，所以D应比B先出栈。（3）不能得到该序列，在C出栈时，A和B在栈中，A比B先进栈，所以B应比A先出栈。（4）能得到该序列。相应的push和pop序列为：push(A);push(B);push(C);push(D);push(E);pop();pop();pop();pop();pop();3.2写出下列表达式的后缀形式。（1）(a+b)/(c+d)（2）b^2-4*a*c（3）a*c-b/c^2（4）(a+b)*c+d/(e+f)（5）(a+b)*(c*d+e)-a*c【参考解答】（1）ab+cd+/（2）b2^4a*c*-（3）ac*bc2^/-（4）ab+c*def+/+（5）ab+cd*e+*ac*-3.13编程实现利用队列将栈中元素逆置的算法。【参考解答】template<classT>voidSeqStack<T>::Reverse(){ SeqQueue<T>sq(maxTop+1); Ttemp;

while(!IsEmpty()){ Top(temp); Pop(); sq.EnQueue(temp); } while(!sq.IsEmpty()){ sq.Front(temp); sq.Dequeue(); Push(temp); }}第四章数组和字符串行优先顺序/列优先顺序存储数组存储地址的计算稀疏矩阵的存储： 行三元组、列三元组稀疏矩阵的快速转置： 行三元组，k[]、num[]数组4.2给出三维数组元素A[i][j][k]的存储地址loc(A[i][j][k])。解：设0≤i≤m1,0≤j≤m2,0≤k≤m3,每个数组元素占c个存储单元，则行优先顺序的存储地址：4.6给出下列稀疏矩阵的行优先和列优先顺序存储的行三元组和列三元组表示。【参考解答】列三元组为

4.7求对题图4-1的稀疏矩阵执行矩阵转置时数组num[]和k[]的值。col01234num[col]10212k[col]01134行三元组为：

第五章树树的基本概念——双亲、孩子、度、层次树不能为空树，森林可以为空森林树和二叉树的区别：P80二叉树的性质：性质5.1——5.4满二叉树、完全二叉树（性质）二叉树类的实现——二叉链表二叉树的遍历——先序/后序/中序（递归算法）二叉树遍历的应用实例

——二叉树复制Copy

——求二叉树结点数Size

——释放一棵二叉树所有结点Clear二叉树和树/森林的互相转换哈夫曼树构造、哈夫曼编码、加权路径长度WPL计算

5.2对于三个结点A，B和C，可分别组成多少不同的无序树、有序树和二叉树？（1）无序树：9棵（2）有序树：12棵（3）二叉树：30棵3棵6棵6棵6棵各6棵5.4高度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上的结点的度均为k。如果按从上到下，从左到右子树的次序对树中结点从1开始编号。（1）各层的结点数目是多少?（2）编号为i的结点的双亲结点（若存在）的编号是多少?（3）编号为i的结点的第m个孩子结点（若存在）的编号是多少?（4）编号为i的结点的有右兄弟的条件是什么?【参考解答】(1)第i层的结点数目为ki-1(2)编号为i的结点的双亲结点的编号为也即：(3)编号为i的结点的第m个孩子结点编号是：(4)编号为i的结点有右兄弟的条件是即：，也即i-1不能被k整除。

5.5找出所有二叉树，其结点在下列两种次序下恰好都以同样的次序出现。（1）先序和中序；（2）先序和后序；（3）中序和后序【参考解答】（1）空二叉树和所有结点均无左孩子的二叉树（2）空二叉树和只有一个根的二叉树（3）空二叉树和所有结点均无右孩子的二叉树5.6设对一棵二叉树进行中序遍历和后序遍历的结果分别为：

（1）中序遍历（BDCE）A

（FHG）

（2）后序遍历（DECB）（HGF）A

画出该二叉树。ABFCDEGH5.7写出下图中二叉树的先序、中序和后序遍历结果先序：DEHFJGCKAB中序：HEJFGKCDAB后序：HJKCGFEBADDEAFJGBCHK5.9设二叉树以二叉链表存储，试编写求解下列问题的递归算法

（1）完成删除一棵二叉树，并释放所有的结点空间template<classT>voidBinaryTree<T>::Clear()//public{ Clear(root);}template<classT>voidBinaryTree<T>::Clear(BTNode<T>*t)//private{

if(t){

Clear(t->lChild); Clear(t->rChild); deletet; }}（2）求一棵二叉树中的度为1的结点个数；template<classT>intBinaryTree<T>::CountDegree1()//public{returnCountDegree1(root); }template<classT>intBinaryTree<T>::CountDegree1(BTNode<T>*t)//private{if(t){if(t->lChild&&!t->rChild||!t->lChild&&t->rChild)

returnCountDegree1(t->lChild)+CountDegree1(t->rChild)+1; elseif(t->lChild&&t->rChild) returnCountDegree1(t->lChild)+CountDegree1(t->rChild); elsereturn0;}elsereturn0;}（3）设计算法，交换一棵二叉树中每个结点的左、右子树。template<classT>voidBinaryTree<T>::Exchange()

//public{ Exchange(root);}template<classT>voidBinaryTree<T>::Exchange(BTNode<T>*t)

//private{ if(t){

BTNode<T>*q=t->lChild; t->lChild=t->rChild; t->rChild=q; Exchange(t->lChild); Exchange(t->rChild); }}补充：P89-90

（1）Size()函数求二叉树结点数

（2）Copy()函数实现二叉树复制

（3）Clear()函数举例：Clear函数template<classT>voidBinaryTree<T>::Clear(BTNode<T>*t){if(t){Clear(t->lChild);Clear(t->rChild);cout<<"delete"<<t->element<<"..."<<endl;deletet;}}5.14将上图中的树转换成二叉树，并将下图中的二叉树转换成森林。5.19设S={A,B,C,D,E,F}，W={2,3,5,7,9,12}，对字符集合进行哈夫曼编码，W为各字符的频率

（1）画出哈夫曼树

（2）计算带权路径长度

（3）求各字符的编码A: 1010B: 1011C: 100D: 00E: 01F: 11加权路径长度：WPL=(2+3)×4+5×3+(7+9+12)×2=91

第六章集合与搜索顺序搜索算法 搜索有序表/无序表，顺序存储/链接存储二分搜索算法

适用于顺序存储的有序表。二叉判定树平均搜索长度的计算方法6.5设计一个递归算法，实现对一个有序表的顺序搜索template<classT>intSeqList<T>::Search4(constT&x)const{elements[length]=1000;returnSch4(x,0);}template<classT>intSeqList<T>::Sch4(constT&x,inti)const{if(x<elements[i])return0;elseif(x==elements[i])return++i; elsereturnSch4(x,i+1);}6.6设有序表用单链表表示，设计一个算法，实现对有序表的顺序搜索。template<classT>ResultCodeListSet<T>::Search(T&x){ Node<T>*p=first; while(p&&p->element<x) p=p->link; if(p&&p->element==x) returnSuccess; else returnNotPresenst;}6.10画出对长度为12的有序表进行对半搜索的二叉判定树，并求等概率搜索时，成功搜索情况下的平均搜索长度。ASL成功=1/12（1*1+2*2+3*4+4*5）=37/12ASL失败=1/13（3*3+4*10）=49/1352803610147119-125013468791011第七章搜索树二叉搜索树——中序遍历二叉搜索树可得递增排序有序序列二叉搜索树的插入、删除操作时间复杂度分析

——平均情况下,O(log2n)

——最坏情况下“退化”树形，O(n)由搜索结果可反向推得二叉搜索树B树m阶B-树的定义：P147B-树的性质B-树的插入、删除操作7.1建立以37，45，91，25，14，76，56，65为输入的二叉搜索树，再从该树上依次删除76，45，画出结果。37254591147656653725911456657.3已知对一棵二叉搜索树进行先序遍历的结果是：28，25，36，33，35，34，43，请画出此二叉搜索树。282536353334437.55阶B_树的高度为2时，树中元素个数最少为多少？至少有5个元素7.16(1)

从空树开始，以关键字序列 a,g,f,b,k,d,h,m,j,e,s,i,r,x,

建立一棵4阶B_树。7.17从上题的B_树中删除a,e,f,h1）删除afdebhkrgijmsx2)删除efdbhkrgijmsxfbdkrgijmsxh3)删除f4)删除hdkrgijmsxhbdkrgmsxibj第八章跳表和散列表散列函数与冲突除留余数法散列函数解决冲突的两种开地址法：

——拉链法

——开地址法（线性探查法、二次探查法、双散列法）8.3设有散列表ht[11]，散列函数为h(key)=key%11，采用线性探测和二次探测法处理冲突，试用关键字序列70，25，80，35，60，45，50，55分别建立散列表。线性探查法：Keyh(Key)7042538033526054515065500551452353254705806607508910Keyh(Key)7042538033526054515065500551452353254705806607508910二次探查法Keyh(Key)70425380335260545150655004513528032547056065075589108.3设有散列表ht[11]，散列函数为h(key)=key%11，采用线性探测和二次探测法处理冲突，试用关键字序列70，25，80，35，60，45，50，55分别建立散列表。8.4对上题的例子，若采用双散列法，试以散列函数h1(key)=keymod11，h2(key)=keymod9+1建立散列表。双散列法Keyh1(Key)7042538033526054515065500551802353254705606457508910Keyh2(Key)7025809356045150655第九章图图的基本概念——有向图、无向图、顶点、边、连通分量、强连通分量、出/入度、生成树、网图的两种表示方法：邻接矩阵、邻接表邻接表的构建和实现已知邻接表，计算各顶点的入度（9.4题）图的遍历算法

——深度优先搜索DFS

——宽度优先搜索BFS拓扑排序算法AOV网拓扑排序步骤拓扑序列最小代价生成树Prim算法9.1对如图所示的有向图，求：

(1)每个顶点的入度和出度；

(2)强连通分量；

(3)邻接矩阵。324150(1)各个顶点的入度和出度顶点 入度出度0 3 01 2 22 1 23 1 14 2 35 1 22415(2)强连通分量(3)邻接矩阵00 00 0010 00 0001 00 1010 00 0011 01 0000 10 10309.2从只有6个顶点没有边的图开始，以边<1,0>,<1,3>,<2,1>,<2,4>,<3,2>,<3,4>,<4,0>,<4,1>,<4,5>,<5,0>的次序建立邻接表结构。画出邻接表。52413005012345034402110123459.4已知有向图的邻接表，写出计算各个顶点的入度的算法。template<classT>voidLinkedGraph<T>::Degree(){int*d=newint[n];inti;Enode<T>*p;

for(i=0;i<n;i++)d[i]=0;

for(i=0;i<n;i++) for(p=a[i];p;p=p->nextArc) d[p->adjVex]++;for(i=0;i<n;i++)cout<<“d[“<<i<<“]=“<<d[i]; }9.6在题9.2所建立的邻接表上进行以顶点2为起点顶点的深度优先搜索和宽度优先搜索。分别画出遍历所得到的深度优先搜索和宽度优先搜索的生成森林（或生成树）。在题9.2所建立的邻接表对应的图为：5241300501234503440211012345以顶点2为起点顶点的深度优先搜索所得到深度优先搜索生成树：0501234503440211012345524130以顶点2为起点顶点的宽度优先搜索所得到宽度优先搜索生成树：52413005012345034402110123459.13设有边集合：<0,1>，<1,2>，<4,1>，<4,5>，<5,3>，<2,3>，（1）求此图的所有可能的拓扑序列；（1）此图的所有可能的拓扑序列：0412530415230451234012534015234051234501235241309.13设有边集合：<0,1>，<1,2>，<4,1>，<4,5>，<5,3>，<2,3>，（2）若以此为顺序通过加入边的方式建立邻接表，则在该邻接表上执行教材给定的拓扑排列算法（TopoSort），将得到何种拓扑序列？（2）得到拓扑序列：0412532501234531310123459.17使用普里姆算法，以1为源点，画出下面无向图的最小代价生成树。2134507612312544333解：构造最小代价生成树的过程如下：1212210232130233213502323213450231232134507123123213450761231243第10章内排序三种简单排序算法快速排序两路合并排序算法的：过程时间复杂度稳定性最好情况平均情况最坏情况稳定性简单选择排序O(n2)O(n2)O(n2)不稳定冒泡排序

O(n)O(n2)O(n2)稳定直接插入排序O(n)O(n2)O(n2)稳定快速排序

O(nlog2n)O(nlog2n)O(n2)不稳定两路合并排序O(nlog2n)O(nlog2n)O(nlog2n)稳定10.1五种内排序算法的排序过程

（1）简单选择排序——每趟确定一个最小元素位置，最好/最坏/平均情况时间复杂度一样

（2）直接插入排序——排序结束前，都不能确定任何一个元素位置，偏爱有序序列

（3）冒泡排序——某趟没有交换元素时可停止，偏爱有序序列。

（4）快速排序——”哨兵“，偏爱基本无序序列

（5）两路合并排序——必须借助一个与原序列等大小的辅助数组实现，辅助存储空间O(n)。10.1元素序列(61,87,12,03,08,70,97,75,53,26)按下列算法排序，写给出各趟排序结果。（1）简单选择排序初始序列61871203087097755326第1趟（03）871261087097755326第2趟（0308）1261877097755326第3趟（030812）61877097755326第4趟（03081226）877097755361第5趟（0308122653）7097758761第6趟（030812265361）97758770第7趟（03081226536170）758797第8趟（0308122653617075）8797第9趟（030812265361707587）9710.1元素序列(61,87,12,03,08,70,97,75,53,26)按下列算法排序，写给出各趟排序结果。（2）冒泡排序（注意冒泡排序只排了7趟）初始序列(61871203087097755326)第1趟61120308708775532697第2趟12030861707553268797第3趟03081261705326758797第4趟03081261532670758797第5趟03081253266170758797第6趟03081226536170758797第7趟03081226536170758797（3）直接插入排序初始序列（61）871203087097755326第1趟（6187）1203087097755326第2趟（126187）03087097755326第3趟（03126187）087097755326第4趟（0308126187）7097755326第5趟（030812617087）97755326第6趟（03081261708797）755326第7趟（0308126170758797）5326第8趟（030812536170758797）26第9趟（03081226536170758797）10.1元素序列(61,87,12,03,08,70,97,75,53,26)按下列算法排序，写给出各趟排序结果。（4）快速排序初始序列61871203087097755326第1趟(53261238)61(97757087)第2趟(826123)5361(97757087)第3趟(3)8(1226)5361(97757087)第4趟3812(26)5361(97757087)第5趟3812265361(877570)97第6趟3812265361(7075)8797第7趟381226536170(75)879710.1元素序列(61,87,12,03,08,70,97,75,53,26)按下列算法排序，写给出各趟排序结果。（5）两路合并排序初始序列（61)(87)(12)(03)(08)(70)(97)(75)(53)(26)第1趟(6187)(0312)(0870)(7597)(2653)第2趟(03126187)(08707597)(2653)第3趟(0308126170758797)(2653)第4趟(03081226536170758797)10.1元素序列(61,87,12,03,08,70,97,75,53,26)按下列算法排序，写给出各趟排序结果。（1）最好、最坏和平均情况下的时间复杂度：简单选择排序:三种情况下的时间复杂度都为O(n2)。直接插入排序：最好情况下为O(n)；平均和最坏情况下为O(n2)。冒泡排序：最好情况为O(n)；最坏和平均情况下为O(n2)。快速排序：最好和平均情况下为O(nlog2n)；最坏情况下时间复杂度为O(n2)。两路合并排序：三种情况下，均为O(nlog2n)10.2从以下几个方面比较上题各种排序算法。（1）最好、最坏和平均情况下的时间复杂度；（2）空间复杂度；（3）稳定性（对不稳定的算法给出一个简单的实例）；（4）指出第一趟排序结束后就能确定某个元素最终位置的算法。（2）空间复杂度：简单选择排序、直接插入排序和冒泡排序都是O(1)快速排序：最好情况，空间复杂度为O(log2n)；最坏情况，空间复杂度为O(n)两路合并排序:均为O(n)10.2从以下几个方面比较上题各种排序算法。（1）最好、最坏和平均情况下的时间复杂度；（2）空间复杂度；（3）稳定性（对不稳定的算法给出一个简单的实例）；（4）指出第一趟排序结束后就能确定某个元素最终位置的算法。（3）稳定性：不稳定的是简单选择排序和快速排序两种，其它是稳定的。实例：331简单选择排序过后变成了133，

343快速排序之后变成了33410.2从