09数据结构练习题

一．1．数据的不可分割的基本单位是(A)。A．元素B．结点C．数据类型D．数据项2．算法是指(C)。A．计算方法B．排序方法C．解决问题的有限运算步骤D．查找方法3．顺序存储结构中数据元素之间的逻辑关系是由（C）表示的A线性结构B非线性结构C存储位置D指针4．单循环链表的主要优点是（B）。A不再需要头指针了B从表中任一结点出发都能扫描到整个链表；C已知某个结点的位置后，能够容易找到它的直接前趋；D在进行插入、删除操作时，能更好地保证链表不断开。5．一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是(C)。A54321B45321C43512D123456．常对数组进行的两种基本操作是(C)A．建立和删除B．索引和修改C．查找和修改D．插入和索引7．算法分析的两个主要方面是（A）。A空间性能和时间性能B正确性和简明性C可读性和文档性D数据复杂性和程序复杂性8．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（B）结构。A栈B队列C数组D线性表9．二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（D）个字节。数组A为9行10列，共有90个元素，所以，存放A至少需要90×6=540个存储单元A90B180C240D54010．下面（C）不属于特殊矩阵。A对角矩阵B三角矩阵C稀疏矩阵D对称矩阵13．算法在发生非法操作时可以作出处理的特性称为（A）。A健壮性B确定性C可行性D正确性16．算法指的是（A）。A对特定问题求解步骤的一种描述，是指令的有限序列。B计算机程序C解决问题的计算方法D数据处理17．算法分析的目的是(C)。A．找出数据结构的合理性B．研究算法中输入和输出的关系C．分析算法的效率以求改进D．分析算法的易读性和文档性18．若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋，则采用（A）存储方法最节省时间。A顺序表B单链表C双链表D单循环链表19．在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（B）操作。As-next=p-next;p-next=s;Bq-next=s;s-next=p;Cp-next=s-next;s-next=p;Dp-next=s;s-next=q;20．若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（D）。A不确定Bn-iCn-i-1Dn-i+121．设有两个串p和q，求q在p中首次出现的位置的运算称作（B）。A连接B模式匹配C求子串D求串长22．将数组称为随机存取结构是因为（B）。A数组元素是随机的B对数组任一元素的存取时间是相等的C随时可以对数组进行访问D数组的存储结构是不定的23．一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（D）成立。【分析】满二叉树中没有度为1的结点，所以有m个叶子结点，则度为2的结点个数为m-1。An=h+mBh+m=2nCm=h-1Dn=2m-124．队列的操作原则是（B）。A．先进后出B．先进先出C．只能进行插入D．只能进行删除26．在栈中，栈顶指针top指示(B)。A．栈底元素的位置B．栈顶元素的位置C．栈中任何元素的位置D．以上均不对27．将数组称为随机存取结构是因为（B）。A．数组元素是随机的B．对数组任一元素的存取时间是相等的C．随时可以对数组进行访问D．数组的存储结构是不定的28．下面（C）不是算法所必须具备的特性。A有穷性B确切性C高效性D可行性29．在一棵树中，（B）没有后继结点。A．根结点B．叶子结点C．分支结点D．所有结点31．若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（D）存储方法最节省时间。在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以，答案是D。A单链表B带头指针的单循环链表C双链表D带尾指针的单循环链表32．设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（C）。A6B4C3D233．二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9,A的第8列和第5行共占（C）个字节。A114B54C108D54034．在一棵树中，每个结点最多有(B)个前驱结点。A．0B．1C．2D．任意多个35．一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（B）。A4321B1234C1432D324136．下面的说法中，不正确的是（C）。A数组是一种线性结构B数组是一种定长的线性结构C除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等D数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作37．队列的操作原则是(B)。A．先进后出B．先进先出C．只能进行插入D．只能进行删除38．如果结点A有3个兄弟，B是A的双亲，则结点B的度是（D）。A1B2C3D439．静态查找与动态查找的根本区别在于（B）。静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作A它们的逻辑结构不一样B施加在其上的操作不同C所包含的数据元素的类型不一样D存储实现不一样40．在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为（B）。A不变Btop=top-1Ctop=0Dtop=top+142．算法能正确地实现预定功能的特性称为(A)。A．正确性B．易读性C．健壮D．高效率44．线性表的顺序存储结构是一种（A）的存储结构。A随机存取B顺序存取C索引存取D散列存取45．假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（B）。A树B图C线性表D集合46．数组通常具有两种基本运算，即（B）A．创建和删除B．读取和修改C．插入和删除D．排序和查找47．线性表采用链接存储时，其地址（D）。A必须是连续的B部分地址必须是连续的C一定是不连续的D连续与否均可以49．线性表的第一个元素叫做（A）。A．表头元素B．表尾元素C．前驱元素D．后继元素50．线性表的最后一个元素叫做（B）。A．表头元素B．表尾元素C．前驱元素D．后继元素51．设二叉树有n个结点，则其深度为（C）。An-1BnClog2n向下取整D不能确定52．G是一个非连通无向图，共有28条边，则该图至少有（D）个顶点。n个顶点的无向图中，边数e≤n(n-1)/2，将e=28代入，有n≥8，现已知无向图非连通，则n=9。A6B7C8D953．在以下哪种情况下，不能执行出栈操作？（B）A．栈满B．栈空C．任何情况均可D．任何情况均不可54．下列数据结构中，（D）不是线性结构。A．栈B．队列C．数组D．树55．栈又称为（B）表。A．先进先出B．后进先出D．不进不出D．以上均不对56．在以下哪种情况下，不能执行入栈操作？（A）A．栈满B．栈空C．任何情况均可D．任何情况均不可60．非空树有（B）个根结点。A．0B．1C．2D．任意多个61．串是一种特殊的线性表，其特殊性体现在(B)A．可以顺序存储B．数据元素是一个字符C．可以链接存储D．数据元素可以是多个字符63．数组中的数据元素的类型（A）。A．必须相同B．不必相同C．一定不能相同D．以上都不对64．下列数据结构中，(D)不都是线性结构。A．栈和队列B．队列和数组C．数组和串D．树和队列65．关于空串与空格串，下面说法正确的是(C)。A．空串与空格串是相同的B．空串与空格串长度是相同的C．空格串中存放的都是空格D．空串中存放的都是NULL66．递归可采用下面哪种结构实现（C）A．队列B．栈C．树D．图67．栈操作的原则是(B)A．先进先出B．后进先出C．只能进行插入D．只能进行删除69．如果一个函数在其函数体中调用自己本身，则该函数叫做(B)。A．重载函数B．递归函数C．普通函数D．成员函数70．线性表若采用链式存储结构时，要求内存中可用存储单元的地址(D)A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以71．设计一个判别表达式中左右括号是否配对的算法，采用（B）数据结构最佳。A顺序表B栈C队列D链表72．下面的说法中，不正确的是（D）。(稀疏矩阵中大量值为零的元素分布没有规律，因此采用三元组表存储。如果零元素的分布有规律，就没有必要存储非零元素的行号和列号，而需要按其压缩规律找出相应的映象函数。)A对称矩阵只须存放包括主对角线元素在内的下（或上）三角的元素即可。B对角矩阵只须存放非零元素即可。C稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。D稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储。73、请回答下列关于图的问题：(1)一个具有n个顶点的完全图的边数为____________。(2)无向图中的连通分量定义为无向图的____极大连通子图___。(3)设无向图G的顶点数为n，则G最少有______________条边。(4)一个具有n个顶点的有向完全图的弧数为____n(n-1)________。(5)有向图中的强连通分量定义为有向图的____极大连通子图___。74．连通分量是___A____的极大连通子图。A.无向图B.有向图C.树D.图75．强连通分量是__B_____的极大连通子图。A.无向图B.有向图C.树D.图76．有n个顶点的无向图的邻接矩阵是用__A____数组存储。A.n行n列B.一维C.任意行n列D.n行任意列77．下列有关图遍历的说法中不正确的是_______。A.连通图深度优先搜索是个递归过程B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C.非连通图不能用深度优先搜索法D.图的遍历要求每一顶点仅被防问一次二．计算题1．有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，列出所有可能的出栈序列。abc,acb,bac,cba,cba2．栈S=(a，b，c)，在栈中插入1个元素d，再从栈中删除一个元素，请写出S的变化过程。3．队列Q=(a，b，c)，在队列中插入1个元素d，再从队列中删除一个元素，请写出Q的变化过程。4．请根据下图回答下列问题①哪个是根结点?A②哪些是叶子结点?D,G③哪个是结点C的双亲?A,④哪些是结点C的孩子?E,F⑤C的兄弟是哪个结点？B⑥F的堂兄弟是哪个结点？D⑦哪些结点是C的子孙结点E，F，G？⑧树的深度是多少?4⑨树的度是多少？2⑩请写出该树的先根遍历序列、中根序列、后根序列、层次遍历序列。ABDCEFGBDAECGFDBEGFCAABCDEFG5．若对序列(56，23，67，4，88，12，55)采用直接插入排序法和冒泡排序法进行排序，请写出每一趟的结果。直接插入排序法:(56，23，67，4，88，12，55)6．请写出求数组最大值、最小值、平均值的递归算法。7．请写出求2个正整数相乘的递归算法。8．请写出对二叉树进行先序遍历、中序遍历、后序遍历、求二叉树高度、结点个数、叶子结点个数等递归算法。三．问答题1．什么是数据结构？ABCGFED数据结构是研究非数值问题中计算机的操作对象以及它们之间的关系和操作的学科。2．什么是算法？算法的五大特性是什么？算法（Algorithm）:是对特定问题求解步骤的一种描述，是指令的有限序列。算法的五大特性：⑴输入：一个算法有零个或多个输入。⑵输出：一个算法有一个或多个输出。⑶有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。⑷确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。⑸可行性：算法描述的操作可