20122013安徽大学《数据结构》期末试卷
一、单项选择题，在括号内填写所选择的标号（每小题1分，共12分）1下面程序段的时间复杂度为。fori
ti0imifori
tj0j
jaijij22AOmBO
COm
DOm
2在二维数组中，每个数组元素同时处于（）个向量中。A0个B1个C2个D
个3设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。A求子串B模式匹配C串替换D串连接4利用双向链表作线性表的存储结构的优点是（）。A便于单向进行插入和删除的操作B便于双向进行插入和删除的操作C节省空间D便于销毁结构释放空间5设链式栈中结点的结构为（datali
k），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行操作。Atopli
ksBsli
ktopli
ktopli
ksCsli
ktoptopsDsli
ktoptoptopli
k6设有一个递归算法如下i
tXi
t
if
3retur
1elseretur
X
2X
41试问计算XX5时需要调用（）次X函数。A．2B．3C．4D．57一棵具有35个结点的完全二叉树的高度为。假定空树的高度为1。A5B6C7D88向具有
个结点的堆中插入一个新元素的时间复杂度为。AO1BO
COlog2
DO
log2
9在一棵AVL树中，每个结点的平衡因子的取值范围是。A11B22C12D0110一个有
个顶点和
条边的无向图一定是。A．连通的B．不连通的C．无环的D．有环的11在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助结构，判断一条边的两个端点是否在同一个连通分量上。A位向量B堆C并查集D生成树顶点集合12设有一个含有200个元素的表待散列存储，用线性探查法解决冲突，按关键码查询时找到一个元素的平均探查次数不能超过15，则散列表的长度应至少为（）。（注：平均探查次数的计算公式为S
l111α2其中α为装填因子）A400B526C624D676二、填空题，在横线处填写合适内容（每小题1分，共12分）1数据结构的逻辑结构包括线性结构和________结构两大类。
f2在程序运行过程中不能扩充的数组是__________分配的数组。这种数组在声明它时必须指定它的大小。3链表只适用于查找。4设双向循环链表中每个结点的结构为datalli
krli
k则结点p的前驱结点的地址为__________。5在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有________个结点。6一棵树的广义表表示为abcdefghijkxy，结点k的所有祖先的结点r