2022年专升本十套数据结构试题及答案.doc

数据构造试卷（一）
一、单选题（每题 2 分，共20分）
栈和队列共同特点是( )。




用链接方式存储队列，在进行插入运算时( ).
A. 仅修改头指针 　 B. 头、尾指针都要修改
C. 仅修改尾指针 、尾指针也许都要修改
如下数据构造中哪一种是非线性构造？( )
A. 队列 　　 B. 栈 C. 线性表 　　 D. 二叉树
设有一种二维数组A[m][n]，假设A[0][0]存储位置在644(10)，A[2][2]存储位置在676(10)，每个元素占一种空间，问A[3][3](10)存储在什么位置？脚注(10)表达用10进制表达。
A．688 B．678 C．692 D．696
树最适合用来表达( )。


二叉树第k层结点数最多为( ).
A．2k-1 +1 -1 　　　D. 2k-1
若有18个元素有序表存储在一维数组A[19]中，第一种元素放A[1]中，现进行二分查找，则查找A［3］比较序列下标依次为( )
A. 1，2，3 B. 9，5，2，3
C. 9，5，3 D. 9，4，2，3
对n个记录文献进行迅速排序，所需要辅助存储空间大体为
A. O（1） 　　B. O（n）　　 C. O（1og2n） D. O（n2）
对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1元素有（ ）个，
A．1 B．2 C．3 D．4
设有6个结点无向图，该图至少应有( )条边才干保证是一种连通图。

二、填空题（每空1分，共26分）
普通从四个方面评价算法质量：_________、_________、_________和_________。
一种算法时间复杂度为(n3+n2log2n+14n)/n2，其数量级表达为________。
假定一棵树广义表表达为A（C，D（E，F，G），H（I，J）），则树中所含结点数为__________个，树深度为___________，树度为_________。
后缀算式9 2 3 +- 10 2 / -值为__________。中缀算式（3+4X）-2Y/3相应后缀算式为_______________________________。
若用链表存储一棵二叉树时，每个结点除数据域外，尚有指向左孩子和右孩子两个指针。在这种存储构造中，n个结点二叉树共有________个指针域，其中有________个指针域是存储了地址，有________________个指针是空指针。
对于一种具备n个顶点和e条边有向图和无向图，在其相应邻接表中，所含边结点分别有_______个和________个。
AOV网是一种___________________图。
在一种具备n个顶点无向完全图中，包具有________条边，在一种具备n个顶点有向完全图中，包具有________条边。
假定一种线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数元素成为一种子表，则得到四个子表分别为____________________________、___________________、_______________________和__________________________。
向一棵B_树插入元素过程中，若最后引起树根结点分裂，则新树比原树高度___________。
在堆排序过程中，对任一分支结点进行筛运算时间复杂度为________，整个堆排序过程时间复杂度为________。
在迅速排序、堆排序、归并排序中，_________排序是稳定。
三、计算题（每题 6 分，共24分）
在如下数组A中链接存储了一种线性表，表头指针为A [0].next，试写出该线性表