数据结构期末复习题(带答案)
2019数据结构期末考题
一、单项选择题：
1．稀疏矩阵一般的压缩存储方法有哪些？（D）
A.二维数组和三维数组
B.三元组顺序表和散列
C.二叉链表和三叉链表
D.三元组顺序表和十字链表
2．在下列存储结构中，哪个不是树的存储结构？（A）
A.顺序存储表示法
B.双亲表示法
C.孩子表示法
D.孩子兄弟表示法
3．在一个无向图中，所有顶点的度之和等于边数的几倍。（C）
A.1/2
B. 1
C. 2
D. 4
4．带头结点的单链表L为空的判定条件是什么？（B）
A.L==NULL
B.L→next==NULL
C.L→next==L
D.L！=NULL
5．下列图中所示的4棵二叉树中，哪棵二叉树树不是完全二叉树。（ C ）
（A）A．DCAB B．ABDC
C．ABCD D．ACDB
7. 算法分析的主要目的是分析算法的效率以求对算法进行改进，算法分析主要分析哪两个方面。（A）A．时间复杂度和空间复杂度
B．正确性和简明性
C．可读性和文档性
D．数据复杂性和程序复杂性
8. 广义表E=（a, E）的长度为？（B）
A．1
B．2
C．4
D．∞
9．队列的操作是按照什么原则进行的？（A）
A.先进先出
B.上进上出
C.可随机访问任一元素
D.后进先出
10．在一个有向图中，所有顶点的度之和等于边数的几倍？（B）
A.1/2
B. 1
C. 2
D. 4
11．对线性表进行折半查找时，要求线性表必须具有的条件是? （C）
A.以顺序方式存储
B.以链表方式存储
C.以顺序方式存储，且结点按关键字有序排序
D.以链表方式存储，且结点按关键字有序排序
12．在数据结构中，从逻辑上可以把数据结构分为哪两类？（A）A．线性结构和非线性结构
B．紧凑结构和非紧凑结构
C．动态结构和静态结构
D．内部结构和外部结构
13．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储什么？（C）
A.数据的处理方法
B.数据元素的类型
C.数据元素之间的关系
D.数据的存储方法
14．串a=’BEI JING’，下列哪个串不是串a 的子串？（ C ）
A.b=’BEI’
B.d=’JING’
C.c=’BEIJI’
D.e=’ BEI JI’
15．广义表（（a ），a ）的表头为？ （ B ） A ．a B ．（a ）
C ．（（a ））
D ．（（a ），a ）
二、简答题：
1. 若频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构，为什么？
应该采用链式存储结构。因为采用链式结构存储线性表，插入和删除操作需要从头结点起查找被插入或删除结点的前驱结点，并修改这些结点的指针域，查找过程平均移动指针域为表长的一半；而采用顺序结构存储线性表，插入和删除操作需要平均移动表中的一半元素。但移动指针域操作比移动元素操作花费的时间少得多。
2. 现有稀疏矩阵A 如下图所示，写出Ａ对应的以行序为主序顺序排列的三元组表示。
012900
00000
00003000014000240000018000001500700
0??
?
?
?????
??????
????
?-- 1
1
2122
139331-3436145432465218761158
6
4
-7
3. 画出无向图G 的邻接表。(该顶点与哪几个顶点相连)
4. 简述顺序表和链表存储方式的优缺点。
顺序表：优点是存取速度高效，通过下标来直接存储；缺点是1.插入和删除比较慢，2.不可以增长长度
链表：优点是插入和删除速度快，保留原有的物理顺序；缺点：查找速度慢，因为查找时，需要循环链表访问。
V1
V4
V3
V5 V2
5.空串和空格串(或称空格符串)的是否一样，如不一样请分别简述空串和空格串是什么？
不一样。首先，空串是指不包括任何字符的串，空格串指包含若干个空格字符的字符串；其次，空串长度为零，空格串长度为所包括的空格字符的个数。
6.算法的5个重要特性是什么，并对其进行简要说明。
有穷性：一个算法必须保证执行有限步之后结束。
确切性：算法的每一步骤必须有确切的定义。
输入：一个算法必须有输入，可以是0个或多个。
输出：一个算法必须有输出，可以是一个或多个输出，没有输出的算法是毫无意义的。可行性：算法原则上能够精确地运行，而且做有限次运算后即可完成。
7.画出有向图G的邻接表。
三、应用题：
1.设给定权集w={4，7，5，2，9}，构造一棵关于w的哈夫曼树，并求其加权路径长度WPL。（找出字符中最小的两个，小的在左边，大的在右边）
2.设查找的关键字序列为{1，12，5，8，3，10，7，13，9}，依次取序列中的各关键字，构造一棵二叉排序树，并写出构造过程。
3.已知序列{49，38，65，97，76，13，27，50，55，04}请给出采用直接插入序法对该序列进行升序排序，并给出排序过程中每趟结果。
4.设给定权集w={2，3，4，7，8，9}，构造一棵关于w的哈夫曼树，并求其加权路径长度WPL。
5.从结点V1开始，使用普里姆（Prim）算法构造出如下图所示的最小生成树，画出最小生成树的构造过程。
6.已知序列{49，38，65，97，76，13，27，49，55，04}请给出采用希尔排序法（d1=6，d2=4，d3=2）对该序列进行升序排序并给出排序过程中每趟结果。
五、算法设计题：
1.在带头结点的单链线性表L中，删除第i个结点，并由e返回其数据值, 试写出函数ListDelete_L来实现这一删除操作。
要求：①如果成功删除，返回字符“OK”；否则返回字符“ERROR”。
②对重要步骤进行说明。
2.在带头结点的单链线性表L中第i个位置之前插入数据e，试写出函数ListInsrt_L 来实现这一插入操作。
（1）如果成功插入，返回字符“OK”；否则返回字符“ERROR”。
（2）对重要步骤进行说明。
//在带头结点的单向链表L中，删除第i 个位置元素，并由e返回其值
//当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
LinkList p=L; //初始化，p指向表头
int j=0; //j为计数器
while (p->next&&j
++j;
}
if (!p->next||j>i-1) return ERROR; //第i个元素不存在
LinkList q=p->next; p->next=q->next; //删除
e=q->data; //返回值送e
free(q); //释放结点
return OK;
} //LinkDelete_L
void CreatList_L(LinkList &L,int n)
{