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

-数据结构（本）期末综合练习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开始),需移动元素的个数为 （ ）。 A9 B10 C15 D16 6线性表在存储后,如果相关操作是:要求已知第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按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列 的可能输出序列是（ ）。（进栈出栈可以交替进行）。 A7，5，3，1 B7，3，1,5 C7，5，1，3 D5,1，3，7 10元素2，4，6，8按顺序依次进栈，按该栈的的可能输出序列依次入队列，该队列的可能输出序列是（ ）（进栈出栈可以交替进行）。 A8，6，2，4 B8，4，2，6 C6，2，4，8 D8，6，4，2 11 对一个栈顶指针为top的链栈进行进栈操作，设P为待进栈的结点，则执行（ ）。 Ap=top-next; top=topnext; Bp-next=top; Cp-next=top;top=p; Dtop=p; 12在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则从该对列中删除一 个结点并把结点的值保存在变量x中的运算为（ ）。 Ax=rdata；r=rnext; Br=rnext; x=rdata Cx=fdata；f=fnext; Df=fnext; x=fdata 13设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第33号元素对应于矩阵中的元素是（ ）。(矩阵中的第1个元素是a1,1 ） Aa7,6 Ba10,8 Ca9,2 Da8,5 14设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第38号元素对应于矩阵中的元素是（ ）。(矩阵中的第1个元素是a1,1 ） Aa10,8 Ba7,6 Ca9,2 Da8,5 15设有一个17阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a10,6 在一维数组B中的下标是（ ）。(矩阵中的第1个元素是a1,1 ）A45, B18 C51 D53 16在C语言中，分别存储 “S”和s，各需要占用（ ）字节。 A一个和两个 B两个 C一个 D两个和一个 17串函数StrCmp（“ABCd”，“ABCD”）的值为（ ）。 A0 B-1 C1 D3 18一棵有n个结点，采用链式存储的二叉树中，共有（ ）个指针域被有效使用（即指针域为非空）。 An+1 Bn Cn-1 Dn-2 19一棵采用链式存储的二叉树中有n个指针域为空,该二叉树共有（ ）个结点。 An+1 Bn Cn-1 Dn-2 20在一棵二叉树中，若编号为i的结点存在双亲结点，则双亲结点的顺序编号为（ ）。 Ai/2.0 Bi/2向下取整 C2i+1 Di+2 21设一棵哈夫曼树共有n个非叶结点，则该树有（ ）个结点。 A2n B2n+2 C2n-1 D2n+1 22设一棵哈夫曼树共有2n+1个结点，则该树有（ ）个非叶结点。 An Bn+1 Cn-1 D2n 23一棵 结点数31nnext=p-next; （p-next）-prior=q；然后再用语句q-prior=p;和语句_ p-next=q；_。 8在双向链表中，要在p所指的结后插入q所指的结点(设q所指的结点已赋值)，其中所用的一条语句（p-next）-prior=q； 的功能是使P所指结点的_直接前驱的左指针_指向q 。 9在一个单向链表中，要删除p所指结点的直接后继结点。则可以用操作 _ p-next=p-next-next;_。（用一条语句） 10设有一个带头结点的，头指针为head的单向链表，p指向表中某一个结点，且有p-next= =NULL,现要删除头结点，并使该单向链表构造成单向循环链表，通过操作head=head-next; _ p-next= head;_。 11向一个栈顶指针为top的链栈中插入一个p所指结点时，可执行_ p-next=top; top=p；操作。( 填两条语句, 结点的指针域为next) 12从一个栈顶指针为top的链栈中删除一个结点时，用d保存被删结点的值，可执行_ d=top-data;top=top-next;_。(结点的指针域为next,数据域为data) 13在一个带头结点的链队中，设front和rear分别为队头和队尾指针，则删除一个结点 的操作为 p=front-next;_ front-next_=p-next;(结点的指针域为next, p为辅助用指针) 14.循环链队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize,采用少用一 个元素的模式),判断循环链队列为满的条件为_ front= =(rear+1)% MaxSize_ 。15设有n阶对称矩阵A，用一维数组s压缩存储A的下三角元素，s的下标从零开始，最 后一个元素的下标为27，则n=_ 7_。(矩阵中的第1个元素是a1,1 ） 16对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A相应的三元组 表共有8个元素,则矩阵A共有_ 34_个零元素。17. 一棵3度的树，其中3度结1个，2度结2个，1度结2个，则该树共有_ 5_个 叶结点。 18.一棵有8个权重值构造的哈夫曼数，共有 15 个结点。 19一棵有7个叶结点的二叉树，其1度结点数的个数为2，则该树共有 15_个结点 20一棵有18个结点的二叉树，其2度结点数的个数为8，则该树共有_ 1_个1度结点 21如图3所示的二叉树，其中序遍历序列为_ 512389746_。 3c7gd6f5e4dc2b1a8hd9图322如图4所示的二叉树，其先序遍历序列为_ 215347896_。 3c7gd6f5e4dc2b1a8hd9 图423二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树非空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子的所有结点的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值。这种说法是_不正确_的。(回答正确或不正确) 24在查找表中，通过记录的某关键字能唯一地确定一个记录，该关键字称为_主关键字_。 三、综合题1 (1) 以3，4，5，8，9，10作为叶结点的权，构造一棵哈夫曼树。 (2) 给出相应权重值叶结点的哈夫曼编码。 (3) 一棵哈夫曼树有2n-1个结点，它是共有多少个权重值构造而成的？简述理由？1(1)1098791293543933171552218 图7 (2) 3 0000 4 0001 5 001 10 01 8 10 9 11 （3）n个，因为非叶结点数比叶结点数少一个,而权值个数=叶结点数2（1）对给定权值3，1 ，4，4，5，6，构造深度为5的哈夫曼树。(设根为第1层) (2) 求树的带权路径长度。（3）链接存储上述哈夫曼树，结点中共有多少个指针域为空,说明理由.2. (1)65435423418145197896434531213 图8（2) WPL=3*4+1*4+4*3+6*2+4*2+5*2=58(3) 共11个结点,22个指针域,除根结点外,每个结点对应一个指针域.,共10个指针域非空,故 有 22-10=12个空指针域, 3（1）简述拓扑排序的步骤。 （2）说明有向图的拓扑序列不一定是唯一的原因。 （3）如何利用拓扑排序算法判定图是否存在回路。 （4）设有向图G如下，写出首先删除顶点1的3种拓扑序列。1234543465 图53. (1) 循环执行以下两步 选择一个度为0的顶点并输出 从网中删除此结点及所有出边 （2） 因为选择一个度为0的顶点时不一定是唯一的 （3） 由顶点活动网构造拓扑序列的过程中，输出结点后，余下的结点均有前驱 (4) 152364 152634 1562344. (1) 如下的一棵树,给出先序遍历序列 (2) 把1,2,3,4,5,6,7,8,9填人,使它成为一棵二叉排序树 提示：设图中的树是二叉排序树，找出中序遍历序列与 1，2，9的对应关系 (3) 请在该树中再插入一个结点3.5作为叶结点，并使它仍然是一棵二叉排序树。A1A2A43A7A5A9A8A3A6 图64 .(1) A1 A2 A4 A7 A8 A5 A9 A3 A6 (2) (3)7421563893.5 图95设有序表为（21，22，23，24，25，26，27，28，29，30，31,32），元素的下标从 0开始。 （1）说出有哪几个元素需要经过4次元素间的比较才能成功查到。（2）画出对上述有序表进行折半查找所对应的判定树（树结点用数值表示）（3）设查找元素为5，需要进行多少次元素间的比较才能确定不能查到。 （4）求在等概率条件下，成功查找的平均比较次数？5.2431427173222818251522112312101000000302026162322132919（1) 5(2) 图10(3) 3 (4) ASL=(1+2*2+3*4+5*4)/12=37/126设查找表为(5,6,7,8,9,10,11,12,13,14) （1）画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点) (2) 给出二叉排序树的定义,针对上述折半查找所对应的判定树的构造过程,说明判定树 是否是二叉排序树(设树中没有相同结点)？(3) 为了查找元素5.5，经过多少次元素间的比较才能确定不能查到？9710141185121366.(1) 图10(2) 二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树 非空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子 树的所有结点的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值; 左,右子树也是一棵二叉排序树，按定义判定树是二叉排序树。 (3) 3次四、程序填空题1以下程序是快速排序的算法 设待序的记录序列存放在astart,aend中，按记录的关键字进行快速排序， 先进行一次划分，再分别进行递归调用 void quicksort ( NODE a , int start ,int end ) int i，j; NODE mid ; if (start=end ) return; i=start; j=end; mid=ai; while (ij) while(imid.key) j- -; if(ij) ai=aj; _(1) i+; _; while(ij & ai.key=mid.key) _(2) i +;_; if(ij) _(3) aj=ai; _ _(4)_ j-;_ ai=mid; quicksort (a,stat, i-1); quicksort _(5) (a, i+1,end);_ 2以下函数为直接选择排序算法，对a1,a2,an中的记录进行直接选择排序，完成程序中的空格typedef struct int key;NODE; void selsort(NODE a,int n)int i,j,k;NODE temp;for(i=1;i= _(1)_ n-1_;i+) k=i; for(j=i+1;j= _(2)_ n _;j+) if(aj.keydata=x; p-next=NULL; _(2)_ rear-next=p _; rear= _(3)_ p _; 4 .设有一个头指针为head的不带头结点单向链表, 且p、q是指向链表中结点类型的指针变量，p指向链表中某结点a（设链表中没有结点的数据域与结点a的数据域相同）, 写出相关语句 (1).使该单向链表成为单向循环链表 (2) 删去a结点 q=p; x=p-data;while （q-next!=NULL）q=q-next; (1) _(1)_ q-next=head;_ q=p; p=p-next;while(p-data!=x) q=p;(1) _(2)_ p=p-next;_(3) q-next=p-next;_期末综合练习二一、单项选择题1. 数据结构在计算机内存中的表示是指 ( ) 。 A数据元素之间的关系 B数据的存储结构 C数据元素的类型 D数据的逻辑结构 2 .结构中的元素之间存在一对多的关系是（ ）。 A集合 B线性结构 C树形结构 D图状结构 3 . 结构中的元素之间存在多对多的关系是（ ）。 A集合 B线性结构 C树形结构 D图状结构 4.对不带头结点的单向链表,判断是否为空的条件是（ ）（设头指针为head）。Ahead=NULL Bhead-next= =NULL Chead-next= =head Dhead =NULL 5 . 设有一个长度为20的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作为新表的第5个元素），则移动元素个数为（ ）。 A15 B16 C. 5 D4 6. 在一个不带头结点的单循环链表中，p、q分别指向表中第一个结点和尾结点，现要删除第一个结点，可用的语句是（ ）。 Ap=q-next; p=p-next; Bp-next=q ; p=p-next; Cp-next=q-next;q=p; Dp=p-next; q-next=p; 7在一个尾指针为rear的不带头结点的单循环链表中,插入一个s所指的结点,并作为第一个结点，可执行（ ）。 Arearnext= s; snext=rearnext Brearnext=snext; Crear=snext Dsnext=rearnext ; rearnext=s;8一个栈的进栈序列是1，2，3，4，5，则栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。A12345 B43512 C45321 D54321 9元素a，b，c,d按顺序依次进栈，则该栈的可能输出序列是（ ）（进栈出栈可以交替进行）。 Ac,a,b，d Bd，b，c,a Ca,c，b，d Dd，c，a,b 10一个队列的入队序列是2，4，6，8，按该队列的输出序列使各元素依次入栈，该栈的可能输出序列是 （ ）。 A8，6，4，2 B6，2，4，8 C8，4，2，6 D8，2，4，6 11从一个栈顶指针为top的链栈中取栈顶元素，用变量x保存该元素的值，则执行（ ）。 Ax=top-data; top=topnext; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data; 12在一个链队中，假设f和r分别为队头和队尾指针，已生成一个结点p,要为结点p赋 值x,并入队的运算为（ ）。 A . p-data=x; p-next=NULL; f-next=p; f=p; B p-data=x; p-next=NULL ;r-next=p;r=p; C p-data=x; p-next=r;r=s; D p-data=x; p-next=f;f=s; 13设有一个对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），B数组共有55个元素,则该矩阵是（ ）阶的对称矩阵。 (矩阵中的第1个元素是a1,1 ）A5 B20 C10 D15 14设有一个25阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a7,6在一维数组B中的下标是（ ）。 (矩阵中的第1个元素是a1,1 ）A34 B14 C26 D27 15设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第53号元素对应于矩阵中的元素是（ ）。(矩阵中的第1个元素是a1,1 ）Aa8,5 , Ba10,8 Ca8,1, Da7,6 16.以下程序段的结果是 c的值为（ ）。char a8= “1236789”, int *p=a, int c=0; while(*p+)c+; A8, B7 C10 D12 17 .以下程序段的结果是 c的值为（ ）。char * a5=“12378”, “1237”, “1236789”, “1237”, “123708”;int i,c=0; for(i=0;iprior）-next=p-next；然 再用语句_（p-next）-prior=p-prior；_。 7在双向链表中，要删除p所指的结点，其中所用的一条语句（p-prior）-next=p-next； 的功能是：使P所指结点的直接前驱的右指针指向_ P所指结点的直接后继_。8在一个单向链表中p所指结点之后插入一个s所指向的结点时，应执行s-next=p-next; 和 _ p-next=s;_的操作. 9设有一个头指针为head的单向链表，p指向链表中的某结点，若要使该链表成为单向 循环链表，可用语句while(p-next!= NULL) p= p-next; 和_ p-next=head;_。 10一个栈和一个队列的输入序列都为abcdefg，它们可能有相同的输出序列吗？_ abcdefg_。 （若没有则回答没有，若有则写出序列,进栈出栈可以交替进行）。11向一个栈顶指针为top的链栈中插入一个p所指结点时，某人用语句top=p；p-next=top; 这样做的结果使p所指向的结点的指针域指向了 _ p本身_。 12.从一个栈顶指针为top的链栈中取栈顶元素，用d保存栈顶元素的值，可执行_ d=top-data;_。(结点的数据域为data) 13在一个链队中，设front和rear分别为队头和队尾指针，则s所指结点(数据域已赋值)的入队操作为s-next=NULL;._ rear-next=s;_和rear=s; 14. 循环链队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize,),判断循环链队列为空的条件是_ front= =rear_为真 。15设有n阶对称矩阵A，用一维数组s压缩存储A的下三角元素，s的下标从零开始，元素s26相应于A中的元素为_ a7,6_。(矩阵中的第1个元素是a1,1 ） 16. 对稀疏矩阵进行压缩存储,可采用三元组表，设a是稀疏矩阵A相应的三元组表类型（结构体类型）变量，a中的一个成员项是三元组类型的结构体数组data，按书中定义，若a.data0.i=2;a.data0.j=3; a.data0.v=16; 它提供的 A数组的相关信息有_ A的第一个非零元素的下标为2，3 ，元素为16 _。17对稀疏矩阵进行压缩存储,可采用三元组表，设a是稀疏矩阵A相应的三元组表类型（结构体类型）变量，a中的一个成员项是三元组类型的结构体数组data，按书中定义，若data的下标从零开始，最后一个元素下标为10，又a.data10.i=8;a.data10.j=5; a.data10.v=36; 它提供的 A矩阵的相关信息有_ A共有11个非零元素 ，a8,5为36_。 18设有一棵深度为5的完全二叉树，该树共有20个结点,第五层上有 5 个叶结点。 （根所在结点为第1层） 19设有一棵有78个结点的完全二叉树，该树共有_ 7_层。（根所在结点为第1层）20中序遍历_二叉排序_树可得到一个有序序列。 21对于一棵具有_ n_个结点的二叉树，其相应的链式存储结构中共有n+1个指针域空. 22如图4所示的二叉树，其后序遍历序列为_ 519876432_。 3c7gd6f5e4dc2b1a8hd9图423如图5所示的二叉树，其中序遍历序列为_ 5387946_。4g3f9a7b58e6c 图5 24 .给定一组权重值，构造哈夫曼树，哈夫曼树的高度一定是唯一的，这种说法是_不正确_的。(回答正确或不正确) 三、综合题1（1）已知某二叉树的后序遍历序列是debca，中序遍历序列是dbeac，试画出该二叉树。 （2）若上述二叉树的各个结点的字符分别代表不同的整数（其中没有相等的），并恰好使该树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系。 （3）给出该树的前序遍历序列。abced1（1） 图8（2）dbeac（3）abdec2. (1) 说明什么是顶点活动网(AOV网)和拓扑序列 （2）设有向图G如下，写出3种拓扑序列， （3）在图G中增加一条边，使图G仅有一条拓扑序列abcd图62 (1) 用顶点表示活动，边表示活动间先后关系的有向图称为顶点活动网 在顶点活动网中，若不存在回路,则所有活动可排列成一个线性序列,使每个活动的所 有前驱活动都排在该活动的前面,称此序列为拓扑序列 (2) abdc adbc dabc (3) 在 b和d间添加有向边 3（1）利用筛选过程把序列42，82，67，102，16，32