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