数据结构的试题及答案
一、单项选择题（每题2分，共10题）
1.数据结构中，与所使用的计算机无关的是数据的（）结构。
A.存储B.物理C.逻辑D.物理和存储
答案：C
2.在一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要向前移动（）个元素。
A.n-iB.n-i+1C.iD.i-1
答案：A
3.链表不具有的特点是（）。
A.可随机访问任一元素
B.插入、删除不需要移动元素
C.不必事先估计存储空间
D.所需空间与线性表长度成正比
答案：A
4.栈和队列的共同特点是（）。
A.都是先进后出
B.都是先进先出
C.只允许在端点处插入和删除元素
D.没有共同点
答案：C
5.设串s1=abcdefg，s2=pqrst，执行concat(s1,s2)操作后的结果是（）。
A.abcdefgpqrstB.pqrstabcdefgC.abcdefgD.pqrst
答案：A
6.二叉树第i（i≥1）层上至多有（）个结点。
A.2^iB.2^(i-1)C.2iD.2i-1
答案：B
7.具有n个结点的完全二叉树的深度为（）。
A.?log?n?B.?log?n?C.?log?(n+1)?D.?log?(n+1)?
答案：B
8.对n个记录的文件进行快速排序，所需要的辅助存储空间平均为（）。
A.O(1)B.O(n)C.O(log?n)D.O(n2)
答案：C
9.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较次数为（）。
A.1B.2C.3D.4
答案：B
10.散列表的地址区间为0-17，散列函数为H（K）=Kmod17。采用线性探测法处理冲突，并将关键字集合{26，25，72，38，8，18，59}依次存储到散列表中。元素59存放在散列表中的地址是（）。
A.11B.12C.13D.14
答案：A
二、多项选择题（每题2分，共10题）
1.以下属于线性结构的有（）。
A.队列B.栈C.线性表D.树E.图
答案：ABC
2.顺序表的优点包括（）。
A.存储密度大
B.可以随机访问
C.插入、删除操作方便
D.无需为表示结点间的逻辑关系而增加额外的存储空间
E.方便扩容
答案：ABD
3.以下关于链表的说法正确的是（）。
A.带头结点的链表在进行插入、删除操作时更方便
B.双向链表可以方便地进行双向遍历
C.循环链表最后一个结点的指针域指向头结点（带头结点的情况）
D.链表的存储密度小于顺序表
E.单链表只能从头结点开始遍历
答案：ABCD
4.栈的应用包括（）。
A.函数调用B.表达式求值C.括号匹配D.迷宫求解E.二叉树遍历
答案：ABC
5.队列的基本操作有（）。
A.入队B.出队C.取队首元素D.判断队列是否为空E.遍历队列
答案：ABCD
6.二叉树的遍历方式有（）。
A.先序遍历B.中序遍历C.后序遍历D.层次遍历E.逆序遍历
答案：ABCD
7.以下关于图的说法正确的是（）。
A.图有有向图和无向图之分
B.图中的边可以有权值
C.图的存储结构有邻接矩阵和邻接表等
D.图的遍历方式有深度优先遍历和广度优先遍历
E.图中顶点的个数不能为0
答案：ABCD
8.以下关于排序算法的说法正确的是（）。
A.冒泡排序是稳定的排序算法
B.快速排序是不稳定的排序算法
C.归并排序的时间复杂度为O(nlog?n)
D.直接插入排序的最好情况时间复杂度为O(n)
E.选择排序的时间复杂度为O(n2)
答案：ABCDE
9.以下关于散列函数的说法正确的是（）。
A.散列函数的值域必须在散列表的地址范围内
B.理想的散列函数应使计算出的地址分布均匀