• /  60
  • 下载费用: 19.90积分  

算法与数据结构期末考试试卷[

'算法与数据结构期末考试试卷['
课程测试试题(卷)课程测试试题(卷)----------------------以下为教师填写--------------------I、命题院(部): 数学与计算机科学学院数学与计算机科学学院 II、课程名称: 数据结构数据结构 III、测试学期:20 -20 学年度第 学期IV、测试对象: 学院 专业 级 班V、问卷页数(A4): 页VI、答卷页数(A4): 页VII、考试方式: 闭卷闭卷 (开卷、闭卷或课程小论文,请填写清楚)VIII、问卷内容:(请老师在出题时安排紧凑,填空题象征性的留出一点空格,学生将所有的答案做在答题纸上的规定位置,并写清楚大题、小题的题号) 一、一、一、一、 单选题(每题单选题(每题 2 分,共分,共 20 分)分)1. 1. 对一个算法的评价,不包括如下( )方面的内容。 A.健壮性和可读性 B.并行性 C.正确性 D.时空复杂度2. 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. 3. 对线性表,在下列哪种情况下应当采用链表表示?( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变4. 4. 一个栈的输入序列为 1 2 3,则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1B. 3 2 1 C. 3 1 2 D. 1 2 35. 5. AOV 网是一种( ) 。 A.有向图 B.无向图 C.无向无环图 D.有向无环图6. 6. 采用开放定址法处理散列表的冲突时,其平均查找长度( ) 。A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同 D.高于二分查找7. 7. 若需要利用形参直接访问实参时,应将形参变量说明为( )参数。A.值 B.函数 C.指针 D.引用8. 8. 在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有相同的( ) 。A.行号 B.列号 C.元素值 D.非零元素个数9. 9. 快速排序在最坏情况下的时间复杂度为( ) 。A.O(log2n) B.O(nlog2n) C.0(n) D.0(n2)10.10. 从二叉搜索树中查找一个元素时,其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、二、二、 运算题(每题运算题(每题 6 分,共分,共 24 分)分)1.1. 数据结构是指数据及其相互之间的______________。当结点之间存在M 对 N(M:N)的联系时,称这种结构为_____________________。2.2. 队列的插入操作是在队列的_________进行,删除操作是在队列的__________进行。3.3. 当用长度为 N 的数组顺序存储一个栈时,假定用 top==N 表示栈空,则表示栈满的条件是_____________________。4.4. 对于一个长度为 n 的单链存储的线性表,在表头插入元素的时间复杂度为_________,在表尾插入元素的时间复杂度为____________。5.5. 设 W 为一个二维数组,其每个数据元素占用 4 个字节,行下标 i 从 0到 7 ,列下标 j 从 0 到 3 ,则二维数组 W 的数据元素共占用_______个字节。W 中第 6 行的元素和第 4 列的元素共占用_________个字节。若按行顺序存放二维数组 W,其起始地址为 100,则二维数组元素 W[6,3]的起始地址为__________。6.6. 广义表 A= (a,(a,b),((a,b),c)),则它的深度为____________,它的长度为____________。7.7. 二叉树是指度为 2 的____________________树。一棵结点数为 N 的二叉树,其所有结点的度的总和是_____________。8.8. 对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个______________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。9.9. 对于一棵具有 n 个结点的二叉树,用二叉链表存储时,其指针总数为 _____________个,其中_______________个用于指向孩子,_________________个指针是空闲的。10. 10. 若对一棵完全二叉树从 0 开始进行结点的编号,并按此编号把它顺序存储到一维数组 A 中,即编号为 0 的结点存储到 A[0]中。其余类推,则 A[ i ]元素的左孩子元素为________,右孩子元素为_______________,双亲元素为____________。11. 11. 在线性表的散列存储中,处理冲突的常用方法有________________________和_____________________________两种。12. 12. 当待排序的记录数较大,排序码较随机且对稳定性不作要求时,宜采用_______________排序;当待排序的记录数较大,存储空间允许且要求排序是稳定时,宜采用________________________排序。 三、三、三、三、 运算题(每题运算题(每题 6 分,共分,共 24 分)分)1.1. 已知一个 6?5 稀疏矩阵如下所示, 试:(1)(1) 写出它的三元组线性表;(2)(2) 给出三元组线性表的顺序存储表示。2.2. 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起,逐个输入各个数据而生成的二叉搜索树。3.3. 对于图 6 所示的有向图若存储它采用邻接表,并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的,试写出:(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树;(2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树; 4.4. 已知一个图的顶点集 V 和边集 E 分别为:??????????????????????007000000520000000100000010000 V={1,2,3,4,5,6,7};E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};若存储它采用邻接表,并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的,按主教材中介绍的拓朴排序算法进行排序,试给出得到的拓朴排序的序列。 四、四、四、四、 阅读算法(每题阅读算法(每题 7 分,共分,共 14 分)分)1.1. int Prime(int n){ int i=1; int x=(int) sqrt(n); while (++i<=x) if (n%i==0) break; if (i>x) return 1; else return 0; } (1) (1) 指出该算法的功能;(2) (2) 该算法的时间复杂度是多少?2.2. 写出下述算法的功能: void AJ(adjlist GL, int i, int n) { Queue Q; InitQueue(Q); cout<<i<<' '; visited[i]=true; QInsert(Q,i); while(!QueueEmpty(Q)) { int k=QDelete(Q); edgenode* p=GL[k]; while(p!=NULL) { int j=p->adjvex; if(!visited[j]) { cout<<j<<' '; 图 6 visited[j]=true; QInsert(Q,j); } p=p->next; } }} 五、五、五、五、 算法填空(共算法填空(共 8 分)分)如下为二分查找的非递归算法,试将其填写完整。Int Binsch(ElemType A[ ],int n,KeyType K){int low=0;int high=n-1;while (low<=high){int mid=_______________________________;if (K==A[mid].key) return mid; //查找成功,返回元素的下标 else if (K<[mid].key) ______________________________________; //在左子表上继续查找 else __________________________________; //在右子表上继续查找}return -1; //查找失败,返回-1} 六、六、六、六、 编写算法(共编写算法(共 8 分)分)HL 是单链表的头指针,试写出删除头结点的算法。ElemType DeleFront(LNode * & HL) 参考答案一、一、一、一、 单选题(每题单选题(每题 2 分,共分,共 20 分)分)1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C二、二、二、二、 填空题(每空填空题(每空 1 分,共分,共 26 分)分)1.1. 联系 图(或图结构)2.2. 尾 首3.3. top==04.4. O(1) O(n) 5.5. 128 44 1086.6. 3 3 7.7. 有序 n-18.8. 有序序列 后缀表达式(或逆波兰式)9.9. 2n n-1 n+110. 10. 2i+1 2i+2 (i-1)/211. 11. 开放定址法 链接法12. 12. 快速 归并三、三、三、三、 运算题(每题运算题(每题 6 分,共分,共 24 分)分)1.1. (1) ((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (3 分)(2) 三元组线性表的顺序存储表示如图 7 示。2.2. 如图 8 所示。3.3. DFS:????? BFS:????? 4.4. 拓朴排序为: 4 3 6 5 7 2 1 四、四、 阅读算法(每题 7 分,共 14 分)1.1. (1) 判断 n 是否是素数(或质数) (2)O(n)2.2. 功能为:从初始点 vi出发广度优先搜索由邻接表 GL 所表示的图。五、五、 算法填空(8 分) (low+high)/2 high=mid-1 low=mid+1 六、六、 编写算法(8 分)ElemType DeleFront(LNode * & HL){if (HL==NULL){ cerr<<"空表"<<endl;exit(1);}LNode* p=HL;HL=HL->next;ElemType temp=p->data;delete p;return temp;} 吉首大学试题库课程测试试题(课程测试试题( 卷)卷)----------------------以下为教师填写--------------------65515132-145-2515637 图 7图 8 I、命题院(部): 数学与计算机科学学院数学与计算机科学学院 II、课程名称: 数据结构数据结构 III、测试学期:20 -20 学年度第 学期IV、测试对象: 学院 专业 级 班V、问卷页数(A4): 页VI、答卷页数(A4): 页VII、考试方式: 闭卷闭卷 (开卷、闭卷或课程小论文,请填写清楚)VIII、问卷内容:(请老师在出题时安排紧凑,填空题象征性的留出一点空格,学生将所有的答案做在答题纸上的规定位置,并写清楚大题、小题的题号) 一、一、一、一、 单选题(每题单选题(每题 2 分,共分,共 20 分)分)1. 1. 栈和队列的共同特点是( )。A.只允许在端点处插入和删除元素B.都是先进后出 C.都是先进先出D.没有共同点 2. 2. 用链接方式存储的队列,在进行插入运算时( ). A. 仅修改头指针   B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改3. 3. 以下数据结构中哪一个是非线性结构?( ) A. 队列    B. 栈 C. 线性表    D. 二叉树4. 4. 设有一个二维数组 A[m][n],假设 A[0][0]存放位置在 644(10),A[2][2]存放位置在 676(10),每个元素占一个空间,问 A[3][3](10)存放在什么位置?脚注(10)表示用 10 进制表示。 A.688 B.678 C.692 D.6965. 5. 树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据6. 6. 二叉树的第 k 层的结点数最多为( ). A.2k-1 B.2K+1 C.2K-1    D. 2k-17. 7. 若有 18 个元素的有序表存放在一维数组 A[19]中,第一个元素放 A[1]中,现进行二分查找,则查找 A[3]的比较序列的下标依次为( ) A. 1,2,3B. 9,5,2,3 C. 9,5,3D. 9,4,2,38. 8. 对 n 个记录的文件进行快速排序,所需要的辅助存储空间大致为 A. O(1)   B. O(n)   C. O(1og2n) D. O(n2)9. 9. 对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用 H(K)=K %9 作为散列函数,则散列地址为 1 的元素有( )个, A.1 B.2 C.3 D.410.10. 设有 6 个结点的无向图,该图至少应有( )条边才能确保是一个连通图。A.5 B.6 C.7 D.8 二、二、二、二、 填空题(每空填空题(每空 1 分,共分,共 26 分)分)1.1. 通常从四个方面评价算法的质量:_________、_________、_________和_________。2.2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2,其数量级表示为________。3.3. 假定一棵树的广义表表示为 A(C,D(E,F,G) ,H(I,J) ) ,则树中所含的结点数为__________个,树的深度为___________,树的度为_________。4.4. 后缀算式 9 2 3 +- 10 2 / -的值为__________。中缀算式(3+4X)-2Y/3对应的后缀算式为_______________________________。5.5. 若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和右孩子的两个指针。在这种存储结构中,n 个结点的二叉树共有________个指针域,其中有________个指针域是存放了地址,有________________个指针是空指针。6.6. 对于一个具有 n 个顶点和 e 条边的有向图和无向图,在其对应的邻接表中,所含边结点分别有_______个和________个。7.7. AOV 网是一种___________________的图。8.8. 在一个具有 n 个顶点的无向完全图中,包含有________条边,在一个具有 n 个顶点的有向完全图中,包含有________条边。9.9. 假定一个线性表为(12,23,74,55,63,40),若按 Key % 4 条件进行划分,使得同一余数的元素成为一个子表,则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。10. 10. 向一棵 B_树插入元素的过程中,若最终引起树根结点的分裂,则新树比原树的高度___________。 11. 11. 在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为________,整个堆排序过程的时间复杂度为________。12. 12. 在快速排序、堆排序、归并排序中,_________排序是稳定的。 三、三、三、三、 运算题(每题运算题(每题 6 分,共分,共 24 分)分)1.1. 在如下数组 A 中链接存储了一个线性表,表头指针为 A [0].next,试写出该线性表。 A 0 1 2 3 4 5 6 7 data 6050789034 40next357204 12.2. 请画出图 10 的邻接矩阵和邻接表。3.3. 已知一个图的顶点集 V 和边集 E 分别为: V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边。4.4. 画出向小根堆中加入数据 4, 2, 5, 8, 3 时,每加入一个数据后堆的变化。 四、四、四、四、 阅读算法(每题阅读算法(每题 7 分,共分,共 14 分)分)1. 1. 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; } 请回答下列问题: (1)说明语句 S1 的功能; (2)说明语句组 S2 的功能; (3)设链表表示的线性表为(a1,a2, …,an),写出算法执行后的返回值所表示的线性表。2. 2. void ABC(BTNode * BT){ if BT {图 10 ABC (BT->left); ABC (BT->right); cout<<BT->data<<' '; } } 该算法的功能是: 五、五、五、五、 算法填空(共算法填空(共 8 分)分)二叉搜索树的查找——递归算法:bool Find(BTreeNode* BST,ElemType& item){ if (BST==NULL) return false; //查找失败 else { if (item==BST->data){ item=BST->data;//查找成功 return ___________;} else if(item<BST->data) return Find(______________,item); else return Find(_______________,item); }//if} 六、六、六、六、 编写算法(共编写算法(共 8 分)分)统计出单链表 HL 中结点的值等于给定值 X 的结点数。 int CountX(LNode* HL,ElemType x) 参考答案一、一、 单选题(每题 2 分,共 20 分)1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A二、二、 填空题(每空 1 分,共 26 分)1. 1. 正确性 易读性 强壮性 高效率2. 2. O(n)3. 3. 9 3 34. 4. -1 3 4 X * + 2 Y * 3 / -5. 5. 2n n-1 n+16. 6. e 2e7. 7. 有向无回路8. 8. n(n-1)/2 n(n-1)9. 9. (12,40) ( ) (74) (23,55,63)10. 10. 增加 1 11. 11. O(log2n) O(nlog2n)12. 12. 归并三、三、 运算题(每题 6 分,共 24 分)1. 1. 线性表为:(78,50,40,60,34,90)2. 2. 邻接矩阵:????????????????0111010101110111010101110 邻接表如图 11 所示:图 113. 3. 用克鲁斯卡尔算法得到的最小生成树为: (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204. 4. 见图 12 图 12四、四、 阅读算法(每题 7 分,共 14 分)1. 1. (1)查询链表的尾结点(2)将第一个结点链接到链表的尾部,作为新的尾结点 (3)返回的线性表为(a2,a3,…,an,a1) 2. 2. 递归地后序遍历链式存储的二叉树。五、五、 算法填空(每空 2 分,共 8 分)true BST->left BST->right 六、六、 编写算法(8 分)int CountX(LNode* HL,ElemType x) { int i=0; LNode* p=HL;//i 为计数器 while(p!=NULL) { if (P->data==x) i++; p=p->next; }//while, 出循环时 i 中的值即为 x 结点个数 return i; }//CountX4444422255522884352834 吉首大学试题库课程测试试题(卷)课程测试试题(卷)----------------------以下为教师填写--------------------I、命题院(部): 数学与计算机科学学院数学与计算机科学学院 II、课程名称: 数据结构数据结构 III、测试学期:20 -20 学年度第 学期IV、测试对象: 学院 专业 级 班V、问卷页数(A4): 页VI、答卷页数(A4): 页VII、考试方式: 闭卷闭卷 (开卷、闭卷或课程小论文,请填写清楚)VIII、问卷内容:(请老师在出题时安排紧凑,填空题象征性的留出一点空格,学生将所有的答案做在答题纸上的规定位置,并写清楚大题、小题的题号) 一、一、 单选题(每小题 2 分,共 8 分)1、1、在一个长度为 n 的顺序线性表中顺序查找值为 x 的元素时,查找成功时的平均查找长度(即 x 与元素的平均比较次数,假定查找每个元素的概率都相等)为 ( )。A n B n/2 C (n+1)/2 D (n-1)/22、2、在一个单链表中,若 q 所指结点是 p 所指结点的前驱结点,若在 q 与 p之间插入一个 s 所指的结点,则执行( )。 A s→link=p→link; p→link=s; B p→link=s; s→link=q; C p→link=s→link; s→link=p; D q →link=s; s→link =p;3、 3、 栈的插入和删除操作在( )进行。A 栈顶 B 栈底 C 任意位置 D 指定位置4、 4、 由权值分别为 11,8,6,2,5 的叶子结点生成一棵哈夫曼树,它的带权路径长度为( ) A 24 B 71 C 48 D 53二、二、 填空题(每空 1 分,共 32 分)1、1、数据的逻辑结构被分为__________、 ___________ 、________和________四种。2、2、一种抽象数据类型包括______________和_____________两个部分。3、3、在下面的数组 a 中链接存储着一个线性表,表头指针为 a[o].next,则该线性表为_________________________________________________。 a 0 1 2 3 4 5 6 7 8 datanext 4、4、在以 HL 为表头指针的带表头附加结点的单链表和循环单链表中,判断链表为空的条件分别为________________和____________________。5、5、用具有 n 个元素的一维数组存储一个循环队列,则其队首指针总是指向队首元素的___________,该循环队列的最大长度为__________。6、6、当堆栈采用顺序存储结构时,栈顶元素的值可用———————表示;当堆栈采用链接存储结构时,栈顶元素的值可用_______________表示。7、7、一棵高度为 5 的二叉树中最少含有_________个结点,最多含有________个结点;一棵高度为 5 的理想平衡树中,最少含有_________个结点,最多含有_________个结点。8、8、在图的邻接表中,每个结点被称为____________,通常它包含三个域:一是_____________;二是___________;三是_____________。9、9、在一个索引文件的索引表中,每个索引项包含对应记录的_________和___________两项数据。10、10、 假定一棵树的广义表表示为 A(B(C,D(E,F,G) ,H(I,J) ) ) ,则树中所含的结点数为_________个,树的深度为_________,树的度为________, 结点 H 的双亲结点为________,孩子结点为_______________ 。11、11、 在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为_________,整个堆排序过程的时间复杂度为________________。12、12、 在对 m 阶的 B_树插入元素的过程中,每向一个结点插入一个索引项(叶子结点中的索引项为关键字和空指针)后,若该结点的索引项数等于______个,则必须把它分裂为_______个结点。 三、三、 运算题(每小题 6 分,共 24 分) 60 56 42 38 74 25 4 3 7 6 2 0 1 1、1、已知一组记录的排序码为(46,79,56,38,40,80, 95,24) ,写出对其进行快速排序的每一次划分结果。 2、2、一个线性表为 B=(12,23,45,57,20,03,78,31,15,36) ,设散列表为 HT[0..12],散列函数为 H(key)= key % 13 并用线性探查法解决冲突,请画出散列表,并计算等概率情况下查找成功的平均查找长度。 3、3、已知一棵二叉树的前序遍历的结果序列是 ABECKFGHIJ,中序遍历的结果是 EBCDAFHIGJ,试写出这棵二叉树的后序遍历结果。 4、4、已知一个图的顶点集 V 各边集 G 如下:V = {0,1,2,3,4,5,6,7,8,9};E = {(0,1) , (0,4) , (1,2) , (1,7) , (2,8) , (3,4) , (3 ,8) , (5,6) ,(5,8) , (5,9) , (6,7) , (7,8) , (8,9)}当它用邻接矩阵表示和邻接表表示时,分别写出从顶点 V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。 四、四、 阅读算法,回答问题(每小题 8 分,共 16 分) 1、假定从键盘上输入一批整数,依次为:78 63 45 30 91 34 –1,请写出输出结果。# include < iostream.h># include < stdlib.h >consst int stackmaxsize = 30;typedef int elemtype;struct stack {elemtype stack [stackmaxsize]; int top;};图深度优先序列广度优先序列邻接矩阵表示时 邻接表表示时 # include “stack.h”Void main ( ){ stack a; initstack(a); int x; cin >>x; while (x! = -1) { push (a, x ); cin >>x;}while (!stackempty (a)) cout <<pop (a) <<” ” ;cout <<end1;}该算法的输出结果为:__________________________________________________________. 2、阅读以下二叉树操作算法,指出该算法的功能。Template <calss type > void BinTree <Type> ::unknown (BinTreeNode<Type>*t) { BinTreeNode< Type> *p =t, *temp; if (p!=NULL) { temp = p→leftchild; p→leftchild = p→rightchild; p→rightchild = temp; unknown(p→leftchild); undnown(p→rightchild); }}该算法的功能是:________________________________ 五、五、 算法填空,在画有横线的地方填写合适的内容(10 分) 对顺序存储的有序表进行二分查找的递归算法 。 int Binsch( ElemType A[ ],int low ,int high,KeyType K ) { if (low <= high){ int mid = 1 if ( K= = A[ mid ].key ) return mid; else if ( K < A[mid].key) return 2 else return 3}else return 4 六、六、 编写算法(10 分) 编写算法,将一个结点类型为 Lnode 的单链表按逆序链接,即若原单链表中存储元素的次序为 a1,……an-1,an,则逆序链接后变为, an,an-1,……a1。Void contrary (Lnode * & HL) 数据结构试题(答案)数据结构试题(答案) 一、单选题(每小题 2 分,共 8 分)题 号 1 2 3 4答 案 C D A B二、填空题(每空 1 分,共 32 分)1: 集合、线性、树、图;2: 数据描述、操作声名;3: (38,56,25,60,42,74) ;4: HL→next =NULL; HL=HL→next;5: 前一个位置; n-1;6: S.stack [S.top]; HS→data;7: 5 318: 边结点、邻接点域、权域、链域;9: 索引值域、开始位置域;10: 10、3、3、B、I 和 J;11: O(log2n) 、O(nlog2n);12: m 、 m - 1三、运算题(每小题 6 分,共 24 分)1、划分次序划分结果第一次[38 24 40] 46 [56 80 95 79]第二次24 [38 40] 46 [56 80 95 79] 第三次24 38 40 46 [56 80 95 79]第四次24 38 40 46 56 [80 95 79]第五次24 38 40 46 56 79 [80 95]第六次24 38 40 46 56 79 80 95 2、 78 1503 57452031 233612 查找成功的平均查找长度:ASL SUCC=14/10= 1.43、此二叉树的后序遍历结果是:EDCBIHJGFA4、四、阅读算法,回答问题(每小题 8 分,共 16 分)1、 1、 该算法的输入结果是:34 91 30 45 63 782、 2、 该算法的功能是:交换二叉树的左右子树的递归算法。五、算法填空,在画有横线的地方填写合适的内容(10 分)1、1 是:(low + high)/2; 2 是: Binsch(A,low,mid–1,K); 3 是: Binsch(A,mid+1,high,K); 4 是: -1;六、编写算法(10 分)根据编程情况,酌情给分。 {Lnode *P=HL;HL=NULL;While (p!=null) { Lnode*q=p; P=p→next; q→next=HL; HL=q; }}吉首大学试题库课程测试试题(卷)课程测试试题(卷)----------------------以下为教师填写--------------------图深度优先序列广度优先序列邻接矩阵表示时0,1,2,8,3,4,5,6,7,90,1,4,2,7,3,8,6,5,9邻接表表示时0,4,3,8,9,5,6,7,1,20,4,1,3,7,2,8,6,9,5 0 1 2 3 4 5 6 7 8 9 10 11 12 I、命题院(部): 数学与计算机科学学院数学与计算机科学学院 II、课程名称: 数据结构数据结构 III、测试学期:20 -20 学年度第 学期IV、测试对象: 学院 专业 级 班V、问卷页数(A4): 页VI、答卷页数(A4): 页VII、考试方式: 闭卷闭卷 (开卷、闭卷或课程小论文,请填写清楚)VIII、问卷内容:(请老师在出题时安排紧凑,填空题象征性的留出一点空格,学生将所有的答案做在答题纸上的规定位置,并写清楚大题、小题的题号)第一部分 选择题(30 分) 一、一、项选择题(本大题共 15 小题,每小题 2 分,共 30 分)在每小题列出的四个选项中只有一个选项是符合题目要求的,请将正确选项前的字母填在题后的括号内。1.算法指的是( ) A.计算机程序 B.解决问题的计算方法 C.排序算法 D.解决问题的有限运算序列2.线性表采用链式存储时,结点的存储地址( ) A.必须是不连续的 B.连续与否均可 C.必须是连续的 D.和头结点的存储地址相连续3.将长度为 n 的单链表链接在长度为 m 的单链表之后的算法的时间复杂度为( ) A.O(1) B.O(n) C.O(m) D.O(m+n)4.由两个栈共享一个向量空间的好处是:( ) A.减少存取时间,降低下溢发生的机率 B.节省存储空间,降低上溢发生的机率 C.减少存取时间,降低上溢发生的机率 D.节省存储空间,降低下溢发生的机率5.设数组 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)%m6.如下陈述中正确的是( ) A.串是一种特殊的线性表 B.串的长度必须大于零 C.串中元素只能是字母 D.空串就是空白串7.若目标串的长度为 n,模式串的长度为[n/3],则执行模式匹配算法时,在最坏情况下的时间复杂度是( ) A.O(n3) B.O(n) C.O(n2) D.O(n3)8.一个非空广义表的表头( ) A.不可能是子表 B.只能是子表 C.只能是原子 D.可以是子表或原子9.假设以带行表的三元组表表示稀疏矩阵,则和下列行表02335 对应的稀疏矩阵是( ) A.08067000000050400000?????????????????? B.08067000504000000300?????????????????? C.08060000020050400000?????????????????? D.08060000700050400300??????????????????10.在一棵度为 3 的树中,度为 3 的结点个数为 2,度为 2 的结点个数为 1,则度为0 的结点个数为( ) A.4 B.5 C.6 D.711.在含 n 个顶点和 e 条边的无向图的邻接矩阵中,零元素的个数为( ) A.e B.2e C.n2-e D.n2-2e12.假设一个有 n 个顶点和 e 条弧的有向图用邻接表表示,则删除与某个顶点 vi相关的所有弧的时间复杂度是( ) A.O(n) B.O(e) C.O(n+e) D.O(n*e)13.用某种排序方法对关键字序列(25,84,21,47,15,27,68,35,20)进行排序时,序列的变化情况如下: 20,15,21,25,47,27,68,35,84 15,20,21,25,35,27,47,68,84 15,20,21,25,27,35,47,68,84 则所采用的排序方法是( ) A.选择排序 B.希尔排序 C.归并排序 D.快速排序14.适于对动态查找表进行高效率查找的组织结构是( )A.有序表 B.分块有序表 C.三叉排序树 D.线性链表15.不定长文件是指( )A.文件的长度不固定 B.记录的长度不固定C.字段的长度不固定 D.关键字项的长度不固定 第二部分 非选择题(共 70 分) 二、填空题(本大题共 10 小题,每小题 2 分,若有两个空格,每个空格 1 分,共 20 分)不写解答过程,将正确的答案写在每小题的空格内。错填或不填均无分。16.数据的逻辑结构是从逻辑关系上描述数据,它与数据的 无关,是独立于计算机的。17.在一个带头结点的单循环链表中,p 指向尾结点的直接前驱,则指向头结点的指针 head 可用 p 表示为 head= 。18.栈顶的位置是随着 操作而变化的。19.在串 S=“structure”中,以 t 为首字符的子串有 个。20.假设一个 9 阶的上三角矩阵 A 按列优先顺序压缩存储在一维数组 B 中,其中 B[0]存储矩阵中第 1 个元素 a1,1,则 B[31]中存放的元素是 。21.已知一棵完全二叉树中共有 768 结点,则该树中共有 个叶子结点。 22.已知一个图的广度优先生成树如右图所示,则与此相 应的广度优先遍历序列为 。 23.在单链表上难以实现的排序方法有 和 。 24.在有序表(12,24,36,48,60,72,84)中二分查找关键字 72 时所需进行的关键字比较次数为 。 25.多重表文件和倒排文件都归属于 文件。 三、解答题(本大题共 4 小题,每小题 5 分,共 20 分)26.画出下列广义表的共享结构图形表示 P=(((z),(x,y)),((x,y),x),(z))27.请画出与下列二叉树对应的森林。 28.已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示 0100110010000110110110110???????????????? (1)画出该图的图形; (2)根据邻接矩阵从顶点 a 出发进行深度优先遍历和广度优先遍历,ab cde 写出相应的遍历序列。 29.已知一个散列表如下图所示: 35 20 33 48 59 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函数为 h(key)=key%13, 处理冲突的方法为双重散列法,探查序列为: hi=(h(key)+i*h1(key))%m i=0,1,…,m-1其中 h1(key)=key%11+1回答下列问题:(1)对表中关键字 35,20,33 和 48 进行查找时,所需进行的比较次数各为多少?(2)该散列表在等概率查找时查找成功的平均查找长度为多少?四、算法阅读题(本大题共 4 小题,每小题 5 分,共 20 分)30.下列算法的功能是比较两个链串的大小,其返回值为: comstr(s1,s2)=?????????101121212当当当ssssss 请在空白处填入适当的内容。int comstr(LinkString s1,LinkString s2) {//s1 和 s2 为两个链串的头指针 while(s1&&s2){ if(s1->date<s2->date)return-1; if(s1->date>s2->date)return1; ① ; ② ; } if( ③ )return-1; if( ④ )return1; ⑤ ; }①②③④⑤31.阅读下面的算法 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; } 请回答下列问题: (1)说明语句 S1 的功能; (2)说明语句组 S2 的功能; (3)设链表表示的线性表为(a1,a2, …,an),写出算法执行后的返回值所表示的线性表。32.假设两个队列共享一个循环向量空间(参见右下图) , 其类型 Queue2 定义如下: typedef struct{ DateType data[MaxSize]; int front[2],rear[2]; }Queue2;对于 i=0 或 1,front[i]和 rear[i]分别为第 i 个队列的头指针和尾指针。请对以下算法填空,实现第 i 个队列的入队操作。 int EnQueue (Queue2*Q,int i,DateType x) {//若第 i 个队列不满,则元素 x 入队列,并返回 1;否则返回 0 if(i<0||i>1)return 0; if(Q->rear[i]==Q->front[ ① ]return0; Q->data[ ② ]=x; Q->rear[i]=[ ③ ]; return1; } ① ② ③33.已知二叉树的存储结构为二叉链表,阅读下面算法。 typedef struct node { DateType data; Struct node * next; }ListNode; typedef ListNode * LinkList ; LinkList Leafhead=NULL; Void Inorder (BinTree T) { LinkList s; If(T){ Inorder(T->lchild); If ((!T->lchild)&&(!T->rchild)){ s=(ListNode*)malloc(sizeof(ListNode)); s->data=T->data; s->next=Leafhead; Leafhead=s; } Inorder(T->rchild); } } 对于如下所示的二叉树 (1)画出执行上述算法后所建立的结构; (2)说明该算法的功能。五、算法设计题(本题共 10 分)34.阅读下列函数 arrange() int arrange(int a[],int 1,int h,int x) {//1 和 h 分别为数据区的下界和上界 int i,j,t; i=1;j=h; while(i<j){ while(i<j && a[j]>=x)j--; while(i<j && a[j]>=x)i++; if(i<j) { t=a[j];a[j]=a[i];a[i]=t;} } if(a[i]<x) return i; else return i-1; } (1)写出该函数的功能; (2)写一个调用上述函数实现下列功能的算法:对一整型数组 b[n]中的元素进行重新排列,将所有负数均调整到数组的低下标端,将所有正数均调整到数组的高下标端,若有零值,则置于两者之间,并返回数组中零元素的个数。 数据结构试题参考答案一、一、 单项选择题(本大题共 15 小题,每小题 2 分,共 30 分) 1.D2.B3.C4.B5.D6.A7.C8,D9,A 10.C11.D12.C 13.D14.C15.B二、填空题(本大题共 10 小题,每小题 2 分,共 20 分)16.存储(或存储结构)17.p->next->next18.进栈和退栈19.1220.a4,821.38422.abefcdg23.快速排序、堆排序、希尔排序24.225.多关键字三、解答题(本大题共 4 小题,每小题 5 分,共 20 分)26. 图 1 图 227. 28.该图的图形为: 深度优先遍历序列为:abdce广度优先遍历序列为:abedc29. (1)对关键字 35、20、33 和 48 进行查找的比较次数为3、2、1、1; (2)平均查找长度ASL ??? ? ??321 12595四、算法阅读题(本大题共 4 小题,每小题 5 分,共 20 分)30. ①S1=S1->next ②s2=s2->next ③s2(或 s2!=NULL 或 s2&&!s1) ④s1(或 s1!=NULL 或 s1&&!s2) ⑤return 031.(1)查询链表的尾结点 (2)将第一个结点链接到链表的尾部,作为新的尾结点 (3)返回的线性表为(a2,a3,…,an,a1)32. ①(i+1)%2(或 1-i) ②Q->rear[i] ③(Q->rear[i]+)%Maxsize33.(1)LeafheadF H G D∧ (2)中序遍历二叉树,按遍历序列中叶子结点数据域的值构建一个以Leafhead 为头指针的逆序单链表(或按二叉树中叶子结点数据自右至左链接成一个链表) 。 五、算法设计题(本题共 10 分) 34. (1)该函数的功能是:调整整数数组 a[]中的元素并返回分界值 i,使所有<x 的元素均落在 a[1..i]上,使所有≥x 的元素均落在 a[i+1..h]上。 (2)int f(int b[],int n) 或 int f(int b[],int n) { { int p,q; int p,q; p=arrange(b,0,n-1,0); p=arrange(b,0,n-1,1); q= arrange(b,p+1,n-1,1); q= arrange(b,0,p,0); return q-p; return p-q; } } 吉首大学试题库课程测试试题(卷)课程测试试题(卷)----------------------以下为教师填写--------------------I、命题院(部): 数学与计算机科学学院数学与计算机科学学院 II、课程名称: 数据结构数据结构 III、测试学期:20 -20 学年度第 学期IV、测试对象: 学院 专业 级 班V、问卷页数(A4): 页VI、答卷页数(A4): 页VII、考试方式: 闭卷闭卷 (开卷、闭卷或课程小论文,请填写清楚)VIII、问卷内容:(请老师在出题时安排紧凑,填空题象征性的留出一点空格,学生将所有的答案做在答题纸上的规定位置,并写清楚大题、小题的题号) 一、选择题(一、选择题(20 分)分)1.组成数据的基本单位是( ) 。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2.设数据结构 A=(D,R),其中 D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},则数据结构 A 是( ) 。(A) 线性结构(B) 树型结构 (C) 图型结构(D) 集合 3.数组的逻辑结构不同于下列( )的逻辑结构。(A) 线性表(B) 栈 (C) 队列(D) 树4.二叉树中第 i(i≥1)层上的结点数最多有( )个。(A) 2i(B) 2i(C) 2i-1(D) 2i-15.设指针变量 p 指向单链表结点 A,则删除结点 A 的后继结点 B 需要的操作为( ) 。(A) p->next=p->next->next(B) p=p->next(C) p=p->next->next(D) p->next=p6.设栈 S 和队列 Q 的初始状态为空,元素 E1、E2、E3、E4、E5 和 E6 依次通过栈 S,一个元素出栈后即进入队列 Q,若 6 个元素出列的顺序为E2、E4、E3、E6、E5 和 E1,则栈 S 的容量至少应该是( ) 。(A) 6(B) 4(C) 3(D) 27.将 10 阶对称矩阵压缩存储到一维数组 A 中,则数组 A 的长度最少为( ) 。(A) 100(B) 40(C) 55(D) 808.设结点 A 有 3 个兄弟结点且结点 B 为结点 A 的双亲结点,则结点 B 的度数数为( ) 。(A) 3(B) 4(C) 5(D) 19.根据二叉树的定义可知二叉树共有( )种不同的形态。(A) 4(B) 5(C) 6(D) 710.10. 设有以下四种排序方法,则( )的空间复杂度最大。(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题二、填空题(30 分分)1.1. 设顺序循环队列 Q[0:m-1]的队头指针和队尾指针分别为 F 和 R,其中队头指针 F 指向当前队头元素的前一个位置,队尾指针 R 指向当前队尾元素所在的位置,则出队列的语句为 F =____________;。2.2. 设线性表中有 n 个数据元素,则在顺序存储结构上实现顺序查找的平均时间复杂度为___________,在链式存储结构上实现顺序查找的平均时间复杂度为___________。3.3. 设一棵二叉树中有 n 个结点,则当用二叉链表作为其存储结构时,该二叉链表中共有________个指针域,__________个空指针域。4.4. 设指针变量 p 指向单链表中结点 A,指针变量 s 指向被插入的结点 B,则在结点 A 的后面插入结点 B 的操作序列为______________________________________。5.5. 设无向图 G 中有 n 个顶点和 e 条边,则其对应的邻接表中有_________个表头结点和_________个表结点。 6.6. 设无向图 G 中有 n 个顶点 e 条边,所有顶点的度数之和为 m,则 e 和m 有______关系。7.7. 设一棵二叉树的前序遍历序列和中序遍历序列均为 ABC,则该二叉树的后序遍历序列为__________。8.8. 设一棵完全二叉树中有 21 个结点,如果按照从上到下、从左到右的顺序从 1 开始顺序编号,则编号为 8 的双亲结点的编号是___________,编号为 8 的左孩子结点的编号是_____________。9.9. 下列程序段的功能实现子串 t 在主串 s 中位置的算法,要求在下划线处填上正确语句。int index(char s[ ], char t[ ]){i=j=0;while(i<strlen(s) && j<strlen(t)) if(s[i]==t[j]){i=i+l; j=j+l;}else{i=_______; j=______;}if (j==strlen(t))return(i-strlen(t));else return (-1);}10. 10. 设一个连通图 G 中有 n 个顶点 e 条边,则其最小生成树上有________条边。 三、应用题(三、应用题(30 分)分)1.设完全二叉树的顺序存储结构中存储数据 ABCDE,要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。2.设给定一个权值集合 W=(3,5,7,9,11),要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度 WPL。3.设一组初始记录关键字序列为(19,21,16,5,18,23),要求给出以 19 为基准的一趟快速排序结果以及第 2 趟直接选择排序后的结果。4.设一组初始记录关键字集合为(25,10,8,27,32,68),散列表的长度为 8,散列函数 H(k)=k mod 7,要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。5.设无向图 G(所右图所示) ,要求给出该图的深度优先和广度优先遍历的序列并给出该图的最小生成树。 四、算法设计题四、算法设计题(20 分分) 1.1. 设计判断单链表中结点是否关于中心对称算法。2.2. 设计在链式存储结构上建立一棵二叉树的算法。3.3. 设计判断一棵二叉树是否是二叉排序树的算法。 数据结构试卷参考答案数据结构试卷参考答案 一、选择题一、选择题1.C2.C3.D4.C5.A6.C7.C8.B9.B10.B 二、填空题二、填空题1.1. (F+1) % m2.2. O(n),O(n)3.3. 2n,n+14.4. s->next=p->next; s->next=s5.5. n, 2e6.6. m=2e7.7. CBA8.8. 4,169.9. i-j+1,010. 10. n-1 三、应用题三、应用题1.1. 链式存储结构略,前序 ABDEC,中序 DBEAC,后序 DEBCA。2.2. 哈夫曼树略,WPL=783.3. (18,5,16,19,21,23),(5,16,21,19,18,23)4.4. 线性探测:6827322510876543210??链地址法:276832251086543210????????????hhhhhhh5.5. 深度:125364,广度:123456,最小生成树 T 的边集为 E={(1,4),(1,3),(3,5),(5,6),(5,6)} 四、算法设计题四、算法设计题1.1. 设计判断单链表中结点是否关于中心对称算法。typedef struct {int s[100]; int top;} sqstack;int lklistsymmetry(lklist *head){ sqstack stack; stack.top= -1; lklist *p; for(p=head;p!=0;p=p->next) {stack.top++; stack.s[stack.top]=p->data;} for(p=head;p!=0;p=p->next) if (p->data==stack.s[stack.top]) stack.top=stack.top-1; else return(0); return(1);}2.2. 设计在链式存储结构上建立一棵二叉树的算法。 typedef char datatype;typedef struct node {datatype data; struct node *lchild,*rchild;} bitree;void createbitree(bitree *&bt){ char ch; scanf("%c",&ch); if(ch=='#') {bt=0; return;}bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch;createbitree(bt->lchild); createbitree(bt->rchild);}3.3. 设计判断一棵二叉树是否是二叉排序树的算法。int minnum=-32768,flag=1;typedef struct node{int key; struct node *lchild,*rchild;}bitree;void inorder(bitree *bt){ if (bt!=0) {inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key; inorder(bt->rchild);}} 数据结构试卷(二)数据结构试卷(二) 一、选择题一、选择题(24 分分)1.下面关于线性表的叙述错误的是( ) 。(A) 线性表采用顺序存储必须占用一片连续的存储空间(B) 线性表采用链式存储不必占用一片连续的存储空间(C) 线性表采用链式存储便于插入和删除操作的实现(D) 线性表采用顺序存储便于插入和删除操作的实现2.设哈夫曼树中的叶子结点总数为 m,若用二叉链表作为存储结构,则该哈夫曼树中总共有( )个空指针域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m3.设顺序循环队列 Q[0:M-1]的头指针和尾指针分别为 F 和 R,头指针 F 总是指向队头元素的前一位置,尾指针 R 总是指向队尾元素的当前位置,则该循环队列中的元素个数为( ) 。(A) R-F(B) F-R(C) (R-F+M)%M(D) (F-R+M)%M4.设某棵二叉树的中序遍历序列为 ABCD,前序遍历序列为 CABD,则后序遍历该二叉树得到序列为( ) 。(A) BADC(B) BCDA(C) CDAB(D) CBDA5.设某完全无向图中有 n 个顶点,则该完全无向图中有( )条边。(A) n(n-1)/2(B) n(n-1)(C) n2 (D) n2-16.设某棵二叉树中有 2000 个结点,则该二叉树的最小高度为( ) 。(A) 9(B) 10(C) 11(D) 127.设某有向图中有 n 个顶点,则该有向图对应的邻接表中有( )个表头结点。(A) n-1(B) n(C) n+1(D) 2n-18.设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字 5 为基准进行一趟快速排序的结果为( ) 。(A) 2,3,5,8,6(B) 3,2,5,8,6(C) 3,2,5,6,8(D) 2,3,6,5,8 二、填空题二、填空题(24 分分)1.1. 为了能有效地应用 HASH 查找技术,必须解决的两个问题是____________________和__________________________。2.2. 下面程序段的功能实现数据 x 进栈,要求在下划线处填上正确的语句。typedef struct {int s[100]; int top;} sqstack;void push(sqstack &stack,int x){if (stack.top==m-1) printf(“overflow”);else {____________________;_________________;}}3.3. 中序遍历二叉排序树所得到的序列是___________序列(填有序或无序) 。4.4. 快速排序的最坏时间复杂度为___________,平均时间复杂度为__________。5.5. 设某棵二叉树中度数为 0 的结点数为 N0,度数为 1 的结点数为 N1,则该二叉树中度数为 2 的结点数为_________;若采用二叉链表作为该二叉树的存储结构,则该二叉树中共有_______个空指针域。6.6. 设某无向图中顶点数和边数分别为 n 和 e,所有顶点的度数之和为 d,则e=_______。7.7. 设一组初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选法建立的初始堆为___________________________。 8.8. 设某无向图 G 的邻接表为31241314234321????????????????????vvvv,则从顶点 V1开始的深度优先遍历序列为___________;广度优先遍历序列为____________。 三、应用题三、应用题(36 分分)1. 1. 设一组初始记录关键字序列为(45,80,48,40,22,78),则分别给出第 4 趟简单选择排序和第 4 趟直接插入排序后的结果。2. 2. 设指针变量 p 指向双向链表中结点 A,指针变量 q 指向被插入结点 B,要求给出在结点 A 的后面插入结点 B 的操作序列(设双向链表中结点的两个指针域分别为 llink和 rlink) 。3. 3. 设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找方法用二分查找,要求计算出查找关键字 62 时的比较次数并计算出查找成功时的平均查找长度。4. 4. 设一棵树 T 中边的集合为{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。5. 5. 设有无向图 G(如右图所示) ,要求给出用普里姆算法构造最小生成树所走过的边的集合。6. 6. 设有一组初始记录关键字为(45,80,48,40,22,78),要求构造一棵二叉排序树并给出构造过程。 四、算法设计题四、算法设计题(16 分分) 1. 1. 设有一组初始记录关键字序列(K1,K2,…,Kn) ,要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于 Ki,右半部分的每个关键字均大于等于 Ki。2. 2. 设有两个集合 A 和集合 B,要求设计生成集合 C=A∩B 的算法,其中集合 A、B和 C 用链式存储结构表示。 数据结构试卷(二)参考答案数据结构试卷(二)参考答案 一、选择题一、选择题1.D2.B3.C4.A5.A6.C7.B8.C 二、填空题二、填空题1.1. 构造一个好的 HASH 函数,确定解决冲突的方法2.2. stack.top++,stack.s[stack.top]=x3.3. 有序4.4. O(n2),O(nlog2n)5.5. N0-1,2N0+N16.6. d/27.7. (31,38,54,56,75,80,55,63)8.8. (1,3,4,2),(1,3,2,4) 三、应用题三、应用题1.1. (22,40,45,48,80,78),(40,45,48,80,22,78)2.2. q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q;3.3. 2,ASL=91*1+2*2+3*4+4*2)=25/94.4. 树的链式存储结构略,二叉树略5.5. E={(1,3),(1,2),(3,5),(5,6),(6,4)}6.6. 略 四、算法设计题四、算法设计题1.1. 设有一组初始记录关键字序列(K1,K2,…,Kn) ,要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于 Ki,右半部分的每个关键字均大于等于 Ki。void quickpass(int r[], int s, int t){ int i=s, j=t, x=r[s]; while(i<j){while (i<j && r[j]>x) j=j-1; if (i<j) {r[i]=r[j];i=i+1;} while (i<j && r[i]<x) i=i+1; if (i<j) {r[j]=r[i];j=j-1;} } r[i]=x;}2.2. 设有两个集合 A 和集合 B,要求设计生成集合 C=A∩B 的算法,其中集合A、B 和 C 用链式存储结构表示。typedef struct node {int data; struct node *next;}lklist;void intersection(lklist *ha,lklist *hb,lklist *&hc){lklist *p,*q,*t;for(p=ha,hc=0;p!=0;p=p->next){ for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;}}} 数据结构试卷(三)数据结构试卷(三) 一、选择题一、选择题(30 分分)1.设某数据结构的二元组形式表示为 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 是( ) 。(A) 线性结构(B) 树型结构(C) 物理结构(D) 图型结构2.下面程序的时间复杂为( )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)3.设指针变量 p 指向单链表中结点 A,若删除单链表中结点 A,则需要修改指针的操作序列为( ) 。(A) q=p->next;p->data=q->data;p->next=q->next;free(q);(B) q=p->next;q->data=p->data;p->next=q->next;free(q);(C) q=p->next;p->next=q->next;free(q);(D) q=p->next;p->data=q->data;free(q);4.设有 n 个待排序的记录关键字,则在堆排序中需要( )个辅助记录单元。(A) 1(B) n(C) nlog2n(D) n25.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以 20 为基准记录的一趟快速排序结束后的结果为( )。(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,216.设二叉排序树中有 n 个结点,则在二叉排序树的平均平均查找长度为( ) 。(A) O(1)(B) O(log2n)(C)(D) O(n2)7.设无向图 G 中有 n 个顶点 e 条边,则其对应的邻接表中的表头结点和表结点的个数分别为( ) 。(A) n,e(B) e,n(C) 2n,e(D) n,2e8. 设某强连通图中有 n 个顶点,则该强连通图中至少有( )条边。(A) n(n-1)(B) n+1(C) n(D) n(n+1)9.设有 5000 个待排序的记录关键字,如果需要用最快的方法选出其中最小的 10 个记录关键字,则用下列( )方法可以达到此目的。(A) 快速排序(B) 堆排序(C) 归并排序(D) 插入排序10.下列四种排序中( )的空间复杂度最大。(A) 插入排序(B) 冒泡排序(C) 堆排序(D) 归并排序 二、填空殖二、填空殖(48 分,其中最后两小题各分,其中最后两小题各 6 分分)1.1. 数据的物理结构主要包括_____________和______________两种情况。2.2. 设一棵完全二叉树中有 500 个结点,则该二叉树的深度为__________;若用二叉链表作为该完全二叉树的存储结构,则共有___________个空指针域。3.3. 设输入序列为 1、2、3,则经过栈的作用后可以得到___________种不同的输出序列。4.4. 设有向图 G 用邻接矩阵 A[n][n]作为存储结构,则该邻接矩阵中第 i 行上所有元素之和等于顶点 i 的________,第 i 列上所有元素之和等于顶点 i 的________。5.5. 设哈夫曼树中共有 n 个结点,则该哈夫曼树中有________个度数为 1 的结点。6.6. 设有向图 G 中有 n 个顶点 e 条有向边,所有的顶点入度数之和为 d,则 e 和 d 的关系为_________。7.7. __________遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序) 。 8.8. 设查找表中有 100 个元素,如果用二分法查找方法查找数据元素 X,则最多需要比较________次就可以断定数据元素 X 是否在查找表中。9.9. 不论是顺序存储结构的栈还是链式存储结构的栈,其入栈和出栈操作的时间复杂度均为____________。10. 10. 设有 n 个结点的完全二叉树,如果按照从自上到下、从左到右从 1 开始顺序编号,则第 i 个结点的双亲结点编号为____________,右孩子结点的编号为___________。11. 11. 设一组初始记录关键字为(72,73,71,23,94,16,5),则以记录关键字 72 为基准的一趟快速排序结果为___________________________。12. 12. 设有向图 G 中有向边的集合 E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>},则该图的一种拓扑序列为____________________。13. 13. 下列算法实现在顺序散列表中查找值为 x 的关键字,请在下划线处填上正确的语句。struct record{int key; int others;};int hashsqsearch(struct record hashtable[ ],int k){int i,j; j=i=k % p;while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);} if (_______________________ ) return(j); else return(-1);}14. 14. 下列算法实现在二叉排序树上查找关键值 k,请在下划线处填上正确的语句。typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree;bitree *bstsearch(bitree *t, int k){ if (t==0 ) return(0);else while (t!=0)if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________;} 三、算法设计题三、算法设计题(22 分分)1. 1. 设计在单链表中删除值相同的多余结点的算法。2. 2. 设计一个求结点 x 在二叉树中的双亲结点算法。 数据结构试卷(三)参考答案数据结构试卷(三)参考答案 一、选择题一、选择题1.B2.B3.A4.A5.A6.B7.D8.C9.B10.D第 3 小题分析:首先用指针变量 q 指向结点 A 的后继结点 B,然后将结点 B 的值复制到结点 A 中,最后删除结点 B。第 9 小题分析:9 快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的 10 个数,而堆排序只需要在初始堆的基础上再进行 10 次筛选即可,每次筛选的时间复杂度为 O(log2n)。 二、填空题二、填空题1.1. 顺序存储结构、链式存储结构2.2. 9,5013.3. 54.4. 出度,入度5.5. 06.6. e=d7.7. 中序8.8. 79.9. O(1)10. 10. i/2,2i+111. 11. (5,16,71,23,72,94,73)12. 12. (1,4,3,2)13. 13. j+1,hashtable[j].key==k14. 14. return(t),t=t->rchild第 8 小题分析:二分查找的过程可以用一棵二叉树来描述,该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度 1+log2n。 三、算法设计题三、算法设计题1.1. 设计在单链表中删除值相同的多余结点的算法。typedef int datatype;typedef struct node {datatype data; struct node *next;}lklist;void delredundant(lklist *&head){ lklist *p,*q,*s; for(p=head;p!=0;p=p->next) { for(q=p->next,s=q;q!=0; ) if (q->data==p->data) {s->next=q->next; free(q);q=s->next;} else {s=q,q=q->next;} }}2.2. 设计一个求结点 x 在二叉树中的双亲结点算法。typedef struct node {datatype data; struct node *lchild,*rchild;} bitree;bitree *q[20]; int r=0,f=0,flag=0;void preorder(bitree *bt, char x){ if (bt!=0 && flag==0)if (bt->data==x) { flag=1; return;}else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); }}void parent(bitree *bt,char x){ int i; preorder(bt,x); for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break; if (flag==0) printf("not found x\n"); else if (i<=r) printf("%c",bt->data); else printf("not parent");} 数据结构试卷(四)数据结构试卷(四) 一、选择题一、选择题(30 分分)1.设一维数组中有 n 个数组元素,则读取第 i 个数组元素的平均时间复杂度为( ) 。(A) O(n)(B) O(nlog2n)(C) O(1)(D) O(n2)2.设一棵二叉树的深度为 k,则该二叉树中最多有( )个结点。(A) 2k-1(B) 2k(C) 2k-1(D) 2k-13.设某无向图中有 n 个顶点 e 条边,则该无向图中所有顶点的入度之和为( ) 。(A) n(B) e(C) 2n(D) 2e4.在二叉排序树中插入一个结点的时间复杂度为( ) 。(A) O(1)(B) O(n)(C) O(log2n)(D) O(n2)5.设某有向图的邻接表中有 n 个表头结点和 m 个表结点,则该图中有( )条有向边。(A) n(B) n-1(C) m(D) m-16.设一组初始记录关键字序列为(345,253,674,924,627),则用基数排序需要进行( )趟的分配和回收才能使得初始关键字序列变成有序序列。(A) 3(B) 4(C) 5(D) 87.设用链表作为栈的存储结构则退栈操作( ) 。(A) 必须判别栈是否为满(B) 必须判别栈是否为空(C) 判别栈元素的类型(D) 对栈不作任何判别8.下列四种排序中( )的空间复杂度最大。(A) 快速排序(B) 冒泡排序(C) 希尔排序(D) 堆9.设某二叉树中度数为 0 的结点数为 N0,度数为 1 的结点数为 Nl,度数为 2 的结点数为N2,则下列等式成立的是( ) 。(A) N0=N1+1(B) N0=Nl+N2(C) N0=N2+1(D) N0=2N1+l10.设有序顺序表中有 n 个数据元素,则利用二分查找法查找数据元素 X 的最多比较次数不超过( ) 。(A) log2n+1(B) log2n-1(C) log2n(D) log2(n+1) 二、填空题二、填空题(42 分分)1. 1. 设有 n 个无序的记录关键字,则直接插入排序的时间复杂度为________,快速排序的平均时间复杂度为_________。2. 2. 设指针变量 p 指向双向循环链表中的结点 X,则删除结点 X 需要执行的语句序列为_________________________________________________________(设结点中的两个指针域分别为 llink 和 rlink) 。3. 3. 根据初始关键字序列(19,22,01,38,10)建立的二叉排序树的高度为____________。4. 4. 深度为 k 的完全二叉树中最少有____________个结点。5. 5. 设初始记录关键字序列为(K1,K2,…,Kn),则用筛选法思想建堆必须从第______个元素开始进行筛选。6. 6. 设哈夫曼树中共有 99 个结点,则该树中有_________个叶子结点;若采用二叉链表作为存储结构,则该树中有_____个空指针域。7. 7. 设有一个顺序循环队列中有 M 个存储单元,则该循环队列中最多能够存储________个队列元素;当前实际存储________________个队列元素(设头指针 F 指向当前队头元素的前一个位置,尾指针指向当前队尾元素的位置) 。8. 8. 设顺序线性表中有 n 个数据元素,则第 i 个位置上插入一个数据元素需要移动表中_______个数据元素;删除第 i 个位置上的数据元素需要移动表中_______个元素。9. 9. 设一组初始记录关键字序列为(20,18,22,16,30,19),则以 20 为中轴的一趟快速排序结果为______________________________。10.10.设一组初始记录关键字序列为(20,18,22,16,30,19),则根据这些初始关键字序列建成的初始堆为________________________。11.11.设某无向图 G 中有 n 个顶点,用邻接矩阵 A 作为该图的存储结构,则顶点 i和顶点 j 互为邻接点的条件是______________________。 12.12.设无向图对应的邻接矩阵为 A,则 A 中第 i 上非 0 元素的个数_________第 i列上非 0 元素的个数(填等于,大于或小于) 。13.13.设前序遍历某二叉树的序列为 ABCD,中序遍历该二叉树的序列为 BADC,则后序遍历该二叉树的序列为_____________。14.14.设散列函数 H(k)=k mod p,解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表 hashtalbe 中查找关键字值等于 k 的结点,成功时返回指向关键字的指针,不成功时返回标志 0。typedef struct node {int key; struct node *next;} lklist; void createlkhash(lklist *hashtable[ ]){int i,k; lklist *s;for(i=0;i<m;i++)_____________________;for(i=0;i<n;i++){s=(lklist *)malloc(sizeof(lklist)); s->key=a[i];k=a[i] % p; s->next=hashtable[k];_______________________;}} 三、算法设计题三、算法设计题(28 分分)1. 1. 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符),要求利用原单链表中结点空间设计出三个单链表的算法,使每个单链表只包含同类字符。1.2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。2.3. 在链式存储结构上建立一棵二叉排序树。 数据结构试卷(四)参考答案数据结构试卷(四)参考答案 一、选择题一、选择题1.C2.D3.D4.B5.C6.A7.B8.A9.C10.A 二、填空题二、填空题1.1. O(n2),O(nlog2n)2.2. p>llink->rlink=p->rlink; p->rlink->llink=p->rlink3.3. 34.4. 2k-15.5. n/26.6. 50,517.7. m-1,(R-F+M)%M8.8. n+1-i,n-i9.9. (19,18,16,20,30,22)10. 10. (16,18,19,20,32,22)11. 11. A[i][j]=112. 12. 等于13. 13. BDCA14. 14. hashtable[i]=0,hashtable[k]=s 三、算法设计题三、算法设计题1.1. 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符),要求利用原单链表中结点空间设计出三个单链表的算法,使每个单链表只包含同类字符。typedef char datatype;typedef struct node {datatype data; struct node *next;}lklist;void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc){ lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) { head=p->next; p->next=0; if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;} else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;} }}2.2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。typedef struct node {int data; struct node *lchild,*rchild;} bitree;void swapbitree(bitree *bt){ bitree *p; if(bt==0) return;swapbitree(bt->lchild); swapbitree(bt->rchild);p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p;}3.3. 在链式存储结构上建立一棵二叉排序树。#define n 10typedef struct node{int key; struct node *lchild,*rchild;}bitree;void bstinsert(bitree *&bt,int key){ if (bt==0){bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0;} else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key);}void createbsttree(bitree *&bt) { int i; for(i=1;i<=n;i++) bstinsert(bt,random(100));} 数据结构试卷(五)数据结构试卷(五) 一、选择题一、选择题(30 分分) 1.数据的最小单位是( ) 。(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2.设一组初始记录关键字序列为(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,203.设一组初始记录关键字序列为(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,854.函数 substr(“DATASTRUCTURE”,5,9)的返回值为( ) 。(A) “STRUCTURE”(B) “DATA”(C) “ASTRUCTUR”(D) “DATASTRUCTURE”5.设一个有序的单链表中有 n 个结点,现要求插入一个新结点后使得单链表仍然保持有序,则该操作的时间复杂度为( ) 。(A) O(log2n)(B) O(1)(C) O(n2)(D) O(n)6.设一棵 m 叉树中度数为 0 的结点数为 N0,度数为 1 的结点数为 Nl,……,度数为 m 的结点数为 Nm,则 N0=( ) 。(A) Nl+N2+……+Nm(B) l+N2+2N3+3N4+……+(m-1)Nm(C) N2+2N3+3N4+……+(m-1)Nm(D) 2Nl+3N2+……+(m+1)Nm7.设有序表中有 1000 个元素,则用二分查找查找元素 X 最多需要比较( )次。(A) 25(B) 10(C) 7(D) 18.设连通图 G 中的边集 E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点 a 出发可以得到一种深度优先遍历的顶点序列为( ) 。(A) abedfc(B) acfebd(C) aebdfc(D) aedfcb9.设输入序列是 1、2、3、……、n,经过栈的作用后输出序列的第一个元素是 n,则输出序列中第 i 个输出元素是( ) 。(A) n-i(B) n-1-i(C) n+1-i(D) 不能确定10 设一组初始记录关键字序列为(45,80,55,40,42,85),则以第一个记录关键字 45为基准而得到一趟快速排序的结果是( ) 。(A) 40,42,45,55,80,83(B) 42,40,45,80,85,88(C) 42,40,45,55,80,85(D) 42,40,45,85,55,80 二、填空题二、填空题(共共 30 分分)1.1. 设有一个顺序共享栈 S[0:n-1],其中第一个栈项指针 top1 的初值为-1,第二个栈顶指针 top2 的初值为 n,则判断共享栈满的条件是____________________。2.2. 在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。3.3. 设有一个 n 阶的下三角矩阵 A,如果按照行的顺序将下三角矩阵中的元素(包括对角线上元素)存放在 n(n+1)个连续的存储单元中,则 A[i][j]与 A[0][0]之间有_______个数据元素。4.4. 栈的插入和删除只能在栈的栈顶进行,后进栈的元素必定先出栈,所以又把栈称为__________表;队列的插入和删除运算分别在队列的两端进行,先进队列的元素必定先出队列,所以又把队列称为_________表。 5.5. 设一棵完全二叉树的顺序存储结构中存储数据元素为 ABCDEF,则该二叉树的前序遍历序列为___________,中序遍历序列为___________,后序遍历序列为___________。6.6. 设一棵完全二叉树有 128 个结点,则该完全二叉树的深度为________,有__________个叶子结点。7.7. 设有向图 G 的存储结构用邻接矩阵 A 来表示,则 A 中第 i 行中所有非零元素个数之和等于顶点 i 的________,第 i 列中所有非零元素个数之和等于顶点 i 的__________。8.8. 设一组初始记录关键字序列(k1,k2,……,kn)是堆,则对 i=1,2,…,n/2 而言满足的条件为_______________________________。9.9. 下面程序段的功能是实现冒泡排序算法,请在下划线处填上正确的语句。void bubble(int r[n]){for(i=1;i<=n-1; i++){for(exchange=0,j=0; j<_____________;j++) if (r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}if (exchange==0) return;}}10. 10. 下面程序段的功能是实现二分查找算法,请在下划线处填上正确的语句。struct record{int key; int others;};int bisearch(struct record r[ ], int k){ int low=0,mid,high=n-1; while(low<=high){ ________________________________; if(r[mid].key==k) return(mid+1); else if(____________) high=mid-1;else low=mid+1; } return(0);}三、应用题三、应用题(24 分分)1.1. 设某棵二叉树的中序遍历序列为 DBEAC,前序遍历序列为ABDEC,要求给出该二叉树的的后序遍历序列。2.2. 设无向图 G(如右图所示) ,给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。3.3. 设一组初始记录关键字序列为(15,17,18,22,35,51,60),要求计算出成功查找时的平均查找长度。4.4. 设散列表的长度为 8,散列函数 H(k)=k mod 7,初始记录关键字序列为(25,31,8,27,13,68),要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。 四、算法设计题四、算法设计题(16 分分)1. 1. 设计判断两个二叉树是否相同的算法。2. 2. 设计两个有序单链表的合并排序算法。 数据结构试卷(五)参考答案数据结构试卷(五)参考答案 一、选择题一、选择题1.A2.B3.A4.A5.D 6.B7.B8.B9.C10.C 二、填空题二、填空题1.1. top1+1=top22.2. 可以随机访问到任一个顶点的简单链表3.3. i(i+1)/2+j-14.4. FILO,FIFO5.5. ABDECF,DBEAFC,DEBFCA6.6. 8,647.7. 出度,入度8.8. ki<=k2i && ki<=k2i+19.9. n-i,r[j+1]=r[j]10. 10. mid=(low+high)/2,r[mid].key>k 三、应用题三、应用题1.1. DEBCA2.2. E={(1,5),(5,2),(5,3),(3,4)},W=103.3. ASL=(1*1+2*2+3*4)/7=17/74.4. ASL1=7/6,ASL2=4/3四、算法设计题四、算法设计题1.1. 设计判断两个二叉树是否相同的算法。typedef struct node {datatype data; struct node *lchild,*rchild;} bitree;int judgebitree(bitree *bt1,bitree *bt2){ if (bt1==0 && bt2==0) return(1); else if (bt1==0 || bt2==0 ||bt1->data!=bt2->data) return(0); else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}2.2. 设计两个有序单链表的合并排序算法。void mergelklist(lklist *ha,lklist *hb,lklist *&hc){ lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->data<hb->data){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;} else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;} if(ha==0) s->next=hb; else s->next=ha;} 数据结构试卷(六)数据结构试卷(六) 一、选择题一、选择题(30 分分)1. 设一组权值集合 W={2,3,4,5,6},则由该权值集合构造的哈夫曼树中带权路径长度之和为( ) 。(A) 20(B) 30(C) 40(D) 452.执行一趟快速排序能够得到的序列是( ) 。(A) [41,12,34,45,27] 55 [72,63](B) [45,34,12,41] 55 [72,63,27](C) [63,12,34,45,27] 55 [41,72](D) [12,27,45,41] 55 [34,63,72]3.设一条单链表的头指针变量为 head 且该链表没有头结点,则其判空条件是( ) 。(A) head==0(B) head->next==0(C) head->next==head(D) head!=04.时间复杂度不受数据初始状态影响而恒为 O(nlog2n)的是( ) 。(A) 堆排序(B) 冒泡排序(C) 希尔排序(D) 快速排序5.设二叉树的先序遍历序列和后序遍历序列正好相反,则该二叉树满足的条件是( ) 。(A) 空或只有一个结点(B) 高度等于其结点数(C) 任一结点无左孩子(D) 任一结点无右孩子6.一趟排序结束后不一定能够选出一个元素放在其最终位置上的是( ) 。(A) 堆排序(B) 冒泡排序(C) 快速排序(D) 希尔排序7.设某棵三叉树中有 40 个结点,则该三叉树的最小高度为( ) 。(A) 3(B) 4(C) 5(D) 68.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为( ) 。(A) O(n)(B) O(n2)(C) O(n1/2)(D) O(1og2n)9.二路归并排序的时间复杂度为( ) 。(A) O(n)(B) O(n2)(C) O(nlog2n)(D) O(1og2n)10. 深度为 k 的完全二叉树中最少有( )个结点。(A) 2k-1-1(B) 2k-1(C) 2k-1+1(D) 2k-111.设指针变量 front 表示链式队列的队头指针,指针变量 rear 表示链式队列的队尾指针,指针变量 s 指向将要入队列的结点 X,则入队列的操作序列为( ) 。(A) front->next=s;front=s;(B) s->next=rear;rear=s;(C) rear->next=s;rear=s;(D) s->next=front;front=s;12.设某无向图中有 n 个顶点 e 条边,则建立该图邻接表的时间复杂度为( ) 。(A) O(n+e)(B) O(n2)(C) O(ne)(D) O(n3)13.设某哈夫曼树中有 199 个结点,则该哈夫曼树中有( )个叶子结点。(A) 99(B) 100(C) 101(D) 10214.设二叉排序树上有 n 个结点,则在二叉排序树上查找结点的平均时间复杂度为( ) 。(A) O(n)(B) O(n2)(C) O(nlog2n)(D) O(1og2n)15.设用邻接矩阵 A 表示有向图 G 的存储结构,则有向图 G 中顶点 i 的入度为( ) 。(A) 第 i 行非 0 元素的个数之和(B) 第 i 列非 0 元素的个数之和(C) 第 i 行 0 元素的个数之和(D) 第 i 列 0 元素的个数之和 二、判断题二、判断题(20 分分)1.调用一次深度优先遍历可以访问到图中的所有顶点。 ( )2.分块查找的平均查找长度不仅与索引表的长度有关,而且与块的长度有关。 ( )3.冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。 ( )4.满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。 ( )5.设一棵二叉树的先序序列和后序序列,则能够唯一确定出该二叉树的形状。 ( )6.层次遍历初始堆可以得到一个有序的序列。 ( )7.设一棵树 T 可以转化成二叉树 BT,则二叉树 BT 中一定没有右子树。 ( )8.线性表的顺序存储结构比链式存储结构更好。 ( ) 9.中序遍历二叉排序树可以得到一个有序的序列。 ( )10.快速排序是排序算法中平均性能最好的一种排序。 ( ) 三、填空题三、填空题(30 分分)1.for(i=1,t=1,s=0;i<=n;i++) {t=t*i;s=s+t;}的时间复杂度为_________。2.设指针变量 p 指向单链表中结点 A,指针变量 s 指向被插入的新结点 X,则进行插入操作的语句序列为__________________________(设结点的指针域为 next) 。3.设有向图 G 的二元组形式表示为 G =(D,R) ,D={1,2,3,4,5},R={r},r={<1,2>,<2,4>,<4,5>,<1,3>,<3,2>,<3,5>},则给出该图的一种拓扑排序序列__________。4.设无向图 G 中有 n 个顶点,则该无向图中每个顶点的度数最多是_________。5.设二叉树中度数为 0 的结点数为 50,度数为 1 的结点数为 30,则该二叉树中总共有_______个结点数。6.设 F 和 R 分别表示顺序循环队列的头指针和尾指针,则判断该循环队列为空的条件为_____________________。7.设二叉树中结点的两个指针域分别为 lchild 和 rchild,则判断指针变量 p 所指向的结点为叶子结点的条件是_____________________________________________。8.简单选择排序和直接插入排序算法的平均时间复杂度为___________。9.快速排序算法的空间复杂度平均情况下为__________,最坏的情况下为__________。10.散列表中解决冲突的两种方法是_____________和_____________。 四、算法设计题四、算法设计题(20 分分)1.1. 设计在顺序有序表中实现二分查找的算法。2.2. 设计判断二叉树是否为二叉排序树的算法。3.3. 在链式存储结构上设计直接插入排序算法 数据结构试卷(六)参考答案数据结构试卷(六)参考答案 一、选择题一、选择题1.D2.A3.A4.A5.D6.D7.B8.A9.C10.B11.C12.A13.B14.D15.B 二、判断题二、判断题1.错2.对3.对4.对5.错6.错7.对8.错9.对10.对 三、填空题三、填空题1.1. O(n)2.2. s->next=p->next; p->next=s3.3. (1,3,2,4,5)4.4. n-15.5. 1296.6. F==R7.7. p->lchild==0&&p->rchild==08.8. O(n2)9.9. O(nlog2n), O(n)10. 10. 开放定址法,链地址法 四、算法设计题四、算法设计题1.1. 设计在顺序有序表中实现二分查找的算法。struct record {int key; int others;};int bisearch(struct record r[ ], int k){ int low=0,mid,high=n-1; while(low<=high){ mid=(low+high)/2; if(r[mid].key==k) return(mid+1); else if(r[mid].key>k) high=mid-1; else low=mid+1; } return(0);}2.2. 设计判断二叉树是否为二叉排序树的算法。int minnum=-32768,flag=1;typedef struct node{int key; struct node *lchild,*rchild;}bitree;void inorder(bitree *bt){ if (bt!=0) {inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key;inorder(bt->rchild);}}3.3. 在链式存储结构上设计直接插入排序算法void straightinsertsort(lklist *&head){ lklist *s,*p,*q; int t; if (head==0 || head->next==0) return; else for(q=head,p=head->next;p!=0;p=q->next) { for(s=head;s!=q->next;s=s->next) if (s->data>p->data) break; if(s==q->next)q=p;else{q->next=p->next; p->next=s->next; s->next=p; t=p->data;p->data=s->data;s->data=t;} }} 数据结构试卷(七)数据结构试卷(七) 一、选择题一、选择题(30 分分)1.设某无向图有 n 个顶点,则该无向图的邻接表中有( )个表头结点。(A) 2n(B) n(C) n/2(D) n(n-1)2.设无向图 G 中有 n 个顶点,则该无向图的最小生成树上有( )条边。(A) n(B) n-1(C) 2n(D) 2n-13.设一组初始记录关键字序列为(60,80,55,40,42,85),则以第一个关键字 45 为基准而得到的一趟快速排序结果是( ) 。(A) 40,42,60,55,80,85(B) 42,45,55,60,85,80(C) 42,40,55,60,80,85(D) 42,40,60,85,55,804. ( )二叉排序树可以得到一个从小到大的有序序列。(A) 先序遍历(B) 中序遍历(C) 后序遍历(D) 层次遍历5.设按照从上到下、从左到右的顺序从 1 开始对完全二叉树进行顺序编号,则编号为 i 结点的左孩子结点的编号为( ) 。(A) 2i+1(B) 2i(C) i/2(D) 2i-16.程序段 s=i=0;do {i=i+1; s=s+i;}while(i<=n);的时间复杂度为( ) 。(A) O(n)(B) O(nlog2n)(C) O(n2)(D) O(n3/2)7.设带有头结点的单向循环链表的头指针变量为 head,则其判空条件是( ) 。(A) head==0(B) head->next==0(C) head->next==head(D) head!=08.设某棵二叉树的高度为 10,则该二叉树上叶子结点最多有( ) 。(A) 20(B) 256(C) 512(D) 10249.设一组初始记录关键字序列为(13,18,24,35,47,50,62,83,90,115,134),则利用二分法查找关键字 90 需要比较的关键字个数为( ) 。(A) 1(B) 2(C) 3(D) 410.设指针变量 top 指向当前链式栈的栈顶,则删除栈顶元素的操作序列为( ) 。(A) top=top+1;(B) top=top-1;(C) top->next=top;(D) top=top->next; 二、判断题二、判断题(20 分分)1.不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑“溢出”情况。 ( )2.当向二叉排序树中插入一个结点,则该结点一定成为叶子结点。 ( )3.设某堆中有 n 个结点,则在该堆中插入一个新结点的时间复杂度为 O(log2n)。 ( )4.完全二叉树中的叶子结点只可能在最后两层中出现。 ( )5.哈夫曼树中没有度数为 1 的结点。 ( )6.对连通图进行深度优先遍历可以访问到该图中的所有顶点。 ( )7.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。 ( )8.由树转化成二叉树,该二叉树的右子树不一定为空。 ( )9.线性表中的所有元素都有一个前驱元素和后继元素。 ( )10.带权无向图的最小生成树是唯一的。 ( ) 三、填空题三、填空题(30 分分)1.1. 设指针变量 p 指向双向链表中的结点 A,指针变量 s 指向被插入的结点 X,则在结点 A 的后面插入结点 X 的操作序列为_________=p;s->right=p->right;__________=s; p->right->left=s;(设结点中的两个指针域分别为 left 和right) 。2.2. 设完全有向图中有 n 个顶点,则该完全有向图中共有________条有向条;设完全无向图中有 n 个顶点,则该完全无向图中共有________条无向边。3.3. 设关键字序列为(Kl,K2,…,Kn),则用筛选法建初始堆必须从第______个元素开始进行筛选。4.4. 解决散列表冲突的两种方法是________________和__________________。 5.5. 设一棵三叉树中有 50 个度数为 0 的结点,21 个度数为 2 的结点,则该二叉树中度数为 3 的结点数有______个。6.6. 高度为 h 的完全二叉树中最少有________个结点,最多有________个结点。7.7. 设有一组初始关键字序列为(24,35,12,27,18,26),则第 3 趟直接插入排序结束后的结果的是__________________________________。8.8. 设有一组初始关键字序列为(24,35,12,27,18,26),则第 3 趟简单选择排序结束后的结果的是__________________________________。9.9. 设一棵二叉树的前序序列为 ABC,则有______________种不同的二叉树可以得到这种序列。10. 10. 下面程序段的功能是实现一趟快速排序,请在下划线处填上正确的语句。struct record {int key;datatype others;};void quickpass(struct record r[], int s, int t, int &i){ int j=t; struct record x=r[s]; i=s; while(i<j){ while (i<j && r[j].key>x.key) j=j-1; if (i<j) {r[i]=r[j];i=i+1;} while (____________________) i=i+1; if (i<j) {r[j]=r[i];j=j-1;} } _________________;} 四、算法设计题四、算法设计题(20 分分)1.1. 设计在链式结构上实现简单选择排序算法。2.2. 设计在顺序存储结构上实现求子串算法。3.3. 设计求结点在二叉排序树中层次的算法。 数据结构试卷(七)数据结构试卷(七) 一、选择题一、选择题1.B2.B3.C4.B5.B6.A7.C8.C9.B10.D 二、判断题二、判断题1.对2.对3.对4.对5.对6.对7.对8.错9.错10.错 三、填空题三、填空题1.1. s->left=p,p->right2.2. n(n-1),n(n-1)/23.3. n/24.4. 开放定址法,链地址法5.5. 146.6. 2h-1,2h-17.7. (12,24,35,27,18,26)8.8. (12,18,24,27,35,26)9.9. 510. 10. i<j && r[i].key<x.key,r[i]=x 四、算法设计题四、算法设计题1.1. 设计在链式结构上实现简单选择排序算法。void simpleselectsorlklist(lklist *&head){ lklist *p,*q,*s; int min,t; if(head==0 ||head->next==0) return; for(q=head; q!=0;q=q->next) { min=q->data; s=q; for(p=q->next; p!=0;p=p->next) if(min>p->data){min=p->data; s=p;} if(s!=q){t=s->data; s->data=q->data; q->data=t;} }}2.2. 设计在顺序存储结构上实现求子串算法。void substring(char s[ ], long start, long count, char t[ ]){ long i,j,length=strlen(s); if (start<1 || start>length) printf("The copy position is wrong"); else if (start+count-1>length) printf("Too characters to be copied");else { for(i=start-1,j=0; i<start+count-1;i++,j++) t[j]=s[i]; t[j]= '\0';}}3.3. 设计求结点在二叉排序树中层次的算法。int lev=0;typedef struct node{int key; struct node *lchild,*rchild;}bitree;void level(bitree *bt,int x){ if (bt!=0){lev++; if (bt->key==x) return; else if (bt->key>x) level(bt->lchild,x); else level(bt->rchild,x);}} 数据结构试卷(八)数据结构试卷(八) 一、选择题一、选择题(30 分分)1.1. 字符串的长度是指( ) 。(A) 串中不同字符的个数(B) 串中不同字母的个数(C) 串中所含字符的个数(D) 串中不同数字的个数2.2. 建立一个长度为 n 的有序单链表的时间复杂度为( )(A) O(n)(B) O(1)(C) O(n2)(D) O(log2n)3.3. 两个字符串相等的充要条件是( ) 。(A) 两个字符串的长度相等(B) 两个字符串中对应位置上的字符相等(C) 同时具备(A)和(B)两个条件(D) 以上答案都不对4.4. 设某散列表的长度为 100,散列函数 H(k)=k % P,则 P 通常情况下最好选择( ) 。(A) 99(B) 97(C) 91(D) 935.5. 在二叉排序树中插入一个关键字值的平均时间复杂度为( ) 。(A) O(n)(B) O(1og2n)(C) O(nlog2n)(D) O(n2)6.6. 设一个顺序有序表 A[1:14]中有 14 个元素,则采用二分法查找元素 A[4]的过程中比较元素的顺序为( )。(A) A[1],A[2],A[3],A[4](B) A[1],A[14],A[7],A[4](C) A[7],A[3],A[5],A[4](D) A[7],A[5] ,A[3],A[4]7.7. 设一棵完全二叉树中有 65 个结点,则该完全二叉树的深度为( ) 。(A) 8(B) 7(C) 6(D) 58.8. 设一棵三叉树中有 2 个度数为 1 的结点,2 个度数为 2 的结点,2 个度数为 3 的结点,则该三叉链权中有( )个度数为 0 的结点。(A) 5(B) 6(C) 7(D) 89.9. 设无向图 G 中的边的集合 E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点 a 出发进行深度优先遍历可以得到的一种顶点序列为( ) 。(A) aedfcb(B) acfebd(C) aebcfd(D) aedfbc10. 10. 队列是一种( )的线性表。(A) 先进先出(B) 先进后出(C) 只能插入(D) 只能删除 二、判断题二、判断题(20 分分)1.1. 如果两个关键字的值不等但哈希函数值相等,则称这两个关键字为同义词。 ( )2.2. 设初始记录关键字基本有序,则快速排序算法的时间复杂度为 O(nlog2n)。 ( )3.3. 分块查找的基本思想是首先在索引表中进行查找,以便确定给定的关键字可能存在的块号,然后再在相应的块内进行顺序查找。 ( )4.4. 二维数组和多维数组均不是特殊的线性结构。 ( )5.5. 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。 ( )6.6. 如果某个有向图的邻接表中第 i 条单链表为空,则第 i 个顶点的出度为零。 ( )7.7. 非空的双向循环链表中任何结点的前驱指针均不为空。 ( )8.8. 不论线性表采用顺序存储结构还是链式存储结构,删除值为 X 的结点的时间复杂度均为 O(n)。 ( )9.9. 图的深度优先遍历算法中需要设置一个标志数组,以便区分图中的每个顶点是否被访问过。 ( )10. 10. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非 0 元素。 ( ) 三、填空题三、填空题(30 分分)1. 1. 设一组初始记录关键字序列为(49,38,65,97,76,13,27,50),则以 d=4 为增量的一趟希尔排序结束后的结果为_____________________________。 2. 2. 下面程序段的功能是实现在二叉排序树中插入一个新结点,请在下划线处填上正确的内容。typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;void bstinsert(bitree *&t,int k){if (t==0 ) {____________________________;t->data=k;t->lchild=t->rchild=0;}else if (t->data>k) bstinsert(t->lchild,k);else__________________________;}3. 3. 设指针变量 p 指向单链表中结点 A,指针变量 s 指向被插入的结点 X,则在结点A 的后面插入结点 X 需要执行的语句序列:s->next=p->next; _________________;。4. 4. 设指针变量 head 指向双向链表中的头结点,指针变量 p 指向双向链表中的第一个结点,则指针变量 p 和指针变量 head 之间的关系是 p=_________和head=__________(设结点中的两个指针域分别为 llink 和 rlink) 。5. 5. 设某棵二叉树的中序遍历序列为 ABCD,后序遍历序列为 BADC,则其前序遍历序列为__________。6. 6. 完全二叉树中第 5 层上最少有__________个结点,最多有_________个结点。7. 7. 设有向图中不存在有向边<Vi,Vj>,则其对应的邻接矩阵 A 中的数组元素 A[i][j]的值等于____________。8. 8. 设一组初始记录关键字序列为(49,38,65,97,76,13,27,50),则第 4 趟直接选择排序结束后的结果为_____________________________。9. 9. 设连通图 G 中有 n 个顶点 e 条边,则对应的最小生成树上有___________条边。10.10. 设有一组初始记录关键字序列为(50,16,23,68,94,70,73),则将它们调整成初始堆只需把 16 与___________相互交换即可。 四、算法设计题四、算法设计题(20 分分)1.1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。2.2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。 数据结构试卷(八)参考答案数据结构试卷(八)参考答案 一、选择题一、选择题1.C2.C3.C4.B5.B6.C7.B8.C9.A10.A 二、判断题二、判断题1.对2.错3.对4.错5.错6.对7.对8.对9.对10.对 三、填空题三、填空题1.1. (49,13,27,50,76,38,65,97)2.2. t=(bitree *)malloc(sizeof(bitree)),bstinsert(t->rchild,k)3.3. p->next=s4.4. head->rlink,p->llink5.5. CABD6.6. 1,167.7. 08.8. (13,27,38,50,76,49,65,97)9.9. n-110. 10. 50 四、算法设计题四、算法设计题1.1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。void countnode(bitree *bt,int &count){ if(bt!=0) {count++; countnode(bt->lchild,count); countnode(bt->rchild,count);}}2.2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix;typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode;typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode;void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]){int i,j; glinklistnode *p;for(i=0;i<=n-1;i++) g2[i].firstarc=0;for(i=0;i<=n-1;i++) for(j=0;j<=n-1;j++)if (g1.edge[i][j]==1){p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j;p->nextarc=g[i].firstarc; g[i].firstarc=p;p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i;p->nextarc=g[j].firstarc; g[j].firstarc=p;}} 数据结构试卷(九)数据结构试卷(九) 一、选择题一、选择题(30 分分)1.下列程序段的时间复杂度为( ) 。for(i=0; i<m; i++) for(j=0; j<t; j++) c[i][j]=0;for(i=0; i<m; i++) for(j=0; j<t; j++) for(k=0; k<n; k++) c[i][j]=c[i][j]+a[i][k]*b[k][j];(A) O(m*n*t)(B) O(m+n+t)(C) O(m+n*t)(D) O(m*t+n)2.设顺序线性表中有 n 个数据元素,则删除表中第 i 个元素需要移动( )个元素。(A) n-i(B) n+l -i(C) n-1-i(D) i3.设 F 是由 T1、T2 和 T3 三棵树组成的森林,与 F 对应的二叉树为 B,T1、T2 和 T3 的结点数分别为 N1、N2 和 N3,则二叉树 B 的根结点的左子树的结点数为( ) 。 (A) N1-1(B) N2-1(C) N2+N3(D) N1+N34.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为( ) 。 (A) O(n)(B) O(nlog2n)(C) O(n2)(D) O(1og2n)5.设指针变量 p 指向双向链表中结点 A,指针变量 s 指向被插入的结点 X,则在结点 A的后面插入结点 X 的操作序列为( ) 。(A) p->right=s; s->left=p; p->right->left=s; s->right=p->right;(B) s->left=p;s->right=p->right;p->right=s; p->right->left=s;(C) p->right=s; p->right->left=s; s->left=p; s->right=p->right;(D) s->left=p;s->right=p->right;p->right->left=s; p->right=s;6.下列各种排序算法中平均时间复杂度为 O(n2)是( ) 。(A) 快速排序(B) 堆排序(C) 归并排序(D) 冒泡排序7.设输入序列 1、2、3、…、n 经过栈作用后,输出序列中的第一个元素是 n,则输出序列中的第 i 个输出元素是( ) 。(A) n-i(B) n-1-i(C) n+l -i(D) 不能确定8.设散列表中有 m 个存储单元,散列函数 H(key)= key % p,则 p 最好选择( ) 。(A) 小于等于 m 的最大奇数(B) 小于等于 m 的最大素数(C) 小于等于 m 的最大偶数(D) 小于等于 m 的最大合数9.设在一棵度数为 3 的树中,度数为 3 的结点数有 2 个,度数为 2 的结点数有 1 个,度数为 1 的结点数有 2 个,那么度数为 0 的结点数有( )个。(A) 4(B) 5(C) 6(D) 710.设完全无向图中有 n 个顶点,则该完全无向图中有( )条边。 (A) n(n-1)/2(B) n(n-1)(C) n(n+1)/2(D) (n-1)/211.设顺序表的长度为 n,则顺序查找的平均比较次数为( ) 。(A) n(B) n/2(C) (n+1)/2(D) (n-1)/212.设有序表中的元素为(13,18,24,35,47,50,62),则在其中利用二分法查找值为 24的元素需要经过( )次比较。(A) 1(B) 2(C) 3(D) 413.设顺序线性表的长度为 30,分成 5 块,每块 6 个元素,如果采用分块查找,则其平均查找长度为( ) 。(A) 6(B) 11(C) 5(D) 6.514.设有向无环图 G 中的有向边集合 E={<1,2>,<2,3>,<3,4>,<1,4>},则下列属于该有向图 G 的一种拓扑排序序列的是( ) 。(A) 1,2,3,4(B) 2,3,4,1(C) 1,4,2,3(D) 1,2,4,315.设有一组初始记录关键字序列为(34,76,45,18,26,54,92),则由这组记录关键字生成的二叉排序树的深度为( ) 。(A) 4(B) 5(C) 6(D) 7二、填空题二、填空题(30 分分)1.1. 设指针 p 指向单链表中结点 A,指针 s 指向被插入的结点 X,则在结点 A 的前面插入结点 X 时的操作序列为:1) s->next=___________;2) p->next=s;3) t=p->data; 4) p->data=___________;5) s->data=t;2.2. 设某棵完全二叉树中有 100 个结点,则该二叉树中有______________个叶子结点。3.3. 设某顺序循环队列中有 m 个元素,且规定队头指针 F 指向队头元素的前一个位置,队尾指针 R 指向队尾元素的当前位置,则该循环队列中最多存储_______队列元素。4.4. 对一组初始关键字序列(40,50,95,20,15,70,60,45,10)进行冒泡排序,则第一趟需要进行相邻记录的比较的次数为__________,在整个排序过程中最多需要进行__________趟排序才可以完成。5.5. 在堆排序和快速排序中,如果从平均情况下排序的速度最快的角度来考虑应最好选择_________排序,如果从节省存储空间的角度来考虑则最好选择________排序。6.6. 设一组初始记录关键字序列为(20,12,42,31,18,14,28),则根据这些记录关键字构造的二叉排序树的平均查找长度是_______________________________。7.7. 设一棵二叉树的中序遍历序列为 BDCA,后序遍历序列为 DBAC,则这棵二叉树的前序序列为____________________。8.8. 设用于通信的电文仅由 8 个字母组成,字母在电文中出现的频率分别为7、19、2、6、32、3、21、10,根据这些频率作为权值构造哈夫曼树,则这棵哈夫曼树的高度为________________。9.9. 设一组记录关键字序列为(80,70,33,65,24,56,48),则用筛选法建成的初始堆为_______________________。10. 10. 设无向图 G(如右图所示) ,则其最小生成树上所有边的权值之和为_________________。 三、判断题三、判断题(20 分分)1. 1. 有向图的邻接表和逆邻接表中表结点的个数不一定相等。( )2. 2. 对链表进行插入和删除操作时不必移动链表中结点。( )3. 3. 子串“ABC”在主串“AABCABCD”中的位置为 2。( )4. 4. 若一个叶子结点是某二叉树的中序遍历序列的最后一个结点,则它必是该二叉树的先序遍历序列中的最后一个结点。( )5. 5. 希尔排序算法的时间复杂度为 O(n2)。( )6. 6. 用邻接矩阵作为图的存储结构时,则其所占用的存储空间与图中顶点数无关而与图中边数有关。( )7. 7. 中序遍历一棵二叉排序树可以得到一个有序的序列。( )8. 8. 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。( )9. 9. 顺序表查找指的是在顺序存储结构上进行查找。 ( )10.10.堆是完全二叉树,完全二叉树不一定是堆。 ( ) 五、算法设计题五、算法设计题(20 分分)1. 1. 设计计算二叉树中所有结点值之和的算法。2. 2. 设计将所有奇数移到所有偶数之前的算法。3. 3. 设计判断单链表中元素是否是递增的算法。 数据结构试卷(九)参考答案数据结构试卷(九)参考答案 一、选择题一、选择题1.A2.A3.A4.C5.D6.D7.C8.B9.C10.A11.C12.C13.D14.A15.A 二、填空题二、填空题1.1. p->next,s->data2.2. 503.3. m-14.4. 6,85.5. 快速,堆6.6. 19/77.7. CBDA8.8. 69.9. (24,65,33,80,70,56,48)10. 10. 8 三、判断题三、判断题1.错2.对3.对4.对5.错6.错7.对8.对9.错10.对四、算法设计题四、算法设计题1. 1. 设计计算二叉树中所有结点值之和的算法。void sum(bitree *bt,int &s){ if(bt!=0) {s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s);}}2. 2. 设计将所有奇数移到所有偶数之前的算法。void quickpass(int r[], int s, int t){ int i=s,j=t,x=r[s]; while(i<j){ while (i<j && r[j]%2==0) j=j-1; if (i<j) {r[i]=r[j];i=i+1;} while (i<j && r[i]%2==1) i=i+1; if (i<j) {r[j]=r[i];j=j-1;} } r[i]=x;}3. 3. 设计判断单链表中元素是否是递增的算法。int isriselk(lklist *head){if(head==0||head->next==0) return(1);elsefor(q=head,p=head->next; p!=0; q=p,p=p->next)if(q->data>p->data) return(0);return(1);} 数据结构试卷(十)数据结构试卷(十) 一、选择题一、选择题(24 分分)1.下列程序段的时间复杂度为( ) 。i=0,s=0; while (s<n) {s=s+i;i++;}(A) O(n1/2)(B) O(n1/3)(C) O(n)(D) O(n2)2.设某链表中最常用的操作是在链表的尾部插入或删除元素,则选用下列( )存储方式最节省运算时间。(A) 单向链表(B) 单向循环链表(C) 双向链表(D) 双向循环链表3.设指针 q 指向单链表中结点 A,指针 p 指向单链表中结点 A 的后继结点 B,指针 s 指向被插入的结点 X,则在结点 A 和结点 B 插入结点 X 的操作序列为( ) 。(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;4.设输入序列为 1、2、3、4、5、6,则通过栈的作用后可以得到的输出序列为( ) 。(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,35.设有一个 10 阶的下三角矩阵 A(包括对角线) ,按照从上到下、从左到右的顺序存储到连续的 55 个存储单元中,每个数组元素占 1 个字节的存储空间,则 A[5][4]地址与 A[0][0]的地址之差为( ) 。(A) 10(B) 19(C) 28(D) 556.设一棵 m 叉树中有 N1个度数为 1 的结点,N2个度数为 2 的结点,……,Nm 个度数为m 的结点,则该树中共有( )个叶子结点。(A) ???miiNi1) 1((B) ??miiN1(C) ??miiN2(D) ????miiNi2) 1(1 7. 二叉排序树中左子树上所有结点的值均( )根结点的值。(A) <(B) >(C) =(D) !=8. 设一组权值集合 W=(15,3,14,2,6,9,16,17),要求根据这些权值集合构造一棵哈夫曼树,则这棵哈夫曼树的带权路径长度为( ) 。(A) 129(B) 219(C) 189(D) 2299. 设有 n 个关键字具有相同的 Hash 函数值,则用线性探测法把这 n 个关键字映射到HASH 表中需要做( )次线性探测。(A) n2 (B) n(n+1)(C) n(n+1)/2(D) n(n-1)/210.设某棵二叉树中只有度数为 0 和度数为 2 的结点且度数为 0 的结点数为 n,则这棵二叉中共有( )个结点。(A) 2n(B) n+l(C) 2n-1(D) 2n+l 11.设一组初始记录关键字的长度为 8,则最多经过( )趟插入排序可以得到有序序列。(A) 6(B) 7(C) 8(D) 912.设一组初始记录关键字序列为(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 二、填空题二、填空题(48 分,其中最后两小题各分,其中最后两小题各 6 分分)1.1. 设需要对 5 个不同的记录关键字进行排序,则至少需要比较_____________次,至多需要比较_____________次。2.2. 快速排序算法的平均时间复杂度为____________,直接插入排序算法的平均时间复杂度为___________。 3.3. 设二叉排序树的高度为 h,则在该树中查找关键字 key 最多需要比较_________次。4.4. 设在长度为 20 的有序表中进行二分查找,则比较一次查找成功的结点数有_________个,比较两次查找成功有结点数有_________个。5.5. 设一棵 m 叉树脂的结点数为 n,用多重链表表示其存储结构,则该树中有_________个空指针域。6.6. 设指针变量 p 指向单链表中结点 A,则删除结点 A 的语句序列为:q=p->next;p->data=q->data;p->next=___________;feee(q);7.7. 数据结构从逻辑上划分为三种基本类型:___________、__________和___________。8.8. 设无向图 G 中有 n 个顶点 e 条边,则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为_________;用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_________。9.9. 设散列表的长度为 8,散列函数 H(k)=k % 7,用线性探测法解决冲突,则根据一组初始关键字序列(8,15,16,22,30,32)构造出的散列表的平均查找长度是________。10. 10. 设一组初始关键字序列为(38,65,97,76,13,27,10),则第 3 趟冒泡排序结束后的结果为_____________________。11. 11. 设一组初始关键字序列为(38,65,97,76,13,27,10),则第 3 趟简单选择排序后的结果为______________________。12. 12. 设有向图 G 中的有向边的集合E={<1,2>,<2,3>,<1,4>,<4,5>,<5,3>,<4,6>,<6,5>},则该图的一个拓扑序列为_________________________。13. 13. 下面程序段的功能是建立二叉树的算法,请在下划线处填上正确的内容。typedef struct node{int data;struct node *lchild;________________;}bitree;void createbitree(bitree *&bt){scanf(“%c”,&ch);if(ch=='#') ___________;else{ bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; ________;createbitree(bt->rchild);}}14. 14. 下面程序段的功能是利用从尾部插入的方法建立单链表的算法,请在下划线处填上正确的内容。typedef struct node {int data; struct node *next;} lklist; void lklistcreate(_____________ *&head ){ for (i=1;i<=n;i++){ p=(lklist *)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0;if(i==1)head=q=p;else {q->next=p;____________;}} } 三、算法设计题三、算法设计题(22 分分)1. 1. 设计在链式存储结构上合并排序的算法。2. 2. 设计在二叉排序树上查找结点 X 的算法。3. 3. 设关键字序列(k1,k2,…,kn-1)是堆,设计算法将关键字序列(k1,k2,…,kn-1,x)调整为堆。 数据结构试卷(十)参考答案数据结构试卷(十)参考答案 一、选择题一、选择题1.A2.D3.B4.B5.B6.D 7.A8.D9.D10.C11.B12.D 二、填空题二、填空题1.1. 4,102.2. O(nlog2n),O(n2)3.3. n4.4. 1,25.5. n(m-1)+16.6. q->next7.7. 线性结构,树型结构,图型结构8.8. O(n2), O(n+e)9.9. 8/310. 10. (38,13,27,10,65,76,97)11. 11. (10,13,27,76,65,97,38)12. 12. 12465313. 13. struct node *rchild,bt=0,createbitree(bt->lchild)14. 14. lklist,q=p 三、算法设计题三、算法设计题1.1. 设计在链式存储结构上合并排序的算法。void mergelklist(lklist *ha,lklist *hb,lklist *&hc){ lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->data<hb->data){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;} else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;} if(ha==0) s->next=hb; else s->next=ha;}2.2. 设计在二叉排序树上查找结点 X 的算法。bitree *bstsearch1(bitree *t, int key){ bitree *p=t; while(p!=0) if (p->key==key) return(p);else if (p->key>key)p=p->lchild; else p=p->rchild; return(0);}3.3. 设关键字序列(k1,k2,…,kn-1)是堆,设计算法将关键字序列(k1,k2,…,kn-1,x)调整为堆。void adjustheap(int r[ ],int n){ int j=n,i=j/2,temp=r[j-1]; while (i>=1) if (temp>=r[i-1])break; else{r[j-1]=r[i-1]; j=i; i=i/2;} r[j-1]=temp;}
关 键 词:
算法 数据结构 期末考试 试卷
 天天文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:算法与数据结构期末考试试卷[
链接地址: https://www.wenku365.com/p-18760069.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给天天文库发消息,QQ:1290478887 - 联系我们

本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】。本站是网络服务平台方,若您的权利被侵害,侵权客服QQ:1290478887 欢迎举报。

1290478887@qq.com 2017-2027 https://www.wenku365.com 网站版权所有

粤ICP备19057495号 

收起
展开