第1章绪论 要求: 1、基本概念:数据结构、数据元素等 2、算法及其时间复杂度; 3、数据结构的抽象数据类型表示 参考练习: 1、试设计将数组inta[n中所有奇数移到偶数之前的算法,要求不能使用其它新数组,且时间复杂 度为0(n)。 参考解答: void shift(int a[, int n) int i=0, j=n-l,t while(inext (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: 1 (7) while(p->next!=Q)P=P->next
1 第 1 章 绪论 要求： 1、基本概念：数据结构、数据元素等； 2、算法及其时间复杂度； 3、数据结构的抽象数据类型表示； 参考练习： 1、试设计将数组 int a[n]中所有奇数移到偶数之前的算法，要求不能使用其它新数组，且时间复杂 度为 O(n)。 参考解答： void shift(int a[],int n) { int i=0,j=n-1,t; while(inext; (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 (13)L=L->next (14)free(Q) 参考解答:a:1 2、习题2.3参考解答 3、习题24参考解答 nt Insert(SeqList *pL, ElemType x) int 1 if(pL->last >= MAXSIZE-1) return i pL->last while(pL->elem[i]>x&&i>=0) pL->elem[i+1]= pL->elem[il pL->elem[i+1]=x: pL->last + 1 return (1) 4、试写一算法,在无头结点的单链表上实现线性表元素插入操作 int Insert( Linklist*pL,inti, ElemType b);并将此算法和带头结点的单链表的插入操作算法进 行比较 参考解答 int Insert(LinkList *pL, int i, ElemType b) I int i, j,n=0 while(p){n++;p=p->next;}/)用n统计链表的长度 f(idata=b S->next=*pL *pL=s; return OK: I p=xpL j=1 //余下情况肯定i1,且L不为空 while(jnext;}//找到插入位置的前一个结点,用p指向 s=(LinkList)malloc(sizeof(Node)) s->next=p->next: s->data=b; p->next=s return 1 对带有头结点的链表来说,无论在什么位置插入元素,指向头结点的指针的指向关系都不会改变, 这样只需要知道头结点的存储地址(指向头结点的指针),就可以实现对链表的操作;而无头结点的 链表在最前面进行插入或删除操作时,指向首元结点的指针均会改变,所以需要把指向首元结点的指
2 (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(in+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(jnext;} //找到插入位置的前一个结点，用 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 指向首元结点。 参考解答: pede struct Node f ElemType data struct Node *pre, * next void double( Linklist l)/L为指向单向循环链表中任一结点的指针 I LinkList p=L: while(p->next! =L) p->next->pre=p;//使p指向结点的后继结点的前驱指针指向p所指结点 L->pre=p;/L所指结点的前驱结点为p所指结点 6、试以循环链表作稀疏多项式的存储结构,编写求其一阶导数的算法,要求利用原多项式中的结点 空间存放导数多项式,同时释放所有无用结点(系数为0)。 参考解答 typedef struct Node i float coef, index;//coef表示系数, index表示该项的指数 struct Node next 3 Node, *PolyList void derivative(PolyList L) i PolyList p, g=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)[ g->next=p->next; free(p): p=q->next: I else[ g=p: p=p->next: 1 7、在线性表的顺序存储中,元素之间的逻辑关系是通过存储位置相临决定的;在线性表的链接 存储中,元素之间的逻辑关系是通过结点的指针域决定的 8、线性表、栈和队列都是线性结构,可以在线性表的_任意位置插入和删除元素:对于栈只 能在一端插入和删除元素,可以进行插入和删除操作的一端叫栈顶_,另一端叫栈底_:对于队列 能插入元素的一端称队尾_’能删除元素的一端称_队头 9、线性表采用链式存储时,其数据元素的存储地址_D A)必须是连续的 B)部分地址必须是连续的 C)一定是不连续的 D)连续与否均可以 10、线性表的链接存储有利于 算 A)插入 B)读表元素C)查找 D)定位 11、线性表是 A)一个无限序列,可以为空B)一个有限序列,不可以为空 C)一个有限序列,可以为空D)一个无限序列,不可以为空
3 针变量的地址作为参数传递给被调函数，即使用二级指针。 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= t=p->date p->data= s->data 参考解答:D> next s->data t 13、简述以下算法的功能 typedef struct Node ElemType data struct Node * next 3 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 >next=NULL return 参考解答:将L所指的含有两个以上结点的链表的首元结点移到链尾,原第二个结点成为首元结点。 14、已知线性表的元素是无序的,且以带头结点的单链表作为存储结构。设计一个删除表中所有值小 于链表中最大值max但大于链表中最小值min的元素结点的算法。 参考解答: void Delete(LinkList L) I LinkList max, min, p, g if(p->next&&p->next->next) if(p->next->data>p->next->next->data)I max=p; min=p->next: 1 else I max=p->next: min=p: 1 p=p->next->next i if(p->next->data>=min->next->data&&p->next->datanext->data) [g=p->next free(a): continue if(p->next->datanext->data I g=min->next min->next=g->next free(g) min-p p=p->next: continue: if(p->next->data>max->next->data)
4 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->datanext->data) { q=p->next; p->next=q->next; free(q);continue; } if(p->next->datanext->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(g) p=p->next: continue 15、某家电超市对仓库中的电视机信息按价格从低到高构成一个单链表存于计算机中,链表结点的结 构体定义如下,链表为带头结点的链表。若现在又新到m台价格为n的电视机入库,试编写相应算法 edef struct Vnode i float price int num: struct Vnode米next I VnOde, *TvList int AddY( TvList l, float m,intn){..}//L为指向头结点的指针 参考解答: int AddT (TvList L, float m, int n TvList p=L, q while(p->next&&p->next->pricenext (TvList)malloc(sizeof(VnOde)) g->price=m: q->numn p->next=q else p->next->numt=n 本章其它习题解答请参看本系网站。 第3章栈和队列 要求:逻辑结构和算法 1、在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以top作为栈顶指针, 则当做出栈处理时,top变化为 A)top不变 B)top= 2、在具有n个单元的顺序存储的循环队列中,假定 front和rear分别为队头指针和队尾指针,则判 断队满的条件为 %n=front B)front%n+1=rear C) rear%n=front D)rear%n+l=front 3、一个中缀算术表达式为1+(3-x)*y,则其对应的后缀算术表达式为 A)13+x-y*B)13x+y*C)13x-y*+D)13xy一+* 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分别为队首和队尾指针,则删除一个结点的操作应执
5 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->pricenext; 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-> 6、写出下列程序段的输出结果(其中栈的元素类型 SElemType为char) i Stack S; char y: InitStack(S) 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): 1 7、写出以下程序段的输出结果(队列中的元素类型 QElemType为char) id @ ueue Q; char x=’e Queue(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(, y): printf (y): 1 printf(x) 8、若栈用顺序存储表示,其栈的元素类型为整型,类型定义如下 #define maXsize 1000 typedef struct i int elem[ MAXSIZE];/用来存放栈元素的数组,下标从0开始 Int top //指向栈顶位置的域,栈底为位置0 STack 请补全以下栈操作函数:(用C语言) (1)判断栈S是否为空栈:若为空,则返回1,不为空则返回0 int StackEmpty (Stack S) else (2)入栈操作:若栈满,则返回0,不满,则入栈,返回1 int push( Stack*p,inte)//p为指向栈的指针,e为待入栈的元素 ) return(0);//栈满,则返回0 =e;//栈 p->top+=l /栈顶位置变化 return (1) 、简述栈、队列和线性表的差别和联系。 参考解答:1、C2、D3、C4、C5、A6、 stack7、char return(O p>top>=MAXSIZE-1 D->elemlp->topl 本章其它习题解答请参看本系网站
6 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='600D’,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, Strength(s), Index(v,g), Index(u,g)各是什么? 3、已知:s=(XYZ)+*,t=(X+Z)*Y。试用联接、求子串和置换等操作,将s转化为t 4、编写算法,求串s所含不同字符的总数和每种字符的个数 5、两个字符串相等的充要条件是 和 设字符串S1= ABCDEF,S2=PQRS°’,则运算S= CONCAT(SUB(S1,2,LEN(S2),SUB(S1,LEN(S2),2)) 后的串值为 参考解答: 1、空串是指长度为零的串,而空格串是指串中字符是空格的字符串 2、s=‘ THIS SAMPLE IS’t= A GOODU='ONE’v= THIS SAMPLE IS A GOOD ONE’14,3,0 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) i StrCopy (s, T) mFStrlength(S for(i=l: i<=m: i++) Substring(Sub1, S, i, 1) if(! StrCompare(Subl, #'))continue I Substring (Sub2, S, j, 1) if(!StrCompare(Sub1, Sub2)) Replace(S,sub1,"#”) nutt printf(Sub1, n) printf(num) 5、长度相等每一对应位置字符相等 第5章数组和广义表 要点 7
7 第 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]的地址是 多少? 0020 3000 2、一个稀疏矩阵为 00-15|,则对应的三元组表是什么? 3、设有一个10阶的对称矩阵A,采用压缩存储方式以行序为主序存储,a为第一个元素,其存储地 址为0,每个元素占有一个存储地址空间,则as5的地址是多少? 4、设有上三角矩阵(a;)axn,将其上三角逐行存于数组B[m中,使得B[m]=a,且k=f(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、试编写一个以三元组形式输出用十字链表存储表示的稀疏矩阵中非零元素的下标及其元素值的算 ik: int Print(Crosslist &M) 8、按照教材5.5节中图5.8所示结点结构,画出下列广义表的存储结构图,并求出它的深度。 (1)((()),a,((b,c),(),d),(((e))) (2)(((a),b)),(((),d),(e,f)) 31000 43000 9、设三角矩阵R= 采用一维数组进行压缩存储,第一个元素为R1,存储位置为1 750 每个元素占一个存储位置,则R2的存储位置为几? 参考解答: 1、&A[O][0]+(i*n+j米/L为每一数据元素所占的字节数 2、(1,3,2),(2,1,3),(3,3,-1),(3,4,5)) 3、&a;=&a+(i*(i+1)/2+j料(i>=j)//&a00为第一个元素的地址,L为每 &a;=&ao+(j*(j+1)/2+i)*L(j>=i)//元素所占存储空间 则a85的地址为0+8*9/2+5=41 4、若行号与列号均从0开始,则元素a;前有i行,各行的非0元素个数从n到n-i+1,共有 i*(n+n-i+1)/2个元素,a;所在的行中,其前面共有j个元素,但为0的元素有i个,不为0的元素 个数则为j-i个,所以在上三角中a前面共有i*(n+n-i+1)/2+j-i个非0的元素,这些元素需要存 储在一维数组B[中,且在a的前面,若一维数组的下标也从0开始,若用B[k]存储ai,则k= i*(n+n-i+1)/2+j-i=(-i2-i+2in)/2+j 即:f1(1)=(-i+2n-1)f2()=jc=0
8 1、掌握数组元素存储位置的换算； 2、了解特殊矩阵地存储方法和元素存储位置计算； 3、了解广义表的长度、深度、head、tail 等概念和操作和存储结构。 1、对于一个二维数组 A[m][n]，若按行序为主序存储，则任一元素 A[i][j]相对于 A[0][0]的地址是 多少？ 2、一个稀疏矩阵为 − 0 0 0 0 0 0 1 5 3 0 0 0 0 0 2 0 ，则对应的三元组表是什么？ 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= 10 14 69 91 58 36 75 0 43 0 0 0 31 0 0 0 采用一维数组进行压缩存储，第一个元素为 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 =(-i 2 -i+2in)/2+j 即： ( 2 1) 2 ( ) 1 = −i + n − i f i f ( j) = j 2 c=0
若下标均从1开始,则f()=(-1+2n+1)f()=jc=n 5、(1)p(2)(k,p,h)(3)((c,d)(4)(b)(5)(d) 6, Status AddMatrix(TSMatrix A, TSMatrix B, TSMatrix &C) I 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(ai,q->j,q->e);/输出一个结点所对应的三元组 g=q->right 8、深度均为4,画图略
9 若下标均从 1 开始，则 ( 2 1) 2 ( ) 1 = −i + n + i f i f ( j) = j 2 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(ai,q->j,q->e); //输出一个结点所对应的三元组 q=q->right; } } } 8、深度均为 4，画图略
9、&R3=&R1+(i*(i-1)/2+j1)*=1+4=5 第6章树 要点: 1、掌握树和二叉树的逻辑结构和基本概念 2、掌握二叉树的性质、二叉链存储、遍历及其相关算法 B)(C)(D 、二叉树与树、森林的转换。 练习: (E(R (G 1、假定有如图的树,则该树的度为 树的深度为,终端结点 的个数为 ,单分支结点的个数为 双分支结点的个数O 为 ,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 eaf(BiTree t) 11、将以下森林转化为相应的二叉树 F G 参考解答: l、34611AF,G 2、n+1 3、满,log2(n+1)最大 4、2nn-1n+1 7、R[2i] R[2i+1]
10 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、2 k -1, 2k-1 , 2k -1 6、30 7、R[2i] R[2i+1]