《(补充)数据结构与算法练习.pdf》由会员分享，可在线阅读，更多相关《(补充)数据结构与算法练习.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！1、在顺序存储的线性表(a1,a2,.,an)中,删除任意一个结点时所需移动结点的平均次数为（C）。A、n B、n/2 C、(n-1)/2 D、(n+1)/2 2、下列数据组织形式中，（C）的结点按逻辑关系依次排列形成一个“锁链”。A、集合 B、树形结构 C、线性结构 D、图状结构 3、下列数据结构中，（D）不都是线性结构。A、栈和队列 B、队列和数组 C、数组和串 D、文件和队列 4、下列说法正确的是（C）A、数据是数据元素的基本单位 B、数据元素是数据项中不可分割的最小标识单位 C、数据可由若干个
2、数据元素构成 D、数据项可由若干个数据元素构成 5、下列数据组织形式中，（D）的各个结点可以任意邻接。A、集合 B、树形结构 C、线性结构 D、图状结构 6、数据的四种基本逻辑结构是指(D)A、数组、链表、树、图形结构 B、线性表、链表、栈队列、数组广义表 C、线性结构、链表、树、图形结构 D、集合、线性结构、树、图形结构 7、下列程序的时间复杂度为（A）i=0；s=0；while（snext B、p-next=p-next C、p-next=p-next-next D、p-next=p 20、在一个具有 n 个结点的双链表中插入一个新结点，则该操作的时间复杂性的量级为（A）A、O(1)B、O
3、(n)C、O(nlog2n)D、O(n2)21、设非空单链表的数据域为 data，指针域为 next，指针 p 指向单链表中第 i 个结点，s 指向已生成的新结点，现将 s 结点插入到单链表中，使其成为第 i 个结点，下列算法段能正确完成上述要求的是（C）A、s-next=p-next;p-next=s；B、p-next=s;s-next=p-next；欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！C、s-next=p-next;p-next=s;交换 p-data 和 s-data；D、p=s;s-next=p；22、栈和队列(C)A、共同之处
4、在于二者都是先进先出的特殊的线性表 B、共同之处在于二者都是先进后出的特殊的线性表 C、共同之处在于二者都只允许在顶端执行删除操作 D、没有共同之处 23、若有一串数字 5、6、7、8 入栈，则其不可能的输出序列为(C)A.5、6、7、8 B.8、7、6、5 C.8、7、5、6 D.5、6、8、7 24、我们通常把队列中允许删除的一端称为队头。25、有关栈的描述，正确的是（B）A、栈是一种先进先出的特殊的线性表 B、只能从栈顶执行插入、删除操作 C、只能从栈顶执行插入、栈底执行删除 D、栈顶和栈底均可执行插入、删除操作 26、顺序栈 S 中 top 为栈顶指针，指向栈顶元素所在的位置，elem
5、 为存放栈的数组，则元素 e 进栈操作的主要语句为（D）A、s.elemtop=e；s.top=s.top+1；B、s.elemtop+1=e；s.top=s.top+1；C、s.top=s.top+1；s.elemtop+1=e；D、s.top=s.top+1；s.elems.top=e；27、循环队列 sq 中，用数组 elem0 25存放数据元素，sq.front 指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前 sq.front 为 20，sq.rear 为 12，则当前队列中的元素个数为（D）A、8 B、16 C、17 D、18 28、深度为 k 的二叉树至多有
6、(B)A、2k个叶子 B、2k-1个叶子 C、2k-1 个叶子 D、2k-1-1 个叶子 28、关于二叉树性质的描述，正确的是（A）A、二叉树结点的个数可以为 0 B、二叉树至少含有一个根结点 C、二叉树若存在两个结点，则必有一个为根，另一个为左孩子 D、二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子 29、具有 4 个结点的二叉树可有（12 种形态?）A、4 种形态 B、7 种形态 C、10 种形态 D、11 种形态 30、树形结构的特点是：一个结点可以有（B）。A、多个直接前趋 B、多个直接后继 C、多个前趋 D、一个后继 31、将一棵有 50 个结点的完全二叉树按层编号，则
7、对编号为 25 的结点 x，该结点（B）A、无左、右孩子 B、有左孩子，无右孩子 C、有右孩子，无左孩子 D、有左、右孩子 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！32、具有 100 个结点的完全二叉树的深度为（B）A、6 B、7 C、8 D、9 33、一棵有 16 结点的完全二叉树，对它按层编号，则对编号为 7 的结点 X，它的双亲结点及右孩子结点的编号分别为（D）A、2，14 B、2，15 C、3，14 D、3，15 34、除根结点外，树上每个结点（B）A、可有任意多个孩子、任意多个双亲 B、可有任意多个孩子、一个双亲 C、可有一个孩子
8、、任意多个双亲 D、只有一个孩子、一个双亲 35、具有 100 个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（D）个指针域为空。A、50 B、99 C、100 D、101 36、顺序查找法与二分查找法对存储结构的要求是（D）A、顺序查找与二分查找均只适用于顺序表 B、顺序查找与二分查找既适用于顺序表，也适用于链表 C、顺序查找只适用于顺序表 D、二分查找只适用于有序的顺序表 37、对于静态表顺序查找算法，若在表头设置岗哨，则正确的查找方式为（C）。A、从第 0 个元素往后查找该数据元素 B、从第 1 个元素往后查找该数据元素 C、从第 n 个元素开始往前查找该
9、数据元素 D、与查找顺序无关 38、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于（B）A、静态查找表 B、动态查找表 C、静态查找表与动态查找表 D、两种表都不适合 39、若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（B）A、该中间位置 B、该中间位置1 C、该中间位置1 D、该中间位置2 40、下列程序段的时间复杂性量级是 o(n2)。for(i=1;in;i+)for(j=1;jtop+；sq-datasq-top=x；43、链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的队尾结点。欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！44、如图所示，输入元素为 A，B，C，在栈的输出端得到一个输出序列 ABC，求出在栈的输入端所有可能的输入序列。（5 分）答：ABC，CBA，CAB，BAC，ACB 45、分别写出下列二叉树的先根、中根、后根遍历序列。答：先根：ABCEDFGH，中根：CEBDGFHA，后根：ECGHFDBA