数据结构(本)期末综合练习(2013年6月)

1数据结构（本）期末综合练习2013年6月期末综合练习一1.在数据结构和算法中，与所使用的计算机有关的是（）。A．数据元数间的抽象关系B．数据的存储结构C．算法的时间复杂度D．数据的逻辑结构2.一种逻辑结构在存储时（）。A．只要存储数据元素间的关系B．只能采用一种存储结构C．可采用不同的存储结构D．只要存储数据元素的值3.对顺序表,以下叙述中正确的是()。A．用一组地址连续的存储单元依次存放线性表的数据元素B．各个数据元素的首地址是连续的C．数据元素不能随机访问D．插入操作不需要移动元素4.对链表,以下叙述中正确的是（）。A．不能随机访问任一结点B．结点占用的存储空间是连续的C．插入删除元素的操作一定要要移动结点D．可以通过下标对链表进行直接访问5．设有一个长度为25的顺序表，要删除第10个元素(下标从1开始),需移动元素的个数为（）。A．9B．10C．15D．166．线性表在存储后,如果相关操作是:要求已知第i个结点的位置访问该结点的前驱结点，则采用（）存储方式是不可行的。A．单链表B．双链表C．单循环链表D．顺序表7.设单向链表中,指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为()。A.p-next=p-next-next;B.p=p-next;C.p=p-next-next;D.p-next=p;8．栈和队列的共同特点是（）。A．都是先进后出B．元素都可以随机进出C．只容许在端点处插入和删除元素D．都是先进先出9．元素1，3，5，7按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的可能输出序列是（）。（进栈出栈可以交替进行）。A．7，5，3，1B．7，3，1,5C．7，5，1，3D．5,1，3，710．元素2，4，6，8按顺序依次进栈，按该栈的的可能输出序列依次入队列，该队列的可能输出序列是（）（进栈出栈可以交替进行）。A．8，6，2，4B．8，4，2，6C．6，2，4，8D．8，6，4，211．对一个栈顶指针为top的链栈进行进栈操作，设P为待进栈的结点，则执行（）。A．p=top-next;top=topnext;B．p-next=top;2C．p-next=top;top=p;D．top=p;12．在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则从该对列中删除一个结点并把结点的值保存在变量x中的运算为（）。A．x=rdata；r=rnext;B．r=rnext;x=rdataC．x=fdata；f=fnext;D．f=fnext;x=fdata13．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第33号元素对应于矩阵中的元素是（）。(矩阵中的第1个元素是a1,1）A．a7,6B．a10,8C．a9,2D．a8,514．设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第38号元素对应于矩阵中的元素是（）。(矩阵中的第1个元素是a1,1）A．a10,8B．a7,6C．a9,2D．a8,515．设有一个17阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a10,6在一维数组B中的下标是（）。(矩阵中的第1个元素是a1,1）A．45,B．18C．51D．5316．在C语言中，分别存储“S”和‘s’，各需要占用（）字节。A．一个和两个B．两个C．一个D．两个和一个17．串函数StrCmp（“ABCd”，“ABCD”）的值为（）。A．0B．-1C．1D．318．一棵有n个结点，采用链式存储的二叉树中，共有（）个指针域被有效使用（即指针域为非空）。A．n+1B．nC．n-1D．n-219．一棵采用链式存储的二叉树中有n个指针域为空,该二叉树共有（）个结点。A．n+1B．nC．n-1D．n-220．在一棵二叉树中，若编号为i的结点存在双亲结点，则双亲结点的顺序编号为（）。A．i/2.0B．i/2向下取整C．2i+1D．i+221．设一棵哈夫曼树共有n个非叶结点，则该树有（）个结点。A．2nB．2n+2C．2n-1D．2n+122．设一棵哈夫曼树共有2n+1个结点，则该树有（）个非叶结点。A．nB．n+1C．n-1D．2n23．一棵结点数31n40的完全二叉树，最后一层有4个结点，则该树有（）个叶结点A．18B．17C．36D．3524．一棵完全二叉树共有4层，且第4层上有2个结点，该树共有（）个非叶子结点(根为第一层)。A．5B．4C．3D．925．已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A．abedfcB．acfebdC．aebcfdD．aedfbc3图126．如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A．abedfcB．acfebdC．aebcdfD．aebcfd图227．一组记录的关键字序列为（46,20,30,79，56，38，40，84,90,110），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。A．20,30,40，38，46，79，56，84,90,100B．40，20,30,38，46，56，79，84,90,110C．30,20,40，38，46，84，56，79,90,100D．20,3038，40，46，56，79，84,90,10028．一组记录的关键字序列为（56，30,89，66，48，50，94,87,100），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。A．30，50,48，56，66，89，94,100,87B．50，30,48，56，66，89，94,87,100C．48，30,50，56，66，89，94,87,100D．50，30,48，66，56，89，94,87,10029．一组记录的关键字序列为（75，63，95，80，53，45，38，20），利用堆排序（堆顶元素是最大元素）的方法建立的初始堆为（）。A．95，80，75，63，53，45，38，20B．95，63，75，80，53，45，38，20c.95,80,45,63,53,75,38,20D．95,80,75,20,53,45,38,6330．线性表以（）方式存储，能进行折半查找。A．关键字有序的链接B．顺序C．关键字有序的顺序D．数组bdfecabdfeca4二、填空题1．数据元素之间的抽象关系称为________结构。2.数据的逻辑结构在计算机中的表示称为________结构。3．要求在n个数据元素中找值最大的元素，其基本操作为________。算法的时间复杂度为_______。4.求两个n阶矩阵的乘积，算法的基本操作为________，时间复杂度为________。5．设有一个长度为25的顺序表,第8号元素到第25号元素依次存放的值为8,9,10,11,…,25，某人想要删除第8个元素，他的做法是从第25号元素开始,直到第9号元素依次向前移动1个位置,其结果新表中第9号元素的值为（）。6．设有一个长度为25的顺序表,第8号元素到第25号元素依次存放的值为8,9,10,11,…25,某人想要在第8个元素前插入1个元素7（也就是插入元素作为新表的第8个元素），他的做法是从第8号元素开始,直到第25号元素依次向后移动1个位置,然后把7存放在8号位置，其结果是新表中第25号元素的值为（）。7．在双向链表中，要在p所指的结后插入q所指的结点(设q所指的结点已赋值)，可以先用语句q-next=p-next;（p-next）-prior=q；然后再用语句q-prior=p;和语句________。8．在双向链表中，要在p所指的结后插入q所指的结点(设q所指的结点已赋值)，其中所用的一条语句（p-next）-prior=q；的功能是使P所指结点的_______指向q。9．在一个单向链表中，要删除p所指结点的直接后继结点。则可以用操作________。（用一条语句）10．设有一个带头结点的，头指针为head的单向链表，p指向表中某一个结点，且有p-next==NULL,现要删除头结点，并使该单向链表构造成单向循环链表，通过操作head=head-next;________。11．向一个栈顶指针为top的链栈中插入一个p所指结点时，可执行________操作。(填两条语句,结点的指针域为next)12．从一个栈顶指针为top的链栈中删除一个结点时，用d保存被删结点的值，可执行________。(结点的指针域为next,数据域为data)13．在一个带头结点的链队中，设front和rear分别为队头和队尾指针，则删除一个结点的操作为p=front-next;_______=p-next;(结点的指针域为next,p为辅助用指针)14.循环链队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize,采用少用一个元素的模式),判断循环链队列为满的条件为________。15．设有n阶对称矩阵A，用一维数组s压缩存储A的下三角元素，s的下标从零开始，最后一个元素的下标为27，则n=_______。(矩阵中的第1个元素是a1,1）16．对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A相应的三元组表共有8个元素,则矩阵A共有_______个零元素。17.一棵3度的树，其中3度结1个，2度结2个，1度结2个，则该树共有_______个叶结点。18.一棵有8个权重值构造的哈夫曼数，共有个结点。19．一棵有7个叶结点的二叉树，其1度结点数的个数为2，则该树共有_______个结点20．一棵有18个结点的二叉树，其2度结点数的个数为8，则该树共有_______个1度结点21．如图3所示的二叉树，其中序遍历序列为_________。5图322．如图4所示的二叉树，其先序遍历序列为_________。图423．二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树非空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子的所有结点的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值。这种说法是__________的。(回答正确或不正确)24．在查找表中，通过记录的某关键字能唯一地确定一个记录，该关键字称为_________。三、综合题1．(1)以3，4，5，8，9，10作为叶结点的权，构造一棵哈夫曼树。(2)给出相应权重值叶结点的哈夫曼编码。(3)一棵哈夫曼树有2n-1个结点，它是共有多少个权重值构造而成的？简述理由？2．（1）对给定权值3，1，4，4，5，6，构造深度为5的哈夫曼树。(设根为第1层)(2)求树的带权路径长度。（3）链接存储上述哈夫曼树，结点中共有多少个指针域为空,说明理由.3c7gd6f5e4dc2b1a8hd93c7gd6f5e4dc2b1a8hd963．（1）简述拓扑排序的步骤。（2）说明有向图的拓扑序列不一定是唯一的原因。（3）如何利用拓扑排序算法判定图是否存在回路。（4）设有向图G如下，写出首先删除顶点1的3种拓扑序列。图54.(1)如下的一棵树,给出先序遍历序列(2)把1,2,3,4,5,6,7,8,9填人,使它成为一棵二叉排序树提示：设图中的树是二叉排序树，找出中序遍历序列与1，2，…9的对应关系(3)请在该树中再插入一个结点3.5作为叶结点，并使它仍然是一棵二叉排序树。图65．设有序表为（21，22，23，24，25，26，27，28，29，30，31,32），元素的下标从0开始。（1）说出有哪几个元素需要经过4次元素间的比较才能成功查到。（2）画出对上述有序表进行折半查找所对应的判定树（树结点用数值表示）（3）设查找元素为5，需要进行多少次元素间的比较才能确定不能查到。（4）