1、数据结构-3 及答案解析(总分：87.98，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( )（分数：2.00）A.数据元素具有同一特点B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C.每个数据元素都一样D.数据元素所包含的数据项的个数要相等2.在下面的排序方法中，属于不稳定的排序方法的是( )（分数：2.00）A.直接插入排序B.冒泡法排序C.堆排序D.归并排序3.带头结点的单链表 head为空的判断条件是( )（分数：2.00）A.head=NULLB.headnext=
2、NULLC.headnext=headD.head!=NULL4.设散列函数为 H(k)=k mod7，一组关键码为 23,14,9,6,30,12和 18，散列表 T的地址空间为 0.6，用线性探测法解决冲突，依次将这组关键码插入 T中，得到的散列表为( ) （分数：2.00）A.B.C.D.5.在一非空二叉树的中序遍历序列中，根结点的右边( )（分数：2.00）A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的所有结点D.只有左子树上的部分结点6.设图 G采用邻接表存储，则拓扑排序算法的时间复杂度为( )（分数：2.00）A.O(B.O(n+C.O(n2)D.O(n7.
3、在一个链队列中，若 f，r 分别为队首、队尾指针，则插入 s所指结点的操作为( )（分数：2.00）A.fnext=c;f=s;B.rnext=s;r=s;C.snext=r;r= sD.snext=f,f=s;8.邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的( )（分数：2.00）A.先序遍历B.中序遍历C.后序遍历D.按层遍历9.非空的单循环链表 L的尾结点 P，满足( )（分数：2.00）A.P.next=NULL;B.P=NULL;C.P.next=L;D.P=L10.一个栈的人栈序列是 a,b,c,d,e，则栈的不可能的输出序列是( )（分数：2.00）A.e d c b
4、aB.d e c b aC.d c e a bD.a b c d e11.从具有 n个结点的单链表中查找值等于 x的结点时，在查找成功的情况下，平均需比较( )个结点。（分数：2.00）A.nB.n/2C.(n-1)/2D.(n+1)/212.排序的重要目的是为了以后对已排序的数据元素进行( )（分数：2.00）A.打印输出B.分类C.查找D.合并13.对文件进行直接存取的是根据( )（分数：2.00）A.逻辑记录号去存取某个记录B.逻辑记录的关键字去存取某个记录C.逻辑记录的结构去存取某个记录D.逻辑记录的具体内容去存取某个记录14.线索二叉树是一种( )结构。（分数：2.00）A.物理B.
5、逻辑C.存储D.线性15.在下面的排序方法中，不需要通过比较关键字就能进行排序的是( )（分数：2.00）A.箱排序B.快速排序C.插入排序D.希尔排序二、B填空题/B(总题数：10，分数：20.00)16.对无向图，其邻接矩阵是一个关于 1 对称的矩阵。（分数：2.00）填空项 1:_17.多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是 1。（分数：2.00）填空项 1:_18.已知 L是无表头结点的单链表，且 P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 (1)在 P结点之前插入 S结点的语句序列是_； (2)在表首插入 S结点的语句序列是_
6、。 a Pnex=S b Pnext=Pnextnext c Pnext=Snext d Snext=Pnext e Snext=L f Q=P g while(Pnext!=QP=Pnext h while(Pnext!=NULL)P=Pnext i P=L j L=S（分数：2.00）填空项 1:_19.在散列技术中，处理冲突的方法有：_和_。（分数：2.00）填空项 1:_20.如果我们定义一个长度为 N的串空间，则它最多能放 1 个字符。（分数：2.00）填空项 1:_21.假设在图 G中任意的顶点设为 vi，此顶点对应的度为 D(vi)，此图的顶点数为 n。则边数 e和度数之间的关系
7、为 1。（分数：2.00）填空项 1:_22. 1的邻接矩阵不一定是不对称的。（分数：2.00）填空项 1:_23.在串的匹配运算中，一般我们将主串称为_，而将子串称为_。（分数：2.00）填空项 1:_24.当所有结点的权值都相等时，用这些结点构造的二叉排序树上只有 1。（分数：2.00）填空项 1:_25.N个顶点的连通图，至少有 1 条边。（分数：2.00）填空项 1:_三、B解答题/B(总题数：1，分数：8.00)设有多项式 A(x)=7+3x+9x8+5x17 B(x)=8x+22x7一 9x8（分数：7.98）(1).用单链表给出 A(x)的存储表示。（分数：1.33）_(2).用
8、单链表给出 B(x)的存储表示。（分数：1.33）_(3).以上述两个单链表为基础，通过插入和删除等运算得出 A(x)+B(x)的存储表示，使其存储空间覆盖 A(x)和 B(x)的存储空间。（分数：1.33）_四、B算法阅读题/B(总题数：4，分数：20.00)26.以下运算实现在循环队上判队空，请在_处用适当的语句予以填充。 int EmptyCycQueue(CycqcleueTp sq) if(_)retum(1); else return(0); （分数：5.00）填空项 1:_27.以下算法在有序表 R中用二分查找法查找键值等于 K的元素，请分析程序，并在_上填充合适的语句。 int
9、 binsearch(sqtable R,keytype K) low=l;hig=R.n;/*置查找区间初值。low，hig 分别标记查找区间的下、上界*/ while(low=hig) mid=(low+hig)/2; switch case K=R.itemi.key:return(mid); /*找到，返回位置 mid*/ case KR.itemi.key:_.break;/*缩小区间*/ case KR.itemi.key:_;break/*缩小区间*/ return(0); /*若区间长度已为 0但仍不成功，则返回 0，表示查找不成功*/ （分数：5.00）填空项 1:_28.以
10、下运算实现在链栈上的退栈，请在_处用适当的语句予以填充。 int Pop(LStackTp*is,DataType*x) LStackTp*P; if(1s!=NULL) p=ls; *x=_; ls=lsnext; _; return(1); else return(0); （分数：5.00）填空项 1:_29.分析下面程序段的时间复杂度_。 j=1; while(j=n) j=j*2; （分数：5.00）填空项 1:_五、B算法设计题/B(总题数：1，分数：10.00)30.对一个有 t个非零值元素的 mn矩阵，用 B0t,13的数组来表示，其中第 0行的三个元素分别是 m,n,t，从第一
11、行开始到最后一行，每行表示一个非零元素，第一列为矩阵元素行号，第二列为其列号，第三列为其元素量，对这样的表示法，试编写一个算法确定任意一个元素 Aij的位置，并考虑若修改其元素值须用多少时间?(设 B中第 1列原行号是递增的)（分数：10.00）_数据结构-3 答案解析(总分：87.98，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( )（分数：2.00）A.数据元素具有同一特点B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C.每个数据元素都一样D.数据元素所包含的数据项的
12、个数要相等解析：2.在下面的排序方法中，属于不稳定的排序方法的是( )（分数：2.00）A.直接插入排序B.冒泡法排序C.堆排序 D.归并排序解析：3.带头结点的单链表 head为空的判断条件是( )（分数：2.00）A.head=NULLB.headnext=NULL C.headnext=headD.head!=NULL解析：4.设散列函数为 H(k)=k mod7，一组关键码为 23,14,9,6,30,12和 18，散列表 T的地址空间为 0.6，用线性探测法解决冲突，依次将这组关键码插入 T中，得到的散列表为( ) （分数：2.00）A.B. C.D.解析：5.在一非空二叉树的中序遍
13、历序列中，根结点的右边( )（分数：2.00）A.只有右子树上的所有结点 B.只有右子树上的部分结点C.只有左子树上的所有结点D.只有左子树上的部分结点解析：6.设图 G采用邻接表存储，则拓扑排序算法的时间复杂度为( )（分数：2.00）A.O(B.O(n+ C.O(n2)D.O(n解析：7.在一个链队列中，若 f，r 分别为队首、队尾指针，则插入 s所指结点的操作为( )（分数：2.00）A.fnext=c;f=s;B.rnext=s;r=s; C.snext=r;r= sD.snext=f,f=s;解析：8.邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的( )（分数：2.00）A.
14、先序遍历 B.中序遍历C.后序遍历D.按层遍历解析：9.非空的单循环链表 L的尾结点 P，满足( )（分数：2.00）A.P.next=NULL;B.P=NULL;C.P.next=L; D.P=L解析：10.一个栈的人栈序列是 a,b,c,d,e，则栈的不可能的输出序列是( )（分数：2.00）A.e d c b aB.d e c b aC.d c e a b D.a b c d e解析：11.从具有 n个结点的单链表中查找值等于 x的结点时，在查找成功的情况下，平均需比较( )个结点。（分数：2.00）A.nB.n/2C.(n-1)/2D.(n+1)/2 解析：12.排序的重要目的是为了以
15、后对已排序的数据元素进行( )（分数：2.00）A.打印输出B.分类C.查找 D.合并解析：13.对文件进行直接存取的是根据( )（分数：2.00）A.逻辑记录号去存取某个记录 B.逻辑记录的关键字去存取某个记录C.逻辑记录的结构去存取某个记录D.逻辑记录的具体内容去存取某个记录解析：14.线索二叉树是一种( )结构。（分数：2.00）A.物理 B.逻辑C.存储D.线性解析：15.在下面的排序方法中，不需要通过比较关键字就能进行排序的是( )（分数：2.00）A.箱排序 B.快速排序C.插入排序D.希尔排序解析：二、B填空题/B(总题数：10，分数：20.00)16.对无向图，其邻接矩阵是一个
16、关于 1 对称的矩阵。（分数：2.00）填空项 1:_ （正确答案：主对角线）解析：17.多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是 1。（分数：2.00）填空项 1:_ （正确答案：一个数据元素可能有多个直接前趋和多个直接后继）解析：18.已知 L是无表头结点的单链表，且 P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 (1)在 P结点之前插入 S结点的语句序列是_； (2)在表首插入 S结点的语句序列是_。 a Pnex=S b Pnext=Pnextnext c Pnext=Snext d Snext=Pnext e Snext=L f
17、Q=P g while(Pnext!=QP=Pnext h while(Pnext!=NULL)P=Pnext i P=L j L=S（分数：2.00）填空项 1:_ （正确答案：figda ej）解析：19.在散列技术中，处理冲突的方法有：_和_。（分数：2.00）填空项 1:_ （正确答案：开放定址法 拉链法）解析：20.如果我们定义一个长度为 N的串空间，则它最多能放 1 个字符。（分数：2.00）填空项 1:_ （正确答案：N1）解析：21.假设在图 G中任意的顶点设为 vi，此顶点对应的度为 D(vi)，此图的顶点数为 n。则边数 e和度数之间的关系为 1。（分数：2.00）填空项
18、1:_ （正确答案：*）解析：22. 1的邻接矩阵不一定是不对称的。（分数：2.00）填空项 1:_ （正确答案：有向图）解析：23.在串的匹配运算中，一般我们将主串称为_，而将子串称为_。（分数：2.00）填空项 1:_ （正确答案：目标串 模式串）解析：24.当所有结点的权值都相等时，用这些结点构造的二叉排序树上只有 1。（分数：2.00）填空项 1:_ （正确答案：右子树）解析：25.N个顶点的连通图，至少有 1 条边。（分数：2.00）填空项 1:_ （正确答案：N1）解析：三、B解答题/B(总题数：1，分数：8.00)设有多项式 A(x)=7+3x+9x8+5x17 B(x)=8x+
19、22x7一 9x8（分数：7.98）(1).用单链表给出 A(x)的存储表示。（分数：1.33）_正确答案：()解析：每一结点由三个域组成 单链表按 x的升幂链接，并且不记录系数为 0的项。于是 A(x)可表示为 (2).用单链表给出 B(x)的存储表示。（分数：1.33）_正确答案：()解析：类似地，B(x)可表示为 (3).以上述两个单链表为基础，通过插入和删除等运算得出 A(x)+B(x)的存储表示，使其存储空间覆盖 A(x)和 B(x)的存储空间。（分数：1.33）_正确答案：()解析：在实现 A(x)+B(x)时，可以 A(x)的单链表为基础，逐项考虑 B(x)。若 B(x)中某项的
20、指数与 A(x)某项指数一致，则将两个相应的系数相加，若结果为 0，则从 A(x)单链表中删去此项的结点；若结果不为0，则修改 A(x)单链表中该项的系数域，使之表示同类项合并的结果。若 B(x)中某项的系数在 A(x)单链表中未出现，则将该项结点插入 A(x)的单链表中。这样就得到下列重复使用 A(x)和 B(x)存储空间的 A(x)+B(x)的存储袁示。 _解析：_解析：_解析：四、B算法阅读题/B(总题数：4，分数：20.00)26.以下运算实现在循环队上判队空，请在_处用适当的语句予以填充。 int EmptyCycQueue(CycqcleueTp sq) if(_)retum(1)
21、; else return(0); （分数：5.00）填空项 1:_ （正确答案：sq.rear=sq.front）解析：27.以下算法在有序表 R中用二分查找法查找键值等于 K的元素，请分析程序，并在_上填充合适的语句。 int binsearch(sqtable R,keytype K) low=l;hig=R.n;/*置查找区间初值。low，hig 分别标记查找区间的下、上界*/ while(low=hig) mid=(low+hig)/2; switch case K=R.itemi.key:return(mid); /*找到，返回位置 mid*/ case KR.itemi.key:
22、_.break;/*缩小区间*/ case KR.itemi.key:_;break/*缩小区间*/ return(0); /*若区间长度已为 0但仍不成功，则返回 0，表示查找不成功*/ （分数：5.00）填空项 1:_ （正确答案：hig=mid-1 lowlow+1）解析：28.以下运算实现在链栈上的退栈，请在_处用适当的语句予以填充。 int Pop(LStackTp*is,DataType*x) LStackTp*P; if(1s!=NULL) p=ls; *x=_; ls=lsnext; _; return(1); else return(0); （分数：5.00）填空项 1:_
23、（正确答案：pdata free(p)）解析：29.分析下面程序段的时间复杂度_。 j=1; while(j=n) j=j*2; （分数：5.00）填空项 1:_ （正确答案：O(log 2n)）解析：五、B算法设计题/B(总题数：1，分数：10.00)30.对一个有 t个非零值元素的 mn矩阵，用 B0t,13的数组来表示，其中第 0行的三个元素分别是 m,n,t，从第一行开始到最后一行，每行表示一个非零元素，第一列为矩阵元素行号，第二列为其列号，第三列为其元素量，对这样的表示法，试编写一个算法确定任意一个元素 Aij的位置，并考虑若修改其元素值须用多少时间?(设 B中第 1列原行号是递增的
24、)（分数：10.00）_正确答案：()解析：分析题意可得其算法思想为： 首先可在数组 B中找到相应的行，然后找到相应的列，即可修改其元素值，可假定要修改的 Aij，原先就具有非零值。从而可将算法描述为： lorte(B,t,i,j,v) /*确定任意一个元素 Aij的位置*/ datatype B;/*B 的杆标为 0t和 13*/ int t,i,j; float v; datatype A; /*A的下标为 1m和 1n，A 表示 mn矩阵*/ int p; p=1; while(Bp1!=1)if(pt)printf Chasnt element found/n“); else while(Bp1=i)*(p=t)if(Bp1=i) else printf (“no element found/n“); /*lorte*| 显然，在本算法中可能出现的最坏情况：一是需要修改的元素位于 B中最后一行；二是 Bij先的元素值为零，而无法在 B中查找到相应的位置。所以，在这两种情况下的时间复杂度为 0(t)。
