发布时间 : 星期四 文章数据结构复习题汇总更新完毕开始阅读63b051366d175f0e7cd184254b35eefdc8d31534
缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依相同次序从该缓冲区中取出数据打印。该缓冲区作为数据结构是一个（ B）结构。 A. 栈 B.队列 C.表（Table） D.线性表
23、 下面四棵树中，数字表示相应叶子结点的权值，则（ D ）是哈夫曼树（Huffman Tree）。
24、栈和队列的共同点是（ C ）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点
25、串是一种特殊的线性表，其特殊性体现在（ B ）。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符
26 带头节点的单链表head为空的判定条件是( A ). A. head->next==NULL B. head==NULL C. head->next==head D. head!=NULL
27 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，该矩阵的大小是 （ D ） A. n B. (n-1)2 C. n-1 D. n2
28 设有两个串p和q，求q在p中首次出现的位置的运算称作（ B ）。 A. 连接 B. 模式匹配 C. 求子串 D. 求串长
29 下列排序方法中，（ C ）不易于在单链表上实现。 A 直接插入排序 B冒泡排序 C 快速排序 D 简单选择排序
30 下面关于图的存储的叙述中，哪一个是正确的。 （ A ） A．用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关
B．用邻接矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关
C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数
无关
D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
31.排序方法中，从未排序序列中挑选元素，并将其依次与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ C ）
A.快速排序 B. 起泡排序 C插入排序 D. 选择排序
32.请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做多少次关键码比较。 （ D ） A.2 B.3 C. 5 D. 4
33.给定下列有向图和初始结点V1, 按深度优先遍历的结点序列为( B ) A、V1，V3，V4，V5，V2 B、V1，V2，V4，V5，V3 C、V1，V2，V5，V3，V4 D、V1，V2，V3，V4，V5
34 顺序查找法适合于存储结构为（ B ）的线性表。
A散列存储 B 顺序存储或链接存储 C 压缩存储 D 索引存储
35 对线性表进行二分存储时，要求线性表必须（ C ）。 A 以顺序方式存储 B以链接方式存储 C 以顺序方式存储，且节点按关键字有序排序 D 以链接方式存储，且节点按关键字有序排序
1. 2.
3.
4. 5.
6.
二．填空题
若一个算法的基本语句的执行次数为(n3+n2log2n+14n)/n2，则该算法的时间复杂度为__ O(n)______。
6.设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f将依次入栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b、d、c、f、e、a，则栈S的容量至少应该是 3 ，上述过程才不会出错。
设有一空队列Q，经Q.EnQueue(1)，Q.DeQueue ()，Q.EnQueue (2)，Q.EnQueue (3)，Q.EnQueue(4)，Q.DeQueue ()；Q.EnQueue (5)一系列操作后。队列中从队首到队尾的元素依次是__ _3 4 5
空字符串与空格串的区别在于 空格串是一个字符串，由若干空格组成；空字符串中没有字符 。
7．已知某二叉树的后序遍历序列是BDECA, 中序遍历序列是BADCE，那么它的前序遍历序列是 ABCDE 。
写出右图所示二叉树按后序遍历的结果 17,23,45,65,78,09,31,53,87 。
7. 写出右图所示二叉树度为1的内部结点的值 09 。 8. 二叉树的第k层的结点数最多为____2k-1____。
9. 已知完全二叉树的第4层（根结点为第1层）总共只有2个结点，则其叶子结点数是 5 。
10. 某表达式二叉树按先序遍历的结果为+a*+bcd，令a=6,b=3,c=4,d=2，则该表达式的值等于 20 。
11. 弗洛伊德（Floyd）算法用于求___每一对顶点之间_____的最短路径问题。 12. 构造最小生成树的经典算法中，____克鲁斯卡尔（Kruskal）算法___更适用于求稀疏网的最小生成树。
13. 假定一个数列｛25，43，62，31，48，56｝，采用的散列函数为H(k)=k mod 7, 则元素48的同义词是__62______。
五．应用题
1． 已知关键字序列为36, 31, 20, 32, 66, 48,依次将各元素插入到一棵初始
为空的二叉排序树，画出对应的二叉排序树。
36 31 66
20 32 48
2． 已知二叉树如左下图，试写出后序遍历结果。
A
B F
3. 现有森林如右上图，请画出对应的二叉树。 C G D
4.已知一颗二叉树遍历的先序序列为ABDFIGCEHJ，中序序列为BIFDGAEJHC，请画出这颗二叉树。
答案：
ABCDFIGEHJ
5.已知一颗二叉树如下图所示，将此二叉树转换为森林。
ABCD答案：
FGEHIK JABCEGHFIJKD