数据结构试卷带答案.doc

数据结构试卷(一）一、选择题(20分）1组成数据的基本单位是( 1。C）。 （A） 数据项（B） 数据类型(C） 数据元素（D） 数据变量2设数据结构A=（D,R）,其中D=1,2，3，4，R=r，r=1，2，2，3,3，4，4，1，则数据结构A是（C）。（A) 线性结构（B） 树型结构 (C） 图型结构（D) 集合3数组的逻辑结构不同于下列（D)的逻辑结构。(A) 线性表(B） 栈 (C） 队列（D) 树4二叉树中第i（i1）层上的结点数最多有（C）个。(A） 2i（B) 2i（C) 2i-1(D） 2i15设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为（。A ）。(A) pnext=p-nextnext(B) p=pnext(C） p=p-nextnext(D) pnext=p6设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（。C ).（A) 6(B) 4(C） 3（D) 27将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为(C ）。(A） 100(B) 40(C） 55（D) 808设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数数为（8。B（A) 3（B） 4（C） 5（D） 19根据二叉树的定义可知二叉树共有( B）种不同的形态。(A） 4（B） 5（C） 6（D） 710. 设有以下四种排序方法，则( B )的空间复杂度最大。（A) 冒泡排序(B） 快速排序(C） 堆排序（D） 希尔排序二、填空题（30分)1. 设顺序循环队列Q0:m1的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置,则出队列的语句为F =_;.2. 设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为_,在链式存储结构上实现顺序查找的平均时间复杂度为_。3. 设一棵二叉树中有n个结点,则当用二叉链表作为其存储结构时，该二叉链表中共有_个指针域,_个空指针域。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的左孩子结点的编号是_。9. 下列程序段的功能实现子串t在主串s中位置的算法,要求在下划线处填上正确语句.int index（char s , char t )i=j=0;while(inext) stack.top+； stack.sstack.top=pdata； for（p=head；p！=0；p=pnext） if (p-data=stack.sstack。top) stack。top=stack。top1； else return（0)； return（1)；2. 设计在链式存储结构上建立一棵二叉树的算法。typedef char datatype；typedef struct node datatype data； struct node *lchild，rchild; bitree；void createbitree（bitree bt) char ch; scanf（”c”，&ch)； if（ch=） bt=0; return;bt=（bitree）malloc(sizeof（bitree）； bt-data=ch；createbitree(btlchild）； createbitree(bt-rchild)；3. 设计判断一棵二叉树是否是二叉排序树的算法。int minnum=32768,flag=1；typedef struct nodeint key； struct node lchild，*rchild；bitree；void inorder（bitree bt） if （bt！=0） inorder（bt-lchild）； if（minnumbt-key)flag=0； minnum=btkey； inorder（btrchild)；数据结构试卷（二）一、选择题(24分）1下面关于线性表的叙述错误的是（。D（A） 线性表采用顺序存储必须占用一片连续的存储空间（B) 线性表采用链式存储不必占用一片连续的存储空间（C） 线性表采用链式存储便于插入和删除操作的实现（D） 线性表采用顺序存储便于插入和删除操作的实现2设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构,则该哈夫曼树中总共有（2。B)个空指针域.（A）2m1（B)2m(C）2m+1(D)4m3设顺序循环队列Q0：M1的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ 3.C ）.（A） R-F(B） FR（C） (RF+M）M(D） （F-R+M）%M4设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD,则后序遍历该二叉树得到序列为（ 4。A )。（A） BADC（B）BCDA(C） CDAB(D） CBDA5设某完全无向图中有n个顶点，则该完全无向图中有（5。A ）条边。（A） n（n-1)/2(B) n（n1)(C） n2 （D） n216设某棵二叉树中有2000个结点,则该二叉树的最小高度为（C）。（A) 9（B） 10（C) 11(D) 127设某有向图中有n个顶点，则该有向图对应的邻接表中有(B)个表头结点。(A） n1（B) n（C） n+1（D） 2n18设一组初始记录关键字序列(5,2，6，3，8),以第一个记录关键字5为基准进行一趟快速排序的结果为（8。C）.(A） 2，3，5，8,6（B） 3，2,5，8,6（C） 3，2，5，6，8（D) 2，3,6,5，8二、填空题（24分）1. 为了能有效地应用HASH查找技术，必须解决的两个问题是_构造一个好的HASH函数_和_确定解决冲突的方法_。2. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。typedef struct int s100； int top； sqstack；void push(sqstack stack，int x)if （stack。top=m1） printf(“overflow）;else _；_；3. 中序遍历二叉排序树所得到的序列是_序列(填有序或无序)。4. 快速排序的最坏时间复杂度为_，平均时间复杂度为_。5. 设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1,则该二叉树中度数为2的结点数为_;若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_个空指针域。6. 设某无向图中顶点数和边数分别为n和e,所有顶点的度数之和为d，则e=_。7. 设一组初始记录关键字序列为（55，63，44，38,75，80,31,56),则利用筛选法建立的初始堆为_。8. 设某无向图G的邻接表为，则从顶点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时的比较次数并计算出查找成功时的平均查找长度.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）的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。2 设有两个集合A和集合B，要求设计生成集合C=AB的算法,其中集合A、B和C用链式存储结构表示.数据结构试卷（二)参考答案一、选择题1.D2。B3.C4.A5.A6.C7.B8。C二、填空题1. 构造一个好的HASH函数，确定解决冲突的方法2. stack.top+,stack.sstack。top=x3. 有序4. O（n2），O(nlog2n)5. N01，2N0+N16. d/27. (31，38，54,56,75，80，55，63）8. (1,3，4,2)，(1，3，2，4)三、应用题1. (22，40，45，48，80,78)，(40，45，48,80，22，78）2. qllink=p; qrlink=prlink; prlink-llink=q; prlink=q;3. 2，ASL=911+22+3*4+42）=25/94. 树的链式存储结构略,二叉树略5. E=(1，3)，（1，2),(3,5），(5，6）,(6，4)6. 略四、算法设计题1. 设有一组初始记录关键字序列（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 (ij & rjx) j=j-1； if （ij） ri=rj；i=i+1； while （inext） for（q=hb；q！=0；q=q-next) if （qdata=pdata） break;if(q！=0） t=（lklist *)malloc（sizeof(lklist）); t-data=pdata；tnext=hc; hc=t;数据结构试卷（三）一、选择题(30分）1设某数据结构的二元组形式表示为A=(D，R),D=01，02，03，04,05,06,07，08，09，R=r，r=01，02，01，03,01,04，02，05，02，06,，03,09，则数据结构A是（ B ）.(A） 线性结构（B） 树型结构(C） 物理结构（D) 图型结构2下面程序的时间复杂为（B ）for(i=1,s=0; idata；pnext=qnext；free（q）；（C） q=p-next；p-next=qnext；free（q)；（D) q=p-next；p-data=q-data；free(q）；4设有n个待排序的记录关键字，则在堆排序中需要( A ）个辅助记录单元。（A） 1(B) n(C） nlog2n（D） n25设一组初始关键字记录关键字为(20，15，14，18,21，36，40，10），则以20为基准记录的一趟快速排序结束后的结果为( A ）。(A) 10，15,14,18，20，36,40，21(B） 10,15，14，18,20，40,36，21(C） 10，15,14，20，18，40，36，2l（D） 15,10，14,18，20，36，40，216设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ B ).（A) O（1）（B） O（log2n）(C）O(n）(D） O（n2）7设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为( D ）。（A） n，e（B） e,n（C） 2n,e(D） n,2e8。 设某强连通图中有n个顶点，则该强连通图中至少有（ C )条边。（A) n（n1）（B） n+1(C） n（D） n(n+1）9设有5000个待排序的记录关键字,如果需要用最快的方法选出其中最小的10个记录关键字,则用下列( B )方法可以达到此目的。(A）快速排序（B）堆排序（C）归并排序(D）插入排序10.下列四种排序中（ D ）的空间复杂度最大。(A）插入排序（B）冒泡排序（C)堆排序（D)归并排序二、填空殖（48分，其中最后两小题各6分)1. 数据的物理结构主要包括_和_两种情况.2. 设一棵完全二叉树中有500个结点，则该二叉树的深度为_9_;若用二叉链表作为该完全二叉树的存储结构，则共有_501_个空指针域.3. 设输入序列为1、2、3，则经过栈的作用后可以得到_5_种不同的输出序列。4. 设有向图G用邻接矩阵Ann作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的_出度_，第i列上所有元素之和等于顶点i的_入度_。5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有_0_个度数为1的结点。6. 设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_e=d_.7. _中序_遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。8. 设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较_7_次就可以断定数据元素X是否在查找表中。9. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为_O（n）_.10. 设有n个结点的完全二叉树,如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为_i/2_，右孩子结点的编号为_2i+1_.11. 设一组初始记录关键字为(72，73，71，23，94,16，5），则以记录关键字72为基准的一趟快速排序结果为_(5,16,23,71,72，73,94）_.12. 设有向图G中有向边的集合E=1，2，1，4，4，3，则该图的一种拓扑序列为_1，4,2，3_.13. 下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句.struct recordint key; int others;int hashsqsearch(struct record hashtable ，int k)int i，j; j=i=k p；while (hashtablej.key！=k&hashtablej。flag！=0)j=(_j+1_） m； if (i=j) return（1）; if （_ ) return（j)； else return（1）；14. 下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句.typedef struct nodeint key； struct node *lchild; struct node rchild；bitree；bitree *bstsearch（bitree t， int k） if （t=0 ） return(0）；else while (t!=0)if （t-key=k）_;else if （tkeyk） t=t-lchild； else_;三、算法设计题（22分）1 设计在单链表中删除值相同的多余结点的算法。2 设计一个求结点x在二叉树中的双亲结点算法.数据结构试卷(三）参考答案一、选择题1.B2。B3。A4。A5.A6.B7.D8。C9.B10。D第3小题分析：首先用指针变量q指向结点A的后继结点B，然后将结点B的值复制到结点A中，最后删除结点B.第9小题分析:9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可,每次筛选的时间复杂度为O（log2n）。二、填空题1. 顺序存储结构、链式存储结构2. 9，5013. 54. 出度,入度5. 06. e=d7. 中序8. 79. O(1)10. i/2，2i+111. （5,16，71，23，72,94，73）12. （1，4,3，2)13. j+1，hashtablej。key=k14. return（t)，t=t-rchild第8小题分析:二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。三、算法设计题1. 设计在单链表中删除值相同的多余结点的算法。typedef int datatype；typedef struct node datatype data; struct node next；lklist；void delredundant(lklist *head) lklist p，q，*s； for（p=head；p！=0；p=p-next） for（q=p-next,s=q；q！=0; ） if （qdata=p-data) s-next=q-next； free(q);q=snext; else s=q，q=qnext； 2. 设计一个求结点x在二叉树中的双亲结点算法。typedef struct node datatype data； struct node lchild，*rchild； bitree；bitree *q20； int r=0,f=0,flag=0；void preorder（bitree *bt, char x) if （bt！=0 & flag=0）if （bt-data=x） flag=1； return;else r=（r+1)% 20； qr=bt; preorder（btlchild,x）； preorder（btrchild，x）； void parent（bitree *bt，char x） int i； preorder(bt，x)； for(i=f+1； i=r； i+)if （qilchilddata=x qi-rchild-data） break； if （flag=0） printf（”not found xn”）; else if （idata）; else printf（”not parent）；数据结构试卷（四）一、选择题（30分）1设一维数组中有n个数组元素,则读取第i个数组元素的平均时间复杂度为（ ）。(A) O(n)（B） O（nlog2n）（C） O(1）（D） O（n2)2设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。（A) 2k-1(B） 2k(C) 2k1（D) 2k13设某无向图中有n个顶点e条边,则该无向图中所有顶点的入度之和为( ）。(A) n(B） e（C) 2n(D） 2e4在二叉排序树中插入一个结点的时间复杂度为( ）。（A） O(1)（B） O(n)(C） O（log2n）（D） O（n2)5设某有向图的邻接表中有n个表头结点和m个表结点,则该图中有（ ）条有向边。（A) n（B) n1（C） m（D) m16设一组初始记录关键字序列为（345，253，674,924，627)，则用基数排序需要进行（ )趟的分配和回收才能使得初始关键字序列变成有序序列.(A) 3（B） 4（C) 5(D） 87设用链表作为栈的存储结构则退栈操作（ )。(A） 必须判别栈是否为满（B) 必须判别栈是否为空(C） 判别栈元素的类型（D) 对栈不作任何判别8下列四种排序中( ）的空间复杂度最大。(A) 快速排序（B) 冒泡排序（C） 希尔排序(D) 堆9设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2,则下列等式成立的是（ ）。（A） N0=N1+1(B） N0=Nl+N2(C） N0=N2+1（D） N0=2N1+l10。设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（ ）.（A) log2n+1（B) log2n1(C) log2n(D) log2（n+1）二、填空题(42分）1 设有n个无序的记录关键字，则直接插入排序的时间复杂度为_，快速排序的平均时间复杂度为_。2 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_（设结点中的两个指针域分别为llink和rlink）。3 根据初始关键字序列(19,22，01，38，10)建立的二叉排序树的高度为_。4 深度为k的完全二叉树中最少有_个结点.5 设初始记录关键字序列为(K1,K2，Kn)，则用筛选法思想建堆必须从第_个元素开始进行筛选。6 设哈夫曼树中共有99个结点,则该树中有_个叶子结点;若采用二叉链表作为存储结构,则该树中有_个空指针域.7 设有一个顺序循环队列中有M个存储单元,则该循环队列中最多能够存储_个队列元素;当前实际存储_个队列元素（设头指针F指向当前队头元素的前一个位置,尾指针指向当前队尾元素的位置)。8 设顺序线性表中有n个数据元素,则第i个位置上插入一个数据元素需要移动表中_个数据元素;删除第i个位置上的数据元素需要移动表中_个元素.9 设一组初始记录关键字序列为（20，18，22，16，30，19),则以20为中轴的一趟快速排序结果为_。10 设一组初始记录关键字序列为(20，18,22，16，30,19)，则根据这些初始关键字序列建成的初始堆为_。11 设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是_。12 设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数_第i列上非0元素的个数（填等于,大于或小于)。13 设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_。14 设散列函数H（k）=k mod p,解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针,不成功时返回标志0。typedef struct node int key； struct node *next； lklist； void createlkhash（lklist hashtable )int i，k; lklist s；for（i=0；im;i+）_;for(i=0；in;i+)s=(lklist ）malloc（sizeof(lklist）； s-key=ai；k=ai p； snext=hashtablek；_；三、算法设计题（28分）1 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符），要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。3. 在链式存储结构上建立一棵二叉排序树。数据结构试卷（四)参考答案一、选择题1C2D 3D 4B 5C6A7B 8。A 9C 10A二、填空题1. O（n2），O(nlog2n）2. pllink-rlink=prlink； p-rlink-llink=prlink3. 34. 2k15. n/26. 50，517. m-1，(RF+M）%M8. n+1-i，ni9. (19，18，16，20，30，22）10. （16,18,19，20，32,22)11. Aij=112. 等于13. BDCA14. hashtablei=0,hashtablek=s三、算法设计题1. 设单链表中有仅三类字符的数据元素（大写字母、数字和其它字符）,要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符.typedef char datatype;typedef struct node datatype data； struct node next;lklist；void split（lklist *head，lklist ha,lklist *&hb，lklist *hc) lklist p；ha=0，hb=0，hc=0；for（p=head；p！=0；p=head) head=pnext； pnext=0； if (pdata=A pdata=Z) pnext=ha; ha=p; else if （pdata=0 & p-datanext=hb； hb=p； else pnext=hc; hc=p； 2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。typedef struct node int data； struct node lchild，rchild； bitree；void swapbitree(bitree *bt） bitree p； if(bt=0) return；swapbitree（btlchild）； swapbitree（bt-rchild）；p=btlchild； btlchild=btrchild； btrchild=p；3. 在链式存储结构上建立一棵二叉排序树。define n 10typedef struct nodeint key； struct node lchild,*rchild;bitree；void bstinsert（bitree *&bt，int key） if (bt=0)bt=(bitree *）malloc（sizeof(bitree）)； btkey=key;btlchild=btrchild=0; else if （bt-keykey) bstinsert（bt-lchild,key）; else bstinsert（btrchild，key）；void createbsttree（bitree &bt） int i； for（i=1；i=n;i+） bstinsert（bt，random（100）;数据结构试卷（五)一、选择题(30分） 1数据的最小单位是（ A ）.（A） 数据项(B） 数据类型（C) 数据元素（D) 数据变量2设一组初始记录关键字序列为(50，40，95