数据结构题
1. 对一个算法的评价，不包括如下（ ）方面的内容。 A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度 2. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 采用开放定址法处理散列表的冲突时，其平均查找长度（ ）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同 D．高于二分查找 6. 若需要利用形参直接访问实参时，应将形参变量说明为（ ）参数。 A．值 B．函数 C．指针 D．引用 7. 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ ）。 A．行号 B．列号 C．元素值 D．非零元素个数 8. 快速排序在最坏情况下的时间复杂度为（ ）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 9. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 10. 栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 11. 用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 12. 以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 13. 树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 14. 二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k+1 15. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 16. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 17. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个， A．1 B．2 C．3 D．4 18. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 19．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ） A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m 20．如下陈述中正确的是（ ） A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串 21．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。 (A) 3 (B) 4 (C) 5 (D) 8 22．设用链表作为栈的存储结构则退栈操作（ ）。 (A) 必须判别栈是否为满 (B) 必须判别栈是否为空 (C) 判别栈元素的类型 (D) 对栈不作任何判别 23．下列四种排序中（ ）的空间复杂度最大。 (A) 快速排序 (B) 冒泡排序 (C) 希尔排序 (D) 堆 24．数据的最小单位是（ ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量 25．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（ ）。 (A) 40，50，20，95 (B) 15，40，60，20 (C) 15，20，40，45 (D) 45，40，15，20 26．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。 (A) 15，25，35，50，20，40，80，85，36，70 (B) 15，25，35，50，80，20，85，40，70，36 (C) 15，25，35，50，80，85，20，36，40，70 (D) 15，25，35，50，80，20，36，40，70，85 27． 设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（ ）。 (A) 20 (B) 30 (C) 40 (D) 45 28．下面程序的时间复杂为( )。 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) B．O(n2) C．O(n3) D．O(n4) 29.递归过程中必定用到的数据结构是( )。 A.循环队列 B.堆栈 C.二叉树 D.散列 30．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ ）。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i-1 31．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ ）。 (A) 1 (B) 2 (C) 3 (D) 4 32.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。 (A) top=top+1; (B) top=top-1; (C) top->next=top; (D) top=top->next; 33. 字符串的长度是指（ ）。 (A) 串中不同字符的个数 (B) 串中不同字母的个数 (C) 串中所含字符的个数 (D) 串中不同数字的个数 34. 队列是一种（ ）的线性表。 (A) 先进先出 (B) 先进后出 (C) 只能插入 (D) 只能删除 35．设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（ ）。 (A) 小于等于m的最大奇数 (B) 小于等于m的最大素数 (C) 小于等于m的最大偶数 (D) 小于等于m的最大合数 36.如下代码段输出的结果是( )。 String s1 = "abc"; String s2 = new String(s1); System.out.println(s1 == s2 + ","); System.out.println(s1.equals(s2)); A．true,true B．false,false C．true,false D．false ,true 37.二叉树有( )种不同的基本形态。 A．3 B．4 C．5 D．6 38.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（ ）。 (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，Y (C) A，D，C，R，F，Q，M，S，Y，P，H，X (D) H，C，Q，P，A，M，S，R，D，F，X，Y 39．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C ）。 (A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M 40．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 41．设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1 42．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ ）。 (A) 9 (B) 10 (C) 11 (D) 12 43．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( A )。 (A) 10，15，14，18，20，36，40，21 (B) 10，15，14，18，20，40，36，21 (C) 10，15，14，20，18，40，36，2l (D) 15，10，14，18，20，36，40，21 44．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。 (A) 3 (B) 4 (C) 5 (D) 8 45．设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到Hash表中需要做( )次线性探测。 A．2 B．n(n+1) C．n(n+1)/2 D．n(n-1)/2 46．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为( )。 A．1 B．2 C．3 D．4 47．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是( )。 A．空或只有一个结点 B．高度等于其结点数 C．任一结点无左孩子 D．任一结点无右孩子 48．设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。 (A) 1 (B) n (C) nlog2n (D) n2 49．下面关于线性表的叙述错误的是（ ）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 50．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（ ）。 (A) 100 (B) 40 (C) 55 (D) 80 51数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。 52．一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是 。 53.队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。54.根据搜索方法的不同，图的遍历有 和 两种。 55.堆栈的操作特点是 。 56. 若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为________,右孩子元素为_______________，双亲元素为____________。 57. 快速排序算法的平均时间复杂度为____________，直接插入排序算法的平均时间复杂度为___________。 58.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。 59．一棵高度为5的二叉树中最少含有______个结点，最多含有_____个结点。 11.对于给定的若干个元素，可以构造出的逻辑结构有 结构， 结构和 结构三种。 60.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。 61．设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。 62．设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。 63．设一组初始记录关键字序列为(19，21，16，5，18，23)，要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。 64．.线性表的存储结构有哪两种，各有何特点？ 65．在顺序循环队列中，什么是假溢出？请指出解决假溢出的常见方法。 66．阅读下面的算法： LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； } return L； } 语句S1和语句组S2的功能是什么？ 67．已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示 (1)画出该图的图形； (2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。 68．已知关键字序列为{8，17，26，32，40，72，87，99},采用折半查找算法，给定值为70，35时分别与哪些元素比较？画出相应的二叉判定树 69． 设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。 70．对于KMP算法，模式串中每个字符的最大真子串构成一个数组，定义为模式串的next[j]函数。next[j]函数定义如下： Max{k|0<k<j且“t0t1…tk-1”=“tj-ktj-k+1…tj-1”} 当此集合非空时 next[j]= 0 其他情况 -1 当j=0 计算t=“abcabaa”的next[j]，要求写出具体的推算步骤。
