完整数据结构算法设计题

一、算法设计题1o设二叉树bt采用二叉链表结构存储试设计一个算法输出二叉树中所有非叶子结点，并求出非叶子结点的个数【答案】int count=0;void a Igo2BTNode*bt{if bt{if bt-lchiId||bt—〉rchiId{pr intfbt—data;count++;algo2bt-lchiId;algo2bt-〉rchiId;}2阅读下列函数arrange Oint arrange inta[],int1,int h,int x{//1和h分别为数据区的下界和上界int i,j,t;i=1；j=h;wh i I ei〈j{while ija[j]=x j----------;wh i Ie ija[j]=x i++;ifi j{t=a[j];a[;a}i fa[i]x returni;eIse returni_1;}1写出该函数的功能；2写一个调用上述函数实现下列功能的算法对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数【答案】

21.一个正读和反读都相同的字符序列称为“回文”例如“abcba”和“1221”是回文,而“abcde”不是回文试写一个算法，要求利用栈的基本运算识别一个以@为结束符的字符序列是否是回文【答案】int Pairchar*str{InitStack s;p=strfor;*p!=,@,;p++Push s,*p;while StackEmptys{Pop s,y;if y!=*str++return0;}return1;22o有一带表头结点的单链表，其结点的元素值以非递减有序排列，编写一个算法删除该链表中多余的元素值相同的结点值相同的结点只保留一个【答案】void DeI sameLNode*h{if h-〉next{for p=h—〉next;p-next;{q=p—〉next;if p-data=q-data{p-〉next=q-next;free q;}eIse p=q;}

23.编写一个算法，判断带表头结点的单链表是否递增有序【答案】int funLNode*h{p=h-next;while p-〉next{q=p-next;if q-datap—data return0;p=q;}return1;}24o假设有两个带表头结点的单链表HA和HB,设计算法将单链表HB插入到单链表HA的第i0〈iW表长个结点前【答案】void funLNode*ha,LNode*hb,int i{for p=hb;p-next;p=p—next;for j=1,q=ha;j i;j++q=q—next;;p-〉next=q—next;q-〉next=hb-next;free hb;}25o假设以带头结点的单链表表示有序表，单链表的类型定义如下typedef struct node{DataType data;struct node*next}LinkNode,*LinkList;编写算法,从有序表A中删除所有和有序表B中元素相同的结点.【答案】空

26.设二叉树T采用二叉链表结构存储，数据元素为字符类型设计算法分别求出二叉链表中data域为英文字母和数字字符的结点个数.【答案】int letter=0,digit=0;/*全局变量*/void aI go2BTNode*bt{if bt{ifbt-data=,A bt-data=,Z|I bt—data=,abt-data=,zletter++；if bt-data Obt-〉data〈=9digit++;aI go2bt—〉Ichi Id;a Igo2bt-rchiId;

27.假设以单链表表示线性表，单链表的类型定义如下typedef struct node{DataType data;structnode*next;}LinkNode,*LinkList;编写算法，将一个头指针为head且不带头结点的单链表改造为一个含头结点且头指针仍为head的单向循环链表，并分析算法的时间复杂度【答案】LinkList f34LinkList headLinkList p,s;p=head;while p-next p=p-next;s=LinkListma Iloc sizeof LinkNode;s-〉next=head;p-next=s;head=s;return head;.时间复杂度为0n28o假设有向图以邻接表方式存储，编写一个算法判别顶点Vi到顶点Vj是否存在弧【答案】int IsArcsALgraphG,int i,int j{/*判断有向图G中顶点i到顶点j是否有弧，是则返回1,否则返回0*/p=G[i].fi rstarc;while p!=NULL{if p-〉adjvex=jreturn1;p=p-nextarc;}return0;

29.设二叉树T采用二叉链表结构存储，数据元素为字符类型设计算法求出二叉链表中data域为大写字母的结点个数【答案】i ntcount=0；/*count为全局变量*/void a Igo2BTNode*bt{if bt{if bt-data bt—data=,Z,count++;a Igo2bt—〉Ichi Id;algo2bt-rchiId;}

30.假设带表头结点的双向循环链表定义如下typedef struct dunode{char data;structdunode*prior,*next;}DuNode;现用该链表存放字符串，编写一个算法，判断该字符串是否中心对称关系例如字符串“xyzzyx”和“xyzyx”都是中心对称的【答案】int funDuNode*h{p=h-next;q=h—〉prior;whi lep!=qp—〉pr ior!=qif q-data==p-data{p=p-next;q=q-pr ior;}else return0;return1;

31.假设以带头结点的单链表表示线性表，单链表的类型定义如下typedef intDataType;typedef structnode{DataType data;structnode*next;}LinkNode,*LinkList;编写算法，删除线性表中最大元素假设最大值唯一存在函数原型为:void f34LinkList head;【答案】void f34LinkList headinte;LinkListp,q,s,spre;//s指向最大值的那个结点spre=head;s=head—〉next;q=s;p=s-next;while pifs-data〈p-〉data{s=p;spre=q;}q=P；p=p—〉next;e=s-data;spre-next=s-〉next;free s;1该函数的功能是调整整数数组a［］中的元素并返回分界值i,使所有Vx的元素均落在.i］上,上或int fint b[],int nint p,q;intp,q;p=arrangeb,0,n—1,1;q=p=arrange b,0,n—1,0;arrange b,0,p,0;q=arrange b,p+1,n—1,1;使所有2x的元素均落在a[i+

1.o h]2int fintb[],int nreturnq—p;return p—q;3o假设线性表以带表头结点的循环单链表表示试设计一个算法，在线性表的第k个元素前插入新元素y假如表长小于k,则插在表尾【答案】void aI go1LNode*h,int k,ElemType y{q=h;P=h—〉next;j=1;whilep!=hjk{q=P；P=p—next;j++;}s=LNode*ma11oc s i zeof Lnode;s-data=y;q_〉next=s;s-〉next=q;}

4.二叉排序树的类型定义如下typedef struct BSTNode{//二叉排序树的结点结构int data;〃数据域structBSTNode*Ichi Id,*rchild;〃左、右孩子指针}BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数【答案】int f34BSTree rootint count;BSTNode*p;p=root;ifpp-data〈a count++;f34p—lchild;return count;}5o设二叉树T采用二叉链表结构存储，试设计算法求出二叉树中离根最近的第一个叶子结点注结点按从上往下，自左至右次序编号【答案】BTNode*First leafBTNode*bt{InitQueueQ;//初始化队列Qi fbt{EnQueue Q,bt;;wh iIe!EmptyQueueQ{DeQueue Q,p;if!p—I chiId!p-rchiId returnp;ifp-Ichi IdEnQueueQ,p-lchiId;if p-rchiId EnQueueQp—〉rchiId;9}60已知一棵具有n个结点的完全二叉树被顺序存储在一维数组中，结点为字符类型，编写算法打印出编号为k的结点的双亲和孩子结点【答案】int algo2char bt[],int n,int k{if k〈l||k〉n return0;ifk==1printf%c isa root\nw,bt

[1];else printfa%csparent is%c\n”,bt[k],bt[k/2];if2*k=n printf%cs Ichildis%c\n”，bt[k],bt[2*k];else printf%c\s notIchi ld\n,bt[k];if2*k+1〈=n printf%cs rchi Id is%c\nw,bt[k],bt[2*k+1];else printf%c isnot rchi ld\n,bt[k];return1;

7.编写算法,将非空单链表hb插入到单链表ha的第i0〈iW表长个结点前【答案】intaIgo1LNode*ha,LNode*hb,int i{for p=hb;p-next;p=p-next;for j=1,q=ha;ji;j++q=q-next;p-〉next=q-〉next;q—〉next=hb-〉next;.free hb;80设二叉树T已按完全二叉树的形式存储在顺序表T中，试设计算法根据顺序表T建立该二叉树的二叉链表结构.顺序表T定义如下struct tree{int no;/*结点按完全二叉树的编号*/EIEMTP data;/*数据域*/}T[N]；/*N为二叉树T的结点数*/【答案】BTNode*creat_tree structtree T[N]{BTNode*p[MAX];t=NULL;for i=0;i〈N;i++{s=BTNode*ma IIoc sizeofBTNode;s-data=T[i].data;s—Ichii d=s-rchil d=NULL;m=T[i].no;p[m]=s;if m==1t=s;else{j=m/2;if m%2=0p[j]—lchild=s;else p[j]—rchild=s;.}//sIse}//for returnt;}//creat_tree9o编写算法判断带表头结点的单链表L是否是递增的若递增返回1,否则返回0【答案】i ntalgol LNode*Lif!L-next return1;p=L-next;whilep-next{if p-〉datap-next-data p=p-next;else return0;}return1;}10o假设一线性表由Fibonacci数列的前n nN3项构成，试以带表头结点的单链表作该线性表的存储结构,设计算法建立该单链表，且将项数n存储在表头结点中Fibonacci数列根据下式求得1f n=1n=1f n-2+f n-1n=2【答案】LNode*Great IistLNode*h,int n{h=LNode*ma II oc sizeof Lnode;h—〉data=n;h-〉next=p=LNode*ma IIoc sizeof Lnode;p-next=q=LNode*ma II ocsizeofLnode;p-data=q-data=1;for i=3;i=n;i++{q-next=s=LNode*ma11ocsizeofLnode;s—〉data=p—data+q-〉data;s-next=NULL;P=q；q=s;}return h;}

11.设二叉树T采用二叉链表结构存储，数据元素为字符类型设计算法将二叉链表中所有data域为小写字母的结点改为大写字母【答案】void algo2BTNode*bt{if bt{if bt-data=,abt-〉data〈二，zbt-data—=32;a Igo2bt—〉Ichi Id;algo2bt-〉rchiId;12o假设线性表以带表头结点的循环单链表表示试设计一个算法，在线性表的第k个元素前插入新元素y假如表长小于k,则插在表尾【答案】void InsertIistLNode*h,int k,ElemType yq=h;P=h-next;j=1;whilep!=hj〈k{q=P；P=p—next;j++;s=LNode*ma II ocsizeofLnode;s-data=y;q-〉next=s;s-next=q;}

13.有一带表头结点的单链表，其结点的元素值以非递减有序排列，编写一个算法在该链表中插入一个元素x,使得插入后的单链表仍有序【答案】void algolLNode*H,ElemTp xs=LNode*ma IIoc sizeof LNode;s-〉data=x;q=H;p=H-next;whilepp-data〈二x q=P；P=p—next;s-next=p;q-〉next=s;14o二叉排序树的类型定义如下typedef structBSTNode{//二叉排序树的结点结构1nt data;〃数据域structBSTNode*lchi Id,*rchild;〃左、右孩子指针}BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数【答案】int f34BSTree rootintcount;BSTNode*p;p=root;ifpp—〉dataa count++;f34p—I child;return count;}15o有一带表头结点的单链表，其结点的data域的类型为字符型，编写一个算法删除该链表中的数字字符.【答案】void DeI_digit LNode*h{for p=h;p-〉next;{q=p-next;if q-data=Qfq-data=9,{p-next=q—〉next;free q;}else p=q;

16.利用栈的基本运算，编写一个算法，实现将整数转换成二进制数输出【答案】void returnDtoOint numinitStacks;whi len{k=n%2;n=n/2;push s,k;while EmptyStacks{pop s,k;printf“%d”，k;17o设二叉树T采用二叉链表结构存储，数据元素为int型，试设计一个算法，若结点左孩子的data域的值大于右孩子的data域的值，则交换其左、右子树【答案】void algo2bitreptr bt{bitreptr x;if bt{if bt-I chiIdbt—〉rchiIdbt—〉I chiId—〉data bt—〉rchild-datax=bt—Ichi Id;bt—I chiId=bt-〉rchiId;bt-〉rchild=x;aIgo2bt-I chiId;algo2bt-rchiId;}

18.设二叉树T采用二叉链表结构存储，试设计算法求出二叉树的深度【答案】int DeepBTNode*bt{if bt==NULL return0;Ieft=Deep bt-Ichi Id;right=Deep bt-〉rchiId;return leftr ight left:right+1;}19o设给定的哈希表存储空间为H0M—1，哈希函数的构造方法为“除留余数法“，处理冲突的方法为“线性探〜测法”，设计算法将元素e填入到哈希表中【答案】void hash-insert hashTableh[],int m,ElemType e{j=e%p;ifh[j]!=NULL h[j]=e;else{do{j=j+1%m;}whileh[j]!=NULL;h[j]=e;}

20.对于给定的十进制正整数，打印出对应的八进制正整数利用栈【答案】void DecToOctint numinitStacks;〃初始化栈while n{k=n%8;n=n/8;pushs,k;while EmptyStacks〃判断栈是否为空{pops,k;pr intf%d”，k;。