练习题
一、 填空题
1、__数据项_是数据的最小单位，_数据元素_____是讨论数
据结构时涉及的最小数据单位。
2、设一棵完全二叉树具有100个结点，则此完全二叉树有 49
个度为2的结点。
3、在用于表示有向图的邻接矩阵中，对第i列的元素进行
累加，可得到第i个顶点的__入____度。
4、已知一棵度为3的树有2个度为1的结点，3个度为2
的结点，4个度为3的结点，则该树中有_____12___ 个叶子的结点。根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。
5、有一个长度为20的有序表采用二分查找方法进行查找，
共有＿4＿＿＿＿＿个元素的查找长度为3。
6、对于双向链表，在两个结点之间插入一个新结点需要修
改的指针共_4___个。
删除一个结点需要修改的指针共______2___个。 7、已知广义表LS=(a,(b,c,d),e)，它的深度是______2____，
长度是______3____。
8、循环队列的引入是为了克服___假溢出_______。 9、表达式
a*(b+c)-d/f
的后缀表达式是
__abc+*df/-_________。
10、数据结构中评价算法的两个重要指标是 时间和空间复杂度 。
11、设r指向单链表的最后一个结点，要在最后一个结点之
后插入s所指的结点，需执行的三条语句是_r->next=s_____；r=s; r->next=null;。
12、设有一个空栈，栈顶指针为1000H(十六进制)，现有输
入序列为
1，2，3，4，5，经过
PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_23______，而栈顶指针值是___1012____H。设栈为顺序栈，每个元素占4个字节。
13、模式串P=‘abaabcac’的next函数值序列为_01122312_______。
14、任意连通图的连通分量只有一个，即是 其自
身 。 15、栈的特性是 后进先出 。
16、串的长度是 串中所包含的字符数 。
17、如果一个有向图中没有＿回路＿＿＿＿＿，则该图的全
部顶点可能排成一个拓扑序列。
18、在具有n个叶子结点的哈夫曼树中，分支结点总数为
n-1 。
19、在线性表的散列存储中，装填因子?又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则?等于____n/m____。
20、排序的主要目的是为了以后对已排序的数据元素进行 查找 。 21、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为___O(1)_____,在给定值为x的结点后插入一个新结点的时间复杂度为_O（n）_______。 22、线性表L=（a1,a2,?,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_表长的一半_______。
23、两个栈共享空间时栈满的条件_____top2=top1+1__。 24、深度为H 的完全二叉树至少有_ 2^（H-1） __个结点；至多有_ 2^H-1__个结点；H和结点总数N之间的关系是 H=log2N+1 __。
25、在有序表A[1?20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是_______1368 11 13 16 19___。
26、设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较_____7___次就可以断定数据元素X是否在查找表中。
27、根据初始关键字序列(17，25，3，39，12)建立的二叉排序树的高度为___3_________。
28、设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。
29、 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。
30、 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。
31、 设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶子结点。
32、 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。
33、typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree;
bitree *bstsearch(bitree *t, int k)
{
if (t==0 ) return(0);else while (t!=0)
if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________; }
34、 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。 void bubble(int r[n]) {
for(i=1;i<=n-1; i++) {
for(exchange=0,j=0; j<_____________;j++) if
(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}
if (exchange==0) return； } }
35、 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。
struct record{int key; int others;}; int bisearch(struct record r[ ], int k)
