数据结构（本）期末综合练习
2009年6月
为了帮助同学们进行期末复习，特拟定以下三套期末综合练习题，望同学们逐一认真完成。
数据结构（本）期末综合练习一
一、单项选择题
1．针对线性表，在存储后如果最常用的操作是取第i个结点及其前驱，则采用（ ）存储方式最节省时间。
A．单链表 B．双链表 C．单循环链表 D．顺序表
2．线性表采用链式存储时，其地址（ ）。
A．一定是不连续的 B．必须是连续的
C．可以连续也可以不连续 D．部分地址必须是连续的 3．数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A．物理 B．存储 C．逻辑与物理 D．逻辑
4．带头结点的单向链表的头指针为head，该链表为空的判定条件是（ ）的值为真。
A．head = = NULL B．head->next= =head C．head->next= = NULL D．head = =head->next 5．以下特征中，（ ）不是算法的特性。
A．有穷性 B．确定性 C．可行性 D．有0个或多个输出
6．设顺序存储的线性表长度为n，对于插入操作，设插入位置是等概率的，则插入一个
元素平均移动元素的次数为（ ）。
A．n/2 B．n C．n-1 D．n-i+1
7．设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i
个元素），则移动元素个数为（ ）。
A．n-i+1 B．n-i C．n-i-1 D．i
8．一个栈的进栈序列是5，6，7，8，则栈的不可能的出栈序列是（ ）（进出栈操
作可以交替进行）
A．5，8，6，7 B．7，6，8，5 C．7，6，5，8 D．8，7，6，5
9．栈的插入删除操作在（ ）进行。
A．栈底 B．任意位置 C．指定位置 D．栈顶 10．栈和队列的相同点是（ ）。
A．都是后进先出 B．都是后进后出
C．逻辑结构与线性表不同
D．逻辑结构与线性表相同，都是操作规则受到限制的线性表 11．以下说法正确的是（ ）。
A．栈的特点是先进先出，队列的特点是先进后出 B．栈和队列的特点都是先进后出
C．栈的特点是先进后出，队列的特点是先进先出 D．栈和队列的特点都是先进先出 12．在C语言中，利用数组a存放字符串“Hello”，以下语句中正确的是（ ）。
1
A．char a[10]= “Hello”; B．char a[10]; a=“Hello”;
C．char a[10]= ?Hello?; D．char a[10]={?H?,?e?,?l?,?l?,?o?}; 13．元素2，4，6，8按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈
可以交替进行）。
A．8，6，4，2 B．2，4，6，8
C．4，2，8，6 D．8，6，2，4
14．设有一个15阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。（矩阵A的第一个元素为a1,1，数组b的下标从1开始），则数组元素b[13]对应A的矩阵元素是（ ）。 A．a5,3 B．a6,4 C．a7,2 D．a6,8
15．设有一个15阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序
存储到一维数组B中（数组下标从1开始），则矩阵中元素a7,6在一维数组B中的下标是（ ）。
A．42 B．13 C．27 D．32
16．一棵完全二叉树共有30个结点，则该树一共有（ ）层(根结点所在层为第一层)。
A．6 B．4 C．3 D．5 17．串函数StrCmp（“d”，“D”）的值为（ ）。
A．0 B．1 C．-1 D．3 18．以下说法正确的是（ ）。 A．连通图G的生成树中不一定包含G的所有顶点
B．连通图G的生成树中一定要包含G的所有边
C．连通图G的生成树一定是唯一的 D．连通图G一定存在生成树
19．在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ ）。 A．2i B．2i-1 C．2i+2 D．2i+1
20．对二叉排序树进行（ ）遍历，遍历所得到的序列是有序序列。
A．按层次 B．前序 C．中序 D．后序
21．设一棵有n个结点采用链式存储的二叉树，则该树共有（ ）个指针域为空。
A．2n B．2n+1 C．2n+2 D．n+1 22．以下排序算法中，在一趟排序过程中，除了其它相关操作外，只进行一次元素间的
交换的算法是（ ）。 A．直接选择 B．冒泡 C．直接插入 D．折半插入
23．已知如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能
得到的一种顶点序列为（ ）。
A．abcedf B．abcefd C．aebcfd D．acfdeb
b a e c d f
2
图1
24．对长度为n的线性表进行顺序查找，在等概率情况下，平均查找长度为（ ）。 A．n B．（n+1）/2 C．2n D．n-1
25．在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找
值86时，经（ ）次比较后查找成功。 A．6 B．3 C．8 D．4 26．如图若从顶点a出发按深度优先搜索法进行遍历，则可能得到的顶点序列为（ ）。 A．acfgedb
B．aedcbgf C．acfebdg D．aecbdgf
a b e c d g f
27．有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功
的平均比较次数为（ ）。 A．29/10 B．31/10 C．26/10 D．29/9 28．一棵哈夫曼树有12个叶子结点（终端结点），该树总共有（ ）个结点。 A．22 B．21 C．23 D．24 29．一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个关
键字为分割元素，经过一次划分后结果为（ ）。
A．31，29，37，47，70，85 B．29，31，37，47，70，85 C．31，29，37，70，47，85 D．31，29，37，85，47，70 30．队列的删除操作在（ ）进行。
A．队头 B．队尾 C．队头或队尾 D．在任意指定位置
得分 评卷人
二、填空题
1．把数据存储到计算机中,并具体体现数据之间的逻辑结构称为________结构。
2．设有一个不带头结点的单向循环链表，结点的指针域为next，指针p指向尾结点，现要使p指向第一个结点，可用语句_______ _。
3．结构中的数据元素存在一对一的关系称为________结构。 4．要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循环链表，若结点的指针域为next，头指针为head，尾指针为p，，则可执行head=head-> next; ______ __。
5．在双向链表中，每个结点有两个指针域，一个指向_____ ___，另一个指向________ _。
6．设有一个非空的链栈，栈顶指针为hs，要进行出栈操作，用x保存出栈结点的值，
3
栈结点的指针域为next，数据域为data，则可执行x= _____ ___；和
hs= ___ _____；
7．设有一个头指针为head的单向链表，p指向表中某一个结点，且有p->next= =NULL,通过操作________，就可使该单向链表构造成单向循环链表。
8．循环队列的最大存储空间为MaxSize，队头指针为f，队尾指针为r，当_____ ___
时表明队列已满。
9．从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h->data;和_______ _。(结点的指针域为next)
10．程序段 int count=0; char *s=” ABCD”; while(*s!=?\\0?){s++;count++;} 执行后count= ____ ____ 11．两个串相等的充分必要条件是_______ ___。 12．一棵二叉树总结点数为11，叶结点数为5，该树有________个双分支结点，________个单分支结点。
13．对二叉树的遍历可分为___ _____、 、 、 四种不同的遍历次序。
14．设一棵完全二叉树，其最高层上最右边的叶结点的编号为偶数，该叶节点的双亲结点的编号为9，该完全二叉树一共有________个结点。
15．一棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2，则该树共有_______个结点。
16．双向循环链表中，p指向表中某结点，则通过p可以访问到p所指结点的直接后继结点和直接前驱结点，这种说法是________的（回答正确或不正确）。 17．一棵有14个结点的完全二叉树，则它的最高层上有_______个结点。 18．栈和队列的操作特点分别是________和 ________。
19．如图2所示的二叉树，其先序遍历序列为_____ ____。
d b a c e f g h i
图2
20．折半查找只适用于 存储的有序表 。
21．哈希函数是记录关键字值与该记录______之间所构造的对应关系。 22．深度为k的二叉树最多有 结点。
23．二叉树排序中任一棵子树都是二叉排序树，这种说法是_______的。(回答正确或不正
4
确)
24．串的两种最基本的存储方式是_______ _和 __ ______。 得 分 评卷人
三、综合题
1．设一组记录的关键字序列为（49，83，59，41，43，47），采用堆排序算法完成以下操作：（要求小根堆，并画出中间过程） （1）以二叉树描述6个元素的初始堆
（2）以二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆
2．
设有一个不带头结点的单向链表，头指针为head，结点类型为NODE，每个结点包含一个数据域data和一个指针域next，该链表有两个结点，p指向第二个结点（尾结点），按以下要求写出相应语句（不要求完整程序，（1）、（2）、（3）、（4）是一个连续的过程）。
（1）新开辟一个结点，使指针s指向该结点，结点的数据成员data赋值为1
（2）把该结点插入链表的尾部，释放指针s的指向
（3）删除链表的第一个结点
（4）已知p1指向另一个新结点，把它插入到p所指结点和尾结点之间
3．设有序表为（13，19，25，36，48，51，63，84，91，116，135，200），元素的下标依次为1,2,??,12。
（1）说出有哪几个元素需要经过4次元素间的比较才能成功查到
（2）画出对上述有序表进行折半查找所对应的判定树（树结点用下标表示） （3）设查找元素5，需要进行多少次元素间的比较才能确定不能查到
4．
（1）设有序列{10，12，15，19，22，25，100，130，150，200}画出对上述序列进行折半查找的判定树（以序列中的元素作为树的结点）
（2）为了成功查找到100需要进行多少次元素间的比较？为了查找9，经过多少次元素间的比较可知道查找失败？
5．
（1）对给定数列{7,16,4,8,20,9,6,18,5}，依次取数列中的数据，构造一棵二叉排序树。 (2 )对一个给定的查找值,简述针对二叉排序树进行查找的算法步骤，在上述二叉树中查找元素20共要进行多少次元素的比较?
5