《(补充)数据结构与算法练习.doc》由会员分享，可在线阅读，更多相关《(补充)数据结构与算法练习.doc（7页珍藏版）》请在金锄头文库上搜索。
1、(补充)数据结构与算法练习1、在顺序存储的线性表(a1,a2,.,an)中,删除任意一个结点时所需移动结点的平均次数为（C）。 A、n B、n/2 C、(n-1)/2 D、(n+1)/22、下列数据组织形式中，（C）的结点按逻辑关系依次排列形成一个锁链。A、集合B、树形结构C、线性结构D、图状结构3、下列数据结构中，（D）不都是线性结构。A、栈和队列 B、队列和数组 C、数组和串 D、文件和队列4、下列说法正确的是（C）A、数据是数据元素的基本单位B、数据元素是数据项中不可分割的最小标识单位C、数据可由若干个数据元素构成D、数据项可由若干个数据元素构成5、下列数据组织形式中，（D）的各个结点可
2、以任意邻接。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(n) C、O(nlog2n) D、O(n2)21、设非空单链表的数据域为data，指针域
3、为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、共同之处在于二者都是先进先出的特殊的线性表 B、共同之处在于二者都是先进后出的特殊的线性表 C、共同之处在于二者都只允许在顶端执行删除操作 D、没有共同之处 23、若有一串数字5、6、7、8入栈，则其不可能的输出序
4、列为(C)A.5、6、7、8B.8、7、6、5C.8、7、5、6D.5、6、8、724、我们通常把队列中允许删除的一端称为队头。25、有关栈的描述，正确的是（B）A、栈是一种先进先出的特殊的线性表B、只能从栈顶执行插入、删除操作C、只能从栈顶执行插入、栈底执行删除D、栈顶和栈底均可执行插入、删除操作26、顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素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
5、、s.top=s.top+1； s.elems.top=e；27、循环队列sq中，用数组elem025存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（D）A、8 B、16 C、17 D、1828、深度为k的二叉树至多有(B)A、2k个叶子 B、2k-1个叶子C、2k-1个叶子D、2k-1-1个叶子28、关于二叉树性质的描述，正确的是（A）A、二叉树结点的个数可以为0B、二叉树至少含有一个根结点C、二叉树若存在两个结点，则必有一个为根，另一个为左孩子D、二叉树若存在三个结点
6、，则必有一个为根，另两个分别为左、右孩子29、具有4个结点的二叉树可有（12种形态?）A、4种形态B、7种形态C、10种形态D、11种形态30、树形结构的特点是：一个结点可以有（B）。A、多个直接前趋 B、多个直接后继 C、多个前趋 D、一个后继31、将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点（B）A、无左、右孩子B、有左孩子，无右孩子C、有右孩子，无左孩子D、有左、右孩子32、具有100个结点的完全二叉树的深度为（B）A、6 B、7 C、8 D、933、一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（D）A、2
7、，14B、2，15C、3，14D、3，1534、除根结点外，树上每个结点（B）A、可有任意多个孩子、任意多个双亲B、可有任意多个孩子、一个双亲C、可有一个孩子、任意多个双亲D、只有一个孩子、一个双亲35、具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（D）个指针域为空。A、50B、99C、100D、10136、顺序查找法与二分查找法对存储结构的要求是（D）A、顺序查找与二分查找均只适用于顺序表B、顺序查找与二分查找既适用于顺序表，也适用于链表C、顺序查找只适用于顺序表D、二分查找只适用于有序的顺序表37、对于静态表顺序查找算法，若在表头设置岗哨，则正确
8、的查找方式为（C）。A、从第0个元素往后查找该数据元素 B、从第1个元素往后查找该数据元素C、从第n个元素开始往前查找该数据元素 D、与查找顺序无关38、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于（B）A、静态查找表B、动态查找表C、静态查找表与动态查找表D、两种表都不适合39、若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（B）A、该中间位置B、该中间位置1C、该中间位置1D、该中间位置240、下列程序段的时间复杂性量级是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，ACB45、分别写出下列二叉树的先根、中根、后根遍历序列。答：先根：ABCEDFGH，中根：CEBDGFHA，后根：ECGHFDBA?2
