数据结构本科试题及答案

《数据结构本科试题及答案》由会员分享，可在线阅读，更多相关《数据结构本科试题及答案（6页珍藏版）》请在金锄头文库上搜索。

1、武汉大学计算机学院2011 年2012 学年第一学期“数据结构”考试试题（A）要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题（共 20 小题，每小题 2 分，共 40 分）1. 下列各选项中属于逻辑结构的是 。A.哈希表 B.有序表 C.单链表 D.顺序表2. 对于数据结构，以下叙述中不正确的是 。A.数据的逻辑结构与数据元素本身的形式和内容无关B.数据的逻辑结构是数据的各数据项之间的逻辑关系C.数据元素是数据的基本单位D.数据项是数据的最小单位3. 某算法的时间复杂度为 O(n2)，表明该算法的 。A.问题规模是 n2 B.执行时间等于

2、 n2C.执行时间与 n2 成正比 D.问题规模与 n2 成正比4. 通常在单链表中增加一个头节点，其目的是为了 。A.使单链表至少有一个节点 B.标识表节点中首节点的位置C.方便单链表运算的实现 D.说明单链表是线性表的链式存储5. 删除某个双链表中的一个节点（非首、尾节点） ，需要修改 个指针域。A.1 B.2 C.3 D.46. 栈和队列是两种不同的数据结构，但它们中的元素具有相同的 。A.抽象数据类型 B.逻辑结构C.存储结构 D.运算7. 元素 a、b、 c、d、e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有的元素都出栈，则所有可能的出栈序列中，以元素 d 开头的序

3、列个数是 。A.3 B.4 C.5 D.68. 设环形队列中数组的下标是 0N -1，其头尾指针分别为 f 和 r（f 指向队列中队头元素的前一个位置，r 指向队尾元素的位置） ，则其元素个数为 。A.r-f B.r-f-1 C.(r-f)N+1 D.(r-f+N)N9. 已知循环队列存储在一维数组 A0.n-1中，且队列非空时 front 和 rear 分别指向队头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在 A0处，则初始时 front 和 rear 的值分别是 。A.0，0 B.0， n-1 C.n-1，0 D.n-1，n-110. 对 于 n 阶 （ n 2） 对

4、称 矩 阵 ， 采 用 压 缩 方 法 以 行 序 优 先 存 放 到 内 存 中 ， 则 需 要 个 存 储 单 元 。2 数据结构试题A.n(n+1)/2 B.n(n-1)/2 C.n2 D.n2/211. 一棵度为 4 的树 T 中，若有 20 个度为 4 的节点，10 个度为 3 的节点，1 个度为2 的节点，10 个度为 1 的节点，则树 T 的叶子节点个数是 。A.41 B.82 C.113 D.12212. 一个具有 n（n2）个顶点的无向图，至少有 个连通分量，最多有 个连通分量。A.0 B.1 C.n-1 D.n13. 含有 n（n2）个顶点的无向图的邻接矩阵必然是一个 。A

5、.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵14. 对如图 1 所示的无向图，从顶点 A 出发得到的广度优先序列可能是 。A.ABECD B.ACBDE C.ACDBE D.ABDEC A B C D E 图 1 一个无向图15. 设有 100 个元素的有序顺序表，用折半查找时，成功时最大的比较次数是 。A.25 B.50 C.10 D.716. 已知一个长度为 16 的顺序表，其元素按关键字有序排序，若采用折半查找法查找一个不存在的元素，则平均关键字比较的次数是 。A.70/17 B.70/16 C.60/17 D.60/1617. 以下关于 m 阶 B-树的叙述中正确的是 。A.每

6、个节点至少有两棵非空子树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进行排序，各趟元素序列的变化情况如

7、下：（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数据结构试题 3（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）求在等概率条件下的查找成功的平均查找长度。

8、2. 有一个无向带权图如图 2 所示，采用 Dijkstra 算法求顶点 0 到其他顶点的最短路径和最短路径长度，要求给出求解过程（即给出求最短路径中各步骤的 S、dist 和 path 值） 。 10 7 9 5 8 1 7 6 0 2 4 1 3 5 图 2 一个无向图3. 简要叙述堆和二叉排序树的区别，并给出关键字序列3,26,12,61,38,40,97,75,53,87调整为大根堆后的结果（直接画出调整后的大根堆） 。三、算法设计题（共 3 小题，每小题 10 分，共 30 分）1有一个线性表(a 1,a2,an)，采用带头节点的单链表 L 存储，设计一个就地算法将其所有元素逆置。所

9、谓就地算法是指算法的空间复杂度为 O(1)。2假 设 二 叉 树 采 用 二 叉 链 存 储 结 构 ， 设 计 一 个 算 法 把 一 棵 含 有 n 个 节 点 的 二 叉 树 b 复 制 到 另一 棵 二 叉 树 t 中 。 给 出 你 所 设 计 算 法 的 时 间 和 空 间 复 杂 度 。3. 假设一个不带权的有向图 G 采用邻接表存储，设计一个算法判断图 G 中是否存在顶点 i 到顶点 j 的边，若存在这样的边返回 1，否则返回 0。4 数据结构试题武汉大学计算机学院2011 年2012 学年第一学期“数据结构”考试试题参考答案（A）要求：所有的题目的解答均写在答题纸上，需写清楚

10、题目的序号。每张答题纸都要写上姓名和序号。一、单项选择题（每小题 2 分，共 40 分）1. B 2. B 3. C 4. C 5. B6. B 7. B 8. D 9. 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)，由先序序列和中序序列可以构造出对应的二叉树，如下图所示。

11、97 38 70 30 45 60 75 40 48 80 （2）ASL 成功 =(11+22+43+34)/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数据结构试题 5求解过程如下：S dist path0 1 2 3 4 5 0 1 2 3 4 50 0 7 11 0 0 0 -1 -1 -101 0 7 11 16 0 0 0 1 -1 -10 1 2 0 7 11 16 18 19 0 0 0 1 2 20 1 2 3 0 7 11 16 1

12、8 19 0 0 0 1 2 20 1 2 3 4 0 7 11 16 18 19 0 0 0 1 2 20 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,3

13、8,40,97,75,53,87调整为大根堆后的结果（直接画出调整后的大根堆） 。答：以小根堆为例，堆的特点是双亲节点的关键字必然小于等于孩子节点的关键字，而两个孩子节点的关键字没有次序规定。而二叉排序树中，每个双亲节点的关键字均大于左子树节点的关键字，每个双亲节点的关键字均小于右子树节点的关键字，也就是说，每个双亲节点的左、右孩子的关键字有次序关系。关键字序列3,26,12,61,38,40,97,75,53,87调整为大根堆后的结果如下：【评分说明】两小题各占 5 分。三、算法设计题（每小题 10 分，共 30 分）1解：对应的算法如下：void Reverse1(LinkList *&L

14、) LinkList *p=L-next,*q; /p 指向开始节点L-next=NULL;6 数据结构试题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 中是否存在边 ArcNode *p;p=G-adjlisti.firstarc;while (p!=NULL & p-adjvex!=j)p=p-nextarc;if (p=NULL)return 0;elsereturn 1;【评分说明】邻接表类型可自行设计。