1、数据结构真题 2008 年下半年及答案解析(总分：125.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是 ( )（分数：2.00）A.栈B.队列C.树D.图2.下面程序段的时间复杂度为 ( ) for(i=0;im;i+) for(j=0;jn;j+) Aij=i*j;（分数：2.00）A.O(m2)B.O(n2)C.O(m*D.O(m+3.在头指针为 head 的非空单循环链表中，指针 p 指向尾结点，下列关系成立的是 ( )（分数：2.00）A.pnext=headB.
2、pnextNext=headC.pnext=NULLD.p=head4.若以 S 和 X 分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作序列是( )（分数：2.00）A.SXSSXXXXB.SXXSXSSXC.SXSXXSSXD.SSSXXSXX5.两个字符串相等的条件是 ( )（分数：2.00）A.串的长度相等B.含有相同的字符集C.都是非空串D.串的长度相等且对应的字符相同6.如果将矩阵 Ann的每一列看成一个子表，整个矩阵看成是一个广义表 L，即 L=(a11，a 21，a n1)，(a12，a 22，a n2)，(a 1n，a 2n，a nn)，并且可以通过求表头 hea
3、d 和求表尾 tail 的运算求取矩阵中的每一个元素，则求得 a21的运算是 ( )（分数：2.00）A.head(tail(head()B.head(head(head()C.tail(head(tail()D.head(head(tail()7.已知一棵含 50 个结点的二叉树中只有一个叶子结点，则该树中度为 1 的结点个数为( )（分数：2.00）A.OB.1C.48D.498.在一个具有 n 个顶点的有向图中，所有顶点的出度之和为 Dout，则所有顶点的入度之和为( )（分数：2.00）A.DoutB.Dout-1C.Dout+1D.n9.如图所示的有向无环图可以得到的拓扑序列的个数是
4、 ( ) （分数：2.00）A.3B.4C.5D.610.如图所示的带权无向图的最小生成树的权为 ( ) （分数：2.00）A.51B.52C.54D.5611.对长度为 n 的关键字序列进行堆排序的空间复杂度为 ( )（分数：2.00）A.O(log2B.O(1)C.O(D.O(n*log212.已知用某种排序方法对关键字序列(51,35,93,24,13,68,56,42,77)进行排序时，前两趟排序的结果为 (35,51,24,13,68,56,42,77,93) (35,24,13,51,56,42,68,77,93) 所采用的排序方法是 ( )（分数：2.00）A.插入排序B.冒泡排
5、序C.快速排序D.归并排序13.已知散列表的存储空间为 T018，散列函数 H(key)=key%17，并用二次探测法处理冲突。散列表中已插入下列关键字：T5=39，T6=57 和 T7=7，则下一个关键字 23 插入的位置是 ( )（分数：2.00）A.T2B.T4C.T8D.T1014.适宜进行批量处理的文件类型是 ( )（分数：2.00）A.顺序文件B.索引顺序文件C.散列文件D.多关键字文件15.VSAM 文件的索引结构为 ( )（分数：2.00）A.B+树B.二叉排序树C.B-树D.最优二叉树二、B填空题/B(总题数：10，分数：20.00)16.如果某算法对于规模为 n 的问题的时
6、间耗费为 T(n)=3n3，在一台计算机上运行时间为 t 秒，则在另一台运行速度是其 64 倍的机器上，用同样的时间能解决的问题规模是原问题规模的 1 倍。（分数：2.00）填空项 1:_17.将两个长度分别为 m 和 n 的递增有序单链表，归并成一个按元素递减有序的单链表，可能达到的最好的时问复杂度是 1。（分数：2.00）填空项 1:_18.已知循环队列的存储空间大小为 m，队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是 1。（分数：2.00）填空项 1:_19.字符串“sgabacbadfgbacst“中存在有 1 个
7、与字符串“ba“相同的子串。（分数：2.00）填空项 1:_20.假设以列优先顺序存储二维数组 A58，其中元素 A00的存储地址为 LOC(a00)，且每个元素占 4个存储单元，则数组元素 Aij的存储地址为 1 。（分数：2.00）填空项 1:_21.假设用x,y表示树的边(其中 s 是 y 的双亲)，已知一棵树的边集为b,d，a,b，c,g，c,f，c,h，a,c)，该树的度是 1。（分数：2.00）填空项 1:_22.n 个顶点且含有环路的无向连通图中，至少含有 1 条边。（分数：2.00）填空项 1:_23.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少
8、的是 1。（分数：2.00）填空项 1:_24.和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对 1 结构也无特殊要求。（分数：2.00）填空项 1:_25.顺序文件中记录存放的物理顺序和 1 顺序一致。（分数：2.00）填空项 1:_三、B解答题/B(总题数：4，分数：25.00)26.由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。 （分数：5.00）_27.图的邻接表的类型定义如下所示： #define MaxVertexNum 50 typedef struct node int adjvex; struct node*next; Edg
9、eNode; typedef struct VertexType vertex; EdgeNode*firstedge; VertexNode; typedef VertexNode A djListMaxVertexNum; typedef struct AdjList adjiist; int n,e; ALGraph; 为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。 （分数：5.00）_28.某类物品的编号由一个大写英文字母及 2 位数字(09)组成，形如 E32。运用基数排序对下列物品编号序列进行按字典序
10、的排序，写出每一趟(分配和收集)后的结果。 E13,A37,F43,B32,B47,E12,F37,B12 第一趟： 第二趟： 第三耥：（分数：5.00）_(1)画出对表长为 13 的有序顺序表进行二分查找的判定树； (2)已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99)，写出在该序列中二分查找 37 时所需进行的比较次数。（分数：10.00）(1). （分数：5.00）_(2).（分数：5.00）_四、B算法阅读题/B(总题数：4，分数：40.00)已知线性表的存储结构为顺序表，阅读下列算法，并回答问题： (1)设线性表 L=(21,-7,-8
11、,19,0，-11,34,30，-10)，写出执行 f30( for(i=j=0;iLlength;i+) if(Ldatai=0) if(i!=j)Ldataj=Ldatai; j+; Llength=j; （分数：10.00）(1).（分数：5.00）(2).（分数：5.00）_阅读下列算法，并回答问题： (1)Q、Q1 和 Q2 都是队列结构，设队列 Q=(1,0,-5,2,-4,-6,9)，其中 1 为队头元素，写出执行f31( InitQueue(Q1); InitQueue(Q2); while(!QueueEmpty(Q) e=DeQueue(Q); if(e=0)EnQueue
12、(Q1,e); else EnQueue(Q2,e); （分数：10.00）(1).（分数：5.00）(2).（分数：5.00）_阅读下列算法，并回答问题： (1)假设串由合法的英文字母和空格组成，并以/0作结束符。设串，写出 f32(s)的返回值； (2)简述算法 f32 的功能。 int f32(char*s) int i,n,inword; n=inword=0; for(i=0;si!=/0;i+) if(si!= n+; else if(si= return n; （分数：10.00）(1).（分数：5.00）(2).（分数：5.00）_阅读下列对正整数关键字序列 L 操作的算法，并
13、回答问题： (1)设 L=(28,19,27,49,56,12,10,25,20,50)，写出 f33(L,4)的返回值； (2)简述函数 f33 的功能。 int Partition(SeqList*L,int low,int high); /对 Llowhigh做划分，返回基准记录的位置，并使左部的关键字 /都小于或等于基准记录的关键字，右部的关键字都大于基准记录的关键字 int f33(SeqList L,int k) int low,high,pivotpos; low=1; high=L.length; if(klow|khigh) return-1; do pivotpos=Par
14、tition( else if(pivotposk) high=pivotpos-1; while(pivotpos!=k); return L.datapivotpos; （分数：10.00）(1).（分数：5.00）(2).（分数：5.00）_五、B算法设计题/B(总题数：1，分数：10.00)29.二叉排序树的类型定义如下： typedef struet BSTNode/二叉排序树的结点结构 int data; /数据域 struct BSTNode*lchild,*rchild;/左、右孩子指针 BSTNode,*BSTree; 设计递归算法，统计一棵二叉排序树 T 中值小于 a 的结
15、点个数。（分数：10.00）_数据结构真题 2008 年下半年答案解析(总分：125.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是 ( )（分数：2.00）A.栈B.队列C.树 D.图解析：解析 在树中，除了根结点和叶子结点外，其余结点都仅有一个直接前驱而且有一个或多个直接后继。而根结点没有直接前驱但有一个或多个直接后继，叶子结点有一个直接前驱却没有直接后继。2.下面程序段的时间复杂度为 ( ) for(i=0;im;i+) for(j=0;jn;j+) Aij=i*j;
16、（分数：2.00）A.O(m2)B.O(n2)C.O(m* D.O(m+解析：解析 此程序的时间复杂度即为程序中循环次数的时间耗费。由程序为嵌套循环，外层循环的时间复杂度 T(n1)=m，内层循环的时间复杂度 T(n2)=n，则此程序的时间复杂度 T(n)=m*n，即为 0(m*n)。3.在头指针为 head 的非空单循环链表中，指针 p 指向尾结点，下列关系成立的是 ( )（分数：2.00）A.pnext=head B.pnextNext=headC.pnext=NULLD.p=head解析：解析 在单链表中，将终端结点的指针域 NULL 改为指向表头结点或开始结点，就得到了单链形式的循环链
17、表，并简单称为单循环链表。故由题目中此单循环锚表的头指针为 head，指针 p 指向尾结点，可得 pnext=head。4.若以 S 和 X 分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作序列是( )（分数：2.00）A.SXSSXXXXB.SXXSXSSXC.SXSXXSSXD.SSSXXSXX 解析：解析 可以按以下两个原则来判断出正确的栈操作序列：(1)操作序列中进栈次数和出栈次数相等；(2)操作序列中任一操作之前的进栈次数大于等于出栈次数。5.两个字符串相等的条件是 ( )（分数：2.00）A.串的长度相等B.含有相同的字符集C.都是非空串D.串的长度相等且对应的字符相同
18、 解析：6.如果将矩阵 Ann的每一列看成一个子表，整个矩阵看成是一个广义表 L，即 L=(a11，a 21，a n1)，(a12，a 22，a n2)，(a 1n，a 2n，a nn)，并且可以通过求表头 head 和求表尾 tail 的运算求取矩阵中的每一个元素，则求得 a21的运算是 ( )（分数：2.00）A.head(tail(head() B.head(head(head()C.tail(head(tail()D.head(head(tail()解析：解析 若广义表 LS 非空(n1)，则 a1是 LS 的表头，其余元素组成的表(a 2，a n)称为 LS 的表尾。则此题目欲求得元
19、素 a21，则需先进行取表头运算 head(L)得子表 1(a11，a 21，a n1)，然后对此子表 1 进行取表尾运算 tail(head(L)得子表 2(a21，a n1)，再对子表 2 进行取表头运算 head(tail(head(L)可得元素 a21。7.已知一棵含 50 个结点的二叉树中只有一个叶子结点，则该树中度为 1 的结点个数为( )（分数：2.00）A.OB.1C.48D.49 解析：解析 由此二叉树仅有一个叶子结点，可知此二叉树中除叶子结点外的所有结点都仅有一颗子树，即这些结点的度都为 1，而这些结点的个数为 50-1=49。8.在一个具有 n 个顶点的有向图中，所有顶点
20、的出度之和为 Dout，则所有顶点的入度之和为( )（分数：2.00）A.Dout B.Dout-1C.Dout+1D.n解析：解析 在有向图中，所有顶点的入度之和等于出度之和。9.如图所示的有向无环图可以得到的拓扑序列的个数是 ( ) （分数：2.00）A.3B.4C.5 D.6解析：解析 此有向无环图可以得到的操作序列：(1)2、6、3、5、4；(2)2、6、5、3、4；(3)6、2、3、5、4；(4)6、2、5、3、4；(5)6、5、2、3、4。10.如图所示的带权无向图的最小生成树的权为 ( ) （分数：2.00）A.51B.52C.54 D.56解析：解析 根据最小生成树的构造过程，
21、可知在构造本题中无向图的最少生成树时，将选取权值分别为 10、14、12、18 的边，所以此最小生成树的权即各边权值之和即 54。11.对长度为 n 的关键字序列进行堆排序的空间复杂度为 ( )（分数：2.00）A.O(log2B.O(1) C.O(D.O(n*log2解析：解析 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为 0(1)，但它是不稳定的。12.已知用某种排序方法对关键字序列(51,35,93,24,13,68,56,42,77)进行排序时，前两趟排序的结果为 (35,51,24,13,68,56,42,77,93) (35,24
22、,13,51,56,42,68,77,93) 所采用的排序方法是 ( )（分数：2.00）A.插入排序B.冒泡排序 C.快速排序D.归并排序解析：解析 由题目中第一趟排序的结果是将所有关键字中最大的关键字(97)放在了序列最后，第二趟排序的结果是将除 97 以外的所有关键字中最大的关键字放在了序列中倒数第二个位置，可知此排序方法为冒泡排序。13.已知散列表的存储空间为 T018，散列函数 H(key)=key%17，并用二次探测法处理冲突。散列表中已插入下列关键字：T5=39，T6=57 和 T7=7，则下一个关键字 23 插入的位置是 ( )（分数：2.00）A.T2B.T4C.T8D.T1
23、0 解析：解析 由题意可得 H(23)=6，而 T6中已有关键字，产生冲突，此时采用二次探测法，则当 i=1 时，h1=(6+11)%17=7，又 T7中也已有关键字仍然冲突。则选 i=2，此时 h2=(6+22)%17=10，此时可判定此关键字可插入 T10单元中。14.适宜进行批量处理的文件类型是 ( )（分数：2.00）A.顺序文件 B.索引顺序文件C.散列文件D.多关键字文件解析：解析 顺序文件采取顺序查找法对于少量的检索是不经济的，但适合于批量检索，即把用户的检索要求先进行积累，一旦待查记录聚集到一定数量之后，便把这批记录按主关键字排序，然后，通过一次顺序扫描文件来完成这一批检索要求
24、。15.VSAM 文件的索引结构为 ( )（分数：2.00）A.B+树 B.二叉排序树C.B-树D.最优二叉树解析：解析 VSAM 是 Virtual Storage Access Method(虚拟存储存取方法)的缩写，它是一种索引顺序文件的组织方式，采用 B+树作为动态索引结构。二、B填空题/B(总题数：10，分数：20.00)16.如果某算法对于规模为 n 的问题的时间耗费为 T(n)=3n3，在一台计算机上运行时间为 t 秒，则在另一台运行速度是其 64 倍的机器上，用同样的时间能解决的问题规模是原问题规模的 1 倍。（分数：2.00）填空项 1:_ （正确答案：4）解析：解析 设在速
25、度快的机器上运行此算法的规模为 n1，则时间耗费为 ，则由速度快机器是原机器速度的 64 倍，即17.将两个长度分别为 m 和 n 的递增有序单链表，归并成一个按元素递减有序的单链表，可能达到的最好的时问复杂度是 1。（分数：2.00）填空项 1:_ （正确答案：O(m+n)）解析：解析 将两个递增有序单链表合并为一个递减有序的单链表，则将这两个单链表都从最后一个元素开始，按照由后至前的顺序，将两单链表中元素进行比较，从而选取较大的元素依次组成新的单链表。18.已知循环队列的存储空间大小为 m，队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置，则在队列不满的情况
26、下，队列的长度是 1。（分数：2.00）填空项 1:_ （正确答案：(rear-front+m)%m）解析：19.字符串“sgabacbadfgbacst“中存在有 1 个与字符串“ba“相同的子串。（分数：2.00）填空项 1:_ （正确答案：3）解析：20.假设以列优先顺序存储二维数组 A58，其中元素 A00的存储地址为 LOC(a00)，且每个元素占 4个存储单元，则数组元素 Aij的存储地址为 1 。（分数：2.00）填空项 1:_ （正确答案：LOC(a 00)+4(5j+i)）解析：21.假设用x,y表示树的边(其中 s 是 y 的双亲)，已知一棵树的边集为b,d，a,b，c,g
27、，c,f，c,h，a,c)，该树的度是 1。（分数：2.00）填空项 1:_ （正确答案：3）解析：解析 树的度为该树中结点的最大度数，由此树的边集可知结点 c 的度数最大为 3，则此树的度为 3。22.n 个顶点且含有环路的无向连通图中，至少含有 1 条边。（分数：2.00）填空项 1:_ （正确答案：n）解析：解析 n 个顶点的无向连通图有环路且边最少时，此图仅有一个环路且所有顶点均在此环路中，此时边数为 n。23.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是 1。（分数：2.00）填空项 1:_ （正确答案：选择排序）解析：24.和二分查找相比，顺序查
28、找的优点是除了不要求表中数据元素有序之外，对 1 结构也无特殊要求。（分数：2.00）填空项 1:_ （正确答案：存储）解析：25.顺序文件中记录存放的物理顺序和 1 顺序一致。（分数：2.00）填空项 1:_ （正确答案：逻辑）解析：三、B解答题/B(总题数：4，分数：25.00)26.由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。 （分数：5.00）_正确答案：()解析：前序序列：G H I J 后序序列：H J I G27.图的邻接表的类型定义如下所示： #define MaxVertexNum 50 typedef struct node int adj
29、vex; struct node*next; EdgeNode; typedef struct VertexType vertex; EdgeNode*firstedge; VertexNode; typedef VertexNode A djListMaxVertexNum; typedef struct AdjList adjiist; int n,e; ALGraph; 为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。 （分数：5.00）_正确答案：()解析：typeclef struct ArcNode V
30、Node*adjvex; /该弧所指向的顶点的位置 struct ArcNode*nextarc; /指向下一条弧的指针 ArcNode; typedef struct VNode VertexType data; /顶点信息 struct VNode*nextVertex; /指向下一个顶点的指针 ArcNode*firstarc; /指向第一条依附该顶点的弧 VNode.*AdjList; typedef struct AdjList adjList; int n,e; ALGraph;28.某类物品的编号由一个大写英文字母及 2 位数字(09)组成，形如 E32。运用基数排序对下列物品编
31、号序列进行按字典序的排序，写出每一趟(分配和收集)后的结果。 E13,A37,F43,B32,B47,E12,F37,B12 第一趟： 第二趟： 第三耥：（分数：5.00）_正确答案：()解析：第一趟：B32,E12,B12,E13,F43,A37,B47,F37 第二趟：E12,B12,E13,B32,A37,F37,F43,B47 第三趟：A37,B12,B32,B47,E12,E13,F37,F43(1)画出对表长为 13 的有序顺序表进行二分查找的判定树； (2)已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99)，写出在该序列中二分查找 3
32、7 时所需进行的比较次数。（分数：10.00）(1). （分数：5.00）_正确答案：()解析：(2).（分数：5.00）_正确答案：()解析：3四、B算法阅读题/B(总题数：4，分数：40.00)已知线性表的存储结构为顺序表，阅读下列算法，并回答问题： (1)设线性表 L=(21,-7,-8,19,0，-11,34,30，-10)，写出执行 f30( for(i=j=0;iLlength;i+) if(Ldatai=0) if(i!=j)Ldataj=Ldatai; j+; Llength=j; （分数：10.00）(1).（分数：5.00）解析：(2).（分数：5.00）_正确答案：()解
33、析：删除顺序表中的负值元素。阅读下列算法，并回答问题： (1)Q、Q1 和 Q2 都是队列结构，设队列 Q=(1,0,-5,2,-4,-6,9)，其中 1 为队头元素，写出执行f31( InitQueue(Q1); InitQueue(Q2); while(!QueueEmpty(Q) e=DeQueue(Q); if(e=0)EnQueue(Q1,e); else EnQueue(Q2,e); （分数：10.00）(1).（分数：5.00）解析：(2).（分数：5.00）_正确答案：()解析：将队列 Q 的元素依次退队，并将正值及 0 元素入队到 Q1，负值元素入队到 Q2。阅读下列算法，并
34、回答问题： (1)假设串由合法的英文字母和空格组成，并以/0作结束符。设串，写出 f32(s)的返回值； (2)简述算法 f32 的功能。 int f32(char*s) int i,n,inword; n=inword=0; for(i=0;si!=/0;i+) if(si!= n+; else if(si= return n; （分数：10.00）(1).（分数：5.00）解析：(2).（分数：5.00）_正确答案：()解析：对字符串内的单词个数进行累加计数。阅读下列对正整数关键字序列 L 操作的算法，并回答问题： (1)设 L=(28,19,27,49,56,12,10,25,20,50
35、)，写出 f33(L,4)的返回值； (2)简述函数 f33 的功能。 int Partition(SeqList*L,int low,int high); /对 Llowhigh做划分，返回基准记录的位置，并使左部的关键字 /都小于或等于基准记录的关键字，右部的关键字都大于基准记录的关键字 int f33(SeqList L,int k) int low,high,pivotpos; low=1; high=L.length; if(klow|khigh) return-1; do pivotpos=Partition( else if(pivotposk) high=pivotpos-1;
36、 while(pivotpos!=k); return L.datapivotpos; （分数：10.00）(1).（分数：5.00）解析：(2).（分数：5.00）_正确答案：()解析：利用快速排序的“划分”机制进行查找，以求取序列中排行第 k 小的元素。五、B算法设计题/B(总题数：1，分数：10.00)29.二叉排序树的类型定义如下： typedef struet BSTNode/二叉排序树的结点结构 int data; /数据域 struct BSTNode*lchild,*rchild;/左、右孩子指针 BSTNode,*BSTree; 设计递归算法，统计一棵二叉排序树 T 中值小于
37、 a 的结点个数。（分数：10.00）_正确答案：()解析：(P 71)参考答案之一： void count(BSTree T,int a,int*sum) /以 sum 所指单元统计二叉排序树中元素值小于 a 的结点个数，其初值为 0 if(T) count(Tlchild,a,sum); if(TdataA)(*sum)+; count(Trchild,a,sum); 参考答案之二： int count(BSTree T,int a) /统计二又排序树中元素值小于 a 的结点个数 int sum; if(!T)return 0; else sum=count(Tlchild,a); if(Tdataa) return sum+1+count(Trchild,a); else return sum;
