数据结构题目.doc

第一章 题目 1 顺序存储结构中数据元素间的逻辑关系是由（ ）表示的，链接存储结构中数据元素间的逻辑关系是由 （） 表示的 A 指针 B 逻辑顺序 C 存储位置 D 问题上下文 2 计算机所处理的数据一般具有某种关系，这是指（） A数据与数据间存在的某种关系 B数据元素与数据元素之间存在的某种关系 C元素内数据项与数据项间存在的某种关系 D 数据文件内记录与记录间存在的某种关系 3.关于数据结构的描述，不正确的是（） A 数据结构相同，对应的存储结构也相同 B 数据结构设计数据的逻辑结构、存储结构和施加其上的操作等三方面 C 数据结构操作的实现与存储结构有关 D 定义逻辑结构时可不考虑存储结构 4.下面关于抽象数据类型的描述，不正确的是（） A数据封装 B 使用与实现分离 C 信息隐藏 D 用例驱动 5 算法的时间复杂度与（）有关 A 问题规模 B 计算机硬件的运行速度 C 源程序的长度 D 编译后执行程序的质量 6 某算法的时间复杂度O（n2），表明该算法（） A 问题规模n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 7 以下说法正确的是（） A 数据结构的逻辑结构独立于其存储结构 B 数据结构的存储结构独立于该数据结构的逻辑结构 C 数据结构的逻辑结构唯一地决定了该数据结构的存储结构 D 数据结构仅仅由其逻辑结构和存储结构决定 第二章 线性表 判断对错 1.数据是一种静态的存储空间分配，就是说在程序设计时必须预先定义数组的数据类型和存储空间大小 （） 2.二维数组可以看成数组元素是一维数组的一维数组，因此二维数组是线性的 3.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。 4.一维数组是线性的 5.顺序表可以利用一维数组表示，因此一维数组与顺序表结构上一直，可以通用。 6.下列关于线性表描述正确的是（） A 线性表的逻辑顺序与物理顺序总是一致的 B 线性表的顺序存储表示优于链式存储表示 C 线性表若采用链式存储表示时所有存储单元的地址可连续或者不连续 D 每种数据结构都应具备三种基本运算：删除、插入和查找 7.顺序表是线性表的（）存储表示 A 有序 B 连续 C数组 D顺序存取 8 设单链表的节点结构是 struct Linknode /节点定义 E data; /数据 Linknode * link; /链接指针 ; 8.1.不带头节点的单链表first为空的判断条件 A first=null；B first-link=null Cfirst-link=first D first!=null 8.2 带头节点的单链表为空的判断条件是（） A first-=null B first-link=null; C first-link=first D first!=null 8.3 已知单链表节点*q是节点*p的直接前驱，若在*q与*p之间插入节点*s,应执行以下（）操作 A s-link=p-link ;p-link=s B q-link=s;s-link=p; Cp-link=s-link;s-link=p D p-link=s;s-link=q; 8.4已知单链表的结点*p不是链尾结点，若在*p之后插入结点*s，则应执行下列（）操作 A s-link=p;p-link=s; B p-link=s;s-link=p C s-link=p-link;p=s D s-link=p-link;p-link=s 8.5 若想在单链表中摘除结点*p（*p既不是第一个也不是最后一个结点）的直接后继，则应执行以下（） 操作 A p-link=p-link-link B p=p-link;p-link=p-link-link C p-link=p-link D p=p-link-link; 8.6 已知L是带表头的单链表，L是表头指针，则摘除首元结点的语句是（） A L=L-link B L-link=L-link-link C L=L-link-link D L-link=L 1下述哪一条是顺序存储结构的优点？（） A存储密度大B插入运算方便C删除运算方便D可方便地用于各种逻辑结构的存储表示 2下面关于线性表的叙述中，错误的是哪一个？（） A线性表采用顺序存储，必须占用一片连续的存储单元。 B线性表采用顺序存储，便于进行插入和删除操作。 C线性表采用链接存储，不必占用一片连续的存储单元。 D线性表采用链接存储，便于插入和删除操作。 3线性表是具有n个（）的有限序列（n0）。 A表元素B字符C数据元素D数据项E信息项 4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。 A顺序表B双链表C带头结点的双循环链表D单循环链表 5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。 A单链表B仅有头指针的单循环链表C双链表D仅有尾指针的单循环链表 6设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。 A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表 7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。 A单链表B双链表C单循环链表D带头结点的双循环链表 8.静态链表中指针表示的是（）. A内存地址B数组下标C下一元素地址D左、右孩子地址 9.链表不具有的特点是（） A插入、删除不需要移动元素B可随机访问任一元素 C不必事先估计存储空间D所需空间与线性长度成正比 10.下面的叙述不正确的是（） A线性表在链式存储时，查找第i个元素的时间同i的值成正比 B.线性表在链式存储时，查找第i个元素的时间同i的值无关 C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比 D.线性表在顺序存储时，查找第i个元素的时间同i的值无关第三章 栈和队列 1 栈的插入和删除操作在（）进行 A 栈顶 B 栈底 C 任意位置 D 指定位置 2.对一个初始为空的栈执行操作s.push(5),s.push(2),s.push(4),s.pop(x),s.gettop(x)后，x是（） A 5 B 2 C 4 D 0 3.若让元素1,2,3依次进栈，出栈序列不可能的是（） A 3,2,1 B 2,1,3 C 3,1,2 D 1,3,2 1.对于栈操作数据的原则是（）。 A.先进先出B.后进先出C.后进后出D.不分顺序 2.在作进栈运算时,应先判别栈是否(),在作退栈运算时应先判别栈是否()。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为()。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的()分别设在这片内存空间的两端,这样,当()时，才产生上溢。 ,: A.空B.满C.上溢D.下溢 : A. n-1B. nC. n+1D.n/2 : A.长度B.深度C.栈顶D.栈底 : A.两个栈的栈顶同时到达栈空间的中心点. B.其中一个栈的栈顶到达栈空间的中心点. C.两个栈的栈顶在栈空间的某一位置相遇. D.两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 3.一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（）。 A.不确定B. n-i+1C.iD. n-i 4.若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是（）。 A. i-j-1B. i-jC. j-i+1D.不确定的 5.若已知一个栈的入栈序列是1,2,3,n，其输出序列为p1,p2,p3，pN,若pN是n，则pi是()。 A. iB. n-iC. n-i+1D.不确定 6. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应