1、数据结构-5 及答案解析(总分：99.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.Aarr和 Barr两个数组的说明如下： VAR Aarr:ArrayO7of char; Barr:Array-52,3,8of char; 这两个数组分别能存放的字符的最大个数是( )（分数：2.00）A.7和 35B.1和 5C.8和 48D.1和 62.下面程序的时间复杂性是( ) for (i=1;i=n;i+) for(j=1;j=m;j+) Aij=i*j; （分数：2.00）A.O(m2)B.O(n2)C.O(m*D.O(m+3.对于一棵具有三个结点的二叉
2、树，共有( )种不同的树的形态。（分数：2.00）A.4B.5C.6D.74.堆(Heap)是( )（分数：2.00）A.完全二叉树B.线性表C.二叉排序树D.平衡二叉树5.下列说法中正确的是( )（分数：2.00）A.任何一棵二叉树中至少有一个结点的度为 2B.任何一棵二叉树中的每个结点的度为 2C.任何一棵二叉树中的度肯定等于 2D.任何一棵二叉树中的度可以小于 26.一个具有 N个顶点的有向图最多有( )条边。（分数：2.00）A.N(N-1)/2B.N(N-1)C.N(N+1)D.N(N+1)/27.二分查找算法要求被查找的表是( )（分数：2.00）A.键值有序的链表B.键值不一定有
3、序的链表C.键值有序的顺序表D.键值不一定有序的顺序表8.将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用( )方法能够最快地找出其中最大的正整数。（分数：2.00）A.快速排序B.插入排序C.选择排序D.归并排序9.与数据元素本身的形式、内容、相对位置、个数无关的是数据的( )（分数：2.00）A.存储结构B.存储实现C.逻辑结构D.运算实现10.长度为 12的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下，查找失败时的 ASL值是( )（分数：2.00）A.37/12B.62/13C.39/12D.49/1311.下面的程序在执行时，S 语句
4、共被执行了( )次。 i=1; while(i=n) for(j=i;jn;j+) S ; i=i+1; （分数：2.00）A.B.C.D.12.设一个数组中，行下标 i的范围是从 1到 8，列下标的范围是从 1到 10，假设此数组的初始存储地址是 A，则如果将此数组按照列优先的顺序连续存放，则元素 Q58的起始地址是( )（分数：2.00）A.1B.23C.24D.52913.设有两个串 p和 q，求 q在 p中首次出现的位置的运算称为( )（分数：2.00）A.连接B.模式匹配C.求子串D.求串长14.对于 shell排序来说，给定的一组排序数值为 49,38,65,97,13,27,49
5、,55,04 则第二趟排序后的结果为( )（分数：2.00）A.04,13,27,49,49,38,55,65,76,97B.04,13,27,38,49,49,55,65,76,97C.13,04,49,38,27,49,55,65,97,76D.13,27,49,55,04,49,38,65,97,7615.具有 24个记录的序列，采用冒泡排序最少的比较次数是( )（分数：2.00）A.1B.23C.24D.529二、B填空题/B(总题数：10，分数：20.00)16. 1的有向图，其全部顶点有可能排成一个拓扑序列。（分数：2.00）填空项 1:_17.朴素的串匹配算法的特点是简单，但是其
6、效率较低，其时间匹配算法的最坏时间是 1(假设模式串的长度是 m，目标串的长度是 n)。（分数：2.00）填空项 1:_18.任何连通图的连通分量只有一个，即 1。（分数：2.00）填空项 1:_19.设有一个已按各元素的值排好序的线性表，长度为 125，对给定的 k值，用二分法查找与 k相等的元素，若查找成功，则至少需要比较_次，至多需比较_次。（分数：2.00）填空项 1:_20.在非空队列中，头指针始终指向_，而尾指针始终指向_。（分数：2.00）填空项 1:_21.数组的长度是_，线性表的长度是_。（分数：2.00）填空项 1:_22.如果一个图中有 n条边，则此图的生成树含有_条边，
7、所以生成树是图的边数_的连通图。（分数：2.00）填空项 1:_23.设二维数组 A1020,510按行优先存储，每个元素占 4个存储单元，A10,5的存储地址是1000，则 A15,10的存储地址是 1。（分数：2.00）填空项 1:_24.顺序串是用一组地址连续的存储单元来存储串中的字符序列，所以可以用字符数组来实现，按照存储分配方式的不同可以将顺序串分为两类：即_和_。（分数：2.00）填空项 1:_25.在线性表的顺序存储中，元素之间的逻辑关系是通过_决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_决定的。（分数：2.00）填空项 1:_三、B解答题/B(总题数：4，分数：19
8、.00)26.试分别画出具有 3个结点的树和具有 3个结点的二叉树的所有不同的形态。（分数：5.00）_27.已知串 S=(xyz)*，t=(x+z)*y，试利用串的基本运算将 s串转化为 t串，t 串转化为 s串。（分数：5.00）_多项式 A(x)=anXn+an-1Xn-1+a1X+a0的线性表表示法有下列两种可能的形式： A=(n,an,an-1，a 1，a 0) A=(m，1 m-1，b m-1，1 m-2，b m-2，1 0，b 0) 其中：m 为非零项的个数，1 i，b i分别为非零项的指数和系数。试分析：（分数：4.00）(1).两种表示方法对存储空间的需要情况；（分数：2.0
9、0）_(2).进行多项式相加，采用哪一种表示方法处理较为简单?（分数：2.00）_28.假设有一个容量为 5的队列，假设其初始状态为 front=rear=0，则对此队列进行下列操作之后，请画出此时的头、尾指针的变化情况和相应的队列内元素的存储情况。 (1)队列为空(即没有任何元素进入)； (2)A，B，C 入队； (3)A 出队； (4)B，C 出队，此时队列为空。（分数：5.00）_四、B算法阅读题/B(总题数：4，分数：20.00)29.以下运算实现在循环队上的入队列，请在_处用适当的语句予以填充。 int EnCycQueue(CycquetaeTp*sq,DataType x) if
10、(sqrear+1)%maxsize=_) error(“队满“);return(0);) else_; _; return(1); （分数：5.00）填空项 1:_30.以下程序段采用先根遍历方法求二叉树的叶子数，请在_处填充适当的语句。 void countleaf(bitreptr t,int*count)/*根指针为 t，假定叶子数 count的初值为 0*/ if(t!=NULL) if(tlchild=NULL) countleaf(1lehild,count); _; （分数：5.00）填空项 1:_31.以下为冒泡排序的算法。请分析算法，并在_处用适当的语句予以填充。 void
11、 bubblesort(int n,list r) /*fiag为特征位，定义为布尔型*/ for(i=1;i=_，i+) _; for(j=1;j=_;j+) if(rj+1.keyrj.key)flag=0;p=rj;rj=rj+1;rj+1=P; if(flag)return; （分数：5.00）填空项 1:_32.基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵 A的三元组 a.data的次序进行转置(快速转置)，请在_处用适当的语句予以填充。 Fast_Trans_Sparmat(SpMatrixTp a,SpMatrixTp*b) (*b)mu=a.nu;(*b).nu=
12、a.mu;(*b).tu=a.tu; if(a.tu) for(col)=1;_col+)unmcol=0 for(t=1;t=a.tu;t+)numa.datat.j+; cpot1=1; for(col=2;col=a.nu;col+)cpotcol=_; for(p=1;p=a.tu;p+) col=a.datap.j; q=cpotcol; (*b).dataq.i=adatap.j; (*b).dataq.j=a.datap.i; (*b).dataq.v=a.datap.v; _; （分数：5.00）填空项 1:_五、B算法设计题/B(总题数：1，分数：10.00)33.假设在表示
13、一棵二叉树的二叉链表上增加两个域，双亲域用于指示其双亲结点，标志域 flag(可取，02)的值，用以区分在遍历过程中到达该结点时继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。（分数：10.00）_数据结构-5 答案解析(总分：99.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.Aarr和 Barr两个数组的说明如下： VAR Aarr:ArrayO7of char; Barr:Array-52,3,8of char; 这两个数组分别能存放的字符的最大个数是( )（分数：2.00）A.7和 35B.1和 5C.8和 48
14、 D.1和 6解析：2.下面程序的时间复杂性是( ) for (i=1;i=n;i+) for(j=1;j=m;j+) Aij=i*j; （分数：2.00）A.O(m2)B.O(n2)C.O(m* D.O(m+解析：3.对于一棵具有三个结点的二叉树，共有( )种不同的树的形态。（分数：2.00）A.4B.5 C.6D.7解析：4.堆(Heap)是( )（分数：2.00）A.完全二叉树B.线性表 C.二叉排序树D.平衡二叉树解析：5.下列说法中正确的是( )（分数：2.00）A.任何一棵二叉树中至少有一个结点的度为 2B.任何一棵二叉树中的每个结点的度为 2C.任何一棵二叉树中的度肯定等于 2D
15、.任何一棵二叉树中的度可以小于 2 解析：6.一个具有 N个顶点的有向图最多有( )条边。（分数：2.00）A.N(N-1)/2B.N(N-1) C.N(N+1)D.N(N+1)/2解析：7.二分查找算法要求被查找的表是( )（分数：2.00）A.键值有序的链表B.键值不一定有序的链表C.键值有序的顺序表 D.键值不一定有序的顺序表解析：8.将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用( )方法能够最快地找出其中最大的正整数。（分数：2.00）A.快速排序B.插入排序C.选择排序 D.归并排序解析：9.与数据元素本身的形式、内容、相对位置、个数无关的是数据的( )（分数
16、：2.00）A.存储结构B.存储实现C.逻辑结构 D.运算实现解析：10.长度为 12的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下，查找失败时的 ASL值是( )（分数：2.00）A.37/12B.62/13 C.39/12D.49/13解析：11.下面的程序在执行时，S 语句共被执行了( )次。 i=1; while(i=n) for(j=i;jn;j+) S ; i=i+1; （分数：2.00）A. B.C.D.解析：12.设一个数组中，行下标 i的范围是从 1到 8，列下标的范围是从 1到 10，假设此数组的初始存储地址是 A，则如果将此数组按照列优先的顺
17、序连续存放，则元素 Q58的起始地址是( )（分数：2.00）A.1B.23C.24 D.529解析：13.设有两个串 p和 q，求 q在 p中首次出现的位置的运算称为( )（分数：2.00）A.连接B.模式匹配 C.求子串D.求串长解析：14.对于 shell排序来说，给定的一组排序数值为 49,38,65,97,13,27,49,55,04 则第二趟排序后的结果为( )（分数：2.00）A.04,13,27,49,49,38,55,65,76,97B.04,13,27,38,49,49,55,65,76,97C.13,04,49,38,27,49,55,65,97,76 D.13,27,4
18、9,55,04,49,38,65,97,76解析：15.具有 24个记录的序列，采用冒泡排序最少的比较次数是( )（分数：2.00）A.1B.23 C.24D.529解析：二、B填空题/B(总题数：10，分数：20.00)16. 1的有向图，其全部顶点有可能排成一个拓扑序列。（分数：2.00）填空项 1:_ （正确答案：存在入度为 O的结点且没有回路）解析：17.朴素的串匹配算法的特点是简单，但是其效率较低，其时间匹配算法的最坏时间是 1(假设模式串的长度是 m，目标串的长度是 n)。（分数：2.00）填空项 1:_ （正确答案：0(m+n)）解析：18.任何连通图的连通分量只有一个，即 1。
19、（分数：2.00）填空项 1:_ （正确答案：其自身）解析：19.设有一个已按各元素的值排好序的线性表，长度为 125，对给定的 k值，用二分法查找与 k相等的元素，若查找成功，则至少需要比较_次，至多需比较_次。（分数：2.00）填空项 1:_ （正确答案：1 7）解析：20.在非空队列中，头指针始终指向_，而尾指针始终指向_。（分数：2.00）填空项 1:_ （正确答案：队头元素 队尾元素）解析：21.数组的长度是_，线性表的长度是_。（分数：2.00）填空项 1:_ （正确答案：固定的 可变的）解析：22.如果一个图中有 n条边，则此图的生成树含有_条边，所以生成树是图的边数_的连通图。
20、（分数：2.00）填空项 1:_ （正确答案：n-1 最少）解析：23.设二维数组 A1020,510按行优先存储，每个元素占 4个存储单元，A10,5的存储地址是1000，则 A15,10的存储地址是 1。（分数：2.00）填空项 1:_ （正确答案：1700）解析：24.顺序串是用一组地址连续的存储单元来存储串中的字符序列，所以可以用字符数组来实现，按照存储分配方式的不同可以将顺序串分为两类：即_和_。（分数：2.00）填空项 1:_ （正确答案：静态存储分配的顺序串 动态存储分配的顺序串）解析：25.在线性表的顺序存储中，元素之间的逻辑关系是通过_决定的；在线性表的链接存储中，元素之间的
21、逻辑关系是通过_决定的。（分数：2.00）填空项 1:_ （正确答案：相邻位置 链接指针）解析：三、B解答题/B(总题数：4，分数：19.00)26.试分别画出具有 3个结点的树和具有 3个结点的二叉树的所有不同的形态。（分数：5.00）_正确答案：()解析：含有三个结点的树只有两种形式见(1)和(2)；含有 3个结点的二叉树有 5种形态见(3)，(4)，(5)，(6)，(7) 27.已知串 S=(xyz)*，t=(x+z)*y，试利用串的基本运算将 s串转化为 t串，t 串转化为 s串。（分数：5.00）_正确答案：()解析：t=CONCAT(Rep(sup(s,1,5),y,+),Rep(
22、sub(s,6,1),*,*y) s=CONCAT(Rep(sub(t,1,5),+,y)，Rep(sub(t,6,2),*y,*)多项式 A(x)=anXn+an-1Xn-1+a1X+a0的线性表表示法有下列两种可能的形式： A=(n,an,an-1，a 1，a 0) A=(m，1 m-1，b m-1，1 m-2，b m-2，1 0，b 0) 其中：m 为非零项的个数，1 i，b i分别为非零项的指数和系数。试分析：（分数：4.00）(1).两种表示方法对存储空间的需要情况；（分数：2.00）_正确答案：()解析：第一种表示需要 n+2个实数存储单元，其中 n为多项式的最高幂数；第二种表示需
23、要 2m+1个实数存储单元，其中 m为非零系数的个数。显然，当非零系数较少时，第二种表示法需要较少的存储空间。(2).进行多项式相加，采用哪一种表示方法处理较为简单?（分数：2.00）_正确答案：()解析：采用每种表示法处理多项式相加比较简单，只需将次数较低的多项式的各项的系数加到次数较高的多项式的相应项的系数上去即可。而第二种方法要查找到相同的指数才能将系数相加，相加之和可能为0，这就要修改项数 m；另外当某个多项式中有的项而在另一个多项式中没有，显然其和也应作相应的修改。28.假设有一个容量为 5的队列，假设其初始状态为 front=rear=0，则对此队列进行下列操作之后，请画出此时的头
24、、尾指针的变化情况和相应的队列内元素的存储情况。 (1)队列为空(即没有任何元素进入)； (2)A，B，C 入队； (3)A 出队； (4)B，C 出队，此时队列为空。（分数：5.00）_正确答案：()解析： 根据队列的操作规则：进队时，将新元素插入到 rear所指的位置，然后将 rear加1，front 不变，出队时，删除 front所指的元素，然后将 front加 1，rear 不变，则有：A，B，C 进队列后，rear 指针指向 3，front 不变，A 出队列时，删除 A，将 front加 1，所以 front指向 1，rear 不变，B，C 都出队时，fron 加 2，rear 不变
25、，此时，rear 和 front相等。四、B算法阅读题/B(总题数：4，分数：20.00)29.以下运算实现在循环队上的入队列，请在_处用适当的语句予以填充。 int EnCycQueue(CycquetaeTp*sq,DataType x) if(sqrear+1)%maxsize=_) error(“队满“);return(0);) else_; _; return(1); （分数：5.00）填空项 1:_ （正确答案：sqfront sqrear=(sqrear+1)%maxsize sqdatasqrear=x）解析：30.以下程序段采用先根遍历方法求二叉树的叶子数，请在_处填充适当的
26、语句。 void countleaf(bitreptr t,int*count)/*根指针为 t，假定叶子数 count的初值为 0*/ if(t!=NULL) if(tlchild=NULL) countleaf(1lehild,count); _; （分数：5.00）填空项 1:_ （正确答案：*count+ eountleaf(1rehild,count)）解析：31.以下为冒泡排序的算法。请分析算法，并在_处用适当的语句予以填充。 void bubblesort(int n,list r) /*fiag为特征位，定义为布尔型*/ for(i=1;i=_，i+) _; for(j=1;j
27、=_;j+) if(rj+1.keyrj.key)flag=0;p=rj;rj=rj+1;rj+1=P; if(flag)return; （分数：5.00）填空项 1:_ （正确答案：n-1 flag-1 n-i）解析：32.基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵 A的三元组 a.data的次序进行转置(快速转置)，请在_处用适当的语句予以填充。 Fast_Trans_Sparmat(SpMatrixTp a,SpMatrixTp*b) (*b)mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu; if(a.tu) for(col)=1;_col+)unmc
28、ol=0 for(t=1;t=a.tu;t+)numa.datat.j+; cpot1=1; for(col=2;col=a.nu;col+)cpotcol=_; for(p=1;p=a.tu;p+) col=a.datap.j; q=cpotcol; (*b).dataq.i=adatap.j; (*b).dataq.j=a.datap.i; (*b).dataq.v=a.datap.v; _; （分数：5.00）填空项 1:_ （正确答案：col=a.nu cpotcol-1+numcol-1 cpotcol+）解析：五、B算法设计题/B(总题数：1，分数：10.00)33.假设在表示一棵
29、二叉树的二叉链表上增加两个域，双亲域用于指示其双亲结点，标志域 flag(可取，02)的值，用以区分在遍历过程中到达该结点时继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。（分数：10.00）_正确答案：()解析：要解答该题必须分析结点所在的状态，这可以通过结点的标志域来进行。对一个结点来说，当前的结点可能由：(1)其双亲结点转换；(2)其左子树遍历结束转换；(3)其右子树遍历结束转换。所以算法主要执行按这三种状态进行处理或处理当前结点切换结点的状态。从而可将算法描述为： void postorder(r)/*后序遍历此二叉树*/ bitree*t/*设为 bitree类型的结点含四个域：flag，parent，lchild，rehild，其中 flag的域初值为 0，指针 t指向根结点*/ bitree * P; P=t; while(p!=Null) switch(flag) case 0:pflag=1; if(plchild!=Null) p=plehild; break; case 1:pflag=2 if(jprchild!=Null) p=prchild; break; case 2:pflag=0; printf(pdata); p=jpparent; break; default; /*postorder*/
