数据结构与算法试题(7)

while(i<=x){ if(n%i==0)break; i++; }

if(i>x) return 1; else return 0; }

(2)int sum1(int n){ int p=1,s=0;

for(int i=1;i<=n;i++) {p*=i;s+=p;} return s; }

答案：（1）程序功能是判断n是否是一个素数，若是则返回数值1，否则返回数值0，该算法的时间复杂度为O（sqrt(n)）. （2）程序功能是计算∑ni=1i!，该算法的时间复杂度为O（n）.

10、判断一个带表头结点的双向循环链表L是否对称相等的算法如下所示，请在算法的 处填入正确的语句。 int symmetry(DblList DL) { int sym=1;

DblNode p=DL->rLink,q=DL->lLink; While(p!=q&&p->lLink==q)&& sym==1 ) if (p->data==q->data){ p=p->rLink;

q=q->lLink; }

else sym=0; return sym;} 11、阅读下面程序，指出其算法的功能 #include “stack.h”

int BaseTrans(int N,int B) { int i,result=0;StackS; while(N!=0){i=N%B;N=N/B;S.Push(i);} while(!S.IsEmpty()){i=S.GetTop();S.Pop(); result=result*10+i;} return result; }

答案：该算法是将一个非负的十进制整数N转换为另一个基数为B的B进制数。 12、阅读下面程序，指出其算法的功能 template

void BinaryTree::binsearchTree(BinTreeNode*t,int &bs) { if(t!=Null){

if((t->letfchild==Null||t->data>t->leftchild->data)&& (t->rightchild==Null||t->datarightchild->data)) { bs=1;

binsearchTree(t->leftchild,bs);

if(bs) binsearchTree(t->rightchild,bs); }

else bs=0; } }

答案：该算法是判别给定的以二叉链表存储的二叉树是否是二叉搜索树。采用递归算法，对树中的所有结点检查是否左子树上结点的关键码都小于它的关键码，右子树上结点的关键码都大于它的关键码。如满足上述条件，则是二叉搜索树。 六、综合算法题

1、试设计一个实现下述要求的查找运算函数Locate。设有一个带表头结点的双向链表L， 每个结点有4个数据成员：指向前驱结点的指针llink、指向后继结点的指针rlink，存放字符数据的成员data和访问频度freq。所有结点的

freq 初始时都为0。每当在链表上进行一次Locate(L, x) 操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。

答案：

(1) 定义链表结构

struct DoubleListNode {

char data ; int freq;

DoubleListNode * llink, *rlink ;

};

初始时，所有结点的freq域的值都为0。 (2) 定义函数

DoubleListNode * locate ( DoubleListNode *f ; char &x ) {

DoubleListNode * p, *q; p = f→rlink;

/*跳过表头结点*/

while ( p != NULL && p→data != x ) p = p→rlink; /*搜索*/ if ( p ) {

p→freq ++; q = p→llink;

p→rlink→llink = q; q→rlink = p→rlink; /*从链中

摘下p*/

while ( q != f && q→freq < p→freq ) q =q→llink;

p→llink = q;

p→rlink = q→rlink; q→rlink→llink = p;

q→rlink = p; /*在q后面插入p*/

}

return p; }

2、已知A[n]为整数数组，试写出实现下列运算的递归算法：

(1) 求数组A中的最大整数。 (2) 求n个整数的和。 (3) 求n个整数的平均值

答案：#include class RecurveArray{ private: int *Elements; int ArraySize; int CurrentSize;

public:

RecurveArray (int MaxSize=10):

ArraySize(MaxSize),Elements(new int[MaxSize]){ } ~ RecurveArray ( ){delete[ ] Elements;} void InputArray( ) ; int Maxkey(int n); int sum(int n); float Average (int n); };

void RecurveArray:: InputArray( ) { cout<<”Input the number of Array :\\n”;

for (int i=0;i< ArraySize;i++) cin>> Elements[i]; }

int RecurveArray::Maxkey(int n) { if(n= =1) return Elements[0]; int temp= Maxkey(n-1);

if(Elements[n-1]>temp) return Elements[n-1]; else return temp; }

int RecurveArray::Sum(int n) { if (n= =1) return Elements[0]; else return Elements[n-1]+Sum(n-1); }