1252数据结构本电大期末试题及其答案

1、数据结构（本）期末综合练习题A.都是先进先出B.都是操作受限的线性结构C.都是先进后出D.兀素都可以随机进出1.栈和队列的共同特点是（C）。一、单选选择题2. 数据的存储结构包括数据元素的表示和（C）。A. 数据处理的方法B.数据元素的类型C.数据元素间的关系的表示D. 相关算法3. 对一个栈顶指针为top的链栈进行入栈操作，通过指针变量p生成入栈结点，则执行p=（struct node *）malloc（sizeof（struct node）;p-data=a;禾口（ C）。A. top-n ext=p; p=top; B. p_n ext=top; p=top;C. p_n ext=top

2、; top=p; D. top=top-n ext; p=top;4. 树状结构中数据元素的位置之间存在（B）的关系。A.每一个元素都有一个直接前驱和一个直接后继B. 一对多C. 一对一 D. 多对多5. 设头指针为head的非空的单向链表，指针p指向尾结点，则通过以下操作（D）可使其成为单向循环链表。A. head = p; B. p=head;C. p-n ext = NULL ; D. p- next=head;6. 设有一个长度为26的顺序表，要插入一个元素，并使它成为新表的第6个元素，需移动元素的个数为（D）。A. 22 B. 19 C. 20 D. 217. 一种逻辑结构（C）。A

3、.与存储该逻辑结构的计算机相关B.是指某一种数据元素的性质C.可以有不同的存储结构D.只能有唯一的存储结构8. 头指针为head的带头结点的单向循环链表，p所指向尾结点，要使该链表成为不带头结点的单向循环链表，可执行head=head- nex;和（A）。A. p-n ext=head; B. p= head-nextC. head-n ext=pD. head-n ext=p-next9. 把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（D）。A.给数据元素分配存储空间B.数据元素的存储C.逻辑结构D.存储结构10. 元素111，113，115，117按顺序依次进栈，则该栈的不可能

4、输出序列是（D）（进栈出栈可以交替进行）。A. 111，113，115，117B. 113，111，117，115C. 117，115，113，111D. 117，115，111，11311. 图状结构中数据元素的位置之间存在（B）的关系。A. 每一个元素都有一个且只有一个直接前驱和一个直接后继B. 多对多 C. 一对一 D. 一对一12. 以下说法正确的是（D）。A. 栈和队列的特点都是后进后出B.队列的特点是先进后出C.栈的特点是先进先出D.栈的特点是先进后出13. 一个单链表中，在p所指结点之后插入一个s所指的结点时，可执行：s-next=p-next;和（D）。A. s=p-n ext

5、;B. p=s-n ext;C. p-n ext=s-n ext;D. p-n ext=s;14. 设有一个20阶的对称矩阵 A （第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵元素 a6,2在一维数组B中的下标是（B）。A. 28 B. 17 C. 21 D. 2315. 元素12，14，16，18顺序依次进栈，则该栈的不可能输出序列是（C）。（进栈出栈可以交替进行）。A. 18，16，14，12B. 12，14，16，18C. 18，16，12，14D. 14，12，18，1616. 设有串 p1=ABADF, P2=A

6、BAFD, P3=ABADFA P4=ABAF,以下四个串中最大的是 （A）。 A. p2 B. p3 C. p4 D. p117. 设有一个30阶的对称矩阵 A （第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（A）。A. 38 B. 32 C. 18 D. 4118. 数组a经初始化 char a = “ English ” ；a7中存放的是（B）。A. h B.字符串的结束符C. 变量h D. 字符h19. 设有一个长度为32的顺序表，要删除第 8个元素需移动元素的个数为（B）。A.

7、 15 B.24 C. 22 D. 1420. 设主串为“ ABcCDABcdEFaBc，以下模式串能与主串成功匹配的是（B）。A. ABC B. Bcd C. Abc D. BCd21. 在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（C）。A. 2i-1 B. 2i C. 2i+1 D. 2i+222. 在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（D）。A. 2i+1 B. 2i-1 C. 2i+2 D. 2i23. 一棵具有16个结点的完全二叉树，共有（B）层。（设根结点在第一层）A. 6 B. 5 C. 4 D. 724. 如下图所示，若从顶点a

8、出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（A）。A. aecbdf B. aedfcb C. aebcfd D. abecdf25. 如下图所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种顶A. aebcfgd B. abecdfg C. aedfcgb D. acfebgd26. 线性表以（B）方式存储，能进行折半查找。A.顺序 B.关键字有序的顺序C. 二叉树 D. 链接27. 字符串“ DABcdabcd321ABC 的子串是（C）。A. “ 321a ” B. “aBcd” C. “ cd32” D. “ ABcD28. 一棵具有38个结点的完

9、全二叉树，最后一层有（B）个结点。A. 6 B. 7 C. 5 D. 829. 如下图所示，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（C）。A. acbfedg B. abcdfegC. abcdfge D. abcfgde30.卜图的拓扑序列是（）。A. 2 3 6 4 5 B. 5 6 2 3 4 C. 2 3 5 6 4 D. 5 2 3 4 631. 下面关于线性表的叙述错误的是（D）。A. 线性表采用链式存储便于插入和删除操作的实现B. 线性表采用链式存储不必占用一片连续的存储空间C. 线性表采用顺序存储必须占用一片连续的存储空间D. 线性表采用顺序存储便

10、于插入和删除操作的实现32. 设有头指针为head的不带头结点的非空的单向循环链表，指针p指向其尾结点，要删除第一个结点，则可利用下述语句head=head-next;和（D）。39. 设某链表中最常用的操作是在链表的尾部插入或删除元素，在已知尾指针的条件下，选 用下列（A存储方式最节省运算时间。A.双向链表 B. 单向链表 C. 单向循环链表 D.双向循环链表40. 图状结构中数据元素的位置之间存在（A）的关系。A.多对多B.每一个元素都有一个直接前驱和一个直接后继C. 一对多D.一对一41. 元素13，15，19，20顺序依次进栈，则该栈的不可能输出序列是（A）。（进栈出栈可以交替进行）A

11、. abcedfg B. abcfgde C. acbfedg D. abcdfge42. 元素20, 14, 16, 18按顺序依次进栈，则该栈的不可能输出序列是（A）。（进栈出栈可以交替进行）A. 18 , 16, 20, 14B. 20, 14, 16, 18C. 14 , 20, 18, 16D. 18, 16, 14, 2043. 设指针q指向单链表中结点 A,指针p指向单链表中结点 A的后继结点B,则在表中删除 结点B的操作为（A）。A. q-n ext=p-n ext； B. q-n ext=p；C. p_next=q_next； D. p_next； p=q；44. 设有一个1

12、2阶的对称矩阵 A （左上角第一个元素为 a1,1 ），采用压缩存储的方式， 将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素 a5,4在一维数组B中的下标是（C）。A. 12 B. 11 C. 14 D. 1345. 栈和队列的共同特点之一是（A）。A.只允许在端点处插入和删除元素B.都是先进先出C.没有共同点D.都是先进后出46. 设有一个长度为22的顺序表，要删除第 8个元素需移动元素的个数为（C）。A. 25 B. 15 C. 14 D. 2347. 用链接方式存储的队列，在进行插入运算时（C）。A.头、尾指针都需要修改B. 头、尾指针都不需要修改C.需修

13、改尾指针D.需修改头指针48. 在一棵二叉树中，若编号为5的结点存在右孩子，则右孩子的顺序编号为（D）。A. 12 B. 10 C. 9 D. 1149. 字符串 a仁AEIJING , a2=AEI , a3=AEFANG a4=AEFI中最大的是（D）。51. 设有一个 20阶的对称矩阵 A （第一个元素为a1,1 ），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a6,2在一维数组B中的下标是（C）。A. 18 B. 23 C. 17 D. 2152. 如下图所示，若从顶点 a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶 点序

14、列为（A）。53. 以下说法正确的是（A）。A. 二叉树中任意一个非叶结点的值都大于其左子树上所有结点的值，小于其右子树上所有 结点的值，则该树为二叉排序树。B. 若二叉树中左子树上所有结点的值均小于根结点的值，右子树上所有结点的值均大于根 结点的值。则该树为二叉排序树。C. 前序遍历二叉排序树可得到一个有序序列。D. 二叉树中任意一个结点的值均大于其左孩子的值，小于其右孩子的值。则该树为二叉排 序树。54. 字符串abcd321ABCD的子串是（B）。A. 321a B. 21ABC C. abcABCD D. abcD55. 二叉树的第k层的结点数最多为（B）。A. 2K-1 B. 2k-

15、1 C. 2K+1 D. 2k-156. 数组a经初始化 char a = “ English ” ;a1中存放的是（D）。A.字符 EB. n C. E D.字符 n57. 如下图所示，若从顶点6出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序A. 6 ， 2， 8， 7， 9， 3， 4C. 6，2，7，9，8，4，3B. 6D. 6，9，2，3，7，8，4，9，3，2，8，7，458.如下图所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种顶点序列为（A）。14.对稀疏矩阵进行压缩存储，可采用三元组表，一个有10行10列的稀疏矩阵 A共有9559.如下图所示，若从

16、顶点 a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序 列为（A）。A. abcdfge B. abcfegd C. abcfgde D. acbfedg60.下图的拓扑序列是(B)。A. 5 2 3 4 6 B. 5 2 3 6 4 C. 2 3 4 5 6 D. 5 6 4 2 3、填空题1.对稀疏矩阵进行压缩存储， 可米用三兀组表，一个有10行的稀疏矩阵 A共有97个零兀素，其相应的三兀组表共有 3个兀素。该矩阵 A有10列。2.结构中的数据兀素存在多对多的关系称为图状结构n ext = q-n ext;。4. n个元素进行冒泡法排序，第j趟冒泡要进行n-j次元素间的比较。5.

17、对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行下标、列下标和数组元素三项信息。6. 中序遍历二叉排序树可得到一个有序序列。7.队列的操作特点是后进后出。8.待排序的序列为8, 3, 4, 1 , 2, 5,9,米用直接选择排序算法，当进行了两趟选择后，结果序列为 124,835,9。9. n个元素进行冒泡法排序，通常需要进行n-1趟冒泡。10. 广义表（a，b），d，e（ i，j），k）的长度是 411. 中序遍历二叉排序树可得到一个有序 的序列。12.广义表的(c, a,( a, b), d, e,( i , j ), k）深度是 3。13.广义表(c, a,( a,

18、b), d, e,( i , j ), k)）的长度是 6。15.广义表的（c, a,（ a, b）, d, e,（ i , j ）, k）深度是 3。16.在对一组记录（50, 49, 97, 22, 16, 73, 65, 47, 88）进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较3次。个零元素，其相应的三元组表共有5个元素。19. c语言中，字符串“E”存储时占2个字节。20.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有 12个结点。（根所在结点为第1层）。17. 循环队列在规定少用一个存储空间的情况下，队空的判定条件为front=rear18

19、. 一棵有5个叶结点的哈夫曼树，该树中总共有_9个结点。21. 一棵二叉树中有 n个非叶结点，每一个非叶结点的度数都为2,则该树共有n+1 个叶结点。22. 设有一个长度为40的顺序表，要删除第 8个元素需移动元素的个数为32。23. 在对一组记录（55，39，97，22，16，73，65，47，88）进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较3 次。24. 有以下程序段：char a=“ Englishchar *p=a;int n=0;while（ *p!= 0 ） n+; p+;结果中，n的值是 7。25. 设：char a =AEIJING;该字符串在计

20、算机中存储时占_8个字节。26. 栈的特点之一是：元素进、出栈的次序是：先进后出 。27. 结构中的数据元素存在多对多的关系称为图状 结构。28. 对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息是 行下标，列下标，数组元素 。29. 对稀疏矩阵进行压缩存储，可采用三元组表，一个有8行的稀疏矩阵 A共有92个零元素，其相应的三元组表共有4个元素。该矩阵 A有12 列。30. 在对10个记录的序列（9，35，19, 77, 2，10，53, 45, 27，68）进行直接插入排序时，当把第6个记录10插入到有序表时，为寻找插入位置，元素间需比较4 次。（按升序排序）31.

21、 循环链队列中，设front和rear分别为队头和队尾指针，最大存储空间元素为 MaxSize,采用少用一个存储空间的模式，则判断循环链队列为空的条件是fron t=rear为真。32. 字符串 a1=beijing , a2 =bef , a3=beifang , a4=befi最小的是 a2 。33. n个元素进行冒泡法排序，第j趟冒泡要进行 n-j次元素间的比较。34. 10个元素进行冒泡法排序，其中第5趟冒泡共需要进行5次元素间的比较。35. 设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有 12 个结点。（根 所在结点为第1层）36. 中序遍历一棵二叉排序树可得到一个有序序

22、列37. 中序遍历一棵二叉排序树树可得到一个有序序列。38. 广义表（c,（ a, b, c）,（ d, e, f）,（ i , j）, k）的长度是 4。39. 待排序的序列为9, 4, 5, 1 , 2, 6, 10,采用直接选择排序算法，当进行了两趟选择后，结果序列为。40. 广义表的（c,（ b, a, b）, f, e,（ i , j）, k）深度是 。41. 广义表（a, b）, d, e,（ i , j ）, k）的长度是 _4。42.序列4, 2, 5, 3 , 8 , 6,采用冒泡排序算法（升序），经一趟冒泡后，结果序列是2,4,3,5,6,8。43.广义表的（c，a，（a,

23、 b）, d, e,（ i , j ）, k）深度是344.待排序的序列为8，3, 4, 1 , 2, 5, 9，采用直接选择排序算法，当进行了两趟选择后，结果序列为1,2,4,8,3,5,9。45.线性表用顺序方式存储需要占用连续的存储空间。46.线性表用顺序方式存储可以随机访问。47.线性表用关键字有序的顺序方式存储，可以用二分法排序。48顺序表 6, 5, 1, 2,4, 3, 8, 7经过一趟（1,1）归并后的结果序列为（5,6 ） ,（ 1,2 ）,（3,4 ）,（ 7,8 ）三、综合题80），兀素的下1.有一个长度为 11 的有序表（1, 2, 11, 15, 24, 28, 30

24、, 56,69, 70,标依次为：1, 2, 3, ,11,按折半查找对该表进行查找。（1 ）画出对上述查找表进行折半查找所对应的判定树。（2）说出成功查找到兀素56,需要依次经过与哪些兀素的比较？（3）说出不成功查找兀素72,需要进行兀素比较的次数？（2）28,69,30,56（3）4 次2. （ 1）以3, 4，5，8，9,作为叶结点的权，构造一棵哈夫曼树。（2）给出相应权重值叶结点的哈夫曼编码。（3）n个叶结点的哈夫曼树，总共有多少个结点？（1）答：（2）答：3:0004:0015:018:109:11（3）2n-13. （1） 一组记录的关键字序列为（57, 90 , 67, 50,

25、51, 56）,利用堆排序（堆顶元素是 最小元素）的方法建立初始堆（要求以完全二叉树描述）。（2）对关键字序列（56, 51, 71, 54, 46, 106）利用快速排序，以第一个关键字为分割元 素，给出经过一次划分后结果。（3）一组记录的关键字序列为（60, 47, 80, 57, 39, 41 , 46, 30）,利用归并排序的方 法，分别给出（1 , 1）归并、（2, 2）归并、（4, 4）归并的结果序列。J（1）答：（2）46,51,54,56,71,106（3）（ 47,60 ）（ 57,80 ）（ 39,41 ）（ 30,46 ）（47,57,60,80 ）（ 30,39,41,

26、46 ）（30,39,41,46,47,57,60,80）4. （ 1）设有数据集合40 , 29, 7, 73, 101, 4, 55, 2, 81, 92, 39，依次取集合中各数 据构造一棵二叉排序树。（2） 在上述二叉排序树上进行查找，给出成功查找到元素 92的查找路径，其中共经过了多 少次元素间的的比较。（3） 有一个长度为10的有序表，按折半查找对该表进行查找，给出在等概率情况下查找成 功的平均比较次数为。（1）(2) 40,73,101,81,92 。共 5 个元素比较。(3) 29/105. (1)以2, 3, 4, 7, 8, 9作为叶结点的权，构造一棵哈夫曼树。(2) 给出

27、相应权重值叶结点的哈夫曼编码。(3) 一组记录的关键字序列为(47, 80，57，39，41，46)，利用堆排序的方法建立的初 始堆(堆顶元素是最小元素，以树的形式给出)。(1)（2） 2 :00003:00014:0017:108 :119: 01(3)6. （1） 一组记录的关键字序列为（36, 69, 46, 28, 30, 35）,给出利用堆排序（堆顶元 素是最小元素）的方法建立的初始堆（要求以完全二叉树描述）。（2）对关键字序列（36, 69, 46, 28, 30 , 74）采用快速排序，给出以第一个关键字为分割兀素,经过一次划分后的结果。(3)设有数据集合30 , 73, 101

28、 ,4, 8, 9, 2, 81，依次取集合中各数据构造一棵二叉排序树。答：(1)28,30,35,69,36,46(2) 30,28,36,46,69,74（3）7. （ 1）已知某二叉树的后序遍历序列是debca，中序遍历序列是 dbeac,试画出该二叉树。（2）若上述二叉树的各个结点的字符分别代表不同的整数（其中没有相等的），并恰好使该树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系。（3）给出该树的前序遍历序列。（1）（2）dbean ext=s; s-n ext=p-n ext;这样做正确吗？若正确则回答正确，若不正确则说明应如何改写。答：（1） p1-next= head2

29、 ； p2-next= headl ；（2）不对，s-next= p-next； p-next=s ；10. （ 1 ）设根为第1层，对给定权值1，3，4，4，5，6，构造深度为5的哈夫曼树。提示：构造中当出现被选的结点值有多个相等时，可尝试不同组合，以得到要求的树的深度。（2 ）求树的带权路径长度。（3）用链接法存储上述哈夫曼树，结点中共有多少个指针域为空，说明理由？（4）给出对上述哈夫曼树中序遍历得到的的序列。（5）棵哈夫曼树有n个非叶结点，构造该树共有多少个权重值？简述理由?答：(1)(2) WPL=1*4+3*4+4*3+6*2+4*2+5*2=58(3) 有12个空指针域，因为共 1

30、1个结点，22个指针域，除根结点外，每个结点对应一个 指针域，共10个指 域非空，故有22-10=12个空指针域。(针对哈夫曼树还可有其它理由)(4) 1， 4， 3, 8， 4， 14， 6， 23, 4， 9， 5(5) n+1，因为叶结点比非叶结点多1。四、程序填空1. 以下是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点)。void In order(struct BTreeNode *BT)if(BT!=NULL)(1) Inorder(BT-left)；(2)printf(%c,BT-dat

31、a)；Ino rder(BT-right);利用上述程序对下图进行遍历，结果是(3) d b f e a c。2. 设线性表为(16，20，26，24)，以不带头结点的单向链表存储，链表头指针为head，以下程序的功能是输出链表中各结点中的数据域data。struct nodeint data;struct node *n ext;typedef struct node NODE;#defi ne NULL 0void mai n()NODE *head,*p;p=head;/*p为工作指针*/doprin tf(%dn,(1);(2);while(3); 答：(1) p-data(2) p=

32、p-next(3) p!=NULL3.以下冒泡法程序对存放在a1 , a2,an中的序列进行排序，完成程序中的空格部分，其中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(ai.keyai+1.key)flag=1;temp=:ai;(3);(4);if(flag=0)break;设有序列6, 4, 5, 8, 2, 1,给出由该程序经过两趟冒泡后的结果序列(5)(4) ai+1=temp(5) 4, 5, 2, 1, 6, 84. 以

33、下函数为直接选择排序算法，对a1 , a2,an中的记录进行直接选择排序,完成程序中的空格：typedef structint key;NODE;void selsort(NODE a ,int n)int i,j,k;(3) k=j(4) ai=ak(5) ak=temp5. 设线性表为(1, 3,7, 5)，以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。struct nodeint data;struct node *next;typedef struct n ode NODE;#defi ne NULL 0Void mai n()NODE a,b,c,d,*hea

34、d,*p;a. data=6;b. data=10;c. data=16;c.data=4;/*d 是尾结点 */head= ( 1);a. n ext=&b;b. n ext=&c;c. n ext=&d;(2)；/*以上结束建表过程*/p=head; /*p为工作指针，准备输出链表 */do6. 以下函数在a0到an-1中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格：typedef structint key;NODE;int Binary_Search(NODE a ,int n,int k) int low,mid,high;low

35、=0;high=n-1;while( ( 1)low=mid+1;else（ 4）;return -1;设数组元素：a0=2 ； a1=5 ； a2=3 ； a3=4 ； a4=9 ； a5=6 ； a6=1 ； a7=10 ;按 上述程序查找元素 5,能否成功查到，说明理由（5）。答：（1） low=high（2）mid（3）amid.keyright);(2) ;利用上述程序对下图进行遍历，结果是(3)。答：(1)Inorder(BT-left)(2) printf(%c,BT-data)(3) f,d,e,b,c,a8. 以下函数为链队列的入队操作，x为要入队的结点的数据域的值，fron

36、t、rear分别是链队列的队头、队尾指针struct nodeElemType data; struct node *n ext;struct node *fron t,*rear;void In Queue(ElemType x)struct node *p;答：(1) malloc(sizeof (struct no de)(2) rear-next=p(3) p9. 设有一个头指针为 head的不带头结点单向链表，p、q是指向链表中结点类型的指针变量， p指向链表中某结点 a (设链表中没有结点的数据域与结点a的数据域相同)，写出相关语句：(1)使该单向链表成为单向循环链表；(2)删去a

37、结点q=p;x=p_data;while(q-n ext!=NULL)q=q-n ext;(1) ;q=p;p=p-n ext;while(p-data!=x)q=p;（2）;（3）;答：（1） q-next=head（2）p=p-next（3）q_next=p-next模拟练习题（一）一、单项选择题（每小题2分，共30分）1单向链表所具备的特点是（C ）。A.可以随机访问任一结点B.占用连续的存储空间C.插入删除不需要移动元素D.可以通过某结点的指针域访问其前驱结点2、 设有一个长度为18的顺序表，要在第6个元素之前插入一个元素（也就是插入元素作为新表的第6个元素），则移动元素个数为（A ）

38、。A. 13 B. 5 C. 12 D. 63、 栈和队列的共同特点是（C ）。A.都是先进后出B.都是先进先出C.都是线性结构D.元素都可以随机进出4、元素1，3，5, 7按顺序依次入队列，按该队列的出队序列进栈，该栈的可能输出序列是（ B）（进栈出栈可以交替进行）。A. 5，1，3，7 B. 7 ，5，3，1 C. 7，5，1，3 D. 7，3，1，55、 在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则对该队列进行出队操作中并把结点的值保存在变量e中，其运算为e=f t data ;和（ C ）。A. f t next=f; B. r=rt next;C. f=f t nex

39、t;D. rtnext=r;6、 设有一个对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），B数组共有45个元素，则该矩阵是（B ）阶的对称矩阵。A.11B. 9 C. 15 D.107、 下列是 C语言中abcd321ABCD的子串的选项是（B ）。A. abcD B. 21ABC C. abcABCD D. 321a8、 字符串 a1=BEIJING，a2 =BEF，a3=BEFANG a4=BEFI最小的是（D ）。A. a1B. a3 C. a4D. a29、 一棵有20个结点采用链式存储的二叉树中，共有（D）个指针域为空。A. 18B.

40、 19 C. 20D. 21）个非叶结点。10、设一棵哈夫曼树共有 18个叶结点，则该树有（A. 16 B. 19C. 17 D.1811、如下图所示的一个图，若从顶点g出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ C ）。A. gaebcfd B. gabecdfC. gaedfcb D. gacfebd12、 线性表以（C ）方式存储，能进行折半查找。A.顺序 B.链接C.关键字有序的顺序D. 关键字有序的13、 有一个长度为8的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ D） |A. 22/8 B. 20/8 C. 23/8D. 21/81

41、4、排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（ C ）。A.归并排序B.选择排序C.折半插入排序D.直接插入排序15、排序方法屮，从未排序序列屮挑选兀素，并将其依次放入已排序序列（初始为空）的端的方法，称为（B）排序。A.快速 B.选择 C. 冒泡 D. 堆二、填空题（每小题 2分，共24分）16、 广义表（a , （a , b） , d, e, （i , j） , k）的长度是5。17、广义表的（c , a, （a , b）, d, e, （i , j） , k）深度是18、设顺序队列的类

42、型为typedef structElemType dataMaxSise;intfron t,rear;Squeue;Squeue *sq;sq为指向顺序队列的指针变量，要进行新兀素x的入队操作，按教课书约定，可用语句sq-datasq-rear=x;禾廿sq-rear+。19、 序列4, 2, 5, 3, 8, 6,采用冒泡排序算法， 经一趟冒泡后，序列的结果是 2,4,3,5,6,8 。（按由小到大顺序）20、在对一组记录（50，34，92，19，11，68，56, 41，79）进行直接插入排序（由小到大排序），当把第7个记录56插入到有序表时，为寻找插入位置需比较_3_次。21、 数据结

43、构中，数据元素可以由一个或多个数据项组成。22、循环队列中，设front和rear分别为队头和队尾指针，（最多兀素为MaxSize，采用少用一个兀素的模式），判断循环队列为满的条件为front= =(rear+1)% MaxSize为真。23、排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素依次 进行比较，然后将其放入已排序序列的正确位置的方法是直接插入排序。24、对稀疏矩阵进行压缩存储，可采用三兀组表，一个6行7列的稀疏矩阵 A共有34个零兀素，其相应的三兀组表共有8个兀素。25、 在双向链表中，要删除p所指的结点，可以先用语句（p-prior ）-next=p-ne

44、xt ;然 后再用语句（p_next）-prior= p-prior; 。26、 在双向链表中，每个结点有两个指针域，一个指向结点的直接后继，另一个指向结点 的直接前驱_。27、 把数据存储到计算机中，并具体体现数据之间的逻辑结构称为存储 结构。三、综合题（每小题 15分，共30分）28、设数据集合 a=1，12，5，8，3，10，7，13，9（1）依次取a中各数据，构造一棵二叉排序树。（2）说明如何依据此二叉树得到 a的有序序列。（3） 对该二叉树进行查找，成功查找到7要进行多少次元素间的比较？（4）给出对该二叉树后序遍历的序列。（5）画出在二叉树中删除 12后的树结构（要求结点 13的位置

45、不变）。答：(1)(2) 中序遍历 1 , 3, 5, 7, 8, 9, 10, 12, 13(3) 5 次(4) 3, 7, 9, 10, 8, 5, 13, 12, 1(5)29、设有序表为(2, 5, 11, 12, 30, 48, 58, 70, 78, 79, 90),兀素的序号依次为1 ,2, 3,11。(1) 画出对上述查找表进行折半查找所对应的判定树(树中结点用序号表示)(2) 说明成功查找到元素 2需要经过多少次比较？(3) 说明不成功查找元素 75需要经过多少次比较?（4）给出后序遍历该折半查找判定树的序列（5）给出中序遍历该折半查找判定树的序列答：（1）（2）3 次（3）

46、4 次（4）2，1，5，4, 3，8，7，11, 10，9，6 （序号）（5）1，2，3，4，5，6，7，8, 9，10，11 （序号）四、程序填空题（每空 2分，共16分）30、设有一个不带头结点的单向链表，头指针为head，p、prep是指向结点类型的指针，该链表在输入信息时不慎把相邻两个结点的信息重复输入，以下程序段是在该单向链表中查找这相邻两个结点，把该结点的数据域data打印出来，并把其中之一从链表中删除，填写程序中的空格。prep=head;p=prep-n ext;while（p-data!=prep-data）prep=p;（1）printf（ “ min=%d , （ 2）;

47、prep-next=（ 3）答：(1) p=p-next;(2) p-data 或 prep_data(3) p- next31、以下程序是折半插入排序的算法(按记录中关键字 key排序)设待排序的记录序列存放在a1，an中，以a0作为辅助工作单元，以下程序是要把ai 插入到已经有序的序列a1，ai-1中。void binsort (NODE a ,int n)int x,i,j,s,k,m;for (i=2 ; i=(1) ; i+ )a0=ai;if( x=j+1;k-)(5) =ak; aj+1=a0;答：(1) n(2) (s+j)/2(3) j=m-1(4) s=m+1(5) ak+

48、1模拟练习题（二）一、单项选择题（每小题2分，共30分）1头指针为head的带头结点的单向链表为空的判定条件是（C ）为真。A. head-next!= NULL B. head=NULLC. head-next=NULLD. head-next=NULL;2、 设有一个长度为 32的顺序表，要删除第8个元素需移动元素的个数为（ B ）。A. 9B. 24 C. 25 D. 83、 一个栈的进栈序列是2，4，6，8，10，则栈的不可能输出序列是（ A ）（进栈出栈可 以交替进行）。A.8 ， 6， 10， 2， 4 B.8， 10， 6， 4， 2C. 10，8，6，4，2 D. 2，4，6，

49、8，104、一个队列的入队序列是a，b，c，d，按该队列的可能输出序列使各兀素依次入栈，该栈的可能输出序列是（C ）。（进栈出栈可以交替进行）。A. d ， a， b，c B. c ， a， b， d C. d ， c，b， a D. d ， b， a， c5、在一个链队中，假设f和r分别为队头和队尾指针，p指向一个已生成的结点，现要为该结点的数据域赋值e,并使结点入队的运算为p-data=e;p-n ext=NULL;和（D）。A. f-n ext=p;f=p; B. p_n ext=f;f=p; C. p_n ext=r;r=p;D. r-n ext=p;r=p;6、设有一个24阶的对称矩阵 A,米用压缩存储的方式（矩阵的第一个兀素为a1,1），将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第 30号兀素对应于矩阵中的兀素是（C）。A. a 10,8 B. a 8 ,5 C. a 8,2 D. a 9,27、字符串 a1=BEIJING，a2=BEI，a3=BEF