1、2007 年中国科技大学计算机专业基础综合（数据结构）真题试卷及答案解析(总分：28.00，做题时间：90 分钟)一、单项选择题(总题数：6，分数：12.00)1.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( )存储方式最节省运算时间。（分数：2.00）A.非循环的单链表B.仅有头指针的单循环链表C.非循环的双链表D.仅有尾指针的单循环链表2.以下与数据的存储结构无关的术语是( )。（分数：2.00）A.循环队列B.链表C.哈希表D.栈3.一个栈的输入序列为 1，2，3，n若输出序列的第一个元素是 n，输出第 i(1iA.不确定B.n-i+1C.iD.n-i
2、4.已知广义表 LS=(a，b)，(d，e，f)，运用 laead 和 tail 函数取出 LS 中原子 e 的运算是( )。（分数：2.00）A.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS)D.head(tail(tail(head(LS)5.算术表达式 a+b*(c+de)转为后缀表达式后为( )。（分数：2.00）A.ab+cd+e*B.aI=)cde+*+C.abode*+D.abcode*+6.B+树应用在( )文件系统中。（分数：2.00）A.ISAMB.VSAMC.MAAAD.MNHA二、简答题(总题数：6，分数：12
3、.00)7.设指针 p 指向双向链表中的一个结点，请写出在 p 所指结点之后插入由 s 所指向的结点的操作序列。（分数：2.00）_8.设有关键字 10，20，30，40 和 50，依照不同的输入顺序，共可能组成多少棵不同的二叉排序树。请说明推导理由。（分数：2.00）_9.假设二维数组 A 的维界为一 27,36，当它在内存中按行存放和按列存放时，分别写出数组元素Ai，j的地址计算公式(设每个元素占两个存储单元)。（分数：2.00）_10.设有一棵空的 3 阶 B 一树，一次插入关键值 32，18，10，40，60，58，47，50，29，22，要求： (1)画出该 3 阶 B-树； (2)
4、画出在该 3 阶 B-树中删除关键字 32 后的树的形态。（分数：2.00）_11.已知二叉树的先序遍历序列为 ABCELMNDFGHK，中序遍历序列为(；BLM-NEAFDHKG，要求： (1)画出该二叉树； (2)画出与该二二叉树相对应的森林。（分数：2.00）_12.在含有 n(n0)个关键字的小根堆(堆顶元素最小)中，关键字最大的记录可能存储在什么位置上?说明理由。（分数：2.00）_三、设计题(总题数：2，分数：4.00)13.编写一个算法，输出二叉树中距给定结点最近的叶子子孙(可以是给定结点的孩子)。注：二叉树用二叉链表示。（分数：2.00）_14.编写克鲁斯卡尔算法求无向连通网的
5、最小生成树，并分析你所编写的算法的时间和空间复杂度。（分数：2.00）_2007 年中国科技大学计算机专业基础综合（数据结构）真题试卷答案解析(总分：28.00，做题时间：90 分钟)一、单项选择题(总题数：6，分数：12.00)1.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( )存储方式最节省运算时间。（分数：2.00）A.非循环的单链表B.仅有头指针的单循环链表C.非循环的双链表D.仅有尾指针的单循环链表 解析：2.以下与数据的存储结构无关的术语是( )。（分数：2.00）A.循环队列B.链表C.哈希表D.栈 解析：3.一个栈的输入序列为 1，2，3，n
6、若输出序列的第一个元素是 n，输出第 i(1iA.不确定B.n-i+1 C.iD.n-i解析：4.已知广义表 LS=(a，b)，(d，e，f)，运用 laead 和 tail 函数取出 LS 中原子 e 的运算是( )。（分数：2.00）A.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS) D.head(tail(tail(head(LS)解析：5.算术表达式 a+b*(c+de)转为后缀表达式后为( )。（分数：2.00）A.ab+cd+e*B.aI=)cde+*+ C.abode*+D.abcode*+解析：6.B+树应用在( )文
7、件系统中。（分数：2.00）A.ISAMB.VSAM C.MAAAD.MNHA解析：二、简答题(总题数：6，分数：12.00)7.设指针 p 指向双向链表中的一个结点，请写出在 p 所指结点之后插入由 s 所指向的结点的操作序列。（分数：2.00）_正确答案：(正确答案： )解析：8.设有关键字 10，20，30，40 和 50，依照不同的输入顺序，共可能组成多少棵不同的二叉排序树。请说明推导理由。（分数：2.00）_正确答案：(正确答案： )解析：9.假设二维数组 A 的维界为一 27,36，当它在内存中按行存放和按列存放时，分别写出数组元素Ai，j的地址计算公式(设每个元素占两个存储单元)
8、。（分数：2.00）_正确答案：(正确答案： )解析：10.设有一棵空的 3 阶 B 一树，一次插入关键值 32，18，10，40，60，58，47，50，29，22，要求： (1)画出该 3 阶 B-树； (2)画出在该 3 阶 B-树中删除关键字 32 后的树的形态。（分数：2.00）_正确答案：(正确答案： )解析：11.已知二叉树的先序遍历序列为 ABCELMNDFGHK，中序遍历序列为(；BLM-NEAFDHKG，要求： (1)画出该二叉树； (2)画出与该二二叉树相对应的森林。（分数：2.00）_正确答案：(正确答案： )解析：12.在含有 n(n0)个关键字的小根堆(堆顶元素最小
9、)中，关键字最大的记录可能存储在什么位置上?说明理由。（分数：2.00）_正确答案：(正确答案： )解析：三、设计题(总题数：2，分数：4.00)13.编写一个算法，输出二叉树中距给定结点最近的叶子子孙(可以是给定结点的孩子)。注：二叉树用二叉链表示。（分数：2.00）_正确答案：(正确答案：/二叉树层次遍历算法 #include #include #define MaxSize 1 000 typedef char ElemType； typedef struct node ElemType data； struct node*lchild： struct node*rchild； BTNo
10、de； /使用队列来存储数据，进行层次遍历算法 Node*LevelOrder(BTNode*b) BTNode*P： BTNode*quMaxSize； int front。rear； front=rear=-1： rear+4-； qurear=b： while(front!=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；
11、 qu rear=p-rchild； jf(p-lchild!=NULL&P-rchild!=NULL) return P； return NULL； )解析：14.编写克鲁斯卡尔算法求无向连通网的最小生成树，并分析你所编写的算法的时间和空间复杂度。（分数：2.00）_正确答案：(正确答案：#include #define MAX VERTEX NUM 10 #define 1NFINITY 1000 typedef st ruet Edge int weight； Edge，EdgeMatrixMAX VERTEX NUMMAX VERTEX NUM； typedef struct MGra
12、ph 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) Gedgenum=Gvexnum=0； for(int i=0；ittdn”，Ektail，Ek head，E Ekweight)； void main() MGraph G： InitializeMG(G)； CreateGraph(G)： MiniSpanTreeKruskal(G)； 时间、空间复杂度分析：排序的代价、检查边所关联的两个顶点是否在同一集合中 以及集合合并的代价。)解析：
