Question

数据结构的问题1？

答题的朋友请注明是那到题

第一次作业
有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。
（1）A=（K，R），其中：
K={a，b，c，d，e，f，g}
R={r}
r={〈a，b〉，〈b，c〉，〈c，d〉，〈d，e〉，〈e，f〉，〈f，g〉}

（2）B=（K，R），其中：
K={a，b，c，d，e，f，g，h}
R={r}
r={〈d，b〉，〈d，g〉，〈d，a〉，〈b，c〉，〈g，e〉，〈g，h〉，〈a，f〉}

（3）C=（K，R），其中：
K={1，2，3，4，5，6}
R={r}
r={（1，2），（2，3），（2，4），（3，4），（3，5），（3，6），（4，5），（4，6）}
这里的圆括号对表示两结点是双向的。

分析以下程序段的时间复杂度。
a=0；b=1；①
for（i=2；i〈=n；i++）②
{
s=a+b；③
b=a；④
a=S；⑤
}

已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相同的元素。

对于一个栈，给出输入项A，B，C。如果输入项序列由A，B，C组成，试给出全部可能的输出序列

利用栈的基本操作，写一个返回栈中结点个数的算法int StackSize (SeqStackS)，并说明S为何不用作为指针参数？

如果用一个循环数组qu[0，m0-1]表示队列时，该队列只有一个头指针front，不设队尾指针rear，而改置计数器count用以记录队列中结点的个数。
（1）编写实现队列的五个基本运算；
（2）队列中能容纳元素的最多个数还是m0-1吗？

求两个正整数m和n的最大公约数可以用如下gcd（m，n）公式表示：

• (1)编写一个计算gcd（m，n）的递归过程；
• (2)将上述过程转换成非递归过程；
• (3)画出计算gcd（20，6）的过程及栈的状态变化，给出计算结果。

第二次
假设稀疏矩阵A采用三元组表示，编写一个函数计算其转置矩阵B，要求B也采用三元组表示

设二维数组A5*6的每个元素占4个字节，已知Loc（a00）=1000，A共占多少个字节？A的终端结点a45的起始地址为多少？按行和按列优先存储时，a25的起始地址分别为多少？

编写下列算法（假定下面所用的串均采用顺序存储方式，参数ch、ch1和ch2均为字符型）：
• 将串r中所有其值为ch1的字符换成ch2的字符。
• 将串r中所有字符按照相反的次序仍存放在r中。
• 从串r中删除其值等于ch的所有字符。
• 从串r1中第index个字符起求出首次与字符r2相同的子串的起始位置。
• 从串r中删除所有与串r3相同的子串（允许调用第（4）小题的函数和第（3）小题的删除子串的函数）。

Answer 1

1）A=（K，R），其中：
K={a，b，c，d，e，f，g}
R={r}
r={〈a，b〉，〈b，c〉，〈c，d〉，〈d，e〉，〈e，f〉，〈f，g〉}

（2）B=（K，R），其中：
K={a，b，c，d，e，f，g，h}
R={r}
r={〈d，b〉，〈d，g〉，〈d，a〉，〈b，c〉，〈g，e〉，〈g，h〉，〈a，f〉}

（3）C=（K，R），其中：
K={1，2，3，4，5，6}
R={r}
r={（1，2），（2，3），（2，4），（3，4），（3，5），（3，6），（4，5），（4，6）}
这里的圆括号对表示两结点是双向的。

分析以下程序段的时间复杂度。
a=0；b=1；①
for（i=2；i〈=n；i++）②
{
s=a+b；③
b=a；④
a=S；⑤
}

已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相同的元素。

对于一个栈，给出输入项A，B，C。如果输入项序列由A，B，C组成，试给出全部可能的输出序列

利用栈的基本操作，写一个返回栈中结点个数的算法int StackSize (SeqStackS)，并说明S为何不用作为指针参数？

如果用一个循环数组qu[0，m0-1]表示队列时，该队列只有一个头指针front，不设队尾指针rear，而改置计数器count用以记录队列中结点的个数。
（1）编写实现队列的五个基本运算；
（2）队列中能容纳元素的最多个数还是m0-1吗？

求两个正整数m和n的最大公约数可以用如下gcd（m，n）公式表示：

• (1)编写一个计算gcd（m，n）的递归过程；
• (2)将上述过程转换成非递归过程；
• (3)画出计算gcd（20，6）的过程及栈的状态变化，给出计算结果。

第二次
假设稀疏矩阵A采用三元组表示，编写一个函数计算其转置矩阵B，要求B也采用三元组表示

设二维数组A5*6的每个元素占4个字节，已知Loc（a00）=1000，A共占多少个字节？A的终端结点a45的起始地址为多少？按行和按列优先存储时，a25的起始地址分别为多少？

编写下列算法（假定下面所用的串均采用顺序存储方式，参数ch、ch1和ch2均为字符型）：
• 将串r中所有其值为ch1的字符换成ch2的字符。
• 将串r中所有字符按照相反的次序仍存放在r中。
• 从串r中删除其值等于ch的所有字符。
• 从串r1中第index个字符起求出首次与字符r2相同的子串的起始位置。
• 从串r中删除所有与串r3相同的子串（允许调用第（4）小题的函数和第（3）小题的删除子串的函数）。

Answer 2

第一次作业 1）线性结构a到g 2）树型结构根节点是d第二层是a b g 第三层是f c e h ,e h的根节点是g 3）是图型结构1 和2 相连，2在和1 3 4 相连，3和4 5 6 相连，4和2 3 5 6 相连，5 和3 4 相连，6和3 4 相连。
时间复杂度为n-2

其他的很麻烦的，我也是好久没有完这东西了有些生疏了，仔细看书认真学习是很简单的
加油

Answer 3

如果用一个循环数组qu[0，m0-1]表示队列时，该队列只有一个头指针front，不设队尾指针rear，而改置计数器count用以记录队列中结点的个数。
（1）编写实现队列的五个基本运算；
（2）队列中能容纳元素的最多个数还是m0-1吗？

求两个正整数m和n的最大公约数可以用如下gcd（m，n）公式表示：

• (1)编写一个计算gcd（m，n）的递归过程；
• (2)将上述过程转换成非递归过程；
• (3)画出计算gcd（20，6）的过程及栈的状态变化，给出计算结果。

Answer 4

afraefaetgaqtdrfaestf