计算机软件基础习题

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。

数据的逻辑结构

数据的存储结构数据的运算：查询、排序、插入、删除、修改等

线性结构

非线性结构

顺序存储

链式存储线性表栈队树形结构图形结构数据结构的三个方面：计算机软件基础习题共16页，您现在浏览的是第1页!1.回文是指正读和反读都相同的字符序列，如“abba”,“abdba”均是回文，“good”不是回文。编写一个算法判定给定的字符串是否为回文。计算机软件基础习题共16页，您现在浏览的是第2页!算法描述1将字符串的一半字符压入栈中，再将其依次弹出与字符串的另一半字符做比较，如果相同则为回文，不相同则不是。这里要考虑串长是奇偶两种情况。计算机软件基础习题共16页，您现在浏览的是第3页!算法描述2先将整串字符压入栈，后将倒序方法用已知字符串的每个字符依次与出栈字符相比。计算机软件基础习题共16页，您现在浏览的是第4页!算法描述3将已知字符串倒序赋值给另外一个字符串，比较它们整个字符串是否相等。计算机软件基础习题共16页，您现在浏览的是第5页!2.参考课件P36前序遍历二叉树的算法和程序写出后序遍历二叉树的算法及程序(非递归)计算机软件基础习题共16页，您现在浏览的是第6页!VoidPreorder(structnode*t){structnode*p；

structnode*s[max];inttop;top=-1;p=t;do{WHILE(p!=null){printf(“%d”,p->data)；

IF(p->rlink!=null) { top=top+1; s[top]=p->rlink; }p=p->llink;}IF(top！=-1){p=s[top];top=top-1;}}while((p！=null)||(top！=-1))}VoidPostorder(structnode*t){structnode*p，*pre；//pre保存刚访问过节点

structnode*s[max];inttop=-1;p=t;pre=null;While(p||top>-1){//沿着左子树走到最底端while(p!=null) {top=top+1;s[top]=p;p=p->llink; }p=s[top];If((p->rlink==null)||(p->rlink==pre)) {//如果没有右子树或者右子树刚被访问过

printf(“%d”,p->data)；top=top-1;pre=p;p=null; }Elsep=p->rlink;}}计算机软件基础习题共16页，您现在浏览的是第7页!思考习题如何对二叉树线索化

遍历二叉树是以一定规则将二叉树的节点排成一个线性序列，得到二叉树中节点的特定序列（前序，中序，后序）。实质上是对一个非线性结构进行线性化操作，使每个节点（除个和最后一个）在这些线性序列中仅有一个直接前驱和直接后继。

计算机软件基础习题共16页，您现在浏览的是第8页!思考习题解决方法增加两个标志域LTAG=0,Lchild域指向节点的左子树LTAG=1,Lchild域指向节点的前驱RTAG=0,Rchild域指向节点的右子树RTAG=1,Rchild域指向节点的后继DATALTAGRTAGRchildLchild计算机软件基础习题共16页，您现在浏览的是第9页!IntText(char*s){intlenth=strlen(s);//计算字符串长度Inti,j,k;If(lenth%2==0)//长度为偶数{i=lenth/2;for(j=0;j<=i-1;j++)//将前半串字符依次压栈push(s[j]);for(j=i-1;j>=0;j--)//依次弹出与后半串比较{k=pop(s[j]);if(k!=s[i++])break;}if(j<0)return1;//是回文return0;}else//长度为奇数{i=lenth/2;for(j=0;j<=i-1;j++)//将前半串入栈push(s[j]);i++;//越过串中间字符for(j=i-1;j>=0;j--){k=pop(s[j]);//依次弹出if(k!=s[i++])//进行比较break;}if(j<0)return1;//是回文return0;}}计算机软件基础习题共16页，您现在浏览的是第10页!inttext(char*s1){charstack[max],k;Inttop=-1;inti;for(i=0;i<strlen(s1);i++) {top=top+1;

stack[top]=s1[i];//入栈 }for(i=strlen(s1)-1;i>=0;i--) { k=stack[top]; top=top-1; if(s1[i]!=k) { break; return0; } else return1; }}计算机软件基础习题共16页，您现在浏览的是第11页!inttext(char*s1){char*s2=newchar[strlen(s1)];inti;for(i=0;i<strlen(s1);i++)//将字符串倒序赋值 s2[strlen(s1)-1-i]=s1[i]; if(strcmp(s1,s2)) return1; else return0;delete[]s2;}计算机软件基础习题共16页，您现在浏览的是第12页!算法比较前序遍历算法1.访问根节点2.遍历左子树3.遍历右子树4.返回后序遍历算法1.遍历左子树2.遍历右子树3.访问根节点4.返回计算机软件基础习题共16页，您现在浏览的是第13页!VoidInorder(structnode*t){structnode*p；

structnode*s[max];inttop;top=-1;p=t;do{WHILE(p!=null)/*扫描左节点*/{top=top+1;s[top]=p;

p=p->llink;}IF(top>=0){p=s[top];/*p所指的节点为无左子树或其左子树已经遍历过*/top=top-1;printf(“%d”,p->data)；/*访问节点*/P=p->rlink/*扫描右子树*/}

while((p！=null)||(top！=-1))}计算机软件基础习题共16页，您现在浏览的是第14页!思考习题问题但是二叉树作为链式的存储结构，只能找到节点的左右子树，不能得到节点在任一序列中的前趋后继，这种信息只有在遍历的动态过程中才能等到。计算机软件基础习题共16页，您现在浏览的是第15页!思考习题提示：

if(p->llink!=NULL) p->ltag=0; else { p->ltag=1; p->llink=pre; }//建立P节点的左线索，指向前趋节点Pre if(pre!=NULL