《数据结构试题及答案(免费)》由会员分享，可在线阅读，更多相关《数据结构试题及答案(免费)（27页珍藏版）》请在金锄头文库上搜索。
1、一、单选题（每题2分，共20分）1. 1.对一个算法的评价，不包括如下（B ）方面的内容。A.健壮性和可读性B .并行性C.正确性 D.时空复杂度2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针 p指向的结 点，则执行（）。A. p-n ext=HL-n ext; HL-n ext=p;B. p-n ext=HL; HL=p;C. p- next=HL; p=HL;D. HL=p; p- next=HL;3. 3.对线性表，在下列哪种情况下应当采用链表表示？（）A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.4
2、. 一个栈的输入序列为1 2 3,则下列序列中不可能是栈的 输出序列的是 （C ）A. 2 3 1C. 3 1 2B. 3 2 1D. 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.元素
3、值D .非零元素个数9. 9.快速排序在最坏情况下的时间复杂度为（）。A. O（log2n）B. 0（nlog2n）C. 0（n）D . 0（n2）10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为（）。A. O（ n）B. O（1） C. O（log2 n）D. O（ n2）二、二、运算题（每题6分，共24分）1. 1.数据结构是指数据及其相互之间的 当结点之间存在M对N （ M : N ）的联系时，称这种结构为 。2. 2.队列的插入操作是在队列的 _尾 行，删除操作是在队列的首行。3. 3.当用长度为N的数组顺序存储一个栈时，假定用top=N表示栈空，则表示栈满的条件是top=
4、0（要超出才为满）。4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为 在表尾插入元素的时间复杂度为 。5. 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7，列下标j从0到3，贝维数组 W的数据元素共占用个字节。W中第6行的元素和第4列的元素共占用个字节。若按行顺序存放二维数组 W，其起始地址为100,则二维数组元素 W6，3的起始 地址为。6. 6. 广义表A= (a,(a,b),(a,b),c),则它的深度为它的长度为7. 7.二叉树是指度为2的 寸。一棵结点数为N的二叉树，其所有结点的度的总和是 。8. 8. 对一棵二叉搜索树进行中序遍历时，
5、得到的结点序列是一个。对一棵由算术表达式组成的二叉语法树进行后序遍历得到 的结点序列是该算术表达式的。9. 9.对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为个，其中个用于指向孩子，指针是空闲的。10. 10.若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A0中。其余类推，贝U A i 元素的左孩子元素为 ，右孩子元素为，双亲元素为11. 11.在线性表的散列存储中，处理冲突的常用方法有和 种。12. 12.当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用 卡序；当待排序的记录数较大，存储空间允许且要求排序 是
6、稳定时，宜米用 卡序。三、三、运算题(每题6分，共24分)1. 1.已知一个6 5稀疏矩阵如下所示，0000100000011 000000025000000700试：(1) (1)写出它的三元组线性表；(2) (2)给出三元组线性表的顺序存储表示。2. 2.设有一个输入数据的序列是 46, 25, 78, 62, 12, 80,试画出从空树起, 逐个输入各个数据而生成的二叉搜索树。3. 3.对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：(1) 从顶点出发进行深度优先搜索所得到的深度优先生成树；(2) 从顶点出发进行广度优先搜
7、索所得到的广度优先生成树；图64. 4.已知一个图的顶点集V和边集E分别为:V=1,2,3,4,5,6,7;E=,v3,2,v3,6,v4,3, ,J若存储它采用邻接表，并且每个顶 点邻接表中的边结点都是按照终点序 号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列四、四、阅读算法(每题7分，共14分)1. 1.int Prime(i nt n)int i=1;int x=(i nt) sqrt (n);while (+ix) retur n 1;else return 0;(1) (1)指出该算法的功能；(2) (2)该算法的时间复杂度是多少？2. 2.
8、写出下述算法的功能：void AJ(adjlist GL, int i, int n)Queue Q;Ini tQueue(Q); coutvvivv;visitedi=true;QInsert(Q,i);while(!QueueEmpty(Q) int k=QDelete(Q); edgenode* p=GLk; while(p!=NULL)int j=p-adjvex;if(!visitedj)coutjnext;五、 五、 算法填空(共 8 分) 如下为二分查找的非递归算法，试将其填写完整。 Int Binsch(ElemType A ,int n,KeyType K) int low=
9、0; int high=n-1; while (low=high) int mid=；if (K=Amid.key) return mid;/查找成功，返回元素的下标else if (Kmid.key) ; / 在左子表上 继续查找 else ; / 在右子表上继续查找return -1;/查找失败，返回 -1六、六、编写算法（共8分）HL是单链表的头指针，试写出删除头结点的算法ElemType DeleFro nt（LNode * & HL）、单选题（每题1.B2.A3.B4.C5.D6.B7.D、填空题（每空1.1.联系图（或图结构）2.2.尾 首3.3.top=04.4.O (1)O (
10、n)5.5.128441086.6.33参考答案2分，共20分）8.A9.D10.C1分，共26分）2.3.4.四、1.2.五、65515132-145-2515637图72.3.BFS:4.1.(2)2.如图8所示。DFS：7.8.9.10.11.12.7.8.9.10.11.12.有序有序序列2n n-12i+1开放定址法快速n-1后缀表达式（或逆波兰式）n+12i+2（i-1）/2链接法 归并运算题（每题6分，共24分）1.（2）(3分)1.12（1）三兀组线性表的顺序存储表示如图（1,5,1）,（3,2,-1）,（4,5,-2）,（5,1,5）,（6,3,7）7示。57（每题（1）判断
11、n是否是素数（或质数）O （ n功能为：五、拓朴排序为:四、43 6阅读算法2 17分，共14分）(low+high)/2六、六、ElemType DeleFro nt(LNode * & HL) if (HL=NULL) cerr空表 next;ElemType temp=p-data; delete p;return temp;第一部分 选择题(30分)一、项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的 四个选项中只有一个选项是符合题目要求的， 请将正确选项前的字母填在题 后的括号内。1 算法指的是()A .计算机程序B.解决问题的计算方法C.排序算法D .解决问题的有限
12、运算序列2.线性表采用链式存储时，结点的存储地址()A. 必须是不连续的B. 连续与否均可C. 必须是连续的D. 和头结点的存储地址相连续3. 将长度为n的单链表链接在长度为()A. O (1)B. O (n)4. 由两个栈共享一个向量空间的好处是:m的单链表之后的算法的时间复杂度为C. O (m)D. O (m+n)()A .减少存取时间，降低下溢发生的机率B. 节省存储空间，降低上溢发生的机率C. 减少存取时间，降低上溢发生的机率D. 节省存储空间，降低下溢发生的机率5 .设数组datam作为循环队列SQ的存储空间，front为队头指针，rear为队尾 指针，则执行出队操作后其头指针front值为()A. front=fro nt+1C. front=(front-1)%m6. 如下陈述中正确的是(A.串是一种特殊的线性表C.串中元素只能是字母B. front=(front+1)%(m-1) D . front=(front+1)%m)B.串的长度必须大于零D .空串就是空白串7. 若目标串的长度为n，模式串的长度为n/3，则执行模式匹配算法时，在最 坏情况下的时间复杂度是()A . O ( 3) B . O (n)C .
