《数据结构》DS习题答案A.docVIP

绪论 1．（第18页，第（5）题） 确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。 (1) i=1; k=0; do { k=k+10*i; i++; } while(i=n-1) 划线语句的执行次数为 n-1 。 (2）i=1; x=0; do{ x++; i=2*i; } while （in）; 划线语句的执行次数为 (log2n(。 (3) for(int i=1;i=n;i++) for(int j=1;j=i;j++) for (int k=1;k=j;k++) x++; 划线语句的执行次数为n(n+1)(n+2)/6 。 (4）x=n;y=0; while(x=(y+1)*(y+1)) y++; 划线语句的执行次数为( (n (。 线性表 1．第37页 习题(2).2 在类LinearList 中增加一个成员函数，将顺序表逆置，实现该函数并分析算法的时间复杂度。不利用类SeqList 提供的操作直接实现。 template class T void SeqListT::Invert() { T e; for (int i=1;i=length/2;i++){ e=elements[i-1]; elements[i-1]=elements[length-i]; elements[length-i]=e; } } 2．第37页习题(5) 在类SingleList中增加一个成员函数，将单链表逆置运算，直接实现该函数并分析其时间复杂度。 template class T void SingleListT::invert() { NodeT *p=first,*q; first=NULL; while (p){ q=p-link; p-link=first; first=p; p=q; } } 栈与队列 第50页 习题(1） 设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈)，问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。 1）A,B,C,D,E 2) A,C,E,B,D 3) C,A,B,D,E 4) E,D,C,B,A 答：2）和3）不能。对2）中的E，B，D而言，E最先出栈，则表明，此时B和D均在栈中，由于，B先于D进栈，所以应有D先出栈。同理3）。 2. 第50页 习题（9） 利用栈可以检查表达式中括号是否配对，试编写算法实现之。 bool match(char a[],int n) { int top=-1; for (int i=0;in;i++) if (a[i]==() top++; else if (a[i]==)) if (top-1) top--; else return true; if (top-1) return true; return false; } 数组与字符串 给出三维数组元素A[i][j][k]的存储地址loc(A[i][j][k])。 答： 设有三维数组声明为A[n1][n2][n3]，每个元素占k个存储单元，则 loc(A[i][j][k])=loc(A[0][0][0])+k*(i*n2*n3+j*n3+k) 2．（第68页，第5题）给出下列稀疏矩阵的 顺序三元组的行优先和列优先表示。 答： 3．（第68页，第6题） 对题图4-5的稀疏矩阵执行矩阵转置时数组num[]和k[]的值。 答： 路径长度 递归 1．设计一个递归算法，实现对一个有序表的顺序有哪些信誉好的足球投注网站。 templateclass T int SeqListT::Search4(const T x) const { elements[length]=1000; return Sch4(x,0); } templateclass T int SeqListT::Sch4(const T x,int i) const { if (xelements[i]) return 0; else if (x==elements[i]) return ++i; else return Sch4(x,i+1); } 树 1．第107页，第（2）题 对于三个结点A，B和C，可分别组成多少不同的无序树、有序树和二叉树？ 答