数据结构习题1.docx
一.判断题
01.某线性表采用顺序存储结构，元素长度为4,首地址为100,则下标为
12的(第13个)元素的存储地址为148。
正确。第0个元素地址为100,则第i个元素地址为100+4*i，将12代入得148。
02.在任何一种线性表上都无法进行随机访问。
错误。比如只要知道顺序表首地址和每一个数据元素所占存储单元的个数，就可以求出第i个数据元素的存储地址来，这也是顺序表具有按数据元素的序号随机存
取的特点。
()3.循环链表中每一个元素都有后继。
正确。注意，这里可能有笔误，应写为“循环链表”而非“循环列表”。
二.填空题。
.下面程序的时间复杂度为o
for(inti=1;i=m;i++)
for(intj=1;j=n;j++)S+=i
法则1：for循环：一个for循环的运行时间至多是该for循环内语句(包含测试)的运行时间乘以迭代的次数。
法则2:嵌套循环：从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有循环的大小的乘积。
对于此处嵌套的for循环，根据以上法则，时间复杂度为0(m*n)。
.在长度为n的顺序表的第个位置上插入一个元素，元素的挪移次数是o
从第i个元素(原来的)到第n个元素，每一个元素后移一位，一共需要n+1-i次。8.在一个具有n个结点的有序单链表中插入一个新结点，并让插入后的单链表仍然有序，则该操作的时间复杂性数量级为o
找到节点位置，0(n);单链表插入操作，0(n);总的时间复杂度为0(n+n)=0(n)。
设n为正整数。计算下面几段代码的时间复杂度。
(l)i=l;k=0;
while(i=n-1){
@k+=10*i;i++
)
(2)i=l;k=0;
do{
解：
StatusCompareOrderList(SqListA,SqListB){
inti,kj;
k=A.lengthB.length?A.length:B.length;
for(i=0;ik;i++){
if(A.elem[i]B.elem[i])j=l;
if(A.elem[i]B.elem[i])j=-1;
if(A.lengthk)j=l;
if(B.lengthk)j=-1;
if(A.length=B.length)j=O;
returnj;}
试写一算法在带头结点的单链表结构上实现线性表操作Located,x)
解：
intLocateElem_L(LinkListL,ElemTypex){
inti=0;
LinkListp=L;
while(pp-data!=x){
p=p-next;
i++；
if(!p)return0;
elsereturni;
试写一算法在带头结点的单链表结构上实现线性表操Length(L)。
解：
〃返回单链表的长度
intListLength_L(LinkListL){
inti=0;
LinkListp=L;
if(p)p=p-next;
while(p){
p=p-next;
i++；
returni;
已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算将这两个链表连接在一起，假设指针he指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。
解：
voidMergeList_L(LinkListha,LinkListhb,LinkListhc)
LinkListpa,pb;
pa=ha;
pb=hb;
while(pa-nextpb-next){
pa=pa-next;
pb=pb-next;
if(!pa-next){
hc=hb;
while(pb-next)pb=pb-next;
pb-next=ha-next;
}else{
hc=ha;
while(pa-next)pa=pa-next;
pa-next=hb-next;
已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第中i个元素起共len个元素后，将它们插入到表lb中第中第中第中第i个元素之前。试问此算法是否正确?若有错，请改正之。
StatusDeleteAndInsertSub(LinkedListla,LinkedListIbjnti,intj,intlen){
if(i011j01Ilen0)returnINFEASIBLE;
p=la;k=l;
while(ki){p=p-next;k++;}
q=p;
while(k=len){q=q-next;k++;}
s=lb;k=l;
while(kj){s=s-ne