《C语言数据结构》第1至9章自测题答案大全53410.doc

《《C语言数据结构》第1至9章自测题答案大全53410.doc》由会员分享，可在线阅读，更多相关《《C语言数据结构》第1至9章自测题答案大全53410.doc（116页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、佳构文档你我共享如你想要领有完满得空的友情，能够一辈子寻不到冤家。第一章概论自测题谜底姓名班级题号一二三四五六总分题分3315982015100得分一、填空题每空1分共33分1.一个盘算机零碎包含硬件零碎跟软件零碎两年夜部分2.一台盘算机中全体次序的聚集称为这台盘算机的软件资本/零碎3.盘算机软件能够分为零碎软件跟运用软件两年夜类迷信盘算次序包属于运用软件诊断次序属于零碎软件东西4.5.一种用助忆标记来表现呆板指令的操纵符跟操纵数的言语是数据结构是一门研讨非数值盘算的次序计划咨询题中盘算机的汇编言语操纵东西以及它们之AAAAAA佳构文档你我共享间的关联跟运算等的学科6.数据结构被方法地界说为R

2、D此中D是数据元素关联的无限聚集R是D上的无限聚集7.数据结构包含数据的逻辑结构、数据的存储结构跟数据的运算这三个方面的内容8.数据结构按逻辑结构可分为两年夜类它们分不是线性结构跟非线性结构9.线性结构中元素之间存在一对一关联树形结构中元素之间存在一对多关联图形结构中元素之间存在多对多关联10在线性结构中第一个结点不先驱结点其余每个结点有且只要其余每个结点有且只要1个先驱结点；最初一个结点1个后续结点不后续结点11.在树形结构中树根结点不先驱其余每个结点有且只要结点1个先驱结点；叶子结点不后续结点其余每个结点的后续结点数能够恣意多个12.在图形结构中每个结点的先驱结点数跟后续结点数能够恣意多个

3、13数据的存储结构可用四种根本的存储办法表现它们分不是次序、链式、索引跟散列14.数据的运算最常用的有5种AAAAAA佳构文档你我共享它们分不是拔出、删除、修正、查寻、排序15.一个算法的效力可分为时间效力跟空间效力16.00年省统考任何一个C次序都由一个主函数跟假设干个被挪用的其余函数组成17.【00年省统考题】变量一经阐明就断定该变量的取值范畴即存储单位及断定变量所同意的运算二、单项选择题每题1分共15分B与硬盘C1.平日所说的主机是指A)CPUB)CPU跟内存C)CPU、内存与外存D)CPU、内存2.在盘算机外部所有信息的存取、处置跟传递的方法是A)ACSII码B)BCD码C)二进制D)

4、十六进制D3.软件与次序的区不是A)次序价钱廉价、软件价钱昂贵；B)次序是用户本人编写的而软件是由厂家供给的；C)次序是用初级言语编写的而软件是由呆板言语编写的；D)软件是次序以及开辟、运用跟保护所需求的所有文档的总称而次序只是软件的一部分C4.所谓裸机是指A)单片机B)单板机C)不配备任何软件的盘算机D)只配备操作零碎的盘算机D5.运用软件是指A)所有能够运用的软件B)能被各运用单位独特运用的某种软件AAAAAA佳构文档你我共享C)所有微机上都应运用的根本软件D)专门为某一运用目标而体例的软件A6.00年省统考C言语中的常量可分为整型常量、实型常量、字符型常量及(枚举)四种A标记常量B长整型

5、常量C逻辑常量D二进制整数C7.编译次序的功用是A)C)发觉源次序中的语法过错将源次序编译成目标次序B)矫正源次序中的语法过错D)将某一初级言语次序翻译成另一种初级言语次序AA)8.零碎软件中最主要的是操纵零碎B)言语处置零碎C)东西软件D)数据库管理零碎C9.可移植性最好的盘算机言语是A)呆板言语B)汇编言语C)初级言语D)天然言语B系10.非线性结构是数据元素之间存在一种：A一对多关联B多对多关联C多对一关联D一对一关C11.数据结构中与所运用的盘算机有关的是数据的结构；A)存储B)物理C)逻辑D)物理跟存储C12.算法剖析的目标是：A)寻出数据结构的合感性C)剖析算法的效力以求改良B)研

6、讨算法中的输入跟输入的关联剖析算法的易明白性跟文档性D)A13.算法剖析的两个要紧方面是：A)空间庞杂性跟时间庞杂性C)可读性跟文档性B)准确性跟扼要性D)数据庞杂性跟次序庞杂性C办法14.盘算机算法指的是：A)盘算办法B)排序办法C)处置咨询题的无限运算序列D)调理B15.盘算机算法必须存在输入、输入跟等5个特点A)可行性、可移植性跟可扩年夜性C)断定性、有穷性跟波动性B)可行性、断定性跟有穷性易读性、波动性跟平安性D)AAAAAA佳构文档你我共享三、简答题每题3分共9分1咱们明白盘算机只能履行呆板指令什么原因它能运转用汇编言语跟初级言语编写的次序？答：靠汇编次序将汇编言语或初级言语翻译转换

7、为目标次序即呆板言语2.【严题集1.2】数据结构跟数据范例两个不雅点之间有区不吗？答：庞杂地说数据结构界说了一组按某些关联联合在一同的数组元素数据范例不只界说了一组带结构的数据元素并且还在其上界说了一组操纵3.简述线性结构与非线性结构的差别点答：线性结构反应结点间的逻辑关联是一对一的非线性结构反应结点间的逻辑关联是多对多的四、00年统考题浏览以下C次序段写出响应的履行结果每题共8分4分1.printf(Inputx);scanf(%d&x);if(x20)y=x;elseif(x10)y=2*x;if(x0&xa13-a24-A30轮回链表单链表双向轮回链表双向链表四、简答题每题5分共10分1

8、.【严题集2.3】试比拟次序存储结构跟链式存储结构的优缺陷在什么状况下用次序表比链表好？答：次序存储时相邻数据元素的寄存地点也相邻延续的逻辑与物理一致；请求内存中可用存储单位的地点必须是长处：存储密度年夜1？存储空间应用率高缺陷：拔出或删除元素时不便利链式存储时相邻数据元素可随便寄存但所占存储空间分两部分一部分寄存结点值另一部分寄存表现结点间关联的指针长处：拔出或删除元素时非常便利运用灵敏缺陷：存储密度小datalink头指针首元结点简而言之头指针是指向链表中第一个结点或为头结点或为首元结点的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标记跟表长等信息内放头指针？那还得另

9、配一个头指针！首元素结点是指链表中存储线性表中第一个数据元素a1的结点五、【软考题】线性表存在两种存储方法即次序方法跟链接方法现有一个存在五个元素的线性表L=2317470531AAAAAA佳构文档你我共享假设它以链接方法存储在以下100119号地点空间中每个结点由数据占2个字节跟指针占2个字节构成如下所示：05U17X23V31Y47Z100120此中指针XYZ的值分不为几多？该线性表的首结点肇端地点为几多？末结点的肇端地点为几多？10分末址=答：X=116Y=0Z=100首址=108112六、浏览剖析题10分AAAAAA佳构文档你我共享【严题集2.10】指出以下算法中的过错跟低效即费时之处

10、并将它改写为一个既准确又高效的算法答：过错有两处：参数分歧法的判不前提不完好比方表长为10假设从第一地位i=1删除10个元素k=10请求公道但会被判为正当正当的进口参数前提为0ia.length(0ka.length-i)应将if(i1|ka.length)returnINFEASIBLE改为：if(！0=i+1;j-)a.elemj-1=a.elemj;改为for(j=i+1;j=a.length;j+)a.elemj-1=a.elemj;七、编程题每题10分共40分AAAAAA佳构文档你我共享1.【徐士良题集2002年1月省统考题】写出在次序存储结构下将线性表逆转的算法请求运用起码的附加空

11、间解：输入：长度为n的线性表数组A(1:n)输入：逆转后的长度为n的线性表数组A(1:n)C言语描绘如下此中ET为数据元素的范例：2.【严题集2.6】曾经明白L是无表头结点的单链表且P结点既不是首元结点也不是尾元结点请写出在P结点后拔出S结点的核心语句序列答：此题谜底不独一但假设从已给定序列当选择那么限度颇多(7)Q=P;(11)P=L;(8)while(P-next!=Q)P=P-next;(10)P=Q;(4)S-next=P-next;P-next=S;3.编写次序将假设干整数从键盘输入以单链表方法存储起来而后盘算单链表中结点的个数此中指针注：统计结点个数是【省统考样题】的请求也是课本P

12、604-6盘算链表长度的请求编程又庞杂P指向该链表的第一个结点非常轻易作为考题解：编写C次序如下(已上机经过)：全局变量及函数提早阐明：-#includeAAAAAA佳构文档你我共享#includetypedefstructliuyuintdata;structliuyu*link;test;liuyu*p*q*r*head;intm=sizeof(test);voidmain()/*第一步从键盘输入整数不时增加到链表*/inti;head=(test*)malloc(m);/*m=sizeof(test);*/p=head;i=0;while(i!=-9999)printf(/ninputa

13、nintegerstopby-9999:);scanf(%d&i);p-data=i;/*inputdataissaved*/p-link=(test*)malloc(m);/*m=sizeof(test);*/q=p;p=p-link;q-link=NULL;p=head;i=0;/*本来用p-link=NULL年夜概太晚！*/*统计链表结点的个数并打印出来*/while(p-link!=NULL)printf(%dp-data);p=p-link;i+;printf(nnodenumber=%dni-1);/*结点的个数不包含-9999*/0301陈建武：3.次序中统计结点数应是而不是i-

14、1.i个假设链表表长为ni从0开场那么在统计某一结点后i加一如今p已指向下一个结点AAAAAA佳构文档你我共享第一结点统计终了i为1p指向第二结点即当p指向尾结点(第n个结点)时i的值为n-1while轮回前提不符(指针域为null)加入轮回即得统计的结点数为n-1.因而i的值确实是结点数不用再减一4.请编写26个字母按特定字母值拔出或删除的完好次序可自行选用次序存储或链表结构答：#include#include/*全局变量及函数提早阐明：*/typedefstructliuyuchardata;structliuyu*link;test;liuyu*p*q*r*head;intL;/*元素的

15、个数*/intm=sizeof(test);voidbuild();/*主函数中会被挪用的函数该当事后阐明*/voiddisplay();intinsert_char(charchar);/*拔出一个字母在第字母Y之前假设无字母那么加到末端*/intdelet_char(char);/*删除元素X留意保管X的前趋元素指针！*/*-*/voidbuild()/*字母链表的天生*/inti;head=(test*)malloc(m);p=head;/*m=sizeof(test);*/for(i=1;idata=i+a-1;/*a也可用其ASCII码97来表现*/p-link=(test*)mal

16、loc(m);p=p-link;/*m=sizeof(test);*/p-data=i+a-1;p-link=NULL;AAAAAA佳构文档你我共享/*-*/voiddisplay()p=head;/*字母链表的输入*/while(p-link!=NULL)printf(%cp-data);p=p-link;printf(%cnp-data);/*-*/intinsert_char(charXcharY)/*拔出一个字母X在某个字母Y之前假设寻不到Y字母那么加到末端*/p=head;r=(test*)malloc(m);r-data=X;if(head-data=Y)head=r;r-link

17、=p;elsewhile(p-data!=Y)&(p-link!=NULL)q=p;p=p-link;if(p-data=Y)q-link=r;r-link=p;elsep-link=r;r-link=NULL;L+;return(0);/*-*/intdelet_char(charX)/*留意保管X的前趋元素指针！*/p=head;删除元素Xif(head-data=X)head=head-link;free(p);elsewhile(p-data!=X)&(p-link!=NULL)q=p;p=p-link;if(p-data=X)q-link=p-link;free(p);elseret

18、urn(-1);L-;return(0);AAAAAA佳构文档你我共享/*-*/voidmain(void)L=26;/*字母线性表的天生跟输入*/build();display();printf(insertreturnvalue=%dninsert_char(LW);display();printf(deletereturnvalue=%dndelet_char(z);display();附：屏幕上表现的履行结果是：abcdefghijklmnopqrstuvwxyzinsertreturnvalue=0abcd9efghijklmnopqrstuvwxyzLdeletereturnval

19、ue=0abcdefghijklmnopqrstuvwxyL0301陈建武修正看法：一.display()voiddisplay()p=head;函数代码可优化为四行/*字母链表的输入*/while(p-link!=NULL)/因为当p指向尾结点时p不为null改为while(p)前提成破轮回/printf()而后p被赋值为null如今轮回前提不符加入恰好.printf(%cp-data);p=p-link;printf(%cnp-data);/此行可删用while(p)AAAAAA佳构文档你我共享二.对intinsert_char(charXcharY)假设用带头结点的链表代码可减为10行我

20、的次序如下(假设参数不slistp代码要多一行让q指向头指针)voidInsertFind(slistpcharinsertcharcharinsertpos)/字母insertpos前拔出字母insertcharslistppriornewnode;/newnode新结点pprior为拔出地位结点的直截了以后驱newnode=newliuyu;newnode-data=insertchar;/while(p)/为新结点调配内存对结点数据域初始化/当p指向尾结点时最初一次轮回重新指针开场pprior=p;/pprior指向p的直截了以后驱p=p-next;/p从首元结点开场不时前移直至最初p为

21、nullif(p&(p-data=insertpos)/当p为null或许结点p的数据域为所要拔出的字母break;/那么加入轮回newnode-next=pprior-next;/pprior-next=newnode;在寻到的地位前拔出对删除结点的操纵假设有头结点异样能够增加代码由此可见创破一个头结点对简化次序有非常年夜的协助.下面的不雅念仅供参考过错之处请指教!第3章栈跟行列自测卷谜底姓名班级AAAAAA佳构文档你我共享题号一二三四五六总分题分151020202015100得分一、填空题每空1分共15分1.【李春葆】向量、栈跟行列基本上线性结构能够在向量的任何地位拔出跟删除元素；关于栈只

22、能在栈顶拔出跟删除元素；关于行列只能在队尾拔出跟队首删除元素2.栈是一种专门的线性表同意拔出跟删除运算的一端称为栈顶差别意拔出跟删除运算的一端称为栈底3.行列是被限制为只能在表的一端进展拔出运算在表的另一端进展删除运算的线性表4.在一个轮回行列中队首指针指向队首元素的前一个地位5.在存在n个单位的轮回行列中队满时共有n-1个元素AAAAAA佳构文档你我共享6.向栈中压入元素的操纵是先挪动栈顶指针后存入元素7.从轮回行列中删除一个元素时其操纵是先挪动队首指针后掏出元素8.00年统考题带表头结点的空轮回双向链表的长度即是0解：二、推断正误推断以下不雅点的准确性并作出扼要的阐明每题1分共10分1.线

23、性表的每个结点只能是一个庞杂范例而链表的每个结点能够是一个庞杂范例错线性表是逻辑结构不雅点能够次序存储或链式存储与元素数据范例有关2.在表结构中最常用的是线性表栈跟行列不太常用错不必定吧？挪用子次序或函数常用CPU中也用行列3.栈是一种对所有拔出、删除操纵限于在表的一端进展的线性表是一种落后先出型结构4.关于差其余运用者一个表结构既能够是栈也能够是行列也能够是线性表准确基本上线性逻辑结构AAAAAA佳构文档你我共享栈跟行列事实上是专门的线性表对运算的界说略有差别罢了5.栈跟链表是两种差其余数据结构错栈是逻辑结构的不雅点是专门殊线性表而链表是存储结构不雅点二者不是同类项6.栈跟行列是一种非线性数

24、据结构错他们基本上线性逻辑结构栈跟行列事实上是专门的线性表对运算的界说略有差别罢了7.栈跟行列的存储方法既但是次序方法也但是链接方法8.两个栈共享一片延续内存空间时为进步内存应用率增加溢出时机应把两个栈的栈底分不设在这片内存空间的两头9.队是一种拔出与删除操纵分不在表的两头进展的线性表是一种进步后出型结构错后半句过错10.一个栈的输入序列是12345那么栈的输入序列不克不及够是12345错有能够三、单项选择题每题1分共20分B1.00年元月统考题栈中元素的收支原那么是AAAAAA佳构文档你我共享进步先出落后先出栈空那么进栈满那么出C2.李春葆假设曾经明白一个栈的入栈序列是 123.n其输入序列

25、为p1p2p3.pn假设p1=n那么pi为in=in-i+1不断定说明：当p1=n即n是开始出栈的依照栈的道理n肯定是最初入栈的那么输入次序肯定是123.n那么出栈的序列是n.321B3.李春葆断定一个栈ST-top0ST最多元素为m0为空的前提是ST-top=0ST-topm0ST-top=m0B4.李春葆断定一个行列QU最多元素为m0为满行列的前提是QU-rearQU-frontQU-rearQU-front=m01=m0QU-front=QU-rearQU-front=QU-rear+1D5数组用来表现一个轮回行列为以后行列头元素的前一地位为队尾元素的地位AAAAAA佳构文档你我共享假设

26、行列中元素的个数小于盘算行列中元素的公式为rf;nfr%n;nrf;nrf%n6.【98初程P71】从供选择的谜底中选出应填入下面表白？内的最确实的解答把响应编号写在答卷的对应栏内设有4个数据元素a1、a2、a3跟a4对他们分不进展栈操纵或队操纵在进栈或进队操纵时按a1、a2、a3、a4次第每次进入一个元素假设栈或队的初始形状基本上空现要进展的栈操纵是进栈两次出栈一次再进栈两次出栈一次；这时第一次出栈掉掉落的元素是第二次出栈掉掉落的元素是AB是；相似地思索对这四个数据元素进展的队操纵是进队两次出队一次再进队两次出队一次；这时第一次出队掉掉落的元素是第二次出队掉掉落的元素是经操纵后CD最初在栈中

27、或队中的元素另有E个供选择的谜底：AD：a1a2a33a40E：12答：ABCDE241227.【94初程P75】从供选择的谜底中选出应填入下面表白？内的最确实的解答把响应编号写在答卷的对应栏内AAAAAA佳构文档你我共享栈是一种线性表它的特色是A设用一维数组A1.n来表现一个栈An为栈底用整型变量T唆使以后栈顶地位AT为栈顶元素往栈中推入PUSH一个新元素时变量T的值B变量T的值C设栈空时；从栈中弹出POP一个元素时有输入序列abc经过PUSHPOPPUSHPUSHPOP操纵后从栈中弹出的元素的序列是变量T的值是ED供选择的谜底：A：进步先出B落后先出进优于出出优于进随机收支C：加1D：a减

28、1稳定清0加2减2bcaabcbcbcaE：n+1n+2nn-1n-2谜底：ABCDE=22164留意向地点的高端成长称为向上天生客栈；向地点低端成长叫向下天生客栈AAAAAA佳构文档你我共享此题中底部为n向地点的低端递加天生称为向下天生客栈8.【91初程P77】从供选择的谜底中选出应填入下面表白？内的最确实的解答把响应编号写在答卷的对应栏内在做进栈运算时应先判不栈是否A应先判不栈是否B当栈中元素为n个做进栈运算时发作上溢那么阐明该栈的最年夜容量为；在做退栈运算时C为了增加内存空间的应用率跟增加溢出的能够性由两个栈共享一片延续的内存空间时应将两栈的D分不设在这片内存空间的两头如此只要当E时才发

29、生上溢供选择的谜底：AB：空满上溢n+1栈顶下溢C：D：n-1nn/2长度深度栈底E：两个栈的栈顶同时抵达栈空间的核心点此中一个栈的栈顶抵达栈空间的核心点两个栈的栈顶在达栈空间的某一地位相遇两个栈均不空且一个栈的栈顶抵达另一个栈的栈底谜底：ABCDE21243四、简答题每题4分共20分1.【严题集3.2跟3.11】阐明线性表、栈与队的异同点刘答：一样点：基本上线性结构AAAAAA佳构文档你我共享基本上逻辑结构的不雅点都能够用次序存储或链表存储；栈跟行列是两种专门的线性表即受限的线性表只是对拔出、删除运算加以限度差别点：运算规那么差别线性表为随机存取而栈是只同意在一端进展拔出、删除运算因而是落后

30、先出表LIFO；行列是只同意在一端进展拔出、另一端进展删除运算因而是进步先出表FIFO用处差别客栈用于子程挪用跟爱护现场行列用于多道功课处置、指令寄存及其余运算等等2.【统考书P604-11难于严题集3.1】设有编号为1234的四辆列车次序进入一个栈式结构的车站详细写出这四辆列车开出车站的所有能够的次序刘答：至少有14种全进之后再出状况只要1种：4321进3个之后再出的状况有3种342132413214AAAAAA佳构文档你我共享进2个之后再出的状况有5种24312341213421432134进1个之后再出的状况有5种143213241342123412433.【刘自编】假设正读跟反读都一样

31、的字符序列为回文比方abba跟abcba是回文abcde跟ababab那么不是回文假设一字符序列已存入盘算机请剖析用线性表、客栈跟行列等方法准确输入其回文的能够性？AAAAAA佳构文档你我共享答：线性表是随机存储能够实现靠轮回变量j-从表尾开场打印输入；客栈是落后先出也能够实现靠正序入栈、逆序出栈即可；行列是进步先出不易实现哪种方法最好要详细状况详细剖析假设注释在机内已是次序存储那么直截了当用线性表从后往前读取即可或将客栈栈顶开到数组末端而后直截了当用POP举措实现但客栈是先减后压依然.假设注释是单链表方法存储那么同即是行列需开辅佐空间能够从链首开场入栈全体压入后再顺次输入4.【统考书P604

32、-13】次序队的假溢出是怎么样发生的？怎样明白轮回行列是空依然满？答：普通的一维数组行列的尾指针曾经到了数组的上界不克不及再有入队操纵但事实上数组中另有空地位这就叫假溢出采纳轮回行列是处置假溢出的道路其余处置队满队空的办法有三：设置一个布尔变量以区不队满依然队空；白费一个元素的空间用于区不队满依然队空运用一个计数器记载行列中元素个数即行列长度咱们常采纳法即队头指针、队尾指针中有一个指向实元素而另一个指向闲暇元素AAAAAA佳构文档你我共享推断轮回行排队空标记是：f=rear队满标记是：f=(r+1)%N40序号从0到395.【统考书P604-14】设轮回行列的容量为现经过一系列的入队跟出队运算

33、后有front=11rear=19;front=19rear=11；咨询在这两种状况下轮回行列中各有元素几多个？答：用行列长度盘算公式：L=401911%40=8(Nrf)%NL=401119%40=32五、浏览了解每题共20分5分至少要写出思绪1.【严题集3.7】依照四那么运算加、减、乘、除跟幂运算优先关联的常规并模仿课本例3-2的格局画出对以下算术表白式求值时操纵数栈跟运算符栈的变更进程：ABC/D+EF答：2.【严题集3.3】写出以下次序段的输入结果栈的元素范例SElemType为charvoidmain()StackS;Charxy;InitStack(S);X=c;y=k;Push(

34、Sx);Push(Sa);Push(Sy);Pop(Sx);Push(St);Push(Sx);Pop(Sx);Push(Ss);AAAAAA佳构文档你我共享while(!StackEmpty(S)Pop(Sy);printf(y);Printf(x);答：输入为stack3.【严题集3.12】写出以下次序段的输入结果行列中的元素范例QElemType为charvoidmain()QueueQ;InitQueue(Q);Charx=e;y=c;EnQueue(Qh);EnQueue(Qr);EnQueue(Qy);DeQueue(Qx);EnQueue(Qx);DeQueue(Qx);EnQu

35、eue(Qa);while(!QueueEmpty(Q)DeQueue(Qy);printf(y);Printf(x);答：输入为char4.【严题集3.13】简述以下算法的功用栈跟行列的元素范例均为intvoidalgo3(Queue&Q)StackS;intd;InitStack(S);while(!QueueEmpty(Q)DeQueue(Qd);Push(Sd);while(!StackEmpty(S)Pop(Sd);EnQueue(Qd);AAAAAA佳构文档你我共享答：该算法的功用是：应用客栈做辅佐将行列中的数据元素进展逆置六、算法计划每题共15分5分至少要写出思绪1.【李春葆及严

36、题集型的括弧3.19】假设一个算术表白式中包含圆括弧、方括弧跟花括弧三品种编写一个判不表白式中括弧是否准确配对的函数correct(exptag)；此中：exp为字符串范例的变量可了解为每个字符占用一个数组元素表现被判不的表白式tag为布尔型变量答：用客栈st进展断定将(、或入栈当碰到、或)时反省以后栈顶元素是否是对应的假设是那么退栈(、或否那么前往表现不配对当全部算术表白式反省终了时假设栈为空表现括号准确配对否那么不配对编程后的全部函数如下李书P31-32#definem0100/*m0correct(exptag)为算术表白式中最多字符个数*/charexpm0;inttag;charst

37、m0;inttop=0i=1;tag=1;while(i0)tag=0;/*那么不配对*/假设栈不空严题集对应对案：3.19StatusAllBrackets_Test(char*str)/判不表白式中三种括号是否婚配InitStack(s);for(p=str;*p;p+)if(*p=(|*p=|*p=)push(s*p);elseif(*p=)|*p=|*p=)if(StackEmpty(s)returnERROR;pop(sc);if(*p=)&c!=()returnERROR;if(*p=&c!=)returnERROR;if(*p=&c!=)returnERROR;/必须与以后栈顶括

38、号婚配AAAAAA佳构文档你我共享/forif(!StackEmpty(s)returnERROR;returnOK;/AllBrackets_Test2.【统考书P604-15】假设一个数组squm寄存轮回行列的元素假设要使这m个重量都掉掉落应用那么需另一个标记tag以tag为0或1来辨别尾指针跟头指针值一样时行列的形状是空依然满试编写响应的入队跟出队的算法解：这确实是处置队满队空的三种办法之见简答题；设置一个布尔变量以区不队满依然队空其余两种思绪：一开场队空设tag=0假设从rear一端加到与front指针一样时表现入队已满那么令tag=1；假设从front一端加到与rear指针一样时那么

39、令tag=0表现出队已空3.【严题集3.31】试写一个算法判不读入的一个以为终了符的字符序列是否是回文答：编程如下：intPalindrome_Test()/判不输入的字符串是否回文序列是那么前往1否那么前往0InitStack(S);InitQueue(Q);while(c=getchar()!=)Push(Sc);EnQueue(Qc);/同时运用栈跟行列两种结构while(!StackEmpty(S)Pop(Sa);DeQueue(QAAAAAA佳构文档你我共享b);if(a!=b)returnERROR;returnOK;/Palindrome_Test第45章串跟数组自测卷谜底姓名班

40、级题号一二三四五总分题分2015201530100得分一、填空题每空1分共20分1.不包含任何字符长度为0的串称为空串；由一个或多个空格仅由空格符构成的串称为空缺串对应严题集4.1简答题：简述空串跟空格串的区不2.设S=A;/document/Mary.doc那么strlen(s)=20/的字符定位的地位为3AAAAAA佳构文档你我共享4.子串的定位运算称为串的方法婚配；被婚配的主串称为目标串子串称为方法5.设目标T=abccdcdccbaa方法P=cdcc那么第6次婚配胜利6.假设n为主串长m为子串长那么串的古典朴实婚配算法最坏的状况下需求比拟字符的总次数为(n-m+1)*m7.假设有二维数

41、组A68每个元素用相邻的6个字节存储存储器按字节编址曾经明白A的肇端存储地位基地点为 1000那么数组A的体积存储量为288B；末端元素A57的第一个字节地点为1282；假设按行存储时元素A14的第一个字节地点为元素A47的第一个字节地点为(8+4)6+1000=1192；假设按列存储时(674)6100012768.00年盘算机系考研题设数组1.70的基地点为2048a1.60每个元素占2个存储单位假设以列序为主序次序存储那么元素a3258的存储地点为9188答：思索0行0列58列61行32行2字节基址2048=9188？9.三元素组表中的每个结点对应于稀少矩阵的一个非零元素它包含有三个数据

42、项分不表现该元素的行下标、列下标跟元素值10.求以下狭义表操纵的结果：AAAAAA佳构文档你我共享1GetHead【(ab)(cd)】=(ab);/头元素不用加括号2GetHead【GetTail【(ab)(cd)】=(cd);3GetHead【GetTail【GetHead【(ab)(cd)】=b;4GetTail【GetHead【GetTail【(ab)(cd)】=d;二、单项选择题每题 1分共15分B1.李串是一种专门的线性表其专门性表白在：能够次序存储数据元素是一个字符能够链式存储数据元素能够是多个字符B2.李设有两个串p跟q求q在p中初次呈现的地位的运算称作：衔接方法婚配求子串求串长

43、D3.李设串s1=ABCDEFGs2=PQRST函数con(xy)前往x跟y串的衔接串subs(sij)前往串s的从序号i开场的j个字符构成的子串len(s)前往串s的长度那么con(subs(s12len(s2)subs(s1len(s2)AAAAAA佳构文档你我共享2)的结果串是：BCDEFBCDEFGBCPQRSTBCDEFEF解：con(xy)前往x跟y串的衔接串即con(xy)ABCDEFGPQRST；subs(sij)前往串s的从序号i开场的j个字符构成的子串那么subs(s12len(s2)2subs(s15)=BCDEF;subs(s1len(s2)2)subs(s152)=E

44、F;因而con(subs(s12len(s2)subs(s1len(s2)2)con(BCDEFEF)之衔接即BCDEFEFA4.01年盘算机系考研题假设有60行70列的二维数组a1.601.70以列序为主序次序存储其基地点为10000每个元素占2个存储单位那么第32行第58列的元素a3258的存储地点为无第0行第0列元素169021690414454谜底ABC均过错答：57列60行31行2字节10000=16902(A)(B)5.设矩阵A是一个对称矩阵为了节约存储将其下三角部分如以下列图所示按行序寄存在一维数组B1AAAAAA佳构文档你我共享n(n-1)/2中对下三角部分中任一元素aij(i

45、j)在一维数组B中下标k的值是：i(i-1)/2+j-1i(i-1)/2+ji(i+1)/2+j-1i(i+1)/2+j6.【91初程P78】从供选择的谜底中选出应填入下面表白？内的最确实的解答把响应编号写在答卷的对应栏内有一个二维数组A行下标的范畴是0到8列下标的范畴是1到5每个数组元素用相邻的存储器按字节编址4个字节存储假设存储数组元素A01的第一个字节的地点是0存储数组A的最初一个元素的第一个字节的地点是A假设按行存储那么A35跟A53的第一个字节的地点分不是假设按列存储BD跟C那么A71跟A24的第一个字节的地点分不是跟E供选择的谜底AE：28116447617692184108188

46、132谜底：ABCDE=835167.【94程P12】从供选择的谜底中选出应填入下面表白？内的最确实的解答AAAAAA佳构文档你我共享把响应编号写在答卷的对应栏内有一个二维数组A行下标的范畴是1到6列下标的范畴是0到7每个数组元素用相邻的存储器按字节编址那么6个字节存储谁人数组的体积是A个字节假设存储数组元素A10的第一个字节的地点是0那么存储数组A的最初一个元素的第一个字节的地点是B假设按行存储那么A24的第一个字节的地点是假设按列存储CD那么A57的第一个字节的地点是供选择的谜底AD：121566672961141202342762821128312288谜底：ABCD=121039三、简

47、答题每题5分共15分1.KMP算法的计划思维是什么？它有什么长处？2.软件技巧？曾经明白二维数组m采纳按行优先次序寄存每个元素占K个存储单位同时第一个元素的存储地点为请写出求Loc(aij)的盘算公式假如采纳列优先次序寄存呢？解：公式课本已给出AmLoc(a11)此处虽是方阵但行列公式仍纷歧样；按行存储的元素地点公式是：Loc(aij)=Loc(a11)+(i-1)*m+(j-1)*KAAAAAA佳构文档你我共享按列存储的元素地点公式是：Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K3.【天下专升本资历测验】递归算法比非递归算法破费更多的时间对吗？什么原因？答：不必定时间庞

48、杂度与样本个数n有关是指最深层的履行语句消耗时间而递归算法与非递归算法在最深层的语句履行上是不区不的轮回的次数也不太年夜差别仅仅是断定轮回是否接着的方法差别递归用栈隐含轮回次数非递归用轮回变量来表现轮回次数罢了四、盘算题每题5分共20分1.设s=IAMASTUDENTt=GOODq=WORKER求WordStr(sSTUDENTq)跟Concat(SubString(s62)Concat(tSubString(s78)解：WordStr(sSTUDENTq)IAMAWORKER因为SubString(s62)A；SubString(s78)STUDENTConcat(tSubString(s7

49、AAAAAA佳构文档你我共享8)GOODSTUDENT因而Concat(SubString(s62)Concat(tSubString(s78)AGOODSTUDENT2.【严题集4.8】曾经明白主串s=ADBADABBAABADABBADADA方法串pat=ADABBADADA写出方法串的nextval函数值并由此画出KMP算法婚配的全进程解：由演示次序得悉nextval函数值为0102101040在第12个字符处发觉匹配！s=ADBADABBAABADABBADADApat=ADABBADADA3.P604-18用三元组表表现以下稀少矩阵：解：拜见填空题4.三元素组表中的每个结点对应于稀少

50、矩阵的一个非零元素它包含有三个数据项分不表现该元素的行下标、列下标跟元素值因而1可列表为：2可列表为：8853233685467858AAAAAA佳构文档你我共享124.P604-19以下各三元组表分不表现一个稀少矩阵试写出它们的稀少矩阵解：1为64矩阵非零元素有6个但此中一数下标有误？2为45矩阵非零元素有5个五、算法计划题每题10分共30分1.【严题集4.12】编写一个实现串的置换操纵WordStr(&STV)的算法解：intWordStr(Stringtype&SStringtypeTStringtypeV);/将串S中所有子串T交流为V并前往置换次数for(n=0i=1;inext);