内容发布更新时间 : 2024/5/6 17:13:06星期一 下面是文章的全部内容请认真阅读。

武汉大学计算机学院

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. n

2

n2B. 2

n(n?1)C.

2

(n?1)2D.

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个叶子节点，则至少有 个节点。

2 A.501 B.502 C.1001 D.1002 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分）