数据结构（本科）期末综合练习四（算法分析题）

数据结构（本科）期末综合练习四（算法分析题）

1. 指出算法的功能并求出其时间复杂度。 int fun ( int n ) { int i = 1, s = 1;

while ( s < n ) s += ++i;

return i; }

功能为：

时间复杂度为：

2. 指出算法的功能并求出其时间复杂度。

void matrimult ( int a[M][N], int b[N][L], int c[M][L] ) { //M、N、L均为全局整型常量 int i, j, k;

for ( i = 0; i < M; i++ )

for ( j = 0; j < L; j++ ) c[i][j] = 0; for ( i = 0; i < M; i++ ) for ( j = 0; j < L; j++ ) for ( k = 0; k < N; k++ )

c[i][j] += a[i][k] * b[k][j];

} 功能为：

时间复杂性为：

3. 针对如下算法，回答问题：

若数组A[n] = {12, 24, 0, 38, 0, 0, 0, 0, 29, 0, 45, 0}, n = 12，给出算法执行后数组A[n]的状态。

template

void unknown ( T A[ ], int n ) {

int free = 0;

for ( int i = 0; i < n; i++ )

if ( A[i] != 0 ) {

if ( i != free ) {

A[free] = A[i]; A[i] = 0; }

free++; }

}

算法执行的结果

1

4. 设顺序表SeqList具有下列操作：

int Length( ) const; //计算表长度并返回，若表为空则返回0

T Remove( ); //删除当前表项并返回其值，置下一表项为当前表项 T First( ); //取表中第一个表项的值并返回，并置为当前表项 T Next( ); //取当前表项后继表项的值并返回， //并把此后继表项置为当前表项

若顺序表中存放的数据为{29,38,47,16,95,64,73,83,51,10,0,26}，表的长度为12，参数值s=10, t=30，说明算法执行后顺序表的状态和长度的变化。 #include #include “SeqList.h” template

void unknown ( SeqList& L, T s, T t ) {

if(!L.Length( ) || s>=t)

{cerr<<“表为空或参数值有误!”<

T temp=L.First( ); while(i

if(temp>=s && temp<=t) L.Remove( ); else {temp=L.Next( ); i++;} }

算法执行后顺序表中的数据：

算法执行后顺序表的长度：

5. 设字符串String具有下列操作：

int Length ( ) const; //计算字符串的长度

char getData ( k ); //提取字符串第k个字符的值 若字符串Tar的值为“a b a b c a b c a c b a b”，Pat的值为“a b c a c”时，给出算法执行后函数返回的结果。

#include “String.h”

int unknown ( String& Tar, String& Pat ) const {

for ( int i = 0; i <= Tar.Length( ) – Pat.Length( ); i++ ) { int j = 0;

while ( j < Pat.Length( ) )

if ( Tar.getData (i+j) == Pat.getData (j) ) j++; else break;

if ( j == Pat.Length( ) ) return i; }

2

return -1; }

算法执行的结果是：

6. 阅读下列算法，并补充所缺内容。 void purge_linkst( ListNode *& la ){

// 从头指针为 la 的有序链表中删除所有值相同的多余元素，并释放被删结点空间

ListNode *p,*q;

if(la==NULL) return; q=la; p = la->link; while (p) {

if (p && ___(1)___) {q=p; p = p->link;} else {

q->link= ___(2)___; delete(p); p=___(3)___; } }//while

}// purge_linkst

(1) (2) (3)

7. 设单链表的存储结构为ListNode=(data,link)，表头指针为LH，所存线性表L=(?a?,?b?,?c?,?d?,?e?,?f?,?g?)，若执行unknown(LH)调用下面程序，则写出执行结束后的输出结果。 void unknown（LinkNode *Ha） { //Ha为指向单链表的头指针 if(Ha){

unknown (Ha->link); cout<data; } }

8. 设单链表结点的结构为LNode=(data,link)，阅读下面的函数，指出它所实现的功能。 int AA(LNode *Ha)

{ //Ha为指向带表头附加结点的单链表的表头指针 int n=0;

LNode *p=Ha->link; while(p) { n++;

p=p->link; }

return(n);

3

}

算法功能：

9. 设单链表结点的结构为ListNode = (data,link)，下面程序段执行后将生成由L所指向的带头结点的单链表，给出该单链表所对应的线性表。 ListNode *L = new ListNode;

ListNode *p=L;

for (int i = 0; i < 4; i++) {

p->link = new ListNode; p = p->link; p->data = i*2-1;

}//for

p->link = NULL;

10. 这是一个统计单链表中结点的值等于给定值x的结点数的算法，其中有两行错误，请指出错误行的行号并改正。

int count (ListNode *Ha, ElemType x) ① { // Ha 为不带头结点的单链表的头指针

int n = 0; ② while (Ha!= NULL){ ③

Ha = Ha->link; ④ if (Ha->data == x) n++; ⑤ } //while

return n; ⑥

}//count

错误语句号: 修改如下:

11. 写出下列程序段的输出结果: void main(){

stack S; char x,y;

S.InitStack( ); x='c';y='k';

S.Push(x); S.Push('a'); S.Push(y); S.Pop(S,x); S.Push('t'); S.Push('s');

while(!S.IsEmpty( )) { S.Pop(y); cout<

}//main

4

运行结果：

12. 写出下列程序段的输出结果: void main(){

queue Q;

char x, y='c'; Q.InitQueue( );

Q.EnQueue('h'); Q.EnQueue('r'); Q.EnQueue(y); Q.DeQueue(x); Q.EnQueue(x); Q.DeQueue(x); Q.EnQueue('a');

while(Q.IsEmpty( )) {Q.DeQueue(y); cout<

}//main

输出结果：

13. 指出下面算法的功能。 Stack unknown(Stack S) { Stack T; int d;

T.IniStack( ); //初始化栈 While(!S.IsEmpty( )){

d=S.GetTop( ); S.Pop( ); T.Push(d); }

return T; }

14. 请写出下面算法的功能. void unknown(Queue &Q) { Stack S; int d; S.InitStack( );

while(!Q.IsEmpty( )) {

Q.DeQueue(d); S.Push(d); }

while(!S.IsEmpty( )) {

S.Pop(d); Q.EnQueue(d); } }

15. 下面算法的功能为：将两个有序单链表合并成一个有序单链表并返回其表头指针。阅读下列算法, 按标号填写空缺的内容，要求统一填写在算法后面的标记处。 ListNode* Merge1(ListNode*& p1, ListNode*& p2)

5

{

ListNode a; //a结点作为结果有序单链表的表头附加结点 ListNode* p=&a; p->link=NULL;

while(p1!=NULL && p2!=NULL) {

if(p1->data<=p2->data) { ___(1)___; p1=p1->link; }

else {

p->link=p2; p2=p2->link; }

___(2)___; }

if(p1!=NULL) p->link=p1; else ___(3)___; p1=p2=NULL; return a.link; }

(1) (2) (3)

16. 阅读下列算法，写出算法功能。 LinkNode* BB(LinkNode *first) {

if(first==NULL || first->link==NULL) return first; LinkNode *q=first,*p=q->link; q->link=NULL; while(p!=NULL) {

ListNode *r=p->link; p->link=q; q=p; p=r; }

return q; }

算法功能：

17. 下面是判断一个带表头结点的双向循环链表L其前后结点值是否对称相等的算法, 若相等则返回1，否则返回0。请按标号补充合适的内容。 int symmetry ( DoublelList* DL ) {

6

DoublelNode * p = DL->rLink, *q = DL->lLink; while (p != q)

if ( p->data == q->data ) { p = p->rLink; ___(1)___;

if(p->lLink==q) ___(2)___; }

else ___(3)___; return 1; }

(1) (2) (3)

18. 阅读下面的算法, 写出它的功能。 ListNode* unknown( ) {

ListNode *first, *p, *q; int x;

p = first = new ListNode; cin>>x;

while (x != 0) {

q = new ListNode;

q->data = x; p->rlink = q; q->llink = p; p = q; cin>>x; }

p->rlink = NULL; return first->rlink;

}

算法功能：

19. rear是指向以循环链表表示的队列的队尾指针，EnLQueue函数实现插入 x 为新的队尾元素的操作。DeLQueue函数实现删除队头元素并赋给x的操作。请按标号补充合适的内容。

void EnLQueue(ListNode*& rear, ElemType x)

// rear是指向以循环链表表示的队列的队尾指针，插入 x 为新的队尾元素。 {

ListNode *p; p = new ListNode;

p->data = x; ___(1)___; rear->link = p; rear = p;

};

bool DeLQueue(ListNode*& rear, ElemType& x)

7

// rear是指向以循环链表表示的队列的队尾指针，若队列不空，

//则删除队头元素并以 x 带回，并返回 true, 否则返回 false, x 无意义 {

if(rear==NULL) return false;

if ( rear->link == rear ) {

x=rear->data; delete rear; rear=NULL; return true;

}

ListNode *p=rear->link; rear->link=p->link;; ___(2)___; delete p; ___(3)___;

}

(1) (2) (3)

20. 设有一个求解汉诺塔（Hanoi）的递归算法如下：

void HANOI ( int n, int peg1, int peg2, int peg3 ) { if(n==1) cout<?<

else {

HANOI(n-1, peg1, peg3, peg2); cout<?<

}

当使用HANOI( 3,1,2,3)进行调用时，执行过程中else子句的cout语句得到的结果为：

21. 针对如下算法，回答问题：

(1) 若整型数组A[8] = {12, 24, 33, 38, 95, 83, 64, 57}，n=8，则给出算法返回的结果。 (2) 说明算法的功能是什么。

int unknown ( int A[ ], int n ) { if ( n == 1 ) return A[0]; int temp = unknown ( A, n-1 );

return A[n-1] > temp ? A[n-1] : temp;

}

返回结果： 算法功能：

22. 针对如下算法，设整数链表L中各结点的数据为12, 24, 30, 90, 84, 36，n的初值为0，则（1）给出执行unknown( L.first, n )调用后的返回结果;（2）指出算法功能。

在算法中getLink()函数返回结点指针域的值，getData()函数返回结点的数据域的值。

8

float unknown ( ListNode *f , int& n ) { if ( f == NULL ) return 0; else {

n++;

return unknown (f->getLink(),n) + f->getData()/n ;

} }

返回结果： 算法功能：

23. 已知二叉树中的结点类型BinTreeNode定义为:

struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是返回二叉树BT中值为X的结点所在的层号，请在划有横线的地方填写合适内容。

int NodeLevel(BinTreeNode * BT, ElemType X) {

if(BT==NULL) return –1; //空树的层号为-1 else if(BT->data==X) return 0; //根结点的层号为0 //向子树中查找X结点 else {

int c1=NodeLevel(BT->left,X); if(c1>=0) _____(1)___________; int c2=_______(2)______________; if _________(3)__________________; //若树中不存在X结点则返回-1 else return -1; }

}

(1) (2) (3)

24. 已知二叉树中的结点类型BinTreeNode定义为:

struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是：从二叉树BT中查找值为X的结点，返回指向其父结点的指针。若该结点不存在或为树根结点则返回空。算法中参数PT的初值为NULL。请在划有横线的地方填写合适内容。

BinTreeNode* ParentPtr(BinTreeNode* BT, BinTreeNode* PT, ElemType& X)

9

{

if(BT==NULL) return NULL;

else if(BT->data==X) return PT; else {

if(PT=ParentPtr(BT->left,BT,X)) __(1)_____;

if _________________(2)_______________ return PT; else ___(3)____; }

}

(1) (2) (3)

25. 已知二叉树中的结点类型BinTreeNode定义为:

struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树。

BinTreeNode* BTreeSwopX(BinTreeNode* BT) {

if(BT==NULL) return NULL; else {

BinTreeNode* pt=new BinTreeNode; pt->data=BT->data;

pt->right=BTreeSwopX(BT->left); pt->left=BTreeSwopX(BT->right); return pt; } }

算法功能：

26. 已知二叉树中的结点类型STreeNode定义为:

struct STreeNode { datatype data; STreeNode *lchild, *rchild, *parent;}; 其中data为结点值域，lchild和rchild分别为指向左、右子女结点的指针域，parent为指向父亲结点的指针域。根据下面函数的定义指出函数的功能。算法中参数ST指向一棵二叉树，X保存一个结点的值。

STreeNode* PN(STreeNode* ST, datatype& X) {

10

if(ST==NULL) return NULL; else {

StreeNode* mt;

if(ST->data==X) return ST->parent;

else if(mt=PN(ST->lchild,X)) return mt; else if(mt=PN(ST->rchild,X)) return mt; return NULL; } }

算法功能：

27. 已知二叉树中的结点类型BinTreeNode定义为:

struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树。 void BTC(BinTreeNode* BT) {

if(BT!=NULL) {

if( BT->left!=NULL && BT->right!=NULL) if(BT->left->data>BT->right->data) { BinTreeNode* t=BT->left; BT->left=BT->right; BT->right=t; }

BTC(BT->left); BTC(BT->right); } }

算法功能：

28. 已知二叉树中的结点类型BinTreeNode定义为:

struct BinTreeNode {char data; BinTreeNode *left, *right;};

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。假定指针bt指向一棵二叉树，该二叉树的广义表表示为a(b(a,d(f)),c(e(,a(k)),b))，每次调用时整数变量C的值均为0，若：

执行BTC1(bt,?a?,C)调用后，C的值为___(1)_____;

执行BTC1(bt,?b?,C)调用后，C的值为___(2)_____;

11

执行BTC1(bt,?c?,C)调用后，C的值为___(3)_____;

执行BTC1(bt,?g?,C)调用后，C的值为__(4)______;

void BTC1(BinTreeNode* BT, char x, int& k) {

if(BT!=NULL) {

if( BT->data==x) k++; BTC1( BT->left, x, k); BTC1( BT->right, x, k); }

}

(1) (2) (3) (4)

29. 已知二叉树中的结点类型BinTreeNode定义为:

struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是从二叉树BT中查找值为X的结点，若查找成功则返回结点地址，否则返回空。请在划有横线的地方填写合适内容。

BinTreeNode* BTF(BinTreeNode* BT, ElemType x) {

if(BT==NULL) ___(1)____; else {

if( BT->data==x) __(2)____; else {

BinTreeNode* t;

if(t=BTF(BT->left, x)) ____(3)____; ___________(4)_____________; else return NULL; } }

}

(1) (2) (3) (4)

12

30. 已知二叉树中的结点类型BinTreeNode定义为:

struct BinTreeNode {char data; BinTreeNode *left, *right;};

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。假定一棵二叉树采用链接存储，它的广义表表示为r(b(,d(f,g)),t(e))，rt,bt,dt和et指针变量分别保存指向r,b,d和e结点的指针值，则：

执行BTM(rt)调用后，得到的函数值为___(1)_____;

执行BTM(bt)调用后，得到的函数值为___(2)_____;

执行BTM(dt)调用后，得到的函数值为___(3)_____;

执行BTM(et)调用后，得到的函数值为__(4)______;

char BTM(BinTreeNode* BT) {

static char max=0; if(BT!=NULL) { char k1,k2;

k1=BTM(BT->left); k2=BTM(BT->right); if(k1>max) max=k1;

else if(k2>max) max=k2;

else if(BT->data>max) max=BT->data; }

return max;

}

(1) ?t? //2分 (2) ?g? //2分 (3) ?g? //2分 (4) ?e? //2分

31. 已知二叉树中的结点类型BinTreeNode定义为:

struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树。

void preserve(BinTreeNode* BT, ElemType a[], int n) {

static int i=0;

13

if(BT!=NULL) {

preserve(BT->left, a, n); a[i++]=BT->data;

preserve(BT->right, a, n); } }

算法功能：

32. 在a[10]数组中的数据{16,42,35,73,54,38,80}为一个最小堆，n为整型变量，其值为7，则执行IH(a,n,25)调用下面算法后数组a中的数据变为________________________________。

void IH(int HBT[], int& n, int item) {

HBT[n]=item; n++;

int x=item; int i=n-1; while(i!=0) {

int j=(i-1)/2;

if(x>=HBT[j]) break; HBT[i]=HBT[j]; i=j; }

HBT[i]=x;

}

33. 在a[10]数组中数据{16,35,42,73,54,58,80}为一个最小堆，n为整型变量，其值为7，则执行DH(a,n)调用下面算法后数组a中的数据变为_____________________________。

int DH(int HBT[], int& n) {

if(n==0) {cerr<<\ int temp=HBT[0]; n--;

int x=HBT[n]; int i=0; int j=2*i+1; while(j<=n-1) {

if(jHBT[j+1]) j++; if(x<=HBT[j]) break; HBT[i]=HBT[j];

14

i=j; j=2*i+1; }

HBT[i]=x; return temp; }

34. 已知二叉搜索树中的结点类型BinTreeNode定义为:

struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。指针参数BST指向一棵二叉搜索树。试根据下面的函数定义指出此算法的功能。 ElemType FM(BinTreeNode* BST) {

if(BST==NULL) {cerr<<\此树为空\ BinTreeNode* t=BST;

while(t->right!=NULL) t=t->right; return t->data; }

算法功能：

35. 假定p1和p2是两个有序单链表的表头指针，用来表示两个集合，单链表中的结点包括值域data和指向后继结点的指针域link，试指出下面算法的功能。 ListNode* BU(ListNode* p1, ListNode* p2) {

ListNode* p3=new ListNode, *p=p3; While(p1!=NULL && p2!=NULL) {

ListNode* newptr=new ListNode; if(p1->datadata) { newptr->data=p1->data; p1=p1->link; }

else if(p1->data>p2->data) { newptr->data=p2->data; p2=p2->link; }

else {

newptr->data=p1->data; p1=p1->link; p2=p2->link; }

p3->link=newptr; p3=newptr; }

15

if(p2!=NULL) p1=p2; while(p1!=NULL) {

p3=p3->link=new ListNode; p3->data=p1->data; p1=p1->link; }

p3->link=NULL;

p3=p->link; delete p; return p3; }

算法功能：

36. 假定p1和p2是两个单链表的表头指针，用来表示两个集合，单链表中的结点包括值域data和指向后继结点的指针域link，试根据下面算法指出算法功能。

int SS(ListNode* p1, ListNode* p2) {

while(p2!=NULL) { ListNode* r=p1;

While(r!=NULL) {

if(p2->data==r->data) break; r=r->link; }

if(r==NULL) return 0; p2=p2->link; }

return 1;

}

37. 假定HL为保存一个集合的有序单链表的表头指针，item为一个新元素，HL单链表中的结点包括值域data和指向后继结点的指针域link，试根据下面算法指出算法功能。

void IS(ListNode*& HL, const ElemType& item) {

ListNode* newptr=new ListNode; newptr->data=item;

if(HL==NULL || itemdata) { newptr->link=HL; HL=newptr; return; }

ListNode *cp, *ap; ap=HL; cp=HL->link;

16

while(cp!=NULL) {

if(itemdata) break; ap=cp;

cp=cp->link; }

newptr->link=cp; ap->link=newptr;

}

算法功能：

38. 已知二叉搜索树中的结点类型BinTreeNode定义为:

struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数t指向一棵二叉搜索树，该树的广义表表示为: 25(10(5,16(12)),40(32(,38)))。按照下面算法，则： 执行LN(pt,40)调用后返回的值为__(1)______。 执行LN(pt,38)调用后返回的值为___(2)_____。 执行LN(pt,5)调用后返回的值为___(3)_____。

int LN(BinTreeNode* t, ElemType X) {

if(t==NULL) return 0;

else if(t->data==X) return 1; else if(t->data>X)

return 1+LN(t->left,X); else

return 1+LN(t->right,X); }

(1) (2) (3)

39. 已知二叉树中的结点类型BinTreeNode定义为:

struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数bt指向一棵二叉树，引用参数x一开始具有的值小于树中所有结点的值。试根据下面的函数定义指出此算法的功能。

int JB(BinTreeNode* bt, ElemType& x) {

if(bt==NULL) return 1; else {

if(JB(bt->left,x)==0) return 0; if(bt->data

17

x=bt->data;

if(JB(bt->right,x)==0) return 0; else return 1; } }

算法功能：

40. 已知一个有向图的顶点集V和边集G分别为： V={0,1,2,3,4};

E={<0,1>,<0,2>,<0,3>,<1,3>,<1,4>,<2,3>,<2,4>,<3,0>,<4,3>}; 若它采用邻接矩阵存储，对应Graph类型的对象为a，则： (1) 使用a.count_D(3)调用下面算法后的返回值是多少？ (2) 该算法的功能是什么？ (3) 给出该算法的时间复杂度。

Template

int Graph::count_D(int i) { int d=0;

for (int j=0; j

if (Edge[i][j]!=0) d++; if (Edge[j][i]!=0 ) d++; }

return(d); }

答（1） （2） （3）

41. 假定一个有向图采用邻接矩阵存储, 请指出下面算法的功能。 template

void Graph::unknown(int i){ int d,j; d = 0;

for (j=0; j

18

CurrentEdges -= d; // CurrentEdges为图中的边数 }

算法功能：

42. 已知图的邻接表中边结点类型Edge的结构为(dest, cost, link)，在表头向量中指向顶点单链表的表头指针为adj，下面算法是在用邻接表表示的图中计算所有顶点的出度，并保存在数组Degree[]中。请按标号填补合适内容。

template

void Graph::FindDegree(int Degree[]) {

int i;

Edge *p=NULL;

for(i=0; i

for(i=0; i

for (p = NodeTable[i].adj; p!=NULL; ___(2)___) ___(3)___; }

}

答(1) (2) (3)

43. 已知图的邻接表中边结点类型Edge的结构为(dest, cost, link)，在表头向量中指向顶点单链表的表头指针为adj，下面算法是在用邻接表表示的图中计算顶点i的入度并返回。请按标号填补合适内容。

Template

int Graph::FindDegree(int i); {

int deg=0,j;

for(j=0; j

Edge* p=NodeTable[j].adj; while (___(1)___) {

if(p->dest==i) {___(2)___; break;} else p=___(3)___; } }

return deg;

19

} 答(1) (2) (3)

44. 已知图的邻接表中边结点类型Edge的结构为(dest, cost, link)，在表头向量中指向顶点单链表的表头指针为adj，下面算法是在用邻接表表示的有向图中删除所有以i为弧头（即终点）的有向边。请按标号填补合适内容。 template

void Graph::DeletEdge(int i) {

int de=0,j; Edge *p, *q;

if(i>=NumVertices) {cout<<\错误输入\ //NumVertices为顶点数 for(j=0;j

if(p->dest==i) ___(1)___; else {q=p; ___(2)___;} }

if(p!=NULL) {

if(q==NULL) NodeTable[j].adj=p->link; else ___(3)___; delete p; de++; } }

NumEdges=NumEdges-de; } 答(1) (2) (3)

45. 下面是进行快速排序的一次划分的算法，请按标号填补合适的内容。 void Exchange(int s[], int i, int j) { int temp =s[i]; s[i]=s[j]; ___(1)___; }

int Partition(int seq[], int low, int high) { int pivotpos=low, pivot=seq[low], i;

20

for(i=low+1; i<=high; i++) if(___(2)___){ pivotpos++;

if(pivotpos!=i) Exchange(seq, pivotpos, i); }

___(3)___;

return pivotpos; } 答(1) (2) (3)

46. 已知给出一个施加于链表List 的选择排序的算法 ListSelectSort。算法中用到一个存放排序结果的临时链表 head。ListSelectSort算法每次从List的first 链上摘下值最大的结点并插入head 中作为首结点。算法结束时，first 和 last 指向结果链表 head 的第一个和最后一个结点。请按标号填补合适内容。 template class List; template class ListNode{ Type data;

ListNode *link; friend class List; };

template class List{

ListNode *first; //指向第一个结点 ListNode *last; //指向最后一个结点 public:

List():first(NULL),last(NULL){} void ListSelectSort(); };

template void List::ListSelectSort ( ){ ListNode * head =NULL , *current,*pre,*p,*q; int flag=1;

while(first!=NULL){

p=current=first; q=NULL; while(p!=NULL){

if(p->data>current->data){pre=q; current=p;} q=p; ___(1)___; }

if (current == first) first=first->link; else pre->link=___(2)___;

if (flag) {last=current; flag=0;}

21

current->link = head; head=___(3)___; }

first = head; }

答(1) (2) (3)

47. 已知给出一个施加于链表List 的选择排序的算法 ListSelectSort。算法中用到一个存放排序结果的临时链表 head。ListSelectSort算法每次从List的first 链上摘下值最大的结点并插入head 中作为首结点。算法结束时，first 和 last 指向结果链表 head 的第一个和最后一个结点。请按标号填补合适内容。 template class List; template class ListNode{ Type data;

ListNode *link; friend class List; };

template class List{

ListNode *first; //指向第一个结点 ListNode *last; //指向最后一个结点 public:

List():first(NULL),last(NULL){} void ListSelectSort(); };

template void List::ListSelectSort ( ){ ListNode * head =NULL , *current,*pre,*p,*q; int flag=1;

while(first!=NULL){

p=current=first; q=NULL; while(p!=NULL){

if(p->data>current->data){pre=q; ___(1)___;} q=p; p=p->link; }

if (current == first) first=___(2)___; else pre->link= current->link; if (flag) {last=current; flag=0;} current->link =head; head=current; }

first = ___(3)___;

22

}

答(1) (2) (3)

48. 下面给出一个排序算法，它属于数据表类dataList的成员函数，其中currentSize是数据表实例的当前长度，Vector[]是存放数据表元素的一维数组。请按标号填补合适内容。

template

void ___(1)___::unknown(){ T temp; int i,j,k;

for(i=0; i

for(j=i+1; j<___(2)___; j++)

if(Vector[j].key

temp=Vector[i]; Vector[i] = Vector[k]; Vector[k] = temp; } } } 答(1) (2) (3)

49. 下面给出数据表类dataList的一个成员函数，其中currentSize是数据表实例的当前长度，Vector[]是存放数据表元素的一维数组。请写出该算法功能。

template

void dataList::unknown(){ T temp; int i, j;

for(i=1; i=0; j--)

if(temp.key

Vector[j+1]=temp; } }

算法功能：

23

50. 下面给出的算法属于数据表类dataList的成员函数，其中currentSize是数据表实例的当前长度，Vector[]是存放数据表元素的一维数组。若一个对象a中的Vector数组的初始排序码序列为：

{45 48 18 36 72 30 53 15 29}

请写出调用a.unknown(0,8)后在Vector数组中得到的结果序列。

template

void dataList::unknown(int left, int right) { int i= left, j=right+1;

T pivot = Vector[left]; //把基准元素的值暂存于pivot中 do {

do {i++;} while(Vector[i].keypivot.key); if(i

T temp=Vector[i]; Vector[i]=Vector[j]; Vector[j]=temp; }

} while(i

Vector[left] = Vector[j]; Vector[j] = pivot; }

结果序列：

51. 下面给出一个排序算法，它属于数据表类dataList的成员函数，其中currentSize是数据表实例的当前长度，Vector[]是存放数据表元素的一维数组。若Vector中数据的初始排序码序列为{30, 20,40,10,60,50}，针对最外层的while循环，给出每次循环执行后的排序码序列。

template

void dataList::unknown() {

int low=0, high=CurrentSize-1, i, j; int exchange;

while(low

if(Vector[i].key>Vector[i+1].key) {

T temp=Vector[i]; Vector[i]=Vector[i+1]; Vector[i+1]=temp;

j=i; //记忆右边最后发生交换的位置j }

high=j; //比较范围上界缩小到j } }

24

(0) {30 20 40 10 60 50} (1) (2) (3)

52. 下面给出的是一个两路归并排序算法merge，它是数据表类dataList的成员函数。merge只需要一个附加存储temp。设算法中参加归并的两个归并段是A[left]?A[mid] 和A[mid+1]?A[right]，归并后，结果归并段放在原地。若A={ 12, 28, 35, 42, 67, 9, 31, 70 }, left = 0, mid = 4, right = 7。请写出首次执行算法最外层for循环后数组A中数据排列情况。

Template

void dataList::merge(int left, int mid, int right) { int i, j; T temp;

for(i=left; i<=mid; i++) { if(A[i]>A[mid+1]) { temp=A[mid];

for(j=mid-1; j>=i; j) A[j+1]=A[j]; A[i]=A[mid+1];

for(j=mid+2; j<=right; j++)

if(temp>A[j]) A[j-1]=A[j]; else break; A[j-1]=temp; } } }

数据排列情况：

算法分析题参考解答

1. 功能为 求出满足不等式1+2+3+...+i ≥ n的最小i值。

时间复杂度为 O(

n)。

2. 功能为： 矩阵相乘，即a[M][N]×b[N][L]→c[M][L]。

时间复杂性为：O(M×N×L)。//4分

3. 算法执行的结果：A[ ] = {12, 24, 38, 29, 45, 0, 0, 0, 0, 0, 0, 0};

4. 该算法执行的结果：在顺序表中的数据为 {38, 47, 95, 64, 73, 83, 51, 0}，表的长度减为8。

5. 算法执行的结果是：函数返回值等于5。该算法即字符串的模式匹配。 6. (1) p->data>q->data (2) p->link (3) q->link

7. gfedcba

8. 计算单链表的长度或计算单链表中结点的个数。

25

9. （-1,1,3,5）

10. 错误语句号: ④ ⑤

修改如下: ④和⑤应对调 2分 11. stack 12. char

13. 将栈S中的元素逆置放到栈T中并返回栈T。

14. 利用\栈\作为辅助存储,将队列中的元素逆置（即相反次序放置）。 15. (1) p->link = p1

(2) p = p->link (3) p->link = p2

16. 逆序排列以first为表头指针的单链表中的所有结点并返回新的表头指针。 17. (1) q = q->lLink

(2) return 1 (3) return 0

18. 建立双向链表并返回表头指针（每个结点的值不为0）。 19. (1) p->link = rear->link

(2) x = p->data (3) return true 20. 1→2

1→3 2→3

21. 返回结果：95

算法功能：求存放于整数数组A[ ]中一组数据的最大值。

22. 返回结果：46

算法功能：求链表中各结点的值的平均值。

23. (1) return c1+1

(2) NodeLevel(BT->right,X) (3) (c2>=0) return c2+1

24. (1) return PT

(2) (PT=ParentPtr(BT->right,BT,X)) (3) return NULL 或return 0

25. 算法功能：生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右子树交换的结果。

26. 算法功能：从树根指针为ST的二叉树中查找值为X的结点，返回指向父结点的指针。

27. 算法功能：当BT中每个结点的左子女的值大于右子女的值则交换左右子树。

26

28. (1) 3

(2) 2 (3) 1 (4) 0

29. (1) return NULL

(2) return BT (3) return t

(4) if(t=BTF(BT->right, x)) return t

30. (1) ?t?

(2) ?g? (3) ?g? (4) ?e? 31. 算法功能：对具有n个结点的二叉树进行中序遍历，把得到的结点值序列保存到数组a中。

32. {16,25,35,42,54,38,80,73}

33. {35,54,42,73,80,58}

34. 从二叉搜索树BST中搜索出具有最大值的结点并返回这个值。

35. 算法功能：实现集合的并运算，即把有序单链表表示的两个集合合并为一个新的集合，并由函数返回新集合的表头指针。

36. 判断p2单链表所代表的集合是否为p1单链表所代表的集合的子集合，若是则返回1否则返回0。

37. 算法功能：向表示集合的有序单链表HL中插入一个新元素，使得插入后的集合单链表仍然保持有序。

38. (1) 2

(2) 4 (3) 3

39.算法功能：判断二叉树bt是否为一棵二叉搜索树，若是则返回1否则返回0。

40. (1) 5

(2) 返回顶点为i的度

(3) 时间复杂度为O(n) //n为图中顶点数

27

41. 算法功能：从有向图中删除所有与顶点i相连的边。

42. (1) 0

(2) p=p->link

(3) Degree[p->dest]++

43. (1) p!=NULL (2) deg++ (3) p->link

44. (1) break (2) p=p->link

(3) q->link=p->link

45. (1) s[j]=temp (2) seq[i]

(3) Exchange(seq, low, pivotpos)

46. (1) p=p->link

(2) current->link (3) current

47. (1) current=p

(2) first->link (或current->link) (3) head

48. (1) dataList (2) currentSize (3) k=j

49. 算法功能：对数据表类dataList中的Vector数组保存的currentSize个元素进行直接插入排序。

50. 结果序列：{30 29 18 36 15 45 53 72 48}

51. (0) {30 20 40 10 60 50}

(1) {20 30 10 40 50 60} (2) {20 10 30 40 50 60} (3) {10 20 30 40 50 60}

52. 数据排列情况：{9,12,28,35,42,31,67,70}

28

本文来源：https://www.bwwdw.com/article/cz3r.html