搜索
一、单选题（共25道试题，共50分。）1.若串S=’software’,其子串的数目是（）A.8B.37C.36D.92.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（）A.p-next=s;s-next=p-next;B.s-next=p-next;p-next=s;C.p-next=s;p-next=s-next;D.p-next=s-next;p-next=s;3.链表不具有的特点是（）A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4.对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。A.选择B.快速C.希尔D.冒泡5.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列（）A.543612B.453126C.346521D.2341566.适用于折半查找的表的存储方式及元素排列要求为（）A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序7.字符串‘ababaabab’的nextval为（）A.(0,1,0,1,04,1,0,1)B.(0,1,0,1,0,2,1,0,1)C.(0,1,0,1,0,0,0,1,1)D.(0,1,0,1,0,1,0,1,1)8.对于栈操作数据的原则是（）A.先进先出B.后进先出C.后进后出D.不分顺序9.下面的程序段中，对x的赋值语句的频度为（）FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A.O(2n)B.O(n)C.O(n2)D.O(log2n)10.散列函数有一个共同的性质，即函数值应当以（）取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率11.在用邻接表表示图时，拓扑排序算法时间复杂度为（）A.O(n)B.O(n＋e)C.O(n*n)D.O(n*n*n)12.栈在（）中应用。A.递归调用B.子程序调用C.表达式求值D.A，Ｂ，Ｃ13.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEG14.从逻辑上可以把数据结构分为（）两大类A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构15.若要求尽可能快地对序列进行稳定的排序，则应选（）A.快速排序B.归并排序C.冒泡排序D.堆16.已知串S=‘aaab’,其Next数组值为（）A.0123B.1123C.1231D.121117.树的后根遍历序列等同于该树对应的二叉树的（）A.先序序列B.中序序列C.后序序列D.都不正确18.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A.m-nB.m-n-1C.n+1D.条件不足，无法确定19.设无向图的顶点个数为n，则该图最多有（）条边。A.n-1B.n(n-1)/2C.n(n+1)/2D.020.具有10个叶结点的二叉树中有（）个度为2的结点，A.8B.9C.10D.ll21.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（）A.选择排序法B.插入排序法C.快速排序法D.堆积排序法22.在一棵二叉树上第5层的结点数最多是（）A.8B.16C.32D.1523.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A.求子串B.联接C.匹配D.求串长24.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（）(1=i=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)25.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。A.插入B.选择C.希尔D.二路归并二、判断题（共20道试题，共40分。）1.消除递归不一定需要使用栈，此说法（）A.错误B.正确2.栈是实现过程和函数等子程序所必需的结构（）A.错误B.正确3.对任何数据结构链式存储结构一定优于顺序存储结构（）。A.错误B.正确4.用一维数组存储二叉树时，总是以前序遍历顺序存储结点（）A.错误B.正确5.任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间（）A.错误B.正确6.完全二叉树一定存在度为1的结点（）A.错误B.正确7.在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面（）A.错误B.正确8.采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的A.错误B.正确9.顺序存储结构的主要缺点是不利于插入或删除操作（）A.错误B.正确10.直接选择排序算法在最好情况下的时间复杂度为O（N）（）A.错误B.正确11.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构（）。A.错误B.正确12.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的（）A.错误B.正确13.排序算法中的比较次数与初始元素序列的排列无关（）A.错误B.正确14.用树的前序遍历和中序遍历可以导出树的后序遍历（）A.错误B.正确15.健壮的算法不会因非法的输入数据而出现莫名其妙的状态（）。A.错误B.正确16.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表（）A.错误B.正确17.当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省（）。A.错误B.正确18.二叉树的遍历结果不是唯一的（）A.错误B.正确19.二维以上的数组其实是一种特殊的广义表（）A.错误B.正确20.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的（）A.错误B.正确三、多选题（共5道试题，共10分。）1.以下数据结构中属于线性数据结构的有哪些（）A.队列B.线性表C.二叉树D.栈2.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形可能出现的是（）A.G中有弧Vi，VjB.G中有一条从Vi到Vj的路径C.G中没有Vi,VjD.G中有一条从Vj到Vi的路径3.下面关于线性表的叙述中，正确的是（）A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。4.下面说法正确的是（）A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C.广义表难以用顺序存储结构D.广义表可以是一个多层次的结构5.下面关于串的的叙述中，正确的是（）A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储