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

1、算法设计题1. 设二叉树 bt 采用二叉链表结构存储。试设计一个算法输出二叉树中所有非叶子结点，并求出非叶子结点的 个数。【答案】int count=0;void algo2(BTNode *bt)if (bt)if(bt-lchild | bt-rchild) printf(bt-data);count+ ; algo2(bt-lchild); algo2(bt-rchild);2. 阅读下列函数 arrange()int arrange(int a,int 1,int h,int x) /1 和h分别为数据区的下界和上界int i,j,t ；i=1 ； j=h ；while(ij) whi

2、le(i=x)j- ； while(i=x)i+ ； if(ij) t=aj ； aj=ai ；ai=t ；if(ainext; j=1;while( p!=h & jnext; j+;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的结点个数

3、。【答案】int f34(BSTree root)int count;BSTNode *p;p=root;if ( p & p-datalchild);return count;5. 设二叉树 T采用二叉链表结构存储，试设计算法求出二叉树中离根最近的第一个叶子结点。(注：结点按从上往下，自左 至右次序编号)【答案】BTNode * Firstleaf(BTNode *bt) InitQueue(Q); / 初始化队列 Qif(bt)EnQueue(Q,bt);while(!EmptyQueue(Q)DeQueue(Q,p);第2 页万维试题库系统if(!p-lchild & !p-rchild

4、) return p; if(p-lchild) EnQueue(Q,p-lchild); if(p-rchild) EnQueue(Q,p-rchild);6. 已知一棵具有 n个结点的完全二叉树被顺序存储在一维数组中，结点为字符类型 , 编写算法打印出编号为 k的结点的双亲和孩子结点。【答案】int algo2(char bt,int n,int k)if (kn) return 0;if( k=1) printf( “%c is a rootn”, bt1);else printf( “ %cs parent is %cn”, btk, btk/2);if(2*k=n) printf(“

5、 %c s lchild is %cn”, btk, bt2*k);else printf( “ %c isnot lchildn”, btk);if(2*k+1=n) printf(“ %c s rchild is %cn”, btk, bt2*k+1);else printf( “ %c isnot rchildn”, btk);return 1;7. 编写算法，将非空单链表 hb插入到单链表 ha的第 i(0next; p=p-next);for(j=1,q=ha;jnext;p-next=q-next;free(hb);8. 构。试设计算法根据顺序表 T建立该二叉树的二叉链表结q-ne

6、xt=hb-next ；设二叉树 T已按完全二叉树的形式存储在顺序表T中，顺序表 T定义如下：struct treeint no;/*ElEMTPdata; /*/* NTN;答案】BTNode *creat_tree(结点按完全二叉树的编号 */ 数据域 */为二叉树 T 的结点数 */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;第3 页万维试题库系统 else j=m/2;if(m%2=0) pj-lchild=s;else

7、 pj-rchild=s;/slse/forreturn t;/ creat_tree9. 编写算法判断带表头结点的单链表 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(n 3)项构成，试以带表头结点的单链表作该线性表的存储结构， 设计算法建立该单链表，且将项数n存储在表头结点中。 Fibonacc

8、i 数列根据下式求得：1(n=1)f(n)= 1(n=2)f(n-2)+f(n-1) (n 3)【答案】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

9、;p=q;q=s;return h;11. 设二叉树 T采用二叉链表结构存储，数据元素为字符类型。设计算法将二叉链表中所有data 域为小写字母的结点改为大写字母。【答案】void algo2(BTNode *bt)if (bt)第4 页万维试题库系统if(bt-data= a & bt - datadata-=32;algo2(bt-lchild);algo2(bt-rchild);12. 假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素 y。假如表长小于 k ，则插在表尾。【答案】void Insertlist(LNode *h,int k,Elem

10、Type y)q=h; P=h-next; j=1;while( p!=h & jnext; j+;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;

11、q-next=s;14. 二叉排序树的类型定义如下：typedef struct BSTNode 二叉排序树的结点结构int data; 数据域struct BSTNode *lchild, *rchild; 左、右孩子指针 BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树 T 中值小于 a的结点个数。【答案】int f34(BSTree root)第5 页万维试题库系统 int count;BSTNode *p;p=root;if ( p & p-datalchild);return count;15. 有一带表头结点的单链表，其结点的data域的类型为字符型，编写一个算法删

12、除该链表中的数字字符。【答案】void Del_digit (LNode *h)for(p=h;p-next;)q=p-next;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);printf( “%d”,k);17. 设二叉树 T采用二叉链表结构存储，数据元素为 i

13、nt 型，试设计一个算法，若结点左孩子的 data 域的值大于 右孩子的 data 域的值，则交换其左、右子树。【答案】void 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;第6 页万维试题库系统bt-rchild=x;algo2(bt-lchild);algo2(bt-rchild);18. 设二叉树 T采用二叉链表结构存储，试设计算法求出二叉树的深度。【答案】int

14、Deep(BTNode *bt)if (bt=NULL) return 0;left=Deep(bt-lchild);right=Deep(bt-rchild);return (leftright?left:right)+1;19. 设给定的哈希表存储空间为 H( 0M-1 )，哈希函数的构造方法为 “除留余数法 ”，处理冲突的方法为 “线性 探测法 ”，设计算法将元素 e填入到哈希表中。【答案】void hash-insert(hashTable h,int m,ElemType e)j=e%p;if(hj!=NULL) hj=e;elsedo j=(j+1) %m;while(hj!=NU

15、LL );hj=e;20. 对于给定的十进制正整数 , 打印出对应的八进制正整数。 (利用栈)【答案】void DecToOct(int num)initStack(s); / 初始化栈while(n) k=n%8;n=n/8;push(s,k);while(EmptyStack(s) / 判断栈是否为空 pop(s,k);printf( “%d”,k);21. 一个正读和反读都相同的字符序列称为 “回文”。例如 “abcba”和“1221”是回文，而 “abcde”不是回文。试写第7 页万维试题库系统一个算法，要求利用栈的基本运算识别一个以为结束符的字符序列是否是回文。【答案】int Pai

16、r(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 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

17、(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. 假设有两个带表头结点的单链表 HA和HB，设计算法将单链表 HB插入到单链表 HA的第i(0next; p=p-next);for(j=1,q=ha;jnext; ; p-next=q-next; q-next= hb-next ； free(hb);25. 假设以带头结点的单链表表示有序表，单链表的类型定义如下：

18、typedef struct nodeDataType data;struct node *nextLinkNode, *LinkList;编写算法，从有序表 A中删除所有和有序表 B中元素相同的结点。 【答案】(空)26. 设二叉树 T采用二叉链表结构存储， 数据元素为字符类型。 设计算法分别求出二叉链表中 和数字字符的 结点个数。【答案】int letter=0 ， digit=0 ；/* 全局变量 */void algo2(BTNode *bt)if (bt)if(bt- data= A &- bdtata| dbatta= a&- bdtatadata= 0 &- bdtatalchi

19、ld);algo2(bt-rchild);27. 假设以单链表表示线性表 ,单链表的类型定义如下 : typedef struct node DataType data;struct node *next; LinkNode, *LinkList;编写算法 ,将一个头指针为 head且不带头结点的单链表改造为一个含头结点且头指针仍为 表,并分析算法的时间复杂度。【答案】LinkList f34(LinkList head)LinkList p,s;p=head;while (p-next) p=p-next; s=(LinkList)malloc(sizeof(LinkNode); s-nex

20、t=head;data域为英文字母head的单向循环链第9 页万维试题库系统p-next=s;head=s;return head; 时间复杂度为 :O(n)28. 假设有向图以邻接表方式存储，编写一个算法判别顶点vi到顶点 vj是否存在弧。【答案】int IsArcs(ALgraph G ,int i,int j) /* 判断有向图 G中顶点 i 到顶点 j是否有弧 ,是则返回 1,否则返回 0*/ p=Gi.firstarc;while (p!=NULL) if(p-adjvex =j)return 1; p=p-nextarc;return 0;29. 设二叉树 T采用二叉链表结构存储，数据元素为字符类型。设计算法求出二叉链表中 结点个数。【答案】int count=0 ； /* count 为全局变量 */void algo2(BTNode *bt)if (bt)if(bt-data= A & bt - datalchild);algo2(bt-rchild);30. 假设带表头结点的双向循环