文档介绍：数据结构试题大题编程及参考答案
数据结构试题大题编程及参考答案
数据结构试题大题编程及参考答案
数据结构考试题参考答案
1、设顺序表L中的数据元素递增有序。试写一算法，将数据元素ｘ插入到顺序表L的适当位置，以保持该表的有序性。
解：存储结构为:
typｅdｅf struct SeqList
｛ DaｔaTyｐe ＊daｔa;
iｎt MaxＬeｎ;
ｉｎt len；
｝SeqＬist;
算法如下:
voiｄ insertLｘ（ＳeｑLｉst &L, DataTypｅ x）
｛ if（L。ｌen==) retuｒn；
ｉnt i=L。len—1;
ｗｈile(ｉ〉=0 &＆ x<[i］)
{ ［i+1]=L．data[i]; i=i-1；｝
L。datａ[i+1］=x； ＋+;
}
2、试写一个算法，在带头结点的单链表L的元素x前插入一个结点y。
解：存储结构如下：
typedef sｔｒuct Lnode
{EｌemＴyｐe dａｔa；
strｕct Lnode ＊ｎexｔ；
｝Lnode, ＊LｉｎkLiｓt；
算法如下:
voｉd insert_y_bｅfｏre＿x（LinkLｉｓt L， ElemTｙpe x， ElｅmTypｅ y）
{ Lnoｄe ＊q， *p＝Ｌ；
ｗhile(p－〉next &＆ p->next-〉dａta!=x） p=p->neｘｔ； //找ｘ的前驱结点p；
ｉf（！p－＞nｅｘｔ） ｒeｔurn； ／/ 若不存在结点x,则返回;
ｑ=ｎeｗ Ｌnode;
ｑ－〉dａta=y; q－＞ｎext=p—＞nｅxｔ； p－＞next=ｑ；
｝
３、试写一个算法,统计带头指针的单链表L的元素个数。
解:存储结构如下：
数据结构试题大题编程及参考答案
数据结构试题大题编程及参考答案
数据结构试题大题编程及参考答案
typｅdef ｓtruct Lnｏdｅ
｛EleｍTyｐe data；
ｓtruct Lｎode *neｘt；
｝Lｎode， *LｉｎkLiｓt;
算法如下：
ｉｎｔ ｌengtｈ（LｉnkLｉst L）
{ int ｌen=0；
Lｎoｄe *p=L；
ｗhilｅ(p) { lｅｎ+＋； ｐ＝p-〉neｘｔ; }
return len;
｝
注:如果单链表是带头结点的,则算法如下：
inｔ lenｇtｈ（LｉｎkList L)
｛ iｎt leｎ=0;
Lnode *p=L－>next；；
while（p) ｛ leｎ++; p＝p—＞neｘt; ｝
retuｒn len；
}
4、试写一个算法，在带头结点的单链表L的第ｋ个结点后插入一个结点x。
解：
存储结构如下：
typedef stｒuct Lｎode
{ElｅmTyｐe ｄatａ；
struct Lnodｅ ＊ｎext;
}Lｎodｅ, *LinkLｉｓt;
算法如下：
ｖｏid inserｔ＿afｔｅr_k（ LiｎｋＬｉst L, inｔ k, ElemＴype x)
｛