发布时间 : 星期三 文章山东专升本计算机专业数据结构练习题 - 图文更新完毕开始阅读
济南铁道职业技术学院 专升本辅导教材 数据结构
C．稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储
D．稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储 (3)与三元组表方法相比，稀疏矩阵采用十字链表表示的优点在于——。 A．便于实现增加或减少矩阵中非零元素的操作 B．便于实现增加或减少矩阵元素的操作 C．节省存储空间
D.可以更快地查找到某个矩阵元素
(4)对稀疏矩阵采用压缩存储，其缺点之一是——。 A．无法判断矩阵的行数和列数
B．无法根据行列号计算矩阵元素的存储地址 C．无法根据行列号查找某个矩阵元素
D．使得矩阵元素之间的逻辑关系更加复杂
(5)将一个20阶的五对角矩阵中所有非零元素压缩存储到一个一维数组中，该一维数组至少应该有——个数组元素。
A．90 B．92 C．94 D．96
(6)将10阶三对角矩阵中的所有非零元素按照行序为主序方式依次存放于一维数组中，矩阵的第7行第8列的元素在该一维数组中————。
A．是第22个数组元素 B．是第21个数组元素 C．是第20个数组元素 D．不存在
(7)将10阶三对角矩阵中的所有非零元素按照行序为主序方式依次存放于一维数组中，一维数组中的第18个数组元素是矩阵——的那个元素。
A．第6行第3列 B．第6行第7列 C。第7行第7列、 D．第7行第6列
(8)若将n阶对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，则该对称矩阵在B中占用了一个数组元素。 A．n2 B．n*(n-1) C．n*(n+1)/2 D．n*(n-1)／2
(9)若将n阶三对角矩阵A按照行序为主序方式将所有非零元素依次存放在一个一维数组B中，则该三对角矩阵在B中占用了——个数组元素。 A．n2 B．3n-2 C．3n D．3n+2
(10)若将对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，那么，A中某元素Aij(i C．(j*(j—1))／2十i—1 D．(j*(j-1))/2—i—1 (11)对三对角矩阵A采用压缩存储的方法将所有非零元素存放于一个一维数组BC3n—2]中，某非零元素Aij在B中位置是——。 A．2*i+j-2 B．2*i+j+2 C．2*i+j-3 D．2*i+j-1 4.4已知一元多项式f(x)=4X(6)—5X(4)十7X(2)-1，请写出f(x)的一维数组表示的两种方法。 4.5按照压缩存储的思想，对于一个具有t个非零元素的mXn阶稀疏矩阵，若采用三元组表存储方法，t到达什么程度时这样做才有意义? 4.6 已知稀疏矩阵A[6][5]如下所示，请分别写出它的三元组表表示与十字链表表示。 第 29 页 共 63 页 济南铁道职业技术学院 专升本辅导教材 数据结构 4.8 已知稀疏矩阵A为m行n列，请写出将该稀疏矩阵转换为三元组表表示的算法。 4.9 设A为一个n阶上三角矩阵，若将此三角矩阵的所有非零元素按照列序为主序分配方式存放在数组B[n*(n+1)/2]中，a11存放于B[0]中，请写出此三角矩阵的非零元素Aij(i≤j)的寻址公式。 4.10 请写算法，该算法将一个n阶矩阵A主对角线以下的所有元素(不包括主对角线上的元素)按照列序为主序方式依次存放于一个一维数组B中。 4.11 请写算法，该算法将一个n阶矩阵A主对角线以下的所有元素(包括主对角线上的元素)按照行序为主序方式依次存放于一个一维数组B中。 4.12 已知n阶对称矩阵A的下三角部分元素按照行序为主序方式依次存放于一个一维数组B[m]中，请写出输出该对称矩阵的算法。 4.13 已知某二维数组A[n][n]按照行序为主序方式依次为每个数组元素获取值，请写一算法，求该数组两条对角线上的元素之乘积。 4.14 已知二维数组A[m][n]，请写一算法，求出该数组最外围一圈的元素之和。 已知二维数组A[n][n]，请写一时间复杂度为O(1)的算法，将该数组按照顺时针方向旋转若稀疏矩阵采用三元组表表示，请写出求两个具有相同行、列数的稀疏矩阵相加的算法。 4.17 若在m*n阶的矩阵A中有一元素Aij满足条件：Aij既是第i行元素的最小值，同时又是第j列元素的最大值，此时称Aij为A的鞍点。试写出求矩阵鞍点的算法。若矩阵中不存在鞍点，应给出相应信息。 4.18 编写一个将十字链表表示的矩阵A转置的算法，转置的结果仍采用十字链表表示。 4.19 若稀疏矩阵采用十字链表表示，请设计两个稀疏矩阵进行相乘运算的算法，即已知A矩阵与B矩阵，求矩阵C=A*B，并且要求C也采用十字链表表示。 4.20 试设计一个算法，将数组A[n]中的元素循环右移k位，要求只用一个元素大小的附加空间。 4.21 试设计一个时间复杂度为O(n)的算法，该算法将数组A[n]中的元素循环右移k位，要求采用尽可能少的附加空间。 4.22 n阶三对角矩阵A按行序为主序分配方式把所有非零元素存放于数组B[3n—2]中，Aij存放于B[0]中，请设计一个算法以确定数组B中元素～的值(1≤i，j≤n)。 4.23 已知存放整型数据的一维数组A[n]，请写一时间复杂度为O(n)的算法，该算法将数组调整为左右两部分，使得左边所有元素均为奇数，右边所有元素均为偶数。 4.24 已知具有n个数组元素的一维数组A，请写一算法，将该数组中所有值为0的元素都依次移到数组的前端A[i](0≤i≤n-1)。 综合部分 1．执行下列程序段后，串X的值为（ ） S=〞abcdefgh〞; T=〞xyzw〞; substr (X,S,2,strlen(T)); substr (Y,S, stelen(T),2); strcat (X,Y); 第 30 页 共 63 页 济南铁道职业技术学院 专升本辅导教材 数据结构 A．〞cdefgh〞 C．〞cdefxy〞 B．〞cdxyzw〞 D．〞cdefef〞 B．数组的元素必须从左到右顺序排列 D．数组是多维结构，内存是一维结构 2．多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（ ） A．数组的元素处在行和列两个关系中 C．数组的元素之间存在次序关系 A．tail (head (LS)) C．head (tail (LS)) A．创建和删除 3．从广义表LS＝（(p, q), r, s）中分解出原子q的运算是（ ） B．head (tail (head (LS))) D．tail (tail (head (LS))) B．索引和修改 4．数组通常具有两种基本运算，即（ ） C．读和写 D．排序和查找 5．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一堆数组B［1..15］中。已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（ ） A．116 B．118 C．120 D．122 6.为查找某一特定单词在文本中出现的位置，可应用的串运算是( ) A.插入 B.删除 C.串联接 D.子串定位 7.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到( ) A.P=″SCIENCE″ B.P=″STUDY″ C.S=″SCIENCE″ D.S=″STUDY″ 8.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］[4][5]的存储地址为( ) A.356 B.358 C.360 D.362 9.串S=″I am a worker″的长度是________。 第五章 树 二叉树 补充内容 后序遍历的非递归算法。 在对二叉树进行后序遍历的过程中，当指针p指向某一个结点时，不能马上对它进行 访问，而要先遍历它的左子树，因而要将此结点的地址进栈保存。当其左子树遍历完毕之 后，再次搜索到该结点时(该结点的地址通过退栈得到)，还不能对它进行访问，还需要遍 历它的右子树，所以，再一次将此结点的地址进栈保存。为了区别同一结点的两次进栈， 引入一个标志变量nae，有 0 表示该结点暂不访问 1 表示该结点可以访问 标志flag的值随同进栈结点的地址一起进栈和出栈。因此，算法中设置两个空间足够的堆栈，其中，STACKlCM]存放进栈结点的地址，STACK2[M]存放相应的标志n昭的值，两个堆栈使用同一栈顶指针top，top的初值为—1。 具体算法如下： #defineH 100 ／●定义二叉树中结点最大数目。／ voidPOSTOiRDER(BTREET) { ／*T为二叉树根结点所在链结点的地址。／ 第 31 页 共 63 页 济南铁道职业技术学院 专升本辅导教材 数据结构 BTREESTACKl[H]，p=T； intSTACK2[M]，flag,top=—1； if(T!=NULL) d0{ while(p!=NULL){ STACK／[++top]=p； ／●当前p所指结点的地址进栈●／ STACK2[top]= 0； ／，标志0进栈●／ p=p->lchild； ／●将p移到其左孩子结点x／ } p=STACKl[top)； flag=STACK2[top--]； if(flag==0){ STACKl[++top]=p； ／，当前p所指结点的地址进栈。／ STACK2[toP]=1； ／●标志1进栈●／ p=p->rchild； ／x将p移到其右孩子结点o／ } else{ VISIT(p)； ／x访问当前p所指的结点x／ p=NULL； } }while(p!=NULLtttop!=-1)； } 不难分析，上述算法的时间复杂度同样为O(n) 5．6．3 二叉树的线索化算法 对--X树的线索化，就是把二叉树的二叉链表存储结构中结点的所有空指针域改造成指向某结点在某种遍历序列中的直接前驱或直接后继的过程，因此，二叉树的线索化过程只能在对二叉树的遍历过程中进行。 · 下面给出二叉树的中序线索化的递归算法。算法中设有指针pre，用来指向中序遍历过程中当前访问的结点的直接前驱结点，pre的初值为头结点的指针；T初始时指向头结点，但在算法执行过程中，T总是指向当前访问的结点。 voldINTHREAD(TBTREET) { TBTREE pre； if(T!=Null){ INTHREAD(T—>lchild)； if(T—>rchild==NULL) T—>rbit=0； if(T—>lchild==NUll)； T—>lchild=pre； T—>lbit=0； } if(pre—>rbitc==0) pre—>rchild=T； pre=T； inthread(T->rchild)； } } 第 32 页 共 63 页