（ ）1. 数据的存贮结构是数据的逻辑结构的存贮映象。
）2. 用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系。
）3. 非线性结构中，至少存在一个元素不止一个直接前趋或不止一个直接后继。
）4. 树的最大特点是层次结构。
）5. 队列的特点是先进先出。
）6. 图的最小生成树是唯一的。
）7. 线性表是广义表的特殊形式。
）8. 后序序列和中序序列能唯一确定一棵二叉树。
）9. 散列表是一种链式存贮结构。
）10. 快速排序并非在任何情况下都比其它排序方法速度快。
二、填空题（每空2分，共20分）
1． 数据的存贮结构的四种形式为存贮、 存贮、 存贮和存贮。
2．所有插入和删除都在表的一端进行的线性表称为。
3．n个结点的完全二叉树，其深度h
4．对于顺序循环队列q[m]，下标从0到m-1，头尾指针分别为f和r，入队时，队尾指针循环加1可表示为r
5．散列法既是一种查找方法，又是一种方法。
6．n个顶点的有向完全图具有条弧。
7．n个元素的顺序查找的平均查找长度为。
1．若进栈序列为1，2，3，4，则不可能得到的出栈序列是（ ）
2．对于下列二叉树，其后序序列为（ ）
1）abdecfg （2）dbeafcg3）debfgca （4）gfcebda
3．对于下列aov网，不能出现的拓扑序列为（ ）
4．深度为k的完全二叉树所含叶结点的个数最多为。
1）2k （2） 2k-1 （3） k （4） 2k
5．衡量查找算法效率的主要标准是。
1） 元素个数2） 所需的存贮量
3） 平均查找长度4） 算法难易程度
1．将下列森林转化为二叉树。（3分）
2．对下图：
1）写出其邻接矩阵。（2分）
2）按kruskal算法求其最小生成树；并写出相应的边集数组。（4分）
3．请画出后序和中序序列相同的二叉树的所有形态。（3分）
4．散列函数为h（k）=k%7，散列表的地址从0到6，用线性探查法解决冲突，建立散列表ht。给定关键字序列。
要求：（1）构造散列表（只画出表，不写算法）；（5分）
2）求出平均查找长度。（2分）
5．用直接选择排序方法对下列关键字进行排序，请写出每一趟排序的结果。（6分）
struct node
elemtype data;
node *next;
void lkinsert (node *head, elemtype x)
node *s, *p;
ss->data=__
p=head->next;
while (p!=null) &p->data!=a )
if (p==null)
cout<<“不存在结点a”;
elsevoid qksort (int r[ ]int p, int q按递增序对r[p] ~r[q] 进行快速排序
int i=p, j=q;
r[ 0 ]=r [ir[0]作临时单元。
whilewhile (i if (i };
r[ ii++;j- -
if (j>p) qksort(r,p,j);
if (i }
）1. 数据的存贮结构独立于计算机。
）2. 线性表简称为“顺序表”。
）3. 对数据的任何运算都不能改变数据原有的结构特性。
）4. 从循环单链表的任一结点出发，可以找到表中所有结点。
）5. 栈是一种先进先出的线性表。
）6. 链表的主要缺点是不能随机访问。
）7. 二叉树是树的特殊形式。
）8. 图可以没有边，但不能没有顶点。
）9. 冒泡排序算法是稳定的排序。
）10. 散列法是一种对关键字进行比较的查找方法。
1．对数据所施加的运算可分为两类，即型和型。
2．将插入限定在表的一端，而删除限定在表的另一端进行的线性表称为 ； 允许插入的一端称为。
3．二叉树的叶结点数n0与二度结点数n2的关系是。
4．对于顺序循环队列q[m]，下标从0到m－1，头尾指针分别用f和r表示，则队空条件是。
5．n个顶点的无向完全图具有条边。
6．拓扑排序的操作对象是。
7．快速排序的最坏情况是初始序列为正序和反序，其时间复杂度为。
8．希尔排序是属于排序的改进方法。
1．栈和队列都是。
1）顺序存贮的线性结构2）限制存取点的线性结构。
3）链接存贮的线性结构4）限制存取点的非线性结构。
2．与线性表的链接存贮不相符合的特性是。
1）便于插、删运算2）存贮空间动态分配。
3）需要连续的存贮空间4）只能顺序查找。
3．设二叉树的根为第一层，则第i层上的结点数最多有 （
1）２i2） ２i +1 （3）２i4）２i -1
4．直接选择排序的时间复杂度为。
1）o（n） （2）o(n㏒2n) （3）o(n24）o(㏒2 n)
5．给定下列有向图，从顶点v1出发，其深度优先搜索序列为（ ）
1．画出下列二叉树所对应的森林。（3分）
2．对于下边有向图
1）画出其邻接表（4分）
2）写出三种不同的拓扑序列（3分。
3．请画出先序与中序序列相同的二叉树的所有形态。（3分）
4．给定关键字序列，散列函数为h[k]=k% 11散列表的地址从0到10，用外链法处理冲突，散列地址为d的同义词均挂在以ht[d]为头指针的单链表中。
1）请画出其散列表（不写算法）；（5分）
2）求出成功的平均查找长度。（2分）
5．对下列关键字序列进行快速排序，请写出第一趟排序结果，并标识出在第一趟排序过程中数据交换的情况。（5分）
第一趟排序结果：
1． 直接插入排序
void insertsort(int r[ ]
/ 按递增序对r[1]~ r[ n ]进行直接插入排序。
int i, j;
for ( i=2; i { r [ 0 ]=r[ i设定r[0]为监视哨。
jwhile (r[ 0 ] r[ j ]
j- -
数据结构练习
一 选择题 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 广度优先遍历的含义是 从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且 先被访问的顶点的邻接点 先于 后被访问的顶点的邻接点 被访问，直至图中所有已被访问的顶点的邻接点都被访问到是下图的广度优先遍历序列。a.1 ...