第1章绪论 要求: 1、基本概念:数据结构、数据元素等 2、算法及其时间复杂度; 3、数据结构的抽象数据类型表示 参考练习: 1、试设计将数组inta[n中所有奇数移到偶数之前的算法,要求不能使用其它新数组,且时间复杂 度为0(n)。 参考解答: void shift(int a[, int n) int i=0, j=n-l,t while(i<j i while(ali]%2==1)i++ while(alj]%2==0) if(i<jIt=ali]: ali]=a[j]: alj]=t: I 2、数据的基本单位是C A)数据项B)数据类型C)数据元素D)数据变量 3、下面程序段的时间复杂度为C for(j=0; j<n; j++) A[i][j]=i* A)0(m2) B)0(n2) C)0(m×n) D)0(m+n) 4、数据结构用二元组表示时,它包括_数据元素的有限集D和D上关系的集合R。 5、数据结构是一门研究_非数值计算的程序设计问题中计算机操作对象以及它们之间的关系和 操作等的学科。 第2章线性表 要求 1、掌握线性表的逻辑结构 2、线性表的顺序存储表示及其算法 3、线性表的链式存储表示及其算法; 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: 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(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、 掌握线性表的逻辑结构； 2、 线性表的顺序存储表示及其算法； 3、 线性表的链式存储表示及其算法； 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 (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(i<1|lin+1) return0;/判断插入位置是否合法 if(i==1){ //对第一位置单独处理 s=(LinkList)malloc(sizeof(Node)) s->data=b S->next=*pL *pL=s; return OK: I p=xpL j=1 //余下情况肯定i1,且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 对带有头结点的链表来说,无论在什么位置插入元素,指向头结点的指针的指向关系都不会改变, 这样只需要知道头结点的存储地址(指向头结点的指针),就可以实现对链表的操作;而无头结点的 链表在最前面进行插入或删除操作时,指向首元结点的指针均会改变,所以需要把指向首元结点的指
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(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 指向首元结点。 参考解答: 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->data<=max->next->data) [g=p->next free(a): continue if(p->next->data<min->next->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->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(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->price<m)p=p->next (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->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 分别为队首和队尾指针，则删除一个结点的操作应执 行