2022年数据结构题集 .pdf

《2022年数据结构题集 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构题集 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构试卷二一、填空题：（共分）1、数据结构研究数据的结构。2、对算法从时间和空间两方面进行度量，分别称为分析。3、线性表是n 个元素的。4、线性表的存储结构有。5、栈和队列分别称为的线性表。6、二叉树第i 层上最多有个结点。7、一个二叉树中每个结点最多只有个孩子。8、Hash技术关键是两个方面。9、二叉排序树若左子树不空，则左子树上的所有结点值均它的根结点值。10、AOV一网以结点和有向边分别代表。二、单项选择题：（共分）1、下列各种结构的物理存储必须占用连续的存储空间的是-(a )(A)数组 (B)栈 (C)二叉树 (D)链表 2、由前根排序序列和中根排序序列(a )唯一确定一棵二叉树。

2、(A)能 (B)不能 (C)不一定。3、同一记录结构中的各数据项的类型(b )一致。(A)必须 (B)不必 (C)不能 (D)不可能。4、4 个元素进S栈的顺序是A,B,C,D,经运算 POP(S)后栈顶元素是-(c )(A)A (B)B (C)C (D)D 5、有 n 个顶点 e 条边的无向图G,它的邻接表中的表结点总数是-()(A)2n (B)n (C)2e (D)e 6、二维数组Amn按行序为主序存放在内存,每个数组元素占1 个存储单元 ,则元素 aij 的地址计算公式是:_(a)(A)loc(aij)=loc(a11)+(i-1)*m+(j-1)(B)loc(aij)=loc(a11)

3、+(j-1)*m+(i-1)(C)loc(aij)=loc(a11)+(i-1)*n+(j-1)(D)loc(aij)=loc(a11)+(j-1)*n+(i-1)7、连通图G中有 n 个顶点,G 的生成树是(a)连通子图.(A)包含 G的所有顶点 (B)包含 G的所有边 (C)不必包含G的所有顶点 (D)必须包含 G的所有顶点和所有的边 8、n=1000,要求最坏情况速度最快的排序方法为_()(A)快速排序 (B)起泡排序 (C)归并排序 (D)shell排序 9、在一个以h 为头的单循环链表中，p 指针指向链尾的条件是（a）a.p.next=h b.p.next=nil c.p.next.

4、next=h d.p.data=-1 10、下面关于求关键路径的说法不正确的是（c）a.求关键路径是以拓扑排序为基础的b.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同c.一个事件的最迟开始时间同以该事件为尾的弧的活动最迟开始时间相同与该活动的持续时间的和d.关键活动一定在关键路径上名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 4 页 -三、简答题：(共 40 分)、静态查找与动态查找的最大区别是什么?相应的查找方法有哪些？2、设 a,b,c,d,e,f六个字母出现的概率分别为7,19,2,6,32,3,写出为这六个字母设计huffman 编码并画出对应huff

5、man 树。、写出下列二叉树的前序，中序，后序遍历序列及对应的森林。A /B C /D E F /G 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 4 页 -、画出下列无向图的邻接表存储结构，并由邻接表写出广度优先搜索序列和深度优先搜索序列。A /|B-C D|/E、用快速排序方法对下列整数序列进行排序，写出中间及最后结果。89,27,52,90,15,28,100,72 四、设计或分析题：(共 20 分)、已知线性链表的头指针为S，每个结点含有数据域DATA和指针域 NEXT，写出使该链表倒排元素次序的算法。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 4 页 -2、有 n 个结点的完全二叉树存放在一维数组A1.n 中，试据此建立一棵二叉链表表示的二叉树，根由tree 指向。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 4 页 -