发布时间 : 星期三 文章数据结构（本）期末综合练习2016年6月更新完毕开始阅读66b30217f705cc175427094f
（根所在结点为第1层） 12. 广义表的( c， a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是________。
13．中序遍历一棵________ 树可得到一个有序序列。
14. 对稀疏矩阵进行压缩存储,可采用三元组表，一个有10 行10列的稀疏矩阵A共有95个零元素，其相应的三元组表共有 个元素。
15.待排序的序列为9,4,5,1,2,6,10, 采用直接选择排序算法,当进行了两趟选择后,结果序 列为________ 。
16．在对一组记录(50, 49, 97, 22, 16, 73, 65, 47, 88)进行直接插入排序时，当把第7个记录65 插入到有序表时，为寻找插入位置需比较_________次。
17.广义表( (a ,b) , d , e ,( (i ,j ) ,k ) )的长度是________ 。
18. 一棵有5个叶结点的哈夫曼树,该树中总共有 _____ 个结点。 19.广义表的 ( c， a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是________ 。
20. 设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有_______个结点。 （ 根所在结点为第1层）。
21.线性表用________方式存储需要占用连续的存储空间 。
22．设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为_______。 23. 线性表用关键字________的顺序方式存储，可以用二分法排序 。 24. 有以下程序段
char a[ ]=“English”; char *p=a; int n=0;
三、综合题 1． （1）设有数据集合{40，29，7，73，101，4，55，2，81，92，39}，依次取集合中各 数据构造一棵二叉排序树。
(2) 在上述二叉排序树上进行查找，给出成功查找到元素92的查找路径,其中共经过了 多少次元素间的的比较。
(3)有一个长度为10的有序表，按折半查找对该表进行查找，给出在等概率情况下查 找成功的平均比较次数为。
2．有一个长度为11的有序表(1, 2, 11, 15, 24, 28, 30, 56, 69, 70, 80) , 元素的下标依次为 1,2,3,??,11，按折半查找对该表进行查找。
(1）画出对上述查找表进行折半查找所对应的判定树。
（2）说出成功查找到元素56,,需要依次经过与哪些元素的比较？ （3）说出不成功查找元素72,需要进行元素比较的次数？ 3.
(1) 以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树， (2) 给出相应权重值叶结点的哈夫曼编码。
(3) 一组记录的关键字序列为（47，80，57，39，41，46），利用堆排序的方法建立的 初始堆（堆顶元素是最小元素,以树的形式给出）。
4. (1)一组记录的关键字序列为（57，90，67，50，51，56），利用堆排序（堆顶元素是 最小元素）的方法建立初始堆（要求以完全二叉树描述 ）。
(2)对关键字序列(56,51,71,54,46,106)利用快速排序，以第一个关键字为分割元素，
第5页
给出经过一次划分后结果。
(3) 一组记录的关键字序列为（ 60,47，80，57，39，41，46,30），利用归并排序的 方法,分别给出(1,1) 归并、(2,2) 归并、(4,4) 归并的结果序列。
四、程序填空题
1.设线性表为（1,3,7,5），以下程序用说明结构变量的方法建立单向链表，并输出 链表中各结点中的数据。 struct node {int data;
struct node *next; };
typedef struct node NODE; #define NULL 0
void main( )
{NODE a,b,c,d,*head,*p; a.data=6; b.data=10; c.data=16;
d.data=4; /*d是尾结点*/ head= （1） ; a.next=&b; b.next=&c; c.next=&d;
（2） ; /*以上结束建表过程*/ p=head; /*p为工作指针，准备输出链表*/ do
{printf(“%d\\n”, （3） ); （4） ; }while(p!=NULL); }
画出按该程序建立的单向链表的示意图，说明程序运行结束后p的指向。（5）
2.设线性表为（16，20，26，24），以不带头结点的单向链表存储，链表头指针为head,以下程序的功能是输出链表中各结点中的数据域data。 struct node {int data;
struct node *next; };
typedef struct node NODE;
#define NULL 0 void main( )
{ NODE *head ,*p ;
p=head; /*p为工作指针*/ do
第6页
{printf(“%d\\n”, ___(1)_____); ___(2)_____ ; }while(___(3)_____); }
3．以下是先序遍历二叉树的递归算法程序，完成空格部分（树结构中左、 右指针域分 别为left和right，数据域data为字符型，BT指向根结点）。 void Inorder (struct BTreeNode *BT) {
if( （1） ){ （2） ; Inorder(BT->leftt);
Inorder(BT->right);} }
a b c d e 利用上述程序对右图进行遍历，结果是 （3） ; f 图5
4.以下函数为直接选择排序算法，对a[1],a[2],?a[n]中的记录进行直接选择排序，完成 程序中的空格
typedef struct { int key;
?? }NODE;
void selsort(NODE a[],int n) {
int i,j,k;
NODE temp;
for( i=1; i<= ___(1)_____; i++) { k=i; for( j=i+1;j<= (2)___ _ _; j++) if(a[j].key 第7页 练习一答案 一、单项选择题 1．D 2．D 3．D 4．D 5．C 6．A 7．B 8．D 9．C 10．C 11．C 12． B 13． B 14．B 15． D 16．B 17．C 18．A 19．A 20．A 21．B 22．C 23． B 24．B 25．C 26．C 27．A 28．A 29．B 30． C 31．C 32．A 33．A 34．B 35．C 二、填空题 1．8 2．图状 3．图状 4．n-j 5．12 6．二叉排序树 7．front= =rear 8．1，2，4，8，3，5，9 9．n-j 10．4 11．12 12．3 13．二叉排序树 14．5 15．1，2，5，9，4，6，10 16．3 17. 4 18．9 19. 3 20. 12 21．顺序 22．32 23．有序 24．7 40 三、综合题 1． (1) 29 73 7 39 55 101 4 81 2 第8页 92 图6