第一章 第一章 三、计算下列程序段中X=X+1 的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; [提示]： i=1 时： 1 = (1+1)×1/2 = (1+1 )/2 i=2 时： 1+2 = (1+2)×2/2 = (2+22)/2 i=3 时： 1+2+3 = (1+3)×3/2 = (3+32)/2 … i=n时： 1+2+3+……+n = (1+n)×n/2 = (n+n )/2 f(n) = [ (1+2+3+……+n) + (1 + 2 + 3 + …… + n ) ] / 2 =[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2 =n(n+1)(n+2)/6 =n /6+n /2+n/3 区分语句频度和算法复杂度： O(f(n)) = O(n ) 四、试编写算法求一元多项式Pn(x)=a +a x+a x +a x +…a x 的值P (x )，并确定算法中的每 一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能 使用求幂函数。注意：本
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
中的输入a (i=0,1,…,n), x和n，输出为P (x ).通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递； （2 ）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 [提示]：float PolyValue(float a[ ], float x, int n) {……} 核心语句： p=1; (x 的零次幂) s=0; i 从0 到n 循环 s=s+a[i]*p; p=p*x; 或： p=x; (x 的一次幂) s=a[0]; i 从 1 到n 循环 s=s+a[i]*p; p=p*x; 第二章 2.1 描述以下三个概念的区别：头指针，头结点，首元素结点。 2.2 填空： （1） 在顺序表中插入或删除一个元素，需要平均移动 一半 元素，具体移动的元素个数与 插入或删除的位置 有关。 （2 ） 在顺序表中，逻辑上相邻的元素，其物理位置 相邻。在单链表中，逻辑上相邻的元素，其物理位置 相邻。 （3） 在带头结点的非空单链表中，头结点的存储位置由 指示，首元素结点的存储位置由 指示，除首元素结点外，其它任一元素结点的存储位置由 其直接前趋的next 域 指示。 2.3 已知L 是无表头结点的单链表，且P 结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是： （4 ）、（1） 。 b. 在P结点前插入S结点的语句序列是： （7）、（11）、（8）、（4 ）、（1）。 c. 在表首插入S结点的语句序列是： （5）、（12）。 d. 在表尾插入S结点的语句序列是： （11）、（9）、（1）、（6）。 供选择的语句有： （1）P->next=S; （2 ）P->next= P->next->next; （3）P->next= S->next; （4 ）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 2.4 已知线性表L 递增有序。试写一算法，将 X 插入到 L 的适当位置上，以保持线性表L的有序性。 [提示]：void insert(SeqList *L; ElemType x) < 方法 1 > （1）找出应插入位置i，（2 ）移位，（3）…… < 方法2 > 参P. 229 2.5 写一算法，从顺序表中删除自第i 个元素开始的k 个元素。 [提示]：注意检查i 和k 的合法性。（集体搬迁，“新房”、“旧房”） < 方法 1 > 以待移动元素下标m（“旧房号”）为中心，计算应移入位置（“新房号”）： for ( m= i －1+k; m<= L－>last; m++) L －>elem[ m－k ] = L－>elem[ m ]; < 方法2 > 同时以待移动元素下标m 和应移入位置j 为中心： < 方法2 > 以应移入位置j 为中心，计算待移动元素下标： 2.6 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink 且小于maxk 的元素（若表中存在这样的元素），
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
你的算法的时间复杂度（注意：mink 和maxk 是给定的两个参变量，它们的值为任意的整数）。 [提示]：注意检查mink 和maxk 的合法性：mink < maxk不要一个一个的删除（多次修改next 域）。 （1）找到第一个应删结点的前驱pre pre=L; p=L －>next; while (p!=NULL && p －>data <= mink) { pre=p; p=p －>next; } （2 ）找到最后一个应删结点的后继s，边找边释放应删结点 s=p; while (s!=NULL && s－>data < mink) { t =s; s=s －>next; free(t); } （3）pre －>next = s; 2.7 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a ..., a ）逆置为（a , a ,..., a ）。 （1） 以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum 个分量中。 （2 ） 以单链表作存储结构。 [方法 1]:在原头结点后重新头插一遍 [方法2]:可设三个同步移动的指针p, q, r，将q 的后继r 改为p 2.8 假设两个按元素值递增有序排列的线性表A 和B，均以单链表作为存储结构，请编写算法，将A 表和B 表归并成一个按元素值递减有序的排列的线性表 C，并要求利用原表（即A 表和B 表的）结点空间存放表 C. [提示]：参P.28 例2-1 < 方法 1 > void merge(LinkList A; LinkList B; LinkList *C) { …… pa=A －>next; pb=B－>next; *C=A; (*C)－>next=NULL; while ( pa!=NULL && pb!=NULL ) { if ( pa －>data <= pb－>data ) { smaller=pa; pa=pa－>next; smaller－>next = (*C)－>next; /* 头插法 */ (*C) －>next = smaller; } else { smaller=pb; pb=pb－>next; smaller－>next = (*C)－>next; (*C) －>next = smaller; } while ( pa!=NULL) { smaller=pa; pa=pa－>next; smaller －>next = (*C)－>next; (*C) －>next = smaller; } while ( pb!=NULL) { smaller=pb; pb=pb－>next; smaller －>next = (*C)－>next; (*C) －>next = smaller; } < 方法2 > LinkList merge(LinkList A; LinkList B) { …… LinkList C； pa=A －>next; pb=B－>next; C=A; C－>next=NULL; …… …… return C; 2.9 假设有一个循环链表的长度大于 1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针 s 所指结点的前趋结点。 [提示]：设指针p 指向 s 结点的前趋的前趋，则p 与s 有何关系？ 2.10 已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 2.11 设线性表A=(a, a ,…,a )，B=(b, b ,…,b )，试写一个按下列规则合并A、B为线性表C的算法，使得： C= (a , b ,…,a , b , b …,b ) 当m≤n时； 或者 C= (a , b ,…,a , b , a …,a ) 当m>n时。 线性表 A、B、C 均以单链表作为存储结构，且 C 表利用 A 表和 B 表中的结点空间构成。 注意：单链表的长度值m 和n 均未显式存储。 [提示]：void merge(LinkList A; LinkList B; LinkList *C) 或：LinkList merge(LinkList A; LinkList B) 2.12 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。 [提示]：注明用头指针还是尾指针。 2.13 建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的 data 域存放一个二进制位。并在此链表上实现对二进制数加 1 的运算 。 [提示]：可将低位放在前面。 2.14 设多项式P(x)采用课本中所述链接方法存储。写一算法，对给定的x 值，求P(x)的值。 [提示]：float PolyValue(Polylist p; float x) {……} 第三章 1. 按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： ⑴ 如进站的车厢序列为 123，则可能得到的出站车厢序列是什么？ 123、213、132、231、321 （312） ⑵如进站的车厢序列为 123456，能否得到435612 和 135426 的出站序列，并说明原因。（即 写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。 SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X6 2. 设队列中有A、B、C、D、E 这 5 个元素，其中队首元素为A 。如果对这个队列重复执行下列4 步操作： （1） 输出队首元素； （2 ） 把队首元素值插入到队尾； （3） 删除队首元素； （4 ） 再次删除队首元素。 直到队列成为空队列为止，则是否可能得到输出序列： （1） A、C、E、C、C （2） A、C、E （3） A、C、E、C、C、C （4 ） A、C、E、C [提示]： A、B、C、D、E （输出队首元素A ） A、B、C、D、E、A （把队首元素A 插入到队尾） B、C、D、E、A （删除队首元素A ） C、D、E、A （再次删除队首元素B） C、D、E、A （输出队首元素C） C、D、E、A、C （把队首元素C 插入到队尾） D、E、A、C （删除队首元素C） E、A、C （再次删除队首元素D ） 3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？ 4. 按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程： A －B ＊Ｃ／Ｄ＋Ｅ↑Ｆ 5. 试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1&序列2’模式的字符序列。其中序列1 和序列2 中都不含字符’&’，且序列2 是序列 1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+ ３& ３－１’则不是。 [提示]： （1） 边读边入栈，直到& （2 ） 边读边出栈边比较，直到…… 6. 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）。 [提示]： 例： 中缀表达式：a+b 后缀表达式: ab+ 中缀表达式：a+b×c 后缀表达式: abc×+ 中缀表达式：a+b×c-d 后缀表达式: abc×+d- 中缀表达式：a+b×c-d/e 后缀表达式: abc×+de/- 中缀表达式：a+b×(c-d)-e/f 后缀表达式: abcd-×+ef/- • 后缀表达式的计算过程：（简便） 顺序扫描表达式， （1） 如果是操作数，直接入栈； （2 ） 如果是操作符op，则连续退栈两次，得操作数X, Y，计算X op Y，并将结果入栈。 • 如何将中缀表达式转换为后缀表达式？ 顺序扫描中缀表达式， （1）如果是操作数，直接输出； （2 ）如果是操作符op ，则与栈顶操作符op 比较： 如果op > op ，则op 入栈； 如果op = op ，则脱括号； 如果op < op ，则输出op ； 7. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设 头指针），试编写相应的队列初始化、入队列和出队列的算法。 [提示]： 参P.56 P.70 先画图. typedef LinkList CLQueue; int InitQueue(CLQueue * Q) int EnterQueue(CLQueue Q, QueueElementType x) int DeleteQueue(CLQueue Q, QueueElementType *x) 8. 要求循环队列不损失一个空间全部都能得到利用,设置一个标志域tag ,以tag 为0 或 1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。 [提示]： 初始状态：front==0, rear==0, tag==0 队空条件：front==rear, tag==0 队满条件：front==rear, tag==1 其它状态：front !=rear, tag==0 （或1、2 ） 入队操作： … …（入队） if (front==rear) tag=1；（或直接tag=1 ） 出队操作： … …（出队） tag=0； [问题]：如何明确区分队空、队满、非空非满三种情况？ 9. 简述以下算法的功能（其中栈和队列的元素类型均为int）： （1）void proc_1(Stack S) { int i, n, A[255]; n=0; while(!EmptyStack(S)) {n++; Pop(&S, &A[n]);} for(i=1; i<=n; i++) Push(&S, A[i]); } 将栈 S 逆序。 （2 ）void proc_2(Stack S, int e) { Stack T; int d; InitStack(&T); while(!EmptyStack(S)) { Pop(&S, &d); if (d!=e) Push( &T, d); } while(!EmptyStack(T)) { Pop(&T, &d); Push( &S, d); } } 删除栈 S 中所有等于e 的元素。 （3）void proc_3(Queue *Q) { Stack S; int d; InitStack(&S); while(!EmptyQueue(*Q)) { DeleteQueue(Q, &d); Push( &S, d); } while(!EmptyStack(S)) { Pop(&S, &d); EnterQueue(Q，d) } } 将队列 Q 逆序。 第四章 1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’。给出下列操作的结果： StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s,’A’,4); StrReplace(s,’STUDENT’,q); StrCat(StrCat(sub1,t), StrCat(sub2,q)); [参考
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
] StrLength(s)=14; sub1= ’I AM A_’; sub2= ’_’; StrIndex(s,’A’,4)=6; StrReplace(s,’STUDENT’,q)= ’I AM A WORKER’; StrCat(StrCat(sub1,t), StrCat(sub2,q))= ’I AM A GOOD WORKER’; 2. 编写算法，实现串的基本操作 StrReplace(S,T,V)。 3. 假设以块链结构表示串，块的大小为 1，且附设头结点。 试编写算法，实现串的下列基本操作： StrAsign(S,chars) ； StrCopy(S,T) ； StrCompare(S,T) ； StrLength(S) ； StrCat(S,T) ； SubString(Sub,S,pos,len)。 [说明]：用单链表实现。 4．叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。 5．已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将 S 转换为T. 6．S 和T 是用结点大小为 1 的单链表存储的两个串，
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
一个算法将串S 中首次与T匹配的子串逆置。 7．S 是用结点大小为4 的单链表存储的串,分别编写算法在第k 个字符后插入串T，及从第k 个字符删除len 个字符。 以下算法用定长顺序串： 8．写下列算法： （1） 将顺序串r 中所有值为ch1 的字符换成ch2 的字符。 （2 ）将顺序串r 中所有字符按照相反的次序仍存放在r 中。 （3） 从顺序串r 中删除其值等于ch 的所有字符。 （4 ） 从顺序串r1 中第index个字符起求出首次与串r2 相同的子串的起始位置。 （5） 从顺序串r 中删除所有与串r1 相同的子串。 9．写一个函数将顺序串s1 中的第i 个字符到第j 个字符之间的字符用 s2 串替换。 [提示]：（1）用静态顺序串 （2 ）先移位，后复制 10． 写算法，实现顺序串的基本操作 StrCompare(s,t)。 11． 写算法，实现顺序串的基本操作 StrReplace(&s,t,v)。 [提示]： （1） 被替换子串定位（相当于第9 题中i） （2 ） 被替换子串后面的字符左移或右移（为替换子串准备房间） （3） 替换子串入住（复制） （4 ） 重复上述，直到…… 第五章 1．假设有 6 行 8 列的二维数组A，每个元素占用6 个字节，存储器按字节编址。已知A 的基地址为 1000，计算： （1） 数组A 共占用多少字节； （288 ） （2 ） 数组A 的最后一个元素的地址； （1282） （3） 按行存储时，元素A36 的地址； （1126） （4 ） 按列存储时，元素A36 的地址； （1192） [注意]：本章自定义数组的下标从1 开始。 2． 设有三对角矩阵（a）,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得 ij n×n B[k]= aij ，求： （1） 用i,j 表示k 的下标变换公式； （2 ） 用k 表示i,j 的下标变换公式。 i = k/3 + 1, j = k%3 + i - 1 = k%3 + k/3 或： i = k/3 + 1, j = k - 2 ×( k/3 ) 2．假设稀疏矩阵 A 和 B 均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元 组表C 存放结果矩阵。 [提示]：参考P.28 例、P.47 例。 4．在稀疏矩阵的快速转置算法5.2 中，将计算position[col]的方法稍加改动，使算法 只占用一个辅助向量空间。 5．写一个在十字链表中删除非零元素aij 的算法。 [提示]：“删除”两次，释放一次。 6．画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f))) 7．求下列广义表运算的结果： （1） HEAD[((a,b),(c,d))]; （2 ） TAIL[((a,b),(c,d))]; （3） TAIL[HEAD[((a,b),(c,d))]]; （4 ） HEAD[TAIL[HEAD[((a,b),(c,d))]]]; b （5） TAIL[HEAD[TAIL[((a,b),(c,d))]]]; (d) 第六章 1．试分别画出具有3 个结点的树和 3 个结点的二叉树的所有不同形态。 2．对题1 所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 3．已知一棵度为k的树中有n 个度为 1 的结点，n 个度为2 的结点，……，n 个度为k的结点，则该树中有多少个叶子结点？ [提示]：参考 P.116 性质3 ∵ n=n + n + …… + n B=n + 2n + 3n + …… + kn n= B + 1 ∴ n + n + …… + n = n + 2n + 3n + …… + kn + 1 ∴ n = n + 2n + …… + (k-1)n + 1 4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二 叉树。 [提示]：参考 P.148 6． 已知二叉树有50 个叶子结点，则该二叉树的
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
点数至少应有多少个？ [提示]：一个叶子结点，总结点数至多有多少个？可压缩一度结点。 7． 给出满足下列条件的所有二叉树： a) 前序和中序相同 b) 中序和后序相同 c) 前序和后序相同 [提示]：去异存同。 a) D L R 与L D R 的相同点：D R，如果无 L，则完全相同, 如果无 LR，…。 b) L D R 与L R D 的相同点：L D，如果无 R，则完全相同。 c) D L R 与L R D 的相同点：D，如果无 L R，则完全相同。 （如果去D，则为空树） 7． n 个结点的K 叉树，若用具有k 个child 域的等长链结点存储树的一个结点，则空的Child域有多少个？ [提示]：参考 P.119 8．画出与下列已知序列对应的树Ｔ： 树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。 [提示]： （1）先画出对应的二叉树 （2 ）树的后根序列与对应二叉树的中序序列相同 9．假设用于通讯的电文仅由8 个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 （1）请为这8 个字母设计哈夫曼编码， （2 ）求平均编码长度。 10．已知二叉树采用二叉链表存放,要求返回二叉树T 的后序序列中的第一个结点的指针,是否可不用递归且不用栈来完成?请简述原因. [提示]：无右子的“左下端” 11. 画出和下列树对应的二叉树： 12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 13．编写递归算法：对于二叉树中每一个元素值为x 的结点，删去以它为根的子树，并释放相应的空间。 [提示]： [方法 1]：（1）按先序查找；（2 ）超前查看子结点（3）按后序释放； void DelSubTree(BiTree *bt, DataType x) { if ( *bt != NULL && (*bt) ->data==x ) { FreeTree(*bt); *bt =NULL; } else DelTree( *bt, x) void DelTree(BiTree bt, DataType x) { if ( bt ) { if (bt->LChild && bt->LChild->data==x) { FreeTree(bt->LChild); bt->LChild=NULL; } if (bt->RChild && bt->RChild->data==x) { FreeTree(bt->RChild); bt->RChild=NULL; } DelTree(bt->LChild, x); DelTree(bt->RChild, x); } } [方法2]：（1）先序查找；（2 ）直接查看当前根结点（3）用指针参数； [方法3]：（1）先序查找；（2 ）直接查看当前根结点 （3）通过函数值，返回删除后结果； （参示例程序） 14．分别写函数完成：在先序线索二叉树T 中，查找给定结点*p 在先序序列中的后继。在后序线索二叉树T 中，查找给定结点*p 在后序序列中的前驱。 [提示]： （1）先查看线索，无线索时用下面规律： （2 ）结点*p 在先序序列中的后继为其左子或右子； （3）结点*p 在后序序列中的前驱也是其左子或右子。 15．分别写出算法，实现在中序线索二叉树中查找给定结点*p 在中序序列中的前驱与后继。 （参例题） 16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。 [提示]： （1）可将孩子-兄弟链表划分为根、首子树、兄弟树，递归处理。 （2 ）可利用返回值，或全局变量。 17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。 18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。（参课本） 19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树 是指：在二叉树中不存在子树个数为 1 的结点。 [提示]：可利用任何递归、非递归遍历算法。 20．计算二叉树最大宽度的算法。二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。 [提示]： [方法一]： （1）利用队列，初值为根 （2 ）出队访问，并将左、右子入队，直到队空 （3）记录每一层中最后一个结点在队中的位置 （4 ）第i 层最后一个结点的右子，必是第i+1 层的最后一个结点 （5）第1 层最后一个结点在队中的位置为0 [方法二]：利用层号和全局数组，任意遍历、统计 21．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。 22. 证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树； 给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树； 23. 二叉树按照二叉链表方式存储，编写算法将二叉树左右子树进行交换。 第七章 7.1 已知如图所示的有向图，请给出该图的： （1） 每个顶点的入度、出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表； （5） 十字链表； （6） 强连通分量。 7.2 已知如图所示的无向图，请给出该图的： （1） 邻接多重表；（要求每个边结点中第一个顶点号小于第二个顶点号，且每个顶点的各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序。） （2） 从顶点1 开始，深度优先遍历该图所得顶点序列和边的序列；（给出深度优先搜索树） （3） 从顶点1 开始，广度优先遍历该图所得顶点序列和边的序列。（给出广度优先搜索树） 7.3已知如图7.31 所示的AOE-网，试求： （1） 每个事件的最早发生时间和最晚发生时间； （2） 每个活动的最早开始时间和最晚开始时间； （3） 给出关键路径。 7.4 已知如图7.30 所示的有向网，试利用 Dijkstra 算法求顶点 1 到其余顶点的最短路径，并给出算法执行过程中各步的状态。 7.5编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。 [参例题] 7.6试在邻接矩阵存储结构上实现图的基本操作：InsertVertex(G,v); InsertArc(G, v, w); DeleteVertex(G,v)和 DeleteArc(G, v, w)。 7.7 试对邻接表存储结构重做题 6。 7.8 试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否存在由顶点v 到顶点v 的路径（i≠j ）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。 7.9 同上题要求。试基于图的广度优先搜索策略写一算法。 7.10 试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的、非递归形式的算法。算法中不规定具体的存储结构，而将图 Graph 看成是一种抽象数据类型。 7.11 采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为 k 的简单路径（指顶点序列中不含有重现的顶点）的算法。 [提示]：利用深度搜索，增设一个深度参数，深度超过k 则停止对该结点的搜索。 7.12 下图是带权的有向图 G 的邻接表表示法。从结点V1 出发，深度遍历图G 所得结点序列为（A），广度遍历图G 所得结点序列为（B）；G 的一个拓扑序列是（C）；从结点 V1 到结点 V8 的最短路径为（D）；从结点V1 到结点 V8 的关键路径为（ E ）。 其中A、B、C 的选择有： ① V1,V2,V3,V4,V5,V6,V7,V8 ② V1,V2,V4,V6,V5,V3,V7,V8 ③ V1,V2,V4,V6,V3,V5,V7,V8 ④ V1,V2,V4,V6,V7,V3,V5,V8 ⑤ V1,V2,V3,V8,V4,V5,V6,V7 ⑥ V1,V2,V3,V8,V4,V5,V7,V6 ⑦ V1,V2,V3,V8,V5,V7,V4,V6 D、E 的选择有： ① V1,V2,V4,V5,V3,V8 ② V1,V6,V5,V3,V8 ③ V1,V6,V7,V8 ④ V1,V2,V5,V7,V8 第八章 8.1 若对大小均为 n 的有序的顺序表和无序的顺序表分别进行查找，试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？ （1） 查找不成功，即表中没有关键字等于给定值K 的记录。 （2） 查找成功，且表中只有一个关键字等于给定值K 的记录。 （3） 查找成功，且表中有若干个关键字等于给定值 K 的记录，一次查找要求找出所有记录。 [提示]：均用顺序查找法。 8.2 画出对长度为 10 的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 [提示]：根据P.191 ASL 定义计算平均查找长度。 8.3 试推导含 12 个结点的平衡二叉树的最大深度并画出一棵这样的树。 [提示]：沿最左分支生长，前提是：其任一祖先的右分支与左分支等深，如不等深，则先生 长右分支，而生长右分支的前提是：其任一祖先的左分支与右分支等深，如不等深，则先生 长左分支，如此交互考虑，逐步生长，直到 12 个结点。 8.4 试从空树开始，画出按以下次序向 2-3 树，即 3 阶B-树中插入关键码的建树过程：20， 30，50，52，60，68，70。如果此后删除50 和68，画出每一步执行后2-3 树的状态。 8.5 选取哈希函数 H(k)=(3k)%11，用线性探测再散列法处理冲突。试在0～10 的散列地址 空间中，对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功与不成功时的平均查找长度。 [提示]：平均查找长度参考P.225。 0 1 2 3 4 5 6 7 8 9 10 22 41 30 01 53 46 13 67 1 1 2 2 1 1 2 6 ASLsucc = (1×4 + 2×3 + 6) / 8 = 2 ASLunsucc = ( 2 + 1 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 1 ) / 11 = 40 / 11 8.6 试为下列关键字建立一个装载因子不小于 0.75 的哈希表，并计算你所构造的哈希表的 平均查找长度。 （ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG，CHANG，CHAO，YANG， JIN） [提示]：（1）由装填因子求出表长，（2）可利用字母序号设计哈希函数， （3）确定解决冲突的方法。 8.7 试编写利用折半查找确定记录所在块的分块查找算法。 8.8 试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结 构，且树中结点的关键字均不同。 [提示]：检验中序遍历序列是否递增有序？ [方法 1]：用非递归中序遍历算法，设双指针pre, p 一旦 pre->data > p->data 则返回假 [方法2]：用递归中序遍历算法，设全局指针pre，（参中序线索化算法） 一旦 pre->data > p->data 则返回假 [方法3]：用递归（中序或后序）算法 （1）空树是（2）单根树是（3）左递归真（4）右递归真 （5）左子树的右端小于根（6）右子树的左端大于根 8.9 编写算法，求出指定结点在给定的二叉排序树中所在的层数。 8.10 编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结 点A、B 中，A 是 B 的祖先，则认为A 是A、B 的最近公共祖先）。 [提示]： （1） 假设A<=B， （2） 从根开始，左走或右走，直到A 在左（或根），B 在右（或根）。 8.11 编写一个函数，利用二分查找算法在一个有序表中插入一个元素 x，并保持表的有序 性。 [提示]：（1）表中已经有x，（2）表中没有x 参 P. 231 8.12 已知长度为12 的表： （Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。 （1） 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树并求其等概率的情况下查找成功的平均查找长度。 （2） 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。 （3） 按表中元素的顺序依次构造一棵平衡二叉排序树，并求其等概率的情况下查找成功的平均查找长度。 [提示]：画出判定树或排序树，根据P.191ASL 定义计算平均查找长度。 8.13 含有 9 个叶子结点的 3 阶 B-树中至少有多少个非叶子结点？含有 10 个叶子结点的 3阶B-树中至少有多少个非叶子结点？ [提示]：叶子结点对应空指针。 8.14 写一时间复杂度为O(log2n + m)的算法，删除二叉排序树中所有关键字不小于x的结点，并释放结点空间。其中n为树中的结点个数，m为被删除的结点个数。 [提示]： （1） p=root （2） 如果p->key 大于、等于x，则删除p->rchild 和 p， （3） 左走一步，转（2） （4） 如果p->key 小于x，则反复右走， （5） 转（2） （6） 直到p==NULL 8.15 在平衡二叉排序树的每个结点中增加一个lsize 域，其值为它的左子树中的结点数加1。编写一时间复杂度为 O(log n)的算法，确定树中第k 个结点的位置。 [提示]：先画图手工求。 （1）sum=0, （2）从当前根开始沿左链找sum + lsize<=k 的最大结点a， （3）沿a 的右链求sum=sum + lsize，直到结点b，sum + lsize(b)>=k 重复（2）、（3），直到sum=k 第九章 9.1 以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手 工执行以下排序算法，写出（前三趟）每一趟排序结束时的关键码状态： （1）直接插入排序； （2）希尔排序（增量d[1]=5）； （3）快速排序； （4）堆排序； （5）归并排序； （6）基数排序。 9.2 一组关键字码，40，27，28，12，15，50，7，采用快速排序或堆排序，写出每趟 排序结果。9.3 不难看出，对长度为 n 的记录序列进行快速排序时，所需进行的比较次数依赖于这 n个元素的初始排列。n=7 时在最好情况下需进行多少次比较？请说明理由。 对 n=7 给出一个最好情况的初始排列实例。（保证每个基准记录都是中间记录） 9.4 假设序列由 n 个关键字不同的记录构成，要求不经排序而从中选出关键字从大到小顺序的前k(k<
a[i+1],则将两者交换；第一趟对所有奇数 i, 第二趟对所有偶数 i，…,依次类推直至整个序列有序为止。 （1） 这种排序方法的结束条件是什么？ （2） 分析当初始序列为正序或逆序两种情况下，奇偶交换排序过程中所需进行的关键字比较的次数。 （3） 写出奇偶交换排序的算法。 9.12 设计一个用链表表示的直接选择排序算法。（与9.8 重） 9.13 插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后 的插入排序算法。（与9.5 重复） 9.14 一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表的前一半为负整数，后一半为正整数。不要求对元素排序，但要尽量减少交换次数。（与9.7 类似） 9.15 为什么通常使用一维数组作为堆的存放形式？ 9.16 已知（k ,k ,…，k ）是堆，写一个算法将（k ,k ,…，k ，k）调整为堆。按此思想写一个从空堆开始一个一个添入元素的建堆算法。 9.17 试比较直接插入排序、简单选择排序、快速排序、堆排序、归并排序、希尔排序和基 数排序的时空性能、稳定性和适用情况。 9.18 在供选择的答案中填入正确答案： 1 ）、排序（分类）的方法有许多种：__A_③_法从未排序序列中依次取出元素，与排序序列（初始为空）中的元素作比较，将其放入已排序列的正确位置上；__B①__法从未排序序列中挑选元素，并将其依次放入已排序序（初始时为空）的一端；交换排序法是对序列中元素进行一系列的比较，当被比较的两元素逆序时进行交换。__C_④__和__D②__是基于这类方法的两种排序方法，而__D__是比__C__效率更高的方法，利用某种算法，根据元素的关键值计算出排序位置的方法是__E_⑦_ 。 供选择答案 ① 选择排序 ② 快速排序 ③ 插入排序 ④ 冒泡排序 ⑤ 归并排序 ⑥ 二分排序 ⑦ 哈希排序 ⑧ 基数排序 2）、一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个 记录为基准得到的一次划分结果为 C 。 A、38，40，46，56，79，84 B、40，38，46，79，56，84 C、40，38，46，56，79，84 D、40，38，46，84，56，79 3）、下列排序算法中，C算法可能会出现下面情况：初始数据有序时，花费时间反而最多。 A、堆排序 B、冒泡排序 C、快速排序 D、SHELL 排序 9.19 判断正误： （ ）在一个大堆中，最小元素不一定在最后。 （ X ）对n个记录采用快速排序方法进行排序，最坏情况下所需时间是o （nlog2n）。 （ X ）在执行某排序算法过程中，出现了排序码朝着与最终排序序列相反方向移动的现象，则称该算法是不稳定的。 第 1 章 绪论 1．4 试编写算法，求一元多项式P (x)=a +a x+a x +a x +…a x 的值P (x )，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入a (i=0,1,…,n),x和n，输出为P (x )。通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。 （2 ）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 void polyvalue() { int n,p,i,x,xp,sum; float a[]; float *p=a; printf("Input number of terms:"); scanf("%d",&n); printf("Input the %d coefficients from a0 to a%d:\n",n,n); for(i=0;i<=n;i++) scanf("%f",p++); printf("Input value of x:"); scanf("%f",&x); p=a;xp=1;sum=0; //xp 用于存放x 的i 次方 for(i=0;i<=n;i++) { sum+=xp*(*p++); xp*=x; } printf("Value is:%f",sum); }//polyvalue 第二章 线性表 2．4 设线性表存于 a(1:arrsize)的前elenum 个分量中且递增有序。试写一算法，将 X 插入 到线性表的适当位置上，以保持线性表的有序性。 Status Insert_SqList(SqList &va,int x)//把x 插入递增有序表va 中 { if(va.length+1>va.listsize) return ERROR; va.length++; for(i=va.length-1;va.elem[i]>x&&i>=0;i--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; return OK; }//Insert_SqList 2．6 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink 且小于maxk 的所有元素 { p=L; while(p->next->data<=mink) p=p->next; //p 是最后一个不大于mink 的元素 if(p->next) //如果还有比mink 更大的元素 { q=p->next; while(q->datanext; //q 是第一个不小于maxk 的元素 p->next=q; } }//Delete_Between 2．7 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a, a ..., a ）逆置为（a, a ,..., a ）。 （1） 以一维数组作存储结构，设线性表存于 a(1:arrsize)的前 elenum 个分量中。 （2）以单链表作存储结构。 void reverse(SqList &A)//顺序表的就地逆置 { for(i=1,j=A.length;iA.elem[j]; }//reverse 2．8 假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C。 while(pa||pb) { if(pa->datadata||!pb) { pc=pa;q=pa->next;pa->next=pre;pa=q; //将A 的元素插入新表 } else { pc=pb;q=pb->next;pb->next=pre;pb=q; //将B 的元素插入新表 } pre=pc; } C=A;A->next=pc; //构造新表头 }//reverse_merge 分析:本算法的思想是,按从小到大的顺序依次把A 和B 的元素插入新表的头部pc 处,最后处理A 或B 的剩余元素. 2．9 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。 Status Delete_Pre(CiLNode *s)//删除单循环链表中结点 s 的直接前驱 { p=s; while(p->next->next!=s) p=p->next; //找到s 的前驱的前驱p p->next=s; return OK; }//Delete_Pre 2．10 已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList 为带头结点的单循环链表类型. { s=L->next; A=(CiList*)malloc(sizeof(CiLNode));p=A; B=(CiList*)malloc(sizeof(CiLNode));q=B; C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点 while(s) { if(isalphabet(s->data)) { p->next=s;p=s; } else if(isdigit(s->data)) { q->next=s;q=s; } else { r->next=s;r=s; } }//while p->next=A;q->next=B;r->next=C; //完成循环链表 }//LinkList_Divide 2．11 设线性表A=(a , a ,…,a )，B= (b, b ,…,b )，试写一个按下列规则合并A、B为线性表C的算法，使得： C= (a , b ,…,a , b , b …,b ) 当m≤n时； 或者 C= (a , b ,…,a , b , a …,a ) 当m>n时。 线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n 均未显式存储。void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A 和B 合并为C,A 和B 的元素间隔排列,且使用原存储空间 { p=A->next;q=B->next;C=A; while(p&&q) { s=p->next;p->next=q; //将B 的元素插入 if(s) { t=q->next;q->next=s; //如A 非空,将A 的元素插入 } p=s;q=t; }//while }//merge1 2．12 将一个用循环链
浙公网安备 33021202002483