第1章 绪论要求：
1、基本概念：数据结构、数据元素等；
2、算法及其时间复杂度；
3、数据结构的抽象数据类型表示；
参考练习：
1、试设计将数组int a[n]中所有奇数移到偶数之前的算法，要求不能使用其它新数组，且时间复杂度为O(n)。
参考解答：
void shift(int a[],int n)
{ int i=0,j=n-1,t;
while(i<j)
{ while(a[i]%2==1)i++;
while(a[j]%2==0)j--;
if(i<j){t=a[i]; a[i]=a[j]; a[j]=t;}
}
2、数据的基本单位是 C 。
A)数据项 B)数据类型 C)数据元素 D)数据变量
3、下面程序段的时间复杂度为 C 。
for(i=0;i<m;i++)
for(j=0;j<n;j++)
A[i][j]=i*j;
A) O(m2) B) O(n2) C) O(m×n) D) O(m+n)
4、数据结构用二元组表示时，它包括 数据元素 的有限集D和D上 关系 的集合R。
5、数据结构是一门研究 非数值计算 的程序设计问题中计算机操作对象以及它们之间的关系和操作等的学科。
第2章 线性表要求：
掌握线性表的逻辑结构；
线性表的顺序存储表示及其算法；
线性表的链式存储表示及其算法；
1、已知L是带头结点的单链表，P,Q,L均为结点结构体类型的指针变量，P指向链表的结点既不是首元结点，也不是尾元结点，试从下列提供的语句中选择合适的语句序列。
a,删除P结点的直接后继结点的语句序列是 。
b,删除P结点的直接前驱结点的语句序列是 。
c,删除P结点的语句序列是 。
d,删除首元结点的语句序列是 。
e,删除尾元结点的语句序列是 。
(1) P=P->next;
(2) P->next=P;
(3) P->next=P->next->next;
(4) P=P->next->next;
(5) while(P!=NULL)P=P->next;
(6) while(Q->next!=NULL){P=Q;Q=Q->next;}
(7) while(P->next!=Q)P=P->next;
(8) while(P->next->next!=Q)P=P->next;
(9) while(P->next->next!=NULL)P=P->next;
(10) Q=P;
(11) Q=P->next;
(12) P=L;
(13) L=L->next;
(14) free(Q);
参考解答：a：11，3，14 b：10，12，8，11，3，14 c：10，12，7，3，14 d：12，11，3，14
e：12，9，11，3，14
2、习题2.3参考解答
a：4，1 b：7，11，8，4，1 c：6，12 d：9，1，5或9，4，1
3、习题2.4参考解答
int Insert(SeqList *pL,ElemType x)
{
int i;
if(pL->last >= MAXSIZE-1)
return (0);
i = pL->last;
while(pL->elem[i]>x&&i>=0)
{ pL->elem[i+1] = pL->elem[i];
i--;}
pL->elem[i+1]=x;
pL->last += 1;
return (1);
}
4、试写一算法，在无头结点的单链表上实现线性表元素插入操作:
int Insert(LinkList *pL,int i,ElemType b); 并将此算法和带头结点的单链表的插入操作算法进行比较。
参考解答：
int Insert(LinkList *pL,int i,ElemType b)
{ int i,j,n=0;
p=*pL;
while(p){ n++; p=p->next; } //用n统计链表的长度
if(i<1 || i>n+1) return 0; //判断插入位置是否合法
if(i==1){ //对第一位置单独处理
s=(LinkList)malloc(sizeof(Node));
s->data=b;
s->next=*pL; *pL=s; return OK;}
p=*pL; j=1 //余下情况肯定i>1，且L不为空
while(j<i-1){j++; p=p->next;} //找到插入位置的前一个结点，用p指向
s=(LinkList)malloc(sizeof(Node));
s->next=p->next; s->data=b; p->next=s;
return 1;
}
对带有头结点的链表来说，无论在什么位置插入元素，指向头结点的指针的指向关系都不会改变，这样只需要知道头结点的存储地址（指向头结点的指针），就可以实现对链表的操作；而无头结点的链表在最前面进行插入或删除操作时，指向首元结点的指针均会改变，所以需要把指向首元结点的指针变量的地址作为参数传递给被调函数，即使用二级指针。
5、已知有一个无头结点的单向循环链表，其每个结点中含三个域：pre,data,next，其中data为数据域，next为指向后继结点的指针域，pre为与next同类型的指针域，但它的值为空(NULL),试编写算法将此单向循环链表改为双向循环链表，即使pre成为指向前驱结点的指针域。提示：指针变量H指向首元结点。
参考解答：
typedef struct Node{
ElemType data;
struct Node *pre,*next;
}Node,*LinkList;
void Double(LinkList L) //L为指向单向循环链表中任一结点的指针
{ LinkList p=L;
while(p->next!=L)
{ p->next->pre=p; //使p指向结点的后继结点的前驱指针指向p所指结点
p=p->next;}
L->pre=p; //L所指结点的前驱结点为p所指结点
}
6、试以循环链表作稀疏多项式的存储结构，编写求其一阶导数的算法，要求利用原多项式中的结点空间存放导数多项式，同时释放所有无用结点（系数为0）。
参考解答：
typedef struct Node{
float coef,index; //coef表示系数，index表示该项的指数
struct Node *next;
}Node,*PolyList ;
void derivative(PolyList L)
{ PolyList p,q=L;
if(!L) return; //若为空链，则退出
p=q->next;
while(p!=L->next)
{ p->coef=p->coef*p->index; p->index=p->index-1; //求p所指项的导数
if(p->coef==0){ q->next=p->next; free(p); p=q->next;}
else{ q=p; p=p->next;}
}
7、在线性表的顺序存储中，元素之间的逻辑关系是通过 存储位置相临 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 结点的指针域 决定的。
8、线性表、栈和队列都是 线性 结构，可以在线性表的 任意 位置插入和删除元素；对于栈只能在一端插入和删除元素，可以进行插入和删除操作的一端叫 栈顶,另一端叫 栈底 ；对于队列能插入元素的一端称 队尾,能删除元素的一端称 队头 。
9、线性表采用链式存储时，其数据元素的存储地址 D 。
A)必须是连续的 B)部分地址必须是连续的
C)一定是不连续的 D)连续与否均可以
10、线性表的链接存储有利于 A 运算。
A)插入 B)读表元素 C)查找 D)定位
11、线性表是 C 。
A)一个无限序列，可以为空 B)一个有限序列，不可以为空
C)一个有限序列，可以为空 D)一个无限序列，不可以为空
12、若在单链表中，对在指针p所指的结点之前插入一个指针s所指的结点，可执行的操作为：（先将s所指结点插入p所指结点之后，再将s所指结点的值与p所指结点的值交换）
s->next= ;
p->next=s;
t=p->data;
p->data= ;
s->data= ;
参考解答,p->next s->data t
13、简述以下算法的功能
typedef struct Node{
ElemType data;
struct Node *next;
}LNode,*LinkList;
Status A(LinkList L){ //L是指向无头结点链表中首元结点的指针
if(L&&L->next){
Q=L;L=L->next;P=L;
while(p->next) P=P->next;
p->next=Q; Q->next=NULL;
}
return OK;
}
参考解答：将L所指的含有两个以上结点的链表的首元结点移到链尾，原第二个结点成为首元结点。
14、已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于链表中最大值max但大于链表中最小值min的元素结点的算法。
参考解答：
void Delete(LinkList L)
{ LinkList max,min,p,q;
p=L;
if(p->next&&p->next->next)
{ if(p->next->data>p->next->next->data){ max=p; min=p->next;}
else { max=p->next; min=p;}
p=p->next->next;
while(p->next)
{ if(p->next->data>=min->next->data&&p->next->data<=max->next->data)
{ q=p->next;
p->next=q->next;
free(q);continue;
}
if(p->next->data<min->next->data)
{ q=min->next;
min->next=q->next;
free(q);
min=p;
p=p->next; continue;
}
if(p->next->data>max->next->data)
{ q=max->next;
max->next=q->next;
free(q);
max=p;
p=p->next; continue;
}
}
}
}
15、某家电超市对仓库中的电视机信息按价格从低到高构成一个单链表存于计算机中，链表结点的结构体定义如下，链表为带头结点的链表。若现在又新到m台价格为n的电视机入库，试编写相应算法。
typedef struct Tvnode{
float price;
int num;
struct Tvnode *next;
}TvNode,*TvList;
int AddTv(TvList L,float m,int n){,..}//L为指向头结点的指针参考解答：
int AddTv(TvList L,float m,int n)
{ TvList p=L,q;
while(p->next&&p->next->price<m)p=p->next;
if(p->next==NULL||p->next->price>m){
q=(TvList)malloc(sizeof(TvNode));
q->price=m; q->num=n;
q->next=p->next;
p->next=q;
}
else p->next->num+=n;
}
本章其它习题解答请参看本系网站。
第3章 栈和队列要求：逻辑结构和算法
1、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，则当做出栈处理时，top变化为 。
A) top不变 B) top=0 C) top-- D) top++
2、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为 。
A) rear%n=front B) front%n+1=rear C) rear%n=front D)rear%n+1=front
3、一个中缀算术表达式为1+(3-x)*y，则其对应的后缀算术表达式为 。
A) 1 3 +x –y* B) 1 3 x +-y * C)1 3 x –y *+ D) 1 3 x y -+*
4、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入*s结点的操作应执行 。
A) front->next=s; front=s; B)s->next=rear; rear=s;
C) rear->next=s; rear=s; D)s->next=front; front=s;
5、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作应执行 。
A) front=front->next; B)rear=rear->next;
C) rear=front->next; D)front=rear->next;
6、写出下列程序段的输出结果（其中栈的元素类型SElemType为char）
void main()
{ Stack S; char x,y;
InitStack(S);
x=’c’; y=’k’;
Push(S,x); Push(S,’a’); Push(S,y); Pop(S,x);
Push(S,’t’); Push(S,x); Pop(S,x); Push(S,’s’);
while(!StackEmpty(S)){Pop(S,y); printf(y); };
printf(x);
}
7、写出以下程序段的输出结果（队列中的元素类型QElemType为char）。
void main()
{ Queue Q; char x=’e’,y=’c’;
InitQueue(Q);
EnQueue(Q,’h’); EnQueue(Q,’r’); EnQueue(Q,y); DeQueue(Q,x);
EnQueue(Q,x); DeQueue(Q,x); EnQueue(Q,’a’);
while(!QueueEmpty(Q)){ DeQueue(Q,y); printf(y);}
printf(x);
}
8、若栈用顺序存储表示，其栈的元素类型为整型，类型定义如下：
#define MAXSIZE 1000
typedef struct{
int elem[MAXSIZE]; //用来存放栈元素的数组，下标从0开始
int top; //指向栈顶位置的域，栈底为位置0
}Stack;
请补全以下栈操作函数：（用C语言）
（1）判断栈S是否为空栈：若为空，则返回1，不为空则返回0
int StackEmpty(Stack S){
if( )return (1);
else;
}
（2）入栈操作：若栈满，则返回0，不满，则入栈，返回1
int Push(Stack *p,int e){ //p为指向栈的指针，e为待入栈的元素
if( )return(0);//栈满，则返回0
=e; //入栈
p->top+=1; //栈顶位置变化
return(1);
}
9、简述栈、队列和线性表的差别和联系。
参考解答：1、C 2、D 3、C 4、C 5、A 6、stack 7、char
8、S.top==0或!(S.top) return(0) p->top>=MAXSIZE-1 p->elem[p->top]
本章其它习题解答请参看本系网站。
第4章 串要求：逻辑结构和顺序存储表示算法（顺序串）
1、简述空串和空格串（或称空格字符串）的区别。
2、已知下列字符串
a=’THIS’,f=’A SAMPLE’,c=’GOOD’,d=’NE’,b=’ ‘,
s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2)))),
t=Replace(f,SubString(f,3,6),c),u=Concat(SubString(c,3,1),d),
g=’IS’,v=Concat(s,Concat(b,Concat(t,Concat(b,u))))
其中Concat(a,b)为将串b联接到串a之后，其他操作与教材P71页串的抽象数据类型中定义的操作一致，试问：s,t,v,StrLength(s),Index(v,g),Index(u,g)各是什么？
3、已知：s=’(XYZ)+*’,t=’(X+Z)*Y’。试用联接、求子串和置换等操作，将s转化为t。
4、编写算法，求串s所含不同字符的总数和每种字符的个数。
5、两个字符串相等的充要条件是 和 。
6、设字符串S1=’ABCDEF’,S2=’PQRS’,则运算S=CONCAT(SUB(S1,2,LEN(S2)),SUB(S1,LEN(S2),2))后的串值为 。
参考解答：
1、空串是指长度为零的串，而空格串是指串中字符是空格的字符串。
2、s= ‘THIS SAMPLE IS’ t=’A GOOD’ u=’ONE’ v=’THIS SAMPLE IS A GOOD ONE’ 14,3,0
3、Replace(s,Substring(s,3,5),Concat(Substring(3,6,1),Concat(Substring(s,4,2),Concat(Substring(s,7,1),Substring(s,3,1)))))
4、算法1：
void count(String T)
{ StrCopy(S,T);
m=Strlength(S);
num=0;
for(i=1;i<=m;i++)
{ n=1;
Substring(Sub1,S,i,1);
if(!StrCompare(Sub1,’#’))continue;
for(j=i+1;j<=m;j++)
{ Substring(Sub2,S,j,1);
if(!StrCompare(Sub1,Sub2))
n++;
}
Replace(S,sub1,’#’);
num++;
printf(Sub1,n);
}
printf(num);
}
5、长度相等 每一对应位置字符相等
6、BCDEDE
第5章 数组和广义表要点：
1、掌握数组元素存储位置的换算；
2、了解特殊矩阵地存储方法和元素存储位置计算；
3、了解广义表的长度、深度、head、tail等概念和操作和存储结构。
1、对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址是多少？
2、一个稀疏矩阵为，则对应的三元组表是什么？
3、设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有一个存储地址空间，则a85的地址是多少？
4、设有上三角矩阵（aij）n×n，将其上三角逐行存于数组B[m]中，使得B[m]= aij，且k=f1(i)+f2(j)+c。请写出函数f1，f2和常数c（f1和f2中不含常数项）。
5、求下列广义表操作的结果：
（1）Head((p,h,w));
（2）Tail((b,k,p,h));
（3）Tail(((a,b),(c,d)));
（4）Tail(Head(((a,b),(c,d))));
（5）Tail(Head(Tail(((a,b),(c,d)))));
6、假设稀疏矩阵A和B均以三元组顺序表作为存储结构，试写出矩阵相加的算法：
int AddMatrix(TSMatrix A,TSMatrix B,TSMatrix &C);
7、试编写一个以三元组形式输出用十字链表存储表示的稀疏矩阵中非零元素的下标及其元素值的算法：int Print(CrossList &M);
8、按照教材5.5节中图5.8所示结点结构，画出下列广义表的存储结构图，并求出它的深度。
（1）（（（）），a，（（b，c），（），d），（（（e））））
（2）（（（（a），b）），（（（），d），（e，f）））
9、设三角矩阵R=采用一维数组进行压缩存储，第一个元素为R11，存储位置为1，每个元素占一个存储位置，则R32的存储位置为几？
参考解答：
1、&A[0][0]+(i*n+j)*L //L为每一数据元素所占的字节数
2、((1,3,2),(2,1,3),(3,3,-1),(3,4,5))
3、&aij=&a00+(i*(i+1)/2+j)*L (i>=j) //&a00为第一个元素的地址，L为每一
&aij=&a00+(j*(j+1)/2+i)*L (j>=i) //元素所占存储空间则a85的地址为0+8*9/2+5=41
4、若行号与列号均从0开始，则元素aij前有i行，各行的非0元素个数从n到n-i+1，共有i*(n+n-i+1)/2个元素，aij所在的行中，其前面共有j个元素，但为0的元素有i个，不为0的元素个数则为j-i个，所以在上三角中aij前面共有i*(n+n-i+1)/2+ j-i个非0的元素，这些元素需要存储在一维数组B[]中，且在aij的前面，若一维数组的下标也从0开始，若用B[k]存储aij，则k= i*(n+n-i+1)/2+ j- i =(-i2-i+2in)/2+j
即： c=0
若下标均从1开始，则 c=-n
5、（1） p （2）（k，p，h） （3）（（c，d）） （4）（b） （5）（d）
6、Status AddMatrix(TSMatrix A,TSMatrix B,TSMatrix &C)
{ if(A.mu!=B.mu||A.nu!=B.nu)return ERROR;
C.mu=A.mu; C.nu=A.nu;
a=1,b=1,c=0;
while(a<=A.tu&&b<=B.tu)
{ i1= A.data[a].i; i2= B.data[b].i;j1= A.data[a].j;j2= B.data[b].j;
if(i1==i2&&j1==j2) //若两三元组的行列都相等，则元素相加
{ sum=A.data[a].e+B.data[b].e;
if(sum){C.data[++c].e=sum; C.data[c].i=i1;C.data[c].j=j1;}
a++; b++;
continue;
}
if(i1*A.nu+j1<i2*A.nu+j2) //若A中三元组的行列数小，则直接放如C中
{ C.data[++c].e=A.data[a].e; C.data[c].i=i1; C.data[c].j=j1;
++a;
}
else //若B中三元组的行列数小，则直接放如C中
{ C.data[++c].e=B.data[a].e; C.data[c].i=i2; C.data[c].j=j2;
++b;
}
}
while(a<A.tu) //若A中还有三元组，则复制到C中
{ C.data[++c].e=A.data[a].e; C.data[c].i=i1; C.data[c].j=j1;
++a;
}
while(b<B.tu) //若B中还有三元组，则复制到C中
{ C.data[++c].e=B.data[a].e; C.data[c].i=i2; C.data[c].j=j2;
++b;
}
C.tu=c;
return OK;
}
7、Status Print(CrossList &M)
{ OLink *p;
p=M.rhead;
for(i=1;i<=M.mu;i++)
{ q=p[i];
while(q){ //将第i行链各结点输出
printf(“(%d,%d,%d),,q->i,q->j,q->e); //输出一个结点所对应的三元组
q=q->right;
}
}
}
8、深度均为4，画图略。
9、&Rij=&R11+(i*(i-1)/2+j-1)*L=1+4=5
第6章 树要点：
1、掌握树和二叉树的逻辑结构和基本概念；
2、掌握二叉树的性质、二叉链存储、遍历及其相关算法；
3、二叉树与树、森林的转换。
练习：
1、假定有如图的树，则该树的度为,树的深度为,终端结点的个数为,单分支结点的个数为,双分支结点的个数为,C结点的双亲结点为,其孩子结点为 。
2、设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有 个。
3、对于一个具有n个结点的二叉树，当它为一棵 二叉树时具有最小高度，即为,当它为一棵单支树（除终端结点外，所有的结点都为单分支结点）时具有最大高度，即为 。
4、对于一棵具有n个结点的二叉树，当采用二叉链进行存储时，其二叉链表中的指针域的总数为 个，其中 个用于链接孩子结点,个空闲着。
5、一棵深度为k的满二叉树的结点总数为,一棵深度为k的完全二叉树的结点总数的最小值为,最大值为 。
6、由a，b，c三个结点构成的二叉树，共有 种不同的结构。
7、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[i]若有左子女，则左子女是,若有右子女，则右子女为 。
8、一棵二叉树如右。
（1）写出对此二叉树进行先序、中序、后序和层序遍历时得到的结点序列。
（2）画出其中序线索二叉树。
9、已知一棵二叉树的中序遍历序列为CDBAEGF，先序遍历序列为ABCDEFG，试问能不能确定唯一一棵二叉树，若能请画出该二叉树。
10、给定一棵用二叉链表示的二叉树，其根结点指针为t，试写出求二叉树叶子结点数目的算法：int leaf(BiTree t);
11、将以下森林转化为相应的二叉树。
参考解答：
1、3 4 6 1 1 A F，G
2、n+1 3、满,log2(n+1) 最大 n
4、2n n-1 n+1 5、2k-1,2k-1,2k-1
6、30 7、R[2i] R[2i+1]
8、（1）ABDFHCEG DFHBACGE HFDBGECA ABCDEFGH
（2）如右。
9、
10、int leaf(BiTree t)
{ BiTree a[10],p=t;
int i=0,n=0;
while(p)
{ if(p){ a[i++]=p; p=p->lchild;}
else
{ p=a[--i];
if(p->lchild==NULL&&p->rchild==NULL)n++;
p=p->rchild;
}
}
return n;
}
4、如右：
第7章 图
要点：
1、图的逻辑结构和基本概念；
2、图的存储表示；
练习：
1、具有n个顶点的完全有向图的弧数为 。
2、对如右无向图：
画出图的邻接表存储结构；
给出邻接矩阵；
指出每个顶点的度；
该图是连通图吗？。
写出从顶点A出发，按深度优先遍历图时得到的顶点序列。
写出从顶点A出发，按广度优先遍历图时得到的顶点序列。
3、对于一个具有n个顶点无向图，回答下面问题：
所有顶点的度数之和与所有边之间存在什么关系？
该图要连通全部顶点至少需要多少条边？
若该图为完全图，则包含多少条边？
4、若一个有向图的十字链表如上，试画出该有向图。
参考解答：
1、n*(n-1)
2、（1）如右：
（2）
（3）A：2 B：2 C：4 D：2 E：3 F：3 G：2 H：2
（4）是连通图 （5）ABDCEHGF （6） ABCDEFHG
3、（1）所有顶点的度数之和是所有边数的2倍；
（2）n-1 （3）n(n-1)/2
4、
第8章 查找要点：
1、各种查找表元素如何组织；
2、各种查找方法的特征；
3、查找算法。
练习：
一、填空题
1、假定在有20个元素的有序表上进行二分查找，则比较一次查找成功的元素个数为,比较两次查找成功的元素个数为,比较三次查找成功的元素个数为,比较四次查找成功的元素个数为,比较五次查找成功的元素个数为,平均查找长度为 。
2、在索引查找中，首先查找,然后再查找相应的 。
3、在一个10阶的B-树上，根结点中所含的关键字数目最多允许为 个，最少允许为 个。
4、一棵深度为h的B-树上，若根结点为第一层，则任一叶子结点所处的层数为,当向该B-树插入一个新关键字时，为检索插入位置需读取 个结点。
参考解答：
1,1 2 4 8 5 3.7
2、索引表 子表
3、9 1
4、h,h（若不包含叶子结点层则为h-1）
二、选择题
1、采用顺序检索的方法检索长度为n的线性表，则检索每个元素的平均比较次数为（ ）。
A）n B）n/2 C）(n+1)/2 D）(n-1)/2
2、已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素，检索成功的比较次数为（ ）。
A）1 B）2 C）3 D）4
3、在一个3阶的B-树上，每个结点包含的子树相同，最多为 个，最少为 个。
A）1 B）2 C）3 D）4
参考解答：1、C 2、B 3、C B
三、应用题
1、习题8.12
（1）ASL = (1*1+2*2+3*3+4*3+5*2+6*1)/12 = 42/12 = 3.5
（2）ASL = (1*1+2*2+3*4+4*5)/12 = 37/12 = 3.1
2、写出二分查找的递归算法。
int Bisearch(int a[],int base,int top,int key)
{ if(base>top)return(-1);
int mid=(base+top)/2;
if(a[mid]==key)return(mid);
else{
if(a[mid]>key)return(Bisearch(a,base,mid-1,key);
else return(Bisearch(a,mid+1,top,key);
}
}
3、试设计一个算法，求出指定结点在给定的二叉排序树中的层次。
int level(BiTree t,KeyType Key)
{ int i=0;
while(t)
{i++;
if(t->data.key==key)break;
else t=t->data.key>key?t->lchild:t->rchild;
}
return i;
}
4、习题8.2解答：
ASL = (1*1+2*2+3*4+4*3)/10 = 2.9
5、习题8.4解答：
（1）3阶B-树中每一个结点中最少棵子树，－1个元素，最多3棵子树，2个元素；
（2）元素的插入总是从叶子结点的上一层结点中操作。首先从根结点开始，找到应当插入的结点；如果插入后结点中的元素个数>2，则结点分裂，且将中间的元素提升到其双亲结点；若双亲结点中的元素个数>2，则分裂、提升……。B-树总是平衡的
……
6、习题8.5解答：H(k) = (3k)%11 22,41,53,46,30,13,01,67
0
1
2
3
4
5
6
7
8
9
10
22
41
30
01
53
46
39
67
30
01
39
67
ASLsucc = (1*4 + 2*3 + 6*1)/8 = 16/8 = 2
ASLunsucc = (1*3 +2*2 + 3 + 4 + 5 + 6 + 7 + 8)/11 = 42/11 = 3.8
7、习题8.13解答,9个叶子结点的3阶B-树至少有4个非叶子结点，10个叶子结点则至少有7个非叶子结点。
第9章 排序要点：
1、熟练掌握各种排序方法的排序过程；
2、掌握各种排序的算法（简单插入、交换、选择法，希尔排序，快速排序，堆排序）；
3、哪些排序算法是稳定排序，哪些是不稳定排序；
4、各排序算法的时空性能分析。
练习题：
一、填空题
1、若有一组记录（50，40，95，20，15，70，60，45，80），在进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 次；在进行直接选择排序时，第4次交换和选择后，未排序记录（即剩下的无序表）为 ；利用快速排序进行递归调用的深度最大为 ；进行堆排序时的初始堆的记录次序为 。
2、对于堆排序和快速排序来说，若初始记录接近正序或反序，则益选用 排序；若初始记录无序，则益选用 排序。
3、从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列中的正确位置上，此方法称为 排序；从未排序序列中挑选元素，并将其放入已排序序列的一端，此方法称为 排序；依次将每两个相临的有序表合并成一个有序表的排序方法叫做 排序；当两个元素比较出现反序（逆序）时就相互交换位置的排序方法叫做 ；每次把待排序的元素划分为左右两个子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，右区间中元素的关键字均大于等于基准元素关键字，则此排序方法叫做 。
参考解答：
1、3 50，60，70，80，95 4 95，80，70，45，15，50，60，40，20
2、堆 快速二、应用题
1、设待排序的记录用无头结点单链表作为存储结构，结点的类型名为linklist，为一结构体类型，包括指针域next，关键字域key和其它数据域，请写出选择排序算法：
void selesort(linklist *head) //head为指向表头的指针
{ linklist p,q,t,max,pre,new=NULL;
p=*head; //p指向首元结点
while(p) //当链表中还有结点
{ pre=max=p; //pre与t作为前后结点的指针，在中间的循环中联动
t=p->next; //先把p所指结点当作最大的结点
while(t){ if(t->key>max->key) //在余下的链表中找一个最大的
{q=pre; max=t;}
pre=t;
t=t->next;
}
if(max==p) //若最大结点为p所指，则将结点插入new链
{q=p->next;p->next=new;new=p;p=q;}
else //否则，将max所指结点插入new链
{q->next=max->next; max->next=new; new=max}
}
*head=new; //排序后的链表
}
2、写出在含有n个元素的堆中增加一个元素，并调整为堆的算法。（设待堆中的元素存储在一个一维数组中，数组元素为整型（即元素值就是关键字，且为整数）。
void heapinsert(int a[],int n,int x)
{ int i,k=n+1;
a[k]=x;
i=k/2;
while(i)
{ t=a[i];
if(k%2&&a[k]<a[k-1])k--;
if(t<a[k])
{ a[i]=a[k]; a[k]=t;
k=i; i=i/2;}
else break;
}
3、若待排序的元素序列为（48，89，56，35，43，83），写出利用快速排序的方法，以第一个元素为基准得到的一次划分的结果。
（43，35，48，56，89）
4、判断以下序列是否为堆？，如果不是，则按筛选法把它调整为堆。
（1）（100，86，48，73，35，39，42，57，66，21）；
（2）（12，70，33，65，24，56，48，92，86，33）；
（3）（103，97，56，38，66，23，42，12，30，52，6，20）。
4、（1）是堆
（2）不是堆，调整后为：（92，86，56，70，33，33，48，65，12，24）
（3）是堆期中考试参考答案判断题（每题1分，共10分，错的打×,对的打√）
1
2
3
4
5
6
7
8
9
10
×
×
√
√
×
√
×
√
×
×
填空题（共20空，每空2分,共40分）
【1】 H->next == NULL 【2】 p->next == L
【3】 p->next 【4】 s
【5】 p->next 【6】 s->data
【7】 t 【8】 16
【9】 字符串的长度相等 【10】 对应位置上的字符相等
【11】 ‘BCDEDE’ 【12】 GetHead( GetHead( GetTail( LS )))
【13】 5 【14】 3
【15】 ((1,2,-3),(1,4,1),(2,1,2),(3,2,5)) 【16】 x + ((i-1)*n+j-1)*t
【17】 x+((j-1)*m+i-1)*t 【18】 线性
【19】 栈顶 【20】 栈底
三、选择题（每题1分，共10分）
1
2
3
4
5
6
7
8
9
10
A
A
D
C
D
D
B或D
A
D
D
四、简答题（每题2分，共10分）
1、数据的逻辑结构是指数据元素之间的逻辑关系描述，通常有哪四种基本的结构？
答：集合结构、线性结构、树型结构和图（网状）结构
2、在数据结构的抽象数据类型（ADT）描述中一般分哪三个主要部分来描述？
答：数据元素、数据元素的关系和操作集。
3、算法有哪五个基本特性？
答：确定性、有限性、可行性、0个或多个输入、一个或多个输出。
4、简述算法的功能.
答：将栈中的元素逆置。
5、简述空串与空格串的区别。
答：空串是指长度为0的字符串，而空格串是指组成串的字符是空格的串。
五、算法填空题（共20空，每空1.5分，共30分）
【1】 j 【2】 k
【3】 p = p->next 【4】 p->next
【5】 q->next或p->next->next 【6】 （pQ->rear+1）%MAXSIZE
【7】 1 【8】 pQ->front
【9】 0 【10】 S.top==-1或IsEmpty(S)
【11】 ch1==ch2 【12】 S.top==-1或IsEmpty(S)
【13】 return(0) 【14】 T.len
【15】 S.ch[i]或ch1 【16】 k
【17】 j 【18】 p
【19】 root->LChild 【20】 root->RChild
1、基本概念：数据结构、数据元素等；
2、算法及其时间复杂度；
3、数据结构的抽象数据类型表示；
参考练习：
1、试设计将数组int a[n]中所有奇数移到偶数之前的算法，要求不能使用其它新数组，且时间复杂度为O(n)。
参考解答：
void shift(int a[],int n)
{ int i=0,j=n-1,t;
while(i<j)
{ while(a[i]%2==1)i++;
while(a[j]%2==0)j--;
if(i<j){t=a[i]; a[i]=a[j]; a[j]=t;}
}
2、数据的基本单位是 C 。
A)数据项 B)数据类型 C)数据元素 D)数据变量
3、下面程序段的时间复杂度为 C 。
for(i=0;i<m;i++)
for(j=0;j<n;j++)
A[i][j]=i*j;
A) O(m2) B) O(n2) C) O(m×n) D) O(m+n)
4、数据结构用二元组表示时，它包括 数据元素 的有限集D和D上 关系 的集合R。
5、数据结构是一门研究 非数值计算 的程序设计问题中计算机操作对象以及它们之间的关系和操作等的学科。
第2章 线性表要求：
掌握线性表的逻辑结构；
线性表的顺序存储表示及其算法；
线性表的链式存储表示及其算法；
1、已知L是带头结点的单链表，P,Q,L均为结点结构体类型的指针变量，P指向链表的结点既不是首元结点，也不是尾元结点，试从下列提供的语句中选择合适的语句序列。
a,删除P结点的直接后继结点的语句序列是 。
b,删除P结点的直接前驱结点的语句序列是 。
c,删除P结点的语句序列是 。
d,删除首元结点的语句序列是 。
e,删除尾元结点的语句序列是 。
(1) P=P->next;
(2) P->next=P;
(3) P->next=P->next->next;
(4) P=P->next->next;
(5) while(P!=NULL)P=P->next;
(6) while(Q->next!=NULL){P=Q;Q=Q->next;}
(7) while(P->next!=Q)P=P->next;
(8) while(P->next->next!=Q)P=P->next;
(9) while(P->next->next!=NULL)P=P->next;
(10) Q=P;
(11) Q=P->next;
(12) P=L;
(13) L=L->next;
(14) free(Q);
参考解答：a：11，3，14 b：10，12，8，11，3，14 c：10，12，7，3，14 d：12，11，3，14
e：12，9，11，3，14
2、习题2.3参考解答
a：4，1 b：7，11，8，4，1 c：6，12 d：9，1，5或9，4，1
3、习题2.4参考解答
int Insert(SeqList *pL,ElemType x)
{
int i;
if(pL->last >= MAXSIZE-1)
return (0);
i = pL->last;
while(pL->elem[i]>x&&i>=0)
{ pL->elem[i+1] = pL->elem[i];
i--;}
pL->elem[i+1]=x;
pL->last += 1;
return (1);
}
4、试写一算法，在无头结点的单链表上实现线性表元素插入操作:
int Insert(LinkList *pL,int i,ElemType b); 并将此算法和带头结点的单链表的插入操作算法进行比较。
参考解答：
int Insert(LinkList *pL,int i,ElemType b)
{ int i,j,n=0;
p=*pL;
while(p){ n++; p=p->next; } //用n统计链表的长度
if(i<1 || i>n+1) return 0; //判断插入位置是否合法
if(i==1){ //对第一位置单独处理
s=(LinkList)malloc(sizeof(Node));
s->data=b;
s->next=*pL; *pL=s; return OK;}
p=*pL; j=1 //余下情况肯定i>1，且L不为空
while(j<i-1){j++; p=p->next;} //找到插入位置的前一个结点，用p指向
s=(LinkList)malloc(sizeof(Node));
s->next=p->next; s->data=b; p->next=s;
return 1;
}
对带有头结点的链表来说，无论在什么位置插入元素，指向头结点的指针的指向关系都不会改变，这样只需要知道头结点的存储地址（指向头结点的指针），就可以实现对链表的操作；而无头结点的链表在最前面进行插入或删除操作时，指向首元结点的指针均会改变，所以需要把指向首元结点的指针变量的地址作为参数传递给被调函数，即使用二级指针。
5、已知有一个无头结点的单向循环链表，其每个结点中含三个域：pre,data,next，其中data为数据域，next为指向后继结点的指针域，pre为与next同类型的指针域，但它的值为空(NULL),试编写算法将此单向循环链表改为双向循环链表，即使pre成为指向前驱结点的指针域。提示：指针变量H指向首元结点。
参考解答：
typedef struct Node{
ElemType data;
struct Node *pre,*next;
}Node,*LinkList;
void Double(LinkList L) //L为指向单向循环链表中任一结点的指针
{ LinkList p=L;
while(p->next!=L)
{ p->next->pre=p; //使p指向结点的后继结点的前驱指针指向p所指结点
p=p->next;}
L->pre=p; //L所指结点的前驱结点为p所指结点
}
6、试以循环链表作稀疏多项式的存储结构，编写求其一阶导数的算法，要求利用原多项式中的结点空间存放导数多项式，同时释放所有无用结点（系数为0）。
参考解答：
typedef struct Node{
float coef,index; //coef表示系数，index表示该项的指数
struct Node *next;
}Node,*PolyList ;
void derivative(PolyList L)
{ PolyList p,q=L;
if(!L) return; //若为空链，则退出
p=q->next;
while(p!=L->next)
{ p->coef=p->coef*p->index; p->index=p->index-1; //求p所指项的导数
if(p->coef==0){ q->next=p->next; free(p); p=q->next;}
else{ q=p; p=p->next;}
}
7、在线性表的顺序存储中，元素之间的逻辑关系是通过 存储位置相临 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 结点的指针域 决定的。
8、线性表、栈和队列都是 线性 结构，可以在线性表的 任意 位置插入和删除元素；对于栈只能在一端插入和删除元素，可以进行插入和删除操作的一端叫 栈顶,另一端叫 栈底 ；对于队列能插入元素的一端称 队尾,能删除元素的一端称 队头 。
9、线性表采用链式存储时，其数据元素的存储地址 D 。
A)必须是连续的 B)部分地址必须是连续的
C)一定是不连续的 D)连续与否均可以
10、线性表的链接存储有利于 A 运算。
A)插入 B)读表元素 C)查找 D)定位
11、线性表是 C 。
A)一个无限序列，可以为空 B)一个有限序列，不可以为空
C)一个有限序列，可以为空 D)一个无限序列，不可以为空
12、若在单链表中，对在指针p所指的结点之前插入一个指针s所指的结点，可执行的操作为：（先将s所指结点插入p所指结点之后，再将s所指结点的值与p所指结点的值交换）
s->next= ;
p->next=s;
t=p->data;
p->data= ;
s->data= ;
参考解答,p->next s->data t
13、简述以下算法的功能
typedef struct Node{
ElemType data;
struct Node *next;
}LNode,*LinkList;
Status A(LinkList L){ //L是指向无头结点链表中首元结点的指针
if(L&&L->next){
Q=L;L=L->next;P=L;
while(p->next) P=P->next;
p->next=Q; Q->next=NULL;
}
return OK;
}
参考解答：将L所指的含有两个以上结点的链表的首元结点移到链尾，原第二个结点成为首元结点。
14、已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于链表中最大值max但大于链表中最小值min的元素结点的算法。
参考解答：
void Delete(LinkList L)
{ LinkList max,min,p,q;
p=L;
if(p->next&&p->next->next)
{ if(p->next->data>p->next->next->data){ max=p; min=p->next;}
else { max=p->next; min=p;}
p=p->next->next;
while(p->next)
{ if(p->next->data>=min->next->data&&p->next->data<=max->next->data)
{ q=p->next;
p->next=q->next;
free(q);continue;
}
if(p->next->data<min->next->data)
{ q=min->next;
min->next=q->next;
free(q);
min=p;
p=p->next; continue;
}
if(p->next->data>max->next->data)
{ q=max->next;
max->next=q->next;
free(q);
max=p;
p=p->next; continue;
}
}
}
}
15、某家电超市对仓库中的电视机信息按价格从低到高构成一个单链表存于计算机中，链表结点的结构体定义如下，链表为带头结点的链表。若现在又新到m台价格为n的电视机入库，试编写相应算法。
typedef struct Tvnode{
float price;
int num;
struct Tvnode *next;
}TvNode,*TvList;
int AddTv(TvList L,float m,int n){,..}//L为指向头结点的指针参考解答：
int AddTv(TvList L,float m,int n)
{ TvList p=L,q;
while(p->next&&p->next->price<m)p=p->next;
if(p->next==NULL||p->next->price>m){
q=(TvList)malloc(sizeof(TvNode));
q->price=m; q->num=n;
q->next=p->next;
p->next=q;
}
else p->next->num+=n;
}
本章其它习题解答请参看本系网站。
第3章 栈和队列要求：逻辑结构和算法
1、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，则当做出栈处理时，top变化为 。
A) top不变 B) top=0 C) top-- D) top++
2、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为 。
A) rear%n=front B) front%n+1=rear C) rear%n=front D)rear%n+1=front
3、一个中缀算术表达式为1+(3-x)*y，则其对应的后缀算术表达式为 。
A) 1 3 +x –y* B) 1 3 x +-y * C)1 3 x –y *+ D) 1 3 x y -+*
4、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入*s结点的操作应执行 。
A) front->next=s; front=s; B)s->next=rear; rear=s;
C) rear->next=s; rear=s; D)s->next=front; front=s;
5、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作应执行 。
A) front=front->next; B)rear=rear->next;
C) rear=front->next; D)front=rear->next;
6、写出下列程序段的输出结果（其中栈的元素类型SElemType为char）
void main()
{ Stack S; char x,y;
InitStack(S);
x=’c’; y=’k’;
Push(S,x); Push(S,’a’); Push(S,y); Pop(S,x);
Push(S,’t’); Push(S,x); Pop(S,x); Push(S,’s’);
while(!StackEmpty(S)){Pop(S,y); printf(y); };
printf(x);
}
7、写出以下程序段的输出结果（队列中的元素类型QElemType为char）。
void main()
{ Queue Q; char x=’e’,y=’c’;
InitQueue(Q);
EnQueue(Q,’h’); EnQueue(Q,’r’); EnQueue(Q,y); DeQueue(Q,x);
EnQueue(Q,x); DeQueue(Q,x); EnQueue(Q,’a’);
while(!QueueEmpty(Q)){ DeQueue(Q,y); printf(y);}
printf(x);
}
8、若栈用顺序存储表示，其栈的元素类型为整型，类型定义如下：
#define MAXSIZE 1000
typedef struct{
int elem[MAXSIZE]; //用来存放栈元素的数组，下标从0开始
int top; //指向栈顶位置的域，栈底为位置0
}Stack;
请补全以下栈操作函数：（用C语言）
（1）判断栈S是否为空栈：若为空，则返回1，不为空则返回0
int StackEmpty(Stack S){
if( )return (1);
else;
}
（2）入栈操作：若栈满，则返回0，不满，则入栈，返回1
int Push(Stack *p,int e){ //p为指向栈的指针，e为待入栈的元素
if( )return(0);//栈满，则返回0
=e; //入栈
p->top+=1; //栈顶位置变化
return(1);
}
9、简述栈、队列和线性表的差别和联系。
参考解答：1、C 2、D 3、C 4、C 5、A 6、stack 7、char
8、S.top==0或!(S.top) return(0) p->top>=MAXSIZE-1 p->elem[p->top]
本章其它习题解答请参看本系网站。
第4章 串要求：逻辑结构和顺序存储表示算法（顺序串）
1、简述空串和空格串（或称空格字符串）的区别。
2、已知下列字符串
a=’THIS’,f=’A SAMPLE’,c=’GOOD’,d=’NE’,b=’ ‘,
s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2)))),
t=Replace(f,SubString(f,3,6),c),u=Concat(SubString(c,3,1),d),
g=’IS’,v=Concat(s,Concat(b,Concat(t,Concat(b,u))))
其中Concat(a,b)为将串b联接到串a之后，其他操作与教材P71页串的抽象数据类型中定义的操作一致，试问：s,t,v,StrLength(s),Index(v,g),Index(u,g)各是什么？
3、已知：s=’(XYZ)+*’,t=’(X+Z)*Y’。试用联接、求子串和置换等操作，将s转化为t。
4、编写算法，求串s所含不同字符的总数和每种字符的个数。
5、两个字符串相等的充要条件是 和 。
6、设字符串S1=’ABCDEF’,S2=’PQRS’,则运算S=CONCAT(SUB(S1,2,LEN(S2)),SUB(S1,LEN(S2),2))后的串值为 。
参考解答：
1、空串是指长度为零的串，而空格串是指串中字符是空格的字符串。
2、s= ‘THIS SAMPLE IS’ t=’A GOOD’ u=’ONE’ v=’THIS SAMPLE IS A GOOD ONE’ 14,3,0
3、Replace(s,Substring(s,3,5),Concat(Substring(3,6,1),Concat(Substring(s,4,2),Concat(Substring(s,7,1),Substring(s,3,1)))))
4、算法1：
void count(String T)
{ StrCopy(S,T);
m=Strlength(S);
num=0;
for(i=1;i<=m;i++)
{ n=1;
Substring(Sub1,S,i,1);
if(!StrCompare(Sub1,’#’))continue;
for(j=i+1;j<=m;j++)
{ Substring(Sub2,S,j,1);
if(!StrCompare(Sub1,Sub2))
n++;
}
Replace(S,sub1,’#’);
num++;
printf(Sub1,n);
}
printf(num);
}
5、长度相等 每一对应位置字符相等
6、BCDEDE
第5章 数组和广义表要点：
1、掌握数组元素存储位置的换算；
2、了解特殊矩阵地存储方法和元素存储位置计算；
3、了解广义表的长度、深度、head、tail等概念和操作和存储结构。
1、对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址是多少？
2、一个稀疏矩阵为，则对应的三元组表是什么？
3、设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有一个存储地址空间，则a85的地址是多少？
4、设有上三角矩阵（aij）n×n，将其上三角逐行存于数组B[m]中，使得B[m]= aij，且k=f1(i)+f2(j)+c。请写出函数f1，f2和常数c（f1和f2中不含常数项）。
5、求下列广义表操作的结果：
（1）Head((p,h,w));
（2）Tail((b,k,p,h));
（3）Tail(((a,b),(c,d)));
（4）Tail(Head(((a,b),(c,d))));
（5）Tail(Head(Tail(((a,b),(c,d)))));
6、假设稀疏矩阵A和B均以三元组顺序表作为存储结构，试写出矩阵相加的算法：
int AddMatrix(TSMatrix A,TSMatrix B,TSMatrix &C);
7、试编写一个以三元组形式输出用十字链表存储表示的稀疏矩阵中非零元素的下标及其元素值的算法：int Print(CrossList &M);
8、按照教材5.5节中图5.8所示结点结构，画出下列广义表的存储结构图，并求出它的深度。
（1）（（（）），a，（（b，c），（），d），（（（e））））
（2）（（（（a），b）），（（（），d），（e，f）））
9、设三角矩阵R=采用一维数组进行压缩存储，第一个元素为R11，存储位置为1，每个元素占一个存储位置，则R32的存储位置为几？
参考解答：
1、&A[0][0]+(i*n+j)*L //L为每一数据元素所占的字节数
2、((1,3,2),(2,1,3),(3,3,-1),(3,4,5))
3、&aij=&a00+(i*(i+1)/2+j)*L (i>=j) //&a00为第一个元素的地址，L为每一
&aij=&a00+(j*(j+1)/2+i)*L (j>=i) //元素所占存储空间则a85的地址为0+8*9/2+5=41
4、若行号与列号均从0开始，则元素aij前有i行，各行的非0元素个数从n到n-i+1，共有i*(n+n-i+1)/2个元素，aij所在的行中，其前面共有j个元素，但为0的元素有i个，不为0的元素个数则为j-i个，所以在上三角中aij前面共有i*(n+n-i+1)/2+ j-i个非0的元素，这些元素需要存储在一维数组B[]中，且在aij的前面，若一维数组的下标也从0开始，若用B[k]存储aij，则k= i*(n+n-i+1)/2+ j- i =(-i2-i+2in)/2+j
即： c=0
若下标均从1开始，则 c=-n
5、（1） p （2）（k，p，h） （3）（（c，d）） （4）（b） （5）（d）
6、Status AddMatrix(TSMatrix A,TSMatrix B,TSMatrix &C)
{ if(A.mu!=B.mu||A.nu!=B.nu)return ERROR;
C.mu=A.mu; C.nu=A.nu;
a=1,b=1,c=0;
while(a<=A.tu&&b<=B.tu)
{ i1= A.data[a].i; i2= B.data[b].i;j1= A.data[a].j;j2= B.data[b].j;
if(i1==i2&&j1==j2) //若两三元组的行列都相等，则元素相加
{ sum=A.data[a].e+B.data[b].e;
if(sum){C.data[++c].e=sum; C.data[c].i=i1;C.data[c].j=j1;}
a++; b++;
continue;
}
if(i1*A.nu+j1<i2*A.nu+j2) //若A中三元组的行列数小，则直接放如C中
{ C.data[++c].e=A.data[a].e; C.data[c].i=i1; C.data[c].j=j1;
++a;
}
else //若B中三元组的行列数小，则直接放如C中
{ C.data[++c].e=B.data[a].e; C.data[c].i=i2; C.data[c].j=j2;
++b;
}
}
while(a<A.tu) //若A中还有三元组，则复制到C中
{ C.data[++c].e=A.data[a].e; C.data[c].i=i1; C.data[c].j=j1;
++a;
}
while(b<B.tu) //若B中还有三元组，则复制到C中
{ C.data[++c].e=B.data[a].e; C.data[c].i=i2; C.data[c].j=j2;
++b;
}
C.tu=c;
return OK;
}
7、Status Print(CrossList &M)
{ OLink *p;
p=M.rhead;
for(i=1;i<=M.mu;i++)
{ q=p[i];
while(q){ //将第i行链各结点输出
printf(“(%d,%d,%d),,q->i,q->j,q->e); //输出一个结点所对应的三元组
q=q->right;
}
}
}
8、深度均为4，画图略。
9、&Rij=&R11+(i*(i-1)/2+j-1)*L=1+4=5
第6章 树要点：
1、掌握树和二叉树的逻辑结构和基本概念；
2、掌握二叉树的性质、二叉链存储、遍历及其相关算法；
3、二叉树与树、森林的转换。
练习：
1、假定有如图的树，则该树的度为,树的深度为,终端结点的个数为,单分支结点的个数为,双分支结点的个数为,C结点的双亲结点为,其孩子结点为 。
2、设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有 个。
3、对于一个具有n个结点的二叉树，当它为一棵 二叉树时具有最小高度，即为,当它为一棵单支树（除终端结点外，所有的结点都为单分支结点）时具有最大高度，即为 。
4、对于一棵具有n个结点的二叉树，当采用二叉链进行存储时，其二叉链表中的指针域的总数为 个，其中 个用于链接孩子结点,个空闲着。
5、一棵深度为k的满二叉树的结点总数为,一棵深度为k的完全二叉树的结点总数的最小值为,最大值为 。
6、由a，b，c三个结点构成的二叉树，共有 种不同的结构。
7、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[i]若有左子女，则左子女是,若有右子女，则右子女为 。
8、一棵二叉树如右。
（1）写出对此二叉树进行先序、中序、后序和层序遍历时得到的结点序列。
（2）画出其中序线索二叉树。
9、已知一棵二叉树的中序遍历序列为CDBAEGF，先序遍历序列为ABCDEFG，试问能不能确定唯一一棵二叉树，若能请画出该二叉树。
10、给定一棵用二叉链表示的二叉树，其根结点指针为t，试写出求二叉树叶子结点数目的算法：int leaf(BiTree t);
11、将以下森林转化为相应的二叉树。
参考解答：
1、3 4 6 1 1 A F，G
2、n+1 3、满,log2(n+1) 最大 n
4、2n n-1 n+1 5、2k-1,2k-1,2k-1
6、30 7、R[2i] R[2i+1]
8、（1）ABDFHCEG DFHBACGE HFDBGECA ABCDEFGH
（2）如右。
9、
10、int leaf(BiTree t)
{ BiTree a[10],p=t;
int i=0,n=0;
while(p)
{ if(p){ a[i++]=p; p=p->lchild;}
else
{ p=a[--i];
if(p->lchild==NULL&&p->rchild==NULL)n++;
p=p->rchild;
}
}
return n;
}
4、如右：
第7章 图
要点：
1、图的逻辑结构和基本概念；
2、图的存储表示；
练习：
1、具有n个顶点的完全有向图的弧数为 。
2、对如右无向图：
画出图的邻接表存储结构；
给出邻接矩阵；
指出每个顶点的度；
该图是连通图吗？。
写出从顶点A出发，按深度优先遍历图时得到的顶点序列。
写出从顶点A出发，按广度优先遍历图时得到的顶点序列。
3、对于一个具有n个顶点无向图，回答下面问题：
所有顶点的度数之和与所有边之间存在什么关系？
该图要连通全部顶点至少需要多少条边？
若该图为完全图，则包含多少条边？
4、若一个有向图的十字链表如上，试画出该有向图。
参考解答：
1、n*(n-1)
2、（1）如右：
（2）
（3）A：2 B：2 C：4 D：2 E：3 F：3 G：2 H：2
（4）是连通图 （5）ABDCEHGF （6） ABCDEFHG
3、（1）所有顶点的度数之和是所有边数的2倍；
（2）n-1 （3）n(n-1)/2
4、
第8章 查找要点：
1、各种查找表元素如何组织；
2、各种查找方法的特征；
3、查找算法。
练习：
一、填空题
1、假定在有20个元素的有序表上进行二分查找，则比较一次查找成功的元素个数为,比较两次查找成功的元素个数为,比较三次查找成功的元素个数为,比较四次查找成功的元素个数为,比较五次查找成功的元素个数为,平均查找长度为 。
2、在索引查找中，首先查找,然后再查找相应的 。
3、在一个10阶的B-树上，根结点中所含的关键字数目最多允许为 个，最少允许为 个。
4、一棵深度为h的B-树上，若根结点为第一层，则任一叶子结点所处的层数为,当向该B-树插入一个新关键字时，为检索插入位置需读取 个结点。
参考解答：
1,1 2 4 8 5 3.7
2、索引表 子表
3、9 1
4、h,h（若不包含叶子结点层则为h-1）
二、选择题
1、采用顺序检索的方法检索长度为n的线性表，则检索每个元素的平均比较次数为（ ）。
A）n B）n/2 C）(n+1)/2 D）(n-1)/2
2、已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素，检索成功的比较次数为（ ）。
A）1 B）2 C）3 D）4
3、在一个3阶的B-树上，每个结点包含的子树相同，最多为 个，最少为 个。
A）1 B）2 C）3 D）4
参考解答：1、C 2、B 3、C B
三、应用题
1、习题8.12
（1）ASL = (1*1+2*2+3*3+4*3+5*2+6*1)/12 = 42/12 = 3.5
（2）ASL = (1*1+2*2+3*4+4*5)/12 = 37/12 = 3.1
2、写出二分查找的递归算法。
int Bisearch(int a[],int base,int top,int key)
{ if(base>top)return(-1);
int mid=(base+top)/2;
if(a[mid]==key)return(mid);
else{
if(a[mid]>key)return(Bisearch(a,base,mid-1,key);
else return(Bisearch(a,mid+1,top,key);
}
}
3、试设计一个算法，求出指定结点在给定的二叉排序树中的层次。
int level(BiTree t,KeyType Key)
{ int i=0;
while(t)
{i++;
if(t->data.key==key)break;
else t=t->data.key>key?t->lchild:t->rchild;
}
return i;
}
4、习题8.2解答：
ASL = (1*1+2*2+3*4+4*3)/10 = 2.9
5、习题8.4解答：
（1）3阶B-树中每一个结点中最少棵子树，－1个元素，最多3棵子树，2个元素；
（2）元素的插入总是从叶子结点的上一层结点中操作。首先从根结点开始，找到应当插入的结点；如果插入后结点中的元素个数>2，则结点分裂，且将中间的元素提升到其双亲结点；若双亲结点中的元素个数>2，则分裂、提升……。B-树总是平衡的
……
6、习题8.5解答：H(k) = (3k)%11 22,41,53,46,30,13,01,67
0
1
2
3
4
5
6
7
8
9
10
22
41
30
01
53
46
39
67
30
01
39
67
ASLsucc = (1*4 + 2*3 + 6*1)/8 = 16/8 = 2
ASLunsucc = (1*3 +2*2 + 3 + 4 + 5 + 6 + 7 + 8)/11 = 42/11 = 3.8
7、习题8.13解答,9个叶子结点的3阶B-树至少有4个非叶子结点，10个叶子结点则至少有7个非叶子结点。
第9章 排序要点：
1、熟练掌握各种排序方法的排序过程；
2、掌握各种排序的算法（简单插入、交换、选择法，希尔排序，快速排序，堆排序）；
3、哪些排序算法是稳定排序，哪些是不稳定排序；
4、各排序算法的时空性能分析。
练习题：
一、填空题
1、若有一组记录（50，40，95，20，15，70，60，45，80），在进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 次；在进行直接选择排序时，第4次交换和选择后，未排序记录（即剩下的无序表）为 ；利用快速排序进行递归调用的深度最大为 ；进行堆排序时的初始堆的记录次序为 。
2、对于堆排序和快速排序来说，若初始记录接近正序或反序，则益选用 排序；若初始记录无序，则益选用 排序。
3、从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列中的正确位置上，此方法称为 排序；从未排序序列中挑选元素，并将其放入已排序序列的一端，此方法称为 排序；依次将每两个相临的有序表合并成一个有序表的排序方法叫做 排序；当两个元素比较出现反序（逆序）时就相互交换位置的排序方法叫做 ；每次把待排序的元素划分为左右两个子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，右区间中元素的关键字均大于等于基准元素关键字，则此排序方法叫做 。
参考解答：
1、3 50，60，70，80，95 4 95，80，70，45，15，50，60，40，20
2、堆 快速二、应用题
1、设待排序的记录用无头结点单链表作为存储结构，结点的类型名为linklist，为一结构体类型，包括指针域next，关键字域key和其它数据域，请写出选择排序算法：
void selesort(linklist *head) //head为指向表头的指针
{ linklist p,q,t,max,pre,new=NULL;
p=*head; //p指向首元结点
while(p) //当链表中还有结点
{ pre=max=p; //pre与t作为前后结点的指针，在中间的循环中联动
t=p->next; //先把p所指结点当作最大的结点
while(t){ if(t->key>max->key) //在余下的链表中找一个最大的
{q=pre; max=t;}
pre=t;
t=t->next;
}
if(max==p) //若最大结点为p所指，则将结点插入new链
{q=p->next;p->next=new;new=p;p=q;}
else //否则，将max所指结点插入new链
{q->next=max->next; max->next=new; new=max}
}
*head=new; //排序后的链表
}
2、写出在含有n个元素的堆中增加一个元素，并调整为堆的算法。（设待堆中的元素存储在一个一维数组中，数组元素为整型（即元素值就是关键字，且为整数）。
void heapinsert(int a[],int n,int x)
{ int i,k=n+1;
a[k]=x;
i=k/2;
while(i)
{ t=a[i];
if(k%2&&a[k]<a[k-1])k--;
if(t<a[k])
{ a[i]=a[k]; a[k]=t;
k=i; i=i/2;}
else break;
}
3、若待排序的元素序列为（48，89，56，35，43，83），写出利用快速排序的方法，以第一个元素为基准得到的一次划分的结果。
（43，35，48，56，89）
4、判断以下序列是否为堆？，如果不是，则按筛选法把它调整为堆。
（1）（100，86，48，73，35，39，42，57，66，21）；
（2）（12，70，33，65，24，56，48，92，86，33）；
（3）（103，97，56，38，66，23，42，12，30，52，6，20）。
4、（1）是堆
（2）不是堆，调整后为：（92，86，56，70，33，33，48，65，12，24）
（3）是堆期中考试参考答案判断题（每题1分，共10分，错的打×,对的打√）
1
2
3
4
5
6
7
8
9
10
×
×
√
√
×
√
×
√
×
×
填空题（共20空，每空2分,共40分）
【1】 H->next == NULL 【2】 p->next == L
【3】 p->next 【4】 s
【5】 p->next 【6】 s->data
【7】 t 【8】 16
【9】 字符串的长度相等 【10】 对应位置上的字符相等
【11】 ‘BCDEDE’ 【12】 GetHead( GetHead( GetTail( LS )))
【13】 5 【14】 3
【15】 ((1,2,-3),(1,4,1),(2,1,2),(3,2,5)) 【16】 x + ((i-1)*n+j-1)*t
【17】 x+((j-1)*m+i-1)*t 【18】 线性
【19】 栈顶 【20】 栈底
三、选择题（每题1分，共10分）
1
2
3
4
5
6
7
8
9
10
A
A
D
C
D
D
B或D
A
D
D
四、简答题（每题2分，共10分）
1、数据的逻辑结构是指数据元素之间的逻辑关系描述，通常有哪四种基本的结构？
答：集合结构、线性结构、树型结构和图（网状）结构
2、在数据结构的抽象数据类型（ADT）描述中一般分哪三个主要部分来描述？
答：数据元素、数据元素的关系和操作集。
3、算法有哪五个基本特性？
答：确定性、有限性、可行性、0个或多个输入、一个或多个输出。
4、简述算法的功能.
答：将栈中的元素逆置。
5、简述空串与空格串的区别。
答：空串是指长度为0的字符串，而空格串是指组成串的字符是空格的串。
五、算法填空题（共20空，每空1.5分，共30分）
【1】 j 【2】 k
【3】 p = p->next 【4】 p->next
【5】 q->next或p->next->next 【6】 （pQ->rear+1）%MAXSIZE
【7】 1 【8】 pQ->front
【9】 0 【10】 S.top==-1或IsEmpty(S)
【11】 ch1==ch2 【12】 S.top==-1或IsEmpty(S)
【13】 return(0) 【14】 T.len
【15】 S.ch[i]或ch1 【16】 k
【17】 j 【18】 p
【19】 root->LChild 【20】 root->RChild
