《数据结构与算法期中练习题答案.doc》由会员分享，可在线阅读，更多相关《数据结构与算法期中练习题答案.doc（8页珍藏版）》请在三一文库上搜索。
1、 数据结构与算法期中练习题一、 写出以下各词语的对应中文queue 队列 singly linked lists 单链表 storge structure 存储结构 time complexity 时间复杂度 Abstract Data Type (ADT) 抽象数据类型 二、 选择题1、在数据结构中，线性结构中元素之间存在_A_关系。 A: 一对一B: 一对多C: 多对一D: 多对多2、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的B_和运算等的学科。A: 结构B: 关系C: 操作D: 算法3、算法分析的两个主要方面是_A_。A: 空间复杂度和时间复杂度B: 正确
2、性和简明性C: 可读性和文档性D: 数据复杂性和程序复杂性4、顺序表中逻辑上相邻的节点其物理位置也_A_。A: 一定相邻B: 不必相邻C: 按某种规律排列D: 无要求5、下面两个图各表现一批数据的结构，其中 C 。A: 左边表现的是逻辑结构，右边表现的是物理结构B: 右边表现的是逻辑结构，左边表现的是物理结构C: 两者表现的都是逻辑结构D: 两者表现的都是物理结构6、 向一个长度为n的顺序表的第i个元素（1=inext=p-next; p-next=s;B: p-next=s-next; s-next=p;C: q-next=s; s-next=p;D: p-next=s; s-next=q;
3、8、一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是_C_。A: edcbaB: decbaC: dceabD: abcde9、循环队列用数组A0,m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_A_。A: (rear-front+m)%mB: rear-front+1C: rear-front-1D: rear-front10、关于空格串，下列说法中正确的有_D_。A: 空格串就是空串B: 空格串是零个字符的串C: 空格串的长度为零D: 空格串的长度就是其包含的空格个数11、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j
4、从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为_C_。A: SA+140B: SA+144C: SA+222D: SA+22512、 深度为4的二叉树至多有_B_个结点。A：14B：15C：16D：1713、对于一棵满二叉树，m个树叶，n个节点，深度为h，则_D_。A: n=h+mB: h+m=2nC: m=h-1D: n=2h-114、具有65个结点的完全二叉树其深度为_B_。（根的层次号为1）A: 8B: 7C: 6D: 515、满二叉树_A_二叉树。A: 一定是完全B: 不一定是完全C: 不是D: 不是完全16、将一棵有100个节点的完全二叉树从
5、上到下，从左到右依次对节点进行编号，根节点的编号为1，则编号为49的节点的左孩子编号为_B_。A: 99B: 98C: 50D: 4817、将递归算法转换成对应的非递归算法时，通常需要使用_A_。A: 栈B: 队列C: 链表D: 树18、按照二叉树的定义，具有3个结点的二叉树有_C_种。A: 3B: 4C: 5D: 619、如图所示的4棵二叉树中，_C_不是完全二叉树。A: B: C: D: 20、所谓稀疏矩阵指的是_C_。A: 零元素个数较多的矩阵B: 零元素个数占矩阵元素总个数一半的矩阵C: 零元素个数远远多于非零元素个数且分布没有规律的矩阵D: 包含有零元素的矩阵三、已知线性链表如下图，
6、头指针为La，写出语句序列使左图中的指针指向改成右图中的指针指向。答:p=La-next;La-next=p-next; p-next=La;La=p;四、在一个C语言程序中，有结构类型STUDENT的定义和结构数组allstudents的声明如下：struct STUDENT char name8; int number;STUDENT allstudents1050; allstudents是一个二维数组，它的每个元素都是包含name和number的结构类型。已知在C语言中，二维数组使用以行序为主序的存储结构，char类型占用1字节，int类型占用4字节。假定allstudents在内存中
7、的起始存储位置是2000，请写出计算allstudentsij的存储位置的算式，并计算allstudents35的存储位置。答: (1) allstudentsij的存储位置=2000+(i*50+j)*12 (2) allstudents35的存储位置=2000(3*50+5)*12=3860五、用下标从0到4的一维数组存储一个循环队列，目前其中有两个元素A、B，状态如图(a)。如果此后有17个数据元素C、D、P、Q、R、S依次进队列，其间又有16个元素先后出队列，请在图(b)中填写队列最后的状态，包括其中的元素和指针的位置。答:rearRBfrontQfrontArearS(a)(b)六、
8、序列(a,b,c,d,e)已存在静态链表如下图a，头指针指向1号结点。请完成：1在静态链表中标出此序列的逻辑关系。2画出依次执行了b前插入f，删除e，c后插入g操作后的新的静态链表图b。答:14 删除e，c后插入g操作后142c52c33e3g54a64a75d35d6b26b277f6图a图b插入”f”后142c53e4a75d36b27f6图b七、已知一个稀疏矩阵A如下，填写下表1给出它的三元组顺序表表示2给出它的转置矩阵B的三元组顺序表表示020000100000030000000040050006答:ijv转置后(排序)ijv122121211212323233454255525544
9、566656A.data B.dataA.mu5B.mu6A.nu6B.nu5A.tu6B.tu6转置后(未排序)ijv212121233544255656八、任意一棵有N个结点的二叉树，已知它有M个叶子结点。试证明非叶子结点中度数为2的有M-1个，其余的度数为1。证: 设二叉树中度为0的结点数为n0, 度为1的结点数为n1，度为2的结点数为n2，二叉树中分支数为B N=n0+n1+n2N=M+n1+n2又 B=0+n1+2*n2 (其中: 0-度为0的结点的分支数(叶子结点) ,n1-度为1的结点的分支数,2*n2-度为2的结点的分支数.又 N=B+1M+n1+n2=0+n1+2*n2+1M
10、=n2+1 n2=M-1证明：设度为1和2 的结点数是n1和n2，则二叉树结点数n为n=m+n1+n2 (1)由于二叉树根结点没有分枝所指，度为1和2的结点各有1个和2个分枝，度为0 的结点没有分枝，故二叉树的结点数n与分枝数B有如下关系n=B+1=n1+2*n2+1.(2)由（1）和（2），得n2=m-1。即n个结点的二叉树，若叶子结点数是m，则非叶子结点中有（m-1）个度为2，其余度为1。九、写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,an）逆置为（an,an-1,a1）。答:#define ListSize 100 / 假定表空间大小为100typedef
11、int DataType;/假定DataType的类型为int型typedef structDataType dataListSize;/ 向量data用于存放表结点int length; / 当前的表长度 Seqlist;/ 顺序表结构定义同上题void ReverseList( Seqlist *L)DataType temp ; /设置临时空间用于存放dataint i;for (i=0;ilength/2;i+)/L-length/2为整除运算 temp = L-datai; /交换数据L - data i = L - data L - length-1-i;L - data L -
12、length - 1 - i = temp;十、写一算法，实现统计带表头的单链表中元素值为奇数的结点个数。答:单链表结点的类型定义如下: typedef int elemtype; /定义数据域的类型typedef struct Lnode /定义结点类型 elemtype data; struct Lnode *next; Lnode, *LinkList; int sum(linklist L) listnode *p;/ linklist p; int s=0; for(p=L-next;p!=NULL;p=p-next) if(p-data%2= =1) s+; return s;第8页，共8页