1 / 6 北京电子科技学院2010～2011 学年第二学期0952~0953 班数据结构期 末 考 试 试 卷（闭卷）（B 卷）题目一二三四五六七八九十十一十二总分数分数评卷人一、选择题（每小题2 分，共 10 分）1．下述哪一条是顺序存储结构的优点？。A．删除运算方便 B．插入运算方便C．存储密度大 D．可方便地用于各种逻辑结构的存储表示2．若某线性表最常用的操作是取第i 个元素和查找第i 个元素的前驱，则采用以下哪种存储结构最节省时间。A．顺序表B．单链表C．双向链表D．单项循环链表3．在含有 n 个元素的顺序表中，删除一个元素所需移动元素的平均次数为。A．n B．n/2C．(n+1)/2 D．(n-1)/2 4．设指针变量 p 指向单链表结点 A，则删除结点A 的后继结点 B 需要的操作为。A．p=p->next B．p->next=p->next->next C．p=p->next->next D．p->next=p 5. 方法是从未排序序列中挑选元素，并将其依次放入已排序序列中的一端。A．归并排序B．插入排序 C．选择排序D．快速排序二、填空题（每小空2 分，共 20 分）专业________________学号__________________姓名__________________班级____________________密封线2 / 6 1．栈的特点是。2. 设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为front 和 rear，其中队头指针 front 指向当前队头元素的前一个位置，队尾指针rear 指向当前队尾元素所在的位置，则出队列的语句为front =_______________。3. 已知一有向图的邻接表存储结构如下：从顶点1 出发， DFS 遍历的输出序列是__________，BFS 遍历的输出序列是 ______________。4.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF ，则该二叉树的中序遍历序列为 ___________，后序遍历序列为 ___________。5. 设有向图 G 的二元组形式表示为G =（D，R），其中 D={1 ，2，3，4，5}，R={<1,2>， <2,4>，<4,5>，<1,3>，<3,2>，<3,5>} ，则该图的一种拓扑排序序列为 ______________。6. 将一棵有 100 个结点的完全二叉树从根开始，从上到下，从左到右依次对结点进行编号，根结点的编号为1，那么编号为49 的结点其左孩子编号是_____，父亲结点编号是 _____，该完全二叉树的深度是 _______。三、简答题（每小题7 分，共 42 分）1．设计单链表结构时，往往要附设一个头结点，请说明这样做的原因及带来的好处。2. 请解释顺序队列的假溢出现象，以及相应的解决办法。3 / 6 3. 请写出顺...
