1、2007年中国科技大学计算机专业基础综合（数据结构）真题试卷及答案与解析 一、单项选择题 1 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用 ( )存储方式最节省运算时间。 （ A）非循环的单链表 （ B）仅有头指针的单循环链表 （ C）非循环的双链表 （ D）仅有尾指针的单循环链表 2 以下与数据的存储结构无关的术语是 ( )。 （ A）循环队列 （ B）链表 （ C）哈希表 （ D）栈 3 一个栈的输入序列为 1， 2， 3， ， n若输出序列的第一个元素 是 n，输出第i(1i0)个关键字的小根堆 (堆顶元素最小 )中，关键字最大的记录可能存储在什么位置上
2、 ?说明理由。 三、设计题 13 编写一个算法，输出二叉树中距给定结点最近的叶子子孙 (可以是给定结点的孩子 )。注：二叉树用二叉链表示。 14 编写克鲁斯卡尔算法求无向连通网的最小生成树，并分析你所编写的算法的时间和空间复杂度。 2007年中国科技大学计算机专业基础综合（数据结构）真题试卷答案与解析 一、单项选择题 1 【正确答案】 D 2 【正确答案】 D 3 【 正确答案】 B 4 【正确答案】 C 5 【正确答案】 B 6 【正确答案】 B 二、简答题 7 【正确答案】 8 【正确答案】 9 【正确答案】 10 【正确答案】 11 【正确答案】 12 【正确答案】 三、设计题 13 【
3、正确答案】 /二叉树层次遍历算法 #include #include #define MaxSize 1 000 typedef char ElemType； typedef struct node ElemType data； struct node*lchild： struct node*rchild； BTNode； /使用队列来存储数据，进行层次遍历算法 Node*LevelOrder(BTNode*b) BTNode*P： BTNode*quMaxSize； int front。 rear； front=rear=-1： rear+4-； qurear=b： while(front!
4、=rear) front=(front+1) MaxSize； p=qufront； printf(“ c“， pdata)； if(p-lchild!=NULL) rear一 (rear+1) MaxSize； qu rear=p-1child； jf(prchild!=NULL) rear=(rear+1) MaxSize； qu rear=p-rchild； jf(p-lchild!=NULL&P-rchild!=NULL) return P； return NULL； 14 【正确答案】 #include #define MAX VERTEX NUM 10 #define 1NFINI
5、TY 1000 typedef st ruet Edge int weight； Edge， EdgeMatrixMAX VERTEX NUMMAX VERTEX NUM； typedef struct MGraph EdgeMatrix edges； int vexnum； int edgenum； MGraph； typedef struct VexGroup int vertex； int group； VexGroup； typedef struct EdgeMuster int tail； int head； int weight； bool used； EdgeMuster； *对图进行初始化 * void InitializeMG(MGraph&G) G edgenum=G vexnum=0； for(int i=0； i t t d n”， Ek tail， Ek head， E Ek weight)； void main() MGraph G： InitializeMG(G)； CreateGraph(G)： MiniSpanTreeKruskal(G)； 时间、空间复杂度分析： 排序的代价、检查边所关联的两个顶点是否在同一集合中 以及集合合并的代价。
