数据结构(本科)期末综合练习四(算法分析题)
更新时间:2024-04-10 03:36:01 阅读量: 综合文库 文档下载
- 数据结构期末试题推荐度:
- 相关推荐
数据结构(本科)期末综合练习四(算法分析题)
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
void unknown ( SeqList
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<
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
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(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->data
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 || item
ListNode *cp, *ap; ap=HL; cp=HL->link;
16
while(cp!=NULL) {
if(item
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
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
for (j=0; j
18
CurrentEdges -= d; // CurrentEdges为图中的边数 }
算法功能:
42. 已知图的邻接表中边结点类型Edge的结构为(dest, cost, link),在表头向量中指向顶点单链表的表头指针为adj,下面算法是在用邻接表表示的图中计算所有顶点的出度,并保存在数组Degree[]中。请按标号填补合适内容。
template
void Graph
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
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
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
ListNode
template
ListNode
List():first(NULL),last(NULL){} void ListSelectSort(); };
template
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
ListNode
template
ListNode
List():first(NULL),last(NULL){} void ListSelectSort(); };
template
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
for(i=1; i
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
T pivot = Vector[left]; //把基准元素的值暂存于pivot中 do {
do {i++;} while(Vector[i].key
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
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
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
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
正在阅读:
四年级数学上册买文具教学反思12-01
医学遗传学课程教学大纲资料04-16
七年级英语下册unit3 how do you get to school?单元测试01-17
第四章 养老保险问题 - 非线性方程求根的数值解法04-02
14天突破4级01-06
合同书格式02-25
单纯形法的灵敏度分析与对偶10-15
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 合练
- 数据结构
- 算法
- 期末
- 本科
- 分析
- 习四(
- 抚州市2013年度考试录用公务员入闱名单 - 图文
- 三年级下册语文阅读
- 《沉香救母》(一)第一课时
- 物理化学考试题库
- 史上最完美2015中考物理分类汇编 - 光的折射 透镜
- 联想S890刷第三方recovery兼卡刷第三方ROM教程 - 图文
- 临时便道施工方案
- 天津理工大学C++期末考试
- 给青年教师课堂教学的十点建议
- 初中八年级全套体育教案(共36课)
- 东213综放工作面回采作业规程
- 国际贸易理论与实务 单选
- 理想车身气动造型研究与F1赛车空气动力学2
- 油价上涨通过三条机制影响化工行业的盈利
- 人教版二年级数学上册第一单元 - 长度单位 - - 教学设计
- 2010年价格鉴证师考试经济学与价格学考前预测试卷(1)-中大网校
- 专接本英语重点词汇、短语汇编
- 园林病虫害
- 2014年八年级下册Unit 5测试题
- 吉林省洗浴中心名录2018版147家