计算机考研数据结构试卷一(练习题含答案)

数据结构试卷1一、单一主题1.堆栈和队列的共同特征是()。A.只能在端点处插入和删除图元B.都是先进的，出类拔萃的C.全部先进先出D.没有共同点2.链接存储的队列，插入操作期间()。A.仅修改头指针b .修改头、尾指针C.仅修改尾部指针d .头，尾部指针都可以修改以下哪个数据结构是非线性结构？（）A.队列b .堆栈c .线性表d .二叉树4.假设二维阵列Amn，A00位于644(10)中，A22位于676(10)中，并且每个元素占用一个空间脚注(10)表示法用小数表示。A.688b.678c.692d.696树最适合表示()。A.排序的数据元素b .无序的数据元素C.元素之间具有分支层次关系的数据d。元素之间未连接的数据二进制树的级别k的节点数最大值()。A.2k-1b.2k1 c.2k-1d.2k-17.有18个元素的有序表存储在一维数组A19中，第一个元素放置在A1中，并且当前正在进行辅助查找，则查找a 3的比较序列的下标为()A.1、2、3B。9、5、2、3C.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的元素为()。A.1 B.2 C.3 D.410.具有6个节点的全向图。此图形必须至少有()个边，才能成为连接的图形。A.5 B.6 C.7 D.8二、填空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)， 根据关键字% 4条件将相同数量的元素细分为子表，结果四个子表分别为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ u10.将元素插入到B_树中时，如果根节点发生分裂，则新树将位于原始树的高度_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _11.累积排序过程中过滤任何分支节点所需的时间复杂性是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _12.在快速排序、堆排序、合并排序中，_ _ _ _ _ _ _ _排序稳定。三、计算问题1.标头指标为A 0。next的线性表格储存为至下一个阵列a的连结。A 0 1 2 3 4 5 6 7数据605078903440下一个35720412.请画出与下图相邻的矩阵和旁边的表。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)(3，5) 12，(3，6) 9，(4，6) 4，(4，7) 20，(5，6) 18，(6，7) 25最小生成树通过巡航车算法得到，并尝试在最小生成树内按顺序得到的每个边。4.每次向小根堆中添加数据4、2、5、8、3时，请在添加数据后绘制堆的变化。四、阅读算法1.LinkList mynote(LinkList L)/L是不引导节点的单个链接表的头指针If(LL-next)q=l；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)关联列表表示的线性表(a1、a2、an)，并创建算法运行后返回值表示的线性表。2.void ABC(BTNode * BT)If BtABC(BT-left)；BT-right(ABC)；Coutdata此算法的功能包括：五、填空算法二进制搜索树搜索递归算法：Bool find (b treenode * BST，elemtype item)If (BST=NULL)Return false/找不到ElseIf (item=BST-data)item=BST-data；/查找成功Return _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _Else if(itemdata)return find(_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _，item)；else return find(_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _，item)；/if六、编写算法单个链接表HL中的节点值等于指定值x中的节点数。Int CountX(LNode* HL，ElemType x)答案一、选择题1.A 2 .D 3 .D 4 .C 5 .c6.D 7 .D 8 .C 9 .D 10 .a二、填空1.准确性可读性强，效率高2.O(n)3.9 3 34-1 3 4 x * 2 y * 3/-5.2n-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.回归三、计算问题1.宣城表如下：(78，50，40，60，34，90)2.相邻矩阵：相邻列表如图11所示。图11使用cruise Carl算法获得的最小生成树如下：(1，2) 3，(4，6) 4，(1，3) 5，(1，4) 8，(2，5) 10，(4，7) 20请参阅图124444422255285283452843图12四、阅读算法1.(1)查询已连接列表的结束节点(2)将第一个节点作为新尾部节点链接到链接列表的末尾(3)返回的线性表为(a2，a3，an、a1)2.递归重复链存储的二叉树