《数据结构算法数据》由会员分享，可在线阅读，更多相关《数据结构算法数据（19页珍藏版）》请在金锄头文库上搜索。
1、第一章 绪论1：设 n 为整数，试确定下列各段中前置以记号的语句频度(1) i=1;lk=0;while(i=n-1) k+=10*i;i+;(2) i=1;k=0;do k+=10*i;i+;while(i=n-1);(3) i=1;k=0;while(i=n-1)i+; k+=10*i;(4) k=0;for(i=1;i=n;i+) for(j=i;j=n;j+) k+;(5) for(i=1;in;i+)for(j=1;j=i;j+) for(k=1;k=j;k+) x+=delta;(6) i=1;j=0;while (i+jj) j+;else i+;(7) x=n;y=0; |n
2、是不小于 1 的常数while (x=(y+1)*(y+1) y+;(8) x=91;y=100;while (y0) if (x100) x-=10; y-;else x+;第二章 线性表例2.6已知L是无表头结点的单链表荷且P结点既不是首元结点荷也不是尾元结点荷试从 下列提供的答案中选择合适的语句序列。a. 在P结点后插入S结点的语句序列是。b. 在P结点前插入S结点的语句序列是。c. 在表首插入 S 结点的语句序列是。d. 在表尾插入S结点的语句序列是。(1) P-next=S;(2) P-next=P-next-next;(3) P-next=S-next;(4) S-next=P-n
3、ext;(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.7已知L是带表头结点的非空单链表荷且P结点既不是首元结点荷也不是尾元结点荷试从 下列提供的答案中选择合适的语句序列。a. 删除 P 结点的直接后继结点的语句序列是。b. 删除 P 结点的直接前驱结点的语句序列是。c. 删除 P 结点的语句序列是。d. 删除首元结点的语句序列是。e. 删除尾元结点的语句序列是。(1)
4、 P=P-next;(2) P-next=P;(3) P-next=P-next-next;(4) P=P-next-next;(5) while(P!=NULL) P=P-next;(6) while(Q-next!=NULL) P=Q; Q=Q-next; (7) while(P-next!=Q) P=P-next;(8) while(P-next-next!=Q) P=P-next;(9) while(P-next-next!=NULL) P=P-next;(10) Q=P;(11) Q=P-next;(12) P=L;(13) L=L-next;(14) free(Q);2.8已知P结
5、点是某双向链表的中间结点荷试从下列提供的答案中选择合适的语句序列。a. 在P结点后插入S结点的语句序列是。b. 在P结点前插入S结点的语句序列是。c. 删除P结点的直接后继结点的语句序列是。d. 删除 P 结点的直接前驱结点的语句序列是。e. 删除 P 结点的语句序列是。(1) P-next=P-next-next;(2) P-priou=P-priou-priou;(3) P-next=S;(4) P-priou=S;(5) S-next=P;(6) S-priou=P;(7) S-next=P-next;(8) S-priou=P-priou;(9) P-priou-next=P-next
6、;(10) P-priou-next=P;(11) P-next-priou=P;(12) P-next-priou=S;(13) P-priou-next=S;(14) P-next-priou=P-priou;(15) Q=P-next;(16) Q=P-priou;(17) free(P);(18) free(Q);第三章 栈和队列1.若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度錬注意磴两侧铁道 均为单向行驶道捋荷则请回答：(1) 如果进站的车厢序列为123荷则可能得到的出站车厢序列是什么拟(2) 如果进站的车厢序列为123456荷则能否得到435612和135426的出站
7、 序列并请说明为什么不能得到或者如何得到錬即写出以S，表示进栈和以X 表示出栈的栈操作序列将。2.写出下列程序段的输出结果栈的元素类型SEIemType为char。void main()Stack S;char x,y;InitStack(S);x= c; y= k;Push(S,x); Push(S, a); Push(S,y);Pop(S,x); Push(S, t); Push(S,x);Pop(S,x); Push(S, s);while(!StackEmpty(S) Pop(S,y); printf(y); printf(x);3. 简述以下算法的功能栈的元素类型 SElemType
8、 为 int。(1) status algo1(Stack S)int i,n,A255;n=0;while(!StackEmpty(S) n+; Pop(S,An); for(i=1;i=n;i+) Push(S,Ai);(2) status algo2(Stack S,int e)Stack T; int d;InitStack(T);while(!StackEmpty(S)Pop(S,d)；if(d!=e) Push(T,d);while(!StackEmpty(T)Pop(T,d);Push(S,d);4. 简述以下算法的功能錬栈和队列的元素类型均为int捋。void algo3(Qu
9、eue &Q)Stack S;int d;InitStack(S);while(!QueueEmpty(Q)DeQueue(Q, d);Push(S, d);while(!StackEmpty(S)Pop(S, d);EnQueue(Q, d);5. 若以1234作为双端队列的输入序列荷试分别求出满足以下条件的输出序列:(1) 能由输入受限的双端队列得到荷但不能由输出受限的双端队列得到的输 出序列。(2) 能由输出受限的双端队列得到荷但不能由输入受限的双端队列得到的输 出序列。(3) 既不能由输入受限的双端队列得到荷也不能由输出受限的双端队列得到 的输出序列。第四章 串1.设 s=I AM A
10、 STUDENT,t=GOOD,q=WORKER。求 ： StrLength(s),StreLength(t),SubString(s,8,7),SubString(t,2,1) Index(s,A) ，Index(s,t) ， Replace(s,STUDENT,q), Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)2 已知下列字符串：a=THIS,f=A SAMPLE, c=GOOD,d=NE,b= , s=Concaat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2) t=Repl
11、ace(f,SubString(c,3,1),d), g=IS v=Concat(s,Concat(b,Concat(t,Concat(b,u)试问：s,t,v,StrLength(s),Index(v,g),Index(u,g洛是什么？3.试问执行以下函数会产生怎样的输出结果？void demonstrate()StrAssign(s,THIS IS A BOOK);Replace(s,SubString(s,3,7),ESE ARE);StrAssign(t,Concat(s,S); StrAssign(u,XYXYXYXYXYXY);StrAssign(v,SubString(u,6,3
12、);StrAssign(w,W); Printf(t=,t,v=,v,u=,Replace(u,v,w);/demonstrate第五章 数组与广义表5.1.假设有二维数组A6*8,每个元素用相邻的6个字节存储，存储器按字节编址。 已知A的起始存储位置（基地址）为1000，计算：（ 1）数组 A 的体积（即存储量）（2）数组A的最后一个元素a57的第一个字节的地址；（3）按行存储时，元素ai4的第一个字节的地址；（4）按列存储时，元素a47的第一个字节的地址。5.9. 已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存 储结构（二维数组和三元组表）完成求 运算的优缺点。5.10. 求下列
13、广义表操作的结果：(1 )GetHead【(p,h,w) 】(2) GetTail【(b,k,p,h)】(3) GetHead (a,b)(c,d)】(4) GetTail【(a,b),(c,d)】(5) GetHead【GetTail【(a,b),(c,d)】(6) GetTail【GetHead(a,b),(c,d)】(7) GetHead【GetTail【GetHead【(a,b),(c,d)】(8) GetTail【GetHead【GetTail【(a,b),(c,d)】 5.12.按教科书 5.5 节中图 5.8 所示结点结构，画出下列广义表的存储 结构图，并求它的深度。(1) ()
14、，a,(b,c), () , d ) , (e)(2) (a),b),( ),d),(e,f)5.13.已知以下各图为广义表的存储结构图，其结点结构和5.12 题相 同，写出各图表示的广义表。(1)2)第六章 树和二叉树6.19 分别画出和下列树对应的各个二叉树：6.21 画出和下列二叉树相应的森林：6.27 假设一颗二叉树的先序序列为 EBADCFHGIKJ 和中序序列为ABCDEFGHIJK。请画出该树。6.28 假设一颗二叉树的先中序序列为 DCBGEAHFIJK 和后序序列为DCEGBFHKJIA。请画出该树。第七章 图7.1已知如右图所示的有向图，请给出该图的（1）每个顶点的入/出度（2）邻接矩阵（3）邻接表（4）逆邻接矩阵（5）强连通分量7.7 请对下页题 7.7图的无向带权图（1）写出它的邻接矩阵，并按普里姆算法求其最小生成树（2）写出它的邻接表
