发布时间 : 星期五 文章数据结构（本）期末综合练习（2014年12月）更新完毕开始阅读326a3983be1e650e53ea992e
Squeue *sq;
sq为指向顺序队列的指针变量，要进行元素的出队操作，并把元素赋给边量x, 按教科书约定,可用语句x=sq->data[sq->front];和________ 。
11.数据结构中, ________可以由一个或多个数据项组成。 12. 设顺序队列的类型为typedef struct
{ ElemType data[MaxSise]; int front,rear;
}Squeue;
Squeue *sq;
sq为指向顺序队列的指针变量，要进行新元素x的入队操作，按教课书约定,可用语句 sq->data[sq->rear]=x;和________。
13．循环队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize,采用少
用一个元素的模式),判断循环队列为满的条件为________为真 。
14. 序列14,12,15,13,18,16,采用冒泡排序算法,经一趟冒泡后,序列的结果是________。（由小到大排序）
15．排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素依次
进行比较，然后将其放入已排序序列的正确位置的方法是 。 16. 数据结构中, ________ 之间的抽象关系称为逻辑结构。 17．对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A共有34个零元 素，其相应的三元组表共有_______个元素。
18. 循环队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize,),判断循环
队列为空的条件为________为真。
19．在双向链表中，要删除p所指的结点，可以先用语句（p->prior）->next=p->next；然
后再用语句（p->next）->prior= ________。
20. 排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行
比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是 。 21.在双向链表中，每个结点有两个指针域，一个指向结点的直接后继 ，另一个指向_________。
22. 对稀疏矩阵进行压缩存储,可采用三元组表,矩阵元素a3,4 对应的三元组为_______ 。 23.把数据存储到计算机中,并具体体现数据之间的逻辑结构称为________结构。
24．在双向链表中，要删除p所指的结点，其中所用的一条语句（p->next）->prior=p->prior; 的功能是：使P所指结点的直接后继的左指针指向______ __。 三、 综合题
1.设数据集合a={1,12,5,8,3,10,7,13,9}
（1）依次取a中各数据，构造一棵二叉排序树。 （2）说明如何依据此二叉树得到a的有序序列。
（3）对该二叉树进行查找，成功查找到7要进行多少次元素间的比较？ （4）给出对该二叉树后序遍历的序列。
2.设数据集合a={62,74,30,15,56,48}
（1）依次取a中各数据，构造一棵二叉排序树。
（2）为了成功查找到48需要进行多少次元素间的比较? （3）给出对该二叉树后序遍历的序列。
3．设有序表为(2, 5, 11, 12, 30, 48, 58, 70, 78, 79, 90) ,元素的序号依次为 1,2,3,??，11.
（1）画出对上述查找表进行折半查找所对应的判定树（树中结点用序号表示） （2）说明成功查找到元素2需要经过多少次比较？
(3) 说明不成功查找元素75需要经过多少次比较？ (4) 给出中序遍历该折半查找判定树的序列
4．设有序表为（3，9，15，26，38，41，53，74，81，96，97，99），元素的 序号依 次为1,2,??,12。
（1）画出对上述有序表进行折半查找所对应的判定树（树结点用序号表示）。
（2）设查找5号元素(38)，需要进行多少次元素间的比较才能确定不能查到, 依次和 哪些元素进行了比较？（要求写出具体元素）。 （3）给出后序遍历该二叉树的序列。 (4) 给出中序遍历该二叉树的序列。
四、程序填空题
1. 设有一个不带头结点的单向链表，头指针为head, p 、prep 是指向结点类型的指针，
该链表在输入信息时不慎把相邻两个结点的信息重复输入,以下程序段是在该单向链表中查找这相邻两个结点,，把该结点的数据域data打印出来，并把其中之一从链表中删除，填写程序中的空格。
prep=head; p=prep->next;
while(p - > data!=prep- >data) { prep=p;
__(1)___ }
printf(“min=%d”, __(2)___); prep->next= __(3)___
2.学生信息存放在结构数组中，每个数组元素存放一个学生的信息，下标从0到n-1。
数组元素按学号num由小到大有序排列，以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字num等于k的记录，查找成功返回该记录的下标(数组元素的下标)。失败时返回-1，完成程序中的空格。
typedef struct
{
char sex; int num; …… }NODE;
int Binary_Search(NODE a[],int n, int k) {
int low,mid,high; low=0; high=n-1;
while(___(1)_____) {
mid=(low+high)/2; if(a[mid].num = =k)
return __(2)______; else if(___(3)_____) low=mid+1; else __(4)______; }
return -1 ; }
3 . 以下程序是折半插入排序的算法(按记录中关键字key排序)
设待排序的记录序列存放在a*1+,…a*n+中，以a[0]作为辅助工作单元，以下程序是要把a[i] 插入到已经有序的序列a*1+,…a*i-1]中。 void binsort (NODE a[ ],int n)
{ int x,i,j,s,k,m;
for （i=2；i<=__(1)___ ; i++） { a[0]=a[i]; x= a[i].key; s=1; j=i-1; while (s<=j) { m=__(2)___ if( x for ( k=i-1;k>=j+1;k- -) __(5)___=a[k]; a[j+1]=a[0]; } } 4．以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指针p（查找成功p指向查找到的树结点，不成功，则p指向为NULL），完成程序中的空格。 struct bnode { int key; struct bnode *left; struct bnode *right; } ; typedef struct bnode Bnode Bnode *BSearch(Bnode *bt, int k) /* bt用于接收二叉排序树 的根结点的指针，k用以 接收要查找的关键字*/