资源描述：
《数据结构(专)阶段练习2》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、华东理工大学网络学院(专科)《数据结构》……第3章、第4章、第5章班级学号姓名成绩—一、填空题(每空1分，共20分)1.栈和队列是两种特殊的线性表，栈的特点是—先进后出，表达式求值,栈的典型应用有和实现递归过程O2.在具有n个单元的循环队列屮，队列满时共有n-1个元素。3.若串的长度不能确定，对采用动态存储结构，为串值分配一个存储空间，同时建立一个串的描述子以指示串值的长度和串在存储空间中的位置，称该结构为堆/堆结构04.稀疏矩阵一种常用的压缩存储方法称为三元组表方式，即每个三元组表中的元素由、行、列、值、三
2、部分组成。5.二维数组A[10][20]采用列序为主方式存储，每个元素占10个存储单元，且A[01(0]的存储地址是2000,则A⑹[12]的地址是3260。6.进栈序列为a,b,c,则通过出栈和进栈操作可能得到的a,b,c的不同的排列序列有5种。7.广义表((a,b),c,d)的表头是(a,b),表尾是(c,d)。8.已知二维数组A[20](10]采用行序为主方式存储，每个元索占2个存储单元，并且A[10]⑸的存储地址是1000,则Afl8]f9]的存储地址是1168。9.广义表((((a),b),c),d
3、)的表头是(((a),b),c),表尾是(d)。10.设s=，YOUAREJUDGINGITRIGHTORWRONG,,顺序执行下列操作：SubString(subl,s,l,8):SubString(sub2,s,20,5)；StrCat(subl,sub2);则最后subl的值为：，YOUARER1GHT,。11.假设用循环单链表实现队列，若队列非空，且队尾指针为R,则将新结点S加入队列吋,需拟I行下而语句：S->next=R->next_；R->next=S；R=So12.设有两个串p和q,求q在p中首
4、次出现的位置的运算称作子串定位o二、判断正误(对的用nr表示，错误的用”F”表示。每小题1分，共10分)1.(F)一个栈的入栈序列是12345,则栈的输出序列12345是不可能的。2.(T)将递归算法转换成对应的非递归算法时，通常需要使用栈。3.(T)两个串相等的充要条件是串的长度相等和对应的字符相等。1.(T)二维数组是其数据元素为线性表的线性表。2.(F)若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置。3.(F)若一个广义表的表头为空表，则此广义表亦为空表。4
5、.(T)两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。&(F)子串是主串中任意个连续字符组成的序列。9.(T)栈和队列是一种线性数据结构。10.(F)顺序栈初始化的条件是栈顶指针top的值为0。三、单项选择题(每小题2分，共20分)。1.栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈，问下列哪一个序列是可能的出栈序列？CAE、D、C、B、A、FBB、C、E^F、A、DCC^B、E^D、A、FDA、D、F、E、B、C2.若进栈序
6、列为a,b,c,则通过入出栈操作可能得到的a,b,c的不可能的出栈序列为：_B_AabcBcabCacbDbca3.以下关于广义表的叙述屮，正确的是：AA广义表是由0个或多个单元索或子表构成的有限序列B广义衣至少有一个元素是子表C广义表不能递归定义D广义表不能为空表4.以下哪一个不是队列的基本运算？BA从队尾插入一个新元素B从队列中删除第i个元素C判断一个队列是否为空D读取队头元素的值5.已知一个3行、4列的二维数组A(各维下标均从1开始)，如果按“以列为主”的顺序存储，则排在第8个位置的元素是：BAA[2,
7、2]BA[2,3]CA[3,3]DA[3,2J6.一个循环队列的头指针为frog尾指针为rear。则判断该队列满的条件是：D。Arcar=frontBrcar=front+1Cfront=rear+lDfront=(rear+l)%(整除)n7.已知二维数组A[10][20]采用行序为主方式存储，每个元素山2个存储单元，并且A[0][0]的存储地址是1024,则A⑹[18]的地址是B。A1298B1300C1344D1424&广义表人=(()),则表尾GetTail(A)为C。A)B(())C空表D(9.对于
8、一个下三角矩阵的压缩存储，只存储非零元素，则需耍存储的元素个数为An2Bn2/2Cn(n-l)/2Dn(n+l)/21().串是DoA不少于一个字母的序列B任意个字母的序列C不少于一个字符的序列D有限个字符的序列四、简答题(每小题5分，共15分)。1.恢路进行列车调度时，常把站台设计成栈式结构的站台，如右图所示。试问：设有编号为123,4,5,6的六辆列车，顺序开入栈式结构的站台，若进站的六辆列车顺
