数据结构试卷

《数据结构试卷》由会员分享，可在线阅读，更多相关《数据结构试卷（12页珍藏版）》请在装配图网上搜索。

1、XXXX学年第二学期期末考试数据结构 试卷 A 卷考试方式：闭卷考试时间：120 分钟卷面总分：100 分请把答案写在答题纸上！ 一、单选题(本题共20 题，每题2 分，共40 分)()1.若线性表采用链式存储结构，要求内存中可用存储单元的地 址。A. 必须是连续的B.部分地址必须是连续的C. 一定是不连续的D.连续或不连续都可以级封 ()2.下列选项中不属于线性结构的是。年A”串B.栈C.图D.数组()3.线性表L在情况下适用于链式存储结构实现。A. 需经常修改L中的结点值B. L中含有大量的结点徑C.需不断对L进行插入删除线DL中结点 结构复杂名 姓允许进栈退栈操作交替进行，但()4. 若

2、元素 a,b,c,d,e,f 依次进栈，不允许连续三次进行退栈工作，则不可能得到的出栈序列是。A.d,c,e,b,f,a B.c,b,d,a,e,f C.b,c,a,e,f,d D.a,f,e,d,c,b()5循环队列存储在数组A0,m中，则入队时的操作为。号A. rear= (rear+1)mod(m+1)B. rear=(rear+1) mod (m-1)学C. rear=(rear+1) mod mD. rear= rear+1()6.串 “bababbaba” 的 nextval 为。A.010102101B.010104101C.010101011D.010114101)7若一棵二叉

3、树的前序遍历序列和后序遍历序列分别为 1,2,3,4和 4,3,2,1，则该二叉树的中序遍历序列不会是。A1,2,3,4B2,3,4,1 C3,2,4,1 D4,3,2,1)8已知一棵有 2019 个结点的树，其叶结点个数为 19，该树对应的二叉树中无右孩子的结点个数是。A19B20C2000D2001)9在一棵度为 4 的树 T 中，若有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1 的结点，则树T 的叶节点个数是。A41B82C113D122()10.图的DFS生成树的树高比BFS生成树的树高。A.大或相等 B.相等C.小或相等D.小)11.

4、 n 个顶点的连通图用邻接距阵表示时，该距阵至少有个非零元素。A.nB.2(n-1)C.n/2D.n2)12.对 19 个记录的有序表作折半查找，当查找失败时，至少需 要比较次关键字。A.3B.4 C.5 D. 6)13.设有一组记录的关键字为19，14，23，1，68，20，84，27，55，11，10，79，用链地址法构造散列表，散列函数为 H(key)=key MOD 13，散列地址为 1 的链中有个记录。A.1B. 2C. 3D. 4)14.下面关于折半查找叙述正确的是。A. 表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序，而且只能从小到大排列C. 表必须有序且表中

5、数据必须是整型，实型或字符型D. 表必须有序，且表只能以顺序方式存储)15.对 n 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为。业专名姓号学A. (n+1)/2B. n/2C. nD. (1+n)*n/2)16下列排序算法中，占用辅助空间最多的是。A.堆排序B.快速排序C.冒泡排序 D.插入排序)17直接插入排序在最好情况下的时间复杂度为。AO(n)BO(logn)CO(n*logn)DO(n2)厂茂：对序列15, 9, 7, 8, 20,-1, 4用希尔排序方法排序，经 一趟后序列变为15, -l, 4, 8, 20, 9, 7,则该次采用的增 量是。A.1B.2C.

6、 3)19下列四个序列中,哪一个是堆_75.65.30.15.25.45.20.1075.65.45.10.30.25.20.1575.45.65.30.15.25.20.1075.45.65.10.25.30.20.15情况下最不利于发挥其长处。D. 4ABCD)20快速排序方法在A.要排序的数据量太大 要排序的数据中含有玄多个相同值C. 要排序的数据个数为奇数D. 要排序的数据已基本有序二、填空题(本题共10空，每空2分，共20分)1. 在单链表L中，指针p所指结点有后继结点的条件是2. 带头结点的双循环链表L中只有一个元素结点的条件是3GetHead GetHeadGetTail(a,b

7、),(c,d)= 。假设以行序为主序存储二维数组 A=array1.100,1.100，设每个数据4.567元素占2个存储单元，基地址为0，则 LOC5,5=数据结构中评价算法的两个重要指标是空间复杂度和一棵具有 255 个结点的完全二叉树，它的深度为_用 5 个权值4, 5, 3, 2, 1构造的哈夫曼树的带权路径长度是8对于稀疏图，采用存储结构较省空间。9. 设散列表表长为11,散列函数是H（key）=key%ll,表中已有数据的关键字为15， 38， 61， 84共四个，现要将关键字为50的结点加到表中， 用线性探测再散列法解决冲突,则放入的位置是。10. 分别采用堆排序、快速排序、冒泡

8、排序和归并排序,对初态为有序的表,则最省时间的是 算法。三、分析求解题 （本题2 小题，共15 分）1. （8分）给定二叉树的中序遍历序列：GLDHBEIACJFK和后序遍历 序列：LGHDIEBJKFCA，完成如下任务。（1）画出这棵二叉树。（4 分）（2）写出这颗二叉树的前序遍历结果。（2分）（3）将这颗二叉树转换成对应的森林。（2分）（1）画出邻接表；（3分）（2）若从顶点 B 出发对该图进行遍历,在邻接表的基础上分别给出图的深度优先搜索顶点序列和广度优先搜索顶点序列；（4 分）名姓年业专号学四、算法题（本题 4小题，共 25 分）1.下面是用C+语言编写的对不带头结点的单链表进行就地逆

9、置的算 .法，该算运用L返回逆置后的链表的头指针，试在空缺处填入适当的语句。（每空2分，共3空，总计6分）void reverse（LinkList &L）p=NULL；q=L；while（q！=NULL）q-next=p；p=q；;暂存后继;待逆置结点void reverse(pointer h)pointer p,q; p=h-next; h-next=NULL; while(p！=NULL) q=p;p=p-next; /依次链接q-next=h-next; 将q所指结点链接到新链表中h-next=q; /头结点指向新链接的结点，也就会第一个结点/不带头结点的单链表的逆置运算void r

10、everse(LinkList &L)p=null;q=L;while(q!=null)L=L-next; /暂存下一个结点否则执行下一步时，就被覆盖了 找不到了q-next=p; q是带操作结点，p是上一个结点p=q; /将本结点设置为上一个结点q=L; /将暂存的结点设为待操作的结点L=p; 将第一个结点设置为L2.在下面Test函数中，S是一个栈，Push和Pop分别是入栈和出栈操 作，InitStack是初始化栈操作；Q是一个队列，EnQueue和DeQueue 分别是入队和出队操作；StackEmpty是判断栈是否为空，QueueEmpty 是判断队列是否为空。已知队列Q中从队头到队

11、尾依次有四个元素: 4,3,2,1,写出执行Test(Q)之后，队列Q中的元素从队头到队尾依次 是什么。(4分)void Test(Queue &Q)Stack S;int x;InitStack(S);while(!QueueEmpty(Q)DeQueue (Q,x); Push(S,x);while(!StackEmpty(S)Pop(S,x); EnQueue (Q,x);3. 已知一棵二叉树T如下图所示，该树已存储在计算机内存中，LChild指向左子树，RChild指向右子树。写出函数Fun(T)运行的输出结果。(5 分)ltypedef struct BiTNodechar data

12、;struct BiTNode *LChild, *RChild BiTNode;BiTNode *T;iit-Ftm(BiTNde *T )if (T!=NULL) coutvvT-data; Fun(T-RChid);:coutvvT-data;业密Fun(T-LChild);专return 0;： 封 级 年4、对于有向图，求其拓扑序列的步骤为：1) 在有向图中选一个没有前驱(即入度为零)的顶点并输出。2) 在图中删除该顶点及所有以它为尾的弧。3) 重复 1)和 2)，直至全部顶点输出，这时拓扑排序完成；否则，图 中存在环，拓扑排序失败。现有 n 个顶点的有向图，其中有向图在内存中用邻接

13、矩阵 array 表 示(如果存在弧vi, j,则arrayij=l,否则为0)、顶点号从0开始编号、 indegree 是有 n 个分量的一维数组，用来存放顶点的入度。下面是其拓 扑排序算法，试补充完整。(每空2分，共5空，总计10分) void TopologicalSort (int array , int n)for (i=0; ivn; i+)indegreei=(1);for(i=0; ivn; i+)for (j=0; jvn; j+)indegreei+=arrayji;InitStack(S);for (i=0; ivn; i+)if()push(S,i);count=;while (!StackEmpty(S)pop(S,i); couti; count+;for (k=0; kn; k+)if (arrayik=1)stack+top=kif ( !(-indegreek) )if()cout“ 图有回路 ”endl