数据结构（本）期末综合练习 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.设顺序存储的线性表长度为，对于插入操作，设插入位置是等概率的，则插入一个 元素平均移动元素的次数为()。 A.n/2 B.n C.n-1 D.n-i+1 7.设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第1 个元素)，则移动元素个数为()。 A.n-i+l B.n-i C.n-i-1 D.i 8.一个栈的进栈序列是5,6,7,8，则栈的不可能的出栈序列是()（进出栈操 作可以交替进行) A.5,8,6,7 B.7,6,8,5
1 数据结构（本）期末综合练习 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”,以下语句中正确的是()。 A.char a[10]=“Hello”: B.char a[10]:a=“Hello”: C.char a[10]='Hello'; D.char a[10]={H',’e',’1’,’1',’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的第一个元素为a.,数组b的下标从1开始），则数组元素 b[13]对应A的矩阵元素是( 。 A.a5.3 B.a6.4 C.a1.2 D.a6.8 15.设有一个15阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序 存储到一维数组B中（数组下标从1开始），则矩阵中元素a.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 2
2 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”，以下语句中正确的是（ ）。 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 图1 24.对长度为的线性表进行顺序查找，在等概率情况下，平均查找长度为( A.n B.(n+1)/2 C.2n D.n-1 3
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 图 1 24．对长度为 n 的线性表进行顺序查找，在等概率情况下，平均查找长度为（ ）。 A．n B．（n+1）/2 C．2n D．n-1 b d f e c a
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.acfgedb B.aedcbgf C.acfebdg D.aecbdgf 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.在任意指定位置 得分 评卷人 二、填空题
4 a b e c d g f 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 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保存出栈结点的值， 栈结点的指针域为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，则该树共有 个结点。 5
5 1．把数据存储到计算机中,并具体体现数据之间的逻辑结构称为________结构。 2．设有一个不带头结点的单向循环链表，结点的指针域为 next，指针 p 指向尾结点， 现要使 p 指向第一个结点，可用语句_______ _。 3．结构中的数据元素存在一对一的关系称为________结构。 4．要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循 环链表，若结点的指针域为 next，头指针为 head，尾指针为 p，，则可执行 head=head-> next; ______ __。 5．在双向链表中，每个结点有两个指针域，一个指向_____ ___，另一个指向 ________ _。 6．设有一个非空的链栈，栈顶指针为 hs，要进行出栈操作，用 x 保存出栈结点的值， 栈结点的指针域为 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，则该树共有_______ 个结点
I6.双向循环链表中，p指向表中某结点，则通过p可以访问到p所指结点的直接后继结 点和直接前驱结点，这种说法是 的（回答正确或不正确）。 17.一棵有14个结点的完全二叉树，则它的最高层上有 个结点。 18.栈和队列的操作特点分别是 和一。 19.如图2所示的二叉树，其先序遍历序列为 6 e 图2 20.折半查找只适用于 存储的有序表。 21.哈希函数是记录关键字值与该记录 之间所构造的对应关系。 22.深度为k的二叉树最多有」 结点。 23.二叉树排序中任一棵子树都是二叉排序树，这种说法是 的。（回答正确或不正 确) 24.串的两种最基本的存储方式是 和 得分 评卷人 三、综合题 6
6 16．双向循环链表中，p 指向表中某结点，则通过 p 可以访问到 p 所指结点的直接后继结 点和直接前驱结点，这种说法是________的（回答正确或不正确）。 17．一棵有 14 个结点的完全二叉树，则它的最高层上有_______个结点。 18．栈和队列的操作特点分别是________和 ________。 19．如图 2 所示的二叉树，其先序遍历序列为_____ ____。 图 2 20．折半查找只适用于 存储的有序表 。 21．哈希函数是记录关键字值与该记录______之间所构造的对应关系。 22．深度为 k 的二叉树最多有 结点。 23．二叉树排序中任一棵子树都是二叉排序树，这种说法是_______的。(回答正确或不正 确) 24．串的两种最基本的存储方式是_______ _和 __ ______。 三、综合题 得 分 评卷人 e f g i b a c h d
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)己知p,指向另一个新结点，把它插入到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，经过多少次元素 间的比较可知道查找失败？ >
7 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，经过多少次元素 间的比较可知道查找失败？
6: (1)对给定数列{7,16,4,8,20,9,6,18,5}，依次取数列中的数据，构造一棵二叉排序树。 (2)对一个给定的查找值，简述针对二叉排序树进行查找的算法步骤，在上述二叉树中查找 元素20共要进行多少次元素的比较？ 6 (1)设有查找表{5,14,2,6,18,7,4,16,3}，依次取表中数据，构造一棵二叉排序树。 (2)说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序 遍历的结果。 四、程序填空题 1.以下冒泡法程序对存放在a[1],a[2],…,a[n]中的序列进行排序，完成程序中 的空格部分，其中n是元素个数，要求按升序排列。 void bsort (NODE a[]int n) NODE temp; int i,j,flag; for(j=1;(1) ;jt+): {f1ag=0: for(i=1:(2) ;i++) if(a[i].key>a[i+1].key) {f1ag=1: temp=a[i]; (3) (4)
8 5． （1）对给定数列{7,16,4,8,20,9,6,18,5}，依次取数列中的数据，构造一棵二叉排序树。 (2 )对一个给定的查找值,简述针对二叉排序树进行查找的算法步骤，在上述二叉树中查找 元素 20 共要进行多少次元素的比较? 6． (1) 设有查找表{5,14,2,6,18,7,4,16,3},依次取表中数据，构造一棵二叉排序树。 （2）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序 遍历的结果。 四、程序填空题 1．以下冒泡法程序对存放在 a[1]，a[2]，……，a[n]中的序列进行排序，完成程序中 的空格部分，其中 n 是元素个数，要求按升序排列。 void bsort (NODE a[ ], int n) { NODE temp; int i,j,flag; for(j=1; （1） ;j++); {flag=0; for(i=1; （2） ;i++) if(a[i].key>a[i+1].key) {flag=1; temp=a[i]; （3） ; （4） ;
if(flag==0)break; } } 程序中flag的功能是(5) 2.以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、 右指针域分别为left和right,数据域data为字符型，BT指向根结点)。 void Preorder (struct BTreeNode *BT) if(BT!=NULL){ (1) (2) (3) } 3.设线性表为(6,10,16,4)，以下程序用说明结构变量的方法建立单向链表，并输 出链表中各结点中的数据。 #define NULL O 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; 9
9 } if(flag= =0)break; } } 程序中 flag 的功能是（5） 2．以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、 右指针域分别为 left 和 right，数据域 data 为字符型，BT 指向根结点）。 void Preorder (struct BTreeNode *BT) { if(BT!=NULL){ （1） ; （2） ; （3） ; } } 3．设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输 出链表中各结点中的数据。 #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;/知为工作指针，准备输出链表*/ do {printf(“%d小n”,(3) (4) }while((5) 4.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、 右指针域分别为left和right,数据域data为字符型，BT指向根结点)。 void Inorder (struct BTreeNode *BT) if(BT!=NULL){ 1) (2) (3) } 10
10 （2） ; /*以上结束建表过程*/ p=head; /*p 为工作指针，准备输出链表*/ do {printf(“%d\n”, （3） ); （4） ; }while( （5） ); } 4．以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、 右指针域分别为 left 和 right，数据域 data 为字符型，BT 指向根结点）。 void Inorder (struct BTreeNode *BT) { if(BT!=NULL){ （1） ; （2） ; （3） ; } }