2014(1)数据结构-A-试题

6.一棵二叉树的第7层上最多含有的结点数为A.14B.64C.127D.128正确答案：B（2分）7.下列选项为完全二叉树的是正确答案：A（2分）8.用邻接表表示n个顶点e条边的无向图，其边表结点的总数是A. n×eB. eC. 2eD. n+e正确答案：C（2分）9.无向图中所有顶点的度数之和与所有边数之比是A.1/2B.1C.2D.4正确答案：C（2分）10.采用邻接矩阵存储图时，广度优先搜索遍历算法的时间复杂度为A. O（n）B. O（n+e）C. O（n2）D. O（n3）正确答案：C（2分）11.对序列（15，9，7，8，20，-1，4）进行排序，若一趟排序后的结果为（-1，15，9，7，8，20，4），则采用的排序方法是A.归并排序B.快速排序C.直接选择排序D.冒泡排序正确答案：D（2分）12.比较次数与待排序列初始状态无关的排序方法是A.快速排序B.冒泡排序C.直接插入排序D.直接选择排序正确答案：D（2分）13.查找较快，且插入和删除操作也比较方便的查找方法是A.分块查找B.二分查找C.顺序查找D.折半查找正确答案：A（2分）14.下列关于m阶B树的叙述中，错误．．的是A.根结点至多有m棵子树B.所有叶子都在同一层次上C.每个非根内部结点至少有棵子树D.结点内部的关键字可以是无序的正确答案：D（2分）15.在散列查找中处理冲突时，可以采用开放定址法。

下列不是开放定址法的是A.线性探查法B.二次探查法C.双重散列法D.拉链法正确答案：D（2分）非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

二、填空题（本大题共10小题，每小题2分，共20分）16.数据结构研究的内容包括数据的逻辑结构、________和数据的运算。

正确答案：存储结构（2分）17.头指针为L的带头结点的双循环链表，结点的前趋指针域为prior，后继指针域为next，判断该链表为空的条件是________。

2014数据结构A卷参考答案试卷编号命题人：审核人：试卷分类A五邑大学试卷及参考答案与评分标准学期：2013至2014学年度第 1 学期课程：数据结构课程代号：0800310使用班级：120109姓名：学号：题号得分一、得分一、单项选择题1．设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是。

A． 2 B．3 C．4 D．6 一二三四五六七八九十总分2．4个叶子结点构造一棵哈夫曼树，该树的总结点数是。

A．4 B．5C．6 D．7 具有n个叶子节点的哈夫曼树共有2n-1 个结点3．对于长度为m的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是。

A．若入栈和入队列的序列相同，则出栈序列和出队序列可能相同B．若入栈和入队列的序列相同，则出栈序列和出队序列可以互为逆序C．入队序列与出队序列关系为1:1，而入栈序列与出栈序列关系是1: n (n≥1) D．入队序列与出队序列关系为1: n (n≥1)，而入栈序列与出栈序列关系是1:1 第一句：入队列和出队列的是一样的，要是什么就都是什么，是1:1,一个入队列只可能对应一个出队列第2句：一个入栈序列可能对应多个出站队列1:n 4．在一个单链表HL中，若要删除指针q所指结点的后继结点，则执行。

A．p=q->next; q->next=p->next; C．p=q->next; p->next=q->next; B．p=q->next; q->next=p; D．q->next=q->next->next; q->next=q; 5．假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女之间不能相互继承。

则表示该遗产继承关系的数据结构应该是。

20XX年复习资料大学复习资料专业：班级：科目老师：日期：广东商学院试题参考答案及评分标准20XX12-20XX13 学年第一学期课程名称： 数据结构（A 卷） 课程代码：20XXXX0XX20XXXX0XX 课程负责人：罗勇题号1 2 3 4 5 6 7 8 9 20XXXX 答案B A AC BACADC题号1 2 3 4 5 6 7 8 9 20XXXX 答案C B C B DDABAB题号1 2 3 4 5 6 7 8 9 20XXXX答案× √ × √ √ × × × √ ×四、算法分析（每小题5分，共20XXXX 分）1．(1) ABC_1是直接插入排序方法。

（1分） 最坏情形下，)(2/2/)1)(2(i KCN 222n O n n n ni =≈-+==∑= （1分）)(2/2/)1)(4()21(RMN 22n2n O n n n i i =≈-+=+-=∑= （1分）(2) 排序过程如下：（2分）初始key r[0] (65) 38 80 50 20XXXX 27i=2 38 (38 65) 80 50 20XXXX 27 i=3 38 (38 65 80) 50 20XXXX 27 i=4 50 (38 50 65 80) 20XXXX 27i=5 20XXXX (20XXXX 38 50 65 80) 27 i=6 27 (20XXXX 27 38 50 65 80) （注：哨兵单元不正确扣1分，已排序列不正确扣1分）2．(1) 算法ABC_2功能：以中序遍历的次序，按关键字值递增的顺序依次输出值小于等于给定值60的结点。

若找到值大于60的结点，提前退出算法。

（3分）（2）20XXXX 20XX 35 45 55（每个值输出后换行）（2分）五、算法设计（共10分）（1）写出单链表存储结构的类型定义。

Typedef struct {int data; (1分)struct LNode *next; (1分)} LNode, *LinkList; (1分)（2）status Delete_L(LinkList &L, int min, int max) { LinkList p,q,s;p=L;while (p&&p->next->data<=min) （2分）p=p->next;if (!p) return ERROR;q=p->next;while (q&&q->data<=max) （3分）{ s=q;q=q->next;free(s);} //whilep->next=q; （2分）return OK;}//Delete_L教师（签名）：年月日。

数据结构试卷一、填空殖（每空1分共20分)1.数据的物理结构主要包括___顺序存储结构__________和_链式_____________两种情况。

2.设一棵完全二叉树中有500个结点，则该二叉树的深度为_______9___;若用二叉链表作为该完全二叉树的存储结构，则共有______501_____个空指针域.3.设输入序列为1、2、3，则经过栈的作用后可以得到_____6______种不同的输出序列。

4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的___出度_____,第i列上所有元素之和等于顶点i的____入度____。

5.设哈夫曼树中共有n个结点,则该哈夫曼树中有___0_____个度数为1的结点。

6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d,则e和d的关系为____e=d_____。

7.____中序______遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序）.8.设查找表中有100个元素,如果用二分法查找方法查找数据元素X,则最多需要比较_____7___次就可以断定数据元素X是否在查找表中。

9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为______1______。

10.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号,则第i个结点的双亲结点编号为___i/2_________,右孩子结点的编号为____2i+1_______。

11.设一组初始记录关键字为（72，73,71，23,94,16,5），则以记录关键字72为基准的一趟快速排序结果为_____5 16 71 23 72 94 73______。

12.设有向图G中有向边的集合E=｛〈1，2〉，<2,3>，〈1，4〉，〈4,2>，〈4，3〉｝，则该图的一种拓扑序列为___1 4 2 3___。

20 09 ---------20 10 学年第一学期期末试题课程名称数据结构使用专业计算机答案一、选择题二、综合应用1、有一份电文中共使用5个字符：a,b,c,d,e。

它们的出现频率一次为4,7,5,2,9，请画出对应的赫夫曼树（按左子树根结点的权值小于等于右子树根结点的权值的次序构造），并求出每个字符的赫夫曼编码。

解答：对应的赫夫曼树为：1每个字符的赫夫曼编码分别为：2－0104－0115－006－017－109－112、请证明：若无向图G的顶点度数的最小值大于或等于2，则G必然存在回路。

解答：证明：设无向图G有n个顶点，整个图G的度之和为N。

由于图中顶点度数的最小值大于或等于2，可知：N >= 2n。

由于图中的每条边涉及2个顶点，即每条边含有2个度，则途中的边数 = N/2 >= n。

因此该图G至少有n条边。

由于多于n-1条边的图中必然存在回路，而该图G至少有n条边，故该图G必有回路存在。

3、设有n个无序元素，按非递减次序排序，但只想得到前面长度为k的部分序列，其中n>>k，最好采用什么排序方法？为什么？解答：用堆排序。

原因如下：在内部排序方法中，一趟排序后只有简单选择排序和冒泡排序可以选出一个最大（或最小）元素，并加入到已有的有序子序列中，但要比较n-1次。

选次大元素要再比较n-2次,其时间复杂度是O(n2)。

而快速排序、插入排序、归并排序、基数排序等时间性能好的排序，都要等到最后才能确定各元素位置。

只有堆排序，在未结束全部排序前，可以有部分排序结果。

建立堆后，堆顶元素就是最大（或最小）元素，然后，调堆又选出次大（小）元素。

因此，要求在n个元素中选出k(k<<n,k>2)个最大（或最小）元素，一般均使用堆排序。

4、已知下图中二叉排序树的各结点的值依次为32—40，请标出结点的值。

解答：按照二叉排序树的定义，其中序遍历的结果应为一有序的序列。

由于其中序序列为：5、在下面数组a中链接存储着一个线性表，表头指针为a[0].next，请给出该线性表的逻辑结构。

合肥学院20 13 至20 14 学年第 2 学期数据结构与算法设计 课程考试（ A ）卷答案一、选择题：（2分×15=30分）1．A 2．D 3．B 4．B 5. C 6．D 7. A 8． B 9. D 10. B 11. D 12. D 13. A 14. A 15. A二、填空题：（2分×10=20分）1． n+1-i 2． s->next=p->next; p->next=s3. 12，24，35，27，18，26 4． A[i][j]=1 5. h6. ki<=k2i && ki<=k2i+17. mid=(low+high)/2; r[mid].key>k 8． 中序。

三、应用题：（5分×5=25分）1．树的链式存储结构（3分） 二叉树（2分）2．邻接矩阵：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡011110101110111010101110（3分）邻接表：（2分）3．（3分）（2分）4．（4分）E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} （1分） 5、（5分）四、算法阅读题：（7分+5分=12分） 1、（1）查询链表的尾结点 （3分） （2）将第一个结点链接到链表的尾部，作为新的尾结点 （3分） （3）返回的线性表为（a2,a3,…,an,a1）。

（1） 2．递归地后序遍历链式存储的二叉树 （5分） 五、算法设计题：（7分+6分=13分） 1．void mergelklist(lklist *ha,lklist *hb,lklist *&hc)AB GC EH JF D Ilklist *s=hc=0; （2分）while(ha!=0 && hb!=0)if(ha->data<hb->data){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;} else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;} （3分）if(ha==0) s->next=hb; else s->next=ha; （2分）}2.typedef struct node {int data; struct node *lchild,*rchild;} bitree; （2分）void swapbitree(bitree *bt){bitree *p;if(bt==0) return;swapbitree(bt->lchild); swapbitree(bt->rchild); （2分）p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; （2分）}。

大题共4小题，每小题5分。

共20分)
请在答题卡上作答。

26．设Q是有N个存储空间的循环队列，初始状态front=rear=0，约定指针rear指向的单元始终为空，回答下列问题。

请根据最优二叉树的基本原理，采用类C语言，描述你所设计的成绩判定过程。

29．给定有向无环图G如题29图所示，写出G的5种不同的拓扑排序序列。

的单链表定义如下，其中freq域记录本结点被访问的次数，初值为0，单链表始终以freq 序。

函数f3l完成的功能是：查找给定关键字所在结点，若查找成功，则该结点的freq域加值调整结r旨位置。

请将空白处(1)～(3)补充完整。

在答题卡上作答。

回答下列问题。

五、算法设计题(本大题共l小题，共“l0分) 请在答题卡上作答。

34．已知带头结点的单链表类型定义如下：
- 10 -。