p=h->next; q=h->prior;
while(p!=q && p->prior!=q) { if (p->data= = q->data)
{p=p->next; q=q->prior; j++;} else j=0; } return(j);
}4、写出按后序序列遍历中序线索树的算法. 5、写出计算树深度的算法。 6、写出计算树叶子结点的算法。 7、写出计算字符串长度的算法。
8、试写出以带头结点单链表为存储结构实现简单选择排序的算法 9、阅读下列算法，并回答下列问题： （1） 该算法完成什么功能
（2） 算法中R[n+1]的作用是什么
Void sort (elemtype r[],int n) {int k,i;
for(k=n-1;k>=1;k- -) if(r[k]>r[k+1])
{ r[n+1]=r[k];
for(i=k+1;r[i] 10、试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。 11.二叉树是由所有度数不大于2的结点构成的一种特定树，若某结点度为2，则该结点有左右两个孩子，请编写算法计算一二叉树所有度数为2的结点个数。 12、试设计一个算法在中序线索化的树中，求指定结点P在后序遍历序列中的前驱结点，要求用非 递归算法。 13、若X和Y是两个单链表存储的串，设计一个算法，找出X中第一个不在Y中出现的字符。 14、试设计一个算法在中序线索化的树中，求指定结点P在后序遍历序列中的前驱结点，要求用非 递归算法。 15、设计一个算法，删去串中第I个字符开始的J个字符，说明算法所用的存储结构，并估计算法的 执行时间。 16、设有单链表中存放着N个字符，试设计算法判断字符串是否中心对称关系，例如： X Y Z Z Y X ，X Y Z Y X 都算是中心对称的字符串。要求用尽可能少的时间完成判断(提示：将一半 字符先依次进栈)。 提示:我们设H为指向链表头结点的指针,单链表每个结点包括两个域:分别是date,next分别代表数 据域和指针域,s为定义的栈。 17、设计一个算法将任意输入的N个数，按输入的顺序(或逆序)链接成一个单链表。 18、试设计一个算法，求单链表中数据值为X0的元素的地址。 19、试编一个程序，将两个字符串s1和s2进行比较，若s1>s2则输出一个正数；若s1=s2，则输出 0；若s1 21、给定一棵用链表表示的二叉树，其根指针为t，试写出从根开始，按层次遍历二叉树的算法，同 层的节点按从左到有的次序访问。 22、完成在二叉排序树中查找结点的程序 Bitreptr *bstsearch(t,k) Bitreptr *k; Keytype k; { if(t= =null) return null; else while(t !=null) {if (t->key= =k)_________; if(t->key>k)______________; else____________________; } } 23、编写一个算法交换单链表中P所指向的位置和其后续位置上的两个结点，HEAD指向该链表的表 头，P指向该链表中的某一结点。 24、已知两个链表A和B，其元素值递增排列。写出编程将A和B合并成一个递减有序（相同值只 保留一个）的链表C的思想，并要求利用原表结点。（*） 25、下列算法完成在一个带头单链表中第i个结点前插入一个结点算法，请将空余处填上。 Void inserti (struct node *head) { p =head ->next;k=0; while(p!=null)&&(k<_______) {________; k++;} if p!=null {printf(“please input to x”); scanf(“%d”,&x); q=(struct node *)malloc(sizeof(struct node)); q->data=x; _________; _________; } else printf(“not found ith node”);} 26、写出下列算法的功能： void weizhi( struct node *head) { p= head->next； head p q sy head->next =null; while (p!=null) { q=p->next; p->next=head->next; head->next=p; p=q; } } 27、建立一个带头结点、有10个结点的单链表，请将下列算法填完整。Void great( ) { struct node *head,*p,*s; int i,x; head = ( struct node *)malloc( sizeof( struct node)); head->next=null; p=head; for ( i =1;i<=10 ; i ++) { s=(struct node *)malloc(sizeof(struct node)); printf(“请输入数据值”)； scanf(“%d”,&x); s ->data= x; s ->next=p->next; _______; _______;}} Void searchbinary( elemtype a[ ],int n ,int k) {int low=0,high=n-1,mid, find=0; while(find= = 0)&&(low<=high) { mid=______________; if(k= = a[mid]) {find=1; printf(“find k!”);} else {if ( k high=mid-1; else _____________;} } if (find= =0) printf(“not find k!”); }Void insstr(char string1,char string2,int i) {int n,m, j; n=strlen(string1); m=strlen(string2); if ( i<0|| i>n – 1) printf(“error!”); else { for(j=n;j>=i-1;j - -) string1[j+m]=string1[j]; for(j=0,j string1[ i +j -1]= string2[j]; }} Void delstr(char string, int i, int j) {if ( i> strlen(string)) printf(“error!”); else{ k= i-1; while(string[k+j] ! =‘\\o’) { ____________; k++;} string[k]=‘\\0’; }}Void delete( int a[n],int i) {if (i<0)||(i>=n) printf(“error”); else{for (j=i-1;j a[j]=a[j+1]; n=n-1;} } 在有头结点head单链表p指针结点后插入值为x的结点，请将下列算法填完整； Void insert( struct node *head, elemtype x) { struct node *s,*p*q; q = head->next ; while (q!=p) q=q->next; if q= =null printf(“not find”); else { s=(struct node *)malloc( sizeof(struct node) ) ; s->data=x; _______________； _______________；}} Void weizhi (linkqueue *q) {struct queuenode *p; if = = printf(“the queue is empty”); else{ p=q->front->next; q->front->next=p->next return(p->data); free(p); }} 41、写出在二叉排序树中插入一指定结点一个结点的算法。 42、完成计算二叉树叶子结点的算法。 Void midtravel(struct treenode *bt) {struct treenode *p,*a[n]; int top= - 1,true =1, j =0; while(true)
数据结构试题及答案
