兰州交大数据结构模拟试题

1.以下数据结构中，是线性结构。（单选2分）A.栈（正确答案）B.图C.树D.二叉树2.计算机算法必须具备输入、输出、等5个特性。（单选2分）A.可行性、确定性和有穷性（正确答案）B.可行性、可移植性和可扩充性C,确定性、有穷性和稳定性D.易读性、稳定性和安全性3.计算机算法指的是。（单选2分）A.解决问题的有限运算序列（正确答案）B.计算方法C.排序方法D.调度方法4.下面程序段的时间复杂度是。s=0;for（i=0;i<n;i++）forO=0;j<n;j++）s+=B[i][j];sum二s;（单选2分）°（n：）（正确答案）0（n）C.O（nlog：n）D.<XD5.设顺序表中有100个数据元素，则删除表中第85个数据元素并保持原来顺序不变，需要移动个数据元素。（单选2分）15（正确答案）168485.数组Q[100]用来存储一个循环队列，front为当前队头元素的前一位置，rear为队尾元素的位置，假定当前rear=17,front=32,则队列中元素个数为。（单选2分）85（正确答案）151686.设单链表中指针p指向结点m,若要删除m之后的结点（假设存在），则需修改指针的操作为=（单选2分）p->next=p->next->next;（正确答案）p=p->next;p=p->next->next;p->next=p;.在一个具有n个结点的有序单链表中插入一个新结点使其仍然有序，其算法的时间复杂度为0（单选2分）.°S）（正确答案）.0（1）D.O0og：n).在n个结点的顺序表中，算法的时间复杂度是0（1）的操作是o（单选2分）A.访问第i个结点（lM4n）和求第i个结点的直接前驱（2MSn）（正确答案）B.将n个结点从小到大排序C.在第i个结点后插入一个新结点（lM4n）D.删除第i个结点（14iSn）10.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素。（单选2分）63.5（正确答案）786311.若有一个栈的输入序列是1,2,3,n,输出序列的第一个元素是n,则第i个输出元素是■>（单选2分）n-i+l（正确答案）n-in-i-1D.不确定12.下面关于串的的叙述中，是不正确的。（单选2分）A.空串是由空格构成的串（正确答案）B.串是字符的有限序列C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储13.设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈。若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容量至少是。（单选2分）3（正确答案）45614.已知广义表L=（a,（（（b,c）,d）,（e,f））｝,则L的长度为。（单选2分）2（正确答案）34515.若串S="software",则其子串的数目是。（单选2分）37（正确答案）893616.已知串S="aaab",其Next数组值为«（单选2分）-1012（正确答案）-1001-1011-102317.设主串T="abccdcdccbaa",模式串P="cdcc",则第次匹配成功。（单选2分）5（正确答案）46D.718.有一个二维数组A⑻口0],每个元素占2个字节。假设A⑼网存放位置在1500,那么该数组按行优先存放时，元素A[5][7]的起始地址为。（单选2分）1614（正确答案）161616221624.已知广义表L=（a,（b,c）,d）,则运算tail（head（tail（L）））的结果为。（单选2分）（c）（正确答案）c（d）0.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,则它的前序遍历序列是o（单选2分）cedba（正确答案）acbeddecabDeabc.已知二叉树如下图所示，则该二叉树的中序遍历结果为o（单选2分）A.DGBAECHF（正确答案）B.ABDGCEFHC.GDBEHFCAD.ABCDEFGH22.已知一棵完全二叉树的第6层（设根是第1层）有8个叶子结点，则该完全二叉树的结点个数最多是。（单选2分）111（正确答案）395211923.设某棵二叉树中有1000个结点，则该二叉树的最小高度为。（单选2分）10（正确答案）9111224.设某棵二叉树的前序遍历序列为ABCDEF,中序遍历序列为CBADEF,则该二叉树的深度为o（单选2分）4（正确答案）35625.已知二叉树如下图所示，则该二叉树的前序遍历结果为oH（单选2分）ABDGCEFH （正确答案）DGBAECHFGDBEHFCAABCDEFGH.按照从上到下、从左到右的顺序，从1开始对完全二叉树进行层序编号，则结点i的右孩子结点（假设存在）的编号为.（单选2分）2i+l（正确答案）2i2i-l2（i+l）.深度为10的二叉树至多有个结点。（单选2分）1023（正确答案）1024512511.由3个结点所构成的二叉树有种形态。（单选2分）5（正确答案）346.在完全的二叉树中，若一个结点没有,则它必定是叶结点。（单选2分）A.左子树（正确答案）B.右子树C.左子树或右子树D.兄弟30.用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。（单选2分）A.栈（正确答案）B.队列C.树D.图.已知有向图如下所示，则从顶点A出发按深度优先遍历，不可能得到的结点序列是O（单选2分）ABDECF（正确答案）ABDCFEABEFDCACFBDE.已知图的邻接表结构如下，则从顶点A出发按深度优先遍历，得到的结点序列是。（单选2分）ABDCFE（正确答案）ABCDEFADBCEFABDFEC.图的深度优先遍历类似于二叉树的（单选2分）A.先序遍历（正确答案）B.中序遍历C.后序遍历D.层次遍历34.对一个具有n个顶点的图，采用邻接矩阵表示，则该矩阵的大小为（单选2分）A./（正确答案）B.nC.⑴厅D.35.10个顶点的强连通图至少有条边。（单选2分）10（正确答案）209045.有10个结点的无向连通图最少有条边。（单选2分）9（正确答案）81011.有10个结点的有向完全图有条边。（单选2分）90（正确答案）100C.45D.180.在一个有向图中，所有顶点的入度之和是所有顶点的出度之和的倍。（单选2分）1（正确答案）S24.一个有序表为｛1,3,9,12,32,41,45,62,75,77,82,95,100）,当二分查找值82为的结点时，次比较后查找成功。（单选2分）4（正确答案）12840.从空树开始依次插入结点37,28,56,80,60,14,25,50后，所构造的二叉排序树的深度是。（单选2分）4（正确答案）35641.对于一个线性表，既要求能够进行较快的插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该。（单选2分）A.以链接方式存储（正确答案）B.以顺序方式存储C.以散列方式存储D.以上均可42.假设有序线性表长度为11,在等概率的情况下，在该表上进行折半查找，则查找成功的平均查找长度为。（单选2分）3（正确答案）2.33.4443.已知一个待散列存储的线性表为（18,34,58,26,75,67,48,93,81）,散列函数为h（k）=k%11,若采用链地址法解决冲突，则检索成功时平均检索长度为.（单选2分）1匏（正确答案）16/915/914^.设散列表的长度为8,散列函数为H（k）=kmod7,采用线性探测法处理冲突，并将关键字序列（25,31,8,27,13,66）依次存储到散列表中，则关键字13存放在散列表中的地址是。（单选2分）7（正确答案）456.在对一组记录（50,40,95,20,15,70,60,45,80）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较次。（单选2分）3（正确答案）45646.在下列排序方法中，方法可能出现这种情况：在最后一趟排序开始之前，所有的元素都不在其最终应在的正确位置上。（单选2分）A.插入排序（正确答案）B.冒泡排序C.快速排序D.堆排序47.用某种排序方法对线性表（25,92,21,47,15,27,68,35,20）进行排序时，元素序列的变化情况如下：TOC\o"1-5"\h\z第一趟：15, 92, 21, 47, 25, 27, 68, 35, 20第二趟：15, 20, 21, 47, 25, 27, 68, 35, 92第三趟：15, 20, 21, 47, 25, 27, 68, 35, 92则采用的排序方法可能是o（单选2分）A.选择排序（正确答案）B.插入排序C.冒泡排序D.归并排序48.从空树开始依次插入结点34,76,45,18,26,54,92,则所构造的二叉排序树中，结点76的左孩子结点是。（单选2分）45（正确答案）54261849.每次把待排序的元素划分为左、右两个子区间，其中左区间中元素的关健字均小于等于基准元素的关键字，右区间中元素的关键字均大于等于基准元素的关键字，则此排序方法叫做。（单选2分）A.快速排序（正确答案）B.堆排序C.冒泡排序D.希尔排序.一组记录的关键字为(45,80,55,40,42,85),则利用快速排序的方法，以第一个记录为基准得到一次划分结果是。(单选2分)(42, 40, 45, 55, 80, 85)(正确答案)TOC\o"1-5"\h\z(40, 42, 45, 55, 80, 85)(42, 40, 45, 80, 55, 85)(42, 40, 45, 85, 55, 80).一组记录的关键字为(45,80,55,40,42,85),则利用堆排序的方法建立的初始堆为.(单选2分)(85, 80, 55, 40, 42, 45)(正确答案)TOC\o"1-5"\h\z(80, 45, 55, 40, 42, 85)(85, 80, 55, 45, 42, 40)(85, 55, 80, 42, 45, 40).将5个不同的数据进行排序，至多需要比较次。(单选2分)10(正确答案)8925.对n个不同的排序码进行冒泡排序，则的情况下比较的次数最多。(单选2分)A.元素从大到小排列好(正确答案)B.元素从小到大排列好C.兀素无序D.元素基本有序.快速排序在的情况下最易发挥其长处。(单选2分)A.被排序的数据完全无序(正确答案)B.被排序的数据中含有多个相同排序码C.被排序的数据己基本有序D.被排序的数据中的最大值和最小值相差悬殊.堆的形状是一棵o（单选2分）A.完全二叉树（正确答案）B.二叉排序树C.满二叉树D.平衡二叉树56.下列排序算法中，在每趟结束后不一定能选出一个元素放到其排好序的最终位置上。（单选2分）A.归并排序（正确答案）B.选择排序C.冒泡排序D.堆排序.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用存储方式最节省运算时间。（单选2分）A.仅有尾指针的单循环链表（正确答案）B.单链表C.仅有头指针的单循环链表D.双链表.以二叉链表作为二叉树存储结构，在具有n个结点的二叉链表中（n>0）,空指针域的个数为。（单选2分）n+1（正确答案）2n-ln-12n+l.带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中•（单选2分）A.第i列非零且非无穷元素个数（正确答案）B.第i行非无穷元素之和C.第i列非无穷元素之和D.第i行非零且非无穷元素个数.在有n个叶子结点的哈夫曼树中，其结点总数为。（单选2分）A.2n-l（正确答案）B.不确定2n2n+l.对任意一个图，从它的主某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。（判断1分）A.错误（正确答案）B.正确.对一个堆按层次遍历，不一定能得到一个有序序列。（判断1分）A.正确（正确答案）B.错误.任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。（判断1分）A.正确（正确答案）B.错误.删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（判断1分）A.错误（正确答案）B.正确.在枝空的情况下，不能做退栈运算，否则产生下溢。（判断1分）A.正确（正确答案）B.错误.在快速排序算法中，取待排序的n个记录中的第一个记录的键值为基准，将所有记录分为两组，该记录就排在这两组的中间，这也是该记录的最终位置。（判断1分）A.正确（正确答案）B.错误.向二叉排序树种插入一个新结点，需要比较的次数可能大于此二叉树的高度。（判断1分）A.错误（正确答案）B.正确.数据元素是数据的最小单位。（判断1分）A.错误（正确答案）B.正确.用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点的个数有关，而与图的边数无关。（判断1分）A.正确（正确答案）B.错误.已知一棵完全二叉树中共有768结点，则该二叉树中共有384个叶子结点。（判断1分）A.正确（正确答案）B.错误.在有n个顶点的有向图中，每个顶点的度最大可达n-1。（判断1分）A.错误（正确答案）B.正确.若模式串t="ababcab",则next[5]=1«（next[0]=-l）（判断1分）A.错误（正确答案）B.正确.设一棵二叉树共有50个叶子结点（终端结点），则共有51个度为2的结点。（判断1分）A.错误（正确答案）B.正确.在插入排序和选择排序中，若初始数据基本正序，则选用插入排序性能更好。（判断1分）A.正确（正确答案）B.错误.关键字序列（16,72,31,23,94,53）是一个堆。（判断1分）A.错误（正确答案）B.正确.数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。（判断1分）A.正确（正确答案）B.错误.顺序表中逻辑上相邻的元素的物理位置必定相邻，单链表中逻辑上相邻的元素的物理位置一定不相邻。（判断1分）A.错误（正确答案）B.正确.单链表的存储密度小于lo（判断1分）A.正确（正确答案）B.错误.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（判断1分）A.错误（正确答