09数据结构练习题.doc

_一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 )。 A 54321 B 45321 C 43512 D 12345 6常对数组进行的两种基本操作是( C )A建立和删除B 索引和修改C查找和修改D插入和索引7算法分析的两个主要方面是（A ）。A空间性能和时间性能 B正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性 8在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区， 该缓冲区应该是一个（ B）结构。 A 栈 B 队列 C 数组 D 线性表 9二维数组A的每个元素是由6个字符组成的串，行下标的范围从08，列下标的范围是从09，则存放A至少需要（D）个字节。数组A为9行10列，共有90个元素，所以，存放A至少需要906=540个存储单元 A 90 B 180 C 240 D 540 10下面（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）操作。 A s-next=p-next; p-next=s; B q-next=s; s-next=p; C p-next=s-next; s-next=p; D p-next=s; s-next=q; 20若一个栈的输入序列是1，2，3，n，输出序列的第一个元素是n，则第i个输出元素是（D ）。 A 不确定 B n-i C n-i-1 D n-i+1 21设有两个串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。 A n=h+m B h+m=2n C m=h-1 D n=2m-1 24队列的操作原则是（ 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 ）。 A 6 B 4 C 3 D 2 33 二维数组A的每个元素是由6个字符组成的串，行下标的范围从08，列下标的范围是从09, A的第8列和第5行共占（C）个字节。 A 114 B 54 C 108 D 540 34在一棵树中，每个结点最多有 ( B ) 个前驱结点。A0 B1 C2 D任意多个35一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（B ）。 A 4321 B 1234 C 1432 D 3241 36下面的说法中，不正确的是（C）。 A 数组是一种线性结构 B 数组是一种定长的线性结构 C 除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等 D 数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作 37队列的操作原则是( B )。A 先进后出 B 先进先出 C 只能进行插入 D 只能进行删除38如果结点A有3个兄弟，B是A的双亲，则结点B的度是（D）。 A 1 B 2 C 3 D 4 39静态查找与动态查找的根本区别在于（ B）。静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作 A 它们的逻辑结构不一样 B 施加在其上的操作不同 C 所包含的数据元素的类型不一样 D 存储实现不一样 40在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为（B ）。 A 不变 B top=top-1 C top=0 D top=top+1 42算法能正确地实现预定功能的特性称为 ( 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）。 A n-1 B n C log2n向下取整+1 D 不能确定 52G是一个非连通无向图，共有28条边，则该图至少有（ D）个顶点。 n个顶点的无向图中，边数en(n-1)/2，将e=28代入，有n8，现已知无向图非连通，则n=9。 A 6 B 7 C 8 D 9 53在以下哪种情况下，不能执行出栈操作？（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 0 B1C2D 任意多个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的变化过程。ABCGFED4请根据下图回答下列问题 哪个是根结点?A 哪些是叶子结点? D , G哪个是结点C的双亲? A,哪些是结点C的孩子? E,F C的兄弟是哪个结点？B F的堂兄弟是哪个结点？D 哪些结点是C的子孙结点 E ， F ， G？ 树的深度是多少? 4 树的度是多少？ 2 请写出该树的先根遍历序列、中根序列、后根序列、层次遍历序列。 ABDCEFG BDAECGF DBEGFCA ABCDEFG 5若对序列(56，23，67，4，88，12，55)采用直接插入排序法和冒泡排序法进行排序，请写出每一趟的结果。直接插入排序法:(56，23，67，4，88，12，55)6请写出求数组最大值、最小值、平均值的递归算法。7请写出求2个正整数相乘的递归算法。8请写出对二叉树进行先序遍历、中序遍历、后序遍历、求二叉树高度、结点个数、叶子结点个数等递归算法。三问答题1什么是数据结构？数据结构是研究非数值问题中计算机的操作对象以及它们之间的关系和操作的学科。2什么是算法？算法的五大特性是什么？算法（Algorithm）:是对特定问题求解步骤的一种描述，是指令的有限序列。算法的五大特性： 输入：一个算法有零个或多个输入。 输出：一个算法有一个或多个输出。 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。3栈是什么？请描述栈的特性，并画图说明。栈：限定仅在表尾进行插入和删除操作的线性表。 “后进先出”4请阐述栈和队列的异同点。相同点：都是线性结构，都是逻辑结构的概念。栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：运算规则不同，栈是只允许在一端进行插入、删除运算，因而是后进先出；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出。5什么是递归？请阐述递归程序和非递归程序的优缺点。子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。 6请阐述线性结构和树状结构的异同点。7二叉树的五种形态？8什么是顺序存储结构和链式存储结构？它们的优缺点？在什么情况下用顺序表比链表好？顺序表的优点： 无需为表示表中元素之间的逻辑关系而增加额外的存储空间； 可以快速地存取表中任一位置的元素（即随机存取）。顺序表的缺点： 插入和删除操作需移动大量元素； 表的容量难以确定； 造成存储空间的“碎片”。 单链表的优点： 不必事先知道线性表的长度； 插入和删除元素时只需修改指针，不用移动元素。单链表的缺点： 指针的结构性开销； 存取表中任意元素不方便，只能进行顺序存取。 应选用顺序存储结构。因为顺序表是随机存取结构，单链表是顺序存取结构。本题很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。 应选用链接存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。顺序存储结构的特点是用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，链接存储结构的特点是用指示元素存储地址的指针表示数据元素之间的逻辑关系。Welcome ToDownload !欢迎您的下载，资料仅供参考！精品资料