《数据结构试题二及答案》由会员分享，可在线阅读，更多相关《数据结构试题二及答案（49页珍藏版）》请在金锄头文库上搜索。
1、吉首大学试题库一、单选题（每题2分，共20分）1. 1.栈和队列的共同特点是（）。A. 只允许在端点处插入和删除元素B. 都是先进后出C. 都是先进先出D. 没有共同点2. 2.用链接方式存储的队列，在进行插入运算时（）.A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3. 3.以下数据结构中哪一个是非线性结构？（）A.队列B.栈 C.线性表 D.二叉树4. 4.设有一个二维数组Amn，假设A00存放位置在644（10），A22存放位置在676，每个 元素占一个空间，问A33（10）存放在什么位置？脚注（10）表示用10进制表示。A. 688B. 678 C.
2、692D. 6965. 5.树最适合用来表示（）。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6. 6.二叉树的第k层的结点数最多为（）.A. 2k-1B.2K+1C.2K-1D. 2k-17. 7. 若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A 3的比较序列的下标依次为（）A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38. 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O （1）B. O （n）C. O （1og2n）D. O （n2）9. 9. 对于线性
3、表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H （K） =K %9 作为散列函数，则散列地址为1的元素有（）个，A.1B.2C.3D.410. 10.设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。A.5B.6C.7D.8填空题（每空1分，共26分）1. 1.通常从四个方面评价算法的质量：正确性_、_易读性_、强壮性和时间复杂_。2. 2.一个算法的高效率度为（疽+2典2+1物）/泌，其数量级表示为。3. 3,假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J），则树中所含的结点数为9_个，树的深度为_3，树的度为_3_。4. 4, 后缀算
4、式9 2 3 +- 10 2 / -的值为。中缀算式（3+4X）-2Y/3对应的后缀算式为5. 5,若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有_2n个指针域，其中有_n-1_个指针域是存放了地址，有 n+1_个指针是空指针。6. 6,对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_e_个和2e_个。7. 7.AOV网是一种有向无回路 的图。8. 8,在一个具有n个顶点的无向完全图中，包含有_n（n-1）/2_条边，在一个具有n个顶点的有向完全图中，包含有_n（n-1）_条边。9. 9
5、,假定一个线性表为（12,23,74,55,63,40），若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为12,40_、无_、74和23, 55, 63_。10. 10.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度。11. 11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为，整个堆排序过程的 时间复杂度为。12. 12.在快速排序、堆排序、归并排序中，排序是稳定的。三、三、运算题（每题6分，共24分）1.1.在如下数组A中链接存储了一个线性表，表头指针为A 0.next，试写出该线性表。V=1,2,3,4,5,6,
6、7;4.4.四、四、阅读算法（每题7分，共14分）次得到的各条边。画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。1. 1. LinkList mynote（LinkList L）/L是不带头结点的单链表的头指针if(L&L-next)q=L； L=L next； p=L；S1：while(p next) p=p next ；S2：p next=q； q next=NULL； return L； 请回答下列问题：(1) 说明语句S1的功能；(2) 说明语句组S2的功能；(3) 设链表表示的线性表为(气以2,an)，写出算法执行后的返回值所表示的线性表。2. 2.
7、void ABC(BTNode * BT) if BT ABC (BT-left);ABC (BT-right);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)panda参考答案一、1.A2.D一、3.D 4.C5.C四、1.1.2.3.4.5.6.7.8.9.10.11.12.1.2.3.4.5.
8、6.7.8.9.10.11.12.正确性 O(n) 9 -1 2n en-12e1.1.2.2.单选题(每题2分，共20分)6.D 7.D8.C9.D10.A填空题(每空1分，共26分) 易读性强壮性高效率33 4 X * + 2 Y * 3 / - n+1有向无回路 n(n-1)/2 (12， 40) 增加1 O(log2n) 归并renlu 二 、线性表为：邻接矩阵:n(n-1)()O(nlog2n)(78,0运算题501401(74)(23,55, 63)(每题6分，共24分)60134， 90)图11 用克鲁斯卡尔算法得到的最小生成树为： (4,6)4, (1,3)5, (1,4)8,
9、 (2,5)10, 见图123. 3.(1,2)3,4. 4.Cd1.四、(1)查询链表的尾结点图12法(每题7分，共14分)(4,7)20（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a ,a ,a,a ）2 3 n 12. 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;
10、/while,出循环时i中的值即为x结点个数return i;/CountX吉首大学试题库super一、一、 单选题（每小题2分，共8分）1、 1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为（）。A nB n/2 C （n+1）/2 D （n-1）/22、 2、在一个单链表中，若q所指结点是p所指结点的前驱结点，若在q与p之间插入一个s所指的结点，则 执行（）。Asf link=pf link;pf link=s;Bpf link=s;slink=q;Cpflink=sflink;sflink=p;D
11、q flink=s;sflink =p;3、3、栈的插入和删除操作在（）进行。A栈顶 B栈底 C任意位置D指定位置4、4、由权值分别为11，8, 6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A 24 B 71 C 48D 53二、二、 填空题（每空1分，共32分）1、 1、数据的逻辑结构被分为、和 四种。2、 2、一种抽象数据类型包括 和 两个部分。则该线性表为3、3、在下面的数组a中链接存储着一个线性表，表头指针为ao,nexta0 123456786056423874254376201datanext4、4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表
12、为空的条件分别为 和。5、5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的，该循环队列的最大长度为。6、 6、当堆栈采用顺序存储结构时，栈顶元素的值可用表示；当堆栈采用链接存储结构时，栈顶元素的值可用 表示。7、 7、一棵高度为5的二叉树中最少含有 个结点，最多含有 个结点；一棵高度为5的理想平衡树中，最少含有 个结点，最多含有 个结点。8、 8、在图的邻接表中，每个结点被称为，通常它包含三个域：一是； 二是；三是。9、 9、在一个索引文件的索引表中，每个索引项包含对应记录的_和 两项数据。10、 10、假定一棵树的广义表表示为A（B（C，D（E，F，G），H（I，
13、J），则树中所含的结点数为 个，树的深度为，树的度为,结点H的双亲结点为,孩子结点为。11、 11、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为，整个堆排 序过程的时间复杂度为。12、12、 在对m阶的B_树插入元素的过程中，每向一个结点插入一个索引项（叶子结点中的索引项为关键字和空指针）后，若该结点的索引项数等于 个，则必须把它分裂为个结点。三、运算题（每小题6分，共24分）1、1、已知一组记录的排序码为（46, 79, 56, 38, 40，80, 95, 24），写出对其进行快速排序的每 一次划分结果。2、 2、一个线性表为 B=（12，23, 45, 57, 20, 03, 78，31, 15, 36），设散列表为 HT0.,12，散 列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查 找成功的平均查找长度。3、3、已知一棵二叉树的前
