数据结构算法设计题复习题

1、v1.0可编辑可修改算法设计题并求出非叶子结点的1.设二叉树bt采用二叉链表结构存储。试设计一个算法输出二叉树中所有非叶子结点,个数。【答案】int count=0;void algo2(BTNode *bt)if (bt)if(bt-lchild | bt-rchild)printf(bt-data);count+ ;10万维试题库系统第16页algo2(bt-lchild);algo2(bt-rchild);)2.阅读下列函数arrange()int arrange(int a口,int 1,int h,int x)i上，使所有x的元素士落在ai +1.h(2) int f(int b口,

2、int n)int p,q ;p=arrange(b,0,n 1,0);q= arrange(b,p+1,n 1,1) return q p;)3.假设线性表以带表头结点的循环单链表表示。上。或 int f(int b口,int n)int p,qp=arrange(b,0,n; q= arrange(b,0,p,0);return p试设计一个算法，在线性表的第 1,1);q;k个元素前插入新元素V。假如表长小于k,则插在表尾。【答案】void algo1( LNode *h,int k,ElemType y)q=h; P=h-next; j=1;while( p!=h & jnext; j

3、+;s=(LNode *)malloc(sizeof(Lnode);s-data=y;q-next=s;s-next=q;4,二叉排序树的类型定义如下：typedef struct BSTNode /二叉排序树的结点结构int data;/ 数据域struct BSTNode *lchild, *rchild;/左、右孩子指针BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。【答案】int f34(BSTree root) int count;BSTNode *p;p=root;if ( p & p-datalchild);return count;（注：

4、结点按从5,设二叉树T采用二叉链表结构存储，试设计算法求出二叉树中离根最近的第一个叶子结点。 上往下，自左至右次序编号)【答案】BTNode * Firstleaf(BTNode *bt) InitQueue(Q); 已知一棵具有n个结点的完全二叉树被顺序存储在一维数组中，结点为字符类型，编写算法打印出编号为k的结点的双亲和孩子结点。【答案】int algo2(char bt,int n,int k)if (kn) return 0;if( k=1) printf( %c is a root n , bt1);else printf( %c s parent is %c n , btk, bt

5、k/2);if(2*k=n) printf( %c s lchild is %c n , btk, bt2*k);else prin tf( %c is not lchild n , btk);if(2*k+1=n) printf( %c s rchild is %c n , btk, bt2*k+1);else printf( %c is not rchild n , btk); return 1;7 .编写算法，将非空单链表 hb插入到单链表ha的第i(0next; p=p-next);for(j=1,q=ha;jnext;p-next=q-next;q-next=hb-next;free

6、(hb);8 .设二叉树T已按完全二叉树的形式存储在顺序表T中，试设计算法根据顺序表Tt立该二叉树的二叉链表结构。顺序表T定义如下：struct treeint no;/*结点按完全二叉树的编号*/ElEMTP data; /* 数据域 */TN；/* N为二叉树T的结点数*/BTNode *creat_tree( struct tree TN ) BTNode *pMAX;t=NULL;for(i=0;idata=Ti.data;s-lchild=s-rchild=NULL;m=Ti.no; pm=s;if(m=1) t=s;else j=m/2;if(m%2=0) pj-lchild=s;

7、else pj-rchild=s;)编写算法判断带表头结点的单链表L是否是递增的。若递增返回 1,否则返回0。【答案】int algo1 (LNode *L ) if(!L-next) return 1;p=L-next;while(p-next)if(p-data next-data) p=p-next;else return 0;return 1;10 .假设一线性表由Fibonacci数列白前n (n3)项构成，试以带表头结点的单链表作该线性表的存储结构，设计算法建立该单链表，且将项数n存储在表头结点中。Fibonacci数列根据下式求得：1 (n=1)f(n)= 1(n=2)f(n-2

8、)+f(n-1) (n3)【答案】LNode * Creatlist(LNode *h,int n)h=(LNode *)malloc(sizeof(Lnode);h-data=n;h-next=p=(LNode *)malloc(sizeof(Lnode);p-next=q=(LNode *)malloc(sizeof(Lnode);p-data= q-data=1;for(i=3;inext=s=(LNode *)malloc(sizeof(Lnode);s-data=p-data+q-data; s-next=NULL;p=q;q=s;)return h;)11 .设二叉树T采用二叉链表

9、结构存储，数据元素为字符类型。设计算法将二叉链表中所有data域为小写字母的结点改为大写字母。【答案】void algo2(BTNode *bt)if (bt)if(bt- data= a & bt -datadata-=32;algo2(bt-lchild);algo2(bt-rchild);)12 .假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k,则插在表尾。【答案】void Insertlist(LNode *h,int k,ElemType y)q=h; P=h-next; j=1;while( p!=h & jnext; j

10、+;s=(LNode *)malloc(sizeof(Lnode);s-data=y;q-next=s;s-next=q;13 .有一带表头结点的单链表，其结点的元素值以非递减有序排列，编写一个算法在该链表中插入一个元素x,使得插入后的单链表仍有序。【答案】void algo1 (LNode *H, ElemTp x)s=(LNode *) malloc ( sizeof (LNode);s-data=x;q=H; p=H-next;while ( p & p-datanext;s-next=p; q-next=s;14 .二叉排序树的类型定义如下：typedef struct BSTNode

11、 /二叉排序树的结点结构int data;/ 数据域struct BSTNode *lchild, *rchild;/左、右孩子指针BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。【答案】int f34(BSTree root)int count;BSTNode *p;p=root;if ( p & p-datalchild); return count;15 .有一带表头结点的单链表，其结点的data域的类型为字符型，编写一个算法删除该链表中的数字字符。【答案】void Del_digit (LNode *h)for(p=h;p-next;)q=p-n

12、ext;if(q-data= 0 & q - data next=q-next; free(q); else p=q; 16 .利用栈的基本运算，编写一个算法，实现将整数转换成二进制数输出。【答案】void returnDtoO(int num) initStack(s); while(n) k=n%2;n=n/2;push(s,k); )while(EmptyStack(s) pop(s,k);p rintf( %d ,k); )17 .设二叉树T采用二叉链表结构存储，数据元素为int型，试设计一个算法，若结点左孩子的data域的值大于右孩子的data域的值，则交换其左、右子树。【答案】vo

13、id algo2(bitreptr bt) bitreptr x;if (bt)if (bt-lchild & bt-rchild) & (bt-lchild -data bt-rchild-data) ) x= bt-lchild ;bt-lchild= bt-rchild;bt-rchild=x;algo2(bt-lchild);algo2(bt-rchild);18,设二叉树T采用二叉链表结构存储，试设计算法求出二叉树的深度。【答案】int Deep(BTNode *bt)if (bt=NULL) return 0;left=Deep(bt-lchild);right=Deep(bt-r

14、child);return (leftrightleft:right)+1;)19 .设给定的哈希表存储空间为H (0M-1),哈希函数的构造方法为“除留余数法”，处理冲突的方法为“线性探测法”，设计算法将元素e填入到哈希表中。【答案】void hash-insert(hashTable h口,int m,ElemType e)j=e%p;if(hj!=NULL) hj=e;else do j=(j+1) %m;while(hj!=NULL);hj=e;20 .对于给定的十进制正整数，打印出对应的八进制正整数。(利用栈)【答案】void DecToOct(int num)initStack(s

15、);一个正读和反读都相同的字符序列称为“回文”。例如“abcba”和“1221”是回文，而“abcde”不是回文。试写一个算法，要求利用栈的基本运算识别一个以碘结束符的字符序列是否是回文。int Pair(char *str ) InitStack(s) ;p=strfor ( ； *p!= ； p+ )Push(s,*p);while(StackEmpty(s) Pop(s,y);if(y!=*str+ ) return 0;return 1;22 .有一带表头结点的单链表，其结点的元素值以非递减有序排列，编写一个算法删除该链表中多余的元素值 相同的结点（值相同的结点只保留一个）。void

16、Delsame (LNode *h)if(h-next) for(p=h-next;p-next;)q=p-next;if(p-data=q-data)p-next=q-next;free(q);else p=q; 23 .编写一个算法，判断带表头结点的单链表是否递增有序。【答案】int fun(LNode *h) p=h-next; while(p-next) q=p-next ;if(q-datap-data) return 0;p=q; return 1; 24 .假设有两个带表头结点的单链表H序口 HB,设计算法将单链表 HBB入到单链表H掰第i(0next; p=p-next);fo

17、r(j=1,q=ha;jnext;p-next=q-next;q-next= hb-next;free(hb); 25 .假设以带头结点的单链表表示有序表，单链表的类型定义如下：typedef struct nodeDataType data;struct node *nextLinkNode, *LinkList;编写算法，从有序表 A中删除所有和有序表B中元素相同的结点。【答案】(空)26,设二叉树T采用二叉链表结构存储，数据元素为字符类型。设计算法分别求出二叉链表中data域为英文字母和数字字符的结点个数。【答案】int letter=0 , digit=0 ;/* 全局变量 */voi

18、d algo2(BTNode *bt)if (bt)if(bt-data= A & bt-datadata=a& bt -datadata= 0 & bt-datalchild);algo2(bt-rchild);27 .假设以单链表表示线性表，单链表的类型定义如下：typedef struct node DataType data;struct node *next; LinkNode, *LinkList;编写算法，将一个头指针为head且不带头结点的单链表改造为一个含头结点且头指针仍为head的单向循环链表，并分析算法的时间复杂度。【答案】LinkList f34(LinkList he

19、ad)LinkList p,s;p=head;while (p-next) p=p-next;s=(LinkList)malloc(sizeof(LinkNode);s-next=head;p-next=s;head=s; return head;时间复杂度为：O(n)28 .假设有向图以邻接表方式存储，编写一个算法判别顶点vi到顶点vj是否存在弧。【答案】int IsArcs(ALgraph G,int i,int j) /*判断有向图 机顶点i到顶点j是否有弧，是则返回1,否则返回0*/p=Gi.firstarc;while (p!=NULL) if(p-adjvex =j) return 1;p=p-nextarc; return 0; 29 .设二叉树T采用二叉链表结构存储，数据元素为字符类型。设计算法求出二叉链表中data域为大写字母的结点个数。【答案】int count=0 ； /* count 为全局变量 */void algo2(BTNode *bt)if (bt)if(bt- data= A & bt -datalchild);algo2(bt-rchi