数据机构专业习题课及答案

1习题练习第一章绪论1、voidmaxtrixmult(intn,inta[][100],intb[][100],intc[][100]){intj,k,r;intx;for(r=0;r=n;r++)1)n+2{for(j=0;j=n;j++)2)(n+1)*(n+2){x=0;3)(n+1)2for(k=1；k=n;k++)4)(n+1)3x+=a[r][k]*[k][j];5)n*(n+1)2c[r][j]=x;6)(n+1)2}}}计算时间每条语句的频度和该算法的时间复杂度2．一个算法应该是（B）。【中山大学1998二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.3.下面说法错误的是（C）【南京理工大学2000一、2（1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1)B.(1),(2)C.(1),(4)D.(3)4．从逻辑上可以把数据结构分为（C）两大类。【武汉交通科技大学1996一、4（2分）】2A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构5．以下与数据的存储结构无关的术语是（D）。【北方交通大学2000二、1（2分）】A．循环队列B.链表C.哈希表D.栈6．连续存储设计时，存储单元的地址（A）。【中山大学1999一、1（1分）】A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续7.数据元素是数据的最小单位。(F)【北京邮电大学1998一、1（2分）】【青岛大学2000一、1（1分）】【上海交通大学1998一、1】【山东师范大学2001一、1（2分）】8.记录是数据处理的最小单位。(F)【上海海运学院1998一、5（1分）】9.在顺序存储结构中，有时也存储数据结构中元素之间的关系。(F)【华南理工大学2002一、2（1分）】10.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(F)【上海海运学院1999一、1（1分）】11.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.(F)【上海海运学院1998一、1（1分）】12．一个数据结构在计算机中映像称为存储结构。【华中理工大学2000一、1（1分）】13.下面程序段中带下划线的语句的执行次数的数量级是：log2n【合肥工业大学1999三、1（2分）】i：=1；WHILEinDOi：=i*2;14.下面程序段中带下划线的语句的执行次数的数量级是(.log2n)。3【合肥工业大学2000三、1（2分）】i:=1;WHILEinBEGINFORj:=1TOnDOx:=x+1;i:=i*2END；第二章线性表1．线性表是具有n个（C）的有限序列（n0）。【清华大学1998一、4（2分）】A．表元素B．字符C．数据元素D．数据项E．信息项2．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。【哈尔滨工业大学2001二、1（2分）】A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表3．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。【南开大学2000一、3】A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表4．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D)最节省时间。4A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表5.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C）(1=i=n+1)。【北京航空航天大学1999一、1（2分）】A.O(0)B.O(1)C.O(n)D.O(n2)6．线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（C）A．O（i）B．O（1）C．O（n）D．O（i-1）【中山大学1999一、2】7．非空的循环单链表head的尾结点p↑满足（A）。【武汉大学2000二、10】A．p-next=headB．p-next=NILC．p=NILD．p=head8．循环链表H的尾结点P的特点是（A）。【中山大学1998二、2（2分）】A．P-NEXT=HB．P-NEXT=H-NEXTC．P=HD．P=H-NEXT9．在一个以h为头的单循环链中，p指针指向链尾的条件是（A）【南京理工大学1998一、15（2分）】A.p-next=hB.p-next=NILC.p-next-next=hD.p-data=-110．完成在双循环链表结点p之后插入s的操作是（D）；【北方交通大学1999一、4（3分）】A．p-next=s;s-priou=p;p-next-priou=s;s-next=p-next;B．p-next-priou=s;p-next=s;s-priou=p;s-next=p-next;C．s-priou=p;s-next=p-next;p-next=s;p-next-priou=s;5D．s-priou=p;s-next=p-next;p-next-priou=s;p-next=s;11．在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是(C)。【北京邮电大学1998二、2（2分）】注:双向链表的结点结构为(llink,data,rlink)。供选择的答案：A．p-llink=q；q-rlink=p；p-llink-rlink=q；q-llink=q；B．p-llink=q；p-llink-rlink=qq-rlink=pq-llink=p-llink；C．q-rlink=p；q-llink=p-llinkp-llink-rlink=q;p-llink=q;D．q-llink=p-llink；q-rlink=p；p-llink=q；p-llink=q；12.线性表的特点是每个元素都有一个前驱和一个后继。(F)【合肥工业大学2001二、1（1分）】13．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是__（n-1）/2____。插入是n/2【北方交通大学2001二、9】14．在一个长度为n的顺序表中第i个元素（1=i=n）之前插入一个元素时，需向后移动______N-I+1__个元素。15、从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（N+1）/2个结点【北京工商大学2001二、4（4分）】16.带头结点的双循环链表L中只有一个元素结点的条件是：6_L-next-next==L___【合肥工业大学1999三、32000三、2（2分）】17.在单链表L中，指针p所指结点有后继结点的条件是：．p-next!=null__【合肥工业大学2001三、3（2分）】18设有一带头结点的单链表,编程将链表颠倒过来.要求不用另外的数组或结点完成.【南京航空航天大学1999八（10分）】（1）要求编程实现带头结点的单链表的逆置。首先建立一单链表，然后逆置。typedefstructnode{intdata；∥假定结点数据域为整型。structnode*next；}node,*LinkedList；LinkedListcreat（）{LinkedListhead，pintx；head=（LinkedList）malloc（sizeof（node））；head-next=null；/*设置头结点*/scanf（“%d”，&x）；while（x!=9999）/*约定输入9999时退出本函数*/{p=（LinkedList）malloc（sizeof（node））；p-data=x；p-next=head-next；/*将新结点链入链表*/head-next=p；scanf（“%d”，&x）；}7return（head）；}∥结束creat函数。LinkedListinvert1（LinkedListhead）/*逆置单链表*/{LinkedListp=head-next;/*p为工作指针*/head-next=null；while（p!=null）{r=p-next；/*暂存p的后继*/p-next=head-next；head-next=p；p=r；}return（head）；}/*结束invert1函数*/main（）{LinkedListla；la=creat(）；/*生成单链表*/la=invert1（la）；/*逆置单链表*/}19、设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相8同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。【清华大学1997二（10分）】[题目分析]首先在双向链表中查找数据值为x的结点，查到后，将结点从链表上摘下，然后再顺结点的前驱链查找该结点的位置。DLinkListlocate(DLinkListL，ElemTypex)∥L是带头结点的按访问频度递减的双向链表，本算法先查找数据x,查找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中适当位置。{DLinkListp=L-next,q;∥p为L表的工作指针，q为p的前驱，用于查找插入位置。while(p&&p-data!=x)p=p-next;∥查找值为x的结点。if(!p){printf(“不存在值为x的结点\n”);exit(0);}else{p-freq++;∥令元素值为x的结点的freq域加1。p-next-pred=p-pred;∥将p结点从链表上摘下。p-pred-next=p-next;q=p-pred;∥以下查找p结点的插入位置while(q!=L&&q-freqp-freq)q=q-pred;p-next=q-next;q-next-pred=p;∥将p结点插入p-pred=q;q-next=p；}return(p);∥返回值为x的结点的指针}∥算法结束9第三章栈和队列1、判定一个循环队列QU（最多元素为m0）为空的条件QU.rear==QU.front2、判定一个循环队列QU（最多元素为m0）为满的条件QU.front==(QU.rear+1)%m03、一个循环队列QU（最多元素为m0）队列满时，队列中有m0-1个元素4.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（B）。A.不确定B.n-i+1C.iD.n-i【中山大学1999一、9(1分)】5.若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（D）。A.i-j-1B.i-jC.j-i+1D.不确定的【武汉大学2000二、3】6.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（B）。A.23415B.54132C.23145D.15432【南开大学2000一、1】【山东大学2001二、4(1分)】【北京理工大学2000一、2（2分）】7.某堆栈的输入序列为a,b