数据结构三套试卷详细分析

1、数据结构试卷(一)一、单项选择题(每题2分，共20分).栈和队列的共同特点是(A )。A.只允许在端点处插入和删除元素B.都是先进后出C都是先进先出D.没有共同点Ps:栈：先进后出；队列：先进先出.用链接方式存储的队列，在进行插入运算时(D ).A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都耍修改ps:新结点的插入和栈顶结点的删除都在链表的表头，即栈顶进行。如果队列为空，即 第一个结点为null,那么插入时改变了头指针。.以下数据结构中哪一个是非线性结构？( D )A.队列B.栈 C.线性表 D.二叉树Ps：数据结构二逻辑结构+存储结构。二叉树属于层次关系一一树结构

2、。4,设有一个二维数组Amn,假设A0存放位置在644A22存放位置在676 ，每个元素占一个空间，问A33存放在什么位置?脚注 表示用10进制 (10)(10)(10)表示。C A. 688B. 678 C. 692 D. 696Ps：此题画个图即知。可知A02的存放位置是646,的存放位置是661,因为A22的存放位置在676,可知两层之差为15,然后即可知道A33的存放位置在 676+15+1=692.树最适合用来表示(C )oA.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据Ps：树属于层次关系，所以可表示元素之间具有分支层次关系的数据。.二叉树

3、的第k层的结点数最多为(D ).A. 2r-1 B. 2K+1 C. 2K-1 D. 21Ps:二叉树的性质一：在二叉树的第k (k=l)层最多有个结点。.假设有18个元素的有序表存放在一维数组A19中，第一个元素放A川中，现进行二 分查找，那么查找A 3的比拟序列的下标依次为(D )A. 1, 2, 3B.9, 5, 2, 3C.9, 5, 3D.9, 4, 2, 3Ps：二分查找又称折半查找，优点是比拟次数少，查找速度快，平均性能好；其缺点是要 求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序 列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键

4、字与查找关键字比拟，如果 两者相等，那么查找成功；否那么利用中间位置记录将表分成前、后两个子表，如果中间位置记录的 关键字大于查找关键字，那么进一步查找前一子表，否那么进一步查找后一子表。重复以上过程， 直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找 不成功。此题分析 思路：首先18个元素是在有序表中的，即将它放入一维数组中的时候是 有顺序的。那么，第 一个比拟应该是(1 + 18) 12=9；第二次比拟应该是(1+9)/2=4；第三次比 较应该是(1+4)/2=2,接下来就是3了。.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为CA. 0 (1)B. 0 (n)

5、C. 0 (logo)D. 0 (n2)2Ps:快速排序是需要一个辅助空间的，该空间的大小最好为c选项，最差情况为B选项，本 题选CH(36)=36 mod 7= 1;H(15)=15mod7=l；.冲突H (15)=(1 + 1) mod 7=2;H(40)=40 mod7=5;H(63)=63 mod7=0;H(22)=22 mod 7=1;冲突H(36)=36 mod 7= 1;H(15)=15mod7=l；.冲突H (15)=(1 + 1) mod 7=2;H(40)=40 mod7=5;H(63)=63 mod7=0;H(22)=22 mod 7=1;冲突H (22)=(l + l)

6、mod7=2；冲突H2(22)=(2+l) mod7=3;ASL=633615224001234561 + 2 + 1 + 1+351.62.待散列的线性表为(36, 15, 40, 63, 22),散列用的一维地址空间为06,假定选用的散列函数是H (K) = K mod 7,假设发生冲突采用线性探查法处理，试：(1)计算出每一个元素的散列地址并在以下图中填写出散列表：0123456(2)求出在查找每一个元素概率相等情况下的平均查找长度。3.序列(10, 18, 4, 3, 6, 12, 1, 9, 18, 8)请用快速排序写出每一趟排序的结果。(8,9,4,3,6,1),10,(12.18

7、,18)(1,6,4,3),8,(9),10,12X18,18) 1,(3,4,6),8,9,10,12.18,(18) 1,3,(4,6),8,9,10,12.18,18 1,3, 4,6,8,9,10,12,18,18四、算法设计题(每题15分，共30分).设计在单链表中删除值相同的多余结点的算法。typedef int datatype;typedef struct node datatype data; struct node*next;lklist; void delredundant(lklist *&head)Iklist *p/q/s;for(p=head;p!=0;p=p-n

8、ext)for(q=p-next,s=q;q!=0;) if (q-data=p-data) s-next=q-next; free(q);q=s-next; else s=q,q=q-next;.设计一个求结点x在二叉树中的双亲结点算法。typedef struct node datatype data; struct node *lchild,*rchild; bitree;bitree *q20; intr=O,f=O,flag=O;void preorder(bitree *bt, char x)if (bt!=O &f!ag=O)if (bt-data=x) flag= 1; ret

9、urn;else r=(r+l)% 20; qr=bt; preorder(bt-lchild,x);preorder(bt-rchild,x);void parent(bitree *bt?charx)int i;preorder(bt,x);for(i=f+l; ilchild-data=x 11 qi-rchild-data) break;if (flag=0) printf(nnot found xnn);else if (idata); else printf(Hnot parent11)；).对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时，假

10、设选用H (K) 二K %9作为散列函数，那么散列地址为1的元素有(D )个，A. 1B. 2C. 3D. 4Ps：散列函数即为将要进行散列存储的数进行一系列的运算，然后将它们确定在散列表中，此题 只需将线性表中的数都用H(K)进行计算，然后结果为1的数有几个即为答案。是取余。.设有6个结点的无向图，该图至少应有(A )条边才能确保是一个连通图。A.5B.6C.7D.8Ps：连通图是每两个结点都有一条边相连，没有任何孤立结点。所以6个结点的无 向图至少应该有5条边。二、填空题(每空1分，共26分).通常从四个方面评价算法的质量：正确性_、易读性_、强壮性和高效率_。. 一个算法的时间复杂度为(

11、m+210g z2+14)2,其数量级表示为 o(n)_Ps：将该式化简开，可发现为n+lo歹z+14/n,里面计算最复杂的就是布，所以该算法的时间复 杂度为n,用数量级表示就是O(n).假定一棵树的广义表表示为A (C, D (E, F, G), H (I, J),那么树中所含的结点数 为_9 个，树的深度为3 ,树的度为3 oPs:根据广义表的表示可知该树的根结点为A,它有三个分支：C、D、H； D下面有EFG三 个结点，H下面有IJ两个结点。由此可知结点总数为9,树的深度是层数，即为3；树的度 即为结点度的最大值，为3.后缀算式9 2 3 +- 10 2 / -的值为中缀算式(3+4X)

12、 -2Y/3对应的后缀算式为 _3 4 X * + 2 Y * 3 / -_。Ps:点缀计算分层次一步一鼠计算。中缀变后缀可将每次计算加个括号，然后将操作符提到 括号后面，全部弄完之后将括号去除，这样后缀表达式就全部出来了。.假设用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。 在这种存储结构中，n个结点的二叉树共有2n_个指针域，其中有n-l_个指针 域是存放了地址，有n+1个指针是空指针。Ps：有左孩子和右孩子，每个孩子有一个指针，即共有2n个指针域。根据性质三可证的二 叉链表中有n+1个，这也是因为在2n个指针域中只有n-1个存有边信息(即存放了地址)。 6

13、.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有e个和2e个。Ps：根据邻接表的定义可知，一个顶点到另一个结点有边即链接。有向图只有一次，而无向 图有两次。. AOV网是一种有向无回路 的图。.在一个具有n个顶点的无向完全图中，包含有_n(n-l)/2条边，在一个具有n个顶点 的有向完全图中，包含有 n(n-l)_条边。Ps：首先看题目中的要求是完全图，即每个顶点要和其他n-1个顶点有边相连，那么无向完全 图有ri(ri-l)/2。有向完全图即为它的两倍。.假定一个线性表为(12,23,74,55,63,40),假设按Key % 4条件进行划分，使得同一余

14、数的元 素成为一个子表，那么得到的四个子表分别为(12, 40)、.(23,55,63)、 (74) 和 () oPs：原因和选择题第9题一样。.向一棵B_树插入元素的过程中，假设最终引起树根结点的分裂,那么新树比原树的高度 增加1O.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为Odogn),整个 堆排序过程的时间复杂度为 0(nlog.,n)o.在快速排序、堆排序、归并排序中，归并排序是稳定的。Ps：归并排序是最稳定的排序三、计算题(每题6分,共24分)60507890344001234567.在如下数组A中链接存储了一个线性表，表头指针为A 0.next,试写出该线性表。 A

15、datanext 3572041(78,50,40, 60, 34, 90).请画出以下图的邻接矩阵和邻接表。邻接矩阵:.一个图的顶点集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;用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。Ps：克鲁斯卡尔算法：设有一个有n个顶点的连通网N=V,E,最初先构造一个只有n 个顶点，没有边的非连通

16、图T=V. E,图中每个顶点自成一个连通分量。当在E中选到一条具 有最小权值的边时，假设该边的两个顶点落在不同的连通分量上，那么将此边加入到T中；否那么将 此边舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分 量上为止。答案：用克鲁斯卡尔算法得到的最小生成树为：(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)2035四、阅读算法(每题7分，共14分)LinkList mynote (LinkList L)IL是不带头结点的单链表的头指针if(L&L-next)q=L； L=Lnext； p=L；SI：while(p next)

17、 p=p next；:p next=q； q next=NULL ； return L； 请回答以下问题:(I)说明语句的功能;答案:查询链表的尾结点(2)说明语句组S2的功能答案:将第一个结点链接到链表的尾部,作为新的尾结点(3)设链表表示的线性表为(a ,a ,a )，写出算法执行后的返回值所表示的线性 1 2 n表。答案:返回的线性表为。凡，,a ,a ； 2 3 n 1void ABC(BTNode *BT)|if BTABC (BT-left);ABC (BT-right);coutdatadata) item=BST-data; / / 查找成功return true; else

18、if (itemdata)return Find(BST-left, item);else return Find(BST-right, item) ;/BST-right 双7BST-left 顺序可交 换。/if)六、编写算法(共8分)统计出单链表HL中结点的值等于给定值X的结点数。int CountX(LNode* HL,ElemType x)答案如下：int CountX(LNode* HL,ElemTypex) inti=0;LNode*p=HL;i 为计数器 while(p!=NULL)if(P-data=x) i+;p=p-next;/while,出循环时i中的值即为x结点个数

19、return i;/CountX数据结构试卷(二)一、选择题(24分).下面关于线性表的表达错误的选项是(D )。(A)线性表采用顺序存储必须占用一片连续的存储空间(B)线性表采用链式存储不必占用一片连续的存储空间(0线性表采用链式存储便于插入和删除操作的实现(D)线性表采用顺序存储便于插入和删除操作的实现Ps:顺序表具有的缺点之一就是不利于插入和删除操作，所以将存储方式改进为链式存 储。.设哈夫曼树中的叶子结点总数为m,假设用二叉链表作为存储结构，那么该哈夫曼树中总共 有(B )个空指针域。(A) 2m-1(B) 2m(C) 2m+l(D) 4mPs：哈夫曼树只有叶子和度为2的结点，用二叉链

20、表存储时每个结点都会有一个左孩子，一 个右孩子，所以空指针域为2m。.设顺序循环队列Q0： MT的头指针和尾指针分别为F和R,头指针F总是指向队头元素 的前一位置，尾指针R总是指向队尾元素的当前位置，那么该循环队列中的元素个数为(C )o(A) R-F(B) F-R(C) (R-F+M)%M (D) (FR+M) %MPs：根据循环队列的定义可知C是正确的。.设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,那么后序遍历该二叉树 得到序列为(A )o(A) BADC(B) BCDA(C) CDAB (D)CBDA Ps：根据前序和中序遍历可知，C为根结点，A为左子树，D为右子树，B

21、为A的右子树。.设某完全无向图中有n个顶点，那么该完全无向图中有(A )条边。(A) n(n-l)/2(B) n(n-l)(C) r)2(D) wTPs：该题和试卷一的一道填空题一样。.设某棵二叉树中有2000个结点，那么该二叉树的最小高度为(C)o(A) 9(B) 10(C) 11(D) 12Ps：根据二叉树的性质2可知，该二叉树的最小高度应该是结点数最多的时候，这样列出一 个表达式即可知道该二叉树的最小高度。.设某有向图中有n个顶点，那么该有向图对应的邻接表中有(B )个表头结点。(A) n-l(B) n(C) n+1(D) 2n-lPs：根据邻接表的定义可知，表头结点数目与顶点数目相同。

22、.设一组初始记录关键字序列(5, 2, 6, 3, 8),以第一个记录关键字5为基准进行一趟快 速排序的结果为(C )o(A) 2, 3, 5, 8, 6(C) 3, 2, 5, 6, 8(A) 2, 3, 5, 8, 6(C) 3, 2, 5, 6, 8(B) 3, 2, 5, 8, 6(D)2, 3, 6, 5, 8 Ps：快速排序是将一个数为基准，然后分为左右两个序列，左边的数都比基准小，右边的数都比基准大。二、填空题(24分).为了能有效地应用HASH查找技术，必须解决的两个问题是构造一个好的HASH函数 和确定解决冲突的方法_。.下面程序段的功能实现数据x进栈，要求在下划线处填上正确

23、的语句。typedef struct int s100; int top; sqstack; void push(sqstack &stack,int x)if (stack.top=m-l) printf，overflow)；else _stack. lop+_;stack. s stack, top=x;.中序遍历二叉排序树所得到的序列是有序 序列(填有序或无序)。.快速排序的最坏时间复杂度为 0(皿)_,平均时间复杂度为_0(nlog,n)_。.设某棵二叉树中度数为0的结点数为N ,度数为1的结点数为N ,那么核二叉树中度数为 012的结点数为_NT_；假设采用二叉链表作为该二叉树的存储

24、结构，那么该二叉树中共有 02N+N 个空指针域。.设某无向图中顶点数和边数分别为n和e,所有顶点的度数之和为d,那么e=d/2_。.设一组初始记录关键字序列为(55, 63, 44, 38, 75, 80, 31, 56),那么利用筛选法建立 的初始堆为_(31, 38, 54, 56, 75, 80, 55, 63)_。.一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是 (1, 3, 4, 5,4，BFS遍历的输出序列是(1, 3, 2, 4,揖Ps:DFS:国撵尤先遍历p即旷,度冬砰历.设一组初始记录虎整军序列亚45, 80, 48, 40, 22, 78),那么分别给

25、出第4趟简单项选择择 排序和第4趟直接插入排序后的结果。简单项选择择排序：(22, 40, 45, 48, 80, 78)；直接插入排序:(40, 45, 48, 80, 22, 78).设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A 的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)。 q-llink=p; q-rlink=p-rlink; p-rlink-llink=q; p-rlink=q;.设一组有序的记录关键字序列为(13, 18, 24, 35, 47, 50, 62, 83, 90),查找方法用 二分查找，要求计

26、算出查找关键字62时的比拟次数并计算出查找成功时的平均查找长 度。2,ASL=91*l+2*2+3*4+4*2)=25/9.设一棵树 中边的集合为3,B), (A, C), (A, D), (B, E), (C, F), (C, G),委求 用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。.设有无向图G,要求给出用普里姆算法构造最小生成树所走过的边的集合。E=(1, 3),(3, 5), (5, 6), (6, 4)(1，2),6.设有一组初始记 要求构造一棵二四、算法设计题(16分)录关键字为&5, 80, 48, 40, 22, 78), 叉排序树并给出构造过程

27、。1.设有一组初始记录关键字序列名，K ,，K ),要求设计一个算法能够在42的时间12n复杂度内将线性表划分成两局部,其中左半局部的每个关键字均小于.，右半局部的每个关键字均大于等于Ko1Ps.该算法即为快速箱序算法void quickpass(int r, int s, int t)inti=sj=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) fbr(q=hb;q!=O;q=q-next) if (q-data=p-data) break;if(q!=0)t=(

28、lklist*)malloc(sizeof(lklist);t-data=p-data;t-next=hc;hc=t;数据结构试卷(三)一、选择题(每题1分，共20分).设某数据结构的二元组形式表示为A=(D, R), D=01, 02, 03, 04, 05, 06, 07, 08, 09, R=r, r=v01, 02, , , , , , , ,那么数据结构A 是(B )。(A)线性结构 (B)树型结构(C)物理结构 (D)图型结构Ps：将该题的结构图画出即可看出是什么结构。.下面程序的时间复杂为(B )for (i=1, s=0； i=n； i+) t=1 ； for(j=1 ； jn

29、ext； p-data=q-data； p-next=q-next； free (q)；q=p-next； q-data=p-data； p-next=q-next； free (q)；q=p-next； p-next=q-next； free (q)；q=p-next； p-data=q-data； free (q)；Ps：首先用指针变量q指向结点A的后继结点B,然后将结点B的值复制到结点A中，最后 删除结点B。4,设有n个待排序的记录关键字，那么在堆排序中需要(A )个辅助记录单元。(A) 1(B) n(C) nlog n (D)皿25.设一组初始关键字记录关键字为(20, 15, 14,

30、 18, 21, 36, 40, 10),那么以20为基准记 录的一趟快速排序结束后的结果为(A )。(A) 10, 15, 14, 18, 20, 36, 40, 21 (B)10, 15, 14, 18, 20, 40, 36, 2110, 15, 14, 20, 18, 40, 36, 2115, 10, 14, 18, 20, 36, 40, 21.设二叉排序树中有n个结点，那么在二叉排序树的平均平均查找长度为(B )o(A) 0(1)(B) 0(log n) (C)(D) 0(n02.设无向图G中有n个顶点e条边，那么其对应的邻接表中的表头结点和表结点的个数分别 为(D )。(A)n

31、, e(B)e, n(C) 2n,e (D) n, 2e.设某强连通图中有n个顶点，那么该强连通图中至少有(C )条边。(A)n(n-l)(B)n+1(C) n(D) n (n+1).设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关 键字，那么用以下(D )方法可以到达此目的。(A)快速排序 (B)堆排序 (C)归并排序 (D)插入排序Ps：快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数， 而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为0(log n) o 2.以下四种排序中(D )的空间复杂度最大。(A)插入排序(B)冒泡排序 (C)堆排序 (D)归并排序二、填空殖(每空1分共20分).数据的物理结构主要包括顺序存储结构和链式存储结构两种情况。.设一棵完全二叉树中有500个结点，那么该二叉树的深度为_9；假设用二叉链表作为 该完全二叉树的存储结构，那么共有501个空指针域。.设输入序列为1、2、3,那么经过栈的作用后可以得到_5 种不同的输出序列。Ps：共 5 种：123,213,321,231, 132.设有向图G用邻接矩阵Ann作为存储结构，那么该邻接矩阵中第i行上所有元素之和 等于