数据结构试题大题编程及参考答案

数据结构考试题参考答案1、设顺序表 L 中的数据元素递增有序。试写一算法，将数据元素 x 插入到顺序表 L 的适当位置，以保持该表的有序性。解：存储结构为：typedef struct SeqList{ DataType *data； int MaxLen; int len;｝SeqList;算法如下:void insertLx(SeqList ＆L, DataType x)｛ if(L。len==L。maxlen） return； int i=L。len-1；while（i〉=0 && x〈L。data［i]）｛ L。data[i+1]=L.data[i]; i=i—1；｝L.data［i+1］=x; L.len++；}2、试写一个算法，在带头结点的单链表 L 的元素 x 前插入一个结点 y。解：存储结构如下：typedef struct Lnode{ElemType data； struct Lnode *next；}Lnode， *LinkList;算法如下：void insert_y_before_x（LinkList L, ElemType x， ElemType y）｛ Lnode ＊q, ＊p=L； while（p—>next && p—〉next—>data！=x） p=p—〉next; //找 x 的前驱结点 p;if（！p—>next） return; // 若不存在结点 x,则返回；q=new Lnode；q-〉data=y； q—>next=p—〉next; p—〉next=q；｝3、试写一个算法，统计带头指针的单链表 L 的元素个数.解:存储结构如下：typedef struct Lnode{ElemType data; struct Lnode ＊next；}Lnode， ＊LinkList;算法如下：int length（LinkList L)｛ int len=0；Lnode *p=L;while(p) { len++； p=p-〉next； ｝return len;}注：假如单链表是带头结点的，则算法如下：int length（LinkList L）{ int len=0;Lnode *p=L->next；；while(p) { len++； p=p-〉next； }return len;｝4、试写一个算法，在带头结点的单链表 L 的第 k 个结点后插入一个结点 x。解:存储结构如下：typedef struct Lnode{ElemType data; struct Lnode ＊next；｝Lnode， ＊LinkList;算法如下：void insert_after_k( LinkList L， int k， ElemType x)｛ if（k〈0） return； Lnode ＊q, *p=L;int i=0；while（p &＆ i〈k) {i++; p=p-〉next; ｝ //找到第 k 个结点 p;if（！p） return; //若不存在第 k 个结点，则返回;q=new Lnode； q—〉data=x; q—〉next=p->next； p—〉next=q；｝注:假如是在 L 的第 k 个结点前插入一个结点，则找第 k—1 个结点 p，然后插入。５、试写一个算法,在带头结点的单链表Ｌ中删除所有的数据元素为 x 的结点。解：存储结构如下：typed...