数据结构复习题

（1）在数据结构中，从逻辑上可以把数据结构分为线性结构和非线性结构。

线性结构主要包括线性表、堆栈、队列、串、数组和广义表，而非线性结构主要包括树形结构和图形结构。

因此也有一种说法是数据结构按逻辑结构可以分为线性结构、树形结构和图形结构。

（2）数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及他们之间的关系和运算等的学科。

（3）算法的五个重要特性是有穷性、确定性、可行性、输入和输出。

数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度。

（4）组成数据的基本单位是数据元素，组成数据的不可分割的最小单位是数据项。

（5）算法的时间复杂度：1）i=s=0;while(s<n){i++;s+=i;}上述算法中基本操作语句是while语句，设while语句循环执行T(n)次，则有：s=1+2+3+…+T(n)<n即(1+T(n))*T(n)/2<n2=O(n)所以，T(n)<)nT<nT((1(n*))2）s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;3）i=1;while(i<=n)i=i*2;上述算法的基本操作语句是i=i*2，假设该语句执行了T(n)次，则有：2T(n)<=n即有T(n)<=log2n所以有T(n)=O(log2n)4）以下语句的时间复杂度是（）。

for ( i=1; i<=n ; ++i )for ( j=1 ; j <=n ; ++j ){ c[i][j] = 0;for ( k=1 ; k <= n; ++k )c[i][j] += a[i][k] * b[k][j] ; }A O(n2)B O(n3)C O(logn)D O(n4)（1）顺序表的优点是可以随机访问数据元素；缺点是大小固定，不利于增减结点（增减操作需要移动元素）。

链表的优点是采用指针方式增减结点，非常方便（只需要改变指针指向，不移动结点）。

其缺点是不能随机访问，只能顺序访问；另外，每个结点上增加指针域，造成额外存储空间增大。

如果最常用的操作是取第i个结点及其前驱，则采用（D）存储方式最节省时间。

A．单链表 B．双链表 C．单循环链表 D．顺序表（2）；判断不带头结点单链表L为空的条件是L=NULL；判断带头结点单链表L 为空的条件是L->next=NULL。

（3）设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为s->next=p->next;和p->next=s;（4）向一个长度为n的顺序表中的第i个元素（1≤i≤n）之前插入一个元素时，需向后移n-i+1个元素。

在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动n-i个元素。

（5）设指针变量p指向循环双向链表中结点A，指针变量s指向被插入结点B，要求给出在结点A的前面插入结点B的操作序列（设双向链表中结点的两个指针域分别为prior和next）。

（6）在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作：（1）s->next= p->next ;（2）p->next=s;（3）t=p->data;（4）p->data= s->data ;（5）s->data= t ;试补充①、②、③，完成上述功能。

（7）LinkList mynote(LinkList L){//L是不带头结点的单链表的头指针if(L&&L->next){q=L；L=L－>next；p=L；S1：while(p->next!=NULL) p=p－>next；S2：p－>next=q；q－>next=NULL；}return L；}请回答下列问题：（1）说明语句S1的功能；找到尾结点（2）说明语句组S2的功能；将头结点置尾，变成新的尾结点（3）设链表表示的线性表为（a1,a2, …,a n）,写出算法执行后的返回值所表示的线性表。

（a2, …,a n,a1）（8）算法设计1）有一个单链表（不同结点的数据域值可能相同），其头指针为head，设计一个算法计算数据域为x的结点个数。

int count(SNode *head, ElemType x)｛Snode *p;int n=0;p=head;while(p!=NULL){ if(p->data==x)n++;p=p->next;}return n;｝2）编写算法，将一个结点类型为Lnode的单链表按逆序链接，即若原单链表中存储元素的次序为a1，......a n-1，a n，则逆序链接后变为, a n，a n-1， (1)void contrary (Lnode * &h){Lnode *p=h;h=NULL;While (p!=null){Lnode*q=p;p=p->next;q→next=h;h=q;}}3）有一个单链表（不同结点的数据域值可能相同），其头指针为L，设计一个算法查找表中第i个结点。

4）若在头结点为*p的单链表中找到了数据域为x的结点，则返回首次找到的结点的序号；若未找到，则返回一个特定值-1。

int locate(SNode *p,ElemType x){int i=0;SNode *q=p->next;while(q!=NULL&&q->data!=x){q=q->next;i++;}if(q==NULL)return -1;elsereturn i;}3 堆栈、队列、数组、串、广义表（1）堆栈的特点是后进先出；而队列的特点是先进先出。

（2）设栈的输入序列是1，2，3，4，则（）不可能是其出栈序列。

A 1，2，4，3B 2，1，3，4C 4，3，1，2D 1，4，3，2（3）判定一个环形队列qu（最多元素为MaxSize）为空的条件是qu->front==qu->rear;判断一个环形队列qu（最多元素为MaxSize）为满的条件是qu->front==(qu->rear+1)%Maxsize;判断一个顺序栈st（最多元素为Maxsize）为空的条件为st->top==-1。

为满的条件为st->top==Maxsize-1。

（4）若用一个大小为6的一维数组来实现环形队列，且当前rear和front的值分别为0和3。

当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是2和4。

（5）已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且A[0][0]的存储地址是LOC(A[0][0])，则A[i][j]的地址是LOC(A[0][0])+(n*i+j)*k；二维数组A[10][20]采用列序为主方式存储，每个元素占1个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是326；设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有i(i+1)/2+j-1个数据元素。

一个n*n的对称矩阵，如果以行或列为主序放入内存，则容量为（B）。

A．n*n B．n*(n+1)/2 C．n*(n-1)/2 D．n*n/2（6）串的两种最基本的存储方式是顺序存储方式和链式存储方式。

（7）在串S=“software”中，其真子串的数目是36，子串的数目是37。

（8）串是一种特殊的线性表，要区别空串和空白串有串S1=’ABCDEFG’，S2=’PQRST’，假设函数con(x,y)返回x和y串的连接串，subs(S,i,j)返回串S的从序号i的字符开始的j个字符组成的子串（设置字符串从0开始编号），len(S)返回串S的长度，则con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的结果串是（D）。

A.BCDEFB.BCDEFGC.BCPQRSTD.CDEFGFG（9）广义表(((a)))的表头是((a))，表尾是（）。

（10）广义表A= (a,(a,b),((a,b),c)),则它的深度为______3_____，它的长度为____4____。

一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，结点f 的层数为___3__(假定根结点的层数为0)。

4 树（1）二叉树的五个性质设一棵完全二叉树中有500个结点，则该二叉树的深度为_9_；设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（2h-1）。

若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（11 ）（2）一棵深度为5的二叉树中最少含有5个结点，最多含有31个结点；（3）设一棵完全二叉树中有n 个结点，若用二叉链表作为该完全二叉树的存储结构，则共有n+1个空指针域。

（4）熟练掌握二叉树的先序遍历、中序遍历和后序遍历，以及如何画出二叉树的线索树，二叉树、树与森林之间的转换。

有如下图所示的二叉树，回答以下问题：abc d i e fh g 1）写出该二叉树的先序、中序和后序序列。

先序：abdgcefhi 中序：dgbaechif 后序：gdbeihfca2）画出该二叉树的后序线索树。

3）画出把此二叉树还原成森林的图。

bd g ae cf h i（5）假设用于通讯的电文仅有8个字母组成，字母在电文中出现的频率分别为：7,19,2,6,32,3,21,10。

试用这8个频率值构造哈夫曼树并求其加权路径长度WPL 。

WPL=（32+19+21）*2+（6+7+10）*4+（2+3）*5=261（6）算法题1）设计一个算法，先序遍历二叉树，并在遍历过程中统计二叉树叶子结点的个数。

（PPT上有，在这里不赘述）2）假设二叉树采用链表存储结构，设计一个算法求二叉树中指定结点的层次。

int level(Btree *b, ElemType x, int h){int h1;if(b==NULL)return 0;else if (b->data==x)return h;else{h1=level(b->lchild,x,h+1);if(h1!=0)return h1;elsereturn level(b->rchild,x,h+1);}}3）设计一个算法，求出二叉树度为1的结点个数。