《数据结构(本)》期末考试复习题

数据结构（本）期末综合练习题一、单选选择题1 .栈和队列的共同特点是（C）。A.都是先进先出 B.都是操作受限的线性结构C.都是先进后出 D.元素都可以随机进出2 .数据的存储结构包括数据元素的表示和（C）。A.数据处理的方法 B.数据元素的类型C.数据元素间的关系的表示 D.相关算法3.对一个栈顶指针为t o p 的链栈进行入栈操作，通过指针变量p 生成入栈结点，则执行p=（s t r u ct node*）malloc（s iz eof（s t r u ct node）;p-dat a=a;和（C）nex t=p;p=t op;B.p-nex t=t op;p=t op;C.p-nex t=t op;t op=p;D.t op=t op-nex t;p=t op;4.树状结构中数据元素的位置之间存在（B）的关系。A.每一个元素都有一个直接前驱和一个直接后继 B.一对多C.一对一 D.多对多5.设头指针为head的非空的单向链表，指 针 p 指向尾结点，则通过以下操作（D）可使其成为单向循环链表。A.head=p;B.p=head;C.p-nex t =NU L L ;D.p-nex t=head;6 .设有一个长度为2 6 的顺序表，要插入一个元素，并使它成为新表的第6个元素，需移动元素的个数为（D）。A.2 2 B.1 9 C.2 0 D.2 17 .一种逻辑结构（C）.A.与存储该逻辑结构的计算机相关 B,是指某一种数据元素的性质C.可以有不同的存储结构 D.只能有唯一的存储结构8 .头指针为head的带头结点的单向循环链表，p 所指向尾结点，要使该链表成为不带头结点的单向循环链表，可执行head=head-nex;和（A）A.p-nex t=head;B.p=head-nex tC.head-nex t=p D.head-nex t=p-nex t9 .把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（D）。A.给数据元素分配存储空间 B.数据元素的存储C.逻辑结构 D.存储结构1 0 .元素 1 1 1,1 1 3,1 1 5,1 1 7 按顺序依次进栈，则该栈的不可能输出序列是（D）（进栈出栈可以交替进行）。A.1 1 1,1 1 3,1 1 5,1 1 7 B.1 1 3,1 1 1,1 1 7,1 1 5C.117,115,113,111 D.117,115,111,11311.图状结构中数据元素的位置之间存在（B）的关系。A.每一个元素都有一个且只有一个直接前驱和一个直接后继B.多对多 C.一对一 D.一对一12.以下说法正确的是（D）。A.栈和队列的特点都是后进后出 B.队列的特点是先进后出C.栈的特点是先进先出 D.栈的特点是先进后出13.一个单链表中，在 p 所指结点之后插入一个s 所指的结点时，可执行：s-next=p-next;和（D）。A.s=p-next;B.p=s-next;C.p-next=s-next;D.p-next=s;14.设有一个20阶的对称矩阵A（第一个元素为al,1）,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B 中（数组下标从1 开始），则矩阵元素a6,2 在一维数组 B 中的下标是（B）。A.28 B.17 C.21 D.2315.元 素 12,14,16,18顺序依次进栈，则该栈的不可能输出序列是（C）。（进栈出栈可以交替进行）。A.18,16,14,12 B.12,14,16,18C.18,16,12,14 D.14,12,18,1616.设有串 pl=ABADF,P2=ABAFD,P3=ABADFA,P4=ABAF,以下四个串中最大的是（A）。A.p2 B.p3 C.p4 D.pl17.设有一个30阶的对称矩阵A（第一个元素为al,1）,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B 中（数组下标从1 开始），则矩阵中元素a9,2 在一维数组B 中的下标是（A）。A.38 B.32 C.18 D.4118.数组a 经初始化char a=English;a7中存放的是（B）1,A.h B.字符串的结束符 C.变量h D.字符h19.设有一个长度为32的顺序表，要删除第8 个元素需移动元素的个数为（B）oA.15 B.24 C.22 D.1420.设主串为“ABcCDABcdEFaBc，以下模式串能与主串成功匹配的是（B）。A.ABC B.Bed C.Abe D.BCd21.在一棵二叉树中，若编号为i 的结点存在右孩子，则右孩子的顺序编号为（C）。A.2i-l B.2i C.2i+l D.2i+222.在一棵二叉树中，若编号为i 的结点存在左孩子，则左孩子的顺序编号为（D）。A.2i+l B.2i-l C.2i+2 D.2i23.一棵具有16个结点的完全二叉树，共 有（B）层。（设根结点在第一层）A.6 B.5 C.4 D.724.如下图所示，若从顶点a 出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（A）o3A.ae cb d f B.ae d fcb C.ae b cfd D.ab e cd f2 5.如下图所示，若从顶点a 出发，按图的深度优先搜索法进行遍历，则可能得到的一种顶点序列为（C）。A.ae b cfg d B.ab e cd fg C.ae d fcg b D.acfe b g d2 6 .线性表以（B）方式存储，能进行折半查找。A.顺序 B.关键字有序的顺序 C.二叉树 I）.链接2 7 .字符串“D A B cd ab cd 3 2 1 A B C”的子串是（C）A.“3 2 1 a”B.“aB cd”C.“cd 3 2”D.“A B cD”2 8 .一棵具有3 8 个结点的完全二叉树，最后一层有（B）个结点。A.6 B.7 C.5 D.82 9 .如下图所示，若从顶点a 出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列 为（C）A.acb fe d g B.ab cd fe g C.ab cd fg e D.ab cfg d e3 0.下图的拓扑序列是（A.2 3 6 4 5 B.5 6 2 3 4 C.2 3 5 6 4 D.5 2 3 4 63 1 .下面关于线性表的叙述错误的是（D）。A.线性表采用链式存储便于插入和删除操作的实现B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用顺序存储必须占用一片连续的存储空间D.线性表采用顺序存储便于插入和删除操作的实现3 2 .设有头指针为h e ad 的不带头结点的非空的单向循环链表，指针p 指向其尾结点，要删除第一个结点,则可利用下述语句h e ad=h e ad-n e x t;和（D）。A.p=h e ad;B.h e ad=p;C.p=N U L L;D.p-n e x t =h e ad;3 3 .以下数据结构中是非线性结构的是（C）。A.线性表 B.队列 C.二叉树 D.栈3 4.以下说法正确的是（B）。A.线性表的链式存储结构必须占用连续的存储空间B.一种逻辑结构可以有不同的存储结构C.一种逻辑结构只能有唯一的存储结构D.线性表的顺序存储结构不必占用连续的存储空间3 5.设有一个长度为1 8 的顺序表，要删除第7个元素需移动元素的个数为（B）。A.1 2 B.1 1 C.1 0 D.1 33 6 .把数据存储到计算机中，并具体体现（A）称为物理结构。A.数据元素间的逻辑关系 B.数据的运算C.数据的处理方法 D.数据的性质3 7 .两个字符串相等的充要条件是（B）。A.两个字符串的长度相等 B.同时具备（A）和（C）两个条件C.两个字符串中对应位置上的字符相等 D.以上答案都不对3 8 .顺序表所具备的特点之一是（B）。A.删除元素的操作不需要移动元素 B.可以随机访问任一结点C.不需要占用连续的存储空间 D.插入元素的操作不需要移动元素3 9 .设某链表中最常用的操作是在链表的尾部插入或删除元素，在已知尾指针的条件下，选用 下 列（A）存储方式最节省运算时间。A.双向链表 B.单向链表 C.单向循环链表 D.双向循环链表40 .图状结构中数据元素的位置之间存在（A）的关系。A.多对多 B.每一个元素都有一个直接前驱和一个直接后继C.一对多 D.一对一41 .元 素 1 3,1 5,1 9,2 0 顺序依次进栈，则该栈的不可能输出序列是（A）.（进栈出栈可以交替进行）A.1 9,1 3,1 5,2 0 B.1 5,1 3,2 0,1 9C.1 3,1 5,1 9,2 0 D.2 0,1 9,1 5,1 342,元素2 0,1 4,1 6,1 8 按顺序依次进栈，则该栈的不可能输出序列是（A）。（进栈出栈可以交替进行）A.1 8,1 6,2 0,1 4 B.2 0,1 4,1 6,1 8C.1 4,2 0,1 8,1 6 D.1 8,1 6,1 4,2 043.设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,则在表中删除结点B的操作为（A）。A.q-n e x t=p-n e x t；B.q-n e x t=p；C.p-n e x t=q-n e x t；D.p-n e x t；p=q；44.设有一个1 2 阶的对称矩阵A （左上角第一个元素为al,1）,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1 开始），则矩阵中元素a 5,4在一维数组B中的下标是（C）。A.1 2 B.1 1 C.1 4 D.1 34 5 .栈和队列的共同特点之一是（A）。A.只允许在端点处插入和删除元素 B.都是先进先出C.没有共同点 D.都是先进后出4 6 .设有一个长度为2 2 的顺序表，要删除第8个元素需移动元素的个数为（C）。A.2 5 B.1 5 C.1 4 D.2 34 7 .用链接方式存储的队列，在进行插入运算时（C）。A.头、尾指针都需要修改 B.头、尾指针都不需要修改C.需修改尾指针 D.需修改头指针4 8 .在一棵二叉树中，若编号为5的结点存在右孩子，则右孩子的顺序编号为（D）。A.1 2 B.1 0 C.9 D.1 14 9 .字符串 a l=A E I J I N G,a 2=A E I,a 3=A E F A N G,a 4=A E F I 中最大的是（D）。A.a 2 B.a 3 C.a 4 D.a l5 0 .一棵具有5 层的完全二叉树，最后一层有4个结点，则该树总共有（B）个结点。A.1 8 B.1 9 C.1 5 D.1 45 1 .设 有 一 个 20阶 的 对 称 矩 阵 A （第 一 个 元 素 为 a l,l）,采用压缩存储的方式，将其 下三角部分以行序为主序存储到一维数组B中（数组下标从1 开始），则矩阵中元素a 6,2在一维数组B中的下标是（C）。A.1 8 B.23 C.17 D.2 15 2.如下图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（A）。gA.a b c e d f g B.a b c f g d e C.a c b f e d g D.a b c d f g e5 3 .以下说法正确的是（A）。A.二叉树中任意一个非叶结点的值都大于其左子树上所有结点的值，小于其右子树上所有结点的值，则该树为二叉排序树。B.若二叉树中左子树上所有结点的值均小于根结点的值，右子树上所有结点的值均大于根结点的值。则该树为二叉排序树。C.前序遍历二叉排序树可得到一个有序序列。D.二叉树中任意一个结点的值均大于其左孩子的值，小于其右孩子的值。则该树为二叉排序树。5 4 .字符串a b c d 3 2 1 A B C D”的子串是（B）.A.3 2 1 a B.2 1 A B C C.a b c A B C D D.a b c D5 5 .二叉树的第k 层的结点数最多为（B）。A.2 K-1 B.2 k-l C.2 K+1 D.2 k-15 6 .数组a 经初始化c h a r a =E n g