数据结构作业.ppt

第一章作业
=(D,R)形式说明字符串: S=“s1, s2,……, sn”(si ∈char)
是一个数据结构,即S=(D,R)中 D=?R=?
:
其中E、C道为单行线。试构造使该路口行驶车辆不碰撞的交通管理模型。
(提示:找出路口各行车路线(AB,BC,….),若两行车路线不能对驶,则将其连线。)
,求下列算法段的时间复杂度,即T(n)=O(?)
(1) i=1; k=0; (2) i=1; j=0; (3) for(i=n-1; i>=1; i--)
while(i<n) while(i+j<=n) for(j=0; j<=i-1; j++)
{ k=k+10*i; i++;} {if(i>j) j++; {temp=A[j];A[j]=A[j+1];
else i++; } A[j+1]=temp;}
C
B
A E
D
第二章****题
=(a0a1, ……,am-1), Lb= (b0b1, ……,bn-1),利用线性表基本运算,求La – Lb =>La 、 La ∩ Lb =>Lc 运算的算法实现。
:
(按学号Sno有序)
(1)设计表S 的顺序存储结构;
(2)写出将一学生记录x 插入到表中正确位置的算法:insert-s(S,x);
(3)写出从表中删除Sno=y 的记录: delete-s(S,y)。
La
Lb
Lb
La
红:La – Lb 蓝:La ∩ Lb
No
Sno
Name[20]
sex
Class[20]
1
0001
丁一
男
计02
2
0002
王二
女
计02
……
……
……
……
……
32
0032
李四
男
计02
第二章****题
3. 设循环链表:
试写出从表R中某p节点开始, 查找data=d的节点指针的算法: search(R,p,d). (算法前应包括对节点的说明)
4. 设链表A、B 如下:
写出判断A 表和B 表是否相等的算法:equal(A,B).
(两表相等的充分必要条件:表长相等,且两表中元素也对应相等。)
A ..….
a0
am-1
^
B ..….
b0
bn-1
^
a0
ai
a1
an-1
R
p
第三章****题
第三章****题
,2,3,4,5 。进栈顺序约定:值小的元素先进栈,但在两次进栈之间,可作出栈运算。写出5个可以得到的出栈序列;5个不可以得到的出栈序列。
:
为对称形式(表长=n)。使用栈操作,写出判断表H是否对称的算法:xyx(H)。
x
H
y
z
y
^
x
x
H
y
y
^
x
第五章****题
第五章****题
1. FORTRAN语言中,数组元素按列优先存放。设每个元素占L个单元,首元素地址=b,试确定:
一维 A[n]=(A[1] A[2] …… A[n]);
二维 A[m,n] (m行、n列);
三维 A[m,n,p] 数组的元素地址计算公式。即:
Loc(A[i])=? Loc(A[i,j])=? Loc(A[i,j,k])=?
2. 设矩阵:



.若将A视为一个上三角矩阵时,请画出A的“按行优先存储”的压缩存储表S,并写出A中元素之下标[i,j]与S中元素之下标k之间的关系;
.若将A视为一个稀疏矩阵时,请画出A的三元组表和十字链表结构。
A5×5 =
1 0 0 0 2
0 3 0 0 4
0 0 0 5 0 (行列下标i、j满足:1≤i,j≤5)
0 0 0 6 0
0 0 0 0 7
第五章****题
:
.试用广义表形式表示H,并用Gethead(H)和Gettail(H)函数提取d2 ;
.画出H 的单链及双链结构。
存款A 取款B
活期定期D 总存款支取利息总支付进款X
a1 a3 b1 b2 b3
1年 2年 3年
d1 d2 d3
第六章****题(1)
。
=n,OD=2、3、……、m的节点数分别为n2、n3、……、nm,证:
n=n2+2n3+……+(m-1)nm+1
h(>1)层的完全二叉树中叶节点数=n,且第h层节点数≥ 2。证:
第六章****题(2)
:


.写出按DLR、LDR和LRD方法
对BT遍历的结果序列,并计算相应满二叉树的节点个数;
.画出BT的前、中、后序线索二叉树。
、中序遍历序列为:
DLR:(A