1、全国数据结构考试集合数据结构全国往年自考试题一、单项选择题1、在数据的逻辑结构中，树结构和图结构都是（ ）A.非线性结构 B.线性结构C.动态结构 D.静态结构2.在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为（ ）A.O（1） B.O（log n） C.O（n） D.O（n2）4.设栈的初始状态为空，入栈序列为1，2，3，4，5，6，若出栈序列为2，4，3，6，5，1，则操作过程中栈中元素个数最多时为（ ）A.2个 B.3个C.4个 D.6个5.队列的特点是（ ）A.允许在表的任何位置进行插入和删除B.只允许在表的一端进行插入和删除C.允许在表的两端进行插入和删除D.只允许在表的一
2、端进行插入，在另一端进行删除6.已知1012的二维数组A，按“行优先顺序”存储，每个元素占1个存储单元，已知A11的存储地址为420，则A55的存储地址为（ ）A.470 B.471 C.472 D.4737.在一棵二叉树中，度为2的结点数为15，度为1的结点数为3，则叶子结点数为（ ）A.12 B.16 C.18 D.208.在带权图的最短路径问题中，路径长度是指（ ）A.路径上的顶点数 B.路径上的边数C.路径上的顶点数与边数之和 D.路径上各边的权值之和10.要以O（n log n）时间复杂度进行稳定的排序，可用的排序方法是（ ）A.归并排序 B.快速排序C.堆排序 D.冒泡排序11.若
3、希望在1000个无序元素中尽快求得前10个最大元素，应借用（ ）A.堆排序 B.快速排序 C.冒泡排序 D.归并排序12.对有序表进行二分查找成功时，元素比较的次数（ ）A.仅与表中元素的值有关 B.仅与表的长度和被查元素的位置有关C.仅与被查元素的值有关 D.仅与表中元素按升序或降序排列有关13.散列文件是一种（ ）A.顺序存取的文件 B.随机存取的文件C.索引存取的文件 D.索引顺序存取的文件1.数据的四种存储结构是( )A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构C.集合存储结构、一对一存储结构、一对多存储结构和多
4、对多存储结构D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构2.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是( )A.无头结点的单向链表 B.带头结点的单向链表C.带头结点的双循环链表 D.带头结点的单循环链表3.若带头结点的单链表的头指针为head，则判断链表是否为空的条件是( )A.head=NULL B.head-next=NULLC.head!=NULL D.head-next!=head4.若元素的入栈顺序为1，2，3.，n，如果第2个出栈的元素是n，则输出的第i(1=inext=r； q-n
5、ext=r-next； r-next=q；Bp-next=r； r-next=q； q-next=r-next；Cr-next=q； q-next=r-next； p-next=r；Dr-next=q； p-next=r； q-next=r-next；4若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是（）A3 B5C6 D75假设以数组An存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为（）Arear= =front B(front+1)n= =re
6、arCrear+1= =front D(rear+1)n= =front7二维数组A106采用行优先的存储方法，若每个元素占4个存储单元，已知元素A34的存储地址为1000，则元素A43的存储地址为（）A1020 B1024C1036 D12409已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（）AFEDCBA BABCDEFCFDECBA DFBDCEA12如图所示的有向图的拓扑序列是（）Ac，d，b，a，eBc，a，d，b，eCc，d，e，a，bDc，a，b，d，e13对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为基准的一次划分的结果为
7、（）A(5，1，4，3，6，2，8，7) B(5，1，4，3，2，6，7，8)C(5，1，4，3，2，6，8，7) D(8，7，6，5，4，3，2，1)14分块查找方法将表分为多块，并要求（）A块内有序 B块间有序C各块等长 D链式存储1.下列程序段的时间复杂度为( ) s=0； for(i=1；in；i+) for(j=1；jnext=NULL；C.head!=NULL； D.head-next=head；3.栈是一种操作受限的线性结构，其操作的主要特征是( )A.先进先出 B.后进先出C.进优于出 D.出优于进4.假设以数组An存放循环队列的元素，其头、尾指针分别为front和rear。若
8、设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( )A.(rear-front-1)n B.(rear-front)nC.(front-rear+1)n D.(rear-front+n)n5.判断两个串大小的基本准则是( )A.两个串长度的大小 B.两个串中首字符的大小C.两个串中大写字母的多少 D.对应的第一个不等字符的大小6.二维数组A45按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A00的存储地址为1000，则数组元素A32的存储地址为( )A.1012 B.1017C.1034 D.10367.高度为5的完全二叉树中含有的
9、结点数至少为( )A.16 B.17C.31 D.328.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为( )A.5 B.8C.11 D.189.下列所示各图中是中序线索化二叉树的是( )10.已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为( )A.(v0，v1，v2，v5，v4，v3)B.(v0，v1，v2，v3，v4，v5)C.(v0，v1，v5，v2，v3，v4)D.(v0，v1，v4，v5，v2，v3)11.如图所示有向图的一个拓扑序列是( )A.ABCDE
10、FB.FCBEADC.FEDCBAD.DAEBCF12.下列关键字序列中，构成大根堆的是( )A.5，8，1，3，9，6，2，7 B.9，8，1，7，5，6，2，33C.9，8，6，3，5，l，2，7 D.9，8，6，7，5，1，2，314.已知一个散列表如图所示，其散列函数为H(key)=key11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( )1.数据的不可分割的最小标识单位是（ ）A.数据项 B.数据记录 C.数据元素 D.数据变量3.若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是（ ）A.单链表 B.双链表C.单循环链表 D.顺序表4.
11、设单链表中指针p指向结点A，要删除A之后的结点（若存在），则修改指针的操作为（ ）A.pnext=pnextnext B.p=pnextC.p=pnextnext D.pnext=p5.向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行的操作为（ ）A.hsnext=s； B.snext=hs；hs=s；C.snext=hsnext；hsnext=s； D.snext=hs；hs=hsnext；6.设循环队列的元素存放在一维数组Q030中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应指向的元素是（ ）A
12、.Q4 B.Q5 C.Q14 D.Q157.定义二维数组A18，010，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（ ）A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L8.具有n个结点的二叉树，拥有指向孩子结点的分支数目是（ ）A.n-1 B.n C.n+1 D.2n9.对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（ ）A.99 B.98 C.97 D.5010.有m个叶子结点的哈夫曼树，其结点总数是（ ）A.2m-
13、1 B.2m C.2m+1 D.2（m+1）11.有n个结点的无向图的边数最多为（ ）A.n+1 B. C.n（n+1） D.2n（n+1）12.设图的邻接矩阵为，则该图为（ ）A.有向图 B.无向图 C.强连通图 D.完全图13.二分查找算法的时间复杂度是（ ）A.O（n2） B.O（nlog2n） C.O（n） D.O（log2n）14.已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（ ）A.4 B.5 C.6 D.7 15.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（ ）A.插入和快速 B
14、.冒泡和快速 C.选择和插入 D.选择和冒泡1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）A. 栈 B. 队列C. 树 D. 图2.下面程序段的时间复杂度为（ ）for (i=0; im; i+)for (j=0; jnext=head B. p-next-next=headC. p-next=NULL D. p=head4.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ ）A. SXSSXXXX B. SXXSXSSXC. SXSXXSSX D. SSSXXSXX5.两个字符串相等的条件是（ ）A. 串的长度相等
15、B. 含有相同的字符集C. 都是非空串 D. 串的长度相等且对应的字符相同7.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ）A. 0 B. 1C. 48 D. 498.在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为（ ）A. Dout B. Dout-1C. Dout+1 D. n9.如图所示的有向无环图可以得到的拓扑序列的个数是（ ）A. 3 B. 4C. 5 D. 610.如图所示的带权无向图的最小生成树的权为（ ）A. 51 B. 52C. 54 D. 5611.对长度为n的关键字序列进行堆排序的空间复杂度为（ ）A
16、. O（log2n） B. O（1）C. O（n） D. O（n*log2n）12.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为（35，51，24，13，68，56，42，77，93）（35，24，13，51，56，42，68，77，93）所采用的排序方法是（ ）A. 插入排序 B. 冒泡排序C. 快速排序 D. 归并排序13.已知散列表的存储空间为T0.18，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T5=39，T6=57和T7=7，则下一个关键字23插入的位置是（ ）A. T
17、2 B. T4C. T8 D. T1014.适宜进行批量处理的文件类型是（ ）A. 顺序文件 B. 索引顺序文件C. 散列文件 D. 多关键字文件1.逻辑上通常可以将数据结构分为（）A.动态结构和静态结构 B.顺序结构和链式结构C.线性结构和非线性结构 D.初等结构和组合结构2.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（）A.访问第i个元素的前驱（1next= =NULLC.head!=NULL D.headnext= =head4.已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（）A.5，4，3，2，1，6 B.2，
18、3，5，6，1，4C.3，2，5，4，1，6 D.1，4，6，5，2，38.树的先根序列等同于与该树对应的二叉树的（）A.先序序列 B.中序序列C.后序序列 D.层序序列9.假设有向图含n个顶点及e条弧，则表示该图的邻接表中包含的弧结点个数为（）A.n B.eC.2e D.ne10.如图所示的有向无环图可以得到的不同拓扑序列的个数为（）A.1 B.2C.3 D.411.下列排序方法中，稳定的排序方法为（）A.希尔排序 B.堆排序C.快速排序 D.直接插入排序12.对下列关键字序列进行快速排序时，所需进行比较次数最少的是（）A.（1，2，3，4，5，6，7，8） B.（8，7，6，5，4，3，2
19、，1）C.（4，3，8，6，1，7，5，2） D.（2，1，5，4，3，6，7，8）13.含n个关键字的二叉排序树的平均查找长度主要取决于（）A.关键字的个数 B.树的形态C.关键字的取值范围 D.关键字的数据类型14.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是（）A.分块查找 B.顺序查找 C.二分查找 D.散列查找15.可有效提高次关键字查找效率的文件是（）A.顺序文件 B.倒排文件C.散列文件 D.VSAM文件1.下面程序段的时间复杂度为( ) s=0； for(i=1；in；i+) for(j=1；jnext=s-next；s-next=p； B.s-next=p；
20、q-next=s-next；C.p-next=s-next；s-next=q； D.s-next=q；p-next=s-next；3.在计算机内实现递归算法时所需的辅助数据结构是( )A.栈 B.队列C.树 D.图4.假设以数组Am存放循环队列的元素。已知队列的长度为length，指针rear指向队 尾元素的下一个存储位置，则队头元素所在的存储位置为( )A.(rear-length+m+1)m B.(rear-length+m)mC.(rear-length+m-1)m D.(rear-length)m5.通常将链串的结点大小设置为大于1是为了( )A.提高串匹配效率 B.提高存储密度C.便
21、于插入操作 D.便于删除操作8.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为( )A.n-1 B.nC.n+l D.2n9.为便于判别有向图中是否存在回路，可借助于( )A.广度优先搜索算法 B.最小生成树算法C.最短路径算法 D.拓扑排序算法10.连通网的最小生成树是其所有生成树中( )A.顶点集最小的生成树 B.边集最小的生成树C.顶点权值之和最小的生成树 D.边的权值之和最小的生成树11.按排序过程中依据的原则分类，快速排序属于( )A.插入类的排序方法 B.选择类的排序方法C.交换类的排序方法 D.归并类的排序方法12.下列关键字序列中，构成小根堆的是( )A.84，4
22、6，62，41，28，58，15，37B.84，62，58，46，41，37，28，15C.15，28，46，37，84，41，58，62D.15，28，46，37，84，58，62，4113.在长度为32的有序表中进行二分查找时，所需进行的关键字比较次数最多为( )A.4 B.5C.6 D.715.散列文件也称为( )A.顺序文件 B.索引文件C.直接存取文件 D.间接存取文件1.在数据结构中，从逻辑上可以把数据结构分成( )A.线性结构和非线性结构 B.紧凑结构和非紧凑结构C.动态结构和静态结构 D.内部结构和外部结构2.for（i=0；im；i+）for（j=0；jn；j+）Aij=i*j；上面算法的时间复杂度为( )A.O(m2) B.O(n2)C.O(mn) D.O(m+n）3.设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为( )A.5 B.6C.7 D.94.设p为指向双向循环链表
