一、选择题。
1． 广度优先遍历的含义是：从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到是下图的广度优先遍历序列。
a. 1 2 6 3 4 5 b. 1 2 3 4 5 6 c. 1 6 5 2 3 4 d. 1 6 4 5 2 3
2． 对于长度为11的顺序存储的有序表，若采用折半查找（向下取整），则找到第5个元素需要与表中的。
个元素进行比较操作（包括与第5个元素的比较）。
a. 5b. 4c. 3d. 2
3． 结点数目为 n 的二叉查找树（二叉排序树）的最小高度为 （ 1 ） 最大高度为（ 2 ）。
（1）a. n b. c. [log2n] d. [log2(n+1)]
（2）a. n b. c. [log2n] d. [log2(n+1)]
4． 堆排序是一种基于__(1)__的排序方法，__2)__不是堆。
(1)a. 计数 b. 插入 c. 选择d. 归并。
(2) a．15，28，25，56，68，63，30 b．15，28，25，30，68，63，56
c．68，28，63，25，15，56，30 d．68，56，39，63，28，25，15
5． 下面关于串的叙述中，哪一个是不正确的？（
a．串是字符的有限序列b．空串是由空格构成的串。
c．模式匹配是串的一种重要运算 d．串既可以采用顺序存储，也可以采用链式存储。
6． 设无向图的顶点个数为n，则该图最多有（ ）条边。
a．n-1 b．n(n-1)/2 c． n(n+1)/2 d．0
7． 以下数据结构中，（ 是非线性数据结构。
a．树 b．字符串 c．队列 d．栈。
8． 下面关于线性表的叙述中，错误的是哪一个？（
a．线性表采用顺序存储，必须占用一片连续的存储单元。
b．线性表采用顺序存储，便于进行插入和删除操作。
c．线性表采用链接存储，不必占用一片连续的存储单元。
d．线性表采用链接存储，便于插入和删除操作。
9． 假设以数组a[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）
a．(rear-front+m)%m b．rear-front+1
c．(front-rear+m)%m d．(rear-front)%m
10． 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ ）
a．p->next=s; s->next=p->next; b．s->next=p->next; p->next=s;
c．p->next=s; p->next=s->next; d．p->next=s->next; p->next=s;
11． 设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。
a．1，2，4，3 b．2，1，3，4 c．1，4，3，2 d．4，3，1，2，12． 下列四个序列中，哪一个是堆（ ）
a．75,65,30,15,25,45,20,10 b．75,65,45,10,30,25,20,15
c．75,45,65,30,15,25,20,10 d．75,45,65,10,25,30,20,15
13． 在下述结论中，正确的是（ ）
只有一个结点的二叉树的度为0;
二叉树的度为2；
二叉树的左右子树可任意交换；
深度为k的完全二叉树结点个数小于或等于深度相同的满二叉树。
abcd．①④
14． 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
a．9b．11 c．15 d．不确定
15． 设森林f中有三棵树，第一，第二，第三棵树的结点个数分别为m1，m2和m3。与森林f对应的二叉树根结点的右子树上的结点个数是（ ）
a．m1 b．m1+m2 c．m3 d．m2+m3
16． 在下面的程序段中，对x的赋值语句的频度为（ ）
for i:=1 to n do
for j:=1 to n do
x:=x+1;
a． o(2n) b．o(n) c．o(n2) d．o(log2n)
17． 一个n个顶点的连通无向图，其边的个数至少为（ ）
a．n-1 b．n c．n+1 d．nlogn；
18． 二叉树的第i层上最多含有结点数为（ ）
a．2ib． 2i-1-1 c． 2i-1 d．2i -1
19． 下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。
a．选择b．冒泡 c．归并 d．堆。
20． 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（ ）方法是散列文件的关键。
a．散列函数b．除余法中的质数
c．冲突处理d．散列函数和冲突处理。
二、填空题。
21． 具有256个结点的完全二叉树的深度为___
22． 深度为h的完全二叉树上至少有多少个结点___
23． 有一个20行20列的对称矩阵a ，将其下三角矩阵以行序为主序压缩存储在数组b中，若b的首地址是1007，每个数组元素占4个存储单元，则a的第12行第10列（行、列从第一行第一列开始）元素的存储地址是：__
24． 数据结构是指数据及其相互之间的。
25． 队列的插入操作是在队列的___进行，删除操作是在队列的进行。
26． 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为在表尾插入元素的时间复杂度为。
27． 设w为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ，则二维数组w的数据元素共占用个字节。w中第6 行的元素和第4 列的元素共占用___个字节。若按行顺序存放二维数组w，其起始地址为100，则二维数组元素w[6，3]的起始地址为___
28． 一棵结点数为n的二叉树，其所有结点的度的总和是。
29． 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为个，其中个用于指向孩子个指针是空闲的。
30． 若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组a中，即编号为0的结点存储到a[0]中。其余类推，则a[ i ]元素的左孩子元素为___右孩子元素为双亲元素为。
31． **性表的散列存储中，处理冲突的常用方法有和两种。
32． 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用排序。
三、应用题。
33． 已知一棵二叉树的中序遍历序列和后序遍历序列分别为ebifjagdh和eijfbghda。
要求：（1）画出这棵二叉树；
2）写出这棵二叉树的前序遍历序列。
34． 设有正文mnopppopmmpopoppopnp，字符集为m，n，o，p，设计一套二进制编码，使得上述正文的编码最短，计算它的带权路径长度。
35． 试写出用克鲁斯卡尔（kruskal）算法构造下图的一棵最小支撑（或生成）树的过程，以及深度优先遍历的序列和广度优先遍历的序列。求结点7到结点3的最短路径。
36． 用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树。
37． 设散列函数为h(k)=k mod 11,解决冲突的方法为链接法，试将下列关键字集合依次插入到散列表中（画出散列表的示意图）。
38． 根据给定的关键字集合（20，15，40，35，45，25，50，30，10）顺序输入。
1)画出平衡二叉树；
2)画出重新调整好的堆树。
39． 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：
1) 归并排序每归并一次书写一个次序。
2) 快速排序每划分一次书写一个次序。
3) 冒泡排序每划分一次书写一个次序。
四、编程题。
40． 已知带头结点的动态单链表l中的结点是按整数值递增排列，试写一算法将值为x的结点插入链表l中，使l仍然有序。单链表的描述如下：
typedef int datatype;
typedef struct node
linklist;
41． 试写出递归的二分查找（折半查找）算法。
数据结构练习
一 选择题 1 若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动 个数据元素。a 2.在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行b a.q next p s next p b.s next p q nex...
数据结构练习
第1章。1.从逻辑上可以把数据结构分为。a 动态结构 静态结构 b 顺序结构 链式结构。c.线性结构 非线性结构 d 初等结构 构造型结构。2.关于算法的描述，不正确的是。a.算法最终必须由计算机程序实现。b 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。c.健壮的算法不会因非法的输人数...
数据结构练习
1 数据结构中，与所使用的计算机无关的是。a.存储结构 b.物理结构 c.逻辑结构 d.物理和存储结构。2 在存储数据时，通常不仅要存储各数据元素的值，还要存储。a 数据的处理方法b 数据元素的类型。c 数据元素之间的关系 d 数据的存储方法。3 算法分析的目的。4 如果对线性表的操作只有两种，即删...