计算机应用专业数据结构课程作业

1、计算机应用专业“数据结构”课程作业第二次作业第二章稀疏矩阵和广义表一、单选题1. 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的OA 行号 B 列号 C 元素值 D 地址2. 设一个具有t个非零元素的 m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为 。5A0(m)B0( n)C3. 设一个广义表中结点的个数为A0(1)B0( n)C0(n+t)D 0(n*t)n，则求广义表深度算法的时间复杂度为20(n ) D 0(log 2n)二、填空题1. 在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的 、和三项。2. 在稀疏矩阵所对应的三元组

2、线性表中，每个三元组元素按为主序、为辅序的次序排列。3. 在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为 参数。4. 在稀疏矩阵的顺序存储中， 利用一个数组来存储非零元素， 该数组的长度应 对应三元组线性表的长度。5 在稀疏矩阵的带行指针向量的链接存储中，每个结点包含有 个域，在相应的十字链接存储中，每个结点包含有 个域。6 在稀疏矩阵的十字链接存储中，每个结点的down指针域指向 相同的下一个结点，right指针域指向 相同的下一个结点。7 一个广义表中的元素分为 元素和元素两类。8 .一个广义表的深度等于 嵌套的最大层数。9 在广义表的存储结构中，每个结点均包含有 个域。10 .在广义

3、表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为域和域。11 .若把整个广义表也看为一个表结点，则该结点的tag域的值为 , next域的值为。三、应用题1. 已知一个稀疏矩阵如图 3-11所示:0 0r-0 0 0 -3 0 00 0 0 00 -7 0 0 0 2 00 0 0 6-0 0 0 图3-11具有6行X 7列的一个稀疏矩阵(1) 写出它的三元组线性表；(2) 给出它的顺序存储表示；(3) 给出它的转置矩阵的三元组线性表和顺序存储表示;2. 画出下列每个广义表的带表头附加结点的链接存储结构图并分别计算出它们的长度和深度。(1) A=()(2) B=(a,b,c)

4、(3) C=(a,(b,(c) D=(a,b),(c,d)(5) E=(a,(b,(c,d),(e) F=(a,(b,(),c),(d),e)第四章栈和队列一、设用第二章定义的类型为 ALinkList的一维数组MSMaxSize建立三个链接堆栈, 其中前三个元素的next域用来存储三个栈顶指针，从下标为3的元素起作为空闲元素提供给三个栈共同使用，试编写一个算法把从键盘上输入的n个整数按照下列条件分别进入不同100，则进第二个栈;的栈：(1)若输入的整数若输入的整数若输入的整数x小于60，则进第一个栈； x大于等于60同时小于等于x大于100，则进第三个栈。4. 编写一个程序，首先调用上题算法，然后分别打印出每个栈中的内容。5. 已知一个中缀算术表达式为：3+4/(25-(6+15)*8(1) 写出对应的后缀算术表达式；(2) 画出在转换成后缀表达式的过程中运算符栈的变化。6. 已知一个后缀算术表达式为：24 8 + 3 * 4 10 7 - * / (1) 写出对应的中缀算术表达式；(2) 画出在进行后缀算术表达式求值的过程中数值栈的变化。8. 编写把十进制正整数转换为十六进制数输