发布时间 : 星期五 文章太原理工大学数据结构试题库及答案更新完毕开始阅读6e1019600029bd64793e2c81
int ListInsert(LinkList L,int i,ElemType e){ LNode *p,*s;int j; p=L;j=0;
while((p!=NULL)&&(j
if(p==NULL||j>i-1) return ERROR; s=(LNode *)malloc(sizeof(LNode)); s->data=e;
s->next=p->next; p->next=s; return OK; }/*ListInsert*/
3、函数ListDelete_sq实现顺序表删除算法，请在空格处将算法补充完整。
int ListDelete_sq(Sqlist *L,int i){ int k;
if(i<1||i>L->length) return ERROR;
for(k=i-1;k
L->slist[k]=L->slist[k+1];
--L->Length; return OK; }
4、函数实现单链表的删除算法，请在空格处将算法补充完整。 int ListDelete(LinkList L,int i,ElemType *s){ LNode *p,*q; int j; p=L;j=0;
while((p->next!=NULL)&&(j
if(p->next==NULL||j>i-1) return ERROR; q=p->next; p->next=q->next; *s=q->data; free(q); return OK; }/*listDelete*/ 5、写出算法的功能。
int L(head){ node * head; int n=0; node *p; p=head;
while(p!=NULL) { p=p->next;
n++; }
return(n); }
答案：求单链表head的长度 五、综合题
1、编写算法，实现带头结点单链表的逆置算法。 答案：void invent(Lnode *head)
{Lnode *p,*q;
if(!head->next) return ERROR;
p=head->next; q=p->next; p->next =NULL; while(q)
{p=q; q=q->next; p->next=head->next; head->next=p;} }
2、有两个循环链表，链头指针分别为L1和L2，要求写出算法将L2链表链到L1链表之后，且连接后仍保持循环链表形式。 答案：void merge(Lnode *L1, Lnode *L2)
{Lnode *p,*q ;
while(p->next!=L1)
p=p->next; while(q->next!=L2)
q=q->next;
q->next=L1; p->next =L2; }
3、设一个带头结点的单向链表的头指针为head，设计算法，将链表的记录，按照data域的值递增排序。
答案：void assending(Lnode *head)
{Lnode *p,*q , *r, *s;
p=head->next; q=p->next; p->next=NULL; while(q)
{r=q; q=q->next;
if(r->data<=p->data)
{r->next=p; head->next=r; p=r; } else
{while(!p && r->data>p->data)
{s=p; p=p->next; } r->next=p; s->next=r;} p=head->next; }
}
4、编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。 答案：
void linklist_c(Lnode *head) {Lnode *p; p=head;
if(!p) return ERROR;
while(p->next!=NULL)
p=p->next; p->next=head; }
设单链表的长度（数据结点数）为N，则该算法的时间主要花费在查找链表最后一个结点上（算法中的while循环），所以该算法的时间复杂度为O（N）。
5、已知head为带头结点的单循环链表的头指针，链表中的数据元素依次为（a1，a2,a3,a4,?,an）,A为指向空的顺序表的指针。阅读以下程序段，并回答问题： （1）写出执行下列程序段后的顺序表A中的数据元素； （2）简要叙述该程序段的功能。
if(head->next!=head) {
p=head->next; A->length=0;
while(p->next!=head) {
p=p->next;
A->data[A->length ++]=p->data; if(p->next!=head)p=p->next; }
}
答案：
(1) (a2, a4, ?, ) (2)将循环单链表中偶数结点位置的元素值写入顺序表A
6、设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 答案：
void Insert_sq(Sqlist va[], ElemType x) {int i, j, n;
n=length(va[]); if(x>=va[i])
va[n]=x; else
{i=0;
while(x>va[i]) i++; for(j=n-1;j>=I;j--)
va[j+1]=va[j]; va[i]=x; } n++; }
7、假设线性表采用顺序存储结构，表中元素值为整型。阅读算法f2，设顺序表L=(3,7,3,2,1,1,8,7,3),写出执行算法f2后的线性表L的数据元素，并描述该算法的功能。
void f2(SeqList *L){
int i,j,k; k=0;
for(i=0;i
for(j=0;j
if(k!=i)L->data[k]=L->data[i];
k++; } }
L->length=k;
}
答案：
(3,7,2,1,8) 删除顺序表中重复的元素
8、已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。 答案：
void Delete_list(Lnode *head, ElemType x, ElemType y) {Lnode *p, *q;
if(!head) return ERROR;
p=head; q=p; while(!p)
{if(p->data>x) && (p->data if(p==head) {head=p->next; free(p); p=head; q=p; } else {q->next=p->next; free(p); p=q->next; } else {q=p; p=p->next; } } } 9、在带头结点的循环链表L中，结点的数据元素为整型，且按值递增有序存放。给定两个整数a和b，且a 第三章 栈和队列 一、选择题 2、判断一个循环队列Q（最多n个元素）为满的条件是（c ）。