发布时间 : 星期一 文章山东专升本计算机专业数据结构练习题 - 图文更新完毕开始阅读f123d207de80d4d8d15a4f7d
济南铁道职业技术学院 专升本辅导教材 数据结构
下面给出创建一个具有m行n列、有t个非零元素的稀疏矩阵的十字链表的算法。 稀疏矩阵用三元组表的形式作为输入。首先输入稀疏矩阵的行数、列数以及非零元素总个数(m，n，t)，然后依次读入个三元组。算法中用到了一个辅助数组hdnode [MAX(m，n)]。其中，hdnode[i]用来分别存放第i列(也是第i行)链表的头结点的指针 (1≤i≤MAX(m，n))。 #defineMaxNl00 HLinkMREAD() {
HLinkHEAD，p，last，hdnode[MaxN]； iht m,n t，k，i，Current_row， int rrow,ccol，val；
scanf(\％d％d％\，&n，&n，&t)； ／x读入矩阵的行、列和非零元素的个数‘／ if(t<=0)
return NULL； k=(m>n)?m：n；
第 25 页 共 63 页
济南铁道职业技术学院 专升本辅导教材 数据结构
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 页