《数据结构(本)期末综合练习》由会员分享，可在线阅读，更多相关《数据结构(本)期末综合练习（47页珍藏版）》请在金锄头文库上搜索。
1、数据结构（本）期末综合练习综合练习一一、单项选择题 1设有头指针为head的带有头结点的非空单向循环链表, 指针p指向其尾结点, 要删除头结点,并使其仍为单向循环链表,则可利用下述语句head =head-next ;（ ）。 Ap =head; Bp=NULL; Cp-next =head; Dhead=p; 2在一个单链表中p指向结点a, q指向结点a的直接后继结点b，要删除结点b，可执行（ ）。 Ap-next=q-next ; Bp=q-next; Cp-next=q; Dp-next=q; 3. 以下说法不正确的是 A. 线性表的链式存储结构不必占用连续的存储空间 B一种逻辑结构只能
2、有唯一的存储结构 C. 一种逻辑结构可以有不同的存储结构 D线性表的顺序存储结构必须占用连续的存储空间4在一个单向链表中,在p所指结点之后插入一个s所指的结点时，可执行（ ）;和p-next=s; Ap= s; B p-next=s-next; Cp=s-next; D s-next=p-next; 5把数据存储到计算机中，并具体体现( )称为物理结构 。 A. 数据元素间的逻辑关系B数据的处理方法 C数据的性质 D数据的运算 6设有一个长度为23的顺序表，要删除第8个元素需移动元素的个数为（ ）。 A16 B14 C15 D13 7链表所具备的特点之一是（ ）。 A可以随机访问任一结点 B需
3、要占用连续的存储空间 C插入元素的操作不需要移动元素 D删除元素的操作需要移动元素8设一棵有8个叶结点的二叉树，度数为1的结点有3个,则该树共有（ ） 个结点。 A20 B18 C17 D16 9图状结构中数据元素的位置之间存在（ ）的关系。 A一对一 B多对多 C一对多 D每一个元素都有一个直接前驱和一个直接后继 10一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（ ）个结点。 A14 B15 C19 D18 11元素15，9，11，13按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。 A13，11，9，15 B15，9，11，13 C13，11，15，9
4、 D9， 15，13，11 12.设主串为“FABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（ ）。 A. EFaBc B. ABCdE C. DABCC D .FAbcC 13设有一个14阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a4,3在一维数组B中的下标是（ ）。 A9 B10 C11 D8 14元素111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。 A117，115，113，111 B111，113，115，117 C113
5、，111，117，115 D117，115，111，113 15在一棵二叉树中，若编号为8的结点存在右孩子，则右孩子的顺序编号为（ ）。 A18 B16 C15 D17 16以下说法不正确的是（ ）。 A栈和队列都是线性结构 B栈的特点是后进先出 C. 栈和队列的特点都是先进后出 D队列的特点是先进先出17设一棵哈夫曼树共有14个非叶结点，则该树总共有（ ）个结点。 A29 B.27 C30 D28 18设有一个15阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三 角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a4,2 在一维数组B中的下标是（ ）。
6、A9 B8 C7 D10 19如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得 到的一种顶点序列为（ ）。 Aabecdf Bacfebd Caebcfd Daedbfc 20如图2所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能 得到的一种顶点序列为（ ）。 Aacedbf Bacebfd Caebcfd Daedfcb 二、填空题 1. 队列的特点之一是：元素进、出队的次序是:先进_。 2. 序列13,11,14,12,17,15,采用冒泡排序算法,经一趟冒泡后,序列的结果是_。3 _结构中，数据元素间存在一对多的关系。 4. 对16个元素的序列用冒泡排
7、法进行排序，通常需要进行_趟冒泡。5对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的 三项信息是_ _。 6. 对9个元素的一组记录（58，35，93，20，12，78，56，41，79）进行直接插入排 序(由小到大排序) ，当把第7个记录56插入有序表，为寻找插入位置需比较 _次。7在对11个记录的序列(12，35, 9, 7 ,2, 11 ,56 , 95 ,37,58 ,60)进行直接插入排序时，当把第6个记录11 插入到有序表时，为寻找插入位置，元素间需比较_次。（由小到大排列） 8结构中的数据元素存在一对多的关系称为_结构。 9哈希函数是记录关键字的值与该记录_ _
8、之间所构造的对应关系。10设有一棵深度为5的完全二叉树，第5层上有3个结点，该树共有_个结点。 （根所在结点为第1层） 1120个元素进行冒泡法排序，通常需要进行19趟冒泡 ,其中第10趟冒泡共需要进行 _ _次元素间的比较。 12 一棵二叉树中每一个非叶结点的度数都为2，共有10个非叶结点，则该树共有 _ 个结点。13一棵有19个结点的二叉树,采用链式结构存储,该树结构中有 _ 个指针 域为空。 14. 序列3,1,7,18,6,9,13,12经一趟归并排序的结果为_ _ _。15中序遍历一棵 _树可得到一个有序序列。 16 一棵有16个叶结点的哈夫曼树，则该树共有_个非叶结点。17二叉排序
9、树插入操作中,新插入的结点总是以树的_ 结点被插入的 18_遍历二叉排序树可得到一个有序序列。 19. 广义表的( a , (d,a ,b) , h , (e ,( (i ,j ) ,k ) )深度是_ 。 20. 广义表( f , h , (a ,b, d, c) , d , e ,( (i ,j ) ,k ) )的长度是_ _。 21. 序列4 , 2 , 5 , 3 , 8 , 6 , 7, 9,采用归并排序算法(升序),经一趟归并后,序列的结果 _ _。 22. 广义表的( h ,c，g, a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_ _。 23. 字符串a1=teijing, a2 =tef , a3= teifang, a4=“tefi最小的 是 _。 24设有串p1=”ABADF”,P2=”ABAFD”，P3=”ABADFA”P4=”ABAF”, 四个串中最 小的是 _ 。 三、综合题 1设查找表
