十套数据结构试题及答案

1、数据结构论文(a)一、单一主题(每个问题2分，共20分)1.堆栈和队列的共同特征是(a)。A.只能在端点处插入和删除图元B.都是先进的，出类拔萃的C.都是先进先出D.没有共同点2.链接存储的队列，插入操作时(d)。A.仅修改头指针b .修改头、尾指针C.仅修改尾部指针d .头，尾部指针都可以修改以下哪个数据结构是非线性结构？(d)A.队列b .堆栈c .线性表d .二叉树4.假设二维阵列Amn，A00位于644(10)中，A22位于676(10)中，并且每个元素占用一个空间脚注(10)表示法用小数表示。cA.688b.678c.692d.696树最适合表达(c)。A.排序的数据元素b .无序的

2、数据元素C.元素之间具有分支层次关系的数据d。元素之间未连接的数据二进制树的级别k节点数为最大值(d)。A.2k-1b.2k1 c.2k-1d.2k-17.有18个元素的有序表存储在一维数组A19中，第一个元素放置在A1中，执行二次查找时，查找a 3的比较序列的下标为(c d)A.1、2、3B。9、5、2、3C.9、5、3D。9、4、2、38.快速排序n个记录的文件所需的辅助存储空间大约为cA.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的元素为(c d)。

3、A.1 B.2 C.3 D.410.要成为连接图，必须有至少(a)个边的6个节点的全向图。A.5 B.6 C.7 D.8第二，填写空白问题(每个空白1分，共26分)1.算法的质量通常为_ _ _ _ _ _ _ _ _ _时间的准确性_ _ _ _ _ _ _ _ _ _占用内存_可读性_2.算法的时间复杂性为(n3 n2log2n 14n)/n2，数量级别表示为_ _ _ 3 0 (n)。3.假定一棵树的广义表显示为A(C，D(E，f，g)，H(I，j)，则树中包含的节点数为_ _ _ _ _ _ _ _ 9 _ _ _ _ _ _ _ _ _ _ _ _ _4.后缀表达式9 2 3-10

4、2/-的值为_ _ _ 3 _ _ 1 _ _ _ _。中-最后一个表达式(3 4X)-2Y/3的后缀表达式为_ _ _ _ _ _ _ 34x * 2Y */-_ _ _ _ _ _ _ _ _ _ _ _ 34x5.如果将二进制树存储为关联列表，则除数据字段外，每个节点还具有指向左右子女的两个指针。在此存储结构中，n个节点的二进制树包含_ _ n _ 2n _ _个指针域。其中_ _ _ _ _ n-1 _ _ _ _个指针域是存储地址，_ _ _ _ _ _ _ _ _ 3 _ _ _ n 1 _ _ _ _ _ _ _ _ _个指针域是存储地址6.对于具有n个顶点和e个边的直接和无向图

5、，相应的相邻表中分别包含_ _ _ e 1 _ e _ e _ _个和_ _ _ e 1 _ _ 2e _ _个。7.AOV网络是_ _ _ _ _ _ _ _ _ _ _ _的无直接循环_ _ _ _ _ _ _ _ _的图形。8.没有n个顶点的方向的完整图表包括_ _ n-1 _ n (n-1)/2 _ _条边，而有n个顶点的直接完整图表包括_ _ _ n-1 _ _ n9.假设一个线条画为(12，23，74，55，63，40)， 如果根据关键字% 4条件拆分相同数量的元素以使其成为一个子表，则生成的四个子表将分别为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

6、 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _10.将元素插入到B_树中时，如果最终导致根节点分裂，则新树的高度将比原始树的高度_ _ _ _ _ _ _ _ _ _ _增加1_ _ _ _ _。1.累积排序过程中过滤任何分支节点的时间复杂性为_ _ _ 0(n/2)_ _ O(log2n)_ _ _ _ _，整个堆排序过程的时间复杂性为_0(1)11.在快速排序、排序堆、排序和排序中，_ _ _ _ _ _排序堆_ _ _排序和排序_ _排序稳定。三、

7、计算问题(每题6分，共24分)1.标头指标为A 0。next的线性表格储存为至下一个阵列a的连结。A 0 1 2 3 4 5 6 7数据605078903440下一个3572041a0a3a2a7a1a5a4a0线性表格如下所示：(78、50、40、60、34、90)2.请画出与下图相邻的矩阵和旁边的表。1.相邻矩阵：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最小生成树通

8、过巡航车算法得到，并尝试在最小生成树内按顺序得到的每个边。(1，2) 3，(4，6) 4，(1，3) 5，(1，4) 8，(2，5) 10，(4，7) 204.每次向小根堆中添加数据4、2、5、8、3时，请在添加数据后绘制堆的变化。四、阅读算法(每题7分，共14分)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的功能。确定p中的下一个节点是

9、否为空；如果不是空，则p指向下一个节点查询链接表的结束节点(2)说明语句组S2的功能。将q分配给p中的下一个节点，并将q的下一个节点创建为空指针。将第一个节点链接到链接列表末尾的新尾部节点(3)关联列表表示的线性表(a1、a2、an)，并创建算法运行后返回值表示的线性表。A2、a3、an、a12.void ABC(BTNode * BT)If BtABC(BT-left)；BT-right(ABC)；Coutdata算法是确定是否是整个二叉树递归后遍历链存储的二叉树的功能五、填空算法(共8分)二进制搜索树搜索递归算法：Bool find (b treenode * BST，elemtype i

10、tem)If (BST=NULL)Return false/找不到ElseIf (item=BST-data)item=BST-data；/查找成功Return _ _ _ item _ _ true _ _ _ _ _ _ _Else if(itemdata)return find(_ _ _ _ _ _ _ BST-data _ _ _ _ BST-left _ _ _ _ _ _，item)；else return find(_ _ _ _ _ _ _ item _ _ _ _ BST-right _ _ _ _ _ _ _，item)；/if六、编写算法(共8分)单个链接表HL中的节点

11、值等于指定值x中的节点数。Int CountX(LNode* HL，ElemType x)Int countNode *head，* p；Head=HLp=head-next；标头-资料(If)！=null)While(p-next)if(p-data=x)count；Struct node HLElemtype dataStruct node * next nodeInt 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节点

12、数return I；/CountX数据结构论文(a)参考答案一、选择题(每题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-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分)2.宣城表如下

13、：(78，50，40，60，34，90)3.相邻矩阵：相邻列表如图11所示。图11使用cruise Carl算法获得的最小生成树如下：(1，2) 3，(4，6) 4，(1，3) 5，(1，4) 8，(2，5) 10，(4，7) 20请参阅图124444422255285283452843四、阅读算法(每题7分，共14分)1.(1)查询已连接列表的结束节点(2)将第一个节点作为新尾部节点链接到链接列表的末尾(3)返回的线性表为(a2，a3，an、a1)2.递归重复链存储的二叉树。第五，填空(每球2分，共8分)True BST-left BST-right六、编写算法(8分)Int CountX(

14、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数据结构论文(2)一、选择题(24分)1.定线表格的下一个叙述性错误是()。(a)顺序存储需要占用连续存储空间(b)使用线性表链存储，无需消耗连续存储空间(c)线性表使用链存储以方便插入和删除操作(d)线性表使用顺序存储，以便于实施插入和删除操作2.Huffman树的叶节点总数为m，如果将二进制列表用作存储结构，则此hufman树具有总计()个空指针域。(A) 2m-1(B) 2m(C