试卷编号 拟题教研室（或教师）签名 教研室主任签名
……………………………………………………………………………………………………… 课程名称（含档次） 数据结构A课程代号 课程编号
专 业 层次（本、专） 本科 考试方式（开、闭卷） 闭卷
一、 应用题(3小题,共20分)
1.设有一个栈，元素进栈的次序为：A，B，C，D，E，用I表示进栈操作，O表示出栈操作，设初始状态栈为空，写出下列出栈的操作序列。（8分） （1）C，B，A，D，E（2）A，C，B，E，D
2. 一份电文中有6种字符：A,B,C,D,E,F，它们的出现频率依次为16，5，9，3，30，1，完成问题：
（1）设计一棵哈夫曼树；（画出其树结构） （2）计算其带权路径长度WPL。（8分）
3. 已知无向图G的邻接表如图所示，分别写出从顶点1出发的深度遍历和广度遍历序列。（4分）
二、判断正误(10小题,共20分)
1．顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 ( )
2．一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。( )
3．栈和队列都是受限的线性结构。（ ）
4. 逻辑结构与数据元素本身的内容和形式无关。（ ）
5．线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。（ ）
6. 完全二叉树的某结点若无左孩子，则它必是叶结点。（ ）
7. 邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。（ ）
8. 图的深度优先搜索序列和广度优先搜索序列不是惟一的。（ ）
9. 折半查找只适用于有序表，包括有序的顺序表和链表。（ ）
10. 每种数据结构都具备三个基本操作：插入、删除和查找。（ ）
三、单项选择题(15小题,共30分) 1.算法分析的两个主要方面是（ ）。
A. 空间复杂度和时间复杂度 B.正确性和简单性
C.可读性和文档性 D.数据复杂性和程序复杂性
2.具有线性结构的数据结构是（ ）。 A.图 B.树 C.广义表 D.栈
3.下面程序段的时间复杂度是（ ）。
for(i=0;i for(j=0;j a[i][j]=i*j; A.O(m2) B.O(n2) C. O(m*n) D. O(m+n) 4. 线性表是n个（ ）的有限序列。 A.表元素 B.字符 C. 数据元素 D.数据项 5. 线性表L=(a1,a2,…,an)，下列说法正确的是（ ）。 A.每个元素都有一个直接前驱和一个直接后继 B.线性表中至少要有一个元素 C.表中诸元素的排列顺序必须是由小到大或由大到小 D.除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继 6. 不带头结点的单链表head为空的判定条件是（ ）。 A.head==NULL B.head->next==NULL C.head->next==head D.head!=NULL 7. 队列的插入操作是在（ ）。 A.队尾 B. 队头 C. 队列任意位置 D. 队头元素后 8. 循环队列的队头和队尾指针分别为front和rear，则判断循环队列为空的条件是（ ）。 A.front==rear B.front==0 C.rear==0 D.front=rear+1 9. 二叉树的深度为k，则二叉树最多有（ ）个结点。 A.2k B.2k-1 C.2k-1 D.2k-1 10．两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（ ）。 A．P->next==Q->next B．P->next== QC．Q->next== P D．P== Q 11．树最适合用来表示( )。 A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据 12. 表达式a*(b+c)-d的后缀表达式是（ ）。 A.abcd+- B. abc+*d- C.abc*+d- D.-+*abcd 13．每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储区里，这种存储结构称为（ ）结构。 A. 顺序存储 B. 链式存储 C. 索引存储 D.散列存储 14.关键路径是事件结点网络中（ ）。 A.从源点到汇点的最长路径 B.从源点到汇点的最短路径 C.最长的回路 D.最短的回路 15．设有以下四种排序方法，则（ ）的空间复杂度最大。 A.冒泡排序 B.快速排序 C.堆排序 D.希尔排序 四、算法设计题(1小题,共8分) 1．已知一个单链表，编写一个函数从单链表中删除自第i个结点起的k个结点。（8分） 五、填空题(5小题,共10分) 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），写出对其进行快速排序的前两趟的划分结果。 2. 请说明顺序表和单链表各有何优缺点。 湖北警官学院信息技术系 2017-2018学年数据结构A期末考试试卷(A卷) （答案部分） 一、应用题(3小题,共20分) 1．（8分）解：（1）IIIOOOIOIO （2）IOIIOOIIOO 2.（8分）（1）树形态： （2）带权路径长度：WPL=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20=129。 3. （4分）【答案】 深度优先遍历序列为：1，2，3，4，5，6 广度优先遍历序列为：1，2，4，3，5，6 二、判断正误(10小题,共20分) 1．（×）2．（×）3．（√）4．（√）5．（√）6.（√）7.（×）8.（√）9.（×）10.（×） 三、单项选择题(15小题,共30分) 1．A 2．D 3．C 4．C 5．D 6．A 7．A 8．A 9．C 10.B 11.C 12.B 13.A 14.A 15.B 四、算法设计题(1小题,共8分) 1．解： void Del(ListNode *head,int i,int k) { node *p,*q; int j; if (i==1) For (j=1;j<=k;j++) // 删除前k个元素 { p=head; // p指向要删除的结点 head=head->next; Free(p); } else { p=head; for (j=1;j<=i-2;j++) p=p->next; // p指向要删除的结点的前一个结点 for (j=1;j<=k;j++) { q=p->next; // q 指向要删除的结点 p->next=q->next; free(q); } } } 五、填空题(5小题,共10分) 1．节省存储空间，降低上溢发生的机率 2．哈希查找 3．正序，n-1，反序，n(n-1)/2 4．2 5．前趋 后继 六、简答题(2小题,共12分) 1. 【答案】 第一趟： 24 40 38 46 [56 80 95 79] 第二趟： 24 [40 40] 46 [56 80 95 79] 2. 【答案】（1）顺序表的优点：① 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；② 可以快速地存取表中任一位置的元素（即随机存取）。顺序表的缺点：① 插入和删除操作需移动大量元素；② 表的容量难以确定；③ 造成存储空间的“碎片”。 （2）单链表的优点：① 不必事先知道线性表的长度；② 插入和删除元素时只需修改指针，不用移动元素。单链表的缺点：① 指针的结构性开销；② 存取表中任意元素不方便，只能进行顺序存取。