交大数据结构012-2013试卷

北 京 交 通 大 学 考 试 试 题 （A卷）

课程名称:数据结构与算法 2012-2013学年第一学期 出题教师:张勇 (请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场) 题号 得分 阅卷人 一 二 三 四 五 六 总分 一、 填空题（每空2分，共20分）

1. 数据的物理结构主要包括_____________和______________两种情况。

2. 设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则

后序遍历该二叉树的序列为_____________。

3. 设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，

r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列__________。

4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子c的运算

是 。

5. 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为

____________。

6. 设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总

共有_______个结点。

7. 设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。

8. 简单选择排序和直接插入排序算法的平均时间复杂度为___________。

二、 选择题（每题2分，共20分）

1. 设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ ）。 (A) head==NULL (B) head->next==NULL (C) head->next==head (D) head!=NULL

2. 设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队

尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（ ）。

(A) front->next=s；front=s； (B) s->next=rear；rear=s； (C) rear->next=s；rear=s； (D) s->next=front；front=s；

3. 设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路

径长度之和为（ ）。 (A) 20 (B) 30 (C) 40 (D) 45

4. 设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个

数分别为（ ）。 (A) n，e (B) e，n (C) 2n，e (D) n，2e

5. 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要

进行（ ）趟的分配和收集才能使得初始关键字序列变成有序序列。 (A) 3 (B) 4 (C) 5 (D) 8

6. 函数substr(“DATASTRUCTURE”，5，9)的返回值为（ ）。 (A) “STRUCTURE” (B) “DATA”

(C) “ASTRUCTUR” (D) “DATASTRUCTURE”

7. 下面程序的时间复杂为（ ）

for（i=1，s=0； i<=n； i++）{t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}

234

(A) O(n) (B) O(n) (C) O(n) (D) O(n)

8. 深度为k的完全二叉树中最少有（ ）个结点。

k-1k-1k-1k

(A) 2-1 (B) 2 (C) 2+1 (D) 2-1

9. 设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为

（ ）。

2

(A) O(n) (B) O(n) (C) O(nlog2n) (D) O(1og2n)

10. 稀疏矩阵是指___ _ (A) 行数，列数和的矩阵 (B) 有少量零元素的矩阵 (C) 有少量非零元素的矩阵 (D) 元素少的矩阵 三、 判断题（每题1分, 共10分）

1. 调用一次深度优先遍历可以访问到图中的所有顶点。（ ） 2. 分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。

（ ）

3. 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（ ） 4. 当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ ）

5. 设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。

（ ）

6. 层次遍历初始堆可以得到一个有序的序列。（ ）

7. 设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（ ） 8. 线性表的顺序存储结构比链式存储结构更好。（ ） 9. 中序遍历二叉排序树可以得到一个有序的序列。（ ） 10. 带权无向图的最小生成树是唯一的。（ ）

四、 应用题（24分）

1.（6分）下图所示的森林：

(1) 求树（a）的先根序列和后根序列； (2) 求森林先序序列和中序序列； （3）将此森林转换为相应的二叉树；

ABD(a)CEFIGHJ(b)K

2．(6分)给定下列图，完成以下问题 （1）画出该图的邻接矩阵和邻接表

（2）根据所画的邻接表，从顶点V0出发，画出图的深度优先搜索树

（3）根据普里姆（Prim）算法，求它的最小生成树（不必写出全部过程，在生成树中标出边生成的次序即可）

v08v2242v6v3756v448v17v58v7 3．（6分）设哈希表HT表长m为13，哈希函数为H(k)=k MOD m，给定的关键值

序列为{19,14,23,10,68,20,84,27,55,11}。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL。

4.（6分）将序列（10，18，4，3，6，12，1，9，18+，8）中的关键字按升序重新排列，请写出

（1）冒泡排序一趟扫描的结果

（2）以第一个元素为分界点的快速排序一趟扫描的结果 （3）希尔排序每趟的排序结果（增量为5，3，1） （4）堆排序所建的初始堆和第一趟排序结果。

五、 程序阅读题（10分）

1．（5分）阅读下面的算法

LinkList mynote(LinkList L)

{//L是不带头结点的单链表的头指针 if(L&&L->next){

q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； }

return L； }

请回答下列问题：

（1）说明语句S1的功能； （2）说明语句组S2的功能；

（3）设链表表示的线性表为（a1,a2, ?,an）,写出算法执行后的返回值所表示的线性表。

2. （5分）已知二叉树的存储结构为二叉链表，阅读下面算法。

typedef struct node { DateType data； Struct node * next； }ListNode；

typedef ListNode * LinkList ； LinkList Leafhead=NULL； void Inorder (BinTree T) {

LinkList s； if(T){

Inorder(T－>lchild)；

if ((!T－>lchild)&&(!T－>rchild)){

s=(ListNode*)malloc(sizeof(ListNode))； s－>data=T－>data；

s－>next=Leafhead； Leafhead=s； }

Inorder(T－>rchild)； } }

对于如下所示的二叉树

（1）画出执行上述算法后所建立的结构；

（2）说明该算法的功能。

六、 算法设计题（16分）

算法书写要求：应简单阐述算法的主要思想，对关键变量和关键语句进行注释；如果为递归算法，则应说明递归调用的初始条件，否则扣分。写出正确的设计思想和伪代码可以酌情给分。

如果算法中用到堆栈，可直接调用下列操作： InitStack(S): 栈初始化

push(S,x): 将元素x推入栈S；（插入） pop(S,x): 将栈顶元素存入变量x中；（删除）

StackEmpty(S): 判别栈S是否为空，如果是，返回1，否则返回0

如果算法中用到队列，可直接调用下列操作： InitQueue(Q): 队列初始化

EnQueue(Q,x): 将元素x加入队列Q；（插入） DeQueue(Q,x): 取出队头元素，放入变量x中；（删除）

QueueEmpty(Q): 判别队列Q是否为空，如果是，返回1，否则返回0

1.（8分）下列题中任选一题

（1）设有一个由正整数序列组成的有序单链表（递增有序，且允许有相等的整数存在），试编写算法，确定在序列中比正整数x大的数有几个（相同的数只计算一次，如序列{20, 20, 17,16,15,15,11,10,8,7,7,5,4}）中比10大的整数有5个；） （2）设计在单链表中删除值相同的多余结点的算法； （3）设计在单链表上实现简单选择排序算法。

链表结构定义为： typedef struct Lnode{

ElemType data; struct Lnode *next; }LNode, *LinkList;

2. (8分) 下列题中任选一题 （1）设计一个求结点x在二叉树T中的双亲结点算法。若没有值为x的结点或没有双亲结点，分别打印出相应的信息；若结点x有双亲，打印其双亲结点的值。 （2）二叉树按二叉链表形式存储，编写一个算法判别给定的二叉树是否为完全二叉树。

（3）在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增顺序打印结点的数据域，要求相同的数据元素仅输出一个，算法还能报出最后被滤掉而未输出的数据元素个数。对如下图所示的二叉排序树，输出为10,12,13,15,18,21,27,35,42, 滤掉3个元素。

181310121518182721273542

二叉树T采用如下定义的存储结构： typedef struct BiTNode {

TElemType data;

struct BiTNode *lchild, *rchild; }BiTNode, *BiTree;

链表结构定义为： typedef struct Lnode{

ElemType data; struct Lnode *next; }LNode, *LinkList;

2. (8分) 下列题中任选一题 （1）设计一个求结点x在二叉树T中的双亲结点算法。若没有值为x的结点或没有双亲结点，分别打印出相应的信息；若结点x有双亲，打印其双亲结点的值。 （2）二叉树按二叉链表形式存储，编写一个算法判别给定的二叉树是否为完全二叉树。

（3）在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增顺序打印结点的数据域，要求相同的数据元素仅输出一个，算法还能报出最后被滤掉而未输出的数据元素个数。对如下图所示的二叉排序树，输出为10,12,13,15,18,21,27,35,42, 滤掉3个元素。

181310121518182721273542

二叉树T采用如下定义的存储结构： typedef struct BiTNode {

TElemType data;

struct BiTNode *lchild, *rchild; }BiTNode, *BiTree;

本文来源：https://www.bwwdw.com/article/xdt8.html