数据结构练习2_副本.doc

华东理工大学网络学院 《数据结构》------第3章、第4章、第5章 班级 学号 姓名 成绩 一、填空题（每空1分，共20分） 1. 栈和队列是两种特殊的线性表，栈的特点是 先进后出，栈的典型应用有表达式求值和 实现递归过程。 2. 在具有n个单元的循环队列中，队列满时共有 n-1 个元素。 3. 若串的长度不能确定，可采用动态存储结构，为串值分配一个存储空间，同时建立一个串的描述子以指示串值的长度和串在存储空间中的位置，称该结构为堆/堆结构。 4. 稀疏矩阵一种常用的压缩存储方法称为三元组表方式，即每个三元组表中的元素由 行 、 列 、 值 三部分组成。 5. 二维数组A[10][20]采用列序为主方式存储，每个元素占10个存储单元，且A[0][0]的存储地址是2000，则A[6][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][5]的存储地址是1000,则A[18][9]的存储地址是 1168 。 9. 广义表((((a),b),c),d)的表头是 (((a),b),c) ，表尾是 (d) 。 10. 设s=’YOU ARE JUDGING IT RIGHT OR WRONG’，顺序执行下列操作：SubString(sub1,s,1,8)；SubString(sub2,s,20,5)；StrCat(sub1,sub2); 则最后sub1的值为： ’YOU ARE RIGHT’ 。 11. 假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，需执行下面语句： S-next=R-next ； R-next=S ； R=S 。 12.设有两个串p和q，求q在p中首次出现的位置的运算称作子串定位 。 二、判断正误（对的用”T”表示，错误的用”F”表示。每小题1分，共10分） 1.（ F ）一个栈的入栈序列是12345，则栈的输出序列12345是不可能的。 2.（ T ）将递归算法转换成对应的非递归算法时，通常需要使用栈。 3.（ T ）两个串相等的充要条件是串的长度相等和对应的字符相等。 4.（ T ）二维数组是其数据元素为线性表的线性表。 5. ( F ) 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置。 6. ( F )若一个广义表的表头为空表，则此广义表亦为空表。 7.（ T ）两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 8.（F ）子串是主串中任意个连续字符组成的序列。 9.（ T ）栈和队列是一种线性数据结构。 10.（ F ）顺序栈初始化的条件是栈顶指针top的值为0。 三、单项选择题（每小题2分，共20分）。 1.栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列? C ?? A E、D、C、B、A、F B B、C、E、F、A、D C C、B、E、D、A、F D A、D、F、E、B、C 2.若进栈序列为a, b, c，则通过入出栈操作可能得到的a, b, c的不可能的出栈序列为: B A abc B cab C acb D bca 3. 以下关于广义表的叙述中，正确的是： A A 广义表是由0个或多个单元素或子表构成的有限序列 B 广义表至少有一个元素是子表 C 广义表不能递归定义 D广义表不能为空表 4. 以下哪一个不是队列的基本运算？ B A 从队尾插入一个新元素 B 从队列中删除第i个元素 C 判断一个队列是否为空 D 读取队头元素的值 5. 已知一个3行、4列的二维数组A（各维下标均从1开始），如果按“以列为主”的顺序存储，则排在第8个位置的元素是： B A A[2,2] B A[2, 3] C A[3, 3] D