1、数据结构导论真题 2012年 10月及答案解析(总分：100.00，做题时间：90 分钟)一、第部分 选择题(总题数：15，分数：30.00)1.下面几种算法时间复杂度阶数中，值最大的是_（分数：2.00）A.O(nlog2n)B.O(n2)C.O(n)D.O(2n)2.即使输入非法数据，算法也能适当地作出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为_（分数：2.00）A.正确性B.易读性C.健壮性D.时空性3.设顺序表的长度为 100，则在第 40个元素之后插入一个元素所需移动元素的个数为_（分数：2.00）A.40B.60C.61D.1004.设带头结点的单循环链
2、表的头指针为 head，则判断该链表是否为空的条件是_（分数：2.00）A.head-next=headB.head-next=NULLC.head!=NULLD.head=NULL5.在链栈的运算中，不需要判断栈是否为空的是_（分数：2.00）A.出栈B.进栈C.取栈顶元素D.求链栈的元素个数6.一个队列的输入序列是 A，B，C，D，则该队列的输出序列是_（分数：2.00）A.A，B，C，DB.B，C，D，AC.D，C，B，AD.C，D，B，A7.以行序为主序的二维数组 a36中，第一个元素 a00的存储地址是 100，每个元素占 2个存储单元，则 a12的存储地址是_（分数：2.00）A.
3、100B.108C.114D.1168.对任何一棵二叉树 T，若叶结点数为 5个，则度为 2的结点个数为_（分数：2.00）A.4B.5C.6D.无法确定9.m个叶结点的哈夫曼树中，其结点总数为_（分数：2.00）AmB.2m+1C.2mD.2m-110.二叉树的中序遍历序列中，结点 P排在结点 Q之前的条件是_（分数：2.00）A.在二叉树中 P在 Q的左边B.在二叉树中 P在 Q的右边C.在二叉树中 P是 Q的祖先D.在二叉树中 P是 Q的子孙11.有 10个顶点的无向完全图的边数是_（分数：2.00）A.11B.45C.55D.9012.在带权有向图中求两个结点之间的最短路径可以采用的算
4、法是_（分数：2.00）A.迪杰斯特拉(Dijkstra)算法B.克鲁斯卡尔(Kruskal)算法C.普里姆(Prim)算法D.深度优先搜索(DFS)算法13.二分查找(Binary Search)算法的时间复杂度是_（分数：2.00）A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)14.在一棵初始时为空的二叉树中，依次插入键值序列 50，72，43，85，75，20，38，45，65，60，构造对应的二叉排序树以后，查找元素 60要进行的比较次数是_（分数：2.00）A.2B.3C.4D.515.快速排序属于_（分数：2.00）A.插入排序B.交换排序C.选择排序D.归并
5、排序二、第部分 非选择题(总题数：13，分数：26.00)16.下面算法程序段的时间复杂度为 1。 for(i=1; i=n; i+) for(j=1; j=n; j+) for(k=1; k=n; k+) x+; （分数：2.00）17.所有存储结点存放在一个连续的存储区里，利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。这种存储方式是 1。 （分数：2.00）18.单链表中指针 p指向结点 A，若要删除 A之后的结点(存在且不释放存储空间)，则需要修改指针的操作为 p-next= 1。 （分数：2.00）19.在带有头结点的单链表 head中，首结点的指针为 1。 （分数：2.0
6、0）20.在栈结构中，允许插入和删除的一端称为 1。 （分数：2.00）21.C程序中，将对称矩阵 Ann的下三角元素压缩存储到 n(n+1)/2个元素的一维数组 M中，设 aij(ij)存放在数组 Mk中，则 k的值(用 i,j表示)为 1。 （分数：2.00）22.具有 64个结点的完全二叉树的深度为 1。 （分数：2.00）23.某二叉树的先序遍历序列为 AJKLMNO，中序遍历序列为 JKANMO，则根结点 A的右子树中的结点个数为 1。 （分数：2.00）24.三个顶点 v 1 ，v 2 ，v 3 的图的邻接矩阵为 （分数：2.00）25.除第一个顶点和最后一个顶点相同外，其余顶点不
7、重复的回路，称为 1。 （分数：2.00）26.在顺序查找、二分查找、散列查找和索引顺序查找四种查找方法中，平均查找长度与元素个数没有关系的查找方法是 1。 （分数：2.00）27.堆排序算法的时间复杂度为 1。 （分数：2.00）28.如果要将序列60，18，28，69，99，75，78建成堆，则只需把 60与 1 相互交换。 （分数：2.00）三、应用题(总题数：5，分数：30.00)29.如下图所示，在栈的输入端依次输入元素 A，B，C，试写出在栈的输出端可以得到的所有输出序列，并给出每个序列的操作过程(用 push(A)表示 A进栈，pop(A)表示 A出栈)。 （分数：6.00）_3
8、0.将下图所示的一棵树转换为对应的二叉树。 （分数：6.00）_31.已知含五个顶点 A，B，C，D，E 的连通带权图的邻接矩阵如下图所示，试画出它所表示的连通带权图及该连通带权图的最小生成树。 （分数：6.00）_32.下图所示二叉排序树的各结点的值为 110 中的数，试标出各结点的数值字号。 （分数：6.00）_33.设散列函数 H(key)=key mod 11(mod表示求余运算)，给出键值序列为66，13，41，15，44，6，68，17，26，3l，39，46，用链地址法解决冲突，试画出相应的散列表，并计算在等概率情况下查找成功时的平均查找长度。 （分数：6.00）_四、算法设计题
9、(总题数：2，分数：14.00)34.带头结点的单链表的结点结构如下： typedef struct node int data; struct node *next; Node,*LinkList; 试编写单链表的删除运算算法 void DeleteLinklist(LinkList head,int i)。 （分数：7.00）_35.写出直接选择排序算法。 （分数：7.00）_数据结构导论真题 2012年 10月答案解析(总分：100.00，做题时间：90 分钟)一、第部分 选择题(总题数：15，分数：30.00)1.下面几种算法时间复杂度阶数中，值最大的是_（分数：2.00）A.O(nl
10、og2n)B.O(n2)C.O(n)D.O(2n) 解析：考点 时间复杂度 解析 由题意知，当 n1 时，nnlog 2 nn 2 2 n ，所有时间复杂度最大的是 O(2 n )。2.即使输入非法数据，算法也能适当地作出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为_（分数：2.00）A.正确性B.易读性C.健壮性 D.时空性解析：考点 评价算法好坏的因素 解析 正确性：能正确地实现预订功能，满足具体问题的需求；易读性：易于阅读、理解和交流，便于调试、修改和扩充；健壮性：即使输入非法数据，算法也能适当地作出反应或进行处理，不会产生预料不到的运行结果；时空性：一个算法的
11、时空性是指该算法的时间性能和空间性能。3.设顺序表的长度为 100，则在第 40个元素之后插入一个元素所需移动元素的个数为_（分数：2.00）A.40B.60 C.61D.100解析：考点 顺序表元素的插入操作 解析 在第 40个元素之后插入，需要移动 40以后到 100的 60个元素。4.设带头结点的单循环链表的头指针为 head，则判断该链表是否为空的条件是_（分数：2.00）A.head-next=head B.head-next=NULLC.head!=NULLD.head=NULL解析：考点 带头结点的单链表为空的条件 解析 带头结点的单链表为空的条件：head-next=head。
12、5.在链栈的运算中，不需要判断栈是否为空的是_（分数：2.00）A.出栈B.进栈 C.取栈顶元素D.求链栈的元素个数解析：考点 栈的运算 解析 在栈的运算，中出栈、取栈顶元素和求链栈的元素个数都需要判断栈是否为空，而进栈则不需要。6.一个队列的输入序列是 A，B，C，D，则该队列的输出序列是_（分数：2.00）A.A，B，C，D B.B，C，D，AC.D，C，B，AD.C，D，B，A解析：考点 队列的存取操作原则 解析 队列存取：先进先出。7.以行序为主序的二维数组 a36中，第一个元素 a00的存储地址是 100，每个元素占 2个存储单元，则 a12的存储地址是_（分数：2.00）A.100
13、B.108C.114 D.116解析：考点 二维数组中元素存储地址的计算 解析 m*n 的二维数组中元素存储地址的计算 Loc(i,j)=Loc(0,0)+(i*n+j)*size，所以 Loc(1,2)=100+(1*5+2)*2=114。8.对任何一棵二叉树 T，若叶结点数为 5个，则度为 2的结点个数为_（分数：2.00）A.4 B.5C.6D.无法确定解析：考点 二叉树的性质 3 解析 二叉树的性质 3：对任何一棵二叉树，若度为 0的结点个数 n 0 ，度为 2的结点个数为 n 1 ，则n 0 =n 2 +1，n 0 =5则度为 2的结点个数=n 2 =5-1=4。9.m个叶结点的哈夫
14、曼树中，其结点总数为_（分数：2.00）AmB.2m+1C.2mD.2m-1 解析：考点 哈夫曼算法 解析 对于 m个叶子结点的哈夫曼树，其是 m个权值分量，经过 m-1次合并又产生 m-1个新结点，从而组成的 m+m-1=2m-1个结点的哈夫曼树。10.二叉树的中序遍历序列中，结点 P排在结点 Q之前的条件是_（分数：2.00）A.在二叉树中 P在 Q的左边 B.在二叉树中 P在 Q的右边C.在二叉树中 P是 Q的祖先D.在二叉树中 P是 Q的子孙解析：考点 二叉树的中序遍历 解析 二叉树的中序遍历顺序是，中序遍历左子树，访问根结点，中序遍历右子树。11.有 10个顶点的无向完全图的边数是_
15、（分数：2.00）A.11B.45 C.55D.90解析：考点 无向完全图 解析 无向完全图中任何两点之间都有边，对于 n个顶点的无向完全图来说，共有 12.在带权有向图中求两个结点之间的最短路径可以采用的算法是_（分数：2.00）A.迪杰斯特拉(Dijkstra)算法 B.克鲁斯卡尔(Kruskal)算法C.普里姆(Prim)算法D.深度优先搜索(DFS)算法解析：考点 迪杰斯特拉(Dijkstra)算法 解析 在带权有向图中求两个结点之间的最短路径可以采用的算法是迪杰斯特拉(Dijkstra)算法。13.二分查找(Binary Search)算法的时间复杂度是_（分数：2.00）A.O(n
16、2)B.O(nlog2n)C.O(n)D.O(log2n) 解析：考点 二分查找(Binary Search)算法的时间复杂度 解析 二分查找(Binary Search)算法的时间复杂度是 O(log 2 n)。14.在一棵初始时为空的二叉树中，依次插入键值序列 50，72，43，85，75，20，38，45，65，60，构造对应的二叉排序树以后，查找元素 60要进行的比较次数是_（分数：2.00）A.2B.3C.4 D.5解析：考点 二叉排序树的插入及查找 解析 得到二叉排序树见下图，由图可知，查找元素 60需进行 4次比较。 15.快速排序属于_（分数：2.00）A.插入排序B.交换排序
17、 C.选择排序D.归并排序解析：考点 快速排序 解析 快速排序属于交换排序。二、第部分 非选择题(总题数：13，分数：26.00)16.下面算法程序段的时间复杂度为 1。 for(i=1; i=n; i+) for(j=1; j=n; j+) for(k=1; k=n; k+) x+; （分数：2.00）解析：O(n 3 ) 考点 算法的时间复杂度计算 解析 此算法包含 3重循环，可知时间复杂度为 O(n 3 )。17.所有存储结点存放在一个连续的存储区里，利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。这种存储方式是 1。 （分数：2.00）解析：顺序存储方式 考点 存储方式 解析
18、 所有存储结点存放在一个连续的存储区里，利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。这种存储方式是顺序存储方式。18.单链表中指针 p指向结点 A，若要删除 A之后的结点(存在且不释放存储空间)，则需要修改指针的操作为 p-next= 1。 （分数：2.00）解析：p-next-next 考点 单链表删除操作 解析 单链表中指针 p指向结点 A，若要删除 A之后的结点(存在且不释放存储空间)，则需要修改指针的操作为 p-next=p-next-next。19.在带有头结点的单链表 head中，首结点的指针为 1。 （分数：2.00）解析：head-next 考点 有头结点的单链表
19、 解析 在带有头结点的单链表 head中，首结点的指针为 head-next。20.在栈结构中，允许插入和删除的一端称为 1。 （分数：2.00）解析：栈顶 考点 栈 解析 在栈结构中，允许插入和删除的一端称为栈顶。21.C程序中，将对称矩阵 Ann的下三角元素压缩存储到 n(n+1)/2个元素的一维数组 M中，设 aij(ij)存放在数组 Mk中，则 k的值(用 i,j表示)为 1。 （分数：2.00）解析：k=i(i+1)/2+j 考点 下三角矩阵的压缩存储 解析 下三角矩阵的压缩存储，对应关系为 k=i(i+1)/2+j。22.具有 64个结点的完全二叉树的深度为 1。 （分数：2.00
20、）解析：7 考点 二叉树深度计算 解析 二叉树深度计算公式：(log 2 n)+1=(log 2 64)+1=7。23.某二叉树的先序遍历序列为 AJKLMNO，中序遍历序列为 JKANMO，则根结点 A的右子树中的结点个数为 1。 （分数：2.00）解析：3 考点 由二叉树的中序和先序遍历序列求取树的右子树 解析 3 个结点分别为 NMO。24.三个顶点 v 1 ，v 2 ，v 3 的图的邻接矩阵为 （分数：2.00）解析：2 考点 由图的邻接矩阵求顶点的出度 解析 v 2 的出度即 v 2 行之和=2。25.除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为 1。 （分数：2.0
21、0）解析：简单回路或简单环 考点 简单回路或简单环定义 解析 除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为简单回路或简单环。26.在顺序查找、二分查找、散列查找和索引顺序查找四种查找方法中，平均查找长度与元素个数没有关系的查找方法是 1。 （分数：2.00）解析：散列查找 考点 散列查找特点 解析 散列查找的平均查找长度与元素个数没有关系。27.堆排序算法的时间复杂度为 1。 （分数：2.00）解析：O(n log 2 n) 考点 堆排序算法的时间复杂度 解析 堆排序算法的时间复杂度为 O(nlog 2 n)。28.如果要将序列60，18，28，69，99，75，78建成堆，则
22、只需把 60与 1 相互交换。 （分数：2.00）解析：18 考点 堆排序 解析 如果要将序列60，18，28，69，99，75，78建成堆，则只需把 60与 18(最小堆)相互交换。三、应用题(总题数：5，分数：30.00)29.如下图所示，在栈的输入端依次输入元素 A，B，C，试写出在栈的输出端可以得到的所有输出序列，并给出每个序列的操作过程(用 push(A)表示 A进栈，pop(A)表示 A出栈)。 （分数：6.00）_正确答案：()解析：共有 5种： (1)push(A)，pop(A)，push(B)，pop(B)，push(C)，pop(C)输出序列为：ABC (2)push(A)
23、，pop(A)，push(B)，push(C)，pop(C)，pop(B)输出序列为：ACB (3)push(A)，push(B)，pop(B)，pop(A)，push(C)，pop(C)输出序列为：BAC (4)push(A)，push(B)，pop(B)，push(C)，pop(C)，pop(A)输出序列为：BCA (5)push(A)，push(B)，push(C)，pop(C)，pop(B)，pop(A)输出序列为：CBA 考点 栈的存取原则：后进先出30.将下图所示的一棵树转换为对应的二叉树。 （分数：6.00）_正确答案：()解析：结果见下图： 31.已知含五个顶点 A，B，C，D
24、，E 的连通带权图的邻接矩阵如下图所示，试画出它所表示的连通带权图及该连通带权图的最小生成树。 （分数：6.00）_正确答案：()解析：连通带权图如下： 最小生成树如下： 32.下图所示二叉排序树的各结点的值为 110 中的数，试标出各结点的数值字号。 （分数：6.00）_正确答案：()解析：结果见下图 33.设散列函数 H(key)=key mod 11(mod表示求余运算)，给出键值序列为66，13，41，15，44，6，68，17，26，3l，39，46，用链地址法解决冲突，试画出相应的散列表，并计算在等概率情况下查找成功时的平均查找长度。 （分数：6.00）_正确答案：()解析：(1)
25、散列表如下： 四、算法设计题(总题数：2，分数：14.00)34.带头结点的单链表的结点结构如下： typedef struct node int data; struct node *next; Node,*LinkList; 试编写单链表的删除运算算法 void DeleteLinklist(LinkList head,int i)。 （分数：7.00）_正确答案：()解析：Void DeleteLinklist(LinkList head,int i) Node *q; if(i=1)q=head; else q=head-next; int e=1; while(ci-1)c+ if(q!=NULL q-next=p-next; free(p); else exit(“找不到删除的结点”); 考点 带头结点的单链表元素删除35.写出直接选择排序算法。 （分数：7.00）_正确答案：()解析：Void SeleetSort(List R,int n) intrain,i,j;List t; for(i=1;in-1;i+) min=i; for(j=i+1;jn;j+) if(Ri.keyRmin.key) min=j; if(min!=i) t=Rmin;Rmin=Ri;Ri=t; 考点 直接选择排序算法
