数据结构模拟试题一

《数据结构模拟试题一》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一.填空题1.设只包含要根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为       ，最小结点数为          。2.某二叉树结点的中序遍历序列为A，B，C，D，E，F，G，后序遍历序列为B，D，C，A，F，G，E，则该二叉树结点的前序遍历序列为             ，该二叉树对应的树林包括        棵树。3.设有关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是          ；若采用以第一个元素为分界元素的快速排序法，则一趟扫描的结果是        

2、     。4.在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个________,且存在一条从根到该结点的_______。5.对于顺序存储的栈，因为栈的空间是有限的，在进行_______运算时，可能发生栈的上溢，在进行________运算时，可能发生栈的下溢。6.对于单链表形式的队列，其空队列的front指针和rear指针都等于_______。7.含有2的n次方个结点的二叉树高度至少是________，至多是________（仅含根结点的二叉树高度为零）。8.用起泡法对n个关键码排序，在最好情况下，只需做___次比较和___次移动；在最坏的情况下要做____次比较。二．

3、判断题(下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”。)1.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面......()2.线性表中的每个结点最多只有一个前驱和一个后继。......()3.线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。.......()4.栈和队列逻辑上都是线性表。........()5.单链表从任何一个结点出发，都能访问到所有结点......()6.设串S的长度为n,则S的子串个数为n(n+1)/2。......()7.一般树和二叉树的结点数目都可以为0。......()8.（101，8

4、8，46，70，34，39，45，58，66，10）是堆。......()9.将一棵树转换成二叉树后，根结点没有左子树。......()10.用树的前序遍历和中序遍历可以导出树的后序遍历。......()11．即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。......()12．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离很较近。......()13．数据的基本单位是数据项。......()14．带权的无向连通图的最小生成树是唯一的。......()15．数组元素之间的关系，既不是线性的，也不是树形的。......()16．对

5、于有n个对象的待排序序列进行归并排序，所需平均时间为O（nlog2n）。......()17．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。......()18．在霍夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应当特殊处理。......()19．线性表采用顺序存储表示时，必须占用一片连续的存储单元。......()20．由树转化成二叉树，其根的右子女指针总是空的。......()21．直接选择排序是一种稳定的排序方法。......()22．装载因子是散列表的一个重要参数，它反映了散列表的装满程度。......()三.单项选择题，从每小题后给出的答案中选择一

6、个正确的答案填入括号内。1.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为(   )。(1≤i≤n+1)   A．O(0)   B．O(1)   C.O(n)   D．O(n2) 2.若在线性表中采用折半查找法查找元素，该线性表应该(   )。A．元素按值有序   B．采用顺序存储结构C．元素按值有序，且采用顺序存储结构   D．元素按值有序，且采用链式存储结构3.已知一算术表达式的中缀形式为A＋B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为(   )。   A.–A+B*C/DE   B.–A+B*CD/E  C.-+*ABC/DE  

7、 D.-+A*BC/DE4.若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用(  )遍历方法最合适。   A．前序   B．中序   C．后序   D．按层次5.对二叉排序树进行(   )遍历，可以得到该二叉树所有结点构成的排序序列。   A.前序   B．中序   C．后序   D．按层次6.具有n个顶点的有向图最多有(   )条边。   A．n   B．n(n—1)   Cn(n+1)   D.n27.从未