数据结构复习习题

1数据结构期末考试题型：判断题、选择题、填空题、综合题、算法设计题第一章1.算法的优劣与算法描述语言无关，但与所用计算机有关。（×）2．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（√）3.算法的时间复杂度取决于问题的规模和待处理数据的初态。（√）1.从逻辑上可以把数据结构分为C两大类。A）动态结构、静态结构B）顺序结构、链式结构C）线性结构、非线性结构D）初等结构、构造型结构2．算法必须具备输入、输出和_____C______。A）计算方法B）排序方法C）解决问题的有限运算步骤D）程序设计方法1.数据结构被形式地定义为（D,R），其中D是数据的有限集合，R是D上关系的有限集合。2．一个算法的效率可分为时间效率和空间效率。。第二章顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（×）1.下面关于线性表的叙述中，错误的是哪一个？（B）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。2.设单链表中指针p指向结点a，若要删除p之后的结点（若存在），则需修改指针的操作为（A）。Ap-next=p-next-nextBp=p-nextCp=p-next-nextDnext=p4.循环链表H的尾结点P的特点是（A）。A．P^.NEXT:=HB．P^.NEXT:=H^.NEXTC．P:=HD．P:=H^.NEXT5.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（B）。A．p-next=s;s-next=p-next;B．s-next=p-next;p-next=s;C．p-next=s;p-next=s-next;D．p-next=s-next;p-next=s;6、在下面的程序段中，对x的赋值语句的频度为C。FORi:=1TOnDOFORj:=1TOnDOx:=x+1;2A）O(2n)B）O(n)C）O(n2)D）O(log2n)7.于一个头指针为head的带头结点的单链表，判定该表为空表的条件是B。A）head==NULLB）head→next==NULLC）head→next==headD）head!=NULL1、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，请为以下操作填写合适的语句。（上课讲过的题目，自己解答掌握）⑴、在P结点后插入S结点的语句序列是________⑵、在P结点前插入S结点的语句序列是________⑶、在表首插入S结点的语句序列是________⑷、在表尾插入S结点的语句序列是________(1)P-next=S;(2)P-next=P-next-next;(3)P-next=S-next;(4)S-next=P-next;(5)S-next=L;(6)S-next=NULL;(7)Q=P;(8)while(P-next!=Q)P=P-next;(9)while(P-next!=NULL)P=P-next;(10)P=Q;(11)P=L;(12)L=S;(13)L=P;1．已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。（上课讲过的题目，自己解答掌握）a.删除P结点的直接后继结点的语句序列是____________________。b.删除P结点的直接前驱结点的语句序列是____________________。c.删除P结点的语句序列是____________________。d.删除首元结点的语句序列是____________________。(1)P=P-next;(2)P-next=P;(3)P-next=P-next-next;(4)P=P-next-next;(5)while(P!=NULL)P=P-next;(6)while(Q-next!=NULL){P=Q;Q=Q-next;}(7)while(P-next!=Q)P=P-next;(8)while(P-next-next!=Q)P=P-next;(9)while(P-next-next!=NULL)P=P-next;(10)Q=P;(11)Q=P-next;(12)P=L;(13)L=L-next;(14)free(Q);1．写一算法，在带头结点的单链线性表L中第i个位置之前插入元素e。StatusListInsert_L(LinkList&L,inti,ElemTypee)/*在带头结点的单链表L中插入1个元素*/{p=L;j=0;while(p&&ji-1){p=p-next;++j;}if(!p||ji-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s-data=e;s-next=p-next;p-next=s;3returnOK;}//ListInsert_L2．写一算法，在带头结点的单链线性表L中，删除第i个元素，并由e返回其值。voidDelList(LinkListL,inti,ElemType*e)/*在带头结点的单链表L中删除第i个元素，并保存其值到变量*e中*/{Node*p,*r;p=L;intj=0;while(p-next!=NULL&&ji-1)/*寻找被删除结点i的前驱结点*/{p=p-next;j=j+1;}if(j!=i-1)/*即while循环是因为p-next=NULL而跳出的*/{printf(“删除结点的位置i不合理！”);returnERROR;}q=p-next;p-next=q-next；e=q-data;/*删除结点r*/free(r);/*释放被删除的结点所占的内存空间*/}3．写一算法，将两个具有相同结点个数的单链表x和y合并成新的链表z。例如：12nxx,x,,x和12nyy,y,,y，合并成新的链表1122nnzx,y,x,y,,x,y。NODE*addcross(NODE*a,NODE*b)/*交叉链接*/{NODE*r,*p,*q,*s,*c,*t;r=c=(NODE*)malloc(sizeof(NODE));r-next=NULL;p=a-next;/*p指向a链表的第一个结点*/q=b-next;/*q指向b链表的第一个结点*/while(p!=NULL){s=(NODE*)malloc(sizeof(NODE));/*复制一个a链表中的结点，链接到z中*/s-data=p-data;r-next=s;p=p-next;r=s;/*r始终指向c的最后一个结点*/t=(NODE*)malloc(sizeof(NODE));/*复制一个b链表中的结点，链接到c中*/t-data=q-data;r-next=t;q=q-next;r=t;}r-next=NULL;return(c);}4第三章1.假定利用数组A[N]顺序存储一个栈，top表示栈顶指针，已知栈未满，则x入栈时所执行的操作是（C）。Aa[--top]=x;Ba[top--]=xCa[++top]=xDa[top++]=x2.一个栈的入栈序列是a,b,c,d,e，则不可能的出栈序列是（B）。AedcbaBdceabCdecbaDabcde3.循环队列S为满的条件是（B）。AS-rear==S-frontB(S-rear+1)%maxsiae==s-frontCS-rear==0Ds-front==04、栈和队列的共同特点是A。A）只允许在端点处插入和删除元素B）都是先进后出C）都是先进先出D）没有共同点5．有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？C。A）543612B）453126C）346521D）2341564.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是__3___。5、若用一个大小为６的数组来实现循环队列，且当rear和front的值分别为０和３。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？2,4第四章第五章1.下面关于串的的叙述中，哪一个是不正确的？（B）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2.若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))其结果为（E）A．ABC###G0123B．ABCD###2345C．ABC###G2345D．ABC###2345E．ABC###G1234F．ABCD###1234G．ABC###012343.若串S=‘software’,其子串的数目是n*(n+1)/2=36。4.INDEX（‘DATASTRUCTURE’，‘STR’）=____5____。57.有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（B）。A.60B.66C.18000D.339.已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是(c)。A.head(tail(LS))B.tail(head(LS))C.head(tail(head(tail(LS)))D.head(tail(tail(head(LS))))10.广义表（a,（b,c）,d,e,（（f,g）,h））的长度为___5_____，深度为__3______。11.已知非空广义表L=（（（a,b）,c）,（d,（e,f））,g），用取表头head（L）和取表尾tail（L）函数，写出从L中取出元素a的运算_head（head（head（L）））=a___________。4．数组的第一个元素的存储地址是1500，每个元素长度是3，则第5个元素的地址是1512。5．广义表(a,(a,b),d,e,((i,j),k))的长度是__5_________。1．设有二维数组A[10][20]，其每个元素占2个字节，第一个元素A1,1的存储地址为100，1)则按行优先顺序存储时元素A6,6的存储地址为?2)若按列优先顺序存储时元素A6,6的存储地址为?解：按行优先A6,6=100+[(6-1)*20+(6-1)]*2=310按列优先A6,6=100+[((6-1)*10+(6-1)]*2=210第六章1、下述编码中哪一个不是前缀编码（B）A、｛00，01，10，11｝B、｛01，0，1，10｝C、｛0，10，110，111｝D、｛10，01，000，111｝2、在一棵具有n个结点的二叉树第I层上，最多具有___C__个结点。A.2IB.2I+1C.2I-1D.2n3、在线索化二叉树中，t所指节点没有左子树的充要条件是（C）A、t-left=NULLB、t-ltag=1C、t-ltag=1且t-left=NULLD、以上都不对5、设某通讯电文由A、B、C、D、E、F六个字符组成，它们在电文中出现的次数分别是16、5、9、3、30、1。试画出编码用的哈夫曼树。（自己解答必须要会）6．已知一个二叉树的先序序列和中序序列如下，请构造（画）出该二叉树，并给出其后序序列。（自己解答必须要会）先序序列：ABDGHJKECFIM6中序序列：GDJHKBEACFMI7．1）将下列由三棵树组成的森林转换为二叉树。（自己解答必须要