2022年数据结构试题及答案宣贯 .pdf

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

1、1 数据结构试卷（一）一、单选题（每题2 分，共 20 分）1.栈和队列的共同特点是( A )。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( ) A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组Am n，假设 A00 存放位置在644(10)，A22 存放位置在676(10)，每个元素占一个空间，问A33(10)存放在什么位置？脚注(10)表示用 10 进制表示。A688

2、 B678 C692 D696 5.树最适合用来表示( )。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k 层的结点数最多为( ). A2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有 18 个元素的有序表存放在一维数组A19 中，第一个元素放A1 中，现进行二分查找，则查找 A3的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对 n 个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.

3、对于线性表（ 7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9 作为散列函数，则散列地址为1 的元素有（）个，A1 B2 C3 D4 10. 设有 6 个结点的无向图，该图至少应有( )条边才能确保是一个连通图。A.5 B.6 C.7 D.8 二、填空题（每空1 分，共 26 分）1.通常从四个方面评价算法的质量：_ _、_ _、_和_。2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为_。3.假定一棵树的广义表表示为A（C，D（E，F，G） ，H（I，J） ） ，则树中所含的结点数为_个，树的深度为 _，树的度为 _。4.后

4、 缀 算 式9 2 3 +- 10 2 / - 的 值 为 _ 。 中 缀 算 式 （ 3+4X ） -2Y/3对 应 的 后 缀 算 式 为名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 34 页 - - - - - - - - - 2 _。5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中， n 个结点的二叉树共有_个指针域，其中有_个指针域是存放了地址，有_个指针是空指针。6.对于一个具有n 个顶点和 e条边的有向图

5、和无向图， 在其对应的邻接表中， 所含边结点分别有_n_个和 _个。7.AOV 网是一种 _的图。8.在一个具有n 个顶点的无向完全图中，包含有_条边，在一个具有n 个顶点的有向完全图中，包含有 _条边。9.假定一个线性表为(12,23,74,55,63,40)，若按 Key % 4 条件进行划分，使得同一余数的元素成为一个子表 ， 则 得 到 的 四 个 子 表 分 别 为 _ 、 _ 、_和_。10.向一棵 B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度_。11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_，整个堆排序过程的时间复杂度为_。12.在快速排

6、序、堆排序、归并排序中，_排序是稳定的。三、运算题（每题6 分，共 24 分）1.在如下数组A 中链接存储了一个线性表，表头指针为A 0.next ，试写出该线性表。A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 2.请画出图 10 的邻接矩阵和邻接表。3.已知一个图的顶点集V 和边集 E分别为：(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 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

7、,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。4.画出向小根堆中加入数据4, 2, 5, 8, 3 时，每加入一个数据后堆的变化。四、阅读算法（每题7 分，共 14 分）1.LinkList mynote(LinkList L) /L 是不带头结点的单链表的头指针if(L&L-next) q=L；L=L next；p=L；S1：while(p next) p=pnext；S2：pnext=q ；qnext=NULL ；图 10 名师资料总结 - - -精品资料欢迎下载 - - -

8、- - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 34 页 - - - - - - - - - 3 return L； 请回答下列问题：1.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3, ,an,a1）（1）说明语句S1的功能；（2）说明语句组S2 的功能；（3）设链表表示的线性表为（a1,a2, , ,an）,写出算法执行后的返回值所表示的线性表。2.void ABC(BTNode * BT) if BT ABC (BT-left); ABC (BT-right);

9、 coutdatadata) item=BST-data;/查找成功return _; else if(itemdata) return Find(_,item); else return Find(_,item); /if 六、编写算法（共8 分）统计出单链表HL 中结点的值等于给定值X 的结点数。int CountX(LNode* HL,ElemType x) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 34 页 - - - - - - - - - 4 数据结构试

10、题（一） （答案）一、单选题（每题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.正确性易读性强壮性高效率2.O(n) 3.9 3 3 4.-1 3 4 X * + 2 Y * 3 / - 5.2n n-1 n+1 6.e 2e 7.有向无回路8.n(n-1)/2 n(n-1) 9.（12，40）（）（74）（23,55，63）10. 增加 1 11. O(log2n) O(nlog2n) 12.归并三、运算题（每题6 分，共 24 分）1.线性表为：（78，50，40，60，34，90）2.邻接

11、矩阵：0111010101110111010101110邻接表如图11 所示：图 11 3.用克鲁斯卡尔算法得到的最小生成树为：(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 4.见图 12 5.4. 画出向小根堆中加入数据4, 2, 5, 8, 3 时，每加入一个数据后堆的变化。6.图 12 四、阅读算法（每题7 分，共 14 分）4 4 4 4 4 2 2 2 5 5 5 2 2 8 8 4 3 5 2 8 3 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

12、 - - - - - - - 第 4 页，共 34 页 - - - - - - - - - 5 3.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,an,a1）4.递归地后序遍历链式存储的二叉树。五、算法填空（每空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

13、中的值即为x 结点个数return i; /CountX 数据结构试卷（二）吉首大学试题库一、 单选题（每小题2 分，共 8 分）1、 在一个长度为n 的顺序线性表中顺序查找值为x 的元素时，查找成功时的平均查找长度（即x 与元素的平均比较次数，假定查找每个元素的概率都相等）为( )。A n B n/2 C (n+1)/2 D (n-1)/2 2、 在一个单链表中 ,若 q所指结点是 p 所指结点的前驱结点,若在 q 与 p 之间插入一个s所指的结点 ,则执行( )。A slink=p link; plink=s; B plink=s; slink=q; C plink=slink; slin

14、k=p; D q link=s; slink =p; 3、栈的插入和删除操作在（）进行。A 栈顶B 栈底C 任意位置D 指定位置4、由权值分别为11，8，6，2，5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A 24 B 71 C 48 D 53 二、 填空题（每空1 分，共 32 分）1、 数据的逻辑结构被分为_、 _ 、_和_四种。2、 一种抽象数据类型包括_和_两个部分。3、 在 下 面 的 数 组a 中 链 接 存 储 着 一 个 线 性 表 ， 表 头 指 针 为ao.next ， 则 该 线 性 表 为_。a 0 1 2 3 4 5 6 7 8 60 56 42 38 74

15、 25 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 34 页 - - - - - - - - - 6 data next 4、 在以 HL 为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为_和_。5、 用具有 n 个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的_，该循环队列的最大长度为_。6、 当堆栈采用顺序存储结构时，栈顶元素的值可用表示；当堆栈采用链接存储结构时，栈顶元素的值可用_表示。7、 一棵高度为5 的二叉树中最少

16、含有_个结点，最多含有_个结点；一棵高度为 5 的理想平衡树中，最少含有_个结点，最多含有_个结点。8、 在图的邻接表中，每个结点被称为_，通常它包含三个域：一是_；二是_；三是 _。9、 在一个索引文件的索引表中，每个索引项包含对应记录的_和_两项数据。10、假定一棵树的广义表表示为A （B （C， D （E， F， G） ， H （I，J） ） ） ， 则树中所含的结点数为_个，树的深度为_,树的度为_, 结点H的双亲结点为_,孩子结点为_ 。11、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_,整个堆排序过程的时间复杂度为 _。12、在对 m 阶的 B_树插入元素的过程中，每

17、向一个结点插入一个索引项（叶子结点中的索引项为关键字和空指针）后，若该结点的索引项数等于_个，则必须把它分裂为_个结点。三、 运算题（每小题6 分，共 24 分）1、 已知一组记录的排序码为（46，79，56，38，40，80, 95，24） ，写出对其进行快速排序的每一次划分结果。2、 一个线性表为B=（12，23，45，57，20，03，78，31，15，36） ，设散列表为HT0.12 ，散列函数为 H（key）= key % 13 并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。3、 已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ ，中序遍历的

18、结果是EBCDAFHIGJ ，试写出这棵二叉树的后序遍历结果。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出发按深度优先搜索遍历得到的顶点序列和4 3 7 6 2 0 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

19、- 名师精心整理 - - - - - - - 第 6 页，共 34 页 - - - - - - - - - 7 按广度优先搜索遍历等到的顶点序列。假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。四、 阅读算法，回答问题（每小题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;

20、; # 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 void BinTree ： ：unknown (BinTreeNode*t) BinTreeNode *p =t, *temp; 图深度优先序列广度优先序列邻接矩阵表示时邻接表表示时名

21、师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 34 页 - - - - - - - - - 8 if (p!=NULL) temp = pleftchild; pleftchild = p rightchild; prightchild = temp; unknown(pleftchild); undnown(prightchild); 该算法的功能是：_ 五、 算法填空，在画有横线的地方填写合适的内容（10 分）对顺序存储的有序表进行二分查找的递归算法。int Bins

22、ch( ElemType A ,int low ,int high,KeyType K ) if (low = high) int mid = 1 if ( K= = A mid .key ) return mid; else if ( K datedate)return1；if(s1dates2date)return1；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 34 页 - - - - - - - - - 13 if( )return1；if( )return1

23、； 31阅读下面的算法LinkList mynote(LinkList L) /L 是不带头结点的单链表的头指针if(L&L-next) q=L；L=L next；p=L；S1：while(p next) p=pnext；S2：pnext=q ；qnext=NULL ；return L； 请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2 的功能；（3）设链表表示的线性表为（a1,a2, , ,an）,写出算法执行后的返回值所表示的线性表。32假设两个队列共享一个循环向量空间（参见右下图），其类型 Queue2定义如下：typedef struct DateType dataMax

24、Size；int front2,rear2 ；Queue2；对于 i=0 或 1，fronti 和 reari 分别为第 i 个队列的头指针和尾指针。请对以下算法填空，实现第i 个队列的入队操作。int EnQueue (Queue2*Q,int i,DateType x) / 若第 i 个队列不满，则元素x 入队列，并返回1；否则返回0 if(i1)return 0 ；if(Q reari=Q front return0；Qdata =x ；Qreari= ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

25、- - - - - - 第 13 页，共 34 页 - - - - - - - - - 14 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)&(!Trchild) s=(ListNode*)ma

26、lloc(sizeof(ListNode)；sdata=Tdata；snext=Leafhead；Leafhead=s； Inorder(Trchild) ； 对于如下所示的二叉树（1）画出执行上述算法后所建立的结构；（2）说明该算法的功能。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 34 页 - - - - - - - - - 15 五、算法设计题（本题共10 分）34阅读下列函数arrange() int arrange(int a,int 1,int h,in

27、t x) /1 和 h 分别为数据区的下界和上界int i,j,t ；i=1；j=h；while(ij) while(i=x)j-；while(i=x)i+；if(ij) t=aj ；aj=ai ；ai=t ； if(ainext s2=s2next s2(或 s2!=NULL 或 s2&!s1) s1(或 s1!=NULL 或 s1&!s2) return 0 31.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3, ,an,a1）32. (i1)%2(或 1i) Qreari (Qreari )%Maxsize 33.(1)Leafh

28、eadF H G D （2）中序遍历二叉树， 按遍历序列中叶子结点数据域的值构建一个以Leafhead 为头指针的逆序单链表（或按二叉树中叶子结点数据自右至左链接成一个链表）。五、算法设计题（本题共10 分）34 （1）该函数的功能是：调整整数数组a中的元素并返回分界值i，使所有 x 的元素均落在a1.i上，使所有 x 的元素均落在ai1.h上。（2）int f(int b,int n) 或int f(int b,int n) int p,q；int p,q；p=arrange(b,0,n1,0)；p=arrange(b,0,n1,1)；名师资料总结 - - -精品资料欢迎下载 - - - -

29、 - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 34 页 - - - - - - - - - 17 q= arrange(b,p+1,n1,1)； q= arrange(b,0,p,0)；return qp；return pq； 数据结构试卷（四）吉首大学试题库一、选择题（ 20 分）1组成数据的基本单位是（） 。(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2设数据结构A=(D ，R)，其中 D=1 ，2，3，4，R=r ，r=， ，则数据结构 A 是（） 。(A) 线性结构(B) 树型结构(C) 图型结构

30、(D) 集合3数组的逻辑结构不同于下列（）的逻辑结构。(A) 线性表(B) 栈(C) 队列(D) 树4二叉树中第i(i1)层上的结点数最多有（）个。(A) 2i (B) 2i(C) 2i-1(D) 2i-1 5设指针变量p 指向单链表结点A，则删除结点A 的后继结点B 需要的操作为（） 。(A) p-next=p-next-next(B) p=p-next (C) p=p-next-next (D) p-next=p 6设栈 S 和队列 Q 的初始状态为空，元素E1、E2、E3、E4、E5 和 E6 依次通过栈S，一个元素出栈后即进入队列 Q，若 6 个元素出列的顺序为E2、E4、E3、E6、

31、E5 和 E1，则栈 S 的容量至少应该是（） 。(A) 6 (B) 4 (C) 3(D) 2 7将 10 阶对称矩阵压缩存储到一维数组A 中，则数组A 的长度最少为（） 。(A) 100 (B) 40 (C) 55(D) 80 8设结点 A 有 3 个兄弟结点且结点B 为结点 A 的双亲结点，则结点B 的度数数为（） 。(A) 3 (B) 4(C) 5 (D) 1 9根据二叉树的定义可知二叉树共有（）种不同的形态。(A) 4 (B) 5(C) 6 (D) 7 10. 10. 设有以下四种排序方法，则（）的空间复杂度最大。(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序二、填空题

32、 (30 分) 1.设顺序循环队列Q0：m-1的队头指针和队尾指针分别为F 和 R，其中队头指针F 指向当前队头元素的前一个位置，队尾指针R 指向当前队尾元素所在的位置，则出队列的语句为F =_;。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 34 页 - - - - - - - - - 18 2.设线性表中有n 个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为_，在链式存储结构上实现顺序查找的平均时间复杂度为_。3.设一棵二叉树中有n 个结点，则当用二叉

33、链表作为其存储结构时，该二叉链表中共有_个指针域， _个空指针域。4.设指针变量p 指向单链表中结点A，指针变量 s 指向被插入的结点B，则在结点 A 的后面插入结点B的操作序列为 _。5.设无向图 G 中有 n 个顶点和 e 条边，则其对应的邻接表中有_个表头结点和 _个表结点。6.设无向图 G 中有 n 个顶点 e 条边，所有顶点的度数之和为m，则 e 和 m有_关系。7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为_。8.设一棵完全二叉树中有21 个结点，如果按照从上到下、从左到右的顺序从1 开始顺序编号，则编号为 8 的双亲结点的编号是_，编号为 8

34、的左孩子结点的编号是_。9.下列程序段的功能实现子串t 在主串 s 中位置的算法，要求在下划线处填上正确语句。int index(char s , char t ) i=j=0; while(istrlen(s) & jnext=p-next; s-next=s 5.n, 2e 6.m=2e 7.CBA 8.4，16 9.i-j+1，0 10.n-1 三、应用题1.链式存储结构略，前序ABDEC ，中序 DBEAC ，后序 DEBCA 。2.哈夫曼树略， WPL=78 3.(18,5,16,19,21,23)，(5，16，21，19，18，23) 4.线性探测：6827322510876543

35、210链地址法：276832251086543210hhhhhhh5.深度： 125364，广度： 123456，最小生成树T 的边集为 E=(1 ，4)，(1，3)，(3，5)，(5，6)，(5,6) 四、算法设计题1.设计判断单链表中结点是否关于中心对称算法。typedef struct int s100; 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.sstack.

36、top=p-data; for(p=head;p!=0;p=p-next) if (p-data=stack.sstack.top) stack.top=stack.top-1; else return(0); return(1); 2.设计在链式存储结构上建立一棵二叉树的算法。typedef char datatype; typedef struct node datatype data; struct node *lchild,*rchild; bitree; void createbitree(bitree *&bt) 名师资料总结 - - -精品资料欢迎下载 - - - - - - -

37、 - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 34 页 - - - - - - - - - 20 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.设计判断一棵二叉树是否是二叉排序树的算法。int minnum=-32768,flag=1; typedef struct nodeint key;

38、struct node *lchild,*rchild;bitree; void inorder(bitree *bt) if (bt!=0) inorder(bt-lchild); if(minnumbt-key)flag=0; minnum=bt-key; inorder(bt-rchild); 数据结构试卷（五）一、选择题 (24 分) 1下面关于线性表的叙述错误的是（） 。(A) 线性表采用顺序存储必须占用一片连续的存储空间(B) 线性表采用链式存储不必占用一片连续的存储空间(C) 线性表采用链式存储便于插入和删除操作的实现(D) 线性表采用顺序存储便于插入和删除操作的实现2设哈夫曼树

39、中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m 3设顺序循环队列Q0：M-1 的头指针和尾指针分别为F 和 R，头指针 F 总是指向队头元素的前一位置，尾指针 R 总是指向队尾元素的当前位置，则该循环队列中的元素个数为（） 。(A) R-F (B) F-R (C) (R-F+M) M (D) (F-R+M) M 4 设某棵二叉树的中序遍历序列为ABCD ， 前序遍历序列为CABD ， 则后序遍历该二叉树得到序列为（） 。(A) BADC (B) BCDA (C) CDAB (D) CBDA 5设

40、某完全无向图中有n 个顶点，则该完全无向图中有（）条边。(A) n(n-1)/2 (B) n(n-1) (C) n2(D) n2-1 6设某棵二叉树中有2000 个结点，则该二叉树的最小高度为（） 。(A) 9 (B) 10 (C) 11 (D) 12 7设某有向图中有n 个顶点，则该有向图对应的邻接表中有（）个表头结点。(A) n-1 (B) n (C) n+1 (D) 2n-1 8设一组初始记录关键字序列(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，

41、6，5，8 二、填空题 (24 分) 1.为 了 能 有 效 地 应 用HASH查 找 技 术 ， 必 须 解 决 的 两 个 问 题 是 _ 和_。2.下面程序段的功能实现数据x 进栈，要求在下划线处填上正确的语句。typedef struct int s100; int top; sqstack; void push(sqstack &stack,int x) if (stack.top=m- 1) printf(“overflow”);else _;_; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -

42、 - - - - - 第 20 页，共 34 页 - - - - - - - - - 21 3.中序遍历二叉排序树所得到的序列是_序列（填有序或无序） 。4.快速排序的最坏时间复杂度为_，平均时间复杂度为_。5.设某棵二叉树中度数为0 的结点数为N0，度数为 1 的结点数为N1，则该二叉树中度数为2 的结点数为_；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_个空指针域。6.设某无向图中顶点数和边数分别为n 和 e，所有顶点的度数之和为d，则 e=_。7.设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为_。8.设 某 无 向 图

43、G的 邻 接 表 为31241314234321vvvv，则从顶点V1开始的深度优先遍历序列为_；广度优先遍历序列为_。三、应用题 (36 分) 1 设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4 趟简单选择排序和第4 趟直接插入排序后的结果。2 设指针变量 p 指向双向链表中结点A，指针变量q 指向被插入结点B，要求给出在结点A 的后面插入结点 B 的操作序列（设双向链表中结点的两个指针域分别为llink 和 rlink） 。3 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62

44、 时的比较次数并计算出查找成功时的平均查找长度。4 设一棵树 T 中边的集合为 (A ，B)，(A，C)，(A ，D)，(B，E)，(C，F)，(C，G) ，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。5 设有无向图 G（如右图所示） ，要求给出用普里姆算法构造最小生成树所走过的边的集合。6 设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。四、算法设计题(16 分) 1设有一组初始记录关键字序列（K1，K2，Kn） ，要求设计一个算法能够在 O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关

45、键字均小于Ki，右半部分的每个关键字均大于等于Ki。2设有两个集合A 和集合 B，要求设计生成集合C=A B的算法，其中集合A、B 和 C 用链式存储结构表示。数据结构试卷（五）参考答案一、选择题1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C 二、填空题1.构造一个好的HASH 函数，确定解决冲突的方法2.stack.top+，stack.sstack.top=x 3.有序4.O(n2)，O(nlog2n) 5.N0-1，2N0+N16.d/2 7.(31，38，54，56，75，80，55，63) 8.(1，3，4，2)，(1，3，2，4) 三、应用题1.(22，40，45，

46、48，80，78)，(40，45，48，80，22，78) 2.q-llink=p; q-rlink=p-rlink; p-rlink-llink=q; p-rlink=q; 3.2,ASL=91*1+2*2+3*4+4*2)=25/9 4.树的链式存储结构略，二叉树略5.E=(1 ，3)，(1，2)，(3，5)，(5，6)，(6，4) 6.略四、算法设计题名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 34 页 - - - - - - - - - 22 1.设有一组初

47、始记录关键字序列（K1，K2，Kn） ，要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki， 右半部分的每个关键字均大于等于Ki。void quickpass(int r, int s, int t) int i=s, j=t, x=rs; while(ij) while (ix) j=j-1; if (ij) ri=rj;i=i+1; while (ij & rix) i=i+1; if (inext) for(q=hb;q!=0;q=q-next) if (q-data=p-data) break; if(q!=0) t=(lklist *

48、)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=， ，则数据结构 A 是（） 。(A) 线性结构(B) 树型结构(C) 物理结构(D) 图型结构2下面程序的时间复杂为（）for（i=1，s=0； i=n ； i+） t=1 ；for(j=1 ；jnext ；p-data=q-data；p-next=q-next ；free(q)；(B) q=p-next ；q-dat

49、a=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

50、，15，14，20，18，40，36，2l (D) 15，10，14，18，20，36，40，21 6设二叉排序树中有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，2e 8. 设某强连通图中有n 个顶点，则该强连通图中至少有（）条边。(A) n(n-1) (B) n+1 (C) n (D) n(n+1) 9设有 5000 个待排序的记录关键字，如果需要用最