发布时间 : 星期三 文章数据结构（本）期末综合练习2016年6月更新完毕开始阅读66b30217f705cc175427094f
23．一棵具有16个结点的完全二叉树，共有（ ）层。(设根结点在第一层) A．7 B．5 C．6 D．4 24.字符串〝abcd321ABCD〞的子串是（ ）。 A. 〝21ABC〞 B.〝abcABCD〞 C. abcD D. 〝321a〞
25．如图2所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得 到的一种顶点序列为（ ）。
A．abecdfg B．acfebgd C．aebcfgd D．aedfcgb a b
e c g
d 图2
f
26.数组a经初始化char a[ ]=“English”; a[1]中存放的是（ ）。 A. 字符n B. 字符E C. 〝n〞 D. 〝E〞
27.字符串“DABcdabcd321ABC” 的子串是( )。 A. “cd32” B. “ABcD” C. “aBcd” D. “321a”
28．如图3所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得 到的一种顶点序列为（ ）。
A．abecdf B．acfebd C．aebcfd D．aedfcb
a
e c
d f
b
图3
第13页
29.如图4所示，若从顶点a出发，按广度优先搜索法进行遍历，则可 能得到的一种顶点序列为（ ）。
A．abcdfge B．abcdfeg C．acbfedg D．abcfgde
a
b
c
d f
g e
图4
30.下图5的拓扑序列是( )。
A．5 2 3 4 6 B．5 2 3 6 4 C．5 6 4 2 3 D. 2 3 4 5 6
2 3 4
56
图5
31 .设有一个长度为18的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作 为新表的第5个元素），则移动元素个数为（ ）。 A．15 B．14 C. 5 D．6
32．设有一个长度为25的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数 为（ ）。
A．10 B．17 C．15 D．16
33．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存 储到一维数组B中（数组下标从1开始），则矩阵中元素a10,8在一维数组B中的下标 是（ ）。
A．62, B．63 C．51 D．53 34．在一个尾指针为rear的不带头结点的单循环链表中,插入一个s所指的结点,并作为第 一个结点，可执行s?next=rear?next ;和（ ）。 A． rear?next= s?next; B． rear =s?next;
C． rear=s;
D． rear?next=s;
35．在一棵二叉树中，若编号为15的结点是其双亲结点的右孩子，则双亲结点的顺序编号
为（ ）。
第14页
A．30 B．8 C．31 D．7
二、填空题
1. 对稀疏矩阵进行压缩存储,可采用三元组表，一个有10行的稀疏矩阵A共有97个 零元素，其相应的三元组表共有3个元素。该矩阵A有 列。
2. 栈的特点之一是：元素进、出栈的次序是:先进_______。
3．在单向链表中，q指向p所指结点的直接后继结点 ，要删除q所指结点，可以用 操作______= q->next; 。
4．对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息 是____ ___。
5. 对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行下 标、列下标和____ ___三项信息。
6．在对10个记录的序列(9，35,19, 77 ,2, 10 ,53, 45,27,68)进行直接插入排序时，当把第 6个记录10 插入到有序表时，为寻找插入位置，元素间需比较_________次。 （按升序排序）
7. 队列的操作特点是后进________。
8. 字符串a1=〝beijing〞, a2 =〝bef〞 , a3= 〝beifang〞, a4=“befi〞最小的 是 ________。
9．n个元素进行冒泡法排序，通常需要进行____ ____趟冒泡。
10．10个元素进行冒泡法排序，,其中第5趟冒泡共需要进行____ ____次元素间的比较。 11． 中序遍历二叉排序树可得到一个________的序列。 12．________遍历一棵二叉排序树可得到一个有序序列。
13. 广义表( c , a , (a ,b) , d , e ,( (i ,j ) ,k ) )的长度是________ 。 14. 广义表( c , (a ,b,c) , ( d , e ,f ) , ( (i ,j ) ,k ) )的长度是________ .
15. 广义表的( c , a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是________ 。 16. 广义表的( c , (b,a ,b) , f , e ,( (i ,j ) ,k ) )深度是________ .
17. 循环队列在规定少用一个存储空间的情况下，队空的判定条件为________。
18. 序列4 , 2 , 5 , 3 ,8, 6,采用冒泡排序算法(升序),经一趟冒泡后, 结果序列是 ________。 19.c语言中,字符串“E”存储时占 个字节 。
20. 待排序的序列为8,3,4,1,2,5,9, 采用直接选择排序算法,当进行了两趟选择后,结果序列 为________。
21．一棵二叉树中有n个非叶结点，每一个非叶结点的度数都为2，则该树共有_______ 个叶结点。
22. 线性表用________方式存储可以随机访问 。 23．在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65 插 入到有序表时，为寻找插入位置需比较_________次。
24. 顺序表,,6，5，1, 2, 4, 3, 8，7经过一趟(1,1)归并后的结果序列为________。
25. 对一组记录（5，8，9，2，12，7，56，44，39）进行直接插入排序(由小到大排序) ，当把第6个记录7插入有序表，为寻找插入位置需比较________次。
26．设有一棵深度为6的完全二叉树，第6层上有3个结点，该树共有_______个结点。（根所在结点为第1层）
27．一棵有16个叶结点的哈夫曼树，则该树共有_______个结点。
28.20个元素进行冒泡法排序，通常第6趟冒泡要进行__ ____次元素间的比较。
29．对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A共有38个
第15页
零元素，其相应的三元组表共有_______个元素。 while( *p!=‘\\0’){ n++; p++;} 结果中，n的值是_______。 三、综合题
1．设查找表为(1,10,11,14,23,27,29,55,68) ,元素的下标依次为1,2,3,??，9。 （1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示）。 （2）说明成功查找到元素14,需要依次经过与哪些元素的比较？共几次比较？ （3）求在等概率条件下，成功查找的平均比较次数？ .
2．设查找表为
序号 1 2 3 4 5 6 7 8 9 10 11 序列 8 16 22 23 41 59 69 81 89 90 121
（1）画出对上述查找表进行折半查找所对应的判定树。 （2）说明成功查找到元素90需要经过多少次比较？
（3）说明不成功查找元素82，依次与哪些元素进行了比较，需要经过多少次比较？
3．
(1) 以3，4，5，8，9，作为叶结点的权，构造一棵哈夫曼树。
(2) 给出相应权重值叶结点的哈夫曼编码。
(3) n个叶结点的哈夫曼树，总共有多少个结点？ 4.
(1) 一组记录的关键字序列为（36，69，46，28，30，35），给出利用堆排序（堆顶 元素是最小元素）的方法建立的初始堆（要求以完全二叉树描述 ）。
(2) 对关键字序列(36,69,46,28,30,74)采用快速排序，给出以第一个关键字为分割 元素，经过一次划分后的结果。
(3) 设有数据集合{30,73,101,4,8,9,2,81}，依次取集合中各数据构造一棵二叉排序树。
四、程序填空题（每空2分，共16分）
1．以下是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、 右指针域分别为left和right，数据域data为字符型，BT指向根结点）。 void Inorder (struct BTreeNode *BT) {
if(BT!=NULL){ （1） ; （2） ; Inorder(BT->right);} }
a b c d e f 利用上述程序对右图进行遍历，结果是 （3） ; 图6
2．以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格
第16页