四川大学
《数据结构与算法分析》课程
习题及参考答案
模拟试卷一
一、单选题（每题2 分，共20分）
1.以下数据结构中哪一个是线性结构？( B )
A. 有向图
B. 队列
C. 线索二叉树
D. B树
2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，
则执行如下(D )语句序列。
A. p=q; p->next=q;
B. p->next=q; q->next=p;
C. p->next=q->next; p=q;
D. q->next=p->next; p->next=q;
3.以下哪一个不是队列的基本运算？（A ）
A. 在队列第i个元素之后插入一个元素
B. 从队头删除一个元素
C. 判断一个队列是否为空
D.读取队头元素的值
4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成
( B )个不同的字符串？ABC ACB BAC BCA CBA
A.14
B.5
C.6
D.8
5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。
A． 11 B.35 C. 19 D. 53
8*1+6*2+3*3+2*3=35
以下6-8题基于图1。
6.该二叉树结点的前序遍历的序列为( C )。
A.E、G、F、A、C、D、B
B.E、A、G、C、F、B、D
C.E、A、C、B、D、G、F
D.E、G、A、C、D、F、B
7.该二叉树结点的中序遍历的序列为( A )。
A. A、B、C、D、E、G、F
B. E、A、G、C、F、B、D
C. E、A、C、B、D、G、F
E.B、D、C、A、F、G、E
E
A G
C
B D
F
图1
8.该二叉树的按层遍历的序列为( C )。
A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F
C. E、A、G、C、F、B、D
D. E、G、A、C、D、F、B
9.下面关于图的存储的叙述中正确的是( C )。
A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关
D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建
堆的结果?( B )
A. a，g，h，m，n，p，q，x，z
B. a，g，m，h，q，n，p，x，z
C. g，m，q，a，n，p，x，h，z
D. h，g，m，p，a，n，q，x，z
二、填空题（每空1分，共26分）
1.数据的物理结构被分为_顺序__、___列表___、____索引______和____散列___四种。
2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为
___O(n)_____，在表尾插入元素的时间复杂度为______O(1)______。
3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是
_____p->next=HS;HS=p______;删除一个结点时，需要执行的操作是________HS=HS->next______（假设栈不空而且无需回收被删除结点）。
4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左孩
子结点的编号为______2i__，若它有右孩子，则右孩子结点的编号为___2i+1_____，若
它有双亲，则双亲结点的编号为___i/2_____。
5.当向一个大根堆插入一个具有最大值的元素时，需要逐层____向上____调整，直到被调
整到_____根___位置为止。
6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为____2.9____。
7.表示图的三种常用的存储结构为____邻接矩阵_____、_____邻接表_______和______边
集数组_________。
8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7
作为散列函数，则散列地址为0的元素有___1 ____个，散列地址为6的有__ 4_____个。
9.在归并排序中，进行每趟归并的时间复杂度为__ O(n)____，整个排序过程的时间复杂
度为______ O(nlog2n)______，空间复杂度为____ O(n)_______。
10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为__(m/2)-1____个，最多为
___m-1_____个，其子树数目最少为___m/2_____，最多为___m_____。
三、运算题（每题6 分，共24分）
1.写出下列中缀表达式的后缀形式：
（1）3X/(Y-2)+1
（2）2+X*(Y+3)
2.试对图2中的二叉树画出其：
(1)顺序存储表示的示意图；
(2)二叉链表存储表示的示意图。
3.判断以下序列是否是小根堆? 如果不是, 将它调
图2 整为小根堆。
（1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }
（2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 }
4.已知一个图的顶点集V和边集E分别为：
V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4, (4,7)20,(5,6)18,(6,7)25};
按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。
四、阅读算法（每题7分，共14分）
1.void AE(Stack& S){
InitStack(S);
Push(S,3);
Push(S,4);
int x=Pop(S)+2*Pop(S);
Push(S,x);
int i,a[5]={1,5,8,12,15};
for(i=0;i<5;i++) Push(S,2*a[i]);
while(!StackEmpty(S)) cout< } 该算法被调用后得到的输出结果为： 2.void ABC (BTNode *BT,int &c1,int &c2) { if (BT !=NULL ) { ABC(BT->left,c1,c2); c1++; if (BT->left==NULL&&BT->right==NULL) c2++; ABC(BT->right,c1,c2); }//if } 该函数执行的功能是什么？ 五、算法填空（共8分） 向单链表的末尾添加一个元素的算法。 Void InsertRear(LNode*& HL,const ElemType& item) { LNode* newptr; newptr=new LNode; If (______________________) { cerr<<"Memory allocation failare!"< exit(1); } ________________________=item; newptr->next=NULL; if (HL==NULL) HL=__________________________; else{ LNode* P=HL; While (P->next!=NULL) ____________________; p->next=newptr; } } 六、编写算法（共8分） 编写从类型为List的线性表L中将第i个元素删除的算法，（假定不需要对i的值进行 有效性检查,也不用判别L是否为空表。） void Delete(List& L, int i) 模拟试卷一参考答案 一、单选题（每题2分，共20分） 1.B 2.D 3.A 4.B 5.B 6.C 7.A 8.C 9.B 10.B 二、填空题（每空1分，共26分） 1.顺序链表索引散列 2.O(n) O(1) 3.p->next=HS;HS=p HS=HS->next 4.2i 2i+1 ?i/2?（或i/2） 5.向上根 6. 2.9 7.邻接矩阵邻接表边集数组 8. 1 4 9.O(n) O(nlog2n) O(n) 10.?m/2?-1 m-1 ?m/2? m 三、运算题（每题6分，共24分） 1.(1) 3 X * Y 2 - / 1 + 图3 (2) 2 X Y 3 + * + 2.（1） 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 （2）见图3所示： 3.(1)不是小根堆。调整为：{12,65,33,70,24,56,48,92,86,33} (2)是小根堆。 4.普里姆算法从顶点1出发得到最小生成树为： (1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20 四、阅读算法（每题7分，共14分） 1.30 24 16 10 2 10 2.该函数的功能是：统计出BT所指向的二叉树的结点总数和叶子总数 五、算法填空（共8分，每一空2分） newptr==NULL newptr->=data newptr p=p->next 六、编写算法（8分） void Delete(List& L, int i) { for(int j=i-1;j L.list[j]=L.list[j+1]; //第i个元素的下标为i-1 L.size--; } 模拟试卷二 一、单选题（每题2 分，共20分） 1.在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结 点，则执行( B )。 A. HL=p; p->next=HL; B. p->next=HL->next; HL->next=p; C. p->next=HL; p=HL; D. p->next=HL; HL=p; 2.若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（ B ）个元素. A. n B.n-1 C. n+1 D.不确定 3.下述哪一条是顺序存储方式的优点？（ A ） A．存储密度大 B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在 678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？(脚注(10)表示用10进制表示,m>3) C A．658 B．648 C．633 D．653 5.下列关于二叉树遍历的叙述中，正确的是( D ) 。 A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点 B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点 D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点 6.k层二叉树的结点总数最多为( A ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.对线性表进行二分法查找，其前提条件是( C ). A.线性表以链接方式存储，并且按关键码值排好序 B.线性表以顺序方式存储，并且按关键码值的检索频率排好序 C.线性表以顺序方式存储，并且按关键码值排好序 D.线性表以链接方式存储，并且按关键码值的检索频率排好序 8.对n个记录进行堆排序，所需要的辅助存储空间为 C A. O（1og2n） B. O（n） C. O（1） D. O（n2） 9.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K） =K %7作为散列函数，则散列地址为0的元素有（ D ）个， A．1 B．2 C．3 D．4 10.下列关于数据结构的叙述中，正确的是( D ). A.数组是不同类型值的集合 B.递归算法的程序结构比迭代算法的程序结构更为精炼 C.树是一种线性结构 D.用一维数组存储一棵完全二叉树是有效的存储方法 二、填空题（每空1分，共26分） 1.数据的逻辑结构被分为_________、________、__________和___________四种。 2.一个算法的时间复杂度为(3n3+2000n log2n+90)/n2，其数量级表示为________。 3.对于一个长度为n的单链存储的队列，在表头插入元素的时间复杂度为_________，在 表尾插入元素的时间复杂度为____________。 4.假定一棵树的广义表表示为A（D（E，G），H（I，J）），则树中所含的结点数为__________ 个，树的深度为___________，树的度为_________。 5.后缀算式79 2 30 + - 4 2 / *的值为__________。中缀算式（3+X*Y）-2Y/3对 应的后缀算式为_______________________________。 6.在一棵高度为5的理想平衡树中，最少含有_______个结点，最多含有_______个结点。 7.在树中，一个结点的直接后继结点称为该结点的________。一个结点的直接前趋结点称 为该结点的________。 8.在一个具有10个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的 有向完全图中，包含有________条边。 9.假定一个线性表为(12,17,74,5,63,49,82,36)，若按Key % 4条件进行划分，使得同一余数 的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 10.对一棵B_树进行删除元素的过程中，若最终引起树根结点的合并时，会使新树的高度 比原树的高度___________。 11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序 过程的时间复杂度为________。 12.在线性表的散列存储中，装填因子α又称为装填系数，若用m表示散列表的长度，n表 示待散列存储的元素的个数，则α等于________。 三、运算题（每题6 分，共24分） 1．在如下数组A中链接存储了一个线性表，表头指针存放在A [ 0].next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 4 0 5 2 7 1 3 2．已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ, 中序遍历的结果是KBCDAFHIGJ, 试画出这棵二叉树。 3．已知一个图的顶点集V为：V={1,2,3,4,5,6,7}; 其共有10条边。该图用如下边集数组存储： 起点 1 2 2 5 5 2 2 6 1 3 终点 6 4 5 4 7 6 7 7 7 5 权 1 1 2 2 2 3 3 4 5 7 试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。 4．画出向小根堆中加入数据4, 2, 5, 8, 3, 6, 10, 1时，每加入一个数据后堆的变化。 四、阅读算法（每题7分，共14分） 1.在下面的每个程序段中，假定线性表La的类型为List，元素类型ElemType为int， 并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。 （1）InitList(La); Int a[]={100,26,57,34,79}; For (i=0;i<5;i++) Insert(La,a[i]); TraverseList(La); （2）DeleteFront(La); InsertRear(La, DeleteFront(La)); TraverseList(La); （3）ClearList(La); For (i=0;i<5;i++) InsertFront(La,a[i]); TraverseList(La); 2.现面算法的功能是什么？ void ABC(BTNode * BT) { if BT { cout< ABC(BT->left); ABC(BT->right); } } 五、算法填空（共8分） 二分查找的递归算法。 Int Binsch(ElemType A[],int low,int high,KeyType K) { if ___________________{ int mid=(low+high)/2; if (_____________________) return mid; //查找成功，返回元素的下标 else if (K return Binsch(A,low,mid-1,K); //在左子表上继续查找 else return_____________________________； //在右子表上继续查找 } else ________________； //查找失败，返回-1 } 六、编写算法（共8分） HL为单链表的表头指针，试写出在该单链表中查找具有给定的元素item的算法。 bool Find(LNode* HL, ElemType &item) 模拟试卷二参考答案 一、单选题（每题2分，共20分） 1.B 2.B 3.A 4.C 5.D 6.A 7.C 8.C 9.D 10.D 二、填空题（每空1分，共26分） 1.集合结构线性结构树结构图结构 2.O(n) 3.O(1) O(1) 4.7 2 2 5.94 3 X Y * + 2 Y * 3 / - 6. 16 31 7. 孩子（或子）结点 双亲（或父）结点 8. 45 n(n-1) 9. （12，36） （17,5,49） （74，82） （63） 10. 减少1（或减少） 11. O(log 2n) O(nlog 2n) 12. n/m 三、 运算题（每题6分，共24分） 1. 线性表为：（90，40，78，50，34，60） 2. 当前序序列为ABKCDFGHIJ ，中序序列为KBCDAFHIGJ 时，逐步形成二叉树的过程 如下图4所示： 图4 3. 用克鲁斯卡尔算法得到的最小生成树为： (1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)7 4. 见图5。 图 5 四、 阅读算法（每题7分，共14分） 1. (1) La=(26,34,57,79,100) (2)La=(57,79,100,34) (3)La=(79,34,57,26,100) 2. 前序遍历链式存储的二叉树。 五、 算法填空（每空2分，共8 分） (low<=high) K==A[mid].key Binsch(A,mid+1,hight,K) return -1 六、 编写算法（8分） bool Find(LNode* HL, ElemType &item) { LNode* p=HL; while p if (p->data==item){ KBCD FHIGJ A A B K F CD HIGJ A B K F C D G J HI A B K F C D G J H I 4 4 4 4 4 2 2 2 5 5 5 2 2 8 8 4 3 5 2 8 3 4 5 2 8 3 4 6 5 2 8 3 4 6 10 5 1 3 2 4 6 10 8 return true; } else p=p->next; return false; } 模拟试卷三 一、单选题（每题2 分，共20分） 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行 ( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.对线性表，在下列哪种情况下应当采用链表表示？( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.AOV网是一种（D ）。 A．有向图B．无向图C．无向无环图D．有向无环图 6.采用开放定址法处理散列表的冲突时，其平均查找长度（B ）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。 A．值B．函数C．指针D．引用 8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的 （ A ）。 A．行号B．列号C．元素值D．非零元素个数 9.快速排序在最坏情况下的时间复杂度为（D ）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题（每题6 分，共24分） 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N） 的联系时，称这种结构为_____________________。 2.队列的插入操作是在队列的_________进行，删除操作是在队列的__________进行。 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件 是_____________________。 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j 从0到3 ，则二维数组W 的数据元素共占用＿_____＿个字节。W 中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W ，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 6. 广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 7. 二叉树是指度为2的____________________树。一棵结点数为N 的二叉树，其所有结 点的度的总和是_____________。 8. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由 算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。 9. 对于一棵具有n 个结点的二叉树，用二叉链表存储时，其指针总数为_____________个， 其中_______________个用于指向孩子，_________________个指针是空闲的。 10. 若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A 中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为________,右孩子元素为_______________，双亲元素为____________。 11. 在线性表的散列存储中，处理冲突的常用方法有________________________和 _____________________________两种。 12. 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_______________ 排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用________________________排序。 三、 运算题（每题6分，共24分） 1. 已知一个6?5稀疏矩阵如右所示，试： （1） 写出它的三元组线性表； （2） 给出三元组线性表的顺序存储表示。 2. 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。 3. 对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻 接表中的边结点都是按照终点序号从小到大的次序链接的，试写出： (1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树； 4. 已知一个图的顶点集V 和边集E 分别为： V={1,2,3,4,5,6,7}; E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>}; 若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。 四、 阅读算法（每题7分，共14分） 1. int Prime(int n) { int i=1; int x=(int) sqrt(n); ??? ? ?? ? ? ????????????--00700000052000000010000001000 0 图6 while (++i<=x) if (n%i==0) break; if (i>x) return 1; else return 0; } (1)指出该算法的功能； (2)该算法的时间复杂度是多少？ 2.写出下述算法的功能： void AJ(adjlist GL, int i, int n) { Queue Q; InitQueue(Q); cout< visited[i]=true; QInsert(Q,i); while(!QueueEmpty(Q)) { int k=QDelete(Q); edgenode* p=GL[k]; while(p!=NULL) { int j=p->adjvex; if(!visited[j]) { cout< visited[j]=true; QInsert(Q,j); } p=p->next; } } } 五、算法填空（共8分） 如下为二分查找的非递归算法，试将其填写完整。 Int Binsch(ElemType A[ ],int n,KeyType K) { int low=0; int high=n-1; while (low<=high) { int mid=_______________________________； if (K==A[mid].key) return mid; //查找成功，返回元素的下标 else if (K<[mid].key) ______________________________________; //在左子表上继续查找 else __________________________________; //在右子表上继续查找 } return -1; //查找失败，返回-1 } 六、编写算法（共8分） HL是单链表的头指针，试写出删除头结点的算法。ElemType DeleFront(LNode * & HL) 模拟试卷三参考答案 一、单选题（每题2分，共20分） 1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C 二、填空题（每空1分，共26分） 1.联系图（或图结构） 2.尾首 3.top==0 4.O（1）O（n） 5.128 44 108 6. 3 3 7.有序n-1 8.有序序列后缀表达式（或逆波兰式） 9.2n n-1 n+1 10.2i+1 2i+2 (i-1)/2 11.开放定址法链接法 12.快速归并 三、运算题（每题6分，共24分） 1.（1）((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (3分) （2）三元组线性表的顺序存储表示如图7示。 2.如图8所示。 3.DFS：①②③④⑤ BFS：②③④⑤① 4.拓朴排序为：4 3 6 5 7 2 1 四、阅读算法（每题7分，共14分） 1.(1) 判断n是否是素数（或质数） （2）O（n） 2.功能为：从初始点v i出发广度优先搜索由邻接表GL所表示的图。 五、算法填空（8 分） (low+high)/2 high=mid-1 low=mid+1 6 5 5 1 5 1 3 2 -1 4 5 -2 5 1 5 6 3 7 图7 图8 六、编写算法（8分） ElemType DeleFront(LNode * & HL) { if (HL==NULL){ cerr<<"空表"< exit(1); } LNode* p=HL; HL=HL->next; ElemType temp=p->data; delete p; return temp; } 模拟试卷四 一、单选题（每题2 分，共20分） 1.以下数据结构中哪一个是线性结构？( B ) A. 有向图 B. 栈 C. 二叉树 D. B树 2.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采 用( C )存储方式最节省时间。 A.单链表 B.双链表 C.带头结点的双循环链表 D.单循环链表 3.以下哪一个不是队列的基本运算？（A ） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以 组成( B )个不同的字符串？ A.15 B.14 C.16 D.21 5.由权值分别为4,7,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( B )。 A． 11 B.37 C. 19 D. 53 以下6-8题基于下面的叙述：若某二叉树结点的中序遍历的序列为A、B、C、D、E、 F、G，后序遍历的序列为B、D、C、A、F、 G、E。 6.则该二叉树结点的前序遍历的序列为( C ). A. E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树有（A ）个叶子。 A．3 B.2 C.5 D.4 8.该二叉树的按层遍历的序列为( C ) A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面的二叉树中，( C )不是完全二叉树。 10.设有关键码序列(q，g，m，z，a)，下面哪一个序列是从上述序列出发建的小根堆的结 果?( C ) A. a，g，m，q， z B. a，g，m，z,q C. g，m，q，a，z D. g， m， a，q，z 二、填空题（每空1分，共26分） 1.数据结构是指数据及其相互之间的______________。当结点之间存在1对N（1：N） 的联系时，称这种结构为_____________________。 2.一个广义表中的元素分为________元素和________元素两类。 3.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 4.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是_________________; 删除一个结点时，需要执行的操作是___________________________（假设栈不空而且无需回收被删除结点）。 5.栈又称为_______________表，队列又称为___________表。 6.在稀疏矩阵所对应的三元组线性表中，每个三元组元素按_________为主序、_________ 为辅序的次序排列。 7.若一棵二叉树中只有叶子结点和左、右子树皆非空的结点，设叶结点的个数为K，则左、 右子树皆非空的结点个数是________。 8.以折半（或二分）查找方法从长度为8的有序表中查找一个元素时，平均查找长度为 ________。 9.表示图的三种常用的存储结构为_____________、____________和_______________。 10.对于线性表（78，4，56，30，65）进行散列存储时，若选用H（K）=K %5作为散列 函数，则散列地址为0的元素有________个，散列地址为4的有_______个。 11.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 12.在n个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为 ________。WPL称为_____________________。 13.在索引表中，若一个索引项对应主表的一个记录，则此索引为__________索引，若对 应主表的若干条记录，则称此索引为________索引。 三、运算题（每题6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2H)+1 （2）2+X*(Y+3) 2.假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按 层遍历的结果。 先序： 中序： 后序： 按层： 3. 已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示 0100110010000110110110110?????????? ?????? (1) 画出该图的图形； （2）根据邻接矩阵从顶点a 出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。 4. 已知一个图的顶点集V 和边集E 分别为： V={0,1,2,3,4,5,6,7}; E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20}; 按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。 四、 阅读算法（每题7分，共14分） 1. void AE(Stack& S){ InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a[5]={2,5,8,22,15}; for(i=0;i<5;i++) Push(S,a[i]); while(!StackEmpty(S)) cout< 该算法被调用后得到的输出结果为： 2. int akm ( unsigned m, unsigned n ) { if ( m == 0 ) return n+1; else if ( n == 0 ) return akm ( m-1, 1 ); else return akm ( m-1, akm ( m, n-1 ) ); } 该函数执行的功能是什么？ 五、 算法填空（共8分） 二叉搜索树的查找——非递归算法 bool Find(BTreeNode* BST,ElemType& item) {while(BST(!=NULL){ if (item==______________){ item=BST->data;//查找成功 return true;} else if(item a b c d e BST=BST->_____________; else BST=BST->_____________; }//while return _____________;//查找失败 } 六、编写算法（共8分） 用递归的算法编写出对存入在a[n+1]数组中的n个有序元素进行二分（又称折半）查找（假定a[0]单元不用）的程序。 int halfsearch(SSTable *a, KeyType k,int low,int high) 模拟试卷四参考答案 一、单选题（每题2分，共20分） 1.B 2.C 3.A 4.B 5.B 6.C 7.A 8.C 9.C 10.B 二、填空题（每空1分，共26分） 1.联系树（或树结构） 2.单（子）表 3.O(n) O(1) 4.p->next=HS;HS=p HS=HS->next 5.先进后出先进先出 6.行列 7.k-1 8. 2.625 9.邻接矩阵邻接表边集数组 10.2 1 11.O(n) O(nlog2n) O(n) 12.哈夫曼树带权路径长度 13.稠密稀疏 三、运算题（每题6分，共24分） 1.(1) 3 X * Y 2 H *- / 1 + （2） 2 X Y 3 + * + 2.先序：a,b,c,d,e,f 中序： c,b,a,e,d,f 后序： c,b,e,f,d,a 按层：a,b,d,c,e,f 3.（1）该图的图形如图9示： （2）深度优先遍历序列为：abdce 广度优先遍历序列为：abedc 4.普里姆：(0,3)2, (0,2)5, (0,1)8, (1,5)6, (3,6)10, (6,4)4, (5,7)20 四、阅读算法（每题7分，共14分） 3.15 22 8 5 2 10 4.该函数的功能是：图9 求：akm m n n m akm m m n akm m akm m n m n (,)(,), (,(,)), = += -≠= --≠≠ ? ? ? ? ? 10 1100 1100 当时 当时 当时 五、算法填空（共8分，每一空2分） BST->data left right false 六、编写算法（8分） 递归算法： int halfsearch(SSTable *a, KeyType k,int low,int high) { if (low>high) return 0; else { int mid=(low+high)/2 if EQ(k,a[mid].key) return mid; else if LT(k,a[mid].key) return halfsearch(a,k,low,mid-1); else return halfsearch(a,k,mid+1,high); } } 模拟试卷五 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( A )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( D ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( D ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。C A．688 B．678 C．692 D．696 5.树最适合用来表示( C )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( A ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( D ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8. 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为A A. O （1） B. O （n ） C. O （1og 2n ） D. O （n2） 9. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H （K ）=K %9作为散列函数，则散列地址为1的元素有（ C ）个， A ．1 B ．2 C ．3 D ．4 10. 设有6个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、 填空题（每空1分，共26分） 1. 通常从四个方面评价算法的质量：_________、_________、_________和_________。 2. 一个算法的时间复杂度为(n 3+n 2log 2n +14n )/n 2，其数量级表示为________。 3. 假定一棵树的广义表表示为A （C ，D （E ，F ，G ），H （I ，J ）），则树中所含的结点数 为__________个，树的深度为___________，树的度为_________。 4. 后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X ）-2Y/3对应的后缀算式 为_______________________________。 5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n 个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 6. 对于一个具有n 个顶点和e 条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 7. AOV 网是一种___________________的图。 8. 在一个具有n 个顶点的无向完全图中，包含有________条边，在一个具有n 个顶点的有 向完全图中，包含有________条边。 9. 假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 10. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度 ___________。 11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序 过程的时间复杂度为________。 12. 在快速排序、堆排序、归并排序中，_________排序是稳定的。 三、 运算题（每题 6 分，共24分） 1. 在如下数组A 中链接存储了一个线性表，表头指针为A [0].next ，试写出该线性表。 A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 2. 请画出图10的邻接矩阵和邻接表。 3. 已知一个图的顶点集V 和边集E 分别为： V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 4. 画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。 图10 四、阅读算法（每题7分，共14分） 1.LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1：while(p－>next) p=p－>next； S2：p－>next=q；q－>next=NULL； } return L； } 请回答下列问题： （1）说明语句S1的功能； （2）说明语句组S2的功能； （3）设链表表示的线性表为（a1,a2, …,a n）,写出算法执行后的返回值所表示的线性表。 2.void ABC(BTNode * BT) { if BT { ABC (BT->left); ABC (BT->right); cout< } } 该算法的功能是： 五、算法填空（共8分） 二叉搜索树的查找——递归算法: bool Find(BTreeNode* BST,ElemType& item) { if (BST==NULL) return false; //查找失败 else { if (item==BST->data){ item=BST->data;//查找成功 return ___________;} else if(item return Find(______________,item); else return Find(_______________,item); }//if } 六、编写算法（共8分） 统计出单链表HL中结点的值等于给定值X的结点数。 int CountX(LNode* HL,ElemType x) 模拟试卷五参考答案 一、 单选题（每题2分，共20分） 1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 二、 填空题（每空1分，共26分） 1. 正确性 易读性 强壮性 高效率 2. O(n) 3. 9 3 3 4. -1 3 4 X * + 2 Y * 3 / - 5. 2n n-1 n+1 6. e 2e 7. 有向无回路 8. n(n-1)/2 n(n-1) 9. （12，40） （ ） （74） （23,55，63） 10.增加1 11.O(log 2n) O(nlog 2n) 12.归并 三、 运算题（每题6分，共24分） 1. 线性表为：（78，50，40，60，34，90） 2. 邻接矩阵：??????? ?????? ???01 110 1010111011 101010111 邻接表如图11所示： 图11 3. 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 4. 见图12 4 4 2 2 2 第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 （2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A．存储结构B．存储实现 C．逻辑结构D．运算实现 （3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（）。 A．顺序队列B.链表C.有序表D.链栈 （6）以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90;y=100; while(y>0) if(x>100) {x=x-10;y--;} elsex++; （2）for(i=0;i 第一章绪论 习题一?1．设x＞0，x＊的相对误差为δ,求f(ｘ)=ln x的误差限。 解:求lnx的误差极限就是求f(x)=lnx的误差限，由公式(１.2.４）有 已知x*的相对误差满足，而 ,故 即 2.下列各数都是经过四舍五入得到的近似值,试指出它们有几位有效数字，并给出其误差限与相对误差限。 解:直接根据定义和式（１.2.２)(1.２.3）则得?有５位有效数字，其误差限,相对误差限 有２位有效数字， 有5位有效数字， 3．下列公式如何才比较准确？ (１)?(2） 解:要使计算较准确，主要是避免两相近数相减，故应变换所给公式。 （1)?(2） 4.近似数x*=０.０３１0,是 3 位有数数字。 5.计算取,利用 :式计算误差最小。 四个选项: 第二、三章插值与函数逼近 习题二、三 1. 给定的数值表 用线性插值与二次插值计算ln０．5４的近似值并估计误差限. 解：仍可使用n＝1及n＝２的Laｇrange插值或Neｗｔo ｎ插值，并应用误差估计（5.8)。线性插值时,用0．５及0．6两点，用Newton插值??误差限 ，因, 故? 二次插值时，用0.5，0．6,０.7三点,作二次Ｎewton插值 ?误差限，故? 2. 在－4≤x≤4上给出的等距节点函数表，若用二次插值法求的近似值，要使误差不超过,函数表的步长ｈ应取多少? 解：用误差估计式（５．8), ?令 因?得 3. 若,求和. 解：由均差与导数关系 ?于是 4. 若互异,求 的值,这里p≤n+1. 解:,由均差对称性 可知当有?而当P＝n ＋1时 ?于是得 5. 求证. 解:解:只要按差分定义直接展开得 ? 6. 已知的函数表 泛函分析答案： 1、 所有元素均为0的n ×n 矩阵 2、 设E 为一线性空间，L 是E 中的一个子集，若对任意的x,y ∈L ，以及变数λ和μ均有λx ＋μy ∈L ，则L 称为线性空间E 的一个子空间。子空间心室包含零元素，因为当λ和μ均为0时，λx ＋μy ＝0∈L ，则L 必定含零元素。 3、 设L 是线性空间E 的子空间，x 0∈E\L,则集合x 0+L={x 0+l,l ∈L}称为E 中一个线性流形。 4、 设M 是线性空间E 中一个集合，如果对任何x,y ∈M ，以及λ＋μ＝1，λ≥0，μ≥0的 λ和μ，都有λx ＋μy ∈M ，则称M 为E 中的凸集。 5、 设x,y 是线性空间E 中的两个元素，d(x,y)为其之间的距离，它必须满足以下条件： （1） 非负性：d(x,y)＞0，且d(x,y)＝0＜―――＞x=y （2） d(x,y)=d(y,x) （3） 三角不等式：d(x,y)≤d(x,z)+d(y,z) for every x,y,z ∈E n 维欧几里德空间常用距离定义： 】 设x={x 1,x 2,…x n }T ,y={y 1y 2,…y n }T d 2(x,y)=( 21 ||n i i i x y =-∑)1/2 d 1(x,y)=1 ||n i i i x y =-∑ d p (x,y) = ( 1 ||n p i i i x y =-∑ )1/p d ∞(x,y)=1max ||i i i n x y ≤≤- 6、距离空间(x,d)中的点列{x n }收敛到x 0是指d(x n ,x 0)0(n ∞)，这时记作 0lim n n x x -->∞ =，或 简单地记作x n x 0 7、设||x||是线性空间E 中的任何一个元素x 的范数，其须满足以下条件： （1）||x||≥0,且||x||＝0 iff x=0 （2）||λx||=λ||x||,λ为常数 （3）||x+y||≤||x||+||y||,for every x,y ∈E 8、设E 为线性赋范空间，｛x n ｝∞ n=1是其中的一个无穷列，如果对于任何ε>0,总存在自然数N ，使得当n>N,m>N 时，均有|x m -x n |<ε,则称序列{x n }是E 中的基本列。若E 的基本列的收敛元仍属于E ，则称E 为完备的线性赋范空间，即为Banach 空间。线性赋范空间中的基本列不一定收敛。 9、有限维的线性赋范空间必然完备，所以它必定是Banach 空间。 $ 10、如果内积空间能在由内积诱导的赋范空间完备，则此内积空间称为Hilbert 空间。 11、L 2（a,b ）为定义在(a,b)上平方可积函数空间，即设f(t)∈L 2（a,b ）, 2|()|b a f t dt ? ＜∞。 当 L 2（a,b ）中内积的定义为（f,g ）= _____ ()()b a f t g t dt ? (其中f(t),g(t)∈L 2（a,b ）)时其为Hilbert 空间。 ★ 12、算子表示一种作用，一种映射。设X 和Y 是给定的两个线性赋范空间，集合D ?X ， 若对D 中的每一个x ，均有Y 中的一个确定的变量y 与其对应，则说这种对应关系确定 习 9解答 判断题： 1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 答：FALSE (错。链表表示的有序表不能用折半查找法。) 2.有n 个数据放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无序其平均查找长度不同。 答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL 相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL 要比有序表的ASL 小。) 3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( ) 答：TRUE 4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答：TRUE 5.查找表是由同一类型的数据元素(或记录)构成的集合。 答：TRUE 单选题： 6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。 A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答：D (第一次??2/)181(+ = 9,第二次??2/)81(+ = 4，第三次??2/)31(+ = 2, (第四次??2/)33(+ = 3，故选D. 7. 顺序查找法适合于存储结构为____________的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 答：B 8.对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B. 以链接方式存储 C ．以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 答：C 9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图 新媒体运营数据分析思维 如果以下有任何一条击中你，说明你正在做无用或者表面的数据分析 *把微信数据后台的图截屏出来做工作报告，然而并没有什么卵用 *认为关注文章的阅读数、点赞数、评论数就是数据分析 *微信更新的内容，是你“想”到的内容，而不是根据数据依据推动出来的内容 *你没法证明产品转化和你的微信运营有什么卵关系 做微信运营数据分析核心点在于：你怎么证明你的工作对公司有价值 显然，以上提到的每一点，都无法证明你的工作非常牛叉，都无法证明业务转化和你有半毛钱关系，都无法证 明你的你更新的每一篇文章，是有依据的更新。 结果是： 1.微信阅读高评论多的时候，领导同事说，好耶，然后就没有然后了。 2.领导说让你更新什么文章就更新什么文章，反正大家都是拍脑袋决定写什么，那就听领导的 3.你涨薪无望，因为你在老板眼里，除了能每周写3篇文章，你还能干嘛 4.你进步无门，你压根不知道内容吸引的是什么用户，吸引了多少用户，转化了多少用户 如果你可以利用数据告诉你的老板，你的工作对公司有这样的价值： 你会说：“在x天的周期内，零成本，通过微信引流100名潜在付费用户，实际转化34人，（举例产品单价1000），共获得收益34000。” 你的老板会给你一个拥吻说，小张啊，我想给你谈谈给你涨工资的事情，万事好商量嘛。 所以问题确切说应该是：如何做能证明和最终转化有关的微信运营数据分析 要想做好微信效果数据分析，就要设置好，微信转化路径，这里举例把最终转化结果作为最终转化目标（如果 你的产品是社交产品，那你想清楚最终目标是什么），从一个陌生用户阅读你的文章开始，这就进入了一个转 化漏斗。在转化过程中，你可以设置多个转化环节，你也可以理解为是为了达到最终转化目标而设定的分目标。 具体执行起来会，你可以得出来这样一条路径 第一步：通过微信文章获取来阅读文章的用户 注意，文章内容本身要和产品相关，不要把注意力放在阅读数和评论数上，你要记得你最终的目标是转化数字， 第一章 1、ln2＝0.69314718…，精确到 10－3 的近似值是多少？ 解 精确到 10－3＝0.001，即绝对误差限是 e ＝0.05％，故至少要保留小数点后三位才可以。 ln2≈0.693。 2、设115.80,1025.621≈≈x x 均具有5位有效数字，试估计由这些数据计算21x x ， 21x x +的绝对误差限 解：记126.1025, 80.115x x == 则有11232411 10, | 102|||2 x x x x --≤?-≤?- 所以 121212121212211122||||||||||||x x x x x x x x x x x x x x x x x x -=-+-+≤-- 3411 80.11610 6.10102522 0.007057-==??+≤?? 1212112243|()|||11 |10100.0005522 |x x x x x x x x --≤≤?+?=+-+-+- 3、一个园柱体的工件,直径d 为10.250.25mm,高h 为40.00 1.00mm,则它的体 积V 的近似值、误差和相对误差为多少。 解： ()() 22222222 4 314210254000000330064 221025400002510251002436444 3300624362436 0073873833006 , .....; ()()()......, ..().()..% .r d h V d h V mm d h V dh d d h V mm V V V πππππεεεεε= ≈=??===+=???+?==±====第二章： 1、分别利用下面四个点的Lagrange 插值多项式和Newton 插值多项式N 3(x )， 计算L 3(0.5)及N 3(-0.5) x －2 －1 0 1 f (x ) －1 1 2 泛函分析答案： 1、所有元素均为0的n ×n 矩阵 2、设E 为一线性空间，L 是E 中的一个子集，若对任意的x,y ∈L ，以及变数λ和μ均有λx ＋μy ∈L ，则L 称为线性空间E 的一个子空间。子空间心室包含零元素，因为当λ和μ均为0时，λx ＋μy ＝0∈L ，则L 必定含零元素。 3、设L 是线性空间E 的子空间，x 0∈E\L,则集合x 0+L={x 0+l,l ∈L}称为E 中一个线性流形。 4、设M 是线性空间E 中一个集合，如果对任何x,y ∈M ，以及λ＋μ＝1，λ≥0，μ≥0的λ和μ，都有λx ＋μy ∈M ，则称M 为E 中的凸集。 5、设x,y 是线性空间E 中的两个元素，d(x,y)为其之间的距离，它必须满足以下条件： （1） 非负性：d(x,y)＞0，且d(x,y)＝0＜―――＞x=y （2） d(x,y)=d(y,x) （3） 三角不等式：d(x,y)≤d(x,z)+d(y,z)foreveryx,y,z ∈E n 维欧几里德空间常用距离定义： 设x={x 1,x 2,…x n }T ,y={y 1y 2,…y n }T d 2(x,y)=(21 ||n i i i x y =-∑)1/2 d 1(x,y)=1 ||n i i i x y =-∑ d p (x,y)=(1 ||n p i i i x y =-∑)1/p d ∞(x,y)=1max ||i i i n x y ≤≤- 6、距离空间(x,d)中的点列{x n }收敛到x 0是指d(x n ,x 0)?0(n ?∞)，这时记作 0lim n n x x -->∞ =，或简单地记作x n ?x 0 7、设||x||是线性空间E 中的任何一个元素x 的范数，其须满足以下条件： （1）||x||≥0,且||x||＝0 iffx=0 （2）||λx||=λ||x||,λ为常数 （3）||x+y||≤||x||+||y||,foreveryx,y ∈E 8、设E 为线性赋范空间，｛x n ｝∞n=1是其中的一个无穷列，如果对于任何ε>0,总存在自然数N ，使得当n>N,m>N 时，均有|x m -x n |<ε,则称序列{x n }是E 中的基本列。若E 的基本列的收敛元仍属于E ，则称E 为完备的线性赋范空间，即为Banach 空间。线性赋范空间中的基本列不一定收敛。 9、有限维的线性赋范空间必然完备，所以它必定是Banach 空间。 10、如果内积空间能在由内积诱导的赋范空间完备，则此内积空间称为Hilbert 空间。 11、L 2 （a,b ）为定义在(a,b)上平方可积函数空间，即设f(t)∈L 2 （a,b ）,2|()|b a f t dt ?＜∞。 数值分析习题集 （适合课程《数值方法A 》和《数值方法B 》） 长沙理工大学 第一章 绪 论 1. 设x >0,x 的相对误差为δ,求ln x 的误差. 2. 设x 的相对误差为2％,求n x 的相对误差. 3. 下列各数都是经过四舍五入得到的近似数,即误差限不超过最后一位的半个单位,试指出 它们是几位有效数字: *****123451.1021,0.031,385.6,56.430,7 1.0.x x x x x =====? 4. 利用公式(3.3)求下列各近似值的误差限: ********12412324(),(),()/,i x x x ii x x x iii x x ++其中**** 1234 ,,,x x x x 均为第3题所给的数. 5. 计算球体积要使相对误差限为1％,问度量半径R 时允许的相对误差限是多少? 6. 设028,Y =按递推公式 1n n Y Y -=( n=1,2,…) 计算到100Y .27.982(五位有效数字),试问计算100Y 将有多大误差? 7. 求方程2 5610x x -+=的两个根,使它至少具有四位有效数字27.982). 8. 当N 充分大时,怎样求2 1 1N dx x +∞+?? 9. 正方形的边长大约为100㎝,应怎样测量才能使其面积误差不超过1㎝2 ? 10. 设 212S gt = 假定g 是准确的,而对t 的测量有±0.1秒的误差,证明当t 增加时S 的绝对 误差增加,而相对误差却减小. 11. 序列 {}n y 满足递推关系1101n n y y -=-(n=1,2,…),若0 1.41y =≈(三位有效数字), 计算到 10y 时误差有多大?这个计算过程稳定吗? 12. 计算6 1)f =, 1.4≈,利用下列等式计算,哪一个得到的结果最好? 3 -- 13. ()ln(f x x =,求f (30)的值.若开平方用六位函数表,问求对数时误差有多大?若 第七章 习题解答 1．设（X ，d ）为一度量空间，令 }),(,|{),(},),(,|{),(0000εεεε≤∈=<∈=x x d X x x x S x x d X x x x U 问),(0εx U 的闭包是否等于),(0εx S ？ 解 不一定。例如离散空间（X ，d ）。)1,(0x U ={0x }，而)1,(0x S =X 。 因此当X 多于两点时，)1,(0x U 的闭包不等于)1,(0x S 。 2. 设 ],[b a C ∞是区间],[b a 上无限次可微函数的全体，定义 证明],[b a C ∞按),(g f d 成度量空间。 证明 （1）若),(g f d =0，则) ()(1)()(max ) () ()()(t g t f t g t f r r r r b t a -+-≤≤=0，即f=g （2）)()(1)()(max 2 1 ),()()()()(0t g t f t g t f g f d r r r r b t a r r -+-=≤≤∞ =∑ =d （f ，g ）+d （g ，h ） 因此],[b a C ∞按),(g f d 成度量空间。 3． 设B 是度量空间X 中的闭集，证明必有一列开集ΛΛn o o o 21,包含B ，而且B o n n =?∞ =1 。 证明 令n n n o n n B x d Bo o .2,1},1 ),({K =<==是开集：设n o x ∈0，则存在B x ∈1，使 n x x d 1),(10<。设,0),(1 10>-=x x d n δ则易验证n o x U ?),(0δ，这就证明了n o 是 开集 显然B o n n ??∞=1 。若n n o x ∞ =?∈1 则对每一个n ，有B x n ∈使n x x d 1 ),(1< ，因此 精心整理 第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现？ 5 A 6 {x=x-10;y--;} elsex++; （2）for(i=0;i （4）i=1; while(i<=n) i=i*3; （5）x=0; for(i=1;i （8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。 A．nB．2n-1 C．2nD．n-1 （9）在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（）个元素。 A．n-i B．n-i+1 C．n-i-1D．i (10)线性表L=(a1，a2,……a n)，下列说法正确的是（）。 A．每个元素都有一个直接前驱和一个直接后继 B．线性表中至少有一个元素 C．表中诸元素的排列必须是由小到大或由大到小 D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 (11)若指定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是（）。 2 , pa=La->next;pb=Lb->next; Lc=pc=La;//用La的头结点作为Lc的头结点 while(pa&&pb){ if(pa->data 第一章绪论 习题一 1.设x>0,x*的相对误差为δ，求f(x)=ln x的误差限。 解：求lnx的误差极限就是求f(x)=lnx的误差限，由公式(1.2.4)有 已知x*的相对误差满足，而 ，故 即 2.下列各数都是经过四舍五入得到的近似值，试指出它们有几位有效数字，并给出其误差限与相对误差限。 解：直接根据定义和式(1.2.2)(1.2.3)则得 有5位有效数字，其误差限，相对误差限 有2位有效数字， 有5位有效数字， 3.下列公式如何才比较准确？ （1） （2） 解：要使计算较准确，主要是避免两相近数相减，故应变换所给公式。 （1） （2） 4.近似数x*=0.0310,是 3 位有数数字。 5.计算取，利用：式计算误差最小。 四个选项： 第二、三章插值与函数逼近 习题二、三 1. 给定的数值表 用线性插值与二次插值计算ln0.54的近似值并估计误差限. 解：仍可使用n=1及n=2的Lagrange插值或Newton插值,并应用误差估计（5.8）。线性插值时，用0.5及0.6两点， 用Newton插值 误差限，因 ，故 二次插值时，用0.5，0.6，0.7三点，作二次Newton插值 误差限 ，故 2. 在-4≤x≤4上给出的等距节点函数表，若用二次插值法求的近似值，要使误差不超过，函数表的步长h应 取多少? 解：用误差估计式（5.8）， 令 因 得 3. 若，求和. 解：由均差与导数关系 于是 4. 若互异，求 的值，这里p≤n+1. 解：，由均差对称性 可知当有 而当P＝n＋1时 于是得 5. 求证. 解：解：只要按差分定义直接展开得 6. 已知的函数表 求出三次Newton均差插值多项式，计算f(0.23)的近似值并用均差的余项表达式估计误差. 解：根据给定函数表构造均差表 由式(5.14)当n=3时得Newton均差插值多项式 N3(x)=1.0067x+0.08367x(x-0.2)+0.17400x(x-0.2)(x-0.3) 由此可得 f(0.23) N3(0.23)=0.23203 由余项表达式(5.15)可得 由于 《计算方法》期中复习试题 一、填空题： 1、已知3.1)3(,2.1)2(,0.1)1(===f f f ，则用辛普生（辛卜生）公式计算求得 ?≈3 1 _________ )(dx x f ,用三点式求得≈')1(f 。 答案：2.367，0.25 2、1)3(,2)2(,1)1(==-=f f f ，则过这三点的二次插值多项式中2 x 的系数为 ，拉 格朗日插值多项式为 。 答案：-1， )2)(1(21 )3)(1(2)3)(2(21)(2--------= x x x x x x x L 3、近似值*0.231x =关于真值229.0=x 有( 2 )位有效数字； 4、设)(x f 可微,求方程)(x f x =的牛顿迭代格式是( )； 答案 )(1)(1n n n n n x f x f x x x '--- =+ 5、对1)(3 ++=x x x f ,差商=]3,2,1,0[f ( 1 ),=]4,3,2,1,0[f ( 0 )； 6、计算方法主要研究( 截断 )误差和( 舍入 )误差； 7、用二分法求非线性方程 f (x )=0在区间(a ,b )内的根时，二分n 次后的误差限为 ( 1 2+-n a b )； 8、已知f (1)＝2，f (2)＝3，f (4)＝5.9，则二次Newton 插值多项式中x 2系数为( 0.15 )； 11、 两点式高斯型求积公式?1 d )(x x f ≈( ?++-≈1 )] 321 3()3213([21d )(f f x x f )，代数精度 为( 5 )； 12、 为了使计算 32)1(6 )1(41310-- -+-+ =x x x y 的乘除法次数尽量地少，应将该表达 式改写为 11 ,))64(3(10-= -++=x t t t t y ，为了减少舍入误差，应将表达式1999 2001- 复习题集─参考答案 一判断题 （√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （√）2. 抽象数据类型与计算机部表示和实现无关。 （×）3. 线性表采用链式存储结构时，结点和结点部的存储空间可以是不连续的。 （×）4. 链表的每个结点中都恰好包含一个指针。 （×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （×）8. 线性表在物理存储空间中也一定是连续的。 （×）9. 顺序存储方式只能用于存储线性结构。 （√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）13.两个栈共享一片连续存空间时，为提高存利用率，减少溢出机会，应把两个栈的栈底分别设在这片存空间的两端。 （×）14.二叉树的度为2。 （√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）16.二叉树中每个结点的两棵子树的高度差等于1。 （√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）18.具有12个结点的完全二叉树有5个度为2的结点。 （√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 （×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （×）21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据] （×）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （×）23.算法必须用程序语言来书写。 （×）24.判断某个算法是否容易阅读是算法分析的任务之一。 （×）25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] （√）26.分配给顺序表的存单元地址必须是连续的。 （√）27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表] （√）28.树形结构中每个结点至多有一个前驱。 （×）29.在树形结构中，处于同一层上的各结点之间都存在兄弟关系。 （×）30.如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。 （×）31.如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。 （×）32.顺序查找方法只能在顺序存储结构上进行。 （×）33.折半查找可以在有序的双向链表上进行。 数值分析整理版试题及答案 例1、 已知函数表 x -1 1 2 ()f x -3 0 4 求()f x 的Lagrange 二次插值多项式和Newton 二次插值多项式。 解： （1）k x -1 1 2 k y -3 0 4 插值基函数分别为 ()()()()()()()()()() 1200102121()1211126 x x x x x x l x x x x x x x ----= ==-------- ()()()()()()()() ()()021******* ()1211122x x x x x x l x x x x x x x --+-= ==-+---+- ()()()()()()()()()()0122021111 ()1121213 x x x x x x l x x x x x x x --+-= ==-+--+- 故所求二次拉格朗日插值多项式为 () ()()()()()()()()()()2 20 2()11131201241162314 121123537623k k k L x y l x x x x x x x x x x x x x ==?? =-? --+?-+-+?+-????=---++-=+-∑ （2）一阶均差、二阶均差分别为 []()()[]()()[][][]010********* 011201202303 ,11204 ,412 3 4,,5 2,,126 f x f x f x x x x f x f x f x x x x f x x f x x f x x x x x ---===-----= = =----=== --- k x ()k f x 一阶 二阶 -1 -3 1 0 3/ 2 2 4 4 5/6 故所求Newton 二次插值多项式为 ()()[]()[]()() ()()()20010012012,,,35 311126537623P x f x f x x x x f x x x x x x x x x x x x =+-+--=-+ +++-=+- 例2、 设2 ()32f x x x =++，[0,1]x ∈，试求()f x 在[0, 1]上关于()1x ρ=，{} span 1,x Φ=的最佳平方逼近多项式。 解： 若{}span 1,x Φ=，则0()1x ?=，1()x x ?=，且()1x ρ=，这样，有 泛函分析复习题2012 1．在实数轴R 上，令p y x y x d ||),(-=，当p 为何值时，R 是度量 空间，p 为何值时，R 是赋范空间。 解：若R 是度量空间，所以R z y x ∈?,,，必须有： ),(),(),(z y d y x d z x d +≤成立 即p p p z y y x z x ||||||-+-≤-，取1,0,1-===z y x ， 有2112=+≤p p p ，所以，1≤p 若R 是赋范空间，p x x x d ||||||)0,(==，所以R k x ∈?,， 必须有：||||||||||x k kx ?=成立，即p p x k kx ||||||=，1=p ， 当1≤p 时，若R 是度量空间，1=p 时，若R 是赋范空间。 2．若),(d X 是度量空间，则)1,m in(1d d =，d d d +=12也是使X 成为度量空间。 解：由于),(d X 是度量空间，所以X z y x ∈?,,有： 1）0),(≥y x d ，因此0)1),,(m in(),(1≥=y x d y x d 和0) ,(1) ,(),(2≥+= y x d y x d y x d 且当y x =时0),(=y x d ， 于是0)1),,(m in(),(1==y x d y x d 和0) ,(1) ,(),(2=+=y x d y x d y x d 以及若 0)1),,(m in(),(1==y x d y x d 或0) ,(1) ,(),(2=+= y x d y x d y x d 均有0),(=y x d 成立，于是y x =成立 2）),(),(y x d x y d =， 因此),()1),,(m in()1),,(m in(),(11y x d y x d x y d x y d === 和),() ,(1) ,(),(1),(),(22y x d y x d y x d x y d x y d x y d =+=+= 3）),(),(),(z y d y x d z x d +≤，因此 }1),,(),(m in{)1),,(m in(),(1z y d y x d z x d z x d +≤= ),(),()1),,(m in()1),,(m in(11z y d y x d z y d y x d +=+≤ 以及设x x x f += 1)(，0)1(1)(2 >+='x x f ，所以)(x f 单增， 所以) ,(),(1),(),(),(1),(),(2z y d y x d z y d y x d z x d z x d z x d +++≤+= ),(),(1) ,(),(),(1),(z y d y x d z y d z y d y x d y x d +++++= ),(),() ,(1) ,(),(1),(22z y d y x d z y d z y d y x d y x d +=+++≤ 综上所述)1,m in(1d d =和d d d += 12均满足度量空间的三条件， 故),(1y x d 和),(2y x d 均使X 成为度量空间。 大学 《数据结构与算法分析》课程 习题及参考答案 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( ) 个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左 孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有 双亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题 6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7}; 数值分析复习题 一、选择题 1. 3.142和3.141分别作为π的近似数具有（ ）和（ ）位有效数字. A ．4和3 B ．3和2 C ．3和4 D ．4和4 2. 已知求积公式()()2 11211()(2)636f x dx f Af f ≈++?，则A ＝（ ） A ． 16 B ．13 C ．12 D ．2 3 3. 通过点()()0011,,,x y x y 的拉格朗日插值基函数()()01,l x l x 满足（ ） A ．() 00l x ＝0，()110l x = B ． ()00l x ＝0，()111l x = C ．()00l x ＝1，()111l x = D ． ()00l x ＝1，()111l x = 4. 设求方程()0f x =的根的牛顿法收敛，则它具有（ ）敛速。 A ．超线性 B ．平方 C ．线性 D ．三次 5. 用列主元消元法解线性方程组1231231220223332x x x x x x x x ++=??++=??--=? 作第一次消元后得到的第3个方程（ ）. A ．232x x -+= B ．232 1.5 3.5x x -+= C ．2323x x -+= D ．230.5 1.5x x -=- 二、填空 1. 设 2.3149541...x *=，取5位有效数字，则所得的近似值x= . 2.设一阶差商 ()()()21122114,321f x f x f x x x x --= ==---， ()()()322332615,422f x f x f x x x x --===-- 则二阶差商 ()123,,______f x x x = 3. 设(2,3,1)T X =--, 则2||||X = ，=∞||||X 。 4．求方程 2 1.250x x --= 的近似根，用迭代公式 1.25x x =+，取初始值 01x =， 那么 1______x =。 5．解初始值问题 00'(,)()y f x y y x y =??=?近似解的梯形公式是 1______k y +≈。 6、 1151A ??= ?-??，则A 的谱半径 ＝ 。 7、设 2()35, , 0,1,2,... , k f x x x kh k =+== ，则[]12,,n n n f x x x ++= 和[]123,,,n n n n f x x x x +++= 。 8、若线性代数方程组AX=b 的系数矩阵A 为严格对角占优阵，则雅可比迭代和高斯-塞德尔迭代都 。 9、解常微分方程初值问题的欧拉（Euler ）方法的局部截断误差为 。 10、为了使计算 23123101(1)(1)y x x x =+ +----的乘除法运算次数尽量的少,应将表达式改写 成 。 11. 设T X )4,3,2(-=, 则=1||||X ，2||||X = . 12. 一阶均差()01,f x x = 13. 已知3n =时，科茨系数()()()33301213,88C C C ===，那么 ()33C = 14. 因为方程()420x f x x =-+=在区间[]1,2上满足 ，所以()0f x =在区间内有根。 15. 取步长0.1h =，用欧拉法解初值问题()211y y y x y ?'=+???=?的计算公式 . 16.设 * 2.40315x =是真值 2.40194x =的近似值，则*x 有 位有效数字。数据结构与算法习题及答案
数值分析习题与答案
泛函分析答案
数据结构与算法复习题10(C语言版)
新媒体运营数据分析思维
数值分析复习题要答案
泛函分析答案
数值分析习题集及答案[1].(优选)
泛函分析习题解答
数据结构与算法习题及答案
数值分析习题集和答案解析
数值计算方法》试题集及答案
数据结构与算法复习题及参考答案
数值分析整理版试题及答案
最新泛函分析考试题集与答案
数据结构与算法分析习题与参考答案
数值分析复习题及答案
相关主题
文本预览