数据结构练习4.doc

栈和队列 习 题 41 判断题(在你认为正确的题后的括号中打，否则打X)。 (1)堆栈和队列都是特殊的线性表。 ( ) (2)堆栈和队列都将插入和删除操作限制在表的端点处进行。 ( ) (3)只允许在表的一端进行插入和删除操作的线性表称为堆栈。 ( ) (4)没有元素的堆栈称为空栈，空栈用不着栈顶指针。 (X ) (5)只要堆栈不空，就能任意删除堆栈的元素。 (X ) (6)堆栈允许删除的一端称为栈顶，而栈底元素是不能删除的。 ( X ) (7)n个元素进栈的顺序一定与它们出栈的顺序相反。 ( X ) (8)对采用链式存储结构的堆栈进行操作不必判断溢出。 (X ) (9)给出顺序堆栈的栈顶元素位置的指针是一个指针类型的变量。 ( X ) (10)判断顺序堆栈是否为空的标志是top是否等于0(top为栈顶指针)。 ( ) (11)插入和删除操作比较简单是链接堆栈和链接队列的优点之一。 ( ) (12)n个元素进队的顺序与它们出队的顺序一定是相同的。 ( )(13)没有任何元素的队列称为空队。空队用不着队头指针与队尾指针。 ( X ) (14)元素进出队列一定满足“先进先出”的规律。 ( ) (15)链接队列不存在溢出问题。 ( X ) (16)在链接队列中删除一个元素是在链表的最前端进行的。 ( ) (17)采用循环链表作为存储结构的队列称为循环队列。 ( ) (18)堆栈和队列都可以用来解决递归问题。 (X ) (19)堆栈和队列都不适合采用散列存储方法。 ( ) (20)无论是顺序队列还是链接队列，插入、删除操作的时间复杂度都是O(1)。 ( ) 42单项选择题。 A(1)堆栈和队列的共同之处在于它们具有相同的。 A逻辑特性 B物理特性 C运算方法 D元素类型 C(2)堆栈和队列都是特殊的线性表，其特殊性在于_。 A它们具有一般线性表所没有的逻辑特性 B它们的存储结构比较特殊 C对它们的使用方法做了限制 D它们比一般线性表更简单 D(3)若5个元素的出栈序列为1，2，3，4，5，则进栈序列可能是。 A2，4，3，1，5 B2，3，1，5，4 C3，1，4，2，5 D3，1，2，5，4 A(4)某队列初始为空，若它的输入序列为a，b，c，d，它的输出序列应为。 Aa，b，c，d Bd，c，b，a Ca，c，b，d Dd，a，c，b 找公式(5)当4个元素的进栈序列给定以后，由这4个元素组成的可能的出栈序列应该有。 A24种 B17种 C16种 D14种 *(6)设n个元素的进栈序列为1，2，3，n，出栈序列为p1，p2，p3，pn，若Pi=n，则B(1in)的值。 A为i B为n-i C为n-i+l D有多种可能 A(7)设n个元素的进栈序列为p1，p2，p3，pn，出栈序列为1，2，3，n，若Pn=l，则n(1ilink=top Dtop-link=p B(13)若非空堆栈采用链式存储结构，栈顶指针为top，删除堆栈的一个元素的过程是依次执行：p=top，free(p)。 Atop=p Btop=p-link Cp=top-link Dp=p-link C(14)若队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，向队列中插入一个由p所指的新结点的过程是依次执行：，rear=p。 Arear=p Bfront=p Crear-link=p Dfront-link=p D(15)若非空队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，删除队列的一个元素的过程是依次执行：p=front，free(p)。 Arear=p Brear=p-link Crear=p-link Dfront=p-link C(16)在循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断循环队列队空的条件是。 Afront=rear+1 B。rear=front+1 Cfront-rear Db叭t：0 A (17)若描述某循环队列的数组为ClUELIEM，当循环队列满时，队列中有个元素。 AM BM-1 CM十1 DM+2 D (18)在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据打印，该缓 冲区应该是一个结构。 A线性表 B数组 C堆栈 D队列 C(19)设计一个递归问题的非递归算法通常需要设置结构。 A线性表 B数组 C堆栈 D队列 *(20)中缀表达式A-(B+CD)*E的后缀形式是。 AABC+D*E BABCD+E* CAB-C十DE* DABC-+DE*43 填空题。 (1)堆栈和队列的逻辑结构都是线性 结构。 (2)堆栈的插入和删除操作都是在栈顶位置进行，而队列的插入操作在队尾进行，删除操作在队头进行。 (3)对某堆栈执行删除操作时，只有在栈顶情况下，才会将栈底元素删除。 (4)在具体的程序设计过程中，堆栈的顺序存储结构一般是利用一个数组描述的，同时还要定义一个整型变量来栈顶。 (5)若堆栈采用顺序存储结构，在不产生溢出的情况下往堆栈中插人一个新元素，首先移动，然后写入。 (6)若队列采用顺序存储结构，未溢出时插入一个元素首先插入一个元素，然后再写入。 (7)当堆栈的最大长度难以估计时，堆栈最好采用链式存储结构。 (8)递归算法都可以通过设置堆栈机制改写成等价的非递归算法。 *(9)中缀形式的算术表达式A+(B-C)D*E的后缀形式为。*(10)后缀形式的算术表达式ABCD/-E*+的中缀形式为。 44 已知堆栈采用链式存储结构，初始时为空，请画出a，b，c，d四个元素依次进栈以后该堆栈的状态，然后再画出此时的那个栈顶元素出栈后堆栈的状态。 45 若按从左到右的顺序依次读人已知序列a，b，c，d，e，f，g1中的元素，然后结合堆栈操作，能得到下列序列中的哪些序列(每个元素进栈一次，下列序列表示出栈的次序)? d，e，c，f，b，g，a f，e，g，d，a，c，be，f，d，g，b，c，a c，d，b，e，f，a，g 46 设有编号1，2，3，4的四辆列车，顺序进入一个栈式结构的站台，请写出这四辆列车开出车站的所有可能的顺序。 47 设STACKM为n(n2)个堆栈共享。各栈栈顶指针为topn，分别指出各栈栈顶元素的位置；栈底指针为botn+1，分别指出各栈栈底元素的位置。初始时， bopi=boti=i*ROUND(Mn05) (i=1，2，.，n) 其中，ROUND()为四舍五人取整函数。请写一算法，该算法向任意指定的第i个堆栈插入一个新的元素x。仅当M个空间全部占用时才产生溢出，并报告相应信息(1in)。48 设中缀表达式E存放于字符数组中，并以作为结束标志。请写出判断一个中缀表达式E中左、右圆括号是否配对的算法。 49 写出将中缀表达#(a+b)c-d#变换为后缀表达式的过程中，每读到一个单词时堆栈的状态(#为中缀表达式的左、右分界符)。410 已知n为大于等于零的整数，请写出利用堆栈计算下列递归函数f(n)的非递归算法。411 已知Ackerman函数定义如下： (1)写出递归算法； (2)利用堆栈写出非递归算法； (3)根据非递归算法，求出A(：K(2，1)的值。412 已知求两个正整数m和n的最大公约数的过程可以表达为如下递归函数： 请写出求解该递归函数的非递归算法。m MOD n表示m对n取模。413 假设以数组QM存放循环队列的元素，同时设置变量rear与qlen分别指示循环队列中队尾元素的位置和队列中元素的个数。请给出此循环队列的队满条件，并写出相应的进队与出队算法(在出队算法中要求返回队头元素)。414 编写一非递归算法，对于给定的十进制整数n，打印出对应的r进制整数(2r16，r10)。415 梵塔问题是这样的：一个底盘上有三根竖着的针，初始时A针穿着一叠盘片(如图4，20所示)，现要求将这一叠盘片移到C针上，并且任何时刻不得将大盘放在小盘之上，而且每一次只允许移动一张盘片。写一算法，打印出正确的操作步骤。提示：将n张盘片由A依次移到C，B作为辅助针。当n=1时，可以直接完成。否则，将顶上的n1张盘片移到B针上，用C针作为辅助针；然后移第n张盘片，最后将B上的n1张盘片移到C针上，并用A针作为辅助针。栈和队列 历年试题1栈和队列都是（）A限制存取位置的线性结构B顺序存储的线性结构C链式存储的线性结构D限制存取位置的非线性结构2若数组s0.n-1为两个栈s1和s2的共用存储空间，且仅当s0.n-1全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为（）A1和n+1B1和n/2 C1和nD1和n+13.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为( ) A.4 B.5 C.6 D.74假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为_，不可能得到的出栈序列为_。5在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现：_；sq - datasq - top=x；6链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的_。7如图所示，设输入元素的顺序是A，B，C，D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为D，则输出序列为_。8队列中允许进行删除的一端为_。9.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为_。10、设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？ 11如图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可能的输入序列。（5分）第五章 广义表 字符串 数组习 题 51单项选择题。 (1)空的广义表是指广义表。 A深度为0 B。尚未赋值 C不含任何原子元素 D不含任何元素 (2)广义表中元素分为。 A原子元素 B表元素 C原子元素和表元素 D任意元素 (3)广义表的长度是指。 A广义表中元素的个数 B广义表中原子元素的个数 C广义表中表元素的个数 Di广义表中括号嵌套的层数 (4)广义表的深度是指。 久广义表中元素的个数 B广义表中原子元素的个数 C广义表中表元素的个数 D广义表中括号嵌套的层数 (5)在一个长度为n，包含m个原子元素的广义表中，。 Am和n相等 Bm不大于n Cm不小于n Dm与n无关 (6)广义表A=( )，(a)，(b，(c，d)的长度为。 A2 B3 C4 D5 (7)广义表A：( )，(a)，(b，(c，d)的深度为。 A2 B3 C4 D5 52有人说，m*n阶矩阵是一种广义表结构，你认为如何?请说明你的理由。 53请分别写出下列各广义表的长度与深度： (1)A=(a) (2)B=(a，(b，c，d)，e，() (3)C=(x，(y)，B，A) (4)D=(A,D) 56 试写出判断两个广义表是否相等的递归算法。 57 根据本章介绍的m元多项式的表示方法，试写出一个m元多项式相加的算法。 61 请回答空串与空格串有何区别。 62 两个字符串相等的充分必要条件是什么? 63 已知字符串S采用链式存储结构，链结点大小为1。试写出求该串长度的算法。 64 已知字符串S1与S2都采用链式存储结构，链结点大小为1。试写出判断S1与S2是否相等的算法。若S1与S2相等，算法返回1否则返回0。 65 设串S，S1，S2分别采用顺序存储结构，长度分别为len，lenl，len2。试写一算法，用串S2替换串S中的子串S1。 66 设串采用链式存储结构，链结点大小为1。试写出删除S中从第i个字符开始连续k个字符的算法。 67 在字节编址的机器中，字符串S1与S2分别存放在字符数组S饥M1与S2M2中(LEN(S1)M1，LEN(S2)M2)，并以，为串的结束标志。试写一算法，求在S1中第一次出现而在S2中不出现的字符的位置。 68 已知字符串的存储结构同 67题，并且有LEN(S1)=m，LEN(S2)=N0试写一算法，从S1中位置k开始插入字符串S2，并且取代S1中从第k个字符开始的连续t个字符。设k+1mo 69 已知字符串存放于字符数组SM中，并以为串的结束标志。试写一算法，判断该字符串是否是回文(即正读与反读相同)。若字符串是回文，算法返回1，否则返回0。 610 根据你所确定的一种存储结构设计一个算法，该算法的功能是求串S中出现的第一个最长重复子串的位置与长度。 611 已知字符串采用链式存储结构，链结点大小为1。对于给定的字符串S1与S2，请写一算法，求在S1中第一次出现，而在S2中不出现的所有字符。各种考试试题1执行下列程序段后，串X的值为（）S=abcdefgh; T=xyzw; substr (X,S,2,strlen(T);substr (Y,S, stelen(T),2);strcat (X,Y);AcdefghBcdxyzwCcdefxyDcdefef2多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（）A数组的元素处在行和列两个关系中 B数组的元素必须从左到右顺序排列C数组的元素之间存在次序关系 D数组是多维结构，内存是一维结构3从广义表LS（(p, q), r, s）中分解出原子q的运算是（）Atail (head (LS)Bhead (tail (head (LS)Chead (tail (LS)Dtail (tail (head (LS)4数组通常具有两种基本运算，即（）A创建和删除B索引和修改C读和写D排序和查找5设有一5阶上三角矩阵A1.5，1.5，现将其上三角中的元素按列优先顺序存放在一堆数组B1.15中。已知B1的地址为100，每个元素占用2个存储单元，则A3，4的地址为（）A116B118 C120 D1226.为查找某一特定单词在文本中出现的位置，可应用的串运算是( ) A.插入 B.删除 C.串联接 D.子串定位7.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=SCIENCESTUDY，则调用函数Scopy(P,Sub(S,1,7)后得到( ) A.P=SCIENCE B.P=STUDY C.S=SCIENCE D.S=STUDY8.三维数组A456按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A45的存储地址为( ) A.356 B.358 C.360 D.3629.串S=I am a worker的长度是_。10.假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为_。11、二维数组 X 的行下标范围是05,列下标范围是18,每个数组元素占六个字节,则该数组的体积为_A_个字节,若已知 X 的最后一个元素的起始字节地址为382,则 X 的首地址(即第一个元素的起始字节地址)为 _B_,记为 Xd。若按行存储,则 X1,5 的起始地址是 _C_, 结束字节地址是_ _D_。若按列存储,则 X4,8的起始字节地址为_E_。供选择的答案：A: 210 240 288 294B: 0 6 94 100C: Xd+24 Xd+72 Xd+78 Xd+144D: Xd+29 Xd+77 Xd+83 Xd+147E: Xd+186 Xd+234 Xd+270 Xd+27612、有一个二维数组A，行下标的范围是16，列下标的范围是07，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是A个字节。假设存储数组元素A1, 0的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是B。若按行存储，则A2, 4的第一个字节的地址是C。若按列存储，则A5, 7的第一个字节的地址是D。就一般情况而言，当E时，按行存储的A5, 7的第一个字节的地址是D。就一般情况而言，当E时，按行存储的AI, J地址与按列存储的AJ, I地址相等。供选择的答案：AD： 12 66 72 96 114 120 156234 276 282 283 288E：行与列的上界相同 行与列的下界相同 行与列的上界相同且行与列的下界相同 行的元素个数与列的元素的个数相同13、设W为一个二维数组，其每个数据元素Wij占用6个字节，行下标i从0到8，列下标j从2到5，则二维数组W的数据元素共占用A个字节。W中第6 行的元素和第4列的元素共占用B个字节。若按行顺序存放二维数组W，其起始地址的字节号为100，则二维数组W的最后一个数据元素的起始地址的字节号为C，数据元素W34的起始地址号为D，而数据元素W22的起始地址与当W按列顺序存放时数据元素E的起始地址相同。供选择的答案 A： 480 192 216 144B： 78 72 66 84 C： 310 311 315 314 D： 179 178 184 185E： W05 W28 W52 W82阅读下列函数说明和代码，将应填入_(n)_处的字句写在答卷的对应栏内。 【函数2.1说明】设长正整数用数组存储，如有k位的长整数m用数组a存储： m=ak*10k-1+ak-1*10K-2+a2*101+a1*100并用a0存储长整数m的位数，即a0=k。通常，存储长整数数组的每个元素只存储长整数的一位数字。长整数运算时，为了运算方便，产生的中间结果的某位数字可能会大于9。这时，就应调用本函数将它规整，使数组的每个元素只存储长整数的一位数字。规整运算函数formal(int *a)就实现这个特殊要求。 【函数2.1】 void formal(int *a) int p； for (p=1；p10；p+) if (p=a0 _(1)_； ap+1+=ap/10； ap=_(2)_； if (pa0) _(3)_； 【函数2.2说明】函数combine(a,b,c)是计算两个整数的组合数。由于计算结果超出long int 的表示范围，故用本题【函数2.1说明】的方法存储计算结果。设整数a和b (a=b) ，它们的组合c(a,b)=a!/(a-b)!*b!)。计算a和b的组合可采用以下方法： a!/(a-b)!/b! =a * (a-1) * (a-2) * * (a-b+1)/b! =u1 * u2 * * ub/(d1*d2*db)其中u1=a，u2=a-1，ub=a-b+1；d1=1，d2=2，db=b。从而计算a和b的组合c(a,b)，可变成计算上述分式。为计算上述分式，先从u1，u2，ub中去掉所有d1*d2*db的因子，得到新的u1，u2，ub。然后再将它们相乘。以下函数中调用的外部函数gcd(a,b)是求两整数a和b最大公因子的函数；函数formal()就是本题中的函数2.1。 【函数2.2】 void combine(int a，int b，int *c) int i，j，x，k； int dMAXN，uMAXN； for (k=0，i=a；i=a-b+1；i-) u+k=i； _(4)_； for (i=1；i=b；i+) di=i；; /*将整数1至b顺序存于数组d*/ for (i=1；i=u0；i+) /*从u的各元素中，去掉d中整数的所有因子*/ if (ui!=1) for (j=1；j=b；j+) if (_(5)_) x=gcd(ui，dj)； ui/=x； dj/=x； c0=c1=1; /*长整数c初始化*/ for (i=1；i=u0；i+) /*将u中各整数相乘，存于长整数c*/ if (ui!=1) for (j=1；j=c0；j+) cj=_(6)_； formal(c)； /*将存于c中的长整数规整*/ 18、阅读下列程序或函数说明和 C 代码,将应填入_(n)_处的字句写在答题纸的对应栏内。 函数1.1说明函数strcmp()是比较两个字符串 s 和 t 的大小。若 s t,函数返回正数。 函数1.1int strcmp(char *s,char *t) while ( *s & *t & _(1)_) s+;t+ ; return _(2)_; 程序1.2说明在 n 行 n 列的矩阵中,每行都有最大的数,本程序求这 n 个最大数中的最小一个 程序1.2#includestdio.h#define N 100int aNN;void main() int row ,col ,max ,min ,n; /*输入合法 n (100 ),和输入 m n 个整数到数组 a 的代码略*/ for ( row = 0;row n;row+) for ( max = arow0,col = l ;col va1 = v;_(1)_; *p = _(2)_;NODE *reverse_copy(NODE *p) NODE *u; for( u = NULL ; p ; p = p -next ) first_insert(_(3)_); return u;void print_link( NODE *p ) for( ;_(4)_) printf (%dt , p - val); printf(n);void free_link(NODE*p) NODE *u; while( p != NULL) u=p-next;free( p );_(5)_;void main() NODE *link1 , *link2;int i ;linkl = NULL ;for( i = 1;i = 10 ; i+ ) first insert( &link1,i );link2 = revere_ copy(link1);print_link(link1);freeJink(linkl);print_link(link2);free_link(link2);函数21说明 函数strcat(char *si，char *s2)是将字符串s2连接在字符串si之后，构成一个首指 针为s1的字符串。 函数2.1 void strcat(char *sl，char *s2) while(*s1!=0) ； (1) ： for( ； (2) ；s1+，s2+)； 函数22说明 本函数输入n(1000)个整数到指定数组，求该数组中最大元素的值和此元素的下标，最大元素值以函数值返回，此元素的下标通过指针形参带回调用处。 函数22 #include #define MAXLINE 1000 int