数据结构题库

线性结构题1. 栈和队列的共同特点是 ( A )。只允许在端点处插入和删除元素都是先进后出都是先进先出没有共同点2. 以下数据结构中哪一个是非线性结构？ ( D )(A)队列(B)栈(C)线性表(D)二叉树3.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在(C)位置。脚注(10)表示用进制表示。(A) 688 (B) 678 (C) 692 (D) 6964．设某数据结构的二元组形式表示为 A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r} ，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构 A是（ B ）。(A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构5．下面程序的时间复杂为（ B ）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)O(n)234(B)O(n)(C)O(n)(D)O(n)6.下列程序段的时间复杂度为（A）。i=0，s=0；while(s<n){s=s+i；i++；}(A)O(n1/2(B)O(n1/3(C)O(n)2)))(D)O(n7.为解决计算机主机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区。主机将要打印输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（B）(A)栈(B)队列(C)树(D)图8．已知二级数组a[50][40]按行序为主序存放，每个元素占4个字节空间，若数组a的首元素a[1][1]地址为2012，计算a[23][21]的内存地址为（B）。(A)5600(B)5612(C)2912(D)36009．设输入序列为 1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为 （B ）。(A)5 ，3，4，6，1，2 (B)3 ，2，5，6，4，1(C)3 ，1，2，5，4，6 (D)1 ，5，4，6，2，310．设有一个 10阶的下三角矩阵 A（包括对角线） ，按照从上到下、从左到右的顺序存储到连续的 55个存储单元中，每个数组元素占 1个字节的存储空间，则 A[5][4] 地址与A[0][0] 的地址之差为（ B ）。(A)10 (B)19 (C)28 (D)5511．广义表 A=（a,b（c,d）,(e,(f,g)) ），则 head(tail(head(tail(tail(A))))) 值为（ D ）(A)（g） (B)(d) (C)(c) (D)(d)12．数据的最小单位是（ A ）。(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量13．函数 substr( “DATASTRUCTURE”，5，9)的返回值为（ A ）。(A)“STRUCTURE”(B)“DATA”(C)“ASTRUCTUR”(D)“DATASTRUCTURE”14．在线性表中，一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）。（A）110（B）108（C）100（D）12015．栈中元素的进出原则是（B）。（Ａ）先进先出（B）后进先出（Ｃ）栈空则进（Ｄ）栈满则出16．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（B）。(A)s->next=p->next ；p->next=-s ；(B)q->next=s ；s->next=p ；(C)p->next=s->next ；s->next=p ； (D)p->next=s ；s->next=q ；非线性结构1.具有n(n>0)个结点的完全二叉树的深度为C。(Ａ)log2(n)(Ｂ)log2(n)(Ｃ)log2(n)+1(Ｄ)log2(n)+12.树最适合用来表示(C)。(A)有序数据元素(B)无序数据元素(C)元素之间具有分支层次关系的数据(D)元素之间无联系的数据3.二叉树的第k层的结点数最多为(D).(A)2k(B)2K+1(C)2K-1(D)2k-1-14．设一棵完全二叉树有700个结点，则共有(D)个叶子结点。（A）200（B）250（C）300（D）3505.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为(D)(A)1，2，3(B)9，5，2，3(C)9，5，3(D)9，4，2，36.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为(C)(A)O（1）(B)O（n）(C)O（1og2n）(D)O（n2）7．设一组初始关键字记录关键字为 (20，15，14，18，21，36，40，10)，则以 20为基准记录的一趟快速排序结束后的结果为 ( A ) 。10，15，14，18，20，36，40，2110，15，14，18，20，40，36，2110，15，14，20，18，40，36，2l15，10，14，18，20，36，40，218．设无向图 G中有 n个顶点 e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ D ）。(A) n，e (B)e ，n (C)2n ，e (D)n ，2e9．设有 5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的 10个记录关键字，则用下列（ B ）方法可以达到此目的。(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序10.下列四种排序中（ D ）的空间复杂度最大。(A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序11．设一棵二叉树的深度为 k，则该二叉树中最多有（ D ）个结点。(A)2k-1kk-1k(B)2(C)2(D)2-112．设一组初始记录关键字序列为 (25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为 2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。15，25，35，50，20，40，80，85，36，7015，25，35，50，80，20，85，40，70，3615，25，35，50，80，85，20，36，40，7015，25，35，50，80，20，36，40，70，8513．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（B）次。(A)25(B)10(C)7(D)114．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（C）。(A)20(B)256(C)512(D)102415．在一个具有n个顶点的无向连通图中,要连通全部顶点至少需要（C）条边。（A）n（B）n+1（C）n-1（D）n/216.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（D）个，(A)1(B)2(C)3(D)417.设有6个结点的无向图，该图至少应有(A)条边才能确保是一个连通图。(A)5(B)6(C)7(D)818.二叉排序树中左子树上所有结点的值均（A）根结点的值。(A)<(B)>(C)=(D)!=设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ D ）。(A)129 (B)219 (C)189 (D)22920.设某棵二叉树中只有度数为 0和度数为 2的结点且度数为 0的结点数为 n，则这棵二叉中共有（ C ）个结点。(A)2n (B)n+l (C)2n-1 (D)2n+l设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（ D ）。(A)F，H，C，D，P，A，M，Q，R，S，Y，X(B)P，A，C，S，Q，D，F，X，R，H，M，YA，D，C，R，F，Q，M，S，Y，P，H，XH，C，Q，P，A，M，S，R，D，F，X，Y22.设用邻接矩阵 A表示有向图 G的存储结构，则有向图 G中顶点 i的入度为（ B ）。(A) 第i行非 0元素的个数之和 (B) 第i列非0元素的个数之和(C) 第i行0元素的个数之和 (D) 第i列0元素的个数之和填空题：1.设F和R分别表示顺序循环队列的头指针和尾指针，该队列最存储空间为N个，则判断该循环队列为空的条件为___F==A________，判断队列为满时条件为(R+1)%N==F。2.一个线性表是n≧0个数据元素a1,a2,a3,⋯⋯an的有限序列，表中每个数据元素，除第一个和最后一个外，有且仅有一个直接前驱和一个直接后继。3.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为_0(1)_____。4.设输入序列为1、2、3，则经过栈的作用后可以得到___5_____种不同的输出序列。5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有____2n___个指针域，其中有___n-1__个指针域是存放了地址，有_____n+1____个指针是空指针。6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有____个和______个。在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。7.在快速排序、堆排序、归并排序中，___归并______排序是稳定的。8. ___中序_______遍历二叉排序树中的结点可以得到一个递增的关键字序列 （填先序、 中序或后序）。9. 设查找表中有 100个元素，如果用二分法查找方法查找数据元素 X，则最多需要比较____7____次就可以断定数据元素 X是否在查找表中。10. 设有向图 G中有 n个顶点 e条有向边， 所有的顶点入度数之和为 d，则e和d的关系为___e=d______ 。设某无向图中顶点数和边数分别为 n和e，所有顶点的度数之和为d，则e=__d/2_____。11. 设一组初始记录关键字序列为 (55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为 ___31,38,44,56,75,80,55,63_____ 。12. 已知一有向图的邻接表存储结构如下：从顶点 1出发，深度优先搜索（ Dfs）的输出序列是 1,3,4,5,2 ，广度优先搜索（ BFS）遍历的输出序列是 1,3,2,4,5假定一个线性表为 (12,23,74,55,63,40) ，若给出哈希函数

H（

key）=Key%4

条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为

____________________________

、___________________

、

_______________________

和__________________________

。13.14. 设有 n个结点的完全二叉树， 如果按照从自上到下、 从左到右从 1开始顺序编号， 则第i个结点的双亲结点编号为 __i/2__________ ，右孩子结点的编号为 ___2i+1_____ 。15.设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为___________________________。16.设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为____1,4,2,3___。17.设哈夫曼树中共有n个结点，则该哈夫曼树中有____0__个度数为1的结点。18.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的_行为出度_，第i列上所有元素之和等于顶点i的_行为入度_。19.为了能有效地应用HASH查找技术，必须解决的两个问题是_构造好的hash函数__和___确定解决冲突方法__。20.中序遍历二叉排序树所得到的序列是___有序___序列（填有序或无序）。21.折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素28,6,12,20比较大小。22.线性结构中元素之间存在一对一关系，树形结构中元素之间存在关系一对多，图形结构中元素之间存在多对多关系。问答题1. 设某棵二叉树的中序遍历序列为 DBEAC，前序遍历序列为 ABDEC，要求给出该二叉树的的后序遍历序列并画出该二叉树。2．已知待散列的线性表为（ 36，15，40，63，22），散列用的一维地址空间为 [0..6]，假定选用的散列函数是 H（K）=Kmod7，若发生冲突采用线性探查法处理，试：计算出每一个元素的散列地址并在下图中填写出散列表：`01234563．设无向图 G（如右图所示） ，画出该图的最小生成树的结构， 并写出该图的最小生成树边的集合及计算最小生成树各边上的权值之和。4．已知序列（ 10，18，4，3，6，12，1，9，18*，8）请用快速排序写出每一趟排序的结果。5．设一组初始记录关键字序列为 (45，80，48，40，22，78)，则分别给出第 4趟直接选择排序和第 4趟直接插入排序后的结果。6．给定一组权值 {2，8，5，4，3}，构造相应的哈夫曼树。7．下图所示的森林：求树（a）的先根序列和后根序列；2）将此森林转换为相应的二叉树；A GB C HD E F I J K(a) (b)8．设散列表的地址范围是[0..9]，散列函数为H（key）=（k