发布时间 : 星期二 文章数据结构（本）期末综合练习（2014年12月）更新完毕开始阅读326a3983be1e650e53ea992e
把第10个记录8插入到有序表时，为寻找插入位置需比较_______次。 14.在对一组记录（50，34，92，19，11，68，56，41，79）进行直接插入排序(由小到大排 序)，当把第 8个记录41插入到有序表时，为寻找插入位置需比较________次。 15. 从数据结构的角度，城市间的交通线路的关系属于 ________结构。 16. 数据的________在计算机中的表示称为物理结构。
17. 循环队列用a[0],…,a[7]的一维数组存放队列元素,(采用少用一个元素的模式)，设front和rear分别为队头和队尾指针，且front和rear 的值分别为2和7,当前队列中的元素个数是________。
18. 循环队列用a[0],…,a[5]的一维数组存放队列元素,(采用少用一个元素的模式)，设front
和rear分别为队头和队尾指针，且front和rear 的值分别为3和0，当前队列中的元素个数是________。
19. 对n个整数用冒泡法进行排序，某趟冒泡中未进行元素间的 ，说明n个元素已排好序。
20．设已有m个元素有序，在未排好序的序列中挑选第m+1个元素，并且只经过一次元素的
交换就使第m+1个元素排序到位，该方法是 。
21. 对稀疏矩阵进行压缩存储,可采用三元组表,每个非零元素对应的三元组包括的三项信息
是行下标、列下标和____ ___ 。
22．对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A相应的三元组 表共有8个元素,则矩阵A共有_______个零元素。
23. 在双向链表中，要删除p所指的结点，其中所用的一条语句（p->prior）->next=p->next； 的功能是：使P所指结点的直接前驱的右指针指向________。
24．在双向链表中，要删除p所指的结点，可以先用语句（p->next）->prior=（p->prior）；然后再用语句（p->prior）->next= ________。
三、综合题
1.设数据集合a={52,20,46,38,5,64,40}
(1)依次取a中各数据，构造一棵二叉排序树。
(2)对该二叉树进行查找，成功查找到38,和46各要进行多少次元素间的比较？ (3)给出按后序遍历该二叉排序树的序列。
2.对给定的数列b={ 6,15,3,7,19,8,5,17,4} (1)依次取b中各数据，构造一棵二叉排序树 (2)给出按中序遍历该二叉排序树的序列 (3)给出按后序遍历二叉排序树的序列 (4)画出在二叉树中删除结点3后的树结构
3．（1）设根为第1层,对给定权值1，3 ，4，4，5, 6，构造深度为5的哈夫曼树。
提示: 构造中当出现被选的结点值有多个相等时,可尝试不同组合，以得到
要求的树的深度。
(2) 求树的带权路径长度。
(3) 给出对上述哈夫曼树中序遍历得到的的序列
(4) 一棵哈夫曼树有n个非叶结点，构造该树共有多少个权重值？简述理由？
4． (1) 以4，5, 6，13, 11, 12作为叶结点的权，构造一棵哈夫曼树。 (2) 给出相应权重值叶结点的哈夫曼编码。
(3) 一棵哈夫曼树有n个叶结点，该树共有多少个结点？简述理由？ (4) 给出对上述哈夫曼树中序遍历的序列。
四、程序填空题 1．职工体检表存放在结构数组中,要求以工资号num为关键字进行排序,以下函数用直接选择排序算法，对a[1],a[2],?a[n]中的记录进行排序，完成程序中的空格。
typedef struct
{ int age; int num; char sex; …… }NODE;
void selsort(NODE a[],int n) {
int i,j,k;
NODE temp;
for(i=1;i<= n-1;i++) { k=i;
for(j=i+1;j<= ___(1)_____;j++)
if(a[j].num <__(2)_____) k=j;
if(i!=k) { temp=a[i];
___(3)_____;
}
}
}
____(4)____;
2.职工信息存放在结构数组中，每个数组元素存放一个学生的信息，下标从1 到n，以a[0]作为辅助工作单元。现要以职工的工资号num为关键字进行排序， 采用折半插入排序的算法，以下程序是要把a[i] 插入到已经有序的序列a[1],…a[i-1]中,( i=2,3,4,…,n)。
typedef struct
{
char sex; int num; …… }NODE;
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].num; s=1; j=i-1; while (s<=j) { m=__(2)___ if( x for ( k=i-1;k>=j+1;k- -) a[k+1] = (5) ; a[j+1]=a[0]; } } 3.设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针 变量，p指向链表中结点a, （设链表中没有结点的数据域与结点a的数据域相同）,写出相关语句。 (1).使该单向链表成为单向循环链表 (2)插入结点s,使它成为a结点的直接前驱 q=p; x=p->data; while （__(1)___ ）q=q->next; q->next= __(2)__; q=p; p=p->next; while(p->data!=x) { q=p; __(3)___ } s->next=p; __(4)___ 4 .设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针变量，p指向链表中某结点a（设链表中没有结点的数据域与结点a的数据域相同）, 写出相关语句 (1)使该单向链表成为单向循环链表 (2) 删去a结点 q=p; x=p->data; while （q->next!=NULL）q=q->next; __(1)___ q=p; p=p->next; while(p->data!=x) { q=p; __(2)___ } __(3)___ 期末综合练习二答案 一、单项选择题 1．B 2．B 3．C 4．B 5．C 6．D 7．B 8．B 9．A 10．D 11．C 12．B 13．A 14．A 15．A 16．C 17．D 18．D 19．A 20．C 21．C 22．A 23．C 24．B 25．B 26．A 27．B 28．C 29．A 30．B 二、填空题 1. 物理（存储） 2. 线性 3. h=h->next; 4. s->next=h; 5.（ d , e , (i ,j ) ,k ） 6. a 7. ( a , c)