《数据结构试卷C.doc》由会员分享，可在线阅读，更多相关《数据结构试卷C.doc（8页珍藏版）》请在三一文库上搜索。
1、数据结构试卷C数据结构试卷（一）一、单选题（每题 分,共20分)1. 栈和队列的共同特点是( )。.只允许在端点处插入和删除元素B.都是先进后出C都是先进先出D.没有共同点2. 用链接方式存储的队列，在进行插入运算时(). 仅修改头指针 B. 头、尾指针都要修改仅修改尾指针 D.头、尾指针可能都要修改. 以下数据结构中哪一个是非线性结构?( ). 队列 B栈 . 线性表 D. 二叉树4 设有一个二维数组mn，假设0存放位置在644(0)，A22存放位置在6(10),每个元素占一个空间，问33(0)存放在什么位置?脚注(10)表示用10进制表示。A68 68 C.692 D.665. 树最适合用
2、来表示( )。A.有序数据元素 .无序数据元素C.元素之间具有分支层次关系的数据 .元素之间无联系的数据6. 二叉树的第k层的结点数最多为( )-1 A-1 B.K+1 .21 .7 若有18个元素的有序表存放在一维数组A19中,第一个元素放A1中,现进行二分查找,则查找的比较序列的下标依次为( )A. 1，3 . 9,，3C. 9,5， . 9，4，2，38 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为. O(1） B. O（n） C. (1on） O（n2）9. 对于线性表（7，4，55,2,64,，20，10)进行散列存储时,若选用（K）=K %9作为散列函数,则散列地址为1
3、的元素有( ）个,A B.2 C D.4. 设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图。A. .6 C.7 D.8二、填空题(每空1分，共26分）. 通常从四个方面评价算法的质量:_、_、_和_。2.一个算法的时间复杂度为(n3+nlog2+14）/n2，其数量级表示为_。3.假定一棵树的广义表表示为A(C，（,F,G）,H（I,J）,则树中所含的结点数为_个，树的深度为_，树的度为_。4. 后缀算式9 2 +-10 /的值为_。中缀算式(3+)-2/对应的后缀算式为_。5 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中,
4、个结点的二叉树共有_个指针域，其中有_个指针域是存放了地址，有_个指针是空指针。6 对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,所含边结点分别有_个和_个。7. O网是一种_的图。8.在一个具有n个顶点的无向完全图中，包含有_条边,在一个具有n个顶点的有向完全图中,包含有_条边。9. 假定一个线性表为（12,23，74,55,0)，若按ey 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为_、_、_和_。10. 向一棵B树插入元素的过程中,若最终引起树根结点的分裂，则新树比原树的高度_。11. 在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为
5、_，整个堆排序过程的时间复杂度为_。2 在快速排序、堆排序、归并排序中，_排序是稳定的。三、计算题(每题 分，共2分)1.在如下数组A中链接存储了一个线性表,表头指针为A .ext,试写出该线性表。dat x 2. 已知一个图的顶点集V和边集E分别为：V=1,3,4,5,6,；E=（1,2）3，（1,3）5,(,4)8,(,)10,（2，3),(3,4）1，(3，5）1,(3,6),(4,6)4，（,）0,(,6)8，(6,7)25;用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边。. 画出向小根堆中加入数据, 2， ,8,3时，每加入一个数据后堆的变化。四、阅读算法(每题
6、7分,共14分) LinkLit mnote(nit L)/L是不带头结点的单链表的头指针i(L&L-ex）q=L;=L-next；p=；S： hie（p-nx) =pn；S2: p-next=q;qxtULL；retun L；请回答下列问题:（1）说明语句S1的功能;(2）说明语句组S2的功能；（)设链表表示的线性表为(a1,2, ?,n）,写出算法执行后的返回值所表示的线性表。2. voidABC(BTNo * BT)if BTBC(B-eft）;BC （BT-rgt)；otatadata)iem=BST-data;查找成功rer_;ese if（itmdata)retun Fin(_,i
7、tm）； lse eurn Find(_,iem); /i六、编写算法(共8分）统计出单链表HL中结点的值等于给定值X的结点数。 int CoutX(LNoe HL，ElemTye)数据结构试卷(一）参考答案一、选择题（每题2分,共20分)1.A2.D 3.D456D7.D .C 9. 1A二、填空题（每空分，共26分)1 正确性 易读性 强壮性 高效率2. (n）3. 9 3 34. 1 3 4 * +2 Y * 3 -5. 2n n1 +16.e 2. 有向无回路.n(n-1)/ n（-1)9.(，40) （ ) (7） (2，55，63）10.增加11.(g2) O(nlog2).归并三
8、、计算题(每题6分，共24分)1.线性表为：（7，50,40,60，3,90)?0?1?1?02. 邻接矩阵:?110?001?？101?0101？11?邻接表如图1所示:图1 用克鲁斯卡尔算法得到的最小生成树为:(1,2)3, (4，)， (1,3)5, （1,4), （,5)10, (4,7）24 见图226四、读算法（每题7分,共14分)1.（1)查询链表的尾结点（2)将第一个结点链接到链表的尾部，作为新的尾结点(3)返回的线性表为(a2,3,？，n,a1)2 递归地后序遍历链式存储的二叉树。五、法填空（每空2分，共8 分)true BST-left BST-rght六、编写算法(8分)n ounX(LNod* HL,lemType ） int =; Lode*p=HL;/i为计数器hile(p!NULL) if (P-data=）i;ppnx;/while, 出循环时i中的值即为结点个数reun i;/CuntX