算法及数据结构期末考试试卷.docx

《算法及数据结构期末考试试卷.docx》由会员分享，可在线阅读，更多相关《算法及数据结构期末考试试卷.docx（61页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、课程测试试题卷-以下为教师填写-I、命题院部： 数学与计算机科学学院 II、课程名称： 数据构造 III、测试学期：20 20 学年度第 学期IV、测试对象： 学院 专业 级 班V、问卷页数A4： 页VI、答卷页数A4： 页VII、考试方式： 闭卷 开卷、闭卷或课程小论文，请填写清楚VIII、问卷内容：请教师在出题时安排紧凑，填空题象征性留出一点空格，学生将所有答案做在答题纸上规定位置，并写清楚大题、小题题号一、 一、 单项选择题每题 2 分，共20分1. 1. 对一个算法评价，不包括如下B 方面内容。 A强健性和可读性 B并行性 C正确性 D时空复杂度2. 2. 在带有头结点单链表HL中，要

2、向表头插入一个由指针p指向结点，那么执行( A )。 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. 对线性表，在以下哪种情况下应当采用链表表示？( B ) A.经常需要随机地存取元素 B.经常需要进展插入和删除操作 C.表中元素需要占据一片连续存储空间 D.表中元素个数不变4. 4. 一个栈输入序列为1 2 3，那么以下序列中不可能是栈输出序列是( C ) A. 2 3 1B. 3 2 1 C. 3 1 2 D. 1 2 35. 5. AOV网是一种

3、D 。 A有向图 B无向图 C无向无环图 D有向无环图6. 6. 采用开放定址法处理散列表冲突时，其平均查找长度 B。A低于链接法处理冲突 B. 高于链接法处理冲突 C与链接法处理冲突一样 D高于二分查找7. 7. 假设需要利用形参直接访问实参时，应将形参变量说明为 D 参数。A值 B函数 C指针 D引用8. 8. 在稀疏矩阵带行指针向量链接存储中，每个单链表中结点都具有一样 A。A行号 B列号 C元素值 D非零元素个数9. 9. 快速排序在最坏情况下时间复杂度为 C。AO(log2n) BO(nlog2n) C0(n) D0(n2)10. 10. 从二叉搜索树中查找一个元素时，其时间复杂度大

4、致为( D )。 A. O(n) B. O(1) C. O(log2n) D. O(n2)二、 二、 运算题每题 6 分，共24分1. 1. 数据构造是指数据及其相互之间_。当结点之间存在M对NM：N联系时，称这种构造为_。2. 2. 队列插入操作是在队列_进展，删除操作是在队列_进展。3. 3. 当用长度为N数组顺序存储一个栈时，假定用top=N表示栈空，那么表示栈满条件是_。4. 4. 对于一个长度为n单链存储线性表，在表头插入元素时间复杂度为_，在表尾插入元素时间复杂度为_。5. 5. 设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ，那么二维数组W

5、数据元素共占用_个字节。W中第6 行元素和第4 列元素共占用_个字节。假设按行顺序存放二维数组W，其起始地址为100，那么二维数组元素W6，3起始地址为_。6. 6. 广义表A= (a,(a,b),(a,b),c),那么它深度为_，它长度为_。7. 7. 二叉树是指度为2_树。一棵结点数为N二叉树，其所有结点度总和是_。8. 8. 对一棵二叉搜索树进展中序遍历时，得到结点序列是一个_。对一棵由算术表达式组成二叉语法树进展后序遍历得到结点序列是该算术表达式_。9. 9. 对于一棵具有n个结点二叉树，用二叉链表存储时，其指针总数为_个，其中_个用于指向孩子，_个指针是空闲。10. 10. 假设对一

6、棵完全二叉树从0开场进展结点编号，并按此编号把它顺序存储到一维数组A中，即编号为0结点存储到A0中。其余类推，那么A i 元素左孩子元素为_,右孩子元素为_，双亲元素为_。11. 11. 在线性表散列存储中，处理冲突常用方法有_和_两种。12. 12. 当待排序记录数较大，排序码较随机且对稳定性不作要求时，宜采用_排序；当待排序记录数较大，存储空间允许且要求排序是稳定时，宜采用_排序。三、 三、 运算题每题6分，共24分1. 1. 一个65稀疏矩阵如下所示，试：（1） 1 写出它三元组线性表；（2） 2 给出三元组线性表顺序存储表示。2. 2. 设有一个输入数据序列是 46, 25, 78,

7、62, 12, 80 , 试画出从空树起，逐个输入各个数据而生成二叉搜索树。3. 3. 对于图6所示有向图假设存储它采用邻接表，并且每个顶点邻接表中边结点都是按照终点序号从小到大次序链接，试写出：(1) 从顶点出发进展深度优先搜索所得到深度优先生成树；(2) 从顶点出发进展广度优先搜索所得到广度优先生成树； 4. 4. 一个图顶点集V和边集E分别为： 图6 V=1,2,3,4,5,6,7;E=,;假设存储它采用邻接表，并且每个顶点邻接表中边结点都是按照终点序号从小到大次序链接，按主教材中介绍拓朴排序算法进展排序，试给出得到拓朴排序序列。图8四、 四、 阅读算法每题7分，共14分1. 1. in

8、t Prime(int n) int i=1; int x=(int) sqrt(n); while (+ix) return 1; else return 0; 1. (1) 指出该算法功能；1.2. (1)答案： 判断n是否是素数或质数 (2) 该算法时间复杂度是多少？答案：O2. 2. 写出下述算法功能： void AJ(adjlist GL, int i, int n) Queue Q; InitQueue(Q); coutiadjvex; if(!visitedj) coutjnext; 3. 2. 功能为：从初始点vi出发广度优先搜索由邻接表GL所表示图。五、 五、 算法填空共8分

9、如下为二分查找非递归算法，试将其填写完整。Int Binsch(ElemType A ,int n,KeyType K)int low=0;int high=n-1;while (low=high)int mid=_(low+high)/2 _；if (K=Amid.key) return mid; /查找成功，返回元素下标 else if (Kmid.key) _high=mid-1_; /在左子表上继续查找 else _ low=mid+1 _; /在右子表上继续查找return -1; /查找失败，返回-1六、 六、 编写算法共8分HL是单链表头指针，试写出删除头结点算法。ElemTyp

10、e DeleFront(LNode * & HL)答案：ElemType DeleFront(LNode * & HL)if (HL=NULL) cerr空表next;ElemType temp=p-data;delete p;return temp; 参考答案一、 一、 单项选择题每题2分，共20分二、 二、 填空题每空1分，共26分1. 1. 联系 图或图构造2. 2. 尾 首3. 3. top=04. 4. O1 On5. 5. 128 44 1086. 6. 3 3 7. 7. 65515132-145-2515637 图7有序 n-18. 8. 有序序列 后缀表达式或逆波兰式9. 9

11、. 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如图8所示。3. 3. DFS： BFS： 4. 4. 拓朴排序为： 4 3 6 5 7 2 1 四、 四、 阅读算法每题7分，共14分4. 1. (1) 判断n是否是素数或质数 2O5. 2. 功能为：从初始点vi出发广度优先搜索由邻接表GL所表示图。五、 五、 算

12、法填空8 分 (low+high)/2 high=mid-1 low=mid+1 六、 六、 编写算法8分ElemType DeleFront(LNode * & HL)if (HL=NULL) cerr空表next;ElemType temp=p-data;delete p;return temp; 吉首大学试题库课程测试试题 卷-以下为教师填写-I、命题院部： 数学与计算机科学学院 II、课程名称： 数据构造 III、测试学期：20 20 学年度第 学期IV、测试对象： 学院 专业 级 班V、问卷页数A4： 页VI、答卷页数A4： 页VII、考试方式： 闭卷 开卷、闭卷或课程小论文，请填写

13、清楚VIII、问卷内容：请教师在出题时安排紧凑，填空题象征性留出一点空格，学生将所有答案做在答题纸上规定位置，并写清楚大题、小题题号一、 一、 单项选择题每题 2 分，共20分1. 1. 栈和队列共同特点是( )。A.只允许在端点处插入和删除元素B.都是先进后出 C.都是先进先出D.没有共同点 2. 2. 用链接方式存储队列，在进展插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改3. 3. 以下数据构造中哪一个是非线性构造？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树4. 4. 设有一个二维数组Amn，假设A00存放位

14、置在644(10)，A22存放位置在676(10)，每个元素占一个空间，问A33(10)存放在什么位置？脚注(10)表示用10进制表示。 A688 B678 C692 D6965. 5. 树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系数据 D.元素之间无联系数据6. 6. 二叉树第k层结点数最多为( ). A2k-1 B.2K+1 C.2K-1 D. 2k-17. 7. 假设有18个元素有序表存放在一维数组A19中，第一个元素放A1中，现进展二分查找，那么查找A3比拟序列下标依次为( ) A. 1，2，3B. 9，5，2，3 C. 9，5，3D. 9

15、，4，2，38. 8. 对n个记录文件进展快速排序，所需要辅助存储空间大致为 A. O1 B. On C. O1og2n D. On29. 9. 对于线性表7，34，55，25，64，46，20，10进展散列存储时，假设选用HK=K %9作为散列函数，那么散列地址为1元素有 个， A1 B2 C3 D410. 10. 设有6个结点无向图，该图至少应有( )条边才能确保是一个连通图。二、 二、 填空题每空1分，共26分1. 1. 通常从四个方面评价算法质量：_、_、_和_。2. 2. 一个算法时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为_。3. 3. 假定一棵树广义表表示为

16、AC，DE，F，G，HI，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个顶点有向完全图中，包

17、含有_条边。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

18、6 7 data605078903440next35720412. 2. 图10请画出图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 m

19、ynote(LinkList L) /L是不带头结点单链表头指针 if(L&L-next) q=L；L=Lnext；p=L； S1： while(pnext) p=pnext； S2： pnext=q；qnext=NULL； return L； 请答复以下问题： 1说明语句S1功能； 2说明语句组S2功能； 3设链表表示线性表为a1,a2, ,an,写出算法执行后返回值所表示线性表。2. 2. void ABC(BTNode * BT) if BT ABC (BT-left); ABC (BT-right); coutdatadata) item=BST-data;/查找成功 return _

20、; else if(itemdata) return Find(_,item); else return Find(_,item); /if六、 六、 编写算法共8分统计出单链表HL中结点值等于给定值X结点数。 int CountX(LNode* HL,ElemType x)参考答案一、 一、 单项选择题每题2分，共20分二、 二、 填空题每空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

21、)/2 n(n-1)9. 9. 12，40 74 23,55，6310. 10. 增加111. 11. O(log2n) O(nlog2n)12. 12. 归并三、 三、 运算题每题6分，共24分1. 1. 线性表为：78，50，40，60，34，902. 2. 邻接矩阵： 邻接表如图11所示：图113. 3. 用克鲁斯卡尔算法得到最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204. 4. 见图124444422255285283452843图12四、 四、 阅读算法每题7分，共14分1. 1. 1查询链表尾结点2将第一个结点链接

22、到链表尾部，作为新尾结点 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; /CountX吉首大学试题库课程测试试题卷-以下为教师填写-I、命题院部： 数学与计算机科学学院 II、课程名

23、称： 数据构造 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、在一个单链表中,假设

24、q所指结点是p所指结点前驱结点,假设在q与p之间插入一个s所指结点,那么执行( )。 A slink=plink; plink=s; B plink=s; slink=q; C plink=slink; slink=p; D q link=s; slink =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、一种抽象数据类型包括_和_两

25、个局部。3、 3、在下面数组a中链接存储着一个线性表，表头指针为ao.next，那么该线性表为_。 a 0 1 2 3 4 5 6 7 8 60 56 42 38 74 25 4 3 7 6 2 0 1datanext4、 4、在以HL为表头指针带表头附加结点单链表和循环单链表中，判断链表为空条件分别为_和_。5、 5、用具有n个元素一维数组存储一个循环队列，那么其队首指针总是指向队首元素_，该循环队列最大长度为_。6、 6、当堆栈采用顺序存储构造时，栈顶元素值可用表示；当堆栈采用链接存储构造时，栈顶元素值可用_表示。7、 7、一棵高度为5二叉树中最少含有_个结点，最多含有_个结点；一棵高度为

26、5理想平衡树中，最少含有_个结点，最多含有_个结点。8、 8、在图邻接表中，每个结点被称为_，通常它包含三个域：一是_；二是_；三是_。9、 9、在一个索引文件索引表中，每个索引项包含对应记录_和_两项数据。10、 10、 假定一棵树广义表表示为ABC，DE，F，G，HI，J，那么树中所含结点数为_个，树深度为_,树度为_, 结点H双亲结点为_,孩子结点为_ 。11、 11、 在堆排序过程中，对任一分支结点进展筛运算时间复杂度为_,整个堆排序过程时间复杂度为_。12、 12、 在对m阶B_树插入元素过程中，每向一个结点插入一个索引项叶子结点中索引项为关键字和空指针后，假设该结点索引项数等于_个

27、，那么必须把它分裂为_个结点。三、 三、 运算题每题6分，共24分1、 1、一组记录排序码为46，79，56，38，40，80, 95，24，写出对其进展快速排序每一次划分结果。2、 2、一个线性表为B=12，23，45，57，20，03，78，31，15，36，设散列表为HT0.12，散列函数为Hkey= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功平均查找长度。3、 3、一棵二叉树前序遍历结果序列是ABECKFGHIJ，中序遍历结果是EBCDAFHIGJ，试写出这棵二叉树后序遍历结果。4、 4、一个图顶点集V各边集G如下：V = 0，1，2，3，4，5，

28、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 # include consst int stackmaxsize = 30;typedef int elemtype;struct stack elemtype stack stackmaxsize; int top;# include “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;该算