中南大学十套数据结构试题及答案2.doc

数据结构试卷（一）一、单选题（每题 2 分，共20分）1. 栈和队列的共同特点是( )。A。只允许在端点处插入和删除元素B。都是先进后出 C.都是先进先出D.没有共同点 2. 用链接方式存储的队列，在进行插入运算时（ ）. A。 仅修改头指针 B。 头、尾指针都要修改 C。 仅修改尾指针 D.头、尾指针可能都要修改3. 以下数据结构中哪一个是非线性结构？（ ) A。 队列 B. 栈 C. 线性表 D. 二叉树4. 设有一个二维数组Amn，假设A00存放位置在644(10），A22存放位置在676（10），每个元素占一个空间，问A33(10）存放在什么位置？脚注（10）表示用10进制表示。 A688 B678 C692 D6965. 树最适合用来表示（ )。 A.有序数据元素 B.无序数据元素 C。元素之间具有分支层次关系的数据 D。元素之间无联系的数据6. 二叉树的第k层的结点数最多为（ ). A2k1 B.2K+1 C。2K-1 D。 2k-17. 若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中,现进行二分查找，则查找A3的比较序列的下标依次为（ ） A. 1，2,3B. 9,5，2，3 C。 9，5，3D. 9，4，2，38. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A。 O（1） B。 O(n） C. O(1og2n） D。 O（n2)9. 对于线性表(7，34，55,25，64，46，20，10)进行散列存储时,若选用H（K)=K %9作为散列函数，则散列地址为1的元素有（ ）个， A1 B2 C3 D410. 设有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. 后缀算式9 2 3 +- 10 2 / 的值为_.中缀算式（3+4X)-2Y/3对应的后缀算式为_。5. 若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有_个指针域，其中有_个指针域是存放了地址，有_个指针是空指针.6. 对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中，所含边结点分别有_个和_个。7. AOV网是一种_的图。8. 在一个具有n个顶点的无向完全图中，包含有_条边，在一个具有n个顶点的有向完全图中，包含有_条边。9. 假定一个线性表为(12,23,74，55,63,40），若按Key 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为_、_、_和_。10. 向一棵B_树插入元素的过程中,若最终引起树根结点的分裂,则新树比原树的高度_.11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_，整个堆排序过程的时间复杂度为_。12. 在快速排序、堆排序、归并排序中，_排序是稳定的。三、计算题（每题 6 分，共24分）1. 在如下数组A中链接存储了一个线性表，表头指针为A 0。next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data605078903440next35720412. 请画出下图的邻接矩阵和邻接表。3. 已知一个图的顶点集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; 用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边。4. 画出向小根堆中加入数据4， 2， 5， 8， 3时,每加入一个数据后堆的变化。四、阅读算法（每题7分,共14分)1. LinkList mynote（LinkList L) /L是不带头结点的单链表的头指针 if（L&Lnext） q=L;L=Lnext;p=L； S1： while(p>next） p=pnext； S2： p>next=q；qnext=NULL; return L; 请回答下列问题： （1）说明语句S1的功能； （2）说明语句组S2的功能； (3)设链表表示的线性表为(a1,a2， ，an），写出算法执行后的返回值所表示的线性表。2. void ABC(BTNode * BT） if BT ABC (BTleft）； ABC (BT->right); coutBT-data< ； 该算法的功能是:五、算法填空(共8分）二叉搜索树的查找递归算法：bool Find(BTreeNode BST,ElemType& item) if (BST=NULL) return false; /查找失败 else if （item=BST->data） item=BST>data;/查找成功 return _； else if（itemBST>data） return Find(_，item）; else return Find（_，item)； /if六、编写算法(共8分）统计出单链表HL中结点的值等于给定值X的结点数。 int CountX(LNode* HL，ElemType x）一、 选择题（每题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 34. -1 3 4 X + 2 Y 3 / -5. 2n n-1 n+16. e 2e7. 有向无回路8. n（n-1）/2 n（n-1）9. （12，40） ( ) （74) (23,55，63）10. 增加111. O(log2n） O（nlog2n）12. 归并三、计算题（每题6分，共24分）1. 线性表为:（78，50,40，60，34，90)2. 邻接矩阵： 邻接表如图11所示：图113. 用克鲁斯卡尔算法得到的最小生成树为： (1,2）3， （4,6)4， （1,3)5, （1，4）8， (2,5）10, （4,7)204. 见图124444422255285283452843图12四、 读算法（每题7分，共14分）1. （1）查询链表的尾结点（2)将第一个结点链接到链表的尾部，作为新的尾结点 (3）返回的线性表为（a2，a3，an,a1) 2. 递归地后序遍历链式存储的二叉树。五、 法填空（每空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中的值即为x结点个数 return i； /CountX数据结构试卷（二）一、选择题（24分）1下面关于线性表的叙述错误的是（ ）。(A) 线性表采用顺序存储必须占用一片连续的存储空间(B） 线性表采用链式存储不必占用一片连续的存储空间(C) 线性表采用链式存储便于插入和删除操作的实现（D) 线性表采用顺序存储便于插入和删除操作的实现2设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有( ）个空指针域。（A） 2m1（B） 2m(C） 2m+1(D） 4m3设顺序循环队列Q0：M1的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）.(A) RF(B) F-R（C） （R-F+M)M（D） （F-R+M)%M4设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD,则后序遍历该二叉树得到序列为（ ）。（A） BADC(B） BCDA（C) CDAB（D) CBDA5设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。(A) n(n-1)/2(B） n（n-1)(C) n2 (D) n216设某棵二叉树中有2000个结点，则该二叉树的最小高度为( ）。（A） 9(B） 10(C） 11（D） 127设某有向图中有n个顶点,则该有向图对应的邻接表中有（ ）个表头结点.（A） n-1(B） n(C) n+1（D） 2n-18设一组初始记录关键字序列(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，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 _;_;3. 中序遍历二叉排序树所得到的序列是_序列（填有序或无序）。4. 快速排序的最坏时间复杂度为_，平均时间复杂度为_。5. 设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为_；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_个空指针域。6. 设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d,则e=_。7. 设一组初始记录关键字序列为(55，63，44，38,75，80，31，56），则利用筛选法建立的初始堆为_。8 已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是 ，BFS遍历的输出序列是 三、应用题（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. N0-1,2N0+N16. d/27. (31，38，54，56,75，80，55，63)8. (1，3，4，5，2),（1，3，2,4,5)三、应用题1. (22,40,45，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=911+22+3*4+4*2)=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 （i<j & rjx) j=j-1; if (ij） ri=rj；i=i+1; while (i<j rix） i=i+1； if (i<j） rj=ri；j=j1; ri=x；2. 设有两个集合A和集合B,要求设计生成集合C=AB的算法，其中集合A、B和C用链式存储结构表示。typedef struct node int data; struct node next;lklist;void intersection(lklist *ha,lklist hb，lklist &hc)lklist p，q，t;for(p=ha，hc=0;p!=0;p=p>next) for（q=hb;q!=0;q=q-next) if (q-data=p->data） break；if（q!=0) t=(lklist *）malloc（sizeof（lklist)）； t-data=pdata；t>next=hc； hc=t；数据结构试卷（三）一、选择题（每题1分,共20分)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，07>,<03，08>，03,09>，则数据结构A是( ）。（A） 线性结构(B） 树型结构(C） 物理结构(D) 图型结构2下面程序的时间复杂为（ ）for（i=1，s=0； i<=n； i+） t=1;for(j=1；j<=i；j+） t=t*j；s=s+t；(A) O(n)（B） O（n2)（C） O(n3)(D） O（n4)3设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。（A） q=pnext；pdata=q-data;p>next=qnext；free（q);(B) q=p-next；q-data=p-data；pnext=q->next;free(q)；(C） q=pnext；p>next=q-next；free（q)；(D) q=p-next；p->data=qdata；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,15，14,20，18，40，36，2l(D) 15，10，14，18,20，36，40,216设二叉排序树中有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，2e8. 设某强连通图中有n个顶点,则该强连通图中至少有( ）条边。(A） n（n1）（B) n+1(C） n(D） n(n+1)9设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ）方法可以达到此目的。(A） 快速排序（B） 堆排序(C） 归并排序(D） 插入排序10.下列四种排序中（ ）的空间复杂度最大。（A） 插入排序（B） 冒泡排序(C） 堆排序（D） 归并排序二、填空殖（每空1分 共20分）1. 数据的物理结构主要包括_和_两种情况.2. 设一棵完全二叉树中有500个结点，则该二叉树的深度为_；若用二叉链表作为该完全二叉树的存储结构，则共有_个空指针域.3. 设输入序列为1、2、3,则经过栈的作用后可以得到_种不同的输出序列。4. 设有向图G用邻接矩阵Ann作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的_，第i列上所有元素之和等于顶点i的_。5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有_个度数为1的结点.6. 设有向图G中有n个顶点e条有向边,所有的顶点入度数之和为d，则e和d的关系为_。7. _遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。8. 设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较_次就可以断定数据元素X是否在查找表中.9. 不论是顺序存储结构的栈还是链式存储结构的栈,其入栈和出栈操作的时间复杂度均为_。10. 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为_，右孩子结点的编号为_。11. 设一组初始记录关键字为（72，73,71，23，94，16，5）,则以记录关键字72为基准的一趟快速排序结果为_。12. 设有向图G中有向边的集合E=<1，2，<2，3，1，4,<4,2>，4，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=(_) %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 (t>key>k) t=t->lchild; else_;三、计算题(每题10分，共30分)1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。2已知待散列的线性表为(36，15，40，63，22），散列用的一维地址空间为0.6，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理,试：（1)计算出每一个元素的散列地址并在下图中填写出散列表： 0 1 2 3 4 5 6(2）求出在查找每一个元素概率相等情况下的平均查找长度。3已知序列(10，18，4,3，6，12,1,9，18,8）请用快速排序写出每一趟排序的结果。四、算法设计题(每题15分，共30分）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 2、H（36）=36 mod 7=1； H(22)=（1+1） mod 7=2; 。冲突H（15)=15 mod 7=1；.冲突 H2（22)=(2+1) mod 7=3; H（15)=(1+1) mod 7=2;H（40）=40 mod 7=5；H(63)=63 mod 7=0;H（22）=22 mod 7=1; .冲突（1） 0 1 2 3 4 5 66336152240(2）ASL=3、(8,9,4,3，6，1)，10,(12，18,18） （1,6，4，3），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 1，3, 4，6，8,9，10，12,18,18四、算法设计题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 （q-data=pdata） s->next=q->next; free(q)；q=snext； else s=q，q=q-next； 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（bt-rchild，x); void parent（bitree *bt,char x） int i； preorder(bt，x); for（i=f+1； i<=r； i+） if (qi-lchilddata=x | qirchild>data） break; if （flag=0) printf（”not found xn”）； else if （i=r) printf(”%c"，bt-data）； else printf（”not parent")；数据结构试卷（四）一、选择题（每题1分共 20分)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）二、填空题(每空1分共 20分）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；i<n；i+)s=（lklist *）malloc(sizeof（lk