《数据结构》作业及复习题
一、填空题
1、数据的存储结构分为( )和( )。
2、数据元素的逻辑结构包括：（）、（）
和（）。
3、线性结构是指数据元素之间存在一种（）关系。
4、如果以链表作为栈的存储结构，则退栈操作时判断（）。
5、在队列中存取数据的原则是（）。
6、设数组Data[m]作为循环队列SQ的存储空间，front为队头指针，
rear为队尾指针，则执行出队操作的语句为（）。
7、设r指向单链表的最后一个结点，要在最后一个结点之后插入s
所指的结点，需执行的三条语句是（）；r=s；r->next=NULL。
8、设矩阵A是一对称矩阵（aij=aji,1≤i,j≤8），若每个矩阵元素
占3个单元，将其上三角部分（包括对角线）按行序为主序存放在数组B中，B的首址为1000，则矩阵元素a67的地址为（）。
9、在无头结点的双链表中，指针p所指结点是第一个结点的条件是
（）。
10、在双循环链表中，若要在指针p所指结点前插入指针s所指的
结点，则需执行下列语句：
s->next=p；s->prior=p->prior；p->prior=s；( )=s。
11、对于循环队列Q，设它的头、尾指针分别为Front和Rear，队
列的最大元素个数为MAXNUM，若采用少用一个数据元素空间的方法，
则判断队列满的条件是（），判断队列空的条件是（）。
12、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有（）个叶子结点。
13、一个具有11个结点的完全二叉树，其叶子结点个数为（）。
14、深度为n（根的层次为1）的二叉树至多有（）结点。
15、深度为6（根的层次为1）的二叉树至多有（）结点。
16、一棵具有n个结点的二叉树，当它采用二叉链表作存储结构时，二叉树中的所有结点共有（）个空指针域。
17、如果结点A有3个兄弟，而且B是A的双亲，则B的度是（）。
18、哈夫曼树中结点的度可能是（）
19、任何一个无向连通图的最小生成树有（）棵。
20、在高级语言编制的程序当中，调用子程序与被调用子程序的链接和信息交换需要通过（）来进行。
21、任何一个无向连通图有（）棵最小生成树。
22、直接插入排序的算法时间复杂度为（），空间复杂度为（）。
23、冒泡排序的算法时间复杂度为（），空间复杂度为（）。
24、串是一种特殊的线性表，其特殊性体现在（）。
25、空串与空格串是相同的，这种说法（）。
26、设主串T=’aabaababaabaa’，子串P=’abab’，则简单模式
匹配算法中直至匹配成功，单个字符比较次数为（）。
27、顺序查找法其平均查找长度为（）。
28、对于哈希函数H(key)=key%13，被称为同义词的关键字是
（）。
二、简答题
1、什么是数据结构? 有关数据结构的讨论涉及哪三个方面?
2、铁路进行列车调度时, 常把站台设计成栈式结构的站台试问：
(1) 设有编号为1, 2, 3, 4, 5, 6的六辆列车, 顺序开入栈式
结构的站台, 则可能的出栈序列有多少种?
(2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612,
325641, 154623和135426的出站序列, 如果不能, 说明为什么不能;
如果能, 说明如何得到(即写出"进栈"或"出栈"的序列)。
3、任意找一棵二叉树写出它的先序、中序和后序遍历的结果序列。
4、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历
的结果是EBCDAFHIGJ, 试画出这棵二叉树。
5、设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6,
18}, 试分别写出使用以下排序方法每趟排序后的结果。
并说明做
了多少次排序码比较。
(1) 直接插入排序(2) 希尔排序(增量为5,2,1) (3) 起泡排序
(4) 快速排序 (5) 直接选择排序 (6) 堆排序
6、对于一组给定的权值{7，9，2，6，32，3，21，10}，建立相应
的哈夫曼树，并计算其带权路径长度。
7、 假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7,
c8组成, 各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。
试为这8个字母设计不等长Huffman 编码, 并给出该电文的总码数。
8、 对于如下图所示的有向图，试写出：
(1) 各顶点的度
(2) 它的邻接矩阵及邻接表
(3) 从顶点①或A 出发进行深度优先搜索所得到的深度优先生成树；
(4) 从顶点②或A 出发进行广度优先搜索所得到的广度优先生成树；
三、 算法设计题
1、 构造一个顺序表的删除算法，把顺序表L 中数据元素x 删除。
2、 分别以顺序存储及带头结点的单链表为存储结构,
编写实现线
性表的逆转。
3、设head为单链表的头指针，并设单链表带有头结点，编写算法
将单链表中的数据元素按照其值递增有序的顺序进行就地排序。
4、假设分别以两个元素值递增有序的线性表A、B表示两个集合
（即同一线性表中的元素各不相同），现要求构成一个新的线性表C，C表示集合A与B的交，且C中的元素也递增有序，试以顺序存储及带头结点的单链表为存储结构，分别编写实现上述运算的算法。
5、有线性链表A和B，其数据元素均按从小到大升序排列，编写
算法将这两个线性链表合并为一个线性链表C，要求C的数据元素也是从小到大排列。
6、假设以数组cycque[m]存放循环队列的元素，同时设变量rear
和quelen，分别指示循环队列中队尾元素位置和内含元素个数，试写出相应的入队列和出队列的算法。
7、若用二叉链表作为二叉树的存储表示，试针对以下问题编写递
归算法：
(1)统计二叉树中结点的个数。
(2)统计二叉树中叶子结点的个数。
(3)以二叉树为参数，交换每个结点的左孩子和右孩子。