武汉大学计算机学院

2012年－2013学年第一学期“数据结构”考试试题（A）

姓名

学号(序号)_ 班号

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和序号。

一、单项选择题（每小题2分，共30分）

1. 数据结构在计算机内存中的表示是指 。 A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系

2. 若线性表最常用的运算是存取第i个元素及其前趋元素的值，则采用 存储方式节省时间。

A.单链表 B.双链表 C.单循环链表 D.顺序表

3. 在一个具有n个结点的有序单链表中插入一个新结点使得仍然有序，其算法的时间复杂度为 。

A.O(log2n) B.O(1) C.O(n2) D.O(n) 4. 栈和队列的共同点是 。 A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有其同点

5. 判定一个循环队列Q（存放元素位置为0～QueueSize-1，front指向队中队首元素的前一个位置，rear指向队中队尾元素的位置）队空的条件是 。

A.Q.front==Q.rear B.Q.front+1==Q.rear C.Q.front==(Q.rear+1)%QueueSize D.Q.rear==(Q.front+1)%QueueSize 6. 串是 。

A.不少于一个字母的序列 B.任意个字母的序列 C.不少于一个字符的序列 D.有限个字符的序列 7. 一个n×n的对称矩阵A，如果采用以列优先（即以列序为主序）的压缩方式存放到一个一维数组B中，则B的容量为 。

A. n2

B.

n2 2 C.

n(n?1) 2 D.

(n?1)2 28. 若一棵3次树中有a个度为1的节点，b个度为2的节点，c个度为3的节点，则该树中有 个叶子节点。

A.1+2b+3c B.a+2b+3c C.2b+3c D.1+b+2c 9. 一棵完全二叉树中有501个叶子节点，则至少有 个节点。 A.501

B.502

C.1001

D.1002

2 10. 在含有n个结点的线索二叉树中，线索的数目为 。

A.n-1 B.n C.n+1 D.2n 11. 下面关于B-树和B+树的叙述中，不正确的结论是 。 A.B-树和B+树都能有效地支持顺序查找 B.B-树和B+树都能有效地支持随机查找 C.B-树和B+树都是平衡的多分树

D.B-树和B+树都可用于文件索引结构

12. 有一个长度为12的有序表R[0..11]，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为 。

A.35/12 B.37/12 C.39/12 D.43/12 13. 数据序列{8,9,10,4,5,6,20,1,2}只能是 的两趟排序后的结果。 A.简单选择排序 B. 冒泡排序 C.直接插入排序 D.堆排序

14. 有一些内排序算法，在最后一趟排序结束前可能所有的数据都没有放在其最终的位置上，这些排序算法是 。

Ⅰ.希尔排序 Ⅱ.快速排序 Ⅲ.归并排序 Ⅳ.堆排序 A.仅Ⅰ、Ⅱ B.仅Ⅱ、Ⅲ C.仅Ⅰ、Ⅲ D.仅Ⅰ、Ⅱ、Ⅳ 15. 在以下排序方法中，关键字比较的次数与元素的初始排列次序无关的是 。 A.快速排序 B.冒泡排序 C.插入排序 D.简单选择排序

二、问答题（共3小题，共30分）

1．设n为3的倍数，分析以下算法的时间复杂度（需给出推导过程）。（8分）

void fun(int n) { int i,j,x,y; for (i=1;i<=n;i++) if (3*i<=n) for (j=3*i;j<=n;j++) { x++; y=3*x+2; } }

2. 按关键字13、24、37、90、53的次序构造一棵平衡二叉树，回答以下问题： （1）该平衡二叉树的高度是多少？ （10分） （2）其根节点的关键字是什么？

（3）其中经过了哪些调整（指出调整名称和次数）。 3. 指出以下关于堆及堆排序叙述的正确性。（12分） （1）任何一棵完全二叉树一定是一个堆。

（2）在大根堆中，最大的元素在根节点中，最小的元素一定在某个叶子节点中。 （3）在大根堆中，堆中任一节点的关键字均大于它的左、右孩子的关键字。

（4）在一个小根堆中，从根节点到某个叶子节点的路径上的所有结点的关键字正好构成一个递增序列。

（5）堆排序在最坏情况下的时间复杂度为O(n2)。 （6）堆排序是一种与初始排序序列无关的排序方法。

四、算法设计题（共3小题，共40分）

1. 设计一个算法，将一个带头结点的数据域依次为a1，a2，…，an（n≥3）的双链表的所有结点逆置，即第一个结点的数据域变为an，即第二个结点的数据域变为an-1，…，最后一个结点的数据域为a1。双链表中每个结点的类型如下：（10分）

typedef struct nhode { ElemType data; struct node *prior,*next; } DLinkList;

2. 假设二叉树采用二叉链存储结构进行存储，每个结点有data、lchild和rchild三个域。设计一个算法，计算一棵给定二叉树中节点值为x的节点个数（注意在一棵二叉树中可能存在相同节点值的节点），并给出你所写出的算法的时间复杂度（设二叉树中结点个数为n）。（15分）

3. 假设一个不带权的无向图采用邻接表G进行存储，设计一个算法FindaPath(G,u,v,&has)，判断该图中顶点u到顶点v是否连通，如果连通，has为1，否则has为0，在调用该算法之前has置初值为0。（15分）

4 考试试题（A）参考答案

一、单项选择题（每小题2分，共30分）

1. A 6. D 11. A

2. D 7. C 12. B

3. D 8. D 13. C

4. C 9. C 14. C

5. A 10. C 15. D

二、问答题（每小题3分，共30分）

1. （8分）解：该算法中的基本运算是x++和y=3*x+2语句。对于最外层的for循环，其执行频度为n+1，但对于里层的for循环，只在3i≤n即i≤n/3时才执行，故基本运算的执行频度=

??1=?(n?3i?1)=

i?1j?3ii?1n／3nn/3n(n?1)=O(n2)。本算法的时间复杂度为O(n2)。 62. （10分）答：如图1所示是构造平衡二叉树的过程，回答问题如下： （1）该平衡二叉树的高度是3。(4) （2）根节点的关键字是24。(4)

（3）其中经过了一次RR调整和一次RL调整。(2)

插入13 插入24 13 24 37 24 24 13 插入90 13 37 90 53 插入53 90 37 90 37 RL调整 13 53 24 插入37 13 24 RR调整 13 24 37 13

图1 构造平衡二叉树的过程

3. （12分）答：（1）错误。 （2）正确。 （3）正确。 （4）正确。 （5）错误。 （6）正确。

四、算法设计题（共3小题，共40分）

1. 解：采用前插法建表，算法如下：（10分）

void Reverse(DLinkList *&h)

{ DLinkList *p=h->next,*q=p->next; h->next=NULL; while (p!=NULL) { p->next=h->next; /*将p所指结点插入到头结点之后*/ p->prior=h; p=q; q=p->next; } }

评分说明：本题可采用循环扫描，改变扫描结点的前后指针域。 2. 解：对应的递归算法如下：（15分）

int FindSum(BTNode *b)

{ if (b==NULL) return 0; if (b->data==x) return(1+FindSum(b->lchild)+FindSum(b->rchild)); else return(FindSum(b->lchild)+FindSum(b->rchild)); }

算法的时间复杂度为O(n)。

评分说明：本题可采用各种遍历方法实现。时间复杂度占2分。 3. 解：对应的算法如下：（15分）

int visited[MAXV]={0}; //全局变量

void FindaPath(ALGraph *G,int u,int v,bool &has) //has表示u?v是否连通，初始时has为0 { int w; ArcNode *p; visited[u]=1; p=G->adjlist[u].firstarc; //p指向u的第一条边 while (p!=NULL) { w=p->adjvex; //w为u的邻接顶点 if (w==v) //从u到v找到一条路径，说经u到v是连通的 { has=1; return; } else if (visited[w]==0) //若顶点未标记访问，则递归访问之 FindaPath(G,w,v,has); //从顶点w出发继续查找 p=p->nextarc //找u的下一个邻接顶点 } }