武汉大学计算机学院2011年－2012学年第一学期“数据结构”考试试题（A）要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。

每张答题纸都要写上姓名和学号。

一、单项选择题（共20小题，每小题2分，共40分）1. 下列各选项中属于逻辑结构的是。

A.哈希表B.有序表C.单链表D.顺序表2. 对于数据结构，以下叙述中不正确的是。

A.数据的逻辑结构与数据元素本身的形式和内容无关B.数据的逻辑结构是数据的各数据项之间的逻辑关系C.数据元素是数据的基本单位D.数据项是数据的最小单位3. 某算法的时间复杂度为O(n2)，表明该算法的。

A.问题规模是n2B.执行时间等于n2C.执行时间与n2成正比D.问题规模与n2成正比4. 通常在单链表中增加一个头节点，其目的是为了。

A.使单链表至少有一个节点B.标识表节点中首节点的位置C.方便单链表运算的实现D.说明单链表是线性表的链式存储5. 删除某个双链表中的一个节点（非首、尾节点），需要修改个指针域。

A.1B.2C.3D.46. 栈和队列是两种不同的数据结构，但它们中的元素具有相同的。

A.抽象数据类型B.逻辑结构C.存储结构D.运算7. 元素a、b、c、d、e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有的元素都出栈，则所有可能的出栈序列中，以元素d开头的序列个数是。

A.3B.4C.5D.68. 设环形队列中数组的下标是0～N-1，其头尾指针分别为f和r（f指向队列中队头元素的前一个位置，r指向队尾元素的位置），则其元素个数为。

A.r-fB.r-f-1C.(r-f)％N+1D.(r-f+N)％N9. 已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。

若初始时队列空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是。

A.0，0B.0，n-1C.n-1，0D.n-1，n-110. 对于n阶（n≥2）对称矩阵，采用压缩方法以行序优先存放到内存中，则需要个存储单元。

A.n(n+1)/2B.n(n-1)/2C.n2D.n2/211. 一棵度为4的树T中，若有20个度为4的节点，10个度为3的节点，1个度为2的节点，10个度为1的节点，则树T的叶子节点个数是。

A.41B.82C.113D.12212. 一个具有n（n≥2）个顶点的无向图，至少有①个连通分量，最多有②个连通分量。

A.0B.1C.n-1D.n13. 含有n（n≥2）个顶点的无向图的邻接矩阵必然是一个。

A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵14. 对如图1所示的无向图，从顶点A出发得到的广度优先序列可能是。

A.ABECDB.ACBDEC.ACDBED.ABDEC图1 一个无向图15. 设有100个元素的有序顺序表，用折半查找时，成功时最大的比较次数是。

A.25B.50C.10D.716. 已知一个长度为16的顺序表，其元素按关键字有序排序，若采用折半查找法查找一个不存在的元素，则平均关键字比较的次数是。

A.70/17B.70/16C.60/17D.60/1617. 以下关于m阶B-树的叙述中正确的是。

A.每个节点至少有两棵非空子树B.树中每个节点至多有⎡m/2⎤-1个关键字C.所有叶子节点均在同一层上D.当插入一个关键字引起B-树节点分裂时，树增高一层18. 为提高散列（哈希）表的查找效率，可以采取的正确措施是。

Ⅰ.增大装填（载）因子Ⅱ.设计冲突（碰撞）少的散列函数Ⅲ.处理冲突（碰撞）时避免产生聚集（堆积）现象A.仅ⅠB.仅ⅡC.仅Ⅰ、ⅡD.仅Ⅱ、Ⅲ19. 数据序列{8,9,10,4,5,6,20,1,2}只能是的两趟排序后的结果。

A.简单选择排序B.冒泡排序C.直接插入排序D.堆排序20. 用某种排序方法对顺序表{24,88,21,48,15,27,69,35,20}进行排序，各趟元素序列的变化情况如下：（1）{24,88,21,48,15,27,69,35,20}（2）{20,15,21,24,48,27,69,35,88}（3）{15,20,21,24,35,27,48,69,88}（4）{15,20,21,24,27,35,48,69,88}则所采用的排序方法是。

A.快速排序B.简单选择排序C.直接插入排序D.归并排序二、问答题（共3小题，每小题10分，共30分）1. 一棵二叉排序树按先序遍历得到的关键字序列为：(50,38,30,45,40,48,70,60,75,80)。

回答以下问题：（1）画出该二叉排序树。

（2）求在等概率条件下的查找成功的平均查找长度。

2. 有一个无向带权图如图2所示，采用Dijkstra算法求顶点0到其他顶点的最短路径和最短路径长度，要求给出求解过程（即给出求最短路径中各步骤的S、dist和path值）。

图2 一个无向图3. 简要叙述堆和二叉排序树的区别，并给出关键字序列{3,26,12,61,38,40,97,75,53,87}调整为大根堆后的结果（直接画出调整后的大根堆）。

三、算法设计题（共3小题，每小题10分，共30分）1．有一个线性表(a1,a2,…,a n)，采用带头节点的单链表L存储，设计一个就地算法将其所有元素逆置。

所谓就地算法是指算法的空间复杂度为O(1)。

2．假设二叉树采用二叉链存储结构，设计一个算法把一棵含有n个节点的二叉树b复制到另一棵二叉树t中。

给出你所设计算法的时间和空间复杂度。

3. 假设一个不带权的有向图G采用邻接表存储，设计一个算法判断图G中是否存在顶点i到顶点j的边，若存在这样的边返回1，否则返回0。

武汉大学计算机学院2011年－2012学年第一学期“数据结构”考试试题参考答案（A）要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。

每张答题纸都要写上姓名和序号。

一、单项选择题（每小题2分，共40分）1. B2. B3. C4. C5. B6. B7. B8. D9. B 10. A11. B 12. ①B ②D 13. A 14. B 15. D16. A 17. C 18. D 19. C 20. A二、问答题（共3小题，共30分）1.答（1）先序遍历得到的序列为：(50,38,30,45,40,48,70,60,75,80)，中序序列是一个有序序列，所以为：(30,38,40,45,48,50,60,70,75,80)，由先序序列和中序序列可以构造出对应的二叉树，如下图所示。

（2）ASL成功=(1×1+2×2+4×3+3×4)/10=2.9。

【评分说明】（1）占8分，（2）占2分。

2. 答：对应的邻接矩阵如下：0 7 11 ∞∞∞7 0 10 9 ∞∞11 10 0 5 7 8∞9 5 0 ∞∞∞∞7 ∞0 6∞∞8 ∞ 6 0求解过程如下：S dist path0 1 2 3 4 5 0 1 2 3 4 5数据结构试题 5{0} 0 7 11 ∞∞∞0 0 0 -1 -1 -1 {01} 0 7 11 16 ∞∞0 0 0 1 -1 -1 {0 1 2} 0 7 11 16 18 19 0 0 0 1 2 2{0 1 2 3} 0 7 11 16 18 19 0 0 0 1 2 2{0 1 2 3 4} 0 7 11 16 18 19 0 0 0 1 2 2{0 1 2 3 4 5} 0 7 11 16 18 19 0 0 0 1 2 2求解结果如下：从0到1的最短路径长度为:7 路径为:0,1从0到2的最短路径长度为:11 路径为:0,2从0到3的最短路径长度为:16 路径为:0,1,3从0到4的最短路径长度为:18 路径为:0,2,4从0到5的最短路径长度为:19 路径为:0,2,5【评分说明】结果为5分,过程为5分。

3. 简要叙述堆和二叉排序树的区别，并给出关键字序列{3,26,12,61,38,40,97,75,53,87}调整为大根堆后的结果（直接画出调整后的大根堆）。

答：以小根堆为例，堆的特点是双亲节点的关键字必然小于等于孩子节点的关键字，而两个孩子节点的关键字没有次序规定。

而二叉排序树中，每个双亲节点的关键字均大于左子树节点的关键字，每个双亲节点的关键字均小于右子树节点的关键字，也就是说，每个双亲节点的左、右孩子的关键字有次序关系。

关键字序列{3,26,12,61,38,40,97,75,53,87}调整为大根堆后的结果如下：【评分说明】两小题各占5分。

三、算法设计题（每小题10分，共30分）1．解：对应的算法如下：void Reverse1(LinkList *&L){ LinkList *p=L->next,*q; //p指向开始节点L->next=NULL;while (p!=NULL){ q=p->next;p->next=L->next; //将*p节点插入到新建链表的前面L->next=p;p=q;}}【评分说明】单链表类型可自行设计。

2．解：对应的递归算法如下：void Copy(BTNode *b,BTNode *&t){ if (b==NULL)t=NULL;else{ t=(BTNode *)malloc(sizeof(BTNode));t->data=b->data; //复制一个根节点*tCopy(b->lchild,t->lchild); //递归复制左子树Copy(b->rchild,t->rchild)；//递归复制右子树}}算法的时间复杂度为O(n)，空间复杂度为O(n)。

【评分说明】二叉链类型可自行设计。

【评分说明】算法的时间和空间复杂度各占1分。

3. 解：对应的算法如下：int HasArc(AGraph *G,int i,int j) //判断图G中是否存在边<i,j> { ArcNode *p;p=G->adjlist[i].firstarc;while (p!=NULL && p->adjvex!=j)p=p->nextarc;if (p==NULL)return 0;elsereturn 1;}【评分说明】邻接表类型可自行设计。