数据结构(A卷)【含答案】

1、试卷编号拟题教研室（或教师）签名教研室主任签名课程名称（含档次） 数据结构A课程代号课程编号闭卷专 业 层次（本、专）本科考试方式（开、闭卷）一、应用题（3小题，共20分）1.设有一个栈，元素进栈的次序为: 设初始状态栈为空，（1） C, B, A ,A , B, 写出下列出栈的操作序列。D , E （ 2） A , C, B ,C,D, E,用I表示进栈操作，0表示出栈操作, （8分）D6种字符：A,B,C,D,E,F ，它们的出现频率依次为16 , 5, 9, 3 , 30 ,1 -4人1J -134411133*1+J判断正误（10小题,共20分）1. 顺序表结构适宜于进行顺序存取,而链

2、表适宜于进行随机存取。2 .一个栈的输入序列为：A , B,C, D，可以得到输出序列：C, A ,2. 一份电文中有1，完成问题：（1 ）设计一棵哈夫曼树；（画出其树结构）（2）计算其带权路径长度WPL。（ 8分）3.已知无向图G的邻接表如图所示，分别写出从顶点1出发的深度遍历和广度遍历序列。（4分）3. 栈和队列都是受限的线性结构。4. 逻辑结构与数据元素本身的内容和形式无关。5 .线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。6. 完全二叉树的某结点若无左孩子，则它必是叶结点。7. 邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。8. 图的深度优先搜索序列

3、和广度优先搜索序列不是惟一的。9.折半查找只适用于有序表，包括有序的顺序表和链表。10.每种数据结构都具备三个基本操作：插入、删除和查找。三、单项选择题（15小题,共30分） 1.算法分析的两个主要方面是（ A.空间复杂度和时间复杂度C.可读性和文档性）。B.正确性和简单性D.数据复杂性和程序复杂性2.具有线性结构的数据结构是（A.图 B.树C.广义表）。D.栈3.下面程序段的时间复杂度是(for(i=0;i<m;i+)for(j=0;j< n;j+)aij=i*j;A.O(m 2)B.O(n2)C. 0(m* n)D. 0(m+n)4.线性表是门个（A.表元素 B.字符）的有限序

4、列。C.数据元素D.数据项5. 线性表L=（a1,a2,an）,下列说法正确的是（A. 每个元素都有一个直接前驱和一个直接后继B. 线性表中至少要有一个元素C. 表中诸元素的排列顺序必须是由小到大或由大到小D. 除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继)。C.head-> next=headD.head!=NULL6. 不带头结点的单链表 head为空的判定条件是（A.head=NULLB.head-> next=NULL 7.队列的插入操作是在（D.队头元素后rear，则判断循环队列为空的条件是（D.fro nt=rear+1A.队尾 B.队头

5、C.队列任意位置8.循环队列的队头和队尾指针分别为frontA.fr on t=rearB.fr on t=0C.rear=09.二叉树的深度为A.2k B.2k-1k,则二叉树最多有（C.2k-1D.2k-1个结点。Q,分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件10 .两个指针P和 是( )。A . P->next=Q->nextB. P->next= QC . Q->next= P D. P= Q11.树最适合用来表示（A .有序数据元素C.元素之间具有分支层次关系的数据）。B.无序数据元素D .元素之间无联系的数据12.表达式a*(b+c)-d的后

6、缀表达式是(A.abcd+- B. abc+*d- C.abc*+d-)。D.-+*abcd13.每个结点只含有一个数据元素, 储结构称为（）结构。A.顺序存储 B.链式存储所有存储结点相继存放在一个连续的存储区里，这种存C.索引存储D.散列存储14.关键路径是事件结点网络中（A.从源点到汇点的最长路径C.最长的回路）。B.从源点到汇点的最短路径D.最短的回路15设有以下四种排序方法，则 A.冒泡排序B.快速排序）的空间复杂度最大。C.堆排序D.希尔排序四、算法设计题（1小题，共8分）1.已知一个单链表，编写一个函数从单链表中删除自第i个结点起的k个结点。（8 分）五、填空题（5小题，共10分

7、）1.由两个栈共享一个存储空间的好处是（2.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。在.3. 对n个元素进行起泡排序， 在情况下比较的次数最少， 其比较次数为况下比较次数最多，其比较次数为4.已知有序表为（12, 18, 24, 35, 47, 50, 62, 83, 90, 115, 134）,当用折半查找 90 时，需进行次查找可确定成功。结点，另一个指向其5在双向链表中，每个结点都有两个指针域，它们一个指向其 结点。六、简答题（2小题，共12分）1 已知一组记录的排序码为（46, 79, 56, 38, 40, 80,95, 24）,写出对其进行快速排序的前两趟的划分

8、结果。2.请说明顺序表和单链表各有何优缺点。湖北警官学院信息技术系2017-2018学年数据结构 A期末考试试卷（A卷）（答案部分）一、应用题（3小题，共20分）1. （ 8 分）解：（1） III000I0I02. （ 8分）（1 ）树形态：jOIS(2) 101100110016（2 ）带权路径长度：3.（4分）【答案】深度优先遍历序列为：1, 2,广度优先遍历序列为：1, 2,二、判断正误（10小题,共20分）1. （X） 2. （X） 3. （V） 4. （V）三、单项选择题WPL=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20=1293,4,5.1.

9、 A 2. D(15小题,共30分)3. C 4. C 5.10.B11.C12.B13.A14.A(V) 6. (V) 7. (X) 8. (V) 9. (X) 10. (X)6. A 7. A 8. A 9. C15.B（1小题，共8分）四、算法设计题1. 解：void Del(ListNode *head,i nt i,i nt k)node *p ,*q;int j;/删除前k个元素if (i=1) For (j=1;j<=k;j+)p=head; / p指向要删除的结点 head=head->n ext; Free( p);elsep=head;for (j=1;j<

10、;=i-2;j+)p=p->next;/ p指向要删除的结点的前一个结点for (j=1；j<=k;j+)q=p->next; / q指向要删除的结点 p->n ext=q->n ext;free(q);五、填空题(5小题，共10分)1. 节省存储空间，降低上溢发生的机率2. 哈希查找3. 正序，n-1，反序，n(n-1)/24. 25. 前趋后继六、简答题1.【答案】(2小题，共12分)第一趟：24 40 38 46 56 80 95 79 第二趟：24 40 40 46 56 80 95 79(1)顺序表的优点：无需为表示表中元素之间的逻辑关系而增加额外的存储。顺序表的缺