46 46 79 56 79 84 38 40 84 38 40 5684 84 79 46 79 56 38 40 56 38 40 46 5．（1）利用筛选法，把序列{37，77，62，97，11，27，52，47}建成堆（小根堆），画出相应的完全二叉树
37 11 77 62 37 27 97 11 27 52 47 77 62 52 47 97
初始树 堆
（2）写出对上述堆所对应的二叉树进行前序遍历得到的序列 答：11，37，47，97，77，27，62，52 6．设查找表为(50,60,75,85,96,98,105,110,120,130)
(1) 说出进行折半查找成功查找到元素120需要进行多少次元素间的比较？ 3次
(2) 为了折半查找元素95，经过多少次元素间的比较才能确定不能查到？
4次
3）画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点) 96 60 11 50 75 98 12
85 105 1311
（
四、程序填空题
1．以下函数为直接选择排序算法，对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<= __ n-1___;i++) { } }
2．以下是用尾插法建立带头结点且有n个结点的单向链表的程序，结点中的数据域从前向后依次为1,2,3,……,n，完成程序中空格部分。
NODE *create(n) {NODE *head , *p, *q; int i;
p=(NODE*)malloc(sizeof(NODE));
head= p ; q=p ;p?next=NULL; /*建立头结点*/ for(i=1; i<=n; i++)
{ p= (NODE*)malloc(sizeof(NODE)) ; p?data=i; p?next=NULL; q?next= p ; q=p ; }
return(head); }
3．以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。
void Inorder (struct BTreeNode *BT) { if(BT!=NULL){
Inorder(BT->left) ; printf(“%c”,BT->data) ; Inorder(BT->right) ; } }
12
k=i; for(j=i+1;j<= ___ n ___;j++) { }
temp=a[i]; __ a[i]=a[k]___; ___ a[k]=temp _;
if(a[j].key
期末综合练习三
一、单项选择题
1．深度为5的完全二叉树共有20个结点，则第5层上有（ C ）个结点(根所在结点为第一层)。
A．3 B．8 C．5 D．6
2．在C语言中，顺序存储长度为3的字符串，需要占用（ A ）个字节。 A．4 B．3 C．6 D．12
3．已知一个图的边数为m，则该图的所有顶点的度数之和为（ A ）。
A．2m B．m C．2m+1 D．m/2 4．串函数StrCat（a,b）的功能是进行串（ D ）。
A．比较 B．复制 C．赋值 D．连接 5．数据结构中，与所使用的计算机无关的是数据的（ D ）结构。 A．物理 B．存储 C．逻辑与物理 D．逻辑
6．一棵有n个结点采用链式存储的二叉树中，共有（ A ）个指针域为空。 A．n+1 B．n C．n-1 D．n-2
7．链表所具备的特点是（ C ）。
A．可以随机访问任一结点 B．占用连续的存储空间
C．插入删除不需要移动元素结点 D．可以通过下标对链表进行直接访问 8．设一棵哈夫曼树共有n个非叶结点，则该树有（ B ）个叶结点。 A．n B．n+1 C．n-1 D．2n 9．线性表只要以（ C ）方式存储就能进行折半查找。
A．链接 B．顺序 C．关键字有序的顺序 D．二叉树
10．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（ A ）。 A．x=top->data; top=top?next; B．x=top->data;
C．top=top->next; x=top->data; D．top=top->next; x=data; 11．散列查找的原理是（ A ）。
A．在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系 B．按待查记录的关键字有序的顺序方式存储 C．按关键字值的比较进行查找 D．基于二分查找的方法
12．一棵完全二叉树共有5层，且第5层上有六个结点，该树共有（ C ）个结点。 A．30 B．20 C．21 D．23
13．对n个元素进行冒泡排序若某趟冒泡中只进行了（ C ）次元素间的交换，则表明序列已经排好序。 A．1 B．2 C．0 D．n-1
14．在一个无向图中，所有顶点的度数之和等于边数的（ D ）倍。 A．3 B．2.5 C．1.5 D．2
15．排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到全部排好
序为止，该排序算法是( A )。
A．直接插入排序 B．快速排序
C．冒泡排序 D．选择排序 16．已知如图1所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ A ）。 A．V1V2V4V8V5V3V6V7 B．V1V2V4V5V8V3V6V7
C．V1V2V4V8V3V5V6V7 D．V1V3V6V7V2V4V5V8
13
V1 V2 V3 V4 V5 V6 V7 V8 图1
17．在对一组元素（64，48，106，33，25，82，70，55，93）进行直接插入排序时，当进行到要把第7个元素70插入到已经排好序
的子表时，为找到插入位置，需进行（ C ）次元素间的比较（指由小到大排序）。 A．6 B．2 C．3 D．4
18．已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ B ）。 A．abcedf B．abcefd C．aebcfd D．acfdeb
a b e c d 图2
f 19．采用顺序查找法对长度为n的线性表进行查找（不采用表尾设监视哨的方法），最坏的情况下要进行（ B ）次元素间的比较。 A．n+2 B．n C．n-1 D．n/2
20．对二叉排序树进行（ C ）遍历，可以使遍历所得到的序列是有序序列。
21．如图3，若从顶点a出发按广度优先搜索法进行遍历，则可能得到的顶点序列为（ B ）。 A．acebdgf
B．abecdgf C．acfedgb D．abecfdg
图3
22．在有序表{2，4，7，14，34，43，47，64，75，80，90，97，120}中，用折半查找法查找值80时，经（ B ）次比较后查找成功。
A．4 B．2 C．3 D．5
14
A．按层次 B．后序 C．中序 D．前序
a b e c d g f 23．元素2，4，6，8按顺序依次进栈，则该栈的不可能输出序列是（ D ）（进栈出栈可以交替进行）。 A．8，6，4，2 B．2，4，6，8
C．4，2，8，6 D．8，6，2，4
24．有一个长度为9的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ B ）。 A．25/10 B．25/9 C．20/9 D．17/9
25．排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（ C ）排序。 A．归并 B．插入 C．选择 D．快速
26．排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（ C ）。
A．冒泡 B．直接插入 C．折半插入 D．选择排序
27．一棵哈夫曼树总共有23个结点，该树共有（ D ）个叶结点（终端结点）
A．10 B．13 C．11 D．12
28．一组记录的关键字序列为（46，79，56，38，40，84），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ B ）。 A．40，38，46，79，56，84 B．40，38，46，56，79，84
C．40，38，46，84，56，79 D．38，40，46，56，79，84 29．队列的插入操作在（ B ）进行。
A．队头 B．队尾 C．队头或队尾 D．在任意指定位置
二、填空题（每小题2分，共24分）
1．一棵二叉树没有单分支结点，有6个叶结点，则该树总共有____11____个结点。
2．在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是_值域__、 左指针 、 右指针。
3．设一棵完全二叉树，其最高层上最右边的叶结点的编号为奇数，该叶节点的双亲结点的编号为10，该完全二叉树一共有___21___个结点。
4．一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为____2i _、___2i+1____。 5．按照二叉树的递归定义，对二叉树遍历的常用算法有__先序_ 、___中序 _、 __后序_三种。 6．串的两种最基本的存储方式是__顺序存储_和 __链式存储___。 7．数据结构中的数据元素存在一对多的关系称为___树形_____结构。
8．一棵有2n-1个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有___N____个叶结点。 9．把数据存储到计算机中,并具体体现数据之间的逻辑结构称为___物理（存储）_____结构。 10．对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有__ n+1______个指针域为空。 11．结构中的数据元素存在一对一的关系称为__线性__结构。 12．__中序______遍历二叉排序树可得到一个有序序列。 13．如图4所示的二叉树，其后序遍历序列为 gdbeihfca 。
a b c d e f g h i 15