数据结构.doc

。NOPI网龙试题库一、选择题（知识点：数据结构与算法部分）1、算法是指( ) A为解决问题而编写的计算机程序 B为解决问题而采取的方法与步骤C为解决问题而需要采用的计算机语言 D为解决问题而采用的计算方法【解题关键点】算法是指人们为了解决问题而选取的方法和实施步骤，而程序设计只是用计算机去实现问题求解的一种手段。计算机语言则是程序设计的基础，计算方法是在解决问题过程中所需要的数学模式等。 【答案】B【结束】2、设栈S的初始状态为空，现有5个元素组成的序列1，2，3，4，5，对该序列在S栈上依次进行如下操作(从序列中的1开始，出栈后不再进栈)：进栈、进栈、进栈、出栈、进栈、出栈、进栈。试问出栈的元素序列是( ) A5，4，3，2，1 B2，1 C2，3 D3，4【解题关键点】栈是一个后进先出的线性表，根据题意，可得，1、2、3进栈，然后是3出栈，4进栈，4出栈，最后5进栈，此时出栈的元素次序为3、4。【答案】D【结束】3、设循环队列中数组的下标范围是n，其中头尾指针分别是f和r，则其元素个数是( ) Ar-f Br-f+1 C(r-f) MOD n+1 D(r-f+n) MOD n【解题关键点】在容量为N的循环队列中，有可能出现两种情况，一种是尾指针R比头指针F大，则其元素个数为R-F；另一种情况是尾指针比头指针小，则其元素个数为R-F+N。为了更好地表示队列中元素的个数，可以用通用公式(r-f+n) MOD n来表示任意情况下的元素个数。【答案】D【结束】4、在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是( ) A堆排序 B希尔排序 C冒泡排序 D快速排序【解题关键点】在通常情况下，数据的徘序，常用快速排序法，然而当数据已经有序时，再用快速排序方法，就不能体现少比较数据、交换数据的特点，需要将数据进行一一比较，这样快速排序就蜕化为冒泡排序了。【答案】D【结束】5、在有n个子叶节点的哈夫曼树中，其节点总数为( ) A不确定 B2n-1 C2n+1 D2n【解题关键点】哈夫曼树是一种特殊的满二叉树，因此若有N个叶子节点，则其总节点数也是2N-1。【答案】B【结束】6、某数列有1000个各不相同的单元，由低到高按序排列，现要对该数列进行二分法检索，在最坏的情况下，需要检视( )个单元( ) A1000 B10 C100 D500【解题关键点】二分法查找元素其基本思想：将数据元素对半分，将待查找的数与中间位置数相比较，若大于该中间位置的数，则在数据段的后半段检索，否则在前半段检索。重复上述步骤，最坏的情况下需要查看10个单元。【答案】B【结束】7、已知数组A中，每个元素AI，J在存储时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存储分配的。试问：A5，8的起始地址为( ) ASA+141 BSA+180 CSA+222 DSA+225【解题关键点】数组地址计算问题，只要掌握数据是顺序存储并占用连续的存储空间。注意问题的要求按行存储还是按列存储，就能计算任意单元的起始地址。如题：按行分配空间，则A5，8前4行共40个单元，第5行开始A5，1至A5，7共7个单元，即A5，8前有47个单元，其地址是SA+(47*3)=SA+141 【答案】A【结束】8、线性表若采用链表存储结构，要求内存中可用存储单元地址( ) A必须连续 B部分地址必须连续 C一定不连续 D连续不连续均可【解题关键点】线性表中的链接存储的特点：是将零散的存储空间通过指针域连接起来，因此链接存储单元一般至少有两个域：数据域和指针域，通过指针将结点链接后生成链接表。所以存储单元地址可以连续也可以不连续。【答案】D【结束】9、下列叙述中，正确的是( )A线性表的线性存储结构优于链表存储结构 B队列的操作方式是先进后出C栈的操作方式是先进先出 D二维数组是指它的每个数据元素为一个线性表的线性表【解题关键点】二维数组本身是一个M行N列的矩阵，每行、每列都可以看做一个线性表。而其中其个元素可以看成一个列向量的线性表，也可以看成一个行向量的线性表。所以二维数组每个数据元素可以看作一个线性表的线性表。【答案】D【结束】10、电线上停着两种鸟(A，B)，可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可公为两类：一类是两端的小鸟相同；另一类是两端的小鸟不相同。已知：电线上两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是( ) A奇数 B偶数 C可奇可偶 D数目固定【解题关键点】由于线段两端相同，故此，增加一只不同鸟，产生两条两端不同小鸟的线段，增加两只不同鸟，可以产生两条或四条两端不同小鸟的线段。增加N只不同小鸟，由于线段两端是相同鸟，通过对称排列，必定是偶数个两端为不同小鸟的线段。【答案】B【结束】11、在列车转辙网络中，有四个车皮编号为1，2，3，4，并按此顺序送入栈中进行调度，这些车皮取出的顺序是( ) A4123 B3241 C3412 D4312【解题关键点】列车转辙网络是一个栈，数据进入栈中可以随时出栈，但其必须遵循后进先出的规则。故此，A中既然4最先出栈则，1不可能第二个出栈；C中既然3、4在前面出栈，1就不可能在2前出栈；D中原因同上。【答案】B【结束】12、从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端，这种排序方法称为( )A插入排序 B归并排序 C选择排序 D快速排序【解题关键点】选择排序的基本思想：每次从待排序的记录中选择出关键码值最小(或最大)的记录，顺序放在已排序的记录序列的一端，直到全部排完。【答案】C【结束】13、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于( )数据结构( ) A栈 B树 C双向队列 D广义表【解题关键点】栈是使用最广泛的数据结构之一，表达式求值、递归过程实现都是栈应用的典型例子。【答案】A【结束】14、使用双向链表存放数据的优点是( ) A提高检索速度 B很方便地插入和删除数据 C节约存储空间 D很快回收存储空间【解题关键点】链表的一个重要特点是插入、删除运算灵活，不需移动结点，只要改变结点中指针域的值就可以了。【答案】B【结束】15、对一个满二叉树，m个树叶，l分枝结点，n个结点，则( ) An=l+m Bl+m=2n Cm=l-1 Dn=2l-1【解题关键点】树叶：度为0的结点；分枝结点：度不为0的结点；结点：树中的每一个元素都叫结点。所以无论是什么二叉树，树叶+分枝结点=结点。【答案】A【结束】16、一维数组与线性表的区别是( ) A前者长度固定，后者长度可变 B后者长度固定，前者长度可变 C两者长度均固定 D两者长度均可变【解题关键点】一维数组长度固定，在定义时都必须指出其下标的范围。线性表是一个相当灵活的数据结构，它的长度可以根据需要增加或缩短。【答案】A【结束】17、用某种排序方法对线性表25,84,21,47,15,27,68,35,20进行排序，结点变化如下：(1)25,84,21,47,15,27,68,35,20;(2)20,15,21,25,47,27,68,35,84;(3)15,20,21,25,35,27,47,68,84;(4)15,20,21,25,27,35,47,68,84.那么，排序方法是( ) A选择排序 B希尔排序 C合并排序 D快速排序【解题关键点】选择排序的基本思想：每次从待排序的记录中选择出关键码值最小(或最大)的记录，顺序放在已排序的记录序列的一端，直到全部排完。【答案】D【结束】18、具有12个记录的序列，采用冒泡排序最少的比较次数是( ) A1 B144 C11 D66【解题关键点】冒泡排序的基本思想：对待排序的记录的关键字进行两两比较，发现两个记录是反序的，则进行交换，直到无反序排序的记录为止。最理想的情况就是原来已经没有反序排序的记录，那么只需要比较n-1次就可以完成了。【答案】C【结束】19、下面关于二叉树的叙述正确的是( ) A一棵二叉树中叶子结点的个数等于度为2的结点个数加1 B一棵二又树中的结点个数大于0 C二叉树中任何一个结点要么是叶，要么恰有两个子女 D二叉树中，任何一个结点的左子树和右子树上的结点个数一定相等【解题关键点】二叉树的性质：对于任意一棵二叉树，如果其端结点数为N，而其度为2的结点总数为M时，有N=M+1。【答案】A【结束】20、先序序列和中序序列相同的二叉树为空树或( ) A任一结点均无右孩子的非空二叉树 B仅有两个结点的二叉树 C任一结点均无左孩子的非空二叉树 D不存在这样的二叉树【解题关键点】二叉树的先序序列顺序为：根左右；中序序列顺序为：左根右；要其两个序列的结果相同，必须是缺少了左子树，即大家都变成了根右的顺序了。【答案】C【结束】21、设有三个元素A、B、C顺序进栈，在进栈过程中可以出栈，出栈次序错误的排列是( ) AABC BBCA CCAB DCBA【解题关键点】栈是一个后进先出的线性表，C：如果C先出栈，则必定是A、B均在栈中，而且B比A后进栈，所以出栈必须是B比A先出。【答案】C【结束】22、下面四种内排序方法中，要求内存容量最大的是( ) A插入排序 B选择排序 C快速排序 D归并排序【解题关键点】几种排序需要内存容量的比较：插入排序：1；选择排序：1；快速排序：以2为底n的对数；归并排序：n。所以最大的是归并排序。【答案】D【结束】23、设有序列F：（49，38，65，97，76，13，27，50），使用快速排序法，其趟数为( ) A3 B2 C1 D4【解题关键点】快速排序：第一趟：27,38,13,49,76,96,65,50；第二趟：13,27,38,49,76，96，65，50(对左子表排序)；第三趟：13,27,38,49,50,65,76,96(对右子表排序)。【答案】A【结束】24、给出一组整型数28、10、37、63、35、30、23，请用二叉树对它进行排序。为此，首先要生成一棵二叉树，规则是把第一数放在根处，接着凡比它小的数放在左子树，比它大的数放在右子树，直到把所有的数均安排好。然后对此二叉树进行( )，得到的就是按照升序排列好的序列。 A前序遍历 B中序遍历 C后序遍历 D横向遍历【解题关键点】利用二叉树对一组数进行排序，先生成一棵二叉排序树，然后进行中序遍历，所得的结果就是按升序排列的数据。【答案】B【结束】25、用某种排序方法对线性表(84,47,25,15,21)进行排序时，结点序列的变化如下： (1)84,47,25,15,21;(2)15,47,25,84,21;(3)15,21,25,84,47;(4)15,21,25,47,84.那么，所采用的排序方法是( ) A选择排序 B冒泡排序 C插入排序 D快速排序【解题关键点】选择排序的基本思想：每次从待排序的记录中选择出关键码值最小(或最大)的记录，顺序放在已排序的记录序列的一端，直到全部排完。这是一个典型的选择排序。【答案】A【结束】26、设二叉树根结点的层次为0，一棵高度为b的满二叉树中结点的个数是( ) A2b B2(b-1) C2b-1 D2(b+1)-1【解题关键点】在二叉树中，第I层的结点总数不超过2(I-1)；而深度为K的二叉树的结点总数不超过2k-1。故满二叉树的结点总数为：2k-1(k为二叉树的深度)【答案】C【结束】27、深度为5的二叉树至多有( )个结点 A16 B32 C31 D10【解题关键点】满二叉树的结点总数为：2k-1(k为二叉树的深度)。由此得：25-1=31。【答案】C【结束】28、下面关于线性表的描述，错误的是( ) A栈是线性表的一种 B任给一个索引I（1=I=表中元素个数），就能在线性表中唯一确定一个元素 C线性表的任一元素都有前驱和后继 D线性表是一个线性序列【解题关键点】线性表的第一个元素没有前趋元素，线性表的最后一个元素没有后继元素。【答案】C【结束】29、带权路径长度最小的二叉树是( ) A顺序二叉树 B二叉排序树 C判定树 D哈夫曼树【解题关键点】哈夫曼树，又称最优树，是一类带权路径最短的树。【答案】D【结束】30、有12个结点的平衡二叉树的最大深度是( ) A4 B5 C6 D3【解题关键点】平衡二叉树，又称AVL树。它或者是一棵空树，或具有下列性质的二叉树：(1)左子树和右子树都是平衡二叉书树；(2)左子树和右子树的深度之差的绝对值不超过1。由此，12个结点的平衡二叉树的深度最多可以为5层。【答案】B【结束】31、若用冒泡排序法对序列18，14，6，27，8，12，16，52，10，26，47，29，41，24从小到大进行排序，共要进行( )次比较。 A33 B45 C70 D91【解题关键点】冒泡排序：对待排序的记录进行逐个比较，如发现两个记录是反序的，则进行交换，直到无反序排列的记录为止，即当一次比较后没有进行交换则排序完成。由此可得，当第七趟排序时就没有出现交换了，所以只比较了70次就可以完成排序。【答案】C【结束】32、设n，m为某二叉树上的两个结点，在中序遍历时，n在m前的条件是( ) An在m右方 Bn是m祖先 Cn在m左方 Dn是m子孙【解题关键点】中序遍历的顺序是左根右；故此要n在m前，必须n在m的左方。【答案】C【结束】33、下列四种排序方法，如果被排序的序列中诸元素恰好已经按要求（由小到大或由大到小排序，就元素的比较次数和移动次数而言，哪种方法最少？( ) A冒泡排序 B直接选择排序 C直接插入排序 D归并排序【解题关键点】直接插入排序的比较的次数为n-1次，交换次数为0。【答案】C【结束】34、如果某二叉树的前序为STUWV，中序为UWTVS，那么该二叉树的后序是( ) AWUVTS BUWVTS CVWUTS DWUTSV【解题关键点】由于已知二叉树的前序与中序后，可画出二叉树，并得出后序。由于前序为STUWV，所以根必然是S，由于中序是UWTVS，故此此二叉树没有右子树。左子树前序为TUWV可得左子树根为T，中序为UWTV可得左子树根T有一右子根V，左子树T的左子树根为U，U有一右子树W。故此后序为A。【答案】A【结束】35、按照二叉树的定义，具有3个结点的二叉树有( ) A3种 B4种 C5种 D6种【解题关键点】具有3个结点的的二叉树有5种。分别是：左孙、左子、根；右孙、左子根；左子、根、右子；根、右子、左孙；根、右子、右孙。【答案】C【结束】36、对以下关键字序列用快速排序法进行排序，速度最慢的情况是( ) A19，23，3，15，7，21，8 B23，21，28，15，19，3，7 C19，7，15，28，23，21，3 D3，7，15，19，21，23，28【解题关键点】快速排序适用了原数列没有序的情况，如果原数大部分成序的话，速度越慢。最慢的情况就是所有数据已经成序。【答案】D【结束】37、数组A中，每个元素AI，j的长度为3个字节，行下标I为1到8，列下标j从1到10。从首地址SA开始连续存放在存储器中，存放该数组至少需要的单元数是( ) A80 B100 C240 D270【解题关键点】该数组一共有80个元素，一个元素需要3个字节，故存放该数组至少需要240个字节。 【答案】C【结束】38、树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。正确的结论是( ) A树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B树的先根遍历序列与其对应的二叉树的中序遍历序列相同 C树的后根遍历序列与其对应的二叉树的先序遍历序列相同 D树的后根遍历序列与其对应的二叉树的后序遍历序列相同【解题关键点】因为把树转化为二叉树时，把所有原来同层的子树都变成了原来的左子树的右子树了。故此，树的先根遍历序列与其对应的二叉树的先序遍历序列相同。【答案】A【结束】39、在数据结构中，从逻辑上可以把数据结构分成( ) A动态结构和静态结构 B线性结构和非线性结构 C内部结构和外部结构 D紧凑结构和非紧凑结构【解题关键点】在数据结构中，从逻辑上把数据结构分成线性结构和非线性结构。【答案】B【结束】40、如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的( ) A前序 B中序 C后序 D层次序【解题关键点】因为把树转化为二叉树时，把所有原来同层的子树都变成了原来的左子树的右子树了。故此，有序树的后序就是其转化成得的二叉树的中序。【答案】B【结束】41、某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是( ) Abdgcefha Bgdbecfha Cbdgaechf Dgdbehfca【解题关键点】通过二叉树的先序与中序可以写出二叉树，并由此可以得出后序为gdbehfca。【答案】D【结束】42、从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端，这种排序方法称为( ) A插入排序 B选择排序 C归并排序 D快速排序【解题关键点】选择排序的基本思想是：每次从待排序的记录中选择出最小(或最大)的记录，顺序放在已排好的记录序列的最后。【答案】B【结束】43、快速排序方法在( )情况下最不利于发挥其长处 A被排序的数据量太大 B被排序数据中含有多个相同值 C被排序数据已基本有序 D被排序数据数目为奇【解题关键点】快速排序在被排序数据中已基本有序的情况下最不利于发挥其长处。【答案】C【结束】44、下面关于数据结构的叙述中，正确的叙述是( ) A顺序存储方式的优点是存储密度大，且插入、删除运算效率高 B链表中的每一个结点都包含一个指针 C包含n个结点的二叉排序树的最大检索长度为log-2n D将一棵树转换为二又树后，根结点没有右子树【解题关键点】A：顺序存储插入、删除运算效率低；B：链表中的最后一个结点的指针域为空。C：包含n个结点的二叉排序树的平均检索长度为(log2n)2为底n的对数。【答案】D【结束】THANKS !致力为企业和个人提供合同协议，策划案计划书，学习课件等等打造全网一站式需求欢迎您的下载，资料仅供参考-可编辑修改-