数据结构试题
一、选择题
1，栈和队列的* *是相同的特性(？)。
A.只允许在端点插入和删除元素？
b .都是先入后出？
c .都是先入先出？
D.没有* * *共同点
参考答案是:a。
2.插入由link()存储的队列时。
A.只修改头指针。
B.头尾指针都要修改？
C.只修改尾指针？
D.头指针和尾指针都需要修改。
参考答案是:d。
3.下列哪种数据结构是非线性的？( )
A.长队
B.堆
C.线性表？
D.二叉树
参考答案是:d。
4.有一个二维数组A[m][n]。假设A[0][0]存储在644(10)，A[2][2]存储在676(10)，每个元素占用一个空间，问A [3] [3]。
脚注(10)用10表示。
A.688
B.678
C.692
公元696年
参考答案是:c。
5、树最适合表示(？)。
A.有序数据元素？
B.无序数据元素
C.元素间具有分支层次关系的数据
D.元素之间没有联系的数据
参考答案是:c。
6.二叉树第k层的最大节点数是(？).
A.2k-1？
B.2K+1
C.2K-1？
D.2k-1
参考答案是:d。
7.如果一个有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
参考答案是:d。
8.快速排序N个记录文件，所需辅助存储空间大致为(？)
A.O(1)
B.O(n)？
C.O(1og2n)？
D.氧气(氮气)
参考答案是:c。
9.线性表(7，34，55，25，64，46，20，10)哈希时，如果选择H(K)= K %9作为哈希函数，哈希地址为1的元素有()个。
A.1？
B.2？
C.3？
丁四
参考答案是:d。
10，一个有6个节点的无向图，应该至少有(？)来保证它是一个连通图。
A.5？
B.6？
C7
D.8
参考答案是:a。
第二，填空
1.一般从四个方面评价算法的好坏:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。
参考答案是:
正确性、可读性、健壮性和高效性
2.一个算法的时间复杂度是(n3+n2log2n+14n)/n2，其数量级是_ _ _ _ _ _ _ _ _。
参考答案是:
O(n)
3.假设一棵树的广义表表示为A(C，D(E，f，g)和H(I，j))，则该树的节点数为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
参考答案是:
9 3 3
4.后缀formula 9 2 3+-10 2/-的值是_ _ _ _ _ _ _ _。中缀公式(3+4X)-2Y/3对应的后缀公式是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _。
参考答案是:
-1 ?3 4 X * + 2 Y * 3 / -
5.如果二叉树存储在链表中，每个节点除了数据字段之外，还有两个指向左子节点和右子节点的指针。在这种存储结构中，有n个节点的二叉树* * *
有_ _ _ _ _ _ _ _个指针字段，其中_ _ _ _ _ _ _ _个指针字段存储了地址，而_ _ _ _ _ _ _ _ _ _ _个指针为空。
参考答案是:
2n n-1 n+1
6.对于一个有向图和一个有n个顶点和e条边的无向图，它们对应的邻接表中有_ _ _ _ _ _个和_ _ _ _ _ _个边节点。
参考答案是:
e 2e
7.AOV网络是一个_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。
参考答案是:
有向无环
8.n个顶点的无向完全图包含_ _ _ _ _ _条边，n个顶点的有向完全图包含_ _ _ _ _ _ _条边。
参考答案是:
n(n-1)/2 n(n-1)
9.假设一个线性表为(12，23，74，55，63，40)，如果按照Key% 4条件划分，使余数相同的元素成为一个子表，得到的四个子表如下。
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _和。
参考答案是:
(12,40) ( ) (74) (23,55,63)
10.在向B_ tree中插入元素的过程中，如果根节点最终被拆分，则新树的高度为_ _ _ _ _ _ _ _ _ _。
参考答案是:
增加1
11.在堆排序过程中，筛选任意一个分支节点的时间复杂度为_ _ _ _ _ _ _ _ _，整个堆排序过程的时间复杂度为_ _ _ _ _ _ _ _ _。
参考答案是:
O(log2n) O(nlog2n)
12.在快速排序、堆排序和归并排序中，_ _ _ _ _ _ _排序是稳定的。
参考答案是:
并入