数据结构与算法期中练习题答案

《数据结构与算法》期中练习题写出以下各词语的对应中文queue队列singlylinkedlists单链表storgestructure存储结构timecomplexity时间复杂度AbstractDataType(ADT)抽象数据类型选择题1、在数据结构中，线性结构中元素之间存在__A__关系。

A:一对一

B:一对多

C:多对一

D:多对多2、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的B___和运算等的学科。A:结构

B:关系

C:操作

D:算法3、算法分析的两个主要方面是__A__。A:空间复杂度和时间复杂度

B:正确性和简明性

C:可读性和文档性

D:数据复杂性和程序复杂性4、顺序表中逻辑上相邻的节点其物理位置也___A_。A:一定相邻

B:不必相邻

C:按某种规律排列

D:无要求5、下面两个图各表现一批数据的结构，其中C。A:左边表现的是逻辑结构，右边表现的是物理结构B:右边表现的是逻辑结构，左边表现的是物理结构C:两者表现的都是逻辑结构D:两者表现的都是物理结构向一个长度为n的顺序表的第i个元素（1<=i<=n）之前插入一个元素时，需向后移动__D__个元素。A:iB:n-iC:n-i-1D:n-i+17、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行_C_。

A:s->next=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;8、一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是_C___。

A:edcba

B:decba

C:dceab

D:abcde9、循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是__A__。

A:(rear-front+m)%m

B:rear-front+1

C:rear-front-1

D:rear-front10、关于空格串，下列说法中正确的有__D__。

A:空格串就是空串

B:空格串是零个字符的串

C:空格串的长度为零

D:空格串的长度就是其包含的空格个数11、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为__C__。

A:SA+140

B:SA+144

C:SA+222

D:SA+225深度为4的二叉树至多有__B__个结点。A：14B：15C：16D：1713、对于一棵满二叉树，m个树叶，n个节点，深度为h，则__D__。

A:n=h+m

B:h+m=2n

C:m=h-1

D:n=2h-114、具有65个结点的完全二叉树其深度为__B__。（根的层次号为1）

A:8

B:7

C:6

D:515、满二叉树__A__二叉树。

A:一定是完全

B:不一定是完全

C:不是

D:不是完全16、将一棵有100个节点的完全二叉树从上到下，从左到右依次对节点进行编号，根节点的编号为1，则编号为49的节点的左孩子编号为__B__。

A:99

B:98

C:50

D:4817、将递归算法转换成对应的非递归算法时，通常需要使用__A__。

A:栈

B:队列

C:链表

D:树18、按照二叉树的定义，具有3个结点的二叉树有__C__种。

A:3

B:4

C:5

D:619、如图所示的4棵二叉树中，_C___不是完全二叉树。

A:

B:

C:

D:20、所谓稀疏矩阵指的是__C__。

A:零元素个数较多的矩阵

B:零元素个数占矩阵元素总个数一半的矩阵

C:零元素个数远远多于非零元素个数且分布没有规律的矩阵

D:包含有零元素的矩阵三、已知线性链表如下图，头指针为La，写出语句序列使左图中的指针指向改成右图中的指针指向。答:p=La->next;La->next=p->next;p->next=La;La=p;四、在一个C语言程序中，有结构类型STUDENT的定义和结构数组allstudents的声明如下：structSTUDENT{charname[8];intnumber;}STUDENTallstudents[10][50];allstudents是一个二维数组，它的每个元素都是包含name和number的结构类型。已知在C语言中，二维数组使用以行序为主序的存储结构，char类型占用1字节，int类型占用4字节。假定allstudents在内存中的起始存储位置是2000，请写出计算allstudents[i][j]的存储位置的算式，并计算allstudents[3][5]的存储位置。答:(1)allstudents[i][j]的存储位置=2000+(i*50+j)*12(2)allstudents[3][5]的存储位置=2000(3*50+5)*12=3860五、用下标从0到4的一维数组存储一个循环队列，目前其中有两个元素A、B，状态如图(a)。如果此后有17个数据元素C、D、……P、Q、R、S依次进队列，其间又有16个元素先后出队列，请在图(b)中填写队列最后的状态，包括其中的元素和指针的位置。答:rear→RBfront→Qfront→Arear→S(a)(b)六、序列(a,b,c,d,e)已存在静态链表如下图a，头指针指向1号结点。请完成：1．在静态链表中标出此序列的逻辑关系。2．画出依次执行了b前插入f，删除e，c后插入g操作后的新的静态链表图b。答:14删除e，c后插入g操作后142c52c33e∧3g54a64a75d35d∧6b26b277f6图a图b插入”f”后142c53e∧4a75d36b27f6图b七、已知一个稀疏矩阵A如下，填写下表1．给出它的三元组顺序表表示2．给出它的转置矩阵B的三元组顺序表表示0 2 0 0 0 01 0 0 0 0 00 3 0 0 0 00 0 0 0 4 00 5 0 0 0 6答:ijv转置后(排序)ijv122121211212323233454255525544566656A.dataB.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=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）。答:#defineListSize100//假定表空间大小为100typedefintDataType;//假定DataType的类型为int型typedefstruct{DataTypedata[ListSize];//向量data用于存放表结点intlength;//当前的表长度}Seqlist;//顺序表结构定义同上题voidReverseList(Seqlist*L){DataTypetemp;//设置临时空间用于存放datainti;for(i=0;i<=L->length/2;i++)//L->length/2为整除运算{temp=L->data[i];//交换数据L->data[i]=L->data[L->length-1-i];L->data[L->length-1-i]=temp;}}十、写一算法，实现统计带表头的单链表中元素值为奇数的结点个数。答:单链表结点的类型定义如下:typedefintelemtype;//定义数据域的类型typedefstructLnode{//定