济南铁道职业技术学院 专升本辅导教材 数据结构
for(i=0；i p=(HLink)malloc(sizeof(HNode))； hdnode[i]=p； p->row=0； p->col=0； p->value.ptr=P； p->rlght=p； p->down=p； } ／*建立k个头结点；初始时第i个头结点的地址存放于hdnode[i-1]中x／ Current_row=1； last=hdnode[0]; for(i=1；i<=t；i++){ scanf(\％d％d％d\，&rrow,&ccol，&val)； ／x读人一个某非零元素的三元组x／ if(rrow>current_row){ last—>right=hdnode[Current_row—1]； current_row=rrow； last=hdnode[rrow—1]； } p=(CrossLink)malloc(sizeof(CNode))； ／x申请一个新的链结点空间x／ p—>row=rrow； p->col=ccol； p—>value.val=val； last->right=p； ／x生成一个新的链结点x／ last=p； hdnode[ccol—1)->value．ptr->down=p； ／‘将新结点链接到相应行链表中，／ kfnode[ccol—1)->value．ptr=p； ／x将新结点链接到相应列链表中，／ ； if(t!=0) last->right：hdnode[current—row—1]； ／x封闭最后——行x／ for(i=0;i HEAD=(HLink)malloc(sizeof(HNode))； ／，申请一个总的头结点x／ HEAD->m=m； HEAD->n=n； HEAD->t=t； for(i=0；i hdnode[i]->value.ptr=nanode[i+1]； if(k==0) HEAD->value.ptr=HEAD； else{ hdnode[k-1]->value.ptr=HEAD； HEAD->value.ptr=hdnode[0]； return HEAD； } 第 26 页 共 63 页 济南铁道职业技术学院 专升本辅导教材 数据结构 第四章 广义表 字符串 数组 4．1单项选择题。 (1)空的广义表是指广义表——。 A．深度为0 B。尚未赋值 C．不含任何原子元素 D．不含任何元素 (2)广义表中元素分为——。 A．原子元素 B．表元素 C．原子元素和表元素 D．任意元素 (3)广义表的长度是指——。 A．广义表中元素的个数 B．广义表中原子元素的个数 C．广义表中表元素的个数 Di广义表中括号嵌套的层数 (4)广义表的深度是指——。 久广义表中元素的个数 B．广义表中原子元素的个数 C．广义表中表元素的个数 D．广义表中括号嵌套的层数 (5)在一个长度为n，包含m个原子元素的广义表中，——。 A．m和n相等 B．m不大于n C．m不小于n D．m与n无关 (6)广义表A=(( )，(a)，(b，(c，d)))的长度为——。 A．2 B．3 C．4 D．5 (7)广义表A：(( )，(a)，(b，(c，d)))的深度为——。 A．2 B．3 C．4 D．5 4．2有人说，m*n阶矩阵是一种广义表结构，你认为如何?请说明你的理由。 4．3请分别写出下列各广义表的长度与深度： (1)A=((a)) (2)B=(a，(b，c，d)，e，()) (3)C=(x，((y)，B，A)) (4)D=(A,D) 4．6 试写出判断两个广义表是否相等的递归算法。 4．7 根据本章介绍的m元多项式的表示方法，试写出一个m元多项式相加的算法。 4．1 请回答空串与空格串有何区别。 4．2 两个字符串相等的充分必要条件是什么? 4．3 已知字符串S采用链式存储结构，链结点大小为1。试写出求该串长度的算法。 4．4 已知字符串S1与S2都采用链式存储结构，链结点大小为1。试写出判断S1与S2是否相等的算法。若S1与S2相等，算法返回1否则返回0。 4．5 设串S，S1，S2分别采用顺序存储结构，长度分别为len，lenl，len2。试写一算法，用串S2替换串S中的子串S1。 4．6 设串采用链式存储结构，链结点大小为1。试写出删除S中从第i个字符开始连续k个字符的算法。 4．7 在字节编址的机器中，字符串S1与S2分别存放在字符数组S饥M1]与S2[M2]中(LEN(S1)≤M1，LEN(S2)≤M2)，并以，@，为串的结束标志。试写一算法，求在S1中第一次出现而在S2中不出现的字符的位置。 4．8 已知字符串的存储结构同 4．7题，并且有LEN(S1)=M，LEN(S2)=N,试写一算法，从S1中位置k开始插入字符串S2，并且取代S1中从第k个字符开始的连续t个字符。设k+1 第 27 页 共 63 页 济南铁道职业技术学院 专升本辅导教材 数据结构 4．9 已知字符串存放于字符数组S[M]中，并以’@’为串的结束标志。试写一算法，判断该字符串是否是回文(即正读与反读相同)。若字符串是回文，算法返回1，否则返回0。 4．10 根据你所确定的一种存储结构设计一个算法，该算法的功能是求串S中出现的第一个最长重复子串的位置与长度。 4．11 已知字符串采用链式存储结构，链结点大小为1。对于给定的字符串S1与S2，请写一算法，求在S1中第一次出现，而在S2中不出现的所有字符。 第四章 各种考试试题 数组部分 选择题 (1)数组是一种线性表结构。 ( ) (2)数组最基本的操作是插入和删除。 ( ) (3)对数组的操作是基于数组下标进行的。 ( ) (4)具有特殊用途的矩阵称为特殊矩阵。 ( ) (5)只需存储n阶对称矩阵的下三角部分的元素。 ( ) (6)在n阶三对角矩阵中，矩阵的每一列都有3个非零元素。 ( ) (7)稀疏矩阵的特点就是矩阵中的元素较少。 ( ) (8)采用三元组表方法存储稀疏矩阵的优点之一是可以随机地访问矩阵中的每一个非零元 素。 ( ) (9)用一维数组存储特殊矩阵的目的是为了节省存储空间。 ( ) (10)从理论上说，任何一个矩阵都可以采用三元组表方法进行存储。 ( ) 填空题。 (1)一般情况下，数组最基本的操作是——。 (2)一个m行n列的矩阵可以看成是长度为——的线性表，表中的每一个元素是长度为 m的线性表。 (3)一个m行n列的矩阵可以看成是长度为——的线性表，表中的每一个元素是长度为n的线性表。 (4)已知二维数组A(4)[6]采用行序为主序方式存储，每个元素占用4个存储单元，该数组一 共占用了——个存储单元。 (5)已知二维数组A[4爪6]采用行序为主序方式存储，每个元素占用3个存储单元，并且 A10爪0]的存储地址为1200，元素A12)14]的存储地址是——。 (6)已知二维数组A14爪6]采用列序为主序方式存储，每个元素占用4个存储单元， 并且A[3][4]的存储地址为1234，元素A[0][0]的存储地址是——。 (7)对特殊矩阵采用压缩存储方法的目的是——。 (8)一个20阶五对角矩阵一共有——个元素，其中有——个非零元素。 (9)将n阶三对角矩阵A中所有非零元素按照行序为主序方式依次存放于数组B中，非零元素A[i][j]在B中的位置是——。 3．3单项选择题。 (1)所谓稀疏矩阵是指——的矩阵。 A．零元素较多且分布无规律 ·B非零元素较少 C．元素较少 D．不适合采用二维数组表示 (2)下面的说法中，不正确的是——。 A．只需存放对称矩阵中包括主对角线元素在内的下(或上)三角部分的元素即可 B‘只需存放对角矩阵中的非零元素即可 第 28 页 共 63 页 济南铁道职业技术学院 专升本辅导教材 数据结构 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 页