当前位置:文档之家› 算法与数据结构 张乃孝 前三章习题课

算法与数据结构 张乃孝 前三章习题课


r–>next=p; r=p; } if (r!=NULL) r–>next=NULL; return(head); }
linklist createlistr1( ){ char ch; linklist head=(linklist)malloc(sizeof(listnode)); listnode *p,*r r=head; while((ch=getchar( ))!=‵\n′{ p=(listnode*)malloc(sizeof(listnode)); p–>data=ch; r–>next=p; r=p; } r–>next=NULL; return(head); }
的指针。若链表中附设头结点,则不管线性表是否为空表, 头指针均不为空,否则表示空表的头指针为空。
2.1 单项选择题 1. 一个向量(即一批地址连续的存储单元)第一个元素的存储 地址是100,每个元素的长度为2,则第5个元素的地址是__ __。 B A. 110 B. 108 C. 100 D. 120 A 2. 线性表的顺序存储结构是一种__ _的存储结构,而链式存储 C 结构是一种__ _的存储结构。 A.随机存取 B.索引存取 C.顺序存取 D.散列存取 B 3. 线性表的逻辑顺序与存储顺序总是一致的,这种说法__ _。 A. 正确 B. 不正确 4. 线性表若采用链式存储结构时,要求内存中可用存储单元的 D 地址__ _。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以
L 指向无头结点的线性链表,写出删除链表中从下标为I的结 点开始的连续k个结点的算法
Linklist Del (linklist L,int I,int k) {pnode p,q; int j=0; p=L; while(p->link!=NULL&&j<i) {p=p->link;j++} for(j=1;j<=k;j++) {q=p->link; p->link=q->link; free(q); } Return(L);}
删除单链表中值相同的多余结点
Diff_link(Linklist llist) {pnode p,q,r; p=llist->link; while( p!=NULL) {q=p; r=q->link; while(r!=NULL) {if(r->info==p->info) {t=r->link; q->link=t; free(r); r=t; }
如果我们在链表的开始结点之前附加一个结点, 并称它为头结点,那么会带来以下两个优点: a、由于开始结点的位置被存放在头结点的 指针域中,所以在链表的第一个位置上的操作就 和在表的其它位置上的操作一致,无需进行特殊 处理;
b、无论链表是否为空,其头指针是指向头结点
在的非空指针(空表中头结点的指针域为空),
5. 在以下的叙述中,正确的是__C_。 线性表的顺序存储结构优于链表存储结构 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况 线性表的链表存储结构适用于频繁插入/删除数据元素的情况 线性表的链表存储结构优于顺序存储结构 6. 每种数据结构都具备三个基本运算:插入、删除和查找,这 A 种说法__ _。 A. 正确 B. 不正确 A 7. 不带头结点的单链表head为空的判定条件是____。 A. head= =NULL B. head->next= =NULL C. head->next= =head D. head!=NULL B 8. 带头结点的单链表head为空的判定条件是____。 A. head= =NULL B. head->next= =NULL C. head->next= =head D. head!=NULL
首元结点、头结点、头指针的区别
首元结点:链表中存储线形表中第一个数据元素的结点
头结点:在链表首元结点之前附设一个结点。该结点的数 据域不存储数据元素,其作用是为了对链表进行操作时,
可以对空表、非空表的情况以及对首元结点进行统一处理。点)
的指针。若链表中附设头结点,则不管线性表是否为空表, 头指针均不为空,否则表示空表的头指针为空。
说明:第一个生成的结点是开始结点,将开始
结点插入到空表中,是在当前链表的第一个位
置上插入,该位置上的插入操作和链表中其它
位置上的插入操作处理是不一样的,原因是开
始结点的位置是存放在头指针(指针变量)中,
而其余结点的位置是在其前趋结点的指针域中。 算法中的第一个if语句就是用来对第一个位置 上的插入操作做特殊处理。
linklist creater( ) { char ch; linklist head; listnode *p,*r; //(, *head;) head=NULL;r=NULL; while((ch=getchar( )!=‵\n′){ p=(listnode *)malloc(sizeof(listnode)); p–>data=ch; if(head==NULL) { head=p; r=head;} else
已知线性表A的长度为n,并且采用顺序存储结构,写一 算法删除线性表中所有值为X的元素
Del (sqlist L,datatype x) {int I,j; for(I=0;i<L->n;I++) if(L->data[i]==x) {for(j=I;j<L->n;j++) L->data[j]=L->data[j+1]; L->n--; } }
(2)设L是不带头结点的单链表。 算法如下: int Length_LinkList2 (LinkList L) { Lnode * p=L; int j; if (p==NULL) return 0; /*空表的情况*/ j=1; /*在非空表的情况下,p所指的是第一个结点 */; while (p->next ) { p=p->next; j++ } return j; }
首元结点、头结点、头指针的区别
习题选讲 栈与队列
树与二叉树
首元结点、头结点、头指针的区别
首元结点:链表中存储线形表中第一个数据元素的结点
头结点:在链表首元结点之前附设一个结点。该结点的数 据域不存储数据元素,其作用是为了对链表进行操作时,
可以对空表、非空表的情况以及对首元结点进行统一处理。
头指针:是指向链表中第一个结点(头结点或首元结点)
else {q=r;r=r->link;} } P=p->link }}
b、无论链表是否为空,其头指针是指向头结点
在的非空指针(空表中头结点的指针域为空),
因此空表和非空表的处理也就统一了。
求表长 算法思路:设一个移动指针p和计数器j,初始化后 ,p所指结点后面若还有结点,p向后移动,计数器 加1。 (1)设L是带头结点的单链表(线性表的长度不包括头结 点)。 算法如下: 加头没加尾 int Length_LinkList1 (LinkList L) { Lnode * p=L; /* p指向头结点*/ int j=0; while (p->next) { p=p->next; j++ } /* p所指的是第 j 个结点*/ return j; }
12. 在一个单链表中,若p所指结点不是最后结点,在p之后插 B 入s所指结点,则执行____。 A. s->next=p; p->next=s; C. s->next=p->next; p=s; B. s->next=p->next; p->next=s; C. p->next=s; s->next=p;
该算法只是对链表中顺序扫描一边即完成了倒置,所以 时间性能为O(n)。
2.22 void LinkList_reverse(Linklist &L)//链表的就地逆 置;为简化算法,假设表长大于2
Rev(linklist L) //带头结点的单链表 {Pnode p,q,r; p=L->link;if(p==NULL) return; q=p->link; if(q==NULL) return; r=q->link; while(r!=NULL) {q->link=p; p=q; q=r; r=r->link;} q->link=p; L->link->link=NULL; L->link=q; }
C 9. 非空的循环单链表head的尾结点(由p所指向)满足____。 A. p->next= =NULL B. p= =NULL C. p->next= =head D. p= =head 10. 在双向循环链表的p所指结点之后插入s所指结点的操作是 D ____。 A. p->right=s; s->left=p; p->right->left=s; s->right=p->right; B. p->right=s; p->right->left=s; s->left=p; s->right=p->right; C. s->left=p; s->right=p->right; p->right=s; p->right->left=s; D. s->left=p; s->right=p->right; p->right->left=s; p->right=s; 11. 在一个单链表中,已知q所指结点是p所指结点的前驱结点, C 若在q和p之间插入s结点,则执行____。 A. s->next=p->next; p->next=s; B. p->next=s->next; s>next=p; C. q->next=s; s->next=p; D. p->next=s; s->next=q;
相关主题