数据结构期末复习习题.pptx

期末复习习题集A1. 数据结构在计算机内存中的表示指A. 数据的存储结构B. 数据结构C. 数据的逻辑结构D. 数据元素之间的关系D2. 串是________ A. 不少于一个字母的序列B. 任意个字母的序列C. 不少于一个字符的序列D. 有限个字符的序列C3. 在n个节点的线索二叉树中，线索的数目为 A. n-1B. nC. n+1D. 2n假溢出4. 顺序队列在实现的时候，通常将数组看成是一个首尾相连的环，这样做的目的是为了避免产生______现象模式匹配5. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为________中序6. 对二叉排序树进行_______遍历，可以得到按关键字从小到大排列的节点序列40,38,46,56,79,847. 在一组记录的关键字为{46,79,56,38,40,84}，利用快速排序的方法，以第1个记录为基准得到的第一次划分结果为_________8. 设n为3的倍数，分析以下算法的时间复杂度 void fun(int n) { int i, j, x, y; for(i=1; i=n; i++) if(3*i=n) for(j=3*i;j=n;j++) { x++; y = 3*x+2; } }（2*4+2）*2+1000=10209. 二维数组A[4][4](即A[0...3][0...3])的元素起始地址是LOC(A[0][0])=1000，元素的长度为2，则LOC(A[2][2])为多少？n=2n2+n1+1且n0=n2+1，得n=2n0+n1-1哈夫曼树n1=0，则n=2n0-110. 如果一棵哈夫曼树T有n0个叶子节点，那么，树T有多少个节点，要求给出求解过程判定树(略)，总共比较4次，依次关键字为：45,77,95,8211. 有一个有序表R[1...13]={1,3,9,12,32,41,45,62,75,77,82,95,100}，当用二分查找法查找关键字为82的节点时，经多少次比较后查找成功，依次与哪些关键字进行比较第一趟：265,301,751,129,937,863,742,694,76,438第二趟：129,265,301,751,863,937,694,742,76,438第三趟：129,265,301,694,742,751,863,937,76,438第四趟：76,129,265,301,438,694,742,751,863,93712. 以关键字序列{265,301,751,129,937,863,742,694,76,438}为例，给出归并排序算法的各趟排序结束时关键字序列的状态A13. 链表不具备的特点是A. 可随机访问任一节点B. 插入删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与其长度成正比C14. 一个栈的进栈序列是abcde，则栈的不可能的输出序列是 A. edcbaB. decbaC. dceabD. abcdeC15. 用直接插入序列对下面4个序列进行递增排序，元素比较次数最少的是 A. 94,32,40,90,80,46,21,69B. 32,40,21,46,69,94,90,80C. 21,32,46,40,80,69,90,94D. 90,69,80,46,21,32,94,40D16. 以下序列不是堆(大根或小根)的是 A. {100,85,98,77,80,60,82,40,20,10,66}B. {100,98,85,82,80,77,66,60,40,20,10}C. {10,20,40,60,66,77,80,82,85,98,100}D. {100,85,40,77,80,60,66,98,82,10,20}4, 317. 广义表((),a,(a),((a)))的长度是_______，深度是_________n+118. 具有n个节点的二叉树采用二叉链存储结构，共有_______个空指针域 2(n-1)19.在有n个顶点的有向图中，每个顶点的度最大可达_______O(n2)20. 设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度 int m =0,i,j for(i=1;i=n;i++) for(j=2*i;j=n;j++) m++; D21. 下述函数中对应的时间复杂度最小是A. T1(n) = nlog2n+5000nB. T2(n) = n2-8000nC. T3(n) = D. T4(n) = 1000log2nB22. 以下各种存储结构中，最适合用做链队的链表是 A. 带队首指针和队尾指针的循环单链表B. 带队首指针和队尾指针的非循环单链表C. 只带队首指针的非循环单链表D. 只带队首指针的循环单链表B23. 设二维数组A[6][10]，每个数组元素占