数据结构 考试 填空选择简答

1、一、选择题1在数据结构中，不可分割的最小数据单位是（A）A数据项B数据元素；C数据对象D.数据类型2.算法指的（D）A计算机程序 B解决问题的计算方法；C排序算法；D解决问题的有限运算序列3一个队列的入列序列是1、2、3、4，则队列的输出序列是（ B ）A4，3，2，1 B1，2，3，4C1，4，3，2 D3，2，4，14某二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则前序序列遍历为 ( D ) A. ACBEDB. DECAB C. DEABC D. CEDBA5 设无向图的顶点个数为n，则该图最多有（D）条边。A n-1 B.n(n+1)/2 C.n2 Dn(n-1)/21

2、.串是一种特殊的线性表，其特殊性体现在（D ）A、可以顺序存储 B、数据元素是一个字符C、可以链接存储 D、数据元素可以是多个字符2.不带头结点的单链表head为空的判定条件是（A ）A.head=NULL B.head-next=NULLC.head-next=head D.head！=NULL3.一个向量第一个元素的存储地址是100 ,每个元素的长度为2，则第5个元素的地址是（B ）A.110 B.108 C.100 D.1204、一个队列的入列序列是1、2、3、4，则队列的输出序列是（B ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 5、线性表若采用

3、链式存储结构时，要求内存中可用存储单元的地址（C ）A.必须是连续 B.部分地址必须是连续的C.一定是不连续的 D.连续或不连续都可以6、在以下的叙述中，正确的是（B ）A、线性表的线性存储结构优于链表存储结构B、二维数组是其数据元素为线性表的线性表C、栈的操作方式是先进先出D、队列的操作方式是先进后出7、串是一种特殊的线性表，其特殊性体现在（D ）A、可以顺序存储 B、数据元素是一个字符C、可以链接存储 D、数据元素可以是多个字符8、若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（A ）A正确 B、错误1. 抽象数据类型概念与C语言

4、中数据类型概念的最大区别在于（D）A前者比后者复杂得多；B前者包含后者；C前者包含一组数据关系，而后者没有；D前者包含一组操作，而后者没有2. 在数据结构中，不可分割的最小数据单位是（A）A数据项 B数据元素；C数据对象D数据类型3. 字符串S1、S2联接成新串T，其中LS1、LS2和LT分别表示S1、S2和T的长度。根据S1和S2长度的不同，新串T值的产生一般要可虑到3种情况，请在以下选项中选出不属于考虑范围的情况：（C）A. LS1LS2LT；B. LS1LS2LT；C. LS2LT；D. LS1LT4. 在链式栈的操作中，关于出栈与取栈顶元素的描述，正确的是（E）A. 两者均为读出栈顶元

5、素的值；B. 两者均使栈顶元素出栈；C. 前者使栈顶元素出栈，而后者为读出栈顶元素的值；D. 后者使栈顶元素出栈，而前者为读出栈顶元素的值；E. 前者使栈顶元素出栈，并释放内存空间，而后者为读出栈顶元素的值一，填序号已知是带表头结点的非空单链表，且结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择全程的语句序列。1.删除结点的直接后继结点的语句序列是11,3,142.删除结点的直接前驱结点的语句序列是10,12,8,11,3,143. 删除结点的语句序列是10,12,7,3,144删除首元结点的语句序列是12,11,3,145. 删除尾元结点的语句序列是12,9,11,3,14（）；

6、（）；（）；（）；（）（！）；（）（！）；（）（！）；（）（！）；（）（！）；（）；（）；（）；（）；（）（）；二简答题1简述下列术语数据:即对客观事物的符号表示。在计算机科学中，指输入到计算机中并被计算机处理的符号的总称数据元素:数据的基本单位。可由若干数据项组成，常把数据元素作为一个整体考虑。数据对象:性质相同的数据元素的集合，是数据的子集。数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合。作为一门学科，它是研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等。数据逻辑结构:是指在数据结构中数据元素之间的逻辑关系的数学模型。数据存储结构:数据结构在计算机中的

7、表示或映象。包含数据元素及其关系的表示。数据类型:一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型:是指一个数学模型以及定义在该模型上的一组操作。包括数据对象、数据关系和基本操作算法:是对特定问题求解步骤的一种描述，是指令的有限序列。2. 简述线性表的定义及其特点答：即多个数据元素的有限序列。特点： 存在惟一一个被称作“第一个”的数据元素存在惟一一个被称作“最后一个”的数据元素集合中的每个数据元素均只有一个前驱（除第一个之外）集合中的每个数据元素均只有一个后继（除最后一个之外）3. 简述顺序表与单链表的定义，并指出它们各自的存储结构、表特点、存取方式。答：用一组地址连续的存储单元依

8、次存储线性表的数据元素，象这种顺序存储结构的线性表叫做顺序表。用一组地址任意的存储单元存储线性表的数据元素，数据元素除了存储其本身的信息之外，还存储一个指示其直接后继的信息，n个数据元素结点链接成的链式存储结构的线性表，就是链表。每个结点只包含一个指针域的链表叫做单链表4. 简述栈与队列的定义，并指出它们各自的特点。答：栈是限定仅在表尾进行插入或删除操作的线性表。特点：后进先出(LIFO) 队列是只允许在表的一端进行插入，而在另一端删除元素的线性表。特点：先进先出（FIFO）3 填空题1、在树形结构中，树根结点没有前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有后继 结点，其余每

9、项个结点的后续结点可以多个。2、在图形结构中，每个结点的前驱结点数和后续结点数可以相等 相同。3在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 个后续结点。4，在顺序表中插入或删除一个元素，需平均移动（表中一半）元素，具体移动的元素个数与（表长和该元素在表中的位置）有关。5，在单链表中，除了首元素结点外，任一结点的存储位置由（其直接前驱结点的链域的值）来指示。6，在单链表中，设置头结点的作用是（对首元结点的操作和对其他结点的操作保持一致，不用特殊）。7、单链表是线性表的链接存储表示。8、两个串相等的充分必要条件是两个串的值

10、相等。9、空串是零个字符的串，其长度等于零。10、一维数组的逻辑结构是 ，存储结构是顺序存储；对二维或多维数组，分为按 列序为主序和行序为主序两种不同的存储方式。11栈和队列都是线性结构，对于栈只能在栈顶插入和删除元素，对于队列只能在队尾插入元素和队头删除元素。12栈是限定仅在表尾进行插入或删除操作的线性表，其进栈和出栈特点为先进后出；队列是只允许在表的一端进行插入，而在另一端除元素的线性表，其进队和出队特点为先进先出。13，算法有5个重要特性，分别是：（有穷性）、（确定性）、（可行性）、（输入）、（输出）。14，一个“好”的算法，通常从5个方面来衡量，它们是（正确性）、（可读性）、（健壮性）

11、（效率高）、（存储空间小）。15，顺序表中逻辑上相邻元素的物理位置（必定）（填写“必定”或“不一定”）紧邻；单链表中逻辑上相邻元素的物理位置（不一定）（填写“必定”或“不一定”）紧邻。16线性结构中元素之间存在 一个对一个关系，树形结构中元素之间存在一个对多个 关系，图形结构中元素之间存在多个对多个关系。17广义表（a），（b），c），(d)）的表头是（a），表尾是（b），c），(d)）。18 有一棵树如右图所示，这棵树的根结点是K1；结点K3的子女是K5，K6；结点K3的父结点是K1。19 根据数据元素之间关系的不同特点，数据结构可分为4种基本类型，它们分别是：集合、线性结构、树形结构和图状结构（或网状结构）。20. 用一维数组保存一组类型相同的数据元素，设数组开始存放位置LOC(0)=a,且每个数据元素占用w个存储单元,那么LOC(i)=Loc（0）+（i-1）*w 。已知广义表B（e）,则GetHead(B)=e，GetTail(B)=1。五，判断题1. 线性表的每个数据元素都有一个前驱和一个后继。X 2广度优先搜索和深度优先搜索是图的两种遍历方法。 3广义表（